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 de forma interactiva 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 tenga 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 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, el píxel se asigna a 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, la caminata aleatoria ocurre en la gráfica ponderada (ver Doyle y Snell para una introducción a las caminatas aleatorias en gráficas [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 completamente automático, dado un término de fidelidad de datos (por ejemplo, una intensidad previa). [3] También se ha ampliado a otras aplicaciones.
El algoritmo fue publicado inicialmente por Leo Grady como artículo de conferencia [4] y más tarde como 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 puede calcularse analíticamente resolviendo un sistema disperso, positivo-definido de ecuaciones lineales 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).
Suponga que la imagen está representada por un gráfico , con cada nodo asociado con 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, usando la intensidad de la imagen en el nodo , es común utilizar la función de ponderación de bordes
Los nodos, aristas y pesos se pueden utilizar para construir la matriz gráfica de Laplacia .
El algoritmo de caminante aleatorio optimiza la energía
dónde representa una variable de valor real asociada con cada nodo en el gráfico y la optimización está restringida por por y por , dónde y representan los conjuntos de semillas de primer plano y de fondo, respectivamente. Si dejamos representan el conjunto de nodos que son sembrados (es decir, ) y representan el conjunto de nodos no sembrados (es decir, dónde es el conjunto de todos los nodos), entonces el óptimo del problema de minimización de energía viene dado por la solución a
donde los subíndices se utilizan para indicar la parte de la gráfica matriz laplaciana indexados por los respectivos conjuntos.
Para incorporar términos de verosimilitud (unarios) en el algoritmo, se mostró en [3] que se puede optimizar la energía
para matrices diagonales positivas y . La optimización de esta energía conduce al sistema de ecuaciones lineales.
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.
Por ejemplo, si los términos verosimilitud / unario se utilizan 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 en que pertenecía a la etiqueta del objeto) y representaría la confianza de que el color en el nodo pertenece al fondo.
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 que cayera 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 recorridos aleatorios en los 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,, asociado con el borde se establece igual a (es decir, el peso del borde es igual a la conductancia eléctrica ).
En la primera interpretación, cada nodo asociado con una semilla de fondo, , está vinculado directamente al suelo, mientras que cada nodo asociado con un objeto / semilla de 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 del circuito eléctrico de estado estacionario establecidos en cada nodo por esta configuración de circuito serán exactamente iguales a las probabilidades aleatorias de los caminantes. Específicamente, el potencial eléctrico, en el nodo será igual a la probabilidad de que un caminante al azar caiga en el nodo llegará a un objeto / nodo de primer plano antes de llegar a un nodo de fondo.
En la segunda interpretación, etiquetar un nodo como objeto o fondo mediante el umbral de la 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 (resistencia efectiva más baja) 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 más alta (resistencia efectiva más baja) 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 formas:
- Paseos aleatorios con reinicio [6]
- Alfombra alfa [7]
- Selección de umbral [8]
- Entradas suaves [9]
- Ejecutar en una imagen preconfigurada [10]
- Paseo aleatorio por el espacio de escala [11]
- Caminante aleatorio rápido que utiliza precomputación sin conexión [12] [13]
- Paseos aleatorios generalizados que permiten funciones de compatibilidad flexibles [14]
- Las cuencas hidrográficas unifican los cortes de gráficos, el caminante aleatorio y el 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 de caminante aleatorio o sus extensiones se han aplicado adicionalmente a varios problemas en la visión por computadora y los 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 imagen unidimensional ) [29]
- Fusión de imágenes [14] [17]
Referencias
- ^ a b c Grady, L .: " Paseos aleatorios para la segmentación de imágenes ". PAMI, 2006
- ^ P. Doyle, JL Snell: paseos al azar y redes eléctricas, Asociación matemática de América, 1984
- ^ a b Leo Grady: " Segmentación de imagen de caminante aleatorio de varias etiquetas utilizando modelos anteriores ", Proc. de CVPR, vol. 1, págs. 763–770, 2005.
- ^ Leo Grady, Gareth Funka-Lea: Segmentación de imágenes de etiquetas múltiples para aplicaciones médicas basadas en potenciales eléctricos teóricos de gráficos , Proc. del 8º 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.
- ^ PG Doyle, JL Snell: paseos al azar y redes eléctricas, monografías matemáticas de Carus, 1984
- ^ TH Kim, KM Lee, SU Lee: Segmentación de imágenes generativas mediante caminatas aleatorias con reinicio , Proc. de ECCV 2008, págs. 264–275
- ^ J. Wang, M. Agrawala, MF Cohen: Tijeras blandas: una herramienta interactiva para tapetes de alta calidad en tiempo real , Proc. de SIGGRAPH 2007
- ^ 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
- ^ W. Yang, J. Cai, J. Zheng, J. Luo: Segmentación de imagen interactiva fácil de usar a través de entradas de usuario combinatorias unificadas , IEEE Trans. en Image Proc., 2010
- ^ C. Chefd'hotel, A. Sebbane: Caminata aleatoria 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
- ^ R. Rzeszutek, T. El-Maraghi, D. Androutsos: Segmentación de imágenes mediante caminatas aleatorias en el espacio de escala , Proc. de la 16ª conferencia internacional sobre procesamiento de señales digitales, págs. 458–461, 2009
- ^ L. Grady, AK Sinop, " Segmentación aleatoria rápida aproximada de caminantes usando precomputación de vectores propios ". En IEEE Conf. CVPR, págs. 1 a 8, 2008
- ^ S. Andrews, G. Hamarneh, A. Saad. Caminante aleatorio rápido con antecedentes que utilizan precomputación para la segmentación interactiva de imágenes médicas , Proc. de MICCAI 2010
- ^ a b 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.
- ^ 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
- ^ S. Ram, JJ Rodriguez: Random Walker Watersheds: A New Image Segmentation Approach , en IEEE International Conference on Acustics, Speech, and Signal Processing (ICASSP), págs. 1473-1477, Vancouver, Canadá, mayo de 2013
- ^ a b R. Shen, I. Cheng, A. Basu: Fusión de exposición múltiple basada en QoE en CRF gaussiano multivariante jerárquico , IEEE Trans. sobre procesamiento de imágenes, 2013.
- ^ X. Liu, J. Liu, Z. Feng: Coloración mediante segmentación con caminata aleatoria , Análisis informático de imágenes y patrones, págs. 468–475, 2009
- ^ R. Rzeszutek, T. El-Maraghi, D. Androutsos: Rotoscopia interactiva a través de caminatas aleatorias en el espacio de escala , Proc. de la conferencia internacional IEEE 2009 sobre Multimedia y Expo
- ^ SP Dakua, JS Sahambi: Extracción del contorno del VI a partir de imágenes de resonancia magnética cardíaca mediante el enfoque de caminatas aleatorias , Int. Revista de tendencias recientes en ingeniería, vol. 1, núm. 3, mayo de 2009
- ^ F. Maier, A. Wimmer, G. Soza, JN Kaftan, D. Fritz, R. Dillmann: Segmentación hepática automática mediante el algoritmo aleatorio de Walker , Bildverarbeitung für die Medizin 2008
- ^ P. Wighton, M. Sadeghi, TK Lee, MS Atkins: una segmentación aleatoria completamente automática de caminantes para lesiones cutáneas en un entorno supervisado , Proc. del MICCAI 2009
- ^ P. Wattuya, K. Rothaus, JS Prassni, X. Jiang: Un enfoque basado en caminantes aleatorios para combinar múltiples segmentaciones , Proc. de ICPR 2008
- ^ Y.-K. Lai, S.-M. Hu, RR Martin, PL Rosin: Segmentación de malla rápida usando caminatas aleatorias , Proc. del simposio de ACM de 2008 sobre modelado físico y sólido
- ^ J. Zhang, J. Zheng, J. Cai: Corte de malla interactivo mediante paseos aleatorios restringidos , IEEE Trans. sobre visualización y gráficos por computadora, 2010.
- ^ X. Sun, PL Rosin, RR Martin, FC Langbein: Caminatas al azar para eliminar el ruido de las mallas que preservan las características , Diseño geométrico asistido por computadora, vol. 25, núm. 7, octubre de 2008, págs. 437–456
- ^ 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. de MICCAI, Vol. 2, 2006, págs. 888–895
- ^ G. Li, L. Qingsheng, Q. Xiaoxu: Eliminación de sombras de vehículos en movimiento basada en características de borde y paseo aleatorio, Proc. del IITA 2008
- ^ R. Shen, I. Cheng, X. Li, A. Basu: Emparejamiento estéreo mediante paseos aleatorios , Proc. de ICPR 2008
enlaces externos
- Código de Matlab que implementa el algoritmo original de caminante aleatorio
- Código de Matlab que implementa el algoritmo de caminante aleatorio con precomputación
- Implementación en Python del algoritmo original de caminante aleatorio en la caja de herramientas de procesamiento de imágenes scikit-image