Método Lucas–Kanade

En visión artificial, el método Lucas–Kanade es un método diferencial ampliamente usado para estimar el flujo óptico desarrollado por Bruce D. Lucas y Takeo Kanade.  Asume que el flujo es esencialmente constante en la vecindad de un píxel en consideración, y resuelve las ecuaciones básicas de flujo óptico para todos los píxeles vecinos, aplicando el criterio de cuadrados mínimos.

Al combinar información de varios píxeles cercanos, el método Lucas–Kanade frecuentemente resuelve la ambigüedad inherente de la ecuación de flujo óptico.  También es más robusto frente al ruido en la imagen que otros métodos locales que se concentran en un punto.  Por otro lado, siendo un método puramente local, no provee información de flujo en el interior de regiones uniformes en la imagen, como sí lo hace el método global de Horn-Schunck.

Concepto 
El método Lucas–Kanade asume que el desplazamiento de los contenidos de la imagen entre dos instantes cercanos dados (entre dos cuadros consecutivos) es pequeño y aproximadamente constante en la vecindad del punto p en consideración.  Por eso la ecuación del flujo óptico se asume válida para todos los píxeles en una ventana centrada en p.  Es decir que el vector velocidad del flujo de la imagen  debe sastisfacer

donde  son los píxeles que pertenecen a la ventana, y  son las derivadas parciales de la imagen  respecto de las posiciones x, y y el tiempo t, evaluada en el punto  en el tiempo actual. 

Estas ecuaciones se pueden escribir en la forma matricial , donde

Este sistema tiene más ecuaciones que incógnitas, por lo que es usualmente sobredeterminado.  El método Lucas–Kanade llega a una solución de compromiso aplicando el principio de cuadrados mínimos.  Resuelve el sistema de 2x2
 o

donde  es la transpuesta de la matriz .  O sea, computa

donde la matriz central en la ecuación es una matriz inversa.  Las sumas van desde i=1 hasta n.

La matriz  es frecuentemente denominada tensor de estructura o matriz de momentos de segundo orden, de la imagen en el punto p.

Ventana ponderada 
La simple solución de cuadrados mínimos de arriba le atribuye la misma importancia a todos los n píxeles  en la ventana. En la práctica es usualmente mejor ponderar con mayor peso los píxeles cercanos al píxel central p.  Para eso se usa la versión ponderada de la ecuación de cuadrados mínimos, 

o

donde  es una matriz diagonal de n×n conteniendo los pesos  que se asignarán a la ecuación de píxeles .  De esta manera computa

El peso  se establece usualmente con una función Gaussiana de la distancia entre  y p.

Condiciones y técnicas de uso 
Para que la ecuación  sea resoluble,  debe ser invertible, o bien los eigenvalores de  deben satisfacer . Para evitar los problemas derivados del ruido, usualmente se requiere que  no sea muy pequeño. También, si  es muy grande, significa que el punto p está sobre un eje, y el método sufre el problema de apertura. Por eso, para que el método funcione como debe, se requiere que  y  sean suficientemente grandes y de magnitud similar. Ésta es la condición para la detección de esquinas. Esto significa que inspeccionando una sola imagen uno puede fácilmente decir qué píxeles son adecuados para este método.

Un supuesto principal para este método es que el movimiento es pequeño (menos de un píxel entre dos imágenes consecutivas).  Si el movimiento es mayor, una técnica consiste en reducir la resolución de la imagen hasta lograr que se cumpla el supuesto, y luego aplicar el método sobre la nueva imagen de menor resolución.

Mejoras y extensiones 
El uso de cuadrados mínimos asume que el error en los datos de la imagen tienen una distribución normal.  Si uno espera que la ventana contenga un cierto porcentaje de valores atípicos (outliers) -como errores groseros- que no siguen la distribución normal, se puede usar análisis estadístico para detectarlos y reducir su paso de manera acorde.

El método Lucas–Kanade per se sólo se puede usar cuando el vector de flujo de la imagen  entre dos cuadros consecutivos es suficientemente pequeño para que la ecuación diferencial del flujo óptico sea válida, que usualmente es menor a un píxel.  Cuando el flujo excede este límite, como en el caso de macheo estereoscópico, el método Lucas–Kanade todavía puede ser usado para refinar alguna estimación grosera obtenida por otros medios; por ejemplo vía extrapolación de vectores de flujo computados en cuadros anteriores, o ejecutando el algoritmo de Lucas-Kanade en versiones de resolución reducida como se mencionó anteriormente.  De hecho, este método es la base del popular algoritmo de macheo Kanade–Lucas–Tomasi Feature Tracker (KLT).

Una técnica similar se puede usar para computar deformaciones diferenciales afines del contenido de la imagen.

Véase también 
 Flujo óptico
 Método de Horn–Schunck

Referencias

Enlaces externos
 The image stabilizer plugin for ImageJ basado en el método de Lucas–Kanade
 Mathworks Lucas-Kanade implementación para Matlab de la afín inversa y normal de Lucas-Kanade
 FolkiGPU : Implementación en GPU de un flujo óptico interactivo basado en Lucas-Kanade
 KLT: Implementación de Kanade–Lucas–Tomasi Feature Tracker
 Takeo Kanade
 C++ example usando el algoritmo de flujo óptico de Lucas-Kanade
  Python example usando el algoritmo de flujo óptico de Lucas-Kanade
 Python example usando el tracker de Lucas-Kanade para macheo homográfico
 MATLAB breve ejemplo del método de Lucas-Kanade para mostrar el campo de flujo óptico
 MATLAB breve ejemplo del método de Lucas-Kanade para mostrar los vectores velocidad de objetos

Visión por computadora
Inventos de Japón