Méthode de Lucas–Kanade

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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 flot optique. Cette méthode a été développé 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 basique du flot optique pour tous les pixels dans ce voisinage, 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)

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 :A v = 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 pour le principe des moindres carrés. Elle résout un système 2×2

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

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 Aest 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 W A v=A^T W b

ou

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

W est matrice diagonale n×n contenant les poids W_{i i} = 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 point 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_yente deux image 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 basée sur la méthode de Kanade-Lucas-Tomasi (KLT).

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

Voir aussi[modifier | modifier le code]

Références[modifier | modifier le code]

  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
  2. Bruce D. Lucas (1984) Generalized Image Matching by the Method of Differences (doctoral dissertation)

Liens externes[modifier | modifier le code]