Постановка задачі розпізнавання образів

Довбиш А.С.

ТЕОРІЯ РОЗПІЗНАВАННЯ ОБРАЗІВ

Конспект лекцій

для студентів спеціальності

“Інформатика”

Суми-2009

Зміст

Перелік умовних позначень................................................... 4

Вступ........................................................................................ 5

Розділ 1. Стратегія розпізнавання образів............................ 6

1.1 Основні принципи та визначення ТРО.......................... 6

1.2 Постановка задачі розпізнавання образів....................... 8

1.3 Побудова вирішальних правил....................................... 8

1.4 Критерій оптимізації вирішальних правил.................... 9

1.5 Основні підходи до розв’язання задач розпізнавання образів 10

Розділ 2. Детерміновані методи ТРО.................................. 12

2.1 Метод еталонів................................................................ 12

2.2 Метод еталонів, що дробляться..................................... 13

2.3 Лінійні вирішальні правила........................................... 15

2.4 Метод найближчих сусідів............................................. 18

2.5 Метод K найближчих сусідів......................................... 19

2.6 Метод потенційних функцій......................................... 19

2.7 Структурні (лінгвістичні методи)................................. 22

2.8 Метод кластер-аналізу.................................................... 24

Розділ 3.Статистичні методи ТРО....................................... 29

3.1 Байесівський класифікатор............................................ 29

3.2 Визначення мінімального обсягу репрезентативної

навчальної вибірки............................................................... 31

Розділ 4. Детерміновано-статистичні методи ТРО............ 36

4.1 Метод еталонів Трубовича............................................. 36

4.2 Метод еталонів опису..................................................... 36

4.3 Узагальнена математична модель розпізнавання

образів.................................................................................... 37

4.4 Інформаційно-екстремальні методи ТРО..................... 39

Розділ 5. Метод групового врахування аргументів........... 53

5.1 Основні принципи і загальна схема методу групового врахування аргументів 54

5.2 Багаторядні поліноміальні алгоритми МГВА.............. 63

5.3 Комбінаторний алгоритм МГВА.................................. 66

5.4 Нечіткий МГВА.............................................................. 71

Список літератури................................................................ 80

Перелік умовних позначень

ВП – вирішальні правила;

ОР – ознака розпізнавання;

ТРО – теорія розпізнавання образів;

ЕВ – еталонний вектор.

Вступ

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

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

Приклад: Британська система прогнозування погоди (розпізнавання образів шляхом аналогії).

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

Розділ 1. Стратегія розпізнавання образів

Основні принципи та визначення ТРО

Основними принципами ТРО є

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

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

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

Достовірність розпізнавання визначається повною ймовірністю правільного прийняття рішень

,

де - безумовні ймовірності, - перша та друга достовірності відповідно.

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

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

Вектором-реалізацією образу називається структурований (впорядкований) вектор-кортеж

,

де - значення i-ї ознаки розпізнавання, одержане при j-му випробуванні.

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

.

У загальному випадку процес розпізнавання образу складається з двох етапів:

- етап навчання, на якому формуються деяким оптимальним способом вирішальні правила;

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

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

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

, (1.1.1)

де – контейнер класу розпізнавання.

Постановка задачі розпізнавання образів

Розглянемо детерміновану постановку задачі розпізнавання образів .

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

1. ;

2. ;

3. ; ; (1.2.1)

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

Таким чином, в топологічному розумінні класом розпізнавання є область у просторі ознак розпізнавання – елемент розбиття

Побудова вирішальних правил

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

Алгоритм побудови вирішальних правил:

- вимірювання ознак розпізнавання;

- нормалізація значень ознак розпізнавання, яка полягає у приведенні значень до вигляду, зручного для оброблення на ЕОМ;

- формування векторів-реалізацій образу на кожному випробуванні;

- формування навчальної матриці;

- допустимі перетворення навчальної матриці в субпарацептуальному просторі;

- розбиття деяким оптимальним способом простору ознак на класи розпізнавання;

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