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

30

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

(реферат)

Біологічні аналоги систем РО

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

Система зору людини і тварин

Сітківка ока - 125 млн. рецепторів. Зоровий нерв - 80 тис. волокон.

Рецептивне поле (100- 200 мкм) - реагує на контур (перепад освітленості).

Сітківка (центр і периферія), Центр (10 сітківки - 6 мм. кори); (150 сітківки - 0,5 мм. кори);

Око сприймає зміну освітленості - в 108 раз.

Етапи розпізнавання: 1) з'явився предмет; 2) поверхнево оцінити; 3) детально оцінити.

Розпізнавання образа - 0,15с - для нетренованого спостерігача; 0,06 с - для тренованого. В оці - перевернуте зображення.

Права півкуля мозку - образи, ліва - логіка, мова. Права півкуля мозку - форма + розмір (детально); ліва - форма без розміру - схематично. Ліва - дерево, права - перебір. Образ - більш первинний, ніж слово; образ - не логіка.

Формування зору; погляди Локка - мозок - чиста пластинка. Зір в курчат налагоджується за 1 день; 1 нейрон - контакти з 1000 нейронами.

Сприйняття зображення; рух очей - на змістові центри (кривизна контуру). Тремор - дрижання (частота 100 Гц, маленькі стрибки на 20 кут сек.); кожні 0,25 с - великий стрибок (саккодичний), око під час стрибка сліпне. Діаметр поля змінюються в 250 разів (деталізація), чим сильніша освітленість - менший діаметр.

Око бачить не колір, а зміну кольору. Поля кольору (еталонні) - 15 нм. (червоно-зелені, синьо-жовті, чорно-білі).

Оптичні ілюзії

Система зору людини є недосконалою, для неї характерні різноманітні оптичні ілюзії. Наприклад, ілюзія „два обличчя - ваза”, „неоднозначна теща” (Грегори Р. Розумний глаз, 1970); стрілки однакової довжини, перенасичені рисунки „промені” (1972) .

Розпізнавання зображень

Гіпотези розпізнавання: детекторна і просторово-частотна. Паттерн - узор, текстура.

Детекторна. В корі виділяються елементи, що часто зустрічаються: лінії, вузли, площадки.

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

Розпізнавання контуру зображень.

Ознаки контура і гештальт-ознаки (для всієї фігури). Гештальт - цілісний образ

Навколо контуру - огинаюча контуру (рух очима)

Найбільш інформативні відрізки - з максимальною кривизною.

Ознаки контуру (первинні): прямий чи кривий; / випуклий чи увігнутий; / ламаний чи гладкий;

Перехід від первинних до вторинних. Симетрія фігури - спрощення.

Третинні ознаки - на об'єкт натягуються оболонки.

Транспозиційні ознаки - положення фігури відносно інших фігур.

Побудова багатогранників - координати вершин - випадково (параметри: число вершин, число гострих кутів).

Ознаки: площа, витягнутість, асиметрія.

Транспозиційні ознаки 1 роду: орієнтація, положення осі симетрії.

Транспозиційні ознаки 2 роду: близкість по елементам контуру.

Розпізнавання і класифікація. Розпізнавання - ознака не усвідомлюється.

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

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

Розпізнавання по глобальним і локальним ознакам контура.

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

Порушена права півкуля - агнозія обличчя.

При сприйманні об'єкта:

-константність розміру; / - константність форми;

Перекриття (предмет і фон). Трансформації (зміщення)

Сприйняття фігури і фону, одночасно - тільки фігура або фон.

Групування. Контури - максимально гладкі.

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

Схожість - ********

++++++

********

Орієнтація (текстура). Замкнутість контуру.

Форма - положення частин фігури відносно один одного.

Ілюзії (стрілки - довжина залежить від напряму)

Детекторна гіпотеза - зображення можна поділити на елементи (лінії, дуги).

Квадрат - не сума 4 ліній.

Голографічна модель мозку

Голографія. Мозок - 50 млрд. клітин. Зв'язок поле на сітківці - стовби (модулі) в мозку. Стовпи - по вертикалі (260, 110 шарів), всі орієнтації образа. Стовпи (циліндри) перекриваються. Реакція на контури і на текстуру.

Поля зору - кусочно-квазіголографічний метод. Поворот легко сприймається до 15 градусів.

Принцип голографічної пам'яті і розпізнавання образів

Багато авторів відзначали, що кора мозку проявляє властивості голографічної пам'яті. Можна перерахувати довгий ряд імен авторів голографічних моделей мозку (R.Beurle, Р.R.Westlake, K.Pribam, І.Г.Беспалько, Р.Greguss, А.Воrsellino, T.Poggio, Ю.А.Воронов, С.Н. Брайнес, А.І.Суслов, В.А.Преснов, Г.І.Шульгина і ін.). і у всіх основою такої позиції була схожість властивостей нашої пам'яті з властивостями голографічної системи.

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

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

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

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

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

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

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

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

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

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

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

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

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

Клас образів - це підмножина образів з найбільш схожими суттєвими ознаками.

Розпізнавання образів (РО) - процес поділу образів на класи.

Мета РО - розробка системи РО, яка б наближувалася по своїм можливостям до системи зору людини.

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

Нехай дана множина об'єктів Ti; i=1,. ..q (кількість об'єктів може бути практично безкінечною); (P - Pattern)

Всі об'єкти поділені на класи (підмножини) Ck, де k=1, .. m. (E - Etalon)

Об'єкти задаються значеннями ознак Xj, j=1, .. n; Ti = {X1(Ti), .. Xn(Ti)}

Задача розпізнавання полягає у знаходженні степені належності об'єкту Ti до кожного з класів Ck.

Об'єкт Ti вважається належним до того класу Ck, для якого коефіцієнт (степінь) належності K(Ti, Ck) максимальний.

Наприклад

Розглянемо множину об'єктів Ti „Транспортні засоби”

Ознаки Xj: кількість коліс, наявність двигуна, вага вантажу

Класи Ck: Велосипед, мотоцикл, легковий автомобіль, вантажний автомобіль, інший

Апріорна інформація в задачі розпізнавання часто задається у вигляді таблиці навчання:

	Ознака	X1	X2	X3
Клас		Кількість коліс	Наявність двигуна (0/1)	Вага вантажу, кг
C1	Велосипед	2	0	<100
C2	Мотоцикл	2, 3	1	<200
C3	Легковий автомобіль	4	1	(>200) AND (<500)
C4	Вантажний автомобіль	4, 6, 8, 10	1	>1000
C5	Інший

Розпізнавання: Транспортний засіб (3, 1, 150) - мотоцикл

	Ознаки	T1 (3, 1, 150)	T2 (4, 0, 50)
Клас		K(T1, Ck)	K(T2, Ck)
C1	Велосипед	0	2
C2	Мотоцикл	3	1
C3	Легковий автомобіль	2	1
C4	Вантажний автомобіль	1	1
C5	Інший

З поняттям „розпізнавання образів” тісно пов'язані задачі класифікації.

Проблема: які ознаки об'єкта вибрати для розпізнавання?

Типові задачі класифікації наступні:

Задача ідентифікації (вирізнити конкретний об'єкт серед інших).

Віднесення об'єкту до певного класу.

Кластерний аналіз (класифікація без вчителя).

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

Технічна діагностика (дефекти).

Медична діагностика (кардіограми).

Розпізнавання літер (друкований і рукописний текст).

Розпізнавання мови.

Робототехніка (технічний зір).

Охоронні системи (відбитки пальців, обличчя).

Схема розпізнавання:

Сприйняття Р-об'єкта у вигляді С-об'єкта (первинний опис, дискретизація)

Попередня обробка С-об'єкта (зменшення шумів)

Формування модельного опису М-об'єкта (інформативні ознаки)

Класифікація

Режими розпізнавання:

1. Режим навчання

Робочий режим

Попередня обробка об'єктів розпізнавання

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

Попередня обробка зображень

1. Дискретизація (оцифрування), поділ на пікселі з певним кроком.

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

3. Сегментація

4. Отримання ознак зображення.

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

1. монохромні;

2. у відтінках сірого

3. кольорові.

Сегментація зображення

Сегментація - це розділення зображення на складові частини, що мають спільні властивості [5]. Існує велика кількість алгоритмів сегментації зображення, але більшість з них можна поділити на дві групи, кожна з яких використовує фундаментальні властивість зображення - подібність та відмінність. У відповідності до цього існує два основних підходи до сегментації:

метод пошуку однорідних областей;

метод виділення контурних ліній.

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

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

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

Tk > G(i,j) Tk-1, k (0, kmax), де Tk - значення k-го порогового рівня. У випадку kmax = 1 цифроване зображення називають бінарним (двоградаційним). Елементи зображення з рівнем яскравості більшим за порогове приймають значення 1, менше порогового - 0.

В нашому випадку використовується сегментація методом пошуку однорідних областей. Сусідні елементи визначаються у восьмизв'язній області Мура (рис.3.1, 3.2). Для отримання бінарного зображення використовується один пороговий рівень, що відповідає яскравості 125. Цей рівень яскравості вибраний тому, що показник яскравості може змінюватись в межах від 0 до 255, тому рівень 125 відповідає середньому значенню. Якщо яскравість точок менша, ніж 125, то вони відносяться до сегменту, якщо ж більша - то це фон.

	1	2	3
	8	0	4
	7	6	5

30

Рис.1. Вигляд восьмизв'язної Рис. Визначення приналежності до

області Мура, фону чи об'єкту,

0 - початкова точка, заповнення

сегментів 1 і 2

1 .. 8 - сусідні

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

1. Шаблонні системи, Метод суміщення з еталоном (шаблоном, маскою, набором еталонів) (структура графу однакова для всіх зображень, але різні стани вершин), задано клас перетворень (масштабування, поворот, ...), розпізнавання друкованих символів.

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

1. Метод допустимих перетворень об'єкта (гумовий аркуш)

1.3. Просторово-частотний метод (Фур'є перетворення)

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

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

2. Логічні методи, засновані на дискретному аналізі і обчисленні висловлювань. З використанням логічних ознак об'єкта розв'язується система булевих рівнянь і знаходяться невідомі величини - класи.

3. Ознакові системи, Розпізнавання у просторі ознак, дискримінантні методи (ймовірнісні і детерміновані), об'єкт - точка у просторі ознак.

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

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

3.3 Байесевські методи

3.4 Метод опорного словника

3.5 Метод зондів

4. Нейронні мережі, перцептрон.

5. Експертні системи.

6. Шаблонні системи (метод суміщення з еталоном)

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

Кореляційний метод розпізнавання

Розпізнавальні системи розділяються за способом зберігання еталонних наборів, сформованих при проектуванні систем РО: системи з фотомаскою, системи з електричними моделями еталонів (у вигляді схем резисторів; феритових осердь з котушками і т.п.) та математичні системи.

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

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

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

Математична модель системи РО, яка використовує принцип суміщення з еталоном, поділяє зображення на багато елементарних прямокутних комірок, які у сукупності створюють загальний прямокутник зображення. У кожній комірці вимірюється яскравість або інша оптична величина, яка характеризує освітлення. Відповідно, для кожної комірки виробляється цифра коду: наприклад, у двоїстій системі числення «1» відповідає освітленій комірці, а «0» - неосвітленій. Результуючий код виглядає як рядок, складений з результатів вимірювання всіх рядків рецепторного поля.

Набір результатів таких вимірювань рецепторного поля створює вектор, який у двійковій системі числення має, наприклад, вигляд P={0011010………111100010}. Відповідний математичний еталон теж має вигляд вектора Еj={0010010………101100010}, який може відрізнятися від зображення рецепторного поля P.

Скалярний добуток Кj=P*MjT характеризує їхню схожість і має назву «коефіцієнт кореляції» (за аналогією з подібними обчисленнями в теорії ймовірності). Задача полягає у знаходженні еталону, який має найбільший коефіцієнт кореляції з зображенням. Порівняння виконують багаторазово, бо точне розміщення зображення невідоме, а центрування (визначення точного положення будь-яким простим методом) не завжди відбувається точно через перешкоди.

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

Метод допустимих перетворень

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

1. Зміщення (центрування)

Масштабування.

3. Поворот.

4. Деформація.

5. Пошкодження (шум)

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

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

Просторово-частотний метод (Фур'є перетворення)

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

Структурні методи (синтаксичний, лінгвістичний метод)

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

Послідовність обробки зображень

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

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

3. Зображення представляється як послідовність (ланцюг) символів.

4. Розпізнавання образу полягає у порівнянні вхідного ланцюга образу з еталонним.

Синтаксичні методи розпізнавання, класифікація граматик за Хомським

Класифікація формальних граматик за Хомським: контекстно-залежна і контекстно-вільна.

Приклади структурних методів

Структурний метод розпізнавання кривих за Фріменом.

Для апроксимації кривої використовують одиничні вектори 1..8.

/ Опис зображень на основі формальних граматик

Структурний метод розпізнавання прямокутників (4 напрямки)

Структурний опис зображення сніговика (відношення, всередині, вище, нижче, зліва, ...)

Реальні образи одночасно цілісні і ділимі.

Квазітопологічний метод (структурний)

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

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

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

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

Згідно з цими правилами кодова комбінація літери «А» має вигляд «1, 3, 1, 3, 3, 1, 3». Цей код отриманий за умови обходу, починаючи з точки «а».

Недоліки цього методу: бруд, переміщення лінії, видалення/ додавання фрагменту утруднює якісне розпізнавання образу; потрібні додаткові ознаки для розпізнавання, наприклад, літер «І», «Ї», «И», «Й».

30

30

Рис.4. Графи літери «А» Рис.5. Визначення коду літери «А»

Розпізнавання у просторі ознак

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

В якості міри близькості між об'єктами a i b використовують зважені евклідові відстані:

,

де ai, bi - ознаки об'єктів, wi - вага ознаки.

Кластерний аналіз. Гіпотеза компактності

Всі дискримінанті методи спираються на гіпотезу компактності. Відповідно до цієї гіпотези класу відповідає компактна множина точок у деякому класі ознак. Термін „компактний” в даному випадку означає:

число граничних точок мале у порівнянні із загальним числом точок;

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

майже будь-яка внутрішня точка має у достатньо великому околі лише точки цієї множини.

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

Рис.6. Класи розділяються

Якщо класи частково перекриваються, то вони розділюються приблизно (вибрати інші ознаки)

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

Кластеризація - виділення скупчень за певними ознаками.

Метод потенціалів

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

,

де k - постійний коефіцієнт, q - величина заряду, R - відстань від точки до заряду.

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

Рис.7. Суперпозиція зарядів

Оскільки в попередній формулі є ділення на нуль при R=0, то використовується формула

,

де коефіцієнт б визначає швидкість зміни потенціалу.

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

(В просторі ознак точки різних класів А і В створюють потенціал певного знаку, клас нової точки С визначається тим, який потенціал в точці С буде більший:

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

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

Байєсівські методи розпізнавання

Байєсівські методи належать до імовірнісних.

Нехай існують класи K1 .. Km, які описується вектором ознак У. З кожним класом пов'язана апріорна ймовірність P(Kj) появи об'єкта j-го класу (частота появи). Умовна ймовірність того, що класу Кі відповідають ознаки У позначається P(Y/Ki). Тоді можна визначити ймовірність того, що вектору ознак У відповідає клас Кі.

,

де спільну для всіх класів величину p(Y) можна скоротити.

Наприклад, потрібно відрізнити стиглі яблука від недостиглих (2 класи: K1=„Стиглі” і K2=„Недостиглі”), m= Вектор ознак Y=(розмір /малий, великий /, колір /зелений, червоний/). Ймовірність попадання стиглих яблук більша: р(К1)=0,7; р(К2)=0,3.

Якщо яблука стиглі (К1): Y=(великий, червоний), то р(У, К1)=0,95;

Y=(малий, зелений), то р(У, К1)=0,05;

Якщо яблука не стиглі (К2): Y=(великий, червоний), то р(У, К2)=0,05;

Y=(малий, зелений), то р(У, К2)=0,95;

Якщо спостерігаються ознаки Y=(великий, червоний), то

p(K1/Y)=0,7*0,95 = 0,665; p(K2/Y)=0,3*0,05 = 0,015.

Метод опорного словника (розпізнавання у просторі ознак)

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

Припустимо, що ми розпізнаємо слово «ЛИСТ» з 4-х літер. Спочатку виділяється характерна сукупність ознак кожного символу цього слова:

ХЛ={х1, х2,…,хр}Л; ХИ={х1, х2,…,хр}И;

ХС={х1, х2,…,хр}С; ХТ={х1, х2,…,хр}Т.

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

gA(X1S), gБ(X2S),…,gЬ(X32S)

приймають максимальне цифрове значення, коли сукупність ознак ХjS відноситься до літери, для якої складена конкретна вирішальна функція. Наприклад, ga(XA) приймає максимальне значення, а ga(XЛ) приймає мінімальне значення.

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

S1(АБАТ)=gA(XЛ)+ gБ(XИ)+ gA(XС)+ gТ(XТ);

……………………………………………….

S10(ЛИСТ)=gЛ(XЛ)+ gИ(XИ)+ gС(XС)+ gТ(XТ);

……………………………………………….

S50(ЯЩУР)=gЯ(XЛ)+ gЩ(XИ)+ gУ(XС)+ gР(XТ).

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

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

Метод зондів (розпізнавання у просторі ознак)

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

Розглянемо принцип використання зондів у припущенні, що наша система РО повинна розпізнавати образи лише чотирьох великих друкованих літер «ЛЕНА», написаних від руки.

Ці літери пишуться (з деякими обмеженнями у розмірах) електропровідними чорнилами на звичайному папері. Можна вважати, що кожний зонд 1, 2, 3 (рис. 3.3) складається з двох електродів, розділених ізоляційним проміжком. Дотик до електропровідних чорнил на папері електрично з'єднує ці два електроди, по них протікає струм, який і фіксує наявність лінії символу на даній ділянці під зондом. Сигнали від всіх електродів, що дотикаються до літери, передаються на дешифратор, який і виконує функції класифікації літери (табл. 3.1). Кожному зображенню одного класу (одній літері) відповідає одна комбінація збуджених зондів. Зонд вважається збудженим, якщо він пересікає лінії літери. Реакцією зонду є «1» у разі збудження і «0» - в іншому випадку. Таким чином, зонди видають код, який складається з нулів та одиниць.

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

30

Рис. 8. Використання зондів для літер «ЛЕНА»

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

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

Таблиця 1. Коди зондів для літер «ЛЕНА»

Літери	Зонди
	1	2	3
Л	1	0	0
Е	1	1	1
Н	0	1	0
А	1	1	0

Системи оптичного розпізнавання, FineReader 4.

OCR - Optical Character Recognition

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

Сьогодні вже існує рішення, що наближається до здібностей людини читати, яке використовує в своїй основі принципи розпізнавання живих систем - технологія цілісного цілеспрямованого адаптивного розпізнавання (Integral Purposeful Adaptive perception, IPA-технологія), реалізована в ABBYY FineReader (або „Фонтанне перетворення”). Саме завдяки IPA-техноло/гії, FineReader демонструє високу точність розпізнавання друкарських і рукодрукованих символів.

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

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

Розробники компанії ABBYY роблять спроби замінити традиційне розпізнавання окремих символів «розпізнаванням з розумінням». Тобто, комп'ютер сприймає не тільки те, що прямо спостерігається на зображенні, але і те, що від зображення очікується. Робота такої системи стала можлива завдяки принципам цілісності, цілеспрямованості і використовуванню контексту. Ці принципи були запропоновані Олександром Шамісом (нині співробітником компанії ABBYY) і групою учених Науково-дослідного центру електронної і обчислювальної техніки в 70-ті роки. Разом з принципом адаптивності, принципи цілісності і цілеспрямованості пошуку стали основою технології FineReader, системи, що розпізнає рукодруковані й друкарські документи. Це якраз ті моменти, які характеризують наше сьогоднішнє уявлення про зорове сприйнятті людини.

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

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

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

Відповідно до трьох основоположних принципів інженерами ABBYY був розроблений новий структурний алгоритм розпізнавання символів. Окрім нього в FineReader використовуються і інші широко відомі алгоритми: ознаковий, растровий (шаблонний) і ін.

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

Цей метод дозволяє виділяти елементи на розірваних і спотворених зображеннях.

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

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

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

Структурно-плямистий метод (фонтанне перетворення)

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

Ідентифікація відвідувачів по особистому підпису

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

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

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

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

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

1) формування багатовимірного масиву точок, одержуваних в процесі написання (введення) підпису, з відповідними координатами (x,y), тиском пір'я (p), його нахилом (j ), швидкістю (v) в даній точці і т. п.,

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

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

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

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

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

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

* розподіл миттєвої швидкості і тиску по довжині підпису,

* розподіл орієнтації вектора градієнта в кожній точці підпису,

* час написання підпису,

* середній тиск по довжині підпису і середня швидкість.

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

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

Висновки

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