Анисимов Б.В., Курганов В.Д., Злобин В.К. - Распознование и цифровая обработка изображений (1033973), страница 9
Текст из файла (страница 9)
Пусть число таких пар равно п,. Отметки зон 5! и З„не входящие ни в одну из этих пар, исключаются из дальнейшего рассмотрения. Число переборов отрезков на этом этапе равно п,п,. Э т а п 2. На данном этапе алгоритма анализируется содержимое зон 3„3, и 3,. Для этого вычисляются величины %з и=] г1»з "~зч,] — з.!.
%»з1~=] гэз гэз1~] — за«: (т й= =1,2, ..., й«, )«=1,2, ... «и!). (1.29) где пэ — число отметок в зоне Зэ; остальные обозначения имеют тот же смысл, что и в (1.28). °, ; Предположим, »гго число троек отметок ((х»„,.у»~) (хз1 у!1)* (хзи ''')], удовлетворяющих соотношениям (1.29) одновременно, равно ~'. Исключим из рассмотрения отметки зон 5„8„5„не входящие ни „одну из них.
Оставшиеся отметки в зонах 5„5, и 3, претендуют на ветствие точкам (х„у,), (х„у,) и (х„у!) в порядке упоминания. ' ело переборов треугольников на этом этапе равно п,п,. Аналогично выполняются и последующие этапы алгоритма. Описы- ' емая процедура продолжается до такого этапа 1, на котором фиксиется п! = 1 (где и» вЂ” число (1+ 1) -угольников, построенных на ' е содержимого зон 5„5„..., Б»~! и совпадающих с г -точностью с урой, образованной опорными точками (х>, у>) (1' = 1, 2,..., 1+ !)).
результате становятся известными координаты точек (х>, у>) (1 = 1, 2,..., '1 + 1) кадра К„, отвечающие этим опорным точкам, что пояет рассчитать параметры взаимного сдвига кадров К„и К„+, и акончить их идентификацию. Общее число переборов многоугольни»-! ов при этом составит п»п! +,~„п! п„, После п — 1 этапов можно «=! олностью опознать опорный узор. Опорные точки в кадре К„+, не должны выбираться на его перифеи, т. е. необходимо, чтобы ]Т] ( )!»'»'2 — г (где г = х, у; 1 = 1, 2, 1., п). Желательно также попарное непересечение зон в.кадре К„, я чего расстояния между вершинами узора должны превышать 2г .
В процессе опознавания узора возможно появление такой ситуации, огда ни одна из точек некоторой зоны 3> не может быть поставлена в ветствие вершине (х>, у>), отвечающей ей (упомянутая вершина яв- яется помехой или величина г выбрана неудачно). Тогда следует исючить из рассмотрения отметку (х>, у>) и, следовательно, зону 3> ли скорректировать параметр гз. Наконец, по окончании (и — 1)-го ага опорному узору может отвечать в кадре К„несколько и-уголь- иков. В этом случае целесообразно увеличить число опорных точек п ли заменить исходный узор частично или полностью. Описанному алгоритму следует отдать предпочтение при его сопоавлении с алгоритмами, базирующимися на прямом переборе, по ебуемым для их реализации вычислительным затратам. Сравнительная оценка операционных затрат.
Действительно, в слу- ае применения воино-комбинаторного алгоритма число операций «« — 1 авнения вида (1.28) составит ]Г,„= п,п, + ~ »п! ! п»+„при прямом » 2 е переборе число ]г этих операций значйтельно больше, даже если еть в виду более экономичные алгоритмы, чем алгоритм, при котом п-угольник, идентичный опорному узору, отыскивается в кадре „среди М„!1(̄— п)! различных п-угольников. Один из таких ал«« — ! "Горитмов дает 1» = (̄— 1)М„/2+,~~ »п» ! (̄— !) (где и," !— «с 2 37 18Л« й 8Лгя "зк=, + (л — 2), )в „= Л (Л вЂ” 1) 2 +2Л (л — 2)— — л (л — 1) +2 Л= Лз+ Л Рнс. 1.13. Идентификация точечных изображений с помощью воино-комбинаторного алгоритма: а — ваавмяос расдоаожсава кадров К в К .; б — раамащааас »»+)' аом Б) в совмещенном кадре; «в обабщаааая аоаа 5 (а уарудаав.
вом масштабе) образуют случайное пуассо постыл Х, вычисляется по Заключение (1.30) 38 ) — число (1 — 1)-угольников, найденных в кадре К» на (1 — 1)-и Шаге). Здесь член (̄— 1) М„ /2 соответствует числу отрезков, соединяющих отметки в кадре К„и совпадающих с гз -точностью с пер- ла вой стороной опорного узора. Математические ожидания случайных величин и), и л," ) близки к единице, а их дисперсии малы.
Средние значения числа отметок в зо- нах и) (1 = 1, 2,..., п) одинаковы. Если а) к - у к тому же положить, что на каждом(-м шаге сопоставляемых алгоритмов для Кд целей сравнения используются в качестве эталонных лишь расстояния гы и гс х ь то средниезначения величин )гав ус и (г могут быть найдены из соотноше- ний где Л, и Л вЂ” число отметок от объектов и помех в каждом из идентифицируемых изображений; ))1 — размер стороны кадра в элементах. Обычно значения )гам и )г„таковы, что 'р',в (( )г„. Оценка вероятности правильной работы воино-комбинированного алгоритма, Оценим теперь число опорных точек и', обеспечивающее достаточно низкую вероятность Р появления в кадре К» хотя бы одного ложного и-угольника, с г -точностью совпадающего с опорным узором.
Точная оценка вероятности Р„затруднительна. Ее приближенная оценка, базирующаяся на предположении, что координаты отметки кадра есть независимые случайные величины, равномерно распределенные в интервале [0,1) (за единицу измерения выбрана длина стороны кадра), т. е. отметки новское поле точек с постоянной плот- формуле Рл мв 1 — ехр ( — 4Лл г' (г )2)ага ))). ,"'' Вероятность Р зависит от числа вершин и опорного узора, плотти Л отметок в кадре К„, максимально допустимой величины взаим''ого сдвига кадров и точности сопоставления расстояний г, На практике для получения достаточно высокой вероятности прального опознавания в кадре К„опорного узора необходимо выполие 2 — 3 шагов алгоритма, т.
е. следует выбрать и = 3 —:4. При этом роятность Р— весьма малая величина, т. е. математические ожида' я и действительно близки к единице, а их дисперсии малы. яд) д а плот- Модификация воино-комбинаторного метода. В случае когда п ость отметок от объектов и помех в кадре невысока, а также при неьших взаимных сдвигах идентифицируемых кадРов представляет нтерес следующая модификация воино-комбинаторного метода. Построим обобщенную зону 3 (рис. 1.13, в), представляющую собой 'о вмещение зон 3, 5,..., З„вместе с их содержимым (рис. 1.13,, ).
з " и иг ка ов Поскольку имеет место лишь плоскопараллельный сдвиг дР К и К, отметки кадра К, соответствующие вершинам опорного »»+1 »в ( ис.1.13, в ,узора, окажутся в зоне 3 в г -окрестности друг от друга (на рис.. ,они совпадают, поскольку влияние нелинейных искажений и других факторов, определяющих значение г, не учитывается). Таким образом, нахождение параметров кю у, взаимного смещения кадров можно свести к поиску точки обобщенной зоны, гв-окрест',ность которой содержит максимальное число отметок (математическое ,ожидание этого числа равно и). Вероятность того, что та же ситуация ; может иметь место в г -окрестности ложной точки зоны З,мала при введенных выше условиях, особенно при и ) 3 —; 4. На практике "поиск представляющей интерес точки может быть выполнен, например, следующим образом. Реально имеет место дискретизация плоскости , кадра и, следовательно, зоны 5.
«Просматриваяз последнюю апертуРой РазмеРом гз, Х гв, нетРУдно опРеделить такое положение этой апертуры, при котором она накрывает наибольшее число отметок обобщенной зоны. Усреднение их координат, взятых в системе, связанной с центром зоны Я, даст искомые значения х„у,. Максимальное число шагов поиска ограничено при квадратной зоне 8 величиной г' .
Описанный алгоритм можно интерпретировать также и как модификацию рассмотренного выше квазикорреляционного итерационного алгоритма. Сравним рассмотренные методы идентификации точечных изображений. Метод трасс наиболее вффективен прн невысоком уровне помех, небольшом взаимном сдввге идентифицируемых изображений и малых нелинейных вскзжениях. В противном случае он существенно пронгрывает в отношении затрат машинного времени и памяти, а также полноты н надежности идентификации как воино-комбинаторному, так н корреляционным методам.
Наиболее благоприятные условия его использования имеют место обычно в первой постановке задачи '. идентификации точечных изображений, когда последние регистрируются одним и тем же инструментом наблюдения точечной картины в процессе перемещения Поеледнего в пространстве по некоторой траектории, причем моменты регистра- 39 ции чсоседних» по времени изображений могут быть выбраны сколь угодно близкими.
Зонно-комбинаторный метод в отличие от метода трасс сохраняет высокую эффективность и прн значительных взаимных сдвигах кадров. Однако его помехозащищенность также недостаточно высокая. Наличие среди отметок опорного узора помех резко увеличивает операционные затраты, снизкает надежность метода и ведет к потере точности совмещения изображений. Наибольшую эффективность при значительных помехах и взаимных сдвигах кадров обеспечивают корреляционные методы идентификации. Однако если упомянутые условия обеспечены, то эти методы проигрывают по быстродействию методу трасс и особенно воино-комбннаторному методу.
Следует также отметить, что идентификация отметок при воино-комбинаторном'методе выполняется лишь частично, а после использования корреляционых методов не имеет места вообще. Поэтому по окончании работы каждого из алгоритмов, базирующихся на этих методах, реализуется совмещение идентифицируемых кадров, в результате чего одноименные отметки оказываются в непосредственной близости друг от друга, а затем осуществляется идентификация упомянутых отметок. Последняя может быть выполнена практически на основе метода трасс. ГЛАВА й МЕТОДЫ ПРЕДВАРИТЕЛЬНОЙ ОБРАБОТКИ ПЛОСКИХ ИЗОБРАЖЕНИЙ ПРОСТРАНСТВЕННЫХ ОБЪЕКТОВ й 2.1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
