algoritmo de caminante aleatorio

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 píxel 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 con 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 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, el píxel se asigna a la etiqueta para la cual es más probable que envíe 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 están ponderadas para reflejar la similitud entre los píxeles. Por lo tanto, el paseo aleatorio ocurre en el grafo ponderado (ver Doyle y Snell para una introducción a los paseos aleatorios en grafos ^{[ 2 ]} ).

Aunque el algoritmo inicial se formuló como un método interactivo para la segmentación de imágenes, se ha ampliado para convertirse en un algoritmo totalmente automático, dado un término de fidelidad de datos (por ejemplo, un prior de intensidad). ^{[ 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 posteriormente como un artículo de revista. ^{[ 1 ]}

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 y definido positivo de ecuaciones lineales con la matriz laplaciana del grafo , que podemos representar con la variable${\displaystyle L}$Se demostró que el algoritmo se aplica a un número arbitrario de etiquetas (objetos), pero la explicación aquí se basa en dos etiquetas (para simplificar la exposición).

Supongamos que la imagen está representada por un grafo , donde cada nodo${\displaystyle v_{i}}$asociado a un píxel y a cada borde${\displaystyle e_{ij}}$conectar píxeles vecinos${\displaystyle v_{i}}$y${\displaystyle v_{j}}$Los pesos de los bordes se utilizan para codificar la similitud de los nodos, que puede derivarse de diferencias en la intensidad de la imagen, el color, la textura o cualquier otra característica significativa. Por ejemplo, utilizando la intensidad de la imagen.${\displaystyle g_{i}}$en el nodo${\displaystyle v_{i}}$Es común utilizar la función de ponderación de bordes.

${\displaystyle w_{ij}=\exp {\left(-\beta (g_{i}-g_{j})^{2}\right)}.}$

Los nodos, las aristas y los pesos se pueden utilizar para construir la matriz laplaciana del grafo .

El algoritmo de caminante aleatorio optimiza la energía

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

dónde${\displaystyle x_{i}}$representa una variable de valor real asociada a cada nodo del grafo y la optimización está restringida por${\displaystyle x_{i}=1}$para${\displaystyle v_{i}\in F}$y${\displaystyle x_{i}=0}$para${\displaystyle v_{i}\in B}$, dónde${\displaystyle F}$y${\displaystyle B}$representan los conjuntos de semillas de primer plano y fondo, respectivamente. Si dejamos${\displaystyle S}$representan el conjunto de nodos que se siembran (es decir,${\displaystyle S=F\cup B}$) y${\displaystyle {\overline {S}}}$representan el conjunto de nodos no sembrados (es decir,${\displaystyle S\cup {\overline {S}}=V}$dónde${\displaystyle V}$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

${\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.${\displaystyle L}$indexados por los conjuntos respectivos.

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

${\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,${\displaystyle S}$, puede estar vacío en este caso (es decir,${\displaystyle {\overline {S}}=V}$), pero la presencia de las matrices diagonales positivas permite una solución única para este sistema lineal.

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

El algoritmo de caminante aleatorio se motivó inicialmente al etiquetar un píxel como objeto/fondo basándose en la probabilidad de que un caminante aleatorio lanzado a ese píxel alcanzara primero una semilla de objeto (primer plano) o una semilla de fondo. Sin embargo, existen varias otras interpretaciones de este mismo algoritmo que han aparecido en ^{[ 1 ] .}

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

• Caminatas aleatorias con reinicio ^{[ 6 ]}
• Matting alfa ^{[ 7 ]}
• Selección de umbral ^{[ 8 ]}
• Entradas suaves ^{[ 9 ]}
• Ejecutar sobre una imagen presegmentada ^{[ 10 ]}
• Paseo aleatorio en el espacio de escalas ^{[ 11 ]}
• Caminante aleatorio rápido que utiliza precomputación fuera de línea ^{[ 12 ] [ 13 ]}
• Caminatas aleatorias generalizadas que permiten funciones de compatibilidad flexibles ^{[ 14 ]}
• Cuencas hidrográficas de potencia que unifican cortes de grafos, caminante aleatorio y camino más corto ^{[ 15 ]}
• Cuencas hidrográficas de caminantes aleatorios ^{[ 16 ]}
• Campo aleatorio condicional gaussiano multivariado ^{[ 17 ]}

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

• Colorizació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 ]}
• Correspondencia estéreo (es decir, registro de imágenes unidimensionales ) ^{[ 29 ]}
• Fusión de imágenes ^{[ 14 ] [ 17 ]}

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