J'essaie de détecter automatiquement l'axe de rotation sur un pointCloud 3D.
En d'autres termes, si je prenais un petit pointCloud 3D, a choisi un seul axe de rotation et effectuez plusieurs copies des points à différents angles de rotation, puis je reçois un plus grand pointCloud.
L'entrée de mon algorithme est le plus grand pointCloud et la sortie souhaitée est l'axe unique de la symétrie. Et finalement, je vais calculer les correspondances entre les points qui sont des rotations les uns des autres.
La taille du plus grand pointCloud est de l'ordre de 100k points et le nombre de copies de rotation faites est inconnu.
Les angles de rotation dans mon cas ont des deltas constants, mais ne couvrent pas nécessairement 360 degrés. Par exemple, je pourrais avoir 0,20, 40, 60. Ou je pourrais avoir 0,90, 180, 270. Mais je n'aurai pas 0, 13, 78, 212 (ou si je fais, je m'en fiche le détecter).
Cela ressemble à un problème de vision de l'ordinateur, mais j'ai du mal à comprendre comment trouver avec précision l'axe. L'entrée sera généralement très propre, proche de la précision du flotteur.
Je n'ai pas l'original plus petit pointCloud qui a été tourné / copié pour faire le plus grand pointCloud. Je sais que les données sont synthétiques avec très peu de bruit (c'est généralement la sortie d'un autre programme).
Nous ne pouvons pas facilement calculer le nombre possible de points de points dans le plus petit nuage, car le long de l'axe n'est pas dupliqué, malheureusement. Si nous savions quels points se trouvaient le long de l'axe, nous pourrions trouver des facteurs possibles, mais nous aurions déjà résolu le problème.
-
Merci à tous pour vos suggestions. On dirait que mon algorithme final va essayer de trouver des cliques de points correspondants à l'aide d'une métrique K-NN. Chaque clique donnera un axe. Je peux ensuite utiliser Ransac pour adapter un axe aux résultats de toutes les cliques.
9 Réponses :
1) Si vous trouvez le Centroid C de la plus grande pointucloud, ISTM l'axe de rotation d'origine devrait passer à travers ce point.
Peu importe: je n'ai pas vu l'obligation que les rotations ne puissent pas couvrir un cercle complet. Pour votre exemple 20,40,60, le Centroid ne serait pas sur l'axe de rotation.
Peut-être que la référence suivante aiderait-elle?
"Reconstruction de surfaces de la révolution avec un échantillonnage partiel" http://portal.acm.org/citation.cfm?id=980064
Je pense que cela rompt si votre pointCloud forme un cône. P1 serait à la base du cône, mais c serait plus éloigné de l'axe. Ensuite, P1-C ne serait pas normal à l'axe, malheureusement.
Certains points :)
Ce que je veux dire, c'est que l'axe de rotation d'un corps rigide est identique à celui de l'axe de rotation de toute particules du corps. Nous n'avons pas besoin de se soucier de tous les autres points.
Comment puis-je obtenir le locus si je ne connais pas l'axe ou la correspondance entre points?
Points en mouvement pour connaître la position initiale du point. En connectant chaque position successive de point sur un précédent, vous pouvez obtenir un locus? Par locus, je veux dire le chemin que le point va tracer en tournant.
Je crois comprendre qu'il n'a pas accès aux points tels qu'ils tournent, il n'a que le produit final (le grand nuage de points).
Il ne sait pas que le point X et le point Y sont en fait le même point tourné, je pense.
@Ron, il semble donc qu'il veuille trouver l'axe de symétrie et non rotation. à droite?
C'est correct, tout ce que j'ai est un pointCloud avec une certaine connaissance du processus qui l'a créé. Le PointCloud contient des copies tournantes d'un original, et j'essaie de trouver l'axe de symétrie (ou des points de correspondance à leurs positions successives me permettraient de trouver l'axe facilement).
Oh je vois des difficultés en effet et intéressantes;) J'essaie :)
Cela pourrait être insoluble dans certains cas, nous avons besoin d'un nombre suffisant de points correctement tournés.
Choisissez n'importe quel point et trouvez deux autres points équidistants. Cela devrait prendre le pire des cas O (n ^ 2), mais les heuristiques peuvent grandement réduire cela. Ces trois points déterminent de manière unique un cercle. S'il y a un quatrième point à la même distance entre le premier ou les troisièmes, cela augmente considérablement votre confiance dans le cercle.
Le centre du cercle est un point de l'axe et le vecteur normal du cercle est le vecteur directionnel de l'axe.
Compte tenu de l'axe, vous pouvez déterminer l'angle entre les rotations et vérifier votre conjecture avec d'autres points. Si c'est faux, choisissez un autre point et recommencez.
Edit: Au fait, il est évident que cela n'est pas déterministe, mais si vos données de points sont aussi propres que vous dites et que vous utilisez de bonnes heuristiques, il devrait être assez précis.
Pourquoi le centre de ce cercle se trouve-t-il sur l'axe?
@kigurai, parce que le fait que les points sont équidistants, il est probable qu'ils sont en fait des rotations du point d'origine sur l'axe: Rappelez-vous que Tfinniga tente de détecter les rotations constante . Bien sûr, il est possible que l'équidistance est simplement une coïncidence, c'est pourquoi il s'agit d'un algorithme non déterministe.
J'allais proposer la même chose. Toutes les autres réponses spéculatives n'ont pas reçu de votes, mais ce qui pourrait fonctionner obtenir un vote au bas? De nombreux points auront 2 autres éléments équidistants afin que vous puissiez trouver plusieurs candidats très rapidement. Vous pouvez même vérifier plus de 3 points équidistants, vous pouvez en moyenne l'axe déterminé par plusieurs ensembles, et vous pouvez facilement tester un axe proposé pour une correction probable - chaque point fera mapper à N Autres en suivant une séquence de rotation proposée si elle est correcte si elle est correcte si elle est correcte. . Je vais le voter jusqu'à zéro :-)
@phkahler, merci. Je ne sais pas pourquoi cela a été évité, mais c'était avant que la plupart des autres réponses ont été postées, alors peut-être que quelqu'un pensait que cela devrait être déterministe.
Regardez les techniques utilisées dans la vision stéréo pour calculer l'homographie entre deux images - votre problème avec des ensembles de nuages de points semble analogues à des points de correspondance dans plusieurs images du même objet / scène. On dirait que vous pouvez appliquer un algorithme Ransac pour calculer une transformation entre vos jeux de nuages de points.
une idée folle ...
Si le même point est tourné sur le même axe à plusieurs reprises, tous les points se situeront dans le même plan. En fonction de votre ensemble de données, il pourrait être possible de détecter ce plan à l'aide de la méthode RANSAC.
L'axe de rotation sera perpendiculaire à ce plan, et il doit être relativement facile de déterminer l'emplacement de l'axe une fois son orientation déterminée.
Eh bien, l'approche suivante pourrait être utile, mais cela dépend du spécifique de vos données. Il est basé sur les hypothèses que l'écart entre les postes voisins est assez gros (20 degrés est probablement bien) et le petit nuage de points se rapproche d'une surface (le dernier pourrait être surmonté). Je suggère d'utiliser la correspondance locale (la technique populaire de la vision informatique).
Premièrement, pour chaque point du grand nuage, vous devez calculer des descripteurs locaux (comme Tamific ou surf pour les images). Le plus populaire pour les nuages de points est spin image :
Johnson, A., & Hebert, M. (1999). Utiliser des images de spin pour une reconnaissance efficace des objets dans des scènes encombrées 3 D. IEEE transactions sur l'analyse de modèle et l'intelligence de la machine, 21 (5), 433-449. Citeser. Récupéré de http://citeeerx.ist. psu.edu/viewdoc/download?diodi=10.1.23.8816&rep=rep1&type=pdf .
La modification avancée est utilisée ici:
Endres, F., Plagemann, C., Stachniss, C., & Burgard, W. (2009). Découverte non supervisée des classes d'objet à partir de données de plage à l'aide de l'allocation de Dirichlet latente. En robotique: science et systèmes. Seattle, USA.
Si cela sera calculé, demandez-moi comment réduire la dimensionnalité sans perdre beaucoup de puissance discriminante, je l'ai fait une fois.
Ensuite, vous devriez correspondre aux descripteurs, c'est-à-dire de trouver les voisins les plus proches de chacun d'entre eux dans leur espace à haute dimension. Si le petit nuage a été tourné 3 fois, il devrait y avoir 3 bons voisins les plus proches. Cependant, en raison de l'auto-intersections de nuage, les allumettes contiendront probablement du bruit. Vous devez toujours trouver l'axe qui convient parfaitement à une grande quantité de matchs (mais pas tous tous). Ici, vous pouvez utiliser un raccord robuste comme Ransac (vous devriez faire des mathématiques pour définir la probabilité d'une position d'axe W.R.T. Les matchs trouvés). Notez qu'il diffère des méthodes que les autres ont suggéré. Vous devez vous installer une seule ligne au lieu de la famille des plans, sur la base des descripteurs, et non des points d'origine (Ransac ne fera probablement pas d'adapter un avion ayant 4-5 points correct et 100 000 valeurs aberrantes).
Aussi NOTE:
Si vous avez la petite balayage qui ne se rapproche pas d'une surface, vous devez trouver un descripteur de rotation-invariant différent, pas d'images de spin.
Pour calculer des normales et faire la récupération, vous pouvez consulter cette bibliothèque: http://graphics.cs.msu.ru/fr/science/research/3dpoint/lidark (une version majeure va bientôt à venir).
Vous ne pouvez pas calculer Tamift ni descripteurs de surf à un point unique dans un nuage de points.
Bien sûr que vous ne pouvez pas. C'était juste une analogie de vision de l'ordinateur. Il existe des descripteurs spéciaux pour les nuages de points comme des images de spin. Il est calculé w.r.t. certains quartiers du point. Pour plus de détails, veuillez consulter les papiers que je fais référence.
C'est un tas d'excellentes informations sur le problème, merci de la publier.
Ce qui suit suppose qu'il y a 3 copies ou plus. Considérez la coque convexe du grand pointucloud. Trouvez deux de ses visages parallèles. L'axe de rotation sera perpendiculaire à ceux-ci. Si vous trouvez plus d'une paire, testez simplement chaque orientation.
Évidemment, cela ne fonctionne pas si les points les plus extrêmes selon l'axe sont exactement sur l'axe, cependant dans le cas général, c'est très rare.
Il y a 2 choses que vous devriez considérer:
Maintenant si (rotation> Span) La solution est plus simple, car vous devez rechercher un sous-modèle et basé sur son occurrence, essayez de faire correspondre un modèle plus grand.
Dans le cas (rotation Si vous n'êtes pas au courant de quelle catégorie vous tombez, sans danger pour assumer dans la seconde.
Comme mentionné précédemment, Ransac est le meilleur moyen de correspondance des motifs, car il prend moins de temps et donne des résultats décents.
Le seul problème que vous avez laissé est l'angle d'estimation de la portée du Mini Point Cloud lors de l'initialisation. Cette estimation est difficile à faire. Donc, si vous avez suffisamment de puissance / temps de calcul, je suggérerais d'itération avec 1 degrés. à partir d'un modeste de 5 degrés sur 45 degrés. Comme les résultats commencent à converger augmenter la précision angulaire.
Étant donné que le nuage de points d'origine est petit, la solution la plus simple pourrait être ransac:
La probabilité d'une estimation correcte est de 1 / ((N-1) (N-2)), où n est le nombre de points dans le nuage d'origine. Étant donné que chaque test peut être effectué très rapidement, cela pourrait être une approche utile.
Avez-vous le nuage initial (petit) ponctuel comme référence ou non? Sinon, ce problème est probablement indéchritable avec une certitude réelle.
Je n'ai pas de réponse complète, mais une heuristique de départ est que la densité de points serait plus grande près de l'axe.
Pas pour de nombreux nuages de points. Les points disposés sur le bord d'un cercle plat tourné autour du centre du cercle n'exposeraient aucun regroupement sur l'axe. Il en va de même lorsque la majeure partie des points ne sont pas symétriques sur l'axe ou sont loin de l'axe de rotation réel.
@Ron, c'est pourquoi cela s'appelle une heuristique.
@tfinniga avons-nous un nombre initial de points? Cela nous aidera à obtenir le nombre de fois que ces points ont été tournés. (Nombre de points en grande surface) / (nombre de points dans le nuage initial).
@Tloflin: Pouvez-vous donner une motivation pour pourquoi c'est une bonne heuristique. Je ne pense pas qu'un nuage de points généraux copié + tourné autour d'un axe présenterait une plus grande densité près de l'axe de rotation. Au moins, ce n'est pas évident pour moi.
@Kigurai, sur une considération supplémentaire, je pense que vous (et Ron) sont corrects; Il n'y a probablement pas de corrélation entre la densité et la proximité de l'axe. Désolé pour la confusion.