Структурно-ієрархічні методи аналізу та розпізнавання зображень в умовах впливу просторових завад

Размещено на http://www.allbest.ru/

Харківський національний університет радіоелектроніки

СТРУКТУРНО-ІЄРАРХІчні Методи аналізу та РозПіЗНАВАНнЯ зображень в умовах впливу просторових завад

05.13.23 - системи та засоби штучного інтелекту

Автореферат

дисертації на здобуття наукового ступеня доктора технічних наук

Гороховатський Володимир Олексійович

УДК 004.932.2:004.93'1

Харків - 2010

Дисертацією є рукопис.

Робота виконана у Харківському національному університеті радіоелектроніки Міністерства освіти і науки України.

Науковий консультант: доктор технічних наук, професор

Путятін Євгеній Петрович, завідувач кафедри інформатики Харківського національного університету радіоелектроніки (м. Харків).

Офіційні опоненти: доктор технічних наук, професор

Воробель Роман Антонович, завідувач відділу обчислювальних методів і систем перетворення інформації Фізико-механічного інституту ім. Г.В.Карпенка НАН України (м. Львів);

доктор технічних наук, професор

Сіроджа Ігор Борисович, професор кафедри інженерії програмного забезпечення Національного аерокосмічного університету ім. М.Є. Жуковського «ХАІ» (м. Харків);

доктор технічних наук, професор

Скобцов Юрій Олександрович, завідувач кафедри автоматизованих систем управління

Донецького національного технічного університету (м. Донецьк).

Захист відбудеться «01» червня 2010 р. о 13 годині на засіданні спеціалізованої вченої ради Д 64.052.01 у Харківському національному університеті радіоелектроніки за адресою: 61166, м. Харків, пр. Леніна, 14.

З дисертацією можна ознайомитися у бібліотеці Харківського національного університету радіоелектроніки за адресою: 61166, м. Харків, пр. Леніна, 14.

Автореферат розісланий «22» квітня 2010 р.

Вчений секретар

спеціалізованої вченої ради С.Ф. Чалий

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

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

Значний внесок у розвиток методів розпізнавання зображень в інтелектуальних системах внесли дослідження українських та зарубіжних вчених, таких як С.Г. Антощук, О.М. Ахмeтшин, М.Ф. Бондаренко, Р.А. Вoрoбeль, Ю.І.Журав-льов, А.Г. Івахненко, В.А. Кoвалeвський, Н.М. Куссуль, В.Г. Лабунець, В.П.Маш-талір, Є.П. Путятін, Б.П. Русин, Ю.О. Скобцов, І.Б. Сіроджа, Ю.П. Шабанoв-Кушнарeнко, М.І. Шлeзінгeр, R. Duda, D.A. Forsyth, R.C. Gonzales, P.V.C. Hough, S. Kim, D.G. Lowe, W.K. Pratt, A. Rosenfeld, L.G. Shapiro, С. Schmid та ін.

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

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

Зв'язок роботи з науковими програмами, планами, темами. Робoту виконано на кафедрі інформатики відповідно до плану науково-дослідних робіт Харківського національного університету радіоелектроніки в межах тем: № ДР 0194U038440 «Обробка складних сигналів (зображень) в інформаційних системах», № ДР 0196U011359 «Розробка і дослідження теоретичних і прикладних аспектів синтезу й обробки рентгенографічних зображень у системах радіаційно-інтроскопічного аналізу», № ДР 0197U008892 «Методи обробки і технології розпізнавання зображень різної фізичної природи», №ДР 0104U004063 «Концептуальні підходи та методи інтелектуальної факторизації даних в умовах багатозначності», №ДР 0107U003029 «Дослідження та розробка методів і моделей інтерпретації даних у системах комп'ютерного зору», №ДР 0108U009112 «Розробка математичних моделей інформаційних систем з великою нелінійністю», а також ряду договорів про науково-технічне співробітництво. У межах зазначених тем здобувачем розроблені та обґрунтовані структурно-ієрархічні методи розпізнавання зображень для СКЗ, а також проведено дослідження їх ефективності.

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

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

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

- розробити модель локально-просторової подібності при розпізнаванні відеооб'єктів шляхом зіставлення їх структурних описів на підставі голосування;

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

- розробити метод побудови і оцінки подібності описів відеооб'єктів для системи ознак стратифікованого подання;

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

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

- розвинути моделі стиснення структурних описів відеооб'єктів та удосконалити метод побудови і зіставлення ієрархії описів з метою скорочення часу розпізнавання;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

У процесі дисертаційних досліджень розв'язано ряд конкретних задач: 1) автоматизації контролю якості та виявлення дефектів устаткування шляхом аналізу магнітограм на основі застосування структурно-ієрархічних методів; 2) локалізації рухомих просторово-протяжних об'єктів на фоні нестаціонарних перешкод з використанням структурно-ієрархічного аналізу відеоданих; 3) вибору адекватної статистичної моделі для значень структурних ознак зображень і визначення оптимального порогу для встановлення еквівалентності фрагментів та векторів ознак; 4) застосування розширеного аналізу альтернатив класів на локальному та глобальному рівнях структурно-ієрархічного методу з метою забезпечення високої ймовірності розпізнавання.

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

Практичне значення результатів досліджень підтверджується їх впровадженням. Метод локалізації просторово-протяжних об'єктів на фоні нестаціонарних перешкод і математичні моделі аналітичних співвідношень для значень середнього ризику використані в Центрі радіофізичного зондування Землі НАН і Національного космічного агентства України (акт впровадження від 07.07.2009); метод розпізнавання зображень з використанням голосування і статистичного ухвалення рішень при тематичному дешифруванні матеріалів космічних зйомок, а також моделі формування компонентного подання двовимірних об'єктів і ієрархічні процедури стиснення використані в Північно-східному філіалі Державного науково-виробничого центру «Природа» (акт від 10.08.2009); ієрархічний метод розпізнавання в умовах фону і математичні моделі фільтрації множини ознак застосовані в дорадчих інформаційних системах у Харківському національному технічному університеті сільського господарства (акт від 05.09.2009); методи, принципи і методика аналізу статистичних характеристик фрагментів магнітограм знайшли застосування в науково-виробничій фірмі «Спеціальні наукові розробки» (акт від 01.07.2009); результати досліджень у вигляді математичних і програмних моделей використовуються в навчальному процесі Харківського національного університету радіоелектроніки (акт від 12.09.2009).

Особистий внесок здобувача. Усі результати, які складають основний зміст роботи і виносяться на захист, отримані автором самостійно, їх суть викладено у [1-51]. У роботах, написаних у співавторстві, здобувачеві належать постановка завдання, обґрунтування рішення, а також: [2,3] - принцип оптимізації параметрів структурно-ієрархічних методів, вибір критеріїв для визначення оптимальних порогів; [4] - спосіб побудови функціоналів для паралельної нормалізації на основі багаторівневого подання; [6,41] - узагальнення, обґрунтування та дослідження завадостійкості структурно-ієрархічних методів до різних типів перешкод; [7,9,43] - формалізовано опис та побудову характерних ознак, досліджено їх властивості, застосовано статистичний аналіз для оцінки значущості та встановлення еквівалентності; [9,46] - узагальнення та обґрунтування моделей локально-просторових мір подібності на підставі голосування; [10] - структурні методи аналізу магнітограм; [13] - синтезовані модифікації, проведена класифікація ієрархічних кореляційних методів розпізнавання на основі голосування; [15] - набули розвитку моделі стиснення описів на основі побудови списку подібних дескрипторів; [18,30,31] - модель одновимірної інтегрально-диференційної узгодженої обробки при формуванні характерних ознак та метод розпізнавання об'єктів в умовах складного фону; [19] - використання перетворення Уолша для визначення інваріантних характерних ознак; [20] - модель обчислення схожості для пірамідальної структури з використанням аналізу страт; [23,34,35] - принцип застосування статистичного та ієрархічного підходів при оцінці параметрів рухомих об'єктів; [28,50] - розвинені моделі стиснення структурних описів, підтверджено скорочення часу обробки; [29] - обґрунтовано принципи побудови та оптимізації структурно-ієрархічних методів на прикладі методу часткових кореляцій; [37,44] - структурні моделі для ідентифікації об'єктів та обчислення параметрів нормалізації; [38,51] - узагальнено моделі побудови мір подібності на основі голосування, проведено аналіз шляхів удосконалення структурно-ієрархічних методів; [39] - спосіб визначення міри подібності та параметрів перетворень на основі стратифікованого уявлення; [47] - удосконалено метод побудови і зіставлення ієрархії описів.

Апробація результатів дисертації. Наукові результати дисертаційних досліджень, концепції і положення докладалися і обговорювалися на конференціях: міжреспубліканській науково-технічній конференції «Обробка растрових зображень в автоматичних системах» (Тула, 1991); VII, VIII, IX-й Міжнародних науково-технічних конференціях «Штучний інтелект. Інтелектуальні системи» (Таганрог-Донецьк, 2006, Дивноморське (Росія), 2007, Донецьк-Кацивелі, 2008); II-й Міжнародній конференції «Сучасні інформаційні системи. Проблеми і тенденції розвитку» (Харків-Туапсе, 2007); Міжнародній конференції з обробки знань KDS «Intelligent Technologies and Application» (Sofia, 2008); IV і V-й Міжнародних конференціях «Інтелектуальні системи прийняття рішень і проблеми обчислювального інтелекту» (Євпаторія, 2008, 2009); Міжнародному радіоелектронному форумі «Прикладна радіоелектроніка. Стан і перспективи розвитку» (Харків, 2008); VIII-й Міжнародній науково-практичній конференції «Сучасні інформаційні технології управління екологічною безпекою, природокористуванням, заходами в надзвичайних ситуаціях» (с. Рибаче, Крим, 2009); IV-й Міжнародній науково-технічній конференції «Комп'ютерні науки та інформаційні технології (csit2009)» (Львів, 2009), VII-й Міжнародній науково-практичній конференції «Математичне та програмне забезпечення інтелектуальних систем (MPZIS2009)» (Дніпропетровськ, 2009), а також на семінарі з проблеми «Образний комп'ютер» (Київ, 2010).

Публікації. Основні наукові положення дисертації викладені в 51 наукових працях, серед яких монографія, 27 статей у фахових виданнях, рекомендованих ВАК України, авторське свідоцтво, 12 публікацій у збірках матеріалів наукових конференцій та 4 за рубежем.

Структура дисертації. Дисертація складається із вступу, восьми розділів, висновків, додатків. Повний обсяг дисертації складає 337 сторінок, обсяг основного тексту 295 сторінок, 71 рисунок, 24 таблиці, список використаних джерел містить 223 назви та займає 21 сторінку, 2 додатки на 13 сторінках.

ОСНОВНИЙ ЗМІСТ РОБОТИ

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

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

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

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

, (1)

де функції описують дію фону та завад, - оператор геометричних перетворень. В умовах дії фіксованої групи перетворень відповідність еталону означає еквівалентність підмножини зображень. Зображення B1 і B2 є еквівалентними відносно G, якщо існує перетворення таке, що переводить до , тобто gB1=B2.

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

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

Рис. 1. Побудова вектора характерних ознак

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

Під терміном «завада» в СКЗ вважають дані, із яких неможливо або важко видобути корисну інформацію. Дія адитивної завади :

, (2)

де - нормально розподілена величина .

Вплив просторових завад описується моделлю Хуанга

(3)

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

. (4)

Просторова завада характеризується вірогідністю p і законом розподілу. Для просторових завад введемо ССШ у вигляді частки площ не викривленої та викривленої частин об'єкта. Якщо m, ml - число точок об'єкта і завади, то ССШ для локальної завади визначимо як

. (5)

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

У другому розділі теоретично обґрунтовано принцип побудови СІМ для розпізнавання відео-об'єктів шляхом оцінки локально-просторової подібності. Розглядаються основи формального опису СІМ, застосування диференційної обробки як базової при виділенні ХО, особливості визначення інваріантних ХО, запропонована модель локально-просторової подібності стосовно методу часткових кореляцій (МЧК) як різновиду СІМ.

Фрагментне уявлення для подамо як

, . (6)

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

, (7)

де - кількість фрагментів, .

Встановлення еквівалентності об'єкта і еталона матиме вигляд

(8)

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

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

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

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

Разом із множиною значень ХО розглядатимемо множину відношень на , де . Для конкретності використовуватимемо бінарні відношення . Маємо три типи відношень: - на множині , - на множині , а також комбіновані виду . реалізує групові властивості значень ХО, а , відображують просторові зв'язки. Використання відношень удосконалює структурне розпізнавання шляхом доповнення ресурсів багаторівневими ознаками. Комбінації ХО у вигляді відношень реалізують грануляцію даних для точнішої апроксимації та отримання більш загальних знань про об'єкт.

Як різновид СІМ розглянемо метод часткових кореляцій (МЧК). Величина схожості (кореляції) безпосередньо пов'язана із функцією правдоподібності. При локальному викривленні зображення оптимальність кореляційного методу втрачається. Експерименти показують, що локальне викривлення 30% точок знижує імовірність правильної ідентифікації до 0,6. Відповідно до МЧК схожості між фрагментами об'єкта і еталона згортаються за певним правилом. Різновиди МЧК розрізнюються числом фрагментів, типом розбиття, формулою для , правилом їх об'єднання. Конкретизуємо ієрархічну локально-просторову схожість: виберемо фрагменти, для яких більше заданого порогу 1; далі усереднимо відібрані значення. Введемо поріг для кількості фрагментів, за якою допустиме обчислення підсумкової схожості

, якщо . (9)

У виразі (9) - предикат, r - число фрагментів, для яких . Якщо r<2, рішення не ухвалюється. Цим задається предикат , що визначає локально-просторову подібність за «значущими» фрагментами. Із правила (9) визначається узагальнена модель локально-просторової подібності у вигляді ієрархічної системи

, (10)

де - локальні рішення з використанням , - функція їх обробки на основі . Модель подібності для СІМ виду (10) поширюється на ознаки або відношення. Загальним чином СІМ можна характеризувати кортежем , де - функція формування ХО.

Принцип побудови СІМ подамо поетапно: 1) формування множин фрагментів або ХО; 2) зіставлення описів ХО для обчислення локальних характеристик подібності ; 3) встановлення результуючої міри локально-просторової подібності між описами об'єкта та еталона; 4) оптимізація на множині описів еталонів. Кожний з етапів має внутрішню структуру.

У загальному вигляді сформульована задача оптимізації МЧК за параметрами , та розмірами фрагментів, цільовою функцією виступає ССШ (5). Чисельне розв'язання задачі оптимізації для конкретних характеристик зображення показало, що надійне рішення про координати відеооб'єкта може бути у окремому випадку прийнято на основі лише 3% не викривленої площі об'єкта. Наведені міркування та оцінки призводять до висновку, що область застосування МЧК і СІМ в цілому істотно ширша, ніж для традиційних методів.

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

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

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

Розглянемо фільтр , що включає одновимірну інтегрально-диференційну обробку, у вигляді

(11)

де - середня довжина фрагмента форми одновимірного імпульсу, -диференціювання, - функція відгуку низькочастотного фільтра. Функцію вибрано так, щоб на множині граничних точок рівень ССШ на виході фільтра перевищував вхідне значення. Варіантом є апроксимація лапласіаном від гаусіану. Наведено розрахунки для визначення оптимальних порогів з метою формування ХО. Як показали числові розрахунки, визначення ХО на основі фільтра значно ефективніше від традиційного . У всьому діапазоні зміни ССШ величина помилки для фільтра на порядок менша. Зниження вірогідності помилки відбувається за рахунок зменшення рівня помилкової тривоги (чисельно 0,003 та 0,046). Підвищення достовірності засноване на використанні у двох граничних точок.

Аналіз методів для визначення ХО показав, що у переважній більшості вони засновані на двовимірних згортках із застосуванням інтегрально-диференційних принципів обробки. Аналіз автокореляційної функції застосовано у методах Харріса, Моравеца, Schmid. Інваріантні локальні потоки близькі до моментних інваріантів, проте використовують відфільтровані диференційні характеристики зображення, що менше залежать від впливу фону. Як показали дослідження, ефективним є також застосування функцій Уолша, дисперсійних ознак, аналіз вигинів контуру, кривизни та ін.

Одним з найбільш універсальних є метод SIFT (масштабно-інваріантне перетворення ознак у відповідності до D.G. Lowe), де будується дескриптор (вектор) з інваріантними значеннями із 128 елементів, в основі лежить диференційний аналіз із застосуванням гаусового згладжування. За рахунок подання у «розгорненому» за множиною значень параметрів (масштаби і повороти) просторі забезпечується точне і стійке визначення ознак. SIFT базований на кореляційному принципі аналізу допустимих значень перетворень і є технологією, що включає в єдиному комплексі локальну фільтрацію, формування значущих ознак, аналіз простору перетворень, апроксимацію координат і ін. Представляється перспективним застосування SIFT для визначення ХО в СІМ.

Розробка модифікацій на основі методу SIFT для умов неповних даних може бути новим кроком у розвитку структурних методів. Дослідження показують, що зіставлення ХО пов'язано з особливостями: а) частина дескрипторів знаходить відповідність з елементами того ж самого об'єкта; б) при зіставленні зі «своїм» еталоном спостерігаються практично одноманітні переходи точок, а при порівнянні з «чужим» еталоном (особливо за наявності фону) відповідності ХО мають хаотичний характер і можуть бути хибними (рис. 2). Ці моменти використаємо при удосконаленні способів зіставлення.

Проведено комп'ютерне моделювання з метою порівняльної оцінки різновидів СІМ на основі підрахунку схожих ХО для бази coil-20. Дослідження завадостійкості відносно адитивних завад показало, що імовірність розпізнавання більше 0,95 досягається: для методу SIFT - при , для локальних потоків - при , для МЧК - при . Очевидні переваги SIFT, в той час як для просторових завад показник методу SIFT та інваріантних потоків () дещо кращий, ніж для МЧК ().

Розв'язано задачу вибору адекватної статистичної моделі для значень ХО зображень і визначення оптимального порогу для встановлення еквівалентності фрагментів та векторів ознак. Проведений статистичний аналіз значень ХО для практичних класів зображень показав, що найбільш універсальним є підхід, коли кожна ХО є незалежною. Це дає можливість аналізувати найважливіші для структурного підходу близькі елементи опису всередині і між об'єктами. Аналіз значень коваріації у просторі ХО на прикладі локальних потоків для бази coil-20 показав, що їх не можна вважати однаковими ні для всіх класів, ні для окремих класів. Для моделі незалежних ХО наявні статистичні дані говорять про те, що, враховуючи їх різноманітність і діапазон зміни, а також значні дисперсії і коваріації, визначення оптимальних порогів викликає ускладнення. Чіткішу визначеність має обчислення порогів для значень мір подібності ХО.

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

Ієрархічний метод розпізнавання відео-об'єктів в умовах складного фону шляхом побудови інтегрального опису реалізується як багатоетапне відображення у вигляді . Кожний етап вирішує свою задачу. Відображення - розгортка за осями; формує кінцеву векторну множину ХО на основі одновимірної інтегрально-диференційної узгодженої обробки; визначає інтегральні групові ХО шляхом сумісного аналізу роздільно для рядків і стовпців; отримує координати об'єкта по осях шляхом оптимізації схожості із еталонними описами; відображенням зіставляються координати і ухвалюється кінцеве рішення. Проведено моделювання при дії адитивного шуму, а також перешкод типу «світлова пляма». Для широкого класу реальних об'єктів оцінювалася вірогідність визначення їх місцеположення, що склала 0,95 при ССШ, більшому 5. Працездатність методу незначно залежить від зміни параметрів геометричних перетворень в межах 10%, а також від зміни контрастності об'єктів щодо фону до 30%. Ефективність застосування методу залежить від близькості форми шуканих і фонових об'єктів.

Узагальнимо модель локально-просторових мір подібності для зіставлення множин ХО при розпізнаванні шляхом голосування. Найбільше задовольняють необхідним властивостям міри, пов'язані з операціями перетину і симетричної різниці множин, що обчислюються шляхом підрахунку відповідностей елементів. Проведено аналіз властивостей основних типів мір подібності: асоціативних, кореляційних, відстаней.

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

(12)

як множини елементів, відстань яких до не перевищує . Правило (12) встановлює еквівалентність, належність перевіряється предикатом

. (13)

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

. (14)

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

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

Принцип відбору близьких елементів опису відповідно до (13),(14) з метою отримання на їх множині глобальної подібності може бути застосовано до будь-якої міри подібності множин, включаючи метрики. Зокрема, при введенні такої обробки метричні властивості зберігають модифікації метрики Хеммінга для векторів у вигляді

(15)

та модифікація метрики Танімото , де - симетрична різниця, - об'єднання множин, причому еквівалентність ХО визначається як заперечення предикату (13).

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

Нехай - розпізнавана множина ХО, , - еталонні множини, , , - об'єднання описів еталонів. Застосуємо для визначення міри подібності спосіб «голосування» елементів . Значення міри інкрементується, якщо елемент має еквівалентний йому із . Еквівалентність розумітимемо у значенні (12),(13). У теоретико-множинному поданні голосування зводиться до побудови на множині уявлення у вигляді розбиття (непересічні підмножини, ) або покриття (), що складаються з елементів, які отримують мітку класу через відображення . Рішення про клас об'єкта приймається вирішальною коаліцією, кількість голосів якої визначається найбільшою потужністю серед .

Подамо розпізнавання як відображення і реалізуємо його шляхом розв'язання задачі оптимізації

, (16)

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

(17)

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

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

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

Проведено комп'ютерне моделювання з метою порівняльної оцінки запропонованих методів розпізнавання для тематичної бази даних із 30 півтонових зображень акваріумних риб (рис.3). Для зіставлення дескрипторів використана евклідова відстань, а поріг вибрано як 1% від максимуму метрики. За результатами експериментів найкращі показники відмінності у просторі ознак та адекватної реакції на просторові викривлення мають модифікації метрик Хеммінга, Танімото, та міри, побудовані на підрахунку бінарних відповідностей. Допустимий рівень викривлень складає 75-80% () об'єму опису при імовірності розпізнавання більше 0,98. Аналіз бінарних відносин у мірах, заснованих на багатозначних відповідностях, забезпечує кращу чутливість до перешкод виключення та вищу достовірність. Відносний локальний оптимум цих мір менш значний, ніж для одиночних відповідностей.

Рис. 3. Експериментальна база зображень акваріумних риб

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

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

, (18)

що означає приналежність околу для кожної з пар (відношення ) і виконання просторових відношень для їх координат. Вираз (18) стосується перетворень рухів і є новим відношенням для четвірки ХО:

.

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

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

. (19)

Значення і (19) є функціями від та способу формування ХО. На основі розрахунку для довільної бази відеоданих можна оцінити граничні можливості структурного розпізнавання за множиною ХО.

Підрахуємо вірогідність того, що ознак із будуть віднесені до класу . Ця подія відповідає -арному відношенню. Якщо враховувати залежність , і позначити () вибірку об'єму із послідовності 1,…,, то , де - значення , () - доповнення () до елементів, . Вірогідність віднесення і більше ознак до класу дорівнює

. (20)

Якщо у спрощеному варіанті значення вважати однаковими, , то відповідно до схеми Бернуллі , де . Враховуючи складність обчислення , пов'язану з перебором кортежів, як верхню оцінку замість (20) можна використати , наприклад, при .

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

Дослідження методів розпізнавання на основі компонент показало значно кращі характеристики достовірності у порівнянні з одиночним голосуванням. Середня для еталонів величина відношення локального максимуму долі голосів до глобального склала: для одиночного голосування - 0,87; для пар - 0,58; для тріад - 0,39. Цим підтверджується ефективність багаторівневих ознак, бо для пар і тріад достовірність значно краща. До аналогічних висновків призвела і оцінка завадостійкості. При дії адитивного шуму забезпечується розпізнавання з вірогідністю вище 0,95 за таких значень ССШ: для одиночних ХО - 5,5, для пар - 1,4, для тріад - 0,03.

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

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

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

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

, (21)

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

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

(22)

де - функція Лапласа, - значення еталона, - різниця між значеннями просторової завади та еталона, - вірогідності появи завади, , . Типові залежності вірогідності помилок (22) від при конкретних наведені на рис. 4, де штрихові криві 1,3 відносяться до традиційному методу, суцільні криві 2,4 - до ієрархічного. Для якісної оцінки наведено залежності при A=10 (криві 3,4), що характеризує істотну відмінність завади та об'єкту, а також при A=1 (криві 1,2 - незначна відмінність). Різна кількість точок у кривих пояснюється залежністю діапазону зміни порогу від значення А.

...