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

87

досліджені методи, при яких граф ділиться на дві зв’язні компоненти.

Отримана при цьому сегментація є бінаризацією зображення [55,60].

Граф G=(U,V) можна поставити у відповідність зображенню, якщо

множина вершин U відповідатиме точкам зображення, а множина ребер

V відповідатиме зв’язкам між сусідніми точками (рис.2.13). Множина

сусідніх точок визначається вибраним типом зв’язності (4,8,16…)

елементів зображення.

Рис.2.13. Формування графу зв’язків, знаходження мінімального

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

Множина U доповнюється двома, так званими, термінальними

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

з’єднана ребром з кожною вершиною графа. Вершини ж графа, що

належать множині U з’єднані між собою ребрами відповідно до

вибраного типу зв’язності. Кожному ребру v∈V приписується деяке

число – вага ребра. Знаходження мінімального перерізу графа означає

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

термінальні вершини повністю відокремленими, тобто між ними не

існувало б шляху. Крім того сума ваг ребер, які становлять цей переріз,

має бути мінімальною серед інших можливих перерізів. Знаходження

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

які менше всього між собою пов’язані, як то об’єкт і фон.

Зосередимо увагу на виборі функцій, які визначають ваги для

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