Статья 'Методы построения векторов нормалей в задачах идентификации объектов' - журнал 'Кибернетика и программирование' - NotaBene.ru
по
Journal Menu
> Issues > Rubrics > About journal > Authors > About the Journal > Requirements for publication > Council of Editors > Peer-review process > Policy of publication. Aims & Scope. > Article retraction > Ethics > Online First Pre-Publication > Copyright & Licensing Policy > Digital archiving policy > Open Access Policy > Open access publishing costs > Article Identification Policy > Plagiarism check policy
Journals in science databases
About the Journal

MAIN PAGE > Back to contents
Cybernetics and programming
Reference:

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
Другие публикации этого автора
 

 
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

DOI:

10.7256/2306-4196.2013.4.9358

Review date:

18-07-2013


Publish date:

1-8-2013


Abstract: The article deals with methods of calculating of normal vectors in tasks of similarity analysis of the polygon models of arbitrary topological type. Such studies can be used in evaluation of the quality of simplification of a polygonal net and the accuracy of the reconstruction of the three-dimensional models in tasks of photogrammetry. To determine the similarity of the three-dimensional (polygonal) objects author proposes to use the approaches of the general topology, the Hausdorff dimension. The author points out, that the most important step in the calculation of the discussed metric if in building the normal vectors to the surface. For the evaluation of the given methods and clear visualization of the normal vectors, the author developed m-functions in the MATLAB Image Processing Toolbox (IPT) environment.  This study confirms the correctness of the chosen direction of the for the analysis of the similarity of polygonal models of arbitrary topological type. The proposed approach can be applied to the tasks of evaluating the quality of algorithms for recognition and reconstruction of 3D models and to the problem of evaluation of the quality of simplified polygonal models.


Keywords: design, normal vector, identification of objects, algorithm, sensor, polygon model, topological space, polygon mesh, computer graphics, calculation
This article written in Russian. You can find full text of article in Russian here .
Введение

Для семантического понимания окружающей среды в системах компьютерного зрения мобильных роботов 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={a1, a2,..., am} и B={b1,b2,...,bn} . Тогда Хаусдорфово расстояние определяется как:

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, потому что эта функция не симметрична.Таким образом, появляется возможность, сравнивать две полигональные поверхности S1 и S2 . Точность оценки определяется точностью интегрирования по поверхности и может быть задана как некая доля от диагонали габаритного прямоугольника модели. Для получения более точных результатов предлагается использовать метод Монте-Карло для генерации k выборок, пропорциональных площади каждой грани.

Построение векторов нормалей

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

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

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

1a

a)

1b

b)

1c

c)

Рис. 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=(ax,ay,az), b=(bx,by,bz) (5)

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

[a,b]=(axbz-azby,azbx-axbz,axby-aybx) (6)

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

2122

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

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

function [ L ] = funcL( X1,Y1,Z1, X2,Y2,Z2 )

L=sqrt(power(X2-X1,2)+power(Y2-Y1,2)+power(Z2-Z1,2));

end

function [ Z ] = func1( X, Y )% функция Z=f(X,Y)

Z=exp(-X.^2-Y.^2).*X.*Y;

end

function [ Z ] = func2( X, Y )% функция Z=f(X,Y)

Z=exp(-X.^2-Y.^2).*X.*Y.^3*0.4-Y.^2.*(X/4+1)*0.06+0.5;

end

Листинг 1. Фрагмент программного кода

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

3

Рис.3. Визуальное представление

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



References
1.
Mezhenin, A. V. Analiz podobiya poligonal'nykh modelei v graficheskikh sistemakh /A.V.Mezhenin, A.Yu. Krotova, A.L. Zelenkovskii // Informatika i vychislitel'naya tekhnika: sbornik nauchnykh trudov / pod red. Voita. – Ul'yanovsk: UlGTU, 2011.-656 s. S. 397-400.
2.
Mezhenin, A. V. Issledovanie metodov postroeniya vektorov normalei / A.M. Aleksandrova, E.E. Kostina, A.V. Mezhenin // Trudy XIX Vserossiiskoi nauchno-metodicheskoi konferentsii «Telematika'2012». – Sankt-Peterburg, 2012. t 2. s. 299-302.
3.
Mezhenin, A. V. Testirovanie metodov stereozreniya/ A.A. Kornilov, A.V.Mezhenin // Trudy XIX Vserossiiskoi nauchno-metodicheskoi konferentsii «Telematika'2012» . – Sankt-Peterburg, 2012. T2. S. 291-293.
4.
Klasing, K. A clustering method for online segmentation of 3d laser data. /K. Klasing, D. Wollherr. M. Buss. in Proc. ICRA, 2008.
5.
Hoffman, R. Segmentation and classification of range images /R. Hoffman, A. K. Jain. IEEE Trans. Pattern Anal. Mach. Intell., vol. 9, no. 5, pp. 608–620, 1987.
6.
Huang, J. Automatic data segmentation for geometric feature extraction from unorganized 3-d coordinate points /|J. Huang, C.-H. Menq. IEEE Trans. Robot. Automat., vol. 17, pp. 268–279, 2001.
7.
Kharitonov A.V. Obzor biometricheskikh metodov identifikatsii lichnosti // NB: Kibernetika i programmirovanie.-2013.-2.-C. 12-19. URL: http://www.e-notabene.ru/kp/article_8300.html
8.
Shunkevich D.V. Mnogoagentnyi podkhod k postroeniyu mashin obrabotki znanii na osnove semanticheskikh setei // NB: Kibernetika i programmirovanie. - 2013. - 1. - C. 37 - 45. URL: http://www.e-notabene.ru/kp/article_8299.html
9.
Kuchinskaya-Parovaya I.I. Komponentnoe proektirovanie neironnykh setei dlya obrabotki baz znanii // NB: Kibernetika i programmirovanie. - 2013. - 1. - C. 9 - 15. URL: http://www.e-notabene.ru/kp/article_8308.html
10.
Bondarenko I.B., Korobeinikov A.G., Prokhozhev N.N., Mikhailichenko O.V. Prinyatie tekhnicheskikh reshenii s pomoshch'yu mnogoagentnykh sistem // NB: Kibernetika i programmirovanie. - 2013. - 1. - C. 16 - 20. URL: http://www.e-notabene.ru/kp/article_8305.html
11.
Malashkevich I.A., Malashkevich V.B. Primenenie fortran-bibliotek lineinoi algebry v srede delphi // NB: Kibernetika i programmirovanie. - 2013. - 1. - C. 1 - 8. URL: http://www.e-notabene.ru/kp/article_8314.html
Link to this article

You can simply select and copy link from below text field.


Other our sites:
Official Website of NOTA BENE / Aurora Group s.r.o.
"History Illustrated" Website