Анисимов Б.В., Курганов В.Д., Злобин В.К. - Распознование и цифровая обработка изображений (1033973), страница 36
Текст из файла (страница 36)
Описание габарита и алгоритм проверки реализаций на ф принадлежность к ней должны быть предельно просты, поскольку через ! этот этап на каждом шаге алгоритма минимизации проходят все ре, ! ализации распознаваемых классов. Всем перечисленным выше условиям удовлетворяет габаритный ,3;,,»! эталон в виде гиперсферы. Поэтому задачей оптимального преобразо- ~ Щ!.' вания исходного пространства признаков в этом случае будет максимальное приближение к гиперсфере области реализаций каждого клас- 163 ~й': р„о ...о об„...
о ам а»« ° . а«л а«1 а»2 ''' а»л см с»«... с»л с«»с, ...с,л О О ... блл ал» аа« "алл сл» сл«, слл Вычисление коэффициентов матриц преобразований для каждого класса требует значительных затрат машинного времени, так как каждый шаг вычислений — это перебор расстояний между всеми реализациями класса. Например, время, необходимое для расчета матрицы ЦаЦ, можно оценить как ( = ([й~ (й« вЂ”, 1)/2) иЛ~,р) и (в фигурных скобках выделено время одного шага работы алгоритма). И хотя на этапе обучения часто нет жестких временных ограничений, хранение матриц требует дополнительных затрат памяти (и 1«и ячеек на матрицу), что может оказаться нежелательным фактором.
Поэтому желательно производить вычисление матриц преобразования только в случае, если выделение эталонов в исходном пространстве признаков не приводит к желаемым результатам (например, число эталонов недопустимо велико). Матрицы преобразования не обязательно рассчитывать для всех классов. Это можно делать только для самых «неудовлетворительных», с точки зрения количества эталонов, классов. Оптимизацию решения задачи отыскания эталонов можно осуществить также по способу ортогонального преобразования пространства признаков путем нахождения одной матрицы ЦаЦ для всех классов одновременно, а матриц ЦРЦ вЂ” для каждого класса в отдельности. Этот способ приводит к положительным результатам, когда направления диаметров подмножеств реализаций для каждого класса не ортогональны, а близки между собой или полностью совпадают.
Выбор способа вычисления матриц преобразования в значительной степени зависит от качественных и количественных характеристик системы признаков. Недостатки системы признаков можно скомпенсиРовать ее преобРазованием и, наоборот, сложную операцию преобразования можно упростить, совершенствуя систему признаков. Поэтому для выбора оптимальных соотношений между недостаточным совершенством системы признаков и сложностью ее преобразований можно рекомендовать моделирование пробных задач на реальном исходном материале. Алгоритм обучения ЭВМ по эталонным описаниям классов.
В случаях, когда законы распределения вероятностей признаков или клас- 164 са. С этой целью предлагается провести для каждого класса объектов отдельно ортогональное преобразование координат (см. 120, 211) с помощью матрицы вращения а = ~ 1а» р Ц", и последующего сжатия вдоль осей с помощью диагональной матрицй Р = Цр»»Ц».
В Результате получается преобразование, максимально приближающее область реализаций, соответствующую «нашему» классу, к гиперсфере с диаметром, равным 1, в классе линейных ортогональных преобразований. Объединяя повороти сжатие, получим матрицу С = = Цс»рЦл» суммарного преобразования: ' в распознаваемых объектов слишком сложны или неизвестнь1, что е дает возможности использовать известные в теории статистических Решений решающие функции, переходят к параметрической интерпреации задачи распознавания с использованием детерминированных 'алгоритмов обучения машины и классификации образов.
Алгоритм 'обучения, описываемый ниже, прост в реализации и дает практически ',стопроцентное распознавание объектов (при наличии представительной выборки объектов на этапе обучения машины), не требует больших '1»бъемов памяти ЭВМ. Суть этого алгоритма сводится к тому, что в и-мерном пространстве ,,признаков опознаваемых объектов строятся для каждого класса объектов один или несколько областей-эталонов, включающих в себя (покрывающих) все объекты этого класса. Поскольку эталоны строятся 1непересекающиеся, достигается практически стопроцентная вероят'. ность распознавания.
Пространство признаков предварительно подвергается преобразованию. Задача оптимального преобразования координат — максимально приблизить к гнперсфере область, занимаемую реализациями «своего» класса,С этой целью предлагается произ- 1 вести ортогональноепреобразование координат исжатие вдоль осей ко,- ординат.
Опишем основные математические и логические операции, выполняе, мые ЭВМ на каждом этапе реализации алгоритма обучения по эталонным описаниям обьектов в пространстве признаков. Э т а п !. На этом этапе вводятся исходные данные (таблицы информации объектов и матрицы ортогонального преобразования ,' ЦаЦ).
Массив Реализаций объектов к описывается системой призна,;: ков распознавания. Э т а и 2. На данном этапе проводится ортогональное преобра': зование исходного пространства признаков с помощью матрицы ЦаЦ , (рис. 4.19): й Ущг1) =1!а»»1Ь 1! хлл й В координатах х Ха,. аи ам ... а»л а«» а»«а«л Уть Ум.
! ал» ал« ° алл 1бб 6» л >,', где к, — и«-го класса 1-й вектор — реализация в исходном простран1стве признаков; у ~ — соответствующий ему вектор в преобразованном пространстве признаков. Э т а п 3. На этом этапе алгоритма вычисляются коэффициенты 'сжатия в преобразованном пространстве признаков и проводится сжа„' тие подмножеств реализаций каждого из и» классов 1« по осям про- ,стРанства признаков в соответствии с выражениями У ) 1 (У 1 2,..., и; 1=1, 2...
Та), (шах (уаы) — пи1П(ужа)1 »,г »,г У л«» = Рла» Улп» / Рнс. 4.20. Отыскание гебз- рита класса А!! ! — 3 — ееснвететвенно ревлнвв- цнн классов ж — ж Рнс. 4.19. Пример преобрззовзння исходного прострзнства прнзнвхов с помощью матрицы ((а((: ! — 3 — спет»ее««венке ревлнввцнн классов ж — Аз которой должны покрываться все реализации т-го класса. С этой цеа) определяются координаты центральной точки эталона, т. е. у„',е»=0,6(тзх (ун»)+поп (у,'не)) (1! =1, 2,..., н; !' =1, 2, ° ., Тле); е.
! ». ! б) рассчитывается евклндово расстояние от центра эталона до самой удаленной реализации т-го, «своего», класса, т. е. л Кв =тех ~ ~~', (у„' » — у'с»)» (! =1,2,..., Т,„); »=! в) определяется расстояние от центра габарита до ближайшей «чужой» точки (реализации), расположенной за пределами сферы с радиусом )« „ т. е. /н л »=! )1 — ~>йултвх (1=Тел+1, Тле+2,..., Т), где Т вЂ” общее число реализаций множества; г) вычисляется радиус габаритного эталона, т. е.
0 5 Мне !ппх + )«щ ! ) ° 166 где )) !ь — коэффициент сжатия по й-й оси т-го класса объекта, !'-й реализации; Т вЂ” общее число реализаций объекта т-го класса; у';ь — преобразованная /с-я координата т-го класса объекта 1-й реализации' Ь!и!ь)ювх~ (унееь)т!и — экстремальНые значения /с-й координаты 1-й реализации т-го класса, для которого на даннол! шаге работы формируются эталоны «своего» класса. Э т а п 4. На этом этапе алгоритма происходит отыскание габарита т-го класса (рис, 4.20). Габарит представляет собой гиперсферу, Таким образом найдены центр и радиус габаритной области.
Если допустить, что точность определения координат (признаков) я всех классов одинакова, то расстояние между наиболее удаленной центра эталона «своей» реализации и ближайшей «чужой» за преамн габарита будет делиться границей габарита пополам [см. п. г)). Э т а п 5. На данном этапе алгоритма выделение «чужнх» точек- / 'реализаций, попавших в габарит т-го класса, проводится по правилу: / л )дслн$/ ~(у~!в — у ед)в()«е(1= Т +1, Т +2, ..., Т), то в '!!чужая» точка попадает в габарит (рис.
4.21), где кружочками обозна'чены «чужие» реализации, попавшие в габа'рит, а крестиками — «свои» реализации клас- у,' .'са А„. Э т а п 5. На этом этапе алгоритма фор;мируется столбцовая матрица минимальных,/ 4 ';расстояний от каждой точки класса т до бли;,жайшей «чужой» точки, попавшей в габарит: хх х 44 2 ! л е х ~~л!! !и!и Х (ум!Ь!р уле!») д у! (шде уел! — координаты «чужих» точек, по- Рнс. 4.21. Выдененне ) павших в габарит; у~ше — координаты «своих» .'точек класса т; 1„— количество «чужих» то- нопввшнх в гпбзрнт '~.чек в габарите.
Из-за конечного числа реализаций 'обу- ! — 3 — втвловм классов Ат )) чающей последовательности и неточности из- .1 мерения признаков реализации, используемые в режиме распоз,";навання, могут несколько отличаться от реализаций, по которым "велось обучение. Поэтому целесообразно ввести для радиусов эта' лонов некоторый запас М„',с, зависящий от точности измерения ,,значений признаков.
Аналитическое определение этой зависимости при многомерной системе признаков чрезвычайно затруднительно, ) ' поэтому можно предложить выбор значений М' с проводить так, что- 'бы граница между ближайшими реализациями, «своей» и «чужой», (, /: проходила посередине расстояния между ними, т. е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
