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

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

Рекомендации

1. Грейди, Л .: "Случайные блуждания для сегментации изображений ". ПАМИ, 2006 г.
2. П. Дойл, Дж. Л. Снелл: Случайные блуждания и электрические сети, Математическая ассоциация Америки, 1984
3. Лео Грейди: "Сегментация изображений со случайным ходом с несколькими метками с использованием предшествующих моделей ", Материалы CVPR, том 1, стр. 763–770, 2005.
4. Лео Грейди, Гарет Функа-Ли: Сегментация изображений с несколькими метками для медицинских приложений на основе теоретико-графических электрических потенциалов, Proc. 8-го семинара ECCV по подходам компьютерного зрения к анализу медицинских изображений и математическим методам в биомедицинском анализе изображений, стр. 230–245, 2004 г.
5. П. Г. Дойл, Дж. Л. Снелл: Случайные блуждания и электрические сети, Математические монографии Каруса, 1984
6. Т. Х. Ким, К. М. Ли, С. У. Ли: Генеративная сегментация изображений с использованием случайных блужданий с перезапуском, Proc. of ECCV 2008, стр. 264–275
7. Дж. Ван, М. Агравала, М. Ф. Коэн: Мягкие ножницы: интерактивный инструмент для высококачественного матирования в реальном времени, Proc. СИГГРАФА 2007
8. С. Рысавый, А. Флорес, Р. Энсисо, К. Окада: Критерии классифицируемости для уточнения сегментации случайных блужданий, Proc. ICPR 2008
9. В. Ян, Дж. Цай, Дж. Чжэн, Дж. Ло: Удобная интерактивная сегментация изображений с помощью унифицированных комбинаторных пользовательских входов, IEEE Trans. на Image Proc., 2010
10. C. Chefd'hotel, A. Sebbane: Случайное блуждание и фронтальное распространение на графах смежности водоразделов для сегментации изображений с несколькими метками, Proc. ICV 2007
11. Р. Жешутек, Т. Эль-Мараги, Д. Андроутсос: Сегментация изображений с использованием случайных блужданий в масштабном пространстве, Proc. 16-й международной конференции по цифровой обработке сигналов, стр. 458–461, 2009 г.
12. Л. Грейди, А.К. Синоп »,Быстрая приближенная сегментация случайного ходока с использованием предварительного вычисления собственного вектора ". В IEEE Conf. CVPR, стр. 1–8, 2008 г.
13. С. Эндрюс, Г. Хамарнех, А. Саад. Устройство быстрой случайной ходьбы с априорными значениями с использованием предварительного вычисления для интерактивной сегментации медицинских изображений, Proc. MICCAI 2010
14. Р. Шен, И. Ченг, Дж. Ши, А. Басу: Обобщенные случайные блуждания для слияния изображений с мультиэкспозицией, IEEE Trans. по обработке изображений, 2011.
15. Камилла Купри, Лео Грейди, Лоран Наджман и Хьюг Талбот "Power Watershads: единая платформа оптимизации на основе графов ”, IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 33, No. 7, pp. 1384-1399, июль 2011 г.
16. С. Рам, Дж. Дж. Родригес: Случайные водоразделы: новый подход к сегментации изображений, в Международной конференции IEEE по акустике, речи и обработке сигналов (ICASSP), стр. 1473-1477, Ванкувер, Канада, май 2013 г.
17. Р. Шен, И. Ченг, А. Басу: Многоэкспозиционное объединение на основе QoE в иерархической многомерной гауссовской CRF, IEEE Trans. по обработке изображений, 2013.
18. X. Лю, Дж. Лю, З. Фэн: Раскрашивание с использованием сегментации со случайным блужданием, Компьютерный анализ изображений и шаблонов, стр. 468–475, 2009.
19. Р. Жешутек, Т. Эль-Мараги, Д. Андроутсос: Интерактивное ротоскопирование с помощью случайных блужданий в масштабном пространстве, Proc. международной конференции IEEE 2009 по мультимедиа и выставкам
20. С. П. Дакуа, Дж. С. Сахамби: Извлечение контура ЛЖ из МРТ-изображений сердца с использованием подхода случайных блужданий, Int. Журнал последних тенденций в машиностроении, Том 1, № 3, май 2009 г.
21. Ф. Майер, А. Виммер, Г. Соза, Дж. Н. Кафтан, Д. Фриц, Р. Диллманн: Автоматическая сегментация печени с использованием алгоритма случайного ходока, Bildverarbeitung für die Medizin 2008
22. П. Уайтон, М. Садеги, Т. К. Ли, М. С. Аткинс: Полностью автоматическая сегментация случайных ходунков для поражений кожи в условиях наблюдения, Proc. MICCAI 2009
23. П. Ваттуя, К. Ротхаус, Дж. С. Прасни, X. Цзян: Подход, основанный на случайном ходьбе, для объединения нескольких сегментов, Proc. ICPR 2008
24. Ю.-К. Лай, С.-М. Ху, Р. Р. Мартин, П. Л. Розин: Быстрая сегментация сетки с использованием случайных блужданий, Proc. симпозиума ACM 2008 г. по твердому телу и физическому моделированию
25. Дж. Чжан, Дж. Чжэн, Дж. Цай: Интерактивное вырезание сетки с использованием случайных блужданий с ограничениями, IEEE Trans. по визуализации и компьютерной графике, 2010.
26. X. Сан, П. Л. Розин, Р. Р. Мартин, Ф. К. Лангбейн: Случайные блуждания для шумоподавления сетки с сохранением характеристик, Компьютерный геометрический дизайн, Том. 25, № 7, октябрь 2008 г., стр. 437–456
27. Л. Грейди, Г. Функа-Леа: "Энергетический подход к редактированию предварительно сегментированных изображений / объемов на основе данных ", Proc. Of MICCAI, Vol. 2, 2006, pp. 888–895.
28. Г. Ли, Л. Циншэн, К. Сяосюй: Устранение тени движущегося транспортного средства на основе случайного блуждания и характеристик краев, Proc. IITA 2008
29. Р. Шен, И. Ченг, Х. Ли, А. Басу: Стерео сопоставление с использованием случайных блужданий, Proc. ICPR 2008

внешняя ссылка

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