Методи розпізнавання образів
В даний час існує безліч завдань, в яких потрібно прийняти деяке рішення в залежності від присутності на зображенні об'єкта або класифікувати його. Здатність «розпізнавати» вважається основною властивістю біологічних істот, в той час як комп'ютерні системи цією властивістю в повній мірі не володіють.
Розглянемо загальні елементи моделі класифікації.
Клас - безліч об'єктом мають загальні властивості. Для об'єктів одного класу передбачається наявність «схожості». Для завдання розпізнавання може бути визначено довільну кількість класів, більше 1. Кількість класів позначається числом S. Кожен клас має свою ідентифікує мітку класу.
Класифікація - процес призначення міток класу об'єктів, відповідно до деякого опису властивостей цих об'єктів. Класифікатор - пристрій, який в якості вхідних даних отримує набір ознак об'єкта, а в якості результату видає мітку класу.
Верифікація - процес зіставлення примірника об'єкта з однією моделлю об'єкта або описом класу.
Під чином будемо розуміти найменування області в просторі ознак, в якій відображається безліч об'єктів або явищ матеріального світу. Ознака - кількісний опис тієї чи іншої властивості досліджуваного предмета або явища.
Простір ознак це N-мірний простір, певне для даної задачі розпізнавання, де N - фіксоване число вимірюваних ознак для будь-яких об'єктів. Вектор з простору ознак x, відповідний об'єкту завдання розпізнавання це N-мірний вектор з компонентами (x_1, x_2, ..., x_N), які є значеннями ознак для даного об'єкта.
Іншими словами, розпізнавання образів можна визначити, як віднесення вихідних даних до певного класу за допомогою виділення істотних ознак або властивостей, які характеризують ці дані, із загальної маси несуттєвих деталей.
Прикладами завдань класифікації є:
- розпізнавання символів;
- розпізнавання мови;
- встановлення медичного діагнозу;
- прогноз погоди;
- розпізнавання осіб
- класифікація документів та ін.
Найчастіше вихідним матеріалом служить отримане з камери зображення. Завдання можна сформулювати як отримання векторів ознак для кожного класу на даному зображенні. Процес можна розглядати як процес кодування, що полягає в присвоєнні значення кожною ознакою з простору ознак для кожного класу.
Якщо розглянути 2 класу об'єктів: дорослі і діти. В якості ознак можна вибрати зріст і вагу. Як випливає з малюнка ці два класи утворюють два непересічних безлічі, що можна пояснити обраними ознаками. Однак не завжди вдається вибрати правильні вимірювані параметри в якості ознак класів. Наприклад вибрані параметри не підійдуть для створення непересічних класів футболістів і баскетболістів.
Другим завданням розпізнавання є виділення характерних ознак або властивостей з вихідних зображень. Це завдання можна віднести до попередньої обробки. Якщо розглянути задачу розпізнавання мови, можна виділити такі ознаки як приголосні і голосні звуки. Ознака повинен представляти із себе характерна властивість конкретного класу, при цьому загальні для цього класу. Ознаки, що характеризують відмінності між - міжкласові ознаки. Ознаки загальні для всіх класів не несуть корисної інформації і не розглядаються як ознаки в задачі розпізнавання. Вибір ознак є однією з важливих задач, пов'язаних з побудовою системи розпізнавання.
Після того, як визначені ознаки необхідно визначити оптимальну вирішальну процедуру для класифікації. Розглянемо систему розпізнавання образів, призначену для розпізнавання різних M класів, позначених як m_1, m_2, ..., m_3. Тоді можна вважати, що простір образів складається з M областей, кожна містить точки, відповідні чином з одного класу. Тоді задача розпізнавання може розглядатися як побудова меж, що розділяють M класів, виходячи з прийнятих векторів вимірювань.
Рішення завдання попередньої обробки зображення, виділення ознак і завдання отримання оптимального рішення і класифікації зазвичай пов'язане з необхідністю провести оцінку ряду параметрів. Це призводить до задачі оцінки параметрів. Крім того, очевидно, що виділення ознак може використовувати додаткову інформацію виходячи з природи класів.
Порівняння об'єктів можна виробляти на основі їх подання у вигляді векторів вимірювань. Дані вимірювань зручно представляти у вигляді дійсних чисел. Тоді схожість векторів ознак двох об'єктів може бути описано за допомогою евклидова відстані.
де d - розмірність вектора ознаки.
Розділяють 3 групи методів розпізнавання образів:
- Порівняння із зразком. У цю групу входить класифікація по найближчому середньому, класифікація по відстані до найближчого сусіда. Також в групу порівняння зі зразком можна віднести структурні методи розпізнавання.
- Статистичні методи. Як видно з назви, статистичні методи використовують деяку статистичну інформацію при вирішенні задачі розпізнавання. Метод визначає приналежність об'єкта до конкретного класу на основі ймовірності В ряді випадків це зводиться до визначення апостеріорної ймовірності приналежності об'єкта до певного класу, за умови, що ознаки цього об'єкта взяли відповідні значення. Прикладом служить метод на основі байєсівського вирішального правила.
- Нейронні мережі. Окремий клас методів розпізнавання. Відмінною особливістю від інших є здатність навчатися.
Далі розглянемо різні методи відносяться до різних груп.
Класифікація по найближчому середнього значення
У класичному підході розпізнавання образів, в якому невідомий об'єкт для класифікації представляється у вигляді вектора елементарних ознак. Система розпізнавання на основі ознак може бути розроблена різними способами. Ці вектори можуть бути відомі системі заздалегідь в результаті навчання або передбачені в режимі реального часу на основі будь-яких моделей.
Простий алгоритм класифікації полягає в угрупованні еталонних даних класу з використанням вектора математичного очікування класу (середнього значення).
де x_ (i, j) - j-й еталонний ознака класу i, n_j- кількість еталонних векторів класу i.
Тоді невідомий об'єкт буде ставитися до класу i, якщо він істотно ближче до вектору математичного очікування класу i, ніж до векторів математичних очікувань інших класів. Цей метод підходить для задач, в яких точки кожного класу розташовуються компактно і далеко від точок інших класів.
Труднощі виникнуть, якщо класи матимуть дещо складнішу структуру, наприклад, як на малюнку. В даному випадку клас 2 розділений на два непересічних ділянки, які погано описуються одним середнім значенням. Також клас 3 занадто витягнуть, зразки 3-го класу з великими значеннями координат x_2 ближче до середнього значення 1-го класу, ніж 3-го.
Описана проблема в деяких випадках може бути вирішена зміною розрахунку відстані.
Будемо враховувати характеристику «розкиду» значень класу - σ_i, уздовж кожного координатного напрямку i. Середньоквадратичне відхилення дорівнює квадратному кореню з дисперсії. Шкалірованние евклідова відстань між вектором x і вектором математичного очікування x_c одно
Ця формула відстані зменшить кількість помилок класифікації, але на ділі більшість завдань не вдається уявити таким простим класом.
Класифікація по відстані до найближчого сусіда
Інший підхід при класифікації полягає у віднесенні невідомого вектора ознак x до того класу, до окремого зразком якого цей вектор найбільш близький. Це правило називається правилом найближчого сусіда. Класифікація по найближчому сусіду може бути більш ефективна, навіть якщо класи мають складну структуру або коли класи перетинаються.
При такому підході не потрібно припущень про моделях розподілу векторів ознак в просторі. Алгоритм використовує тільки інформацію про відомих еталонних зразках. Метод рішення заснований на обчисленні відстані x до кожного зразка в базі даних і знаходження мінімальної відстані. Переваги такого підходу очевидні:
- в будь-який момент можна додати нові зразки в базу даних;
- деревовидні і сіткові структури даних дозволяють скоротити кількість обчислюваних відстаней.
Крім того, рішення буде краще, якщо шукати в базі не одного найближчого сусіда, а k. Тоді при k> 1 забезпечує найкращу вибірку розподілу векторів в d-вимірному просторі. Однак ефективне використання значень k залежить від того, чи є достатня кількість в кожній області простору. Якщо є більше двох класів то прийняти вірне рішення виявляється складніше.