автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Модели и методы обработки и представления сложных пространственных объектов

На правах рукописи

АКСЕНОВ Алексей Юрьевич

МОДЕЛИ И МЕТОДЫ ОБРАБОТКИ И ПРЕДСТАВЛЕНИЯ СЛОЖНЫХ ПРОСТРАНСТВЕННЫХ ОБЪЕКТОВ

Специальность 05.13.01 - Системный анализ, управление и обработка информации (технические системы)

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

- I СЕН 2015

Санкт-Петербург - 2015

005561766

005561766

Работа выполнена в Федеральном государственном бюджетном учреждении науки Санкт-Петербургском институте информатики и автоматизации Российской академии наук (СПИИРАН).

Научный руководитель: Кулешов Сергей Викторович,

доктор технических наук

Официальные оппоненты: Дегтярев Владимир Михайлович,

доктор технических наук, профессор, профессор кафедры «Информатики и компьютерного дизайна». Федеральное государственное образовательное бюджетное учреждение высшего профессионального образования «Санкт-Петербургский государственный университет телекоммуникаций им. проф. М.А. Бонч-Бруевича» Потапов Максим Владимирович, кандидат технических наук, ассистент кафедры компьютерной фотоники и видеоинформатики, Федеральное государственное автономное образовательное учреждение высшего образования «Санкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики» (Университет ИТМО)

Ведущая организация: Федеральное государственное автономное

образовательное учреждение высшего образования «Санкт-Петербургскнй политехнический университет Петра Великого» (ФГАОУ ВО «СПбПУ») Защита состоится «29» сентября 2015 г. в 15.00 часов на заседании диссертационного совета Д.002.199.01 при Федеральном государственном бюджетном учреждении науки Санкт-Петербургском институте информатики и автоматизации Российской академии наук по адресу: 199178, Санкт-Петербург, В.О., 14 линия, 39.

С диссертацией можно ознакомиться в библиотеке Федерального государственного бюджетного учреждения науки Санкт-Петербургского института информатики и автоматизации Российской академии наук и на сайте http://www.spiiras.nw.ru/dissovet/

Автореферат разослан « jf'y> авг\'ста 2015 г. Ученый секретарь

диссертационного совета Д.002.199.01 кандидат технических наук, доцент

Фаткиева Роза Равильевна

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы диссертации. На протяжении многих лет человечество искало пути представления пространственного положения объектов, а также способы описания самих этих объектов. Начиная с Р. Декарта и Г. Монжа сформировались парадигмы прямоугольного представления координат в пространстве и способы описания объектов средствами начертательной геометрии путем построения моделей по проекциям.

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

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

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

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

В практических задачах для экономии памяти или ресурсов каналов связи применяется компрессия данных. В методах сжатия применяются теоретические основы, разработанные Ziv J., Lempel A., Welch Т. A, Katz P. W., Huffman D. А., В. В. Александровым, Д. С. Ватолиным и др.

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

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

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

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

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

1. Анализ возможностей цифровых систем получения, представления и обработки пространственных данных.

2. Разработка метода динамического масштабирования пространства облаков точек.

3. Разработка метода переупорядочения в битовый поток, имеющий упорядоченную структуру, обеспечивающую эффективное вторичное сжатие для передачи и хранения.

4. Разработка алгоритма и формата представления цифровых сканов с целью уменьшения битового объема их цифрового представления.

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

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

Предметом исследований являются методы и алгоритмы представления и сжатия цифровых сканов сложных пространственных объектов.

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

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

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

2. Метод динамического разбиения и масштабирования пространства облаков точек для возможности применения заполняющей пространство кривой.

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

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

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

Научная новизна предлагаемой диссертации состоит в следующем:

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

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

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

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

5. Разработана интерактивная система сжатия облаков точек, отличающаяся применением динамического разбиения и масштабирования пространства и заполняющей пространство кривой.

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

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

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

Реализация результатов работы. Представленные в работе методы и алгоритмы были программно реализованы в виде объектно-ориентированной библиотеки классов на языке Java и других вспомогательных программ. Библиотека нашла применение в рамках проектов ОНИТ РАН, НОЦ Курск и учебных курсов.

Апробация результатов работы. Научные результаты и основные положения работы представлялись на конференциях: Всероссийская конференция «Информационные технологии в управлении» (ИТУ-2014), Санкт-Петербург, 2014; International Conference of Young Scientists AUTOMATION & CONTROL (Saint-Petersburg, State Polytechnical University, 2013); «Информационные технологии в управлении» (ИТУ-2012), г. Санкт-Петербург, 2012; VII Международная научно-практическая конференция «Регионы России: стратегии и механизмы модернизации, инновационного и технологического развития», г. Москва, 2011 г.; 10-я Международная конференция «Распознавание образов и анализ изображений: новые информационные технологии» РОАИ-10-2010, г. Санкт-Петербург, 2010, VIII всероссийская научно-практическая конференция с международным участием «Современные информационные технологии в науке, образовании и практике», Оренбург, 2009; 9-я Санкт-Петербургская международная конференция «Региональная информатика - 2004», СПб, 2004.

Публикации. Автором опубликовано по теме диссертации 11 печатных работ, среди них 6 работ в рецензируемых журналах из перечня ВАК.

Структура и объем диссертационной работы. Диссертация объемом 110 машинописных страниц содержит введение, 4 главы и заключение, список литературы (95 наименований), 57 рисунков, 7 таблиц и 2 приложения.

СОДЕРЖАНИЕ РАБОТЫ

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

В первой главе проводится анализ современных методов получения и представления пространственных данных.

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

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

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

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

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

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

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

Следует заметить, что в случае использования портативного ЗБ-сканера в «полевых условиях» без возможности применения хранилищ данных и серверного оборудования проблема компактного хранения объема отсканированных данных становится определяющей. Особенно важно не допускать потерь данных или ухудшения точности представления в результате применения сжатия с потерями, чтобы иметь возможность корректной постобработки ЗБ-объекта без вносимых методом сжатия артефактов. В качестве примера необходимости такого подхода можно привести

рекомендации в профессиональной фотографии использовать RAW-формат вместо формата сжатия с потерями JPEG, используемого в любительской фотографии.

В зависимости от способа получения ЗБ-данных занимаемый ими объем битового представления будет различным.

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

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

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

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

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

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

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

3) Модели, основанные на картах глубины. Включают в себя модели, основанные на изображениях с картами глубины и многослойных изображениях с глубиной. Сложность реализации методов визуализации и поддержки многомасштабности ограничивают возможности применения этих моделей.

4) Точечные представления (облака точек). Объекты моделируется как набор трехмерных координат точек принадлежащих поверхностям объекта. Основной проблемой таких представлений является отсутствие данных о связности точек и их принадлежности к непрерывным поверхностям сканируемого ЗБ-объекта.

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

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

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

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

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

В настоящее время известные методы сжатия данных, полученных в результате ЗО-сканирования, делятся на 2 группы:

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

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

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

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

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

Такое остовное дерево может кодироваться при помощи последовательностей символов В, L. R, F, Т (base, left, right, forward, terminal), способ построения которых основан на алгоритме с использованием линейных предсказателей. Рекурсивное описание точек, принадлежащих поверхности, путем включения их в описание уже построенных деревьев позволяет уменьшать битовую длину представления исходного объекта (рисунок 2). Теоретически, использование метода сжатия позволяет кодировать описание от 2 до 3 бит на точку, что на реальных объектах дает результат компрессии в 517 раз, в зависимости от количества точек в облаке. При этом коэффициент сжатия уменьшается с увеличением количества точек в облаке. Подобные методы показывают очень хорошие результаты на обработанных, сглаженных облаках точек без артефактов и на слабо детализированных объектах без сложной внутренней структуры.

Рисунок 2. Пример описания поверхности при помощи остовного дерева.

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

=31

Щ

Рисунок 3. Облако точек (слева) преобразованное в полигональную сетку

(справа).

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

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

Таблица 1

Ориентировочное сравнение объемов битового

Вид объекта Способ получения Размер, байт

Барельеф 3 D-сканирование 16 757 334

Подшипник 3 D-сканирование 362 982 784

Анатомическая модель «мозг» ЗО-сканирование 4 567 684

Декоративная фигурка 3 D-сканирование 5 950 884

Барельеф2 3 D-сканирование 10 866 084

Вертолет (модель) синтезирован в 3 D Studio Мах 5 505 893

Стереопара в НО-качестве (фильм) ЗО-камера 12 441 600

Кроме того, в задаче представления и компрессии многомерных данных важно учитывать характерные особенности технической системы «ЗЭ-сканер— программное обеспечение сканера», проявляющиеся на этапах постобработки (например, склейка слоев, удаление пустых областей и т.д.). Эти особенности (артефакты) связаны с относительным взаимным смещением координатных сеток, по которым происходит привязка точек отсканированных поверхностей (рисунок 5).

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

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

Рисунок 4. Примеры облаков точек («подшипник» и «барельеф»).

Рисунок 5. Артефакты при автоматической склейке отсканированных

поверхностей.

Массив М является разреженным, что обусловлено близким расположением точек, принадлежащих поверхностям сканируемого объекта, соответственно для этапа нормализации (преобразования И3—»Я1) целесообразно использовать алгоритм, основанный на применении развертки специального вида, для обхода точек трехмерного пространства.

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

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

Наиболее часто применяемые типы разверток можно разбить на три класса:

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

2) Рекурсивные развертки (рисунок 6), являются приближением к некоторой заполняющей пространство кривой. Закон построения этих разверток полностью определяется первым и вторым приближением.

п

! Г

п

г

я 1

ТС ■*£.

год

Рисунок 6. Рекурсивные виды разверток.

3) Замкнутые блочные развертки (рисунок 7). В этих развертках, в отличие от рассмотренных выше, последующее приближение получается из предыдущих не в соответствии с первым приближением, а за счст использования связей, обеспечивающих замыкание развертки.

ш

Б ПГ71 й

1x1.11гг1

шЗ щ\1 гО Еш

гп] 1._п

Й Сш Ы И

Рисунок 7. Замкнутые блочные виды разверток.

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

Для случая блока 8Х8Х8, порядок обхода точек при преобразовании 11''—»Я1 с использованием ЗПК будет иметь вид, представленный на рисунке Я.

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

ГГри использовании ЗПК для успешного решения задачи взаимнооднозначного соответствия координат точки в пространстве R3 , представленной в дискретном виде с конечным числом десятичных знаков, координатам пространства R1 требуется производить динамическое разбиение и масштабирование пространства исходных облаков точек пространства R3.

Для этого разработана модель представления пространственных объектов, использующая упорядоченное одномерное представление облаков точек ЗО-объекта: {S, C,/?(G)}, где S — облако точек, G — кривая, задающая порядок точек, R(G) - функция развертки, соответствующая порядку обхода точек G. Приведенное ниже функциональное описание является основой модели представления пространственных объектов, использующей упорядоченное одномерное представление.

В рамках разработанной модели определяется область пространства, содержащего все облако точек сканированного объекта, определяется шаг квантования и коэффициенты, обеспечивающие представление облака точек на регулярной сетке без потери пространственного разрешения путем перевода координат в целочисленные значения (рисунок 9, 10). После этого находится необходимое количество элементов разбиения для заданного объекта (рисунок 11). Шаг квантования берется равным весу младшего разряда числовых значений координат полученных системой сканирования и не изменяется в процессе работы, Ах = S, где min S такое что (105 • х) е ж.

/ ""Г4

Рисунок 9 - Область пространства (параллелепипед), ограничивающая

облако точек.

А

1

0,8 0,6 0,4 0,2 0

(0,8; 0,8)

(0,2; 0,65)

г Ау=0,01

(0,4; 0,2) (0,8; 0,2)

100 80

N 60

40 20 0

(8; 80)

(2; 65)

(4; 20) (й; 20)

0 0,2 0,4 0,6 0,8 1 0 2 4 6 8 10

Рисунок 10. Иллюстрация преобразования координат в облаке точек.

Рисунок 11. К понятию динамического разбиения и масштабирования пространства облаков точек.

Используя вышеописанное динамическое разбиение пространства (рисунок 11). содержащего ЗЭ-объект, и его масштабирование в пространстве, координаты точки (х1, у', г') внутри элемента разбиения (;', ], I) вычисляются согласно выражению:

X — кх(х ^оЗ £ X БХ у' = ку(у-у0) -) X Бу, г' = к2(г - г0) — I х эг где ¿,у, / — позиция текущего элемента разбиения пространства, х0, у0, г0 — начальное смещение облака точек относительно нуля системы координат, кх,ку,кг— коэффициенты масштабирования по ширине, высоте и глубине соответственно, и х 5у х 52 — размер единичного элемента, к которому применяется компрессия данных.

Функционально процесс сжатия без потерь можно представить в следующем виде: пусть 5 — множество точек, описывающих исходный объект

N

в форме облака точек. Испол ьзуя отображение о > производится

нормализация координат точек с целью получить целые значения координат

с

х',у',г' е /Е, р' (х',у'6 . После этого, используя отображение Б -> 5С с использованием заполняющей пространство кривой в: q=f(x,y,z), задавая отношение линейного порядка для элементов р' формируется упорядоченный кортеж точек. Здесь [{х, у, г) — функция порядкового номера <7 элемента р'^х'.у'.г') £ в кортеже 5С {рц}

г 1 (0,если р(х,у,г) ? Яд = /(х,у,г) I <7-1' ч (1, если р(х,у, г) е Б, <7 =/(х,

Представив полученный кортеж {clq} как битовую последовательность длиной |5| , к ней применяются описанные ниже операции группового кодирования и вторичного сжатия, после которых формируется окончательный битовый поток.

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

М

3D->1D RLE вторичное

сжатие

компрессированный формат

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

После преобразования массива М из R —>R в сформированной битовой последовательности присутствуют длинные последовательности нулей, которые при использовании группового кодирования типа RLE (англ. Run-length encoding) позволяет достичь уменьшения битового объема.

Алгоритм RLE осуществляет групповое кодирование длинных последовательностей нулей. При этом формируются пары вида <пропустить,

число>, где «пропустить» является счетчиком пропускаемых нулей, а «число» — значение, которое необходимо поставить в следующую ячейку. Так. вектор (42, 3, 0, 0, 0, -2, 0, 0, 0, 0, 1) будет свернут в пары (0,42) (0,3) (3,-2) (4,1), а конкретное битовое представление будет зависеть от реализации.

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

При этом битовая последовательность: (0, 0, 0, 0, 0, 1, 0. 0, 0, 1, 1, 0, 1, 0, 0, 0) будет преобразована в вид (0,5), 1, (0,3), 1,1, (0,1), 1, (0,3) и представлена в виде последовательности байтов (0, 5, 1, 0, 3, 1, 1, 0, 1, 1, 0, 3), при этом значение байта "0" зарезервировано для кодирования последовательностей нулей.

В качестве заключительного этапа вторичного сжатия может быть использован один из методов энтропийного сжатия, например, арифметическое сжатие, сжатие с предсказанием по частичному совпадению (РРМ), группа алгоритмов сжатия LZxx, сжатие Хаффмана и ряд других. Эти алгоритмы компрессии позволяют уменьшать среднюю длину кодового слова для символов алфавита.

На рисунке 13 приведена схема программной реализации алгоритма компрессии ЗЭ-данных.

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

Сравнительный анализ эффективности сжатия разработанным алгоритмом в различных режимах работы приведен на рисунке 14. Здесь используются следующие сокращения: грк+г1е — вариант алгоритма с использованием ЗПК с групповым кодированием без энтропийного сжатия.

грк+г1р — вариант алгоритма с использованием ЗПК с энтропийным сжатием без группового кодирования, грк+г1р+г!е — вариант алгоритма с использованием ЗПК с энтропийным сжатием после группового кодирования.

Из графика видно, что применение алгоритма с использованием ЗПК совместно с энтропийным сжатием после операции группового кодирования дает наилучшие результаты с точки зрения сжатия.

"»üHzpk+zip *~*»»zpk+rle+zip

169 609 654 1018 1538 1873 2018 Количество точек очек в облаке

Рисунок 14. Сравнительный анализ эффективности разработанного алгоритма для различных режимов работы.

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

Процесс сканирования 30-объекта включает в себя ряд последовательных действий, каждое из которых влияет на конечный результат сканирования. В связи с этим программное обеспечение ЗО-сканера (ПОС), осуществляющее реконструкцию облака точек из набора изображений, полученных с нескольких камер ЗО-сканера. а также его постобработку имеет смысл рассматривать как техническую систему «ЗО-сканер — ПОС». В качестве ПОС в экспериментах использована система «Artec Studio» версии 9.2.

Влияние ПОС проявляется в первую очередь в изменении (часто искажении) формы объекта при попытке компенсировать ошибки в работе сканера.

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

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

Таблица 2

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

Объект Количество Исходный формат, байт Результат сжатия

точек в облаке Текстовый Бинарный предложенным

obj float методом, байт

1 — коннектор 169 10140 3042 274

Бочонок с резьбой (горизонтально) 609 36540 10962 395

Разъем питания 654 39240 11772 424

Разъем mini Din 1018 61080 18324 512

Светодиодная лампочка 1538 92280 27684 659

Дроссель 1873 112380 33714 758

Штыревой разъем 2018 121080 36324 715

Бочонок с резьбой (вертикально) 4122 247320 74196 916

Уголок с резьбой 5784 347040 104112 1665

Трансформатор 12463 747780 224334 3048

На рисунке 15 приведена зависимость уровня сжатия (выраженного в битах на точку) от количества точек в исходном объекте для предложенного метода на основе ЗПК (вариант zpk+rle+zip) в сравнении с методами сжатия без потерь на основе остовного дерева (метод Octree, метод Spanning tree).

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

Бит на точку

о ..........г—-----------,---------,------------------<—...........

4СОС- SOOO 16300 32SOO &49&3 US0Í30 J5S900

Количество точек s обпакв

Рисунок 15. Сравнение разработанного метода с существующими методами компрессии.

Предложенный метод может быть использован в программном обеспечении, предназначенном для работы с 31>сканерами и ЗО-принтерами. пакетах гюст-обработки сложных пространственных форм и в системах

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

В приложении А приводятся фрагменты программного кода для обработки облаков точек.

ЗАКЛЮЧЕНИЕ

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

1. Проведен анализ современного состояния и возможностей технических систем получения, представления и сжатия пространственных данных.

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

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

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

5. Разработана интерактивная система сжатия облаков точек, отличающаяся применением динамического разбиения и масштабирования пространства и заполняющей пространство кривой.

Полученные результаты соответствуют п. 5 «Разработка специального математического и алгоритмического обеспечения систем анализа, оптимизации, управления, принятия решений и обработки информации», п. 12 «Визуализация, трансформация и анализ информации на основе компьютерных методов обработки информации» паспорта специальности 05.13.01 «Системный анализ, управление и обработка информации (технические системы)».

СПИСОК ПУБЛИКАЦИЙ ПО ТЕМЕ ДИССЕРТАЦИИ

Работы автора в рецензируемых журналах из перечня ВАК

1. Аксенов А.Ю., Александрова В.В., Зайцева A.A. Метод эффективного представления ЗО-данных, полученных в результате ЗО-сканирования // Информационно-измерительные и управляющие системы, 2014, №6. С. 20-25.

2. Аксенов А.Ю. Исследование применимости существующих методов сжатия к ЗБ-видео данным. /У Труды СПИШ'АН. 2013. Вып. 4(27). С. 73-80.

3. Аксенов АЛО., Зайцева A.A., Кулешов C.B. О критерии адекватности цифровых трактов передачи данных // Информационно-измерительные и управляющие системы, №7, т.8, 2010. С. 75-77.

4. Аксенов А.Ю., Зайцева A.A. Применение программируемой технологии к обработке сигналов и изображений // Информационно-измерительные и управляющие системы, №11, т.7, 2009. С.63-66.

5. Кулешов C.B., Зайцева A.A., Аксенов А.Ю. Ассоциативно-пирамидальное представление данных. // Информационно-измерительные и управляющие системы, №4, т.6, 2008. С. 14-17.

6. Кулешов С. В., Аксенов A. FO-, Зайцева А. А., Идентификация факта компрессии с потерями в процессе обработки изображении // Труды СПИИРАН. Вып. 5. СПб.: Наука, 2007. С. 60-65.

Работы автора в других изданиях

7. A. Aksenov, S. Kuleshov, A. Zaytseva. Аи application of computer vision systems to solve the problem of unmanned aerial vehicle control // Transport and Telecommunication, 2014, volume 15, no. 3, 209-214 (индексируется в системе Scopus).

8. S. Kuleshov, A. Zaytseva, A. Aksenov. Spatiotemporal Video Representation and Compression // Pattern Recognition and Image Analysis. Vol. 23, No. 1, 2013. p.87 (индексируется в системе Scopus).

9. Аксенов А.Ю., Александрова В.В., Зайцева А.А. Особенности представления пространственных данных, полученных в результате ЗО-сканирования // Материалы конференции «Информационные технологии в управлении» (ИТУ-2014). СПб.: ОАО «Концерн «ЦНИИ «Электроприбор», 2014. С. 440-444.

Ю.Аксенов А.Ю., Зайцева А. А., Кулешов С.В. Критерий е-идентнфицируемости в обработке аудио и видео данных // Материалы VIII всероссийской научно-практической конференции с международным участием «Современные информационные технологии в науке, образовании и практике». Оренбург, 25-27 ноября 2009.

11.Аксенов А.Ю., Макаров А.Н. Цифровая технология анализа и синтеза сигналов. // По пути прогресса - к новым достижениям / ОАО "Научно-производственное предприятие «Радар ммс»/ Сб. материалов под редакцией Генерального директора-Генерального конструктора Г.В.Анцева. СПб.: ООО «Издательство «Логос», 2006. с.188-191.

Типография «Копицентр «Васнлеостровский» 199004, Санкт-Петербург, 6-линия д.29, В.О. Подписано в печать 24.07.2015 г. Формат 60x84 1/16. Тираж 100