Досліждення проблем розпізнавання образів

Ця стаття відноситься до групи довідкових статей для студентів ФІН.

• Портал:Інформаційні науки

Основні поняття розпізнавання образів

Образ є описом об'єкту.

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

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

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

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

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

Процеси сенсорного типу розпізнання забезпечують ідентифікацію просторових та часових образів.

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

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

Приклади розпізнання абстракцій - понятійне розпізнання:

- впізнати доведення

- провести паралелі між ситуаціями

- узагальнення досвіду

Задача розпізнавання образів

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

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

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

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

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

Приклад:

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

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

Система інтерпритує їх, виокремлюючи істотні ознаки і формуючи на їх основі прогноз.

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

Змістовних характер задачі класифікації	Вид вихідних даних	Вигляд відповіді системи розпізнавання
Розпізнавання символів	Оптичні сигнали або елементи розгортки	Назва символу
Прогноз погоди	Синоптичні карти	Прогноз погоди

Предмет розпізнавання образів

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

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

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

Між образами та класами образів існує деяке ієрархічне підпорядкування.

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

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

Основні задачі, що виникаються при розробці систем розпізнавання образів

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

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

• Проблема чутливості

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

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

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

Цей процес полягає в тому, що кожній характеристиці образа присвоюється символ із множини елементів алфавіту {x_i}

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

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

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

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

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

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

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

Основні концепції побудови систем

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

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

Принцип перерахування членів класу

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

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

Принцип спільності властивостей

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

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

Принцип кластеризації

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

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

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

• еврестична
• математична
• лінгвістична

Методології побудови принципів 1-3

Еврестичний метод

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

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

Математичний метод

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

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

• детерміністські
• статистичні

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

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

Лінгвістичні (синтаксичні) методи

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

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

Книги з теорії розпізнавання образів

1. Файн В.С. Опознавание изображений

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

1. Фу К. Структурные методы в распознавании образов

Новое направление исследований по автоматической обработке изображений связано с открытием аналогии между структурой изображений и синтаксисом языка. Развитие этого направления потребовало привлечения методов математической лингвистики и привело к роду обобщений порождающих грамматик Хомского. Настоящая книга служит хорошим введением как в методы автоматической обработки изображений, так и в новые аспекты исследования формальных грамматик. Книга адресована специалистам по распознаванию образов, автоматической обработке изображений, математической лингвистике. Она доступна также и тем читателям, которые впервые знакомятся с этой областью науки.

1. Фурман Я.А., Юрьев А.Н., Яншин В.В. Цифровые методы обработки и распознавания бинарных изображений

Рассмотрены модели и методы обработки и распознавания изображений в бинарных по яркости сценах. Основное внимание уделено подходам, приводящим к алгоритмам, реализующимся на современных вычислительных устройствах. Для синтеза алгоритмов применен аппарат дискретных цепей Маркова. На его основе с использованием одномерной модели строк (столбцов) бинарного изображения описаны новые подходы к фильтрации бинарной сцены, обеспечивающие небольшие временные затраты. Обобщён метод цепного кодирования контуров изображения по Фримену на комплексную плоскость. книга предназначена для научно-технических работников, занимающихся разработкой алгоритмов, проектированием устройств обработки изображений и распознавания образов, а также аспирантов и студентов старших курсов соответствующих специальностей.

1. Гренандер У. Лекции по теории образов. 3-х томник

В период с 1960 по 1970 годы известный американский математик Ульф Гренандер создал основы теории паттернов. К сожалению, автору не удалось придать теории законченную форму, и он был вынужден опубликовать изложение результатов своих многолетних исследований только в виде трех томов своих лекций. Ульф Гренандер охарактеризовал свой подход следующим образом: "Любая математическая теория представляет собой набор частных случаев, трактуемых с единых позиций". Теория паттернов остается незавершенной. Существует ряд причин, препятствующих приданию ей законченной формы. Одна из них заключается в отсутствии примеров эффективного практического применения теории Гренандера, обобщение которых привело бы к ее уточнению и дальнейшему развитию. Выход в свет работы Гренандера привлек внимание специалистов в области распознавания образов, информатики и программирования. Однако со временем, ввиду отсутствия эффективных практических применений, интерес к теории паттернов значительно уменьшился.

1. Эдвард А. Патрик Основы теории распознавания образов

Классика теории распознавания образов

1. Тэрано Т., Асаи К., Сугэно М. Прикладные нечеткие системы

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

1. Ту Дж., Гонсалес Р. Принципы распознавания образов

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