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

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

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

Замість терміна “розпізнавання” часто використовують термін – “класифікація”. Наведемо деякі типові постановки задач класифікації.

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

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

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

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

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

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

1) Розпізнавання літер. Окрім усього іншого, ця проблема має велике значення для власне комп’ютерних технологій. Системи розпізнавання літер працюють разом зі сканерами-пристроями, використовуваними для введення у комп’ютер друкованих зображень і текстів. При введенні друкованого тексту сканер формує лише графічне зображення; для того щоб створити текстовий документ, з яким може працювати текстовий редактор, необхідно впізнати на цьому зображенні окремі літери. Аналогічно розпізнавання літер є необхідним для підтримки пристроїв рукописного введення. Цими пристроями, зовні схожими на звичайну авторучку, часто комплектуються надпортативні комп’ютери (персональні помічники). Основна мета цих пристроїв – замінити введення з клавіатури, що є незручним для багатьох користувачів, розпізнаванням літер і цифр з метою введення даних в ЕОМ.

2) Розпізнавання мови. На теперішній час інтенсивно розвиваються технології, пов’язані, по-перше, з голосовим керуванням комп’ютером; по-друге – з введенням текстів “з голосу” з метою введення даних в ЕОМ або управління системою розпізнавання фраз або слів в тексті, написаному формальною або природною мовою.

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

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

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

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

7) Автоматична класифікація живих клітин, наприклад кров'яних тілець, спостережуваних під мікроскопом.

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

9) Розпізнавання алгебри, виразів певних типів при виконанні формальних перетворень над формулами за допомогою ЕОМ.

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

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

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

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

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

Класифікація систем розпізнавання грунтується на використанні як класифікаційний принцип властивості інформації, використовуваної в процесі розпізнавання. Можлива класифікація систем розпізнавання показана на рис. 5.2.

Рис. 5.2. Класифікація систем розпізнавання

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

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

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

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

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

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

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

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

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

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

8) Детерміновані системи. У цих системах для побудови алгоритмів розпізнавання використовують “геометричні” заходи близькості, засновані на вимірюванні відстаней між розпізнаваним об'єктом і еталонами класів. У загальному випадку застосування детермінованих методів розпізнавання передбачає наявність координат еталонів класів в признаковому просторі або координат об'єктів, належних відповідним класам.

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

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

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

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

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

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

13) Комбіновані системи. У цих системах для побудови алгоритмів розпізнавання використовується спеціально розроблений метод обчислення оцінок. Такі алгоритми розпізнавання називають “алгоритмами обчислення оцінок” (АОО). Їх застосування вимагає наявності таблиць, де містяться об'єкти, належні відповідним класам, а також значення ознак, якими характеризуються ці об'єкти. Ознаки можуть бути детермінованими, логічними, ймовірнісними, структурними.

У кожному завданні розпізнавання початковими даними є результати деяких спостережень або безпосередніх вимірювань. Їх називають “первинними ознаками”, а сукупність всіх первинних ознак – “вхідним сигналом”.

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

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

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

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

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

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

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

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

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

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

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

Класифікація основних методів розпізнавання

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Рис. 5.3. Розпізнавання в просторі ознак

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

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

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

Виділяють різні типи ознак: дихотомічні (ознака може бути присутня або відсутня; наприклад, є крила або немає крил); номінальні (наприклад, колір: червоний, синій, зелений і т.п.); порядкові (наприклад, “великий” – “середній” – “маленький”); кількісні. Для кожного типу ознак можна вводити свої міри відстані між об’єктами.

Існують спеціальні методики, які дозволяють здійснювати перехід від некількісних типів ознак до кількісних.

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

Будь-який об’єкт при застосуванні дискримінантних методів розпізнавання зображається вектором ознак у деякому n -вимірному просторі, де n – кількість ознак. Таким чином, будь-якому об’єктові відповідає n –вектор: x = (x j; j = 1,…,n);

де x j – значення j –ї ознаки.

Навчальну вибірку прийнято позначати у вигляді спеціальної матриці, яку часто називають матрицею даних: Y=(yij; i =1,…,q; j = 1, …, n+1),

де q – загальна кількість представників усіх класів;

n – кількість ознак; yij (j = 1, …, n) – значення j- ї ознаки для i -го об’єкта; yi, n+1 – клас, до якого належить i - й об’єкт.

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

Термін “компактний ” тут використовується у дещо незвичному значенні. Компактною у даному розумінні називається множина точок, для якої:

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

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

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

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

Отже, нехай маємо два класи: К1 і К2. Нехай довільний вектор x описується своїми координатами: x = (x1,..., xn). Отже функція g(x) розділяє ці класи, або є розділяючою функцією, якщо для всіх векторів класу К1 g(x) > 0, адля всіх векторів класу К2 g(x) < 0.

Побудова і використання розділяючих функцій є основою багатьох методів розпізнавання. Насправді в робочому режимі, як правило, не можна знати заздалегідь, до якого класу належить даний об’єкт (саме це і потрібно визначити). Натомість, якщо є деяка розділяюча функція, що є наближенням до справжньої розділяючої функції, можна на основі її аналізування прийняти певне рішення, а саме: рішення про належність вектора x класові К1, якщо g(x) > 0, і класові К2, якщо g(x) < 0. Це рішення може, взагалі кажучи, бути помилковим. Таким чином, метою навчання має бути отримання справжньої розділяючої функції, якщо вона існує, або побудова деякої наближеної розділяючої функції – в іншому разі. Саме такий зміст будемо надалі вкладати в поняття “розділяюча функція”.

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

g(x) = w1x1+ … + wnxn+ wn+1; коефіцієнти wi повинні бути визначені в процесі навчання.

Одним з найпростіших методів підбору параметрів є алгоритм персептрона. Алгоритм названий так через свій тісний зв’язок з навчанням персептронів.

Алгоритм полягає в наступному. Задається початковий вектор параметрів w(0), який уточнюється по мірі розпізнавання елементів навчальної вибірки. Правила уточнення наступні:

- якщо черговий елемент навчальної вибірки x(i) належить К1, а g(x) £ 0, то

w(i+1):= w(i) + c x(i); c >0;

- якщо черговий елемент навчальної вибірки x(i) належить К2, а g(x) ³ 0, то

w(i+1):= w(i) – c x(i); c >0;

У разі лінійної роздільності алгоритм збігається.

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

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

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

а) б)

Рис 5.4. Лінійна роздільність класів

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

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

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

У разі (рис. 5.5, а) надійно виокремити один клас від другого не вдається, і це значно збільшує кількість помилок при проведенні розпізнавання.

а) б)

Рис. 5.5. Класи частково або повністю перекриваються

У разі (рис. 5.5, б) не про яке розпізнавання в такому просторі ознак судити, очевидно, не доводиться.

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

На рис. 5.6 показана така персептронна конфігурація розпізнавання літер. Допустимо, що вектор Х є розпізнавальним образом літери. Кожна компонента (квадрат) Х – (x ₁, x ₂,., x_n) множиться на відповідну компоненту вектора вагів W – (w ₁, w ₂,..., w_n). Цей добуток підсумовуються. Якщо сума перевищує поріг, то вихід нейрона Y рівний одиниці (індикатор світиться), інакше – нуль. Ця операція компактно записується у векторній формі як: Y = XW, а потім слідує порогова операція.

Рис. 5.6. Персептронна система розпізнавання зображень

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

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

Для побудови системи розпізнавання образів можно використати алгоритм Isodata (Iterative Self-Organizing Data Analysis, Ітеративний аналіз даних, що самоорганізується) є цілком визначеною, гнучкою послідовністю операцій. Їх ітеративне виконання призводить до того, що основні елементи класифікації виробляються безпосередньо в процесі роботи. Зокрема, це належить і до ядер, кількість яких апріорі не була визначена. Алгоритм складається з наступних етапів. Початкове розташування центрів вибирають довільно. Досвід показує, що остаточний результат майже не залежить від первинного вибору. Визначають області, в які входять точки, близькі (у евклідовому геометричному сенсі) до початкових центрів.

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

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

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

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

Крок 1. Задаються параметри, що визначають процес кластеризації:

К – необхідна кількість кластерів;

– параметр, з яким порівнюється кількість вибіркових образів, що ввійшли в кластер;

– параметр, що характеризує середнєквадратичне відхилення;

– параметр, що характеризує компактність;

– максимальна кількість пар центрів кластерів, які можна об’єднати;

– допустима кількість циклів та ітерацій.

Крок 2. Задані N образів розподіляються по кластерах, що відповідають вибраним початковим цетрам за правилами:

якщо i=1,2,..., N_c,

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

Крок 4. Кожен центр кластера , ..., N_c, локалізується і коригується:

j=1,2,...,N_c

де – число об’єктів, що ввійшли до підмножини S_j.

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

, j=1,2,..., .

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

Крок 7.

а) Якщо біжучий цикл ітерації – останній, то задається ; перехід до кроку 10.

б) Якщо умова виконуєтьяс то перехід до кроку 8.

в) Якщо біжучий цикл ітерацій має перший порядковий номер або виконується умова , то перехід до кроку 11; інакше крок 8.

Крок 8. Для кожної підмножини вибіркових образів за допомогою співвідношення

, і=1,2,..., n; j=1,2,...,

вираховується вектор середнєквадратичного відхилення:

,

де n – розмірність образа;

Х_ik – -та компонента к -го об’єкта підмножини;

S_j, Z_ij – -та компонента вектора, що представляє центр кластера;

Z_j, N_j – кількість вибіркових образів, включених до підмножини S_j.

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

Крок 9. В кожному векторі середнєквадратичного відхилення , j=1,2,...,N_c, виконуються умови _мах > і а) або б) , то кластер з центром Z_j розщеплюється на два повних кластера з центрами і відповідно, кластера із центром ліквідується, а значення збільшується на 1. Для визначення центру кластера до компоненти вектора , що відповідає максимальній компоненті вектора , додається задана величина ; центр кластера визначається відніманням цієї ж величини із цієї компоненти вектора Z:

Крок 10. Якщо розщеплення відбувається на даному кроці, то перейти на крок 2, інакше крок 10.

Крок 11. Вираховуються відстані між усіма парами центрів кластерів:

Крок 12. Відстані порівнюються з параметрами . Ті з відстаней, які виявилися меншими за , ранжуються в порядку зростання

.

Причому , а L – максимальна кількість пар центрів кластерів, які можна об’єднати.

Крок 13. Кожна відстань Dieje вирахувано для певної пари кластерів із центрами Z_il, Z_jl. До цих пар послідовності, що відповідає збільшенню відстані між центрами, застосовується процедура злиття:

кластери з центрами Z_il і Z_jl, l=1,2,...,L, об’єднуються (за умови, що в біжучому циклі ітерації процедура злиття не застосовувалася ні до того, ні до другого кластера), причому новий центр кластера визначається за формулою:

Центри кластерів Z_il, Z_jl ліквідуються, і значення N_c зменшується на 1.

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

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

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

Рис. 5.7. Приклад розпізнавання відбитка пальців алгоритмом Isodata по п’яти кластерних образах

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

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