Моделі мультиграничної сегментації зображень

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





Чупиков Андрій Миколайович

	УДК 004.932.2:004.93’14





МОДЕЛІ МУЛЬТИГРАНИЧНОЇ СЕГМЕНТАЦІЇ ЗОБРАЖЕНЬ



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



Автореферат

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

кандидата технічних наук





























Харків – 2008


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

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

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

Машталір Володимир Петрович,

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

декан факультету комп’ютерних наук.

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

Крилов Віктор Миколайович, Григорович,

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

професор кафедри прикладної математики та інформаційних технологій в бізнесі; Харківський нац

ух обчислювальних машин;

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

Шабанов-Кушнаренко Юрій Петрович, й університет 

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

професор кафедри програмного забезпечення ЕОМ. .

овідна установаіональнй технічний університет України «Одеський політехнічний інститут», кафедра технчної кібернетики, Міністерство освіти і науки України, м. Одеса.

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

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

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

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

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

	

	

загальна характеристика роботи



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

Серед основних цілей сегментації зображень варто виділити такі: позиціонування областей на основі агрегованих ознак; врахування ознак форми цільового об’єкта та просторових відношень між різними об’єктами; створення передумов для підвищення швидкодії за рахунок виключення необхідності аналізу окремих пікселів; стиснення зображень на основі сукупностей областей, які не перетинаються, та їх яскравих та геометричних ознак, забезпечення можливостей індексації та пошуку в базах даних по змісту зображень із запитами ‘ad exemplum’.

Основний вплив на розвиток методів сегментації зображень зробили українські та зарубіжні вчені С.Г. Антощук, А.М. Ахметшин, Р.А. Воробель, В.М. Крилов, Є.П. Путятін, М.І. Шлезінгер, L. Alvarez, B.K.P. Horn, W.G. Kropatsch, A. Rosenfeld, J. Serra, J. Weіckert та ін. Аналіз стану та тенденцій розвитку методів сегментації дозволяє стверджувати, що, незважаючи на численні дослідження в цьому напрямку, задача синтезу розумних із погляду прикладної інтерпретації фактор-множин ще далека від свого остаточного розв’язання.

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

Зв’язок роботи з науковими програмами, планами, темами. Дисертаційна робота виконана відповідно до плану науково-дослідних робіт Харківського національного університету радіоелектроніки в межах держбюджетних тем «Дослідження та розробка методів аналізу зображень в умовах складних перетворень» (№ ДР 0103U001572, виконавець), «Розробка моделей та методів факторизації інформації в умовах багатозначності» (№ДР 0104U004063, виконавець) та “Інтелектуальний аналіз і обробка даних у реальному часі на основі засобів обчислювального інтелекту” (№ДР 0104U003432, виконавець), що виконуються згідно з наказами Міністерства освіти і науки України за результатами конкурсного відбору проектів наукових досліджень. У межах зазначених тем здобувачем було удосконалено моделі мультиграничної сегментації півтонових зображень, а також введено та обґрунтовано методи трансформації отриманих класів еквівалентностей або їх окремих елементів.

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

Відповідно до поставленої мети дисертаційна робота передбачала розв’язання таких завдань:

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

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

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

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

Предмет дослідження – моделі мультиграничної сегментації візуальної інформації для контекстної інтерпретації в системах технічного зору.

Методи дослідження – при розробці та дослідженні моделей сегментації зображень було використано математичний апарат розпізнавання образів, теорії множин та алгебри, елементи статистичного аналізу.

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

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

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

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

Практичне значення отриманих результатів. Розроблені в дисертаційній роботі моделі мультиграничної сегментації зображень, що засновані на аналізі зв’язку розбиття та покриття поля зору та області значень даних із використанням їх перетворень для пошуку раціонального прикладного трактування, можуть бути застосовані для вирішення широкого кола завдань інтерпретації зображень. Використання отриманих результатів забезпечило досить стійку автоматичну сегментацію зображень та створило передумови для оцінки подібності зображень за результатами сегментації, що дозволяє враховувати надмірність або дефіцит інформації разом з її багатозначністю на етапі тематичної інтерпретації. Синтезовані методи підтвердили свою ефективність при створенні систем медичної діагностики, зокрема в Харківському державному медичному університеті (акт про впровадження від 15.09 2007 р.), в Дорожній клінічній лікарні ст. Харків (акт про впровадження від 19.09 2007 р). Також наукові положення, висновки і рекомендації, викладені в дисертації, були використані в навчальному процесі Харківського національного університету радіоелектроніки (акт про впровадження від 24.10 2007 р).

Особистий внесок здобувача. Усі основні результати, що виносяться на захист, отримані здобувачем особисто. У роботах, опублікованих зі співавторами, здобувачу належать: у [2] – запропоновані й досліджені моделі часткової сегментації на базі зв’язку розбиттів (покриттів) областей визначення і значень даних; у [3] – проведено оцінку ефективності застосування існуючих методів сегментації для виділення областей інтересу на різних класах зображень; у [4] – формалізовані та вивчені властивості толерантностей у задачах сегментації зображень; у [5] – введенні трансформації перерізів зображень, які є класами еквівалентностей або толерантностей; у [9] – запропоноване врахування ознак форми, яке забезпечує можливості інтерпретації перетворень результатів сегментації.

Апробація результатів дисертації. Основні результати роботи були висвітлені, обговорені і схвалені на таких науково-технічних конференціях: 10-й Міжнародний молодіжний форум “Радіоелектроніка і молодь у XXI столітті” (м. Харків, 10-12 квітня 2006 р.); Перша міжнародна наукова конференція «Глобальні інформаційні системи. Проблеми і тенденції розвитку» (м. Харків, 3-6 жовтня 2006 р.); Х Міжнародна наукова конференція, присвячена пам’яті генерального конструктора ракетно-космічних систем, академіка М.Ф. Решетнєва (м. Красноярськ, 8-10 листопада 2006 р.); Міжнародна наукова конференція «Сучасні проблеми математики та її застосування в природних науках й інформаційних технологіях» (м. Харків, 23-25 березня 2007 р.); Міжнародна конференція «Інтелектуальні системи прийняття рішень і прикладні аспекти інформаційних технологій» (м. Євпаторія, 14-18 травня 2007 р.), International conference on computer vision and graphics (Warsaw, Poland, September 22-24, 2004); 4-th International Workshop Adaptive multimedia retrieval (Geneva, Switzerland, July 27-28, 2006).

Публікації. Основні результати дисертаційної роботи надруковано у 10 наукових працях, у тому числі 3 статті у виданнях, що входять до переліків, затверджених ВАК України, та 7 публікацій у збірниках праць міжнародних наукових конференцій.

Структура дисертації. Дисертація складається зі вступу, чотирьох розділів, висновків, списку використаних джерел та додатку. Повний обсяг дисертації становить 146 сторінок; обсяг основного тексту 121 сторінка; 43 рисунка; 7 таблиць; список використаних джерел, що включає 139 найменувань та займає 15 сторінок; додаток на 5 сторінках.


основний зміст роботи



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

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

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

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

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

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

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

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



.



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



 (1)



де  



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



 – клас образів елемента ;

 – клас прообразів елемента .



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

Твердження 1. Класи толерантності утворюють правильне покриття множини .

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

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







Вивчені властивості правильних і впорядковано зв’язних покриттів.

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



.



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

Властивість 3. Довільне розбиття скінченної множини  є впорядковано зв’язним покриттям.

Довільне бінарне відношення , яке задане на множині , названо функціональним, якщо задана деяка функція , а на  задано покриття  і , де , .

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

Ці результати створили передумови для вивчення питань взаємозв’язку завдання покриттів значень функцій розподілу яскравості і результатів сегментації.

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

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

Інтерпретація доведеного твердження прозора – при раціональному розбитті діапазону зміни функції розподілу яскравості можна одержати "області подібності" на носії зображення у вигляді класів толерантності, які трактуються доволі просто.

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

На питання про зв’язок класів толерантності й суміжних класів відповідає 

Твердження 4. Будь-який суміжний клас довільного толерантного відношення містить підмножину – клас толерантності, якому належить елемент, що породжує цей суміжний клас.

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

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

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







де , , , .

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



.

Це відношення є відношенням еквівалентності, продукуючи клас еквівалентності  правилом



. (2)



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



 



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

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

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

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



, (3)

, (4)

, (5)

. (6)



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

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

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

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

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

Якщо  використовувати  і  як структурні елементи, отримуємо ортогональні () або ізотропні () межі. Застосовуючи розклад чотиризв’язності , де  , , отримуємо горизонтальні та вертикальні складові межі.

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







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

У розділі встановлений взаємозв’язок між парами  і  елементів двох довільних розбиттів  і 



,

,

.



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



,

.



Якщо ввести позначення , де  означає внутрішню частину елемента  з межею  і визначити відношення






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



 



дозволяє для будь-яких розбиттів , визначити



, ,

, ,  



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

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

Для опису форми елементів покриття використовувався набір таких ознак: площа, заповнена площа, опукла площа, периметр, діаметр кола рівної площі, діаметр окружності рівного периметра, максимальний діаметр Ферре, довжини великої та малої піввісей еліпсу, координати центру тяжіння, середня арифметична відстань від контурних точок до центру тяжіння, розкид відстані від контурних точок до центра тяжіння; максимальна й мінімальна відстань до центру тяжіння; максимальний та мінімальний моменти інерції відносно головних центральних вісей інерції контуру; число Ейлера. На основі цих ознак вираховувалися такі числові характеристики елементів покриття: сферична проекція, відношення Ваделла (опуклості форми), відношення Пентланда (сферичність проекції), коефіцієнт складчастості, ексцентриситет, фактор компактності Гортона, відношення опуклості, параметри кривизни.

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

Рис. 1 ілюструє описану схему сегментації. На рис. 1, а) наведено початкове зображення; на рис. 1, б) показано реквантоване зображення з розбиттям  , де , , , , . На рис. 1, в) зображено 127 класів однорідності (отримане розбиття є правильним і порядковано зв’язним); рис. 1, г) демонструє результати трансформацій (отримано 10 класів еквівалентності). Рис. 1, д) показує зв’язок кінцевого розбиття з початковим зображенням, на рис. 1, е) наведено результати апроксимації райдужної оболонки й зіниці. Залежності на рис 1, ж), з) ілюструють значення ознак «округлості», «складчастості» та опуклості. 

Для дослідження залежності точності багатозначного реквантування від кількості порогів використовувалось розбиття оператором початкового зображення, що приймалося як еталонне. Для визначення міри близькості між еталонним розбиттям («ground truth» парадигма)  і розбиттями , які отримуємо внаслідок автоматичного реквантування, використовувалася метрика 



,



де  – симетрична різниця множин.


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

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

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

У додатку наведено акти впровадження теоретичних і практичних результатів дисертаційних досліджень.


Висновки



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

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

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

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

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

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

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

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


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



	1. Чупиков А.Н. Свойства толерантностей при сегментации изображений // Прикладная радиоэлектроника. – 2006. – № 3 (5). – С. 408–411.

	2. Машталир В.П., Чупиков А.Н. Модели покрытий в задачах сегментации изображений реквантованием // Радиоэлектроника и информатика. – 2006. – № 3. – С. 58–65.

	3. Егорова Е.А., Чупиков А.Н., Щербинин К.А. Интеллектуальная обработка результатов сегментации синтезированных изображений // Прикладная радиоэлектроника. – 2006. – Т. 5, № 3. – С. 408–411.

	4. Chupikov A., Kinoshenko D., Mashtalir V., Shcherbinin K. Image retrieval with segmentation-based query // Adaptive multimedia retrieval: user, context, and feedback / S. Marchand-Maillet et al. (Eds.). 4-th International Workshop Adaptive Multimedia Retrieval. Geneva, Switzerland, July 27–28, 2006. – Berlin Heidelberg: Springer-Verlag. – Lecture Notes in Computer Science. – Vol. 4398. – 2007. – Р. 208–222.

	

165. Chupikov A., Mashtalir S., Yegorova E. Morpholohical normalization of image binary cuts // Computational Imaging and Vision / M.A. Viergever, ed. International Conference on Computer Vision and Graphics. Warsaw. Poland, September 22–24, 2004. – Dordrecht: Springer. –Vol. 32. – 2006. – P. 558–564.

	

166. Чупиков А.Н. Синтез методов сегментации в задачах идентификации // Материалы I международной научной конференции «Глобальные информационные системы. Проблемы и тенденции развития». Харьков, 3–6 октября 2006 г. – Харьков: ХНУРЭ, 2006. – С. 87–88.

	7. Чупиков А.Н. Синтез и комбинирование методов сегментации изображений // Материалы Х международной научной конференции, посвященной памяти генерального конструктора ракетно-космических систем академика М.Ф. Решетнева. Красноярск, Россия, 8–10 ноября, 2006 г. – Красноярск: СибГАУ, 2006. – С. 327–328.

	8. Чупиков А.Н. Современные проблемы сегментации изображений // Сборник материалов международной научной конференции «Современные проблемы математики и ее приложения в естественных науках и информационных технологиях». Харьков, 23–25 марта 2007 г. – Харьков: ХНУ им. В.Н. Каразина, 2007. – С. 49–52.

	9. Каграманян А.Г., Киношенко Д.К., Чупиков А.Н., Щербинин К.С. Мультипороговая сегментация с использованием признаков формы // Материалы международной конференции «Интеллектуальные системы принятия решений и прикладные аспекты информационных технологий». Евпатория, 14–18 мая 2007 г. – Херсон: ПП Вышемирский В.С., 2007 – Т. 3. – С. 143–146.

	10. Чупиков А.Н. Анализ отношений толерантности в задачах сегментации изображений // Материалы 10 международного молодежного форума «Радиоэлектроника и молодежь в XXI веке». Харьков, 10–12 апреля 2006 г. – Харьков: ХНУРЭ, 2006. – С. 275.


анотація



Чупиков А.М. Моделі мультиграничної сегментації зображень – Рукопис.

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

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

Ключові слова: зображення, сегментація, розбиття, покриття, мультигранична обробка. 


аннотация



Чупиков А.Н. – Модели мультипороговой сегментации изображений. – Рукопись.

Диссертация на соискание ученой степени кандидата технических наук по специальности 05.13.23 – системы и средства искусственного интеллекта. – Харьковский национальный университет радиоэлектроники, Харьков, 2008.

Диссертация посвящена разработке моделей и методов сегментации изображений на основе анализа и преобразований индуцированных мультипороговыми ограничениями классов толерантностей и эквивалентностей с целью создания предпосылок для проблемно-ориентированной интерпретации визуальной информации. 

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

Установлено, что для устранения семантического конфликта в настоящее время внимание исследователей все более фокусируется на так называемом «среднем уровне», обеспечивающем разумную связь результатов первичной обработки (в том числе и традиционной сегментации) и продукционных методов. 

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

Проведена формализация и изучены свойства индуцированных покрытий на базе правильных, упорядоченно связных, базисных покрытий, транзитивных триплетов, функциональных бинарных отношений. Доказано, что классы толерантности образуют правильное покрытие множества, функциональное отношение не меняется, если из индуцирующего его покрытия будут удалены все неправильные элементы. Найдены условия, когда классы образов и прообразов функционального отношения, фактически индуцированного изображением и некоторым упорядоченно связным покрытием, являются классами толерантности. Показано, что любой смежный класс произвольного толерантного отношения содержит подмножество – класс толерантности, которому принадлежит элемент, порождающий данный смежный класс. Изучены свойства матричных представлений произвольных толерантных отношений, условия, когда покрытие является базисным для произвольной функциональной толерантности.

Поскольку результаты частичной сегментации практически всегда являются чрезмерными или недостаточными для валидной интерпретации изображений требуется достаточно интенсивная обработка полученных разбиений или покрытий. Указаны условия, налагаемые на потенциальные преобразования как отдельных областей, так и их семейств (вплоть до фактор-множеств): условие существования требуемого отображения, его аддитивности, монотонности, возможности обработки нескольких множеств, определяющих сегментированное изображение. 

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

Для огрубления и/или детализации результатов сегментации или отдельных фрагментов введена характеристическая функция классов эквивалентности, формализующая их преобразования с использованием матрицы отношений, однозначно задающей все возможные варианты взаимного расположения элементов разбиения, анализ которых повышает точность и надежность интерпретации. 

Определен набор признаков формы областей, обсуждены алгоритмы аппроксимации недостаточно определенных результатов сегментации. 

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

Схема реализации теоретических результатов представляется следующим образом. После медианной фильтрации на основе мультиграничных моделей выполняется мультипороговое реквантование изображений с учетом детектирования локальных максимумов гистограмм. После индексации связных областей на базе бинарной морфологии исключаются из анализа мелкие детали, а в каждом оставляемом классе устраняются несущественные вложения. Пороговая фильтрация в признаковом пространстве обеспечивает отсечение ряда элементов фактор-множеств, представляющих фоновые компоненты. После выделения внутренностей и границ элементов разбиений (покрытий) на базе пространственного контекста (вложенности, касания, пересечения областей) выполняются теоретико-множественные операции с целью получения пригодного для однозначной интерпретации результата.

Ключевые слова: изображение, сегментация, разбиение, покрытие, мультипороговая обработка.


ABSTRACT



Chupikov A.N. Models of multithreshold image segmentation. – Manuscript.

Thesis for a candidate of technical science (Ph.D.) degree in specialty 05.13.23 – systems and tools of artificial intelligence. – Kharkiv National University of Radio Electronics, Kharkiv, 2008.

The thesis is devoted to development of models and methods providing on the basis of double-step procedures synthesis of partitions of a field of view which are adequate from applied standpoint. The first stage consists in production of partial image segmentation on application of multithreshold processing. The second one is connected with obtaining on the transformation basis of partitions or coverings of image carriers families, which are suitable for problem-oriented interpretation, and correlate with significant objects of the scene. The implemented theoretic and experimental researches of multithreshold models and operations with classes of equivalences or tolerances, in view of their spatial properties and aprioristic feature information connected with specificity of subject-oriented fields, have allowed to create the software providing as solutions of specific processing and interpretation of the visual information problems and their use at a choice of multithreshold segmentation algorithms parameters.

Keywords: image, segmentation, partition, covering, multithreshold processing.

1