Системи розпізнавання образів (ідентифікації). Розпізнавання образів Огляд існуючих методів розпізнавання образів

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

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

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

У літературі, присвяченій проблемі навчання розпізнавання образів (ГРВ), часто замість поняття образу вводиться поняття класу.

Проблема навчання розпізнаванню образів (ОРО)

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

Розглянемо приклад завдань із галузі ОРО.

Мал. 3.1.

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

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

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

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

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

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

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

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

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

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

Розпізнавання образів

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

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

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

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

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

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

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

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

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

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

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

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

Що таке цілісність і яку роль вона грає при сприйнятті?

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

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

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

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

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

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

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

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

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

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

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

Вище зазначалося, що з моделювання мислення дуже важливо, і, можливо, і треба зрозуміти, як працюють нейронні механізми живого мозку. У зв'язку з цим постає запитання: а чи не є формальні нейронні мережі, що розпізнають, якщо і не вирішенням проблеми моделювання нейронних механізмів мозку, то хоча б важливим кроком у цьому напрямку? На жаль, відповідь має бути негативною. На відміну від активної живої нейронної мережі РІС – це пасивний ознаковий чи растровий класифікатор з усіма недоліками традиційних класифікаторів. Аргументи, виходячи з яких зроблено цей висновок, докладніше ми розглянемо надалі.

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

Sun, Mar 29, 2015

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

Розглянемо загальні елементи моделі класифікації.

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

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

Верифікація- процес зіставлення екземпляра об'єкта з однією моделлю об'єкта чи описом класу.

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

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

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

Прикладами завдань класифікації є:

• розпізнавання символів;
• розпізнавання мови;
• встановлення медичного діагнозу;
• прогноз погоди;
• розпізнавання осіб
• класифікація документів та ін.

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

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

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

Після того, як визначено ознаки, необхідно визначити оптимальну вирішальну процедуру для класифікації. Розглянемо систему розпізнавання образів, призначену для розпізнавання різних класів M, позначених як m_1,m_2,…,m 3. Тоді можна вважати, що простір образів складається з M областей, кожна містить точки, відповідні з одного класу. Тоді завдання розпізнавання може розглядатися як побудова кордонів, що розділяють класів M, виходячи з прийнятих векторів вимірювань.

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

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

де d - Розмірність вектора ознаки.

Поділяють 3 групи методів розпізнавання образів:

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

Класифікація за найближчим середнім значенням

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

Простий алгоритм класифікації полягає у групуванні еталонних даних класу з використанням вектора математичного очікування класу (середнього значення).

де x(i,j)-j-й еталонний ознака класу i, n_j-кількість еталонних векторів класу i.

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

Проблеми виникнуть, якщо класи матимуть дещо складнішу структуру, наприклад, як у малюнку. В даному випадку клас 2 розділений на дві ділянки, що не перетинаються, які погано описуються одним середнім значенням. Також клас 3 занадто витягнутий, зразки 3-го класу з більшими значеннями координат x_2 ближче до середнього значення 1-го класу, ніж 3-го.

Описана проблема деяких випадках може бути вирішена зміною розрахунку відстані.

Враховуватимемо характеристику «розкиду» значень класу - σ_i, вздовж кожного координатного напрямку i. Середньоквадратичне відхилення дорівнює квадратному кореню дисперсії. Шкальована евклідова відстань між вектором x та вектором математичного очікування x_c дорівнює

Ця формула відстані зменшить кількість помилок класифікації, але насправді більшість завдань не вдається уявити таким простим класом.

Класифікація на відстані до найближчого сусіда

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

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

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

Крім того, рішення буде кращим, якщо шукати в базі не одного найближчого сусіда, а k. Тоді при k > 1 забезпечує найкращу вибірку розподілу векторів d-мірному просторі. Однак ефективне використання значень k залежить від того, чи є достатня кількість у кожній області простору. Якщо є більше двох класів, то прийняти правильне рішення виявляється складніше.

Література

• M. Castrillón, . O. Déniz, . D. Hernández і J. Lorenzo, «Показник face and facial feature detectors заснований на Viola-Jones загальний об'єкт помітки framework,» International Journal of Computer Vision, № 22, pp. 481-494, 2011.
• Y.-Q. Wang, "An Analysis of Viola-Jones Face Detection Algorithm," IPOL Journal, 2013.
• Л. Шапіро та Д. Стокман, Комп'ютерний зір, Біном. Лабораторія знань, 2006.
• З. Н. Р., Методи розпізнавання та їх застосування, Радянське радіо, 1972.
• Дж. Ту, Р. Гонсалес, Математичні принципи розпізнавання образів, Москва: "Світ" Москва, 1974.
• Khan, H. Abdullah і M. Shamian Bin Zainal, «Ефективні яйця і велику стирання algorithm використовуючи комбінацію з фіолетовими тонами і фарбою pixel detection» International Journal of Engineering and Applied Sciences, № Vol. 3 №4, 2013.
• V. Gaede та O. Gunther, «Multidimensional Access Methods,» ACM Computing Surveys, pp. 170-231, 1998.

Лекція №17.МЕТОДИ РОЗІЗНАННЯ ОБРАЗІВ

Розрізняють такі групи методів розпізнавання:

Методи функцій близькості

Методи дискримінантних функцій

Статистичні методи розпізнавання.

Лінгвістичні методи

евристичні методи.

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

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

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

Методи функцій близькості

Методи цієї групи засновані на використанні функцій, що оцінюють міру близькості між розпізнаваним чином з вектором x * = (x * 1 ,….,x * n), та еталонними образами різних класів, представленими векторами x i = (x i 1 ,…, x i n), i= 1,…,N, де i –номер класу образів.

Процедура розпізнавання згідно з цим методом полягає у обчисленні відстані між точкою образу, що розпізнається, і кожної з точок, що представляють еталонний образ, тобто. у обчисленні всіх значень d i , i= 1,…,N. Образ відноситься до класу, для якого значення d iмає найменше значення серед усіх i= 1,…,N .

Функція, що ставить у відповідність кожній парі векторів x i, x *речове число як міру їх близькості, тобто. визначальна відстань з-поміж них може бути досить довільною. У математиці таку функцію називають метрикою простору. Вона має задовольняти наступним аксіомам:

r(x,y)=r(y,x);

r(x,y) > 0, якщо xне дорівнює yі r(x,y)=0 якщо x=y;

r(x,y) <=r(x,z)+r(z,y)

Перерахованим аксіомам задовольняють, зокрема, такі функції

a i= 1/2 , j=1,2,…n.

b i=sum, j=1,2,…n.

c i=max abs ( x i‑ x j *), j=1,2,…n.

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

Часто як функцію близькості вибирають середньоквадратичну різницю координат образу, що розпізнається. x *та зразка x i, тобто. функцію

d i = (1/n) sum( x i j‑ x j *) 2 , j=1,2,…n.

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

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

В такому випадку d i = (1/n) sum w j (x i j‑ x j *) 2 , j=1,2,…n,

де w j- Вагові коефіцієнти.

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

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

Групи близьких один одному точок образів (накопичення образів) у просторі ознак називають кластерами, а завдання виділення таких груп – завданням кластеризації.

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

Методи дискримінантних функцій

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

Загальний вигляд лінійної вирішальної функції задається формулою

d(x)=w 1 x 1 + w 2 x 2 +…+w n x n +w n +1 = Wx+w n

де x- Вектор образу, w=(w 1 , w 2 ,…w n) - Вектор вагових коефіцієнтів.

У разі розбиття на два класи X 1 та X 2 дискримінантна функція d(x) дозволяє здійснити розпізнавання відповідно до правила:

xналежить X 1 , якщо d(x)>0;

xналежить X 2 , якщо d(x)<0.

Якщо d(x)=0, має місце випадок невизначеності.

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

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

xналежить X 1 , якщо d 1 (x)>0,d 2 (x)<0,d 3 (x)<0;

xналежить X 2 , якщо d(x)<0,d 2 (x)>0,d 3 (x)<0;

xналежить X 3 , якщо d(x)<0,d 2 (x)<0,d 3 (x)>0.

При цьому вважається, що для інших комбінацій значень d 1 (x),d 2 (x),d 3 (x) має місце випадок невизначеності.

Різновидом методу дискримінантних функцій є метод вирішальних функцій. У ньому за наявності mкласів передбачається існування mфункцій d i(x), званих вирішальними, таких, що якщо xналежить X i, то d i(x) > d j(x) для всіх jне рівних i,Тобто. вирішальна функція d i(x) має максимальне значення серед усіх функцій d j(x), j=1,...,n..

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

Евклідова відстань між вектором ознак образу, що розпізнається xта вектором еталонного образу визначається формулою || x i ‑ x|| = 1/2 , j=1,2,…n.

Вектор xбуде віднесено до класу i, котрій значення || x i ‑ x *|| мінімально.

Замість відстані порівнювати квадрат відстані, тобто.

||x i ‑ x|| 2 = (x i ‑ x)(x i ‑ x) т = x x- 2x x i +x i x i

Оскільки величина x xоднакова для всіх i, Мінімум функції | | x i ‑ x|| 2 збігатиметься з максимумом вирішальної функції

d i(x) = 2x x i -x i x i.

тобто xналежить X i, якщо d i(x) > d j(x) для всіх jне рівних i.

Т.о. машина, що класифікує за мінімумом відстані, ґрунтується на лінійних вирішальних функціях. Загальна структура такої машини використовує вирішальні функції виду

d i (x)=w i 1 x 1 + w i 2 x 2 +…+w in x n +w i n +1

Вона може бути представлена ​​відповідною структурною схемою.

Для машини, що здійснює класифікацію мінімуму відстані мають місце рівності: w ij = -2x i j , w i n +1 = x i x i.

Еквівалентне розпізнавання методом дискримінантних функцій може бути здійснено, якщо визначити дискримінантні функції як різниці d ij (x)=d i (x)‑d j (x).

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

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

У цьому алгоритм автоматичного навчання виявляється дуже простим проти іншими методами розпізнавання.

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

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

Розглянемо методи побудови дискримінантної функції за заданою (навчальною) вибіркою стосовно задачі про поділ образів на два класи. Якщо задані дві множини образів, що належать відповідно до класів А і В, то розв'язання задачі побудови лінійної дискримінантної функції шукається у вигляді вектора вагових коефіцієнтів W=(w 1 ,w 2 ,...,w n,w n+1), що володіє тим властивістю, що для будь-якого образу виконуються умови

xналежить класу A, якщо >0, j=1,2,…n.

xналежить класу B, якщо<0, j=1,2,…n.

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

x 1 1 w i+x 21 w 2 +...+x n 1 w n+w n +1 >0;

x 1 2 w i+x 22 w 2 +...+x n 2 w n+w n +1 <0;

x 1 iw i+x 2i w 2 +...+x ni w n+w n +1 >0;

................................................

x 1 Nw i +x 2N w 2 +...+x nN w n +w n + 1>0;

тут x i=(x i 1 ,x i 2 ,...,x i n ,x i n+ 1 ) - Вектор значень ознак образу з навчальної вибірки, знак > відповідає векторам образів x, що належать класу A, а знак< - векторам x, що належать класу B.

Шуканий вектор wіснує, якщо класи A і B розділяються і не існує інакше. Значення компонент вектора wможуть бути знайдені або попередньо, на етапі, що передує апаратної реалізації СРО, або безпосередньо СРО в процесі її функціонування. Останній із зазначених підходів забезпечує більшу гнучкість та автономність СРО. Розглянемо його з прикладу пристрою, званого перцентроном. винайденого 1957 року американським ученим Розенблатом. Схематичне уявлення перцентрону, що забезпечує віднесення образу одного з двох класів, представлено на наступному малюнку.

Сітківка SСітківка AСітківка R

о про x 1

о про x 2

о про x 3

про (sum)-------> R(Реакція)

о про x i

о про x n

о про x n +1

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

Позначивши через x iреакцію i-го асоціативного елемента та через w i- ваговий коефіцієнт реакції i-го асоціативного елемента, реакцію системи можна записати як R= sum ( w j x j), j=1,..,n. Якщо R>0, то пред'явлений системі образ належить класу A, і якщо R<0, то образ относится к классу B. Описание этой процедуры классификации соответствует рассмотренным нами раньше принципам классификации, и, очевидно, перцентронная модель распознавания образов представляет собой, за исключением сенсорной сетчатки, реализацию линейной дискриминантной функции. Принятый в перцентроне принцип формирования значений x 1 , x 2 ,...,x nвідповідає деякому алгоритму формування ознак з урахуванням сигналів первинних датчиків.

Загалом може бути кілька елементів R, Що формують реакцію перцептрону У такому разі говорять про присутність у перцептроні сітківки. Rреагуючих елементів.

Схему перцентрону можна поширити на випадок, коли число класів більше двох шляхом збільшення числа елементів сітківки Rдо числа класів, що розрізняються, і введення блоку визначення максимальної реакції відповідно до схеми, представленої на наведеному вище малюнку. При цьому образ зараховується до класу з номером i, якщо R i>R j, для всіх j.

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

Розглянемо алгоритм дії перцентрону на прикладі розпізнавання об'єктів двох класів: A та B. Об'єктам класу A має відповідати значення R= +1, а класу B – значення R= -1.

Алгоритм навчання ось у чому.

Якщо черговий образ xналежить класу A, але R<0 (имеет место ошибка распознавания), тогда коэффициенты w jз індексами, яким відповідають значення x j>0, збільшують деяку величину dw, а інші коефіцієнти w jзменшують на dw. При цьому значення реакції Rотримує збільшення убік її позитивних значень, відповідних правильної класифікації.

Якщо xналежить класу B, але R>0 (має місце помилка розпізнавання), то коефіцієнти w jз індексами, яким відповідають x j<0, увеличивают на dw, а інші коефіцієнти w jзменшують на ту саму величину. При цьому значення реакції Rотримує збільшення убік негативних значень, відповідних правильної класифікації.

Алгоритм вносить зміну у вектор ваг wв тому і тільки в тому випадку, якщо образ, що пред'являється на k-ом кроці навчання, був при виконанні цього кроку неправильно класифікований, і залишає вектор ваг wбез змін у разі правильної класифікації. Доказ збіжності даного алгоритму представлено у роботі [Ту, Гонсалес]. Таке навчання зрештою (при належному виборі dwі лінійної роздільності класів образів) призводить до отримання вектора w, Що забезпечує правильну класифікацію

Статистичні методи розпізнавання.

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

P = sum[ p(i)·prob( D(x)+i | xкласу i)]

де m- Число класів,

p(i) = prob ( xналежить класу i) - апріорна ймовірність приналежності довільного образу xдо i-му класу (частота появи образів i-го класу),

D(x) - функція, що приймає класифікаційне рішення (вектор ознак xставить у відповідність номер класу iз множини (1,2,..., m}),

prob( D(x) не дорівнює i| xналежить класу i) - ймовірність події D(x) не дорівнює iпри виконанні умови приналежності xкласу i, тобто. ймовірність винесення помилкового рішення функцією D(x) для даного значення x, що належить i-му класу.

Можна показати, що ймовірність неправильної класифікації досягає мінімуму, якщо D(x)=iв тому і тільки в тому випадку, якщо p(x|i)· p(i)>p(x|j)· p(j), для всіх i+j, де p(x|i) - щільність розподілу образів i-го класу у просторі ознак.

Відповідно до наведеного правила точка xвідноситься до того класу, якому відповідає максимальне значення p(i) p(x|i), тобто. твір апріорної ймовірності (частоти) появи образів i-го класу та щільності розподілу образів i-го класу у просторі ознак. Подане правило класифікації називається байєсовським, т.к. воно випливає з відомої теорії ймовірності формули Байєса.

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

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

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

У клас №1 об'єднаємо сигнали, що представляють одиниці, клас №2 - сигнали, що представляють нулі. Нехай наперед відомо, що в середньому з кожної 1000 сигналів aсигналів являють собою одиниці та bсигналів – нулі. Тоді значення апріорних ймовірностей появи сигналів 1-го та 2-го класів (одиниць та нулів), відповідно можна прийняти рівними

p(1)=a/1000, p(2)=b/1000.

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

p(x 1) =(2piб) -1/2 exp(-( x-1) 2 / (2б 2)),

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

p(x 2) = (2piб) -1/2 exp (- x 2/(2б 2)),

Застосування байєсовського вирішального правила призводить до висновку, що сигнал сигналу класу 2, тобто. переданий нуль, якщо

p(2) p(x 2) > p(1) p(x 1)

або, більш конкретно, якщо

b exp(- x 2 /(2б 2)) > a exp(-( x-1) 2 / (2б 2)),

Поділивши ліву частину нерівності на праву, отримаємо

(b/a) exp((1-2 x)/(2б 2)) >1,

звідки після логарифмування знаходимо

1-2x> 2б 2 ln(a/b)

x< 0.5 - б 2 ln(a/b)

З отриманої нерівності випливає, що за a=b, тобто. при однакових апріорних ймовірностях появи сигналів 0 і 1 образу присвоюється значення 0 коли x<0.5, а значение 1, когда x>0.5.

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

Так при a/b=2.71 (що відповідає у 2.71 разу більш частої передачі одиниць) і б 2 =0.1, образу надається значення 0, якщо x<0.4, и значение 1, если x>0.4. Якщо інформація про апріорні ймовірності розподілу відсутня, то можуть бути використані статистичні методи розпізнавання, в основу яких покладено інші, відмінні від байєсовського, правила класифікації.

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

Лінгвістичні методи розпізнавання образів.

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

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

приклад. Нехай задано три зображення літери А, отримані в результаті попередньої обробки зображень. Позначимо ці зображення ідентифікаторами А1, А2 та А3.

Для лінгвістичного опису представлених образів скористаємося мовою PDL (Picture Description Language). Словник мови PDL містить такі символи:

1. Імена найпростіших зображень (примітивів). Що стосується даного випадку примітиви і відповідні їм імена такі.

Зображення у вигляді лінії, спрямованої:

вгору та вліво (le F t), на північ (north)), вгору та вправо (right), на схід (east)).

Імена: L, N, R, E.

2. Символи бінарних операцій. (+,*,-) Їх зміст відповідає послідовному з'єднанню примітивів (+), з'єднанню початків і закінчень примітивів (*), з'єднанню тільки закінчень примітивів (-).

3. Праву та ліву дужки. ((,)) Дужки дозволяють визначати послідовність виконання операцій у виразі.

Розглянуті зображення А1, А2 і А3 описуються мовою PDL відповідно до таких виразів.

T(1)=R+((R-(L+N))*E-L

T(2)=(R+N)+((N+R)-L)*E-L

T(3)=(N+R)+(R-L)*E-(L+N)

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

Очевидно, літера А завжди містить такі структурні елементи: ліву "ніжку", праву "ніжку" та головну частину. Назвемо ці елементи відповідно до STL, STR, TR.

Тоді на мові PDL клас символів А – SIMB A описується виразом

SIMB A = STL + TR - STR

Ліва "ніжка" STL завжди є ланцюжок елементів R і N, що можна записати так

STL -> R | N (STL + R) (STL + N)

(STL є символ R або N, або ланцюжок, отриманий додаванням кисневому ланцюжку STL символів R або N)

Права "ніжка" STR є ланцюжок елементів L і N, що можна записати так, тобто.

STR -> L N (STR + L) (STR + N)

Головна частина літери - TR є замкнутим контуром, складеним з елемента E і ланцюжків типу STL і STR.

Мовою PDLструктура TR описується виразом

TR -> (STL - STR) * E

Остаточно отримаємо такий опис класу літер А:

SIMB A -> (STL + TR - STR),

STL -> R | N (STL + R) (STL + N)

STR -> L N (STR + L) (STR + N)

TR -> (STL - STR) * E

Процедура розпізнавання у разі може бути реалізована так.

1. Вираз, що відповідає образу, порівнюється з еталонною структурою STL + TR - STR.

2. Кожному елементу структури STL, TR, STR, якщо можливо, тобто. якщо опис зображення порівняно з еталоном, ставиться у відповідність деякий вираз з виразу T(А). Наприклад,

для А1: STL=R, STR=L, TR=(R-(L+N))*E

для А2: STL = R + N, STR = L, TR = ((N + R) - L) * E

для А3: STL = N + R, STR = L + N, TR = (R - L) * E3.

Вирази STL, STR, TR порівнюються з відповідними еталонними структурами.

4. Якщо структура кожного виразу STL, STR, TR відповідає еталонній, робиться висновок про належність образу до класу літер А. Якщо на якомусь з етапів 2, 3, 4 виявляється невідповідність структури виразу еталону, що аналізується, робиться висновок про неналежність образу класу SIMB A. Зіставлення структур виразів може проводитися за допомогою алгоритмічних мов LISP, PLANER, PROLOG та інших подібних до них мов штучного інтелекту.

У цьому прикладі всі ланцюжки STL складені із символів N і R, а ланцюжка STR із символів L і N, що відповідає заданій структурі цих ланцюжків. Структура TR у аналізованих образах відповідає еталонної, т.к. складається з "різниці" ланцюжків типу STL, STR, "помноженої" на символ E.

Т.ч., приходимо до висновку про належність аналізованих образів класу SIMB A.

Синтез нечіткого регулятора електроприводу постійного струмуу середовищі «MatLab»

Синтез нечіткого регулятора з одним входом та виходом.

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

Рис.4 Узагальнена функціональна схема системи з двома лінгвістичними змінними.

Рис.5 Принципова схема нечіткого регулятора з двома лінгвістичними змінними.

Алгоритм нечіткого управління в загальному випадку є перетворенням вхідних змінних нечіткого регулятора в його вихідні змінні за допомогою наступних взаємопов'язаних процедур:

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

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

3. перетворення вихідних лінгвістичних змінних нечіткого регулятора на фізичні управляючі змінні.

Розглянемо спочатку найпростіший випадок, коли для керування електроприводом, що стежить, вводяться всього дві лінгвістичні змінні:

"кут" - вхідна змінна;

«керівна дія» - вихідна змінна.

Синтез регулятора будемо здійснювати в середовищі MatLab за допомогою тулбоксу Fuzzy Logic. Він дозволяє створювати системи нечіткого логічного висновку та нечіткої класифікації в рамках середовища MatLab, з можливістю їх інтегрування до Simulink. Базовим поняттям Fuzzy Logic Toolbox є FIS-структура – ​​система нечіткого виведення (Fuzzy Inference System). FIS-структура містить усі необхідні дані для реалізації функціонального відображення "входи-виходи" на основі нечіткого логічного висновку згідно зі схемою, наведеною на рис. 6.

Малюнок 6. Нечіткий логічний висновок.

X – вхідний чіткий вектор; - Вектор нечітких множин, що відповідає вхідному вектору X;
- результат логічного виведення у вигляді вектора нечітких множин; Y - вихідний чіткий вектор.

Модуль fuzzy дозволяє будувати нечіткі системи двох типів – Мамдані та Сугено. У системах типу Мамдані база знань складається із правил виду "Якщо x 1 = низький і x 2 = середній, то y = високий". У системах типу Сугено база знань складається із правил виду Якщо x 1 = низький і x 2 = середній, то y = a 0 + a 1 x 1 + a 2 x 2 ". Таким чином, основна відмінність між системами Мамдані та Сугено полягає в різних способах завдання значень вихідної змінної у правилах, що утворюють базу знань. У системах типу Мамдані значення вихідний змінної задаються нечіткими термами, у системах типу Сугено – як лінійна комбінація вхідних змінних. У нашому випадку використовувати систему Сугено, т.к. вона найкраще піддається оптимізації.

Для керування електроприводом, що стежить, вводяться дві лінгвістичні змінні: «помилка» (за становищем) і «керівна дія». Перша є вхідний, друга – вихідна. Визначимо терм-множину для зазначених змінних.

Основні компоненти нечіткого логічного висновку. Фаззифікатор.

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

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

Рис.7. Лінгвістична змінна "помилка".

Лінгвістичну змінну «управління» зручніше подати у вигляді таблиці:

Таблиця 1

Блок правил.

Розглянемо послідовність визначення кількох правил, які описують деякі ситуації:

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

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

Т.о. складено два правила, які можуть бути формально визначені так:

якщопомилка = нуль, токеруючий вплив = нуль.

якщопомилка = велика позитивна, токеруючий вплив = велика позитивна.

Рис.8. Формування управління при малій позитивній помилці за становищем.

Рис.9. Формування управління при нульовій помилці за становищем.

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

Таблиця 2

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

Дефаззифікатор.

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

, де n-число правил, що спрацювали (дефаззифікація методом центру області), u n- фізичне значення керуючого сигналу, що відповідає кожному з нечітких множин UBO, UMo, UZ, UMp, UBP. mUn(u)– ступінь належності керуючого сигналу u до відповідної нечіткої множини Un=( UBO, UMo, UZ, UMp, UBP). Існують також інші методи дефазифікації, коли вихідна лінгвістична змінна пропорційна найсильнішому або слабкому правилу.

Промоделюємо процес керування електроприводом за допомогою вищеописаного нечіткого регулятора.

Рис.10. Структурна схема системи у середовищіMatlab.

Рис.11. Структурна схема нечіткого регулятора у середовищіMatlab.

Рис.12. Перехідний процес при одиничній ступінчастій дії.

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

Аналіз характеристик приводу із синтезованим алгоритмом управління показує, що вони далекі від оптимальних і гірше, ніж при синтезі управління іншими методами (занадто великий час регулювання при одиничному ступінчастому впливі та помилка при гармонійному). Пояснюється це тим, що параметри функцій належності вибиралися досить довільно, а як вход регулятора використовувалася тільки величина помилки по положенню. Природно ні про яку оптимальність отриманого регулятора не може йтися. Тому актуальним стає завдання оптимізації нечіткого регулятора з метою досягнення ним максимально можливих показників якості управління. Тобто. стоїть завдання оптимізації цільової функції f(a 1 ,a 2 …a n), де a 1 ,a 2 …a n – коефіцієнти, що визначають вид та характеристики нечіткого регулятора. Для оптимізації нечіткого регулятора скористаємося блоком ANFIS із середовища Matlab. Також одним із способів покращення характеристик регулятора може бути збільшення числа його входів. Це зробить регулятор гнучкішим і покращить його характеристики. Додамо ще одну вхідну лінгвістичну змінну – швидкість зміни вхідного сигналу (його похідну). Відповідно зросте і кількість правил. Тоді принципова схема регулятора набуде вигляду:

Рис.14 Принципова схема нечіткого регулятора з трьома лінгвістичними змінними.

Нехай значення швидкості вхідного сигналу. Базове терм-множина Тn визначимо у вигляді:

Тn=("негативна (ВО)", "нульова (Z)", "позитивна (ВР)").

Розташування функцій приналежності всім лінгвістичних змінних показано малюнку.

Рис.15. Функції власності лінгвістичної змінної «помилка».

Рис.16. Функції приналежності лінгвістичної змінної "швидкість вхідного сигналу".

У зв'язку з додаванням ще однієї лінгвістичної змінної кількість правил зросте до 3x5=15. Принцип їх складання повністю аналогічний розглянутому вище. Усі вони наведені у наступній таблиці:

Таблиця 3

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

Рис.17. Формування управління за трьох лінгвістичних змінних.

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

Рис.18. Структурна схема нечіткого регулятора із двома входами.

Додати малюнок

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

Мал. 21. Сигнал помилки при гармонійному вхідному впливі для моделі з нечітким регулятором, що містить дві вхідні лінгвістичні змінні.

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

Оптимізація нечіткого регулятора.

Розглянемо використання генетичних алгоритмів оптимізації нечіткого регулятора. Генетичні алгоритми - адаптивні методи пошуку, які останнім часом часто використовуються для вирішення задач функціональної оптимізації. Вони засновані на подібності до генетичних процесів біологічних організмів: біологічні популяції розвиваються протягом кількох поколінь, підкоряючись законам природного відбору і за принципом "виживає найбільш пристосований" (survival of the fittest), відкритому Чарльзом Дарвіном. Наслідуючи цей процес генетичні алгоритми здатні "розвивати" вирішення реальних завдань, якщо ті відповідним чином закодовані.

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

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

Є багато способів реалізації ідеї біологічної еволюції у межах генетичних алгоритмів. Традиційний, можна подати у вигляді наступної блок-схеми показаної на малюнку 22, де:

1. Ініціалізація початкової популяції – генерація заданого числа розв'язків задачі, з яких починається процес оптимізації;

2. Застосування операторів кросовера та мутації;

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

Серед Matlab генетичні алгоритми представлені окремим тулбоксом, і навіть пакетом ANFIS. ANFIS – це абревіатура Adaptive-Network-Based Fuzzy Inference System – адаптивна мережа нечіткого висновку. ANFIS одна із перших варіантів гібридних нейро-нечетких мереж - нейронної мережі прямого поширення сигналу особливого типу. Архітектура нейро-нечіткої мережі ізоморфна нечіткої основі знань. У нейро-нечітких мережах використовуються диференційовані реалізації трикутних норм (множення та ймовірнісне АБО), а також гладкі функції приналежності. Це дозволяє застосовувати для налаштування нейронечітких мереж швидкі та генетичні алгоритми навчання нейронних мереж, засновані на методі зворотного поширення помилки. Нижче описуються архітектура та правила функціонування кожного шару ANFIS-мережі.

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

Входи мережі до окремого шару не виділяються. На рис.23 зображена ANFIS-мережа з однією вхідною змінною («помилка») та п'ятьма нечіткими правилами. Для лінгвістичної оцінки вхідної змінної «помилка» використовується 5 термів.

Рис.23. СтруктураANFIS-Мережі.

Введемо такі позначення, необхідні подальшого викладу:

Нехай – входи мережі;

y – вихід мережі;

Нечітке правило із порядковим номером r;

m - кількість правил;

Нечіткий терм з функцією приналежності, застосовуваний для лінгвістичної оцінки змінної в r-му правилі (,);

Дійсні числа у висновку r-го правила (,).

ANFIS-мережа функціонує так.

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

,

де a, b і c - параметри функції приналежності, що настроюються.

Шар 2.Кількість вузлів другого шару дорівнює m. Кожен вузол цього шару відповідає одному нечіткому правилу. Вузол другого шару з'єднаний із тими вузлами першого шару, які формують антецеденти відповідного правила. Отже, кожен вузол другого шару може приймати від 1 до вхідних n сигналів. Виходом вузла є ступінь виконання правила, що розраховується як добуток вхідних сигналів. Позначимо виходи вузлів цього шару через , .

Шар 3.Кількість вузлів третього шару також дорівнює m. Кожен вузол цього шару розраховує відносний рівень виконання нечіткого правила:

Шар 4.Кількість вузлів четвертого шару також дорівнює m. Кожен вузол з'єднаний з одним вузлом третього шару і з усіма входами мережі (на рис. 18 зв'язку з входами не показані). Вузол четвертого шару розраховує внесок одного нечіткого правила у вихід мережі:

Шар 5.Єдиний вузол цього шару підсумовує вклади всіх правил:

.

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

Рис.24. Робоча область ANFISedit.

Спробуємо тепер оптимізувати нечіткий регулятор для одиничного ступеневого впливу. Бажаний перехідний процес має приблизно такий вигляд:

Рис.25. Бажаний перехідний процес.

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

Таблиця 4

Рис.26. Вигляд навчальної вибірки.

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

Рис.27. Процес навчання нейромережі.

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

Рис.28. Графік залежності керування від помилки поп положення всередині регулятора.

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

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

Рис.30. Сигнал помилки при гармонійному вхідному впливі моделі з нечітким регулятором, що містить дві вхідні лінгвістичні змінні.

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

Методи автоматичного розпізнавання образів та їх реалізація в системах оптичного розпізнавання текстів (Optical Character Recognition – OCR-системи) – одна з найпрогресивніших технологій штучного інтелекту. У розвитку цієї технології російські вчені займають провідні позиції у світі.

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

Абревіатура OCR іноді розшифровується як Optical Character Reader – пристрій оптичного розпізнавання символів або автоматичного читання тексту. Нині такі пристрої у промисловому використанні обробляють до 100 тис. документів на добу.

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

Перерахуємо особливості предметної області, суттєві з погляду OCR-систем:

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

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

Виділяються три принципи, на яких ґрунтуються всі OCR-системи.

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

Провідні російські OCR-системи: FineReader; FineReader Рукопис; FormReader; CunieForm (Cognitive Technologies), Cognitive Forms (Cognitive Technologies).

Система FineReader випускається компанією ABBYY, яка була заснована в 1989 р. Розробки компанії ABBYY ведуться у двох напрямках: машинний зір та прикладна лінгвістика. Стратегічним напрямом наукових досліджень та розробок є природно-мовний аспект технологій у галузі машинного зору, штучного інтелекту та прикладної лінгвістики.

CuneiForm GOLD for Windows є першою в світі інтелектуальною OCR-системою, що самонавчається, що використовує новітню технологію адаптивного розпізнавання текстів, підтримує багато мов. Для кожної мови постачається словник контекстної перевірки та підвищення якості результатів розпізнавання. Розпізнає будь-які поліграфічні, машинописні гарнітури та шрифти, які отримуються з принтерів, за винятком декоративних та рукописних, а також дуже низькоякісних текстів.

Характеристики систем розпізнавання образів. Серед ОСЯ-технологій велике значення мають спеціальні технології вирішення окремих класів задач автоматичного розпізнавання образів:

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

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

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

Потім рядки розбиваються на безперервні області зображення, які відповідають окремим буквам; алгоритм розпізнавання висуває припущення щодо відповідності цих областей символам, а потім здійснюється вибір кожного символу, внаслідок чого сторінка відновлюється у символах тексту, причому зазвичай у заданому форматі. ОСЯ-системи можуть досягати найкращої точності розпізнавання - понад 99,9% для чистих зображень, складених із звичайних шрифтів. На перший погляд така точність розпізнавання здається ідеальною, але рівень помилок все ж таки пригнічує, тому що, якщо є приблизно 1500 символів на сторінці, то навіть при коефіцієнті успішного розпізнавання 99,9% виходить одна або дві помилки на сторінку. У разі слід скористатися методом перевірки за словником, т. е. якщо якогось слова немає у словнику системи, вона за спеціальними правилами спробує знайти схоже. Але це все одно не дозволяє виправляти 100% помилок та потребує контролю результатів людиною.

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

Програмне забезпечення ОСЯ-системи зазвичай працює з великим растровим зображенням сторінки, отриманої зі сканера. Зображення зі стандартним ступенем роздільної здатності досягаються скануванням з точністю 9600 п/д. Зображення аркуша формату A4 при цьому роздільній здатності займає близько 1 Мб пам'яті.

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

Робота з OCR-системами, як правило, не повинна викликати особливих труднощів. Більшість таких систем мають найпростіший автоматичний режим «сканування та розпізнавання» (Scan & Read), а також вони підтримують і режим розпізнавання зображень з файлів. Однак для того, щоб досягти кращих з можливих для даної системи результатів, бажано (а нерідко і обов'язково) попередньо вручну налаштувати її на конкретний вид тексту, макет бланка та якість паперу. Сторінка, розташована з порушенням кордонів або перекосом, створює трохи спотворені символьні зображення, які можуть бути переплутані системою OCR.

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

На даний момент існує безліч програм, що підтримують розпізнавання тексту як одну з можливостей. Лідером у цій галузі є система FineReader. Остання версія програми (6.0) має засоби для розробки нових систем на базі технології FineReader 6.0. До складу сімейства FineReader 6.0 входять: система FineReader 6.0 Professional, FineReader 6.0 Corporate Edition, FineReader Scripting Edition 6.0 та FineReader Engine 6.0. Система FineReader 6.0, крім того, що знає безліч форматів для збереження, включаючи PDF, має можливість прямого розпізнавання з PDF-файлів. Нова технологія Intelligent Background Filtering (інтелектуальна фільтрація фону) дозволяє відсіяти інформацію про текстуру документа та фоновий шум зображення: іноді для виділення тексту в документі використовується сірий або кольоровий фон. Людині це не заважає читати, але звичайні алгоритми розпізнавання тексту зазнають серйозних труднощів при роботі з літерами, розташованими поверх такого фону. Програма FineReader вміє визначати зони, що містять подібний текст, відокремлюючи текст від фону документа, знаходячи точки, розмір яких менший за певну величину, і видаляючи їх. При цьому контури літер зберігаються, тому точки фону, близько розташовані до даних контурів, не вносять перешкод, здатних погіршити якість розпізнавання тексту.

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

Система ABBYY FormReader - одна з програм розпізнавання фірми ABBYY, заснована на системі ABBYY FineReader Engine. Ця програма призначена для розпізнавання та обробки форм, які можуть бути заповнені вручну. Програма ABBYY FormReader може обробляти форми з фіксованою схемою так само добре, як і форми, структура яких може змінюватися. Для розпізнавання було використано нову технологію ABBYY FlexiForm technology.

Провідні виробники програмного забезпечення ліцензували російську інформаційну технологію застосування зі своїми продуктами. У популярні програмні пакети Corel Draw (Corel Corporation), FaxLine/OCR & Business Card Wizard (Inzer Corporation) та багато інших вбудовано OCR-бібліотеку CuneiForm. Ця програма стала першою у Росії OCR-системою, що отримала MS Windows Compatible Logo.

Система Readiris Pro 7 – професійна програма розпізнавання тексту. За словами виробників, ця OCR-система відрізняється від аналогів найвищою точністю перетворення звичайних (щоденних) друкованих документів, таких як листи, факси, журнальні статті, газетні вирізки, об'єкти, доступні для редагування (включаючи файли формату PDF). Основними перевагами програми є можливість більш-менш точного розпізнавання картинок, стиснутих «по максимуму» (з максимальною втратою якості) методом формату JPEG, підтримка цифрових камер і автовизначення орієнтації сторінки, підтримка до 92 мов (включаючи російську).

Система OmniPage 11 – продукт компанії ScanSoft. Обмежена версія програми (OmniPage 11 Limited Edition, OmniPage Lite) зазвичай постачається в комплекті з новими сканерами (на території Європи та США). Розробники стверджують, що їхня програма практично зі 100% точністю розпізнає друковані документи, відновлюючи їх форматування, включаючи стовпці, таблиці, переноси (у тому числі переноси частин слів), заголовки, назви розділів, підписи, номери сторінок, виноски, параграфи, нумеровані списки, червоні рядки, графіки та малюнки. Є можливість збереження у форматах Microsoft Office, PDF та в 20 інших форматів, розпізнавання з PDF-файлів та редагування в цьому форматі. Система штучного інтелекту дозволяє автоматично виявляти та виправляти помилки після першого виправлення вручну. Новий спеціально розроблений програмний модуль Dcspeckle дозволяє розпізнавати документи з погіршеною якістю (факси, копії, копії копій тощо). Перевагою програми є можливість розпізнавання кольорового тексту та коригування голосом. Версія OmniPage існує для комп'ютерів фірми Macintosh.

• Див: Башмаков А. І., Башмаков І. А.Інтелектуальні інформаційні технології.