Применение метода PSO при решении задач распознавания образов

Распознавание объектов по изображениям независимо от их расположения, ориентации, масштаба и перспективы – является важным направлением информационных технологий в области распознавания образов и машинного зрения. В задачах математической морфологии важной является задача сопоставления близких форм, а не точное определение каждой формы; деформация сложной фигуры может привести к пониманию формы. Изучение формы и изменчивости изображения в рамках теории распознавания образов можно свести к оцениванию преобразований, которые последовательно деформируют изображения. Вычисление многомерных нежёстких преобразований изображений привело к развитию стратегии эластичного сравнения, при этом преобразование линеаризуется относительно системы координат исходного изображения и генерируется векторное поле смещений. Стоимость преобразования измеряется функционалом – нормой разности между преобразованным исходным изображением и эталонным изображением; оптимальному преобразованию этого функционала соответствует векторное поле смещений с наибольшей гладкостью. Измерение гладкости достигается указанием нормы в пространстве векторных полей с использованием дифференциального оператора. Одним из ограничений данного подхода является то, что не гарантируется биективность преобразования. Представляет интерес вычисление диффеоморфных преобразований, которые сами являются гладкими, но и обратные преобразования сохраняют свойства гладкости. Модель больших деформаций для вычисления преобразований изображений [1] гарантирует, что преобразования, вычисленные между изображениями, диффеоморфны. При этом преобразование исходных точек области в требуемые формируется на основе зависящего от времени векторного поля скоростей, которое определяется системой обыкновенных дифференциальных уравнений (ODE).

В работе рассмотрена задача оценивания нормы расстояния между двумя замкнутыми гладкими кривыми при распознавании 2D-образов. Рассмотрены действия групп переноса, вращения и масштабирования на 2D замкнутую кривую, инварианты к действию этих групп. Для оценивания нормы расстояния между кривыми положение кривых нормализуется центрированием, приведением главных осей инерции изображения к осям системы координат и приведением к единице площади замкнутой кривой соответствующим масштабированием. Для оценивания нормы расстояния между двумя замкнутыми кривыми формируется функционал, соответствующий норме расстояния между двумя кривыми, и уравнение эволюции диффеоморфных преобразований. Предложен алгоритм решения уравнения диффеоморфного преобразования, построенный на основе метода PSO, который позволяет значительно сократить объем вычислительных операций по сравнению с градиентными методами решения.

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

Построение инвариантов переноса, вращения и масштабирования

Для нахождения инвариантов при распознавании образов необходимо найти группу G , действующую на множестве аргументов функции изображения. Изображение объекта может быть описано функцией f ( x, y ) = 1, если ( x , y ) e S c R² ( f ( x , y ) = 0, иначе), где ( x , y ) -декартовы координаты изображения с границей с = d S множества S . Действие группы переноса на функцию f ( x , y ) в направлении оси X : g_ч^f ( ^x , у ) = ^f ( ^x + ^e x , у ) ; ^оси Y ^:

g _b^f ( ^x , у ) = ^f ( ^x, у + ^e y ) .

Действие группы масштабирования на функцию f ( x, y ) :

gФsf (x, У ) = f ((1 + Фs ) x, (1 + Фs ) У ) .

Действие группы вращения (поворот на угол α ):

g_af ( x , y ) = f ( x cos a - y sina, x sina + y cos a ) .

Инвариантность по отношению к группе переноса может быть обеспечена нахождением центра ( x ₀, y ₀) с последующим переносом. Для действия группы переноса на функцию 2D-изображения нахождение центра изображения сводится к методу моментов [2] . Сформируем моменты порядка ( p + q ) 2D - функции f ( x , y ) :

m p , q = J x^py⁴f ( x, у ) ds; p, q ^eZ+ ;

S например, площадь изображения m0 0 = J f (x, y) dS .

S

Центр ( x ₀, y ₀) функции изображения f ( x, y )    определяется из соотношений:

x0 = m om-1;  y0 = m m-1. Центрированная функция f (x + x0, y + y0) является инвариантной по отношению к действию группы переносов. Для нормализации изображения перенесём центр f (x, y) в начало координат. Нормализованные моменты: f (x + x0, y + y0) являются инвариантами масштабирования. Подействуем на f ( x, y) таким элементом группы масштаби-

• •    Группа масштабирования может быть представлена диагональными матрицами

A 4^{p 0} I ,

k 0  p J

p e R⁺ .

рования g^ , что значение будет F = 1 .

Для выделения определённой ориентированной системы координат построим тензор

• •    SE ( 2 ) - специальная группа Евклида определяется полупрямым произведением SO ( 2 ) ® R².

Дифференцируемая кривая в GL ( 2 ) это функция:   g_t : ( a,b ) ^ GL ( 2 ) , для которых

изображения: J =

m 2,0    ^- m 1,1

— m 1,1    m 0,2 j

. При повороте

существует производная ^^; V t e ( а , b ) .

Уравнение первого порядка для элемента

матричной группы:

= A • g t ; g t = о = ^Id , где

объекта угол а с матрицей направляющих ко

синусов T =

cos а  - sin а ]

I тензор инерции sin а cos а J

изменяется по закону: J ' = Т^т • J • T . При пово-

роте

объекта

на

а = 0,5 • arctg ( 2 J_X y ( J yy - J xx )^- 1 ) , тензор

угол:

инерции

A e R^2x2 - матрица с постоянными элементами, имеет решение: g_t = exp ( tA ) , которое обладает групповыми свойствами.

Кривая, соединяющая элементы g ₀, g_x e GL ( 2 ) , минимизирующая функционал:

будет

иметь

J d = diag ( J_x  J JeR

диагональный .^2x2 , где J x , J

вид – соб-

J( Lv_t , v^dt ; L e R^2x2 ,     (1)

и удовлетворяющая уравнению

= v t • g t ,

ственные числа тензора инерции J . При Jx ^ J можно провести такое преобразование координат: (x’ y')T = T(x y)T - формированием поворота T , что оси X,Y будут направлены по главным осям тензора инерции 2D-изображения.

Будем рассматривать C ¹ замкнутую кривую – как непрерывно дифференцируемое отображение е : S ¹ ^ R² ; S ¹ = { x e R²|1 x | = 1 } , для которого производная c '( O ) существует для любого значения а и е ’ ( O ) ^ 0; VOe S ¹ .

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

Действие элементов групп на кривые

Рассмотрим действие матричных групп на кривые можно представить: A ^ Ac , где A : R² ^ R² действие матричной группы в R². Приведём примеры матричных групп [3] .

• •    GL ( 2 ) - линейная группа матриц GL ( 2 ) = { A e R^{2 x 2};det A ^ о } с законом композиции – умножением матриц.

• •    SO ( 2 ) e GL ( 2 ) - специальная ортого

нальная группа может быть представлена матрицами SO ( 2 ) : = { A e R^{2x 2} | AA^T = A^T A = Id;det ( A ) = 1 } .

является решением уравнения Эйлера [4] :

• d ( ^Lv t )/ ^dt = ( ^Lv t ) v * - v * ( ^Lv t ) .       ⁽²⁾

Группа диффеоморфных преобразований

Будем считать, что замкнутые кривые принадлежат открытому подмножеству X c R². Диффеоморфизм X является обратимым непрерывно дифференцируемым преобразованием X ^ X ; существует тождественное отображение (Id – композиция прямого и обратного диффеоморфизма). Множество диффеоморфизмов Diff ( X ) определяют структуру группы. Диффеоморфизмы изменяют количественные характеристики объектов, которые определены на множестве X . Матричные группы диффеоморфизмов имеют конечную размерность и кодируется с помощью параметров матриц.

Рассмотрим группу бесконечномерных диффеоморфизмов, действующих на ограниченном множестве X c R² . Определим диффеоморфизм g : X ^ X с обратным элементом g ^{- 1} и определим группу преобразований G , как подгруппу диффеоморфизмов, с законом композиции : g ^о g ' = g ( g ') e G . Для формирования диф-феоморфных отображений диффеоморфизмы рассматриваются как потоки ODE. Предположим, диффеоморфизмы g_t ( x ) ; x e X эволюционируют во времени t e [ 0,1 ] с векторным полем v ( • ) :

dg t ( ^x )/ ^dt = v t ( g t ( ^x ) ) ; g 0 ( ^x ) = ^x .      ⁽³⁾

Формированием требуемого векторного поля v_t ( • ) в любой момент времени t e [ 0...1 ] можно добиться такого действия элементов группы g_t ( ’ ) на точки пространства X с R², что g 0 ( x ) = x ; g i ( x ) = y; ^{V x} , y ^e X .

Допустим, что задана норма:

II v X = ( Lv t , v t >2 = J^{( Lv} t ) * v t dS ’

S где at = Lvt; t e [0,1] - момент векторного поля. Для    gt e G    существуют    скорости vt (gt) = dgt /dt, минимизирующие функционал:

Ф( vt ) = J|IvX dt = J (Lvt , v >2 dt , на траектории, соединяющей элементы группы g0 = g|t=0 и gi = g|t=1 • Представим обратную связь между скоростью v и моментом α в форме: vt = L-a, = Kat.(5)

Для дифференциального оператора:

L = id - a V ² в R² - обратный оператор K = L - аппроксимируем функцией:

K (x) = вe"7-11 x.(6)

Уравнения эволюции диффеоморфизмов Эйлера-Пуанкаре можно получить решением уравнений вариационной задачи с функционалом Ф ( v_t ) [5]:

da_t /dt = - ( Da_t ) v_t - a_tVv_t - ( Dv_t )T a_t ,  (7)

где Df = ( d f i /дx j ) ; i , j = 1,2 .

Если объектами являются точечные множества, то векторные поля в точках x_t = ( x ( t ) ,..., x_N ( t ) )

N принимают вид: v (*) = ^K(’,xz )a .

i = 1

Уравнения вариационной задачи позволяют перемещать объекты вдоль траекторий, которым соответствуют диффеоморфные преобразования. Диффеоморфизмы не позволяют изменить топологию вдоль геодезических траекторий. Неточный вид диффеоморфизмов [6, 7] обеспечивает механизм, который позволяет при эволюции геодезических отклоняться от точных деформаций. В задаче неточного сравнения минимизируемый функционал содержит член, который оценивает точность попадания точек g ₁ ( x 0 ) ; n = 1,... , N в требуемые позиции x ¹ :

1 N ₂

JII v t l ^ dt + a " ² £|| x n ^- g 1 ( ^x 0 )|| ,       ⁽⁸⁾

0                       n = 1

при этом в уравнения Эйлера-Пуанкаре диффеоморф-ных преобразований вводится параметр σ2 :

^dx kJ ^dt - v t ( x k ) = ^{a 2 a} k ; v t ( • ) =

N

= ^ K ( • , x l ) a l ; d a _k/ dt =          (9)

l = 1

N

• = ^- Z ^V 1 K ( x k , x i ) ^a T ^a i , l = 1

здесь V_t K представляет собой градиент функции ( x , y ) ^ K ( x , y ) по отношению к первой координате. Примем для оператора L функцию K ( x , • ) в виде: K ( x , • ) = e ¹ “x (’^ . Тогда:

• ^V 1 ^K ( x_k , x l ) = ^-2Y ^{- 1} ( x k ^- x_t ) e "⁷¹¹ x^{k -} x^{l 1} .

Решение задачи методом PSO

При решении уравнения (9) необходимо определить краевые условия a0 = (ax (0),...,aN (0)) и a =( a1 (1) ,...,aN (1)) при известных x0 =(x1 (0),•• •,xN (0)) и x1 =(x1 (1) v,xN (1)) . Применение градиентных методов решения задачи (9) требует значительное количество вычислительных операций. Для решения этой задачи в работе предлагается применение метода пристрелки (shooting) с использованием алгоритма PSO (particle swarm optimization). Метод пристрелки заключается в нахождении такого начального вектора    a0 = (ax (0) ,...,aN (0)), что значение функционала (8) минимизируется.

Метод PSO основан на имитации поведения роя насекомых и был предложен J. Kennedy в 1995 году [8] . В контексте многопараметрической оптимизации рой (swarm) имеет фиксированный размер; каждая частица первоначально расположена в случайных местах в многомерном пространстве проектирования. Частицы имеют две характеристики: положение и скорость. Положение частицы определяется значением целевой функции. Частицы обмениваются информацией (лучшими позициями) и могут корректировать свои позиции и скорости. Алгоритм метода PSO приведён в приложении.

Пример . Рассмотрим пример диф-феоморфного преобразования замкнутой кривой – окружности единичного радиуса (эллипс с эксцентриситетом 8 = 0 и длиной окружности 2п) в отрезок прямой длиной п (эллипс с 8 = 1) за единичный период времени. Для этого выберем N = 12 точек на эллипсе, соответствующие параметру 0_z = 2п iN '; i = 1,..., N . Выберем параметр уравнения диффеоморфных преобразований: a² = 10 ^{- 4}; параметр метод PSO: Э = 0,7 ; число частиц: 10. В таблице 1 представлены результаты моделирования диффеоморфных преобразований точек эллипса от значения эксцентриситета 8 = 0 до 8 = 1 для четырёх точек (из 12) замкнутой кривой.

Таблица 1.

Результаты моделирования диффеоморфных преобразований

Table 1.

The results of simulations of diffeomorphic transformations

t	0 x 0	x 0	x 6 0	x 9 0	0 x 0	ε
0	(0,00; 1,00)	(1,00; 0,00)	(0,00; -1,00)	(-1,00; 0,00)	(0,00; 1,00)	0,000
2	(0,01; 0,77)	(1,41; -0,01)	(-0,01; -0,77)	(-1,43; 0,02)	(0,01; 0,77)	0,840
4	(0,02; 0,55)	(1,83; -0,01)	(-0,02; -0,55)	(-1,84; 0,02)	(0,02; 0,55)	0,954
6	(0,02; 0,36)	(2,22; -0,01)	(-0,02; -0,36)	(-2,22; 0,03)	(0,02; 0,36)	0,987
8	(0,02; 0,18)	(2,56; -0,01)	(-0,02; -0,18)	(-2,54; 0,03)	(0,02; 0,18)	0,998
10	(0,03; 0,00)	(2,85; -0,02)	(-0,03; 0,00)	(-2,82; 0,05)	(0,03; 0,00)	1,000
	x 0	x 1	x 6 1	x 9 1	x 0
x 1	(0,00; 0,00)	(3,14; 0,00)	(0,00; 0,00)	(-3,14; 0,00	(0,00; 0,00)	1,000

В результате получена дисперсия неточности попадания £|| x 1 - g_Y ( x„' ) |2 = 0,34 и сред- n = 1

нее  отклонение одной точки от цели

/12 ^{- 1} £ | x n - g1 ( x n )| |2 = 0,17 . Для повышения У        n = 1

точности попадания необходимо увеличить число итераций и количество частиц в методе PSO, а также уменьшить параметр дисперсии σ2 .

Заключение

Рассмотрена задача оценивания расстояния между замкнутыми 2D кривыми. Представлены методы нахождения инвариантов к действию групп переноса, вращения и масштабирования на замкнутую кривую, не зависящие от координатного описания изображения. Для оценивания нормы расстояния между двумя замкнутыми кривыми формируется функционал, соответствующий норме расстояния между двумя кривыми, и уравнение эволюции диффеоморфных преобразований, полученное решением вариационной задачи. Предложен алгоритм решения уравнения диффеоморфного преобразования, построенный на основе метода PSO, который позволяет значительно сократить объем вычислительных операций по сравнению с градиентными методами решения. В дальнейшем алгоритм решения уравнения    диффеоморфного    преобразования будет распространен на 3D объекты: точечные множества, кривые и поверхности. Следует рассмотреть задачу распознавания динамически изменяющихся объектов методом решения уравнений диффеоморфного преобразования.

Приложение

Метод PSO [9, 10] . Рассмотрим задачу оптимизации (максимизации) без ограничений:

Maximize/ (X);X(l) < X < X(u), где X(l), X(“) - нижняя (lower) и верхняя (upper) границы X . Пусть число частиц N .

Процедура PSO применяется с использованием следующих шагов.

• 1.    Сформируем случайное начальное множество X_t ( 0 ),..., X_N ( 0 ) . Положение и скорость частицы j при итерации i : X ( i ) , V_J ( i ) , соответственно. Определим значение целевой функции: / [ X 1 ( 0 ) ,...,X n ( 0 )_] .

• 2.    Найдём скорости частиц. Начальные скорости всех частиц принимаются равными нулю и номер итерации: i = 1.

• 3.    На итерации i найдём параметры X ( i ) , V ■ i ) частицы j :

• (a)    Историческое лучшее значение положения X ( ¹ ) : P, , . с лучшим значением целевой j         best , j

функции / ^ X ( i ) J частицы j на всех предыдущих итерациях. Историческое лучшее значение положения X ⁽ ( ^z ) : G_best с лучшим значением целевой функции / ^ X ( i ) J на всех предыдущих итерациях для всех N частиц;

• (b)    найдём скорость частицы j на итерации i :

• V ( 0= _S . V ( i ^{- 1} ) + _{С 1} Г 1 [ р _бю(    X j ^{- 1 )}] +

+С2Г2 [Gbest — XF)] + С3 * Г3 ’ 2—^^0 , где c1, c2, с3 - скорости обучения, rx, r2, r3 е[0 .. .1] -равномерно случайно распределённые числа;

• (c)    найдём положение частицы j на итерации i : X ( i ) = X ( i ^{- 1 )} + Vj ( i ) , и соответствующее значение целевой функции / ^ X ⁽ i ) ,..., X ( i ) J .

• 4.    Шаг 3 повторяется с i = i + 1 и новыми значениями P , G . Процесс продолжается до тех пор, пока все частицы не сойдутся к значению, обеспечивающему оптимум целевой функции.

Работа выполнена при финансовой поддержке Российского фонда фундаментальных исследований (проекты 14-07-0027215 и 14-08-14-08-01132) и при поддержке Программы РАН по проекту «Математические методы распознавания образов и прогнозирования» (№0314-2014-2017) (№ госрегистрации 01201351843).