Методы визуализации и сжатия дискретных моделей поверхностей тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат физико-математических наук Жирков, Александр Олегович

• Жирков, Александр Олегович
• кандидат физико-математических наук
• 2008

Оглавление диссертации кандидат физико-математических наук Жирков, Александр Олегович

СОДЕРЖАНИЕ.

ВВЕДЕНИЕ.

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

Цель работы.

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

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

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

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

Благодарности. ' ' 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. Визуализация моделей больших реалистичных дискретных сцен предложенным методом.

Список литературы диссертационного исследования кандидат физико-математических наук Жирков, Александр Олегович, 2008 год

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".