Єгорова Олена Андріївна

УДК 004.932.2:004.93’14

РЕЛЯЦІЙНА КЛАСТЕРНА СЕГМЕНТАЦІЯ

НАПІВТОНОВИХ ЗОБРАЖЕНЬ

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

Автореферат

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

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

Харків – 2007

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

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

Науковий керівник доктор технічних наук, професор Машталір Володимир Петрович, Харківський національний університет радіоелектроніки, декан факультету комп’ютерних наук.

Офіційні опоненти: доктор технічних наук, професор Руденко Олег Григорович, Харківський національний університет радіоелектроніки, завідувач кафедри електронних обчислювальних машин;

доктор технічних наук, професор Соколов Олександр Юрійович, Національний аерокосмічний університет ім. М. Є. Жуковського “Харківський авіаційний інститут”, завідувач кафедри інформатики.

Провідна установа

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

Захист відбудеться “ 30 ” травня 2007 р. о 13.00 годині на засіданні спеціалізованої вченої ради Д 64.052.01 у Харківському національному університеті радіоелектроніки за адресою: 61166, м. Харків, пр. Леніна, 14.

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

Автореферат розісланий  “ 28 ” квітня 2007 р.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Наукова новизна отриманих результатів.– 

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

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

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

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

Особистий внесок здобувача. Усі основні результати, що виносяться на захист, отримані здобувачем особисто. У роботах, опублікованих зі співавторами, здобувачу належать: у [1] – розроблено та досліджено нової метрики на розбиттях; у [2] – проведено оцінку ефективності застосування існуючих методів сегментації для виділення областей інтересу на різних класах зображень; у [3] – проведено алгоритмізацію автоматичного синтезу правил тематичної інтерпретації зображень; у [4] - модифіковано відношення на зображеннях для методу морфологічної нормалізації; у [5] – проаналізовано та удосконалено метод формалізації представлення зображень для створення інваріантних функціоналів для однопараметричних перетворень; у [6] – запропоновано метод грубого кластерного аналізу для пошуку зображень у базах відеоданих; у [7] – удосконалено кластерний метод контекстного пошуку зображень у базах даних; у [8] – модифіковано відношення областей на площині для методу морфологічної нормалізації двухградаційних зображень; у [9] – розроблено та обґрунтовано нову метрику на кінцевих множинах; у [10] – розглянуто питання обмежень використання методів кластерного аналізу в задачах сегментації та напрямки його покращення; у [11] – проаналізовано перспективи сегментації зображень за допомогою методів кластерного аналізу; у [12] – введено елементи математичних моделей, що знаходяться в основі алгоритмізації автоматичного синтезу правил тематичної інтерпретації зображень; у [13] – введено відношення на площині для сегментації зображень враховуючи позиціонування областей; у [14] – запропоновано представлення розбиття зображень у вигляді матриць відношень.

Апробація результатів дисертації. Основні результати роботи доповідалися, обговорювалися і були схвалені на наступних науково-технічних, конференціях і семінарах: на 8-у, 9-у, 10-у Міжнародних молодіжних форумах “Електроніка і молодь у XXI столітті” (Харків, 2003, 2004, 2005), 25-му симпозіумі німецької асоціації з розпізнавання образів DAGM’03 (Магдебург, Німеччина, 2003), “Штучний інтелект” (Кацивєлі, 2004), конференції з комп’ютерного зору і графіки ICCVG’04 (Варшава, Польща, 2004), конференції з графіки, зору та обробки зображень GVIP’05 (Каїр, Єгипет 2005), конференції з машинного навчання та інтелектуальному аналізу даних MLDM’05 (Лейпциг, Німеччина, 2005), 14-й міжнародній конференції в центральній Європі по комп’ютерної графіці, візуалізації та комп’ютерного зору WSCG’06 (Пльзень, Чеська Республіка, 2006), IEEE конференції по спостереженням відеосигналів AVSS’06 (Сідней, Австралія, 2006).

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

Структура дисертації. Дисертація складається зі вступу, чотирьох розділів, висновків, списку використаних джерел та двох додатків. Повний обсяг дисертації становить 153 сторінок; обсяг основного тексту 136 сторінок; 51 рисунок; 1 таблиця; список використаних джерел, що включає 170 найменування та займає 18 сторінок; два додатки на 6 сторінках.

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

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

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

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

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

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

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

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

Якщо дві множини з покриття мають непусте перетинання, тобто , то назвемо їх толерантними: .

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

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

,

де .

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

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

, ,

, .

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

Для двох областей притаманні наступні властивості:

· та не перетинаються, якщо (рис. , а);

· повністю лежить в , якщо (рис. , б);

· при (рис. , в);

· повністю знаходиться в , якщо (рис. , г);

· та перетинаються, якщо (рис. , д);

· , якщо два довільних елемента покриття торкаються один одного (рис. , е);

· , якщо знаходиться усередині елемента покриття , опираючись на його границю (рис. , ж);

· цілком аналогічно (рис. , з).

Рис. 1. Просторовий контекст елементів покриттів поля зору

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

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

Для виділення ознак об’єкта запропоновано представлення об’єкта у вигляді дерева складових.

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

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

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

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

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

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

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

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

,

, ,

,

.

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

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

На парі кінцевих розбиттів введемо функціонал

, (1)

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

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

Твердження 1. Функціонал задовольняє аксіомам рефлективності та симетричності.

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

де , , ,.

Ці матриці можна поелементно перемножувати, тобто отримувати матриці , де . Далі, якщо усі елементи матриці просумувати, то отримана сума, очевидно, дає значення функціоналу (1). Тобто

.

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

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

Якщо до множини додати -й елемент, то розбиття може трансформуватися двома способами:

– елемент може додаватися до набору елементів розбиття як окремо узятий елемент, та трансформується у розбиття виду

, (2)

де

– елемент може “вливатися” в один із елементів розбиття , тоді нове розбиття множини буде мати вигляд

, (3)

де

Трансформацію вигляду (2) визначимо через а вигляду (3) – через при .

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

Твердження 2. Для будь-яких двох розбиттів множини має місце

де ;.

Твердження 3. Для будь-яких двох розбиттів множини та будь-якого номеру має місце

де ,;.

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

Слідство 1. Для будь-яких двох розбиттів множини та будь-якого номеру має місце

,

де, ,.

Твердження 4. Для будь-яких двох розбиттів множини та будь-яких фіксованих номерів та буде виконуватися рівність

,

де ,; .

Якщо дана кінцева множина , на двох довільних кінцевих розбиттях та якого задано функціонал виду

,

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

якщо ;

якщо ;

якщо ;

, якщо ,

де , тобто є розбиття множини с потужністю на 1 більше, ніж потужність множини , а номера та – будь які, тобто

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

Твердження 5. Функціонал , визначений на розбиттях довільних кінцевих множин є метрикою.

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

Разом з тим, природнім залишається питання: як метрика на розбиттях узгоджується з традиційними метриками на зображеннях?

На рис. 2 наведено приклади напівтонових зображень цитологічних препаратів.

Рис. 2. Приклади напівтонових зображень

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

Рис. 3. Результати сегментації зображень, приведених на рис. 2

Порівняння метрики (1) на отриманих розбиттях та евклідової метрики на вихідних напівтонових зображеннях наведено на рис. 4.

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

Рис. 4. Результати порівняння метрик

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

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

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

На рис. 5 наведено результати оцінки відстані (схожості) між даними зображеннями метрикою на розбиттях та евклідовою метрикою (рис. 5, фрагмент а), та відстанню Хаусдорфа (рис. 5, фрагмент б), де у якості еталону було використано зображення 4.

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

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

Рис. 5. Результати порівняння розбиттів синтезованих зображень по евклідовою відстанню, відстанню Хаусдорфа та новою метрикою на розбиттях:

- нова метрика на розбиттях;

- евклидова відстань;

- відстань Хаусдорфа.

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

Рис.6. Паралельний переніс у полі зору відеодатчика

Результати порівняння зображень при використанні паралельного переносу показано на рис. 7.

Можна відмітити, що метрика Хаусдорфа чутливо реагує на випадки, коли область перетинає сусідні області. Новий метод є менш чутливим до часткового та повного поміщення об’єкту в інші області.

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

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

Рис. 7. Схожість зображень після застосування паралельного переносу:

- нова метрика на розбиттях;

- евклідова відстань;

- відстань Хаусдорфа.

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

Рис. 8. Приклад реляційної сегментації цитологічних зображень.

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

У додатках наведені документи щодо впровадження отриманих результатів.

висновки

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

При проведенні досліджень отримано наступні основні результати:

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

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

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

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

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

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

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

1. Егорова Е.А. Киношенко Д.К., Машталир В.П., Шляхов Д.В. Метрическое сравнение результатов сегментации изображений // Радиоэлектроника та информатика. – № 2. – 2006. – С. 55–62.

2. Егорова Е. А. Анализ методов сегментации изображений // Восточно-Европейский журнал передовых технологий. – № 4. – 2006. – С. 67–71.

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

4. Kinoshenko D,. Mashtalir S., Yegorova E. Image normalization via salient points of skeletons // ICGST International Journal on Graphics, Vision and Image Processing. Special Issue on Features and Analysis. – 2006. – P. 1–7.

5. Kinoshenko D., Mashtalir V., Orlov A., Yegorova E. Method of creating of functional invariants under one parameter geometric transformations // Patters Recognition. Michaelis B., Krall G. (Eds.). Lecture Notes in Computer Science, Berlin-Heidelberg, Springer-Verlag. – Vol. 2781. - 2003. – P. 68-75.

6. Kinoshenko D., Mashtalir V., Yegorova E. Clustering method for fast content-based image retrieval // Computer Vision and Graphics. K. Wojciechowski et al. (Eds.). Computational Imaging and Vision, Springer. – Vol. 32. – 2006. P. 946–952.

7. Kinoshenko D., Mashtalir V., Vinarsky V., Yegorova E. Hierarchical partitions for content image retrieval from large-scale database // Machine Learning and Data Mining in Pattern Recognition. Perner. P., Imlya A. (Eds.). Lecture Notes in Artificial Intelligence, Springer–Verlag. – Vol. 3587. – 2005. – P. 445–455.

8. Mashtalir S., Shcherbinin K., Yegorova E. Internal and external salient points under affine transformations. Comparative Study // Proc. of 14th International Conference in Central Europe for Computer Graphics, Visualization and Computer Vision. Plzen, Czech Republic. – 2006. – P. 156–161.

9. Mashtalir V., Mikhnova E., Shlyakhov V., Yegorova E. A Novel metric on partitions for image segmentation // IEEE International Conference on Video and Signal Based Surveillance. Los Alamitos, CA, USA. – 2006. – P. 18–23.

10 Егорова Е.А.  Применение методов кластерного анализа в задачах сегментации // Материалы 8–го Международного молодежного форума “Радиоэлектроника и молодежь в XXI веке”. ХНУРЭ. – 2004. – С. 83.

11. Егорова Е.А. Анализ алгоритмов кластеризации при сегментации изображений // Матеріали 7–й Міжнародної науково–практичної конференції “Наука і освіта 2004”.– Т. 72. –Дніпропетровськ: Наука і освіта. – 2004. – С. 7–8.

12. Егорова Е.А., Машталир В.П. Пространственный контекст в задачах сегментации изображений // Материалы Международной научно–технической конференции “Искусственный интеллект. Интеллектуальные и многопроцессорные системы”. – Т. 2. Таганрог. Изд-во ТРТУ. – 2004. – С.  – .

13. Егорова Е.А., Шерстюк Н.М. Сегментация изображений с учетом позиционирования областей // Материалы 9–го Международного молодежного форума “Радиоэлектроника и молодежь в XXI веке”. ХНУРЭ. – 2005. – С. 414.

14. Егорова Е.А. Пространственный контекст элементов покрытия поля зрения // Материалы 10–го Международного молодежного форума “Радиоэлектроника и молодежь в XXI веке”. ХНУРЭ. – 2006. – С. 277.

анотація

Єгорова О. А. Реляційна кластерна сегментація напівтонових зображень. – Рукопис.

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

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

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

аннотация

Егорова Е. А. Реляционная кластерная сегментация полутоновых изображений. – Рукопись.

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

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

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

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

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

Разработана модель сравнения изображений на основе новой метрики на разбиениях конечных множеств. Одним из принципиальных вопросов эффективного применения любых алгоритмов кластеризации (сегментации изображений в том числе) является объективное сравнение продуцируемых разбиений как на этапе собственно получения группировок, так и на стадии интерпретации результатов. Эвристические оценки результатов кластеризации такие, как коэффициенты Кауфмана, Руссо, Дана и др. позволяют лишь при интерактивном анализе характеризовать “оптимальность” количества кластеров, внутрикластерное сходство, межкластерные различия, степень нечеткости кластеров. Традиционно используемые метрики (городских кварталов, евклидова, Минковского, Махаланобиса, Хаусдорфа и др.) обеспечивают возможность анализа лишь на уровне отдельных пикселей, контуров объектов, объединений и/или пересечений кластеров и, наконец, изображений в целом. Иначе говоря, они не позволяют при сравнениях получать совокупные оценки, учитывающие и форму отдельных элементов разбиений, и их взаимное пространственное расположение. Это обуславливает необходимость введения такой метрики изображений, которая может эффективно работать с методами сегментации.

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

Экспериментальный анализ показал, что метрика имеет ряд преимуществ по сравнению с традиционными, в частности с евклидовым расстоянием и расстоянием Хаусдорфа, так как является более устойчивой к шумам, а также трансформациям объекта.

Проведено имитационное моделирование разработанного метода реляционной кластерной сегментации изображений. Показано его преимущества перед известными методами сегментации в задачах поиска областей интереса за счет анализа позиционирования областей и анализа их объединений.

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

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

ABSTRACT

YegorovaRelational clustering segmentation of gray-scale images. – Manuscript.

Dissertation for a candidate of technical science degree in specialty 05.13.23 – systems and means of artificial intelligence. – Kharkiv National University of Radio Electronics, Kharkiv, 2007.

The dissertation work is devoted to developing intellectual segmentation methods for context image interpretation and evaluating of obtained results via introducing a new metric on partitions.

Exciting modern methods for solving image segmentations tasks and their disadvantages are considered. Necessity of developing a new method of relational clustering segmentation which has advantages due to image special layout considering is grounded.

Spatial layout relationships formalization which allows considering all possible variants of regions positioning for effective partitions and coverings processing is given and using tolerance matrixes for region merging analysis is introduced.

First a model for comparing images, using a new metric on finite partitions, a tool for analysis the partitions obtained on the earlier stages of image processing and for combining segmentations results on interpretation stage, is introduced, grounded and studied. Under that, from one side, a possibility for algorithms objective integral comparison arises, from the other side, introducing operations on partitions creates premises for obtaining the best