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

А.Г. Броневіч, Н.С. Зюзерова

1.Вступ

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

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

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

2. Основні визначення

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

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

якщо точка належить контуру, то (зворотне твердження в загальному випадку невірно);

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

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

Для математичного опису таких вимог введемо в розгляд неорієнтовані граф градієнтного зображення. Вершинами цього графа є ЕІ з координатами , для яких < img src = "http://localhost/uploads/posts/2009-10/1255892809_Modeli_teorii_grafov_dlya_vydeleniya_konturov_po_gradientnomu_izobrazheniyu_13.gif" alt = "" width = "68" height = "20" />. Будемо вважати, що вершини , цього графа є суміжними, якщо знайдуться такі числа , не рівні нулю одночасно, що = . Різні варіанти суміжних вершин показані на рис.1 а), б), в), г).

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

.

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

3. Постановка оптимізаційної завдання

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

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

Введемо числову характеристику = , яку будемо називати вартістю вершини графа градієнтного зображення. Далі розглянемо дві вершини і Vk і припустимо, що ці вершини належать контуру. Очевидно, що будь-який шлях, що з'єднує дані вершини можна розглядати в якості апроксимації даного гіпотетичного контуру. Довжиною (вартістю) шляхи (V1, V2, ..., Vm, Vk) будемо називати суму

.

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

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

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

4. Алгоритм виділення контурного зображення

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

4.1. Визначення і позначення

Gg - граф градієнтного зображення;

Gc - граф контурного зображення;

E (V1) - околиці вершини V1 = (i1 , J1), E (V1) = ;

) - околиця графа контурного зображення, E (G (i)) = .

4.2. Ітераційні кроки алгоритму для зв'язкового графа

Знайти вершину , що має найменшу вартість на графі Gg. Покласти Gс (0) = , тобто на кроці 10 граф Gс (0) складається з однієї вершини

Нехай вже побудований граф G (i) для деякого . Тоді, якщо E (G (ic)) Gg = Gg, то перейти до кроку 4.

Знайти вершину графа Gg, що має найменшу вартість, причому V E (G (ic )). Побудувати шлях, що має найменшу вартість, від вершини до безлічі (графа) G (i). (Це можна зробити за допомогою хвильового алгоритму). Вершини, що належать цьому шляху, необхідно додати до графа G (i). У результаті ми отримаємо граф контурного зображення Gс (i +1) на наступному ітераційне кроці, , перейти до кроку 2.

На цьому ітераційне кроці граф контурного зображення вже буде задовольняти умові 1. Однак, цілком можливо, умова 3 ще не буде виконуватися. Поетму на кроці 40 алгоритму для всіх пар близько розташованих вершин = , = , що задовольняють умові: , необхідно перевірити справедливість нерівності . Якщо ця нерівність не виконується, то для кожної такої пари вершин необхідно побудувати шлях, що має найменшу вартість і з'єднує вершини V1 і V2 , І додати вершини, що належать цьому шляху, до графа Gc.

Список літератури

Spacek L.A. Edge detection of contours and motion detection// Image Vision Compute, vol.4, p.43, 1986.

David L. Coping with Discontinuities in Computer Vision: Their Detection, Classification, and Measurement// IEEE Transactions on Pattern Analysis and Machine Intelligence, vol.13, № 5, 1991.

Petrov M., Kittler J. Optimal Edge Detectors for Ramp Edges// IEEE Transactions on Pattern Analysis and Machine Intelligence, vol.13, № .5, 1991.

Дуда Р., Харт П. Розпізнавання образів та аналіз сцен. - М.: Світ, 1976.