Un nuage de points est généré à l'aide d'une fonction aléatoire uniforme pour (x,y,z)
. Comme le montre la figure suivante, un plan ( profil ) d' intersection plat est à l'étude qui correspond au meilleur (même s'il n'est pas exact) un profil cible, c'est-à-dire donné dans le coin inférieur gauche. La question est donc:
1- Comment trouver une telle correspondance de donné
target 2D point map
enpoint cloud
considérant les notes / conditions suivantes?
2- Quelles sont alors les coordonnées / orientations / degrés de similitude etc?
Remarque 1: Le profil d'intérêt peut être n'importe où avec une rotation le long des axes et peut également avoir une forme différente, par exemple un triangle, un rectangle, un quadrilatère, etc., selon son emplacement et son orientation. Lors de la démonstration suivante, seul un rectangle simple est affiché.
Remarque 2: Une valeur de tolérance peut être considérée comme la distance des points par rapport au profil. Pour le voir la figure suivante suppose une tolérance de 0.01
temps la plus petite dimension (~1)
donc tol=0.01
. Donc, si nous supprimons le reste et projetons tous les points restants sur le plan du profil étudié, nous serons en mesure de vérifier sa similitude avec le profil cible.
Remarque 3: Un sujet connexe peut être trouvé à la reconnaissance des formes de points .
Python
+MatPlotLib
pour faire mes recherches et générer les graphiques etc.P:{x,y,z}
. Ce sont en effet des points sans dimension. Cependant, avec une certaine approximation, ils pourraient être discrétisés à une dimension d'un pixel sous forme de tableaux 3D. Ils peuvent également incorporer d'autres attributs (tels que des poids, etc.) aux coordonnées.Réponses:
Cela va toujours nécessiter beaucoup de calculs, surtout si vous souhaitez traiter jusqu'à 2000 points. Je suis sûr qu'il existe déjà des solutions hautement optimisées pour ce type de correspondance de modèles, mais vous devez comprendre comment cela s'appelle afin de les trouver.
Puisque vous parlez d'un nuage de points (données clairsemées) au lieu d'une image, ma méthode de corrélation croisée ne s'applique pas vraiment (et serait encore pire sur le plan informatique). Quelque chose comme RANSAC trouve probablement une correspondance rapidement, mais je n'en sais pas grand-chose.
Ma tentative de solution:
Hypothèses:
Vous devriez donc pouvoir prendre beaucoup de raccourcis en disqualifiant les choses et en réduisant le temps de calcul. En bref:
Plus détaillé:
Quelle que soit la configuration qui présente le moins d'erreur quadratique pour tous les autres points, c'est la meilleure correspondance
Étant donné que nous travaillons avec 3 points de test voisins les plus proches, la correspondance des points cibles peut être simplifiée en vérifiant s'ils se trouvent dans un certain rayon. Si vous recherchez un rayon de 1 à partir de (0, 0), par exemple, nous pouvons disqualifier (2, 0) sur la base de x1 - x2, sans calculer la distance euclidienne réelle, pour l'accélérer un peu. Cela suppose que la soustraction est plus rapide que la multiplication. Il existe également des recherches optimisées basées sur un rayon fixe plus arbitraire .
Le temps de calcul minimum serait si aucune correspondance à 2 points n'est trouvée.
S'il y a 2000 points dans la cible, ce serait des calculs de distance de 2000 * 2000, bien que beaucoup soient disqualifiés par une soustraction, et les résultats des calculs précédents pourraient être stockés de sorte que vous n'avez qu'à faire = 1999000.( 20002) En fait, puisque vous devrez de toute façon calculer tous ces éléments, que vous trouviez des correspondances ou non, et puisque vous ne vous souciez que des voisins les plus proches pour cette étape, si vous avez la mémoire, il est probablement préférable de pré-calculer ces valeurs à l'aide d'un algorithme optimisé . Quelque chose comme une triangulation de Delaunay ou Pitteway , où chaque point de la cible est connecté à ses voisins les plus proches. Stockez-les dans un tableau, puis recherchez-les pour chaque point lorsque vous essayez d'ajuster le triangle source à l'un des triangles cibles.
Il y a beaucoup de calculs impliqués, mais cela devrait être relativement rapide car il ne fonctionne que sur les données, ce qui est rare, au lieu de multiplier beaucoup de zéros sans signification, comme une corrélation croisée de données volumétriques impliquerait. Cette même idée fonctionnerait pour le cas 2D si vous trouviez d'abord les centres des points et les stockiez sous la forme d'un ensemble de coordonnées.
la source
Fortran
nombres supérieurs aux500
points, il serait impossible d'avoir des expériences avec PC.J'ajouterais une description @ mirror2image sur la solution alternative à côté de RANSAC, vous pouvez considérer l'algorithme ICP (point le plus proche itératif), une description peut être trouvée ici !
Je pense que le prochain défi dans l'utilisation de cet ICP est de définir votre propre fonction de coût et la pose de départ du plan cible par rapport aux données de point de nuage 3D. Une approche pratique consiste à introduire du bruit aléatoire dans les données pendant l'itération pour éviter de converger vers les faux minima. C'est la partie heuristique que je suppose que vous devez concevoir.
Mise à jour:
Les étapes sous forme simplifiée sont:
Répétez l'étape 1-4.
Il y a une bibliothèque disponible que vous pouvez considérer ici ! (Je ne l'ai pas encore essayé), il y a une section sur la partie enregistrement (y compris d'autres méthodes).
la source