Алгоритм случайного блуждания - Википедия - Random walker algorithm

В алгоритм случайного блуждания это алгоритм для сегментация изображения. В первом описании алгоритма^[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}}$

куда ${ 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 чашка B}$) и ${ displaystyle { overline {S}}}$ представляют собой набор незавершенных узлов (т. е. ${ Displaystyle S чашка { 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-изображение