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

2.5. Сканирование по случайным криволинейным траекториям

61

Если проинтегрировать правую часть равенства (2.48) по всем значениям Со, С\, 7 , то получится

Lo L| 2ж

dC() d,C\ sin7 d j = 4L\L Q.

При интегрировании левой части каждое положение кривой Г[ учитывается столько раз, сколько она имеет точек пересечения с кри­ вой Го. Следовательно,

n d K = ALILQ,

(2.49)

где интегрирование распространяется на все возможные положения кривой Г], а в есть число точек пересечения Г[ с Го. Это соотно­ шение (2.49) известно в геометрии как формула Пуанкаре.

Рассмотрим следующий пример. Предположим, что подвижная кри­ вая Г1 есть окружность радиуса г. Выберем ее центр за начало коор­

динат (х ,у ) подвижной	системы. Тогда для	каждого положения х, у
при изменении угла ip	от 0 до 2к число	п остается неизменным

(это свойство использовано в рассмотренном ниже устройстве). Таким образом,

n d K = ndx f\dy A dip 2к ndx A dy

и, применяя формулу Пуанкаре, получаем 1 ndx A dy = 4rLo,

где интегрирование распространяется на всю плоскость.

Отметим, что, использовав формулу кинематической плотности (2.47), можно получить выражение, связывающее значения кривизн ко и к\ в каждой точке пересечения кривых Го и Г) с полными кривизна­ ми х(Го) и x(Ti) этих кривых:

р П
Y , { h U h ) i dK = 4х(Г0)х(Г,).	(2.50)

Приведенные выше свойства пересечений кривых интересуют нас в связи с нашим стремлением применить при распознавании объектов сканирование по случайным криволинейным траекториям. Такой вид сканирования реализован в рассматриваемой в приложении Б элек­ тронной системе распознавания образов (см. [41]).

Следует обратить внимание на одну теоретическую проблему, воз­ никающую при проектировании распознающих систем со сканирова­ нием по случайным криволинейным траекториям. Легко осуществить равномерное распределение сдвигов сканирующих кривых. Однако это означает, что в таких случаях мы применяем в системе неравномерное

1 И з это го в ы р аж ен и я	с л е д у е т ф орм ула Lo =	J п dA, которую п р и н и м а ­
ю т за о п р ед ел ен и е д л и н ы	Lo то ч еч н о го м н о ж ес тва	с п л о тн о стью dA = dx A dy.

62	Гл. 2. Траектории сканирования

случайное распределение кривых, ибо для равномерного распределе­ ния кривых на сетчатке необходимы одинаковые веса для координат любой точки А, связанной с кривой, и для любого угла ориентации кривв1х.

Итак, посколвку в данном случае существует инвариантность толь­ ко относительно сдвигов или трансляций кривых, кинематическая плотность примет вид:

К* = S(p) dx Ady A dp.

С её помощью можно вычислить геометрические вероятности, слу­ жащие признаками распознавания, для таких неравномерно распре­ делённых кривых. В целом, следует подчеркнуть, что работа с кри­ волинейными развёртками сопряжена с возрастанием геометрических трудностей. Детально эти проблемы можно уяснить при рассмотрении электронной системы распознавания образов, основанной на скани­ ровании по случайным криволинейным траекториям, приведённой в приложении Б (также см. [43]).

Пересечение областей. Рассмотрим фиксированную область Ко, представляющую собой конечную часть плоскости, ограниченную ко­ нечным числом ориентированных замкнутых кривых, не имеющих двойных точек. Обозначим через хо полную кривизну области, через So — ее площадь. Далее, пусть К\ — подвижная область площади Si, a dK\ — кинематическая плотность для множества положений этой подвижной области.

Свойства пересечений определяет интеграл

/dA A dK\,

Ае к , п к 0

вкотором А {х,у) — точка, определяющая положение подвижной облас­ ти К\\ dA = dx Ady — плотность множества точек А; интегрирование

осуществляется по всем возможным положениям области К\ и точек А в области пересечения К\ и Ко.

Зафиксируем сначала положение точки А. Тогда, применяя форму­

лу (1.25) и интегрируя,		получаем
I	dA	dK i = 2TTS I	dA = 2TTS IS0.
А е к 0		A e K ,	A € K 0

Можно фиксировать в другой последовательности: сначала положе­ ние области К\. Тогда результат интегрирования таков:

I	dK\	dA	SQI dK i,
K\C\KQ^ 0		A(EK\C\KQ

где Soi — площадь пересечения K Q и K\.

Из объединения двух последних равенств получается интегральная формула

S0i dKi = 2irS\S0.

64	Гл. 2. Траектории сканирования

образом на плоскость так, что она пересекает K Q. Определим веро­ ятность того, что К 2 пересекает и if]. На основании (2.52) искомая вероятность

р _ 2TT(SI + S2) + L\L2

27г(5о+ S2) + LQL2

б) Точка А и выпуклая область К\ случайно размещаются на плос­ кости так, что А е К 0 и K Q (~\K\ ^ 0 . Найти вероятность того, что точка А лежит на пересечении областей К 0 П К\ ф 0 .

Вероятность этого геометрического события

	р	2^ !
	2Tr(50 + Si) + LoLr
	в) Прямая G и выпуклая область К\ выбираются случайным обра­
зом на плоскости так, что они пересекают K Q. Найти вероятность того,
что G П К\ П K Q ф 0. Искомая вероятность
	2TT(SQL 1+ S 1L0)
	LQ [27г(50 + 5 I ) + LQL\] '
от	Вышерассмотренные формулы (2.51) и (2.52) выражают интегралы
	площади 5oi и периметра L Q\	пересечения K Q\ = K Q П К\	облас­
тей	K Q и К\, распространенные	на всевозможные положения	облас­
ти К\. Еще полнее охватываются		свойства пересечений, если	учесть

полные кривизны этих областей %о и Х\ и полную кривизну их пере­ сечения хоь Связь этих величин отражается интегральной формулой

XoidKi = 2тг(5'оХ1 + <51X0 + LQL\).	(2.54)
К\С\Къф&
Она известна в стохастической геометрии как основная формула
Бляшке [31].	то их
В частном случае, если K Q и К\ — выпуклые области,
пересечение KQ\ — также выпуклая область и, следовательно,	хо =

= xi = Xoi = 2тг. Для этого случая формула Бляшке совпадает с фор­ мулой (2.52).

Пусть, например, К\ есть круг радиуса г. В качестве точки А(х,у), фигурирующей в определении кинематической плотности и рассмат­ риваемой при выводе (2.51), можно взять центр этого круга. Тогда

получится, что	|	dK\ = 2 д	j	dA и формула (2.53) дает
	К\ П к оф 0		к,[~]Коф 0

результат

dA = So + Lor + 7гг2.

К\Г\Ко^0

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

2.5. Сканирование по случайным криволинейным траекториям

65

(г = 1 ,2 ,... ,т), общей площадью 5о> периметром Lo и полной кри­ визной х = 2ттгп (так как малые области Щ, образующие текстуру, тоже выпуклые, их полные кривизны равны 2ж). Пример такой области Ко дает модельное изображение текстуры на рис. 2.7, г. Допустим, что область К\, которой сканируют это изображение Ко, ограничена кривой без самопересечений так, что полная ее кривизна х = 2д. Тогда справедливо соотношение

ndK \ = 2ir(So + mS\) + LQL\,

(2.55)

К\Г\Коф0

где п — число множеств Щ, пересекающихся со сканирующей обла­ стью К\.

В частности, если исследуемая текстура Ко состоит из точек, то, учитывая, что в этом случае So = 0, Lo = 0, получаем

n d K 1= 2TrmSi.

Здесь п — число точек из Ко, попавших в К\, и интегрирование распространяется на всю плоскость.

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

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

ГЛА ВА 3

ГЕОМЕТРИЧЕСКИЕ РЕШЁТКИ И ПРИЗНАКИ РАСПОЗНАВАНИЯ

3.1. Архитектура распознающих устройств с позиций стохастической геометрии

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

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

Существование отмеченной во Введении тенденции меньшего инте­ реса к исследованию признаков распознавания, к форме, в какой дол­ жны быть представлены первичные описания, в сравнении с большим интересом к решающим процедурам привело Международную конфе­ ренцию по методологии проблем распознавания образов (Гавайский

3.1. Архитектура распознающих устройств

67

университет, США, 1966) к выводу, что общей теории выбора при­ знаков распознавания, возможно, нельзя построить и этот вопрос решается интуицией конструктора распознающей системы. В пуб­ ликациях, посвященных рецептивной системе, хотя и не утверждается это в явном виде, но они, как правило, характеризуют инженерный и технологический аспекты ее построения. Немногие исследования о вы­ боре признаков относились, в основном, к специальным задачам стати­ стического распознавания, тесно примыкающим к моделям статистики, и требования к признакам в этих работах получены, условно говоря, в отраженном свете от решающих правил. В этих задачах признаки являлись как бы производным элементом от априорно принятых ал­ горитмов классификации, причем большую роль играли устойчивость, повторяемость статистических характеристик, что обычно имеет место лишь для узкого класса объектов.

У читателя, не сталкивавшегося с проектированием распознающих систем, может возникнуть вопрос, не отражает ли скудость исследо­ ваний о признаках распознавания отсутствие проблем в этой сфере. Для того чтобы показать, что проблемы есть, рассмотрим следующий пример. Пусть имеется некоторая распознающая система. Предполо­ жим, что её рецептивная подсистема представляет собой рецептивную матрицу X , каждый элемент которой выдает двоичное число. Для удобства последующих рассмотрений будем полагать, что элемент хц, на который попало изображение, выдает +1, все остальные элементы выдают —1. Таким образом, под изображением объекта будем понимать множество элементов хц матрицы X , на выходе которых имеется число +1.

Пусть решающая подсистема реализует решающую процедуру с помощью разделяющей гиперплоскости. Это означает, что неизвестный объект относится к тому или иному образу в зависимости от того, по какую сторону от гиперплоскости находится точка, соответствую­ щая объекту в многомерном пространстве. К этому типу решающих процедур сводятся многие методы распознавания: корреляционный, аппроксимации по методу максимального правдоподобия, дискрими­ нантный анализ, по расстоянию до средних, по правилу АндерсонаБахадура и т. д. Таким образом, следует подчеркнуть, что в качестве примера выбран не какой-нибудь «экзотический» примитив, а весьма распространенный, особенно при распознавании образов статистиче­ ской природы, линейный классификатор.

На рис. 3.1 пояснено действие линейного классификатора для двух образов. Через Н обозначен след гиперплоскости (в двумерном прост­ ранстве гиперплоскость вырождается в линию). Линейная решающая процедура заключается в том, что неизвестный вектор ж*, соответству­ ющий распознаваемому изображению объекта, относится к классу или образу А тогда, когда его проекция wx; на нормированный весовой вектор w больше порога у. Поэтому любой вектор, расположенный с той же стороны гиперплоскости Н, что и вектор х*, должен быть отнесен к образу А, в противном случае — к образу В.

5’

3.1. Архитектура распознающих устройств

69

Заметим, что при выбранном нами кодировании двоичного выхода элементов матрицв1 X значениями хц = ±1, запись этих условий упро­ щается. Для первого образа А

w (2+a)(l +b) - W(l+ a)(2+b)	>	V ~	w (l +a)(l+Ь) +		W(i+a.)(j+b)-
					ij¥={ П.12.21)
Аналогично для образа В получаем
^ ( 1 + а ) ( 2 + Ь ) - ™{2+а){\ + Ь)	<	V ~	^ ( 1 + а)(1 + Ь ) +		^	w (i+a)(j+b) •
					ij={ 11,12,21)
Если обозначить
W*(a,b) = г) - W(i+a)(i+fe) +				^ 2	W(i+a)(j+b),
				i m 11.12.21)

тогда для всех параметров преобразования а и b получим условие принадлежности к образу А:

w ( 2 + o ) ( l + b ) - W ( l + a ) ( 2 + 6 ) > | w * ( a , 6 ) | .

В силу того, что

|w*(a, 6)| >0,

для всех а, Ъ получаем

W (2 + a ) ) ( l + b ) > И>(1 + 0 )(2+ ь ).

Это означает, что весовые коэффициенты w вдоль диагонали, имеющей положительный наклон, монотонно уменьшаются по мере продвижения сверху вниз. Но поскольку в матрице осуществляется тороидальное соединение, то необходимо признать, что имеет место следующее соотношение: иу,- > Wij. Оно является строгим неравен­ ством. Так как это невозможно, то, следовательно, мы приходим к противоречию, которое опровергает изначальное предположение об инвариантности распознавания в рассматриваемой в нашем примере системе. И в целом, необходимо признать, что систему, осуществ­ ляющую линейную решающую процедуру, невозможно настроить таким образом, чтобы она давала инвариантное распознавание по первичным описаниям изображений объектов.

Стохастическая геометрия дает ориентир в проблеме выбора при­ знаков. Согласно ее выводам описания изображений, поступающие в решающий блок, должны быть представлены в виде геометрических инвариантов. Таким образом, подобно тому, как в теории моделиро­ вания обрабатываемая информация должна удовлетворять критериям подобия объекта и модели, согласно стохастической геометрии инфор­ мация, по которой осуществляет распознавание решающая подсистема распознающего устройства, должна быть представлена в виде гео­ метрических инвариантов. Многочисленные формулы предшествующей главы являются достаточно полным собранием таких инвариантов. Часть из них реализована в системах, рассмотренных в качестве примеров, однако следует подчеркнуть, что такое же применение может найти каждая из формул главы 2, так как каждая из них связывает инвариантные признаки распознавания.

70 Гл. 3. Геометрические решётки и признаки распознавания

Итак, центральная проблема при выборе признаков заключается в том, что они должны быть инвариантными относительно группы движения твердого тела, ибо «автоматически», как мы видели, инвари­ антность распознавания по любым первичным описаниям не случается. В силу этого распознающие устройства и системы наряду с рецептив­ ными и решающими подсистемами содержат и третью подсистему, ко­ торую называют по-разному — либо подсистемой сжатия данных, либо подсистемой предварительной обработки, либо подсистемой преобразо­ вания описаний, но общая её функция заключается в формировании инвариантов для решающей подсистемы. Это находит отражение и в обобщенной архитектуре распознающих устройств и систем; она, как правило, трехзвенная (см., например, обзор [9]).

С позиций стохастической геометрии можно упростить трехзвенную обобщенную архитектуру и исключить промежуточный блок преобра­ зования описаний, который по объему оборудования занимает до 40% всего распознающего устройства (по-видимому, можно считать, что настолько же приблизительно из-за него снижается быстродействие устройства). Такое упрощение осуществимо, если производить скани­ рование объекта так, как это было описано в главе 2, ибо при этом одновременно формируются инвариантные признаки распознавания, т.е. происходит совмещение функций рецептивного блока и блока пре­ образования описаний. Можно предложить иной вариант, также приво­ дящий к упрощению структуры распознающего устройства и исключе­ нию блока преобразования описаний. Он основан на проецировании изображения через специальный дискретный оптический фильтр со случайными параметрами [42]. В этом случае на входе распознающего устройства формируется дискретная случайная сетчатка, в отличие от непрерывной сетчатки предшествующих устройств, представлявшей собой сканируемую часть плоскости изображения. При разработке дискретных оптических фильтров со случайными параметрами при­ менялся математический аппарат стохастической геометрии. (Пример такой электронной распознающей системы приведён в приложении В).

При проектировании программных систем распознавания образов этот же эффект можно получить, сканируя изображения геометриче­ скими решётками (см. главы 5-12).

Кроме того, геометрические решётки нас будут интересовать в связи со специальным классом задач распознавания образов, существу­ ющих в геологии. Если до сих пор мы преимущественно рассматривали задачи распознавания конкретных изображений, предъявленных для распознавания, то при решении геологических задач мы лишь предпо­ лагаем существование геологического объекта и на основе косвенных данных геофизики, геохимии и пр. можем представить его форму. Для решения задач распознавания в подобных условиях важным инстру­ ментом зондирования и восприятия объектов являются решётки гео­ физических исследований, математической моделью которых служат геометрические решётки фигур, областей, кривых. Эти математические модели рассматриваются в последующих параграфах настоящей главы.