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

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

Реферат

 

Изобретение относится к представлению трехмерных объектов на основе изображений с глубиной. Его применение, при визуализации трехмерного изображения в компьютерной графике и анимации позволяет получить технический результат в виде обеспечения компактности хранения информации об изображении, быстрой визуализации с высоким качеством выходного изображения. Этот результат достигается благодаря тому, что способ включает в себя этапы, на которых: создают поле текстуры, в которое записывают цветное изображение, содержащее информацию о цвете для каждого пиксела; создают поле глубины, в которое записывают изображение с глубиной, содержащее информацию глубины для каждого пиксела, и генерируют узел простой текстуры путем объединения поля текстуры и поля глубины в заданном порядке. 8 н. и 15 з.п. ф-лы, 36 ил., 10 табл.

I. Область изобретения

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

II. Предшествующий уровень техники

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

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

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

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

СУЩНОСТЬ ИЗОБРЕТЕНИЯ

Одним из аспектов настоящего изобретения является создание способа генерирования структуры узлов для компьютерной графики и анимации, предназначенных для представления трехмерных объектов с использованием изображений с глубиной и называемых представлениями на основе изображений с глубиной (ПОИГ), которые были приняты в качестве Расширения Структуры Анимации (РСА) формата MPEG-4.

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

Согласно другому аспекту, структура узла, основывающаяся на изображениях с глубиной, включает в себя поле size (размер), в которое записана информация о размере плоскости изображения; поле resolution (разрешение), в которое записано разрешение по глубине для каждого пикселя; поле depth (глубина), в которое записано множество сегментов информации о глубине, относящейся к каждому пикселю, и поле color (цвет), в которое записана информация о цвете, относящаяся к каждому пикселю.

Согласно еще одному аспекту, структура узла, основывающаяся на изображениях с глубиной, включает в себя поле viewpoint (точка наблюдения), в которое записана точка наблюдения плоскости изображения; поле visibility (область наблюдения), в которое записана область наблюдения от точки наблюдения до плоскости изображения; поле projection method (способ проецирования), в которое записан способ проецирования из точки наблюдения на плоскость изображения;

поле distance (расстояние), в которое записано расстояние от ближней плоскости до дальней плоскости, и поле texture (текстура), в которое записано цветное изображение.

Согласно еще одному аспекту, структура узла на основе изображений с глубиной включает в себя поле resolution (разрешение), в которое записано максимальное число листьев октодерева, расположенных вдоль грани заключающего его куба, который содержит объект; поле octree (октодерево), в которое записана структура внутреннего узла октодерева; поле index (индекс), в которое записан индекс эталонного изображения, соответствующего данному внутреннему узлу, и поле image (изображение), в которое записано эталонное изображение.

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

КРАТКОЕ ОПИСАНИЕ ЧЕРТЕЖЕЙ

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

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

фиг.2 - схема структуры октодерева и порядок дочерних углов;

фиг.3 - график, иллюстрирующий степень сжатия октодерева;

фиг.4 - схема примеров многослойного изображения с глубиной (МИГ): (а) иллюстрирует проекцию объекта, где темные ячейки (воксели) соответствуют единицам, а белые ячейки - нулям, а (б) иллюстрирует двумерное сечение в координатах (x, глубина);

фиг.5 - схема, иллюстрирующая цветовую компоненту модели "Ангел" после переупорядочивания ее цветовых данных;

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

фиг.7, 8 и 9 - данные сжатия геометрии для лучшего способа, основывающегося на предсказании посредством частичного совпадения (ПЧС);

фиг.10 - схема, иллюстрирующая два способа переупорядочивания поля color (цвет) модели "Ангел" формата PointTexture (точечная текстура) в двумерное изображение;

фиг.11 - схема примеров сжатия геометрии без потерь и сжатия цвета с потерями: (а) и (б) - соответственно, исходная и сжатая версии модели "Ангел", а (в) и (г) - соответственно, исходная и сжатая версии модели "Мортон256";

фиг.12 - схема, иллюстрирующая модель "Ангел" в формате бинарного волюметрического октодерева (БВО) и модель "Ангел" в формате текстурированного БВО (ТБВО);

фиг.13 - схема, иллюстрирующая дополнительные изображения, снимаемые дополнительными камерами в случае ТБВО: (а) - изображение индекса камеры, (б) - первое дополнительное изображение и (в) - второе дополнительное изображение;

фиг.14 - схема, иллюстрирующая пример записи потока данных БВО: (а) иллюстрирует структуру дерева ТБВО. Серый цвет соответствует "неопределенному" символу текстуры. Каждый цвет обозначает индекс камеры, (б) иллюстрирует порядок обхода октодерева в узле БВО и индексы камер, (в) иллюстрирует результирующий поток данных ТБВО, в котором заполненные кубы и куб октодерева обозначают байты текстуры и байты БВО, соответственно;

фиг.15, 17, 18 и 19 - схемы, иллюстрирующие сжатие ТБВО для моделей "Ангел", "Мортон", "Пальма512" и "Роботы512", соответственно;

фиг.16 - схема, иллюстрирующая изображения моделей "Ангел" и "Мортон", полученные после избирательного удаления части вокселей;

фиг.20 - схема примера изображения рельефной текстуры и карты глубины;

на фиг.21 приведена схема примера многослойного изображения с глубиной (МИГ): (а) иллюстрирует проецирование объекта, а (б) иллюстрирует многослойные пиксели;

фиг.22 - схема примера блочной текстуры (БТ), в котором для визуализации показанной в центре модели используются шесть объектов SimpleTexture (простой текстуры) (пары изображения и карты глубины);

фиг.23 - схема примера обобщенной блочной текстуры (ОБТ): (а) иллюстрирует положения камеры для модели "Пальма", (б) иллюстрирует плоскости эталонных изображений для той же самой модели (используется 21 объект SimpleTexture);

фиг.24 - схема примера, показывающего двумерное представление октодерева: (а) иллюстрирует "облако точек", (б) иллюстрирует соответствующие усредненные карты;

фиг.25 - псевдокод, предназначенный для записи битового потока ТБВО;

фиг.26 - спецификация узлов ПОИГ;

фиг.27 - схематичное представление объемной модели для DepthImage (изображение с глубиной): (а) в перспективе, (б) в ортогональной проекции;

фиг.28 - псевдокод визуализации SimpleTexture, основывающегося на OpenGL;

фиг.29 - пример, иллюстрирующий сжатие эталонного изображения в формате SimpleTexture: (а) иллюстрирует исходное эталонное изображение, и (б) иллюстрирует модифицированное эталонное изображение в формате JPEG;

фиг.30 - пример, иллюстрирующий результат визуализации модели "Мортон" в соответствии с различными форматами: (а) в исходном полигональном формате, (б) в формате DepthImage (изображение с глубиной) и (в) в формате OctreeImage (изображение октодерева);

фиг.31 - примеры визуализации: (а) иллюстрирует сканированную модель "Башня" в формате DepthImage, (б) иллюстрирует ту же самую модель в формате OctreeImage (данные сканера использовались без удаления шумов, поэтому в верхней части модели видны черные точки);

фиг.32 - примеры визуализации модели "Пальма": (а) иллюстрирует исходный полигональный формат, (б) иллюстрирует ту же самую модель, но в формате DepthImage;

фиг.33 - пример визуализации, иллюстрирующий кадр из анимации "Дракон512" в формате OctreeImage;

фиг.34 - пример визуализации модели "Ангел512" в формате PointTexture;

фиг.35а и 35б - схемы, иллюстрирующие взаимоотношения соответствующих узлов при представлении объекта в формате DepthImage, имеющем узлы SimpIeTexture и узлы PointTexture, соответственно;

фиг.36 - схема, иллюстрирующая структуру соответствующего узла OctreeImage при представлении объекта посредством узлов OctreeImage.

ПОДРОБНОЕ ОПИСАНИЕ ПРЕДПОЧТИТЕЛЬНЫХ ВАРИАНТОВ ОСУЩЕСТВЛЕНИЯ

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

Ниже излагается изобретение, описанное в предварительной заявке №60/333167 на патент США, поданной 27 ноября 2001 г. и озаглавленной "Способ и устройство для кодирования данных представления на основе изображений в трехмерной сцене".

I. КОДИРОВАНИЕ ДВИЖУЩИХСЯ ИЗОБРАЖЕНИЙ И АУДИОСИГНАЛОВ В СООТВЕТСТВИИ С ISO/IEC JTC 1/SC 29/WG 11

1. Введение

В этом документе приведены результаты основного эксперимента РСА А8.3 по визуализации на основе изображений. Основной эксперимент касается технологии визуализации на основе изображений, в которой используются текстуры с информацией о глубине. Также представлены некоторые изменения, внесенные в спецификацию узлов на основе экспериментов, выполненных после 57-го заседания Экспертной Группы по вопросам Движущегося Изображения (MPEG) и обсуждений во время заседания Специальной Группы РСА, прошедшего в октябре.

2. Экспериментальные результаты

2.1 Тестовые модели

Для неподвижных объектов

Узел DepthImage (изображение с глубиной) с SimpleTexture (простой текстурой)

Собака

Тиранозавр (DepthImage, с использованием около 20 камер)

Монстр (DepthImage, около 20 камер)

ChumSungDae (DepthImage, сканированные данные)

Пальма (DepthImage, 20 камер)

Узел DepthImage с LayeredTexture (многослойной текстурой)

Ангел

Узел DepthImage с PointTexture (точечной текстурой)

Ангел

Узел OctreeImage (изображение октодерева)

Существо

Для анимированных объектов

Узел DepthImage с SimpleTexture

Дракон

Дракон в окружении сцены

Узел DepthImage с LayeredTexture

Не предоставлен

Узел OctreeImage

Робот

Дракон в окружении сцены

Дополнительные данные (полученные в результате сканирования или моделирования) будут предоставлены в будущем.

2.2 Результаты тестов

Все предложенные в Сиднее узлы интегрированы в эталонное программное обеспечение blaxxun contact 4.3. Тем не менее, исходные коды до сих пор не загружены на сервер Системы Управления Версиями (СУВ).

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

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

(Фигура удалена)

3. Обновления спецификации узлов ПОИ

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

Декодер (битовые потоки) - спецификация узлов

Узел DepthImage определяет одну текстуру СИИ. Когда несколько узлов DepthImage связаны друг с другом, они обрабатываются как группа, и, таким образом, их следует подчинить одному и тому же узлу Transform (преобразование).

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

Поля position (положение) и orientation (ориентация) задают относительное положение точки наблюдения текстуры ПОИ в местной системе координат. Положение определяется относительно начала (0, 0, 0) системы координат, в то время как ориентация задает поворот относительно ориентации, принятой по умолчанию. В положении и ориентации, принятым по умолчанию, наблюдатель находится на оси Z и смотрит вниз по оси -Z в направлении начала координат со смещением +Х вправо и +Y вверх. Однако, иерархия преобразований влияет на конечные положение и ориентацию точки наблюдения.

Поле fieldOfView (область наблюдения) задает угол наблюдения от точки наблюдения камеры, определяемой полями position и orientation. Первая величина обозначает угол с горизонтальной стороной, а вторая величина обозначает угол с вертикальной стороной. Значения, принятые по умолчанию, равны 45 в радианах. Однако в случае, если поле orthogonal (ортогональное) задано как TRUE (истинно), поле fieldOfView обозначает ширину и высоту ближней плоскости и дальней плоскости.

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

Поле orthogonal задает тип вида текстуры ПОИ. В случае, если данное поле установлено равным TRUE, текстура ПОИ основывается на ортогональном виде. В противном случае текстура ПОИ основывается на перспективном виде.

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

position

orientation

fieldOfView

nearPlane

farPlane

orthogonal

diTexture

однобайтовый заголовок, предназначенный для флагов наличия/отсутствия вышеперечисленных полей.

Узел SimpleTexture определяет отдельный слой текстуры ПОИ.

Поле texture задает плоское изображение, которое содержит цвет для каждого пикселя. Оно относится к одному из множества типов узлов текстур (ImageTexture (текстура изображения), MovieTexture (текстура кинофрагмента) или PixelTexture (пиксельная текстура).

Поле depth (глубина) задает глубину для каждого пикселя в поле texture. Размер карты глубины должен совпадать с размером изображения или кинофильма в поле texture. Это поле относится к одному из множества типов узлов текстур (ImageTexture, MovieTexture или PixelTexture). В случае, если узел depth равен NULL или поле depth не задано, альфа-канал в поле texture будет использоваться в качестве карты глубины.

Узел PointTexture определяет множество слоев точек ПОИ.

Поля width (ширина) и height (высота) задают ширину и высоту текстуры, соответственно.

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

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

(Фиг.1 и 2 удалены)

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

Поле octreeresolution (разрешение октодерева) задает максимальное число листьев октодерева, расположенных вдоль грани заключающего его куба. Уровень октодерева можно определить из поля octreeresolution (разрешение октодерева), используя следующее уравнение: octreelevel = int (log2 (octreeresolution -1)) +1).

Поле octree (октодерево) задает набор внутренних узлов октодерева. Каждый внутренний узел представлен байтом. 1 в i-м бите из этого байта означает, что для i-го дочернего узла рассматриваемого внутреннего узла существуют дочерние узлы, в то время как 0 означает, что этих узлов не существует. Порядок внутренних узлов - это порядок обхода октодерева по схеме "сначала в ширину". Порядок для восьми дочерних узлов внутреннего узла приведен на фиг.2.

(Фиг.3 удалена)

Поле octreeimages (изображения октодерева) задает набор узлов DepthImage, где в качестве поля diTexture выступает SimpleTexture. Однако, поля nearPlane и farPlane узла DepthImage и поле depth узла SimpleTexture не используются.

Поле octreeUrl задает адрес потока данных octreeImage, который включает в себя:

заголовок для флагов

octreeresolution

octree

octreeimages (множество узлов DepthImage)

nearPlane не используется

farPlane не используется

diTexture SimpleTexture без поля depth

Ниже излагается изобретение, описанное в предварительной заявке №60/363545 на патент США, поданной 8 марта 2002 г. и озаглавленной "Способ и устройство для сжатия и формирования потока данных представления на основе изображений с глубиной".

II. КОДИРОВАНИЕ ДВИЖУЩИХСЯ ИЗОБРАЖЕНИЙ И АУДИОСИГНАЛОВ В СООТВЕТСТВИИ С ISO/IEC JTC 1/SC 29/WG 11

1. Введение

В этом документе приведены результаты основного эксперимента РСА А8.3 в области представлений на основе изображений с глубиной (ПОИГ). Данный основной эксперимент касается узлов представлений на основе изображений с глубиной, для которых используются текстуры с информацией о глубине. Эти узлы получили одобрение и были включены в предложение для Редакционной Комиссии во время заседания в Паттайе. Однако работы по преобразованию этой информации в поток данных посредством поля octreeUrl узла OctreeImage и поля depthImageUrl узла DepthImage все еще продолжаются. Настоящий документ описывает формат формирования потока данных, связанных этими полями url. Формат формирования потока данных включает в себя сжатие поля octree узла OctreeImage и полей depth/color узла PointTexture.

2. Формат формирования потока данных для octreeUrl

2.1 Формат потока

Узел OctreeImage включает в себя поле octreeUrl, которое задает адрес потока данных OctreeImage. Этот поток может дополнительно включать в себя:

заголовок для флагов

octreeresolution

octree

octreeImages (множество узлов DepthImage)

nearPlane не используется

nearPlane не используется

diTexture SimpleTexture без поля depth

Поле octree задает набор внутренних узлов октодерева. Каждый внутренний узел представлен байтом. 1 в i-м бите из этого байта означает, что для i-гo дочернего узла рассматриваемого внутреннего узла существуют дочерние узлы, в то время как 0 означает, что этих узлов не существует. Порядок внутренних узлов - это порядок обхода октодерева по схеме "сначала в ширину". Порядок для восьми дочерних узлов внутреннего узла приведен на фиг.2.

(Фиг.1 удалена)

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

2.2. Схема сжатия для поля octree

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

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

2.2.1. Сжатие octree

Для сжатия поля octree, представленного в форме октодерева с порядком обхода по схеме "сначала в глубину", нами разработан способ сжатия без потерь, в котором используются некоторые идеи подхода, известного как предсказание посредством частичного совпадения (ПЧС) [1, 2]. Основная используемая идея состоит в "предсказании" (то есть, оценке вероятности) следующего символа посредством нескольких предшествующих символов, которые называются "контекст". Для каждого контекста существует таблица вероятности, содержащая оцененную вероятность появления каждого символа в этом контексте. Эта процедура используется в комбинации с арифметическим кодером, называемым кодером дальности [3, 4].

Двумя основными отличительными признаками данного способа являются:

1) использование порождающего узла в качестве контекста для дочернего узла;

2) использование предположения об "ортогональной инвариантности" с целью уменьшения числа контекстов.

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

Кодирование - это процесс построения и обновления таблицы вероятности в соответствии с контекстной моделью. В прелагаемом способе контекст моделируется как иерархия "порождающий узел - дочерний узел" в структуре октодерева. Во-первых, мы определяем символ как узел размером в один байт, биты которого указывают на заполнение подкуба после внутреннего разбиения. Следовательно, каждый узел октодерева может представлять собой символ, а его числовое значение лежит в пределах от 0 до 255. Таблица вероятности (ТВ) содержит 256 целых чисел. Значение i-й переменной (0i255), деленное на сумму всех переменных, равно частоте (оценке вероятности) появления i-го символа. Таблица вероятности контекстов (ТВК) - это набор таблиц ТВ. Вероятность символа определяется из одной и только одной из таблиц ТВ. Число конкретных таблиц ТВ зависит от контекста. Пример ТВК приведен в таблице 1.

Кодер работает следующим образом. Сначала он использует 0-контекстную модель (то есть, одна и та же ТВ для всех символов, в исходном состоянии характеризуемая равномерным распределением элементов и обновляемая после каждого нового кодового символа). Дерево обходится в порядке обхода по схеме “сначала в глубину”. После того, как собран достаточный объем статистических данных (эмпирически определенное значение соответствует 512 кодовым символам), кодер переключается на 1-контекстную модель. Она содержит 27 контекстов, которые задаются следующим образом.

Рассмотрим набор из 32 фиксированных ортогональных преобразований, которые включают в себя преобразования симметрии и повороты на 90 относительно осей координат (см. Приложение 2). Далее, мы можем категоризировать символы в соответствии с шаблоном заполнения их подкубов. Согласно нашему способу, имеются 27 наборов символов, в данном документе называемых группами, которые характеризуются следующим свойством: 2 символа связаны посредством одного из этих фиксированных преобразований тогда и только тогда, когда они принадлежат одной группе.

В байтовом обозначении группы представлены 27 наборами чисел (см. Приложение 2). Мы полагаем, что таблица вероятности зависит не от самого порождающего узла (в этом случае мы получили бы 256 таблиц), а только от группы (обозначаемой в таблице 1 как ParentSymbol), к которой принадлежит этот порождающий узел (таким образом, 27 таблиц).

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

После кодирования 2048 (еще одно эвристическое значение) символов в соответствии с 1-контекстной моделью, мы переключаемся на 2-контекстную модель, которая использует пары (ParentSymbol, NodeSymbol) в качестве контекстов. NodeSymbol просто представляет собой положение текущего узла в порождающем узле. Таким образом, у нас есть 27*8 контекстов для 2-контекстной модели. В момент переключения на эту модель таблицы ТВ, полученные для каждого контекста, используются для каждого узла "внутри" этого контекста и с этого момента обновляются независимо.

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

Таким образом, при заданных порождающем узле и позиции субузла определяется ContextID, который задает идентификатор группы и позицию ТВ в ТВК. Распределение вероятности в ТВ и ContextID подаются на кодер дальности. После кодирования ТВК обновляется с целью использования при следующем кодировании. Следует отметить, что кодер дальности представляет собой вариант арифметического кодирования, при котором выполняется повторное нормирование в байтах вместо битов, в результате чего время выполнения снижается вдвое, а сжатие ухудшается на 0,01% по сравнению со стандартной реализацией арифметического кодирования.

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

2.3. Результаты тестов

На фиг.3 представлена это таблица, предназначенная для сравнения нашего подхода как для неподвижных, так и для анимационных моделей (ось ординат обозначает степень сжатия). Степень сжатия октодерева варьируется в районе 1,5-2 раз по сравнению с исходным размером октодерева и не менее чем на 30% превосходит способы сжатия без потерь, предназначенные для общих целей (на основе алгоритма Лемпеля-Зива, например, программа RAR).

(Фиг.3 удалена)

3. Формат преобразования в поток данных для depthImageUrl

3.1. Формат потока

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

однобайтовый заголовок для флагов наличия/отсутствия нижеприведенных полей

position

orientation

fieldOfView

nearPlane

farPlane

orthogonal

diTexture (SimpleTexture или PointTexture)

Определение узла PointTexture, который можно использовать в поле diTexture, проводится следующим образом.

PointTexture{

Узел PointTexture определяет множество слоев точек ПОИ. Поля width и height задают ширину и высоту текстуры, соответственно. Поле depth задает множество значений глубины каждой точки (в нормированных координатах) в плоскости проекции в порядке, при котором обход начинается с точки в левом нижнем углу и продолжается слева направо до завершения горизонтальной строки, после чего выполняется переход на строку, расположенную выше. Для каждой точки сначала запоминается количество значений глубины (пикселей), а затем - сами значения глубины. Поле color задает цвет текущего пикселя. Порядок тот же самый, что и для поля depth за исключением того, что не включается указанное число глубин (пикселей) для каждой точки.

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

3.2. Схема сжатия для PointTexture

3.2.1. Сжатие поля depth

Поле depth узла PointTexture просто является набором точек в "дискретизированном заключающем кубе". Мы предполагаем, что плоскостью проекции является нижняя плоскость. При условии, что для модели заданы сетки размерностью m*n*I, причем точки являются центрами ячеек (в случае октодерева мы называем их вокселями) данной сетки, мы можем рассматривать занятые воксели в качестве единиц, а пустые воксели - в качестве нулей. Далее результирующий набор битов (m*n*I битов) организуется в поток байтов. Это осуществляется посредством просмотра вокселей по направлению в глубину (ортогонально плоскости проекции) по слоям глубиной 8, и в обычном (по столбцам) порядке в плоскости проекции (при необходимости последний слой байтов дополняется нулями в случае, если размерность глубины не делится на 8 нацело). Таким образом, мы можем рассматривать наш набор точек в качестве стека 8-битовых изображений (в качестве варианта - 16-битовых изображений) шкалы уровней серого. Соответствие вокселей и битов проиллюстрировано на фиг.4 (а), приведенной ниже.

(Фиг.4 удалена)

Например, на фиг.4(б) черные квадраты соответствуют точкам на объекте. Плоскостью проекции является горизонтальная плоскость. Рассмотрим "срез" высотой 16 (его верхняя граница обозначена жирной линией). Будем интерпретировать "столбцы" как байты. Иными словами, столбец, находящийся над отмеченной на рассматриваемой фигуре точкой, представляет собой стек из 2 байтов со значениями 18 и 1 (или 16-битовое целое 274). Если мы применим лучшие из имеющихся на настоящий момент способов сжатия, основывающихся на ПЧС, к полученному таким образом объединению байтов, то получим весьма хорошие результаты. Однако, если в рассматриваемом случае напрямую применяется простой 1-контекстный способ (конечно, в рассматриваемом случае не может использоваться ортогональная инвариантность или иерархические контексты), степень сжатия для этих результатов оказывается немного меньше. Ниже приведена таблица объемов, требуемых для различных типов геометрических представлений МИГ: сжатие БВО (СБВО); вышеупомянутый массив байтов, сжатый лучшим уплотнителем информации ПЧС, и тот же самый массив, сжатый используемым в текущий момент нашим уплотнителем информации (цифры в Кбайтах).

3.2.2. Сжатие поля color

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

Рассмотрим сначала порядок сканирования, диктуемый нашим исходным форматом хранения данных для МИГ (PointTexture) - сканирование геометрии по схеме "сначала в глубину". Мультипиксели сканируются в естественном порядке поперек плоскости проекции так, как будто они являются простыми пикселями, а точки внутри того же самого мультипикселя сканируются в направлении глубины. Результатом этого порядка сканирования является одномерный массив цветов (1-й ненулевой мультипиксель, 2-й ненулевой мультипиксель и т.д.). Как только глубина становится известной, цвета точек можно последовательно воссоздать из этого массива. Для того чтобы сделать возможным применение способов сжатия изображений, мы должны однозначно отобразить эту длинную строку в двумерный массив. Это можно сделать разными способами.

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

Сжатие данного изображения выполнялось несколькими способами, включая ст