Преглед съществуващи методиразпознаване на шаблон

Л.П. Попова , И ОТНОСНО. Датиев

Способността за "разпознаване" се счита за основно свойство на хората, както и на другите живи организми. Разпознаването на образи е раздел от кибернетиката, който разработва принципи и методи за класифициране и идентифициране на обекти, явления, процеси, сигнали, ситуации - всички тези обекти, които могат да бъдат описани чрез краен набор от някои характеристики или свойства, които характеризират даден обект.

Изображението е описание на обект. Образите имат характерно свойство, което се проявява във факта, че запознаването с крайно числоявления от едно и също множество дава възможност за произволно разпознаване голямо числонегови представители.

Има две основни направления в теорията за разпознаване на образи:

изучаването на способностите за разпознаване, притежавани от човешки същества и други живи организми;

развитие на теорията и методите за конструиране на устройства, предназначени за решаване на индивидуални проблеми на разпознаване на образи в определени области на приложение.

Освен това статията описва проблемите, принципите и методите за внедряване на системи за разпознаване на образи, свързани с развитието на второто направление. Втората част на статията разглежда невронно-мрежовите методи за разпознаване на образи, които могат да бъдат отнесени към първото направление на теорията за разпознаване на образи.

Проблеми на изграждането на системи за разпознаване на образи

Задачите, които възникват при изграждането на автоматични системи за разпознаване на образи, обикновено могат да бъдат класифицирани в няколко основни области. Първата от тях е свързана с представянето на изходните данни, получени като резултати от измервания за разпознаваемия обект. проблем с чувствителността. Всяка измерена стойност е някаква "характеристика на изображение или обект. Да предположим, например, че изображенията са буквено-цифрови знаци. В този случай може успешно да се използва измервателна ретина, подобна на тази, показана на фиг. 1 (а). в сензора Ако ретината се състои от n-елементи, тогава резултатите от измерването могат да бъдат представени като вектор на измерване или вектор на изображение ,

където всеки елемент xi приема, например, стойността 1, ако е през i-та клеткаретината преминава през изображението на символа и в противен случай стойността е 0.

Разгледайте фиг. 2(б). В този случай изображенията са непрекъснати функции (от типа на звуковите сигнали) на променливата t. Ако стойностите на функцията се измерват в дискретни точки t1,t2, ..., tn, тогава векторът на изображението може да се формира, като се вземе x1= f(t1),x2=f(t2),... , xn = f(tn).

Фигура 1. Измерване на ретината

Вторият проблем на разпознаването на образи е свързан със селекцията характерни особеностиили свойства от получените първоначални данни и намаляване на размерността на векторите на изображението. Този проблем често се определя като проблем предварителна обработка и избор на функции.

Характеристиките на класа изображения са характерни свойства, общи за всички изображения от този клас. Характеристиките, които характеризират различията между отделните класове, могат да се интерпретират като междукласови характеристики. Вътрешнокласовите характеристики, общи за всички разглеждани класове, не носят полезна информацияпо отношение на разпознаването и може да не се вземат предвид. Изборът на характеристики се счита за една от важните задачи, свързани с изграждането на системи за разпознаване. Ако резултатите от измерването позволяват да се получи пълен набор от отличителни характеристики за всички класове, действителното разпознаване и класифициране на моделите няма да причини особени затруднения. След това автоматичното разпознаване ще бъде сведено до прост процес на съпоставяне или процедури, като търсене на таблици. В повечето практически проблеми с разпознаването обаче определението пълен комплектразграничаването на черти се оказва изключително трудно, ако не и невъзможно изобщо. От оригиналните данни обикновено е възможно да се извлекат някои от отличителните характеристики и да се използват за опростяване на процеса на автоматично разпознаване на образи. По-специално, размерът на измервателните вектори може да бъде намален чрез трансформации, които минимизират загубата на информация.

Третият проблем, свързан с изграждането на системи за разпознаване на образи, е да се намерят оптималните процедури за вземане на решения, необходими за идентификация и класификация. След като събраните данни за шаблоните, които трябва да бъдат разпознати, са представени чрез точки или измервателни вектори в пространството на шаблона, оставете машината да разбере на кой клас шаблони съответстват тези данни. Нека машината е проектирана да прави разлика между M класове, означени с w1, w2, ... ..., wm. В този случай пространството на изображението може да се счита, че се състои от M области, всяка от които съдържа точки, съответстващи на изображения от същия клас. В този случай проблемът с разпознаването може да се разглежда като конструиране на границите на регионите за вземане на решения, разделящи M класове въз основа на регистрираните измервателни вектори. Нека тези граници са дефинирани например чрез решаващи функции d1(х),d2(x),..., dm(х). Тези функции, наричани още дискриминантни функции, са скаларни и еднозначни функции на образа на x. Ако di (x) > dj (x), тогава изображението на x принадлежи към класа w1. С други думи, ако i-то решаващофункция di(x) има най-висока стойност, тогава смислена илюстрация на такава схема за автоматична класификация, базирана на изпълнението на процеса на вземане на решение, е показана на фиг. 2 (в схемата "GR" - генератор решаващи функции).

Фигура 2. Схема на автоматична класификация.

Функциите за вземане на решения могат да бъдат получени по няколко начина. В тези случаи, когато е налична пълна априорна информация за разпознаваемите модели, функциите за вземане на решение могат да бъдат определени точно въз основа на тази информация. Ако е налична само качествена информация за моделите, могат да се направят разумни предположения относно формата на функциите за вземане на решения. б последен случай, границите на регионите на решение могат да се отклоняват значително от истинските и затова е необходимо да се създаде система, способна да постигне задоволителен резултат чрез серия от последователни корекции.

Обектите (изображенията), които трябва да бъдат разпознати и класифицирани с помощта на система за автоматично разпознаване на образи, трябва да имат набор от измерими характеристики. Когато за цяла група изображения резултатите от съответните измервания са сходни, се счита, че тези обекти принадлежат към един и същи клас. Целта на системата за разпознаване на образи е да определи, въз основа на събраната информация, клас от обекти с характеристики, подобни на тези, измерени за разпознаваеми обекти. Правилността на разпознаването зависи от количеството отличителна информация, съдържаща се в измерените характеристики, и ефективността на използването на тази информация.

Основни методи за внедряване на системи за разпознаване на образи

Разпознаването на образи е задача за конструиране и прилагане на формални операции върху числени или символни представяния на обекти от реалния или идеалния свят, резултатите, чиито решения отразяват отношенията на еквивалентност между тези обекти. Отношенията на еквивалентност изразяват принадлежността на оценяваните обекти към някои класове, разглеждани като самостоятелни семантични единици.

Когато се конструират алгоритми за разпознаване, класовете за еквивалентност могат да бъдат зададени от изследовател, който използва свои собствени значими представяния или използва външен Допълнителна информацияза сходството и различието на обектите в контекста на решавания проблем. След това се говори за „проницателност с учителя“. В противен случай, т.е. Кога автоматизирана системарешава проблема с класификацията, без да включва външна информация за обучение, се говори за автоматична класификация или „неконтролирано разпознаване“. Повечето алгоритми за разпознаване на образи изискват включването на много значителна изчислителна мощност, която може да бъде осигурена само от високопроизводителна компютърна технология.

Различни автори (Ю.Л. Барабаш, В.И. Василиев, А.Л. Горелик, В.А. Скрипкин, Р. Дуда, П. Харт, Л.Т. Кузин, Ф.И. Перегудов, Ф.П. Тарасенко, Темников Ф.Е., Афонин В.А., Дмитриев В.И., Ж. Ту, Р. Gonzalez, P. Winston, K. Fu, Ya.Z. Tsypkin и др.) дават различна типология на методите за разпознаване на образи. Някои автори разграничават параметрични, непараметрични и евристични методи, други - разграничават групи от методи, базирани на исторически установени школи и тенденции в тази област.

В същото време добре познатите типологии не отчитат една много съществена характеристика, която отразява спецификата на начина на представяне на знанията за предметна областизползвайки някакъв формален алгоритъм за разпознаване на образи. Д. А. Поспелов идентифицира два основни начина за представяне на знанието:

Интензионално представяне - под формата на диаграма на връзките между атрибути (характеристики).

Разширено представяне - използване конкретни факти(обекти, примери).

Трябва да се отбележи, че съществуването на тези две групи методи за разпознаване: тези, работещи с характеристики и тези, работещи с обекти, е дълбоко естествено. От тази гледна точка нито един от тези методи, взет отделно от другия, не дава възможност да се формира адекватно отражение на предметната област. Между тези методи съществува връзка на допълване по смисъла на Н. Бор, следователно обещаващите системи за разпознаване трябва да осигуряват прилагането и на двата метода, а не само на един от тях.

По този начин класификацията на методите за разпознаване, предложена от Д. А. Поспелов, се основава на основните закони, които са в основата на човешкия начин на познание като цяло, което го поставя в много специална (привилегирована) позиция в сравнение с други класификации, които на този фон изглеждат по-лек и изкуствен.

Интензивни методи

Отличителна черта на интензивните методи е, че те използват като елементи на операции при конструирането и прилагането на алгоритми за разпознаване на образи различни характеристикифункции и техните взаимоотношения. Такива елементи могат да бъдат индивидуални ценностиили интервали от стойности на признаци, средни стойности и дисперсии, матрици на взаимоотношения на признаци и др., върху които се извършват действия, изразени в аналитична или конструктивна форма. В същото време обектите в тези методи не се разглеждат като интегрални информационни единици, а действат като индикатори за оценка на взаимодействието и поведението на техните атрибути.

Групата от методи за интензивно разпознаване на образи е обширна и нейното разделяне на подкласове е донякъде произволно:

– методи, базирани на оценки на плътността на разпределението на стойностите на характеристиките

– методи, базирани на предположения за класа на решаващите функции

– логически методи

– лингвистични (структурни) методи.

Методи, базирани на оценки на плътността на разпределението на стойностите на характеристиките.Тези методи за разпознаване на образи са заимствани от класическа теория статистически решения, в който обектите на изследване се разглеждат като реализации на многоизмерно случайна величинаразпределени в пространството на характеристиките според някакъв закон. Те се основават на байесова схема за вземане на решения, която се обръща към априорни вероятности на обекти, принадлежащи към конкретен разпознаваем клас и условни плътности на разпределение на стойностите на вектора на характеристиките. Тези методи се свеждат до определяне на съотношението на вероятността в различни полетамногоизмерно пространствено пространство.

Групата от методи, базирани на оценката на плътността на разпределението на стойностите на характеристиките, е пряко свързана с методите на дискриминантния анализ. Байесовият подход за вземане на решения е един от най-развитите в съвременната статистика, така наречените параметрични методи, за които аналитичният израз на закона за разпределение се счита за известен (в този случайнормален закон) и само малък брой параметри трябва да бъдат оценени (средни вектори и ковариационни матрици).

Тази група също така включва метод за изчисляване на коефициента на вероятност за независими характеристики. Този метод, с изключение на допускането за независимост на характеристиките (което в действителност почти никога не се изпълнява), не изисква познаване на функционалната форма на закона за разпределение. Може да се припише на непараметрични методи.

Особено място заемат други непараметрични методи, използвани когато формата на кривата на плътността на разпределението е неизвестна и изобщо не могат да се направят предположения за нейния характер. Те включват добре известния метод на многомерните хистограми, метода на „k-най-близките съседи“, метода на евклидовото разстояние, метода на потенциалните функции и др., чието обобщение е методът, наречен „оценки на Парзен“. Тези методи формално работят с обекти като интегрални структури, но в зависимост от вида на задачата за разпознаване, те могат да действат както в интензионален, така и в екстензионален хипостаз.

Непараметричните методи анализират относителния брой обекти, попадащи в дадените многомерни обеми, и използват различни функции на разстоянието между обектите на обучителната извадка и разпознатите обекти. За количествени признаци, когато техният брой е много по-малък от размера на извадката, операциите с обекти играят междинна роля при оценката на локалната плътност на разпространение условни вероятностии обектите не носят семантичното натоварване на самостоятелни информационни единици. В същото време, когато броят на характеристиките е съизмерим или по-голям от броя на изследваните обекти и характеристиките са от качествен или дихотомичен характер, тогава не може да се говори за никакви локални оценки на плътностите на разпределението на вероятностите. В този случай обектите в тези непараметрични методи се разглеждат като независими информационни единици (холистични емпирични факти) и тези методи придобиват значението на оценки на сходството и различието на изследваните обекти.

По този начин едни и същи технологични операции на непараметрични методи, в зависимост от условията на проблема, имат смисъл или локални оценки на плътностите на разпределение на вероятностите на стойностите на характеристиките, или оценки на приликата и разликата на обектите.

В контекста на интензивното представяне на знанието тук се разглежда първата страна на непараметричните методи, като оценки на плътностите на разпределение на вероятностите. Много автори отбелязват, че непараметричните методи като оценките на Парзен работят добре на практика. Основните трудности при прилагането на тези методи се считат за необходимостта да се запомни цялата обучителна извадка, за да се изчислят оценките на локалните плътности на разпределение на вероятностите и висока чувствителностдо непредставителността на обучителната извадка.

Методи, базирани на предположения за класа на решаващите функции.В тази група методи общата форма на решаващата функция се счита за известна и се дава нейният функционал на качеството. Въз основа на този функционал се търси най-доброто приближение на решаващата функция за последователността на обучение. Най-често срещаните са представяния на решаващи функции под формата на линейни и обобщени нелинейни полиноми. Качественият функционал на правилото за вземане на решение обикновено се свързва с класификационната грешка.

Основното предимство на методите, базирани на предположения за класа на решаващите функции, е яснотата на математическата формулировка на проблема за разпознаване като проблем за намиране на екстремум. Решението на този проблем често се постига с помощта на някакъв вид градиентни алгоритми. Разнообразието от методи от тази група се обяснява с широкия спектър от използвани функционали за качество на правилата за вземане на решения и алгоритми за търсене на екстремуми. Обобщение на разглежданите алгоритми, които включват по-специално алгоритъма на Нютон, алгоритми от типа на персептрон и др., Е методът на стохастичното приближение. За разлика от методите за параметрично разпознаване, успехът на тази група методи не зависи толкова от несъответствието на теоретичните представи за законите на разпределение на обектите в пространството на признаците с емпиричната реалност. Всички операции са предмет на един основна цел- намиране на екстремума на функционала на качеството на решаващото правило. В същото време резултатите от параметричния и разглеждания метод могат да бъдат сходни. Както е показано по-горе, параметрични методи за случая нормални разпределенияобекти в различни класове с равни ковариационни матрици водят до линейни решаващи функции. Също така отбелязваме, че алгоритмите за избор на информативни характеристики в линейни диагностични модели могат да се интерпретират като конкретни варианти на градиентни алгоритми за търсене на екстремум.

Възможности на градиентни алгоритми за търсене на екстремуми, особено в групата на линейните правила за вземане на решения, са доста добре проучени. Конвергенцията на тези алгоритми е доказана само за случая, когато разпознаваемите класове обекти се показват в пространството на характеристиките чрез компактни геометрични структури. Въпреки това, желанието да се постигне достатъчно качество на правилото за решаване често може да бъде удовлетворено с помощта на алгоритми, които нямат строг математическо доказателствосходимост на решението към глобалния екстремум .

Такива алгоритми включват голяма група процедури за евристично програмиране, представящи посоката на еволюционното моделиране. Еволюционното моделиране е бионичен метод, заимстван от природата. Тя се основава на използването на известни механизми на еволюцията, за да се замени процесът на смислено моделиране на сложен обект с феноменологично моделиране на неговата еволюция.

Добре известен представител на еволюционното моделиране в разпознаването на образи е методът на групово отчитане на аргументи (MGUA). GMDH се основава на принципа на самоорганизацията, а алгоритмите на GMDH възпроизвеждат схемата на масов подбор. В алгоритмите GMDH членовете на обобщен полином се синтезират и избират по специален начин, който често се нарича полином на Колмогоров-Габор. Този синтез и селекция се извършват с нарастваща сложност и е невъзможно да се предвиди предварително каква крайна форма ще има обобщеният полином. Първо, обикновено се разглеждат прости комбинации по двойки от начални характеристики, от които се съставят уравненията на решаващите функции, като правило, не по-високи от втори ред. Всяко уравнение се анализира като независима решаваща функция, а стойностите на параметрите на съставените уравнения се намират по един или друг начин от обучителната извадка. След това от резултантния набор от функции за вземане на решения се избира част от най-добрите в известен смисъл. Качеството на отделните функции за решаване се проверява на контролна (тестова) проба, която понякога се нарича принцип на външно добавяне. Избраните частични решаващи функции се разглеждат по-долу като междинни променливи, които служат като начални аргументи за подобен синтез на нови решаващи функции и т.н. Процесът на такъв йерархичен синтез продължава до достигане на екстремума на критерия за качество на решаващата функция, което на практика се проявява в влошаване на това качество при опит за допълнително увеличаване на реда на членовете на полинома спрямо оригиналните характеристики.

Принципът на самоорганизация, който е в основата на GMDH, се нарича евристична самоорганизация, тъй като целият процес се основава на въвеждането на външни добавки, избрани евристично. Резултатът от решението може значително да зависи от тези евристики. Полученият диагностичен модел зависи от това как обектите са разделени на проби за обучение и тестване, как се определя критерият за качество на разпознаване, колко променливи са пропуснати в следващия ред за избор и т.н.

Тези характеристики на GMDH алгоритмите са характерни и за други подходи към еволюционното моделиране. Но тук отбелязваме още един аспект на разглежданите методи. Това е тяхната съдържателна същност. Използвайки методи, базирани на предположения за класа на функциите за вземане на решения (еволюционни и градиентни), може да се изградят диагностични модели висока сложности да получите практически приемливи резултати. В същото време постигането на практически цели в този случай не е придружено от извличане на нови знания за природата на разпознаваемите обекти. Възможността за извличане на това знание, по-специално знания за механизмите на взаимодействие на атрибути (характеристики), тук е фундаментално ограничена от дадената структура на такова взаимодействие, фиксирана в избраната форма на решаващи функции. Следователно максимумът, който може да се каже след конструирането на конкретен диагностичен модел, е да се изброят комбинациите от характеристики и самите характеристики, които са включени в получения модел. Но значението на комбинациите, които отразяват природата и структурата на разпределението на изследваните обекти, често остава неразкрито в рамките на този подход.

Булеви методи. Логическите методи за разпознаване на образи се основават на апарата на логическата алгебра и позволяват да се работи с информация, съдържаща се не само в отделни характеристики, но и в комбинации от стойности на характеристики. В тези методи стойностите на всеки атрибут се считат за елементарни събития.

В самата общ изгледлогическите методи могат да се характеризират като вид търсене на логически модели в обучителната извадка и формирането на определена система от правила за логическо решение (например под формата на връзки елементарни събития), всеки от които има собствено тегло. Групата на логическите методи е разнообразна и включва методи с различна сложност и дълбочина на анализ. За дихотомични (булеви) характеристики са популярни така наречените дървовидни класификатори, методът за тестване в задънена улица, алгоритъмът на Кора и други. По-сложните методи се основават на формализацията индуктивни методи D.S. Mill. Формализацията се извършва чрез конструиране на квазиаксиоматична теория и се основава на многосортирана многозначна логика с квантори над кортежи с променлива дължина.

Алгоритъмът на Kora, подобно на други логически методи за разпознаване на образи, е доста трудоемък, тъй като при избора на връзки е необходимо пълно изброяване. Следователно, когато се прилагат логически методи, се поставят високи изисквания към ефективната организация на изчислителния процес и тези методи работят добре със сравнително малки размери на функционалното пространство и само на мощни компютри.

Езикови (синтактични или структурни) методи.Лингвистичните методи за разпознаване на образи се основават на използването на специални граматики, които генерират езици, с помощта на които може да се опише набор от свойства на разпознаваеми обекти. Граматиката се отнася до правилата за конструиране на обекти от тези непроизводни елементи.

Ако описанието на изображенията се извършва с помощта на непроизводни елементи (подизображения) и техните връзки, тогава се използва лингвистичен или синтактичен подход за изграждане на системи за автоматично разпознаване, като се използва принципът на общността на свойствата. Едно изображение може да бъде описано с помощта на йерархична структура от подизображения, подобна на синтактичната структура на даден език. Това обстоятелство дава възможност за прилагане на теорията официални езици. Предполага се, че граматиката на изображенията съдържа крайни набори от елементи, наречени променливи, непроизводни елементи и правила за заместване. Характерът на правилата за заместване определя вида на граматиката. Сред най-изучаваните граматики са регулярните, контекстно-свободните и граматиките на преките съставни части. Ключовите точки на този подход са изборът на непроизводни елементи на изображението, обединяването на тези елементи и връзките, които ги свързват в граматиката на изображенията, и накрая, прилагането на процесите на анализ и разпознаване в съответните език. Този подход е особено полезен при работа с изображения, които или не могат да бъдат описани чрез числени измервания, или са толкова сложни, че техните локални характеристики не могат да бъдат идентифицирани и трябва да се обърнете към глобалните свойства на обектите.

Например Е.А. Бутаков, В.И. Островски, И.Л. Фадеев предлага следната структурасистеми за обработка на изображения (фиг. 3), използващи лингвистичен подход, където всеки от функционалните блокове е софтуерен (фърмуерен) комплекс (модул), който изпълнява съответните функции.

Фигура 3 Структурна схемаустройство за разпознаване

Опитите да се приложат методите на математическата лингвистика към проблема с анализа на изображенията водят до необходимостта от решаване на редица проблеми, свързани с картографирането на двумерна структура на изображение върху едномерни вериги на формален език.

Разширителни методи

В методите на тази група, за разлика от интензивното направление, на всеки изследван обект се дава самостоятелна диагностична стойност в по-голяма или по-малка степен. По същество тези методи са близки до клиничния подход, който разглежда хората не като верига от обекти, ранжирани по един или друг показател, а като цялостни системи, всеки от които е индивидуален и има специална диагностична стойност. Такова внимателно отношение към обектите на изследване не позволява да се изключи или загуби информация за всеки отделен обект, което се случва при прилагане на методите на интензивно насочване, като се използват обекти само за откриване и фиксиране на моделите на поведение на техните атрибути.

Основните операции при разпознаване на образи с помощта на обсъжданите методи са операциите за определяне на приликата и разликата на обекти. Обектите в посочената група методи играят ролята на диагностични прецеденти. В същото време, в зависимост от условията на конкретна задача, ролята на индивидуалния прецедент може да варира в най-широки граници: от основно и определящо до много косвено участие в процеса на разпознаване. От своя страна условията на проблема може да изискват за успешно решениеучастие на различен брой диагностични случаи: от един във всеки признат клас до целия размер на извадката, а също различни начиниизчисляване на мерки за сходство и различие на обекти. Тези изисквания обясняват по-нататъшното разделяне на разширените методи на подкласове:

метод за сравнение на прототип;

k-метод на най-близкия съсед;

екипи от правила за вземане на решения.

Метод за сравнение на прототип.Това е най-простият метод за екстензивно разпознаване. Използва се, например, когато разпознатите класове се показват в пространството на характеристиките в компактни геометрични групи. В този случай центърът на геометричната групировка на класа (или обектът, който е най-близо до центъра) обикновено се избира като прототипна точка.

За да се класифицира неизвестен обект, се намира най-близкият до него прототип и обектът принадлежи към същия клас като този прототип. Очевидно при този метод не се формират обобщени класови образи.

Като мярка за близост могат да се използват различни видове разстояния. Често за дихотомични характеристики се използва разстоянието на Хеминг, което в този случай е равно на квадрата на евклидовото разстояние. В този случай решаващото правило за класифициране на обекти е еквивалентно на линейна решаваща функция.

Този факт трябва да се отбележи специално. Той ясно демонстрира връзката между прототип и индикативно представяне на информация за структурата на данните. Използвайки горното представяне, например, всяка традиционна измервателна скала, която е линейна функция на стойностите на дихотомичните характеристики, може да се разглежда като хипотетичен диагностичен прототип. От своя страна, ако анализът на пространствената структура на разпознатите класове ни позволява да заключим, че те са геометрично компактни, тогава е достатъчно да заменим всеки от тези класове с един прототип, което всъщност е еквивалентно на линеен диагностичен модел.

На практика, разбира се, ситуацията често е различна от описания идеализиран пример. Изследовател, който възнамерява да приложи метод за разпознаване, базиран на сравнение с прототипите на диагностичните класове, е изправен пред трудни проблеми. Това е преди всичко изборът на мярка за близост (метрика), която може значително да промени пространствената конфигурация на разпределението на обектите. И второ, независим проблеме анализ на многомерни структури от експериментални данни. И двата проблема са особено остри за изследователя в условията на висока размерност на признаковото пространство, което е характерно за реалните проблеми.

Метод на k-най-близките съседи.Методът на k-най-близкия съсед за решаване на проблеми с дискриминантния анализ е предложен за първи път през 1952 г. Тя е следната.

При класифицирането на неизвестен обект се намира даден брой (k) други обекти, геометрично най-близки до него в пространството на характеристиките (най-близки съседи) с вече известна принадлежност към разпознаваеми класове. Решението за присвояване на неизвестен обект на конкретен диагностичен клас се взема чрез анализиране на информация за това известно членство на неговите най-близки съседи, например, като се използва просто преброяване на гласовете.

Първоначално методът на k-най-близкия съсед се счита за непараметричен метод за оценка на съотношението на вероятността. За този метод са получени теоретични оценки на неговата ефективност в сравнение с оптималния байесов класификатор. Доказано е, че вероятностите за асимптотична грешка за метода на k-най-близкия съсед превишават грешките на правилото на Байс не повече от два пъти.

Както беше отбелязано по-горе, в реални задачичесто е необходимо да се работи с обекти, които се описват с голям брой качествени (дихотомични) характеристики. В същото време размерът на пространството на характеристиките е съизмерим или надвишава обема на изследваната извадка. При такива условия е удобно всеки обект от обучителната извадка да се интерпретира като отделен линеен класификатор. После едното или другото диагностичен класе представен не от един прототип, а от набор от линейни класификатори. Комбинираното взаимодействие на линейни класификатори води до частична линейна повърхност, която разделя разпознаваемите класове в пространството на характеристиките. Видът на разделителната повърхност, състояща се от части от хиперравнини, може да варира и зависи от относителна позициякласифицирани колекции.

Може да се използва и друга интерпретация на механизмите за класифициране на k-най-близките съседи. Базира се на идеята за съществуването на някои латентни променливи, абстрактни или свързани чрез някаква трансформация с оригиналното пространство на характеристиките. Ако в пространството на латентните променливи разстоянията по двойки между обектите са същите като в пространството на първоначалните признаци, а броят на тези променливи е значително по-малко от числообекти, тогава интерпретацията на метода на k-най-близките съседи може да се разглежда от гледна точка на сравняване на непараметрични оценки на плътностите на разпределение на условните вероятности. Концепцията за латентни променливи, представена тук, е близка по природа до концепцията за истинска размерност и други представяния, използвани в различни методи за намаляване на размерността.

Когато използва метода на k-най-близките съседи за разпознаване на образи, изследователят трябва да реши трудния проблем с избора на показател за определяне на близостта на диагностицираните обекти. Този проблем в условията на висока размерност на пространственото пространство е изключително утежнен поради достатъчната трудоемкост. този метод, което става значимо дори за високопроизводителни компютри. Следователно тук, както и в метода на сравнение с прототипа, е необходимо да се реши творческа задачаанализ на многомерната структура на експерименталните данни за минимизиране на броя на обектите, представляващи диагностични класове.

Алгоритми за изчисляване на оценки (гласуване).Принципът на работа на алгоритмите за оценка (ABO) е да се изчисли приоритетът (резултатите за сходство), които характеризират „близостта“ на разпознатите и референтните обекти според системата от характеристики ансамбли, която е система от подмножества на даден набор на характеристиките.

За разлика от всички разгледани по-рано методи, алгоритмите за изчисляване на оценки работят с описания на обекти по принципно нов начин. За тези алгоритми обектите съществуват едновременно в много различни подпространства на пространството на характеристиките. Класът ABO довежда идеята за използване на функции до логично заключение: тъй като не винаги е известно кои комбинации от характеристики са най-информативни, в ABO степента на сходство на обектите се изчислява чрез сравняване на всички възможни или определени комбинации от характеристики включени в описанията на обектите.

Екипи от правила за вземане на решения.Правилото за вземане на решение използва схема за разпознаване на две нива. На първо ниво работят частни алгоритми за разпознаване, резултатите от които се комбинират на второ ниво в блока за синтез. Най-често срещаните методи за такава комбинация се основават на разпределението на областите на компетентност на определен алгоритъм. Най-простият начин да се намерят области на компетентност е априорно да се раздели пространството на характеристиките въз основа на професионалните съображения на определена наука (например стратификация на извадката според някои характеристики). След това за всяка от избраните области се изгражда собствен алгоритъм за разпознаване. Друг метод се основава на използването на формален анализ за определяне на локални области на пространството на характеристиките като околности на разпознаваеми обекти, за които успехът на всеки конкретен алгоритъм за разпознаване е доказан.

Най-общият подход за конструиране на блок за синтез разглежда получените индикатори на определени алгоритми като първоначални характеристики за конструиране на ново обобщено правило за вземане на решение. В този случай могат да се използват всички горепосочени методи за интензивни и екстензионални направления в разпознаването на образи. Ефективни за решаване на проблема за създаване на набор от правила за решаване са логическите алгоритми от типа "Кора" и алгоритмите за изчисляване на оценки (ABO), които са в основата на така наречения алгебричен подход, който осигурява изследване и конструктивно описание на алгоритми за разпознаване, в които се вписват всички съществуващи типове алгоритми.

Методи на невронни мрежи

Методите на невронната мрежа са методи, базирани на приложението различни видовеневронни мрежи (NN). Основните области на приложение на различни NN за разпознаване на образи и изображения:

приложение за извличане на ключови характеристики или характеристики на дадени изображения,

класифициране на самите изображения или характеристиките, вече извлечени от тях (в първия случай извличането на ключови характеристики става имплицитно в мрежата),

решение на оптимизационни проблеми.

Многопластов невронни мрежи. Архитектурата на многослойната невронна мрежа (MNN) се състои от последователно свързани слоеве, където невронът на всеки слой е свързан с всички неврони на предходния слой с неговите входове и изходите на следващия.

Най-простото приложение на еднослойна NN (наречена автоасоциативна памет) е да обучи мрежата да реконструира изображенията на захранването. Чрез подаване на тестово изображение към входа и изчисляване на качеството на реконструираното изображение, може да се оцени колко добре мрежата е разпознала входното изображение. Положителните свойства на този метод са, че мрежата може да възстанови изкривени и шумни изображения, но не е подходящ за по-сериозни цели.

MNN се използва и за директна класификация на изображения - входът е или самото изображение в някаква форма, или набор от предварително извлечени ключови характеристики на изображението, на изхода невронът с максимална активност показва принадлежност към разпознатия клас (фиг. 4). Ако тази активност е под определен праг, тогава се счита, че изпратеното изображение не принадлежи към нито един от известните класове. В процеса на обучение се установява съответствието на входните изображения с принадлежността към определен клас. Това се нарича контролирано обучение. Този подход е добър за задачи за контрол на достъпа за малка група хора. Този подход осигурява директно сравнение на самите изображения от мрежата, но с увеличаване на броя на класовете времето за обучение и работа на мрежата се увеличава експоненциално. Следователно, за задачи като търсене на подобен човек в голяма база данни, това изисква извличане на компактен набор от ключови характеристики, от които да се търси.

Класификационен подход, използващ честотните характеристики на цялото изображение, е описан в . Използван е еднослоен NS, базиран на многоценни неврони.

B показва използването на NN за класификация на изображения, когато мрежовият вход получава резултатите от разлагането на изображението по метода на главните компоненти.

В класическия MNS междуслойните невронни връзки са напълно свързани и изображението е представено като едномерен вектор, въпреки че е двуизмерно. Архитектурата на конволюционната невронна мрежа има за цел да преодолее тези недостатъци. Той използва локални рецепторни полета (осигуряващи локална двуизмерна свързаност на неврони), общи тегла (осигуряващи откриване на някои характеристики навсякъде в изображението) и йерархична организация с пространствена подизвадка (пространствена подизвадка). Конволюционната NN (CNN) осигурява частична устойчивост на промени в мащаба, измествания, завъртания, изкривявания.

MNS се използват и за откриване на обекти от определен тип. В допълнение към факта, че всеки обучен MNS може до известна степен да определи принадлежността на изображенията към „своите собствени“ класове, той може да бъде специално обучен да открива надеждно определени класове. В този случай изходните класове ще бъдат класове, които принадлежат и не принадлежат към дадения тип изображение. Използван е детектор на невронна мрежа за откриване на изображението на лицето във входното изображение. Изображението се сканира с прозорец от 20x20 пиксела, който се подава на входа на мрежата, която решава дали дадената област принадлежи към класа лица. Обучението се проведе както с помощта на положителни примери ( различни изображениялица) и негатив (изображения, които не са лица). За да се подобри надеждността на откриването, беше използвана група от NN, обучени с различни първоначални тегла, в резултат на което NN направиха грешки по различни начини и окончателно решениеприети с гласуване на целия екип.

Фигура 5. Главни компоненти (собствени лица) и разлагане на изображението на главни компоненти

NN се използва и за извличане на ключовите характеристики на изображението, които след това се използват за последваща класификация. В е показан метод за прилагане на невронна мрежа на метода за анализ на главните компоненти. Същността на метода за анализ на главните компоненти е да се получат максимално декорелираните коефициенти, които характеризират входните модели. Тези коефициенти се наричат ​​главни компоненти и се използват за статистическа компресия на изображение, при което малък брой коефициенти се използват за представяне на цялото изображение. NN с един скрит слой, съдържащ N неврона (който е много по-малък от измерението на изображението), обучен чрез метода на обратното разпространение на грешки за възстановяване на входното изображение на изхода, генерира коефициентите на първите N главни компоненти на изхода на скрити неврони, които се използват за сравнение. Обикновено се използват от 10 до 200 основни компонента. С увеличаването на броя на компонентите неговата представителност намалява значително и няма смисъл да се използват компоненти с големи числа. При използване на нелинейни функции на активиране на невронни елементи е възможно нелинейно разлагане на главни компоненти. Нелинейността ви позволява да отразявате по-точно вариациите във входните данни. Прилагайки анализ на главните компоненти към декомпозицията на изображения на лица, ние получаваме главните компоненти, наречени правилни лица, които също имат полезно свойство- има компоненти, които отразяват главно такива съществени характеристики на човек като пол, раса, емоции. Когато се възстановят, компонентите изглеждат като лице, като първите отразяват най-много обща формалица, последните - различни малки разлики между лицата (фиг. 5). Този метод е добре приложим за търсене на подобни изображения на лица в големи бази данни. Показана е и възможността за по-нататъшно намаляване на размера на главните компоненти с помощта на NS. Чрез оценка на качеството на реконструкцията на входното изображение може много точно да се определи дали то принадлежи към класа на лицата.

Невронни мрежи висок ред. Невронните мрежи от висок ред (HNN) се различават от MNN по това, че имат само един слой, но входовете на невроните също получават термини от висок ред, които са продукт на два или повече компонента на входния вектор. Такива мрежи могат също да образуват сложни разделителни повърхности.

Невронни мрежи на Хопфийлд. Hopfield NN (HSH) е еднослойна и напълно свързана (няма връзки на неврони към себе си), нейните изходи са свързани с входове. За разлика от MNS, NSH е релаксиращ, т.е. като е зададен в първоначално състояние, той функционира, докато достигне стабилно състояние, което ще бъде неговата изходна стойност. За да намерите глобалния минимум по отношение на проблеми с оптимизациятаизползвайте стохастични модификации на NSH.

Използването на NSH като асоциативна паметви позволява точно да възстановите изображенията, на които мрежата е обучена, когато на входа се подава изкривено изображение. В този случай мрежата ще „запомни“ най-близкото (в смисъл на местен минимуменергия) изображение и по този начин го разпознава. Такова функциониране може също да се разглежда като последователно приложение на описаната по-горе автоасоциативна памет. За разлика от автоасоциативната памет, NSH ще възстанови изображението идеално точно. За да се избегнат минималните смущения и да се увеличи капацитетът на мрежата, се използват различни методи.

Самоорганизиращи се невронни мрежи на Кохонен.Самоорганизиращите се невронни мрежи на Кохонен (SNNC) осигуряват топологично подреждане на пространството на входното изображение. Те позволяват топологично непрекъснато картографиране на входа n-мерно пространствокъм изхода m-мерен, m<

Когнитрон.Когнитронът в своята архитектура е подобен на структурата на зрителната кора, има йерархична многослойна организация, в която невроните между слоевете са свързани само локално. Обучавани чрез състезателно обучение (без учител). Всеки слой на мозъка прилага различни нива на обобщение; входният слой е чувствителен към прости модели, като линии, и тяхната ориентация в определени области на визуалната област, докато реакцията на други слоеве е по-сложна, абстрактна и независима от позицията на шаблона. Подобни функции се изпълняват в когнитрона чрез моделиране на организацията на зрителната кора.

Neocognitron е по-нататъшно развитие на идеята за когнитрон и по-точно отразява структурата на визуалната система, позволява ви да разпознавате изображения независимо от техните трансформации, завъртания, изкривявания и промени в мащаба.

Cognitron е мощен инструмент за разпознаване на изображения, но изисква високи изчислителни разходи, които в момента са непостижими.

Разгледаните методи на невронни мрежи осигуряват бързо и надеждно разпознаване на изображения, но при използването на тези методи възникват проблеми при разпознаването на триизмерни обекти. Този подход обаче има много предимства.

Заключение

В момента има доста голям брой системи за автоматично разпознаване на образи за различни приложни проблеми.

Разпознаването на образи чрез формални методи като фундаментално научно направление е неизчерпаемо.

Математическите методи за обработка на изображения имат голямо разнообразие от приложения: наука, технологии, медицина, социална сфера. В бъдеще ролята на разпознаването на образи в човешкия живот ще се увеличи още повече.

Методите на невронни мрежи осигуряват бързо и надеждно разпознаване на изображения. Този подход има много предимства и е един от най-обещаващите.

Литература

Д.В. Брилюк, В.В. Старовойтов. Невронни мрежови методи за разпознаване на изображения // /

Кузин Л.Т. Основи на кибернетиката: Основи на кибернетичните модели. Т.2. - М.: Енергия, 1979. - 584 с.

Перегудов F.I., Тарасенко F.P. Въведение в системния анализ: Учебник. - М .: Висше училище, 1997. - 389s.

Темников Ф.Е., Афонин В.А., Дмитриев В.И. Теоретични основи на информационните технологии. - М.: Енергия, 1979. - 511s.

Tu J., Gonzalez R. Принципи на разпознаване на образи. / пер. от английски. - М.: Мир, 1978. - 410s.

Уинстън П. Изкуствен интелект. / пер. от английски. - М.: Мир, 1980. - 520-те.

Фу К. Структурни методи в разпознаването на образи: Превод от английски. - М.: Мир, 1977. - 320-те.

Цыпкин Я.З. Основи на информационната теория на идентификацията. - М.: Наука, 1984. - 520-те.

Поспелов Г.С. Изкуственият интелект е в основата на новите информационни технологии. - М.: Наука, 1988. - 280s.

Ю. Лифшиц, Статистически методи за разпознаване на образи ///modern/07modernnote.pdf

Бор Н. Атомна физика и човешкото познание. / Превод от англ. - М.: Мир, 1961. - 151s.

Бутаков Е.А., Островски В.И., Фадеев И.Л. Обработка на изображения на компютър.1987.-236с.

Дуда Р., Харт П. Разпознаване на образи и анализ на сцена. / Превод от англ. - М.: Мир, 1978. - 510-те.

херцог В.А. Компютърна психодиагностика. - Санкт Петербург: Братство, 1994. - 365 с.

Айзенберг И. Н., Айзенберг Н. Н. и Кривошеев Г. А. Многоценни и универсални бинарни неврони: алгоритми за обучение, приложения за обработка и разпознаване на изображения. Лекционни бележки по изкуствен интелект - машинно обучение и извличане на данни в разпознаването на образи, 1999 г., стр. 21-35.

Ранганат С. и Арун К. Разпознаване на лица с помощта на трансформиращи характеристики и невронни мрежи. Pattern Recognition 1997, Vol. 30, стр. 1615-1622.

Головко В.А. Невроинтелигентност: теория и приложения. Книга 1. Организация и обучение на невронни мрежи с директна и обратна връзка - Брест: BPI, 1999, - 260s.

Vetter T. и Poggio T. Класове на линейни обекти и синтез на изображения от едно примерно изображение. IEEE Transactions on Pattern Analysis and Machine Intelligence 1997, Vol. 19, стр. 733-742.

Головко В.А. Невроинтелигентност: теория и приложения. Книга 2. Самоорганизация, устойчивост на грешки и използване на невронни мрежи - Брест: BPI, 1999, - 228s.

Lawrence S., Giles C. L., Tsoi A. C. и Back A. D. Разпознаване на лица: подход на конволюционна невронна мрежа. IEEE Transactions on Neural Networks, Special Issue on Neural Networks and Pattern Recognition, pp. 1-24.

Васерман Ф. Неврокомпютърна технология: Теория и практика, 1992 - 184с.

Rowley H. A., Baluja S. и Kanade T. Откриване на лица, базирано на невронни мрежи. IEEE Transactions on Pattern Analysis and Machine Intelligence 1998, Vol. 20, стр. 23-37.

Валентин Д., Абди Х., O "Toole A. J. и Cottrell G. W. Конекционистки модели на обработка на лица: проучване. IN: Pattern Recognition 1994, том 27, стр. 1209-1230.

Документ

Те съставят алгоритми разпознаванеизображения. МетодиразпознаванеизображенияКакто беше отбелязано по-горе ... реалността не е такава съществува„екосистеми като цяло“ и съществуватсамо няколко ... заключения от това подробно прегледметодиразпознаванепредставихме в...

1. Преглед на методите за идентифициране на хора въз основа на изображения на лица, като се вземат предвид характеристиките на визуалното разпознаване

   Преглед

   ... разпознаванеот човек на слабоконтрастни обекти, вкл. лица. Донесе прегледчесто срещани методи ... Съществувацяла линия методи ... начин, в резултат на проучването, платформа за развитие на методразпознаване ...

2. Имени Глазкова Валентина Владимировна ИЗСЛЕДВАНЕ И РАЗРАБОТВАНЕ НА МЕТОДИ ЗА КОНСТРУКЦИЯ НА СОФТУЕРНИ СРЕДСТВА ЗА КЛАСИФИКАЦИЯ НА МНОГОТЕМАТИЧНИ ХИПЕРТЕКСТОВИ ДОКУМЕНТИ Специалност 05

   Автореферат на дисертация

   хипертекстови документи. Главата съдържа прегледсъществуващметодирешение на разглеждания проблем, описание ... чрез отрязване на най-малко подходящи класове // Математика методиразпознаванеизображения: 13-та Всеруска конференция. Ленинградска област...

3. Слайд 0 Преглед на задачите на биоинформатиката, свързани с анализа и обработката на генетични текстове

   Лекция

   ДНК и протеинови последователности. Прегледзадачи на биоинформатиката като задачи ... сигнали изискват използването на съвр методиразпознаванеизображения, статистически подходи и ... с ниска генна плътност. Съществуващпрограмите за предсказване на гени не...

Съвременните роботи, оборудвани със системи за зрение, могат да виждат добре, за да работят с реалния свят. Те могат да заключат какъв тип обекти присъстват, в каква връзка са помежду си, какви групи образуват.

Същността на проблема за разпознаване е да се установи дали изследваните обекти имат фиксиран краен набор от признаци, който им позволява да бъдат отнесени към определен клас.

Целите на науката за разпознаване на образи:

Замяна на човешки експерт или сложна експертна система с по-проста система (автоматизация на човешката дейност или опростяване на сложни системи);

Изграждане на системи за обучение, които са в състояние да вземат решения, без да определят ясни правила, а именно системи, които са в състояние сами да синтезират правила за вземане на решения въз основа на някакъв краен брой примери за правилни решения, „демонстрирани“ на системата.

Задачи за разпознаванеможе да се характеризира по следния начин.

1. Това са информационни задачи, състоящи се от два основни етапа: привеждане на изходните данни в удобен за разпознаване вид и самото разпознаване.

2. В тези задачи може да се въведе концепцията за аналогия и сходство на обекти и да се формулира концепцията за близост на обекти като основа за приписване на обект към определен клас.

3. В тези задачи е възможно да се работи с набор от примери, чиято класификация е известна и които под формата на формализирани описания могат да бъдат представени на алгоритъма за разпознаване за адаптиране към задачата в процеса на обучение.

4. За тези проблеми е трудно да се изградят формални теории и да се приложат класически математически методи.

5. В тези задачи е възможна "лоша" информация.

Видове задачи за разпознаване:

Присвояване на представения обект на един от класовете (обучение с учител);

Автоматична класификация - разделяне на набор от обекти (ситуации) според тяхното описание в система от незастъпващи се класове;

Избор на набор от информационни характеристики за разпознаване;

Привеждане на изходните данни в удобен за разпознаване вид;

Динамично разпознаване и динамична класификация;

Прогнозни задачи.

Основни определения

Изображениее структурирано описание на обект или явление, представено чрез вектор на признаци, всеки елемент от който представлява числената стойност на един от признаците, характеризиращи дадения обект. С други думи: изображение е всеки обект, за който може да бъде измерен набор от определени цифрови характеристики. Пример за изображение: буква, изображение, кардиограма и др.

Цифров знак(или просто знак). е формула или друго описание на метод за съпоставяне на обект с определена числена характеристика, който работи в рамките на специфичен проблем за разпознаване на образи. За всеки обект могат да се дефинират няколко различни характеристики, т.е. няколко числени характеристики.

пространство за функции.N-мерно пространство, дефинирано за дадена задача за разпознаване, където N е фиксиран брой измерени характеристики за всякакви обекти. Векторът от пространството на характеристиките, съответстващ на обекта на проблема за разпознаване, е N-мерен вектор с компоненти (x1, x2, ..., xN), които са стойностите на характеристиките на този обект.

ОБЕКТ->Nхарактеристики->M-измерен вектор на характеристиките

Клас- неформализируема (като правило) идея за възможността за присвояване на произволен обект от набора от обекти на задачата за разпознаване на определена група обекти. За обекти от един и същи клас се предполага наличието на "сходство". За проблема с разпознаването на образи може да се дефинира произволен брой класове, по-голям от 1. Броят на класовете се означава с числото S.

Като цяло проблемът с разпознаването на образи се състои от две части: разпознаване и обучение.

Разпознаването на образи е класифицирането на определена група обекти въз основа на определени изисквания. Обектите, принадлежащи към един и същи клас изображения, имат общи свойства. Изискванията, които определят класификацията, могат да бъдат различни, тъй като различните ситуации изискват различни видове класификации.

Например при разпознаване на английски букви се формират 26 класа изображения. Въпреки това, за да се разграничат английските букви от китайските знаци по време на разпознаването, са необходими само два класа изображения.

Най-простият подход за разпознаване на образи е съпоставянето на шаблони. В този случай набор от изображения, по един от всеки клас изображения, се съхранява в паметта на машината. Входното (разпознаваемо) изображение (на неизвестен клас) се сравнява със стандарта на всеки клас. Класификацията се основава на предварително избран критерий за съвпадение или сходство. С други думи, ако входното изображение съвпада с шаблона от i-тия клас шаблони по-добре от всеки друг шаблон, тогава входният шаблон се класифицира като принадлежащ към i-тия клас шаблони.

Недостатъкът на този подход, т.е. съпоставянето със стандарт, е, че в някои случаи е трудно да се избере подходящ стандарт от всеки клас изображения и да се установи необходимият критерий за съвпадение.

По-напреднал подход е, че класификацията се основава на някакъв набор от избрани измервания, направени върху входните изображения. Предполага се, че тези избрани измервания, наречени „характеристики“, са инвариантни или нечувствителни към често срещани промени и изкривявания и имат малък излишък.

Специален случай на втория подход „измерване на признаци“, при който стандартите се съхраняват под формата на измерени признаци и в класификатора се използва специален класификационен критерий (сравнение).

Характеристиките се определят от разработчиците и трябва да бъдат инвариантни спрямо ориентацията, размера и формата на обектите.

И т.н. обекти, които се характеризират с краен набор от определени свойства и характеристики. Такива задачи се решават доста често, например при пресичане или шофиране по улица на светофари. Разпознаването на цвета на светещ светофар и познаването на правилата за движение ви позволява да вземете правилното решение дали да пресечете улицата или не.

Необходимостта от такова разпознаване възниква в различни области - от военното дело и системите за сигурност до цифровизацията на аналогови сигнали.

Проблемът с разпознаването на образи придоби изключително значение в условията на информационно претоварване, когато човек не може да се справи с линейно-последователното разбиране на постъпващите към него съобщения, в резултат на което мозъкът му преминава в режим на едновременност на възприятие и мислене. , за които подобно разпознаване е характерно.

Следователно не е случайно, че проблемът с разпознаването на образи се оказа в областта на интердисциплинарните изследвания, включително във връзка с работата по създаването на изкуствен интелект и създаването на технически системи. разпознаване на шаблонпривлича все повече внимание.

Енциклопедичен YouTube

1 / 4

Въведение в разпознаването на образи

Р.В. Шамин. Лекция № 6 Мрежи на Хопфийлд и Хеминг в проблемите на разпознаването на образи

[DDSH-2016]: Невронни мрежи и модерно компютърно зрение

Лекция 9. Експоненциално изглаждане. Разпознаване на образи: метод на k-тия най-близък съсед

субтитри

Насоки в разпознаването на образи

Има две основни направления:

• Изучаване на способностите за разпознаване на живите същества, тяхното обясняване и моделиране;
• Развитие на теорията и методите за конструиране на устройства за решаване на индивидуални задачи за приложни цели.

Официално изложение на проблема

Разпознаването на образи е приписването на първоначални данни към определен клас чрез подчертаване на основните характеристики, които характеризират тези данни от общата маса несъществени данни.

Когато задават проблеми с разпознаването, те се опитват да използват математически език, опитвайки се - за разлика от теорията на изкуствените невронни мрежи, където основата е да се получи резултат чрез експеримент - да заменят експеримента с логически разсъждения и математически доказателства.

Класическа постановка на проблема за разпознаване на образи: даден набор от обекти. Те трябва да бъдат класифицирани. Едно множество се представя от подмножества, които се наричат ​​класове. Дадени: информация за класове, описание на цялото множество и описание на информация за обект, чиято принадлежност към определен клас е неизвестна. Необходимо е според наличната информация за класовете и описанието на обекта да се определи към кой клас принадлежи този обект.

Най-често монохромните изображения се разглеждат при проблеми с разпознаването на образи, което прави възможно разглеждането на изображение като функция в равнина. Ако разгледаме точка, зададена на равнина T (\displaystyle T), където функцията изразява във всяка точка от изображението неговата характеристика - яркост, прозрачност, оптична плътност, то такава функция е формален запис на изображението.

Набор от всички възможни функции f (x, y) (\displaystyle f(x, y))на повърхността T (\displaystyle T)- има модел на набора от всички изображения X (\displaystyle X). Представяне на концепцията приликимежду изображенията можете да зададете задачата за разпознаване. Конкретната форма на такава настройка силно зависи от последващите етапи в разпознаването в съответствие с един или друг подход.

Някои методи за разпознаване на графични изображения

За оптично разпознаване на изображения можете да приложите метода на повторение на външния вид на обект под различни ъгли, мащаби, отмествания и т.н. За букви трябва да повторите шрифта, свойствата на шрифта и т.н.

Вторият подход е да се намери контурът на обекта и да се изследват неговите свойства (свързаност, наличие на ъгли и др.)

Друг подход е използването на изкуствени невронни мрежи. Този метод изисква или голям брой примери за задачата за разпознаване (с верни отговори), или специална структура на невронна мрежа, която отчита спецификата на тази задача.

Перцептронът като метод за разпознаване на образи

Ф. Розенблат, въвеждайки концепцията за модел на мозъка, чиято задача е да покаже как психологическите явления могат да възникнат в някаква физическа система, чиято структура и функционални свойства са известни, описва най-простите експерименти за разграничаване. Тези експерименти са изцяло свързани с методите за разпознаване на образи, но се различават по това, че алгоритъмът за решение не е детерминиран.

Най-простият експеримент, въз основа на който е възможно да се получи психологически значима информация за определена система, се свежда до факта, че на модела се представят два различни стимула и се изисква да реагира на тях по различни начини. Целта на такъв експеримент може да бъде да се проучи възможността за тяхното спонтанно разграничаване от системата при липса на намеса от експериментатора или, обратно, да се проучи принудителната дискриминация, при която експериментаторът се стреми да научи системата да извършва необходима класификация.

В учебен експеримент перцептронът обикновено се представя с определена последователност от изображения, която включва представители на всеки от класовете, които трябва да бъдат разграничени. Според някои правила за модифициране на паметта правилният избор на реакция се затвърждава. След това контролният стимул се представя на перцептрона и се определя вероятността за получаване на правилния отговор за стимули от този клас. В зависимост от това дали избраният контролен стимул съвпада или не с едно от изображенията, които са били използвани в тренировъчната последователност, се получават различни резултати:

1. Ако контролният стимул не съвпада с нито един от стимулите за обучение, тогава експериментът се свързва не само с чиста дискриминация, но включва и елементи обобщения.
2. Ако контролният стимул възбужда определен набор от сетивни елементи, които са напълно различни от онези елементи, които са били активирани под въздействието на предварително представени стимули от същия клас, тогава експериментът е изследване. чисто обобщение.

Перцептроните нямат способността за чисто обобщение, но те функционират доста задоволително в експерименти с дискриминация, особено ако контролният стимул съвпада достатъчно близо с един от моделите, за които перцептронът вече е натрупал известен опит.

Примери за проблеми с разпознаването на образи

• Разпознаване на баркод
• Разпознаване на регистрационен номер
• Разпознаване на изображения
• Разпознаване на локални зони от земната кора, в които се намират находища

В тази статия се заех да подчертая някои от фундаменталните резултати от теорията на машинното обучение по начин, който прави концепциите разбираеми за читателите, които са донякъде запознати с проблемите на класификацията и регресията. Идеята да напиша такава статия все по-ясно се проявяваше в съзнанието ми с всяка книга, която прочетох, в която идеите за преподаване на машини за разпознаване бяха разказани сякаш от средата и изобщо не беше ясно какво правят авторите на това или този метод, на който се разчита при разработването му. От друга страна, има редица книги, посветени на основните понятия в машинното обучение, но представянето на материала в тях може да изглежда твърде сложно за първо четене.

Мотивация

Нека разгледаме такава задача. Разполагаме с ябълки от два класа - вкусни и невкусни, 1 и 0. Ябълките имат характеристики - цвят и размер. Цветът ще се променя непрекъснато от 0 до 1, т.е. 0 - напълно зелена ябълка, 1 - напълно червена. Размерът може да се променя по същия начин, 0 - малка ябълка, 1 - голяма. Бихме искали да разработим алгоритъм, който да приема цвят и размер като вход и да връща класа на ябълка като изход - независимо дали е вкусна или не. Много е желателно броят на грешките в този случай да бъде колкото по-малък, толкова по-добре. В същото време имаме окончателен списък, който съдържа исторически данни за цвета, размера и класа на ябълките. Как бихме могли да решим такъв проблем?

логичен подход

Решавайки нашия проблем, първият метод, който може да ни хрумне, може да е следният: нека съставим ръчно правила if-else и в зависимост от стойностите на цвета и размера ще присвоим определен клас на ябълката. Тези. имаме предпоставки - това е цвят и размер, и има следствие - вкус на ябълка. Съвсем разумно е, когато има малко признаци и можете да оцените праговете за сравнение на око. Но може да се случи, че няма да е възможно да се измислят ясни условия и от данните не е очевидно кои прагове да се вземат, а броят на функциите може да се увеличи в бъдеще. Но какво ще стане, ако в нашия списък с исторически данни намерим две ябълки с еднакъв цвят и размер, но едната е отбелязана като вкусна, а другата не? По този начин нашият първи метод не е толкова гъвкав и мащабируем, колкото бихме искали.

Нотация

Нека въведем следната нотация. Ще обозначим тата ябълка като . От своя страна всеки се състои от две числа – цвят и размер. Ще обозначим този факт с двойка числа: . Означаваме класа на всяка -та ябълка като . Списъкът с исторически данни ще бъде обозначен с буквата , дължината на този списък е равна на . Елементът от този списък е стойността на атрибута на ябълката и нейния клас. Тези. . Ще го наречем още проба. С главни букви и ние обозначаваме променливи, които могат да приемат стойностите на определен признак и клас. Въвеждаме нова концепция - правило за вземане на решение е функция, която приема стойност на цвят и размер като вход и връща етикет на клас като изход:

Вероятностен подход

Развивайки идеята за логичен метод с предпоставки и последствия, нека си зададем въпроса - каква е вероятността -тата ябълка, която не принадлежи към нашата извадка, да е вкусна, предвид измерените стойности на цвят и размер? В нотацията на теорията на вероятностите този въпрос може да бъде написан по следния начин:

В този израз той може да се тълкува като предпоставка, като следствие, но преходът от предпоставка към следствие ще се подчинява на вероятностни закони, а не на логически. Тези. вместо таблица на истината с булеви стойности от 0 и 1 за класа, ще има вероятностни стойности, които приемат стойности от 0 до 1. Приложете формулата на Bayes и получете следния израз:

Нека разгледаме по-подробно дясната страна на този израз. Множителят се нарича априорна вероятност и означава вероятността да се намери вкусна ябълка сред всички възможни ябълки. Априорната вероятност да срещнете неприятна ябълка е . Тази вероятност може да отразява нашите лични познания за това как добрите и лошите ябълки са разпределени в природата. Например, знаем от миналия си опит, че 80% от всички ябълки са вкусни. Или можем да оценим тази стойност просто като преброим дела на вкусните ябълки в нашия списък с исторически данни S. Следващият множител показва колко е вероятно да получим определен цвят и стойност за размер на ябълка от клас 1. Този израз се нарича още функция на вероятността и може да бъде под формата на определено разпределение, например нормално. Ние използваме знаменателя като нормализираща константа, така че желаната вероятност да варира от 0 до 1. Крайната ни цел не е да търсим вероятности, а да намерим правило за вземане на решение, което веднага ще ни даде клас. Крайната форма на правилото за вземане на решение зависи от това какви стойности и параметри знаем. Например, можем да знаем само стойностите на предишната вероятност, а останалите стойности не могат да бъдат оценени. Тогава решаващото правило ще бъде следното - да се присвои на всички ябълки стойността на класа, за който априорната вероятност е най-голяма. Тези. ако знаем, че 80% от ябълките в природата са вкусни, тогава за всяка ябълка поставяме клас 1. Тогава грешката ни ще бъде 20%. Ако можем също така да оценим стойностите на функцията на вероятност $p(X=x_m | Y=1)$, тогава можем също да намерим стойността на изискваната вероятност, използвайки формулата на Bayes, както е написано по-горе. Правилото за вземане на решение тук ще бъде следното: поставете етикета на класа, за който вероятността е максимална:

Ще наречем това правило байесов класификатор. Тъй като имаме работа с вероятности, дори голяма стойност на вероятността не гарантира, че ябълката не принадлежи към клас 0. Нека оценим вероятността за грешка на ябълката, както следва: ако правилото за вземане на решение върна стойността на класа, равна на 1, тогава вероятността за грешка ще бъде и обратно:

Ние се интересуваме от вероятността за грешка в класификатора не само в този конкретен пример, но като цяло за всички възможни ябълки:

Този израз е математическото очакване на грешката. И така, решавайки първоначалния проблем, стигнахме до байесовия класификатор, но какви са неговите недостатъци? Основният проблем е да се оцени условната вероятност от данните. В нашия случай ние представяме обекта като двойка числа - цвят и размер, но при по-сложни задачи размерността на характеристиките може да бъде многократно по-голяма и броят на наблюденията от нашия списък с исторически данни може да не е достатъчен за оценка на вероятността на многомерна случайна променлива. След това ще се опитаме да обобщим нашата концепция за грешка в класификатора и също така ще видим дали е възможно да изберем друг класификатор за решаване на проблема.

Загуби поради грешки в класификатора

Да предположим, че вече имаме някакъв вид правило за вземане на решения. След това може да направи два вида грешки - първият е да присвои обект към клас 0, който има реален клас 1, и обратното, да присвои обект към клас 1, който има реален клас 0. В някои проблеми, може да е важно да се прави разлика между тези случаи. Например повече страдаме от това, че ябълка, обозначена като вкусна, се е оказала безвкусна и обратното. Формализираме степента на нашия дискомфорт от измамени очаквания в концепцията.По-общо казано, имаме функция за загуба, която връща число за всяка грешка в класификатора. Нека бъде истински класен етикет. След това функцията за загуба връща стойността на загубата за действителния етикет на класа и стойността на нашето правило за вземане на решения. Пример за използване на тази функция е да вземем от ябълка с известен клас, да подадем ябълката към входа на нашето правило за вземане на решение, да получим оценката на класа от правилото за вземане на решение, ако стойностите и съвпадат, тогава считаме, че класификаторът не е сбъркал и няма загуба, ако стойностите не съвпадат, тогава размерът на загубата ще каже нашата функция

Условен и байесов риск

Сега, когато имаме функция за загуба и знаем колко губим от неправилна класификация на обекти, би било хубаво да разберем колко губим средно за много обекти. Ако знаем стойността - вероятността -тата ябълка да е вкусна, предвид измерените стойности на цвета и размера, както и реалната стойност на класа (например вземете ябълка от проба S, вижте в началото на статията), тогава можем да въведем концепцията за условен риск. Условният риск е средната стойност на загубите в съоръжението за правилото за вземане на решение:

В нашия случай на двоична класификация, когато се окаже:

По-горе описахме правилото за вземане на решение, което приписва обект към класа, който има най-висока стойност на вероятността. Такова правило осигурява минимум на нашите средни загуби (Байесов риск), така че Байесовият класификатор е оптимален по отношение на рисковия функционал, който въведохме . Това означава, че байесовият класификатор има възможно най-малката класификационна грешка.

Някои типични функции на загуба

Една от най-често срещаните функции на загуба е симетрична функция, когато загубите от първия и втория тип грешки са еквивалентни. Например функцията за загуба 1-0 (загуба нула-едно) се дефинира, както следва:

Тогава условният риск за a(x) = 1 ще бъде просто стойността на вероятността за получаване на клас 0 на обект:

По същия начин за a(x) = 0:

Функцията за загуба 1-0 приема стойност 1, ако класификаторът направи грешка в обекта и 0, ако не го направи. Сега нека направим така, че стойността на грешката да не е 1, а друга функция Q, в зависимост от правилото за вземане на решение и етикета на реалния клас:

Тогава условният риск може да се запише по следния начин:

Бележки за нотацията

Предишният текст е написан според нотацията, възприета в книгата на Дуда и Харт. В оригиналната книга на V.N. Вапник разглежда такъв процес: природата избира обект според разпределението $p(x)$ и след това му присвоява класов етикет според условното разпределение $p(y|x)$. Тогава рискът (очакването на загуба) се определя като

Къде е функцията, с която се опитваме да апроксимираме неизвестната зависимост, е функцията на загубата за реалната стойност и стойността на нашата функция. Тази нотация е по-описателна, за да се въведе следващото понятие – емпиричен риск.

Емпиричен риск

На този етап вече разбрахме, че логическият метод не е подходящ за нас, защото не е достатъчно гъвкав и не можем да използваме байесовия класификатор, когато има много характеристики и има ограничен брой данни за обучение, и няма да можем да възстановим вероятността. Знаем също, че байесовият класификатор има възможно най-малката класификационна грешка. Тъй като не можем да използваме байесов класификатор, нека вземем нещо по-просто. Нека фиксираме някакво параметрично семейство от функции H и да изберем класификатор от това семейство.

Пример: нека наборът от всички функции на формата

Всички функции от този набор ще се различават една от друга само по коефициенти.Когато избрахме такова семейство, предположихме, че в координатите цвят-размер между точки от клас 1 и точки от клас 0 е възможно да се начертае права линия с коефициенти по такъв начин, че точки с различни класове да са разположени по противоположните страни на права линия. Известно е, че за права линия от този вид векторът на коефициентите е нормалата към правата линия. Сега правим това - вземаме нашата ябълка, измерваме нейния цвят и размер и нанасяме точка с получените координати върху графиката в осите цвят-размер. След това измерваме ъгъла между тази точка и вектора $w$. Отбелязваме, че нашата точка може да лежи от едната или от другата страна на линията. Тогава ъгълът между и точката ще бъде или остър, или тъп, а скаларното произведение е или положително, или отрицателно. Тук идва правилото за вземане на решения:

След като сме фиксирали класа на функциите $H$, възниква въпросът - как да изберем функция от него с необходимите коефициенти? Отговорът е - нека изберем функцията, която доставя минимума на нашия байесов риск $R()$. Отново проблемът е, че за да изчислите стойностите на байесовия риск, трябва да знаете разпределението $p(x,y)$, но то не ни е дадено и не винаги е възможно да се възстанови то. Друга идея е да се минимизира рискът не на всички възможни обекти, а само на извадка. Тези. функция за минимизиране:

Тази функция се нарича емпиричен риск. Следващият въпрос е защо решихме, че като минимизираме емпиричния риск, минимизираме и байесовия риск? Напомням, че нашата практическа задача е да допускаме възможно най-малко класификационни грешки. Колкото по-малко са грешките, толкова по-нисък е байесовият риск. Обосновката за конвергенцията на емпиричния риск към Bayesian с увеличаване на количеството данни е получена през 70-те години от двама учени - V. N. Vapnik и A. Ya. Chervonenkis.

Гаранции за конвергенция. Най-простият случай

И така, стигнахме до извода, че байесовият класификатор дава възможно най-малката грешка, но в повечето случаи не можем да го обучим и не можем да изчислим грешката (риска) също. Въпреки това можем да изчислим приближение на байесовия риск, което се нарича емпиричен риск, и знаейки емпиричния риск, да изберем приближаваща функция, която би минимизирала емпиричния риск. Нека разгледаме най-простата ситуация, при която емпиричното минимизиране на риска води до класификатор, който минимизира и байесовия риск. В най-простия случай ще трябва да направим предположение, което рядко се изпълнява на практика, но което може да бъде отслабено по-късно. Ние фиксираме краен клас от функции, от които ще изберем нашия класификатор и приемаме, че истинската функция, която природата използва, за да маркира нашите ябълки за вкус, е в този краен набор от хипотези: . Имаме и извадка, получена от разпределение по обекти. Всички примерни обекти се считат за еднакво независимо разпределени (iid). Тогава ще е вярно следното

Теорема

Избирайки функция от клас, използващ емпирично минимизиране на риска, гарантираме, че ще намерим такава, че тя има малка байесова стойност на риска, ако извадката, върху която минимизираме, има достатъчен размер.

За значението на „малка стойност“ и „достатъчен размер“ вижте литературата по-долу.

Идеята за доказателство

По условието на теоремата получаваме извадка от разпределението , т.е. процесът на избиране на обекти от природата е случаен. Всеки път, когато събираме извадка, тя ще бъде от едно и също разпространение, но самите обекти в нея може да са различни. Основната идея на доказателството е, че можем да получим толкова неудачна извадка, че алгоритъмът, който избираме чрез минимизиране на емпиричния риск върху дадена извадка, ще бъде лош за минимизиране на байесовия риск, но в същото време ще бъде добър за минимизиране на емпиричния риск, но вероятността за получаване на такава извадка е малка и с увеличаване на размера на извадката тази вероятност пада. Подобни теореми съществуват за по-реалистични предположения, но ние няма да ги разглеждаме тук.

Практически резултати

Имайки доказателства, че функцията, намерена чрез минимизиране на емпиричния риск, няма да има голяма грешка върху ненаблюдавани преди това данни с достатъчен размер на обучителната извадка, можем да използваме този принцип на практика, например, както следва - приемаме израза:

И заместваме различни функции на загуба в зависимост от проблема, който се решава. За линейна регресия:

За логистична регресия:

Въпреки че опорните векторни машини са мотивирани основно от геометрията, те могат да се разглеждат и като емпирични проблеми за минимизиране на риска.

Заключение

Много контролирани методи на обучение могат да се разглеждат, наред с други неща, като специални случаи на теорията, разработена от В. Н. Вапник и А. Я. Червоненкис. Тази теория дава гаранции по отношение на грешката на тестовия набор, при достатъчен размер на обучаващия набор и някои изисквания за пространството на хипотезите, в което търсим нашия алгоритъм.

Използвани книги

• Природата на теорията за статистическото обучение, Владимир Н. Вапник
• Класификация на моделите, 2-ро издание, Ричард О. Дуда, Питър Е. Харт, Дейвид Г. Щъркел
• Разбиране на машинното обучение: от теория до алгоритми, Шай Шалев-Шварц, Шай Бен-Дейвид

P.S. Моля, пишете на лични за всички неточности и правописни грешки

Тагове: Добавете тагове

Живите системи, включително хората, са били постоянно изправени пред задачата за разпознаване на образи от самото им създаване. По-специално, информацията, идваща от сетивните органи, се обработва от мозъка, който от своя страна сортира информацията, осигурява вземането на решения и след това, използвайки електрохимични импулси, предава необходимия сигнал по-нататък, например към органите за движение, които изпълни необходимите действия. След това има промяна в околната среда и горните явления се появяват отново. И ако погледнете, тогава всеки етап е придружен от разпознаване.

С развитието на компютърните технологии стана възможно да се решат редица проблеми, които възникват в процеса на живот, да се улесни, ускори, подобри качеството на резултата. Например работата на различни системи за поддържане на живота, взаимодействието човек-компютър, появата на роботизирани системи и т.н. Отбелязваме обаче, че в момента не е възможно да се осигури задоволителен резултат при някои задачи (разпознаване на бързо движещи се подобни обекти , ръкописен текст).

Цел на работата: да се проучи историята на системите за разпознаване на образи.

Посочете качествените промени, настъпили в областта на разпознаването на образи, както теоретични, така и технически, като посочите причините;

Обсъждане на методите и принципите, използвани в изчисленията;

Дайте примери за перспективи, които се очакват в близко бъдеще.

1. Какво е разпознаване на образи?

Първите изследвания с компютърна техника основно следват класическата схема на математическо моделиране - математически модел, алгоритъм и изчисление. Това бяха задачите за моделиране на процесите, протичащи по време на експлозии на атомни бомби, изчисляване на балистични траектории, икономически и други приложения. Въпреки това, в допълнение към класическите идеи на тази поредица, имаше и методи, базирани на съвсем различно естество, и както показва практиката за решаване на някои проблеми, те често дават по-добри резултати от решенията, базирани на прекалено сложни математически модели. Тяхната идея беше да се откаже от желанието да се създаде изчерпателен математически модел на изследвания обект (освен това често беше практически невъзможно да се конструират адекватни модели) и вместо това да се задоволят с отговора само на конкретни въпроси, които ни интересуват, и тези отговори трябва да се търсят от съображения, общи за широк клас проблеми. Изследванията от този вид включват разпознаване на визуални изображения, прогнозиране на добиви, речни нива, проблем за разграничаване на нефтени и водоносни хоризонти с помощта на косвени геофизични данни и т.н. Конкретен отговор в тези задачи беше необходим в доста проста форма, като например например дали даден обект принадлежи към един от предварително фиксираните класове. И първоначалните данни на тези задачи, като правило, бяха дадени под формата на фрагментарна информация за обектите, които се изследват, например под формата на набор от предварително класифицирани обекти. От математическа гледна точка това означава, че разпознаването на образи (и този клас проблеми беше наречен у нас) е широкообхватно обобщение на идеята за екстраполация на функции.

Значението на подобна формулировка за техническите науки е извън съмнение и това само по себе си оправдава множество изследвания в тази област. Проблемът с разпознаването на образи обаче има и по-широк аспект за естествените науки (обаче би било странно нещо толкова важно за изкуствените кибернетични системи да не е важно за естествените). Контекстът на тази наука органично включва въпросите, поставени от древните философи за естеството на нашето знание, способността ни да разпознаваме образи, модели, ситуации от околния свят. Всъщност практически няма съмнение, че механизмите за разпознаване на най-простите образи, като образи на приближаващ опасен хищник или храна, са се формирали много по-рано от възникването на елементарния език и формалния логически апарат. И няма съмнение, че такива механизми са достатъчно развити и при висшите животни, които в своята жизнена дейност също спешно се нуждаят от способността да различават доста сложна система от признаци на природата. Така в природата виждаме, че феноменът на мисленето и съзнанието ясно се основава на способността за разпознаване на модели и по-нататъшният напредък на науката за интелигентността е пряко свързан с дълбочината на разбиране на основните закони на разпознаването. Разбирайки факта, че горните въпроси далеч надхвърлят стандартната дефиниция за разпознаване на образи (терминът контролирано обучение е по-често срещан в англоезичната литература), също така е необходимо да се разбере, че те имат дълбоки връзки с тази сравнително тясна (но все пак далеч не е изчерпана) посока.

Дори сега разпознаването на образи е навлязло твърдо в ежедневието и е едно от най-важните знания на съвременния инженер. В медицината разпознаването на образи помага на лекарите да поставят по-точни диагнози; във фабриките то се използва за прогнозиране на дефекти в партиди стоки. Биометричните системи за персонална идентификация като тяхно алгоритмично ядро ​​също се основават на резултатите от тази дисциплина. По-нататъшното развитие на изкуствения интелект, по-специално проектирането на компютри от пето поколение, способни на по-директна комуникация с човек на естествени езици за хората и чрез реч, е немислимо без признание. Тук роботиката, изкуствените системи за управление, съдържащи системи за разпознаване като жизненоважни подсистеми, са лесно достъпни.

Ето защо много внимание беше приковано към развитието на разпознаването на образи от самото начало от специалисти от различни профили - кибернетици, неврофизиолози, психолози, математици, икономисти и др. До голяма степен поради тази причина самото модерно разпознаване на образи се храни с идеите на тези дисциплини. Без да претендираме за изчерпателност (а е невъзможно да го претендираме в кратко есе), ще опишем историята на разпознаването на образи, ключовите идеи.

Дефиниции

Преди да преминем към основните методи за разпознаване на образи, даваме няколко необходими определения.

Разпознаването на образи (обекти, сигнали, ситуации, явления или процеси) е задача за идентифициране на обект или определяне на някое от неговите свойства чрез изображение (оптично разпознаване) или аудиозапис (акустично разпознаване) и други характеристики.

Една от основните е концепцията за набор, която няма конкретна формулировка. В компютъра наборът е представен от набор от неповтарящи се елементи от един и същи тип. Думата "неповтарящ се" означава, че някакъв елемент в набора или го има, или го няма. Универсалното множество включва всички възможни елементи за решаваната задача, празното множество не съдържа никакви.

Изображението е класификационна група в класификационната система, която обединява (изолира) определена група от обекти по някакъв признак. Образите имат характерно свойство, което се проявява в това, че запознаването с краен брой явления от едно и също множество позволява да се разпознае произволно голям брой от неговите представители. Изображенията имат характерни обективни свойства в смисъл, че различни хора, които се учат от различен материал за наблюдение, в по-голямата си част класифицират едни и същи обекти по един и същ начин и независимо един от друг. При класическата постановка на проблема за разпознаване универсалното множество се разделя на части-изображения. Всяко картографиране на който и да е обект към възприемащите органи на системата за разпознаване, независимо от неговото положение спрямо тези органи, обикновено се нарича изображение на обекта, а комплекти от такива изображения, обединени от някои общи свойства, са изображения.

Методът за присвояване на елемент на всяко изображение се нарича правило за вземане на решения. Друга важна концепция е метриката, начин за определяне на разстоянието между елементите на универсален набор. Колкото по-малко е това разстояние, толкова по-сходни са обектите (символи, звуци и т.н.), които разпознаваме. Обикновено елементите са посочени като набор от числа, а показателят е определен като функция. Ефективността на програмата зависи от избора на представяне на изображения и изпълнението на метриката, един алгоритъм за разпознаване с различни метрики ще прави грешки с различна честота.

Обучението обикновено се нарича процесът на развитие в дадена система на определена реакция към групи от външни идентични сигнали чрез многократно въздействие върху външната коригираща система. Такава външна корекция в обучението обикновено се нарича "насърчение" и "наказание". Механизмът за генериране на тази корекция почти напълно определя алгоритъма на обучение. Самообучението се различава от обучението по това, че тук не се съобщава допълнителна информация за правилността на реакцията към системата.

Адаптацията е процес на промяна на параметрите и структурата на системата, а евентуално и на управляващи действия, въз основа на текуща информация, за да се постигне определено състояние на системата с първоначална несигурност и променящи се условия на работа.

Обучението е процес, в резултат на който системата постепенно придобива способността да реагира с необходимите реакции на определени набори от външни въздействия, а адаптацията е настройка на параметрите и структурата на системата с цел постигане на необходимото качество на управление в условия на непрекъснати промени във външните условия.

Примери за задачи за разпознаване на образи: - Разпознаване на букви;