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

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

Методы обнаружения и пространственной локализации групп точечных объектов
Ипатов Юрий Аркадьевич

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

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

424000, Россия, Республика Марий Эл, г. Йошкар-Ола, пл. Ленина, 3

Ipatov Yurii Arkad'evich

PhD in Technical Science

Associate Professor of the Department of Informatics at the Volga State University of Technology

424000, Russia, Mari El, Yoshkar-Ola, pl. Lenina, d. 3

philsilver@mail.ru
Другие публикации этого автора
 

 
Кревецкий Александр Владимирович

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

профессор, кафедра информатики, Поволжский государственный технологический университет

424000, Россия, республика Марий Эл, г. Йошкар-Ола, пл. Ленина, 3

Krevetsky Aleksandr Vladimirovich

PhD in Technical Science

Professor, Department of Computer Science, Volga State University of Technology

424000, Rossiya, respublika Mariy El, g. Yoshkar-Ola, pl. Lenina, 3

krevetskyav@marstu.net
Другие публикации этого автора
 

 

Аннотация.

Современные системы компьютерного зрения используют интеллектуальные алгоритмы, которые решают широкий класс задач от простого распознавания текста до сложных систем пространственного ориентирования. Одна из основных проблем, с которой сталкиваются разработчики таких систем – это выбор уникальных признаков, которые остаются инвариантными к различного рода преобразованиям. В статье приведен сравнительный анализ методов обнаружения и пространственной локализации групп точечных объектов. Рассмотренные методы сравниваются по производительности и эффективности при заданных размерностях. На сегодняшний день не существует универсальных подходов к определению таких характеристик, а их выбор зависит от контекста решаемой задачи и регистрируемых условий наблюдения. В качестве доминирующих признаков могут быть выбраны различного рода дескрипторы, такие как точки, линии, углы и геометрические примитивы. В работе выли исследованы алгоритмы обнаружения групп точечных объектов на основе минимального оставного дерева (MST) и с использованием модели ассоциированного сплошного образа (ACI).

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

УДК:

004.93

DOI:

10.7256/2306-4196.2014.6.13642

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

11-11-2014


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

12-11-2014


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

16-11-2014


Работа выполнена в рамках проекта РФФИ № 13-01-00427.

Abstract.

Modern systems of computer vision use intelligent algorithms that solve a wide class of problems from simple text recognition to complex systems of spatial orientation. One of the main problems for developers of such systems is in selection of unique attributes which remain invariant to various kinds of transformations. The article presents a comparative analysis of methods of detection and spatial localization of groups of point objects. The reviewed methods are compared by the performance and efficiency at specified dimensions. As of today there are no universal approaches to determine of such attributes, and its’ selection depends on the context of the problem being solved and on the registered conditions of observation. Various kinds of descriptors such as points, lines, angles and geometric primitives can be selected as dominating attributes. The authors study  algorithms for detection of groups of point objects based on the minimum spanning tree (MST) and using a model of associated continuous image (ACI).

Keywords:

computer vision, object recognition, speed of the algorithm, modeling of point objects, associated continuous image, minimum spanning tree, group of point objects, point objects, intelligent algorithms, localization of groups

Введение

Рассмотрим сущетсвующие методы и подходы обнаружения и пространственной локализации групп точечных объектов, которые в качестве описательных признаков используют особые точки [1,2]. Существует множество алгоритмов для локализации такого рода точек. Так можно выделить класс методов, где особые точки поддвергаюся минимальным искажениям с течением времени, например, между соседними кадрами видеопоследовательнсти. Одним из наиболее распространенных типов особых точек являются углы на изображении, т.к. в отличие от ребер углы на паре изображений можно однозначно сопоставить. Детектор Моравеца [3] является самым простым детектором углов. Предлагается измерять изменение интенсивности пикселя I(x,y) посредством смещения небольшого квадратного окна с центром в (x,y) на один пиксель в каждом из восьми принципиальных направлений. Следует отметить, что данный детектор не является инвариантным относительно преобразования поворота и имеет большое число ложных срабатываний на ребрах вследствие шума. Детектор Харриса [4] строится на основании детектора Моравеца и является его улучшением, т.к. для него характерна анизотропия по всем направлениям. Харрис и Стефан вводят в рассмотрение производные по некоторым принципиальным направлениям, раскладывают функцию интенсивности в ряд Тейлора. Однако ему присущи некоторые недостатки, среди которых большая вычислительная трудоемкость (по сравнению с детектором Моравеца), чувствительность к шуму и зависимость результатов детектирования от масштаба изображения. Также здесь можно отметить алгоритмы нахождения особых точек, основанные на преобразованиях вейвлет [5], риджет [6], Хафа [7] и др.

Следующий класс обнаружителей особых точек, которые являются стабильными при смене освещения и небольших движениях объекта. Детектор MSER (Maximally Stable Extremal Regions) [8] решает проблему инвариантности особых точек при масштабировании изображения. Детектор выделяет множество различных регионов с экстремальными свойствами функции интенсивности внутри региона и на его внешней границе. Преимущества, которыми обладает детектор – это инвариантность к аффинным преобразованиям интенсивностей, устойчивость, одновременное детектирование областей разного масштаба и вычислительная эффективность. Описанные ранее детекторы определяют особые точки на изображении, в частности, углы, применяя некоторую модель или алгоритм напрямую обращаясь к пикселям исходного изображения. Альтернативный подход состоит в том, чтобы использовать алгоритмы машинного обучения для тренировки классификатора точек на некотором множестве изображений. FAST-детектор (Features from Accelerated Test) [9] относится к эвристическим алгоритмам и строит деревья решений для классификации пикселей. Он хорошо зарекомандовал себя при слежении за объектами в реальном времени.

В настоящее время существует ряд методик описания изображений по особым точкам, которые обладают высокой стабильностью и хорошими характеристиками работы, инвариантыми к масшабу и повороту: Алгоритм SIFT (Scale Invariant Feature Transform) [10]. Один из наиболее часто используемых алгоритмов описания особых точек. Точки, полученные с помощью алгоритма, устойчивы к изменениям освещения, шумам и изменениям позиции наблюдателя. Характеризуется приемлемой вычислительной эффективностью. Алгоритм SURF (Speeded Up Robust Features) [11]. Методика основана на поиске особых точек, при этом для каждой точки считается градиент максимального изменения яркости и коэффициент масштабирования по матрице Гессе. Метод RIFF (Rotation Invariant Fast Features) [12]. В основу метода положено радиальное и тангенциальное разложение гистограмм градиента и последующая обработка по кольцам. Дескриптор также инвариантен к изменению освещенности.

Постановка задачи

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

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

Алгоритм обнаружения групповых точечных объектов

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

`x^2/a^2 + y^2/b^2 + z^2/c^2 = 1,` (1)

где полуоси элипсоида.

На рис.1, а предсталена моделируемая сцена, которая состоит из смеси ТО и ГТО.

01

Рис. 1. Моделирование ГТО и ТО

Важнейшим информативным признаком, отличающим область расположения ГТО от фона из ложных отметок, служит более высокая плотность точечных объектов. Для представления и дальнейшей обработки предполагается решить задачу построения минимального остова [13,14] на множестве точек (рис.1, а ).

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

Пусть имеется связный неориентированный граф G = (V, E), в котором V – множество ТО, E – множество ребер. Для каждого ребра графа (u,v) задан неотрицательный вес w(u,v), измеряемый эвлидовой метрикой. Задача состоит в нахождении подмножества T Ì E, связывающего все вершины, для которого суммарный вес (2)

`omega(T) = sum_( (u,v)in T) omega(u,v)` (2)

минимален. Такое подмножество T можно считать деревом. Минимальным покрывающим деревом называют покрывающее дерево, имеющее минимально возможный вес [15].

Наиболее известными алгоритмами построения минимального остовного дерева являются алгоритмы Крускала, Прима и Борувки [16]. Лучшее время работы алгоритма Крускала составляет O(E * logE ), а лучшее время работы алгоритма Прима O(E * V * logV ) и для алгоритма Борувки O(E * logV ), где |V| - количество вершин графа G , |E| - количество ребер графа G.

02

Рис. 2. ГТО после удаления длиных ребер пороговым значением.

Для реализации и построения минимального оставного дерева был взят алгоритм Крускала. На рис. 2 предавлена сцена из ГТО после пороговой обработки минимального оставного дерева, где хорошо видно, как пространственные ГТО выделяются в изолированные оставы.

Алгоритм обработки ассоциативнного сплошного образа

В модель наблюдаемого изображения – результат обнаружения точечных объектов, введем дополнительный математический объект – ассоциированный сплошной образ (АСО). АСО представляет собой новый объект, полученный посредствам увеличения радиуса ТО до некоторого значения, при котором ГТО начинает рассматирваться, как единый объект. На рис. 3 представлен процесс моделирования АСО из ТО с ростом внутреннего радиуса ТО.

Для построения объекта АСО используется алгорим заполнения области с затравкой [17]. Сложность такого алгоритма сотавляет O(N), где N – размерность области заливки.

03

Рис. 3. АСО с разным внутренни радиусом для ТО.

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

04

Рис. 4. Объекты АСО после пороговой обработки.

Для исследования зависимости количества объекто АСО от внутренненго радиуса ТО построим график (рис.5). Анализ графика показывает, что число объектов будет уменьшаться по обрано пропорциональной завизависимости. Дальнейшее распознавание АСО можно реализовать по информативным признакам контуров, площади и другим характеристикам.

05

Рис. 5. Зависомость числа объектов АСО от радиуса ТО.

Выводы

Таким образом, в работе выли исседованы алгоритмы обнаружения ГТО на основе минимального оставного дерева (MST) и с использованием модели ассоциированного сплошного образа (ACI).

06

Рис. 6. Временные характеристики для алгоритмов MST и ACI.

Из графика рис.6 видно, что алгоритм ACI имеет линейную сложность, а алгоритм MST экспоненциальную. При этом до некоторой размерности скорость работы алгоритмов будут примерно сопоставимы. Созданные алгоритмы подверждаются теоретическими и практическими рассчетами [18-20].

Библиография
1.
Szeliski R. Computer Vision: Algorithms and Applications. Springer, 2011 – 812 p.
2.
Вудс Р. Цифровая обработка изображений. Пер. с англ. под ред. П.А. Чочиа. / Р. Гонсалес, Р. Вудс-М.: Техносфера, 2005.-1072 с.
3.
Moravec H. Rover visual obstacle avoidance // Proc. Intl. Joint Conference on Artificial Intelligence. – 1981. – P. 785–790.
4.
Harris C. G., Stephens M. J. Combined corner and edge detector // Proc. Fourth Alvey Vision Conference. – 1988. – P. 147–151.
5.
Дзенчарский Н. Л. Поиск изображений с выделением особых точек на основе вейвлет-преобразования / Н. Л. Дзенчарский, М. В. Медведев, М. П. Шлеймович // Вестник Казанского государственного технологического университета. Казань: Изд-во КГТУ, 2011. – № 1 – С.131–135.
6.
D. L. Donoho, “Ridge functions and orthonormal ridgelets,” Journal of Approximation Theory, vol. 111, no. 2, pp. 143–179, 2001.
7.
Hough P. V. C. Methods, Means for Recognizing Complex Patterns / U.S., Patent 3069654, 1962.
8.
J. Matas, O. Chum, M. Urban, and T. Pajdla. "Robust wide baseline stereo from maximally stable extremal regions." Proc. of British Machine Vision Conference, pages 384-396, 2002.
9.
Rosten E., Drummond T. Machine learning for high-speed corner detection // Proc. European Conference on Computer Vision. – 2006. – V. 1. – P. 430–443.
10.
Lowe D. Object Recognition from Local Scale-Invariant Features / David G. Lowe // Proceedings of the International Conference on Computer Vision. 2. 1999, pp. 1150-1157.
11.
Herbert B. SURF: Speeded Up Robust Features / B. Herbert, Andreas Ess, Tinne Tuytelaars, Luc Van Gool // Computer Vision and Image Understanding (CVIU), Vol. 110, No. 3, 2008, pp. 346-359.
12.
Takacs G. Unified Real-Time Tracking and Recognition with Rotation-Invariant Fast Features / G. Takacs, V. Chandrasekhar, S. Tsai, D. Chen, R. Grzeszczuk, B. Girod // [Электронный ресурс] CVPR2010_RIFF.pdf
13.
Joseph. B. Kruskal. On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem. // Proc. AMS. 1956. Vol 7, No. 1. C. 48-50.
14.
Новиков Ф.А. Дискретная математика для программистов / Ф.А. Новиков-СПб.: Питер, 2002 год.-420 стр.
15.
Окулов С.М. Программирование в алгоритмах / С.М. Окулов-М.: БИНОМ. Лаборатория знаний, 2004 г.-341 стр.
16.
Кормен Т. Х. Алгоритмы: построение и анализ, 2-е изд. / Т. Х. Кормен, Ч. И. Лейзерсон, Р. Л. Ривест, К. Штайн — М.: Вильямс, 2005. — 1296 с.
17.
Роджерс Д. Алгоритмические основы машинной графики. Пер. с англ. / Д. Роджерс-М.: Мир, 1989. 512 c.
18.
Кревецкий А.В. Инвариантные к форме обнаружение и пространственная локализация групп точечных объектов в трехмерном пространстве [Текст] / А. В. Кревецкий. // Вестник Марийского государственного технического университета. Сер.: Радиотехнические и инфокоммуникационные системы.-2011.-№ 1(11).-С. 47-52.
19.
Кревецкий А.В. Специализированный графический редактор локационных изображений ландшафтных сцен с группами малоразмерных и точечных объектов [Текст] / А. В. Кревецкий, Д. В. Уржумов. // Вестник Поволжского государственного технологического университета. Сер.: Радиотехнические и инфокоммуникационные системы.-2012.-№ 2(16).-С. 24-28.
20.
Ипатов Ю.А. Архитектура системы комплексного дешифрирования изображений аэрокосмических изображений подстилающей поверхности земли в реальном масштабе времени [Текст] / Ю. А. Ипатов, А. В. Кревецкий, Д. В. Уржумов, С. Е. Чесноков. // Вестник Марийского государственного технического университета. Сер.: Радиотехнические и инфокоммуникационные системы.-2012.-№ 1(14).-С. 47-59.
References (transliterated)
1.
Szeliski R. Computer Vision: Algorithms and Applications. Springer, 2011 – 812 p.
2.
Vuds R. Tsifrovaya obrabotka izobrazhenii. Per. s angl. pod red. P.A. Chochia. / R. Gonsales, R. Vuds-M.: Tekhnosfera, 2005.-1072 s.
3.
Moravec H. Rover visual obstacle avoidance // Proc. Intl. Joint Conference on Artificial Intelligence. – 1981. – P. 785–790.
4.
Harris C. G., Stephens M. J. Combined corner and edge detector // Proc. Fourth Alvey Vision Conference. – 1988. – P. 147–151.
5.
Dzencharskii N. L. Poisk izobrazhenii s vydeleniem osobykh tochek na osnove veivlet-preobrazovaniya / N. L. Dzencharskii, M. V. Medvedev, M. P. Shleimovich // Vestnik Kazanskogo gosudarstvennogo tekhnologicheskogo universiteta. Kazan': Izd-vo KGTU, 2011. – № 1 – S.131–135.
6.
D. L. Donoho, “Ridge functions and orthonormal ridgelets,” Journal of Approximation Theory, vol. 111, no. 2, pp. 143–179, 2001.
7.
Hough P. V. C. Methods, Means for Recognizing Complex Patterns / U.S., Patent 3069654, 1962.
8.
J. Matas, O. Chum, M. Urban, and T. Pajdla. "Robust wide baseline stereo from maximally stable extremal regions." Proc. of British Machine Vision Conference, pages 384-396, 2002.
9.
Rosten E., Drummond T. Machine learning for high-speed corner detection // Proc. European Conference on Computer Vision. – 2006. – V. 1. – P. 430–443.
10.
Lowe D. Object Recognition from Local Scale-Invariant Features / David G. Lowe // Proceedings of the International Conference on Computer Vision. 2. 1999, pp. 1150-1157.
11.
Herbert B. SURF: Speeded Up Robust Features / B. Herbert, Andreas Ess, Tinne Tuytelaars, Luc Van Gool // Computer Vision and Image Understanding (CVIU), Vol. 110, No. 3, 2008, pp. 346-359.
12.
Takacs G. Unified Real-Time Tracking and Recognition with Rotation-Invariant Fast Features / G. Takacs, V. Chandrasekhar, S. Tsai, D. Chen, R. Grzeszczuk, B. Girod // [Elektronnyi resurs] CVPR2010_RIFF.pdf
13.
Joseph. B. Kruskal. On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem. // Proc. AMS. 1956. Vol 7, No. 1. C. 48-50.
14.
Novikov F.A. Diskretnaya matematika dlya programmistov / F.A. Novikov-SPb.: Piter, 2002 god.-420 str.
15.
Okulov S.M. Programmirovanie v algoritmakh / S.M. Okulov-M.: BINOM. Laboratoriya znanii, 2004 g.-341 str.
16.
Kormen T. Kh. Algoritmy: postroenie i analiz, 2-e izd. / T. Kh. Kormen, Ch. I. Leizerson, R. L. Rivest, K. Shtain — M.: Vil'yams, 2005. — 1296 s.
17.
Rodzhers D. Algoritmicheskie osnovy mashinnoi grafiki. Per. s angl. / D. Rodzhers-M.: Mir, 1989. 512 c.
18.
Krevetskii A.V. Invariantnye k forme obnaruzhenie i prostranstvennaya lokalizatsiya grupp tochechnykh ob''ektov v trekhmernom prostranstve [Tekst] / A. V. Krevetskii. // Vestnik Mariiskogo gosudarstvennogo tekhnicheskogo universiteta. Ser.: Radiotekhnicheskie i infokommunikatsionnye sistemy.-2011.-№ 1(11).-S. 47-52.
19.
Krevetskii A.V. Spetsializirovannyi graficheskii redaktor lokatsionnykh izobrazhenii landshaftnykh stsen s gruppami malorazmernykh i tochechnykh ob''ektov [Tekst] / A. V. Krevetskii, D. V. Urzhumov. // Vestnik Povolzhskogo gosudarstvennogo tekhnologicheskogo universiteta. Ser.: Radiotekhnicheskie i infokommunikatsionnye sistemy.-2012.-№ 2(16).-S. 24-28.
20.
Ipatov Yu.A. Arkhitektura sistemy kompleksnogo deshifrirovaniya izobrazhenii aerokosmicheskikh izobrazhenii podstilayushchei poverkhnosti zemli v real'nom masshtabe vremeni [Tekst] / Yu. A. Ipatov, A. V. Krevetskii, D. V. Urzhumov, S. E. Chesnokov. // Vestnik Mariiskogo gosudarstvennogo tekhnicheskogo universiteta. Ser.: Radiotekhnicheskie i infokommunikatsionnye sistemy.-2012.-№ 1(14).-S. 47-59.
Ссылка на эту статью

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


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