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

воспользоваться биномиальным законом распределения, в результате получим

Здесь применен результат (2.3), согласно которому вероятность того, что случайная прямая, пересекающая K(t), пересечет Ко, равна отношению длин выпуклых оболочек Ко и Kit). Отрезок прямой Ко можно рассматривать как вырожденный случай выпуклого множества, длина границы которого равна 21. С учетом этого вероятность рав­ на 21/L, она и фигурирует в формуле (2.34).

Рассмотрим теперь предельный случай, когда K it) распространяет­ ся на всю плоскость и число случайных линий сканирования возраста­

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

Из этого факта в соответствии с теорией вероятностей вытекает,

а это есть среднее число вершин на единицу площади.

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

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

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

Если сфера имеет единичный радиус, а число секущих плоско­ стей N, то при N = 1 число различных областей равно 2, при N = =2 оно равно 4, при N = 3 равно 8. Применив метод математической

числу высекаемых дуг окружностей (соответственно 4, 12, 24). По индукции получаем, что для любого N оно равно 2N (N — 1). Отсюда при увеличении N среднее число сторон будет равно пределу отноше-

4N (N —1), а не 2N (N —1), поскольку каждая дуга является стороной для двух многоугольников и должна учитываться дважды. Средняя площадь в пределе стремится к 4TT/ N 2, общий периметр 2 + N (N —1) областей равен 4TTN, поэтому средний периметр области в пределе стремится к 4лN. Далее, при больших N рассматривается распреде­ ление областей в малом круге радиуса R на поверхности сферы. На эти области круг рассекается большими окружностями, число которых равно NR. Для упрощения анализа предполагается, что эти области также являются кругами. Затем находят среднюю площадь MQ обла­ стей на плоскости, образованных пуассоновским полем с плотностью dp Add. Она равна 4/лА2, а средний периметр М и равен 4/А.

В стохастической геометрии рассматриваются полученные вероят­ ностными методами средние значения и некоторых других параметров случайных многоугольников, образующихся при пуассоновском линей­ ном процессе [17, 31, 105].

2.4.Развёртка в виде случайных отрезков прямой

ипризнаки распознавания

Сканирование случайно ориентированными и случайно располо­ женными в поле изображения отрезками прямой фиксированной дли­ ны (называемыми для простоты случайными отрезками) оказывается информативнее, чем сканирование случайными линиями. При скани­ ровании случайными линиями единственный признак — интеграл от

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

Пересечение отрезка с геометрическими элементами. Рассмот­ рим пересечение ориентированного отрезка К прямой с выпуклым множеством. Определим меру множества отрезков длиной I, пере­ секающих выпуклое множество Ко, площадь которого равна So, а периметр До. Для этого применим формулу (1.32) для кинематиче­ ской плотности dK. Зафиксируем прямую G как опору, на которой находится отрезок К, обозначая через g длину хорды, высекаемой множеством Ко на прямой:

Переход от последнего интеграла в этой цепи равенств к оконча­ тельному результату осуществляется в соответствии с формулами (2 .1) и (2.3).

Рассмотрим вырожденный случай, когда выпуклое множество Ко представляет собой отрезок прямой длины /о; периметр такого мно­ жества будет равен 21Q. Применяя вышеприведенную формулу, получа­ ем меру

Этот результат можно распространить на ломаную линию. Если Ко — ломаная линия, длина которой До. то, применяя последнюю формулу для каждого ее звена и складывая результаты, получаем

где п — число звеньев ломаной К 0, которые пересекаются с К при данном положении отрезка. Определим меру множества отрезков дли-

Подставив сюда вышеприведенное значение S и взяв интеграл, получим

Этой формуле можем придатв вероятностный смысл, если рассмотретв случай, когда отрезок длиной I, пересекающий угол а, пересекает и стороны болвшего угла [3 с общей вершиной в точке О, расположен­ ною вне угла а. Вероятности этого геометрического события

1 + (-7Г- ( 3 ) ctg 1 3

(2.42)

1 + (ж—a) ctg а

Рассмотрим сканирование случайными отрезками выпуклого мно­ гоугольника. Предположим, что Ко — выпуклый многоугольник, име­ ющий углы оу при вершинах, площадь SQ, периметр LQ. Обозначим через К ориентированный отрезок длиной /, который не может пересе­ кать две несмежные стороны многоугольника Ко.

Далее, пусть /х* (7 = 0,1,2) есть мера множества положений отрез­ ка К, в которых он имеет г общих точек с контуром многоугольника Ко (Мо — мера множества отрезков, размещенных внутри Ко). Тогда пред­ шествующие формулы (2.37), (2.39) и (2.41) можно записать в виде

Mo + Mi + М2 —27rSo + 2/Lo,

Mi Т 2м2 = 4ILQ,

М2 = (/2/ 2) ^ [ 1 + (Tr-oy)ctg оу].

°ч

Из этих уравнений получаем

Mo = 27rS'o - 2ILo + (l2/ 2 ) ^ 2 П + (^ - ay) ctg ay],

(2.43)

М2 = (/2/ 2 ) ^ [ l + (д —ay) ctg ay].

Для приложений к распознаванию образов нас будет интересо­ вать вероятностный смысл этих соотношений. Чтобы выявить его, рассмотрим случай, когда многоугольник Ко располагается внутри выпуклой фигуры Ф, имеющей площадь S<p и периметр Ьф (роль такой фигуры играет сетчатка распознающей системы). В такой ситуации

вероятность пересечения случайным отрезком К длины I выпуклого многоугольника

(2.44)

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

В заключение рассмотрим пересечение ориентированного отрезка длиной I с параллельными линиями на плоскости. В главе 1, пред­ лагая идею распознающей системы, мы оттолкнулись от этой задачи, называемой также задачей Бюффона об иголках. Итак, напомним ее постановку: иголка (т. е. ориентированный отрезок длиной /) бросается случайно на плоскость, на которой начерчены параллельные прямые на единичном расстоянии друг от друга. Требуется определить вероят­ ность того, что иголка пересечет эти прямые. Рассмотрим случай, когда I < 1. Это означает, что возможно только одно пересечение. Обозначим через х расстояние от центра иголки до ближайшей параллели и через 9 угол, составленный иголкой с этой параллелью. Величины х и 9 полностью определяют положение иголки. Тогда, поскольку случайное бросание означает, что х распределена равномерно на (—1/2, 1/2) и 9 распределена равномерно на (0,27г), искомая вероятность

2тг

Если иголка бросается N раз и при п бросках получается хотя бы одно пересечение, тогда Р = n N ~ l является несмещенной оценкой для Р с дисперсией N ~ lP( 1 —Р).

Можно рассматривать вероятность того, что брошенная случайно иголка пересечет прямоугольную решетку, образованную двумя мно­ жествами параллельных линий, пересекающих друг друга под прямым углом. Если линии разделены промежутками а и Ь и I < а, I < Ъ, то

вероятность того, что иголка пересечет, по крайней мере, одну прямую,

При Ъ—>оо получаем известный результат для вероятности пересе­ чения параллельных линий одного множества 21/жа.

Задача Бюффона обобщена на случай бросания иголки в трех­ мерном пространстве, в котором размещено бесконечное множество параллельных плоскостей на единичном расстоянии друг от друга. Пусть I < 1. Считая, что ось координат направлена перпендикулярно плоскостям, применим полярные координаты для определения направ­ ления иголки. В этих координатах вероятностным элементом является

47г- 1 sin в dO dtp. После интегрирования по <р его можно записать как (l/2)d(cos0). По этой причине длина проекции lz иголки на ось, пер­ пендикулярную плоскостям, равномерно распределена на (0,1). Так как положение проекции случайно, то вероятность пересечений для всякой данной ориентации равна lz, а это после усреднения по распределению ориентации дает для полной вероятности пересечений значение 0,5/.

Рассмотренные теоретические положения о свойствах пересечений отрезков и выпуклых фигур на плоскости можно распространить на случай пересечения тел отрезками в трехмерном пространстве. Это да­ ет возможность делать выводы о телах на основе свойств пересечений. Приведем в завершение данной темы одно из таких положений. Мера множества отрезков К длиной I, пересекающих выпуклое тело Ко,

y ( K n K o = 0) = 2n2(4Vo + lSo),

где Vo — объем и 5о — площадь поверхности тела.

Приведенные теоретические положения применены при построении распознающих систем, которые рассматриваются ниже в главе 12 и приложении А.

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

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

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

Пересечения кривых. Рассмотрим ситуацию, когда объекты пред­ ставляют собой ломаную линию Гд длиной I/O, а подвижная кривая, случайным образом брошенная на плоскость и пересекающая объект, также есть некоторая m-звенная ломаная Г[ длиной L\. На основании соотношения (2.39), примененного к каждому звену ломаной Гь

Здесь п — общее число точек пересечения ломаных Го и Г), инте­ грирование ведется по всем возможным положениям Г). Возможность сложения предшествующих формул для каждого звена следует из того, что на основании свойства инвариантности кинематической меры относительно выбора подвижной системы координат (см. § 1.2) можем выбрать одну и ту же систему координат для всех звеньев k (i = = 1 , 2 , ... , то).

Рассмотрим пересечение объекта со случайными кривыми. Пока­ жем, что формула (2.47) носит универсальный характер и применима к кривым более общего класса, чем ломаные линии. Предположим,

имеется некоторая фиксированная спрямляемая 1 кривая Го длиной Lo, образованная конечным числом дуг, имеющих касательную в каждой точке. Будем полагать, что в некоторой системе координат (0 ,х,у) она определяется уравнениями

х = х(С0); у = у(С0),

где параметр Со является длиной дуги кривой Го.

Обозначим через Г[ подвижную спрямляемую кривую, задаваемую

где С\ — длина дуги Г[.

Для анализа пересечений наиболее удобной формой кинематиче­

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

Эта формула очень полезна для приложений. Из нее, в частности, следует, что вероятность того, что угол между кривой Го и случайной

Спрямляемая кривая —это кривая, имеющая конечную длину.