Бесплатный автореферат и диссертация по наукам о земле на тему

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

ВАК РФ 25.00.34, Аэрокосмические исследования земли, фотограмметрия

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

ДК: 528.73.004

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

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

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

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

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

Москва-2008

003452142

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

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

профессор,

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

Официальные оппоненты:

доктор технических наук, профессор, Журкнн Игорь Георгиевич

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

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

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

Защита состоится «27» 2008 года в (О56* часов на заседании

диссертационного совета Д.212Л43.01 при Московском государственном университете геодезии и картографии по адресу: 105064, Москва К-64, Гороховский пер. д.4., МИИГАиК, ауд. Зал заседаний диссертационного совета.

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

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

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

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

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

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

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

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

® Провести теоретический анализ существующих методик и

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

э Разработать алгоритм автоматического взаимного

ориентирования трехмерных дискретных моделей объектов без использования специальных марок-отражателей;

® Провести экспериментальный анализ точности алгоритма взаимного ориентирования трехмерных дискретных моделей объектов;

Данная работа посвящена автоматизации решения задачи

С'1

• Разработать алгоритм быстрой визуализации результатов лазерного сканирования.

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

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

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

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

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

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

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

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

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

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

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

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

Любую точку Pi можно перевести в систему координат Р2> используя уравнение:

Я-&Л+Г (IX

где Т — вектор переноса и Я - матрица поворот между системами координат точечных моделей Р| и Р2, р,- произвольная точка из Р^ ¡\ -координаты точки р1 н системе координат Р2 Пусть N1 и N2 - число точек в . точечных моделях Р| и Р2

Таким образом, решение задачи взаимного ориентирования дискретных точечных моделей сводигся к отысканию значений трех углов схм, юм, км, входящих в матрицу поворота Л, и трех координат Х0, Уо, Z0, задающих вектор переноса Т.

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

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

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

• с использованием только точек сканирования.

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

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

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

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

в требуются значения начальных приближений Rj и Ti для первой итерации;

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

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

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

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

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

• отождествление соответствующих точек;

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

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

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

• оценка матрицы угловой ориентации К;

• оценка вектора сдвига Т.

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

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

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

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

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

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

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

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

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

• все узлы одного уровня не пересекаются;

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

• точки сканирования хранятся только в листьях дерева;

• все потомки одного уровня покрываюг все пространство корня дерева. Рассмотрим понятие ориентационной гистограммы и алгоритм её

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

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

Рис. 2. А — дискретная модель фасада церкви, В — соответствующая ориентационная гистограмма. Пик ориеитационной гистограммы соответствует плоскости фасада церкви.

Рассмотрим алгоритм построения ориеитационной гистограммы Н: • Вычисляем размер матрицы ориеитационной гистограммы //

® Инициализируем все элементы матрицы нулевыми значениями ® Для каждого вектора нормали У1ШПП: о Вычислить значения углов ш и а

о Вычислить значения индексов (а_М,ш_М) ориеитационной матрицы

о Увеличить значение матрицы Н(а_Ш,ю_Ш)на единицу Примеры дискретных точечных моделей и их ориентационных гистограмм приведены на рисунке 3.

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

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

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

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

, (17)

где Д е $0(3) - матрица поворота.

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

Введем функцию схожести С(Н, #2) для двух ориентационных гистограмм

»1 и л2

МхИ МхЫ

Н, и Я,:

С(//,,Я2) = -

(18)

N М

V1-1 1-1

Рассмотрим алгоритм оценки угловой ориентации двух точечных представлений объекта:

1 Расчет ориентационных гистограмм Я, и Н2 для Г, и Р2 соответственно;

2 Поиск максимума значений функции схожести С(Я Я2) при различных допустимых значениях матрицы поворота К .

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

[II_I_I-1_1_I_I_I_

-180 -150 -1D0 -50 0 50 100 150 180 Рис. 3 График зависимости функции схожести С(Н Н2) при поворотах

ориешпационной гистограммы вокруг оси Z с шагом 3 градуса.

Рассмотрим построение воксельного представления дискретной

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

Если для каждой точки облака доступна информация о цвете или интенсивности отраженного сигнала, то эту информацию можно использовать в качестве значений элементов вокселей [1].

После нахождения матрицы угловой ориентации двух дискретных представлений объекта Rc на основе сравнения ориентационных гистограмм к каждой точке Гг применяется преобразование поворота:

Л'. -/'. (24)

где Р\ - массив трехмерных точек, соответствующий повернутым точкам /'2. В результате дискретные точечные представления и 1"2 имеют одинаковую угловую ориентацию, поэтому их взаимное положение определяется . простым преобразованием:

Р\ = Р,+Т, (25)

где Г = (Тх Тг Т7 )г - вектор переноса.

Пусть V, - бинарное воксельное представление, вычисленное для

м^шк

объекта Р1, а \\ - для Р\. Значение вектора сдвига Т соответствует

МхНхК

максимуму корреляционной функции для двух вексельных представлений :

0(0= ¡Г,(г)-У^р-т)ф (26)

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

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

Таблица 1. Описание тестовых наборов

№ Описание Количество точек в одной модели Шаг сканирования, см Количество моделей

1 Фасад церкви с колокольней 50 ООО 2.40 4

2. Плоский фасад церкви с глубоким порталом 60 ООО 3.10 2

3. Выпуклая гладкая поверхность, без ярких особенностей 75 ООО 0,25 2

4. Скульптура на постаменте 45 ООО 3.00 4

5. ве стороны 110 000 1.00 6

фасада церкви с одним большим куполом, с деревьями на фоне

6. Широкий фасад замка, деревья 110 000 2.40 2

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

сначала приближенно ориентировались с помощью предложенной в данной работе методики. А затем, точное решение автоматически вычислялось в про1рамме Trimble RealWorkSurvey версии 6.0. Важно отметить, что алгоритм автоматического ориентирования, заложенный в программе RealWorkSurvey требует ручного приближенного ориентирования точечных моделей путем указания трех соответствующих точек. Предложенная в данной paGoie методика позволяет исключить этап ручного указания пар точек и полностью автоматизировать этап взаимной ориентации. Результаты тестирования алгоритма приведены в таблице 5. Угол а - результирующая оценка взаимного угла вокруг оси Z систем координат первой и второй дискретной точечной модели.

Таблица 2. Результаты взаимной ориентации точечных моделей

№ Название а,0 Время, с Точность, см / кол-во точек

1 Церковь, город Вартбург 70 30 2.22/24569

2. Церковь, город Вартбург (2) -51 52 2.20/25189

3. Готический собор -73 33 5.10/23411

4. Фарфоровая скульптура кошки 78 47 0,11 /45913

5 Скульптура льва в натуральную величину -46 37 3.01 /28943

6. Скульптура льва в натуральную величину (2) 4 34 3.62/27812

7. Скульптура льва в натуральную величину (3) -10 41 3.26/29456

8. Скульптура льва в натуральную величину (4) 128 34 3.47/31856

9. Церковь Самарина 43 36 0,50 / 45259

1 0 Церковь Самарина (2) 39 43 0,71 /49546

1 1 1 ЦсрКииь СаМарйна уЗ) -115 30 0,43 / 39748

1 2 Замок Вельфеншлос 72 41 2.12/83443

Точность решения задачи оценивалась путем вычисления расстояний от точек первой точечной модели до ближайшей точки второй модели. В столбце 3 таблицы (5) приведено среднее расстояние между точечными моделями рассчитанное по указанному количеству точек.

Па рисунке 5. показаны результаты взаимного ориентирования точечной модели замка Вельфеншлос.

.. . 1 1 1 . я ; Г|

. • • <• |Я;!?1 ; 1 ■■ и ' • ■ ' - . 1 -; (''Г' "у. ■/? - ? А '

?|г' •у-с У ' к, * " •.•ГТ^''

г г*1

Рис. 4. Результаты взаимного ориентирования точечной модели замка Вельфеншлос. а) исходные неориентированные точечные модели б) результат автоматического приближенного ориентирования по предложенной методике

При анализе результатов взаимного ориентирования дискретных точечных моделей можно использовать субъективную визуальную оценку. Такой подход позволяет быстро выявить грубые ошибки ориентирования, а также помогает оценить результат в случае симметричного объекта сканирования. В настоящее время производительность лазерных сканеров увеличивается с каждым годом. Современные наземные лазерные сканеры импульсного типа способны сканировать поверхность объекта со скоростью порядка 10 ООО точек в секунду, а сканеры фазового типа - порядка 500 ООО точек в секунду. Большинство существующих видео-карт широкого доступа могут отображать порядка 1-3 миллионов точек без ощутимых задержек. Однако, объемы данных, с которыми приходится сталкиваться на практике, существенно превышают указанный объем. Таким образом, на практике возникают трудности с быстрой визуализацией больших объемов точечных данных.

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

1. быстро отображать данные при любых операциях навигации по сцене (масштабировании, вращении, сдвиге);

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

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

® использование специальной структуры данных для хранения координат

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

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

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

В диссертационной работе решены следующие задачи:

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

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

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

4. Выполнены многочисленные экспериментальные исследования предложенной методики автоматического ориентирования дискретных точечных моделей. Результаты исследования показывают высокую эффективность и надежность решения задачи.

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

Публикации по теме диссертации

1. Чибуничев А.Г., Велижев А.Б., Автоматическое определение взаимной ориентации трехмерных моделей объектов, полученных по результатам лазерного сканирования, «Геодезия и аэрофотосъемка», Москва, 2007, № 1, стр. 127-134.

2. Чибуничев А.Г., Велижев А.Б., Автоматическое сопоставление облаков точек, полученных в результате наземного лазерного сканирования, с использованием ориентационных гистограмм, «Геодезия и аэрофотосъемка», 2008, Москва, №3, стр. 112-119

3. Велижев А.Б., Визуализация результатов лазерного сканирования, "Инженерные изыскания", 2008, №2, стр. 94-95

4. A. Chibunichev, A. Velizhev, "Automatic Matching of Terrestrial Scan Data Using Orientation Histograms", The International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, 2008, Vol. XXXVII. Part B5, Beijing, p.601-604

Подписано в печать 21.10.2008. Гарнитура Тайме Формат 60x90/16. Бумага офсетная. Печать офсетная. Печ. л. 1,5 Тираж 80 экз. Заказ № 231 Цена договорная

Отпечатано в УПП «Репрография» МИИГАиК 105064, Москва, Гороховский пер., 4

Содержание диссертации, кандидата технических наук, Велижев, Александр Брониславович

Введение.

1. Обзор методов взаимного ориен гирования дискретных точечных моделей.

1.1 Введение.

1.2 Итеративный алгоритм ближайшей точки.

1.3 Получение начальных приближений.

1.4 Выбор точек для поиска соответствий.

1.5 Выбор пространства поиска соответствий.

1.6 Поиск соответствий.

1.7 Минимизация.

1.8 Выводы.

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

2.1 Введение.

2.2 Построение восьмеричного дерева.

2.3 Построение ориентадиониой гистограммы.

2.4 Сравнение ориентационных гистограмм, оценка угловой ориентации.

2.5 Построение воксельного представления дискретной точечной модели.

2.6 Сравнение воксельных представлений дискретных точечных моделей методом Фурье анализа.

2.7 Выводы.

3. Описание алгоритма автоматической взаимной ориентации дискретных точечных моделей.

3.1 Введение.

3.2 Чтение файла данных с координатами точек двух точечных моделей.

3.3 Определение пространственных границ каждой точечной модели.

3.4 Рекурсивное построение восьмеричного дерева для каждой точечной модели

3.5 Вычисление нормалей и фильтрация точек.

3.6 Вычисление матрицы ориентацпонной гистограммы.

3.7 Оценка угловых параметров взаимной ориентации точечных моделей.

3.8 Выравнивание угловой ориентации точечных моделей.

3.9 Построение воксельного представления каждой точечной модели.

ЗЛО Оценка вектора сдвига и линейное выравнивание точечных моделей.

3.11 Сохранение второй развернутой точечной модели в файл.

3.12 Описание тестовых данных.

3.13 Результаты автоматического взаимного ориен тирования.

3.14 Визуализация дискретных точечных моделей.

3.14.1 Обратное движение точек.

3.14.2 Динамическая визуализация точечных моделей.

3.14.3 Результаты работы алгоритма визуализации точечных моделей.

3.15 Выводы.

Введение Диссертация по наукам о земле, на тему "Разработка и исследование алгоритмов автоматического взаимного ориентирования трехмерных дискретных моделей объектов, полученных в результате лазерного сканирования"

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

Математическим и методическим аспектам обработки данных лазерного сканирования посвящено сравнительно небольшое количество научных работ российских и зарубежных ученых. Стоит отметить, что значительный вклад в разработку данной научной темы внесли российские ученые кандидат технических наук Михайлов А.П., доктор технических наук Журкин И.В., а также и зарубежные ученые Бесл, П.Дж. и МакКей Н.Д.

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

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

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

3д1 ,г3 3.xI Зг| где Т - вектор переноса иЕ- матрица поворота между системами координат точечных моделей Р| и Рч, р1 - произвольная точка из Р|, /?, - координаты точки в системе координат Р2. Пусть N1 и N2 - число точек в точечных моделях Р| и Ро.

Таким образом, решение задачи взаимного ориентирования дискретных точечных моделей сводится к отысканию значений грех углов ам, оом, км. входящих в магрицу поворота Л, и трех координат Х0, У0, задающих вектор переноса Т.

В данной работе предлагается автоматическая методика о гыскания значений К и Т без знания каких-либо начальных значений параметров взаимной ориентации точечных моделей (Х0, У о, ¿о, <*м, <»м, км).

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

Заключение Диссертация по теме "Аэрокосмические исследования земли, фотограмметрия", Велижев, Александр Брониславович

3.15 Выводы

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

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

Заключение

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

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

В диссертационной работе решены следующие задачи:

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

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

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

4. Выполнены многочисленные экспериментальные исследования предложенной методики автоматического ориентирования дискретных точечных моделей. Результаты исследования показывают высокую эффективность и надежность решения задачи.

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

Библиография Диссертация по наукам о земле, кандидата технических наук, Велижев, Александр Брониславович, Москва

1. Arun, K., Huang, Т., and Blostein, S. "Least-Squares Fitting of Two 3-D Point Sets," Trans. PAMI, Vol. 9. No. 5, 1987

2. Benjemaa. R. and Schmitt, F. "Fast Global Registration of 3D Sampled Surfaces Using a Multi-z-Bufter Technique," Proc. 3D1M, 1997

3. Bentley. J.L. Multidimensional binary search trees used for associative searching. Comm. of the ACM. 18(9). 509-517, 1975

4. Besl, P.J. and McKay, N.D. 1992. A method for registration of 3D shapes. IEEE Transactions on Pattern Analysis and Machine Intelligence, 14 (2), pp. 239-256.

5. Besl, P. J., and McKay, N.D. A method for registration of 3D shapes. IEEE Transactions on Pattern Analysis and Machine Intelligence, 14 (2), pp. 239-256, 1992

6. Bohm, .1., Becker S„ Automatic Marker-Free Registration of Terrestrial Laser Scans using Reflectance Features. In: Proceedings of 8th Conference on Optical 3D Mcasurment Techniques, Zurich, Switzerland, July 9-12, pp. 338-344, 2007

7. Boubekeur Т., Reuter P., Schlick C., Surfel Stripping, ACM Graphite, 2005

8. Boubekeur Т., Heidrich W., Granier X., Schlick C., Volume-Surface Trees, Computer Graphics Forum (Proceedings of EUROGRAPHICS), Volume 25, Number 3, page 399406. 2006

9. Brinkhoff, Т., Spatial access methods for organizing laserscanner data. IAPRS, 35(B4), pp. 98-102,2004

10. Chen, Y., and Medioni, G., Object modelling by registration of multiple range images. Image and Vision Computing, 10(3), pp. 145-155, 1992

11. Chetverikov D., Stepanov D., Krsek P., Robust Euclidean alignment of 3D point sets: the Trimmed Iterative Closest Point algorithm. Im. and Vis. Сотр. 23, 3, 299-309, 2005

12. Dold, C. and Brenner, C., Automatic Matching of Terrestrial Scan Data as a Basis for the Generation of Detailed 3D City Models, 2004

13. Dold, C., Extended Gaussian images for the registration of terrestrial scan data, ISPRS WG III/3, III/4, V/3 Workshop "Laser scanning 2005". Enschede, the Netherlands, September 12-14, 2005

14. Godin, G., Rioux, M., and Baribeau, R., "Three-dimensional Registration Using Range and Intensity Information," Proc. SPIE: Videometries III, Vol. 2350, 1994

15. Godin, G., Laurendeau, D. and Bergevin. R., A method for the registration of attributed range images. 3DIM. Quebec, pp. 179-186, 2001

16. Eggert, D.W., Fitzgibbon. A.W. and Fisher, R.B. Simultaneous registration of multiple range views for use in reverse engineering of CAD models. CVIU, 69(3). 253-272, 1998

17. Feldmar J., N.J. Ayache, Rigid, affine and locally affine registration of free-form surfaces. International Journal of Computer Vision, No. 2, May, pp. 99-119, 1996

18. Fischler, Bolles, "RANdom SAmpling Consensus: a paradigm fro model fitting with application to image analysis and automated cartography" Comniun.Assoc.Comp. Mack. :381-95, 1981

19. Greenspan, M., and Godin, G., A nearest neighbor method for efficient ICP. 3DIM, Quebec, pp. 161-168,2001

20. Gobbetti E., Marton F. Layered point clouds, in: Proc. Eurographics Symposium on Point Based Graphics, pp. 113-120,227, 2004

21. Hansen, W., Registration of Agia Sanmarina Lidar Data Using Surface Elements. ISPRS Workshop on Laser Scanning 2007 and SilviLaser 2007, Espoo, September 12-14, 2007

22. Isenburg M., Gumhold S., Out-of-Core Compression for Gigantic Polygon Meshes. Proceedings of SIGGRAPH'03, pages 935-942, July, 2003

23. Jackins C. L., Tanimoto S. L., Quad-trees, oct-Uees, and k-trees. A generalized approach to recursive decomposition of Euclidean space, EEE Trans. Pattern Anal. Machine Intell, vol. PAMI-5, pp. 533-539, 1983

24. Johnson, A. and Hebert, M., '"Surface Registration by Matching Oriented Points," Proc. 3DIM, 1997

25. Johnson 97 II. Johnson A.E. S.B. Kang, '"Registration and integration of textured 3-D data", Proc. Int. Conf. on Recent Advances in 3-D Digital Imaging and Modeling, Ottawa, Canada, May 12-15. pp. 234-241, 1997

26. Jokinen, O., and Ilaggren, H., Statistical analysis of two 3-D registration and modeling strategies. ISPRS Journal of Photogrammetry & Remote Sensing, 53(6), 320-341, 1998

27. Horn, B., "Closed-Form Solution of Absolute Orientation Using Unit Quaternions," JOSA A, Vol. 4, No. 4, 1987

28. Horn B., Extended gaussian images, Proc. IEEE, A.I. Memo No. 740. Vol. 72(12), pp. 1671-1686, 1984

29. Horn, B., Hilden, H., and Negahdaripour, S., "Closed-Form Solution of Absolute Orientation Using Orthonormal Matrices," JOSA A, Vol. 5, No. 7, 1988

30. Kang Z., Zlatanova S., Gorte B., Automatic Registration of Terrestrial Scanning Data Based on Registered Imagery, Proceedings FIG Working Week, May, Hong Kong, pp. 11,2007

31. Kwang-Ho Bae, D. D. Lichti. Automated Registration Of Unorganised Point Clouds From Terrestrial Laser Scanners, 2004

32. Lowe D.G. Distinctive image features from scale-invariant key points, International journal of computer vision, 60(2):9l-l 10, 2004

33. Masuda, T., Sakaue, K., and Yokoya, N. "Registration and Integration of Multiple Range Images for 3-D Model Construction," Proc. CVPR. 1996.

34. Neugebauer. P.J., Reconstruction of real-world objects via simultaneous registration and robust combination of multiple range images. Int. J. of Shape Modeling, 3(1-2), 71-90, 1997

35. Nishino K.,. Ikeuchi. K., "Robust simultaneous registration of multiple range images," The 5th Asian Conf. on Computer Vision (ACCV2002), 23-25, 2002

36. Pajdla T. and L. Van Gool, Matching of 3-D Curves using Semi-differential Invariants. In 5th International Conference on Computer Vision, pages 390-395. 1995

37. Park, S.Y., Subbarao, M., A fast point-to-tangent plane technique for multi-view registration. IEEE International Conference on 3D Digital Imaging and Modeling, Banff, October 6-10, pp. 276-283, 2003

38. Pulli fC, "Multiview registration for large data sets." Proc. Of 2nd Intn. Conf. on 3D Digital Imaging and Modeling, 1999

39. Rabbania T„ vail den Heuvelb F. A., Vosselman G., Segmentation of point clouds using smoothness constraint, IAPRS Volume XXXVI. Part 5, 2006

40. Ripperda, N., Brenner, C., "Marker-Free Registration of Terrestrial Laser Scans Using the Normal Distribution Transform", Proceedings of the ISPRS Working Group V/4 Workshop VOLUME XXXVI, PART 5/W17, 2005

41. Rusinkiewicz, S., and Levoy. M., Efficient variants of the ICP algorithm. IEEE International Conference on 3D Digital Imaging and Modeling, Quebec, May 28 June l,pp. 145-152,2001

42. Sankaranarayanan, .1., Samet, H., Varshney, A., A fast all nearest neighbor algorithm for applications involving large point-clouds. Computers and Graphics, 31,2 (Apr. 2007), 157-174, 2007

43. Sharp, G. C. Lee. S.W. and Wehe, D. K., ICP registration using invariant features. IEEE Transactions on Pattern Recognition and Machine Intelligence 24(1), pp. 90-102, 2002

44. Simon, D., Fast and Accurate Shape-Based Registration. PhD thesis, Robotics Institute, Carnegie Mellon University, 1996

45. The Stanford 3D Scanning Repository, электронный ресурс., http://graphics.stanford.edu/data/3Dscanrep

46. Turk. G., and Levoy. M., Zippered polygon meshes from range images. In: A. Glassner (ed.), Proceedings of SIGGRAPH'94. Florida. July 24-29, pp. 311-318, 1994

47. Umeyama S., "Least-Squares Estimation of Transformation Parameters Between Two Point Patterns." IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 13, no. 4, pp. 376-380, Apr. 1991

48. Vanden Wyngaerd, J., Van Gool, L. Koch, R., and Proesmans, M., Invariant-based registration of surface patches. IEEE International Conference on Computer Vision, Kerkyra, September 20-27, pp. 301-306, 1999

49. Weik, S. "Registration of 3-D Partial Surface Models Using Luminance and Depth Information," Proc. 3DIM, 1997.

50. Walker, M., Shao, L., and Volz, R., "Estimating 3-D Location Parameters Using Dual Number Quaternions," CVGIP: Image Understanding, Vol. 54. No. 3, 1991

51. Zhang, Z., Iterative point matching for registration of free-form curves and surfaces. International Journal of Computer Vision, 13 (2). pp. 119-152, 1994

52. Чнбуннчев А.Г., Велижев А.Б., Автоматическое определение взаимной ориентации трехмерных моделей объектов, полученных по результатам лазерного сканирования, «Геодезия и аэрофотосъемка», Москва, 2007, № 1, стр. 127-134.

53. Чибуничев А.Г., Велижев А.Б., Автоматическое сопоставление облаков точек, полученных в результате наземного лазерного сканирования, с использованием ориентационных гистограмм, «Геодезия и аэрофотосъемка», 2008, Москва, №3, стр. 112-119

54. Велижев А.Б., Визуализация результатов лазерного сканирования, "Инженерные изыскания", 2008, №2, стр. 94-95

55. Комиссаров А.В., 2007. Методика исследования метрических характеристик сканеров, автореферат диссертации на соискание ученой степени кандидата технических наук, Новосибирск

56. Жигалов К.Ю., Векторизация и конвертация данных лазерной локации в ГИС-технологиях, автореферат диссертации на соискание ученой степени кандидата технических наук, Москва, 2007

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