Discussion :

[Pepper13]

Bonjour à toute la communauté.

Je cherche à recaler (*) à l’aide d’une transformation rigide (rotation+translation) deux nuages de points 2D. Dans ces nuages, il existe un certain nombre de points qui leur sont communs; les autres points sont considérés comme du bruit.

Ma question est toute simple : je voudrais constituer une liste d’algos qui permettent la mise en correspondance des points communs aux deux nuages…

Par exemple, j’ai déjà trouvé ces algos là :
- ICP (Iterative Closest Point)
- RANSAC
- Méthodes « feature-based »

Auriez-vous d’autres idées ??

Un grand merci d’avance pour votre aide !!
Pepper.

(*) = « superposer géométriquement »

[ToTo13]

Bonjour,

et une mise en correspondance avec le barycentre et l'axe principal ? C'est simple, mais peu apporter de bon résultats si les nuages ne sont pas trop différents.

[Pepper13]

Bonjour et merci pour votre réponse.

Une ACP donc ? C'est une idée, je la note dans ma liste ;-)

D'autres idées ?

Pepper.

[souviron34]

Je cherche à recaler (*) à l’aide d’une transformation rigide (rotation+translation) deux nuages de points 2D.

Juste ça ? pas de facteur de zoom ?

[Pepper13]

Oui, juste une transfo rigide...

[pseudocode]

Si on peut avoir une bonne première estimation, il y a la descente de gradient sur la distance de chamfer.

[Pepper13]

Bonjour et merci pour votre réponse.

Disons qu'avec cette proposition, de petites améliorations en petites améliorations, on va très vite retomber sur un algo de type ICP (Iterative Closest Point). Ce que l'on aura changé par rapport à la publication originale, c'est la distance (euclidienne --> chanfrein) et l'ajout d'une descente de gradient qui n'a pas lieu d'être, puisque l'estimation des paramètres d'une transformation rigide peut se faire directement (exemple : décomposition SVD).

Donc je ne la note pas dans ma liste ! ;-)

Pour l'instant j'ai donc :
- ICP (Iterative Closest Point)
- RANSAC
- Méthodes « feature-based »
- ACP (merci Toto13 ^^)

[pseudocode]

Disons qu'avec cette proposition, de petites améliorations en petites améliorations, on va très vite retomber sur un algo de type ICP (Iterative Closest Point). Ce que l'on aura changé par rapport à la publication originale, c'est la distance (euclidienne --> chanfrein) et l'ajout d'une descente de gradient qui n'a pas lieu d'être, puisque l'estimation des paramètres d'une transformation rigide peut se faire directement (exemple : décomposition SVD).

Ah... c'est sûr que si tu changes la distance, la fonction de coût, et la méthode de minimisation... et bien ça change l'algo.

[Pepper13]

Ah ben vi ! L'algo change strictement parlant... mais pas sa "classe" ! :-)

ICP c'est un ensemble d'algos qui fonctionnent de la manière suivante :
Basés sur la recherche du point le plus proche, ils calculent, de façon itérative, la matrice de transformation permettant d’effectuer le recalage. Leur principe est d'itérer les deux étapes du recalage: la mise en correspondance des points et l'estimation de la transformation entre les nuages à recaler. Au bout de chaque itération, l'algorithme fournit une liste de points appariés et une estimation de la transformation de recalage. Cette transformation est utilisée à l'itération suivante pour la mise à jour de la liste des points appariés. Ces derniers serviront, à leur tour, pour calculer une nouvelle estimation de la transformation. Ces étapes sont répétées jusqu'à convergence de l'algorithme.

Après, il existe tout un tas de sous-déclinaisons où effectivement on change la distance, la fonction de coût, la méthode de minimisation… etc… mais fondamentalement, le principe est celui que je viens de décrire. C’est pourquoi je n’ajoute pas cette proposition à ma liste !

Moi en parallèle, je continue mes recherches :

- ICP (Iterative Closest Point)
- RANSAC
- Méthodes « feature-based »
- Méthodes statistiques (exemple : ACP)
- Méthodes spectrales (exemple : transformation Fourier-Mellin même si je me fous du facteur de zoom)

Ceci dit, je reste évidemment preneur de vos idées !

[pseudocode]

Pour moi, l'ICP est une sorte de "méta-algo", dans le sens où on peut l'utiliser "au dessus" des autres méthdoes.

Tes points peuvent être des coordonées (ton ICP de base), des features (SIFT, ...), des descripteurs (fourier, ...). L'appariement peut être fait de manière aléatoire (ransac) ou statistique (ACP).

Mais bon, j'ai un esprit tordu.