Алгоритм распознавания изображений на основе градиентного совмещения объекта с эталоном

Размещено на http://www.allbest.ru//

Размещено на http://www.allbest.ru//

Алгоритм распознавания изображений на основе градиентного совмещения объекта с эталоном

Е.А. Самойлин

Аннотация

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

Ключевые слова: распознавание изображений, градиентное совмещение объектов, реперные точки, подстройка координат.

ALGORITHM FOR IMAGING THE IMAGES BASED ON GRADIENT OBLITATION OF AN OBJECT WITH STANDARD

E.A. Samoylin1, S. A. Karpov1, D. Y. Dronov 1, K. E. Skugorov 1

1MESC AF «N.E. Zhukovsky and Y.A. Gagarin Air Force Academy», Voronezh, Russia

Abstract. An algorithm for deterministic image recognition has been proposed, in which, in order to ensure the invariance of objects to shift, rotate and scale, a procedure for gradient matching of the reference and recognizable objects has been introduced.

Keywords: image recognition, gradient alignment of objects, fixed points, coordinate adjustment.

Введение

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

Геометрия задачи совмещения эталона с объектом

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

- выделение контуров объектов;

- выбор реперных (ключевых, информативных, узловых и т.д.) точек объекта и эталона, а также нахождение соответствия между ними;

- совмещение реперных точек объекта и эталона (т.е. автосмещение, автоповорот и автомасштабирование контура объекта либо эталона);

- вычисление меры близости объекта и эталона, принятие решения о принадлежности объекта к некоторому классу образов.

Выделение контуров и выбор реперных точек объекта и эталона частично решены в работах [4-6]. Рассмотрим предлагаемую процедуру совмещения реперных точек эталона и объекта.

Анализ известных методов совмещения изображений [1-3] показывает, что одним из перспективных направлений является использование методов оптимизации, в частности градиентных методов [2], основанных на введении какой-либо функции ошибки и движении одного из объектов в направлении, минимизирующем эту функцию.

Предположим, что имеется два объекта: эталонный A0B0C0, и распознаваемый ABC (рис. 1). Для упрощения изложения положим, что эти объекты имеют форму треугольника (в виде контура), а также определены их реперные точки.

Рис. 1. Геометрия задачи совмещения эталона с объектом

Требуется совместить реперные точки эталонного объекта A0B0C0 с соответствующими реперными точками полученного объекта ABC, обеспечив минимум функции F1 невязки их координат:

(1)

при сохранении формы (углов a0, b0, c0) объекта A0B0C0 (рис. 1):

(2)

где K - число шагов.

Процедура градиентного совмещения эталона с объектом

Решение сформулированной задачи совмещения объектов (1)-(2) в классическом [7] для численной оптимизации виде может быть основано на введении общей функции ошибки F=(F1)2+(F2)2. Однако такой подход может привести к плохой обусловленности задачи оптимизации и сложностям дифференцирования функции F. Кроме того, поскольку функции (1) и (2) разнородны (F1 минимизирует невязку координат, F2 - углов), их объединение может привести к такой величине шага, при котором недорегулированным окажется процесс подстройки координат, минимизирующих F1 (1), и перерегулированным процесс подстроки координат, минимизирующих F2 (2), либо наоборот.

Разработанная процедура предполагает раздельную для функции F1 и F2 подстройку, где на нечетных шагах осуществляется движение (подстройка координат) точек A0, B0, C0 в направлении антиградиента функции ошибки F1, а на четных - в направлении, минимизирующем F2.

а. Нечетные шаги процедуры

Рассматриваемая задача (1) предполагает адаптивную подстройку координат xA0, yA0, xB0, yB0, xC0, yC0, в направлении антиградиента ошибки в соответствии с выражением:

(3)

где k - номер шага или итерации, k=0…K, где K - число шагов; xk(yk) - текущее (на шаге k) значение координаты x (y) для любой из реперных точек; xk+1 (yk+1) - новое значение координаты x (y) на шаге k+1; - параметр, определяющий скорость и устойчивость сходимости градиентного поиска для функции (1); , - частные производные функции F1 по координатам x и y соответственно.

Частные производные , по координатам x, y для реперной точки A0 примут вид:

(4)

Подставляя (4) в (3), получим выражение для первого, третьего, а также последующих нечетных шагов (вплоть до K -1) координат x, y реперной точки A0:

(5)

Аналогичным образом (3)-(5) на первом и последующих нечетных шагах осуществляется градиентное движение точек B0 и C0 в направлении точек B и C соответственно.

б. Четные шаги процедуры

На втором, четвертом, а также последующих четных шагах осуществляется градиентная коррекция координат точек A0, B0, C0 в направлениях, позволяющих по возможности точнее сохранить углы a0, b0, c0 эталонного объекта (рис. 1), т.е. минимизирующих выражение (2):

(6)

где - параметр, определяющий скорость и устойчивость сходимости градиентного поиска для функции (2).

Для нахождения частных производных функции F2 по координатам x, y выразим значения углов a0, b0, c0 через эти координаты:

(7)

где r(A0B0) - евклидово расстояние между точками A0 и B0: r(B0C0) - евклидово расстояние между точками B0 и C0: r(A0C0) - евклидово расстояние между точками A0 и C0: .

С учетом выражения (7), подставляя производную в первое выражение системы (6), а - во второе, получим общее выражение для четных шагов (вплоть до K) точки A0 по координатам x и y:

(8)

Шаги k продолжаются до значения K, пока не перестанут уменьшаться ошибка невязки координат F1 и ошибка рассогласования углов F2.

В качестве примера предположим, что заданы следующие значения координат реперных точек полученного объекта: xA0=2, yA0=2; xB0=7, yB0=8; xC0=2, yC0=8, а также эталонного объекта: xA=80, yA=60; xB=55, yB=45; xC=80, yC=35.

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

Рис. 2. Совмещение эталонного и распознаваемого объектов на изображении

Распознавание объекта на основе сличения с эталоном

На заключительном шаге алгоритма требуется определить принадлежность объекта к определенному классу. В данном случае будем рассматривать двухальтернативную задачу: принадлежность/непринадлежность объекта единственному классу образов.

Матрица координат реперных точек, получаемая после процедуры градиентного совмещения эталонного объекта, может быть представлена в виде (для объектов в виде треугольника, рис. 1), а матрица координат реперных точек распознаваемого объекта - в аналогичном виде . Тогда для определения принадлежности объекта ABC к классу образов, соответствующему эталону A0B0C0, можно воспользоваться известным выражением:

градиентный совмещение эталон распознавание

(9)

где P - величина порога, определяемая экспериментальным путем; H1 - принимаемое решение о том, что распознаваемый объект ABC принадлежит классу эталонного образа A0B0C0; H0 - принимаемое решение о том, что распознаваемый объект ABC не принадлежит классу эталонного объекта A0B0C0.

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

Рис. 3. Пример распознавания на основе градиентного совмещения эталона с объектами

Заключение

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

Литература

, Костяшкин Л.Н., Логинов А.А., Никифоров М.Б. Совмещение изображений в корреляционно-экстремальных навигационных системах. М.: Радиотехника, 2015. 208 с.

Васильев К.К., Крашенинников В.Р. Статистический анализ последовательностей изображений. Монография. М.: Радиотехника, 2017. 248 с

Гонсалес Р., Вудс Р. Цифровая обработка изображений. М.: Техносфера, 2012. 1104 с.

Hast. A. Optimal RANSAC - Towards a Repeatable Algorithmfor Finding the Optimal Set / A. Hast, J. Nysjo, A. Marchetti // Journal of WSCG. - 2013. - Vol. 21(1). - P. 21-30.

Самойлин Е.А., Карпов С.А., Алейник И.С. Оценивание эффективности алгоритмов выделения контуров зашумленных изображений // Радиолокация, навигация, связь: Сборник трудов XXIV Международной НТК. 2018. Том 1. С. 403-408.

Самойлин Е.А., Карпов С.А. Алгоритм адаптивного оконтуривания объектов на изображениях в условиях аддитивных гауссовских искажений с дисперсией различного уровня // Радиотехника. 2018. № 8. С. 61-66.

Уидроу Б., Стирнз С. Адаптивная обработка сигналов / Пер. с англ. М.: Радио и связь, 1989. 440 с.

Размещено на Allbest.ru