Discussion :

[EaudeRoche]

Bonjour à tous,

je cherche à trouver une méthode pour calculer la transformée permettant de minimiser les distances entre 2 nuages de points reliés dans le temps.
Je pense travailler avec le langage R, mais ce n'est pas encore défini.

Je m'explique :
en input : j'ai 2 nuages de point (que je vais nommé {M1;M2;M3;...;Mi} et {N1;N2;N3;...;Nj) et leur liens (correspondant au couple (Mx,Ny) où x appartient à [1;i] et y à [1;j]).
Il ne peut pas y avoir de couple (Mx,My) ou (Nx,Ny)
Et il peut y avoir plusieurs couples avec un même point.
Chaque point apparait au moins une fois dans la liste des couples.

Mon but est de trouver la transformée globale permettant de transformer le nuage M en N en minimisant le plus possible la distance (le tout sans déformation).

Je pensais donc procéder comme suit :
- pour chaque x constant : pour tout y de [1,j] calculer le barycentre B(x) de tous les couples (Mx; Ny)
- pour tout x, calculer la distance entre Mx et B(x) c'est à dire le barycentre des points qui sont lié au point Mx dans le nuage N
- trouver la transformée (rotation, translation) minimisant ces distances d(Mx,B(x)) pour tout x.
C'est là où je bloque : je ne sais pas comment calculer cette fameuse transformation....
Connaitriez vous des algos/formules connus pour faire ça ?

Plusieurs autres intérogations (moins importante) que lesquels j'aimerais vous demander votre avis :
- ne vaut-il pas mieux utiliser le point de Fermat ?
- j'ai lu quelques infos sur l' "Iterative Closest Point", mais à ce que j'ai compris, ça ne fonctionne pas dans le cas où l'on a relié les 2 nuages de points...

N'hésitez pas à me poser des questions si ce n'est pas clair.

[tbc92]

Bonjour,
Il y a des mots que je découvre (point de Fermat, Iterative Closest Point) ; je ne suis donc pas un spécialiste de la question.
Ceci dit, essayons.
Tu as un nuage M, et un nuage B (... je fais l'impasse sur N), chaque Point de M est associé à un point de B, et ce que tu cherches, c'est quelle est la forme de la transformation qui permet de passer de M à B.
Et tu listes 2 types de transformation : Rotation et Translation.
C'est là que tu te trompes.
Si tu te limites à Rotation et Translation, tu n'as aucune chance de trouver. Si tu fais une rotation de ton nuage M, tu ne modifies pas la forme du nuage. Les distances entre les points 2 à 2 sont conservées, ainsi que les angles. Si 3 points sont alignés, il resteront alignés après une rotation.
Idem avec les translations, les formes sont conservées.

Parmi les autres transformations 'standard', il y a les homothéties, ou les symétries. Mais la aussi, les angles sont conservés.

Sauf cas très particulier, tu ne trouveras pas de transformation 'standard' qui te permette de passer de M à B.

A priori, si tu réduis ton nuage M à 4 points symboliques, et donc ton nuage B à 4 points, là, tu vas pouvoir trouver les rotations / translations / homothéties à appliquer pour passer de M à B. Puis restera à 'propager' cette transformation aux autres points du nuage.

[EaudeRoche]

Merci pour ta réponse

En réalité si, je veux justement conserver les distances entre mes points pour chaque nuages. Si tu veux : je leur cherche un repère commun pour pouvoir plus facilement les comparer, donc je ne vois que les rotations et les translations pour mon problème...
Il est important que je conserve cette relation entre mes 2 nuages : limiter mon énorme nuage à quelques points ne serait pas forcément pertinent, même si je fais une moyenne des points alentours et en tenant compte des relations de ces points dans chaque nuage.

J'ai trouvé les méthodes qui me permettent de tout faire dans des bibliothèques de Singular Value Decomposition (SVD).