Огляд існуючих методів розпізнавання образів

Л.П. Попова , І.О. Датьєв

Здатність "розпізнавати" вважається основною властивістю людських істот, як, втім, інших живих організмів. Розпізнавання образів - розділ кібернетики, що розробляє принципи та методи класифікації, а також ідентифікації предметів, явищ, процесів, сигналів, ситуацій - всіх об'єктів, які можуть бути описані кінцевим набором деяких ознак або властивостей, що характеризують об'єкт.

Образ є описом об'єкта. Образи мають характерну властивість, що виявляється в тому, що ознайомлення з кінцевим числом явищ з однієї і тієї ж множини дає можливість дізнаватися скільки завгодно велика кількість його представників.

Теоретично розпізнавання образів можна назвати два основних напрями:

вивчення здібностей до розпізнавання, якими мають людські істоти та інші живі організми;

розвиток теорії та методів побудови пристроїв, призначених для вирішення окремих завдань розпізнавання образів у певних прикладних галузях.

Далі у статті описуються проблеми, принципи та методи реалізації систем розпізнавання образів, пов'язані з розвитком другого напряму. У другій частині статті розглядаються нейромережевые методи розпізнавання образів, які можна віднести до першого напряму теорії розпізнавання образів.

Проблеми побудови систем розпізнавання образів

Завдання, що виникають при побудові автоматичних систем розпізнавання образів, зазвичай можна віднести до кількох основних областей. Перша з них пов'язана з поданням " вихідних даних, отриманих як результати вимірювань для об'єкта, що підлягає розпізнаванню. Це проблема чутливості. Кожна виміряна величина є деякою "характеристикою образу або об'єкта. Припустимо, наприклад, що образами є буквено-цифрові символи. B такому випадку, в датчику може бути успішно використана вимірювальна сітківка, подібно до наведеної на рис. 1(а). Якщо сітківка складається з n-елементів, то результати вимірів можна подати у вигляді вектора вимірів або вектора образу ,

де кожен елемент xi приймає, наприклад, значення 1, якщо через i-ю комірку сітківки проходить зображення символу, і значення 0 в іншому випадку.

Розглянемо рис. 2(б). У цьому випадку образами служать безперервні функції (типу звукових сигналів) змінної t. Якщо вимір значень функцій проводиться у дискретних точках t1, t2, ..., tn, то вектор образу можна сформувати, прийнявши x1 = f (t1), x2 = f (t2), ... xn = f (tn).

Малюнок 1. Вимірювальна сітківка

Друга проблема розпізнавання образів пов'язана з виділенням характерних ознак або властивостей отриманих вихідних даних і зниженням розмірності векторів образів. Цю проблему часто визначають як проблему попередньої обробки та вибору ознак.

Ознаки класу образів є характерні властивості, загальні всім образів даного класу. Ознаки, що характеризують різницю між окремими класами, можна інтерпретувати як міжкласові ознаки. Внутрішньокласові ознаки, загальні всім класів, що розглядаються, не несуть корисної інформації з точки зору розпізнавання і можуть не братися до уваги. Вибір ознак вважається одним із важливих завдань, пов'язаних з побудовою систем, що розпізнають. Якщо результати вимірювань дозволяють отримати повний набір ознак для всіх класів, власне розпізнавання і класифікація образів не викликають особливих труднощів. Автоматичне розпізнавання тоді зведеться до процесу простого зіставлення чи процедур типу перегляду таблиць. B більшості практичних завдань розпізнавання, проте, визначення повного набору розрізнювальних ознак виявляється справою винятково важким, якщо взагалі неможливим. З вихідних даних зазвичай вдається отримати деякі з розрізняючих ознак і використовувати їх для спрощення процесу автоматичного розпізнавання образів. Зокрема, розмірність векторів вимірювань можна знизити за допомогою перетворень, що забезпечують мінімізацію втрати інформації.

Третя проблема, пов'язана з побудовою систем розпізнавання образів, полягає у пошуку оптимальних вирішальних процедур, необхідних при ідентифікації та класифікації. Після того як дані, зібрані про образи, що підлягають розпізнаванню, представлені точками або векторами вимірювань у просторі образів, надамо машині з'ясувати, якому класу образів ці дані відповідають. Нехай машина призначена для розрізнення класів M, позначених w1, w2, ... ..., wm. В такому випадку, простір образів можна вважати, що складається з M областей, кожна з яких містить точки, що відповідають образам одного класу. При цьому завдання розпізнавання може розглядатися як побудова меж областей рішень, що розділяють класи M, виходячи з зареєстрованих векторів вимірювань. Нехай ці межі визначені, наприклад, вирішальними функціями d1(x), d2(x),..., dm(x). Ці функції, звані також дискримінантними функціями, є скалярні та однозначні функції образу х. Якщо di(х) > dj(х), то образ х належить класу w1. Іншими словами, якщо i-я вирішальна функція di(x) має найбільше значення, то змістовною ілюстрацією подібної схеми автоматичної класифікації, що базується на реалізації процесу прийняття рішення, служить наведена на рис. 2 (на схемі "ГР" - генератор вирішальних функцій).

2. Схема автоматичної класифікації.

Вирішальні функції можна одержувати цілим рядом способів. В тих випадках, коли про образи, що розпізнаються, є повні апріорні відомості, вирішальні функції можуть бути визначені точно на основі цієї інформації. Якщо щодо образів є лише якісні відомості, можна висунути розумні припущення про вигляді вирішальних функцій. В останньому випадку межі областей рішень можуть істотно відхилятися від істинних, і тому необхідно створювати систему, здатну приходити до задовільного результату за допомогою ряду послідовних коригувань.

Об'єкти (образи), що підлягають розпізнаванню та класифікації за допомогою автоматичної системи розпізнавання образів, повинні мати набір вимірних характеристик. Коли цілої групи образів результати відповідних вимірів виявляються аналогічними, вважається, що це об'єкти належать одному класу. Мета роботи системи розпізнавання образів полягає в тому, щоб на основі зібраної інформації визначити клас об'єктів з характеристиками, аналогічними виміряним у об'єктів, що розпізнаються. Правильність розпізнавання залежить від обсягу розрізняючої інформації, що міститься у вимірюваних характеристиках, та ефективності використання цієї інформації.

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

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

При побудові алгоритмів розпізнавання класи еквівалентності можуть задаватися дослідником, який користується власними змістовними уявленнями або використовує зовнішню додаткову інформацію про схожість та відмінність об'єктів у контексті завдання. Тоді говорять про “розпізнавання з учителем”. Інакше, тобто. коли автоматизована система вирішує завдання класифікації без залучення зовнішньої навчальної інформації, говорять про автоматичну класифікацію чи “розпізнавання без вчителя”. Більшість алгоритмів розпізнавання образів потребує залучення значних обчислювальних потужностей, які можуть бути забезпечені лише високопродуктивною комп'ютерною технікою.

Різні автори (Ю.Л. Барабаш, В.І. Васильєв, А.Л. Горелік, В.А. Скрипкін, Р. Дуда, П. Харт, Л.Т.Кузін, Ф.І. Перегудов, Ф.П Тарасенко, Темников Ф.Є., Афонін В.А., Дмитрієв В.І., Дж. Ту, Р. Гонсалес, П. Вінстон, К. Фу, Я.З. Ципкін та ін.) дають різну типологію методів розпізнавання образів. Одні автори розрізняють параметричні, непараметричні та евристичні методи, інші - виділяють групи методів, виходячи з шкіл і напрямів, що історично склалися, в даній галузі.

У той самий час, відомі типології не враховують одну дуже істотну характеристику, яка відбиває специфіку способу уявлення знання предметної області з допомогою будь-якого формального алгоритму розпізнавання образів. Д.А.Поспелов виділяє два основні способи представлення знань:

Інтенсіональне уявлення - як схеми зв'язків між атрибутами (ознаками).

Екстенсіональне уявлення – за допомогою конкретних фактів (об'єкти, приклади).

Слід зазначити, що саме цих двох груп методів розпізнавання: оперують з ознаками, і оперують з об'єктами, глибоко закономірно. З цього погляду жоден із цих методів, взятий окремо від іншого, не дозволяє сформувати адекватне відображення предметної галузі. Між цими методами існує відношення додатковості у сенсі Н. Бора, тому перспективні системи розпізнавання повинні забезпечувати реалізацію обох цих методів, а не якогось одного з них.

Отже, основою класифікації методів розпізнавання, запропонованої Д.А.Поспеловым , покладено фундаментальні закономірності, які у основі людського способу пізнання взагалі, що ставить їх у цілком особливе (привілейоване) становище проти іншими класифікаціями, які у цьому фоні виглядають більш легковажними та штучними.

Інтенсіональні методи

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

Група інтенсіональних методів розпізнавання образів велика, і її розподіл на підкласи носить певною мірою умовний характер:

– методи, що ґрунтуються на оцінках щільностей розподілу значень ознак

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

– логічні методи

- Лінгвістичні (структурні) методи.

Методи, що ґрунтуються на оцінках щільностей розподілу значень ознак.Ці методи розпізнавання образів запозичені з класичної теорії статистичних рішень, у якій об'єкти дослідження розглядаються як реалізації багатовимірної випадкової величини, розподіленої у просторі ознак за яким-небудь законом. Вони базуються на байєсовській схемі прийняття рішень, що апелює до апріорних ймовірностей приналежності об'єктів до того чи іншого класу, що розпізнається, і умовним щільностям розподілу значень вектора ознак. Дані методи зводяться до визначення ставлення правдоподібності у різних галузях багатовимірного простору ознак.

Група методів, заснованих на оцінці щільності розподілу значень ознак, має пряме відношення до методів дискримінантного аналізу. Байєсовський підхід до прийняття рішень і відноситься до найбільш розроблених у сучасній статистиці так званих параметричних методів, для яких вважається відомим аналітичний вираз закону розподілу (в даному випадку нормальний закон) і потрібно оцінити лише невелику кількість параметрів (вектори середніх значень та матриці кваріації).

До цієї групи належить і метод обчислення ставлення правдоподібності для незалежних ознак. Цей метод, за винятком припущення про незалежність ознак (яке практично ніколи не виконується), не передбачає знання функціонального виду закону розподілу. Його можна віднести до непараметричних методів.

Інші непараметричні методи, що застосовуються тоді, коли вид кривої щільності розподілу невідомий і не можна взагалі ніяких припущень про її характер, займають особливе положення. До них відносяться відомі метод багатовимірних гістограм, метод "k-найближчих сусідів, метод евклідової відстані, метод потенційних функцій та ін., узагальненням яких є метод, який отримав назву "оцінки Парзена". Ці методи формально оперують об'єктами як цілісними структурами, але в залежності від типу завдання розпізнавання можуть виступати і в інтенсивній і екстенсійній іпостасях.

Непараметричні методи аналізують відносні кількості об'єктів, що потрапляють у задані багатовимірні обсяги, і використовують різні функції відстані між об'єктами навчальної вибірки та об'єктами, що розпізнаються. Для кількісних ознак, коли їх кількість набагато менше обсягу вибірки, операції з об'єктами відіграють проміжну роль в оцінці локальних щільностей розподілу умовних ймовірностей та об'єкти не несуть смислового навантаження самостійних інформаційних одиниць. У той самий час, коли кількість ознак порівнянно чи більше числа досліджуваних об'єктів, а ознаки носять якісний чи дихотомічний характер, то ні про які локальні оцінки щільностей розподілу ймовірностей не може йтися. У цьому випадку об'єкти в зазначених непараметричних методах розглядаються як самостійні інформаційні одиниці (цілісні емпіричні факти) і дані методи набувають сенсу оцінок подібності та відмінності досліджуваних об'єктів.

Отже, одні й самі технологічні операції непараметричних методів залежно та умовами завдання мають сенс або локальних оцінок щільностей розподілу ймовірностей значень ознак, чи оцінок подібності і розходження об'єктів.

У контексті інтенсіонального уявлення знань тут розглядається перша сторона непараметричних методів як оцінок щільностей розподілу ймовірностей. Багато авторів зазначають, що на практиці непараметричні методи на кшталт оцінок Парзена працюють добре. Основними труднощами застосування зазначених методів вважають необхідність запам'ятовування всієї навчальної вибірки для обчислення оцінок локальних щільностей розподілу ймовірностей і висока чутливість до непредставницькості навчальної вибірки.

Методи, що ґрунтуються на припущеннях про клас вирішальних функцій.У цій групі методів вважається відомим загальний вигляд вирішальної функції та заданий функціонал її якості. З цього функціоналу по навчальної послідовності шукається найкраще наближення вирішальної функції. Найпоширенішими є уявлення вирішальних функцій у вигляді лінійних та узагальнених нелінійних поліномів. Функціонал якості вирішального правила зазвичай пов'язують із помилкою класифікації.

Основною перевагою методів, заснованих на припущеннях про клас вирішальних функцій, є ясність математичної постановки задачі розпізнавання як завдання пошуку екстремуму. Вирішення цього завдання нерідко досягається за допомогою будь-яких градієнтних алгоритмів. Різноманітність методів цієї групи пояснюється широким спектром використовуваних функціоналів якості вирішального правила та алгоритмів пошуку екстремуму. Узагальненням аналізованих алгоритмів, яких ставляться, зокрема, алгоритм Ньютона, алгоритми перцептронного типу та інших., є метод стохастичної апроксимації. На відміну від параметричних методів розпізнавання успішність застосування цієї групи методів негаразд залежить від неузгодженості теоретичних уявлень про закони розподілу об'єктів у просторі ознак з емпіричною реальністю. Усі операції підпорядковані однієї головної мети - знаходження екстремуму функціоналу якості вирішального правила. У той самий час результати параметричних і аналізованих методів може бути схожими. Як показано вище, параметричні методи для випадку нормальних розподілів об'єктів у різних класах з рівними матрицями кваріації приводять до лінійних вирішальних функцій. Зазначимо також, що алгоритми відбору інформативних ознак у лінійних діагностичних моделях можна інтерпретувати як окремі варіанти градієнтних алгоритмів пошуку екстремуму.

Можливості градієнтних алгоритмів пошуку екстремуму, особливо у групі лінійних вирішальних правил, досить добре вивчені. Схожість цих алгоритмів доведена тільки для випадку, коли класи об'єктів, що розпізнаються, відображаються в просторі ознак компактними геометричними структурами. Однак прагнення домогтися достатньої якості вирішального правила нерідко може бути задоволене за допомогою алгоритмів, що не мають суворого доказу математичного доказу збіжності рішення до глобального екстремуму.

До таких алгоритмів відноситься велика група процедур евристичного програмування, що представляють напрямок еволюційного моделювання. Еволюційне моделювання є біонічним методом, запозиченим у природи. Воно ґрунтується на використанні відомих механізмів еволюції з метою заміни процесу змістовного моделювання складного об'єкта феноменологічним моделюванням його еволюції.

Відомим представником еволюційного моделювання у розпізнаванні образів є метод групового обліку аргументів (МГУА). В основу МГУА покладено принцип самоорганізації і алгоритми МГУА відтворюють схему масової селекції. У алгоритмах МГУА особливим чином синтезуються та відбираються члени узагальненого полінома, який часто називають поліномом Колмогорова-Габора. Цей синтез і відбір проводиться з наростаючим ускладненням, і заздалегідь не можна передбачити, який остаточний вигляд матиме узагальнений поліном. Спочатку зазвичай розглядають прості попарні комбінації вихідних ознак, з яких складаються рівняння вирішальних функцій, як правило, не вище за другий порядок. Кожне рівняння аналізується як самостійна вирішальна функція, і з навчальної вибірці тим чи іншим способом перебувають значення параметрів складених рівнянь. Потім з отриманого набору вирішальних функцій відбирається частина певному сенсі кращих. Перевірка якості окремих вирішальних функцій складає контрольної (перевірочної) вибірці, що іноді називають принципом зовнішнього доповнення. Відібрані приватні вирішальні функції розглядаються далі як проміжні змінні, що є вихідними аргументами для аналогічного синтезу нових вирішальних функцій тощо. буд. якості при спробах подальшого збільшення порядку членів поліном щодо вихідних ознак.

Принцип самоорганізації, покладений основою МГУА, називають евристичної самоорганізацією, оскільки весь процес полягає в запровадження зовнішніх доповнень, вибираних евристично. Результат рішення може суттєво залежати від цих евристиків. Від того, як розділені об'єкти на навчальну та перевірочну вибірки, як визначається критерій якості розпізнавання, скільки змінних пропускається в наступний ряд селекції тощо, залежить результуюча діагностична модель.

Зазначені особливості алгоритмів МГУА властиві та іншим підходам до еволюційного моделювання. Але зазначимо тут ще одну сторону методів, що розглядаються. Це – їх змістовна сутність. За допомогою методів, заснованих на припущеннях про клас вирішальних функцій (еволюційних та градієнтних), можна будувати діагностичні моделі високої складності та отримувати практично прийнятні результати. У той самий час досягненню практичних цілей у разі не супроводжує вилучення нових знань про природу об'єктів, що розпізнаються. Можливість отримання цих знань, зокрема знань про механізми взаємодії атрибутів (ознак), тут принципово обмежена заданою структурою такої взаємодії, зафіксованою у вибраній формі вирішальних функцій. Тому максимально, що можна сказати після побудови тієї чи іншої діагностичної моделі – це перерахувати комбінації ознак і самі ознаки, що увійшли до результуючої моделі. Але сенс комбінацій, що відбивають природу і структуру розподілів об'єктів, що досліджуються, в рамках даного підходу часто залишається нерозкритим.

Логічні методи. Логічні методи розпізнавання образів базуються на апараті алгебри логіки і дозволяють оперувати інформацією, укладеною у окремих ознаках, а й у поєднаннях значень ознак. У цих методах значення будь-якої ознаки сприймаються як елементарні події.

У найзагальнішому вигляді логічні методи можна охарактеризувати як різновид пошуку за навчальною вибіркою логічних закономірностей і формування деякої системи логічних вирішальних правил (наприклад, як кон'юнкцій елементарних подій), кожне з яких має власну вагу. Група логічних методів різноманітна і включає методи різної складності та глибини аналізу. Для дихотомічних (бульових) ознак популярними є звані деревоподібні класифікатори, метод тупикових тестів, алгоритм “Кора” та інші. Найбільш складні методи ґрунтуються на формалізації індуктивних методів Д.С.Мілля. Формалізація здійснюється шляхом побудови квазіаксіоматичної теорії та базується на багатосортній багатозначній логіці з кванторами по кортежах змінної довжини.

Алгоритм “Кора”, як та інші логічні методи розпізнавання образів, є досить трудомістким, оскільки за відборі кон'юнкцій необхідний повний перебір. Тому при застосуванні логічних методів висуваються високі вимоги до ефективної організації обчислювального процесу, і ці методи добре працюють при порівняно невеликих розмірностях простору ознак і тільки на потужних комп'ютерах.

Лінгвістичні (синтаксичні чи структурні) методи.Лінгвістичні методи розпізнавання образів засновані на використанні спеціальних граматик, що породжують мови, за допомогою яких може описуватися сукупність властивостей об'єктів, що розпізнаються. Граматикою називають правила побудови об'єктів із цих непохідних елементів.

Якщо опис образів виробляється з допомогою непохідних елементів (подобразів) та його відносин, то побудови автоматичних систем розпізнавання застосовується лінгвістичний чи синтаксичний підхід з допомогою принципу спільності властивостей. Образ можна описати за допомогою ієрархічної структури підобразів, аналогічної синтаксичною структурою мови. Ця обставина дозволяє застосовувати під час вирішення завдань розпізнавання образів теорію формальних мов. Передбачається, що граматика образів містить кінцеві множини елементів, званих змінними, непохідними елементами та правилами підстановки. Характер правил підстановки визначає тип граматики. Серед найбільш вивчених граматик можна відзначити регулярні, безконтекстні та граматики безпосередньо складових. Ключовими моментами даного підходу є вибір непохідних елементів образу, об'єднання цих елементів і зв'язуючих їх в граматики образів і, нарешті, реалізація у відповідній мові процесів аналізу та розпізнавання. Такий підхід особливо корисний при роботі з образами, які або не можуть бути описані числовими вимірами, або настільки складні, що їх локальні ознаки не вдається ідентифікувати і доводиться звертатися до глобальних властивостей об'єктів.

Наприклад, Є.А. Бутаков, В.І. Островський, І.Л. Фадєєв пропонують наступну структуру системи для обробки зображень (рис. 3), що використовує лінгвістичний підхід, де кожен із функціональних блоків є програмним (мікропрограмним) комплексом (модулем), що реалізує відповідні функції.

Малюнок 3. Структурна схема пристрою, що розпізнає

Спроби застосувати методи математичної лінгвістики до завдання аналізу зображень призводять до необхідності вирішити низку проблем, пов'язаних із відображенням двовимірної структури зображення на одномірні ланцюжки формальної мови.

Екстенсіональні методи

У методах цієї групи, на відміну від інтенсійного напряму, кожному об'єкту, що вивчається, більшою чи меншою мірою надається самостійне діагностичне значення. За своєю суттю ці методи близькі до клінічного підходу, який розглядає людей не як проранжований за тим чи іншим показником ланцюжок об'єктів, а як цілісні системи, кожна з яких є індивідуальною і має особливу діагностичну цінність. Таке дбайливе ставлення до об'єктів дослідження не дозволяє виключати або втрачати інформацію про кожен окремий об'єкт, що відбувається при застосуванні методів інтенсійного спрямування, які використовують об'єкти лише для виявлення та фіксації закономірностей поведінки їх атрибутів.

Основними операціями у розпізнаванні образів з допомогою обговорюваних методів є операції визначення подібності та відмінності об'єктів. Об'єкти у зазначеній групі методів відіграють роль діагностичних прецедентів. При цьому залежно від умов конкретної задачі роль окремого прецеденту може змінюватися в найширших межах: від головної та визначальної і до непрямої участі в процесі розпізнавання. У свою чергу умови завдання можуть вимагати для успішного вирішення участі різної кількості діагностичних прецедентів: від одного в кожному класі, що розпізнається, до повного обсягу вибірки, а також різних способів обчислення заходів подібності та відмінності об'єктів. Цими вимогами пояснюється подальший поділ екстенсіональних методів на підкласи:

метод порівняння із прототипом;

метод k-найближчих сусідів;

колективи вирішальних правил

Метод порівняння із прототипом.Це найпростіший екстенсіональний метод розпізнавання. Він застосовується, наприклад, тоді, коли класи, що розпізнаються, відображаються в просторі ознак компактними геометричними угрупованнями. У такому випадку зазвичай як точка – прототипу вибирається центр геометричного угруповання класу (або найближчий до центру об'єкт).

Для класифікації невідомого об'єкта знаходиться найближчий до нього прототип і об'єкт відноситься до того ж класу, що і цей прототип. Очевидно, жодних узагальнених образів класів у цьому методі не формується.

Як міру близькості можуть застосовуватися різні типи відстаней. Часто для дихотомічних ознак використовується відстань Хеммінга, яка в даному випадку дорівнює квадрату евклідової відстані. У цьому вирішальне правило класифікації об'єктів еквівалентно лінійної вирішальної функції.

Вказаний факт слід особливо наголосити. Він наочно демонструє зв'язок прототипної та ознакової репрезентації інформації про структуру даних. Користуючись наведеним уявленням, можна, наприклад, будь-яку традиційну вимірювальну шкалу, що є лінійною функцією від значень дихотомічних ознак, розглядати як гіпотетичний діагностичний прототип. У свою чергу, якщо аналіз просторової структури класів, що розпізнаються, дозволяє зробити висновок про їх геометричну компактність, то кожен з цих класів досить замінити одним прототипом який, фактично еквівалентний лінійній діагностичній моделі.

Насправді, звичайно, ситуація часто буває відмінною від описаного ідеалізованого прикладу. Перед дослідником, який має намір застосувати метод розпізнавання, що базується на порівнянні з прототипами діагностичних класів, постають непрості проблеми. Це, у першу чергу, вибір міри близькості (метрики), від якого може суттєво змінитися просторова конфігурація розподілу об'єктів. І по-друге, самостійною проблемою є аналіз багатовимірних структур експериментальних даних. Обидві ці проблеми особливо гостро постають перед дослідником за умов високої розмірності простору ознак, характерної реальних завдань.

Метод k-найближчих сусідів.Метод k-найближчих сусідів на вирішення завдань дискримінантного аналізу було вперше запропоновано ще 1952 року. Він полягає у наступному.

p align="justify"> При класифікації невідомого об'єкта знаходиться задане число (k) геометрично найближчих до нього в просторі ознак інших об'єктів (найближчих сусідів) з вже відомою приналежністю до класів, що розпізнаються. Рішення про віднесення невідомого об'єкта до того чи іншого діагностичного класу приймається шляхом аналізу інформації про цю відому приналежність його найближчих сусідів, наприклад, за допомогою простого підрахунку голосів.

Спочатку метод k-найближчих сусідів розглядався як непараметричний метод оцінювання відносин правдоподібності. Для цього методу отримано теоретичні оцінки його ефективності порівняно з оптимальним класифікатором байєсовським. Доведено, що асимптотичні ймовірності помилки для методу k-найближчих сусідів перевищують помилки правила Байєса не більше ніж у два рази.

Як зазначалося вище, у реальних завданнях часто доводиться оперувати об'єктами, що описуються великою кількістю якісних (дихотомічних) ознак. При цьому розмірність простору ознак можна порівняти або перевищує обсяг досліджуваної вибірки. У таких умовах зручно інтерпретувати кожен об'єкт навчальної вибірки як окремий лінійний класифікатор. Тоді той чи інший діагностичний клас є не одним зразком, а набором лінійних класифікаторів. Сукупна взаємодія лінійних класифікаторів дає в результаті шматково-лінійну поверхню, що розділяє в просторі ознак класи, що розпізнаються. Вигляд розділяючої поверхні, що складається з шматків гіперплощин, може бути різноманітним і залежить від взаємного розташування сукупностей, що класифікуються.

Також можна використовувати іншу інтерпретацію механізмів класифікації за правилом k-найближчих сусідів. У її основі лежить уявлення про існування деяких латентних змінних, абстрактних чи пов'язаних будь-яким перетворенням з вихідним простором ознак. Якщо в просторі латентних змінних попарні відстані між об'єктами такі ж, як і в просторі вихідних ознак, і кількість цих змінних значно менша за кількість об'єктів, то інтерпретація методу k-найближчих сусідів може розглядатися під кутом зору порівняння непараметричних оцінок щільностей розподілу умовних ймовірностей. Наведене тут уявлення про латентні змінні близько за своєю суттю до уявлення про справжню розмірність та інші уявлення, що використовуються в різних методах зниження розмірності.

При використанні методу k-найближчих сусідів для розпізнавання образів досліднику доводиться вирішувати складну проблему вибору метрики для визначення близькості об'єктів, що діагностуються. Ця проблема в умовах високої розмірності простору ознак надзвичайно загострюється внаслідок достатньої трудомісткості даного методу, що стає значущою навіть високопродуктивних комп'ютерів. Тому тут так само, як і в методі порівняння з прототипом, необхідно вирішувати творчу задачу аналізу багатовимірної структури експериментальних даних для мінімізації числа об'єктів, які мають діагностичні класи.

Алгоритми обчислення оцінок (голосування).Принцип дії алгоритмів обчислення оцінок (АВО) полягає у обчисленні пріоритеті (оцінок подібності), що характеризують “близькість” розпізнаваного та еталонних об'єктів за системою ансамблів ознак, що є системою підмножин заданої множини ознак.

На відміну всіх раніше розглянутих методів алгоритми обчислення оцінок принципово по-новому оперують описами об'єктів. Для цих алгоритмів об'єкти існують одночасно в різних підпросторах простору ознак. Клас АВО доводить ідею використання ознак до логічного кінця: оскільки завжди відомо, які поєднання ознак найбільш інформативні, то АВО ступінь подібності об'єктів обчислюється при зіставленні всіх можливих чи певних поєднань ознак, які входять у описи об'єктів .

Колективи вирішальних правил.У вирішальному правилі застосовується дворівнева схема розпізнавання. У першому рівні працюють приватні алгоритми розпізнавання, результати яких поєднуються другою рівні у блоці синтезу. Найбільш поширені способи такого об'єднання ґрунтуються на виділенні областей компетентності того чи іншого приватного алгоритму. Найпростіший спосіб знаходження областей компетентності полягає в апріорному розбиття простору ознак, виходячи з професійних міркувань конкретної науки (наприклад, розшарування вибірки за деякою ознакою). Тоді для кожної з виділених областей будується власний алгоритм, що розпізнає. Інший спосіб базується на застосуванні формального аналізу для визначення локальних областей простору ознак як околиць об'єктів, що розпізнаються, для яких доведена успішність роботи будь-якого приватного алгоритму розпізнавання.

Найзагальніший підхід до побудови блоку синтезу розглядає результуючі показники приватних алгоритмів як вихідні ознаки побудови нового узагальненого вирішального правила. У цьому випадку можуть використовуватися всі перераховані вище методи інтенсійного та екстенсійного напрямів у розпізнаванні образів. Ефективними для вирішення завдання створення колективу вирішальних правил є логічні алгоритми типу "Кора" та алгоритми обчислення оцінок (АВО), покладені в основу так званого підходу алгебри, що забезпечує дослідження і конструктивний опис алгоритмів розпізнавання, в рамки якого вкладаються всі існуючі типи алгоритмів.

Нейромережні методи

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

застосування для отримання ключових характеристик або ознак заданих образів,

класифікація самих образів або вже вилучених із них характеристик (у першому випадку вилучення ключових характеристик відбувається неявно всередині мережі),

вирішення оптимізаційних завдань.

Багатошарові нейронні мережі.Архітектура багатошарової нейронної мережі (МНС) складається з послідовно з'єднаних шарів, де нейрон кожного шару своїми входами пов'язаний з усіма нейронами попереднього шару, а виходами наступного.

Найпростіше застосування одношарової НС (названої автоасоціативною пам'яттю) полягає в навчанні мережі відновлювати зображення, що подаються. Подаючи на вхід тестове зображення та обчислюючи якість реконструйованого зображення, можна оцінити, наскільки мережа розпізнала вхідне зображення. Позитивні властивості цього методу полягають у тому, що мережа може відновлювати спотворені та зашумлені зображення, але для більш серйозних цілей він не підходить.

МНС також використовується для безпосередньої класифікації зображень – на вхід подається або саме зображення у якомусь вигляді, або набір раніше вилучених ключових характеристик зображення, на виході нейрон з максимальною активністю вказує на належність до розпізнаного класу (рис. 4). Якщо ця активність нижча за деякий поріг, то вважається, що поданий образ не відноситься до жодного з відомих класів. Процес навчання встановлює відповідність поданих на вхід образів з належністю до певного класу. Це називається навчанням з учителем. Такий підхід є хорошим для завдань контролю доступу невеликої групи осіб. Такий підхід забезпечує безпосереднє порівняння мережею самих образів, але зі збільшенням числа класів час навчання та роботи мережі зростає експоненційно. Тому для таких завдань, як пошук схожої людини у великій базі даних, вимагає отримання компактного набору ключових характеристик, на основі яких можна здійснювати пошук.

Підхід до класифікації з використанням частотних характеристик всього зображення описаний в . Застосовувалася одношарова СР, заснована на багатозначних нейронах.

У показано застосування СР для класифікації зображень, коли на вхід мережі надходять результати декомпозиції зображення за методом основних компонентів.

У класичній МНС міжшарові нейронні сполуки пов'язані, і зображення представлене у вигляді одновимірного вектора, хоча воно двовимірне. Архітектура згорткової СР спрямована на подолання цих недоліків. У ній використовувалися локальні рецепторні поля (забезпечують локальну двовимірну зв'язність нейронів), загальні ваги (забезпечують детектування деяких рис у будь-якому місці зображення) та ієрархічна організація з просторовими підвиборками (spatial subsampling). Згорткова СР (СНР) забезпечує часткову стійкість до змін масштабу, зсувів, поворотів, спотворень.

МНС застосовують і для виявлення об'єктів певного типу. Крім того, що будь-яка навчена МНС певною мірою може визначати належність образів до “своїх” класів, її можна навчити спеціально детектування певних класів. У цьому випадку вихідними класами будуть класи, що належать і не належать до заданого типу образів. У застосовувався нейромережевий детектор виявлення зображення обличчя у вхідному зображенні. Зображення сканувалося вікном 20х20 пікселів, яке подавалося на вхід мережі, що вирішує, чи належить ця ділянка до класу осіб. Навчання проводилося як із використанням позитивних прикладів (різних зображень осіб), так і негативних (зображень, що не є особами). Для підвищення надійності детектування використовувався колектив СР, навчених з різними початковими вагами, внаслідок чого СР помилялися по-різному, а остаточне рішення приймалося голосуванням всього колективу.

Малюнок 5. Головні компоненти (власні особи) та розкладання зображення на головні компоненти

СР застосовується також для вилучення ключових характеристик зображення, які потім використовуються для наступної класифікації. У , показаний метод нейромережевої реалізації методу аналізу основних компонентів. Суть методу аналізу основних компонентів полягає у отриманні максимально декореллированных коефіцієнтів, що характеризують вхідні образи. Ці коефіцієнти називаються головними компонентами та використовуються для статистичного стиснення зображень, у якому невелика кількість коефіцієнтів використовується для представлення всього образу. НС з одним прихованим шаром містить N нейронів (яке набагато менше ніж розмірність зображення), навчена методом зворотного поширення помилки відновлювати на виході зображення, подане на вхід, формує на виході прихованих нейронів коефіцієнти перших N головних компонент, які використовуються для порівняння. Зазвичай використовується від 10 до 200 основних компонентів. Зі збільшенням номера компоненти її репрезентативність сильно знижується, і використовувати компоненти з великими номерами немає сенсу. З використанням нелінійних активаційних функцій нейронних елементів можлива нелінійна декомпозиція на основні компоненти. Нелінійність дозволяє точніше відобразити варіації вхідних даних. Застосовуючи аналіз основних компонент до декомпозиції зображень осіб, отримаємо основні компоненти, звані власними особами, яким так само властива корисна властивість - існують компоненти, які в основному відображають такі суттєві характеристики особи як стать, раса, емоції. При відновленні компоненти мають вигляд, схожий на особу, причому перші відображають найбільш загальну форму обличчя, останні – різні дрібні відмінності між особами (рис. 5). Такий метод добре застосовується для пошуку схожих зображень осіб у великих базах даних. Показано також можливість подальшого зменшення розмірності основних компонентів за допомогою НС . Оцінюючи якість реконструкції вхідного зображення, можна дуже точно визначати його приналежність до класу осіб.

Нейронні мережі високого порядку.Нейронні мережі високого порядку (НСВП) відрізняються від МНС тим, що у них тільки один шар, але на входи нейронів надходять так само терми високого порядку, що є твором двох або більше компонентів вхідного вектора. Такі мережі можуть формувати складні розділяючі поверхні.

Нейронні мережі Хопфілд.НС Хопфілда (НСХ) є одношаровим і повнозв'язковим (зв'язки нейронів на самих себе відсутні), її виходи пов'язані з входами. На відміну МНС, НСХ є релаксаційної – тобто. будучи встановленою початковий стан, функціонує до того часу, доки досягне стабільного стану, що й буде її вихідним значенням. Для пошуку глобального мінімуму стосовно оптимізаційним завданням використовують стохастичні модифікації НСХ.

Застосування НСХ як асоціативна пам'ять дозволяє точно відновлювати образи, яким мережа навчена, при подачі на вхід спотвореного образу. У цьому мережа “згадає” найближчий (у сенсі локального мінімуму енергії) образ, і в такий спосіб розпізнає його. Таке функціонування так само можна як послідовне застосування автоасоціативної пам'яті, описаної вище. На відміну від автоасоціативної пам'яті НСХ ідеально точно відновить образ. Для уникнення інтерференційних мінімумів та підвищення ємності мережі використовують різні методи.

Самоорганізовані нейронні мережі Кохонена.Самоорганізовані нейронні мережі Кохонена (СНСК) забезпечують топологічне впорядкування вхідного простору образів. Вони дозволяють топологічно безперервно відображати вхідний n-вимірний простір у вихідний m-вимірний, m<

Когнітрон.Когнітрон своєю архітектурою нагадує будову зорової кори, має ієрархічну багатошарову організацію, у якій нейрони між шарами пов'язані лише локально. Навчається конкурентним навчанням (без учителя). Кожен шар мозку реалізує різні рівні узагальнення; вхідний шар чутливий до простих образів, таких, як лінії, та їх орієнтації у певних областях візуальної області, у той час як реакція інших шарів є більш складною, абстрактною та незалежною від позиції образу. Аналогічні функції реалізовані в когнітроні шляхом моделювання організації зорової кори.

Неокогнітрон є подальшим розвитком ідеї когнітрону і більш точно відображає будову зорової системи, що дозволяє розпізнавати образи незалежно від їх перетворень, обертань, спотворень та змін масштабу.

Когнітрон є потужним засобом розпізнавання зображень, проте вимагає високих обчислювальних витрат, які на сьогоднішній день недосяжні.

Розглянуті нейромережевые методи забезпечують швидке і надійне розпізнавання зображень, але з цих методів виникають проблеми розпізнавання тривимірних об'єктів. Проте цей підхід має масу переваг.

Висновок

В даний час існує досить велика кількість систем автоматичного розпізнавання образів для різних прикладних завдань.

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

Математичні методи обробки зображень мають найрізноманітніші застосування: наука, техніка, медицина, соціальна сфера. Надалі роль розпізнавання образів у житті буде зростати ще більше.

Нейромережні методи забезпечують швидке та надійне розпізнавання зображень. Даний підхід має масу переваг і є одним із найперспективніших.

Література

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

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

Перегудов Ф.І., Тарасенко Ф.П. Введення у системний аналіз: Навчальний посібник. - М.: Вища школа, 1997. - 389с.

Темніков Ф.Є., Афонін В.А., Дмитрієв В.І. Теоретичні засади інформаційної техніки. - М: Енергія, 1979. - 511с.

Ту Дж., Гонсалес Р. Принципи розпізнавання образів. /Пер. з англ. - М: Мир, 1978. - 410с.

Уінстон П. Штучний інтелект. /Пер. з англ. - М: Мир, 1980. - 520с.

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

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

Поспєлов Г.С. Штучний інтелект – основа нової інформаційної технології. - М: Наука, 1988. - 280с.

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

Бор Н. Атомна фізика та людське пізнання. /Пер.з англ. - М: Мир, 1961. - 151с.

Бутаков Є.А., Островський В.І., Фадєєв І.Л. Обробка зображень на ЕОМ.1987.-236с.

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

Дюк В.О. Комп'ютерна психодіагностика. – СПб: Братство, 1994. – 365с.

Aizenberg I. N., Aizenberg N. N. and Krivosheev G.A. Multi-valued і Universal Binary Neurons: Написання алгоритмів, Applications до Image Processing and Recognition. Lecture Notes in Artificial Intelligence – Machine Learning and Data Mining in Pattern Recognition, 1999, pp. 21-35.

Ranganath S. і Arun K. Face recognition використовуючи transform features and neural networks. Pattern Recognition 1997, Vol. 30, pp. 1615–1622.

Головко В.О. Нейроінтелект: Теорія та застосування. Книга 1. Організація та навчання нейронних мереж з прямими та зворотними зв'язками – Брест: БПІ, 1999, - 260с.

Vetter T. and Poggio T. Linear Object Classes and Image Synthesis From a Single Example Image. IEEE Transactions on Pattern Analysis and Machine Intelligence 1997, Vol. 19, pp. 733-742.

Головко В.О. Нейроінтелект: Теорія та застосування. Книга 2. Самоорганізація, стійкість до відмови і застосування нейронних мереж - Брест: БПИ, 1999, - 228с.

Lawrence S., Giles C. L., Tsoi A. C. and Back A. D. Face Recognition: A Convolutional Neural Network Approach. IEEE Transactions on Neural Networks, Special Issue on Neural Networks and Pattern Recognition, pp. 1-24.

Уоссермен Ф. Нейрокомп'ютерна техніка: Теорія та практика, 1992 - 184с.

Rowley H. A., Baluja S. and Kanade T. Neural Network-Based Face Detection. IEEE Transactions on Pattern Analysis and Machine Intelligence 1998, Vol. 20, pp. 23-37.

Valentin D., Abdi H., O"Toole A. J. and Cottrell G. W. Connectionist models of face processing: a survey. IN: Pattern Recognition 1994, Vol. 27, pp. 1209-1230.

Документ

Їм становлять алгоритми розпізнаванняобразів. МетодирозпізнаванняобразівЯк зазначалося вище... реальності не існує"екосистеми взагалі", а існуютьтільки окремі... висновки з цього детального оглядуметодіврозпізнаваннями представили в...

1. Огляд методів ідентифікації людей на основі зображень осіб з урахуванням особливостей візуального розпізнавання

   Огляд

   ... розпізнаваннялюдиною слабоконтрастних об'єктів, зокрема. осіб. Наведено оглядпоширених методів ... Існуєцілий ряд методів ... чином, в результаті проведеного дослідження підготовлено платформу для розробки методурозпізнавання ...

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

   Автореферат дисертації

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

3. Слайд 0 Огляд завдань біоінформатики пов'язаних з аналізом та обробкою генетичних текстів

   Лекція

   Послідовностей ДНК та білків. Оглядзадач біоінформатики як задач... сигналів вимагає застосування сучасних методіврозпізнаванняобразів, статистичних підходів та... з низькою щільністю генів Існуючіпрограми передбачення генів не...

Сучасні роботи, з системами технічного зору, здатні добре бачити, щоб працювати з реальним світом. Вони можуть робити висновок про те, якого типу об'єкти присутні, в яких відносинах вони знаходяться між собою, які утворюють групи.

Суть завдання розпізнавання – встановити, чи володіють об'єкти, що вивчаються, фіксованим кінцевим набором ознак, що дозволяє віднести і ке певному класу.

Цілі науки розпізнавання образів:

Заміна людського експерта чи складної експертної системи більш простою системою (автоматизація діяльності чи спрощення складних систем);

Побудова систем, що навчаються, які вміють приймати рішення без вказівки чітких правил, а саме, систем, які вміють самі синтезувати правила прийняття рішень на основі деякої кінцевої кількості «продемонстрованих» системі прикладів правильних рішень.

Завдання розпізнаванняможна охарактеризувати в такий спосіб.

1.Це інформаційні завдання, що складаються з двох основних етапів: приведення вихідних даних до виду, зручного для розпізнавання та власне розпізнавання.

2. У цих завданнях можна вводити поняття аналогії ІІ подоби об'єктів і формулювати поняття близькості об'єктів як основу для зарахування об'єкта до певного класу.

3. У цих завданнях можна оперувати набором прикладів, класифікація яких відома і які у вигляді формалізованих описів можуть бути пред'явлені алгоритму розпізнавання для налаштування завдання в процесі навчання.

4. Для цих завдань важко будувати формальні теорії та застосовувати класичні математичні методи.

5. У цих завданнях можлива погана інформація.

Типи завдань розпізнавання:

Віднесення пред'явленого об'єкта до одного з класів (навчання з учителем);

Автоматична класифікація – розбиття безлічі об'єктів (ситуацій) за їх описом на систему класів, що не перетинаються;

Вибір набору інформаційних ознак при розташуванні;

Приведення вихідних даних до виду, зручного для розпізнавання;

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

Завдання прогнозування.

Основні визначення

Образ- це структурований опис об'єкта або явища, представлений вектором ознак, кожен елемент якого представляє числове значення однієї з ознак, що характеризують даний об'єкт. Іншими словами: образ – будь-який об'єкт, для якого можна виміряти набір певних числових ознак. Приклад образу: літера, зображення, кардіограма тощо.

Числова ознака(або просто ознака). – це формула чи інший опис способу зіставлення об'єкту деякої числової характеристики, що у межах конкретної завдання розпізнавання образів. До кожного об'єкта можна визначити кілька різних ознак, тобто кілька числових характеристик.

Простір ознак.N-вимірний простір, визначений для даної задачі розпізнавання, де N - фіксована кількість вимірюваних ознак для будь-яких об'єктів. Вектор з простору ознак, що відповідає об'єкту завдання розпізнавання, це N-мірний вектор з компонентами (х1, х2, …, хN), які є значеннями ознак даного об'єкта.

ОБ'ЄКТ->N ознак-> M-мірний вектор ознак

Клас- неформалізоване (як правило) уявлення про можливість віднесення довільного об'єкта з безлічі об'єктів завдання розпізнавання до певної групи об'єктів. Для об'єктів одного класу передбачається наявність схожості. Для завдання розпізнавання образів може бути визначена довільна кількість класів, більша за 1. Кількість класів позначається числом S.

Загалом проблема розпізнавання образів складається з двох частин: розпізнавання та навчання.

Розпізнавання образів полягає у класифікації певної групи об'єктів на основі певних вимог. Об'єкти, що відносяться до одного класу образів, мають спільні властивості. Вимоги, що визначають класифікацію, можуть бути різними, тому що в різних ситуаціях виникає необхідність у різних типах класифікацій.

Наприклад, при розпізнаванні англійських букв утворюється 26 класів образів. Однак, щоб відрізнити при розпізнаванні англійські літери від китайських ієрогліфів, потрібні лише два класи образів.

Найпростіший підхід до розпізнавання образів у порівнянні з стандартами. У цьому випадку кілька образів, по одному з кожного класу образів, зберігається в пам'яті машини. Вхідний (розпізнаваний) образ (невідомого класу) порівнюється з ідеалом кожного класу. Класифікація полягає в заздалегідь обраному критерії відповідності чи критерії подоби. Інакше кажучи, якщо вхідний образ краще відповідає еталону i-го класу образів, ніж будь-якому іншому еталону, то вхідний образ класифікується як належить i-му класу образів.

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

Більш досконалий підхід полягає в тому, що класифікація ґрунтується на деякій кількості відібраних вимірів, що виробляються на вхідних образах. Ці відібрані виміри, звані «ознаками», передбачаються інваріантними або малочутливими по відношенню до змін і спотворень, що зазвичай зустрічаються, і володіють невеликою надмірністю.

Окремий випадок другого підходу «вимірювання ознак», у якому еталони зберігаються як виміряних ознак й у класифікаторі використовується спеціальний критерій класифікації (порівняння).

Ознаки визначаються розробниками і повинні бути інваріантними до орієнтації, розміру та варіацій форми об'єктів.

І т. п. об'єктів, які характеризуються кінцевим набором деяких властивостей та ознак. Такі завдання вирішуються досить часто, наприклад, під час переходу чи проїзду вулиці за сигналами світлофора. Розпізнавання кольору лампи світлофора і знання правил дорожнього руху дозволяє прийняти правильне рішення про те, можна або не можна переходити вулицю.

Необхідність у такому розпізнаванні виникає в різних областях - від військової справи і систем безпеки до оцифрування аналогових сигналів.

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

Невипадково, таким чином, проблема розпізнавання образу опинилася у полі міждисциплінарних досліджень - у тому числі у зв'язку з роботою зі створення штучного інтелекту, а створення технічних систем розпізнавання образупривертає до себе дедалі більшу увагу.

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

1 / 4

Введення у розпізнавання образів

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

[ДДШ-2016]: Нейронні мережі та сучасний комп'ютерний зір

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

Субтитри

Напрями у розпізнаванні образів

Можна виділити два основних напрямки:

• Вивчення здібностей до розпізнавання, якими мають живі істоти, пояснення та моделювання їх;
• Розвиток теорії та методів побудови пристроїв, призначених для вирішення окремих завдань у прикладних цілях.

Формальна постановка задачі

Розпізнавання образів - це віднесення вихідних даних до певного класу за допомогою виділення суттєвих ознак, що характеризують ці дані із загальної маси несуттєвих даних.

При постановці завдань розпізнавання намагаються користуватися математичною мовою, прагнучи - на відміну від теорії штучних, нейронних мереж, де основою є отримання результату шляхом експерименту, - замінити експеримент логічними міркуваннями та математичними доказами.

Класична постановка задачі розпізнавання образів: Дано безліч об'єктів. Щодо них необхідно провести класифікацію. Багато представлено підмножинами, які називаються класами. Задано: інформація про класи, опис всієї множини та опис інформації про об'єкт, належність якого до певного класу невідома. Потрібно за наявною інформацією про класи та опис об'єкта встановити - якого класу належить цей об'єкт.

Найчастіше в завданнях розпізнавання образів розглядаються монохромні зображення, що дає можливість розглядати зображення як функцію на площині. Якщо розглянути точкове безліч на площині 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. Застосуємо формулу Байєса і отримаємо наступне вираз:

Розглянемо праву частину цього виразу докладніше. Множник називається апріорною імовірністю і означає можливість зустріти смачне яблуко серед усіх можливих яблук. Апріорна ймовірність зустріти несмачне яблуко є. Ця можливість може відображати наше особисте знання про те, як розподілені смачні та несмачні яблука в природі. Наприклад, на наш минулий досвід ми знаємо, що 80% усіх яблук - смачні. Або ми можемо оцінити це значення просто порахувавши частку смачних яблук у нашому списку з історичними даними S. Наступний множник - показує, наскільки ймовірно отримати конкретне значення кольору та розміру для яблука класу 1. Цей вираз так само називається функцією правдоподібності і може мати вигляд якого- або конкретного розподілу, наприклад, нормального. Знаменник ми використовуємо як нормувальну константу, щоб шукана ймовірність змінювалася в межах від 0 до 1. Нашою кінцевою метою є не пошук ймовірностей, а пошук вирішального правила, яке б відразу давало нам клас. Кінцевий вигляд вирішального правила залежить від того, які значення та параметри нам відомі. Наприклад, ми можемо знати лише значення апріорної ймовірності, а решту оцінити неможливо. Тоді вирішальне правило буде таке – ставити всім яблукам значення того класу, для якого апріорна ймовірність найбільша. Тобто. якщо ми знаємо, що 80% яблук у природі смачні, то кожному яблуку ставимо клас 1. Тоді наша помилка становитиме 20%. Якщо ми до того ж можемо оцінити значення функції правдоподібності $p(X=x_m | Y=1)$, то можемо знайти значення шуканої ймовірності за формулою Байєса, як написано зверху. Вирішальне правило тут буде таким: поставити мітку того класу, для якого максимальна ймовірність:

Це правило назвемо Байєсівським класифікатором. Оскільки ми маємо справу з ймовірностями, то навіть велике значення ймовірності не дає гарантій, що яблуко не належить до класу 0. Оцінимо ймовірність помилки на яблуку таким чином: якщо вирішальне правило повернуло значення класу 1, то ймовірність помилитися буде і навпаки:

Нас цікавить ймовірність помилки класифікатора не лише на даному конкретному прикладі, а й взагалі для всіх можливих яблук:

Цей вираз є математичним очікуваний помилки. Отже, вирішуючи вихідну проблему, ми прийшли до байєсівського класифікатора, але які у нього є недоліки? Головна проблема - оцінити з даних умовну ймовірність. У нашому випадку ми представляємо об'єкт парою чисел - колір і розмір, але в складніших завданнях розмірність ознак може бути в рази вищою і для оцінки ймовірності багатовимірної випадкової величини може не вистачити числа спостережень із нашого списку з історичними даними. Далі ми спробуємо узагальнити наше поняття помилки класифікатора, а також подивимося, чи можна підібрати якийсь інший класифікатор для вирішення проблеми.

Втрати від помилок класифікатора

Припустимо, що ми вже маємо якесь вирішальне правило . Тоді воно може зробити два типи помилок - перший, це зарахувати об'єкт до класу 0, який має реальний клас 1 і навпаки, зарахувати об'єкт до класу 1, у якого реальний клас 0. У деяких завданнях буває важливо розрізняти ці випадки. Наприклад, ми страждаємо більше від того, що яблуко, позначене як смачне, виявилося несмачним і навпаки. Ступінь нашого дискомфорту від ошуканих очікувань ми формалізуємо у понятті Більше загально - ми маємо функцію втрат, яка повертає число кожної помилки класифікатора. Нехай – реальна мітка класу. Тоді функція втрат повертає величину втрат для реальної мітки класу та значення нашого вирішального правила. Приклад застосування цієї функції - беремо з яблуко з відомим класом, передаємо яблуко на вхід нашому вирішальному правилу, отримуємо оцінку класу від вирішального правила, якщо значення і збіглися, то вважаємо, що класифікатор не помилився і втрат немає, якщо значення не збігаються, то величину втрат скаже наша функція

Умовний та байєсовський ризик

Тепер, коли ми маємо функцію втрат і ми знаємо, скільки ми втрачаємо від неправильної класифікації об'єкта, було б непогано зрозуміти, скільки ми втрачаємо в середньому, на багатьох об'єктах. Якщо ми знаємо величину - ймовірність того, що яблуко буде смачне, за умови виміряних значень кольору і розміру, а також реальне значення класу (наприклад візьмемо яблуко з вибірки S, див. на початку статті), то можемо ввести поняття умовного ризику . Умовний ризик є середня величина втрат на об'єкті для вирішального правила:

У нашому випадку бінарної класифікації коли виходить:

Вище ми описували вирішальне правило, яке відносить об'єкт до того класу, який має найбільше значення імовірності. Це означає, що Байєсовський класифікатор має найменшу можливу помилку класифікації.

Деякі типові функції втрат

Однією з функцій втрат, що найчастіше зустрічаються, є симетрична функція, коли втрати від першого і другого типів помилок рівнозначні. Наприклад, функція втрат 1-0 (zero-one loss) визначається так:

Тоді умовний ризик для a(x) = 1 буде просто значенням ймовірності отримати клас 0 на об'єктці:

Аналогічно для a(x) = 0:

Функція втрат 1-0 приймає значення 1, якщо класифікатор робить помилку на об'єкті та 0 якщо не робить. Тепер зробимо так, щоб значення помилки дорівнювало не 1, а інший функції Q, яка залежить від вирішального правила і реальної мітки класу:

Тоді умовний ризик можна записати так:

Зауваження щодо нотації

Попередній текст був написаний згідно з нотацією, прийнятою в книзі Дуди та Харта. В оригінальній книзі В.М. Вапника розглядався такий процес: природа вибирає об'єкт згідно з розподілом $p(x)$, а потім ставить йому мітку класу згідно з умовним розподілом $p(y|x)$. Тоді ризик (маточкування втрат) визначається як

Де – функція, якою ми намагаємося апроксимувати невідому залежність, – функція втрат для реального значення та значення нашої функції. Ця нотації наочніша для того щоб ввести наступне поняття - емпіричний ризик.

Емпіричний ризик

На даному етапі ми вже з'ясували, що логічний метод нам не підходить, тому що він недостатньо гнучкий, а байєсовський класифікатор ми не можемо використовувати, коли ознак багато, а даних для навчання обмежена кількість і ми не зможемо відновити ймовірність. Також нам відомо, що байєсівський класифікатор має найменшу можливу помилку класифікації. Якщо ми не можемо використовувати байесовський класифікатор, давайте візьмемо що-небудь по простіше. Давайте зафіксуємо деяке параметричне сімейство функцій H і підбиратимемо класифікатор із цього сімейства.

Приклад: нехай багато всіх функцій виду

Усі функції цієї множини відрізнятимуться одна від одної лише коефіцієнтами Коли ми вибрали таке сімейство, ми припустили, що в координатах колір-розмір між точками класу 1 і точками класу 0 можна провести пряму лінію з коефіцієнтами таким чином, що точки з різними класами знаходяться по різні боки від прямої. Відомо, що у прямої такого виду вектор коефіцієнтів є нормаллю до прямої. Тепер робимо так – беремо наше яблуко, міряємо у нього колір та розмір і наносимо крапку з отриманими координатами на графік у осях колір-розмір. Далі міряємо кут між цією точкою та вектором $w$. Помічаємо, що наша точка може лежати або з одного, або з іншого боку від прямої. Тоді кут між точкою буде або гострий, або тупий, а скалярне твір або позитивне, або негативне. Звідси випливає вирішальне правило:

Після того, як ми зафіксували клас функцій $Н$, постає питання - як вибрати з нього функцію з потрібними коефіцієнтами? Відповідь – давайте виберемо ту функцію, яка доставляє мінімум нашому байєсовському ризику $R()$. Знову проблема - щоб порахувати значення байєсовського ризику, потрібно знати розподіл $p(x,y)$, а воно нам не дано, і відновити його не завжди можливо. Інша ідея – мінімізувати ризик не на всіх можливих об'єктах, а лише на вибірці. Тобто. мінімізувати функцію:

Ця функція називається емпіричним ризиком. Наступне питання - чому ми вирішили, що мінімізуючи емпіричний ризик, ми при цьому також мінімізуємо байєсовський ризик? Нагадаю, що наше завдання практичне - допустити якнайменше помилок класифікації. Чим менше помилок, тим менший ризик Байєса. Обґрунтування про збіжність емпіричного ризику до байєсівського із зростанням обсягу даних було отримано у 70-ті роки двома вченими – В. Н. Вапником та А. Я. Червоненкісом.

Гарантії збіжності. Найпростіший випадок

Отже, ми дійшли того, що байєсовський класифікатор дає найменшу можливу помилку, але навчити його здебільшого ми не можемо і помилку (ризик) порахувати ми теж не в змозі. Однак, ми можемо порахувати наближення до байєсовського ризику, яке називається емпіричний ризик, а знаючи емпіричний ризик підібрати таку апроксимуючу функцію, яка мінімізувала б емпіричний ризик. Давайте розглянемо найпростішу ситуацію, коли мінімізація емпіричного ризику дає класифікатор, який також мінімізує байєсовський ризик. Для найпростішого випадку нам доведеться зробити припущення, яке рідко виконується на практиці, але яке надалі можна буде послабити. Зафіксуємо кінцевий клас функцій з якого ми вибиратимемо наш класифікатор і припустимо, що справжня функція, яку використовує природа для розмітки наших яблук на смаки знаходиться в цій кінцевій множині гіпотез: . Також у нас є вибірка, отримана з розподілу над об'єктами. Усі об'єкти вибірки вважаємо однаково незалежно розподіленими (iid). Тоді буде вірна наступна

Теорема

Вибираючи функцію з класу за допомогою мінімізації емпіричного ризику, ми гарантовано знайдемо таку, що вона має невелике значення байєсовського ризику, якщо вибірка, на якій ми виробляємо мінімізацію, має достатній розмір.

Що означає «невелике значення» та «достатній розмір» див. у літературі нижче.

Ідея доказу

За умовою теореми отримуємо вибірку з розподілу , тобто. процес вибору об'єктів із природи випадковий. Щоразу, коли ми збираємо вибірку, вона буде з того ж розподілу, але самі об'єкти в ній можуть бути різні. Головна ідея доказу полягає в тому, що ми можемо отримати таку невдалу вибірку, що алгоритм, який ми виберемо за допомогою мінімізації емпіричного ризику на даній вибірці, погано мінімізуватиме байєсовський ризик, але при цьому добре мінімізувати емпіричний ризик, але ймовірність отримати таку вибірку мала й зростанням. розміру вибірки ця можливість падає. Подібні теореми існують і для більш реалістичних припущень, але тут ми їх не розглядатимемо.

Практичні результати

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

І підставляємо різні функції втрат, залежно від завдання, що розв'язується. Для лінійної регресії:

Для логістичної регресії:

Незважаючи на те, що за методом опорних векторів лежить в основному геометрична мотивація, його можна як проблему мінімізації емпіричного ризику.

Висновок

Багато методів навчання з учителем можна розглядати у тому числі як окремі випадки теорії, розробленої В. Н. Вапником та А. Я. Червоненкісом. Ця теорія дає гарантії щодо помилки на тестовій вибірці за умови достатнього розміру навчальної вибірки та деяких вимог до простору гіпотез, у якому ми шукаємо наш алгоритм.

Використовувана література

• The Nature of Statistical Learning Theory, Vladimir N. Vapnik
• Pattern Classification, 2nd Edition, Richard O. Duda, Peter E. Hart, David G. Stork
• Understanding Machine Learning: З Theory to Algorithms, Shai Shalev-Shwartz, Shai Ben-David

P.S. Прохання писати в личку про всі неточності та друкарські помилки

Теги: Додати теги

Із завданням розпізнавання образів живі системи, зокрема й людина, зіштовхуються постійно з його появи. Зокрема, інформація, що надходить з органів чуття, обробляється мозком, який у свою чергу сортує інформацію, забезпечує прийняття рішення, а далі за допомогою електрохімічних імпульсів передає необхідний сигнал далі, наприклад, органи руху, які реалізують необхідні дії. Потім відбувається зміна навколишнього оточення, і вищезгадані явища відбуваються заново. І якщо розібратися, кожен етап супроводжується розпізнаванням.

З розвитком обчислювальної техніки стало можливим вирішити низку завдань, що виникають у процесі життєдіяльності, полегшити, прискорити, підвищити якість результату. Наприклад, робота різних систем життєзабезпечення, взаємодія людини з комп'ютером, поява роботизованих систем та ін. Проте, зазначимо, що забезпечити задовільний результат у деяких завданнях (розпізнавання подібних об'єктів, що швидко рухаються, рукописного тексту) в даний час не вдається.

Мета роботи: вивчити історію систем розпізнавання образів.

Вказати якісні зміни в області розпізнавання образів як теоретичні, і технічні, із зазначенням причин;

Обговорити методи та принципи, що застосовуються у обчислювальній техніці;

Навести приклади перспектив, які очікуються найближчим часом.

1. Що таке розпізнавання образів?

Перші дослідження з обчислювальної техніки в основному слідували класичній схемі математичного моделювання - математична модель, алгоритм і розрахунок. Такими були завдання моделювання процесів при вибухах атомних бомб, розрахунку балістичних траєкторій, економічних та інших додатків. Однак крім класичних ідей цього ряду виникали і методи, засновані на зовсім іншій природі, і як показувала практика вирішення деяких завдань, вони часто давали кращий результат, ніж рішення, засновані на переускладнених математичних моделях. Їх ідея полягала у відмові від прагнення створити вичерпну математичну модель досліджуваного об'єкта (причому найчастіше адекватні моделі було практично неможливо побудувати), а натомість задовольнитися відповіддю лише на конкретні питання, що цікавлять нас, причому ці відповіді шукати із загальних для широкого класу завдань міркувань. До досліджень такого роду належали розпізнавання зорових образів, прогнозування врожайності, рівня річок, завдання розрізнення нафтоносних і водоносних пластів за непрямими геофізичними даними тощо. буд. класів. А вихідні дані цих завдань, як правило, задавалися у вигляді уривчастих відомостей про об'єкти, що вивчаються, наприклад у вигляді набору заздалегідь розкласифікованих об'єктів. З математичної точки зору це означає, що розпізнавання образів (а так і був названий у нашій країні цей клас завдань) є далекосяжним узагальненням ідеї екстраполяції функції.

Важливість такої постановки для технічних наук не викликає жодних сумнівів і це саме собою виправдовує численні дослідження у цій галузі. Однак завдання розпізнавання образів має і ширший аспект для природознавства (втім, було б дивно якщо щось таке важливе для штучних кібернетичних систем не мало б значення для природних). У контекст цієї науки органічно увійшли і поставлені ще древніми філософами питання природі нашого пізнання, нашої здатності розпізнавати образи, закономірності, ситуації навколишнього світу. Насправді, можна практично не сумніватися в тому, що механізми розпізнавання найпростіших образів, типу образів небезпечного хижака або їжі, що наближається, сформувалися значно раніше, ніж виникла елементарна мова і формально-логічний апарат. І не викликає жодних сумнівів, що такі механізми досить розвинені і у вищих тварин, яким так само в життєдіяльності украй необхідна здатність розрізняти досить складну систему знаків природи. Таким чином, у природі ми бачимо, що феномен мислення та свідомості явно базується на здібностях до розпізнавання образів та подальший прогрес науки про інтелект безпосередньо пов'язаний з глибиною розуміння фундаментальних законів розпізнавання. Розуміючи той факт, що перелічені вище питання виходять далеко за рамки стандартного визначення розпізнавання образів (в англомовній літературі більш поширений термін supervised learning), необхідно так само розуміти, що вони мають глибокі зв'язки з цим відносно вузьким (але ще далеко невичерпаним) напрямом.

Вже зараз розпізнавання образів щільно увійшло у повсякденне життя і є одним із найнагальніших знань сучасного інженера. У медицині розпізнавання образів допомагає лікарям ставити точніші діагнози, на заводах воно використовується для прогнозу шлюбу у партіях товарів. Системи біометричної ідентифікації особистості як своє алгоритмічне ядро ​​також засновані на результатах цієї дисципліни. Подальший розвиток штучного інтелекту, зокрема проектування комп'ютерів п'ятого покоління, здатних до більш безпосереднього спілкування з людиною природними для людей мовами та за допомогою мови, немислимі без розпізнавання. Тут рукою подати і до робототехніки, штучних систем управління, які містять як життєво важливі підсистеми системи розпізнавання.

Саме тому до розвитку розпізнавання образів із самого початку було прикуто чимало уваги з боку фахівців різного профілю – кібернетиків, нейрофізіологів, психологів, математиків, економістів тощо. Певною мірою саме з цієї причини сучасне розпізнавання образів саме живиться ідеями цих дисциплін. Не претендуючи на повноту (а на неї в невеликому есе претендувати неможливо) опишемо історію розпізнавання образів, ключові ідеї.

Визначення

Перш ніж розпочати основні методи розпізнавання образів, наведемо кілька необхідних визначень.

Розпізнавання образів (об'єктів, сигналів, ситуацій, явищ чи процесів) - завдання ідентифікації об'єкта чи визначення будь-яких його властивостей з його зображення (оптичне розпізнавання) чи аудіозапису (акустичне розпізнавання) та інших характеристик.

Одним із базових є не має конкретного формулювання поняття множини. У комп'ютері безліч представляється набором однотипних елементів, що не повторюються. Слово "неповторюваних" означає, що якийсь елемент у множині або є, або його там немає. Універсальна множина включає всі можливі для розв'язуваної задачі елементи, порожнє не містить жодного.

Образ - класифікаційне угруповання у системі класифікації, що об'єднує (виділяє) певну групу об'єктів за деякою ознакою. Образи мають характерну властивість, що виявляється в тому, що ознайомлення з кінцевим числом явищ з однієї і тієї ж множини дає можливість дізнаватися скільки завгодно велика кількість його представників. Образи мають характерними об'єктивними властивостями тому, що різні люди, які навчаються на різному матеріалі спостережень, переважно однаково і незалежно друг від друга класифікують одні й самі об'єкти. У класичній постановці завдання розпізнавання універсальна множина розбивається на частини-образи. Кожне відображення будь-якого об'єкта на сприймаючі органи системи, що розпізнає, незалежно від його положення щодо цих органів, прийнято називати зображенням об'єкта, а безліч таких зображень, об'єднані будь-якими загальними властивостями, являють собою образи.

Методика віднесення елемента до якогось образу називається вирішальним правилом. Ще одне важливе поняття – метрика, спосіб визначення відстані між елементами універсальної множини. Чим менша ця відстань, тим більше схожими є об'єкти (символи, звуки та ін) - те, що ми розпізнаємо. Зазвичай елементи задаються як набору чисел, а метрика - як функції. Від вибору подання образів та реалізації метрики залежить ефективність програми, один алгоритм розпізнавання з різними метриками помилятиметься з різною частотою.

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

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

Навчання - це процес, в результаті якого система поступово набуває здатності відповідати потрібними реакціями на певні сукупності зовнішніх впливів, а адаптація - це підстроювання параметрів та структури системи з метою досягнення необхідної якості управління в умовах безперервних змін зовнішніх умов.

Приклади завдань розпізнавання образів: - розпізнавання букв;