Спосіб розпізнавання об’єктів

Реферат: UA 96379 U UA 96379 U 5 10 15 20 25 30 Корисна модель належить до галузі обчислювальної техніки й інформаційних технологій, зокрема до способів розпізнавання об'єктів, образи яких можуть бути описані набором логічних ознак. Корисна модель може бути використана для автоматизації процесу розпізнавання образів у широкому спектрі прикладних областей, зокрема розпізнаванні зорових і мовних образів, робототехніці, системах штучного інтелекту, медичній діагностиці, екологічному, геологічному й іншому видах моніторингу. У даний час відомо багато різних способів розпізнавання образів, пов'язаних з формуванням на основі навчального набору вирішальних правил, що дозволяють виконати віднесення невідомого об'єкта до одного з класів прийнятого алфавіту. Відомий підхід до вирішення задач класифікації й розпізнавання, заснований на посиленні простих класифікаторів, шляхом їхнього комбінування в один сильний. Даний підхід поєднує сімейство алгоритмів, в основі яких лежить алгоритм AdaBoost [Schapire R.E., Singer Y. "Improved Boosting Algorithms Using Confidence-rated Predictions" //In Proceedings of Machine Learning, 1999. - Р. 297-336; Александр Вежневец, Владимир Вежневец. Boosting - Усиление простых классификаторов. Компьютерная графика и мультимедиа. Випуск №4 (2) / 2006 http://cgm.computergraphics.ru/ content/view/112]. Алгоритм навчання класифікатора заснований на відборі й комбінуванні малоефективних елементарних класифікаторів (або простих ознак розпізнаваних об'єктів) в один, більш ефективний класифікатор, при цьому кожний наступний класифікатор більшою мірою будується за об'єктами, які погано класифікуються на попередніх кроках. На кожній ітерації ваги кожного невірно класифікованого об'єкта зростають, таким чином, наступний класифікатор виконує класифікацію об'єктів, які важко класифікуються попередніми. Комбінування простих класифікаторів відбувається лінійно (складається лінійна комбінація), а рішення приймається залежно від знаку отриманої комбінації. Відомі технічні рішення, які використовують для вирішення задач розпізнавання вищевикладений підхід. Відомий спосіб видалення спотворень на цифрових зображеннях [Патент РФ № 2402070, МПК G06K 9/40, публ. 20.10.2010], що реалізує спосіб класифікації за методом двійкового Real AdaBoost класифікатора, заснованого на посиленні й зваженому голосуванні комітету слабких класифікаторів [Friedman J., Т. Hastie, R. Tibshirani, 2000, "Additive logistic regression: A statistical view of boosting". The Annals of Statistics, 38(2):337-374], застосований до вектора характерних ознак. Функція рішення сформована як зважена сума слабких класифікаторів:   Fx   sign   Wnhn x n  , n 1    35 40 45 50 55 (1) де Ν - довжина лінійної комбінації елементарних класифікаторів; n - номер елемента в лінійній комбінації класифікаторів; wn - вага, що задає "важливість" об'єкта для чергового кроку алгоритму; hn - елементарний класифікатор; хn - вектор ознак об'єкта. Також відома система й спосіб сегментації зображення людини для отримання знімка обличчя [патент US 2010/0158325 ΑΙ, публ. 24.06.2010, МПК G06K9/00]. Дані система й спосіб реалізують спосіб виявлення обличчя на зображенні за допомогою використання посиленого класифікатора, заснованого на Хаар-подібних властивостях [R. Lienhart, A. Kuranov, V. Pisarevsky "Empirical analysis of detection cascades of boosted classifiers for rapid object detection", MRL Technical Report, Intel Labs, May 2002]. Недоліками способів розпізнавання, що використають способи класифікації, засновані на посиленні простих класифікаторів, є: 1. У випадку, якщо деякі об'єкти з навчальної множини є шумовими викидами, відбувається перенавчання класифікатора за рахунок того, що кожний наступний класифікатор настроюється на об'єкти, які погано класифікуються попереднім класифікатором, тобто класифікатор, таким чином, настроюється на шум. 2. Жадібна стратегія послідовного додавання елементарних класифікаторів може приводити до їх неоптимальної й громіздкої комбінації. Перераховані вище недоліки в остаточному підсумку знижують ефективність розпізнавання. Також відомий спосіб логічного розпізнавання об'єктів [патент України №82212 МПК G06K 9/68, публ. 25.03.2008]. Даний спосіб логічного розпізнавання об'єктів полягає у виборі логічних ознак для заданого складу класів об'єктів, у визначенні логічних ознак невідомого 1 UA 96379 U 5 10 15 20 25 30 35 40 45 50 55 60 розпізнаваного об'єкта, причому для визначення логічних ознак використовують інформацію фізичних вимірників і їхніх комбінацій. У відомому способі виділені специфічні логічні ознаки включають в n-мірні логічні породжувальні вектори класів, для кожної логічної ознаки визначають імовірності пропуску виявлення й помилкового виявлення й відповідні ймовірності допустимих q-ознакових інверсій породжувальних векторів. Таке розміщення ознак забезпечує повне початкове відокремлення відповідних векторів у просторі ознак, що представляється для логічного опису одиничним гіперкубом. Автоматично генерують вектори логічних ознак повних описів класів, цей склад логічних векторів відповідає всім вершинам одиничного гіперкуба, що представляє собою простір логічних ознак. Розпізнавання невідомого об'єкта виконується відповідно до вибраних вирішальних правил. Недоліками способу є: евристичний характер вибору логічних ознак, що ускладнює рішення завдання побудови системи розпізнавання образів у випадках значної внутрішньокласової мінливості об'єктів класифікації й випадках, коли неможливо евристично визначити породжувальні вектори через складність розпізнаваних класів, що часто зустрічається при розробці систем розпізнавання зорових образів. Формування ознакових описів класів здійснюється за допомогою q-ознакових інверсій породжувальних векторів класів. Це призводить до істотного збільшення обчислювальної складності процесу класифікації у випадках складних класів, представлених наборами породжувальних векторів, що знижує ефективність розпізнавання через недостатньо повний опис складного класу одним породжувальним вектором. Найбільш близьким до способу розпізнавання об'єктів, що заявляється, за технічною сутністю й результатом, що досягається, є спосіб для ідентифікації людей за допомогою декількох типів вводу [патент US 2007/0297682 ΑΙ, МПК G06K 9/46, G06K 9/62, публ. 27.12.2007]. У даному способі приймають вхідні дані, ідентифікують пул ознак і формують класифікатор за допомогою алгоритму навчання, при цьому вузли класифікатора обираються з пула ознак, а алгоритм навчання містить алгоритм AdaBoost. Пул ознак являє собою тимчасовий набір ознак декількох типів вводу й містить у собі аудіоознаку, асоціативно зв'язану з вводом з локалізацією джерела звуку, і відеоознаку, що задається за допомогою прямокутника, також він може включати й інші типи ознак. Відомий спосіб не може бути ефективно використаний для розпізнавання складних класів у різних предметних областях. Класифікатор, що формується за допомогою алгоритму AdaBoost, є громіздким, що призводить до збільшення обчислювальної складності процесу класифікації, а також використовуваний лінійний механізм об'єднання простих класифікаторів недостатньо повно характеризує положення об'єктів у просторі ознак, що впливає на якість класифікації й знижує ефективність розпізнавання. В основу корисної моделі, що заявляється, поставлена задача створення способу розпізнавання об'єктів, що має підвищену ефективність розпізнавання складних класів у різних предметних областях. Поставлена задача вирішується тим, що в способі розпізнавання об'єктів, що полягає в прийомі вхідних даних, формуванні класифікатора за допомогою алгоритму навчання, додатково при навчанні здійснюють вибір системи логічних ознак для заданого алфавіту класів вхідних об'єктів, у класифікатор, що навчають, послідовно додають логічні ознаки, які максимально зменшують помилку класифікації об'єктів у вершинах одиничного гіперкубу; для кожної вершини визначають номер класу, що відповідає мінімальній помилці класифікації; формують класифікатор у вигляді наборів значень логічних ознак і номерів класів, яким вони відповідають; при розпізнаванні невідомого об'єкта обчислюють набір значень логічних ознак, отриманих у результаті навчання; невідомому об'єкта привласнюють номер класу, що відповідає отриманим значенням логічних ознак. Крім цього при розпізнаванні навчений класифікатор представляють у вигляді дерева рішень. Порівняльний аналіз заявленого способу й способу-прототипу показує, що спосіб, що заявляється, відрізняється від прототипу сукупністю відмітних ознак. Це дозволяє зробити висновок про відповідність способу, що заявляється, критерію "новизна". Сукупність відмітних ознак способу розпізнавання об'єктів, що заявляється, порівняно з відомими технічними рішеннями аналогічного призначення дозволяє способу, що заявляється, проявляти такі властивості: - навчальний набір, що використовується для формування класифікатора, обробляється автоматично, що не вимагає використання евристичних знань про об'єкти розпізнавання для формування ознакових описів класів; - класифікатор формується на основі аналізу найбільш повного опису положення об'єктів класів у просторі логічних ознак у вигляді одиничного гіперкуба, без яких-небудь припущень про 2 UA 96379 U 5 10 15 20 25 30 35 вид поверхні, яка розділяє класи, що дозволяє описувати й розпізнавати об'єкти класів будьякої складності; - процедура послідовного додавання в класифікатор логічних ознак дозволяє сформувати компактний опис розташування класів у просторі ознак за рахунок включення в класифікатор на кожному етапі додавання такої логічної ознаки, що у сукупності з вже включеними в класифікатор логічними ознаками максимально зменшує помилку класифікації об'єктів у вершинах одиничного гіперкубу і, як наслідок, мінімізує перетинання об'єктів різних класів у вершинах породжувального логічними ознаками одиничного гіперкуба, що збільшує ефективність розпізнавання об'єктів; - обчислювальна складність процесу класифікації відповідає кількості операцій порівняння кодів рівному числу використовуваних логічних ознак, при поданні класифікатора у вигляді дерева рішень. Це позитивно позначається на швидкодії способу розпізнавання об'єктів, що заявляється, і може розглядатися як додатковий технічний результат. Таким чином, сукупність відмітних ознак забезпечує підвищену ефективність розпізнавання складних класів у різних предметних областях, а також швидкодію при використанні технічного рішення, що заявляється. Для розкриття суті способу розпізнавання об'єктів використані графічні матеріали. На фіг. 1 наведений загальний вигляд логічних ознак, що використані для розпізнавання зображень об'єктів. На фіг. 2 наведена схема алгоритму навчання класифікатора. На фіг. 3 наведений приклад отриманого після навчання класифікатора, представленого у вигляді дерева рішень. На фіг. 4 наведені зображення символів автомобільного номерного знаку. На фіг. 5 наведений графік залежності помилки класифікації від кількості властивостей, отриманий у процесі навчання класифікатора. Особливості способу, що заявляється, полягають у наступному. При навчанні здійснюють вибір системи логічних ознак для заданого алфавіту класів вхідних об'єктів. Як вхідні дані для навчання класифікаторів у способі, що заявляється, використовується кінцева множина навчальних об'єктів із заданого алфавіту класів із вказівкою їхньої класової приналежності й завдання системи використовуваних логічних ознак, що приймають для кожного конкретного об'єкта два значення, наприклад, 0 або 1. Зазначена система логічних ознак може бути задана кінцевим набором логічних ознак, наприклад, вказівкою способу їхнього отримання. Перетворення вхідних даних у значення ознак може бути зроблено будь-яким відомим способом. Наприклад, це може бути гранична обробка дійсного результату виміру ознаки або результат математичних дій над вхідними даними. Так, для розпізнавання зображень об'єктів як логічні ознаки можуть бути використані Хаарподібні властивості, загальний вигляд яких наведений на фіг. 1. Довільне розташування чорної та білої областей (див. фіг. 1) задає систему ознак, що використовуються для розпізнавання. Значення ознаки для конкретного зображення можна обчислити на основі таких виразів: 40  SБ SЧ 1,    ;  Б Ч R SБ SЧ  0,  .  Б Ч  (1) у випадку областей, що не перетинаються (див. фіг. 1а), і SЧ  SЧБ  SБ ; 1,       Б Ч ЧБ R S S  SЧБ 0, Б  Ч .   Б  Ч   ЧБ  45 50 (2) у випадку перетинання областей (див. фіг. 1б). Де індекси Ч і Б означають чорну й білу області відповідно, а ЧБ - позначає область перетинання областей чорного та білого кольору; S - сума яскравостей пікселів зображення, що перебувають під областю; N - кількість пікселів зображення, що перебувають під областю. Навчання класифікації відбувається шляхом послідовного включення в класифікатор логічних ознак і перевірки одержуваної в результаті включення помилки класифікації на 3 UA 96379 U навчальному наборі вхідних даних. Якщо позначити функцію класифікатора, що повертає номер класу для довільного вхідного об'єкта х як h(x), а його класову приналежність (правильний номер) як у, то для розрахунку помилки класифікації використається вираз:  1   Si, де  і 1  1, h x i  y i ,  Si    o, інакше .  (3) 5 10 15 20 де N - кількість навчальних об'єктів. Навчання класифікатора можна представити у вигляді такої послідовності дій (фіг. 2). 1. Задається умова виходу із циклу навчання. Це може бути: - кількість включених ознак більше Т, де Τ - обмеження на кількість використовуваних логічних ознак; - помилка класифікації менше Е, де Ε - обмеження зверху припустимої помилки класифікації; - значення Etest перестало зменшуватися з ростом кількості включених ознак, де Etest значення помилки класифікації на тестовому наборі вхідних даних. 2. Вибирається перша ознака з кінцевого набору, що дає мінімальну помилку класифікації (3) і включається в класифікатор, що навчають (t=1). 3. Для кожного наступного кроку навчання t=2,…,T: 3.1) організовується цикл додавання тимчасової t-ϊ ознаки до вже включених t-Ι ознак у класифікатор, що навчають; 3.1.1) розраховується помилка класифікації (3) після додавання нової t-ϊ ознаки: 3.1.1.1) всі об'єкти навчального набору розташовуються у вершинах t-мірного гіперкуба, тому що для кожної з них t ознак приймають конкретні значення; 3.1.1.2) для кожної вершини (і) розраховується відносна частота попадання в неї навчальних вхідних об'єктів кожного класу, відповідно до виразу: 25 ki  30 35 40 45  ki k (4) де Рki - відносна частота потрапляння у вершину (і) навчальних вхідних об'єктів класу з номером k, Nki - кількість навчальних вхідних об'єктів класу з номером k, які потрапили у вершину (і), Nk - кількість навчальних вхідних об'єктів класу з номером k; 3.1.1.3) кожна вершина, у яку потрапив хоча б один об'єкт навчального набору, наділяється номером того класу, відносна частота потрапляння (4) об'єктів якого в дану вершину найбільша порівняно з іншими класами; 3.1.1.4) відповідно до призначених номерів класів у вершинах розраховується помилка класифікації для всього навчального набору на основі формули (3); 3.1.2) зберігаються параметри доданої тимчасової ознаки, після додавання якої помилка класифікації класифікатора, що навчають, менша зі всіх отриманих; 3.1.3) додана тимчасова ознака видаляється з класифікатора, що навчається, залишаються t-Ι вже включених ознак. 3.2) Вибирається ознака, яка при додаванні в класифікатор, що навчають, дає мінімальну помилку класифікації, і включається в класифікатор. 3.3) Перевіряється умова виходу із циклу додавання нових ознак, обумовлена в пункті 1). Якщо умова виконана, процес навчання закінчується. Формується класифікатор. Після навчання класифікатора об'єкти всього навчального набору внаслідок бінарності значень кожної ознаки, включеної в класифікатор, розподіляються по вершинах одиничного гіперкубу розмірності Т-числа ознак. Кожній не порожній вершині відповідає набір конкретних значень, прийнятих набором логічних ознак, включених у класифікатор, і номер класу, привласнений вершині в ході процесу навчання. Сформований класифікатор може бути представлений у вигляді таблиці, наприклад показаний у таблиці 1. 4 UA 96379 U Таблиця 1 № ознаки 1 2 3 • • • Τ-1 Т Номер класу вершини 5 10 15 20 25 30 35 40 45 Вершина 1 0 1 0 • • • 1 0 1 Значення ознак у непустих вершинах гіперкуба Вершина 2 Вершина 3 Вершина 4 ••• Вершина N 1 0 0 ••• 0 1 0 1 ••• 0 0 0 0 •••· 0 • • • • • • • • • • • • • • • 1 0 1 ••• 0 0 1 0 ••• 1 2 3 1 ••• 3 При розпізнаванні невідомого об'єкта обчислюють набір з Τ значень логічних ознак, отриманих у результаті навчання. Знаходять вершину багатовимірного гіперкуба, яка відповідає отриманому набору значень ознак. Невідомому об'єкта привласнюють номер класу, що відповідає знайденій вершині багатовимірного гіперкуба. Наприклад, у ході обчислення для невідомого об'єкта отримано набір значень логічних ознак 110-10), що відповідає вершині № 2 (Таблиця 1). Відповідно до знайденої вершини, невідомий об'єкт відносять до класу 2. На основі даних (Таблиця 1), отриманих після навчання класифікатора, будується дерево рішень, що дозволяє прискорити процес розпізнавання. Кожний стовпець таблиці 1 являє собою гілку дерева рішень від кореня до листа, кожному листу дерева рішень відповідає номер класу. У цьому випадку процес класифікації являє собою послідовне отримання для вхідного об'єкта впорядкованого набору значень логічних ознак і залежно від прийнятих ними значень просування від кореня дерева до листів зверху вниз, як показано на фіг. 2. Після отримання для вхідного об'єкта значення останньої логічної ознаки прохід по дереву закінчується в одному з листів, номер класу якого приймається як результат розпізнавання. Якщо прохід по дереву не приводить до жодного з листів, то генерується подія "Відмова від розпізнавання", що відповідає тому, що розпізнаваний об'єкт не потрапляє в жодну з непустих вершин гіперкуба, для яких призначений номер класу. Подання класифікатора у вигляді дерева рішень збільшує обчислювальну ефективність способу розпізнавання об'єктів, що заявляється. Формування класифікатора на основі аналізу найбільш повного опису положення об'єктів класів у просторі логічних ознак у вигляді одиничного гіперкуба, без яких-небудь допущень про вид поділяючої класи поверхні, дозволяє описувати й розпізнавати об'єкти класів будь-якої складності, а також, урахувати внутрішньокласову мінливість об'єктів розпізнавання за рахунок повного логічного опису розташування навчальних об'єктів у вершинах одиничного гіперкуба. Це забезпечує ефективне використання способу, що заявляється, для розпізнавання складних класів у різних предметних областях. Розглянемо один із прикладів реалізації способу розпізнавання об'єктів, що заявляється, за допомогою комп'ютерної системи розпізнавання символів автомобільного номерного знака. Вихідні дані для навчання й розпізнавання являли собою зображення цифр, отримані шляхом автоматичної сегментації символів на номері (див. фіг. 4). Загальна кількість зображень цифр дорівнювала 4300, серед яких кожна із цифр зустрічалася приблизно з однаковою частотою. Як ознаки зображення, застосовані для класифікації, використовувалися Хаар-подібні логічні властивості, вигляд яких наведений на фіг. 1. Набори зображень кожної цифри були розділені на рівні частини, одна з яких використовувалася для навчання, друга - для тестування навченого класифікатора, який автор надалі позначає як МКВ-класифікатор. Навчання класифікатора, що відповідає способу, який заявляється, виконувалося шляхом мінімізації сумарної помилки класифікації відповідно до алгоритму навчання, наведеного вище. Умовою виходу із циклу навчання було досягнення середньої помилки по всіх класах менш 0,01 (1 %). Вершини одиничного гіперкуба наділялися номером класу, відносна частота потрапляння об'єктів якого в дану вершину була найбільша порівняно з іншими класами. У ході навчання був побудований деревоподібний МКВ-класифікатор, який використовує 8 прямокутних властивостей, що мають різне розташування чорної й білої частини. Графік залежності помилки від кількості використовуваних властивостей, отриманий у ході навчання, наведений на фіг. 5. 5 UA 96379 U 5 Після навчання кількість вершин гіперкуба, у які потрапляли навчальні об'єкти і які отримали номер класу, дорівнювала 136 (з 256). При тестуванні класифікатора на навчальному наборі була отримана матриця прийнятих рішень, наведена в таблиці 2. У таблиці 2 рядкам відповідають класи, що подаються на вхід класифікатору, стовпцям ухвалені рішення. Діагональні елементи відповідають відносним частотам прийняття правильних класифікуючих рішень. Таблиця 2 Класи 0 1 2 3 4 5 6 7 8 9 10 0 1 0 0 0 0 0 0 0,004 0 0 1 0 0,99 0 0 0 0 0 0 0 0,005 2 0 0 0,986 0,005 0 0 0 0,004 0 0 3 0 0 0 0,976 0 0,005 0 0 0 0 4 0 0,005 0 0 1 0 0,006 0 0 0 5 0 0 0 0,005 0 0,995 0 0 0 0,01 6 0 0 0,005 0 0 0 0,994 0 0,009 0 7 0 0 0,009 0,015 0 0 0 0,991 0 0 8 0 0 0 0 0 0 0 0 0,991 0,01 9 0 0,005 0 0 0 0 0 0 0 0,976 Для виконання розпізнавання з застосуванням отриманого деревоподібного МКВкласифікатора був використаний тестовий набір зображень символів автомобільного номера, що не перетинається з навчальним набором. У таблиці 3 наведена матриця ухвалених рішень розпізнавання невідомих об'єктів, що отримана в ході проведеного тестування. Таблиця 3 Класи 0 1 2 3 4 5 6 7 8 9 15 20 25 0 0,988 0,029 0,019 0,024 0,016 0,014 0,025 0,018 0,026 0 1 0,006 0,951 0 0,005 0,005 0 0 0,018 0 0,024 2 0,003 0 0,92 0,005 0 0 0 0,004 0 0 3 0 0,005 0,005 0,941 0 0,024 0 0,009 0,009 0 4 0 0,005 0 0 0,974 0,005 0,019 0 0 0 5 0 0,005 0 0,01 0 0,948 0 0 0,018 0,019 6 0 0 0,009 0 0 0 0,944 0 0,004 0 7 0 0 0,042 0,015 0 0 0 0,952 0 0 8 0,003 0 0,005 0 0,005 0,009 0,012 0 0,939 0,01 9 0 0,005 0 0 0 0 0 0 0,004 0,947 Наведені результати говорять про досягнення в ході навчання високої ефективності класифікатора й досить високі характеристики узагальнення класових особливостей по навчальному набору. Використання восьми властивостей дозволило одержати відсоток правильного розпізнавання в середньому по всіх класах - 95 %. Таким чином, спосіб, що заявляється, у представленій сукупності відмітних ознак при використанні забезпечує високу ефективність розпізнавання складних класів у різних предметних областях і має високу швидкодію. Наведений приклад підтвердив можливість успішного використання способу розпізнавання об'єктів, що заявляється, для вирішення прикладних завдань, зокрема, розпізнавання зображень, що дає підстави зробити висновок про його відповідність критерію "промислова застосовність". ФОРМУЛА КОРИСНОЇ МОДЕЛІ 30 1. Спосіб розпізнавання об'єктів, що полягає в прийомі вхідних даних, формуванні класифікатора за допомогою алгоритму навчання, який відрізняється тим, що при навчанні здійснюють вибір системи логічних ознак для заданого алфавіту класів вхідних об'єктів, у класифікатор, що навчають, послідовно додають логічні ознаки, які максимально зменшують помилку класифікації об'єктів у вершинах одиничного гіперкуба, для кожної вершини 6 UA 96379 U 5 визначають номер класу, що відповідає мінімальній помилці класифікації,формують класифікатор у вигляді наборів значень логічних ознак і номерів класів, яким вони відповідають, при розпізнаванні невідомого об'єкта обчислюють набір значень логічних ознак, отриманих у результаті навчання, невідомому об'єкту привласнюють номер класу, що відповідає отриманим значенням логічних ознак. 2. Спосіб за п.1, який відрізняється тим, що при розпізнаванні навчений класифікатор представляють у вигляді дерева рішень. 7 UA 96379 U 8 UA 96379 U Комп’ютерна верстка М. Мацело Державна служба інтелектуальної власності України, вул. Урицького, 45, м. Київ, МСП, 03680, Україна ДП “Український інститут промислової власності”, вул. Глазунова, 1, м. Київ – 42, 01601 9