Компрессия 3D-данных, полученных в результате 3D-сканирования

Размещено на http://www.allbest.ru/

Компрессия 3D-данных, полученных в результате 3D-сканирования

А.Ю. Аксенов, А.А. Зайцева

Санкт-Петербургский институт информатики и автоматизации РАН

тел. (812) 323-51-39, e-mail: cher@iias.spb.su

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

С появлением устройств, способных создавать цифровые копии реальных объектов (камер на основе ПЗС- и КМОП-матриц, цифровых томографов, 2D и 3D-сканеров) основным способом представления являлась запись свойств отдельных точек объекта, находящихся в узлах регулярной сетки (пикселов в случае 2D и вокселов для 3D).

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

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

В зависимости от способа получения 3D-данных, занимаемый ими объем битового представления будет различным (таблица 1).

Таблица 1

Ориентировочное сравнение объемов битового представления различных 3D-объектов

В таблице 1 представлены сравнительные объемы исходного (несжатого) битового представления различных 3D-объектов.

Для эффективного хранения 3D-объектов необходимы форматы представления этих объектов в сжатом виде, ориентированные на конкретный класс представления.

Авторами предлагается метод компрессии пространства точек на основе разбиения областей пространства на элементы размером 256Ч256Ч256, с последующим их преобразованием в битовые последовательности с использованием обхода в соответствии с алгоритмом заполняющей пространство кривой (ЗПК) и вторичного сжатия.

Исходные данные для экспериментов

Для проведения экспериментов использовалось полученное с помощью 3D-сканера Artec Spider облако точек (рисунок 1). Под облаком точек будем понимать набор вершин в трёхмерной системе координат, которые предназначены для представления внешней поверхности объекта.

Параметры сканирования: процесс сканирования производился в «реальном времени» с использованием программного обеспечения Artec Studio версии 9.2.3.15. Облако точек получено за один проход сканирования.

Рисунок 1. Исходное облако точек различных 3D-объектов

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

Традиционным представлением сканированных данных являются форматы: ply, STL, obj, xyz, WRML, трехмерное облако точек (asc) и другие. В них в текстовой или бинарной форме содержится матрица координат ненулевых точек .

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

Рисунок 2. Общая схема алгоритма компрессии

Основным этапом сжатия является преобразование трехмерной матрицы в линейную бинарную последовательность (в терминологии работы [1] этот этап является нормализацией, ориентированной на семантику данных). Особенностями матрицы являются компактные области точек пространства, соответствующие поверхностям сканируемого объекта, соответственно для этапа нормализации (преобразования ) (рисунок 2) целесообразно использовать алгоритм обхода точек, сохраняющий локальные особенности, например, алгоритм заполняющей пространство кривой (ЗПК). Способ построения ЗПК для применения в процедуре кодирования описан в [2].

Визуализация ЗПК для этого случая представлена на рисунке 3.

Рисунок 3. Заполняющая пространство кривая для трехмерного случая с размерностью 8Ч8Ч8

компрессия сканирование бит алгоритм

Групповое кодирование. После преобразования матрицы из 3D в 1D в сформированной битовой последовательности присутствуют длинные последовательности нулей, которые при использовании группового кодирования типа RLE позволяет достичь уменьшения битового объема.

Алгоритм RLE (Run-Length Encoding) осуществляет групповое кодирование длинных последовательностей нулей. При этом формируются пары вида <пропустить, число>, где «пропустить» является счетчиком пропускаемых нулей, а «число» -- значение, которое необходимо поставить в следующую ячейку. Так, вектор 42 3 0 0 0 -2 0 0 0 0 1 ... будет свернут в пары (0,42) (0,3) (3,-2) (4,1) ... .

Вторичное сжатие. В качестве заключительного этапа вторичного сжатия может быть использован один из методов энтропийного сжатия, например, арифметическое сжатие [3] или сжатие Хаффмана [4]. Эти алгоритмы компрессии позволяют уменьшать среднюю длину кодового слова для символов алфавита.

Результаты. В таблице 2 приведены результаты применения предлагаемого метода для различных сложных пространственных форм, полученных в результате сканирования. При компрессии все пространство разбивалось на трехмерные ячейки размером 256Ч256Ч256, каждая из которых сжималась независимо от других, а результаты сжатия объединялись в единый выходной поток. В таблице приводятся результаты компрессии ячейки 256Ч256Ч256 для разных объектов. Приводится сравнение некомпрессированного битового объема облака точек, заданного в виде координат (RAW-файл), объема RAW-файла, сжатого алгоритмом Deflate, а также результаты применения предложенного алгоритма компрессии с использованием обхода пространства по ЗПК и стандартного построчного преобразования .

Таблица 2

Результаты применения метода

Для экспериментальной проверки предлагаемый метод реализован программно в виде кроссплатформенного приложения на языке Java, представляющего собой кодер/декодер компрессированного потока 3D-данных (рисунок 4). В режиме кодера исходный формат представления (облако точек или набор полигонов) при помощи конвертера преобразуется во внутреннее представление матрицы в виде массива координат точек. Отдельный программный формирователь ЗПК задает порядок обхода матрицы для последующего группового кодирования и вторичного сжатия. При необходимости выходной поток может быть сохранен в одном из стандартных контейнеров (XML, RIFF и т.д.) или стать основой сетевого протокола. Впоследствии кодер/декодер может быть выполнен в виде модуля (plugin) для программных продуктов, работающих с данными в 3D-формате для непосредственной работы с этим форматом. Декодер работает в противоположном направлении и использует тот же программный формирователь ЗПК.

Рисунок 4. Схема программной реализации алгоритма компрессии 3D-данных

Заключение

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

Предложенный метод может быть использован в программном обеспечении, предназначенном для работы с 3D-сканерами и 3D-принтерами, пакетами пост-обработки сложных пространственных форм и системах когнитивного программирования для повышения эффективности использования систем хранения данных 3D-объектов, создания библиотек объектов и сокращении издержек на связь при передаче 3D-объектов.

Литература

1. Кулешов С.В. Критерий оценки энергетической эффективности компрессии видеопотока. // Информационно-измерительные и управляющие системы. №11, т.8, 2010. С. 16-18

2. Александров В.В., Поляков А.О., Лачинов В.М. Рекурсивная алгоритмизация кривой, заполняющей многомерный интервал // Техническая кибернетика. № 1. 1978.

3. Huffman, D.A. A method for the construction of minimum redundancy codes. // In Proceedings IRE, vol. 40, 1962, pp. 1098-1101.

4. Witten I., Neal R.M., Cleary G. Arithmetic coding for data compression // Comm. ACM. - 1987, V.30 - No 6. pp. 520-540

Размещено на Allbest.ru