Рисунок 1 – Принцип работы лазерного сканера

         Для определения расстояний существуют два метода. Первый метод носит название Time-of-Flight (TOF). Он основан на измерении времени действия лазерного импульса. Этот импульс производится сенсором, отражается объектом и принимается чувствительным элементом.
         В данном случае расстояние находится по формуле:

(1)

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

(2)

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

(3)

Актуальность и цель

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

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

         Существуют различные алгоритмы определения плоскостей. В частности Andreas Rietdorf в своей работе «Automatisierte Auswertung und Kalibrierung von scannenden Messsystemen mit tachzmetrischem Messprinzip» (Munhen 2005) [1] в качестве критерия для решения, лежат ли точки на плоскости, выполнял расчет определителя. Исследуются соответственно два смежных треугольника, которые достаточно точно определяют плоскость.
         Согласно его работы, к каждой грани треугольника должны искаться две следующих грани, которые имеют общую точку с первой. Таким образом, существуют 4 точки, которые определяют параллелепипед. Если смешенное произведение трех векторов, образованных четырьмя точками, равно нулю, то эти четыре точки лежат в одной плоскости. Таким образом, принадлежность какой-либо точки плоскости определяется из равенства нулю определителя образованного тремя векторами:

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

         Рассмотрим преобразование координат точек составляющих матрицу Х. Геометрически это можно изобразить следующим образом: рис. 2.

Рисунок 2 – Преобразование координат точек плоскости, здесь: система координат – система, в которой находится плоскость; система координат x,y,z – это система координат, в которой точки лежат в плоскости ху.

         Вычтем из каждой координаты матрицы Х средние значения ( ) по каждой из координат. Получим матрицу А, все точки которой будут рассеяны относительно центра тяжести:

(4)

         Умножим матрицу А на АТ получим симметричную матрицу N. Это необходимо для нахождения собственных векторов (U) матрицы А.
         Поясним необходимость определения собственных векторов. Задачу преобразования координат можно свести к преобразованию базиса. Для этого каждую точку матрицы А будем рассматривать как вектор. Тогда согласно определению совокупность векторов пространства называется оператором. В результате преобразования базиса будут получены две различные матрицы соответствующие одному оператору, то есть они будут подобными. Подобные матрицы связаны между собой соотношением:

(5)

где A’ – преобразованная матрица координат точек; А – исходная матрица; U – матрица преобразования координат при переходе к новому базису. Если собственные числа матрицы А попарно различны, то собственные вектора являются ортогональными и линейно независимыми, а, следовательно, их можно использовать в качестве базиса. Тогда формула (6) имеет следующий вид:

(6)

Планируемые результаты

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

Список источников.

1. Andreas Rietdorf «Automatisierte Auswertung und Kalibrierung von scannenden Messsystemen mit tachzmetrischem Messprinzip» - Munhen 2005
2. Н.В. Ефимов «Краткий курс аналитической геометрии» - М., «Наука», 1969
3. Д.В.Беклемишев «Курс аналитической геометрии и линейной алгебры» - М., «Физматлит», 2005
4. Д.К.Фадеев, В.Н.Фадеева «Вычилительные методы линейной алгебры» - М., «Наука», 1963