Methods of the normal vectors construction in tasks of objects identification

Mezhenin Aleksandr Vladimirovich PhD in Technical Science Assosiate Professor of the Department of Engineering and Computer Graphics of the St. Petersburg State University of Information Technologies, Mechanics and Optics 197101, Russia, g. Saint Petersburg, ul. Kronverkskii Prospekt, 49 mejenin@mail.ru Other publications by this author

Izvozchikova Vera Vasil'evna PhD in Technical Science Associate Professor of the Department of Information Systems and Technology at the Orenburg State University 460018, Russia, Orenburg, Sharlukskoe shosse, d. 5 mejenin@mail.ru

Для семантического понимания окружающей среды в системах компьютерного зрения мобильных роботов 3D распознавание объектов играет все более важную роль ^[1,2]. Разрабатываемые в этой области алгоритмы используют сегментацию геометрии, которая опирается в первую очередь на построение векторов нормалей к поверхности. Существуют различные подходы к их вычислению на основе данных, представляющих собой облако точек. Однако, часто неясно, какие методы являются предпочтительными.

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

При генерации полигональной сетки необходимо учитывать ошибки измерений. Чаще всего, исходными данными для систем компьютерного зрения является некоторое облако точек ^[3]. Эти данные могут быть получены с помощью лазерного дальномера или других датчиков, например стереокамер. Точность оценки положения этих точек зависит от точности аппаратуры и наличия различных помех, возникающих в процессе измерения. Кроме этого, возникают ошибки работы алгоритмов реконструкции, решающих задачи восстановления топологии относительно топологии исходной поверхности.

Использование метода вычисления среднеквадратичной ошибки (Root Mean Square Error, RMSE) для оценки точности реконструкции трехмерных моделей не дает достоверных оценок подобия 3D геометрии. Определение подобия, опирающееся на трехмерное (полигональное) представление объектов подразумевает нахождение количественной оценки понятия «подобие формы» ^[1]. Для этого предлагается использовать подходы из общей топологии - размерность Хаусдорфа.

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

Топологическое пространство X называется Хаусдорфовым, если любые две различных точки x, y из X обладают непересекающимися окрестностями U(x), V(x).

Пусть даны два набора точек A={a₁, a₂,..., a_m} и B={b₁,b₂,...,b_n}. Тогда Хаусдорфово расстояние определяется как:

H=(A,B)=max(h(A,B), h(B,A)), (1)

где h(A,B)=`max_(ainA)` `min_(binB)` ||a-b|| и ||`*` || Евклидова норма. Функция h(A,B) называется направленным Хаусдофовым расстоянием между A и B, потому что эта функция не симметрична.Таким образом, появляется возможность, сравнивать две полигональные поверхности S₁ и S₂. Точность оценки определяется точностью интегрирования по поверхности и может быть задана как некая доля от диагонали габаритного прямоугольника модели. Для получения более точных результатов предлагается использовать метод Монте-Карло для генерации k выборок, пропорциональных площади каждой грани.

Важнейший этап в вычислении рассмотренной метрики – построение векторов нормали к поверхности ^[4-6]. Многие из существующих методов расчета вектора нормали относятся к классу оптимизационных задач, которую можно описать следующим выражением:

`min_(n_i)J(p_i,Q_i,n_i)` (2)

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

Рис. 1. Различные подходы к построению векторов нормалей

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

Для решения задачи нахождения точек пересечения векторов нормалей, построенных от одной поверхности к другой, воспользуемся следующими предположениями. Пусть ABC произвольный треугольник, a, b, c длины сторон, лежащие против вершин A, B и C соответственно, M – точка пересечения биссектрис. Тогда для любой точки O верно равенство:

`bar(OM)=(a*bar(OA)+b*bar(OB)+c*bar_(OC))/(a+b+c)` (3)

Следствие из этой теоремы, если O – начало координат, тогда:

`x_M=(a*x_A+b*x_B+c*x_C)/(a+b+c)`

`y_M=(a*y_A+b*y_B+c*y_C)/(a+b+c)`

`z_M=(a*z_A+b*z_B+c*z_C)/(a+b+c)`

(4)

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

a=(a_x,a_y,a_z), b=(b_x,b_y,b_z) (5)

а система координат правая, то их векторное произведение имеет вид:

[a,b]=(a_xb_z-a_zb_y,a_zb_x-a_xb_z,a_xb_y-a_yb_x) (6)

Для оценки рассматриваемых методов и наглядной визуализации построения векторов нормалей к поверхности разработаны m-функции в среде MATLAB Image Processing Toolbox (IPT) (рис.2).

Рис. 2. Построение векторов нормалей к различным поверхностям

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