Algoritmo del caminante aleatorio

Algoritmo de segmentación de imágenes

El algoritmo del caminante aleatorio es un algoritmo para la segmentación de imágenes . En la primera descripción del algoritmo, ^[1] un usuario etiqueta interactivamente una pequeña cantidad de píxeles con etiquetas conocidas (llamadas semillas), por ejemplo, "objeto" y "fondo". Se imagina que cada uno de los píxeles sin etiquetar 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 calcular, para cada píxel, la probabilidad de que un caminante aleatorio que abandone el 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 por bordes, y los bordes se ponderan 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 para que sea un algoritmo totalmente automático, dado un término de fidelidad de 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 caminatas aleatorias , la probabilidad de que cada nodo envíe un caminante aleatorio a las semillas se puede calcular analíticamente resolviendo un sistema disperso, positivo-definido de ecuaciones lineales con la matriz laplaciana gráfica , que podemos representar con la variable . Se demostró que el algoritmo se aplica a una cantidad arbitraria de etiquetas (objetos), pero la exposición aquí se realiza 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 y . Los pesos de los bordes se utilizan para codificar la similitud de los nodos, que puede derivarse de las diferencias en la intensidad de la imagen, el color, la textura o cualquier otra característica significativa. Por ejemplo, al utilizar la intensidad de la imagen en el nodo , es común utilizar la función de ponderación de los 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, los bordes y los pesos se pueden utilizar luego 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 para y para , donde y representan los conjuntos de semillas de primer plano y de fondo, respectivamente. Si dejamos que represente el conjunto de nodos que tienen semillas (es decir, ) y represente el conjunto de nodos sin semillas (es decir, donde es el conjunto de todos los nodos), entonces el óptimo del problema de minimización de energía está 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 conjuntos respectivos. ${\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 . Optimizar 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 las matrices diagonales positivas permite una solución única para este sistema lineal. ${\displaystyle S}$ ${\displaystyle {\overline {S}}=V}$

Por ejemplo, si se utilizan los términos de probabilidad/unarios 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 pertenece 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 lanzado sobre el píxel alcance primero una semilla de objeto (primer plano) o una semilla de fondo. Sin embargo, existen 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 grafos. ^[5] En consecuencia, el algoritmo del caminante aleatorio tiene dos interpretaciones diferentes en términos de un circuito eléctrico. En ambos casos, el grafo 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 una semilla de objeto/primer plano, está conectado a una fuente de voltaje ideal de corriente continua unitaria conectada a tierra (es decir, para establecer un potencial unitario en cada ). Los potenciales de circuito eléctrico de estado estable establecidos en cada nodo por esta configuración de circuito serán exactamente iguales a las probabilidades de caminante aleatorio. Específicamente, el potencial eléctrico, en el nodo será igual a la probabilidad de que un caminante aleatorio lanzado en el nodo alcance un nodo de objeto/primer plano antes de alcanzar 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 de 0,5 es equivalente a etiquetar un nodo como objeto o fondo en función de la conductancia efectiva relativa entre el nodo y las semillas de objeto o fondo. Específicamente, si un nodo tiene una conductancia efectiva más alta (menor resistencia efectiva) a las semillas de objeto que a las semillas de fondo, entonces el nodo se etiqueta como objeto. Si un nodo tiene una conductancia efectiva más alta (menor resistencia efectiva) a las semillas de fondo que a las semillas de objeto, entonces el nodo se etiqueta como fondo.

Extensiones

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

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

Aplicaciones

Más allá de la segmentación de imágenes, el algoritmo Random Walker o sus extensiones se han aplicado también a diversos problemas en visión artificial y gráficos:

• Coloración de imágenes ^[18]
• Rotoscopia interactiva ^[19]
• Segmentación de imágenes médicas ^{[20] [21] [22]}
• Fusión de 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.: "Recorridos aleatorios para la segmentación de imágenes". PAMI, 2006
2. P. Doyle, JL Snell: Paseos aleatorios y redes eléctricas, Asociación Matemática de Estados Unidos, 1984
3. Leo Grady: "Segmentación de imágenes de caminante aleatorio de múltiples etiquetas utilizando modelos anteriores", Proc. of CVPR, vol. 1, págs. 763–770, 2005.
4. Leo Grady, Gareth Funka-Lea: Segmentación de imágenes de múltiples etiquetas para aplicaciones médicas basada en potenciales eléctricos de teoría de grafos, Actas del 8º Taller ECCV sobre enfoques de visión artificial 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 generativa de imágenes mediante recorridos aleatorios con reinicio, Proc. of ECCV 2008, págs. 264-275
7. J. Wang, M. Agrawala, MF Cohen: Tijeras blandas: una herramienta interactiva para realizar enmarcados de alta calidad en tiempo real Archivado el 27 de junio de 2021 en Wayback Machine , Proc. de SIGGRAPH 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 ICPR 2008
9. W. Yang, J. Cai, J. Zheng, J. Luo: Segmentación de imágenes interactiva y fácil de usar mediante entradas de usuario combinatorias unificadas, IEEE Trans. on Image Proc., 2010
10. C. Chefd'hotel, A. Sebbane: Recorrido aleatorio y propagación frontal en gráficos de adyacencia de cuencas hidrográficas para segmentación de imágenes con múltiples etiquetas, Proc. de ICV 2007
11. R. Rzeszutek, T. El-Maraghi, D. Androutsos: Segmentación de imágenes mediante recorridos aleatorios en el espacio de escala, Actas 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 y aproximada de caminantes aleatorios mediante precomputación de vectores propios". En IEEE Conf. CVPR, págs. 1–8, 2008
13. S. Andrews, G. Hamarneh, A. Saad. Caminante aleatorio rápido con valores anteriores que utiliza precomputación para la segmentación de imágenes médicas interactivas, Proc. de 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, "Cuencas hidrográficas de potencia: un marco de optimización basado en gráficos unificador", IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 33, n.º 7, págs. 1384-1399, julio de 2011
16. S. Ram, JJ Rodriguez: Random Walker Watersheds: A New Image Segmentation Approach, en IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP), págs. 1473-1477, Vancouver, Canadá, mayo de 2013
17. R. Shen, I. Cheng, A. Basu: Fusión de múltiples exposiciones 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 recorrido 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 de escala, Actas de la conferencia internacional IEEE de 2009 sobre Multimedia y Exposición
20. SP Dakua, JS Sahambi: Extracción del contorno del VI a partir de imágenes de resonancia magnética cardíaca mediante el método de recorridos aleatorios, Int. Journal of Recent Trends in Engineering, vol. 1, n.º 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: Segmentación de caminante aleatoria totalmente automática para lesiones cutáneas en un entorno supervisado, Actas de MICCAI 2009
23. P. Wattuya, K. Rothaus, JS Prassni, X. Jiang: Un enfoque basado en un caminante aleatorio para combinar múltiples segmentaciones, Proc. de ICPR 2008
24. Y.-K. Lai, S.-M. Hu, RR Martin, PL Rosin: Segmentación rápida de mallas mediante recorridos aleatorios, Actas del simposio ACM de 2008 sobre modelado físico y sólido
25. J. Zhang, J. Zheng, J. Cai: Corte de malla interactivo utilizando paseos aleatorios restringidos, IEEE Trans. sobre visualización y gráficos por computadora, 2010.
26. X. Sun, PL Rosin, RR Martin, FC Langbein: Recorridos aleatorios para la eliminación de ruido de mallas que preservan las características, Computer Aided Geometric Design, vol. 25, n.º 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. of MICCAI, vol. 2, 2006, págs. 888-895
28. G. Li, L. Qingsheng, Q. Xiaoxu: Eliminación de sombras de vehículos en movimiento basada en características de borde y de recorrido aleatorio, Proc. de IITA 2008
29. R. Shen, I. Cheng, X. Li, A. Basu: Coincidencia estéreo mediante recorridos aleatorios Archivado el 27 de junio de 2021 en Wayback Machine , Proc. de ICPR 2008

Enlaces externos

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