Projet Réalisé par Jean-François
Bobier (promo 96)
 |
 |
Objectif
Il s'agit, à partir d'une séquence animée, d'être capable de suivre un objet donné afin de remplacer un motif du choix de l'utilisateur. Ici, l'objet est le panneau de la fourgonnette, sur lequel nous désirons placer, pour fixer les idées, une publicité pour l'Ecole Polytechnique.
 |
Le logiciel suit au cours du temps 4 points caractéristiques appartenant au plan du panneau (supposé parfaitement plan, ce qui n'est pas rigoureusement le cas, car il est légèrement bombé). |
|
Il conserve une petite historique des emplacements de ces 4 points, ce qui lui permet d'évaluer leurs vitesses et leurs accélérations notamment. |
|
La
séquence étant "réelle", elle est donc
"continue" et c'est par
conséquent le cas des vitesses et des accélérations.
Cette propriété importante permet de prédire
l'emplacement suivant d'un point par un développement
limité de Taylor :
|
|
Il suffit ensuite de choisir des points suffisamment caractéristiques pour qu'une recherche locale autour des points prédits permette de retrouver aussi rapidement que possible leurs coordonnées réelles. |
|
Muni de ces 4 points et d'un modèle de leur emplacement sur le panneau, le logiciel calcule l'homographie menant de ce modèle vers les points mesurés, puis applique la publicité choisie. |
|
Les 4
points choisis sont des coins extraits
dans l'image à des emplacements dont l'éloignement
mutuel est grand et facilement reconnaissables par
l'algorithme.
|
|
|
Nous nous
munissons d'un détecteur de coins. A l'aide des travaux de Rachid Deriche , nous implémentons les filtres de laplacien (dont les zéros déterminent le contour) et de gradient. De plus, nous enlevons à la carte de contour tout contour de taille (composante connexe) inférieure à 10, par exemple. Ceci nous permet d'obtenir une carte de contours comme suit :
La carte des contours par les zéros du laplacien Le calcul du coin se fait à l'aide de la mesure DET de Beaudet. DET est un scalaire proportionnel à la courbure fondé sur les invariances par rotation. Donc, si DET est grand, le pixel du contour testé est très probablement un coin (moyennant le bruit, malheureusement doté d'assez grandes courbures). De plus, DET présente l'intérêt de présenter des maxima bien localisés et une "continuité" qui permet de discriminer deux coins proches - pour s'en convaincre, il suffit regarder sa formule de définition :
où I(x,y) est l'image à traiter. Nous établissons une carte de coins en cherchant les maxima locaux de DET puis seuillage :
La carte des coins : les DET<0 en Vert et les DET>0 en Rouge, l'intensité de la couleur est proportionnelle au DET |
|
|
L'algorithme
calcule l'homographie entre un modèle plan du panneau et
des points choisis.
Grâce aux travaux sur la stéréovision, nous savons qu'il existe une matrice H (H pour homographie) telle que : x'i = h11 xi + h12 yi + h13 zi où ( x'i/z'i ,
y'i/z'i ) sont les coordonnées de l'image destination
(dans notre exemple, l'image ci-dessus) zi et z'i servent simplement à linéariser le problème; pour le calcul à partir des coordonnées mesurées, nous les prenons égaux à 1. Multiplions chaque ligne par la relation de définition de z'i, il vient : x'i.(h31 xi + h32 yi + h33 zi) = z'i.(h11
xi + h12 yi + h13 zi) Soit A.H = 0 avec :
4 points fournissent 8 équations, or puisque H est définie à un facteur multiplicatif près (de par le fait que seul x'i/z'i et y'i/z'i nous intéressent au final), cela permet dans les cas non triviaux (alignement...) de déterminer H, comme le montre l'exemple précédent. |
|
|
Le suivi proprement
dit se fait coin par coin, indépendamment les uns des
autres. Après application directe de l'équation de suivi, il nous faut choisir le bon coin parmi les coins proches du coin prédit. Cette situation se présente de nombreuses fois dans la séquence fournie, notamment pour le coin inférieur droit. L'expérience prouve que la valeur de DET garde le même ordre de grandeur et le même signe pour un coin donné au cours du suivi : c'est une hypothèse de continuité assez forte, toutefois justifiée par l'équation de définition et la robustesse remarquable au bruit du filtre de Deriche. Nous cherchons dans une zone d'incertitude autour du coin prédit dont la taille est proportionnelle à l'accélération. Dans cette zone, nous cherchons les candidats potentiels - c'est-à-dire les points dont le DET présente le même ordre de grandeur et le même signe que le coin suivi. Nous élargissons éventuellement la zone si celle-ci ne présente pas assez de candidats. Enfin, nous choisissons le coin dans la liste des candidats possibles en fonction de deux facteurs : - l'éloignement
au point prédit (si on a un peu trop élargi la zone) |
Efficacité de l'algorithme
L'algorithme parvient à suivre la séquence exemple comme le montre le GIF animé liminaire. La méthode, de par sa nature locale, est extrêmement rapide une fois le filtre calculé (lui-même assez peu coûteux en temps de calcul) - elle présente donc un grand intérêt lorsque l'on désire suivre plusieurs objets sur une même image. En revanche, le bruit pose de nombreux problèmes, notamment en créant des coins fantômes mais aussi en empêchant une localisation précise du coin sur le contour.
Enfin, notons que ces difficultés peuvent être contournées en suivant plus de quatre points toujours coplanaires bien sûr et en utilisant l'homographie avec des méthodes d'optimisation et/ou élimination/déplacement.
