по
Меню журнала
> Архив номеров > Рубрики > О журнале > Авторы > О журнале > Требования к статьям > Редакция и редакционный совет > Порядок рецензирования статей > Рецензирование за 24 часа – как это возможно? > Политика издания > Ретракция статей > Этические принципы > Политика открытого доступа > Оплата за публикации в открытом доступе > Публикация за 72 часа: что это? > Политика авторских прав и лицензий > Политика цифрового хранения публикации > Политика идентификации статей > Политика проверки на плагиат
Журналы индексируются
Реквизиты журнала

Публикация за 72 часа - теперь это реальность!
При необходимости издательство предоставляет авторам услугу сверхсрочной полноценной публикации. Уже через 72 часа статья появляется в числе опубликованных на сайте издательства с DOI и номерами страниц.
По первому требованию предоставляем все подтверждающие публикацию документы!
ГЛАВНАЯ > Вернуться к содержанию
Кибернетика и программирование
Правильная ссылка на статью:

Методы построения векторов нормалей в задачах идентификации объектов
Меженин Александр Владимирович

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

доцент, кафедра Факультет программной инженерии и компьютерной техники, Санкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики

197101, Россия, г. Санкт-Петербург, ул. Кронверкский Проспект, 49

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
Извозчикова Вера Васильевна

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

доцент , кафедра информационных систем и технологий, Оренбургский государственный университет

460018, Оренбург, Шарлыкское шоссе, 5

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

Аннотация.

В статье рассматриваются методы построения вектров нормалей в задачах анализа подобия полигональных моделей произвольного топологического типа. Данные исследования могут быть использованы для оценки качества упрощения полигональной сети и оценки точности реконструкции трехмерных моделей в задачах фотограмметрии. Для определения подобия трехмерных (полигональных) объектов, предлагается использовать подходы из общей топологии – размерность Хаусдорфа. Говорится,ч то важнейший этап в вычислении рассмотренной метрики – построение векторов нормали к поверхности. Для оценки рассматриваемых методов и наглядной визуализации построения векторов нормалей к поверхности разработаны m-функции в среде MATLAB Image Processing Toolbox (IPT). Проведенные исследования подтверждают правильность выбранного направления для разработки методов анализа подобия полигональных моделей, произвольного топологического типа. Предлагаемый подход может быть применен в задачах оценки качества алгоритмов распознавания и реконструкции 3D моделей и в задачах оценки качества упрощения полигональных моделей.

Ключевые слова: проектирование, вектра нормалей, идентификация объектов, алгоритм, датчик, полигональная модель, топологическое пространство, полигональная сетка, компьютерная графика, вычисление

DOI:

10.7256/2306-4196.2013.4.9358

Дата направления в редакцию:

28-08-2013


Дата рецензирования:

29-08-2013


Дата публикации:

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

Введение

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

Библиография
1.
Меженин, А. В. Анализ подобия полигональных моделей в графических системах /А.В.Меженин, А.Ю. Кротова, А.Л. Зеленковский // Информатика и вычислительная техника: сборник научных трудов / под ред. Войта. – Ульяновск: УлГТУ, 2011.-656 с. С. 397-400.
2.
Меженин, А. В. Исследование методов построения векторов нормалей / А.М. Александрова, Е.Е. Костина, А.В. Меженин // Труды XIX Всероссийской научно-методической конференции «Телематика'2012». – Санкт-Петербург, 2012. т 2. с. 299-302.
3.
Меженин, А. В. Тестирование методов стереозрения/ А.А. Корнилов, А.В.Меженин // Труды XIX Всероссийской научно-методической конференции «Телематика'2012» . – Санкт-Петербург, 2012. Т2. С. 291-293.
4.
Klasing, К. 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.
Харитонов А.В. Обзор биометрических методов идентификации личности // NB: Кибернетика и программирование.-2013.-2.-C. 12-19. URL: http://www.e-notabene.ru/kp/article_8300.html
8.
Шункевич Д.В. Многоагентный подход к построению машин обработки знаний на основе семантических сетей // NB: Кибернетика и программирование. - 2013. - 1. - C. 37 - 45. URL: http://www.e-notabene.ru/kp/article_8299.html
9.
Кучинская-Паровая И.И. Компонентное проектирование нейронных сетей для обработки баз знаний // NB: Кибернетика и программирование. - 2013. - 1. - C. 9 - 15. URL: http://www.e-notabene.ru/kp/article_8308.html
10.
Бондаренко И.Б., Коробейников А.Г., Прохожев Н.Н., Михайличенко О.В. Принятие технических решений с помощью многоагентных систем // NB: Кибернетика и программирование. - 2013. - 1. - C. 16 - 20. URL: http://www.e-notabene.ru/kp/article_8305.html
11.
Малашкевич И.А., Малашкевич В.Б. Применение fortran-библиотек линейной алгебры в среде delphi // NB: Кибернетика и программирование. - 2013. - 1. - C. 1 - 8. URL: http://www.e-notabene.ru/kp/article_8314.html
References (transliterated)
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
Ссылка на эту статью

Просто выделите и скопируйте ссылку на эту статью в буфер обмена. Вы можете также попробовать найти похожие статьи


Другие сайты издательства:
Официальный сайт издательства NotaBene / Aurora Group s.r.o.
Сайт исторического журнала "History Illustrated"