Инициализирующий график для алгоритма Push-Relabel

Question

Учитывая алгоритм Cut-Relabel Graph Cut, описанный в this article Я хочу выполнить сегментацию двоичного изображения. Мой вопрос касается инициализации графика.

При представлении изображения в виде графика с решетчатой ​​структурой (MRF) обычно формулируется задача в соответствии с стандартной функцией унарных и попарных членов энергии в соответствии с разделом 3, уравнение 1 в this paper, где унарный термин представляет собой энергию данных и гладкость гладкомерных термов в некоторой окрестности.

Я изо всех сил пытаюсь установить связь между этой формулой оптимизации MRF и формулировкой алгоритма максимального потока в связанной статье. Насколько я понимаю, возможности между соседними узлами могут быть представлены некоторой функцией расстояния (на основе пространственных расстояний и значений интенсивности), например, раздел 2, уравнение 7 в this paper. Однако неясно, как можно было бы включить предварительные знания в инициализацию графика, например, начальные распределения для начальных точек.

На более высоком уровне, учитывая изображение с некоторыми помеченными семенными точками, относящимися к фону или классам объектов, как инициализировать график потока таким образом, что max-flow может использоваться для выполнения двоичной сегментации?

Answer 1

Граф имеет вершину для каждого пикселя, но также имеет вершинную вершину и вершину стока, ни одна из которых не соответствует пикселю. Одна возможная интерпретация этих специальных вершин заключается в том, что источник представляет сегмент «переднего плана», а приемник представляет собой «фоновый» сегмент.

Емкость дуги от источника до вершины пикселя является логарифмической вероятностью того, что этот пиксель находится на переднем плане. Емкость дуги от вершины пикселя до приемника является логарифмической вероятностью того, что этот пиксель находится в фоновом режиме. Емкость дуги между вершинами пикселей представляет логарифмическую вероятность того, что пиксели находятся как на переднем плане, так и в фоновом режиме. Это убеждение должно быть выше, когда пиксели близки друг к другу и когда пиксели имеют одинаковые цвета.