Page 57 - Microsoft Word - Дисертація.docx

57

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

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

визначенні, які підмножини вузлів і ребер, відповідають однорідним

областям на зображенні. Ключовим принципом тут є те, що вузли, що

належать до однієї підмножини або групи повинні бути з'єднані ребрами

з великими вагами, в той час як вузли, які з'єднані слабкими ребрами,

ймовірно, належать до різних підмножин [61].

Для розбиття вершин графа на підмножини необхідно розв’язати

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

двовимірного зображення обчислювальна складність методів

2
знаходження оптимального розв’язку є О(N logN), де N – кількість
вершин графа, у випадку тримірних зображень поліноміального

алгоритму для її вирішення не існує [62]. У зв’язку із великою

обчислювальною складністю важливе значення має визначення вагових

коефіцієнтів ребер графа, які б дозволили найбільш правдоподібно

відобразити степінь подібності елементів зображення. Традиційно цю

функцію вибирають у такому вигляді [63,64]:

I ( p − I q ) 2 1
( u q , p ) λ= I exp(− )⋅ , (1.1)
2σ 2 dist ( q , p )

де I , I – яскравості у точках p, q відповідно, коефіцієнт σ
q
p
експериментально і, як правило, залежить від властивостей зображення,

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

табл. 1.1

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

полягають у збільшенні виду зв’язності між пікселами з 4-х або 8-ми до

16-ти і більше, а також переходу від Евклідової метрики до метрики

Рімана або Фінслера [65, 66]. Це, в окремих випадках, дає можливість