ELECINF344/381

Partie interactive du site pédagogique ELECINF344/ELECINF381 de Télécom ParisTech (occurrence 2011).

Catégories

Copterix : Topo sur Lucas and Kanade

L’algorithme de Lucas et Kanade

Principe

Nous disposons de deux images en niveau de gris, A et B, espacées dans le temps de δt.
Nous cherchons à déterminer les vecteurs déplacement de certains points d’intérêt, que nous pouvons par exemple soit choisir arbitrairement, soit trouver grâce à un filtre de Sobel (détection de contours), soit finalement rechercher d’une manière plus lourde mais qui donne des résultats plus efficaces que nous aborderons dans la dernière partie. Bien entendu, un grand nombre de points d’intérêt permettrait d’avoir une meilleure estimation de la vitesse globale de l’image, mais une quantité plus faible de points d’intérêt demanderait moins de ressources système et de temps de calcul : un compromis est donc nécessaire pour les systèmes embarqués.
Nous nous donnons pour cela une fenêtre de recherche pour chaque point d’intérêt trouvé de taille 2*ωx+1 par 2*ωy+1 (en nombre de pixels). Une fois encore, une plus grande fenêtre permettrait de trouver une plus grande amplitude du mouvement, mais demanderait plus d’itérations (ce problème est en grande partie pallié par la forme pyramidale, que nous aborderons par la suite).
Il ne reste plus qu’à trouver le déplacement qui minimise l’erreur :


Développements

Nous commençons donc par calculer la dérivée de l’erreur par rapport au déplacement :

pour ensuite lui appliquer un développement de Taylor à l’ordre 1 autour du déplacement [0, 0] (valide si nous estimons que le déplacement est petit , ce que nous allons admettre) :

À partir d’ici, nous pouvons arrêter les calculs pour faire quelques considérations.
Tout d’abord, l’expression A(x, y) – B(x, y) fait penser à la dérivée de l’image dans le temps au point (x, y), que nous noterons dI(x, y).
Ensuite, les dérivées partielles de B en x et en y ressemblent à un gradient. Nous pouvons de plus considérer que la fenêtre étant grande en comparaison du vecteur mouvement, la dérivée de l’image dans la fenêtre sur l’image B sera la même que sur l’image A. Nous avons donc le gradient suivant :

pour tout (x, y) appartenant à la fenêtre :
Avec ces notations, nous obtenons :

Enfin, une légère transformation nous permet d’obtenir :

Si nous nous donnons :
et

nous pouvons réécrire l’équation précédente sous la forme :

Or, ne l’oublions pas, le but de cette démarche étant d’annuler la dérivée de l’erreur afin de la minimiser, nous avons


G est inversible si le gradient de A est défini, c’est-à-dire si la fenêtre se trouve dans l’image et que nous disposons d’un contraste suffisamment élevé dans la fenêtre (se référer à la dernière partie pour un choix correct des bons pixels à suivre).

Nous avons ici le moyen de calculer le vecteur déplacement ‘le plus cohérent’ qui permet de passer de l’image A à l’image B dans la fenêtre donnée.

Itérations sur k pour affiner la recherche

Le calcul précédent représente un unique passage de l’algorithme. Nous pouvons affiner le résultat en effectuant plusieurs passages, jusqu’à ce que, par exemple, la norme du déplacement soit inférieure à une valeur que nous pouvons choisir.
Pour un indice d’itération k, si nous avons un résultat , nous transformons B ainsi :


pour calculer :

Nous voyons ici l’intérêt de calculer le gradient sur A et non sur B car ainsi nous n’avons qu’à calculer b à chaque itération.
Nous obtenons le déplacement final suivant :

Du problème des déplacements de plus grande amplitude : la mise en pyramide

Nous avons vu dans la première partie que la fenêtre ne suffisait pas à obtenir un compromis satisfaisant entre vitesse de calcul et détection des grands mouvements.
Une solution à ce problème est l’utilisation de pyramides.

Nous nous donnons m niveaux de pyramide (souvent égal à 3) et nous appliquons l’algorithme entier à chaque niveau de Lm à 0.
À chaque niveau de la pyramide, nous construisons une image de résolution 2^L fois inférieure à l’image originale.
Nous gardons la fenêtre de la même taille et transformons les coordonnées des pixels à suivre pour rester cohérent avec la nouvelle résolution.
Pour obtenir le déplacement final, il ne reste plus qu’à sommer tous les déplacements trouvés mis à l’échelle :

Voici une petite illustration du procédé :

Certains pixels sont plus faciles à suivre que d’autres

Nous pouvons déterminer les meilleurs pixels à suivre en nous basant sur l’utilisation que nous souhaitons en faire.
Ici, ce sera le calcul de l’inverse de G qui sera déterminant, il nous faut donc un déterminant non nul pour chaque pixel de la fenêtre, ou bien, pour rester plus mathématique, une valeur propre minimale maximale.
Nous pouvons donc procéder de la manière suivante :

  1. Calculer G et sa valeur propre minimale λ pour chaque pixel de l’image A
  2. Retenir la plus grande valeur λ sur toute l’image (et s’arranger pour éviter que son pixel soit trop au bord pour faciliter les problèmes de fenêtrage)
  3. Garder les pixels qui ont un λ supérieur à un certain pourcentage de ce maximum (5 ou 10 % par exemple)
  4. Parmi les pixels sélectionnés, choisir ceux dont λ est le maximum dans leur voisinage 3×3
  5. Ne garder que les pixels qui ont une distance suffisante (5 ou 10 pixels par exemple)
  6. Enfin, supprimer les pixels de λ minimal pour respecter un seuil maximal de nombre de pixels à suivre que nous nous serons fixés

Cette procédure est un petit peu lourde, d’autant plus qu’il faudrait théoriquement la répéter à chaque nouveau couple d’images à traiter, c’est pourquoi nous pouvons garder les pixels suivis d’une image à l’autre sur par exemple 10 itérations avant de les rechercher à nouveau.

Conclusion

Nous avons vu la version de l’algorithme de Lucas et Kanade implémentée en openCV. Cet algorithme se révèle facile à comprendre et à implémenter, et est personnalisable à souhait pour s’adapter aux besoins exigeants des systèmes embarqués.

Source

Pyramidal Implementation of the Lucas Kanade Feature Tracker