Discussion :

[sjunod]

Bonjour,

Dans le cadre d'un projet, je dois pouvoir faire "matcher" des images (niveaux de gris).

Le but est (dans une interface utilisateur) charger trois image, de les aligner au mieux et d'obtenir une sorte de score (ou d'erreur) permettant d'avoir une donnée objective sur la qualité du matching.

Les trois images représentent la même chose, mais ne sont pas identiques (Ces images représentent en quelque sorte des croissants de lune de différentes épaisseurs et dont la forme générale peu légèrement varier ainsi que différentes formes pouvant varier légèrement dans leur position et forme).

Actuellement j'effectue un pré-alignage, avant ICP, assez simple de la manière suivante :
Manuel :
Translation-Rotation

Automatique:
1. Alignement des centres de masse
2. Légères rotations et translations (intervalles spécifiés)
3. Recherche du meilleur alignement avec la fonction corr2.

J'utilise ensuite un algorithme ICP (Téléchargé sur MathWorks). Les résultats sont assez prometteurs, malheureusement parfois l'alignement n'est pas optimal (Minimum local ?).

J'ai regardé du côté de Image Processing Toolbox > Image Registration, mais cela ne semble pas s'appliquer à mon cas.

Existerait-il une manière générale plus performante permettant d'effectuer un tel alignement en diminuant au maximum les actions de l'utilisateur (L'idéal serait entièrement automatique) ?
Avez-vous une idée d'un autre algorithme que l'ICP pouvant effectuer un tel travail ?

Je précise que je suis débutant en Matlab, et que je suis ni mathématicien, ni informaticien.

J'espère que j'ai été assez clair. Si ce n'est pas le cas, je peux compléter les informations données.

Merci d'avance.

[pseudocode]

Comme toujours dans les problèmes de matching, il faut être clair sur la définition mathématique de la notion "alignement". Généralement il s'agit de minimiser une distance. Mais quelle est cette distance ?

distance moyenne, maximale, commune ?
distance entre des valeurs, des positions, les 2 ?
distance entre des contours, des surfaces, des intensités, les 3 ?
etc.

[sjunod]

OK, merci déjà de votre réponse. Voici un peu plus d'informations, je précise que je suis sous MATLAB:

comme déjà dit, les trois images représentent la même chose, mais ne sont pas identiques.

Les formes présentent sur les trois images sont des traces formées par un certain phénomène. Ces traces laissées sont partiellement variables. Elles sont alignées et superposées avec une transparence de 1/3 afin d'observer les zones les plus stables (les plus foncées). Ceci forme donc un modèle (tenant compte ainsi de la variabilité du phénomène ) pouvant être insérés dans une base de donnée. On peut ensuite a partir d'une image donnée, soumettre l'image à la base de donnée et ainsi la comparer à chaque modèle. Le modèle le plus probable (et par conséquent le phénomène le plus probable) est donc obtenu. Actuellement, je ne tiens pas encore compte, lors de la comparaison, du "poids" à donner aux zones déterminées les plus stables.

Ces images sont avant l'ICP convertie en binaire. Je ne sais pas exactement quelle distance l'algorithme ICP minimise (comme déjà dit ce n'est pas moi qui l'ai fait et mon niveau en algorithmique est assez faible). Je ne sais pas trop donc actuellement quelle distance est minimisée, mais mon but est que la distance entre chaque points formant mon image soit minimisée (ou entre chaque surface) afin de former le fameux modèle. Je pense qu'on peux assimiler ça à des nuages de points dont la distance entre chaque points doit être minimisée.

Ai-je suffisamment compléter mon problème ?

Merci d'avance.

[pseudocode]

Voila 3 matching possibles d'un rectangle et d'un hexagone. Aucun n'est "mieux" que les autres, tant que la définition de "matching" n'est pas explicitée.

[sjunod]

Pour être plus explicite, je travaille sur les traces d'oreilles. Voici une image de 2 traces d'oreilles (trouvées sur Google) pour vous faire une idée de ce qu'il faut aligner (j'espère que la qualité suffit, je travaille actuellement avec des images en TIFF ~1000x1000)

Le meilleur "matching" est pour moi lorsque, par exemple, les deux traces sont visuellement le mieux superposées. Je ne peux expliciter mieux le matching, puisque je suis toujours à la minimisation de la distance entre chaque points, mais visiblement il semblerait que cela ne suffise pas...

Je comprend tout a fait la difficulté que vous avez à m'aider dans mon problème s'il n'est pas explicité clairement. Cependant ma volonté est justement de discuter d'une méthodologie génèrale différente à celle que j'utilise actuellement (ICP).
J'espère que j'ai tout de même réussi à expliciter ma vision du matching dans mon problème

[briqueabrac]

Dans les codes matlab disponibles pour le recalage/suivi par corrélation, tu peux regarder et lire les articles associés:

- le site de Matthews et Baker (Lucas Kanade 20 years on: a unifying framework)
- le site de Malis (Efficient Second-order Methods)
- le site de Dowson et Bowden (Mutual Information Lucas Kanade)

[pseudocode]

Cependant ma volonté est justement de discuter d'une méthodologie génèrale différente à celle que j'utilise actuellement (ICP).

L'ICP est une méthode itérative pour résoudre le problème de minimisation de distance. Cette méthode utilise un schéma explicite (Explicit and implicit methods) ce qui est peut-être la cause de tes ennuis.

Tu peux essayer de rajouter une heuristique de type RANSAC pour eviter la convergence vers un minimum local. Ça marche plutôt bien en général.

Tu peux aussi utiliser des méthodes plus compliquées qui utilisent un schéma implicite (moindres carrés, relaxation, ...) mais ce n'est pas dit pour autant que les résultats seront meilleurs.

[sjunod]

Merci beaucoup pour vos réponse.

Si j'ai bien compris, il n'existe pas d'algo tout fait pour lequel je peux simplement adapter mes données d'entrée pour le matching ?

[pseudocode]

Merci beaucoup pour vos réponse.

Si j'ai bien compris, il n'existe pas d'algo tout fait pour lequel je peux simplement adapter mes données d'entrée pour le matching ?

Il y a des algos "tout fait" dans des cas précis. Mais il n'y a pas d'algo universel qui marche dans tous les cas, car tout dépend de ta définition personnelle du "meilleur matching possible".

[sjunod]

Et dans le cas où c'est la distance entre les points que j'aimerais minimiser ?

[pseudocode]

Et dans le cas où c'est la distance entre les points que j'aimerais minimiser ?

Ah... Distance entre les points... Distance max entre un point et tous les autres... Distance min entre un point et son plus proche voisin... Distance moyenne entre un point et ses plus proches voisins dans un rayon donné...

Pour ton problème, essaye déjà d'ajouter l'heuristique RANSAC sur ton ICP. C'est un bon début.

[sjunod]

Ok merci ! Je vais voir ce que je peux faire avec RANSAC.

Dernière question, connais-tu un liens du type "RANSAC pour les nuls" qui pourrai me permettre de bien cerner ce que je dois faire sans prendre de cours de mathématiques avancés ?

[pseudocode]

Dernière question, connais-tu un liens du type "RANSAC pour les nuls" qui pourrai me permettre de bien cerner ce que je dois faire sans prendre de cours de mathématiques avancés ?

Heu... non. RANSAC est une heuristique simple, donc pas besoin de mathématiques avancées. L'idée générale pour l'utiliser avec l'ICP c'est:

1. on génère des paires de points possibles entre les 2 images selon la méthode ICP (= points de l'image A qui sont proches des points de l'image B).
2. on calcule la transformation T qui aligne le mieux les paires de points.
3. on applique cette transformation à TOUS LES POINTS de A => on modifie la position de tous les points de A
4. retour à l'étape 1.

Je suis sûr que tu trouveras pleins d'exemples sur google.

[sjunod]

Merci

Je vais voir ce que je peux faire. Si j'obtiens de meilleurs résultats je vous le ferai savoir. Je me permets de revenir si j'ai d'autres questions.

Merci encore pour votre aide pseudocode et briqueabrac