Національна академія наук України

Міністерство освіти і науки України

Міжнародний науково-навчальний центр

інформаційних технологій та систем

Ковтун Іван Володимирович

УДК 004.932[519.157+519.854]

СЕГМЕНТАЦІЯ ЗОБРАЖЕНЬ НА ОСНОВІ

ДОСТАТНІХ УМОВ ОПТИМАЛЬНОСТІ В NP-ПОВНИХ

КЛАСАХ ЗАДАЧ СТРУКТУРНОЇ РОЗМІТКИ

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

Автореферат

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

Київ - 2005

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

Робота виконана в Міжнародному науково-навчальному центрі інформаційних технологій і систем, НАН України та МОН України.

Наукові керівники: | Доктор фізико-математичних наук, професор
Шлезінгер Михайло Іванович, Міжнародний науково-навчальний центр інформаційних технологій та систем, головний науковий співробітник.

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

Офіційні опоненти: |

Доктор технічних наук, професор
Литвинов Віталій Васильович, Інститут проблем математичних машин і систем НАН України, завідуючий відділом.

Кандидат фізико-математичних наук Стецюк Петро Іванович, Інститут Кібернетики ім. В.М. Глушкова НАН України, старший науковий співробітник.

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

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

ахист відбудеться 12.05.2005 року о 14 годині на засіданні спеціалізованої вченої ради Д 26.171.01 в Міжнародному науково-навчальному центрі інформаційних технологій та систем НАН України та МОН України за адресою:

03680, Київ, проспект Академіка Глушкова, 40.

дисертацією можна ознайомитися в бібліотеці Міжнародного науково-навчального центру інформаційних технологій та систем НАН України та МОН України: 03680, Київ, проспект Академіка Глушкова, 40.

Автореферат розісланий 08.04. 2005 р.

Вчений секретар спеціалізованої вченої ради РЕВЕНКО В.Л.

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

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

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

В цьому напрямку відомі роботи Бойкова, Гімельфарба, братів Джименів, Забіха, Ішикави, Ковалевського, Колмогорова, Розенфельда, Флаха, Хуммела, Цукера, Шлезінгера, та ін.

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

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

Таким чином, постає нагальна потреба у

·

·

·

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

Проведені в дисертації дослідження є складовою частиною науково-дослідної роботи “Дослідження структурних та статистичних моделей зображень і розробка оптимізаційних методів їх обробки та розпізнавання” за завданням Національної Академії наук України, 2001-2003 рр. (№ держреєстрації 0101U002683), яка виконувалась у відповідності з планами наукових досліджень відділу № 120 “Розпізнавання зображень” Міжнародного науково-навчального центру інформаційних технологій та систем. Робота виконувалась також за підтримки гранту International Quality Network Міністерства вищої освіти Німеччини, та при виконанні наступних контрактів:

· "Сегментація багатосенсорних зображень на основі марковських випадкових полів" на замовлення німецької фірми Jena-Optronik GmbH, 1999-2000 рр.;

· "Покращена текстурна сегментація зображень на основі марковських випадкових полів" на замовлення німецької фірми Jena-Optronik GmbH, 2000-2001 рр.;

· "Апаратно-програмний комплекс для просторової реконструкції тривимірних сцен за стереопарою зображень (обличчя, промислові споруди, ландшафти)" в рамках Державної науково-технічної програми "Образний комп'ютер", 2001 р. (№ держреєстрації 0204U000172),

в яких здобувач був відповідальним виконавцем.

Мета і задачі дослідження. Метою дисертації є:

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

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

Для досягнення поставленої мети в дисертації були розв’язані наступні задачі:

· узагальнено існуючий і розроблено новий методи розв’язання задач розмітки великої розмірності;

· вперше розроблено методи спрощення задач розмітки загального вигляду;

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

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

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

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

Об’єкт дослідження. Задачі структурної розмітки зображень.

Предмет дослідження.

· Оптимізаційні задачі, що виникають при пошуку найімовірніших реалізацій прихованих марковських полів;

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

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

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

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

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

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

3. Узагальнено для розв’язання супермодулярних задач розмітки великої розмірності метод “Coarse to Fine Dynamic Programming” (Raphael C. Coarse to fine dynamic programming// IEEE Trans. on PAMI. – 2001. – Vol. 23, no. 12. – Pp. 1379-1390.), що використовувався раніше для розв’язання задач динамічного програмування великої розмірності.

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

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

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

Наведені в роботі приклади показують, що використання допоміжних супермодулярних (max,+) задач дозволяє визначити значення оптимальної розмітки початкової задачі в деяких пікселах поля зору (іноді більше ніж в 90% пікселів).

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

Особистий внесок здобувача. Всі основні наукові результати, що виносяться на захист дисертації, отримані здобувачем самостійно, в тому числі:

· методи розв’язку супермодулярних задач розмітки великої розмірності;

· методи знаходження частини оптимального розв’язку задачі розмітки в загальному вигляді;

· статистична модель зображення, що складається з декількох текстур;

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

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

Всі опубліковані статті написані автором самостійно, без співавторів.

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

· 25th Pattern Recognition Symposium “DAGM 2003” (Magdeburg, Germany), на якій робота дисертанта під назвою “Partial optimal labeling search for a NP-hard subclass of (max,+) problems” зайняла призове місце;

· Одинадцятій міжнародній конференції по автоматичному управлінню „Автоматика–2004” (м. Київ, Україна);

· Сьомій всеукраїнській міжнародній конференції „Оброблення сигналів і зображень та розпізнавання образів – УкрОбраз’2004” (м. Київ, Україна).

Результати дисертації неодноразово доповідалися на семінарах в Міжнародному науково-навчальному центрі інформаційних технологій та систем НАНУ та МОН України, в Інституті штучного інтелекту Дрезденського технічного університету (м. Дрезден, Німеччина), в Центрі машинного бачення Чеського технічного університету (м. Прага, Чехія), та на постійнодіючому науковому семінарі Державної науково-технічної програми “Образний комп’ютер” (МННЦ ІТС, м. Київ, Україна).

Публікації. За темою дисертації опубліковано 7 наукових праць, три з яких – статті у наукових фахових журналах, затверджених ВАК України, три статті опубліковано в збірниках праць конференцій, крім того, результати дисертації викладено в технічному звіті (Technical report ISSN 1430-211X, TUD-FI03-04).

Структура та обсяг роботи. Дисертація складається із вступу, п’яти розділів, висновків, списку використаних джерел із 43 найменувань (5 сторінок) та одного додатку (3 сторінки). Робота містить 12 рисунків. Загальний обсяг дисертації складає 114 сторінок. Повний обсяг дисертації (включаючи додаток, список використаних джерел та рисунки, які повністю займають площину сторінки) складає 135 сторінок.

ЗМІСТ РОБОТИ

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

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

Необхідні означення. Точне формулювання результатів другого і подальших розділів вимагає введення наступних означень.

Поле зору – скінчена множина , її елементи називатимемо пікселами.

Множина позначок – скінчена множина .

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

Структура поля зору – множина підмножин пікселів поля зору.

Якість розмітки задається функцією , що визначена на множині всіх розміток наступним чином:

,

де – звуження розмітки на підмножину пікселів;–

функція, що співставляє число кожній розмітці множини пікселів.

Задача розмітки або (max,+) задача – це оптимізаційна задача знаходження розмітки з найкращою якістю:

.

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

Задачу розмітки називатимемо супермодулярною (max,+) задачею, якщо для довільної пари розміток виконується нерівність:

.

Відомо, що супермодулярні задачі розмітки, до яких можуть бути зведені задачі текстурної сегментації на дві текстури і задачі стереозору, є поліноміально розв’язними. Задача текстурної сегментації на три і більше текстури не є супермодулярною. Більше того, доведено, що вона є NP-повною. Тому один з напрямків досліджень дисертаційної роботи полягав у дослідженні (max,+) задач довільного вигляду, щоб знайти практично прийнятні методи текстурної сегментації і у випадку, коли кількість текстур більше двох.

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

В другому розділі “Оптимізаційні задачі розмітки” описано запропоновані методи вирішення супермодулярних задач розмітки великої розмірності, а також методи визначення частини оптимальної розмітки довільної (max,+) задачі.

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

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

,

розв’язок якої шукається лише серед тих розміток, які лежать не нижче розмітки .

2. Для розв’язання супермодулярних (max,+) задач великої розмірності в дисертаційній роботі узагальнено метод “Coarse to Fine Dynamic Programming” (Raphael C. Coarse to fine dynamic programming// IEEE Trans. on PAMI. – 2001. – Vol. 23, no. 12. – Pp. 1379-1390.), що використовувався раніше для розв’язання задач динамічного програмування великої розмірності.

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

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

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

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

3. Запропоновано концептуально новий підхід до розв’язання (max,+) задач довільного вигляду. Підхід полягає у використанні допоміжних супермодулярних (max,+) задач:

нехай – оптимальна розмітка початкової задачі, а саме, .

Називатимемо супермодулярну (max,+) задачу допоміжною для початкової (max,+) задачі, якщо її найнижчий розв’язок задовольняє умову:.

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

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

Теорема (Достатні умови спрощення довільної (max,+) задачі). Якщо для найнижчого розв’язку допоміжної задачі і для довільної розмітки справедлива нерівність

,

то довільний розв’язок початкової задачі задовольняє умову: .

Наслідок (Достатні умови оптимальності (max,+) задачі). Нехай для деякої початкової (max,+) задачі існує супермодулярна задача, яка є допоміжною і має розв’язок . Нехай для деякого піксела множина складається лише з одного елемента . Тоді позначка у розв’язку початкової задачі у пікселі дорівнює .

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

де через позначено множину можливих значень найнижчої оптимальної розмітки допоміжної задачі.

Загальний алгоритм побудови допоміжних задач полягає у наступному:

1. Виберемо для кожного елемента за множину порожню множину.

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

3. Розв’яжемо допоміжну задачу і знайдемо її найнижчий розв’язок.

4. Якщо для всіх і для всіх розмітка задовольняє записану вище систему нерівностей при, то

· побудована допоміжна задача задовольняє вимогам теореми про достатні умови спрощення довільної (max,+) задачі;

· довільний розв’язок початкової задачі задовольняє умову ;

· алгоритм завершує свою роботу.

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

В третьому розділі “Текстурна сегментація зображень на основі марковських випадкових полів” міститься:

· опис нововведеної моделі текстурного зображення;

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

· дослідження можливості розв’язання задач з цього класу.

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

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

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

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

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

1)

2)

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

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

Рисунок 2 демонструє один з експериментів текстурної сегментації модельних зображень, складених з трьох текстур. На рисунках 2(а), 2(б), 2(в) показані згенеровані приклади цих трьох текстур. Зауважимо, що в даному прикладі згенеровані текстури описуються марковськими випадковими полями, налагодженими за прикладами реальних текстур. Сама сегментація також є випадковою реалізацією певного марковського поля. Вона показана на рис. 2(д) і відома експериментатору, завдяки чому можна оцінити ступінь похибки того чи іншого алгоритму. Рисунок 2(е) містить розв’язок байєсівської задачі. Кількість невірно просегментованих пікселей становить 1,35% від загальної кількості пікселей поля зору. Рисунок 2(ж) містить знайдену частину оптимальної розмітки (max,+) задачі. Невідомою залишилось 3,24% оптимальної розмітки, а знайдена частина містить 0,97% помилок. Нарешті рисунок 2(з) містить отриманий за допомогою алгоритму (Boykov., Veksler O., Zabih R. Fast approximate energy minimization via graph cuts // IEEE Trans. on PAMI. – 2001. – Vol. 23, no. 11. – Pp. 1222-1239.) наближений розв’язок відповідної (max,+) задачі в тих пікселах, які на попередньому рисунку помічені чорним кольором. Кількість невірно просегментованих пікселей становить 1,74%.

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

Наступний експеримент показує результат вирішення супермодулярної (max,+) задачі великої розмірності. Задача полягає у відновленні тривимірної поверхні за стереопарою зображень. На рис. 5(а) і 5(б) зображено вихідні дані такої задачі – стереопару зображень, розміром пікселей. Кількість позначок відповідної (max,+) задачі становить . Як наслідок, супермодулярна задача розмітки потребує щонайменше 8 Гб оперативної пам’яті для свого розв’язання. Використовуючи наведений в дисертації алгоритм, розв’язок цієї задачі, зображений на рис. 5(в), було отримано із обмеженням оперативної пам’яті в 400 Мб.

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

(а) (б) (в)

(г) (д)

(е) (ж) (з)

Рис. 2. Експеримент із трьома штучно-згенерованими текстурами:

(а), (б), (в) – згенеровані зображенні першої, другої та третьої текстур;

(г) – згенероване зображення сегментації;

(д) – текстурне зображення, отримане із зображень (а), (б), (в) та (г);

(е) – розв’язок байєсівської задачі, 1,35% помилок;

(ж) – знайдена частина оптимальної розмітки (max,+) задачі, 3,24% оптимальної розмітки залишилось невідомою, знайдена частина містить 0,97% помилок;

(з) – знайдений наближений розв’язок (max,+) задачі, 1,74% помилок.

(а) (б)

(в) (г)

Рис. 3. Текстурна сегментація аерофотознімку,

(а) – вхідне текстурне зображення;

(б) – розв’язок байєсівської задачі, де чорним кольором позначені ті 2,27% пікселів, в яких ймовірність кожної позначки менша за 0,95%;

(в) – знайдені 97,66% оптимальної розмітки (max,+) задачі;

(г) – знайдений за допомогою алгоритму (Boykov., Veksler O., Zabih R. Fast approximate energy minimization via graph cuts // IEEE Trans. on PAMI. – 2001. – Vol. 23, no. 11. – Pp. 1222-1239.) наближений розв’язок (max,+) задачі.

(а)

(б) (в)

Рис. 4. Текстурна сегментація аерофотознімку,

(а) – вхідне зображення;

(б) – знайдені 95% оптимальної розмітки (max,+) задачі;

(в) – знайдений за допомогою алгоритму (див. посилання в попередньому прикладі) наближений розв’язок (max,+) задачі.

(а) (б)

(в)

Рис. 5. Розв’язок задачі відновлення поверхні за двома знімками як

супермодулярної (max,+) задачі великої розмірності:

(а),(б) – лівий та правий знімки стереопари відповідно;

(в) – відновлена поверхня, показана за допомогою яскравості (яскравіші точки ближче до спостерігача).

Додаток А містить довідки про впровадження результатів дисертаційної роботи на підприємстві Jena-Optronik GmbH (Німеччина) та про використання результатів дисертаційної роботи при виконанні контрактів у Міжнародному науково-навчальному центрі інформаційних технологій та систем НАН України та МОН України.

ОСНОВНІ РЕЗУЛЬТАТИ РОБОТИ І ВИСНОВКИ

Сукупність отриманих в дисертації результатів вирішує актуальну науково-прикладну задачу сегментації зображень на основі достатніх умов оптимальності в NP-повних класах задач структурної розмітки, а саме:

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

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

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

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

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

ПУБЛІКАЦІЇ ЗА ТЕМОЮ ДИСЕРТАЦІЇ

1. Ковтун И. Текстурная сегментация изображений на основании марковских случайных полей // УСиМ. – 2003. – № 4. – С. 46-55.

2. Ковтун И. Поиск части оптимальной разметки некоторого NP-полного подкласса (max,+) задач // УСиМ. – 2003. – № 6. – С. 33-38.

3. Ковтун И. Технология текстурной сегментации изображений на основании марковских случайных полей и решения (max,+) задач // УСиМ. – 2004. – № 2. – С. 61-66.

4. Kovtun I. Partial optimal labeling search for a NP-hard subclass of (max,+) problems // Pattern Recognition / Під ред. G. K. Bernd Michaelis. – T.2781 з LNCS. – Springer, September 2003. – pp. 402-409.

5. Ковтун І. Пошук частини оптимального розв’язку в задачах розмітки //
Автоматика-2004, Матеріали 11-ї конференції по автоматичному управлінню / Під ред. В. Кунцевич, О. Куржанський, Ф. Кирилова та ін. – Т. 1. – Вересень 2004. – С. .

6. Ковтун І. Знаходження частини оптимального розв'язку довільної задачі розмітки за допомогою методів вирішення супермодулярних (max,+) задач // Праці 7-ї Всеукраїнської міжнародної конференції “Оброблення сигналів і зображень та розпізнавання образів” – УкОбраз’2004, Київ / Під ред. Т. Вінцюк. – Жовтень 2004. – С. 163-168.

7. Kovtun I. Texture segmentation of images on the basis of markov random fields: Tech. rep.: TUD-FI03, 05 2003.

АНОТАЦІЯ

Ковтун І. В. Сегментація зображень на основі достатніх умов оптимальності в NP-повних класах задач структурної розмітки. – Рукопис.

Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 05.13.23 – системи та засоби штучного інтелекту. – Міжнародний науково-навчальний центр інформаційних технологій та систем, НАН України та МОН України, Київ, 2004.

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

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

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

АННОТАЦИЯ

Ковтун И. В. Сегментация изображений на основании достаточных условий оптимальности в NP-полных классах задач структурной разметки. – Рукопись.

Диссертация на соискание ученой степени кандидата технических наук по специальности 05.13.23 – системы и средства искусственного интеллекта. – Международный научно-учебный центр информационных технологий и систем, НАН Украины и МОН Украины, Киев, 2004.

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

В работе для решения супермодулярных задач разметки большой размерности применен метод “Coarse to fine dynamic programming” (Raphael. Coarse to fine dynamic programming// IEEE Trans. on PAMI. – 2001. – Vol. 23, no. 12. – Pp. 1379-1390.), использованный ранее для решения задач динамического программирования большой размерности. Кроме этого, для решения задач разметки большой размерности разработан и новый метод, основанный на решении вспомогательных супермодулярных задач разметки меньшей размерности.

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

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

ABSTRACT

Kovtun I.V. Image segmentation based on sufficient conditions for optimality in NP-complete classes of structural labeling problems. – Manuscript.

Dissertation for scientific degree of candidate of technical sciences on specialty 05.13.23 – systems and tools of artificial intelligence. – International Research and Training Center for Information Technologies and Systems, National Academy of Sciences and Ministry of Science and Formations of Ukraine, Kyiv, 2004.

The dissertation is devoted to solving the problem of image segmentation. A special attention is given to the investigation of the possibility to the exact solving of the appropriate optimization problem, which is also called labeling problem. The labeling problem is NP-complete in general case. It is proposed to search for a part of the exact solution for such a problem. The appropriate sufficient conditions are formulated.

The new model of the textured image was also proposed. The Bayesian recognition problems were considered for different penalty functions on the basis of this model. The method of approximate solution of the problem was proposed for additive penalty function.

Key words: texture segmentation of images, labeling problem, supermodular function optimization, Markov Random Fields, partial optimal labeling search