книги / Теория признаков распознавания образов на основе стохастической геометрии и функционального анализа

6.2. Триплетные признаки, инвариантные к аффинным преобразованиям 141

для всех гладких возрастающих (сохраняющих направление) диффео­ морфизмов р окружности; если в считается углом (переменной, ко­ торая принимает значения на всех действительных числах), то р — гладкий возрастающий диффеоморфизм прямой действительных чисел, удовлетворяющий дополнительному условию, что (р(в) —в) является 27г-периодической функцией от в.

Тогда триплетный признак в форме (6.7) не зависит от выбора пра­ вильной системы координат (0 ,e i,e 2) в плоскости или инвариантен к сохраняющим направление аффинным преобразованиям изображения.

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

Теорема В. Пусть функционалы ©, Р и Т будут инвариантны

кпереносу, т. е. предположим, что для всех чисел Ъ:

1)Т (u(t + Ъ)) = Т(м(£)) для всех допустимых функций и;

2)Р (и(р + Ь)) = Р(и(р)) для всех допустимых функций и;

3)@(и(в + Ь)) = &(и(в)) для всех допустимых функций и.

Тогда признак (6.7) не зависит от переносов и поворотов изобра­ жения.

Теорема С. Пусть функционалы ©, Р и Т будут таковы, что для всех чисел Ъи а:

1) Т (u(t + Ъ)) = Т (u(t)) для всех допустимых функций и\

2)Р (и(р —Ъ)) = Р(Цр)) + b для всех допустимых функций и\

3)@(и(в + Ь)) = @(и(в)) для всех допустимых функций и;

4)@(и(в) + asin(# + b)) = &(и(в)), что означает, что этот функци­ онал не зависит от первой гармоники функции и.

Тогда признак (6.7) не зависит от переносов и поворотов изобра­ жения.

Генерировать большое количество функционалов с приведенными свойствами просто. Заметим, что функционалы не обязательно должны быть линейными. Мы даем несколько примеров ниже.

Инвариантные к переносу и чувствительные к переносу функ­ ционалы. Эксперименты с различными функционалами, определяю­ щими признак П в (6.7), показывают, что большинство эффективных признаков имеет общие свойства, которые мы рассмотрим отдельно.

Пусть х будет действительной переменной (чтобы сделать дальней­ шие формулы строгими, мы предполагаем, что х является отображе­ нием идентичности числовой оси R в себя). Пусть Е будет функцио­

142	Гл. 6. Триплетные признаки распознавания образов

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

Функционал Е называется инвариантным к переносу, если (il) Е(£ о (ж + b)) = Е£ для всех Ъе R.

Инвариантный к переносу функционал Е может иметь дополнительные свойства:

02) существует положителвная функция с областью определения Бопк/г, такая что 1 & Dom<р, <у?( 1) = 1 и В(£ о (ах)) = <р(а)Е£ для всех а > О, а £ Dom(/r;

03) существует положительная функция -у с областью определения Domy, такая что 1 & Domy, у(1) = 1 и Е(с£) = у(с)Е^ для всех с > О, с (Е Domy;

(i4) Е(£о (—х )) = Е£; это свойство называется симметрией.

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

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

Функционал Z называется чувствительным к переносу если (si) Z(£ o(x + b)) = Z ( - b для всех b е R. Дополнительными, необязательными свойствами являются

(s2) Z(C о (ах)) = —Z С для всех а > 0;

а

Свойства (si) и (s2) дают

Z(Co(a(x + b ) ) ) = -l Z C - b

или в другой форме

Z(Co(ax + 6)) = I (ZC - Ь);

(s3) Z(сф) = Zф для всех с > 0; (s4) Z(£ + d) = Z ( для всех d <ЕR.

6.2. Триплетные признаки, инвариантные к аффинным преобразованиям 143

Область определения функционала Z, чувствительного к переносу в смысле определения (si), не может содержать нулевую функцию,

потому что функция	£ = 0	не удовлетворяет условию (si). Подоб­
ным образом условие	(si)	не выполняется для любой периодиче­

ской функции. Однако чувствительный к переносу функционал мож­ но правильно определить для непериодической функции. Например, существует много способов определения чувствительного к переносу функционала на множестве всех конечных ненулевых функций. Про­ стейший способ — определить, что функционал должен быть точкой максимума (или минимума) в области определения функции: Z£ = = max Close {ж: £(ж) ф 0}, где Close — операция топологического за­ мыкания. Чувствительный к переносу функционал можно неформально интерпретировать, как операцию выбора точки на оси абсцисс графика функции независимо от положения начала координат. Если шкала также исключается из рассмотрения, то выполняется условие (s2).

Чувствительные к переносу функционалы, определенные в пространстве 27г-периодических функций, должны рассматриваться отдельно. Определение (s2) тогда неприменимо. Предположим, что h является 27г-периодической функцией, и существует ее минимальный положительный период, равный т. Тогда для некоторого целого п

выполняется 2ж = пт. Анализ (si) позволяет нам	заключить, что
дискретную регулярную сетку
{a + jr: j = 0 ,1,-1,2,-2,3,...}	(6.8)

можно естественно считать функциональным образом.

Число а, определяющее сетку, само определено с точностью до множителя, кратного т.

Если некоторые числа А и В различаются числом, кратным т, мы пишем А = E>(modd т). Предположим, что функция h является 2тт- периодической, не делая каких-либо предположений об ее минималь­ ном периоде. Пусть т будет положительным числом (не обязательно периодом функции К). Функционал Z чувствителен к переносу по модулю т, если

(si. т) 7i(h о (ж + Ъ)) = Zh —6(modd т) для всех Ъ6 М. Для т = 2т:/п мы также используем обозначение

(si. 2 т:/п) = (si. т).

Очевидно, можно предположить, что функционал Z определяется с точностью до множителя, кратного т. Строгое определение следую­ щее: образ функционала Z является множеством регулярных дис­ кретных сеток в форме (6.8). Ясно, что это утверждение является естественным обобщением понятия фазы синусоидальной функции. Мы будем применять определение (si. г) для анализа периодической функции h в (6.6), получаемой на предпоследней стадии вычисления признака (6.7). Определение фаз и амплитуд гармоник согласуется со схемами (s l.r) и (il) соответственно. При переносе суммы гармоник различные гармоники переносятся на различные фракции их перио­ дов. Однако сетки (6.8), соответствующие гармоникам с периодами

144Гл. 6. Триплетные признаки распознавания образов

т= 2-7Г/п, претерпевают одинаковые сдвиги. Таким образом, рассмот­ рение фаз как сеток, определенных свойством (si. г), позволяет нам применять спектральный анализ для конструирования чувствительных

иинвариантных к переносам функционалов.

Триплетный признак для поворота, гомотетии и переноса изоб­ ражения. В этом параграфе выводятся формулы (6.9), (6.11), (6.13) и (6.14), которые описывают зависимости триплетных признаков от конформных линейных преобразований изображения. Здесь также по­ казывается, как можно использовать признаки для нахождения пара­ метров преобразования. Эти результаты являются значительно более

важными, чем теоремы, приведенные выше.		(5.9) связаны как
Предположим, что	две системы координат
О — Р = (vi, У2)воА(фо)	и (ei, ед) = (vi, \ 2 )pS(a),	где ц > 0, т. е. мы

имеем поворот изображения на угол а, затем д-кратное расширение и перенос. Как показывает формула (5.16), параметры прямой линии и точки прямой линии в первой и второй системах координат связаны равенствами

О =	0 -Т сц	р — рр + si(# + a),	t = pt Т s2($ о?),
где штрихи	соответствуют второй		системе координат,	si(£) =
= so cos(ipo -	£) и s2(£) = sosin(^o —£)• Установим v = l / p .			Тогда
приведенные выше равенства записываются как
в = в' —а,		р = vp' —vs\(Q'),	t = v t ' — vs2 (6 ').

Подставим эти формулы в (5.16) и удалим штрихи для упрощения обозначения. Мы получаем соотношение, эквивалентное соотноше­ нию (5.16) для всех р и в,

L (О, e i , е г , 0 — a, vp — i/s\(9), vt — J/S 2( 0 )) =

= L(P, v i,v 2,0, p,t), t e R . (6.9)

Нашей целью является выражение триплетного признака П2, запи­ санного во второй системе координат, в терминах признака П), запи­ санного в первой системе координат. Согласно (6.7) и (6.9) получаем

П2 = П(Р, vi, V2, ©, Р, Т, F) = 0 о Р о Т (F о L(P, v i, V2 , 0, руt)) =

= @ о Р о T(F о L (О, ei, ег, в —a, vp —vs\(0), vt —J/S2(#))).

Для продолжения мы должны сделать некоторые допущения, ка­ сающиеся функционалов. Мы ограничились рассмотрением инвариант­ ных к переносу или чувствительных к переносу функционалов. Вполне естественно предположить, что функция изображения является произ­ вольной конечной функцией. Тогда функционал Т мог бы применяться к нулевой функции. Следовательно, функционал Т не мог бы быть чувствительным к переносу, потому что, как было отмечено ранее, функционалы, которые чувствительны к переносу в смысле наших определений, не могут применяться к нулевой функции. Поэтому функ­ ционал Т должен быть инвариантным к переносу. Пусть функционал Т удовлетворяет условиям (П) и число v = \ / p находится в области

6.2. Триплетные признаки, инвариантные к аффинным преобразованиям 145

определения функции ip = ipT . Тогда

П2 = 0 о Р (<pT(i/)g(9 — a,vp — vs\(6 ))),

где функции д и к , введенные выше, описываются равенствами (6.6).

В зависимости от	свойств функционала Р существуют две возмож­
ности:
1) функционал	Р	удовлетворяет	условиям	инвариантности	(il);
тогда				а)),
П2 = 0 (7 р(Тт(^))Тр(^)к{в -
если коэффициент		не бессмысленен, т. е. » е Dom^r , г; 6 Dom <рр
и 4>T {V )4>P {V ) S Domyp;			условиям	чувствительности	(si)
2) функционал	Р	удовлетворяет
и (s2); тогда		П2 = @(/лк(в -	а) + si (в)).

В зависимости от свойств функционала © эти возможности раз­

ветвляются.
Рассмотрим первый вариант:
(l.i) функционал 0 удовлетворяет условию (il)	и коэффициент
в (6.10) определен; тогда
П2 = 7ф(7р(^т(г/))<Рр(^/))П1;	(6.10)

заметим, что это равенство доказывает теорему В: достаточно поло­ жить v = \/ р = 1 ;

(l.s) функционал 0 удовлетворяет условиям (si. 2-п/п) и (s3); тогда

П2 = III + a(modd 2ж/п).

(6.11)

Второй вариант более усложнен, но он позволяет получать па­

раметры /г,	s0 и ф0 аффинного преобразования. Гармоника si(#) =
= soсс©(фо -	6 ), включенная в выражение П2 = ®(рьк(в — а) + si(#)),

полностью определяет перенос изображения и может быть найдена методами гармонического анализа при данной функции дк(в —а). Про­ цедура заключается в следующем. После вычисления функционалов Т и Р получается 27г-периодическая функция

к'(в) = /лк(в —а) + socos(^o —0),

(6.12)

где h — периодическая функция, полученная на предпоследней стадии вычисления стандартного признака изображения. Однако в рассмот­ ренной системе координат изображение не обязательно имеет стан­ дартную форму. На предпоследней стадии функция (6.12) известна, но параметры аффинного преобразования д, a, SQ и фо не известны. Мы должны определить их. Мы также должны определить функцию h для распознавания изображения. Предположим, что функция (6.12) может быть разложена в ряд Фурье. Тогда у нас есть

ОО
к1 (в) = р, ^ М*) ( 6 -	а) + so cos (ф0 -	в) =
г = О
д ^ к ^ \ в	- а) + М (1)(0 -	«) + s0cos (ф0 + в) =
г^ 1	= /j,hL ( 6 — а) + р к ^ \ в - а) + so cos (фо - в),

10 Федотов Н. Г.

146	Гл. 6. Триплетные признаки распознавания образов

где hМ — i-я гармоника в разложении, т. е. ftW является линейной комбинацией cos (id) и sin (г#), г = 0, 1, 2,..., и функция h1 — проек­ ция функции h в подпространство, ортогональное первой гармонике. Следовательно, можем вычислить две функции

(h,)_L=

—a), pih,(l\ 6 —а) + socos(0 —фо).

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

Приведенное выше рассуждение частично иллюстрируется равен­ ствами (6.13) и (6.14). Пусть и —>и1- будет операцией исключения первой гармоники (см. выше). Пусть функционал Р имеет свойства (si) и (s2).

Если функционал © имеет свойства (П) и @и= (©и1 ) для всех допустимых функций и, то

П2 = 7е(/х)П1.	(6.13)
Если функционал 0 имеет свойства (sl.27r/n),	(s3) и &и = (0м-1),
то
П2 = П[ + a(modd 2тг/п).	(6.14)

Примеры функционалов. Будем считать, что параметры функ­ ционалов, приведенных ниже, не делают соответствующие формулы бессмысленными.

1. Инвариантные функционалы на конечных функциях, определен­ ных на числовых осях:

(a) Нм = А(м(ж)) dx для произвольной функции А; ясно, </?(«) =

= 1/от,
(b) Е и = | ип(х) dx; это частный	случай предыдущей формулы, и
мы имеем
7 (c) =	сп;

(c)количество экстремумов функции и;

(d)количество изменений знака функции и ;

(e)максимальное значение функции и;

(f)любой функционал, определяемый распределением значений функции и;

(g)длина области определения функции и;

(h)общая вариация функции и.

2.Чувствительные функционалы на конечных функциях, опреде­ ленных на числовых осях:

(i)средняя точка области определения функции;

6.2.Триплетные признаки, инвариантные к аффинным преобразованиям 147

(j)Ъи = | x\(u(x))dx/X(u(x)) dx, т. е. теоретико-вероятностные мо­ менты;

(k)Ъи = ArgMax (и);

(l) теоретико-вероятностная медиана.

3.Инвариантные функционалы на периодических функциях, опре­ деленных на числовых осях: подходящими являются примеры (a)-(h), если операции ограничены периодом функции (например, интегрирова­ ние выполняется по периоду);

(т)абсолютное значение коэффициента Фурье какой-либо гармо­ ники функции Х(и).

4.Чувствительные функционалы на периодических функциях, опре­ деленных на числовых осях:

(п) фаза какой-либо гармоники функции и.

Доказательства теорем А и В. Теорема В доказывается формулой (6.10). Теорема С доказывается формулой (6.13).

Далее, доказываем теорему А. Для прямой линии I (5.6) и (5.10) дают равенство

0 + (ex,e 2) (pl + tS ( 1 ) ) т =

= Р + (vx, v2) (p'l + (kt + b)S ( 0 ) Х(в'),

где, согласно (5.10) к > 0 и р', в' и b являются функциями от р и 9. Нужно сделать это соотношение более определенным, т. е. доказать, что условия теоремы А выполняются. Системы координат связаны равенствами (5.5). Пусть w обозначает вектор-столбец с координа­ тами w\, w2 . Тогда во второй системе координат последняя формула становится следующей:

w + A (pi + tS ( I ) ) Х(в) = (РЧ + (kt + b)S ( 0 ) Х(в').

Приравнивание термов, остающихся в этом равенстве при t = 0, дает

w + рАХ(в) = р'Х(в') + bS 0 ) Х(в')	(6.15)
A s { ^ ) x ( e ) = k S ( ^ ) x ( e ' ) .	(6.16)
Заметим, что к зависит только от в,
к = к (в) > 0.	(6.17)

Известно, что отображение sgn : М2\{0} —>S1 координатной плос­ кости без начала координат, с одной стороны, в окружность, определен­ ную формулой sgn(rA(#)) = А(6) для г > 0, с другой стороны, является гладким. Поэтому, формулы (6.16) и (6.17) дают

А(0') = sgn <?(-£) AS (|)А (0),	(6.18)
Х(в') = sgn (S ( - | ) AS ( | ) ) ~ ‘ Х(в),	(6.19)

ю*

148Гл. 6. Триплетные признаки распознавания образов

ивыражения в правых частях этих соотношений являются гладкими функциями от 9 € R. Следовательно, существует гладкое отображение

р: R —*• R, поэтому 9 в первом соотношении (а поэтому — и во втором) можно заменить на р{9).

Мы должны доказать, что производная отображения р положи­ тельна, и что функция р(9) —9 является 27г-периодической. Хорошо известно, что матрицу А с положительным определителем можно представить как А = S(a 2 )DS(a 1), где оц и а 2 — числа, и D(d\,d,2 ) — диагональная матрица с положительными диагональными элементами. Поэтому (6.16) можно записать как

DX	^ + 0	= к(9)Х ^—«2 + ~2 + P(@)j ■
Следовательно, получаем два равенства
U ^ tan (он + ^		+ 0	= tan ( - а 2 + ^	+ р(#)) >
( | )	c°t (а , + |	+ в )	= cot ( - « ! + \	+ т ) ■

Дифференцирование этих равенств легко доказывает, что производ­ ная отображения р{9) положительна для всех 9.

Теперь докажем, что разность р{9) — 9 является 27г-периодической функцией. Так как функция р является гладкой и строго монотон­ ной, (6.18) предполагает, что р(9 + 2тт) = р(9) + 2тгт дляданного в иположительного целого то. Предположение, что то больше едини­ цы, позволяет нам найти положительное значение а < 27т, такое что р(в + а) = р{в) + 27г. Согласно (6.19)

Х(в + а ) = sgn (S ( - 0 AS Х(р(в + а)),

где правая часть соответствует правой части в (6.19), а левая часть — не соответствует. Полученное противоречие доказывает, что наше предположение то > 1 не верно. Это показывает, что функция р удо­ влетворяет условиям теоремы А.

Рассмотрим равенство (6.15). Скалярное умножение обеих частей этого равенства на А(в') дает

(W,A(^))+P(A\W,A(0/)) = /O/;

Следовательно,		c{9)p + d{9) = р'.				(6.20)
Мы должны показать, что функция с{9) = {АХ{9),Х{9'))						положи­
тельна. Согласно (6.16)
к{е){АХ{9),Х{#)) =		(АХ(9), S ( - J ) АД Q ) А(0)) .				(6.2 1 )
Угол,	отсчитываемый	от	А(9) до S	^^0 А(9) в	положительном
направлении (против часовой			стрелки),	положителен	и меньше чем
7г. После	невырожденного сохраняющего ориентацию				преобразования

6.3. Применение теории триплетных признаков		149
угол между изображениями АА[в) и A S	А($), отсчитываемый

от первого до второго, положителен и меньше чем ж. Если второй вектор поворачивается в отрицательном направлении на ж/2, то угол можно включить в открытый интервал (—7г/2, ж/2). Поэтому, выраже­ ние (6.2 1 ) положительно.

Независимо от этого геометрического соображения прямое вычис­ ление (6.21) дает det А.

Обозначим рассматриваемый признак в первой системе координат как П[. Тогда (6.17) и (6.20) предполагают

Пт = П (0, ех,в2 , ©, Р, Т, Д) =

= © о Р о Т (F о L(Р, vi, v 2,p(6>), с(6)р + d(6), k(6)t + b(p, 6))).

Во второй системе координат определим функции

f(0,p,t) = F(L(P, v i, v2, #, />,i)), g'{0,p) = T f(e,p,t), h'{e) = v g{e,p), п 2 = © В Д .

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

П! = 0 о Р о Т(/'(р(0), с(в)р+ d(6), h(e)t + b(p, в))) =

= 0 ОР ( д ' Ш , c(e)p+d(e))) = 0 (Л'(р(0))) = п 2, что доказывает теорему А.

6.3.Применение теории триплетных признаков

враспознавании биологических объектов

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

Описание вычисления признаков. Рассмотрим прямую, опреде­ ляемую уравнением х cos +у sin в = р. Направление прямой задаётся вектором с координатами (—sin#,cos#). Центр декартовой системы координат расположим в центре изображения. Параметр р, в отличие от обычно принятой записи, может принимать также и отрицательные