Содержание к диссертации
Введение
ГЛАВА 1. Трехмерные модели и методы их получения 11
1.1 Методы классификации трехмерных моделей 11
1.1.1 Модели поверхностей и объемов 12
1.1.2 Векторные и растровые модели 13
1.1.3 Дискретные и непрерывные модели 13
1.1.4 Объектные и пространственные способы задания моделей 14
1.1.5 Явные и неявные способы задания моделей 14
1.1.6 Классификация моделей по методам их визуализации 15
1.1.7 Классификация моделей по степеням свободы при визуализации 15
1.2 Постановка задач 16
1.3 Выборочный обзор трехмерных моделей... 17
1.3.1 Векторные непрерывные поверхностные модели: полигональные 17
1.3.2 Векторные дискретные поверхностные модели: точечные 18
1.3.3 Дискретные поверхностные модели: изображения с картами глубины 21
1.3.4 Дуализм моделей, основанных на изображениях 22
1.3.5 Растровые непрерывные объемные модели: воксельные 25
1.4 Сравнительный анализ моделей '. 26
1.4.1 Интерактивность и фотореалистичность визуализации 26
1.4.2 Компактность и эффективное сжатие 27
1.4.3 Универсальность представлений 28
1.5 Предложенная модель н метод её получения 29
1.5.1 Предложенная математическая модель 29
1.5.2 Основные свойства предложенной модели 31
1.5.3 Методы получения предложенной модели 34
1.6 Выводы 40
ГЛАВА 2. Методы визуализации дискретных моделей поверхностей .41
2.1 Визуализация объектов с фиксированным цветом поверхности 41
2.1.1 Постановка задачи 41
2.1.2 Обзор существующих методов решения 42
2.1.3 Предложенный метод 45
2.1.3.1 Размеры и формы примитивов : 45
2.1.3.2 Предложенный метод вычисления проекции 46
2.1.4 Оценка сравнительной вычислительной сложности предложенного метода 50
2.1.4.1 Гипотеза об оценке количества вокселов и вершин 52
2.1.4.2 Доказательство асимптотики для случая целочисленных размерностей 52
2.1.4.3 Практическая проверка гипотезы 54
2.1.4.4 Фрактальные свойства октодерева 56
2.1.4.5 Результирующая сравнительная оценка сложности 59
2.1.5 Сравнение скорости визуализации дискретных и полигональных моделей 60
2.2 Визуализация попсрхностеп с изменяющимся от положення наблюдения цветом 62
2.2.3 Специфика задачи 62
2.2.3.1 Обзор моделей освещения 62
2.2.3.2 Динамическое освещение 64
2.2.3.3 Полупрозрачные поверхности 65
2.2.3.4 Поверхности с не только диффузным отражением 65
2.2.3.5 Уточнение постановки задачи 66
2.2.4 Обзор существующих методов решения 66
2.2.5 Предложенный метод вычисления светового поля 67
2.2.6 Предложенный метод визуализации на основе изображений 71
2.2.7 Предложенный метод визуализации полупрозрачных поверхностей 74
2.2.8 , Предложенный метод учета динамического освещения 78
2.2.9 ' Алгоритмическое ускорение предложенных методов 80
2.3 Адаптивная визуализация и управление детализацией участков сцены 81
2.3.3 Специфика задачи 81
2.3.4 Обзор существующих методов решения 82
2.3.5 Предложенный метод управления детализацией в клиент-серверной архитектуре 84
2.4 Улучшение качества визуализации объектов сцены 87
2.4.1 Специфика задачи 87
2.4.2 Предложенный метод сферического сплатинга 89
2.4.3 Предложенный метод адаптивной фильтрации 91
2.4.3.1 Адаптивная к уровню детализации фильтрация изображения 91
2.4.3.2 Сглаживание формы границ объектов 91
2.4.4 Анализ результатов 93
2.5 Выводы 95
ГЛАВА 3. Методы компактного представления и сжатия 98
3.1 Обзор существующих методов 98
3.1.1 Теория информации и перцептивная энтропия 98
3.1.1 Требования к методам сжатия данных 100
3.1.2 Методы сжатия без потери информации 102
3.1.3 Методы сжатия изображений, текстур и видео 104
3.1.4 Методы сжатия полигональных моделей 106
3.1.4.1 Сжатие без потерь информации о связности полигональных сеток 106
3.1.4.2 Сжатие информации о геометрии полигональных сеток с потерями 107
3.1.4.3 Прогрессивная компрессия полигональных сеток 108
3.1.5 Дискретные трехмерные модели и трехмерное видео 109
3.1.6 Итоги 113
3.2 Предложенный метод сжатии статичных объектов 114
3.2.1 Постановка задачи 114
3.2.2 Сжатие геометрической составляющей 114
3.2.3 Сжатие цветовой составляющей. Метод отображения в изображение 119
3.2.4 Сжатие цветовой составляющей. Отображение через октоизображение 122
3.3 Предложенный метод сжатия объектов трехмерного видео 127
3.3.1 Специфика задачи 127
3.3.2 Метод огрубленной проекции 128
3.3.3 Метод текстурной составляющей 131
3.3.4 Анализ и сравнение предложенных методов на примерах моделей 134
3.4 Выводы 142
Заключение 145
Список литературы
- Модели поверхностей и объемов
- Интерактивность и фотореалистичность визуализации
- Оценка сравнительной вычислительной сложности предложенного метода
- Сжатие без потерь информации о связности полигональных сеток
Введение к работе
Актуальность
Цифровые методы хранения данных повсеместно вытесняют традиционные физические способы хранения. С самого начала компьютерной эры текстовые данные были перенесены в цифровую форму. Затем в нашу жизнь вошли так называемые мультимедиа-данные: цифровые фотографии, видео и музыка. Трехмерные цифровые модели объектов вытесняют физические макеты объектов.
При переводе цифровых данных в форму, удобную для человеческого восприятия, возникает множество научных задач. В мультимедиа-данных акцент сложности приходится на методы кодирования и сжатия данных. Методы сжатия применяются для экономии памяти при хранении мультимедиа-данных, а также для улучшения качества их восприятия при удаленной передаче по каналам данных с узкой пропускной способностью. Для цифровых трехмерных моделей1 научные исследования сосредоточены в основном на задаче их визуализации2.
Традиционные мультимедиа-данные неинтерактивны, т.е. человек может их только пассивно слушать и смотреть. Напротив, визуализация трехмерных моделей изначально обладала свойством интерактивности. Мультимедиа-данные аналитичны, поскольку создаются посредством анализа окружающего мира, напротив, природа трехмерных моделей синтетична, поскольку модель синтезируются при помощи компьютерного моделирования с участием человека. Разрозненность мультимедиа-данных и трехмерных моделей ощущается и на уровне стандартизации форматов данных. Стандартизация важна для обеспечения возможности создания и совместного использования информации между людьми. Только в недавно вышедшем стандарте MPEG-4 появилась возможность кодировать мультимедиа-данные и трехмерные модели в едином бинарном формате сцен BIFS, наследника языка виртуального моделирования VRML.
Трехмерные модели - модели, заданные в трехмерном пространстве. Различают трехмерные модели объемов, модели поверхностей и модели, основанные только на изображениях. В контексте диссертационной работы под трехмерной моделью, если не оговорено особо, подразумевается модель поверхности. Также под трехмерным видео будет подразумеваться не видео объема и не стерео-видео, а анимация поверхностей.
" В контексте диссертационной работы вместо термина визуализация более корректно использовать термин трехмерный рендеринг или экранизации, что означает процесс формирования дискретного двумерного изображения трехмерного объекта по его представлению в соответствии с параметрами наблюдения. Термин визуализация обозначает процесс геометризации некоторой сущности перед сё непосредственной экранизацией. Однако, в связи с малой распространенностью данных терминов в русском языке, здесь и далее будет использоваться термин визуализация.
На стыке мультимедиа, компьютерной графики и компьютерного зрения возникает новое направление, ориентированное на получение, обработку, кодирование и визуализацию трехмерных моделей поверхностей, полученных непосредственно из реального мира В отличие от других трехмерных моделей, эти модели получаются не в результате синтеза, а в результате анализа или трехмерного сканирования, что сближает их с мультимедиа-данными Различают пассивное сканирование, когда поверхность восстанавливается путем анализа фотографий поверхности, и активное, при котором расстояние до поверхности находится путем ее физического облучения. В отличие от многоугольных сеток (далее "полигонов"), обычно получаемых при создании моделей дизайнером, после трехмерного сканирования получаются дискретные модели поверхности
В полигональных моделях, созданных дизайнером, полностью задана геометрия поверхности и ее световые свойства В дискретной модели заданы лишь положения некоторых точек поверхности с ограниченной точностью и частичные данные о световых свойствах поверхности. Для дискретных моделей поверхностей актуальны задачи создания эффективных методов сжатия, активно применяемых для мультимедиа-данных, и создания методов быстрой визуализации, применяемых также для других трехмерных моделей. Обе задачи становятся особенно актуальными для представления объектов трехмерного видео и протяженных трехмерных сцен, где возникают большие объемы данных, которые необходимо сжимать, передавать, быстро декодировать и интерактивно визуализировать в реальном времени и в поточном режиме
Простым и широко используемым способом решения задач, связанных с дискретными моделями, является перевод их в полигональную форму. Таким образом, может показаться, что этим и решаются все проблемы. Однако поставим под сомнение этот тезис и более того, возможно, некоторые непрерывные полигональные модели эффективнее переводить в дискретную форму Сформулируем два вставших вопроса.
1 Полигональное представление требует задания явной геометрии и топологии для кусочно-плоских поверхностей, что естественным образом определяется в процессе моделирования дизайнером. Однако для данных, полученных из трехмерного сканера, представленных обычно множеством несвязанных трехмерных точек, понятия топологии, связности и даже поверхности не определены явным образом Таким образом, возникает вопрос о целесообразности использования полигонов для хранения дискретных моделей
2. Если объекты настолько детализированы, что размер проекций графических примитивов при визуализации меньше размеров пиксела экрана, то вместо сложных примитивов, таких как полигоны, можно использовать просто точки без потери качества визуализации. В этом случае отпадает необходимость в сложной структуре данных, включающей полигональные сетки, текстуры и текстурные координаты -можно использовать просто множество трехмерных точек. Возникает вопрос о целесообразности визуализации полигонами высоко-детализированных моделей.
Эти и другие вопросы включаются в область исследований диссертационной работы, схема предметной области которой показана на рисунке 1
Методы визуализации {качество, скорость}
Дискретные модели:
3D точки
карты глубин
фотографии
Как максимизировать эффективность по совокупности показателей: качество, скорость, размер?
Когда непрерывную модель эффективнее переводить в дискретную модель и наоборот?
Автоматические и полуавтоматические
\
методы получения:
Изображение на экране
трехмерный сканер, методы компьютерного
\>
Непрерывные модели:
полигоны
сплайны
текстуры
Компактное представление
зрения, результаты вычислений
Автоматизированные
Методы сжатия {размер}
методы моделирования
Область исследований
человеком
Рис. 1. Общая схема затрагиваемых предметных областей с выделенной в рамку областью исследований, являющейся темой диссертационной работы. Выделены основные показатели, составляющие критерий эффективности методов визуализации и сжатия: качество визуализации модели, скорость визуализации модели, размер - количество информации, необходимое дія записи модели.
Цель работы
Исследование и разработка новых методов визуализации и сжатия дискретных моделей поверхностей, обладающих большей эффективностью по сравнению с существующими методами. Совокупная оценка эффективности включает скорость синтеза изображений модели и объем информации, необходимый для представления модели. При этом синтез изображений при визуализации модели не должен содержать артефактов .
Адаптация разработанных методов для специализированных задач:
- интерактивная визуализация объектов с видозависимым цветом повер-хности;
'Артефакт - (от лат. artefactum - искусственно сделанное) - явление, процесс, предмет, свойство предмета или процесса, появление которого в наблюдаемых условиях по естественным причинам невозможно или маловероятно. Применительно к компьютерной графике - нежелательные особенности синтезированного при визуализации изображения, появляющиеся в определённых условиях.
интерактивная визуализация больших трёхмерных сцен;
визуализация потока кадров сжатого трёхмерного видеообъекта.
Определение условий, при которых более эффективным является использование дискретных моделей, нежели полигональных.
Реализация разработанных методов в виде отдельных программ и в виде программных модулей для интеграции в распространенные прикладные программные комплексы.
Научная новизна
Предложены новые виды дискретных моделей поверхностей объектов, для которых были предложены методы создания, сжатия и визуализации.
Практическая значимость и реализация
Разработаны и доведены до реализации предложенные методы создания, сжатия и визуализации дискретных моделей поверхностей трехмерных объектов. Реализованные алгоритмы удовлетворяют требованиям, сформулированным при постановке задачи, большинство из них запатентовано. Базовые предложенные представления моделей и методы их компрессии вошли в качестве форматов в стандарт 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., Корея, Сеул, 2004.
Научно-технологическом семинаре Intel, Inc., США, Сан-Хосе, 2000.
По теме диссертации имеется 8 публикаций. Предложенные методы защищены российскими и международными патентами.
Структура работы
Диссертация состоит из введения, трех глав, заключения и двух приложений.
В первой главе дана постановка задачи, вытекающая из поставленной цели. Сформулированы требования к методу представления трехмерной модели. С точки зрения этих требований дан обзор и проанализированы существующие способы представления трехмерных моделей и методов их представления. Описана предложенная автором модель и методы её получения. В двух следующих главах показывается, почему предложенная модель удовлетворяет сформулированным требованиям.
Во второй главе были описаны предложенные методы для визуализации предложенных в первой главе моделей. Глава состоит из четырех разделов, каждый из которых посвящен своей области исследований. Первый раздел описывает предложенный метод визуализации объектов с фиксированным цветом поверхности, где акцент делается на скорости визуализации. Во втором разделе решается задача о визуализации дискретных моделей, цвет поверхности которых изменяется в зависимости от угла просмотра поверхности. В третьем разделе рассматривается задача адаптивной визуализации в общем случае с удаленным сервером, хранящим сцену, и клиентом, на котором осуществляется визуализация. В четвертом разделе рассматривается другая задача, возникающая при визуализации сцен, -
обеспечение качества визуализации без артефактов при недостаточной частоте дискретизации4 участков сцены.
Третья глава посвящена методам сжатия и компактного представления. В первом разделе главы дан обзор методов сжатия мультимедийной информации, во втором разделе описывается предложенный метод сжатия статических дискретных моделей, в третьем разделе - предложенные методы сжатия объектов трехмерного видео.
В заключении приводится общий вид в результате построенной системы и области её применения. Сформулированы дальнейшие направления исследований и основные результаты работы.
В приложениях описан предложенный метод сжатия текстур и предложенный формат хранения данных в рамках стандарта.
Дан указатель основных терминов и список процитированной литературы.
Благодарности
Автор выражает благодарность:
Научному руководителю Ю.М. Банковскому за исходное определение направления исследований и предоставление возможности его развития.
Членам коллектива лаборатории "Компьютерный графики и мультимедиа МГУ" за полезные дискуссии и помощь на различных этапах работы, в особенности - ЛЛевковичу-Маслюку, АЛаршину, А.Конушину, А.Игнатенко, П.Калюжному, Б.Михайловичу, М.Федюкову, Д.Тимасову, С.Яковлеву и А.Соснову.
Фирмам, без финансовой поддержки которых многие идеи автора, касающиеся темы диссертационной работы, могли бы остаться только идеями - институту передовых технологий Samsung и компании Intel Inc. Компании ВидеоПорт за приобретенный автором профессиональный опыт в современных методах сжатия данных и работе с видео.
Коллегам и друзьям, в особенности ДС.Ватолину, родственникам, в особенности отцу О.А.Жиркову, за настойчивые напоминания о необходимости написания диссертации
Частота дискретизации = частота сэмплирования - частота, с которой аналогово-цифровой преобразователь {АЦП) производит замеры характеристик аналогового сигнала. Применительно не к реальному электронному устройству, а методу, вместо термина АЦП, говорят о методе перевода из непрерывной в дискретную форму. Как следует из теоремы Котельникова, частота дискретизации должна превышать наибольшую необходимую частоту сигнала в два раза.
Модели поверхностей и объемов
Как уже было замечено, "трехмерная модель" - общепринятый устоявшийся термин, но трехмерна лишь область пространства, в котором находится представляемый ею объект. Сама же "трехмерная" модель может представлять и поверхность - двумерное множество, и объем -трехмерное множество.
Модели поверхностей описывают только поверхность объекта в трехмерном пространстве. Наиболее распространенные до последнего времени были текстурированные полигональные представления поверхностей. С помощью текстур эмулируются материалы поверхностей и их свойства. Однако в последнее время замечается повышенный интерес к представлениям поверхностей с помощью точечных представлений и производных от них.
Модели объемов описывают весь объем объекта, содержащийся в нем. Обычно для этого используют вексельные структуры, представляющие из себя трехмерный растровый массив, элементы которого - вокселы - имеют базовый атрибут прозрачности или плотности, опционально атрибут цвета и другие. Данный массив называется вексельным, а пространство, которое он представляет, вексельным кубом.
Для большинства приложений достаточно моделирования только поверхностей объектов, модели объемов используют в достаточно узких областях - томографии, научной визуализации, моделировании природных явлений.
Можно выделить ещё один отдельный класс моделей - класс моделей, основанных на изображениях. Будем причислять его к моделям поверхностей, но условно, поскольку модели в привычном понимании в них нет. Синтез изображений в них происходит без явного участия геометрической модели из самих изображений. Данный класс также называют немодельным или классом моделей синтеза изображений по изображениям.
Векторные трехмерные модели состоят из множества элементарных векторных объектов, зафиксированных в единой системе координат. Векторные объекты можно подвергать аффинным преобразованиям без потери качества. К таким моделям принадлежат, например, полигональные сетки, а к элементарным векторным объектам их составляющих - полигоны, отрезки и точки.
Растровой объект определяет сразу всю геометрию своих подобъектов, заключенных в некотором пространстве, которые отличаются обычно лишь своими атрибутами. К растровым объектам относятся, в первую очередь, изображения и вексельные массивы, элементарные элементы которых называются соответственно пикселями и вокселами
При переводе векторного объекта в растровый, обратное восстановление векторного объекта без потери информации в общем случае невозможно.
Заметим, что человеческий глаз работает с растровой моделью мира, он регистрирует изображение в растровом массиве, в который попадают фотоны. Тогда как наш мозг, по всей видимости, наоборот, путем распознавания образов в растровой модели работает уже с векторной моделью.
Процесс перевода из растровой модели в векторную называется растеризацией. Обратный перевод - векторизация. Трехмерная модель задается двумя основными компонентами: 1. Задание области определения модели, которая задается геометрическим местом точек в трехмерном пространстве. 2. Определение свойств модели на заданном множестве.
Дискретные и непрерывные модели отличаются мощностью множества определения модели. Дискретная трехмерная модель — модель, определенная на конечном множестве точек. Непрерывная трехмерная модель - модель, заданная на множестве мощности континуум.
Очевидно, что в цифровой форме модель не может быть задана на бесконечном множестве, поскольку в цифровой форме может быть задано только конечное количество координат точек. Поэтому, данное определение при задании модели в цифровой форме надо воспринимать с точки зрения математической абстракции.
К непрерывным объектам относятся полигональные модели и модели свободных форм. К трехмерным дискретным объектам относятся точечные модели и карты глубин.
Чисто растровые модели — изображения и воксельные массивы - сложно однозначно отнести к дискретным или непрерывным. С одной стороны, они задаются таблицами точечных значений, и поэтому дискретны. С другой стороны, значения модели считаются определенными не только в точках, но и на всем пространстве через интерполяционные функции и с этой точки зрения, они являются непрерывными.
Процесс перевода из векторной модели в дискретную называется дискретизацией.
Объектный способ подразумевает задания модели путем прохода примитивов, указывая их положения в пространстве. Пространственный способ, наоборот, осуществляется путем обхода пространства, указывая, какие примитивы расположены в данной области.
Приведем следующий простой пример. Пусть есть бинарное изображение. Можно его записать построчно как последовательность пикселей, а можно записать координаты черных точек. Если концентрация черных точек большая, то компактнее использовать пространственный способ, если маленькая, то объектный. Но обычно выбор осуществляется не по критерию компактности, а по способу обращения с моделью. Если необходимо обращаться с объектами по их идентификаторам, то предпочтительнее объектный способ, если же по положению в пространстве, то пространственный. На практике обычно используют смешенный тип задания, либо объектно-пространственный, когда используются отдельные объекты, каждый из которых записан по пространственному способу, либо пространственно-объектные, которые используют пространственную структуризацию для задания объектов.
Грань между явными и неявными способами задания трехмерных моделей провести достаточно сложно. Проще привести пример с двумерными моделями изображений. Явный способ задания - определение матрицы цветов. Неявные способы делятся на процедурные и фрактальные. При процедурном способе текстура задается некоторым неявным аналитическим выражением. Фрактальный или итерационный способ задания - когда изображение задается посредством итераций, применяемых к исходному или единичному изображению.
Интерактивность и фотореалистичность визуализации
Рассмотрим методы визуализации с точки зрения свойства интерактивности и свойства фотореалистичности. Интерактивным можно считать визуализацию со скоростью не менее одного кадра в секунду, а визуализацию реального времени (либо плавно-интерактивную, либо высоко-интерактивную, либо с однородным движением), начиная со скорости 10-15 кадров в секунду, когда человек начинает воспринимать последовательность кадров как непрерывное движение. Максимальное количество кадров в секунду, которых человек может различать, зависит от конкретного человека, но в среднем составляет 40 Гц.
Фотореалистичным считается такое качество визуализации, при котором человек не замечает разницу между фотографией реального объекта и визуализированной моделью объекта, такое качество компьютерной графики позволяет делать эффекты для киноиндустрии.
Полигональные представления при использовании алгоритмов обратной трассировки лучей, в особенности с применением эффектов глобальной освещенности, можно назвать фотореалистичными, но не интерактивными, хотя сейчас и существуют специальные методы интерактивной трассировки лучей, но он осуществляется за счет потери качества и некоторых ограничений. Проективные методы в основном нацелены на интерактивность, а при использовании современных аппаратных ускорителей даже позволяет визуализировать достаточно сложные сцены со скоростью большей, чем необходимо человеку для достижения эффекта плавности анимации. Качество визуализации проективных методов также постоянно растет, но оно ещё недостигло уровня фотореализма, и его правильней называть просто высококачественным.
Качество визуализации вексельных объемных представлений можно назвать фотореалистичным, но только для полупрозрачных объектов с нулевой отражающей компонентой, на которых и специализируются воксельные представления. Скорость синтеза изображений из-за огромных массивов исходных данных, обычно в лучшем случае дотягивает до интерактивной.
Качество визуализации точечных моделей и моделей, основанных на изображениях с глубиной, сложно отнести к фотореалистичному даже при использовании последних достижений в области сплаттинга и использовании детализированных моделей, сканированных из реального мира. Одна из причин - использование диффузных поверхностей и простых методов прямого освещения. Скорость визуализации можно считать интерактивной Хотя ситуация в ближайшие годы может измениться, поскольку появились публикации о визуализации точечных моделей с использованием глобальной освещенности с почти интерактивной скоростью.
Качество визуализации некоторых моделей, основанных на изображениях, можно отнести к фотореалистичным, а скорость к интерактивной. Это относится в основном к моделям типа панорамных, однако, это достигается в достаточно узкой области применения, где данные модели могут быть применены. Также в большинстве из них область навигации сильно ограничена, наиболее популярные модели ограничивают возможность навигации поворотами камеры без возможности поменять положения камеры.
Заметим, что к моделям, отвечающим и свойству интерактивности и фотореалистичности, и являющимися достаточно универсальными для представления объектов, по мнению автора, можно считать только уже упоминаемое гибридное представление поверхностных световых полей.
Эффективное сжатие термин достаточно условный, можно сказать, что для таких представлений как изображение, аудио и, особенно видео, разработаны эффективные методы. Коэффициент сжатия в этих областях, по сравнению с несжатым представлением без воспринимаемых человеком отличий, составляет порядка 10-ти для аудио, 20-ти раз для изображений и порядка ста раз для видео. Эффективное сжатие мультимедиа данных невозможно без такого важного свойства как устойчивость к сжатию с потерями.
Сжатие полигональных моделей хорошо исследованная область, однако, в силу сложной топологической части, сжатое представление нельзя назвать высокоэффективным и компактным для сложных и реалистичных объектов. Причина - сжатие таких представлений неустойчиво к сжатию с потерями, в особенности топологической составляющей представления.
Компрессию точечных моделей нельзя назвать глубоко исследованной задачей. В целом такое сжатие пока нельзя также назвать эффективным.
Сжатие моделей, основанных на изображениях с глубиной, можно считать относительно эффективным и просто реализующимся, однако, здесь возникает ряд проблем, о которых будет подробно рассказано в главе, посвященной сжатию.
Сжатие моделей, основанных на изображениях, также в целом неисследованная задача, хотя сжатие отдельных изображений, как уже упоминалось, эффективно.
Что касается гибридного представления моделей - метода световых полей, то для них в настоящее время разработано большое количество достаточно эффективных методов компрессии. Эти методы будут обсуждаться более детально в главе, посвященной сжатию.
Под универсальностью в данном случае подразумевается возможность эффективно представлять модели поверхностей, созданных различным способом: 1. Модели, созданные дизайнером - сводятся к полигональным моделям 2. Модели, полученные полу- или полностью автоматически посредством трехмерного сканирования или компьютерного зрения - сводятся к точечным моделям или картам глубины. 3. Модели, используемые для визуализации результатов научных экспериментов и представимые поверхностями, большинство из которых сводится к неявнозаданной функции, например, изо-поверхности многомерных функций.
Дополнительное требование к универсальности модели - отсутствие ограничений на геометрическую и фотометрическую сложность модели.
Хотя в настоящее время существует множество методов перевода из одних моделей в другие, при этом в большинстве случаев эффективность исходного и конечного представления модели при этом существенно уменьшается. Например, если перевести синтетическую полигональную модель, состоящую в основном из большого количества плоских поверхностей, в точечную, то такая модель будет проигрывать исходной по скорости, размеру и качеству. И наоборот, полученная из трехмерного сканера модель в большинстве случаев после перевода в полигональную, не выиграет в качестве, а потеряет в размере и скорости визуализации.
Поэтому на настоящий момент не существует представления модели, которое было бы универсально и могло заменить остальные без ущерба для эффективности.
Оценка сравнительной вычислительной сложности предложенного метода
В таблице 3 приведем известные по статьям скорости визуализации дискретных моделей без использования полигонального ускорения и сравним со скоростью, полученной при реализации нашего метода. Однотипные методы и соответственно схожие скорости не вошли в таблицу. За скорость предложенного метода возьмем опубликованные в 2001 году результаты [15], которые в настоящее время улучшены, но не существенно.
Заметим, что скорость реализации на CPU можно считать пропорциональной теоретической алгоритмической сложности при условии отсутствия использований SIMD-инструкций (напр., команд ММХ и SSE). Реализация, основанная на ускорителях полигональной графики или на универсальных GPU, обычно существенно быстрее вследствие существенно более мощных графических процессорах по сравнению с универсальными CPU. Так, реализация упомянутого здесь "ЕУ/А"-сплаттинга на GPU дала более чем десятикратный прирост скорости [74].
Посчитаем количество операций, необходимых для осуществления трехмерного преобразования в случае использования прямого вычисления для каждого воксела, и предложенного метода иерархической трансформации. Для прямого метода нам потребуется количество вокселов на нижнем уровне Мюкс[п], а для предложенного метода количество всех вершин в октодереве Мверш[п]. Сведем уже известные подсчеты количества операций в таблице 4.
Посчитаем отношение теоретических вычислительных сложностей прямого трехмерного преобразования и предложенного иерархического метода, пренебрегая вычислениями, не зависящими от количества точек, получим:
Видно, что дальнейшему упрощению мешает то, что знаменатель зависит от соотношения количества вершин к количеству вокселов, т.е. листовых вершин. Зададимся вопросом: можно ли далее упростить данное выражение и сделать его оценку без привязки к количеству уровней и конкретной модели. Следующие подразделы раздела 2.1.4 будут посвящены этому вопросу.
Причем семантика параметра "D" - топологическая размерность множества, а "к" - мера множества в данной размерности. Сведем в таблице 5 полученные результаты.
Для случая точечной модели доказательство элементарное, приведем его. Возьмем некоторое множество точек. Выберем є 0, такое, что расстояние между любыми двумя точками было не меньше чем є. Вексельная модель, построенная по этому множеству, начиная с масштабного уровня п0 = log2() +1, будет содержать ровно столько вокселов, сколько точек в исходной модели, итого, получим М еокс(п,к,0) = к,М верш(п,к,0) = пк. Как не сложно видеть, асимптотические формулы для D=0 выполняются, более того для п п0 формула становится тождеством: М еОкс[п]=М еоКс(п,к,0). Приведем доказательство для случая полигональной модели, а случаи линии и объемной модели доказываются похожим способом и будут пропущены.
Докажем, что в случае, когда октодерево получается из обычного полигонального представления, т.е. представлено конечным множеством полигонов с ненулевой площадью, существует следующий ненулевой предел:
Рассмотрим полигон под номером t с площадью SftJ. Спроецируем его на сторону вексельного куба, соответствующего октодереву, где его площадь проекции SMWCPTOJ [t] максимальна. Не сложно показать, что минимум отношения SMaxProJ [t]/S[t] достигается тогда, когда проекции на все стороны куба равновелики, и равны , таким образом:
Из математического определения площади не сложно вывести, что площадь пикселов грани куба, покрываемых проекцией с площадью SMaKcn полигона, при увеличении разрешения изображения, равного 2", стремится к площади этой проекции: ПШ , 2п МаксПроещІЧ л- оо 2
Исходя из метода построения бинарного вексельного растра, количество единичных вокселов при растеризации полигона равно его проекции на грань с минимальным углом с полигоном. Или, что эквивалентно, на грань, где площадь проекции максимальна.
Таким образом, данный предел справедлив и для количества единичных вокселов, содержащихся в растерном кубе: ПШ -2л - 2L, lim 2л І ЬмаксПроехчІЧ-К, n- oo J t=no всем полигонам л- оо J t=no всем полигонам Поскольку пределы существуют, то: 3S k S 3 Где S - площадь поверхности всей полигональной сетки.
Таким образом, для объектов, поверхность которых представима полигонами, мы доказали, что исходный предел действительно существует. Причем D = 2, а к — величина предела, границы ограничения которого пропорциональны площади объекта.
Сжатие без потерь информации о связности полигональных сеток
В отличие от рассмотренных методов, методы компрессии дискретных моделей находятся только на этапе становления. И в большинстве случаев можно говорить только о методах компактного представления, но не о методах сжатия как таковых. Точную границу между компактным представлением и сжатием провести сложно, по мнению автора, компактное представление должно обладать свойством прямого доступа к каждому элементу и, как следствие, не использовать методы учета- корреляционных зависимостей между отдельными элементами.
Исходя из такой терминологии, большинство точечных представлений дискретных моделей являются компактными, но не компрессированными представлениями. Например, в работах [5] и [8] для каждой точки в явном виде хранятся координаты точки, направления нормали, размеры сплата и цвет. Как бы мы сильно не квантовали и не выделяли минимальное количество бит на каждый из данных атрибутов, суммарное количество информации без потери качества и универсальности для каждой точки будет не менее 5 байт. Т.е. методы компакного хранения точек по отдельности сильно ограничены по степени сжатия.
Основная решаемая задача в данных работах - повышение скорости визуализации модели. А задача минимизации объема представления моделей не относилась к важными и серьёзно не исследовалась.
Однако для моделей, основанных на световых полях и поверхностных световых полях, задача сжатия очень важна. Исходные данные в этих моделях включают сотни тысяч фотографий и без сжатия данного объема их просто нельзя будет визуализировать в реальном масштабе времени. Для этих представлений степени сжатия варьируются обычно от 100:1 до 1000:1. Задачу сжатия световых полей сводят к задаче сжатия видео, а в качестве временной оси используют обход камер вокруг объекта [137]. Для сжатия световых поверхностных полей используют технологию, которая уже обсуждалась нами при описании методов визуализации. Напомним только основную идею: рассматривают 4-х мерную функцию излучения в каждой точке поверхности и для каждого полигона сводят её к сумме произведений функций от двух переменных. Эти функции называются картами световых полей (light field maps) [46]. Наиболее эффективный метод сжатия этих полей основывается на использовании векторного квантования карт световых полей с последующим сжатием по алгоритму сжатия текстур S3TC [138], что позволяет использовать одно и то же представление для цвета, как в памяти, так и для долговременного хранения. Поскольку полигональная составляющая в поверхностных световых полях является достаточно грубой, то после её сжатия одним из описанных ранее методов, она сильно не влияет на суммарный размер модели. Наиболее эффективные методы сжатия дают порядка одного мегабайта на среднюю модель с линейным разрешением изображений порядка 512.
Отметим работу 2002 года по сжатию бинарно-воксельных массивов поверхностей без потерь [139]. Бинарно-воксельный массив эквивалентен с точки зрения модели рассматриваемому в нашей работе бинарно-воксельному октодереву, однако данные там представлены не иерахически, а линейно. В этой работе используется библиотека из сотен стандартных разбиений бинарного массива 3x3x3 и корреляция локального контекста воксела с этим массивом используется при сжатии. Данный метод позволяет умещать информацию об одном непустом вокселе примерно в одном бите, что существенно превышает степень сжатия как полигонов, так и точек по количеству бит на примитив.
Другой класс моделей, имеющий непосредственное отношение к нашей работе, является класс моделей трехмерного видео. Различают несколько совершенно разных моделей, называющихся трехмерным видео, что может приводить к путанице. Во-первых, стоит различать классификацию трехмерных дисплеев и трехмерных видеопредставлений. Можно визуализировать трехмерное видео представление на обычном дисплее, а также существуют технологии, показывающие на стереодисплеях обычное видеоизображение со стереоэффектами.
Разделим представления трехмерного видео на следующие типы: Стереоскопическое видео ? Сферическое (всенаправленное) видео ? Панорамное видео ? Много-камерное видео {Multi-View video) ? Видео с возможностью указания произвольной точкой зрения, видео с геометрической моделью Потоковая передача параметров модели лица О Видеотекстуры Дисплейные технологии разделим на следующие: ? Обычный дисплей ? Стерео очки ? Стерео экран ? Голограммы ? Объемный экран
В 3D Видео существует 3 проблемы .- проблема получения, проблема записи/передачи и проблема трехмерной визуализации. Проблему получения трехмерного видео решают двумя способами — получение из обычного видео, например, в [140] [141] используют алгоритмы компьютерного зрения, либо при помощи аппаратных трехмерных сканеров, которые уже научились выдавать динамические данные [142]. Очевидны плюсы и минусы обоих способов. Первый способ универсальный, он не требует специального оборудования, однако он ограничен определенными типами трехмерных сцен. Так методы, основанные на кадровой задержке (frame delay) применимы лишь в случае, когда все объекты на переднем плане движутся в одном направлении. Методы, пытающиеся восстанавливать полную геометрию по видео (shape from motion), можно использовать только для ограниченного количества статических сцен. Поэтому универсальных способов пока только два - использование аппаратных методов съёмки окружающей реальности, либо использование уже готовых трехмерных синтетических анимированных сцен. Для реализации последней возможности было разработано расширение стандарта MPEG-4 - AFX, позволяющее представлять и записывать анимированные трехмерные сцены. Одним из вошедших в этот стандарт методов является предложенная разработка, которая будет описана в разделе 3.3, а детали стандарта в приложении.
