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

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

1.Вступ

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

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

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

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

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

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

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

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

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

Для математичного опису таких вимог введемо в розгляд неорієнтований граф градієнтного зображення. Вершинами цього графа є ЕІ з координатами , Для яких . Будемо вважати, що вершини , цього графа є суміжними, якщо знайдуться такі числа , Не рівні нулю одночасно, що = . Різні варіанти суміжних вершин показані на рис.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 LA 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.