Материал: Лекція 10

Лекція 10

Тема: Розпізнавання образів.

План

1. Історія виникнення ШС автоматизованого розпізнавання.

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

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

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

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

1. Історія виникнення штучних систем автоматичного розпізнавання і їх реалізації.

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

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

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

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

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

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

Протягом достатньо тривалого часу проблема розпізнавання привертає увагу фахівців в області прикладної математики, а потім і інформатики. Так, зокрема, на сайті http://www2.cs.kspu.ru відзначають роботи Р. Фішера, виконані в 20-х роках і що привели до формування дискриминантного аналізу як одного з розділів теорії і практики розпізнавання. В 40-х роках А. Н. Колмогоровым і А. Я. Хинчиным поставлена задача про розділення суміші двох розподілів.

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

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

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

І до середини 70-х років визначився вигляд розпізнавання як самостійного наукового напряму, з'явилася можливість створення нормальної математичної теорії розпізнавання.

2. Основні визначення та методи.

Здатність "розпізнавати" вважається основною властивістю людських істот, як, втім, і інших живих організмів. Образ є описом об'єкту.

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

Відповідно до характеру розпізнаваних образів акти розпізнавання можна розділити на два основні типи:

• розпізнавання конкретних об'єктів

• розпізнавання абстрактних об'єктів.

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

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

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

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

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

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

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

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

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

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

В табл. 1.1 перерахований ряд задач класифікації, а також відповідні початкові дані і відповіді, видавані системою.

Таблиця 1.1 - Задачі класифікації

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

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

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

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

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

Методика віднесення елемента до якого-небудь образу називається вирішальним правилом.

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

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

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

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

Приклади задач розпізнавання образів:

• розпізнавання букв;

• розпізнавання штрих-кодів;

• розпізнавання автомобільних номерів;

• розпізнавання осіб і інших біометричних даних;

• розпізнавання мови.

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

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

Як другий приклад розглянемо наступні п'ять англійських букв: C O I N 8

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

Мал. 13.1 - Блок-схема простої логічної (питання- відповідь) процедури класифікації ознак;

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

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

Мал. 13.2 - Ієрархія відносин між чинами і класами образів;