Introduction :
Le programme réalisé et décrit ici a pour
fonction de retrouver un objet dans l’image d’une scène. Une utilisation
évidente est celle des robots manipulateurs ou mobiles qui doivent
« reconnaître » leur environnement, au moins en partie,
pour agir dessus.
On part donc de l’image d’une scène contenant des objets,
et d’une image ou d’un modèle de l’objet recherché. Le programme
doit alors donner la localisation de l’objet recherché dans la scène,
sachant que celui-ci peut être partiellement caché.
Nous allons expliquer ici les choix faits concernant les algorithmes,
détailler les algorithmes choisis, et donner les résultats
obtenus et les améliorations possibles du programme.
Algorithmes utilisés
Il faut tout d’abord extraire les contours des objets de l’image de la scène (éventuellement de celle du modèle) et les chaîner pour pouvoir les utiliser. Ceci est fait par un autre programme qui rend dans un fichier les chaînes de pixels de contour trouvées. Ce sont ces chaînes qui vont être utilisées par notre programme.
Il faut ensuite mettre ces chaînes sous une forme plus simple pour pouvoir les utiliser dans la recherche. On choisit ici de les approcher par des segments qui seront les « primitives » constituant le modèle des objets utilisé dans l’algorithme de recherche. On utilise pour cela un algorithme de « split » récursif qui calcule la primitive par interpolation puis, si l’erreur est trop grande, coupe la chaîne au point le plus éloigné de la primitive et réitère l’opération sur les deux morceaux formés.
Une fois ces « primitives » extraites, on aborde le
cœur du programme : l’algorithme de recherche qui doit retrouver les
« primitives » de l’objet dans celles de la scène. Une
possibilité consiste à faire l’équivalent d’une transformée
de Hough : on calcule l’image de l’objet par toutes les transformations
possibles et on regarde si cette image correspond à la scène.
L’inconvénient est que cet algorithme est très lourd en temps
de calcul (le nombre de transformations possibles est en n4, si n est la
dimension de l’image).
Une autre possibilité est d’extraire des relations entre
les primitives de l’objet telles que parallélisme ou adjacence,
de même pour la scène. On construit alors un graphe dont les
sommets sont les couples de primitives de l’objet et de la scène
(Mi,Sj). (Mi,Sj) et (Mi’,Sj’) sont reliés si les relations entre
Mi et Mi’ sont les mêmes qu’entre Sj et Sj’. Trouver l’objet dans
la scène revient alors à trouver le plus grand clique (sous-graphe
entièrement connecté) du graphe. Cependant, c’est un problème
qui peut être très consommateur de temps car NP-complet.
La possibilité retenue ici consiste à essayer de
faire correspondre une primitive de l’objet avec chacune des primitives
de la scène et de calculer l’image de l’objet par les deux transformations
correspondantes (différentes d’une rotation d’angle pi). On compare
alors l’image de l’objet ainsi obtenue avec la scène en essayant
de faire correspondre chacune des primitives de l’objet avec une des primitives
de la scène. On compare à chaque fois l’erreur avec une valeur
limite pour déterminer si la correspondance est acceptable.
Pour prendre en compte le fait que l’objet peut être caché
en partie, on introduit dans le modèle de la scène une primitive
supplémentaire. Toute primitive de l’objet liée à
celle-là est considérée comme cachée.
Les résultats
Dans le programme, les modèles de l’objet et de la scène
sont stockés dans les « figures » « modele »
et « scene ». Le parcours d’une branche de l’arbre de recherche
s’arrête dès que la valeur limite de l’erreur est atteinte.
L’arbre n’est donc pratiquement jamais parcouru en entier, mais la valeur
maximale de l’erreur doit être ajustée en fonction des circonstances.
Comme celui-ci plante toujours à l’heure où j’écris
ce rapport, je ne peux pas donner de résultats concrets obtenus
avec mon programme.
Améliorations
Le programme ne prend pas en compte le cas où le premier
segment de l’objet est caché. Il faudrait dans ce cas reprendre
la recherche à partir du deuxième segment pour pouvoir calculer
les transformations.
Il peut y avoir aussi un léger décalage entre la
position réelle de l’objet et celle trouvée, du fait de l’imprécision
liée à l’approximation par des segments des contours. Cette
erreur pourrait être réduite en appliquant une petite transformation
supplémentaire à l’objet, après que toutes ses primitives
aient été reliées à des primitives de la scène.
On pourrait aussi tenter d’améliorer le programme en essayant
de relier les primitives de l’objet en priorité aux primitives de
la scène qui leurs sont proches, mais cela est pris en compte en
abandonnant un essai de liaison dès que l’erreur est trop grande,
sans essayer de lier les autres primitives de l’objet.
On peut envisager aussi d’introduire des primitives autres que
des segments pour prendre en compte les cercles et les formes courbes.
Toutefois, en deux dimensions, cela risque de compliquer inutilement le
programme.
3D
Les algorithmes utilisés sont directement transposables
en 3D. Il vaut mieux dans ce cas disposer d’un modèle en 3D de l’objet
à chercher. On peut alors essayer de calculer un modèle en
trois dimensions de la scène, puis appliquer la méthode précédente.
Une méthode plus simple serait d’essayer de lier deux primitives
(ici, ce sont des arrêtes) de l’objet avec deux primitives d’une
image en 2 dimensions de la scène, d’en déduire la position
dans l’espace de l’objet, d’appliquer la méthode précédente
à la projection sur le plan de l’image de l’objet, puis de vérifier
dans les autres images de la scène dont on disposerait.
De nouveaux problèmes se posent toutefois avec le passage
à la troisième dimension comme les contours de l’objet cachés
par l’objet lui-même, ou la gestion des contours des formes courbes.
On peut envisager d’utiliser pour cela des primitives qui soient des volumes
géométriques ou des surfaces, et non plus des segments.