Identification of the chain structure images within the groups of point objects via correlation of code elements of their contours.

Krevetsky Aleksander Vladimirovich PhD in Technical Science Head of the Department of Computer Science, Volga State University of Technology 424000, Russia, Marii El, g. Yoshkar-Ola, pl. Lenina, 3 krevetskyav@volgatech.net Other publications by this author

Urzhumov Daniil Vladimirovich Senior Lecturer, Volga State Technological University 424000, Russia, Marii El, g. Ioshkar-Ola, pl. Lenina, 3 UrzhumovDV@volgatech.net Other publications by this author

Введение

Изображения групп точечных и малоразмерных объектов (ГТО) представляют собой множество изолированных контрастных по отношению к фону отметок в пространстве заданной размерности. Примерами таких изображений могут служить множества характерных точек крупноразмерных объектов, локационные изображения транспорта или других объектов искусственного происхождения, снимки созвездий, кластеры результатов наблюдений в признаковом пространстве ^[1-7].

Распознавание ГТО, по сравнению с изображениями крупноразмерных объектов, осложняется вследствие несвязности их элементов, узости автокорреляционных функций их изображений по параметрам геометрических преобразований, наличием координатных шумов и помех в виде ложных отметок. Наиболее перспективные подходы к распознаванию изображений данного типа основаны на преобразовании ГТО в связный объект и анализе его вторичных дискриминационных признаков ^[7-14]. Для связывания используют графовый, фильтровой подход или метод потенциальных функций. Чаще всего, самым информативным вторичным признаком служит форма такого связного ассоциированного с ГТО образа, отображающего конфигурацию взаимного положения элементов ГТО ^[7,10,12,14].

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

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

Рис. 1. Примеры изображений цепочки и скопления

В настоящей работе исследуется возможность использования признаков формы для различения цепочек и скоплений.

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

Для целей данной статьи предположим, что задача обнаружения отдельных элементов ГТО решена ^[5,7], по ее результатам сформирована точечная сцена, а в этой сцене решена задача обнаружения ГТО по признаку пространственной компактности ^[7,8]. Один из наиболее эффективных подходов к обнаружению пространственно компактных ГТО состоит в построении связного графа на множестве обнаруженных точечных отметок с минимальной суммарной длинной ребер (минимального дерева), разрушении длинных, в статистическом смысле, ребер и принятии решения в пользу подграфов с достаточным числом вершин ^[8].

Таким образом, будем считать, что на вход различителя цепочек и скоплений предъявлено подмножество точек Q, связанных минимальным деревом (рис.2,а). На основе анализа формы этого графа необходимо вынести обоснованное решение в пользу гипотезы H₁, о том что это граф цепочки, или в пользу гипотезы Н₀ – что это граф скопления.

Рис. 2. Описание (а) и кодирование формы (б) цепочек и скоплений

Методика решения задачи

Примем в качестве метода описания формы представленного на вход различителя минимального дерева N(x) его контурное представление (рис. 2, б). В результате цепного комплекснозначного кодирования полигональной аппроксимации контура ^[7,9] формируется вектор-контур N={v(n)}, где v(n), n=0,1,2,…,k-1 – элементарные векторы (ЭВ) контура, k – его размерность. Контуру N в унитарном пространстве Сk соответствуют свой спектр мощности и нормированная автокорреляционная функция (АКФ)

(1)

где ||N||² ― квадрат нормы (энергия) контура, d – циклическое смещение начальной точки контура,* – знак комплексного сопряжения.

Упорядоченность точек цепочечного ГТО вдоль траектории слабой кривизны обуславливает сильную корреляцию направлений элементарных векторов контура минимального дерева цепочки, медленно убывающую с удалением одного ЭВ от другого, и, следовательно, широкий интервал корреляции и сосредоточенный в области низких частот спектр мощности. Для сильно разветвленного контура минимального дерева скопления степень корреляции направлений ЭВ убывает значительно быстрее. В результате, для его контура характерен узкий интервал корреляции, и, следовательно, существенно более широкий спектр.

Примеры модулей нормированных АКФ контуров цепочек и скоплений приведены на рис. 3 (случай цепочки ― сплошная линия, скопление ― пунктир).

Рис. 3. Графики нормированных АКФ цепочки и скопления

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

В связи с тем, что лишь ширина спектра контура, а не каждый его отсчет в отдельности, несет информацию о принадлежности ГТО к одному из семейств, целесообразно в качестве информативного признака выбрать именно данную характеристику ГТО. С учетом связи ширины спектра мощности и ширины интервала корреляции сигналов для минимизации вычислений выберем в качестве меры сосредоточенности энергетического спектра контура в области низких частот размер его интервала корреляции τ, определяемый как ширина главного лепестка модуля АКФ вектор-контура N:

(2)

Вследствие случайного характера шума размер интервала корреляции в обоих случаях становится случайной величиной с плотностью вероятности W₁(τ|q) для цепочки и W₀(τ|q) –для скопления, где q― параметр, характеризующий относительную мощность шума. Плотности вероятности показаны условными, т.к. могут меняться с изменением мощности шума.

В работе ^[7] показано, что оптимальный в смысле критерия отношения правдоподобия на основе минимальной достаточной статистики различитель должен реализовать алгоритм

(3)

где τ₀ ― порог, назначаемый согласно конкретному варианту критерия оптимальности.

Трудоемкость данного алгоритма пропорциональна квадрату размерности контура: T~6k2 , где 6 – число операций типа сложение/умножение на одно слагаемое при вычислении одного отсчета АКФ (1). Следует отметить, что для возможности сопоставления результатов измерения ширины интервала корреляции для ГТО различной мощности, необходимо выполнять дополнительную процедуру выравнивания размерностей k. Это дополнительно увеличивает трудоемкость алгоритма различения пропорционально размерности кода контура.

Если в качестве модели цепочки взять аналог колонны транспортных средств, где и длина и направление текущего ребра минимального дерева связаны только со смежным, то можно в качестве информативного признака использовать среднюю корреляцию только соседних ЭВ контура минимального дерева, где каждый ЭВ по длине совпадает с длиной соответствующего ребра минимального дерева ГТО, т.е. первый отсчет модуля нормированной АКФ (1):

(4)

Трудоемкость вычисления (4) в k раз меньше трудоемкости предыдущего алгоритма, причем нет необходимости выполнять эквализацию кода контура.

Оптимальный по критерию отношения правдоподобия алгоритм различения цепочек и скоплений для такой модели цепочки сводится к вычислению функций правдоподобия гипотез H₁ и Н₀, подстановке статистики g в условные законы распределения вероятностей W₁(g|q) и W₀(g|q), вычислению отношения правдоподобия и сравнению его с порогом:

(5)

Для конкретизации условных распределений вероятностей в качестве эталонного скопления использовалось случайное равномерное поле точечных отметок в пределах заданного квадрата. В качестве эталонных цепочек использовались расположенные на траектории с относительным радиусом кривизны R=R’/r_c c равным шагом точечные отметки. Здесь r_c – средняя длина ребра минимального дерева ГТО. В каждом опыте эталонные положения точечных отметок ГТО искажались независимо нормальным шумом с нулевым математическим ожиданием и СКО σ’=σ∙r_c. Исследовались ситуации с R={∞; 13,8; 8,3; 5,9; 4,1}.

На рис. 4 приведены выборочные распределения вероятностей (гистограммы относительных частот) статистики g для ГТО со структурой скопления (левый график) и цепочки для траектории с кривизной R=4,1 при различных уровнях координатных шумов: σ={0,05; 0,1; 0,15; 0,2; 0,25; 0,3; 0,35; 0,4} – графики справа налево. Указанные значения σ соответствуют отношеням сигнал/шум g=1/σ={20; 10; 6,7; 5; 4; 3,3; 2,9; 2,5}.

Рис. 4. Гистограммы частот значений статистики различения g

Одномодовый характер и компактность выборочных распределений позволяет сделать предположение, что в качестве минимальной достаточной статистики оптимального алгоритма может использоваться величина g. В этом случае получаем более простую в вычислительном плане реализацию оптимального алгоритма (5):

(6)

где g₀(q) – пороговое значения модуля первого отсчета нормированной АКФ контура, назначаемое согласно заданной версии критерия оптимальности. Так, на рис. 5 приведен график значений порога g₀(q) для критерия максимального правдоподобия. Он практически совпадает для всех указанных выше значений кривизны траектории цепочки R.

Рис. 5. Значение порога g₀(q), оптимального по критерию максимального правдоподобия

Характеристики различения цепочек и скоплений

На рис. 6 даны характеристики различителя (6) в виде зависимости суммы условных вероятностей ошибок

(7)

Рис. 6. Характеристики различения цепочек и скоплений на основе статистики g

Полученные характеристики различения совпадают с характеристиками алгоритма (5), т.е. предположение о минимальной достаточной статистике g полностью подтвердились.

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

Если отношение сигнал/шум не известно заранее, то в качестве критерия оптимальности может использоваться критерий Неймана-Пирсона, где порог g₀ назначается по независящему от уровня координатных шумов условному распределению вероятностей скопления W₀(g|q) из заданной вероятности ошибок первого рода F:

(8)

На рис. 7 даны характеристики различителя при выборе порога по критерию Неймана-Пирсона для уровня ошибок первого рода F=0,01. При выборе данного критерия алгоритм различения цепочек и скоплений можно назвать алгоритмом «опознавания» цепочек.

Рис. 7. Характеристики различения для критерия Неймана-Пирсона

Пунктиром на рис. 6 и 7 приведены характеристики различения цепочек и скоплений с помощью базового алгоритма (3) для случая максимальной кривизны траектории цепочек. Из сравнения характеристик алгоритмов (3) и (6) следует более высокая помехоустойчивость алгоритма (3). По мнению авторов это обусловлено кумулятивным вкладом всех компонент спектра мощности контура в ширину интервала корреляции.

Выводы

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

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

Второй алгоритм существенно выигрывает по трудоемкости различения. Платой за это служит определенное снижение пороговых отношений сигнал / шум. В то же время, данный алгоритм обеспечивает вероятность ошибок не выше 10%, вплоть до случайных флуктуаций координат элементов ГТО со среднеквадратическим отклонением σ=0,33 от среднего расстояния между ними.

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