Algoritmo de caminante aleatorio

Algoritmo de segmentación de imágenes

El algoritmo de caminante aleatorio es un algoritmo para la segmentación de imágenes . En la primera descripción del algoritmo, ^[1] un usuario etiqueta interactivamente un pequeño número de píxeles con etiquetas conocidas (llamadas semillas), por ejemplo, "objeto" y "fondo". Se imagina que cada uno de los píxeles sin etiqueta libera un caminante aleatorio, y se calcula la probabilidad de que el caminante aleatorio de cada píxel llegue primero a una semilla que lleva cada etiqueta, es decir, si un usuario coloca K semillas, cada una con una etiqueta diferente, entonces es necesario para calcular, para cada píxel, la probabilidad de que un caminante aleatorio que salga del píxel llegue primero a cada semilla. Estas probabilidades se pueden determinar analíticamente resolviendo un sistema de ecuaciones lineales. Después de calcular estas probabilidades para cada píxel, se asigna al píxel la etiqueta para la que es más probable que envíe un caminante aleatorio. La imagen se modela como un gráfico , en el que cada píxel corresponde a un nodo que está conectado a los píxeles vecinos mediante bordes, y los bordes están ponderados para reflejar la similitud entre los píxeles. Por lo tanto, el paseo aleatorio ocurre en el gráfico ponderado (ver Doyle y Snell para una introducción a los paseos aleatorios en gráficos ^[2] ).

Aunque el algoritmo inicial se formuló como un método interactivo para la segmentación de imágenes, se ha ampliado hasta convertirlo en un algoritmo completamente automático, dado un término de fidelidad de los datos (por ejemplo, una intensidad previa). ^[3] También se ha extendido a otras aplicaciones.

El algoritmo fue publicado inicialmente por Leo Grady como un artículo de conferencia ^[4] y luego como un artículo de revista. ^[1]

Matemáticas

Aunque el algoritmo se describió en términos de paseos aleatorios , la probabilidad de que cada nodo envíe un caminante aleatorio a las semillas se puede calcular analíticamente resolviendo un sistema disperso de ecuaciones lineales definidas positivas con la gráfica matriz laplaciana , que podemos representar con La variable . Se demostró que el algoritmo se aplica a un número arbitrario de etiquetas (objetos), pero la exposición aquí es en términos de dos etiquetas (para simplificar la exposición). ${\displaystyle L}$

Supongamos que la imagen está representada por un gráfico , con cada nodo asociado a un píxel y cada borde conectando píxeles vecinos . Los pesos de los bordes se utilizan para codificar la similitud de los nodos, que pueden derivarse de diferencias en la intensidad, el color, la textura o cualquier otra característica significativa de la imagen. Por ejemplo, al usar la intensidad de la imagen en el nodo , es común usar la función de ponderación de bordes. ${\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)}.}$

Los nodos, aristas y pesos se pueden utilizar para construir la matriz laplaciana del gráfico .

El algoritmo del caminante aleatorio optimiza la energía.

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

donde representa una variable de valor real asociada con cada nodo en el gráfico y la optimización está restringida por for y for , donde y representan los conjuntos de semillas de primer y segundo plano, respectivamente. Si representamos el conjunto de nodos que están sembrados (es decir, ) y representamos el conjunto de nodos no sembrados (es decir, donde está el conjunto de todos los nodos), entonces el óptimo del problema de minimización de energía viene dado por la solución a ${\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},}$

donde los subíndices se utilizan para indicar la porción de la matriz laplaciana del gráfico indexada por los respectivos conjuntos. ${\displaystyle L}$

Para incorporar términos de probabilidad (unarios) en el algoritmo, se demostró en ^[3] que se puede optimizar la energía

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

para matrices diagonales positivas y . La optimización de esta energía conduce al sistema de ecuaciones lineales. ${\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}}}.}$

El conjunto de nodos sembrados , puede estar vacío en este caso (es decir, ), pero la presencia de matrices diagonales positivas permite una solución única para este sistema lineal. ${\displaystyle S}$ ${\displaystyle {\overline {S}}=V}$

Por ejemplo, si se usan términos de probabilidad/unario para incorporar un modelo de color del objeto, entonces representaría la confianza de que el color en el nodo pertenecería al objeto (es decir, un valor mayor de indica una mayor confianza de que pertenecía a la etiqueta del objeto). ) y representaría la confianza de que el color en el nodo pertenece al fondo. ${\displaystyle f_{i}}$ ${\displaystyle v_{i}}$ ${\displaystyle f_{i}}$ ${\displaystyle v_{i}}$ ${\displaystyle b_{i}}$ ${\displaystyle v_{i}}$

Interpretaciones de algoritmos

El algoritmo del caminante aleatorio se motivó inicialmente al etiquetar un píxel como objeto/fondo en función de la probabilidad de que un caminante aleatorio caído en el píxel alcanzara primero una semilla de objeto (primer plano) o una semilla de fondo. Sin embargo, hay varias otras interpretaciones de este mismo algoritmo que han aparecido en ^{[1] .}

Interpretaciones de la teoría de circuitos.

Existen conexiones bien conocidas entre la teoría de circuitos eléctricos y los paseos aleatorios en gráficos. ^[5] En consecuencia, el algoritmo del caminante aleatorio tiene dos interpretaciones diferentes en términos de un circuito eléctrico. En ambos casos, el gráfico se ve como un circuito eléctrico en el que cada borde se reemplaza por una resistencia lineal pasiva . La resistencia, asociada con el borde, se establece igual a (es decir, el peso del borde es igual a la conductancia eléctrica ). ${\displaystyle r_{ij}}$ ${\displaystyle e_{ij}}$ ${\displaystyle r_{ij}={\frac {1}{w_{ij}}}}$

En la primera interpretación, cada nodo asociado con una semilla de fondo, está conectado directamente a tierra, mientras que cada nodo asociado con un objeto/semilla de primer plano, está conectado a una fuente de voltaje ideal de corriente directa unitaria conectada a tierra (es decir, para establecer una unidad potencial en cada ). Los potenciales del circuito eléctrico de estado estacionario establecidos en cada nodo mediante esta configuración de circuito serán exactamente iguales a las probabilidades del caminante aleatorio. Específicamente, el potencial eléctrico en el nodo será igual a la probabilidad de que un caminante aleatorio dejado en el nodo alcance un objeto/nodo de primer plano antes de llegar a un nodo de fondo. ${\displaystyle v_{i}\in B}$ ${\displaystyle v_{i}\in F}$ ${\displaystyle v_{i}\in F}$ ${\displaystyle x_{i}}$ ${\displaystyle v_{i}}$ ${\displaystyle v_{i}}$

En la segunda interpretación, etiquetar un nodo como objeto o fondo estableciendo un umbral de probabilidad de caminante aleatorio en 0,5 es equivalente a etiquetar un nodo como objeto o fondo en función de la conductancia efectiva relativa entre el nodo y el objeto o semillas de fondo. Específicamente, si un nodo tiene una conductancia efectiva más alta (menor resistencia efectiva) a las semillas del objeto que a las semillas de fondo, entonces el nodo se etiqueta como objeto. Si un nodo tiene una conductancia efectiva mayor (menor resistencia efectiva) a las semillas de fondo que a las semillas del objeto, entonces el nodo se etiqueta como fondo.

Extensiones

El algoritmo tradicional de caminante aleatorio descrito anteriormente se ha ampliado de varias maneras:

• Paseos aleatorios con reinicio ^[6]
• Estera alfa ^[7]
• Selección de umbral ^[8]
• Entradas suaves ^[9]
• Ejecutar en una imagen presegmentada ^[10]
• Paseo aleatorio en el espacio de escala ^[11]
• Caminante aleatorio rápido que utiliza precálculo fuera de línea ^{[12] [13]}
• Paseos aleatorios generalizados que permiten funciones de compatibilidad flexibles ^[14]
• Cuencas hidrográficas unificadoras de gráficos, caminante aleatorio y camino más corto ^[15]
• Cuencas hidrográficas aleatorias ^[16]
• Campo aleatorio condicional gaussiano multivariado ^[17]

Aplicaciones

Más allá de la segmentación de imágenes, el algoritmo de caminante aleatorio o sus extensiones se ha aplicado adicionalmente a varios problemas en visión por computadora y gráficos:

• Colorización de imágenes ^[18]
• Rotoscopia interactiva ^[19]
• Segmentación de imágenes médicas ^{[20] [21] [22]}
• Fusionar múltiples segmentaciones ^[23]
• Segmentación de malla ^{[24] [25]}
• Eliminación de ruido de malla ^[26]
• Edición de segmentación ^[27]
• Eliminación de sombras ^[28]
• Coincidencia estéreo (es decir, registro de imágenes unidimensionales ) ^[29]
• Fusión de imágenes ^{[14] [17]}

Referencias

1. Grady, L .: "Paseos aleatorios para segmentación de imágenes". PAMI, 2006
2. P. Doyle, JL Snell: paseos aleatorios y redes eléctricas, Asociación Matemática de América, 1984
3. Leo Grady: "Segmentación de imágenes de caminantes aleatorios de múltiples etiquetas utilizando modelos anteriores", Proc. de CVPR, vol. 1, págs. 763–770, 2005.
4. Leo Grady, Gareth Funka-Lea: Segmentación de imágenes de etiquetas múltiples para aplicaciones médicas basada en potenciales eléctricos teóricos de grafos, Proc. del octavo taller de ECCV sobre enfoques de visión por computadora para el análisis de imágenes médicas y métodos matemáticos en el análisis de imágenes biomédicas, págs. 230–245, 2004.
5. PG Doyle, JL Snell: paseos aleatorios y redes eléctricas, monografías matemáticas de Carus, 1984
6. TH Kim, KM Lee, SU Lee: Segmentación de imágenes generativas mediante recorridos aleatorios con reinicio, Proc. de ECCV 2008, págs. 264-275
7. J. Wang, M. Agrawala, MF Cohen: Tijeras blandas: una herramienta interactiva para mateados de alta calidad en tiempo real Archivado el 27 de junio de 2021 en Wayback Machine , Proc. de SIGGRAFO 2007
8. S. Rysavy, A. Flores, R. Enciso, K. Okada: Criterios de clasificabilidad para el refinamiento de la segmentación de paseos aleatorios, Proc. de la CIPR 2008
9. W. Yang, J. Cai, J. Zheng, J. Luo: Segmentación de imágenes interactiva y fácil de usar a través de entradas combinatorias unificadas del usuario, IEEE Trans. en Image Proc., 2010
10. C. Chefd'hotel, A. Sebbane: Paseo aleatorio y propagación frontal en gráficos de adyacencia de cuencas hidrográficas para segmentación de imágenes de múltiples etiquetas, Proc. de ICV 2007
11. R. Rzeszutek, T. El-Maraghi, D. Androutsos: Segmentación de imágenes mediante paseos aleatorios en el espacio de escala, Proc. de la 16ª conferencia internacional sobre procesamiento de señales digitales, págs. 458–461, 2009
12. L. Grady, AK Sinop, "Segmentación rápida aproximada de caminantes aleatorios mediante precálculo de vectores propios". En la Conferencia IEEE. CVPR, págs. 1 a 8, 2008
13. S. Andrews, G. Hamarneh, A. Saad. Caminante aleatorio rápido con antecedentes que utiliza precomputación para la segmentación interactiva de imágenes médicas, Proc. del MICCAI 2010
14. R. Shen, I. Cheng, J. Shi, A. Basu: paseos aleatorios generalizados para la fusión de imágenes de exposición múltiple, IEEE Trans. sobre procesamiento de imágenes, 2011.
15. Camille Couprie, Leo Grady, Laurent Najman y Hugues Talbot, "Power Watersheds: A Unifying Graph-Based Optimization Framework", IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 33, No. 7, págs. 1384-1399, julio 2011
16. S. Ram, JJ Rodriguez: Random Walker Watersheds: A New Image Segmentation Approach, en la Conferencia internacional IEEE sobre acústica, habla y procesamiento de señales (ICASSP), págs. 1473-1477, Vancouver, Canadá, mayo de 2013
17. R. Shen, I. Cheng, A. Basu: Fusión de exposición múltiple basada en QoE en CRF gaussiano multivariado jerárquico, IEEE Trans. sobre procesamiento de imágenes, 2013.
18. X. Liu, J. Liu, Z. Feng: Colorización mediante segmentación con paseo aleatorio, análisis informático de imágenes y patrones, págs. 468–475, 2009
19. R. Rzeszutek, T. El-Maraghi, D. Androutsos: rotoscopia interactiva a través de paseos aleatorios en el espacio a escala, Proc. de la conferencia internacional IEEE 2009 sobre Multimedia y Expo
20. SP Dakua, JS Sahambi: Extracción del contorno del VI a partir de imágenes de resonancia magnética cardíaca mediante un enfoque de caminatas aleatorias, Int. Revista de tendencias recientes en ingeniería, Vol 1, No. 3, mayo de 2009
21. F. Maier, A. Wimmer, G. Soza, JN Kaftan, D. Fritz, R. Dillmann: segmentación automática del hígado mediante el algoritmo Random Walker ^{[ enlace muerto ]} , Bildverarbeitung für die Medizin 2008
22. P. Wighton, M. Sadeghi, TK Lee, MS Atkins: una segmentación de caminantes aleatorios completamente automática para lesiones cutáneas en un entorno supervisado, Proc. del MICCAI 2009
23. P. Wattuya, K. Rothaus, JS Prassni, X. Jiang: Un enfoque basado en caminantes aleatorios para combinar múltiples segmentaciones, Proc. de la CIPR 2008
24. Y.-K. Lai, S.-M. Hu, RR Martin, PL Rosin: Segmentación de malla rápida mediante paseos aleatorios, Proc. del simposio ACM de 2008 sobre modelado físico y sólidos
25. J. Zhang, J. Zheng, J. Cai: Corte de malla interactivo mediante recorridos aleatorios restringidos, IEEE Trans. sobre visualización y gráficos por computadora, 2010.
26. X. Sun, PL Rosin, RR Martin, FC Langbein: Paseos aleatorios para eliminar el ruido de la malla y preservar las características, Diseño geométrico asistido por computadora, vol. 25, núm. 7, octubre de 2008, págs. 437–456
27. L. Grady, G. Funka-Lea: "Un enfoque de minimización de energía para la edición basada en datos de imágenes/volúmenes presegmentados", Proc. del MICCAI, vol. 2, 2006, págs. 888–895
28. G. Li, L. Qingsheng, Q. Xiaoxu: Eliminación de sombras de vehículos en movimiento según características de paseo aleatorio y bordes, Proc. del IITA 2008
29. R. Shen, I. Cheng, X. Li, A. Basu: coincidencia estéreo mediante paseos aleatorios Archivado el 27 de junio de 2021 en Wayback Machine , Proc. de la CIPR 2008

enlaces externos

• Código de Matlab que implementa el algoritmo de caminante aleatorio original
• Código Matlab que implementa el algoritmo de caminante aleatorio con precómputo
• Implementación en Python del algoritmo de caminante aleatorio original Archivado el 14 de octubre de 2012 en Wayback Machine en la caja de herramientas de procesamiento de imágenes scikit-image