Анисимов Б.В., Курганов В.Д., Злобин В.К. - Распознование и цифровая обработка изображений (1033973), страница 37
Текст из файла (страница 37)
АК' с — — 0,5 Х ,',, Х Ж ! 1„ш!и = 0,5 пип ()«' ! !и). Тогда элемент столбцовой матрицы будет определяться как рпы = К »„1,— с!)«!мс Э т а п 7. На данном этапе алгоритма вычисляется квадратная симметричная матрица взаимных расстояний между реализациями ",,1," т-го класса, т. е. лт!!=1/ 1 (у' » — у'!!)в 0*1=1 2 " Тю) , "~!1 где 1 — строка матрицы (1-я реализация); 1 — столбец матрицы (1-я реализация). 162 Э т а п 8. Здесь вычисляется двоичная матрица функций принадлежности: г 0„=()Вы 11,, где д ы = 11, если Р„, — гмы) 0; Это фУнкциЯ (О, если рм~ — гпи~ ( О.
принадлежности, показывающая, попала (1) или не попала (0) 1-я реализация т-го класса в гиперсферу радиусом рем с центром в р-й точке. . Таким образом получена компактная запись взаимного положения «своих» н <чужих» точек в пределах габаритного эталона. Э т а п 9. На этом этапе проводится выделение эталонов т-го класса, т. е. наиболее представительных реализаций, гиперсферы которых покрывают всю область, занимаемую остальными реализациями этого класса„ и не включают «чужих» реализаций. Для матриц, аналогичных матрице 6 = цдыц»™, методика выделения минимальных покрытий разработана (см.
120, 21]). Минимизация полученной двоичной матрицы функций принадлежности проводится последовательным поглощением строк и столбцов по следующему правилу. ПРавило: стРока ~)УП.Ц поглоЩает стРокУ ЦУП,Ц, если ЦУО,Ц -ь- ~ К и ~ Ц ведет к функций, тождественно равной 1 (знак «-ь» означает операцию импликации); столбец (~ды,((поглощает спюлбец Цуы, Ц, если Цуы,ц-ь Цкы,ц ведет к с)»ункции, тождественно равной 1, Операцию минимизации двоичной матрицы функций принадлежности можно свести только к операции поглощения строк. В этом случае поглощение столбцов заменено операцией поглощения строк, которая проводится над транспонированной и обращенной матрицей.
Операции поглощения строк и столбцов чередуются и проводятся до тех пор, пока матрица б либо не приведется к диагональному виду, либо не образуется одна из ее тупиковых (циклических) форм. П р и м е ч и н и е. Возникновение сложных тупиковых форм характерно для специального вида матриц, обладающих упорядоченной структурой и редко встречающихся при решении практических задач. Прн наличии тупиковых форм [20, 2 И. матриц можно воспользоваться разработзннымн методиками и алгоритмами в На рис. 4.22 в качестве примера одного варианта задачи разделения трех классов объектов, имеющих сложные конфигурации размещения их реализаций в двумерном пространстве признаков (коордииат) х» и х„приведена картина расположения сформированных машиной эталонов.
Здесь первый класс А, объектов (обозначен кружочками) был представлен выборкой из 285 реализаций, второй класс А, объектов (обозначен точками) имел 132 реализации, третий класс Аз объектов (обозначен крестиками) — 242 реализации. Преобразование исходного пространства признаков заключалось в сжатии с различными значениями для каждого класса объектов т коэффициентами р по осям х, и х,. Поэтому при возврате к исходному 166 остранству эталоны классов превратились в эллипсы с осями, про.
'орциональными коэффициентам сжатия р, — р». Габариты классов ' а рисунке не показаны. В местах пересечения габаритных эталонов азных классов использовалась линейная разделяющая плоскость. результате работы алгоритма было выделено эталонов: для класса А, — 1О; для класса А, — 4; для класса Аз — 7. Кроме того, на каждйй класс объектов бйл сформирован габарит. Описанный алгоритм помимо обеспечения компактной записи исходных данных задачи после этапа обучения машины, убыстрения про.
Хз ! \ + ° + ++ ! ххх | + + хххх Ехххх хххехххвхххххххх»хх ххххх хххххх~ хх + ° ° «ххххххххххх »хх »хххххххх1 ~ + ++ хххх х. Ф их « ! +ьь+ ° ьйг~ +ь + +++ ьх+ иххььт + ++ ° + Ф + ьх ь +е+ +хььь»«Ь+ь ь» ° й Иг Рис. 4.22. Пример разделения реализаций трех классов в двумерном ирострвнстве при»ивков цесса распознавания и высокой вероятности распознавания обладает ! еще одним важным достоинством: появляется возможность в объеди, ' !.'' нении по различным критериям распознаваемых объектов в новые классы без какого-либо изменения алгоритма обучения и распознава',.„, ния.
5 4.7. РАСПОЗНАВАНИЕ ОБЪЕКТОВ ПО ЭТАЛОННЫМ ОПИСАНИЯМ КЛАССОВ Суть алгоритма классификации заключается в установлении факта принадлежности неизвестной реализации одного из распознаваемых классов объектов к какому-либо габариту или габариту и эталону, сформированным на этапе обучения ЭВМ. 1;$ Исходными данными для работы алгоритма являются: ЦаЦ— ~,',4: матрица ортогональных преобразований размером и Х и (и — число 169 признаков распознавания); ))()1) — матрица коэффициентов сжатия по осям; общий объем массива и х т (т — число классов объектов); массив описаний габаритных эталонов, каждый из которых включает в себя и координат центра габаритного эталона и его радиус (« общий объем этих данных (и + 1) х т; массив описаний эталонов гл классов общим объемом ~(п+ 1) Р! (Р! — число эталонов у-го клас! ! са).
Распознавание объектов ведется следующим образом. После предъявления машине неизвестной реализации ху обьекта ее признаки (координаты) подвергаются предусмотренному для каждого класса преобразованию в соответствии с п. 2 и 3 З 4.6, т. е. ху -!- -у- ху. Затем вычисляется расстояние от конца неизвестной вектор-реализации до центра каждого габарита в соответствии с выражением // е /7„=$ ~ЧЗ (д,у — Р „,)е (!=1,2,..., т), е=! и если )с' ( /с' е, то реализация считается отнесенной к т-му классу. Классификация заканчивается, если класс, к которому отнесена неизвестная реализация, характеризуется только габаритом. В противном случае аналогичным образом проверяется принадлежность реализации к одному из эталонов.
Окончательное решение об отнесении реализации ху к т-му классу принимается по правилу. Правило: реализация х; относится к классу т, если она попала в габарит т-го класса и в один из эталонов того же класса объектов, т. е. ху й Л;„ П ху с Л ', 0 ху с Л ', () ... () ху Е Л з , где Л',— множество вектор-реализаций т-го класса, попавших в габаритный эталон; Л „..., Л, — множества вектор-реализаций, ограниченных эталонами т-го класса. Поскольку пространственные объекты могут быть достаточно сложными, а ракурс их наблюдения — случайным и «малоинформативнымя, то для надежности выделения признаков на реализациях и распознавания иногда приходится использовать несколько реализаций объектов.
$48. СПОСОБ ПОВЫШЕНИЯ ВЕРОЯТНОСТИ РАСПОЗНАВАНИЯ ОБЪЕКТОВ При распознавании пространственных объектов сформированное признаковое описание классифицируемых объектов может не обеспечивать нужной вероятности распознавания по одной реализации. В этом случае для получения заданной вероятности распознавания в процессе классификации используют не одну, а несколько реализаций каждого объекта, полученных под различными ракурсами. Многократное измерение признаков на ряде реализаций объекта должно цовысить вероятность распознавания по сравнению стой, которая будет 170 ри обследовании однои реализации.
Докажем это, отыскав связь меж- 7(у числом реализаций объекта и ошибкой распознавания. Обозначим вектор признаков объекта или его реализацию через где / = 1, 2, ..., г — число используемых при распознавании 'реализаций обьекта. Тогда ху будет вектором признаков, полученных 1' при измерении /-й реализации. В этом случае решение вопроса о при.'- надлежности вектора ху классам А, или А, (двухальтернативная ситуация) на основании только у'-го измерения вектора х будет проис.ходить в соответствии с выражением Р (А!) Р (ху/А,) р (А,) == — у,у) 1, если ху ~ А«, Р (А ) р (ху/Ае) Р (А,) или — ьу(1, если ху с Ае Р (А!) Р (А*) '' где "(»1 ' = 1, — отношение правдоподобия для /-го измерения; Р(ху/А ) 1 ' р (А!) — априорная вероятность !-го класса объектов; р (ху/А, я)— :,' условная вероятность реализации ху в классе А,, Для простоты последующих рассуждений будем считать, что кор- .," реляция между последовательными реализациями объекта отсутству- ет.
Это означает, что при наличии / = г" статистически независимых ' реализаций решение о принадлежности последовательности векторов (х„х„..., ху, ..., хр) тому или иному классу можно принимать на основании неравенств П Р(ху/А!) Р(А!) А" П Еу ) 1 есле (» х. " » »з) б А, А' Р (Ае) у=! П Р (ху/А,) 1=1 или П 1.1~ 1, если (хм хе.
° ° »Р) с 4« Р(А!) Р (Ае) Теперь можно определить уменьшение вероятности ошибки распоз- '(4)„навания в результате многократного измерения вектора признаков ' гч (на разных реализациях), если известны отношения правдоподобия каждого измерения. Связь между вероятностью ошибки распознавания и отношением правдоподобия для /-го измерения вектора признаков была получена в З 3.11. Запишем это выражение для случая, когда р (А,(ху) -> р (А,!ху): 1 Р(АВ 1 А /х если — ) — ° (4.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
