Автореферат А.О.Жиркова: "Методы визуализации и сжатия дискретных моделей поверхностей"

Российская академия наук

Институт прикладной математики им. М.В. Келдыша

На правах рукописи

Жирков Александр Олегович

МЕТОДЫ ВИЗУАЛИЗАЦИИ И СЖАТИЯ

ДИСКРЕТНЫХ МОДЕЛЕЙ ПОВЕРХНОСТЕЙ

Специальность 05.13.11 – математическое и программное обеспечение

вычислительных машин, комплексов и компьютерных сетей

Автореферат

диссертации на соискание ученой степени

кандидата физико-математических наук

Москва – 2008

Работа выполнена в Институте прикладной математики

им.М.В.Келдыша РАН

Научный руководитель – кандидат физико-математических наук, доцент

Баяковский Юрий Матвеевич

Официальные оппоненты:

- доктор физико-математических наук,

старший научный сотрудник

Лазутин Юрий Михайлович

- кандидат физико-математических наук,

Иванов Денис Владимирович

Ведущая организация: Государственный научно-исследовательский институт авиационных систем (ГосНИИАС)

Защита состоится «______» ____________________ 2008 г. в ____ часов на заседании Диссертационного совета Д 002.024.01 при ИПМ им.М.В.Келдыша РАН по адресу: 125047, Москва, Миусская пл. 4.

С диссертацией можно ознакомиться в библиотеке Института прикладной математики им.М.В.Келдыша РАН

Автореферат разослан «_____» ___________________ 2008 г.

Учёный секретарь диссертационного совета,

доктор физико-математических наук Т.А. Полилова

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность

Цифровые методы хранения данных повсеместно вытесняют традиционные физические способы хранения. С начала компьютерной эры текстовые данные были перенесены в цифровую форму. Затем в нашу жизнь вошли так называемые мультимедиа-данные: цифровые фотографии, видео и музыка. Цифровые трёхмерные модели поверхностей объектов вытесняют трёхмерные физические макеты объектов в архитектуре и дизайне.

При переводе цифровых данных в форму, удобную для человеческого восприятия, возникает множество задач для научных исследований. Для мультимедиа-данных исследования сосредоточены на методах их сжатия и анализа. Методы сжатия применяются для экономии памяти при хранении мультимедиа-данных, а также для улучшения качества их восприятия при удалённой передаче по каналам данных с узкой пропускной способностью. Для цифровых моделей поверхностей исследования сосредоточены на задачах их моделирования и визуализации.

Традиционные мультимедиа-данные неинтерактивны, т.е. человек может их только пассивно слушать и смотреть. Напротив, визуализация моделей поверхностей изначально обладала свойством интерактивности. Мультимедиа-данные аналитичны, поскольку создаются посредством анализа окружающего мира; природа обычных моделей поверхностей, напротив, синтетична, поскольку они синтезируются при помощи компьютерного моделирования с участием человека. Разрозненность мультимедиа-данных и моделей поверхностей ощущается и на уровне стандартизации форматов данных. Стандартизация важна для обеспечения возможности создания и совместного использования информации между людьми. Только в недавно вышедшем стандарте MPEG-4 появилась возможность кодировать мультимедиа-данные и модели поверхностей в едином бинарном формате сцен BIFS, наследника языка виртуального моделирования VRML.

На стыке мультимедиа, компьютерной графики и компьютерного зрения возникает новое направление, ориентированное на обработку, кодирование и визуализацию моделей поверхностей, полученных непосредственно из реального мира. В отличие от других моделей поверхностей эти модели образуются в результате не синтеза, а в результате анализа или трёхмерного сканирования, что сближает их с типичными мультимедиа-данными. Различают пассивное сканирование, когда поверхность восстанавливается путем анализа фотографий поверхности, и активное, при котором расстояние до поверхности находится путём её физического облучения. В отличие от многоугольных сеток (далее “полигонов”), обычно получаемых при создании моделей дизайнером, после трёхмерного сканирования формируются дискретные модели поверхности.

В полигональных моделях, созданных дизайнером, полностью задана геометрия поверхности и её световые свойства. В дискретной модели заданы лишь положения некоторых точек поверхности с ограниченной точностью и частичные данные о световых свойствах поверхности. Для дискретных моделей поверхностей актуальны задачи создания эффективных методов сжатия, активноприменяемых для мультимедиа-данных, и создания методов быстрой визуализации, используемых и для других трёхмерных моделей. Обе задачи становятся особенно актуальными для представления объектов трёхмерного видео и протяжённых трёхмерных сцен, где возникают большие объёмы данных, которые необходимо сжимать, передавать, быстро декодировать и интерактивно визуализировать в реальном времени и в поточном режиме.

Простым и широко используемым способом решения задач, связанных с дискретными моделями, является перевод их в полигональную форму. Таким образом, может показаться, что этим и решаются все проблемы. Однако поставим под сомнение этот тезис. И более того, возможно, некоторые непрерывные полигональные модели эффективнее переводить в дискретную форму. Сформулируем два возникших вопроса:

1. Полигональное представление требует задания явной геометрии и топологии для кусочно-плоских поверхностей, что в процессе моделирования дизайнером определяется естественным образом. Однако для данных, полученных из трёхмерного сканера, представленных обычно множеством несвязанных трёхмерных точек, понятия топологии, связности и даже поверхности не определены явным образом. Поэтому возникает вопрос о целесообразности использования полигонов для хранения дискретных моделей.

2. Если объекты настолько детализированы, что размер проекций графических примитивов при визуализации меньше размеров пиксела экрана, то вместо сложных примитивов, таких как полигоны, можно использовать точки без потери качества визуализации. В этом случае отпадает необходимость в сложной структуре данных, включающей полигональные сетки, текстуры и текстурные координаты – можно использовать просто множество трёхмерных точек. Возникает вопрос о целесообразности визуализации полигонами моделей с высокой степенью детализации.

Эти и другие вопросы включаются в область исследований диссертационной работы, схема предметной области которой показана на рис. 1.

Рис. 1. Общая схема затрагиваемых предметных областей

Рамкой ограничена область исследований, являющейся темой диссертационной работы. Выделены основные показатели, составляющие критерий эффективности методов визуализации и сжатия: качество визуализации модели, скорость визуализации модели, размер – количество информации, необходимое для записи модели.

Цель работы

Исследование и разработка новых методов визуализации и сжатия дискретных моделей поверхностей, обладающих большей эффективностью по сравнению с существующими методами. Совокупная оценка эффективности включает скорость синтеза изображений модели и объём информации, необходимый для представления модели. При этом синтез изображений при визуализации модели не должен содержать артефактов, т.е. визуально-различимых нежелательных особенностей изображения.

Адаптация разработанных методов для специализированных задач:

– интерактивная визуализация объектов с видозависимым цветом поверхности;

– интерактивная визуализация больших трёхмерных сцен;

– визуализация потока кадров сжатого трёхмерного видеообъекта.

Определение условий, при которых более эффективным является использование дискретных моделей, нежели полигональных.

Реализация разработанных методов в виде отдельных программ и в виде программных модулей для интеграции в распространенные прикладные программные комплексы.

Научная новизна

Предложены новые виды дискретных моделей поверхностей объектов, для которых были предложены методы создания, сжатия и визуализации.

Практическая значимость и реализация

Разработаны и доведены до реализации предложенные методы создания, сжатия и визуализации дискретных моделей поверхностей трёхмерных объектов. Реализованные алгоритмы удовлетворяют требованиям, сформулированным при постановке задачи, большинство из них запатентовано. Базовые предложенные представления моделей и методы их компрессии вошли в качестве форматов в стандарт MPEG-4 для представления мультимедиа-данных. Для визуализации моделей в этих форматах разработаны модули визуализации к программному комплексу Contact 3D. Также разработаны отдельные самостоятельные программы визуализации для платформ Windows и Pocket-PC. Реализован пакет консольных утилит для создания и редактирования моделей. Для редактирования цветовой компоненты моделей необходим редактор растровых изображений, например, программа Photoshop. Для создания моделей и связи с другими форматами пакет утилит может использоваться как самостоятельно, так и совмещаться с плагином для популярного пакета трёхмерного моделирования 3DS-MAX.

Апробация работы и публикации

Основная часть работы была выполнена в Лаборатории компьютерной графики и мультимедиа факультета Вычислительной математики и кибернетики МГУ им. М.В. Ломоносова по заказу Института передовых технологий компании Самсунг.

Кроме апробации в рамках Лаборатории рассматриваемые технологии выдержали многоступенчатые этапы международных проверок и этапов стандартизации. Основные положения докладывались и обсуждались на следующих конференциях и научных семинарах:

13-й международной конференции по компьютерной графике и машинному зрению “GraphiCon’2003”. Россия, Москва, 2003
Международной конференции по обработке изображений “IEEE International Conference on Image Processing”. США, Рочестер, 2002.
11-й Международной конференции по компьютерной графике и машинному зрению “GraphiCon’2001”. Россия, Нижний Новгород, 2001.
Международной конференции по мультимедиа “ACM Multimedia 2000. США, Лос-Анжелес, 2000.
Научно-исследовательских семинарах по компьютерной графике и обработке изображений под руководством Ю.М. Баяковского, ф-т ВМиК МГУ, Москва, 2000–2004.
Научно-технологических семинарах института передовых технологий Samsung AIT, Inc., Корея, Сеул, 2002–2004.
Семинаре отдела Оптоэлектроники ОКРФ ФИАН, Москва, 2007.
Научно-технологическом семинаре Intel, Inc., США, Сан-Хосе, 2000.

По теме диссертации имеется 8 публикаций. Предложенные методы защищены российскими и международными патентами.

Структура и объём работы

Диссертация состоит из введения, трёх глав, заключения, двух приложений и указателя основных терминов и сокращений. Общий объём диссертации 183 страницы, включая 41 рисунок и 18 таблиц. Список цитируемой литературы состоит из 164 наименований.

СОДЕРЖАНИЕ РАБОТЫ

Во введении обоснована актуальность исследования методов работы с дискретными моделями поверхностей, сформулированы цели и задачи диссертационной работы, научная новизна, практическая ценность, описана структура диссертации, выражены благодарности.

В первой главе “Трёхмерные модели и методы их получения” сформулирована постановка задач на основе поставленной цели и вытекающих из неё требований, предъявляемых к трёхмерной модели. С точки зрения этих требований дан обзор существующих видов трёхмерных моделей, проведён их сравнительный анализ. На основании этого анализа сделан вывод, что существующие методы визуализации и сжатия имеющихся видов моделей не удовлетворяют в полной мере предъявляемым требованиям. Были предложены новые модели, которые гипотетически могут удовлетворить данным требованиям. Описаны предложенные методы их получения и создания. Таким образом, для достижения поставленной цели осталось подтвердить, что предложенные виды моделей удовлетворяют поставленным требованиям. Доказательству существования данных методов визуализации и сжатия посвящены две следующие главы.

Геометрическая компонента предложенных видов моделей состоит из бинарно-воксельного октодерева (далее БВО, или просто октодерево) – дерево, имеющее до восьми ветвлений, причём все листовые вершины одинаковой длины до корня. Дереву ставится в соответствие воксельный куб в трёхмерном пространстве, разрешение которого равно двум в степени высоты дерева. Каждая листовая вершина определяет единственным образом соответствующий ей единичный/непрозрачный воксел, все остальные вокселы считаются нулевыми. Условие одинаковой длины каждой ветви позволяет определять такое дерево одним байтом информации для каждого узла дерева. Если поверхность пересекает воксел, его значением будет 1, в противном случае – 0. Были предложены три вида моделей, отличающихся методом представления цветовой компоненты для непрозрачных вокселов. Рассмотрим каждый из видов с указанием тех их ключевых свойств, которые позволят создать для этих моделей эффективные методы визуализации и сжатия:

- Раскрашенное октодерево, в котором каждому узлу дерева явно сопоставлен цвет. Простая структура и наличие встроенных уровней детализации в этом виде моделей повысят скорость визуализации модели.

- Октоизображение, в котором хранятся пространственная конфигурация камер и изображения, соответствующие камерам. Наличие информации о видозависимых свойствах поверхности повысит реалистичность визуализации. Хранение цветовой компоненты модели в изображениях увеличит степень сжатия цветовой компоненты без появления артефактов.

- Текстурированное октоизображение, которое отличается от октоизображения тем, что в нём дополнительно хранится текстурная информация, явным образом ставящая в соответствие каждому вокселу камеру и пиксел соответствующего изображения. Такое отличительное свойство этого вида модели повысит скорость декодирования модели, что особенно важно для поточного декодирования и визуализации потока кадров трёхмерного видеообъекта.

Предложенные виды моделей были рассмотрены с точки зрения различных классификаций трёхмерных моделей. Одна из возможных классификаций вместе со схематичными образами конкретных видов моделей представлена на рис. 2.

Рис. 2. Классификации известных и предложенных трёхмерных моделей

Модели отсортированы в порядке убывания условной “трёхмерности” геометрической компоненты модели, начиная от моделей объёмов, заканчивая моделями, основанными только на изображениях.

Сформулируем краткие результаты анализа по каждому из рассмотренных типов классификаций:

Модели объёмов, модели поверхностей и модели, основанные на изображениях. Предложенные моделизадают поверхность объекта и поверхностные по определению, но используют структуру октодерева, которая обычно используется для представления моделей объёмов. Без октодерева октоизображение превращается вмодель без геометрии, основанную на изображениях.
Векторные и растровые модели. Бинарно-воксельное октодерево является записью трёхмерного бинарного растра и поэтому растровое. Также растровые, но двухмерные, являются изображения, входящие в октоизображение. Однако параметры, связывающие камеры и воксельный куб, а также положение и ориентация модели в пространстве, являются векторными.
Дискретные и непрерывные модели. Данная классификация относится только к геометрической части представления, т.е. только к октодереву. Октодерево обладает свойствами дискретной модели, поскольку определено только в точках поверхности с неточно определенными координатами. Октодерево обладает также понятиями связности и непрерывности, присущими непрерывной модели. Точная классификация октодерева зависит от геометрической интерпретации. В диссертационной работе вокселы, структурируемые октодеревом, геометрически интерпретируются как точки, расположенные в объёме соответствующих вокселам кубов, для определенности в центрах кубов. Поэтому в данной интерпретации модель является дискретной.
Явные и неявные способы задания моделей. В октоизображении цветовая компонента определена неявным образом, в раскрашенном октодереве – явным. Поскольку координаты вокселов могут быть определены только в ходе обхода октодерева, то геометрическая компонента – октодерево это неявное представление вокселов.
Объектные и пространственные способы определения моделей. Раскрашенное октодерево записывается пространственным способом. Октоизображение сочетает геометрию и изображения, заданные пространственно, и камеры, заданные объектным способом.

Во второй главе “Методы визуализации дискретных моделей поверхностей” описаны методы визуализации предложенных в первой главе видов дискретных моделей поверхностей.

В первой части второй главы описывается метод решения задачи визуализации объектов с фиксированным относительно наблюдателя цветом поверхности, где акцент делается на максимизации скорости визуализации. После формулировки данной задачи дан обзор существующих методов, из которого сделан вывод – отсутствуют опубликованные методы ускорения визуализации, использующие особенности структуры октодерева. Был предложен и реализован метод, учитывающий особенности записи октодерева при визуализации на стадии преобразования проекции. Для теоретического сравнения вычислительной сложности этого метода с явным преобразованием проекции каждой координаты необходимо было определить зависимость между количеством всех вершин и количеством только листовых вершин октодерева (см. табл. 1 (а)). Для этого была сформулирована гипотеза о возможности аппроксимации с высокой точностью отношения количества всех вершин октодерева к листовым вершинам формулой с одним параметром. Этот параметр определяется, как и называется фрактальной размерностью октодерева (далее просто размерностью октодерева), где значение V[n] равно количеству единичных вокселов при высоте октодерева равнойn. Для оценки размерности конечных октодеревьев высоты n использовалась формула . На реальных примерах различных моделей было показано, что данная аппроксимация отношения показывает высокую и прогнозируемую точность (см. табл. 1 (б)). Из формулы было выведено, что предложенный метод асимптотически быстрее прямого метода, если размерность октодерева больше чем . Для обычных моделей поверхности размерность октодерева близка к двум, поэтому ускорение составляет ≈3.5 раз. Наиболее эффективный метод ускорения для других видов дискретных моделей – метод деформации Мак-Маллана, в котором ускорение по сравнению с прямым методом преобразования проекции составляет только ≈2.5 раза.

Табл. 1. Оценка коэффициента ускорения предложенного метода преобразования проекции, учитывающего структуру октодерева, по сравнению с прямым методом, преобразующим все вершины независимо

(а) – оценка, использующая конкретные значения количества вершин и вокселов. (б) – оценка, сведённая к одному параметру D – размерности октодерева.

При сравнении со сложностью визуализации полигональных моделей было вычислено, что предложенный метод визуализации будет вычислительно менее сложным, если количество вокселов в модели менее чем в ≈25 раз превосходит количество полигонов. Примерами эффективного применения дискретных моделей являются объекты с высокой концентрацией мелких деталей. Пример неэффективного применения дискретных моделей – объект с геометрией, описываемой прямоугольным параллелепипедом.

Во второй части второй главы решается задача визуализации дискретных моделей, цвет поверхности которых зависит от направления наблюдения, т.е. свет в точках поверхности исходит в общем случае неравномерно. Рассматривается три типа моделирования подобных поверхностей: непрозрачные поверхности с локальным прямым освещением, полупрозрачные поверхности с рассеянным освещением и поверхности, заданные световым полем. На основе обзора существующих методов делается вывод, что существующие решения непригодны для прямого использования в рамках предложенной модели октодерева.

Поэтому была поставлена задача разработки методов, использующих октодерево и обеспечивающих реализацию всех трёх описанных видов моделирования освещения. Первый тип был реализован посредством предложенного метода реконструкции нормалей по воксельной модели. При реализации третьего типа полупрозрачными сплатами возникли артефакты, связанные со ступенчатостью бинарно-воксельных моделей. Для частичного устранения описанных артефактов были разработаны методы адаптивной фильтрации синтезированных изображений и предобработки воксельных моделей. При решении третьей, наиболее общей задачи моделирования световых полей, была предложена модель, которая позволяет вычислять прохождение света в любой точке объёма и с любого направления путем интерполяции известных значений. Данная модель позволяет, не выходя за рамки модели октоизображения, аппроксимировать любое световое поле и, как следствие, любые свойства материала поверхности и глобальной освещенности. Однако чем более неоднородное излучение поверхности необходимо смоделировать и чем большую точность надо получить, тем количество хранимых изображений будет соответственно больше и визуализация медленнее.

В табл. 2 даны основные формулы предложенного метода в сравнении с аналогичным методом световых полей для полигонального представления. На рис. 3 показано исходное дискретное представление модели, его визуализация без применения предложенного метода и с его применением.

Табл. 2. Сравнение предложенного метода видозависимой визуализации поверxности и наиболее близкого к нему методу поверхностных световых полей

Основное отличие предложенного метода – световое поле вычисляется интерполяцией в пятимерном пространстве точек и углов, а не суммой произведений двумерных функций, заданных на полигонах.

Рис. 3. Сравнение обычного (б, в) и предложенного (г, д) методов визуализации дискретной модели, исходно представленной 28-ю изображениями с глубиной (a)

Снимки экрана обычной точечной визуализации – видозависимость поверхности порождает артефакты. Снимки экрана визуализации, использующий предложенный метод, не создающий артефактов, а напротив, увеличивающий реалистичность визуализации благодаря наличию видозависимости цвета поверхности.

В следующих частях главы обсуждается задача визуализации дискретных моделей сцен, отличие которых от ранее рассматриваемых моделей объектов в том, что при визуализации модели сцен камера находится внутри ограничивающего объёма, а не снаружи.

В третьей части второй главы рассматривается задача адаптивной визуализации, в общем случае в системе с сервером, содержащим модель, и клиентом, на котором происходит визуализация. Под адаптивной визуализацией подразумевается возможность обеспечить интерактивный просмотр больших сцен без задержек, адаптируясь к таким параметрам вычислительной системы, как: вычислительная мощность клиента, разрешение экрана, положение наблюдателя в сцене, количество доступной оперативной памяти на клиенте, скорость передачи данных от сервера к клиенту. Было разработано новое представление сцены, названное иерархическими ячейками, и методы работы с ним, решающие поставленную задачу. Иллюстрацией к этой части служит рис. 4, содержащий общую схему клиент-серверной архитектуры удаленной визуализации, различные состояния сцены от начала загрузки сцены до периода максимальной детализации с учётом перемещения пользователя по сцене, и примеры визуализации большой реалистичной дискретной сцены с различной степенью детализации.

Рис. 4. Предложенный метод удаленной визуализации в рамках клиент-серверной архитектуры

(а) – схема потока данных и распределения функций между клиентом и сервером. (б) – схематичный вид реализации структуры иерархических ячеек в последовательные моменты времени – (б.1)- (б.4). Зелёные квадраты – границы ячеек, серые линии – границы отдельных вокселов, красные квадраты – единичные вокселы, белые квадраты – пустое пространство, красные линии – реальные границы объектов. (в) – снимок экрана фрагмента сцены в начале сеанса удаленной визуализации (соответствует схематичному рисунку б.2) и он же в период насыщения (соответствует схематичному рисунку б.4).

Проблема минимизации артефактов, возникающих при визуализации дискретных сцен, является предметом исследований четвёртой части второй главы.

Данная проблема возникает вследствие отказа от двух допущений, которые были сделаны при визуализации отдельных объектов. Во-первых, в случае сцены нельзя сделать допущение, что детализации объектов сцены всегда достаточно для обеспечения плотности проецируемых точек сравнимой с плотностью пикселов экрана. При размере спроецированного примитива больше двух пикселей, примитивы нельзя уже рассматривать как бесформенные. И как показывает практика, перцептивное качество визуализации сильно зависит от формы и геометрической интерпретации примитива. Простой сплаттинг, рассматривающий спроецированный воксел как квадрат или круг, порождает множество артефактов. Во-вторых, нельзя допускать, что плотность проецируемых точек на экране близка к равномерной. Поэтому при визуализации объектов сцены необходимо применять адаптивные к плотности точек методы.

Была предложена классификация артефактов визуализации дискретных моделей, возникающая при низкой плотности проецируемых точек, причём было замечено, что с понижением плотности артефакты не просто усиливаются, но и возникают новые их разновидности. Проведённый анализ известных методов решения проблемы возникновения артефактовпоказал, что большинство методов исправляют только цветовую компоненту, а методы, которые исправляют и геометрию, неприемлемы для интерактивной визуализации из-за большой вычислительной сложности. Поэтому была поставлена и решена задача создания методов нивелирования как геометрических, так и цветовых артефактов, требующих соизмеримых с базовым методом визуализации вычислительных затрат.

Первый предложенный метод – метод сферических сплатов (отпечатков) позволил избавиться от эффекта “плавающей” геометрии. Второй метод – метод размытия адаптивного к плотности спроецированных точек, позволил избавиться от таких артефактов, как появление линий и узоров, появления одноцветных областей. Наиболее сложный для устранения и появляющийся последним при уменьшении плотности проецируемых точек артефакт – артефакт, заметный на краях объектов. Для его нивелирования предложен третий метод – метод сглаживания формы границ между объектами.

Иллюстрацией содержания этой части служит табл. 3, в которой сравнивается качество визуализации простого метода сплаттинга с предложенным методом сферического сплаттинга и адаптивной фильтрацией.

Табл. 3. Сравнение простого метода с предложенным методом визуализации

В третьей главе “Методы компактного представления и сжатия” дан обзор методов сжатия мультимедиа данных и трёхмерных моделей, описаны предложенные методы сжатия.

В первой части третьей главы даны основы теории информации, введен термин перцептивной энтропии, формулируется общая задача сжатия, дан краткий обзор текущего статуса развития сжатия без потерь информации, сжатия изображений, текстур, видео, полигональных моделей, дискретных моделей и трёхмерного видео. Из этого обзора делается вывод, что сжатие дискретных моделей и трёхмерных видеообъектов, в отличие от других областей сжатия, находится в самом начале своего развития. Также сделаны выводы, которые были существенно использованы в следующих разделах главы: наиболее практичный и эффективный метод сжатия цветовой информации – посредством изображений; наиболее эффективные методы сжатия трёхмерных полигональных и точечных моделей используют октодерево; при сжатии трёхмерных видеообъектов компенсация геометрии неэффективна, а сжатие геометрии с потерями приводит к артефактам.

Сформулированы критерии эффективности методов сжатия. Количественные показатели эффективности методов сжатия – степень сжатия, скорости компрессии и декомпрессии, а также качественная мера, которая обычно также приводится к аналитическому выражению. Однако в случае использования моделей разных классов использовать адекватную аналитическую меру не представляется возможным, поэтому использовался бинарный показатель перцептивного качества – отсутствие или присутствие видимых артефактов при трёхмерной визуализации модели. Так как компрессия производится один раз, скорость компрессии, в отличие от скорости декомпрессии, будем считать несущественным фактором, а скорость декомпрессии данных модели не должна вносить существенную задержку в процесс визуализации самой модели.

Вторая часть третьей главы посвящена методам сжатия статических дискретных моделей. Сформулированы постановка задачи и специфичные для данной задачи требования. Далее рассматривается предложенный метод сжатия геометрической компоненты модели без потерь. Метод использует современные инструменты сжатия без потерь – адаптивное арифметическое кодирование и контекстное моделирование. Метод включает три основные составляющие, каждая из которых повышает степень сжатия. Первая составляющая заключается в наследовании информации при увеличении порядка контекстных моделей. По мере увеличения закодированных символов контекстная модель переключается на модель с большим порядком, наследуя накопленную информацию о вероятностном распределении символов. Использование такой схемы позволило применить преимущества контекстных моделей малого порядка, эффективных на малом количестве исходных данных, и контекстных моделей большого порядка, проявляющих свою эффективность на больших массивах данных. Вторая составляющая – использование фрактального свойства октодерева, проявляющегося в самоподобности в усреднении по разным масштабным уровням. Что, в частности, означает, что корреляции разбиения узлов-родителей и узлов-потомков можно считать инвариантными относительно уровня детализации. Поэтому родительскую вершину можно использовать на разных масштабных уровнях в качестве контекста для кодирования текущего узла дерева. Третья составляющая – использование геометрического свойства воксельного куба – существует 48 ортогональных преобразований куба, при которых он переходит сам в себя. Было обнаружено, что все 256 различных сочетаний потомков вершины образуют 22 замкнутые относительно этих преобразований группы. Эта составляющая метода сжатия позволила не только многократно уменьшить количество используемой памяти для хранения статистики, но и существенно увеличила скорость набора статистики, что, в свою очередь, увеличило степень сжатия. Конкретные значения степеней сжатия представлены на рис. 5.

Далее рассматриваются различные пути решения задачи сжатия цветовой составляющей статической модели. В отличие от геометрической компоненты сжатие цветовой компоненты без потерь неэффективно, что показывает опыт сжатия двумерных изображений и видео, где достигаются степени сжатия порядка 20–30 и 100 раз соответственно без наличия существенных искажений для человеческого восприятия. Однако в этих случаях существенно используется естественная согласованность данных в пространстве и во времени. В случае трёхмерных поверхностей задача использования пространственной близости не имеет очевидного решения. Один из простых способов – осуществление локального обхода по точкам с записью этого прохода на двумерное изображение. Были исследованы различные пути обхода и методы отображения на двумерную плоскость. Было установлено, что наиболее устойчивым к разрывам среди обладающих высоким сжатием является предложенный метод сжатия текстур с использованием адаптивного подразбиения на кластеры и аппроксимации геометрии локальной цветовой палитры, описание которого дано в приложении к диссертации. Данный метод сжатия изначально был предложен для сжатия текстур полигонального представления. Однако и этот метод в применении к задаче сжатия цветовой составляющей дискретной модели порождал заметные артефакты в местах разрывов отображения трёхмерной поверхности на двумерное изображение. Поэтому был предложен другой метод, ключевой особенностью которого является наличие не одного, а нескольких изображений, на которые осуществляется отображение поверхности. В качестве метода отображения используются проекции трёхмерной плоскости на плоскости виртуальных камер, соответствующих изображениям. Таким образом, сжатие цветовой составляющей дискретной модели свелось к сжатию октоизображения, введенного ранее.

Рис 5. Диаграмма сравнения по степени сжатия предложенных методов сжатия октодерева (a–д) без потерь и популярного универсального архиватора (е)

Усреднение произведено по десяти тестовым примерам. (а) – простое адаптивное арифметическое кодирование; (б) – добавление контекста от родительского узла; (в) – учёт положения потомка в родительском узле; (г) – схема контекстного моделирования с наследованием информации с последовательным применением методов (а)–(б)–(в); (д) – финальный используемый метод, добавляющий к (г) инвариантность распределения вероятностей относительно ортогональных преобразований.

Изображения октоизображения могут присутствовать в модели изначально либо могут быть получены путём обратной проекции вокселов на изображения камер. Обратное соответствие для каждого воксела по изображениям получается методом вычисления светового поля, описанного во второй главе. Назовем фоновыми пикселы изображения, не использующиеся при визуализации. При сжатии изображений с потерями цвет фоновых пикселов влияет на степень сжатия самих изображений, а также опосредованно на синтезируемые при визуализации изображения. Простой метод закраски фоновых пикселов однородным фоном при сжатии изображений с потерями порождает артефакты, аналогичные возникающим в методе отображения с одним изображением. Был разработан специальный метод заполнения фона посредством адаптивного цветового расширения – аналога известного метода математической морфологии для бинарных изображений. В случае использования сжатия изображений на основе дискретно-косинусного преобразования был разработан метод блочного цветового расширения. Для набирающего популярность метода сжатия на основе вейвлет-преобразования был предложен метод плавного цветового расширения. Практические примеры сжатия показали, что данный метод не только позволил избежать появления артефактов при визуализации, но и существенно повысил степень сжатия по сравнению с простой одноцветной закраской фона. Иллюстрации сравнения рассмотренных методов сжатия цветовой компоненты даны на рис. 6. Эмпирически, основываясь на более чем 20-ти примерах моделей, были получены следующие оценки перцептивной энтропии: ≈50 Кбайт на дискретную модель с линейным разрешением 256 точек и ≈4 бита в пересчете на один раскрашенный воксел.

Рис 6. Сравнение артефактов изображений модели, цветовая компонента которой сжата различными методами, но с одинаковым суммарным размером ≈30КБ

Третья часть третьей главы посвящена методам сжатия объектов трёхмерного видео. Специфика задачи, по сравнению со сжатием статических моделей, заключается в необходимости быстрого метода извлечения из потока данных и декомпрессии одного кадра. Использование метода, предложенного для статических моделей, неэффективно, поскольку скорость предложенного метода интерполяции светового поля даже после ряда сделанных алгоритмических ускорений осталась более чем на порядок медленнее скорости непосредственной визуализации одного кадра. Был предложен метод огрубленной проекции, ускоряющий время подготовки одного видеокадра для визуализации более чем на порядок. Суть его заключается в том, что поиск соответствий между вокселами октодерева и пикселами в изображениях осуществляется с пониженной геометрической детализации, а для всех вокселов в соответствующем кубе пониженной детализацией, все вокселы считаются соответствующими только одной определенной камере. Однако за скорость пришлось платить появлением ряда артефактов для некоторых сложных моделей.

Поэтому был предложен ещё один метод, идея которого заключается в перераспределении вычислительной сложности по формированию цветовой компоненты с критичного по времени этапа визуализации на этап создания модели. В данном методе кроме октоизображения добавляется информация, явно связывающая геометрическую и цветовую компоненты путём сопоставления для каждого воксела соответствующего изображения. По аналогии с полигональными текстурированными моделями данная компонента была названа текстурной, а вид модели – текстурированным октоизображением. Для сжатия этой компоненты используется метод, аналогичный известному методу группового кодирования только для случая не линейно, а иерархически расположенных данных. После чего данные подвергаются адаптивному арифметическому кодированию с очень сильным параметром агрессивности, что позволяет вероятностной модели быстро адаптироваться к часто меняющимся данным.

В конце третьей части третьей главы проведён сравнительный анализ предложенных методов сжатия трёхмерного видео с существующими аналогами. Был сделан вывод, что сравнимым по компактности представления дискретных моделей является только метод сжатия моделей, представленных изображениями с картами глубины. Недостатки этого метода проявляются на моделях достаточно сложных объектов, когда приходится использовать много карт глубины, которые становятся избыточны либо разреженны. На протестированных объектах сжатые модели карт глубины с изображениями в два раза и более превысили размеры сжатых октоизображений, даже с учётом применения к изображениям карт глубин предложенного метода плавного расширения. Также в этой части главы рассмотрены два типичных примера трёхмерных видеообъектов и один пример динамической сцены, содержащий эмуляцию природного явления – снега с моделированием его падения на дискретную поверхность сцены. Данный пример продемонстрировал гибкость предложенных методов – возможность совмещать исходно полигональные и сгенерированные физические модели. Показано, как без существенной потери визуального качества, комбинируя статические и динамические участки сцены, а также выбирая разные уровни детализации для разных моделей объектов сцены, модель динамической сцены была сжата более чем в 5000 раз.

В заключении приводится общий вид построенной системы, изображенный на рис. 7, описаны конкретные области применения, краткие иллюстрации и комментарии к которым даны на рис. 8. Перечислены дальнейшие направления исследований. Сформулированы основные результаты диссертационной работы.

Рис 7. Архитектура построенной системы, включающей методы создания, визуализации и сжатия трёхмерных моделей

Пунктиром обозначены внешние к созданной системе сущности, но являющиеся необходимыми для её функционирования. Аббревиатура “(Т)БВО” означает, что допускается использование как текстурированного бинарно-воксельного октодерева, так и не текстурированного.

Рис 8. Снимки экранов с приложений, использующих предложенные методы

(а) – интерактивная визуализация по сети сложной реалистичной сцены; (б) – детализированная модель объекта, пример эффективного применения предложенных методов; (в) – дискретная модель исходно полигональной сцены с большим количеством плоских поверхностей, пример неэффективного использования предложенных методов; (г) – сцена, состоящая из нескольких сжатых статических и анимированных объектов в формате MPEG-4, записанных в расширенном формате VRML; (д) – визуализации палитры изображения; (e) – модель, полученная трёхмерным сканером; (ж) – модель, полученная методами компьютерного зрения; (з) – динамическое освещение модели; (и) – визуализация поверхностей с видозависимым цветом; (к) – визуализация многомерной функции трехмерными полупрозрачными видеообъектами; (л) – визуализация сонограммы звукового сигнала; (м) – кадр типичного трёхмерного видеообъекта; (н) – реализация адаптивной визуализации для карманного компьютера; (о) – реализация упрощённой визуализации объектов для карманного компьютера; (п) – пример использования предложенного метода рисования на трёхмерной модели посредством использования внешнего двумерного редактора

В приложении A дано описание формата хранения для предложенной модели текстурированного октоизображения в стандарте MPEG-4. В приложении Б описан предложенный метод сжатия текстур полигональных моделей, выходящий за рамки основной области исследования диссертации.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

1. Предложены новые виды трёхмерных дискретных моделей поверхностей объекта. Предложены методы создания, визуализации и сжатия этих видов моделей. В рамках представления статичных матовых поверхностей с достаточной частотой дискретизации показано, что предложенные методы визуализации быстрее, а методы сжатия обладают большей степенью сжатия при визуализации без артефактов по сравнению с показателями известных методов для других видов дискретных моделей. Определены условия, при которых использование предложенных методов визуализации дискретных моделей более эффективно, нежели использование полигональных моделей.

2. Предложены и разработаны методы для специализированных задач:

– интерактивная визуализация без проявления артефактов моделей объектов с видозависимым цветом дискретной поверхности;

– интерактивная визуализация больших дискретных сцен; предложены методы контроля за детализацией участков сцены в клиент-серверной архитектуре; предложены методы устранения артефактов, возникающих при визуализации участков сцен с недостаточной частотой дискретизации;

– декодирование и интерактивная визуализация потока кадров трёхмерных видеообъектов.

3. Предложенные форматы кодирования статических и анимационных дискретных моделей поверхностей стандартизированы в рамках стандарта MPEG-4. Разработаны методы создания и сжатия в этих форматах для интеграции в популярную систему трёхмерного моделирования 3DS MAX. Для визуализации моделей в этих форматах разработаны модули визуализации к программному комплексу Contact 3D.

Публикации по теме диссертационной работы

1. Жирков А., Паршин А. Адаптивный рендеринг трёхмерных сцен на основе иерархических ячеек // 15-я Международная конференция по компьютерной графике и машинному зрению GraphiCon’2005. Россия, Новосибирск, 2005. 409–504.

2. Levkovich-Maslyuk L., Ignatenko A., Zhirkov A, Konushin A., Timasov D., Bayakovski Y., Han Mahnjin, In Kyu Park. Depth Image-Based Representation for Static and Animated 3D Objects // IEEE Transaction on Circuits and Systems for Video Technology. Special Issue on MPEG-4 AFX. 2004. 1032–1045.

3. Жирков А. View-Dependent Octree Image Rendering // 13-я Международная конференция по компьютерной графике и машинному зрению GraphiCon’2003. М., 2003. 112–117.

4. Bayakovski Y., Levkovich-Maslyuk L., Ignatenko A., Konushin A., Timasov D., Zhirkov A., Han Mahnjin, In Kyu Park. Depth Image-Based Representation for Static and Animated 3D Objects // IEEE International Conference on Image Processing. USA, New York, 2002. 25–28.

5. Жирков А. Binary Volumetric Octree Representation for Image Based Rendering // 11-я Международная конференция по компьютерной графике и машинному зрению GraphiCon’2001. М., 2001. 195–199.

6. Matiouchenko V., Strakhov V., Zhirkov А. Geometrical calibration television measuring systems with solid-state photo detectors // 16-th International conference on photo electronics and night vision. М., 2000. 72–77.

7. Levkovich-Maslyuk L., Kalyuzhny P.G., Zhirkov A. Texture Compression with Adaptive Block Partitions // ACM Multimedia 2000. USA, Los Angelеs, 2000. 401–404.

8. Жирков A., Корчагин Д., Лукин А., Крылов А., Баяковский Ю. Нейросетевой метод представления и нейросетевое распознавание частотно-временных векторов речевой информации // Программирование. 2003. № 4. 210–218.

9. Han Mahnjin, Zhirkov A. Hierarchical image-based representation of still and animated three-dimensional object, method and apparatus for using this representation for the object rendering. // Российский патент № 2001118222, июль 2001; патент США № 6778173; европейский патент № 02254451.4, август 2004 г.