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]​

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 ${\displaystyle L}$. 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 ${\displaystyle v_{i}}$ asociado con un píxel y cada arista ${\displaystyle e_{ij}}$ conecta los píxeles vecinos ${\displaystyle v_{i}}$ y ${\displaystyle v_{j}}$. 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 ${\displaystyle g_{i}}$ en el nodo ${\displaystyle v_{i}}$, es común el uso de la función de ponderación de arista

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

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

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

donde ${\displaystyle x_{i}}$ representa una variable de valor real asociado con cada nodo en el grafo y la optimización se ve limitada por ${\displaystyle x_{i}=1}$ para ${\displaystyle v_{i}\in F}$ y ${\displaystyle x_{i}=0}$ para ${\displaystyle v_{i}\in B}$, donde where ${\displaystyle F}$ y ${\displaystyle B}$ representan los conjuntos de semillas objetos y fondo, respectivamente. Si dejamos que ${\displaystyle S}$ represente el conjunto de nodos que se siembran (es decir, ${\displaystyle S=F\cup B}$) y ${\displaystyle {\overline {S}}}$ represente el conjunto de nodos sin sembrar (es decir, ${\displaystyle S\cup {\overline {S}}=V}$ donde ${\displaystyle V}$ 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 L_{{\overline {S}},{\overline {S}}}x_{\overline {S}}=-L_{{\overline {S}},S}x_{S},}$

donde se utilizan los subíndices para indicar la porción del grafo de la matriz laplaciana ${\displaystyle L}$ 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

${\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}$, en este caso puede estar vacío (es decir, ${\displaystyle {\overline {S}}=V}$), 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 ${\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 una mayor confianza en que ${\displaystyle v_{i}}$ pertenece a la etiqueta objeto) y ${\displaystyle b_{i}}$ representaría la confianza de que el color en el nodo ${\displaystyle v_{i}}$ pertenece al fondo.

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]​

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, ${\displaystyle r_{ij}}$, asociado con la arista ${\displaystyle e_{ij}}$ se fija igual a ${\displaystyle r_{ij}={\frac {1}{w_{ij}}}}$ (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,, ${\displaystyle v_{i}\in B}$, está ligado directamente a la tierra mientras que cada nodo asociado con una semilla objeto, ${\displaystyle v_{i}\in F}$ 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 ${\displaystyle v_{i}\in F}$). 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, ${\displaystyle x_{i}}$ en el nodo ${\displaystyle v_{i}}$ será igual a la probabilidad de que un caminante aleatorio cayó en el nodo ${\displaystyle v_{i}}$ 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.

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]​

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]​

• Código de implemetación del algoritmo del camino aleatorio tradicional en Matlab
• Código de implemetación del algoritmo del camino aleatorio en Matlab con precomputación
• Implementación del algoritmo del camino aleatorio en Python en la herramienta para el procesamiento de imágenes scikits-image