Projet de Aboutabit et Beynet

1. Une Méthode itérative de recalage :

1°)Présentation du problême :

Le problème du recalage des images peut être traité par plusieures méthodes et algorithmes mathématiques. La méthode que nous allons présenter est connue comme efficace et robuste. On dispose de deux images (en 3D ou 2D), une étant l’image d'1 autre par une transformation rigide (rotation et/ou translation). L'application de cette méthode nécessite un travail préparatoire qui consiste à repérer différentes courbes sur chacune des deux images et à les représenter par des listes chaînées de points. Le but de cet algorithme est de faire correspondre chacune des courbes des deux images. Pour cela on utilisera un algorithme itératif : on réitèrera le calcul que nous allons décrire dans cette partie jusqu'à ce que la rotation R et la translation t obtenues donnent un résultat satisfaisant.

2°)Fondements mathématiques :

Nous présentons, dans cette partie, la méthode mathématique utilisée dans l'algorithme de recalage itératif. Cet algorithme utilise une repésentation matricielle utilisant des quaternions (vecteurs de R⁴ ) qui permettent de simplifier la démonstration mathématique et qui de plus, en évitant de manipuler des formules trigonométriques, donnent des résultats moins imprécis que ceux faisant appel à des fonctions comme sin,cos, ...

Pour plus de détails sur le fonctionnement de cet algorithme vous pouvez nous contacter ou vous reporter sur la page web de l'auteur du document sur lequel nous nous sommes appuyés : http://www-sop.inria.fr/robotvis/personnel/zhang/abstracts.html

2. Considérations pratiques et implémentation du programme :

1°)Condition d'appariement des closest points :

A chaque itération, le programme calcule une transformation T, ensuite il applique cette transformation aux points de l'image n°1: (ensembles de points X_i) et à chaque T(X_i) il cherche à quel point Y_i de l'image n°2 T(X_i) peut être apparié. Lorsque cet appariement est possible, on appelle "closets point" les points ainsi appariés.

Il faut pour que les closest points conviennent.

Il y a encore d'autres conditions que nous décrivons plus en détail dans notre compte-rendu.

2°)Algorithme général :

Arrivée à ce point, on peut donc résumer la structure qu’aura un programme voulant utiliser la méthode que nous venons de décrire :

• Entrées: 2 images 3 D.

• Sortie: la meilleure transformation entre les deux images.

• Détail du programme :

1. Initialisation : préparation à la première itération.

2. On rentre dans la boucle des itérations.

3. Recherche des closest points de l’itération n° i.Calcul de R et t minimisant F, selon l'algorithme décrit précédemment. (cf. §I.4)

4.On applique la transformation ainsi calculée à tous les points de l'image numéro 1.

6.On recommence la boucle avec la nouvelle image numéro 1 ainsi calculée et l'autre.

7.On retourne la transformation (R et t) lorsque le résultat est satisfaisant cf. §II.3.

3°)Condition d'arrêt du programme : (critère de convergence)

Dans notre compte-rendu, nous exposons une méthode possible pour coder la condition d'arrêt du programme, cette solution n'est pas unique mais est assez simple et fiable.En fait on stoppe les itérations lorsque :

où r_i représente l'axe de la rotation trouvée à l'itération n°i.

Et de même : où t_i est le vecteur de la translation trouvée à l'itération n° i.

3. Notre Programme :

1°)Structure du programme :

• histo.c : programme traçant l'histogramme des intensités (le spectre en niveau de gris) d’une image. Son but a été de nous familiariser avec la structure des images en niveau de gris. Retourne une image graphe.raw contenant ce spectre.

• rotation.c : ce programme lit une image (format raw). Pour chaque point de l'image finale il calcule (à l'aide de la matrice inverse de rotation) les coordonnées de son antécédent sur l'image d'origine. Ensuite deux méthodes d'interpolation différentes nous donnent l'intensité de ce point.

• coins.c : dans un premier temps, ce programme détecte les quatre coins du carré de chaque image, ceci afin de créer les listes représentant chacun des côtés. Ensuite notre fonction de recalage tente de retrouver l'angle de la rotation par la méthode itérative exposée.

2°)Notre cheminement :

Dans cette dernière partie nous décrivons le cheminement que nous avons suivi durant la conception de notre petit programme.