Método de Lucas-Kanade

En visión por computadora , el método de Lucas-Kanade es un método diferencial ampliamente utilizado para la estimación del flujo óptico , desarrollado por Bruce D. Lucas y Takeo Kanade . Este método asume que el flujo es esencialmente constante en un entorno local del píxel considerado y resuelve las ecuaciones básicas de flujo óptico para todos los píxeles de dicho entorno, mediante el criterio de mínimos cuadrados . ^{[ 1 ] [ 2 ]}

Al combinar información de varios píxeles cercanos, el método de Lucas-Kanade suele resolver la ambigüedad inherente de la ecuación de flujo óptico. Además, es menos sensible al ruido de la imagen que los métodos puntuales. Por otro lado, al ser un método puramente local, no puede proporcionar información de flujo en el interior de regiones uniformes de la imagen.

El método de Lucas-Kanade supone que el desplazamiento del contenido de la imagen entre dos instantes (fotogramas) cercanos es pequeño y aproximadamente constante dentro de una vecindad del punto.${\displaystyle p}$bajo consideración. Por lo tanto , se puede suponer que la ecuación de flujo óptico se cumple para todos los píxeles dentro de una ventana centrada en${\displaystyle p}$. Es decir, el vector de flujo (velocidad) de la imagen local${\displaystyle (V_{x},V_{y})}$debe satisfacer

$${\displaystyle {\begin{aligned}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})\end{aligned}}}$$

dónde${\displaystyle q_{1},q_{2},\dots ,q_{n}}$son los píxeles dentro de la ventana, y${\displaystyle I_{x}(q_{i}),I_{y}(q_{i}),I_{t}(q_{i})}$son las derivadas parciales de la imagen${\displaystyle I}$con respecto a la posición${\displaystyle x,y}$y tiempo${\displaystyle t}$, evaluado en el punto${\displaystyle q_{i}}$y en este momento.

Estas ecuaciones se pueden escribir en forma matricial.${\displaystyle Av=b}$, dónde $${\displaystyle 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 y, por lo tanto, suele estar sobredeterminado. El método de Lucas-Kanade obtiene una solución de compromiso mediante el principio de mínimos cuadrados . Es decir, resuelve el${\displaystyle 2\times 2}$sistema $${\displaystyle A^{T}Av=A^{T}b}$$o $${\displaystyle \mathrm {v} =(A^{T}A)^{-1}A^{T}b}$$ dónde${\displaystyle A^{T}}$es la transpuesta de la matriz${\displaystyle A}$. Es decir, calcula $${\displaystyle {\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${\displaystyle i=1}$a${\displaystyle n}$.

La matriz${\displaystyle A^{T}A}$A menudo se le llama tensor de estructura de la imagen en el punto${\displaystyle p}$.

La solución de mínimos cuadrados simple anterior da la misma importancia a todos${\displaystyle n}$píxeles${\displaystyle q_{i}}$en la ventana. En la práctica, suele ser mejor dar más peso a los píxeles que están más cerca del píxel central.${\displaystyle p}$Para ello, se utiliza la versión ponderada de la ecuación de mínimos cuadrados. $${\displaystyle A^{T}WAv=A^{T}Wb}$$ o $${\displaystyle \mathrm {v} =(A^{T}WA)^{-1}A^{T}Wb}$$ dónde${\displaystyle W}$es un${\displaystyle n\times n}$matriz diagonal que contiene los pesos${\displaystyle W_{ii}=w_{i}}$ser asignado a la ecuación del píxel${\displaystyle q_{i}}$. Es decir, calcula $${\displaystyle {\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${\displaystyle w_{i}}$Por lo general, se establece en una función gaussiana de la distancia entre${\displaystyle q_{i}}$y${\displaystyle p}$.

Para que la ecuación${\displaystyle A^{T}Av=A^{T}b}$ser resoluble,${\displaystyle A^{T}A}$debe ser invertible, o${\displaystyle A^{T}A}$Los valores propios de satisfacen${\displaystyle \lambda _{1}\geq \lambda _{2}>0}$Para evitar problemas de ruido, normalmente${\displaystyle \lambda _{2}}$Se requiere que no sea demasiado pequeño. Además, si${\displaystyle \lambda _{1}/\lambda _{2}}$es demasiado grande, esto significa que el punto${\displaystyle p}$está en un borde, y este método sufre del problema de la apertura . Por lo tanto, para que este método funcione correctamente, la condición es que${\displaystyle \lambda _{1}}$y${\displaystyle \lambda _{2}}$son suficientemente grandes y tienen una magnitud similar. Esta condición también se aplica a la detección de esquinas . Esta observación demuestra que se puede determinar fácilmente qué píxel es adecuado para que funcione el método de Lucas-Kanade con solo inspeccionar una sola imagen.

Una suposición principal de este método es que el movimiento es pequeño (menos de 1 píxel entre dos imágenes, por ejemplo). Si el movimiento es grande y no cumple con esta suposición, una técnica consiste en reducir primero la resolución de las imágenes y luego aplicar el método de Lucas-Kanade. ^{[ 3 ]}

Para lograr el seguimiento de movimiento con este método, el vector de flujo se puede aplicar y recalcular iterativamente hasta alcanzar un umbral cercano a cero, momento en el que se puede asumir que las ventanas de imagen son muy similares. ^{[ 1 ]} Al hacer esto con cada ventana de seguimiento sucesiva, el punto se puede rastrear a lo largo de varias imágenes en una secuencia, hasta que se oculte o salga del encuadre.

El método de mínimos cuadrados asume implícitamente que los errores en los datos de la imagen siguen una distribución gaussiana con media cero. Si se espera que la ventana contenga un cierto porcentaje de valores atípicos (valores de datos erróneos que no siguen la distribución de error gaussiana "ordinaria"), se puede utilizar un análisis estadístico para detectarlos y reducir su ponderación en consecuencia.

El método de Lucas-Kanade en sí mismo solo puede utilizarse cuando el vector de flujo de la imagen${\displaystyle V_{x},V_{y}}$La distancia entre los dos fotogramas es lo suficientemente pequeña como para que se cumpla la ecuación diferencial del flujo óptico, que suele ser menor que la distancia entre píxeles. Cuando el vector de flujo puede exceder este límite, como en la correspondencia estéreo o el registro de documentos deformados, el método de Lucas-Kanade aún puede utilizarse para refinar una estimación aproximada del mismo, obtenida por otros medios; por ejemplo, extrapolando los vectores de flujo calculados para fotogramas anteriores, o ejecutando el algoritmo de Lucas-Kanade en versiones de las imágenes a escala reducida. De hecho, este último método es la base del popular algoritmo de correspondencia de características de Kanade-Lucas-Tomasi (KLT) .

Se puede utilizar una técnica similar para calcular deformaciones afines diferenciales del contenido de la imagen.

• Flujo óptico
• Método de Horn-Schunck
• Algoritmo de detección de esquinas de Shi-Tomasi
• Rastreador de características Kanade-Lucas-Tomasi

• El complemento estabilizador de imágenes para ImageJ basado en el método de Lucas-Kanade.
• Implementación en Matlab de la transformada inversa y normal afín de Lucas -Kanade de Mathworks Lucas-Kanade
• FolkiGPU: Implementación en GPU de un flujo óptico iterativo basado en Lucas-Kanade
• KLT : Una implementación del rastreador de características de Kanade-Lucas-Tomasi
• Takeo Kanade
• Ejemplo en C utilizando el algoritmo de flujo óptico de Lucas-Kanade.
• Ejemplo en C++ utilizando el algoritmo de flujo óptico de Lucas-Kanade.
• Ejemplo en Python utilizando el algoritmo de flujo óptico de Lucas-Kanade.
• Ejemplo en Python que utiliza el rastreador de Lucas-Kanade para la comparación de homografías.
• Ejemplo rápido en MATLAB del método de Lucas-Kanade para mostrar el campo de flujo óptico.
• Ejemplo rápido en MATLAB del método de Lucas-Kanade para mostrar el vector de velocidad de los objetos.