Graph matching by simulated annealing.
Mise en correspondance de graphes par recuit simulé.
Résumé
Many image processing applications are based on image-model or image-image matching. When the data to compare are of different nature, a classical technique consists in representing them by graphs. So, the problem becomes a graph matching problem. The major difficulty is the size of the graphs in some applications, because the computation time increases exponentially with the number of nodes. Here, a solution to that problem, based on simulated annealing, is proposed. After a description of the proposed algorithm, a validation on image processing applications is discussed (registration of two images and stereo matching).
De nombreuses applications de traitement d'image reviennent à réaliser une mise en correspondance image-modèle, ou image-image. Dans le cas où les données sont de natures différentes, une technique classique consiste à les représenter sous forme de graphes. Le problème se ramène donc à de la mise en correspondance de graphes. La difficulté majeure liée à l'utilisation de telles techniques en analyse d'images provient du fait que les graphes ont souvent un grand nombre de nœuds. Une solution originale à ce
problème, basée sur l'utilisation du recuit simulé, est proposée dans cet article. Après une description de l'algorithme proposé, la méthode est validée sur des applications de recalage d'images et de mise en correspondance stéréoscopique.