автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Методы визуализации и сжатия дискретных моделей поверхностей

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

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

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

МЕТОДЫ ВИЗУАЛИЗАЦИИ И СЖАТИЯ ДИСКРЕТНЫХ МОДЕЛЕЙ ПОВЕРХНОСТЕЙ

Специальность 05.13.11 - математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

Автореферат

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

11«1|1Ш11

Москва-2008

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

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

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

- доктор физико-математических наук, старший научный сотрудник Лазутин Юрий Михайлович

- кандидат физико-математических наук, Иванов Денис Владимирович

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

Защита состоится « » ^ схлЗ. 2008 г. в ^ V часов на

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

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

Автореферат разослан « » ДК^^Д 2008 г.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Автоматические и полуавтоматические методы получения: трехмерный сканер, [етоды компьютерного зрения, результаты вычислений

Автоматизированные методы моделирования человеком

Дискретные модели:

• 30 точки

• карты глубин

• фотографии

Непрерывные

модели:

• полигоны

• сплайны

• текстуры

Как максимизировать эффективность по совокупности показателей: качество, скорость, размер?

Когда непрерывную модель эффективнее переводить в дискретную модель и наоборот?

Методы визуализации {качество, скорость}

<

Изображение на экране

Компактное представление

Область исследований

Методы сжатия {размер}

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

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

Цель работы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

□ 13-й международной конференции по компьютерной графике и машинному зрению "GraphiCon'2003". Россия, Москва, 2003

□ Международной конференции по обработке изображений "ШЕЕ 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

■

Модели объёмов:

л модели из полу-

(_ прозрачных

N вокселей

Трехмерные модели

Модели поверхностей

Ж

1ВНЫМ

Модели без

геометрии г-

объектов, Ц-

основанные на

1 изображениях:

1 панорамы, световые

поля,стерео

У X

[ Модели с непрерывнь множеством точек \ поверхности; полигоны, |_сплайновые поверхности, > элементы поверхности

Дискретные модели -

модели с дискретным множеством точек поверхности

Структурированное множество точек - Ото изображение

с картами глубины Слоистое изображение с глубиной

Раскрашенное октодерево

Теистурированное октоизображение

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

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

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

типов классификаций:

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

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

□ Дискретные и непрерывные модели. Данная классификация относится только к геометрической части представления, т.е. только к октодереву. Октодерево обладает свойствами дискретной модели,

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

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

□ Объектные и пространственные способы определения моделей. Раскрашенное октодерево записывается пространственным способом. Октоизображение сочетает геометрию и изображения, заданные пространственно, и камеры, заданные объектным способом.

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

В первой части второй главы описывается метод решения задачи визуализации объектов с фиксированным относительно наблюдателя цветом поверхности, где акцент делается на максимизации скорости визуализации. После формулировки данной задачи дан обзор существующих методов, из которого сделан вывод - отсутствуют опубликованные методы ускорения визуализации, использующие особенности структуры октодерева. Был предложен и реализован метод, учитывающий особенности записи октодерева при визуализации на стадии преобразования проекции. Для теоретического сравнения вычислительной сложности этого метода с явным преобразованием проекции каждой координаты необходимо было определить зависимость между количеством всех вершин и количеством только листовых вершин октодерева (см. табл. 1 (а)). Для этого была сформулирована гипотеза о возможности аппроксимации с высокой точностью отношения количества всех вершин октодерева к листовым вершинам формулой с одним параметром Этот параметр определяется, как \[тп1\о%2У[п] и называется фрактальной

п~><х>

размерностью октодерева (далее просто размерностью октодерева), где значение у[п] равно количеству единичных вокселов при высоте

октодерева равной п. Для оценки размерности конечных октодеревьев высоты п использовалась формула 1о„ VM . На реальных примерах

V[n -1]

различных моделей было показано, что данная аппроксимация отношения показывает высокую и прогнозируемую точность (см. табл. 1 (б)). Из формулы было выведено, что предложенный метод асимптотически быстрее прямого метода, если размерность октодерева больше чем log -«019 Д-™ обычных моделей поверхности размерность октодерева

близка к двум, поэтому ускорение составляет ~3.5 раз. Наиболее эффективный метод ускорения для других видов дискретных моделей -метод деформации Мак-Маллана, в котором ускорение по сравнению с прямым методом преобразования проекции составляет только ~2.5 раза.

Метод Количество операций Суммарная сложность

сложения умножения деления

Прямой \2М[п\ 16 М[п] ЗМ[п] 5Ш[п]

Предложенный 48 + 6V[ri\ 0 2 V[n] 48 + 6М [и] + 8F[w]

(а) М[п]- количество вершин октодерева до высоты rr, V[n] - количество вокселов на уровне п Для подсчета оценочной сложности были взяты следующие относительные времена элементарных операций, приблизительно соответствующие процессорам семейства х86- сложение -1, умножение - 2, деление - 4

Модель п V[n] М[п] D* К[п] K*(D)

Поверхность камня 8 61695 81773 2 02 3.510 3.508

Колоски пальмы 9 39414 56907 169 3.360 3.354

(6) 2>* - вычисленная оценка размерности октодерева для данной модели; Цп] -коэффициент уменьшения вычислительной сложности на основе экспериментальных данных на уровне п конкретной модели, ^ ~ ^ ~ выведенная асимпто- 4 7 7 2с-4 тическая формула д ля оценки К[п], зависящая только от размерности октодерева В.

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

(а) - оценка, использующая конкретные значения количества вершин и вокселов

(б) - оценка, сведённая к одному параметру О—размерности октодерева

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

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

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

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

Метод Краткое описание метода

Известный метод поверхностных световых полей N I (г,Э,6,ф) = 'YJgl(J■,s)f¡{в,ф) ■ Для каждого треугольника 1=1 функции gj и fi свои; N берут обычно от 1 до 3

Предложенный метод вычисления светового поля '=' £ К ,ф) {V,. = (х,, у. ,21),0пф1, /пк1} - известные дискретные значения светового поля: N - количество членов, участвующих в интерполяции, обычно от 1 до 10; Рсоогс/, рЛг - мера расстояний между координатами и углами соответственно; &соогЛ, 8Лг - радиальные функции координат и углов соответственно, могут меняться от тождественной константы до дельта-функции. Важный частный случай 5Шг = СО/7 Л/ используется для перевода из октоизображения в раскрашенное октодерево

Ь - выходная энергия светового поля; (в.ф) - выходящий луч; у = (х,у,г),л> = (г,з) - вектор координат точки на поверхности в декартовой и параметрической системе координат на полигоне соответственно; п - нормаль к поверхности в заданной точке.

*

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

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

(а) (б) (в) (г) Сд)

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

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

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

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

Л Команды/Операции с ячейками-октодеревьями

Сервер Клиент

Данные: Данные:

структура 1 множество

иерархических • принятых

ячеек ячеек

Задача: Задача:

адаптивное ; адаптивная

управление ; визуализация

1

1 —-Л Тч Г1 П

1 ¡Л \

\ ™М

ч

Р • 1

Положение наблюдателя, Ч Скорость визуализации кадра

7

И?" V

\

(а)

(б)

(в)

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

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

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

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

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

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

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

Снимки экрана при визуализации одной сцены разными методами

Артефакты

пи» •

1 - ступенчатость; 2 -"плавающая" при движении геометрия; 3 -эффект паразитных линий и узоров; 4 - одноцветные области; 5 — границы в форме сплатов_

Небольшая размытость изображения.

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

В третьей главе "Методы компактного представления и сжатия" дан I

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

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

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

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

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

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

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

□ (а) Адаптивный арифметический кодер

□ (б) Контекстная модель первого порядка

□ (в) Контекстная модель второго порядка D (г) Эволюционная контекстная модель

□ (л) Инвариантная контекстная модель

□ (е) Универсальный кодер (RAR МАХ)

метод кодирования данных

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

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

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

Метод построчного отображения с последующим стандартным сжатием JPEG

Метод блочного отображения и сжатия предложенным методом сжатия текстур

Метод отображения посредством октоизображения, плавного цветового расширения с последующим сжатием изображений методом .¡РЕС-2000

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

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

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

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

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

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

ЗО точки, вокселы, карты глубин,..

изображения, видео...

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

(Т)БВО

трехмерные сканеры фотоаппаратура И методы! машинного зрения

реальные трехмерные объекты

Иерархические ячейки раскрашенных БВО

компрессия декомпрессия

адаптивная визуализация сцены

сжатьш формат МРЕО-4 &¥ХОстгее1та§е

сжатое Т1БВО)

Л>Ев/ГТС/АУ1 изображения

в/ге

Узел

локальное хранение или сетевая передача данных

запоминающее устройство

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

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

(е)

(ж)

(з)

(и)

(к)

(л)

(М)

(Н)

(О)

(П)

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

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

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

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

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

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

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

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

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

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

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

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

2. Levkovich-Maslyuk L, Ignatenko A., Zhirkov A, Konushin А, Timasov D, Bayakovski Г., 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 Жирков A 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. Жирков A Binary Volumetric Octree Representation for Image Based Rendering // 11-я Международная конференция по компьютерной графике и машинному зрению GraphiCon'2001. М., 2001.195-199.

6. Matiouchenko V, Strakhov V, Zhirkov A Geometrical calibration television measuring systems with solid-state photo detectors // 16-th International conference on photo electronics and night vision M., 2000.72-77.

7. Levkovich-Maslyuk L, Kalyuzhny P G, Zhirkov A Texture Compression with Adaptive Block Partitions // ACM Multimedia 2000. USA, Los Angeles, 2000.401-404

8. Жирков A, Корчагин Д, Лукин 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 г.

Напечатано с готового оригинал-макета

Издательство ООО "МАКС Пресс" Лицензия ИД N 00510 от 01 12 99 г Подписано к печати 16 01 2008 г Формат 60x90 1/16 Услпечл 1,25 Тираж 80 экз Заказ 006 Тел 939-3890 Тел/Факс 939-3891 119992, ГСП-2, Москва, Ленинские горы, МГУ им М В Ломоносова, 2-й учебный корпус, 627 к

СОДЕРЖАНИЕ.

ВВЕДЕНИЕ.

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

Цель работы.

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

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

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

Структура работы.

Благодарности. ' ' I! j ,: *

ГЛАВА 1. ТРЕХМЕРНЫЕ МОДЕЛИ И МЕТОДЫ ИХ ПОЛУЧЕНИЯ*.

1.1 Методы классификации трехмерных моделей.

1.1.1 Модели поверхностей и объемов.

1.1.2 Векторные и растровые модели.

1.1.3 Дискретные и непрерывные модели.

1.1.4 Объектные и пространственные способы задания моделей.

1.1.5 Явные и неявные способы задания моделей.

1.1.6 Классификация моделей по методам их визуализации.

1.1.7 Классификация моделей по степеням свободы при визуализации.

1.2 Постановка задач.

1.3 Выборочный обзор трехмерных моделей.

1.3.1 Векторные непрерывные поверхностные модели: полигональные.

1.3.2 Векторные дискретные поверхностные модели: точечные.

1.3.3 Дискретные поверхностные модели: изображения с картами глубины.

1.3.4 Дуализм моделей, основанных на изображениях.

1.3.5 Растровые непрерывные объемные модели: вексельные.

1.4 Сравнительный анализ моделей.1.

1.4.1 Интеракгивность и фотореалистичность визуализации.".

1.4.2 Компактность и эффективное сжатие.

1.4.3 Универсальность представлений.

1.5 Предложенная модель н метод её получения.

1.5.1 Предложенная математическая модель.

1.5.2 Основные свойства предложенной модели.

1.5.3 Методы получения предложенной модели.

1.6 Выводы.

ГЛАВА 2. МЕТОДЫ ВИЗУАЛИЗАЦИИ ДИСКРЕТНЫХ МОДЕЛЕЙ ПОВЕРХНОСТЕЙ

2.1 Визуализация объектов с фиксированным цветом нопсрхносги.

2.1.1 Постановка задачи.

2.1.2 Обзор существующих методов решения.

2.1.3 Предложенный метод.

2.1.3.1 Размеры н формы примитивов.:.

2.1.3.2 Предложенный метод вычисления проекции.

2.1.4 Оценка сравнительной вычислительной сложности предложенного метода.

2.1.4.1 Гипотеза об оценке количества вокселов и вершин.

2.1.4.2 Доказательство асимптотики для случая целочисленных размерностей.

2.1.4.3 Практическая проверка гипотезы.

2.1.4.4 Фрактальные свойства октодерева.

2.1.4.5 Результирующая сравнительная оценка сложности.

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

2.2 Визуализация поверхностей с изменяющимся от положения наблюдения цветом.

2.2.3 Специфика задачи.

2.2.3.1 Обзор моделей освещения.

2.2.3.2 Динамическое освещение.

2.2.3.3 Полупрозрачные поверхности.

2.2.3.4 Поверхности с не только диффузным отражением.

2.2.3.5 Уточнение постановки задачи.

2.2.4 Обзор существующих методов решения.

2.2.5 Предложенный метод вычисления светового поля.

2.2.6 Предложенный метод визуализации на основе изображений.

2.2.7 Предложенный метод визуализации полупрозрачных поверхностей.

2.2.8 , Предложенный метод учета динамического освещения.

2.2.9 ' Алгоритмическое ускорение предложенных методов.

2.3 Адаптивная визуализации и управление детализацией участков сцены.

2.3.3 Специфика задачи.

2.3.4 Обзор существующих методов решения.

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

2.4 Улучшение качества визуализации объектов сцены.

2.4.1 Специфика задачи.

2.4.2 Предложенный метод сферического сплатинга.

2.4.3 Предложенный метод адаптивной фильтрации.

2.4.3.1 Адаптивная к уровню детализации фильтрация изображения.

2.4.3.2 Сглаживание формы границ объектов.

2.4.4 Анализ результатов.

2.5 Выводы.

ГЛАВА 3. МЕТОДЫ КОМПАКТНОГО ПРЕДСТАВЛЕНИЯ И СЖАТИЯ.

3.1 Обзор существующих методов.

3.1.1 Теория информации и перцептивная энтропия.

3.1.1 Требования к методам сжатия данных.

3.1.2 Методы сжатия без потери информации.

3.1.3 Методы сжатия изображений, текстур и видео.

3.1.4 Методы сжатия полигональных моделей.

3.1.4.1 Сжатие без потерь информации о связности полигональных сеток.

3.1.4.2 Сжатие информации о геометрии полигональных сеток с потерями.

3.1.4.3 Прогрессивная компрессия полигональных сеток.

3.1.5 Дискретные трехмерные модели и трехмерное видео.

3.1.6 Итоги.

3.2 Предложенный метод сжатии статичных объектов.

3.2.1 Постановка задачи.

3.2.2 Сжатие геометрической составляющей.

3.2.3 Сжатие цветовой составляющей. Метод отображения в изображение.

3.2.4 Сжатие цветовой составляющей. Отображение через октоизображение.

3.3 Предложенный метод сжатия объектов трехмерного видео.

3.3.1 Специфика задачи.

3.3.2 Метод огрубленной проекции.

3.3.3 Метод текстурной составляющей.

3.3.4 Анализ и сравнение предложенных методов на примерах моделей.

3.4 Выводы.

MPEG-4 AFX и DIBR форматы.163

Пример Octreelmage узла в текстовом и бинарном форматах.163

Указатель основных терминов н сокращений.165

Общематематические термины.165

Термины методов визуализации.166

Термины методов компактного представления и сжатия.168

Термины предложенных методов.169

СПИСОК ЛИТЕРАТУРЫ .171

Введение

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

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

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

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

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

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

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

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

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

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

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

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

Автоматические и полуавтоматические метолм получения: трехмерный сканер, методы компьютерного зрения, результаты вычислений

Автоматизированные методы моделирования человеком

Дискретные модели:

• 3D точки

• карты глубин

• фотографии

Непрерывные модели: полигоны сплайны ivkc гуры

Как максимизировать эффективность по совокупности показателей: качество, скорость, размер?

Когда непрерывную модель эффективнее переводить в дискретную модель и наоборот'.'

Методы визуализации {качество, скорость}

И \

Изображение на экране

Компактное представление

Область исследовании

Методы сжатия {размер}

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

Цель работы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

13-ой международной конференции по компьютерной графике и машинному зрению "GraphiCon'2003". Россрм, Москва, 2003

Международной конференции по обработке изображений "ШЕЕ International Conference on Image Processing". США, Рочестер, 2002

11-ой международной конференции по компьютерной графике и машинному зрению "GraphiCon'2001". Россия, Нижний Новгород, 2001

Международной конференции по мультимедиа "ACM Multimedia 2000. США, JIoc-Анжделес, 2000

Научно-исследовательских семинарах по компьютерной графике и обработке изображений под руководством Ю.М. Банковского, ф-т ВМиК МГУ, Москва 2000-2004

Научно-технологических семинарах института передовых технологий Samsung AIT, Inc., Корея, Сеул, 2004.

Научно-технологическом семинаре Intel, Inc., США, Сан-Хосе, 2000.

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

Структура работы

Диссертация состоит из введения, трех глав, заключения и двух приложений.

Основные результаты работы

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

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

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

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

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

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

Эпилог

Дадим прогноз о возможном развитии и широком распространении рассматриваемого в диссертации направления путем ответа на три вопроса.

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

Для того, чтобы дискретные модели в области визуализации трехмерных сцен были эффективнее полигонов, необходимо преодолеть количественную границу мощности ПК по скорости и памяти. Обозначим эту границу как 1 ТФлопса мощности GPU/CPU и порядка 1 Тбайта оперативной памяти. После перехода этой границы станет возможным интерактивная визуализация сцены с детализацией геометрии, достаточной, чтобы при навигации по сцене размер проекции примитива был всегда меньше, чем размер пикселя экрана среднего разрешения. По скорости современные GPU почти подошли к этой границе, а памяти еще существенно не достаточно. Но даже если эта граница будет пройдена и теоретически будет доказано, что представлять сцены дискретно стало более эффективно, это не будет моментально означать повсеместного перехода на визуализацию дискретными моделями в силу инерционности технологий. Латентность смены технологий в индустрии может составлять и десятки лет, в особенности, если это связано с переобучением людей. Так же надо не забывать о таких факторах как существования "критической массы" прироста эффективности и субъективности взгляда людей принимающих решения.

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

Рассмотрим для примера проект "Google Earth" в качестве образца использования полигональной графики по моделированию реального мира. В нем используются данные фотографий со спутника для текстурирования модели земли в виде шара. Текстура получается с разрешением порядка 10 миллионов текстелей (7 порядков). Для придания трехмерности используется карта высот, искривляющая поверхность шара. А для городов на искривленную поверхность шара наносятся коробко-подобные модели домов без текстур. Все это делается полуавтоматически, единственное что, по-видимому, делается вручную - для небольшого количества достопримечательных зданий, создаются трехмерные полигональные модели с использованием реальных фотографий для текстурирования. Для дальнейшего увеличения детализации модели на еще один-два порядка до уровня сантиметров полигональные модели станут, видимо, не пригодны, поскольку на таких масштабах реальность уже не описывается простыми моделями типа параллелепипедов и искривлениями простых поверхностных тел. Для её моделирования полигонами необходимы немыслимые затраты человеческих ресурсов. Более реалистичным выглядит использование для таких масштабов трехмерных сканеров, для которых дискретные модели более эффективны.

Вопрос второй - "Заменит ли трёхмерное видео обычное видео и если да, то когда?"

Широкое распространение стереодисплеев возможно произойдет уже в ближайшие 5 лет, что стимулирует необходимость создания стереофильмов. Далее, примерно 5 лет, широкое распространение получат многоракурсные видеопотоки и соответствующие им интегральные дисплеи. Далее будут использоваться видео с каналами глубины, что добавит дополнительных измерений интерактивности наблюдения 3D фильмов. Через еще 5-10 лет, логическим итогом станет появление трехмерных фильмов с почти не ограниченными возможностями по перемещению в пространстве. Здесь использование предложенных методов может стать актуальным. Что касается отдельных трёхмерных видеообъектов, то их широкое применение может произойти и раньше, но не в области кинопроизводства.

Третий вопрос - "Будут ли для дискретных моделей широко использоваться именно растерные (вексельные), а не векторные (точечные) модели?"

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

Заключение

Общий вид построенной системы и области её применения

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

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

3D pa стер и ад имя дискретная модель

3D точки, вокселы. карты глубин,. изображения, видео. флтпрралигтнчная втуялтапия. трехмерные сканеры, фото апиаратура и метилы компьютерною фения реа.1ьные трехмерные объекты окт отображение изображения/ видео параметры камер j ГГ)БВО компрессия' декомпрессия видо-зависимое БВО С нормалям» к вок селам

Топология камер фотореалистичная янтуалигапия

Раскрашенное БВО вюуадвмцвя трехмерного видео

Иерархические ячейки раскрашенных ЬВО адаптивная внпннпаипя сцепы двумернын редактор изображение на экране сжатый формат Octreelmage локальное храпение или сетевая передача данных сжатое Т/БВО;

JPEGiVTCJA VI изображения

MPEG-4 AFX Узел запоминающее устройство

Рис. 30. Архитектура созданной системы, включаю и (ей методы создания, визуализации н сжатия трехмерных данных. Пунктиром отделены внешние к системе блоки, но которые необходимы для сё по.нюфункцноналыюй работ ы.

Представление объектов, полученных трехмерным сканированием

Основное направление применения предложенных методов - представление дискретных моделей, которые в большинстве случаев получены посредством применения трехмерного сканера, либо при помощи методов компьютерного зрения. Однако трехмерные сканеры пока мало распространены, хотя тенденция к изменению этой ситуации очевидна: за последние годы их стоимость упала более чем на порядок, а качество и точность возросли. Что касается методов компьютерного зрения, то автоматические методы применимы только к узкому классу объектов, а неавтоматические требуют существенного труда по доработке человеком. И сложно ожидать большого прорыва в ближайшем будущем. ш 1 б)

Рис. J1. Примеры моделей, полученных по данным из реального мира, представленных н визуализированных предложенными методами, (а) визуализация раскрашенного октодерева модели, созданною при помощи активного трехмерного сканера; (б) - модель, полученная но одной фотографии с применением методов компьютерного зрения хзя придания трехмерное! и.

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

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

Упомянем здесь только очень интересную технологию работающей камеры, снимающей кроме обычного видео параллельно и глубинный канал в реальном времени на основе активного сканера, работающего в инфракрасном диапазоне [154].

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

Последнее время интерес к подобным сканерам растет, упомянем лишь статью суммирующую, на взгляд автора, достижения последних лет [155], где в результате анализа создается модель непосредственно в виде множества точек без перевода в полигональное представление.

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

Визуализация функций от трех и четырех переменных а) (б)

Рнс. 32. Пример визуализации изоповсрхностен функции от грех переменных с применением пред, южен пых методов визуализации полупрозрачных вокссльиых поверхностей и трехмерного видео. (а), (б) — соседние кадры анимации под разными углами зрения

В данном применении была визуализирована функция от трех переменных. Для чего методом, описанным в разделе 1.5.3, была создана вексельная модель. Не ограничивая общности, функция была единичной по области значений и области определения Уровни изоповерхности брались с таким смещением, чтобы при полном цикле анимации, кадры линий переходили один в один, тем самым получался эффект плавности стыковки трехмерного видео. Воксельная поверхность была выбрана полупрозрачной, чтобы можно было видеть сразу несколько изо-поверхностей. Нормированный цвет поверхности соответствовал координатам в кубе. На Рис. 32. показаны два различных кадра изоповерхности анимации под различными ракурсами.

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

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

Применение для анализа сонограмм звуковых сигналов

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

На рисунке видны общие черты сонно-энергограмм Эти и другие закономерности в произнесенных словах легли в основу разработанной автором нейросетевой диктор-независимых системы распознавания слов и идентификации дикторов [158] [159] [160]. Данная система имеет только одно пересечение с темой диссертационной работы -предложенные в диссертации методы визуализации помогли понять суть тех закономерностей, распознавать которые затем были обучены нейронные сети.

J 01 a) (6)

Рис. 33. Пример визуализации звуковых conoi рамм, представленных цветом, совмещенной с визуализацией энергетической поверхностной огибающей, представленной трехмерной компонентой, (а) - медленно сказанный слог "гх", скорость визуализации с динамическим освещением 101 кадр/сек на Р-М 2GHz без использования GPU; (б) - быстро сказанный слог "тзс"

Двумерное рисование на трехмерных моделях

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

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

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

Рис. 34. Предложенный метод редактирования цветовой составляющей трехмерной дискретной модели посредством двумерного редактирования синтезируемого изображении, (а) - стоп-кадр визуализации объекта, изображение которого отправлено в буфер обмена; (б) - измененное изображение посредством обычною двумерного редактора; (в) — визуализация обз>екта после изменения цвета поверхности с другой позиции

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

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

Рис. 35. Простая точечная визуализации (а) и предложенный метод визуализация с учетом кодозависимых свойств (б).

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

Автор выражает благодарность А. Конушину за помощь в подготовке моделей при реализации тестирования данного приложения.

Трехмерная визуализация на мобильных устройствах

Мобильные устройства, в частности, такие как телефоны и карманные компьютеры, имеют своей особенностью малую вычислительную мощность, вытекающую из необходимости достаточно длительной работы без подзарядки Поэтому, трехмерные ускорители, сложные наборы команд, встроенные для ПК, плохо подходят для ультрамобильных устройств, и возникает задача реализации алгоритмов с помощью простого набора команд. В отличие, например, от полигональной графики, предложенные методы как нельзя лучше подходят для данных приложений, поскольку имеют существенно меньшую вычислительную сложность в пересчете на примитив визуализации Это преимущество проявляется для сложных и реалистичных объектов, например, таких, которые представлены на Рис. 36. . я 4; м © г: гг (г* rwffi у ■ Mku f-iht Ней Jm FitUrmg Svltti Г й»||* а) (б)

Рис. 36. Реализация предложенных методов визуализации для КПК.

Автор выражает благодарность А. Паршину и институту SAIT за непосредственную реализацию предложенных методов на карманном ПК

Интерактивная удаленная визуализация реалистичных детализированных сцен

Рис. 37. Визуализация моделей больших реалистичных дискретных сцен предложенным методом.

1. Brian Curless, Marc Levoy. "A Volumetric Method for Building Complex Models from Range Images", SIGGRAPH '96, Август 1996.

2. С. L. Bajaj, F. Bernardini, G. Xu. "Automatic reconstruction of surfaces and scalar fields from 3d scans". SIGGRAPH'95 Proceedings, Август 1995.

3. Marc Levoy, Turner Whitted. "The use of points as a display primitive", Report TR85-022, University of North Carolina at Chapel Hill, 1985.

4. Matthias Zwicker, Hanspeter Pfister, Jeroen van Baar, and Markus Gross. "Surface splatting", SIGGRAPH'01 Proceedings, Июль 2001.

5. H. Pfister, M. Zwicker, J. Baar, M. Gross. "Surfels: Surface elements as rendering primitives", SIGGRAPH'00 Proceedings, Август 2000.

6. Andrew P. Witkin, Paul S. Heckbert. "Using particles to sample and control implicit surfaces". SIGGRAPH'94 Proceedings, 1994.

7. J. P. Grossman. "Point sample rendering". Master's thesis, Department of Electrical Engineering and Computer Science, MIT, 1998.

8. S. Rusinkiewicz, M. Levoy. "QSplat: A multiresolution point rendering system for large meshes". SIGGRAPH'00 Proceedings, Август 2000.

9. Szymon Rusinkiewicz, Marc Levoy. "Streaming QSplat: A viewer for networked visualization of large, dense models", 2001 Symposium for Interactive 3D Graphics Proceedings, Апрель 2001.

10. Marc Stamminger, George Drettakis. "Interactive sampling and rendering for complex and procedural geometry", 12th Eurographics Workshop on Rendering Proceedings, 2001.

11. Baoquan Chen, Minh Xuan Nguyen. "POP: A hybrid point and polygon rendering system for large data", IEEE Visualization, 2001.

12. Matthias Zwicker, Hanspeter Pfister, Jeroen van Baar, Markus Gross. "EWA volume splatting", IEEE Visualization Proceedings, 2001.

13. Marc Alexa, Johannes Behr, Daniel Cohen-Or, Shachar Fleishman, David Levin, Claudio T. Silva. "Point set surfaces", IEEE Visualization Proceedings, 2001.

14. Mario Botsch, Andreas Wiratanaya, Leif Kobbelt. "Efficient high quality rendering of point sampled geometry", 13th Eurographics Workshop on Rendering Proceedings, 2002.

15. A.Zhirkov. "Binary Volumetric Octree Representation for Image Based Rendering", Graphicon'OI, Сентябрь 2001.

16. Liviu Coconu, Hans-Christian Hege. "Hardware-accelerated point-based rendering of complex scenes", 13th Eurographics Workshop on Rendering Proceedings, 2002.

17. Liu Ren, Hanspeter Pfister, Matthias Zwicker. "Object space EWA surface splatting: A hardware accelerated approach to high quality point rendering", Eurographics '02 Proceedings, 2002.

18. Stephan Wurmlin, Edouard Lamboray, Oliver G. Staadt, Markus H. Gross. "3D video recorder", Pacific Graphics 2002 Proceedings, 2002.

19. Gevorg Grigoryan, Penny Rheingans. "Probabilistic Surfaces: Point Based Primitives to Show Surface Uncertainty", IEEE Visualization '02 Proceedings, 2002.

20. Anders Adamson, Marc Alexa. "Ray tracing point set surfaces", Shape Modeling International 2003 Proceedings, 2003.

21. G. Schaufler, H. W. Jensen. "Ray tracing point sampled geometry", RenderingTechniques 2000: 11th Eurographics Workshop on Rendering, Июнь 2000.

22. Marc Alexa, Johannes Behr, Daniel Cohen-Or, Shachar Fleishman, David Levin, Claudio T. Silva. "Point Set Surfaces", IEEE Visualization, 2001.

23. Jaroslav Krivanek. "Representing and Rendering Surfaces with Points", Thesis, 2003

24. M. Gross, Н. Pfister, М. Zwicker, М. Pauly, М. Stamminger, М. Alexa. "Tutorial T6: Point Based Computer Graphics", Eurographics 2002, 2002

25. James Blinn, Martin Newell. "Texture and reflection in computer generated images". Communications of the ACM, Октябрь 1976.

26. Edwin Catmull. "Computer display of curved surfaces". IEEE Conference on Computer Graphics Proceedings, Pattern Recognition and Data Structures, Май 1975.

27. Paul Heckbert. "Fundamentals of texture mapping and image warping". Master's thesis, University of California at Berkeley, Июнь 1989.

28. George Wolberg. "Digital Image Warping". IEEE Computer Society Press, 1990.

29. Jonathan Shade, Dani Lischinski, David H. Salesin, Tony DeRose, and John Snyder. "Hierarchical image caching for accelerated walkthroughs of complex environments". SIGGRAPH '96 Proceedings, 1996.

30. William Mark, Leonard McMillan, Gary Bishop. "Post-rendering 3D warping". 1997 Symposium on Interactive 3D Graphics, ACM SIGGRAPH, 1997.

31. Jay Torborg, James Kayija, Talisman. "Commodity realtime 3D graphics for the PC". SIGGRAPH'96 Proceedings. 1996.

32. Shenchang Eric Chen, Lance Williams. "View interpolation for image synthesis". SIGGRAPH' 93 Proceedings, 1993.

33. Stephane Laveau, Olivier Faugeras. "3-D scene representation as a collection of images and fundamental matrices", Technical Report RR-2205, Февраль 1994.

34. Olivier Faugeras, Stephane Laveau, Luc Robert, Gabriella Csurka, Cyril Zeller. "3-D reconstruction of urban scenes from sequences of images", Technical Report RR-2572, Июнь1995.

35. Steven Seitz, Charles Dyer. "View morphing", SIGGRAPH'96 Proceedings, 1996.

36. Qian Chen and Gerard Mendioni. Image synthesis from a sparse set of views. In Proceedings of Visualization'97, Los Alamitos, California, 1997. IEEE Computer Society Press.

37. Антон Конушин. "Система построения трехмерных моделей реальных объектов по последовательности изображений", Ломопосов-2005, 2005.

38. AKonouchine, V.Gaganov, V. Vezhnevets. "AMLESAC: A New Maximum Likelihood Robust Estimator", Graphicon-2005, Июнь 2005

39. Shenchang Eric Chen. "QuickTime VR An image-based approach to virtual environment navigation", SIGGRAPH'95 Proceedings, 1995.

40. E. H. Adelson, J. R. Bergen. "The plenoptic function and the elements of early vision", Computational Models of Visual Processing, MIT Press, 1991.

41. Marc Levoy, Pat Hanrahan. "Light field rendering", SIGGRAPH'96 Proceedings, 1996.

42. Steven J. Gortler, Radek Grzeszczuk, Richard Szeliski, Michael F. Cohen. "The lumigraph", SIGGRAPH'96 Proceedings. 1996.

43. Wei-Chao Chen, Jean-Yves Bouguet, Michael H. Chu, Radek Grzeszczuk. "Light Field Mapping: Efficient Representation and Hardware Rendering of Surface Light Fields", SIGGRAPH'01 Proceedings, Август 1996.

44. Gavin S. P. Miller, Steven M. Rubin, D. Ponceleon. "Lazy decompression of surface light fields for precomputed global illumination", Eurographics Rendering Workshop Proceedings, Июнь 1998.

45. Daniel N. Wood, Daniel I. Azuma, Ken Aldinger, Brian Curless, Tom Duchamp, David H. Salesin, Werner Stuetzle. "Surface light fields for 3D photography", SIGGRAPH 2000 In Proceedings, 2000.

46. Emilio Camahort Gurrea. "4D Light-Field Modeling and Rendering", Dissertation, Май 2001

47. Marc Levoy. "Display of surfaces from volume data", IEEE Computer Graphics & Applications, Май 1988.

48. David Laur, PatHanraha. "Hierarchical splatting: A progressive refinement algorithm for volume rendering", SIGGRAPH '91 Proceedings, Июль 1991.

49. Roni Yagel, Arie Kaufman. "Template-based volume viewing", Eurographics'92, Сентябрь 1992.

50. Westover, Footprint. "Evaluation for Volume Rendering", SIGGRAPH'90 Proceedings, 1990.

51. Philippe Lacroute, Marc Levoy. "Fast Volume Rendering using a Shear-warp Factorization ot the Viewing Transform", SIGGRAPH'94 Proceedings, Июль 1994.

52. D. Laur, P. Hanrahan. "Hierarchical Splatting: A Progressive Refinement Algorithm for Volume Rendering", SIGGRAPH 1991,1991

53. Александр Паршин. "Вычисление видимости в иерархически представленных вексельных моделях", Дипломная работа МГУ ВМиК, 2005.

54. W. Е. Lorensen, Н. Е. Cline. "Marching Cubes: a high resolution 3D surface construction algorithm", Computer Graphics, 21 (4), 1987

55. Liviu Coconu, Hans-Christian Hege. "Hardware-Oriented Point-Based Rendering of Complex Scenes", Eurographics workshop on rendering Proceedings, 2002.

56. C. Dachsbacher, C. Vogelgsang, M. Stamminger. "Sequential point trees", SIGGRAPH'2003 Proceedings, 2003.

57. Steven Gortler, Li-wei He, Richard Szeliski. "Layered Depth Images", SIGGRAPH '98 Proceedings, 1998. Июль 1998.

58. Manuel M. Oliveira, Gary Bishop. "Image-Based Objects", SIGGRAPH '99 Proceedings, 1999.

59. Paul Rademacher, Gary Rademacher. "Multiple-Center-of-Projection Images", SIGGRAPH'98 Proceedings, Июль 1998.

60. Manuel M. Oliveira, Gary Bishop, McAllister. "Relief Textures Mapping". SIGGRAPH'2000 Proceedings, 2000.

61. Leonard McMillan. "An Image-Based Approach to Three-Dimensional Computer Graphics", Ph.D. Thesis, University of North Carolina at Chapel Hill, 1997

62. Sergey Parilov, Wolfgang Stuerzlinger. "Layered Relief Textures", Journal of WSCG, 2002.

63. Fabio Policarpo, Manuel M. Oliveira, Joao Comba. "Real-Time Relief Mapping on Arbitrary Polygonal Surfaces", ACM SIGGRAPH 2005 Symposium on Interactive 3D Graphics and Games, 2005.

64. A. Ignatenko, A. Konushin. "A Framework for Depth Image-Based Modeling and Rendering", Graphicon-2003 Proceedings, Сентябрь 2003.

65. Д. Роджерс, Дж. Адаме. "Математические основы машинной графики", Москва, изд-во Мир, 2001.

66. Т. Павлидис. "Алгоритмы машинной графики и обработка изображений", Москва, изд-во Радио и связь, 1986.

67. G. Frieder, D. Gordon, R. A. Reinolds. "Back-to-Front Display of Voxel-Based Objects", IEEE Computer Graphics and Applications, Январь 1985.

68. Y. Ohtake, A. Belyaev, M. Alexa. "Sparse Low-degree Implicit Surfaces with Applications to High Quality Rendering, Feature Extraction, and Smoothing", Eurographics Symposium on Geometry Processing 2005, 2005.

69. Matthias Zwicker, Hanspeter Pfister, Jeroen van Baar, Markus Gross. "EWA Splatting", IEEE TRANSACTIONS ON VISUALIZATION AND COMPUTER GRAPHICS, VOL.8, N0.3, Январь-Сентябрь 2002.

70. M. Oliveira, G. Bishop. "Image-based objects," of ACM Symposium on Interactive 3D Graphics 1999 Proceedings, Апрель 1999.

71. L. Ren, H. Pfister, M. Zwicker. "Object space EWA surface splatting: A hardware accelerated approach to high quality point rendering", Computer Graphics Forum 21 (3), 2002.

72. Liu Ren, Hanspeter Pfister, Matthias Zwicker. "Accelerated Approach to High Quality Point Rendering", EUROGRAPHICS'2002, 2002.

73. А.Жирков, А.Паршин. "Адаптивный рендеринг трехмерных сцен на основе иерархических ячеек", 15-ая международная конференция по компьютерной графике и машинному зрению GraphiCon'2005, 2005.

74. Lee Shin Jun, Seok Yoon Jung, Alexander Parshin, Alexander Zhirkov. "Adaptive 3D Scene Rendering Based on Hierarchical Cells" Представленный патент, 2004.

75. G. Hausdorff. "Dimension und auberes Mab", Math. Ann. 79, 1919.

76. И.Пригожин, И.Стенгерс. "Время. Хаос. Квант", Москва, УРСС, 2001.

77. М. Li, P. Vitanyi. "An Introduction to Kolmogorov Complexity and its Applications", 2nd ed. New York: Springer, 1996.

78. B.B.Mandelbrot. "Fractals, Form, Chance, and Dimension", San Francisco: Freeman, 1977.

79. Р.М.Кроновер. "Фракталы и Хаос в динамических системах. Основы теории", Москва, изд-во Постмаркет, 2000.

80. J. Hutchinson. "Fractals and Self Similarity", Indiana Univ. Math. Journal, Vol.30, No.5., 1981.

81. С.В.Божокин, ДА.Паршин. "Фракталы и Мультифракталы", Ижевск, НИЦ "Регулярная и Хаотическая динамика", 2001.

82. Pat Hanrahan. "Computer Graphics: Image Synthesis Techniques", Stanford University course CS 348B, http://graphics.stanford.edu/courses/cs348b-0/lectures/lectureI2/walk001.html, Весна 2000

83. F. E.NICODEMUS, J. C. RICHMOND, J. J. HSIA, I. W. GINSBERG, T. LIMPERIS. "Geometric Considerations and Nomenclature for Reflectance", National Bureau of Standards (USA), 1977.

84. Eric Veach. "Robust Monte Carlo Methods for Light Transport Simulation", PhD thesis, STANFORD UNIVERSITY, Декабрь 1997.

85. J.T. Kajiya. "The Rendering Equation", SIGGRAPH '86 Proceedings, Computer Graphics, v20, пЗ, Август 1986.

86. Кирилл Дмитриев. "Разработка и модернизация методов генерации физически достоверных изображений на ЭВМ", Диссертация, 2002.

87. Levin. "The approximation power of moving least-squares", Math. Сотр. 67(224): 15171531, 1998

88. Alexa Behr, Cohen-Or Fleishman, Levin Silva. "Point Set Surfaces", IEEE Visualization 2002, 2002.

89. Savchenko, Pasko, Okunev, Kunii. "Function representation of solids reconstructed from scattered surface points and contours", Computer Graphics Forum, 14(4): 181-188, 1995.

90. Carr Beatson, Cherrie Mitchell, Fright McCallum. "Reconstruction and Representation of 3D Objects with Radial Basis Functions", SIGGRAPH'2001 Proceedings, 2001.

91. Я.Б.Зельдович. "Высшая математика для начинающих и её приложения к физике", стр. 567, Изд-во "наука", М., 1965.

92. Э.Эргон. "Синтез изображений. Базовые алгоритмы", М., Радио и Сеть, 1993.

93. Alexander Zhirkov. "View-Dependent Octree Image Rendering", Graphicon '2003, 2003.

94. H. Hoppe. "Progressive Meshes", SIGGRAPH 4996 Proceedings, 1996.

95. E. Puppo, R.Scopigno. "Simplification, LOD and Multiresolution Principals and Applications", EUROGRAPHICS 97 Tutorial Notes, 1997.

96. S. Chen and D. Gordon. "Front-to-Back Display of BSP Trees." IEEE Computer Graphics & Algorithms, pp 79-85. September 1991.

97. Teller, S. 1992. "Visibility Computations in Densely Occluded Polyhedral Environments". University of California at Berkeley, 1992.

98. J. Shade, D. Lischinski, D. H. Salesin, T. DeRose, J. Snyder. "Hierarchical Image Caching for Accelerated Walkthroughs of Complex Environments", SIGGRAPH' 96 Proceedings, 1996.

99. Chun-Fa Chang, Gary Bishop. "A Hierarchical Representation for Image-based Rendering", SIGGRAPH'1999, Computer Graphics Proceedings, 1999.

100. M. Wand, W. Straber. "Multi-Resolution Rendering of Complex Animated Scenes", Eurographics 2002 Proceedings, 2002.

101. Szymon Rusinkiewicz, Marc Levoy. "Streaming QSplat: A Viewer for Networked Visualization of Large, Dense Models", Symposium on Interactive 3D Graphics, 2001.

102. Eyal Teler, Dani Lischinski. "Streaming of Complex 3D Scenes for Remote Walkthroughs", Eurographics 2001 Proceedings, 2001.

103. I. Wald, H.-P. Seidel. "Interactive Raytracing of Point-based Models", Proceedings of2005 Symposium on Point Based Graphics, 2005.

104. Shin-junLee, Seok-yoon Jung, Alexei Sosnov, Do-kyoonKim, Keun-ho Kim, Alexander Zhirkov, Alexander Parshin. "Points-based rendering apparatus, method and medium", Представленный патент, 2006.

105. Shin-jun Lee, Gyeong-ja Jang, Seok-yoon Jung, Alexei Sosnov, Do-kyoon Kim, Keun-ho Kim, Alexander Zhirkov, Alexander Parshin. "Method, medium and apparatus rendering 3D graphic data using point interpolation", Представленный патент, 2006.

106. Shin-jun Lee, Gyeong-ja Jang, Seok-yoon Jung, Alexei Sosnov, Do-kyoon Kim, Keun-ho Kim, Alexander Zhirkov, Alexander Parshin. "Splat filtering method, medium, and system", Представленный патент, 2006.

107. Д.С.Чернавский. "Информация, Самоорганизация, Мышление". Изд-воМГУ, 2000. "Самоорганизация и синергетика: идеи, подходы и перспективы"

108. H.Quastler. "The emergence of biological organization", Yale University Press, 1964.

109. Шеннон. К, Бандвагон.Е. "Работы по теории информации и кибернетики", М.: ИЛ, 1963. С. 667.

110. J. Johnston. "Estimation of perceptual entropy using noise masking criteria," in Proc. ICASSP-88, 1988.

111. Д.Ватолин, А.Ратушняк, М.Смирнов, В.Юкин. "Методы сжатия данных", Москва, Диалог-МИФИ, 2002.

112. J. Ziv, A.Lempel. "A universal algorithm for sequential data compression", IEEE Transactions on Information Theory, Vol. 23(3), pp.337-343, Май 1977.

113. J.G. Cleary, I.H. Witten. "Data compression using adaptive coding and partial string matching", IEEE Transactions on Communications, Vol. 32(4), Апрель 1984.

114. M. Schindler. "A byte oriented arithmetic coding", Proceedings of Data Compression Conference, 1998.

115. J.J. Rissanen, G.G.Langdon. "Universal modeling and coding", IEEE Transactions on Information Theoiy, Vol. 27(1), Январь 1981.

116. Шкарин Д. "Повышение эффективности алгоритма РРМ", Проблемы передачи информации, 34(3), 2001.

117. G.V. Cormack, R.N. Horspool. "Data compression using dynamic Markov modeling", The Computer Journal 30(6), Декабрь 1987.

118. M. Burrows, D.J.Wheeler. "A Block-sorting Lossless Data Compression Algorithm", SRC Research Report 124, Digital Systems Research Center, Palo Alto, Май 1994.126. "The Virtual Reality Modeling Language (VRML)", ISO/IEC14772-1, 1997.

119. G. Taubin, W. Horn, F. Lazarus, J. Rossignac. "Geometry coding and VRML", Proceeding of the IEEE 96 (6) 1228-1243, 1998.128. "Coding of Audio-Visual Objects: Visual", ISO/IEC 14496-2, Июль 2001.

120. J. Peng, C.-C. J. Kuo. "Geometry-guided progressive lossless 3D mesh coding with octree (ОТ) decomposition", SIGGRAPH'2005, 2005.

121. A. Khodakovsky, I. Guskov. "Compression of Normal Meshes", Geometric Modeling for Scientific Visualization, 2003.

122. H. Hoppe. "Progressive meshes", SIGGRAPH'96Proceeding, 1996.

123. S. Gumhold. "Improved cut-border machine for triangle mesh compression", Erlangen Workshop'99 on Vision, Modeling and Visualization, IEEE Signal Processing Society, 1999.

124. M. Chow. "Optimized geometry compression for real-time rendering", IEEE Visualization, 1997.

125. P. M. Gandoin, 0. Devillers. "Progressive lossless compression of arbitrary simplicial complexes", ACM Transactions on Graphics 21 (3), 2002.

126. P. Alliez, M. Desbrun. "Progressive encoding for lossless transmission of triangle meshes", SIGGRAPH'2001 Proceedings, 2001.

127. Jingliang Peng, Chang-Su Kim, C.-C. Jay Kuo. "Technologies for 3D Mesh Compression: A Survey", Preprint submitted to Elsevier Science, Март 2005.

128. Marcus Magnor, Bernd Girod. "Data Compression for Light-Field Rendering", IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS FOR VIDEO TECHNOLOGY, VOL. 10, NO. 3, Апрель 2000.138. "S3TC DirectX 6.0 Standard Texture Compression", Savage 3D white papers, 1998.

129. Chang-Su Kim, Sang-Uk Lee. "Compact encoding of 3D voxel surfaces based on pattern code representation", IEEE Trans, on Image Processing, vol. II, no. 8, Август 2002.

130. Т. Jebara, A. Azarbayejani, A. Pentland. "3D structure from motion", IEEE Signal Processing Magazine, Vol. 16, No. 3, 1999.

131. Dynamic Digital Depth Inc., http://www.ddd.com.142. 3DV Systems: Zcam, http://www.3dvsystems.com.

132. Stephan W.urmlin*, Edouard Lamboray, Markus Gross. "3D video fragments: dynamic point samples for real-time free-viewpoint video", Elsevier Science, Computer & Graphics, 2004.

133. Edouard Lamboray, Stephan Wurmlin, Markus Gross. "Real-Time Streaming of Point-Based 3D Video", Computer Graphics Laboratory

134. Department of Computer Science, Zurich

135. Switzerland, http://graphics. ethz. ch/Downloads/Publications/Papers/ '2004/lam04/pjMin04.pdf 2004.

136. M. Botsch, A. Wiratanaya, L. Kobbelt. "Efficient high quality rendering of point sampled geometry", 13th Eurographics Workshop on Rendering Proceedings, pages 53-64, 2002.

137. Edouard Lamboray, Michael Waschbusch, Stephan Wurmlin, Hanspeter Pfister, Markus Gross. "Dynamic Point Cloud Compression for Free Viewpoint Video", Mitsubishi Electric Research Laboratories, http://www.merl.com/papers/docs/TR2003-137.pdf 2003.

138. JianGuang Lou, Hua Cai, Jiang Li. "A RealTime Interactive MultiView Video System", ACM Internationa! Conference on Multimedia, Ноябрь 2005.

139. Bong-Soo Sohn, Chandrajit Bajaj, Vinay Siddavanahalli. "Volumetric Video Compression for Interactive Playback", Elsevier Science preprint, Март 2004.

140. H. Coxeter, W. Moser. "Generators and relations for discrete groups", 3rd edition, Springer-Verlag, 1972.

141. Roncn Gvili, Amir Kaplan, Eyal Ofek, Giora Yahav.

142. Depth keying", 3DVSystems Ltd. http://www.3dvsystems.com/

143. Filip Sadlo, Tim Weyrich, Ronald Peikert, Markus Gross. "A Practical Structured Light Acquisition System for Point-Based Geometry and Texture", Proceedings of the Eurographics Symposium on Point-Based Graphics, 2005.

144. V.G. Matiouchenko, V.V. Strakhov, A.O. Zhirkov. "Geometrical calibration television measuring systems with solid-state photo detectors", 16-th international conference on photo electronics and night vision, Moscow, 2000.

145. E.A. Горобинская, A.O. Жирков. "Телевизионная измерительная система", 18-ая международная конференции по фотоэлектронике и приборам ночного видения, 2004.

146. А.О. Жирков, Д.Н. Корчагин, А.С. Лукин, А.С. Крылов, Ю.М. Баяковский. "Нейросетевой метод представления и нейросетевое распознавание частотно-временных векторов речевой информации", журнал ПРОГРАММИРОВАНИЕ, 2003, № 4, 2003.

147. С. А. Яковлев. "Глобальная освещенность для точечных моделей", диплом, ВМиКМГУ, 2005.

148. Mikael Bourges-Sevenier. "An introduction to

149. MPEG-4 AFX", http://www.gti.ssr.upm.es/~fmb/pub/AFXtutorial/AFXtutoriallintro.ppt, 2002.

150. ISO/TEC JTC1/SC29/WG11 14496-1, "Coding of Audio-Visual Objects: Systems".

151. ISO/IEC JTC1/SC29/WG11 14496-2, "Coding of Audio-Visual Objects: Visual".