Анисимов Б.В., Курганов В.Д., Злобин В.К. - Распознование и цифровая обработка изображений (1033973), страница 32
Текст из файла (страница 32)
точка на плоскости 4ю9. Находя ближайшие к ней аппликаты, нетрудно'по формуле (4.10) вычислить величину хц (ае, ае). Повторим эту процедуру (~о раз (значение 9е определяется требуемой точностью нахождения ац (х,)). В результате будет получен одномерный массив значений х», используя который несложно построить соответствующую гистограмму 47» (х;).
Для этого диапазон изменения хц разбивается на 10 — 20 интервалов, затем подсчитываются частоты попадания значений хц в каждый из интервалов и, наконец, находятся ординаты гистогРаммй 4» (х;) отнесением УпомЯнУтых частот к соответствУюЩим им интервалам. Изложенная методика свободна от упомянутых выше недостатков. Действительно, имея в ЭВМ библиотеку датчиков псевдослучайных чисел, можно получить любой закон распределения углов у и 9. Для хранения одной гистограммы необходимо всего 12 — 22 ячейки, поскольку ось абсцисс разбита на интервалы равномерно и для характеристики количества интервалов разбиения достаточно, например, указать минимальное значение признака и величину интервала. Определение требуемой ординаты гистограммы в случае необходимости сводится к выборке ее из соответствующей ячейки памяти.
Нетрудно обобщить эту методику и на случай зависимости х; от многих параметров. Например, в отдельных случаях распознавания вид проекции объекта существенно зависит от фазы его освещения. Можно, конечно, ввести дискретные фазы освещения и для каждой из них вычислить и запомнить распределения признаков я» (х;), с тем >' чтобы при опознавании объекта измерить фазу освещения и обратиться для принятия решения к соответствующим этой фазе распределениям. Однако такой подход связан со значительными затратами объема памяти. Если же при построении плотностей распределения признаков дц(х;) есть возможность привлечь законы распределения значений углов, характеризующих фазу освещения, то часто требуемый объем па) мяти может быть уменьшен.
Правда, при этом необходимо изучение зависимости х, (оз/А») от более чем двух параметров, Теоретически оценить количество с(з случайных испытаний, необходимое для формирования гистограмм с заданной точностью, в общем случае затруднительно. Для приближенной оценки (',)з был поставлен следующий эксперимент.
а) х Пу ь например записи мость х (ф О) имеет вид ! казанный на рис. 4.12, а, б, и аспределение углов обзора ! ! описывается двумя независимыми законами равномерной З В плотности я (ф) = 1/ф, я (О)= У = 1/О. Теоретические оценки распределений величины х для рис. 4.12, а, б соответх ственно будут в этих условиях иметь вид д (х) = 1/х и д(х)=2(х „— х)/ха х „= 1 (рис. 4.13, а, б).ша На этом рисунке приведей ны и отвечающие им экспериментальные гистограммы и Ф о (х), а на рис.
4.14 — зависимости относительных средРнс. 4.1х примеры зависимости х (ф, В) неквадратичных отклонений а гистограмм от количества (/э случайных испытаний (вид этих гистограмм практически не зависит от х , ). Как видим, целесообразно установить значение (;)э = 3000, поскольку при („)е ь 3000 значение а изменяется очень медленно (при ф> — — 10 000 и ж 4%).
Определение плотностей распределения признаков в задаче классификации трехмерных объектов. Возможность пересечения классов по используемым для опознавания а/ ои/,оач признакам в этом случае резко возрастает. Известно также, что если априорные вероятности отдельных объектов, составляюших тот или иной класс, не заданы, то о плотно- йб оо йб дб оа о олб аобялб гзоб(ох ЯК б/ ри/,ра/ хо йб йх дб ол о и м 8 б г о 1о бООО Ро,ое, ДЯ об Опб Лоб адб бпмйол Рис. 4.14. Графики зависимости о= -/(0,) для признаков к(ф,В) (см.
рис. 4 12) Ряс. 4.13. Графики теоретических и (х) и экспериментальных и (х) плотностей распределеяия значений х для призяаков х (ф, В) (см. рис. 4.12) 148 ях распределения признаков для этого класса трудно говорить. Сооттвующие плотности для каждого из объектов можно получить по ложенным выше методикам. При этом, поскольку в рассматриваемом учае принимаемые решения должны относиться к номерам классов, йеобъектов, и цены решений каждого типа зависят только от номера Л ' асса, подобная задача должна рассматриваться как известная в ма' матической статистике задача различения сложных гипотез. Эта п а поедняя задача очень сложна и решена лишь для некоторых частных ' учаев.
В этой связи целесообразно предположить, что априорные вероятости объектов, составляющих класс, одинаковы. Подобное допущение асто довольно близко к реальной ситуации. Тогда плотность распре' еления 1-го признака для /-го класса может быть получена суммироаннем плотностей распределения 1-го признака для всех т/ объектов, ' редъявленных при обучении и относящихся к /-му классу, с последую' им меньшением масштаба по оси ординат в т/ раз.
При этом особое ' ниманне должно уделяться требованию достаточности статистики. Вероятностный подход к задаче автоматического опознавания трех- ~ ерных объектов позволяет далее при разработке решающей части алгоритмов опознавания эффективно использовать методы теории ста„, истических решений. 5 4.4, ВЕРОЯТНОСТНЫЕ МЕТОДЫ ПРИНЯТИЯ РЕШЕНИЯ Рассмотрим класс алгоритмов принятия решения, использующих 'В той или иной форме сведения о плотностях распределения признаков. П а н е. Этот класс алгоритмов наяболее последовательно моримеч и Ьжет быть изложен с позиции теории статистических решений (см. [ 1), е у'дут рассмотрены только основные положения этой теоряи и вопросй ее приме'нении для целей автоматического распознавания трехмерных тел, '[' ) П е положим, что совокупность возможных входных ситуаций си- Р д А , А ..., А и [стемы опознавания подлежит разделению на классы А„А„..., 'для этого используется п подходящих признаков.
При предъявлении [Некоторой реализации Х, подлежащей опознаванию и являихцейся в ,'общем случае случайной, соответственно п признакам делается п из:мерений х„х„..., х, которые в последующем часто будут рассматри,'ваться как компоненты случайного вектора х = (х„х„..., „). у ;распред еление вероятностей х зависит от класса А известным образом, 'т. е если класс есть А/, то функция плотности вероятностей по отноше, нию к некоторой мере Р в выборочном пространстве ь) есть я (х/А/) ,",,,~Л (х).
Поскольку природа Р не уточнена, то непрерывные и диск'ретные распределения вероятностей включаются в эту формулировку ;~",1(ак частный случай. Требуется по наблюденному значению х опознать ,"Класс предъявленной реализации Х. Пусть ау будет решение, что класс есть А/ (/ =- 1,2,..., т), а ио— „" „' решение не относить Х ни к одному из классов А. Введем понятие ре,'/);,', шающей функции н (а,(х) или просто и (т(х) как функции, определен,": '[1 ной для каждого х Р ь) и решения а, (т = 0,1, ..., т), причем Х к (т( 149 ь' (4.19) (4.20) (4.22) 150 /х) =1, к (ч/х))0(ч= О, 1, ..., т). Класс всех таких решающихфунк- ций к обозначим (). Таким образом, если х есть наблюденное значение случайного век- тора, то к (ч/х) есть вероятность выбора решения и„.'Задача заключает- ся в нахождении оптимальной в некотором смысле решающей функции.
Если в действительности реализация Х относится к классу Аь а ре- шение есть а„, то предположим, что имеют место потери (штраф) С (А/, а„) в 0 или просто С/ч. Риск (математическое ожидание штрафа) использования данной к Е /х в случае, когда реализация Х Е А/, определяется следующим образом: Т(А/, к)= ~ ) С/ к(ч/х)д/(х)!()! (/=1,2,..., О!). (4.15) ч=ОО Теперь предположим, что априорная вероятность (или частота по- явления) А/ есть $/(9/ О, / = 1,2,..., и), ~ 9/ = 1.
Средний риск, /=1 соответствующий $ = ($„$О...., $„), определяется как Т(О, )= ~ Т(А/, )О/. (4.14) /=! Данная решающая функция /! (т/х) в () есть решающая функция Бейеса, если Т (О, /!) ~( Т Я, к) (4.15) для всех функций к б О. Величина Т (9, /!), являющаяся минимумом всех Т (9, к), называется бейссовым риском и обозначается Т (9). Решающие, функции Бейеса можно легко найти. Из (4.13) и (4.14) следует, что Т(О. )=) ~ ~ ~ С/ч//(х) (~/~)О(х, йч О( / 1 где Т/ (х) = В/й/ (х). Далее обозначим символом /р множество целых чисел 0,1, ..., и. Для фиксированного значения вектора х Е 11 положим, что /О (х) есть подмножество /О такое, что / Е,/р (х), если и только если пцп ~ С //(х)= ~' С/!//(х).
(4.16) ч6/~ /=1 Пусть также к (ч/х) есть решающая функция в классе /) такая, что к(ч/х) =0 (4. 17/ для всех т ф,/ (х). Из (4.16) следует, что функция х, определяемая по (4.17), является бейесовой. Величины к (т/х) для ч Е ./О (х) не вполне точно определены, но соответствующая величина Т (9, к) всегда та же, т. е. Т ($). Другими словами, средний риск минимизируется, если при распознавании кандый раз принимается решение и1, при котором ~х/~ с/1//(х)( х~', с/ //(х) (ч=о,..., ак чзь/). (4.18) / 1 / ! Пусть теперь С„=о, См=Сх =С (' 1=1 ° 2""'м! /~ )' Тогда - ~, „,,/,)/,(.)л„+Е Х 1С„-(/)//()"~- ! / 1ч 1 ~7 (О/х) / (х) !/(х+С! Х ) Х к(ч/х) //(х) ()$' 1 /=1 чч/ Так как ',Р~ „(ч/х) 1 — к (О/х) — к (//х), чР/ т ($! к) =С! Рч(н)+Сх Рх (к) ® ~~ ~„(0/„) р (х) б„— вероятность отказа от Распознавания; 1, (к) = ~ ~ к(//х) //(х) !/(' (4.21) /=1 Р ! — 1 Р„(к)— , — вероятность прав равильного распознавания; Р,( )— ние выполняется по всему пространству Под (х: .4, ~,...) (где А Е, ...
— 1ю1!от!! : нимать множество всех х Р !4, ати 11, для которых зги е Е и Р Ниже буду использованы ,' ственно объединение и пересечение Е и . иже !: следующие обозначения: /(х) =;~ // (х); х; й (х) = шах (/! (х), /О(х),..., (х)); Е, = (х: (1 — с) ° /(х) ) /! (х)); О = ( Е = (х: (1 — с) ° /'(х) = = /! (х)); Е, = (х: (1 — с) /(х) (/! (х) ); Емх = для фиксированного вектора х Е Т г а из (4.16), (4.17) и (4.19) найдем, что чун '; я " " ф нк ией, если для всех ' является бейесовой решающей фу ц х ~ 51,к(0/х) 1, к(//х) 0 (/ 1, 2,..., т)! х ~ Е к(О/х)+ х ! ко/х) 1 к(//х) О (/ й 2(х)); /в/ !х] хЕ Е ~~~ кб/х) 1, к(0/х)=к (//х) О(/й /(х)) /Ы (х! 4.22), ф нкция к не всегда однозначно определена. и больше чем одно / можно оп' /х) = 1 для ~екот~ро~о !, Е,/ (х) ли х Е и / (х) содержит льш или ределить к (О/х) 1 или к (/, х) = д я 151 и (О/х) = 1/3, и Ц /х) = 0,5..., .
Ц, ) =,..., . Все эти функции х имеют тот же самый бейесов риск, хотя вероятности Р, (х), Р, (х) и Р к П стью б Теперь предположим, что исключили а, как возможное » ое решение. усть| будет множеством всех решающих функций хЦ/х) таких, что и (//х) = 1 (к Ц/х) ) 0) для всех х Е й (/ = 1,2, ..., т). Поскольку У'.и (//х) = 1 к '/х ) 0 (О/ ) — О, , /). х может рассматриваться как решающая фун кцня, для которой х ( х) = О, видим, что б ~ /). ( ) — О,, /).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
