Способ кодирования и декодирования данных трехмерных объектов и устройство для его осуществления

Способ кодирования и декодирования данных трехмерных объектов и устройство для его осуществления

Иллюстрации

Показать все

Реферат

Область техники, к которой относится изобретение

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

Уровень техники

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

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

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

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

Между тем, имеется относительно новый способ представления или визуализации объекта, имеющего сложную геометрическую структуру, а именно представление на основе изображения с глубиной (DIBR), которое было принято в расширении анимационной инфраструктуры (AFX) стандарта MPEG-4. Хотя для представления объектов компьютерной графики обычно используют многоугольные ячейки (сетки), для представления трехмерного объекта в DIBR используется набор эталонных изображений, которые покрывают видимую поверхность трехмерного объекта. Каждое из эталонных изображений представляется картой глубины, а карта глубины представляет массив различных расстояний между пикселями на плоскости изображения и поверхности трехмерного объекта. Одним из самых главных преимуществ DIBR является то, что может быть обеспечено высокое качество представления объектов просто путем использования эталонных изображений без использования полигональных моделей. Вдобавок, сложность визуализации изображения на основе DIBR зависит только от количества пикселей, образующих вид DIBR (то есть, от разрешения изображения DIBR) независимо от сложности сцены. DIBR включает в себя SimpleTexture (простая текстура), PointTexture (точечная текстура) и Octreelmage (изображение октодерева). PointTexture представляет объект с помощью пикселей PointTexture, видимых из заданного места расположения камеры. Каждый из пикселей PointTexture представлен своим цветом и глубиной (расстояние между каждым из пикселей PointTexture и заданным местом расположения камеры) и другими свойствами, которые помогают обеспечить визуализацию PointTexture. Множество пикселей может быть представлено вдоль линий визирования. Изображение PointTexture в общем случае содержит множество уровней. На фиг.1 показан простой пример одномерного изображения PointTexture. Для PointTexture требуется значительное количество данных, чтобы обеспечить реалистичное представление объектов. В общем случае, чем реалистичнее изображение, тем более высокая плотность дискретизации и больше данных требуется для обработки. Следовательно, обязательно потребуется эффективное сжатие изображений PointTexture. На фиг.2 показаны узловые спецификации PointTexture. На фиг.2 сжатию подвергаются поля «глубина» и «цвет».

На сегодняшний день проведено мало исследований над PointTexture, и поэтому известно всего несколько способов визуализации на основе PointTexture. Одним из известных способов, базирующихся на PointTexture, является способ сжатия многоуровневых изображений с глубиной (LDI), который раскрыт в работе Dual and Li «Compression of the Layered Depth Image», IEEE Trans. Image Processing, Vol.12, No.3, pp.365-372, March 2003.

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

Между тем, в работе С.S.Kim and S.U.Lee «Compact Encoding of 3D Voxel Surface Based on Pattern Code Representation, IEEE Trans. Image Processing, Vol.11, N0.8, pp.932-943, 2002, раскрыт способ сжатия модели поверхности трехмерных вокселей с использованием представления на основе кодированных шаблонов (PCR). Однако в этом способе не используется иерархическая структура октодерева и нет возможности реализации схем прогрессивного сжатия. Вдобавок, для MPEG-4 AFX был разработан способ сжатия данных на основе октодерева [ISO/IEC/JTC1/SC29/WG11 14496-16: 2003, Information Technology-Coding of Audio-Visual Objects-Part 16: Animation Framework extension]. Однако этот способ, как и вышеупомянутые стандартные способы, не может обеспечить прогрессивные потоки битов.

Сущность изобретения

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

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

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

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

Предпочтительно, чтобы кодирование узлов данных трехмерных объектов включало в себя кодирование информации об узле, которая указывает, является или нет текущий узел узлом 'S' или узлом 'Р'; кодирование данных с битами детализированной информации (DIB) узла 'S', если информация об узле указывает на то, что текущий узел является узлом 'S', и кодирование данных DIB узла 'Р', если информация об узле указывает на то, что текущий узел является узлом 'Р'.

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

Предпочтительно, чтобы на этапе (а) узлу, имеющему подузлы, присваивалась метка 'S'; узлу, чьи воксели не содержат объекты, присваивалась метка 'W'; узлу, у которого все воксели содержат объекты, присваивалась метка 'В'; а узлу, чьи воксели закодированы с использованием алгоритма РРМ, присваивалась метка 'Р'.

Предпочтительно, чтобы этап (b), включал в себя выбор узлов 'S', чьим подузлам присвоены метки 'W' и 'В', и узлов 'Р' в качестве узлов-кандидатов на объединение; выбор среди узлов-кандидатов в качестве оптимального узла того узла, который может минимизировать отношение разности ΔD между количеством искаженных битов перед объединением узлов-кандидатов и количеством искаженных битов после объединения узлов-кандидатов к разности ΔR между количеством битов перед объединением узлов-кандидатов и количеством битов после объединения узлов-кандидатов; присвоение метки выбранному узлу 'В' и обновление всех узлов-кандидатов, кроме узла, выбранного в качестве оптимального узла.

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

где X×Y×Z представляет разрешение исходной модели.

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

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

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

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

Предпочтительно, чтобы при кодировании информации о цвете значения красного (R), зеленого (G) и синего (В) вокселей 'В' текущего узла кодировались путем выполнения дифференциальной импульсно-кодовой модуляции (DPCM, ДИКМ) и адаптивного арифметического кодирования (ААС).

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

Предпочтительно, чтобы селектор, задающий порядок объединения, включал в себя селектор узлов-кандидатов, который в качестве узлов-кандидатов, подлежащих объединению, выбирает узлы 'Р' и узлы 'S', чьим подузлам присвоены метки 'W' и 'В'; селектор оптимального узла, который из числа узлов-кандидатов выбирает в качестве оптимального узла тот узел, который может минимизировать отношение разности ΔD между количеством искаженных битов перед объединением узлов-кандидатов и количеством искаженных битов после объединения узлов-кандидатов к разности ΔR между количеством битов перед объединением битов-кандидатов и количеством битов после объединения битов-кандидатов, и присваивает метку выбранному узлу 'В'; и блок обновления узлов-кандидатов, который обновляет все узлы-кандидаты, кроме узла, выбранного в качестве оптимального узла.

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

Согласно еще одному аспекту настоящего изобретения предлагается способ декодирования данных трехмерных объектов. Способ включает в себя: считывание информации о непрерывном флаге из потока битов закодированных данных трехмерных объектов и декодирование информации о непрерывном флаге; декодирование информации о типе узлов в потоке битов; декодирование узла 'S', если информация о типе узла указывает, что текущий узел является узлом 'S,' и декодирование узла РРМ, если информация о типе узла указывает, что текущий узел является узлом РРМ; и восстановление данных трехмерных объектов, чьи узлы закодированы в древовидную структуру.

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

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

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

Предпочтительно, чтобы при декодировании узла РРМ текущий узел декодировался на основе РРМ с использованием данных с битами данных (DIB), а значения R, G и В вокселей 'В' текущего узла декодировались путем выполнения обратного кодирования ААС и обратной модуляции DPCM.

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

Предпочтительно, чтобы декодер узлов включал в себя декодер непрерывного флага, который декодирует непрерывный флаг, указывающий, является или нет текущий узел концом потока битов; декодер информации о положении узлов, который считывает информацию о положении узлов, указывающую, какой узел-кандидат, находящийся в очереди, является текущим узлом, и декодирует информацию о положении узла; селектор типа узла, который декодирует информацию о типе узлов в потоке битов; декодер узлов S, который декодирует средний цвет восьми подузлов текущего узла в виде данных DIB, а затем последовательно декодирует восемь подузлов в узлы 'В' или узлы 'W'; и декодер узлов Р, который на основе РРМ декодирует данные DIB текущего узла, а затем декодирует значения R, G и В вокселей 'В' текущего узла путем выполнения декодирования с обратным ААС и обратной DPCM для узла 'S', если информация о типе узла указывает, что текущий узел является узлом РРМ.

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

Краткое описание чертежей

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

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

фиг.2 - схема, иллюстрирующая образец узла для точечной текстуры;

фигуры с 3(а) по 3(d) - схемы, иллюстрирующие различные структуры октодерева для объемных данных, в которых каждому узлу присвоена метка;

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

фиг.5 - диаграмма, иллюстрирующая структуру потока битов узла;

фиг.6 - диаграмма, иллюстрирующая структуру потока битов узла S;

фиг.7 - диаграмма, иллюстрирующая структуру потока битов узла Р;

фигуры 8(а) и 8(b) - диаграммы, иллюстрирующие примеры контекстов, которые используют при кодировании с предсказанием на основе частичного совпадения (РРМ);

фиг.9 - диаграмма, иллюстрирующая тестовую модель для проверки эффективности функционирования настоящего изобретения;

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

фиг.11 - блок-схема устройства для кодирования трехмерных данных согласно предпочтительному варианту настоящего изобретения;

фиг.12 - подробная блок-схема селектора по фиг.11, задающего порядок объединения;

фиг.13 - блок-схема последовательности операций, иллюстрирующая работу селектора узлов-кандидатов по фиг.12;

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

фиг.15 - подробная блок-схема кодера узлов по фиг.11;

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

фиг.17 - блок-схема последовательности операций, иллюстрирующая работу кодера узлов S по фиг.15;

фиг.18 - блок-схема последовательности операций, иллюстрирующая работу кодера узлов Р по фиг.15;

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

фиг.20 - подробная блок-схема декодера узлов по фиг.19;

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

фиг.22 - блок-схема последовательности операций, иллюстрирующая работу декодера узлов S по фиг.20; и

фиг.23 - блок-схема последовательности операций, иллюстрирующая работу декодера узлов Р по фиг.20.

Подробное описание изобретения

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

На фиг.11 представлена блок-схема устройства для кодирования данных трехмерных объектов согласно предпочтительному варианту настоящего изобретения. Обратимся к фиг.11, где устройство включает в себя генератор 1100 древовидной структуры, селектор 1110, задающий порядок объединения, кодер 1120 узлов и генератор 1130 потока битов.

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

Далее более подробно описывается способ создания октодерева. Изображение PointTexture преобразуется в объемные данные, и объемные данные поочередно представляются октодеревом. Затем краевые узлы октодерева подвергают эффективному кодированию, используя способ кодирования с предсказанием на основе частичного совпадения (РРМ). Соответственно, способ кодирования и декодирования трехмерного объекта согласно предпочтительному варианту настоящего изобретения эквивалентен способу сжатия модели PointTexture и модели октодерева.

Для того чтобы преобразовать информацию о глубине трехмерного объекта в объемные данные (данные об объеме), сначала создают ограничивающий объем. Ограничивающий объем имеет то же разрешение, что и PointTexture. Например, если предположить, что PointTexture представляет изображение с разрешением X×Y и информация о глубине каждого пикселя имеет разрешение Z, то создается ограничивающий объем, имеющий разрешение X×Y×Z. Начало ограничивающего прямоугольника расположено в нижнем левом переднем углу ограничивающего прямоугольника. Правый воксель имеет значение х, которое больше, чем значение левого вокселя; верхний воксель имеет значение у, которое больше, чем значение нижнего вокселя, а задний воксель имеет значение z, которое больше значения переднего вокселя. Информацию о глубине можно немедленно преобразовать в двоичные данные объема. Все воксели данных объема инициализируют, присваивая значение W (белый, '0'). После этого значение вокселей данных объема устанавливают равным В (черный, '1'), если места их расположения определены как пиксели точечной текстуры. Черные воксели представляют точки на трехмерном объекте, а белые воксели представляют прозрачный задний фон.

Данные объема представляют октодерево, а узлы октодерева классифицируются по четырем различным категориям. Ниже в таблице показаны метки, соответственно представляющие четыре различные категории. Если ограничивающий объем содержит объект, то корневому узлу присваивается метка 'S', и ограничивающий объем делится на восемь одинаковых подобъемов. Если подобъем включает в себя только черные воксели или белые воксели, то соответствующему узлу присваивают метку 'В' или 'W'. В противном случае узлу, соответствующему подобъему, присваивают метку 'S', и этот подобъем дополнительно разделяют на восемь одинаковых более мелких частей. Этот процесс выполняется многократно, пока не будет достигнут узел на заданной глубине октодерева. Если узел на заданной глубине октодерева включает в себя как черные, так и белые воксели, то такому узлу присваивают метку 'Р', и значения вокселей, включенные в этот узел, могут быть закодированы с использованием метода РРМ.

Таблица
Метки	Комментарии
S	Расщепление: узел делится на 8 подузлов
W	Белый: узел содержит только белые воксели
В	Черная закраска: узел полностью или в основном содержит черные воксели
Р	РРМ: значения векселей в узле кодируются с использованием алгоритма РРМ

На фигурах с 3(а) по 3(d) представлены диаграммы, иллюстрирующие различные структуры октодеревьев для объемных данных, где каждому узлу присвоена метка. На фигурах с 3(а) по 3(d) показаны двухмерные двоичные изображения и их соответствующие представления в виде деревьев квадрантов. В частности, на фиг.3(а) показана связь «родитель-потомок» в структуре квадрантов, а на фиг.3(b) показано дерево квадрантов, соответствующее двоичному изображению, где значение информации о глубине двоичного изображения установлено равным 2. Двоичное изображение может быть восстановлено без потерь данных путем использования данных, закодированных с помощью РРМ, для дерева квадрантов и трех узлов Р.

На фиг.12 представлена подробная блок-схема селектора 1110 по фиг.11, задающего порядок объединения. Селектор 1110, задающий порядок объединения, объединяет узлы для данных трехмерных объектов, представленных древовидной структурой, путем обращения к меткам узлов. Как показано на фиг.12, селектор 1110, задающий порядок объединения, включает в себя селектор 1200 узлов-кандидатов, селектор 1210 оптимального узла и блок 1220 обновления узлов-кандидатов. Селектор 1200 узлов-кандидатов выбирает узел с меткой 'Р' и узел с меткой 'S' в качестве кандидатов на объединение. Здесь узел S, чьи все узлы-потомки являются белыми узлами (далее обозначены как узлы 'W') или черными узлами (далее обозначены как узлы 'В'), или узлы 'W' и 'В', могут быть выбраны в качестве кандидата на объединение.

Селектор 1210 оптимального узла выбирает в качестве оптимального узла тот узел, для которого отношение разности ΔD между количеством искаженных битов до процесса объединения узлов и количеством искаженных битов после процесса объединения узлов к разности ΔR между общим количеством битов до процесса объединения узлов и общим количеством битов после процесса объединения узлов достигает минимального значения. После этого селектор 1210 оптимального узла присваивает выбранному узлу метку 'В'. Блок 1220 обновления узлов-кандидатов обновляет все узлы-кандидаты, за исключением узла, выбранного в качестве оптимального.

Далее со ссылками на фигуры с 3(а) по 3(d), 13 и 14 более подробно описывается способ объединения деревьев. На фиг.3 показано представление в виде октодеревьев с метками и объединение деревьев. Узлы начального дерева многократно объединяются для аппроксимации исходной информации о глубине до нескольких уровней детализации. Здесь объединяемыми узлами являются узлы, имеющие метку 'Р', или узлы, чьи все узлы-потомки являются узлами В или узлами W. Например, в дереве на фиг.3(b) имеется четыре объединяемых узла, обведенных тонкими окружностями. Предположим, что среди четырех объединяемых узлов один узел, соответствующий области, отмеченной квадратом на двоичном изображении, объединяется с узлом В. Результирующее двоичное изображение и результирующее дерево показаны на фиг.3(с). Теперь, как показано на фиг.3(с), имеются три объединяемых узла слева. Затем один из трех объединяемых узлов (например, узел Р, на дальней левой части дерева, показанного на фиг.3(с)) объединяется в узел В. Затем объединяемым становится узел, который соответствует левому верхнему квадранту аппроксимированной модели по фиг.3(d) и чьи все узлы-потомки являются узлами 'В' или узлами 'W'. Этот процесс объединения на дереве выполняется непрерывно, пока все узлы дерева не будут объединены вместе под одним корневым узлом.

На фиг.13 представлена блок-схема, иллюстрирующая работу селектора 1200 узлов-кандидатов. Предположим, что 'i' представляет порядковый номер каждого узла, а 'count' (отсчет) представляет количество узлов-кандидатов; причем на этапе 1300 'i' и 'count' инициализируют, присваивая им значение 0. Если на этапе 1310 узлу присваивается метка 'S' или 'Р', то этот узел выбирается в качестве узла-кандидата, а затем он хранится в очереди, а переменная 'count' на этапе 1330 увеличивается на 1. Здесь в качестве узлов-кандидатов среди узлов 'S' могут быть выбраны только те узлы, у которых все узлы-потомки являются узлами 'W' или узлами 'В', или узлами 'W' и 'В'. Если узел не является ни узлом 'S', ни узлом 'Р', то выполняется этап 1310 для следующего узла на этапе 1320. Этапы с 1310 по 1330 выполняются многократно, пока 'i' не укажет последний узел (на этапе 1340).

Узлы, подлежащие объединению друг с другом, выбирают из набора объединяемых узлов, и минимизируют отношение ΔD к ΔR при заданной скорости, как показано в приведенном ниже уравнении (1).

В уравнении (1) ΔR представляет разность между общим количеством (R_a) битов перед процессом объединения узлов и общим количеством (R_b) битов после процесса объединения узлов, а ΔD представляет разность между количеством (D_a) искаженных битов до процесса объединения узлов и количеством (D_b) искаженных битов после процесса объединения узлов. Когда узлы объединены, требуемая скорость передачи битов уменьшается, но степень искажения аппроксимированной модели возрастает. Следовательно, необходимо найти узлы, которые могут минимизировать вероятность искажения аппроксимированной модели и могут обеспечить максимум снижения требуемой скорости передачи в битах, как только узлы будут объединены друг с другом.

Для того, чтобы вычислить ΔD в качестве меры искажения, используют расстояние Хэмминга между исходной моделью V и соответствующей аппроксимацией.

X×Y×Z представляет разрешение модели.

Чтобы вычислить ΔD, необходимо вычислить количество битов, требуемое (то есть, требуемую скорость передачи в битах) для представления октодерева и его узлов РРМ. Однако указанную требуемую скорость передачи в битах вычислить очень сложно. Поэтому требуемую скорость передачи в битах вычисляют путем использования битов типового дерева и битов РРМ в нескольких тестовых моделях.

На фиг.14 представлена блок-схема алгоритма, иллюстрирующая работу селектора 1210, задающего порядок объединения. Обратимся к фиг.14, где на этапе 1410 из числа узлов, которые выбраны селектором 1200 узлов-кандидатов в качестве узлов-кандидатов, выбирают в качестве оптимального узел, для которого может быть получено минимальное значение из уравнения (1). На этапе 1420 выбранному оптимальному узлу присваивают метку 'В'. На этапе 1430 узел с меткой 'В' удаляют из очереди. На этапе 1440 очередь обновляется. Этапы с 1410 по 1440 многократно повторяются, пока все узлы не будут объединены друг с другом (на этапе 1450).

Кодер 1120 узлов кодирует объединенный узел. На фиг.15 представлена подробная блок-схема кодера 1120 узлов. Обратимся к фиг.15, где кодер 1120 узлов включает в себя кодер 1500 непрерывного флага, кодер 1510 положения узлов, селектор 1520 узлов S -или -Р (SOP), кодер 1530 узлов S и кодер 1540 узлов Р.

Кодер 1500 непрерывного флага кодирует непрерывный флаг, который указывает, является или нет текущий узел концом сжатого потока битов. Если текущий узел не является концом сжатого потока битов, то непрерывному флагу присваивают значение «истина». В противном случае непрерывному флагу присваивают значение «ложь». Кодер 1510 положения узлов, который включает в себя очередь узлов-кандидатов, где хранятся узлы, выбранные селектором 1200 узлов-кандидатов в качестве узлов-кандидатов, кодирует информацию о положении узлов, которая указывает положение каждого из узлов-кандидатов в очереди узлов-кандидатов. Селектор 1520 узлов (SOP) кодирует информацию о типе узлов, которая указывает, является ли текущий узел узлом S или узлом Р. Кодер 1530 узлов S кодирует данные с битами детализированной информации (DIB) узла Р, если информация о типе узла указывает, что текущий узел является узлом Р.

На фиг.16 представлена блок-схема последовательности операций, иллюстрирующая работу кодера 1120 узлов. Обратимся к фиг.16, где на этапе 1600 кодируется непрерывный флаг. Как было описано выше, непрерывный флаг указывает, является или нет текущий узел концом сжатого потока битов. Если текущий узел не является концом сжатого потока битов, то непрерывному флагу присваивают значение «истина». В противном случае непрерывному флагу присваивают значение «ложь». На этапе 1600 кодируется информация о положении узла. На этапе 1620 проверяют, является или нет объединенный узел узлом Р. Если объединенный узел является узлом Р, то на этапе 1630 выполняется кодирование узла Р. В противном случае выполняют кодирование узла S. Этапы с 1600 по 1640 многократно выполняют до тех пор, пока не будут закодированы все узлы (на этапе 1650).

На фиг.17 представлена блок-схема последовательности операций, иллюстрирующая работу кодера 1520 узлов S. Обратимся к фиг.17; на этапе 1700 кодируется информация о среднем цвете. На этапе 1710 кодируют метки восьми подузлов.

На фиг.18 представлена блок-схема последовательности операций, иллюстрирующая работу кодера 1530 узлов Р. Обратимся к фиг.18; на этапе 1800 кодируется информация о глубине с использованием РРМ. На этапе 1810 кодируется информация о цвете с использованием дифференциальной импульсно-кодовой модуляции (DPCM).

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

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

Непрерывный флаг указывает, является или нет заданный узел концом сжатого потока битов. Все данные, составляющие информацию об узле по фиг.5, подвергаются статистическому кодированию с использованием адаптивного арифметического кодера (ААС). Данные о положении указывают, требуется или нет расщепление либо кодирование на основе РРМ узла 'В'. Например, предположим, что декодер восстанавливает аппроксимированную модель, показанную на фиг.3(d), используя все полученные данные. Октодерево по фиг.3(d) включает в себя четыре узла 'В', которые являются узлами-кандидатами на объединение. Для того чтобы получить как можно более детальную модель, показанную на фиг.3(с), кодер информирует декодер о том, что среди четырех узлов 'В' второй узел слева в октодереве должен быть закодирован с использованием алгоритма РРМ. Если имеется более одного узла-кандидата на объединение, как это показано на фиг.3(d), то в качестве данных о положении кодируются данные о том, в каком порядке следует код