WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

загрузка...
   Добро пожаловать!

Pages:     || 2 | 3 |

ДК: 528.73.004 На правах рукописи

Велижев Александр Брониславович

РАЗРАБОТКА И ИССЛЕДОВАНИЕ АЛГОРИТМОВ АВТОМАТИЧЕСКОГО ВЗАИМНОГО ОРИЕНТИРОВАНИЯ ТРЕХМЕРНЫХ ДИСКРЕТНЫХ МОДЕЛЕЙ ОБЪЕКТОВ, ПОЛУЧЕННЫХ В РЕЗУЛЬТАТЕ ЛАЗЕРНОГО СКАНИРОВАНИЯ

25.00.34 – «Аэрокосмические исследования Земли, фотограмметрия»

Автореферат диссертации на соискание ученой степени

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

Москва – 2008

Работа выполнена на кафедре фотограмметрии Московского государственного университета геодезии и картографии (МИИГАиК).

Научный руководитель: доктор технических наук, профессор,

Чибуничев Александр Георгиевич

Официальные оппоненты: доктор технических наук,

профессор,

Журкин Игорь Георгиевич

Кандидат технических наук

Кадничанский Сергей Алексеевич

Ведущая организация: Сибирская Государственная

Геодезическая Академия (СГГА)

Защита состоится «27» ноября 2008 года в 10 часов на заседании диссертационного совета Д.212.143.01 при Московском государственном университете геодезии и картографии по адресу: 105064, Москва К-64, Гороховский пер. д.4., МИИГАиК, ауд. Зал заседаний диссертационного совета.

С диссертацией можно ознакомиться в библиотеке МИИГАиК.

Автореферат разослан « » 2008 года.

Ученый секретарь диссертационного совета Краснопевцев Б.В.

Общая характеристика работы

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

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

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

Основные задачи исследования:

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

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

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

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

Разработана компьютерная программа, позволяющая:

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

Апробация работы: Результаты работы докладывались на третьей общероссийской конференции изыскательских организаций «перспективы развития инженерных изысканий в строительстве в российской федерации» в 2007 году; на конгрессе международного общества фотограмметрии и дистанционного зондирования в Пекине в 2008 году, на конференциях студентов, аспирантов и молодых ученых в МИИГАиК в 2006, 2007 годах.

Предлагаемая методика визуализации дискретных точечных моделей внедрена в инженерное программное обеспечение GeoKosmos® GeoModeller.

Публикации: По материалам диссертации опубликовано 4 работы, из них 2 – в журнале, включенном в перечень ВАК.

Структура и объем диссертации: Диссертация изложена на 78 страницах основного текста и состоит из введения, трех глав, заключения и списка литературы. Работа проиллюстрирована 50 рисунками, 5 таблицами. Библиографический указатель содержит 60 источников, в том числе 53 иностранных.

Краткое содержание работы

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

Любую точку P1 можно перевести в систему координат P2, используя уравнение:

(1),

где T – вектор переноса и R – матрица поворота между системами координат точечных моделей P1 и P2, - произвольная точка из P1, - координаты точки в системе координат P2. Пусть N1 и N2 – число точек в точечных моделях P1 и P2.

Таким образом, решение задачи взаимного ориентирования дискретных точечных моделей сводится к отысканию значений трех углов м, м, м, входящих в матрицу поворота R, и трех координат X0, Y0, Z0, задающих вектор переноса T.

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

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

  • с использованием специальных отражателей-марок;
  • с использованием только точек сканирования.

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

Важно отметить, что информации, заложенной в самих результатах сканирования, достаточно для решения задачи ориентирования точечных моделей, поэтому в последние десятилетия параллельно разрабатываются методики ориентирования без использования специальных отражателей. Такие методики имеют более высокой уровень автоматизации технологического процесса, но требуют существенно более сложных и устойчивых алгоритмов решения. Первые работы появились в начале 1990 годов. В течение нескольких лет был независимо разработан и предложен алгоритм итеративного решения задачи, который определил направление развития методов автоматического взаимного ориентирования. Предложенный алгоритм носит название итеративного алгоритма ближайшей точки (далее ICP, от iterative closest point). Данный алгоритм получил очень широкую известность и многочисленные улучшения, ссылки на алгоритм есть практически в каждой научной работе по данной теме. Но важно сразу заметить, что его применение возможно только для уточнения решения задачи и не может быть использовано для решения в общем случае. Такое ограничение обусловлено областью сходимости, которая заложена в основе самого алгоритма. Но, несмотря на ограничение в области применения, алгоритм ICP стал основой решения важных вопросов, которые являются основополагающими для оценки и анализа решения всей задачи. В первую очередь, это вопрос оценки точности и качества решения задачи, во-вторых, это вопрос оценки устойчивости и надежности решения задачи. В диссертации рассматривается развитие методик автоматического взаимного ориентирования точечных моделей, на примере развития алгоритма ICP.

Главным достоинством алгоритма ICP является простота его реализации, однако уже из формулировки алгоритма напрямую следуют и его главные недостатки:

  • требуются значения начальных приближений R1 и T1 для первой итерации;
  • на каждой итерации необходимо выполнять трудоемкую операцию поиска ближайшей точки.

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

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

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

В данной работе предложено разбить решение задачи взаимной ориентации точечных моделей на два главных этапа:

  • оценка матрицы угловой ориентации R;
  • оценка вектора сдвига T.

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

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

Рассмотрим общую блок-схему предлагаемого метода:

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

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

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

Восьмеричное иерархическое дерево обладает следующими свойствами:

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

Рассмотрим понятие ориентационной гистограммы и алгоритм её построения. Расширенные изображения гауссиана (далее, РИГ) являются одним из вариантов представления формы выпуклого многогранника. Построение РИГ осуществляется путем переноса всех единичных векторов нормали к каждой грани многогранника в общий центр – центр гауссовой сферы. Совокупность нормалей и расстояний от центра масс объекта до начала нормали математически строго описывают форму многогранника. Понятие ориентационной гистограммы основано на РИГ. Если наложить на полученную гауссову сферу сетку меридианов и параллелей с заданным угловым шагом, а затем для каждой полученной клетки на сфере рассчитать число нормалей, указывающих на эту клетку, то мы получим сферическое представление ориентационной гистограммы. Можно представить ориентационную гистограмму в виде изображения, каждый пиксель которого соответствует клетке, образованной пересечением меридианов и параллелей на гауссовой сфере, а значением в каждом пикселе изображения будет количество нормалей (Рис. 2.).

Pages:     || 2 | 3 |






© 2011 www.dissers.ru - «Бесплатная электронная библиотека»