Анисимов Б.В., Курганов В.Д., Злобин В.К. - Распознование и цифровая обработка изображений (1033973), страница 27
Текст из файла (страница 27)
Дей- ствительно, по заданной пороговой величине вероятности распознава- ния из графика (рис. 3.18) находится необходимое количество инф тво инфор- ве оятн . 3 рую должны содержать признаки, обеспечиваю щие эту тивность кото р ость. Затем определяется группа признаков, об щая информа- п изнаков ля орых не меньше требуемой. Ранжирование выб раиных следования. Р д распознавания определит минимальный марш бшрут их о- $3.!2. ВЫДЕЛЕНИЕ ОБЛАСТЕН ПОПАРНОГО РАЗДЕЛЕНИЯ КЛАССОВ классов возмож Для заданной системы признаков только при попарном разделе нии навания см. 3.6 . но обеспечение предельно высокой надежност ( .
2 . ). Однако при больиюм числе классов распознаваемы объектов даже ион бъе рац ально организованная процедура попарного пе наваемых ра классов т б ет ре у больших временных и аппаратурных затрат на ретехническую реализацию. Известны попытки с целью экономии времени решен ения задачи и апур ограничить перебор, производя его только для самых близких классон через разнастные эталоны (см. [161). тоне ности а Противоречие, возникающее между высокими требовани р р опознавания и необходимым для этого объемом об ваниями к досваиия, наиболее удачно разрешается в распознающих системах, исемом арудопользующих сочетание двух (и более) различных методов распознаватать ап оби ованн Например, в практике построения читающих устройств можно с р р анным сочетание таких методов распознавания, как ме- чи122 ды матричного сопоставления и методы структурного анализа изоб' ажений («Рута-701», «Север-3», ВИНИТИ-2).
С помощью небольшого числа структурных признаков заданный алфавит разбивается на части, пределах которых распознавание ведется уже с применением методов матричного сопоставления. Только при расчленении алфавита возмож'но практически приемлемое осуществление процедуры попарного „сравнения классов, а последнее позволяет достичь высоких показате:лей достоверности распознавания.
Издержки, связанные с процедурой 'попарного перебора классов, могут быть скомпенсированы за счет зна- чительного упрощения эталонных описании каждан пары сравнивае мых классов. Действительно, для некоторой пары классов А; и А, за данного алфавита в пространстве исходных признаков существенными , с точки зрения распознавания будут только области, заключающие в ;;себе лишь дискриминантную информацию, как единственно полезную ',для различения данных классов. В н-мерном пространстве признаков в общем случае можно выде, лить области связные и области несвязные, содержащие в себе исчер' пывающую дискриминантную информацию о классах А, и АР Любой ,:.
признак, участвующий в дискриминации рассматриваемых классов, : может принадлежать только одной из этих областей. Если признак не , участвует в дискриминации классов А; и Ал он бесполезен и не при. нимается во внимание (не принадлежит ни одной из выделяемых об' ластей). Признак х„принадлежит области Рц попарного различения клас'„сов А; и А! (!' ( !), если частная производная дискриминантной функции «(ц (х, Ф') по этому признаку положительна, или области Р1; попарного различения, если частная производная дискриминантной , функции отрицательна, т. е. ддц(х, Ф') х» с Оц, если )0; (3.57) дх!, хл'~ О!!, если ' СО, ддц(х, %') (3.58) дхл ", где х» — А-й признак распознаваемого объекта х = (х„х„..., х„). Таким образом, при возрастании значений А-го признака в области Рц мера сходства распознаваемого объекта с классом А! увеличивается, а с классом А! — уменьшается; при возрастании же значений х» в области РЛ мера сходства распознаваемого объекта с классом А, умень:, шается, а с классом А! — увеличивается.
Область Рц попарного разделения классов А, и А! является утверждающей для объектов класса А! н отвергающей для объектов класса А! (см. П7,181), соответственно область Р1; — утверждающей для объектов класса А! и отвергающей для объектов класса А о - Установим соотношения, согласно которым производится разбие- -)А,' ние пространства признаков на области попарного разделения классов А ! и А! для случая, когда в качестве решающих используются линейные функции (например, функции в виде скалярных произведений). Для непрерывных значений признаков меры сходства распознаваемо- го объекта пой му признаку ггц и гду соответственно с классами А, и А равны (см.
18)): у (3.69) гс„-хс„хд, гду=хсухдс хдс = — ~~ хдп, хс, = — ~' хдсс, (3. 60) с=! где хдь х„у — средние значения й-го признака соответственно в клас- сах А с и А;; хд ц и хдп — значения й-го признака соответственно в 1-й ре- ализации обучающей последовательности длиной Е класса А; и бй реализации обучающей последовательности длиной Т класса А,. Дискриминантная функция !усу (х, %') классов А; и Ау с учетом (3.59) может быть представлена в виде д х сссу (х, )Р)= ~ (гд! — гду) = ~ (хдс — хду) хд. (3.61) д=! д=! Согласно выражениям (3.57) и (3.61), для области попарного разли- чения классов Рц имеем х д ~'( — ) (хс с — хду) хд дхд =хдс — хду) О.
д=! кото ых в Следовательно, в область Рц попадают признаки, средние зн ачения р в классе Ас превышают соответствующие средние значения признаков в классе Ар Аналогично можно показать, что область Ву, составляет совокуп- ность признаков, средние значения которых в классе Ас меньше соот- ветствующих средних значений признаков в классеА, (О. ;,т.е. хдс — хду( Если признаки принимают бинарные значения (1 или 0), то их сре- ние зна ен ачения заменяются оценками вероятностей появления единич- сред- ного признака рю и рду соответственно в классах А; и А;.
Область Рц составляют признаки, для которых рд,— рду >о, (3.62) а область В!с — признаки, для которых рм — р„,<о. ного Эффективность признаков, составляющих области Р и Р . ,у и ус попарразделения классов, определяется в соответствии с методикой, описанной в $ 3.13. В исходном эталонном описании класса Ас выделяется область Рц, для которой выполняется условие (3.62). Эталонное значение каждого признака, входящего в эту область и классифицирующегося полезным, взвешивается в соответствии с величиной оценки полезности ессу этого признака при попарном сравнении классов А с и Ау.
из области В.. ' о Признаки, оказавшиеся вредными или бесполезными, исклю чаются ;у. Сформированная область Рц при необходимости мо- жет быть нормирована. 124 Область Рп попарного разделения классов определяется по исход'.ному эталонному описанию класса Ау аналогично области Вц.
Сформированные таким образом области Вц и Ву; попарного разде:ления классов представляют собой компактные и эффективные эталонные описания классов А,. и Ау. имеющие в два раза меньший объ-ем, чем исходные эталонные описания. $3.13. АЛГОРИТМ ОТБОРА ЭФФЕКТИВНЫХ ПРИЗНАКОВ. СОСТАВЛЕНИЕ ЭТАЛОННЫХ ОПИСАНИИ КЛАССОВ Рассмотрим последовательность процедур отбора эффективных при знаков при построении эталонных описаний обьектов любой природы, составляющих некоторый алфавит Ас — — (А,, А,,, А ).
Э т а п 1. На этом этапе определяются параметры дискриминантных ,'функций г(с (х, Я7) (с = 1, т) на основе обучающей выборки распознава- емых обьектов при заданной размерности пространства признаков, т. е. исходные эталонные описания классов. Если принятый алгоритм распознавания предполагает нормирование эталонных описаний, ' последние нормируются. Э т а п 2. На данном этапе алгоритма для каждой пары классов А; 'и Ау (с, 1' = 1, си; с ( у) алфавита на основе обучающей выборки объ- 'ектов определяются параметры дискриминантной функции сусу (х, )сг), ' получаемой как разность дискриминантных функций ссс (х, )сг) и :-.
бу (х, )Р): сссу(х, )Р) =Нс(х, Цг) — с(у(х, )Р), где х = (х„х,..., хд, ... х„) — распознаваемый объект; )Тг = (нс„ :, пс„..., нс„) — параметры дискриминантной функции. Искомыми параметрами являются математическое ожидание зна- , чений дискриминантной функции с(су (х, Яг) для класса Ас тсу и для : класса Ау тус, а также среднеквадратичные отклонения осу и оус со- ' ответственно для классов А, и А;: 1 яссу= — 3~~~ (гп — гц); оп= — )' цгп — гц) — яссу)с, с-! с-! ;. где 7.
— число реализаций класса А; в обучающей выборке; 1 — номер 'реализации класса А; в обучающей выборке;гп — мера сходства 1-й ;реализации с эталоном класса А;; гц — мера сходства 1-й реализа- "ции с эталоном класса Ау. Аналогично определяются параметры 1 г рсус — ~~~ (гц — гсу); оус = ~~~Э„((гсс — гц) — тус]с, с=! с=! !где Т вЂ” число реализаций класса Ау в обучающей выборке; 1 — но- Мер реализации класса Ау в обучающей выборке; гц — мера сходства Вй Реализации с эталоном класса Ас) гц — меРа сходства бй Реяли- :;.зации с эталоном класса Ау. 126 Э т а п 3. На этом этапе алгоритма для каждой пары классов алфавита А на основе обучающей выборки определяются параметры распределений дискриминантной функции с(!» (х, ))т) при исключении й-го признака (й = 1, и) из исходной совокупности признаков: ! 1 (=! где ги, г); — меры сходства 1-й реализации класса А! с эталонами гл) (ь) классов А; и А; после исключения й-го признака из исходной совокупности признаков.
Аналогично определяются параметры (=1 Э т а п 4. На этом этапе алгоритма по найденным величинам т()ч т)! и л);(, )ии определяются значения приращений математических (ю га) ожиданий Л(мт(1 и Л(а)т;! дискриминантной функции при исключении Й-го признака из исходного описания: и(! шц яц Л а шд ш! ш!! (э) .. (ь), и) ..
(!) Аналогично по величинам аеь и(! и и;и о„находятся приращения (а) (ь) среднеквадратичных отклонений: А(*)оп=осу — о) ); Л( ) и (=оп — и(. ). ! )! Э т а п 5, На этом этапе алгоритма вычисляются согласно (3.20) оценки полезности признаков исходного описания при попарном разделении классов, которые записываются в виде совокупности матриц Ед (3.34).
Э т а п 6. На этом этапе алгоритма вычисляются для каждой матрицы Еа в соответствии с (3.35) и (3.36) значения добротности й-го признака аь в заданном алфавите А. Э т а п 7. На данном этапе алгоритма составляется согласно (3.37) матрица Е и по соотношениям (3.39) и (3.40) определяется значение средней добротности признака исходного описания а в алфавите А . Э т а п 8. На этом этапе алгоритма вычисляется по (3.41) первичная система весов уь (й = 1, и), дающая характеристику эффективности каждого из п признаков исходного описания.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
