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.^[1]^[2]

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 editar

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 $(V_{x},V_{y})$ debe sastisfacer

I_{x}(q_{1})V_{x}+I_{y}(q_{1})V_{y}=-I_{t}(q_{1})

I_{x}(q_{2})V_{x}+I_{y}(q_{2})V_{y}=-I_{t}(q_{2})

\vdots

I_{x}(q_{n})V_{x}+I_{y}(q_{n})V_{y}=-I_{t}(q_{n})

donde $q_{1},q_{2},\dots ,q_{n}$ son los píxeles que pertenecen a la ventana, y $I_{x}(q_{i}),I_{y}(q_{i}),I_{t}(q_{i})$ son las derivadas parciales de la imagen $I$ respecto de las posiciones x, y y el tiempo t, evaluada en el punto $q_{i}$ en el tiempo actual.

Estas ecuaciones se pueden escribir en la forma matricial $Av=b$ , donde

A={\begin{bmatrix}I_{x}(q_{1})&I_{y}(q_{1})\\[10pt]I_{x}(q_{2})&I_{y}(q_{2})\\[10pt]\vdots &\vdots \\[10pt]I_{x}(q_{n})&I_{y}(q_{n})\end{bmatrix}}\quad \quad \quad v={\begin{bmatrix}V_{x}\\[10pt]V_{y}\end{bmatrix}}\quad \quad \quad b={\begin{bmatrix}-I_{t}(q_{1})\\[10pt]-I_{t}(q_{2})\\[10pt]\vdots \\[10pt]-I_{t}(q_{n})\end{bmatrix}}

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

A^{T}Av=A^{T}b

o

\mathrm {v} =(A^{T}A)^{-1}A^{T}b

donde $A^{T}$ es la transpuesta de la matriz $A$ . O sea, computa

{\begin{bmatrix}V_{x}\\[10pt]V_{y}\end{bmatrix}}={\begin{bmatrix}\sum _{i}I_{x}(q_{i})^{2}&\sum _{i}I_{x}(q_{i})I_{y}(q_{i})\\[10pt]\sum _{i}I_{y}(q_{i})I_{x}(q_{i})&\sum _{i}I_{y}(q_{i})^{2}\end{bmatrix}}^{-1}{\begin{bmatrix}-\sum _{i}I_{x}(q_{i})I_{t}(q_{i})\\[10pt]-\sum _{i}I_{y}(q_{i})I_{t}(q_{i})\end{bmatrix}}

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

La matriz $A^{T}A$ es frecuentemente denominada tensor de estructura o matriz de momentos de segundo orden, de la imagen en el punto p.

Ventana ponderada editar

La simple solución de cuadrados mínimos de arriba le atribuye la misma importancia a todos los n píxeles $q_{i}$ 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,

A^{T}WAv=A^{T}Wb

o

\mathrm {v} =(A^{T}WA)^{-1}A^{T}Wb

donde $W$ es una matriz diagonal de n×n conteniendo los pesos $W_{ii}=w_{i}$ que se asignarán a la ecuación de píxeles $q_{i}$ . De esta manera computa

{\begin{bmatrix}V_{x}\\[10pt]V_{y}\end{bmatrix}}={\begin{bmatrix}\sum _{i}w_{i}I_{x}(q_{i})^{2}&\sum _{i}w_{i}I_{x}(q_{i})I_{y}(q_{i})\\[10pt]\sum _{i}w_{i}I_{x}(q_{i})I_{y}(q_{i})&\sum _{i}w_{i}I_{y}(q_{i})^{2}\end{bmatrix}}^{-1}{\begin{bmatrix}-\sum _{i}w_{i}I_{x}(q_{i})I_{t}(q_{i})\\[10pt]-\sum _{i}w_{i}I_{y}(q_{i})I_{t}(q_{i})\end{bmatrix}}

El peso $w_{i}$ se establece usualmente con una función Gaussiana de la distancia entre $q_{i}$ y p.

Condiciones y técnicas de uso editar

Para que la ecuación $A^{T}Av=A^{T}b$ sea resoluble, $A^{T}A$ debe ser invertible, o bien los eigenvalores de $A^{T}A$ deben satisfacer $\lambda _{1}\geq \lambda _{2}>0$ . Para evitar los problemas derivados del ruido, usualmente se requiere que $\lambda _{2}$ no sea muy pequeño. También, si $\lambda _{1}/\lambda _{2}$ 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 $\lambda _{1}$ y $\lambda _{2}$ 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. ^[3]

Mejoras y extensiones editar

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 $V_{x},V_{y}$ 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 editar

Referencias editar

↑ B. D. Lucas and T. Kanade (1981), An iterative image registration technique with an application to stereo vision. Proceedings of Imaging Understanding Workshop, pages 121--130
↑ Bruce D. Lucas (1984) Generalized Image Matching by the Method of Differences (doctoral dissertation)
↑ J. Y. Bouguet, (2001) . Pyramidal implementation of the affine lucas kanade feature tracker description of the algorithm. Intel Corporation, 5.

Enlaces externos editar

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

Datos: Q920025

[LKproc-1] B. D. Lucas and T. Kanade (1981), An iterative image registration technique with an application to stereo vision. Proceedings of Imaging Understanding Workshop, pages 121--130

[Lthesis-2] Bruce D. Lucas (1984) Generalized Image Matching by the Method of Differences (doctoral dissertation)

[iteraLK-3] J. Y. Bouguet, (2001) . Pyramidal implementation of the affine lucas kanade feature tracker description of the algorithm. Intel Corporation, 5.

[1]

[2]

[3]