Статья 'Методы обнаружения и пространственной локализации групп точечных объектов' - журнал 'Кибернетика и программирование' - 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 > Article Processing Charge > Article Identification Policy > Plagiarism check policy
Journals in science databases
About the Journal

MAIN PAGE > Back to contents
Cybernetics and programming
Reference:

Methods of detection and spatial localization of groups of point objects

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
Other publications by this author
 

 
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
Other publications by this author
 

 

DOI:

10.7256/2306-4196.2014.6.13642

Received:

02-11-2014


Published:

16-11-2014


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

This article written in Russian. You can find original text of the article here .
Введение

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

References
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
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.