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

Анотація наукової статті з комп'ютерних та інформаційних наук, автор наукової роботи - Гороховатський Володимир Олексійович, Передрій Олена Олегівна


The results of application of voting procedures in correlation methods of image recognition are shown. The ways of systems of fragments construction are studied. The recognition problem is formalized. The variety of voting procedures, the ways of choosing fragment characteristics and the estab-lishment of the conformity between them are analyzed. The efficiency of the suggested approach is experimentally.


Область наук:

  • Комп'ютер та інформатика

  • Рік видавництва: 2009


    Журнал: Радіоелектроніка, інформатика, управління


    Наукова стаття на тему 'Кореляційні методи розпізнавання зображень шляхом голосування систем фрагментів'

    Текст наукової роботи на тему «Кореляційні методи розпізнавання зображень шляхом голосування систем фрагментів»

    ?681.51: 007.5

    В. А. Гороховатський, Е. О. Передрій

    КОРЕЛЯЦІЙНІ МЕТОДИ РОЗПІЗНАВАННЯ ЗОБРАЖЕНЬ ШЛЯХОМ ГОЛОСУВАННЯ СИСТЕМ ФРАГМЕНТІВ

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

    ВСТУП І ПОСТАНОВКА ЗАВДАННЯ

    Кореляційні методи розпізнавання набули популярності в системах комп'ютерного зору через високу надійності, хорошої працездатності в широкому діапазоні зовнішніх умов, а також внаслідок високої перешкодозахищеності щодо адитивного шуму [1, 2]. Кореляційними вважають всі підходи до розпізнавання, так чи інакше засновані на побудові міри схожості В, В0) аналізованого зображення В (х, у) е Ш, (х, у) е П і еталона В0 (х, у) е ШШ0, Ш0 з Ш (Ш - безліч зображень, - безліч еталонів, П - область визначення зображень) і оптимізації її значення на безлічі і на безлічі перетворень д з групи О [3].

    Розробка модифікацій кореляційного підходу привела до появи ряду методів, що володіють поряд зі стійкістю до аддитивним шумів також досить хорошою помехозащищенностью і до дії перешкод локального типу. Цей шлях пов'язаний з аналізом фрагментів П зображення, коли область визначення П представляється у вигляді П = і П. У методі приватних кореляцій [3, 7] при визначенні координат об'єктів передбачається побудова ієрархічної заходи, значення якої обчислюється в два етапи: спочатку для відповідних фрагментів , а потім на основі цього - результуюче схожість.

    Ефективним шляхом встановлення відповідності між множинами фрагментів, апроксимуючими розпізнається об'єкт і еталони, є голосування. Методи голосування набули поширення при розпізнаванні візуальних об'єктів шляхом аналізу безлічі локальних ознак [4, 5]. Це призводить до необхідності здійснити побудова кореляційних методів на основі голосування

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

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

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

    1 ФОРМУВАННЯ СИСТЕМИ

    ФРАГМЕНТІВ

    Фрагментація може бути виконана багатьма способами, що мають свої переваги в певних ситуаціях. У методі приватних кореляцій з метою використання оптимальних відповідностей фрагменти будуються шляхом включення всіх точок об'єкта (рис. 1, а), в той же час в інших ситуаціях в інтерактивному режимі можна побудувати більш просту і часто більш ефективну для цілей розпізнавання систему інформативних фрагментів (рис . 1, б). При автоматичному побудові характерних ознак з урахуванням аналізу можливого руху об'єктів система фрагментів формується шляхом поелементного сканування вікном фіксованих розмірів [2, 7].

    Особливістю застосування голосування в кореляційних методах в порівнянні з ознаковими під-

    Малюнок 1 - Приклади систем фрагментів: а - фіксована, б - довільна

    © Гороховатський В. А., Передрій Е. О. 2009

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

    Нехай еталонні зображення представлені множинами інформативних фрагментів Б0 = {Ь}, i = 1, Sj, Ш0 = {В0}, / е], де] - безліч класів (еталонів), 3 / - кількість фрагментів / -го еталона.

    На просторове розміщення фрагментів різних еталонів в загальному випадку не будемо накладати особливих обмежень. Фрагменти еталонів можуть вибиратися або за допомогою автоматичної процедури шляхом побудови і оптимізації відгуків локальних фільтрів, або випадковим чином, або в інтерактивному режимі. Зокрема, інформативні фрагменти можна відібрати, враховуючи ступінь відмінності їх характеристик для різних еталонів [2].

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

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

    2 ПОБУДОВА МЕТОДІВ ГОЛОСУВАННЯ

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

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

    j * = argmaxmaxy (B (j), Bjg), (1)

    j e J g e G

    де B (j) - система фрагментів, побудована на зображенні B відповідно до фрагментного поданням еталона з класу j, B0g - аналогічна система, отримана на перетвореному під дією геометричного перетворення ідеалі B0.

    В результаті рішення (1) поряд з оцінкою j * параметра класу отримуємо також і значення оцінки g * для параметра перетворення g. З огляду на, що в кореляційних підходах вирішення завдань оптимізації виду (1) здійснюється, як правило, шляхом повного перебору можливих значень параметрів, порядок пошуку максимуму принципового значення не має. Рішення буде аналогічним, якщо в (1) спочатку знайти максимум по змінної j, а потім - по змінної g. У даній роботі для конкретності обмежимося розглядом випадку, коли G є група двовимірних зсувів з безліччю значень в межах поля зору.

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

    4 (i, j) = -р (i, j) = - i) - Ук \, (2)

    k = 1

    де k - номер пікселя зображення всередині фрагмента, K - кількість точок фрагмента, р (i, j) - відстань для пари фрагментів (i, j), а знак мінус

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

    Діапазон зміни значень функції г, /) у вигляді (2) можна вважати відомим в зв'язку з фіксованим діапазоном яскравості зображення. При необхідності цей діапазон можна привести до інтервалу [0, 1].

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

    Спільне голосування. Значення функції.) Визначимо у вигляді

    1 Л

    у (В (/), В0д) = ^ г, /)

    (3)

    1 = 1

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

    Пд (г, / ') =

    1,4д (г, /)>б, 0, 4д (г, /)<е,

    (4)

    де?, д (г, /) - функція відповідності еталону / с урахуванням параметра перетворення д, а значення 8 задає поріг значимості величини?, д (.). Нормировка в співвідношенні (3) забезпечує незалежність значення голосує функції від кількості фрагментів конкретного зразка, якщо величини В / різні. Відповідно до виразом (3) значення функції.) Належать відрізку [0, 1].

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

    Щоб уникнути цих труднощів, на величину максимуму в (1) має бути накладено додаткове обмеження виду

    максимуму необхідно додатково перевіряти умову В (/), В0д)>8т.

    З огляду на, що значення.) Належать відрізку [0, 1], значення порога 8т зі статистичної точки зору при рівноцінних фрагментах має бути вибрано у вигляді 8т = 0, 5, хоча можливі ситуації, коли ступінь довіри задається умовою 8т<0, 5 [1, 3]. У такому випадку рішення може бути прийнято по коаліції найбільш важливих фрагментів.

    Незалежне голосування. Розглянемо тепер систему з з фрагментів, що представляє собою об'єднання множин інформативних фрагментів всіх 1

    класів, з = ^ - кількість фрагментів систе- / = 1

    ми. Побудуємо ідентичну систему з в фрагментів для зображення і еталонів. Окремим випадком є ​​система однакових фрагментів для всіх еталонів, т. Е. Коли вк = В /, до ф /, а координати і розміри фрагментів різних еталонів збігаються. В такому випадку виконано У до в = $ до.

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

    Фд [г] = а ^ та ^ ДС ц).

    1 Е 1

    (6)

    Значення ФД [г] при цьому залежить від параметра д. Потім на отриманому безлічі значень ФД [г] сформуємо розподіл (гістограму) рд [/] голосів, відданих елементами множини {ФД [г]} за кожен з класів

    Рд [/] = # {ЛФЛг] = /},

    (7)

    де символ # позначає потужність (кількість елементів) множини.

    Номер результуючого класу визначимо відповідно до максимумом за параметром д на безлічі отриманих гістограм

    / '* = А ^ тах {рд [/]}

    д е з

    (8)

    Обмеження виду (5) для даного типу голосування має вигляд

    тах {Рд [1]} ^

    д е з '

    (9)

    тахти ^ (В (/), В0д) > 8 "

    1 е 1 д е С

    (5)

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

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

    Принципова відмінність незалежного і спільного видів голосування полягає в тому, що при незалежному голосуванні кожен фрагмент самостоя-

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

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

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

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

    При дотриманні кореляційних принципів обробки реалізація підтримки зводиться до аналізу безлічі фрагментів, в просторовому плані сусідніх з аналізованих. Схематично елементи околиці в сенсі восьмизв'язною можна представити у вигляді рис. 2, де аналізований фрагмент позначений ХП (характерна ознака), а сусідні з ним фрагменти околиці для конкретності викладу пронумеровані числами від 1 до 8.

    У більшості застосувань розмір фрагмента дорівнює 5 х 5. Таким чином, шляхом розширення області побудови і аналізу ознак загальний розмір поля зображення, який бере участь в прийнятті локального рішення, зростає до величини 15 х 15. Схематично представлене на рис. 2 розташування фрагментів-

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

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

    Таким чином, для околиці аналізованого фрагмента з номером г маємо п додаткових фрагментів у вигляді сукупності иг = (ь1, Іоп) г (на рис. 2 п = 8). Безліч фрагментів з околиці відповідного фрагмента / -го зразка, щодо якого приймається локальне рішення, позначимо і / = {Ьу, V = 1, п. Еквівалентність околиць иг, і / може бути встановлена ​​на основі предиката пі [иг, і /], що підтверджує або спростовує локальне рішення за клас з номером /

    | | Г 1,1і (и1, і /)>е ", Пі [и1, і] = \ ^ '/ і (10) 10,4і (иг, і /)<8и,

    де функція?, і (.) характеризує величину подібності (відповідності) двох систем фрагментів иг, і /, а єї -порог значущості подібності.

    У загальному випадку функція ^ і [иг, і /] може бути побудована на основі іншої міри, ніж функція відповідності фрагментів г, /) з виразу (2). З іншого боку, з метою уніфікації можна використовувати і однакові співвідношення, наприклад,

    4и (иг, і) = -? ? \ Ьи (г)

    |Ь {,

    (11)

    Малюнок 2 - Розташування фрагментів підтримки

    де ьи - піксель фрагмента підтримки з номером 1.

    «Повний» набір фрагментів. Всі три розглянутих підходу засновані на частковому поданні у вигляді досить невеликої кількості інформативних фрагментів (5-20). У порівняльному аспекті також становить інтерес підхід, коли прийняття рішення при розпізнаванні спирається на найбільш повну інформацію про зображення, що описується, наприклад, у вигляді повного покриття непересічними фрагментами, як це можна бачити з рис. 1, а. Кількість фрагментів в такому покритті суттєво більше, ніж в інших схемах. Наприклад, при розмірі зображення 100 х 100 і розмірі фрагмента 5 х 5 воно дорівнює 400. Найбільш повне уявлення несе про зображення «скануючий» уявлення [7], коли безліч фрагментів, що застосовуються при розпізнаванні, формується шляхом сканування з кроком в один піксель. Для розглянутих розмірів зображення і фрагмента кількість елементів тако-

    I = 1 к = 1

    го покриття вже становить величину (100 - 5 + 1) = = 9216, що ускладнює реалізацію таких методів в реальному часі, враховуючи багаторазове повторення обчислень в кореляційному підході.

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

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

    Другим важливим аспектом є можливість достроково зупинити процес розпізнавання при досягненні деяких граничних характеристик, заощадивши при цьому на обсязі обчислень. Це можна здійснити в разі, коли набрану кількість голосів, виражене в значенні функції.), Близько до максимально можливого значення. Аналогічну дію можна реалізувати також при обчисленні величин типу (2), (11), враховуючи, що з кожним новим складовою їх значення тільки зменшується [2].

    3 ВИБІР локальних ОЗНАК І ФУНКЦІЇ ВІДПОВІДНОСТІ

    Основним інформаційним критерієм при прийнятті рішень для всіх розглянутих підходів є функції відповідності i, j) і E, U (U1, U), значення яких визначають величини відмінностей фрагментів або околиць. Зрозуміло, що ці функції можна побудувати не тільки на основі кореляційної заходи подібності. Іншими варіантами системи ознак можуть бути наступні.

    1. Інваріантні ознаки фрагментів. Приклади: моментні інваріанти [1], спектральні ознаки [2, 8], локальні потоки [6], масштабно-інваріантне перетворення SIFT [5] та інші.

    2. Статистичні ознаки [4]: ​​математичне сподівання, дисперсія, коваріаційні характеристики, автокореляційна функція фрагмента, гістограма яскравості.

    Для зіставлення в просторах цих ознак використовуються відповідні заходи [2, 4, 7].

    Свої особливості має функція E, U (U1, Uj) по відношенню до i, j). З огляду на основне призначення методів голосування, пов'язане з ефективною можливістю локального аналізу зображення, ви-

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

    Якість розпізнавання запропонованої системи в цілому залежить від наступних факторів: розпізнаються об'єкти (еталони), методи формування ознак, правило прийняття рішення про клас об'єкту (функція відповідності). Запорука успіху - саме в узгодженні цих факторів один з одним. З цієї причини важливим є такий підхід, коли для фіксованого безлічі еталонів та обраної системи ХП заздалегідь оцінюється рівень якості розпізнавання на основі обраної функції відповідності. Це можна здійснити на основі наявної апріорної інформації - еталонів. Наприклад, якщо фрагменти голосують незалежно, критерієм якості може бути величина подібності окремих фрагментів різних класів, а також фрагментів фону. Для випадку спільного голосування критичним може бути максимальну схожість між сумами фрагментів різних класів. Якщо ж рішення будується на відповідності пар фрагментів кожного класу [6], то якість розпізнавання потрібно оцінювати на основі парних співвідношень.

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

    4 ЕКСПЕРИМЕНТИ І ПРАКТИЧНІ

    АСПЕКТИ

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

    Розмір еталонів обраний рівним 100 х 100 пікселів, розмір зображення, за яким здійснювалося сканування і кореляційне зіставлення -125 х 125. Таким чином, загальна кількість варіантів порівняння при оптимізації по параметру д для єдиного зразка одно 676. Як функції відповідності фрагментів взято значення ( 2), а поріг 8 (у відсотках) обраний, виходячи з величини відхилення

    ч:

    го класу, над найближчим за величиною локальним максимумом (тах2) у вигляді

    Малюнок 3 - Еталонні зображення і фрагменти

    Малюнок 4 - Розпізнавані зображення:

    а - на тлі без перешкод, б - під дією локальної перешкоди

    від максимального значення, для заходів (2) і зображення з 256 градаціями рівного 5 х 5 х 255 = 6375. Два фрагмента вважалися еквівалентними, якщо величина їх подібності за метрикою (2) перевищувала граничне значення, рівне -6375е, виражене у відсотках.

    Правило підтвердження голосу полягало в тому, що а) подібність фрагмента перевищує поріг 8, б) подібність двох і більше сусідів з чотирьох також вище порога 8. Таким чином, для підтримки рішення в експерименті використовувалися фрагменти з номерами 2, 4, 6, 8 ( см. рис. 2).

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

    Якісні властивості системи розпізнавання можна оцінити величиною т, що становить відносне перевищення максимуму гістограми р [/], / е /, який відповідає правильно розпізнати-

    ТАХРОМ [/] - тах2р [/] ТАХРОМ [/]

    (12)

    Малюнок 5 - Гістограма голосів

    Значення (12) знаходиться в межах відрізка [0, 1]. Чим ближче до одиниці величина т, тим вище буде надійність побудованої системи розпізнавання. Для гістограми рис. 5 значення т одно 0,67. Зрозуміло, що зі збільшенням кількості розпізнаваних класів, а також при зростанні числа використовуваних фрагментів величина (12) знижується. Крім того, вона знижується при збільшенні порога 8, т. К. С ростом 8 росте число фрагментів, що беруть участь в голосуванні.

    Провівши аналіз еталонів (рис. 3), можна відзначити, що навіть для повного набору фрагментів в кількості 400 характерним є те, що перший і другий еталони відрізняються від інших в сенсі побудованої моделі розпізнавання всього приблизно в 170 фрагментах (43% від загальної кількості) , третій еталон - в 100 фрагментах (25%). Ця ситуація в цілому є типовою для задач розпізнавання зображень в комп'ютерному зорі, коли тільки частина наявної візуальної інформації може бути застосована з користю. Наведені процентні співвідношення означають величину частини пікселів носія конкретного зразка щодо загального їх числа. Звичайно, ідеальним для фрагментного уявлення був би випадок, коли рішення базується на максимально можливому числі розрізняються для різних еталонів фрагментів. Для еталонів рис. 3 збільшення інформативного кількості фрагментів можна досягти, наприклад, шляхом зменшення розміру еталонного зображення. Іншим способом може бути вибір потрібної кількості інформативних фрагментів в діалоговому режимі.

    Грунтуючись на характеристиках еталонів, вибиралося значення порога 8т для максимуму схожості. Саме воно дорівнювало 8т = 0, 3 для числа фрагментів, рівного 10, і 8т = 0, 1 при числі фрагментів, що дорівнює 100. У цілому апріорно задається значення 8т є компромісом між надійністю розпізнавання на основі обмеженої кількості фрагментів і стійкістю до локальних спотворень.

    Рівень дії адитивного шуму оцінювався величиною відносини сигнал - шум у вигляді ЦА = = А / (а), де А - середня яскравість інформаційної частини (носія) для набору еталонів, а - середньоквадратичне відхилення шуму з нульовим математичним очікуванням. Для еталонів рис. 3 величина середньої яскравості дорівнювала 162.

    У табл. 1 наведені значення показників, що відображають якість розпізнавання шляхом голосування фрагментів для різних методів при 8 = 10% і кількості фрагментів, що дорівнює 10. Варіант повного

    т =

    набору включає 400 фрагментів. Експерименти показали, що для порога схожості 8 = 5% більшість з розглянутих підходів при дії шуму не забезпечують стійких оцінок. Величина ЦА відповідає максимальному значенню співвідношення сигнал - шум для адитивного шуму, коли ймовірність розпізнавання залишається в межах вище 0,95. значен-

    1оС і

    ня ца - це максимальний рівень адитивних перешкод при одночасній дії локальної перешкоди, коли ймовірність розпізнавання залишається більшою 0,95. Рівень локальної перешкоди р оцінювався співвідношенням площ сигналу і перешкоди в межах області еталона [8]. У таблиці наведено дані при величині р = 2 (приблизно третя частина спотворена перешкодою). Тут наведено також в порівняльному плані значення часу розпізнавання (в умовних величинах).

    Таблиця 1 - Значення показників, що відображають якість розпізнавання

    "" -|-Параметри Метод ас | Ца Ца "(в = 2) Час

    Спільне голосування 5 6 6

    Спільне голосування з підтримкою 4,5 5,5 14

    Повний набір фрагментів 3,5 4,5 90

    Незалежне голосування 5,2 6,3 9

    Незалежне голосування з підтримкою 4,5 5 15

    Величина т для розглянутих методів без перешкод перебувала в межах 0,88-1,0, а при заваді з рівнем ЦА = 5 знижується до діапазону 0,7-0,85. Для методів з підтримкою значення т в цілому на 15% вище, ніж без підтримки.

    Аналіз кількості фрагментів, що представляють зображення, показав наступне. Наприклад, при ЦА = 4 ймовірність розпізнавання для методу спільного голосування з підтримкою при використанні як 5, так і 10 фрагментів дорівнює приблизно однієї і тієї ж величині 0,85. Таким чином, при високому рівні шуму незначне збільшення кількості фрагментів (від 5 до 10) не призводить до потрібного підвищення надійності. При зниженні ж рівня шуму (ЦА > 5) ймовірність розпізнавання і так досить висока (більше 0,95). Однак зі збільшенням кількості фрагментів пропорційно зростає і час розпізнавання, тому при невисокому рівні шуму природним виглядає використання якомога меншої кількості фрагментів.

    Найбільш сильно в плані помехозащищенности виглядає спосіб повного набору фрагментів, при якому рішення спирається на число фрагментів, рівне 400, що значно більше, ніж у інших підходів (5-20). Як бачимо з таблиці, надійність цього методу істотно вище (ЦА = 3, 5), ніж при примене-

    ванні інших підходів. У той же час і швидкодія даного підходу значно нижче. Для адитивних перешкод перешкодозахищеність методу голосування з повним набором фрагментів можна порівняти з характеристиками класичного кореляційного методу (ца = 3 [1]).

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

    Застосування підтримки, як показали наші експерименти, в більшій мірі ефективно при незалежному голосуванні. Так, при числі фрагментів 10 надійність зростає при використанні підтримки, т. К. Необхідне співвідношення сигнал - шум знижується від 5,2 до 4,5 (табл. 1). Ще більш ефективна підтримка для цього виду голосування при малому числі фрагментів. Для незалежного голосування при рівні перешкод ЦА = 5,5 величини ймовірності склали 0,80 і 0,95 відповідно.

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

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

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

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

    ВИСНОВКИ

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

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

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

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

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

    Подальші дослідження будуть спрямовані на теоретичне обґрунтування правил прийняття рішень по безлічі відносин фрагментів.

    ПЕРЕЛІК ПОСИЛАНЬ

    1. Гороховатський В, А, Розпізнавання зображень в умовах неповної інформації / Гороховатський В. А. -Харків: ХНУРЕ, 2003. - 112 с.

    2. Баклицький В, К, Методи фільтрації сигналів в кореляційно-екстремальних системах навігації / Баклицький В. К., Бочкарьов А. М., Мусьяков М. П. -Москва: Радио и связь, 1986. - 216 с.

    3. Гороховатський В. А. Структурно-ієрархічні методи визначення подібності зображень об'єктів // АСУ та прилади автоматики. - 2005. - Вип. 131. -С. 55-62.

    4. Шапіро Л. Комп'ютерне зір: пров. з англ. / Шапіро Л., Стокман Дж. - М.: Біном. 2006. - 752 с.

    5. Гороховатський В. А. Застосування процедур голосування в структурних методах розпізнавання візуальних об'єктів / Гороховатський В. А. // Вісник НТУ ХПІ. Системний аналіз, управління та інформаційні технології. - 2006. - № 39. - С. 132-140.

    6. Kim S. Biologically motivated perceptual feature: generalized robust invariant feature / Kim S., Kweon I.-S. // Asian Conference of Computer Vision (ACCV-06), 2006. -P. 305-314.

    7. Путятін E. П. Розпізнавання зображень в просторі інваріантних локальних ознак / Путятін Є.П., Гороховатський В. А., Кузьмін С. В. // Радіоелектроніка та інформатика. - 2006. - № 1 (32). -З. 69-73.

    8. Путятін E. П. Обробка зображень в робототехніці / Путятін Є.П., Аверін С. І. - М.: Машинобудування, 1990. - 320 с.

    Надшшла 16.05.2008

    Наведено результати досл1джень i3! Застосування процедур Голосування у кореляцшніх методах розтзна-вання збережений. Вівче Способи формирование систем фрагментiв, формалiзована постановка задачi розтзна-вання, проаналiзовано рiзноманiтнi варiанті Голосування, шляхи Вибори ознака фрагментiв та встановлення вiдповiдностi мiж ними. Експеріментальт результати пiдтверджують ефектівтсть! Застосування тдходу.

    The results of application of voting procedures in correlation methods of image recognition are shown. The ways of systems of fragments construction are studied. The recognition problem is formalized. The variety of voting procedures, the ways of choosing fragment characteristics and the estab-lishment of the conformity between them are analyzed. The efficiency of the suggested approach is experimentally.

    УДК 519.85

    І. В. Гребенник, А. В. Баранов

    ОЦІНКИ МІНІМУМУ опуклої функції НА КЛАСАХ КОМБІНАТОРНИХ множині перестановок

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

    ВСТУП

    При математичному моделюванні класичні комбінаторні безлічі часто з надлишком опісива- © Гребенник І. В., Баранов А. В. 2009

    ють область припустимих рішень комбінаторних оптимізаційних задач [1]. В роботі [2] введений новий клас комбінаторних множин - композиційні образи комбінаторних множин, які дозволяють більш адекватно описувати області допустимих рішень складних завдань комбінаторної оптимізації. Для вирішення завдань оптимізації на композиційних образах комбінаторних множин необхідно застосовувати методи комбінаторної оптимізації, які б враховували особливості введеного класу комбінаторних множин.


    Завантажити оригінал статті:

    Завантажити