Поиск хорошего соседа

Чтобы найти лучшего соседа, мы проверяем каждую метку по отдельности. Начнем с метки a. Утверждается, что лучшее переназначение, в котором узлы могут изменить свои метки на a, может быть найдено посредством вычисления минимального разреза.

Построение графа минимального разреза G’ = (V’, E’) аналогично вычислению минимального разреза, разработанному для бинарной сегментации изображений.

Тогда мы определили источник s и сток t для представления двух меток. Здесь мы тоже введем источник и сток, но источник s будет представлять метку a, а сток t будет фактически представлять другой вариант, имеющийся у узлов, а именно сохранение их исходных меток.

Идея заключается в том, чтобы найти минимальный разрез в G’ и заменить метки всех узлов на стороне s разреза меткой a, тогда как все узлы на стороне t сохранят свои исходные метки.

Ребро (i, s) будет иметь пропускную способность ci( f (i)), если f (i) ≠ a, или она будет выражаться очень большим числом M (или +∞), если f (i) = a. Разрезание ребра (i, t) помещает узел i на сторону стока, а следовательно, соответствует сохранению узлом i исходной метки f (i) ≠ a. Большая пропускная способность M предотвращает размещение узлов i с f (i) = a на стороне стока.

В построении для задачи с двумя метками мы добавляли ребра между узлами V и использовали штрафы за разделение как пропускные способности. Этот способ хорошо работает для узлов, разделенных разрезом, или узлов на стороне источника, одновременно имеющих метку a.

Но если i и j находятся на стороне стока, то соединяющее их ребро еще не разрезано, но i и j разделены, если f (i) ≠ f ( j).

Чтобы решить эту проблему, мы дополним построение G’ следующим образом. Для ребра (i, j), если f (i) = f ( j) или один из узлов i или j имеет метку a, в E’ добавляется ребро (i, j) с пропускной способностью pij.

Для ребер e = (i, j), у которых f (i) ≠ f ( j) и ни один узел не имеет метку a, чтобы правильно закодировать через граф G’, что i и j остаются разделенными, даже если находятся на стороне стока, придется действовать иначе.

Для каждого такого ребра e в V’ добавляется дополнительный узел e, соответствующий ребру e, и ребра (i, e), (e, j) и (e, s) с пропускной способностью pij. Эти ребра изображены на рис. 12.7.