Зміст

1. Вступ
2. 1. Автоматична сегментація зображень
1. 1.1 Постановка задачі
2. 1.2 Оцінка якості роботи методів автоматичної сегментації
3. 1.3 Методи автоматичної сегментації
1. 1.3.1 Кластеризація простору кольорів
2. 1.3.2 Методи вирощування регіонів, дроблення-злиття
3. 1.3.3 Моделювання зображення Марківським полем
4. 1.3.4 Методи, що грунтуються на операторах виділення країв
5. 1.3.5 Методи теорії графів
6. 1.3.6 Метод Normalized Cut
7. 1.3.7 Метод Nested Cuts
8. 1.3.8 Метод M. Pavan і M. Pelillo
9. 1.3.9 Метод сегментації SWA
10. 1.3.10 Оптимізаційний підхід
11. 1.3.11 Налаштування параметрів
3. 2. Інтерактивна сегментація зображень
1. 2.1 Постановка задачі
2. 2.2 Оцінка якості роботи алгоритмів інтерактивної сегментації
4. Висновки
5. Перелік джерел

Вступ

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

Методи сегментації можна розподілити на два класи: автоматичні - ті, що не потребують взаємодії з користувачем і інтерактивні - ті, що використовують введення користувача безпосередньо у процесі роботи [2],[3].

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

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

1. Автоматична сегментація зображень

1.1 Постановка задачі

Задачі автоматичної сегментації поділяються на два класи:

1. виділення областей зображення з відомими властивостями;
2. розбиття зображення на однорідні області.

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

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

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

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

Рисунок 1 - Вихідне зображення

Рисунок 2 - Варіанти сегментації вихідного зображення

1.2 Оцінка якості роботи методів автоматичної сегментації

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

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

1. однорідність регіонів (однорідність кольору або текстури);
2. несхожість сусідніх регіонів;
3. гладкість межі регіону;
4. незначна кількість дрібних «дірок» усередині регіону.

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

Загальніший підхід до оцінки якості роботи методу, що не враховує конкретного застосування, полягає в тестуванні методів на загальній базі зображень, для яких відома «правильна» сегментація. Наприклад, Berkeley Segmentation Dataset налічує більше 1000 зображень, відсегментованих вручну 30 різними людьми [2].

1.3 Методи автоматичної сегментації

1.3.1 Кластеризація простору кольорів

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

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

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

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

1.3.2 Методи вирощування регіонів, дроблення-злиття

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

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

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

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

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

Конкретні методи відрізняються алгоритмами, що використовуються на етапах дроблення і злиття. Для одержання пересегментаціі зображення використовуються алгоритми k-середніх, watershed, fuzzy expert systems, на другому етапі використовуються алгоритми k-середніх, карти Кохонена, що самоорганізуються, fuzzy expert systems, і т. д. На етапі злиття регіонів використовуються relaxation process, k-середніх, SIDE-рівняння, карти Кохонена, що самоорганізуються, і т. д.

1.3.3 Моделювання зображення Марківським полем

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

1.3.4 Методи, що грунтуються на операторах виділення країв

При даному підході задача сегментації формулюється як задача пошуку меж регіонів. Методи пошуку меж добре розроблені для напівтонових зображень. Напівтонове зображення розглядається як функція двох змінних (x і y), і передбачається, що межі регіонів відповідають максимуму градієнту цієї функції. Для їх пошуку застосовується апарат диференціальної геометрії (у найпростішому випадку це фільтри Roberts, Kirsch, Prewitt, Sobel).

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

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

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

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

1.3.5 Методи теорії графів

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

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

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

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

1.3.6 Метод Normalized Cut

Метод Normalized Cut запропоновано J. Shi, J. Malik (1997). Вводиться нормалізований функціонал якості розрізу таким чином, щоб одночасно максимізувати відмінність точок між класами і мінімізувати відмінності точок всередині класу. Оптимізація нормалізованого функціоналу зводиться до задачі пошуку власних значень матриці попарних відстаней між усіма точками зображення. Для сегментації зображення на дві частини достатньо знайти друге за величиною власне значення такої матриці.

1.3.7 Метод Nested Cuts

Метод Nested Cuts запропонований Olga Veksler (2000). Основний принцип цього методу полягає у відокремленні кожної точки зображення від спеціальної точки за межами зображення розрізом мінімальної вартості. При такому підході зображення ділиться на сегменти що не перетинаються. Можна показати, що величиною сегментів зображення можна керувати, накладаючи обмеження на вартість розрізу.

1.3.8 Метод M. Pavan і M. Pelillo

M. Pavan і M. Pelillo (2003) було запропоновано новий підхід, що грунтується на розрізах графа. Автори вводять таке визначення сегменту, яке дозволяє переформулювати задачу пошуку розрізу на графі як задачу квадратичного програмування. Запропоновано метод розв'язання одержаної задачі, що грунтується на методах еволюційної теорії ігор. Цей підхід також вимагає збереження в пам'яті матриці попарних відстаней, як і метод Normalized Cuts.

1.3.9 Метод сегментації SWA

Метод сегментації SWA (Segmentation by Weighted Aggregation) грунтується на групуванні схожих точок зображення. Основна ідея методу полягає в побудові піраміди зважених графів, кожен з яких отриманий з попереднього шляхом об'єднання схожих вершин.

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

1.3.10 Оптимізаційний підхід

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

1.3.11 Налаштування параметрів

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

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

2. Інтерактивна сегментація зображень

Останнім часом стало ясно, що сучасні автоматичні алгоритми не здатні розв'язувати будь-які задачі сегментації з гарантованим результатом [3]. Більше того, очевидно, найближчим часом такі алгоритми не з'являться. Тому все більшої і більшої уваги приділяють інтерактивній сегментації зображень.

Справжній прорив в цій області стався в 2000 р. - з винаходом Юрієм Бойковым і Мари-Пьер Джоллі алгоритму GraphCut. Цей алгоритм де-факто став еталонним. Велика частина нових алгоритмів інтерактивної сегментації зображень є розвитком алгоритму GraphCut. Інші алгоритми порівнюються, в першу чергу, з ним. Розрізи графів, на яких спирається GraphCut, стали активно використовуватися і в інших областях комп'ютерного зору: сегментації відео, стичинзі, стерео-реконструкції [1],[3],[5].

Інтерактивна сегментація зображень активно використовується для редагування зображень, аналізу медичних даних, а також є складовою частиною багатьох алгоритмів комп'ютерного зору [10],[11],[12].

2.1 Постановка задачі

В інтерактивній сегментації зображень зазвичай розглядається задача розбиття тільки на дві області - об'єкт і фон (розбиття на більшу кількість областей здійснюється багатократним розбиттям на дві області) [3].

На вхід алгоритм отримує:

1. початкове зображення;
2. якусь додаткову інформацію від користувача:
   1. обмеження на те, що деякі конкретні пікселі обов'язково мають належати об'єкту (фону);
   2. обмежуючий прямокутник навколо об'єкту;
   3. приблизну межу об'єкту.

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

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

Рисунок 3 - Приклад інтерактивної сегментації зображення. (Анімація - 4 кадра)

2.2 Оцінка якості роботи алгоритмів інтерактивної сегментації

В автоматичній сегментації, для побудови міри якості розбиття, використовуються припущення про те, що схожість кольору пікселів, текстури усередині одного об'єкту має бути максимальною, а між об'єктами - мінімальною [2]. Але в інтерактивній сегментації користувач може робити скільки завгодно багато підказок алгоритму - додавати нові обмеження, уточнювати вхідну інформацію до тих пір, поки не отримає очікуваного результату. Зрозуміло, що на границі, коли користувач явно вкаже щодо кожного пікселю, до якої області він має належати, він завжди отримає ідеальну сегментацію. Можна було б оцінювати якість сегментації за одних і тих самих підказок, але різні алгоритми одержують різну вхідну інформацію від користувача [3],[8],[9].

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

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

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

Висновки

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

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

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

Перелік джерел

1. Конушин А.С. Материалы курса лекций лаборатории компьютерной графики при ВМК МГУ.
   // http://courses.graphicon.ru/files/courses/vision2/2012/lectures/cv2012_14_segmentation.pdf
2. Вежневец А. Баринова О. Методы сегментации изображений: автоматическая сегментация.
   // http://cgm.computergraphics.ru/content/view/147
3. Конушин В. Вежневец В. Методы сегментации изображений: интерактивная сегментация.
   // http://cgm.computergraphics.ru/content/view/172
4. Вежневец А. Выделение связных областей в цветных и полутоновых изображениях.
   // http://cgm.computergraphics.ru/content/view/53
5. Фурман Я.А. Введение в контурный анализ. // ФИЗМАТЛИТ 2003, 592 стр.
6. Шлезингер М. И. Математические средства обработки изображений. // Наукова думка, 1989, 196 стр.
7. Шлезингер М. И. Теоретические и прикладные вопросы распознавания изображений. // Издательство института кибернетики АН УССР, 1991, 86 стр.
8. Rafael Ceferino Gonzalez, Richard Eugene Woods. Digital Image Processing. // Prentice Hall, 2008, 954 p.
9. Bernd Jähne. Digital Image Processing. // Springer, 2005, 607 p.
10. David Salomon. Data Compression. // Springer, 2007, 1092 p.
11. Paragios N., Chen Y., Faugeras O. Handbook of Mathematical Models in Computer Vision. // Springer, 2010, 605 p.
12. Francus P. Image Analysis, Sediments and Paleoenvironments. // Springer, 2004, 330 p.