Изменения

v[i] - список вершин, которые были сжаты в i-тую(сначала заполняется i);

for i = 1..n-1

for j = 1..n-1

if (j != n-1)

пересчитываем связность w[i] для остальных вершин;

prev = s;

minCost = w[s];

minCut = v[s];

return minCut - список вершин в минимальном разрезе;

Изображение представляется в виде взвешенного графа, вершинами которого являются точки изображения(скорее всего pixels, но может и области чуть больше, от этого зависит качество сегментации, а также скорость ее построения). Вес ребра представляет отражает "разницу" между точками(расстояние по некоторой введенной метрике). Разбиение изображения на однородные области сводится к задаче поиска минимального разреза в графе. Специально для такого рода задач был предложен метод нахождения разреза минимальной стоимости Normalized Cut(J. Shi, J. Malik (1997))

== Источники ==