UKR | ENG || ДонНТУ > Портал магистров ДонНТУ
Магистр ДонНТУ Черниговский Дмитрий Яковлевич

Черниговский Дмитрий Яковлевич

Факультет: Вычислительной техники и информатики
Специальность: Программное обеспечение автоматизированных систем
Тема выпускной работы: Эффективная программная визуализация реальных объектов заданных моделями класса «облако точек»
Руководитель: Зори Сергей Анатольевич

Биография | Библиотека | Ссылки | Отчет о поиске | Индивидуальное задание

Эффективная программная визуализация реальных объектов заданных моделями класса «облако точек»


Введение

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

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

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

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

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

Цели и задачи, которые должны решаться

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

При этом должны быть решены следующие задачи:

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

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

Актуальность темы

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

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

Предполагаемая научная новизна

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

Планируемые практические результаты

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

Обзор исследований и разработок по теме

В мире уже существуют разработки, касающиеся подобных программных систем. Хотелось бы перечислить наиболее успешные из них:
  1. Leica Cyclone. Программный комплекс Leica Cyclone – одно из самых распространенных в мире решений для обработки данных наземного лазерного сканирования. Leica Cyclone содержит в себе все инструменты, необходимые для выполнения полного цикла работ с использованием оборудования Leica HDS, начиная с управления процессом сканирования и заканчивая оформлением конечного результата и передачей его заказчику. Работа в Cyclone возможна как в однопользовательском режиме, так и по технологии «Клиент-Сервер», с использованием плавающих или узловых лицензий. Комплекс Leica Cyclone состоит из отдельных модулей, встраиваемых в единую программную оболочку. Каждый модуль предназначен для решения конкретного круга задач и соответствует определенному этапу обработки данных сканирования [5].
  2. DAVID. Бесплатное программное обеспечение, которое дает возможность выполнять трехмерное сканирование объектов и преобразовывать полученный результат в модели, которые можно импортировать в 3D-редакторы. К сожалению, на бесплатную версию накладываются некоторые ограничения сравнительно с платной программой DAVID Pro [4].

Представители локального уровня:
  1. Бабков Виктор Светозарович, «Реконструкція 3D-моделей реальних об’єктів методом RBF з використанням GPU». В работе Виктора Светозаровича исследуются возможности реконструкции моделей объектов, средствами распараллеливания вычислений на процессоре графической платы [1].
  2. Хромова Елена Николаевна, «Воссоздание поверхности по произвольному набору точек. Подзадача построения плоскости, наименее удаленной от совокупности точек». Отличиями работы Елены Николаевны являются использование иных методов обработки облака точек, используемые программные инструментальные средства и отсутствие возможности стерео визуализации [2].

Постановка задачи

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

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

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

Таким образом, задачу визуализации объекта представленного облаком точек можно разделить на три этапа:

1. Построение интерполирующей поверхности

2. Триангуляция полученной поверхности

3. Вывод полигональной модели на экран

При использовании стереовизуализации добавляется этап формирования стереопары и ее последующее преобразование в стереоизображение.

Построение поверхностной модели. Метод RBF.

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

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

Задача триангуляции. Обзор методов.

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

{(x,y,z)|f(x,y,z)=c}

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

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

Ячеечные методы (cell-based)

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

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

Наиболее известные ячеечные алгоритмы: метод Канейро (Caneiro), метод, предложенный Гуэзеком (Gueziec), метод Скалы (Skala), метод «Марширующих кубов».

Метод предиктора-корректора (predictor-corrector)

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

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

Мозаичные методы (pre-tessellation methods & particle-based methods)

Суть таких методов заключается в разбиении искомой поверхности на части и дальнейшей их триангуляции. Разбиение на части в pre-tessellation методах подразумевает разбиение поверхности на «примитивные» поверхности - фрагменты сфер и плоскостей. Разбиение на части в методах из плеяды particle-based - менее «интеллектуально» - ищутся только фрагменты плоскостей. При этом возникает проблема «соединения» уже «протриангулированных» частей. Чаще всего этот процесс сводится к подбору локальных по Делоне треугольников, соединяющих части искомой поверхности.

Определение: треугольник локален по Делоне, если его самая маленькая сфера ограничения не содержит никакую другую точку триангуляции, которая имеет ту же самую поверхностную ориентацию.

Достоинства и недостатки методов триангуляции

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

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

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

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

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

Однако, рассматриваемые алгоритмы имеют одну и ту же основу. Поэтому скорость и ошибка аппроксимации различаются несущественно. Таким образом, анализ алгоритмов достаточно провести по следующим критериям - количество треугольников, «качество» треугольников.

Обзор методов формирования стереоизображений

Метод сквозного взгляда

Этот метод позволяет видеть стереокартинку без использования какого-либо оборудования.

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

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

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

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

Метод перекрёстного взгляда

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

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

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

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

Анаглифовые очки

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

Растровая стереофотография

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

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

Затворные стереоочки

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

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

Поляризованные стереоочки

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

Обычно этот метод применяется в стереокинотеатрах.

Стереомонитор

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

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

Стереошлем

Виртуальный шлем (VR HMD) — шлем с двумя проекторами, который показывает для каждого глаза отдельные изображения. В результате этого получается стереоэффект.

«Псевдостереоскопия»

Восприятие объёма может быть получено не только с помощью одновременного рассматривания объекта или изображения двумя глазами одновременно, но и путём достаточно быстрой смены изображений в одном канале изображения (при монокулярном зрении). Так, технология GIF-анимации позволяет создавать псевдостереоскопические объёмные изображения.
Пример псевдостерео. (Анимация, 32 Кб, 410*230 px, состоит из 4-х кадров, задержка между кадрами 100мс, семь циклов воспроизведения)

Пример псевдостерео.
(Анимация, 32 Кб, 410*230 px, состоит из 4-х кадров, задержка между кадрами 100мс, семь циклов воспроизведения)

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

Формирование стереопары

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



для формирования корректной Off-axis стереопары необходимо модифицировать матрицу таким образом

Здесь переменные означают:

Выводы

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

Литература

  1. Бабков В.С. Реконструкція 3D-моделей реальних об’єктів методом RBF з використанням GPU / В.С. Бабков // Наукові праці Донецького національного технічного університету. Серія: “Інформатика, кібернетика та обчислювальна техніка”, випуск 9 (132). – Донецьк: ДонНТУ. 2008. – С. 132-136.
  2. Хромова Е.Н., Пауков Д.П., Башков Е.А. «Воссоздание поверхности по произвольному набору точек. Подзадача построения плоскости, наименее удаленной от совокупности точек» ІІ Республіканська наукова конференція студентів , аспірантів та молодих вчених «Комп ’ютерний моніторинг та інформаційні технології» Донецк ДонНТУ 15 мая 2006г.
  3. Башков Е.А. Исследование возможностей применения RBF-алгоритма и его модификаций для построения поверхностных компьютерных моделей в медицинской практике / Е.А. Башков, В.С. Бабков // Сборник трудов международной конференции "Моделирование-2008", 14-16 мая 2008 г. – Киев: Институт проблем моделирования в энергетике им. Г.Е. Пухова, т. 1, 2008. - С. 166–171.
  4. DAVID-laserscanner [Электронный ресурс] / Сайт DAVID, - http://www.david-laserscanner.com/
  5. Leica Geosystems [Электронный ресурс] / Leica Geosystems, - http://www.leica-geosystems.ru/ru/index.htm
  6. Горькавый И. Н. Автоматизация обработки данных лазерного сканирования для получения высокоточных трехмерных моделей земного рельефа / ВМиК МГУ. http://2006.edu-it.ru/docs/4/04_09_Gorkaviy.doc
  7. Ohtake Y., Belyaev A. G., Proceedings of the International Conference on Shape Modeling & Applications, Page: 74, 2001. http://cis.k.hosei.ac.jp/~F-rep/OhtakeSmi01.pdf
  8. Ohtake Y., Belyaev A. G., ACM Symposium on Solid Modeling and Applications, pp. 171 - 178, 2002. http://cis.k.hosei.ac.jp/~F-rep/SM02ob.pdf
  9. Durst M., "Letters: Additional Reference to Marching Cubes" Computer Graphics, vol. 22, no. 2, pp. 72-73, 1988.
  10. Skala V., Conference on Scientific Computing 2000, pp. 368 - 378. http://www.emis.de/journals/AMUC/_contributed/algo2000/skala.pdf

Примечание

На момент написания данного автореферата магистерская работа не является оконченной. Окончательный вариант работы может быть получен у автора или его руководителя после 1 декабря 2009 г.

Биография | Библиотека | Ссылки | Отчет о поиске | Индивидуальное задание