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.