Méthode de Lucas–Kanade

La méthode de Lucas-Kanade suppose que le déplacement d'un point de l'image entre deux instants consécutifs est petit et approximativement constant dans un voisinage du point p. L'équation du flot optique peut être supposée vraie pour tous les pixels dans une fenêtre centrée au point p. Le vecteur vitesse local ${\displaystyle (V_{x},V_{y})}$ doit satisfaire

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

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

${\displaystyle \vdots }$

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

où ${\displaystyle q_{1},q_{2},\dots ,q_{n}}$ sont les pixels à l'intérieur de la fenêtre, et ${\displaystyle I_{x}(q_{i}),I_{y}(q_{i}),I_{t}(q_{i})}$ sont les dérivées partielles de l'image ${\displaystyle I}$ selon les variables d'espace x, y et de temps t, évaluée au point ${\displaystyle q_{i}}$ et au temps courant.

Ces équations peuvent être écrites sous la forme matricielle suivante : ${\displaystyle Av=b}$, où

${\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 v={\begin{bmatrix}V_{x}\\[10pt]V_{y}\end{bmatrix}},\quad {\mbox{and}}\quad b={\begin{bmatrix}-I_{t}(q_{1})\\[10pt]-I_{t}(q_{2})\\[10pt]\vdots \\[10pt]-I_{t}(q_{n})\end{bmatrix}}}$

Le système a plus d'équations que d'inconnues et est donc sur-déterminé. La méthode de Lucas-Kanade apporte une solution par la méthode des moindres carrés. Elle résout un système d'équations normales :

${\displaystyle A^{T}Av=A^{T}b}$ ou

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

où ${\displaystyle A^{T}}$ est la matrice transposée de la matrice ${\displaystyle A}$. Alors, on calcule

${\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})\\\sum _{i}I_{x}(q_{i})I_{y}(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}}}$

avec les sommes allant de i = 1 à n.

La matrice ${\displaystyle A^{T}A}$ est appelée le tenseur de structure de l'image au point p.

La solution donnée ci-avant donne la même importance à tous les n pixels ${\displaystyle q_{i}}$ de la fenêtre. En pratique, il est préférable de donner un poids plus important aux pixels qui sont proches du pixel p. Pour cela, on utilise la version pondérée de l'équation des moindres carrés,

${\displaystyle A^{T}WAv=A^{T}Wb}$

ou

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

où ${\displaystyle W}$ est matrice diagonale n×n contenant les poids ${\displaystyle W_{ii}=w_{i}}$ associé à l'équation du pixel ${\displaystyle q_{i}}$. Alors, le calcul est le suivant :

${\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}}}$

Le poids ${\displaystyle w_{i}}$ est habituellement un ensemble de Gaussienne de la distance entre ${\displaystyle q_{i}}$ et p.

L'approche des moindres carrés suppose implicitement que les erreurs dans l'image ont une distribution gaussienne avec une moyenne nulle. Si on s'attend à ce que la fenêtre contienne un certain pourcentage de points aberrants (valeurs aberrante du pixel, qui ne suivent pas la distribution gaussienne « ordinaire »), on peut utiliser une analyse statistique pour les détecter, et réduire leur poids.

La méthode de Lucas-Kanade en soi peut être utilisée uniquement quand le déplacement ${\displaystyle V_{x},V_{y}}$ entre deux images est petit pour que l'équation différentielle du flot optique soit vérifiée, souvent inférieur à un pixel. Quand le déplacement dépasse cette limite, la méthode de Lucas-Kanade est encore utilisée pour raffiner des estimations grossières; par exemple, par extrapolation du déplacement calculé auparavant, ou en utilisant l'algorithme de Lucas-Kanade sur une version réduite des images. En effet, cette dernière méthode est fondée sur la méthode de Kanade-Lucas-Tomasi (KLT).

Une technique similaire peut-être utilisée pour calculer les déformations affines différentielles de l'image.

• Flux optique
• Méthode de Horn–Schunck (en)
• Algorithme de Farneback