пʼятниця, 23 січня 2009 р.

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

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

Вибір методу синтезу системи не розв’язує до кінця проблеми складання конкретної програми і проблеми реалізації. В більшості випадків є образи, що представляють кожний з розглядуваних класів. В таких випадках можна скористатися методами розпізнавання, які називаються "навчання з учителем". У схемі "навчання з учителем" система навчається розпізнавати образи за допомогою різного роду адаптивних схем. В деяких прикладних задачах для елементів, що належать до визначеного класу, навчаючі множини невідомі. У таких випадках, властиво, і можна звернутися до методів "розпізнавання з учителем". Розпізнавання по схемі навчання з учителем характеризується тим, що відома правильна класифікація кожного навчаючого образу. У випадку навчання без учителя потрібно конкретно вивчити класи образів, які є в даній інформації [1].
Типовим прикладом лінійного представлення є блок-схеми, технічні і архітектурні креслення і т.д. Лінійні структури можуть бути описані аналітично, а з використанням ЕОМ можна порівняно легко формувати складні структури. Ці структури використовують також в тих випадках, коли для вводу зображення застосовують методи слідкування за контуром чи іншими траєкторними точками. Яка б структура не використовувалась, в машинному представленні найкраще використовувати єдиний вид структури даних – ланцюговий код. Це послідовність з восьми цифр.

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

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

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

Інший підхід відомий як метод потенціальних функцій [6], відрізняється тим, що об’єднуються деякі розмиті множини, що описуються так званою потенціальною функцією. При цьому здійснюється апроксимація не розв’язуючою, а дискримінантною функцією. Її значення вираховується шляхом складання значень «потенціалу», який зменшується в міру зникання від деяких центрів, що вибираються в процесі навчання. Цей підхід є еквівалентним апроксимації дискримінантної функції за допомогою функціонального ряду. Суть полягає в тому, що на просторі вхідних векторів Х задається функція, яка називається «потенціалом». Потенціал визначається наближенням двох точок і задається як функція відстані між точками. Потенціальна функція така, що вона монотонно зменшується із збільшенням відстані.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Щоб знайти розв’язок, що задовольняє всім потребам, потрібно зробити над компонентами зображення визначену послідовність обчислювальних і логічних операцій. Ця послідовність називається алгоритмом розпізнавання. Ідея, яка покладена в основу алгоритму розпізнавання, називається методом розпізнавання. Розв’язуюча функція задає розбиття множини V всіх значень сигналу W на підмножини. Ці підмножини називаються областями розв’язків. Для всіх значень сигналу, які належать одній області розв’язків, розв’язуюча функція має постійне значення. Інколи зручно задавати розв’язуючу функцію за допомогою так званих дискримінантних функцій, які визначені для кожної області розв’язку. В випадках, коли існує істинна класифікація і розв’язок, прийнятий за клас представленого зображення, не збігається з його істинним класом, говорять про помилку розпізнавання. Число помилок можна зменшити, якщо передбачити для розв’язуючого правила можливість видавати для важких (сумнівних) зображень невизначений розв’язок або так звану відмову від розпізнавання. Оскільки розв’язок при наявності випадкових спотворень є випадковим, то говорять про імовірність помилки і імовірність відмови. Ці величини є найважливішими характеристиками системи розпізнавання або алгоритму розпізнавання.
Ймовірність помилки є основним критерієм, за яким оцінюється практична застосовність системи розпізнавання в задачах, де існує об’єктивна правильна класифікація. Тому проблема розпізнавання формулюється як знайдення оптимальних за цим критерієм розв’язуючих правил.
При розпізнаванні зображень, вільних від випадкових спотворень, але інваріантних до переносу, розв’язуюче правило може бути отримане за допомогою процедури центрування: деяка характерна точка зображення повинна бути шляхом переносу всього зображення поміщена в фіксовану точку поля зору. Після цього всі зображення, які відрізняються одне від одного тільки переносом, стають ідентичними і розв’язок може бути зроблений незалежно від початкового положення. Аналогічно може бути здійснена нормалізація зображення за їх розмірами. Але в умовах спотворень центрування і взагалі нормалізація є дуже складними.

Розпізнавання простих геометричних фігур і цифр

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

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

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

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

Different methods of improvement and recognition of images

Different methods of improvement and recognition of images are considered. The description of algorithms of selection, segmentation, description and identification of objects is submitted. The special attention is given to the methods of the description of objects: chain codes, Fourier transform, signature; to the methods of improvement of the image on spatial and frequency domains.

Algorithms, which are used for recognition of simple geometrical figures and numbers are realized and described. Here have come: a method of comparison of the areas of figures, a method with use of Fourier transform, a method of crossings of object straight lines.

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

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

Реалізовано і описано алгоритми, які використано для розпізнавання простих геометричних фігур і цифр. Сюди ввійшли: метод порівняння площ фігур, метод з використанням перетворення Фур’є, метод перетинів об’єкта прямими.