Majeure "Mathématiques et Informatique" Enseignement d'approfondissement "Images: Analyse et Synthèse"

Hyper 2D

Projet Réalisé par Vincent Julliand (promo 95)

Description du projet

Dans ce projet, on suppose que l'on dispose d'une caméra qui observe une scène. Cette scène contient certains objets dont le modèle est connu (par exemple un boulon). L'objectif est d'identifier ces objets dans la scène. Ceci pourrait par exemple permettre la conduite d'un robot ou d'un bras chargé de trier un certain nombres de pièces. Pour des raisons évidentes, nous ne condidérerons ici que des objets indéformables, mais nous autoriserons de possibles chevauchements (parties cachées).

Afin de faire la correspondance entre deux images (celle d'un objet simple-le modèle- et celle de la scène), il est nécessaire de choisir des primitives et de les extraire. Nous avons choisi les primitives les plus simples possibles, à savoir les contours des objets (extraits par une méthode du type variations du gradient) que l'on approxime par des polygones. Une première partie du projet aura donc consisté à extraire ces primitives. La seconde partie (la plus intéressante) consiste à implémenter l'algorithme de reconnaissance.

Algorithmes utilisés

Pour l'extraction des contours, nous avons utilisé un algorithme dit de "split". Nous disposons au départ de chaînes de pixels qu'il s'agit d'approximer. Le principe est simple: étant donnée une chaîne (M₀,..,M_n), on parcourt toute la chaîne et on détermine le point M_k de la chaîne le plus éloigné du segment [M₀M_n]; on applique ensuite l'algorithme récursivement sur les deux sous-chaînes (M₀,..,M_k) et (M_k,..,M_n) .

La reconnaissance proprement dite peut se faire de différentes manières. Ainsi existe-t-il des algorithmes inspirés de la transformation de Hough. On peut aussi utiliser des graphes pour représenter les segments et leurs interactions(proximité,...). Pour plus de précisions sur ces méthodes, on pourra se reporter au livre d'Olivier Faugeras [1].

Le point de départ de la méthode utilisée est la donnée des segments (M₀,..,M_n) du modèle et des segments (S₀,..,S_p) de la scène. L'algorithme est simple: on passe en revue tous les couples (M₀,S_j) (j<p) et on calcule les transformations rigides T_0j associées (décrites par un facteur d'échelle, une rotation, et une translation). Ensuite, on calcule les images T_0j( M_i) pour i>0 des segments du modèle et on cherche pour chacun des segments images le segment de la scène le plus "proche", s'il existe. A la fin, on peut donc juger de la pertinence de la transformation T_0j en fonction des erreurs calculées. On répète la même opération pour les autres transformations T_ij qui à M_i associe S_j (l'exploration pour les i>0 suppose que les segments M _k où k<i n'ont pas de correspondant dans la scène -ce qui peut arriver dans le cas où il y a des arêtes cachées.). On dispose ainsi d'un tableau de transformations T_ij (associées à une erreur) dont on peut déterminer les meilleurs candidats pour la reconnaissance.

Résultats obtenus

L'extraction de contours et l'approximation polygonale ont donné de très bons résultats, sauf dans le cas d'objets circulaires ( l'algorithme introduit alors des sommets de façon peu contrôlable).

L'algorithme de reconnaissance de formes nous fournit un certain nombre de réponses pondérées par des erreurs. Voici un exemple de reconnaissance effectuée en prenant pour modèle le trapèze suivant (Cliquez pour voir la grande image, les segments reconnus sont en vert):

donne les résultats:

Problèmes rencontrés et solutions apportées

L'implémentation de l'algorithme en tant que tel ne présentait pas de grandes difficultés. Les problèmes les plus importants ont consisté à trouver de "bons" seuils d'erreurs afin de déterminer si l'association entre deux segments était légitime ou non. C'est en effet une condition nécessaire à la robustesse de l'algorithme, qui ne doit pas dépendre de différences d'échelle entre scène et modèle. On a retenu la formule suivante:Erreur=(d₁+d₂)/echelle où l'échelle est le rapport S₁S₂/M₁M₂.

De plus, il fallait faire en sorte de pénaliser une séquence dans le cas où un segment important du modèle ne trouvait pas d'image dans la scène. La solution retenue (et qui fonctionne bien) fut d'ajouter la longueur du sement célibataire à l'erreur de la séquence.

Pour toute question, n'hésitez pas à me contacter: mailto:Vincent.Julliand@polytechnique.fr

[1] Olivier.D Faugeras Three-dimensional Computer Vision:a geometric point of view MIT Press 1993