Алгоритм случайного блуждания

Алгоритм случайного блуждания — это алгоритм сегментации изображений . В первом описании алгоритма пользователь в интерактивном режиме помечает небольшое количество пикселей известными метками (называемыми исходными), например «объект» и «фон». Предполагается, что каждый из немаркированных пикселей высвобождает случайного блуждающего агента, и вычисляется вероятность того, что случайный блуждающий элемент каждого пикселя сначала достигнет начального числа, несущего каждую метку, т. е. если пользователь размещает K начальных чисел, каждое с различной меткой, тогда необходимо вычислить для каждого пикселя вероятность того, что случайный пешеход, покинувший пиксель, первым достигнет каждого начального числа. Эти вероятности могут быть определены аналитически путем решения системы линейных уравнений. После вычисления этих вероятностей для каждого пикселя пикселю присваивается метка, для которой с наибольшей вероятностью будет отправлен случайный блуждающий объект. Изображение моделируется как граф , в котором каждый пиксель соответствует узлу, который соединен с соседними пикселями ребрами, а ребра взвешиваются, чтобы отразить сходство между пикселями. Следовательно, случайное блуждание происходит на взвешенном графе (введение в случайные блуждания на графах см. в Дойле и Снелле). ).

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

Алгоритм был первоначально опубликован Лео Грейди в качестве доклада на конференции. а затем в виде журнальной статьи.

Математика

Хотя алгоритм был описан в терминах случайных блужданий , вероятность того, что каждый узел отправит случайного блуждающего человека к начальным числам, может быть рассчитана аналитически путем решения разреженной положительно определенной системы линейных уравнений с матрицей Лапласа графа , которую мы можем представить с помощью переменная $L$. Было показано, что алгоритм применим к произвольному числу меток (объектов), но здесь изложение представлено в виде двух меток (для простоты изложения).

Предположим, что изображение представлено графом , в котором каждый узел $v_{i}$ связанный с пикселем и каждым краем $e_{ij}$ соединение соседних пикселей $v_{i}$ и $v_{j}$. Веса ребер используются для кодирования сходства узлов, которое может быть получено из различий в интенсивности изображения, цвете, текстуре или любых других значимых характеристиках. Например, используя интенсивность изображения $g_{i}$ в узле $v_{i}$, обычно используется функция взвешивания ребер

$w_{ij}=\exp {\left(-\beta (g_{i}-g_{j})^{2}\right)}.$

Узлы, ребра и веса затем можно использовать для построения матрицы Лапласа графа .

Алгоритм случайного блуждания оптимизирует энергию

$Q(x)=x^{T}Lx=\sum _{e_{ij}}w_{ij}\left(x_{i}-x_{j}\right)^{2}$

где $x_{i}$ представляет переменную с действительным знаком, связанную с каждым узлом графа, и оптимизация ограничена $x_{i}=1$ для $v_{i}\in F$ и $x_{i}=0$ для $v_{i}\in B$, где $F$ и $B$ представляют собой наборы семян переднего плана и фона соответственно. Если мы позволим $S$ представляют собой набор узлов, которые засеяны (т. е. $S=F\cup B$) и ${\overline {S}}$ представляют собой набор незаполненных узлов (т.е. $S\cup {\overline {S}}=V$ где $V$ — множество всех узлов), то оптимум задачи минимизации энергии определяется решением

$L_{{\overline {S}},{\overline {S}}}x_{\overline {S}}=-L_{{\overline {S}},S}x_{S},$

где нижние индексы используются для обозначения части матрицы Лапласа графа $L$ индексируются соответствующими наборами.

Чтобы включить в алгоритм условия правдоподобия (унарные), это было показано на рис. что можно оптимизировать энергию

$Q(x)=x^{T}Lx+\gamma \left((1-x)^{T}F(1-x)+x^{T}Bx\right)=\sum _{e_{ij}}w_{ij}\left(x_{i}-x_{j}\right)^{2}+\gamma \left(\sum _{v_{i}}f_{i}(1-x_{i})^{2}+\sum _{v_{i}}b_{i}x_{i}^{2}\right),$

для положительных диагональных матриц $F$ и $B$. Оптимизация этой энергии приводит к системе линейных уравнений

$\left(L_{{\overline {S}},{\overline {S}}}+\gamma F_{{\overline {S}},{\overline {S}}}+\gamma B_{{\overline {S}},{\overline {S}}}\right)x_{\overline {S}}=-L_{{\overline {S}},S}x_{S}-\gamma F_{{\overline {S}},{\overline {S}}}.$

Набор начальных узлов, $S$, в этом случае может быть пустым (т. е. ${\overline {S}}=V$), но наличие положительных диагональных матриц позволяет найти единственное решение этой линейной системы.

Например, если термины правдоподобия/унарные используются для включения цветовой модели объекта, то $f_{i}$ будет представлять уверенность в том, что цвет в узле $v_{i}$ будет принадлежать объекту (т. е. большее значение $f_{i}$ указывает на большую уверенность в том, что $v_{i}$ принадлежал метке объекта) и $b_{i}$ будет представлять уверенность в том, что цвет в узле $v_{i}$ принадлежит фону.

Интерпретации алгоритмов

Алгоритм случайного блуждающего изначально был основан на маркировке пикселя как объекта/фона на основе вероятности того, что случайный блуждающий объект, упавший в пиксель, сначала достигнет начального значения объекта (переднего плана) или начального числа фонового изображения. Однако существует несколько других интерпретаций этого же алгоритма.

Интерпретации теории цепей

Существуют хорошо известные связи между теорией электрических цепей и случайными блужданиями по графам. Следовательно, алгоритм случайного блуждания имеет две разные интерпретации с точки зрения электрической цепи. В обоих случаях граф рассматривается как электрическая цепь, в которой каждое ребро заменено пассивным линейным резистором . Сопротивление, $r_{ij}$, связанный с краем $e_{ij}$ устанавливается равным $r_{ij}={\frac {1}{w_{ij}}}$ (т.е. вес края равен электропроводности ).

В первой интерпретации каждый узел связан с фоновым начальным значением, $v_{i}\in B$, привязан непосредственно к земле, в то время как каждый узел связан с начальным объектом/передним планом, $v_{i}\in F$ подключается к постоянного тока, источнику идеального напряжения подключенному к земле (т. е. для установления единичного потенциала на каждом $v_{i}\in F$). Стационарные потенциалы электрической цепи, установленные в каждом узле этой конфигурацией схемы, будут точно равны вероятностям случайного блуждания. В частности, электрический потенциал, $x_{i}$ в узле $v_{i}$ будет равна вероятности того, что случайный ходок упал в узел $v_{i}$ достигнет узла объекта/переднего плана раньше, чем достигнет узла фона.

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

Расширения

Традиционный алгоритм случайного блуждания, описанный выше, был расширен несколькими способами:

• Случайные блуждания с перезапуском
• Альфа матирование
• Выбор порога
• Мягкие входы
• Запуск на предварительно сегментированном изображении
• Масштабировать случайное блуждание в пространстве
• Быстрый случайный ходок с использованием автономных предварительных вычислений
• Обобщенные случайные блуждания, обеспечивающие гибкие функции совместимости.
• Мощные водоразделы, объединяющие разрезы графа, случайный блуждающий объект и кратчайший путь
• Водоразделы случайных блуждающих
• Многомерное гауссово условное случайное поле

Приложения

Помимо сегментации изображений, алгоритм случайного блуждания или его расширения дополнительно применялись для решения нескольких задач компьютерного зрения и графики:

• Раскрашивание изображения
• Интерактивное ротоскопирование
• Сегментация медицинских изображений
• Объединение нескольких сегментаций
• Сегментация сетки
• Шумоподавление сетки
• Редактирование сегментации
• Устранение теней
• одномерного Стереосопоставление (т.е. регистрация изображения )
• Слияние изображений

Внешние ссылки

• Код Matlab, реализующий оригинальный алгоритм случайного блуждания
• Код Matlab, реализующий алгоритм случайного блуждания с предварительным вычислением
• Реализация исходного алгоритма случайного блуждания на Python. Архивировано 14 октября 2012 г. на Wayback Machine в наборе инструментов обработки изображений scikit-image.