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

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

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

Алгоритм был первоначально опубликован Лео Грэди как доклад на конференции ^[4], а затем как статья в журнале. ^[1]

Математика [ править ]

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

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

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

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

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

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

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

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

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

В ^[3] было показано, что для включения в алгоритм вероятностных (унарных) членов можно оптимизировать энергию

${\displaystyle 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),}$

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

${\displaystyle \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}}}.}$

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

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

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

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

Интерпретации теории цепей [ править ]

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

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

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

Расширения [ править ]

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

• Случайные блуждания с перезапуском ^[6]
• Альфа-матирование ^[7]
• Выбор порога ^[8]
• Мягкие входы ^[9]
• Запуск на предварительно сегментированном изображении ^[10]
• Масштабируемое случайное блуждание по пространству ^[11]
• Устройство для быстрой ходьбы с использованием предварительного вычисления в автономном режиме ^{[12] [13]}
• Обобщенные случайные блуждания, обеспечивающие гибкие функции совместимости ^[14]
• Мощные водоразделы, объединяющие разрезы графа, случайное блуждание и кратчайший путь ^[15]
• Водоразделы, ходящие случайно ^[16]
• Многомерное гауссовское условное случайное поле ^[17]

Приложения [ править ]

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

• Раскрашивание изображения ^[18]
• Интерактивное ротоскопирование ^[19]
• Сегментация медицинских изображений ^{[20] [21] [22]}
• Объединение нескольких сегментов ^[23]
• Сегментация сетки ^{[24] [25]}
• Сетка шумоподавления ^[26]
• Редактирование сегментации ^[27]
• Устранение тени ^[28]
• Стерео сопоставление (т. Е. Регистрация одномерного изображения ) ^[29]
• Объединение изображений ^{[14] [17]}

Ссылки [ править ]

Внешние ссылки [ править ]

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