Algoritmo del camino aleatorio

De Wikipedia, la enciclopedia libre

El algoritmo del camino aleatorio es un algoritmo de segmentación de imágenes. En la primera descripción del algoritmo,[1]​ un usuario interactivamente etiquetaba 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 no marcados libera un caminante aleatorio, y la probabilidad es calculada cuando el caminante aleatorio llega a una semilla etiquetada, es decir, si un usuario colaca K semillas, cada una con una etiqueta diferente, entonces es necesario para cada píxel calcular, la probabilidad de que un caminante aleatorio dejando el primer píxel llegue a cada semilla. Este cálculo se puede determinar analíticamente resolviendo un sistema de ecuaciones lineales. Después de calcular estas probabilidades para cada pixel, al píxel se le asigna la etiqueta para la que es más probable enviar un caminante aleatorio. La imagen se modela como un grafo, en el que cada píxel corresponde a un nodo que está conectado a los píxeles vecinos por aristas, y las aristas son ponderadas para reflejar la similitud entre los píxeles. Por lo tanto, el camino aleatorio se produce en el grafo ponderado (véase Doyle y Snell para una introducción a caminos aleatorios en los grafos[2]​).

Aunque el algoritmo inicial se formuló como un método interactivo para la segmentación de la imagen, se ha extendido a ser un algoritmo completamente automático, dado un conjunto de términos fiables (por ejemplo, una intensidad previamente fijada).[3]​ También se ha extendido a otras aplicaciones, tales como Correspondencia de imágenes (Image Matching) (R. Shen, I. Cheng, X.li y A. Basu), ICPR 2008, y fusión de imágenes (Image Fusion), (R. Shen, I. Cheng, J.Shi y A. Basu), IEEE Trans. on Image Processing, de 2011, y otras aplicaciones.

El algoritmo fue inicialmente publicado en una conferencia[4]​ y más tarde como en una revista científica.[1]

Fundamentación Matemática[editar]

Aunque el algoritmo se describe en términos de caminos aleatorios, la probabilidad de que cada nodo envía un caminante aleatorio a las semillas puede calcularse analíticamente mediante la resolución de un sistema disperso, definido positivo de ecuaciones lineales, con el grafo de la matriz laplaciana, que podemos representar con la variable . El algoritmo se demostró que 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).

Supongamos que la imagen está representada por un grafo, con cada nodo asociado con un píxel y cada arista conecta los píxeles vecinos y . Los pesos de las aristas se utilizan para codificar similitud entre nodos, que puede derivarse de las diferencias de intensidad de la imagen, color, textura o cualesquiera otras características significativas. Por ejemplo, utilizando intensidad de la imagen en el nodo , es común el uso de la función de ponderación de arista

Los nodos, aristas y pesos pueden entonces ser usados para construir el grafo de la matriz laplaciana.

El algoritmo del camino aleatorio optimiza la energía

donde representa una variable de valor real asociado con cada nodo en el grafo y la optimización se ve limitada por para y para , donde where y representan los conjuntos de semillas objetos y fondo, respectivamente. Si dejamos que represente el conjunto de nodos que se siembran (es decir, ) y represente el conjunto de nodos sin sembrar (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

donde se utilizan los subíndices para indicar la porción del grafo de la matriz laplaciana indexados por los respectivos conjuntos.

Para incorporar la probabilidad de términos (unarios) en el algoritmo, se muestra en in[3]​ que uno 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, , en este caso puede estar vacío (es decir, ), pero la presencia de las diagonales positivas en las matrices permite una solución única a este sistema lineal.

Por ejemplo, si la probabilidad de los términos unarios 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 pertenece a la etiqueta objeto) y representaría la confianza de que el color en el nodo pertenece al fondo.

Interpretaciones del algoritmo[editar]

El algoritmo del caminante aleatorio fue motivado inicialmente por el etiquetado de un píxel como objeto/fondo, basado en la probabilidad de que un caminante al azar que cayó en el pixel llegará primero a una semilla objeto o una semilla fondo. Sin embargo, hay varias otras interpretaciones de este mismo algoritmo que han aparecido en.[1]

Interpretaciones en la Teoría de Circuitos[editar]

Hay conexiones conocidas entre la teoría de circuitos eléctricos y paseos aleatorios en los 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 sustituye por una lineal pasiva resistencia. La resistencia, , asociado con la arista se fija igual a (es decir, el peso de la arista es igual a la conductancia eléctrica ).

En la primera interpretación, cada nodo asociado con una semilla de fondo,, , está ligado directamente a la tierra mientras que cada nodo asociado con una semilla objeto, está unido a una unidad de corriente directa, fuente de voltaje ideal conectada a tierra (es decir, para establecer un potencial de unidad en cada ). Los potenciales de circuitos eléctricos en estado estacionario establecidos en cada nodo por esta configuración de circuito serán exactamente igual a las probabilidades del camino aleatorio. Específicamente, el potencial eléctrico, en el nodo será igual a la probabilidad de que un caminante aleatorio cayó en el nodo llegará a un nodo de objeto antes de llegar a un nodo de fondo.

En la segunda interpretación, el etiquetado de un nodo como objeto o fondo por umbralización, la probabilidad aleatoria es de 0,5, que es equivalente a un nodo etiquetado como objeto o de fondo basado en la conductancia efectiva relativa entre el nodo y las semillas objeto y fondo. Específicamente, si un nodo tiene una conductancia efectiva más alta (resistencia efectiva inferior) a las semillas objeto que las semillas fondo, entonces este nodo será etiquetado como objeto. Si un nodo tiene una conductancia efectiva más alta (resistencia efectiva inferior) a las semillas fondo que a las semillas objeto, entonces este nodo será etiquetado como fondo.

Extensiones[editar]

El algoritmo del camino aleatorio tradicional descrito anteriormente ha sido extendido de diferentes modos:

  • Caminos aleatorios con recomienzo[6]
  • Alfa esteras[7]
  • Selección de umbral[8]
  • Entradas suaves[9]
  • Hacer una presegmentación de una imagen[10]
  • Caminos aleatorios en espacios escalares[11]
  • Caminante aleatorio rápido usando una precomputación offline[12][13]

Aplicaciones[editar]

Más allá de la segmentación de imagen, el algoritmo del camino aleatorio ha sido aplicado a varios problemas en visión por computadoras y gráficos:

  • Coloración de una imagen[14]
  • Rotoscopia interactiva[15]
  • Segmentación de imágenes médicas[16][17][18]
  • Combinación de múltiples segmentaciones[19]
  • Malla de segmentación[20][21]
  • Malla de reducción de ruido en una imagen[22]
  • Edición de una segmentación[23]
  • Eliminación de sombras[24]
  • Correspondencia de una imagen[25]
  • Fusión de una imagen[26]

Referencias[editar]

  1. a b c L. Grady: Random Walks for Image Segmentation Archivado el 19 de julio de 2011 en Wayback Machine., IEEE Trans. on Pattern Analysis and Machine Intelligence, Vol. 28, No. 11, pp. 1768–1783, Nov., 2006.
  2. P. Doyle, J. L. Snell: Random Walks and Electric Networks, Mathematical Association of America, 1984
  3. a b Leo Grady: Multilabel Random Walker Image Segmentation Using Prior Models, Proc. of CVPR, Vol. 1, pp. 763–770, 2005. «Copia archivada». Archivado desde el original el 23 de septiembre de 2015. Consultado el 15 de diciembre de 2014. 
  4. Leo Grady, Gareth Funka-Lea: Multi-Label Image Segmentation for Medical Applications Based on Graph-Theoretic Electrical Potentials, Proc. of the 8th ECCV Workshop on Computer Vision Approaches to Medical Image Analysis and Mathematical Methods in Biomedical Image Analysis, pp. 230–245, 2004.
  5. P. G. Doyle, J. L. Snell: Random Walks and Electrical Networks, Carus Mathematical Monographs, 1984
  6. T. H. Kim, K. M. Lee, S. U. Lee: Generative Image Segmentation Using Random Walks with Restart, Proc. of ECCV 2008, pp. 264–275
  7. J. Wang, M. Agrawala, M. F. Cohen: Soft scissors: an interactive tool for realtime high quality matting, Proc. of SIGGRAPH 2007
  8. S. Rysavy, A. Flores, R. Enciso, K. Okada: Classifiability Criteria for Refining of Random Walks Segmentation, Proc. of ICPR 2008
  9. W. Yang, J. Cai, J. Zheng, J. Luo: User-friendly Interactive Image Segmentation through Unified Combinatorial User Inputs, IEEE Trans. on Image Proc., 2010
  10. C. Chefd'hotel, A. Sebbane: Random walk and front propagation on watershed adjacency graphs for multilabel image segmentation, Proc. of ICV 2007
  11. R. Rzeszutek, T. El-Maraghi, D. Androutsos: Image segmentation using scale-space random walks, Proc. of the 16th international conference on Digital Signal Processing, pp. 458–461, 2009
  12. L. Grady, A.K. Sinop: Fast approximate random walker segmentation using eigenvector precomputation. In IEEE Conf. CVPR, pp. 1–8, 2008
  13. S. Andrews, G. Hamarneh, A. Saad. Fast random walker with priors using precomputation for interactive medical image segmentation, Proc. of MICCAI 2010
  14. X. Liu, J. Liu, Z. Feng: Colorization Using Segmentation with Random Walk, Computer Analysis of Images and Patterns, pp. 468–475, 2009
  15. R. Rzeszutek, T. El-Maraghi, D. Androutsos: Interactive rotoscoping through scale-space random walks, Proc. of the 2009 IEEE international conference on Multimedia and Expo
  16. S. P. Dakua, J. S. Sahambi: LV Contour Extraction from Cardiac MR Images Using Random Walks Approach, Int. Journal of Recent Trends in Engineering, Vol 1, No. 3, May 2009
  17. F. Maier, A. Wimmer, G. Soza, J. N. Kaftan, D. Fritz, R. Dillmann: Automatic Liver Segmentation Using the Random Walker Algorithm, Bildverarbeitung für die Medizin 2008
  18. P. Wighton, M. Sadeghi, T. K. Lee, M. S. Atkins: A Fully Automatic Random Walker Segmentation for Skin Lesions in a Supervised Setting, Proc. of MICCAI 2009
  19. P. Wattuya, K. Rothaus, J. S. Prassni, X. Jiang: A random walker based approach to combining multiple segmentations, Proc. of ICPR 2008
  20. Y.-K. Lai, S.-M. Hu, R. R. Martin, P. L. Rosin: Fast mesh segmentation using random walks, Proc. of the 2008 ACM symposium on Solid and physical modeling
  21. J. Zhang, J. Zheng, J. Cai: Interactive Mesh Cutting Using Constrained Random Walks, IEEE Trans. on Visualization and Computer Graphics, 2010.
  22. X. Sun, P. L. Rosin, R. R. Martin, F. C. Langbein: Random walks for feature-preserving mesh denoising, Computer Aided Geometric Design, Vol. 25, No. 7, Oct. 2008, pp. 437–456
  23. L. Grady, G. Funka-Lea: An Energy Minimization Approach to the Data Driven Editing of Presegmented Images/Volumes, Proc. of MICCAI, Vol. 2, 2006, pp. 888–895
  24. G. Li, L. Qingsheng, Q. Xiaoxu: Moving Vehicle Shadow Elimination Based on Random Walk and Edge Features, Proc. of IITA 2008
  25. R. Shen, I. Cheng, X. Li, A. Basu: Stereo matching using random walks, Proc. of ICPR 2008
  26. R. Shen, I. Cheng, J. Shi, A. Basu: Generalized Random Walks for Fusion of Multi-exposure Images, IEEE Trans. on Image Processing, 2011.


Enlaces externos[editar]