Московский государственный университет имени М.В. Ломоносова
Факультет вычислительной математики и кибернетики
На правах рукописи
Игнатенко Алексей Викторович
МЕТОДЫ ИНТЕРАКТИВНОЙ ВИЗУАЛИЗАЦИИ И ОБРАБОТКИ
ТРЕХМЕРНЫХ ДАННЫХ НА ОСНОВЕ ИЗОБРАЖЕНИЙ
Специальность 05.13.11 – «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей»
Автореферат диссертации на соискание учёной степени кандидата физико-математических наук
Москва – 2005
Работа выполнена на кафедре Автоматизации Систем Вычислительных Комплексов факультета ВМиК МГУ
Научный руководитель: Кандидат физико-математических наук Баяковский Ю.М.
Официальные оппоненты: Доктор физико-математических наук Михайлюк М.В.
Кандидат физико-математических наук Березин С.Б.
Ведущая организация: Институт Системного Программирования РАН
Защита диссертации состоится «»2005г. в _ часов на заседании диссертационного совета Д 501.001.44 в Московском государственном университете им. М.В. Ломоносова по адресу: 119992, ГСП-2, Москва, Ленинские горы, МГУ, 2-й учебный корпус, факультет ВМиК, аудитория 685.
С диссертационной работой можно ознакомиться в библиотеке факультета ВМиК МГУ.
Автореферат разослан «» 2005г.
Ученый секретарь диссертационного совета, кандидат физикоматематических наук, профессор Н.П. Трифонов
Общая характеристика работы
Объект исследований и актуальность темы Одна из основных задач в области разработки человеко-машинных интерфейсов – это задача синтеза изображений трехмерных геометрических моделей. В настоящее время особую актуальность приобретают задачи, связанные с алгоритмами интерактивного синтеза изображений объектов реального мира.
Эти алгоритмы находят свое применение во многих прикладных областях, таких как автоматизированное проектирование, медицина, археология, мультимедийные, образовательные приложения, виртуальная реальность.
Процесс синтеза изображений трехмерной модели называется экранизацией (rendering). Традиционный процесс экранизации состоит из нескольких этапов:
создание геометрической модели, моделирование материалов и условий освещения, синтез проекции модели для заданных параметров виртуальной камеры, растеризация геометрии, вычисление цвета пикселей результирующего изображения с учетом модели освещения.
Для реальных объектов входными данными для создания модели, как правило, являются цифровые фотографии, видеопоследовательности или карты дальности (глубины), получаемые с помощью специальных дальномерных устройств, позволяющих вводить в компьютер данные о форме интересующего объекта.
Представлением (representation) трехмерных данных будем называть класс (тип) цифровых трехмерных моделей, обладающих схожими признаками (структурой данных, свойствами и т.п.). Наиболее распространенным представлением трехмерных данных, используемым в интерактивной трехмерной графике, является граничное полигональное представление. Такое представление задает кусочно-линейную аппроксимацию поверхности объекта с помощью набора полигонов.
Современные системы экранизации реальных объектов реконструируют из входных данных поверхность объекта, создают модель в граничном представлении и экранизируют уже ее. Такая схема хорошо работает для синтетических, созданных вручную моделей и достаточно простых моделей освещения.
Однако для экранизации моделей объектов реального мира традиционный процесс недостаточно эффективен по следующим причинам:
• Для полигонального представления необходима полная реконструкция поверхности, провести которую автоматически для исходных данных в виде фотографий или видеопоследовательностей затруднительно или невозможно, а ручная реконструкция является чрезвычайно трудоемкой.
• Модели реального мира обычно имеют высокую детализацию и сложную форму, поэтому требуют огромного количества полигонов для качественной аппроксимации. Также проблемой является оптическая сложность – это сложность модели материала и освещения. На данный момент используемые в интерактивной экранизации модели материалов и освещения достаточно просты и не полностью передают свойства реальной поверхности. Использование более сложных моделей ограничено требованием интерактивности.
• В последнее время становится все более актуальной задача адаптации сложных данных для их экранизации на маломощных устройствах – например, наладонных компьютерах или мобильных телефонах. Для полигональных моделей решение этих задач связано с большими вычислительными затратами, что может быть неприемлемо для маломощных устройств.
Таким образом, чрезвычайно актуальной является задача исследования альтернативных представлений и методов экранизации, адаптированных под реальные данные.
В рамках диссертационной работы исследуется идея прямого использования входных данных о реальных объектах в качестве модели для экранизации. Поскольку на входе и выходе алгоритма экранизации находятся изображения объектов в том или ином виде, прямое использование изображений в качестве модели может преодолеть недостатки традиционного графического процесса.
В диссертации анализируются трехмерные представления на основе изображений. Рассматривается задача адаптации данных в этих представлениях, показывается их эффективность для решения этой задачи.
Цели работы • Исследование представлений трехмерных объектов на основе изображений, алгоритмов их обработки и экранизации.
• Разработка представления трехмерных данных на основе изображений, позволяющего эффективно хранить, передавать по сети и визуализировать трехмерные модели. Разработка алгоритмов обработки и синтеза изображений для этого представления.
• Исследование применимости представлений на основе изображений к задаче адаптации трехмерных данных для интерактивного показа на маломощных устройствах (карманных компьютерах, мобильных телефонах). Разработка эффективных методов экранизации трехмерных данных высокой сложности на маломощных устройствах.
Научная новизна работы • Предложено новое представление трехмерных данных на основе изображений, позволяющее эффективно хранить, передавать по сети и экранизировать трехмерные модели. Также предложены методы обработки моделей в этом представлении.
• Разработан алгоритм многомасштабной экранизации предложенного представления, обеспечивающий более высокую скорость экранизации по сравнению с известными алгоритмами.
• Предложен новый алгоритм клиент-серверной экранизации потока трехмерных данных, ориентированный на мобильные клиентские устройства (включая карманные ПК) в условиях низкой пропускной способности сети.
Практическая значимость и реализация Разработаны и доведены до реализации методы и алгоритмы решения актуальных задач компьютерной графики. Программные реализации описываемых в диссертации методов удовлетворяют требованиям и ограничениям, сформулированным в постановке задачи.
На основе предложенного представления трехмерных данных разработана спецификация формата данных, которая была включена в международный стандарт MPEG-4 AFX (Animated Framework Extension). Часть разработанных алгоритмов экранизации вошла в пакет стандартного программного обеспечения MPEG-4 AFX.
Разработана программная система Visual Framework, в рамках которой разрабатывались алгоритмы экранизации, а также клиент-серверная система экранизации потока трехмерных данных. Система предназначена для анализа различных методов представления и экранизации трехмерных данных. Компонентная архитектура системы позволяет добавлять новые форматы данных, представления и алгоритмы экранизации без изменения существующего кода.
Система Visual Framework используется в учебном и научном процессе в лаборатории компьютерной графики и мультимедиа на факультете ВМиК МГУ для обучения методам экранизации по изображениям и разработки новых алгоритмов.
По тематике разработанных методов и алгоритмов, в рамках курса компьютерной графики, который читается на 2-м курсе факультета ВМиК МГУ, было подготовлено практическое задание (http://graphics.cs.msu.su/courses/cg02b/assigns/hw-6/hw6.html).
Также было подготовлено учебное пособие по графической библиотеке OpenGL, которая использовалась для реализации разработанных алгоритмов (Ю. Баяковский, А. Игнатенко, А. Фролов, Графическая библиотека OpenGL.
2003, Москва: Издательский отдел факультета Вычислительной Математики и Кибернетики МГУ им. М.В. Ломоносова, 132с).
Апробация работы и публикации Результаты работы докладывались и обсуждались на:
• 13-й международной конференции по компьютерной графике и машинному зрению GraphiCon 2003, “A Framework for Depth Image-Based Modeling and Rendering” («Система для экранизации и моделирования на основе изображений с глубиной»), Россия, Москва, 2003.
• 14-й международной конференции по компьютерной графике и машинному зрению GraphiCon 2004, “A Real-Time 3D Rendering System with BRDF Materials and Natural Lighting” («Система интерактивной визуализации с поддержкой материалов с ДФОС и природным освещением»), Россия, Москва, 2004.
• Международной конференции по обработке изображений ICIP (International Conference on Image Processing), “Depth Image-based Representations for static and animated 3D objects” («Представление на основе изображений с глубиной для статических и анимированных трехмерных объектов»), США, Нью-Йорк, 2002.
• Семинаре по компьютерной графике и мультимедиа под руководством Ю.М. Баяковского (ф-т ВМиК МГУ).
• Научно-исследовательском семинаре по автоматизации программирования под руководством проф. М.Р. Шура-Бура (ф-т ВМиК МГУ).
По тематике диссертации получено четыре международных патента.
Объем и структура работы Диссертация состоит из введения, четырех глав, заключения, приложения и списка литературы. Содержание работы изложено на 148 страницах. Список литературы включает 96 наименований.
Краткое содержание работы Во введении формулируются цели и задачи диссертации, обосновывается ее актуальность, научная новизна и практическая значимость, кратко излагается содержание работы.
В первой главе приводится сравнительный анализ методов представления трехмерных данных и методов экранизации на основе изображений.
В п.1. даются общие понятия и определения, описываются сложности традиционного подхода, основанного на применении граничных или воксельных моделей.
Основными проблемами применения традиционного процесса моделирования к экранизации реальных объектов являются сложность моделирования, высокая геометрическая сложность моделей, затрудняющая интерактивную визуализацию, а также высокая оптическая сложность моделей реального мира, не позволяющая достичь фотореалистичного качества синтезируемых изображений.
Экранизация на основе изображений (Image-Based Rendering, IBR) – это подход к решению задачи экранизации, основанный на стремлении преодолеть трудности традиционного подхода путем прямого использования исходных данных (изображений, видеопоследовательностей) в процессе экранизации. С экранизацией на основе изображений тесно связано моделирование на основе изображений (Image-Based Modeling, IBM), задачей которого является создание моделей на основе изображений.
Анализировать представления и методы экранизации на основе изображений предлагается с помощью понятия пленоптик-функции.
Пленоптик-функция определяется как интенсивность светового излучения, проходящего через некоторую точку пространства ( x, y, z ), для данного наданной длины световой волны и в заданное время t :
правления Набор входных изображений может рассматриваться как конечный набор значений пленоптик-функции для некоторой области аргументов. Задача алгоритма экранизации – получение значений функции при заданных параметрах, в общем случае отличных от исходных. Это позволит построить изображение сцены для произвольного положения виртуальной камеры.
Реконструкция неизвестных значений пленоптик-функции может вестись как с восстановлением трехмерной геометрической информации (полным или частичным), так и без него (с помощью интерполяции между изображениями).
В п.2. приводятся критерии сравнения алгоритмов экранизации с использованием изображений:
• Удобство получения моделей • Класс представляемых объектов (индивидуальные, сцены и т.п.) • Объем данных и возможность сжатия • Аппаратная поддержка экранизации • Качество экранизации • Поддержка адаптивности, эффективная передача по сети В п.3. описаны основные классы методов экранизации. Методы делятся на четыре категории: экранизация без геометрии, экранизация с неявным использованием геометрии, экранизация с дискретной геометрией и экранизация с явной реконструкцией геометрии. Это деление должно рассматриваться скорее как непрерывный спектр методов, чем дискретный набор категорий (см.
Рисунок 1).
Интерполяция Деформация Обычный графический процесс Рисунок 1 Спектр методов экранизации по изображениям Методы, основанные изображениях без реконструкции геометрии, рассматриваются п.4. Эти методы синтезируют выходное изображение с помощью фильтрации и интерполяции изображений из большого набора исходных фотографий с известными положениями камеры. К достоинствам интерполирующих алгоритмов относится возможность воспроизведения практически любых материалов и форм поверхностей. К недостаткам можно отнести использование излишнего количества данных для увеличения качества выходных изображений. Это ведет к усложнению процесса получения фотографий, дублированию данных и очень большому объему используемой памяти.
В п.5 анализируются методы следующей категории – использующие неявное представление геометрии. Термин «неявная геометрия» означает что трехмерные положения точек не восстанавливаются, а целевое изображение реконструируется с помощью манипуляций с соответствиями на изображениях. Методы этой категории не требуют явных геометрических моделей. Вместо них достаточно построить соответствие особенностей (например, точек или линий) на изображениях исходного набора. Для генераций таких соответствий используются технологии компьютерного зрения. Эти методы позволяют значительно уменьшить объем используемых данных (по сравнению с методами без реконструкции геометрии), однако на практике их применение ограничено из-за неустойчивости методов автоматического поиска соответствий, ведущей к некорректным результатам интерполяции пленоптик-функции.
В п.6 описываются методы, использующие геометрию в дискретном представлении: карты глубины (карты дальности), многослойные карты глубины, деревья многослойных карт глубины. Методы этой категории используют алгоритмы деформации изображений (image warping) для синтеза новых изображений. Для заданной целевой камеры исходные изображения с глубиной деформируются таким образом, чтобы результирующее изображение совпадало с результатом восстановления трехмерных положений точек и их последующей проекции на экранную плоскость целевой камеры. Методы на основе деформации используют алгоритмы обработки изображений и поэтому более эффективны, чем традиционный графический процесс.
Другой край спектра методов занимает традиционная экранизация с поддержкой текстурированной геометрии. Такие методы рассматриваются в п.7.
Действительно, текстурирование относится к методам экранизации на основе изображений. Эти подходы основываются на точной геометрии и небольшом количестве изображений, используемых для создания текстур. Недостатки таких методов описаны выше.
Результаты проведенного анализа приводятся в п.8. Делается вывод о том, что по мере уменьшения количества и точности геометрии в модели, увеличиваются требования к количеству изображений, необходимых для качественного синтеза. С другой стороны, дискретные представления (в частности, на основе изображений) позволяют использовать более простые алгоритмы адаптации и многомасштабности, т.к. работа ведется в двумерном пространстве изображения. Делается заключение о том, что представления на основе изображений эффективно решают задачу экранизации моделей реального мира, в том числе многомасштабной экранизации.
Во второй главе приводится описание нового представления трехмерных данных на основе изображений, а также алгоритмов его обработки и экранизации. Представление основано на моделировании сцены с помощью набора проекций геометрии на заданные плоскости.
В п.1 приводится постановка задачи разработки универсального представления и обосновывается ее актуальность.
Популярность полигонального представления обусловлена прежде всего наличием набора стандартных форматов для полигональных трехмерных данных. Это позволяет независимо развивать алгоритмы и системы создания данных и методы экранизации, обмениваться данными и т.д.
Несмотря на быстрое развитие и нарастающую популярность методов экранизации на основе изображений, до последнего времени не существовало международных стандартов представления трехмерных данных на основе изображений (за исключением Apple QuickTime VR – стандарта де-факто, охватывающего только самые простые представления на основе панорам и видеопоследовательностей).
Была поставлена задача разработки универсального и гибкого представления, охватывающего широкий участок спектра методов представления и экранизации на основе изображений. Представление разрабатывалось с целью включения в развивающийся международный стандарт MPEG-4.
В п.2. приводится описание структуры предлагаемого универсального представления, разработанного по результатам анализа существующих представлений и алгоритмов.
Модель представляет собой пару ( P, K ), где P - набор проекций сцены на заданные плоскости, расположенные в трехмерном пространстве, а K - информация о связи проекций между собой. Проекция задается преобразованием C декартовых координат в пространстве в декартовы координаты на плоскости. В общем случая каждая проекция Pi может содержать один или несколько из следующих возможных атрибутов, записанных в виде изображений: карта цвета (фотография), карта глубины, карта нормалей, карта коэффициентов материалов.
Исходные изображения могут храниться в различных форматах, включая те, которые могут прогрессивно передаваться по сети (например, с вейвлетным сжатием). При этом изображения не обязательно должны иметь одинаковые размеры – понижение разрешения уменьшает размер модели при соответствующем ухудшении качества.
Каждая проекция может обладать различными атрибутами, что позволяет использовать такое представление для различных задач компьютерной графики. Например, для индивидуального объекта исходные изображения могут быть расположены как грани описывающего параллелепипеда. Для более детализированных частей модели могут создаваться карты глубины высокого разрешения.
Рисунок 2 Пример модели, состоящей из карт цвета и карт глубины Информацию K о связи проекций между собой допускается хранить в виде соответствий в форме точек либо примитивов (треугольников, многоугольников).
В п.3. описываются форматы данных, разработанных для универсального представления.
Были разработаны два формата:
• расширенный, на основе языка XML;
• ограниченный вариант, предложенный и включенный в спецификацию международного стандарта для мультимедийных данных MPEG-4 AFX (AFX – Animated Framework Extension) как часть набора представлений, основанных на изображениях (DIBR – Depth Image-Based Representation).
Расширенный формат позволяет с помощью языка XML описывать модель в разработанном представлении.
Пример записи файла в расширенном формате:
color1.jpg depth1.jpg color2.jpg Рисунок 3 Пример модели на основе изображения с глубиной и ее запись в разработанном Ограниченный вариант формата позволяет задавать представление на основе изображений с глубиной. В него вошли описания параметров проекций, причем каждая проекция может хранить только изображение с глубиной или видеопоследовательность с глубиной.
Для обоих форматов были разработаны программные модули для загрузки и сохранения.
В п.4. рассматриваются вопросы обработки и оптимизации моделей в представлении на основе изображений с глубиной (включенного в MPEG-4 AFX).
Задача удаления избыточности состоит в том, чтобы минимизировать число участков поверхности, встречающихся в различных изображениях объекта.
Дискрет (область пространства, соответствующая пикселю на проекции) считается избыточным, если существует другой дискрет или набор дискретов, описывающий цвет той же части поверхности, но с лучшим качеством. Избыточные дискреты появляются в процессе работы трехмерных сканеров или алгоритмов машинного зрения.
В работе описывается разработанный алгоритм поиска и удаления таких дискретов из исходных изображений. Для каждого пикселя карты глубины восстанавливается соответствующий трехмерный дискрет и вычисляется оценка, характеризующая качество описания дискрета на данной карте глубины (считается, что чем меньше угол между нормалью к поверхности дискрета и направлением на камеру, соответствующую данной карте, тем лучше пиксель карты глубины описывает дискрет).
Далее все дискреты, расположенные достаточно близко друг к другу в трехмерном пространстве (т.е. те, которые представляют одну и ту же часть трехмерной поверхности), сравниваются по их оценкам. Дискрет с наивысшей оценкой сохраняется, а остальные удаляются из соответствующих изображений. Также рассматриваются случаи, когда один дискрет полностью покрывает другой, в этом случае могут сохраняться несколько дискретов.
«