R6.06 - Techniques d'optimisation

Le travail, à rendre pour le lundi 22 juin à 18h au plus tard, est constitué de deux parties :

1. Le programme que vous deviez faire dans le cadre du Cours 3, à savoir l'implémentation de l'optimisation par essaim de particules et son application aux fonctions de Rosenbrock (F2) et Ackley (F11) ;
2. Un programme implémentant le recalage d'images 2D par évolution différentielle, un algorithme évolutionnaire, comme décrit ci-dessous. Vous n'oublierez pas d'inclure le jeu d'images que vous aurez créé.

Chaque programme devra être commenté, de même que chacune des étapes qui le compose.

Vous rendrez vos programmes (sous forme d'archive le cas échéant) en envoyant un email à l'adresse michel.salomon@umlp.fr

*****

Projet : Recalage d’images 2D par évolution différentielle

Contexte

Le recalage d’images est une opération base en traitement d’images et en vision par ordinateur. Il consiste à aligner deux images représentant une même scène ou un même objet acquis à des instants différents, sous des angles différents ou à l’aide de capteurs distincts. Cette technique est largement utilisée dans des domaines tels que l’imagerie médicale, la télédétection, ou encore la robotique.

Les méthodes classiques de recalage reposent souvent sur des approches d’optimisation locale, qui peuvent être sensibles à l’initialisation et se retrouver bloquées dans des minima locaux. Les algorithmes évolutionnaires, et notamment l’algorithme d’évolution différentielle (Differential Evolution, DE), constituent une alternative intéressante grâce à leur capacité à explorer efficacement l’espace de recherche global.

Problématique

On considère deux images 2D :

• Une image de référence I_ref ;
• Une image source I_src à recaler.

L’objectif est de déterminer automatiquement les paramètres géométriques permettant d’aligner au mieux l’image source sur l’image de référence. Dans le cadre de ce projet, on se limitera à une transformation rigide comprenant :

• Une translation tx selon l’axe x ;
• Une translation ty selon l’axe y ;
• Une rotation θ dont le centre est le milieu de l’image.

Ce problème peut être alors formulé comme un problème d’optimisation, où l'on cherche un vecteur de paramètres qui minime une fonction de coût

arg min_ϴ C(I_ref(.),I_src(T_ϴ(.)))

avec :

• ϴ qui représente le vecteur des paramètres de transformation, soit ϴ = (x,y,θ)^T ;
• T_ϴ qui est la transformation géométrique appliquée à l’image source ;
• C, également appelé la fonction de coût, qui est une mesure de similarité entre les deux images (corrélation croisée, information mutuelle, erreur quadratique moyenne, etc.).

Objectif général

Développer une application permettant :

1. de charger deux images ;
2. d'estimer les paramètres de transformation par évolution différentielle ;
3. d'afficher le résultat du recalage ;
4. de mesurer la qualité de l'alignement obtenu.

Travail demandé

Étape 1 : Génération des données de test

À partir d'une image de référence :

• appliquer une rotation aléatoire comprise entre −20∘ et 20∘ ;
• appliquer une translation comprise entre −20 et 20 pixels ;
• générer automatiquement l'image déformée.

L'application doit mémoriser les paramètres réels afin de pouvoir comparer les résultats obtenus.

Étape 2 : Définition de la fonction coût

Choisir une mesure de similarité entre les deux images.

Par exemple, l’erreur quadratique ou sa moyenne, etc.

Le but de l'algorithme sera de minimiser cette erreur.

Étape 3 : Implémentation de l'évolution différentielle

Chaque individu de la population représente :

X=(tx​,ty​,θ)

avec :

• tx​∈[−20,20]
• ty​∈[−20,20]
• θ∈[−20∘,20∘]

Implémenter :

• l'initialisation de la population ;
• la reproduction des individus ;
• la sélection ;
• le critère d'arrêt.

Deux articles décrivant l'évolution différentielle : article général et un article plus ancien focalisé sur le recalage d'images

Étape 4 : Interface de visualisation

Créer une interface simple permettant d'afficher :

• l'image de référence ;
• l'image à recaler ;
• l'image recalée ;
• la superposition avant/après recalage ;
• la courbe d'évolution du coût au cours des générations.

Étape 5 : Analyse des performances

Tester plusieurs configurations :

Mesurer :

• l'erreur finale ;
• le temps d'exécution ;
• l'erreur sur les paramètres estimés ;
• le nombre de générations nécessaires à la convergence.

Résultats attendus

À la fin du projet, l'application devra être capable de :

• retrouver automatiquement la rotation et la translation appliquées à une image ;
• afficher les paramètres estimés et les paramètres réels ;
• produire un recalage visuellement correct.

Enfin, on vous demande de comparer l'évolution différentielle avec l'optimisation par essaim de particules.