Méthode de Lucas–Kanade

Dans le domaine de la vision par ordinateur, la méthode Lucas–Kanade est une méthode différentielle utilisée pour l'estimation du flux optique. Cette méthode a été développée par Bruce D. Lucas et Takeo Kanade. Elle suppose que le flot est essentiellement constant dans un voisinage local du pixel considéré, et résout l'équation du flot optique pour tous les pixels dans ce voisinage par la méthode des moindres carrés^[1]^,^[2].

En combinant les informations des pixels proches environnant, la méthode de Lucas-Kanade peut souvent résoudre l'ambiguïté inhérente de l'équation du flot optique : le problème de l'ouverture. Cependant, comme c'est une méthode purement locale, elle ne peut pas fournir d'information sur le flux à l'intérieur d'une région uniforme de l'image.

Principe[modifier | modifier le code]

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

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})

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

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

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 :

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

ou

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

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

{\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 $A^{T}A$ est appelée le tenseur de structure de l'image au point p.

Fenêtre pondérée[modifier | modifier le code]

La solution donnée ci-avant donne la même importance à tous les n pixels $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,

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

ou

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

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

{\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 $w_{i}$ est habituellement un ensemble de Gaussienne de la distance entre $q_{i}$ et p.

Améliorations et extensions[modifier | modifier le code]

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 $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).