Способ кодирования и декодирования данных трехмерных объектов и устройство для его осуществления
Владельцы патента RU 2267161:
САМСУНГ ЭЛЕКТРОНИКС КО.,ЛТД (KR)
СЕУЛ НЭШНЛ ЮНИВЕРСИТИ ИНДАСТРИ ФАУНДЕЙШН (KR)
Изобретение относится к кодированию и декодированию данных трехмерных объектов, которые состоят из данных точечной текстуры, данных вокселей или данных дерева октетов. Его применение позволяет получить технический результат в виде обеспечения более высокой степени сжатия информации об изображении с глубиной. Этот результат достигается благодаря тому, что способ кодирования данных трехмерных объектов включает в себя: формирование данных трехмерных объектов, имеющих древовидную структуру, где за узлами закреплены метки, указывающие их типы; кодирование узлов данных трехмерных объектов и создание данных трехмерных объектов, чьи узлы кодируют в поток битов. 12 н. и 18 з.п. ф-лы, 23 ил., 1 табл.
Область техники, к которой относится изобретение
Настоящее изобретение относится к способу и устройству для кодирования и декодирования данных и, в частности, касается способа и устройства для кодирования и декодирования данных трехмерных объектов, содержащих либо данные точечной текстуры, либо данные вокселей (элемент объемного изображения), либо данные октодерева.
Уровень техники
Одной из наиболее фундаментальных целей исследований в области трехмерной графики всегда было создание наиболее реалистичных графических экранных изображений реальных изображений. В этой связи проведены исследования технологий визуализации с использованием полигональной модели, в результате чего было разработано множество способов моделирования и визуализации, позволяющих обеспечить весьма реалистичное представление трехмерной среды. Однако для построения сложных трехмерных графических моделей требуются незаурядные усилия и значительное количество времени. Вдобавок, для представления сложной среды с высокой степенью реалистичности необходимо иметь значительный объем данных, что может привести к весьма низкой эффективности их хранения и передачи.
В настоящее время для представления трехмерных объектов в компьютерной графике обычно применяют полигональную модель. При этом подходе произвольная форма может быть грубо представлена набором цветных многоугольников, например набором треугольников. Последние, представляющие значительный интерес разработки в области программных алгоритмов и аппаратных средств для графики, позволяют обеспечить визуализацию сложного объекта или сцены в весьма реалистичной, неподвижной (или подвижной) полигональной модели в реальном времени.
За несколько прошедших лет проведены интенсивные исследования технологии представления трехмерного объекта главным образом из-за трудностей построения полигональных моделей для множества различных объектов реального мира, сложности известных способов визуализации и ограничений при представлении изображений, настолько реалистичных, насколько это возможно.
Для представления трехмерных объектов прикладная программа должна иметь значительное количество многоугольников. Например, модель для подробного представления человеческого тела должна иметь несколько миллионов треугольников, что слишком много с точки зрения практического применения. Хотя последние разработки в области технологии трехмерных измерений, такие как трехмерное сканирование, дают возможность получить сложные трехмерные данные, ошибки которых лежат в допустимых границах, все еще очень трудно и дорого построить полигональную модель, которая хорошо согласуется с трехмерными объектами. Вдобавок, алгоритм визуализации для обеспечения таких реалистичных форм представления изображений, как фотографии, слишком сложен для поддержки визуализации в реальном времени.
Между тем, имеется относительно новый способ представления или визуализации объекта, имеющего сложную геометрическую структуру, а именно представление на основе изображения с глубиной (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 представляет разность между общим количеством (Ra) битов перед процессом объединения узлов и общим количеством (Rb) битов после процесса объединения узлов, а ΔD представляет разность между количеством (Da) искаженных битов до процесса объединения узлов и количеством (Db) искаженных битов после процесса объединения узлов. Когда узлы объединены, требуемая скорость передачи битов уменьшается, но степень искажения аппроксимированной модели возрастает. Следовательно, необходимо найти узлы, которые могут минимизировать вероятность искажения аппроксимированной модели и могут обеспечить максимум снижения требуемой скорости передачи в битах, как только узлы будут объединены друг с другом.
Для того, чтобы вычислить Δ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), то в качестве данных о положении кодируются данные о том, в каком порядке следует кодировать, используя РРМ, каждый из узлов-кандидатов, то есть узлов 'В'. Если имеется только один узел-кандидат (узел 'В'), то в данных о положении нет необходимости, и, следовательно, кодирование данных о положении не потребуется. Данные SOP указывают, следует ли расщеплять на восемь узлов-потомков либо кодировать с использованием РРМ заранее заданный узел. Если данные SOP указывают, что заранее заданный узел является узлом 'S', то данные DIB содержат восемь флагов, указывающих, какой средний цвет у заданного узла, и указывающих, являются или нет узлы-потомки заранее заданного узла узлами 'W'. Узлы, не являющиеся узлами 'W', временно считаются узлами В и поэтому хранятся в очереди, где записаны узлы-кандидаты 'В' для следующего потока битов. На фиг.6 показана структура узла 'S'.
Если данные SOP указывают, что заданный узел является узлом 'Р', то информация о глубине вокселей 'В' в заданном узле подвергается кодированию с использованием РРМ, а также с использованием DPCM кодируется информация о цвете вокселей 'В'. На фиг.7 показана структура потока битов узла 'P'. Метод РРМ был впервые предложен Клери (Cleary) и Виттенсом (Witten) для сжатия данных факсимильной связи без потери данных.
Далее более подробно описывается кодирование РРМ. Как было описано выше, информация о глубине представлена двоичными значениями вокселей. Воксели 'W' представляют прозрачный задний фон, а воксели 'В' представляют трехмерный объект. Двоичные воксели в узле 'Р' подвергаются кодированию на основе РРМ путем использования вокселей, прилегающих к двоичным вокселям как контексты. На фиг.8(а) и 8(b) показаны примеры контекстов. Тринадцать круглых вокселей используют как контексты для кодирования прямоугольного вокселя. В соответствии с растровым сканированием воксели 'W' устанавливают в '0', а воксели 'В' устанавливают в '1'. Эти тринадцать битов, то есть тринадцать круглых вокселей, используют в качестве контекстов для прямоугольного вокселя, показанного на фиг.8(b). В этом случае контексты для прямоугольного вокселя могут быть представлены как '0011101000011', что соответствует количеству контекстов, равному 213. Однако 213 контекстов слишком много для вычислений. Соответственно, имеется потребность уменьшить количество контекстов. Посредством имитационного моделирования отбирают воксели, которые незначительно увеличивают энтропию, даже если их удалить. Сначала удаляют два вокселя. Затем удаляют еще один воксель. Эти три вокселя отмечены на фиг.8(а) знаком 'X'. Адаптивный арифметический кодер сжимает воксели, используя данный контекст.
Черный квадрат на фиг.8(b) кодируется, а черные кружки на фиг.8(а) и 8(b) используются в качестве контекстов. На фиг.8(а) воксели, отмеченные символом 'Х', являются удаляемыми вокселями.
После кодирования информации о глубине выполняют кодирование с использованием DPCM значений цвета R, G и В вокселя 'В' в заданном узле в соответствии с заданным порядком, определяемым растровым сканированием. В частности, значения цвета R, G и В вокселя 'В' оценивают на основе значений цвета R, G и В предыдущего вокселя 'В'. Невязки оценки кодируют, используя арифметический кодер.
Генератор 1130 потока битов создает данные, кодированные по узлам, в виде потока битов.
В настоящем изобретении данные трехмерных объектов кодируют с использованием способа прогрессивного кодирования. Однако трехмерный объект возможно закодировать, используя способ кодирования без потерь или способ кодирования с потерями. При кодировании всего потока битов в целом в качестве способа кодирования можно использовать кодирование без потерь. С другой стороны, когда кодируют только часть потока битов, начиная с корневого узла древовидной структуры, соответствующей данному потоку битов, и кончая заданным узлом на более низком уровне древовидной структуры, то в качестве способа кодирования можно выбрать кодирование с потерями.
Далее более подробно описывается способ и устройство для декодирования данных трехмерных объектов.
На фиг.19 представлена блок-схема устройства для декодирования данных трехмерных объектов согласно предпочтительному варианту настоящего изобретения. Обратимся к фиг.19: устройство включает в себя блок считывания 1900 считывания потока битов, декодер 1910 узлов и блок 1920 восстановления древовидной структуры. Блок 1900 считывания потока битов принимает закодированный поток битов данных трехмерных объектов, декодер 1910 узлов декодирует закодированный поток битов, а блок 1920 восстановления древовидной структуры восстанавливает декодированные узлы в виде древовидной структуры.
На фиг.20 представлена подробная блок-схема декодера 1910 узлов. Декодер 1910 узлов включает в себя декодер 2000 непрерывного флага, декодер 2010 информации о положении узлов, селектор 2020 типа узлов, декодер 2030 узлов S и декодер 2040 узлов Р.
Декодер 2000 непрерывного флага считывает информацию о непрерывном флаге из закодированного потока битов данных трехмерных объектов и декодирует закодированный поток битов. Декодер 2010 информации о положении узлов считывает информацию о положении узлов из закодированного потока битов и декодирует считанную информацию о положении узлов, формируя информацию о положении, которая указывает, в каком месте очереди находится текущий узел. Селектор 2020 типа узлов декодирует информацию о типе узла. Если информация о типе узла указывает, что текущий узел является узлом S, то декодер 2030 узлов S декодирует средний цвет восьми подузлов в виде данных DIB, а затем последовательно декодирует восемь подузлов в узлы 'В' или 'W'. Если информация о типе узла указывает, что текущий узел является узлом РРМ, то декодер 2040 узлов Р декодирует, используя РРМ, данные DIB текущего узла. Декодер 2040 узлов Р декодирует цвета R, G и В вокселей 'В' текущего узла, выполняя обратное кодирование ААС и обратную модуляцию DPCM.
На фиг.21 представлена блок-схема последовательности операций, иллюстрирующая работу декодера 1910 узлов. Обратимся к фиг.21: на этапе 2100 декодируют непрерывный флаг. На этапе 2110 декодируют данные о положении. На этапе 2120 проверяют, является или нет текущий узел узлом 'P'. Если текущий узел является узлом 'P', то этот текущий узел на этапе 2130 декодируют, используя способ декодирования узлов 'Р'. В противном случае текущий узел декодируют, используя способ декодирования 'S'. Этапы с 2100 по 2130 выполняют многократно до тех пор, пока все узлы не будут декодированы (на этапе 2150).
На фиг.22 представлена блок-схема последовательности операций, иллюстрирующая работу декодера 2020 узлов S. Обратимся к фиг.22: на этапе 2200 декодируют информацию о среднем цвете. На этапе 2210 декодируют метки восьми подузлов текущего узла.
На фиг.23 представлена блок-схема последовательности операций, иллюстрирующая работу декодера 2030 узлов Р. Обратимся к фиг.23: на этапе 2300 декодируют информацию о глубине РРМ. На этапе 2310 декодируют информацию о цвете путем выполнения обратной DPCM. В частности, декодируют на основе РРМ текущий узел, используя данные DIB, а значения R, G и В черных вокселей текущего узла декодируют путем выполнения обратного ААС и обратной DPCM.
Далее более подробно описывается способ декодирования данных трехмерных объектов согласно настоящему изобретению.
Способ декодирования данных трехмерных объектов согласно настоящему изобретению подобен способу кодирования данных трехмерных объектов согласно настоящему изобретению. Декодер считывает непрерывный флаг потока битов и проверяет, является или нет текущий узел концом потока битов. Затем декодер считывает данные о положении и данные SOP и определяет, какие узлы необходимо расщепить или декодировать, используя РРМ, на основе считанных данных о положении и данных SOP. Если текущий узел является узлом 'S', то значения цвета всех вокселей текущего узла временно устанавливают равными средним значениям значений цвета R, G и В в данных DIB. Значения цвета вокселей текущего узла обновляют при приеме данных об узлах-потомках текущего узла. Если текущий узел является узлом 'Р', то информация о глубине и цвете вокселей 'В' текущего узла восстанавливается без потерь с использованием данных DIB.
В настоящем изобретении декодирование данных трехмерных объектов выполняется «прогрессивным» образом. При «прогрессивном» способе узлы декодируют в заранее заданном порядке, в котором декодируются потоки битов данных изображений. Поэтому, если данные изображений отображаются на экране, то декодированные узлы отображаются на экране последовательно в порядке от самого верхнего узла к самому нижнему узлу. Соответственно, когда процесс декодирования достигает нижних узлов в древовидной структуре, представляющей данные трехмерных объектов, то изображение, отображенное на экране, становится более детальным и ясным. Когда процесс декодирования заканчивается после декодирования последнего узла, на экране отображается максимально детализированное и ясное изображение.
Как было описано выше, в настоящем изобретении данные трехмерных объектов декодируют «прогрессивным» образом. Однако трехмерный объект можно декодировать, используя способ декодирования без потерь либо способ декодирования с потерями. Когда декодируют весь поток битов в целом, в качестве способа декодирования можно выбрать декодирование без потерь. С другой стороны, если декодируется только часть потока битов, начиная с корневого узла древовидной структуры, соответствующей потоку битов, и кончая заданным узлом на более низком уровне древовидной структуры, то в качестве способа декодирования можно выбрать декодирование с потерями.
Эффективность способов кодирования и декодирования данных трехмерных объектов согласно настоящему изобретению оценивалась с использованием тестовых моделей, показанных на фиг. с 9(а) по 9(h). Тестовые модели, показанные на фиг. с 9(а) по 9(е) имеют разрешение 256×256×256, а тестовые модели, показанные на фиг. с 9(f) по 9(h), имеют разрешение 512×512×512.
На фиг.10(а) и 10(b) представлены таблицы, иллюстрирующие эффективность сжатия данных в настоящем изобретении по сравнению с WinZip. При использовании настоящего изобретения требуется только 22˜59% от размера файла, который понадобится WinZip для обработки информации о глубине. Для обработки информации о цвете в настоящем изобретении требуется только 59˜81% от размера файла, который необходим для WinZip. Однако, с точки зрения обработки «плоской» модели, WinZip демонстрирует более высокую эффективность, чем настоящее изобретение, поскольку «плоская» модель содержит только несколько цветов, и WinZip, который представляет собой кодер на основе словаря, лучше походит для работы с «плоской» моделью. В настоящем изобретении для сжатия информации о глубине и информации о цвете требуется только 49˜75% от размера файла, необходимого для WinZip.
Примечательно, что настоящее изобретение поддерживает прогрессивную передачу данных и прогрессивное декодирование данных, что недоступно кодеру WinZip. Прогрессивная передача данных и прогрессивное декодирование данных является предпочтительным, поскольку это облегчает адаптацию потоков битов к среде с ограниченной полосой пропускания и просмотр трехмерных моделей.
В настоящем изобретении предлагается способ прогрессивного сжатия данных для PointTexture. При использовании способа прогрессивного сжатия данных пиксели тесно связаны друг с другом в смысле векторов цвета и информации о глубине. В настоящем изобретении информацию о глубине и информацию о цвете можно эффективно кодировать, используя способ РРМ в структуре октодерева. Многочисленные результаты имитационного моделирования показывают, что настоящее изобретение обеспечивает более высокую степень сжатия, чем универсальный кодер LempelZiv, то есть WinZip.
Настоящее изобретение можно реализовать в виде программ, считываемых компьютером, которые записаны на носителе записи, считываемом компьютером. Носитель записи, считываемый компьютером, включает в себя все типы записывающих устройств, на которые можно записать данные с возможностью их считывания компьютером. Например, среда для записи, считываемая компьютером, включает в себя ПЗУ (ROM), ОЗУ (RAM), ПЗУ на компакт-диске (CD-ROM), магнитную ленту, гибкий диск, оптическое запоминающее устройство, а также сигнал несущей, к примеру сигнал, обеспечивающий передачу данных через Интернет. Среда для записи, считываемой компьютером, может быть распределена по множеству компьютерных систем, которые соединены друг с другом в виде сети; в этом случае данные могут храниться в среде для записи, считываемой компьютером, децентрализовано.
Хотя настоящее изобретение было подробно показано и описано со ссылками на примерные варианты его осуществления, специалистам в данной области техники очевидно, что в него могут быть внесены различные изменения по форме и в деталях в рамках существа и объема настоящего изобретения, определенного нижеследующей формулой изобретения.
1. Способ кодирования данных трехмерных объектов, которые содержат данные точечной текстуры, данные вокселей или данные структуры октодерева, причем способ содержит этапы: формирование данных трехмерных объектов, имеющих древовидную структуру, за узлами которой закреплены метки, указывающие их типы; кодирование узлов данных трехмерных объектов, по которому выполняют кодирование информации об узле, которая указывает, является или нет текущий узел узлом 'S' или узлом 'P', и кодирование данных с битами детализированной информации (DIB) узла 'S', если информация об узле указывает на то, что текущий узел является узлом 'S', и кодирование данных DIB узла 'P', если информация об узле указывает на то, что текущий узел является узлом 'P', и этап формирования данных трехмерных объектов, чьи узлы закодированы в поток битов.
2. Способ по п.1, по которому при формировании данных трехмерных объектов воксели отличаются друг от друга в результате преобразования данных трехмерных объектов в данные вокселей с использованием трехмерного связывающего объема и дифференцированного присваивания меток вокселям в зависимости от того, находятся они или нет в местах, где существуют объекты.
3. Способ по п.2, по которому при представлении данных трехмерных объектов в виде древовидной структуры узлу, имеющему подузлы, присваивают метку 'S', узлу, чьи воксели не содержат объекты, присваивают метку 'W', узлу, чьи все воксели содержат объекты, присваивают метку 'B', а узлу, чьи воксели закодированы с использованием алгоритма предсказания на основе частичного совпадения (PPM), присваивают метку 'P'.
4. Способ по п.1, по которому при кодировании узлов данных трехмерных объектов кодируют только некоторые из узлов данных трехмерных объектов, находящиеся в пределах от корневого узла до заданного нижележащего узла.
5. Способ по п.1, по которому при кодировании узлов данных трехмерных объектов кодируют все узлы данных трехмерных объектов.
6. Способ кодирования данных трехмерных объектов, которые содержат данные точечной текстуры, данные вокселей или данные структуры октодерева, причем способ содержит этапы: (a) формирование данных трехмерных объектов, имеющих древовидную структуру, за узлами которой закреплены метки, указывающие их типы; (b) объединение узлов данных трехмерных объектов путем обращения к их меткам; (c) кодирование объединенных узлов, содержащее кодирование непрерывного флага, который представляет собой информацию, указывающую на то, имеются или нет в очереди узлы-кандидаты; кодирование информации о положении узлов, которая указывает положение каждого из узлов-кандидатов в очереди; кодирование информации о типе узлов, которая указывает, является или нет текущий узел узлом 'S' или узлом 'P'; кодирование данных DIB узла 'S', если информация об узлах указывает, что текущий узел является узлом 'S', и кодирование данных DIB узла 'P', если информация об узлах указывает, что текущий узел является узлом 'P'; (d) формирование данных трехмерных объектов, чьи объединенные узлы кодируют в поток битов; (е) повторное выполнение этапов с (а) по (d) до тех пор, пока не будет закодирован самый верхний узел древовидной структуры, представляющей данные трехмерных объектов.
7. Способ по п.6, по которому на этапе (а) узлу, имеющему подузлы, присваивают метку 'S'; узлу, чьи воксели не содержат объекты, присваивают метку 'W'; узлу, у которого все воксели содержат объекты, присваивают метку 'B', а узлу, чьи воксели закодированы с использованием алгоритма PPM, присваивают метку 'P'.
8. Способ по п.7, по которому этап (b) содержит выбор узлов 'P' и узлов 'S', чьим подузлам присвоены метки 'W' и 'B', в качестве узлов-кандидатов на объединение; выбор среди узлов-кандидатов в качестве оптимального узла того узла, который может минимизировать отношение разности ΔD между количеством искаженных битов перед объединением узлов-кандидатов и количеством искаженных битов после объединения узлов-кандидатов к разности ΔR между количеством битов перед объединением узлов-кандидатов и количеством битов после объединения узлов-кандидатов; присвоение метки выбранному узлу 'B'; обновление всех узлов-кандидатов кроме узла, выбранного в качестве оптимального узла.
9. Способ по п.8, по которому ΔD вычисляют, исходя из следующего уравнения с использованием расстояния Хэмминга между исходной моделью V и ее аппроксимацией 
в качестве меры искажения:
где Х×Y×Z представляет разрешение исходной модели.
10. Способ по п.6, по которому кодирование данных DIB узла 'S' содержит кодирование среднего значения информации о цвете и кодирование меток восьми подузлов текущего узла.
11. Способ по п.6, по которому кодирование данных DIB узла 'P' содержит кодирование информации о глубине и кодирование информации о цвете.
12. Способ по.11, по которому при кодировании информации о глубине все узлы, расположенные ниже заданного узла в древовидной структуре, представляющей данные трехмерных объектов, кодируют на основе PPM в соответствии с порядком растрового сканирования путем использования заданного количества контекстов.
13. Способ по п.11, по которому при кодировании информации о цвете значения красного (R), зеленого (G) и синего (B) вокселей 'B' текущего узла кодируют путем выполнения дифференциальной импульсно-кодовой модуляции (DPCM) и адаптивного арифметического кодирования (ААС).
14. Способ по п.6, по которому на этапе (с) кодируют только некоторые из объединенных узлов, находящихся в пределах от первого узла до узла с заданным номером.
15. Способ по п.6, по которому на этапе (с) кодируют все объединенные узлы.
16. Устройство для кодирования данных трехмерных объектов, которые содержат данные точечной текстуры, данные вокселей или данные структуры октодерева, причем устройство содержит: генератор древовидной структуры, который формирует данные трехмерных объектов, имеющие древовидную структуру, за узлами которой закреплены метки, указывающие их типы; селектор, задающий порядок объединения, который объединяет узлы данных трехмерных объектов путем обращения к их меткам; кодер узлов, который кодирует объединенные узлы, и который содержит: кодер непрерывного флага, кодирующий непрерывный флаг, который представляет собой информацию, указывающую, является или нет текущий узел концом сжатого потока битов; кодер положения узлов, который кодирует информацию о положении узлов, указывающую положение каждого из узлов-кандидатов в очереди; селектор узлов 'S' - или - 'P' (SOP), который кодирует информацию о типе узла, указывающую, является или нет текущий узел узлом 'S' или узлом 'P'; кодер узла S, который кодирует данные DIB узла 'S', если информация об узле указывает, что текущий узел является узлом 'S'; и кодер узла P, который кодирует данные DIB узла 'P', если информация об узле указывает, что текущий узел является узлом 'P'; и генератор потока битов, который формирует данные трехмерных объектов, чьи объединенные узлы закодированы в поток битов.
17. Устройство по п.16, по которому селектор, задающий порядок объединения, содержит селектор узлов-кандидатов, который в качестве узлов-кандидатов, подлежащих объединению, выбирает узлы 'P' и узлы 'S', чьим подузлам присвоены метки 'W' и 'B'; селектор оптимального узла, который из числа узлов-кандидатов выбирает в качестве оптимального узла тот узел, который может минимизировать отношение разности ΔD между количеством искаженных битов перед объединением узлов-кандидатов и количеством искаженных битов после объединения узлов-кандидатов к разности ΔR между количеством битов перед объединением узлов-кандидатов и количеством битов после объединения узлов-кандидатов, и присваивает метку выбранному узлу 'B'; блок обновления узлов-кандидатов, который обновляет все узлы-кандидаты, кроме узла, выбранного в качестве оптимального узла.
18. Устройство по п.16, в котором кодер узлов кодирует только некоторые из объединенных узлов, находящиеся в пределах от первого узла до узла с заданным номером.
19. Устройство по п.16, в котором кодер узлов кодирует все объединенные узлы.
20. Способ декодирования данных трехмерных объектов, содержащий этапы считывания информации о непрерывном флаге из потока битов закодированных данных трехмерных объектов и декодирования информации о непрерывном флаге; декодирования информации о типе узла в потоке битов; декодирования узла 'S', если информация о типе узла указывает, что текущий узел является узлом 'S', и декодирования узла PPM, если информация о типе узла указывает, что текущий узел является узлом PPM; восстановления данных трехмерных объектов, чьи узлы закодированы в древовидную структуру.
21. Способ декодирования данных трехмерных объектов, содержащий декодирование узлов из потока битов закодированных данных трехмерных объектов, которое содержит этапы считывания информации о непрерывном флаге из потока битов закодированных данных трехмерных объектов и декодирования информации о непрерывном флаге; считывания информации о положении узлов, указывающей, какой узел-кандидат в очереди является текущим узлом, и декодирования информации о положении узлов; декодирования информации о типе узла в потоке битов; декодирования узла 'S', если информация о типе узла указывает, что текущий узел является узлом 'S'; декодирования узла PPM, если информация о типе узла указывает, что текущий узел является узлом PPM; восстановление данных трехмерных объектов, чьи узлы закодированы в древовидную структуру.
22. Способ по п.21, по которому при декодировании узла 'S' средний цвет восьми подузлов текущего узла декодируют в виде данных DIB, а восемь подузлов последовательно декодируют в черные узлы (узлы 'B') или белые узлы (узлы 'W').
23. Способ по п.22, по которому при декодировании узла PPM текущий узел декодируют на основе PPM с использованием данных с битами данных (DIB), а значения R, G и B вокселей 'B' текущего узла декодируют путем выполнения обратного кодирования ААС и обратной модуляции DPCM.
24. Устройство для декодирования потока битов закодированных данных трехмерных объектов, причем устройство содержит блок считывания потока битов, который принимает поток битов закодированных данных трехмерных объектов; декодер узлов, который декодирует поток битов и который содержит декодер непрерывного флага, который декодирует непрерывный флаг, указывающий, является или нет текущий узел концом потока битов; декодер информации о положении узлов, который считывает информацию о положении узлов, указывающую, какой узел-кандидат, находящийся в очереди, является текущим узлом, и декодирует информацию о положении узлов; селектор типа узла, который декодирует информацию о типе узла в потоке битов; селектор типа узла, который декодирует информацию о типе узла из потока битов; декодер узлов S, который декодирует средний цвет восьми подузлов текущего узла в виде данных DIB, а затем последовательно декодирует восемь подузлов в узлы 'B' или узлы 'W'; декодер узлов P, который на основе PPM декодирует данные DIB текущего узла, а затем декодирует значения R,G и B вокселей 'B' текущего узла путем выполнения декодирования с обратным ААС и обратной DPCM для узла 'S', если информация о типе узла указывает, что текущий узел является узлом PPM; блок восстановления древовидной структуры, который восстанавливает декодированные узлы в древовидную структуру.
25. Носитель записи, считываемый компьютером, на который записывают программу, позволяющую выполнить способ по любому из пп.1-5.
26. Носитель записи, считываемый компьютером, на который записывают программу, позволяющую выполнить способ по любому из пп.6-15.
27. Носитель записи, считываемый компьютером, на который записывают программу, позволяющую выполнить способ по п.20.
28. Носитель записи, считываемый компьютером, на который записывают программу, позволяющую выполнить способ по любому из пп.21-23.
29. Носитель записи, считываемый компьютером, для использования в устройстве для кодирования данных трехмерных объектов по любому из пп.16-19.
30. Носитель записи, считываемый компьютером, для использования в устройстве для декодирования потока битов закодированных данных трехмерных объектов по п.24.
