Guter Algorithmus zum Finden von Teilmengen von Punktmengen
Ich suche nach geeigneten Algorithmen für die Suche nach Teilmengen von 2D-Punkten in größeren Mengen. Ein Bild sagt mehr als tausend Worte:
Irgendwelche Ideen, wie man das erreichen könnte? Beachten Sie, dass die Transformationen nur Rotation und Skalierung sind.
Es scheint, dass das am meisten problematische Punktsatz-Registrierung [1] ist. Ich habe mit CPD und anderen starren und nicht-starren Algorithmen Implementierungen experimentiert, aber sie scheinen nicht zu funktionieren zu gut, um kleine Untermengen in größeren Mengen von Punkten zu finden.
Ein anderer Ansatz könnte die Verwendung von Sternenverfolgungsalgorithmen wie der in [2] erwähnten Angle-Methode sein. oder robustere Methoden wie [3]. Aber wiederum scheinen sie alle für große Eingabesätze und Zielsätze gedacht zu sein. Ich suche etwas weniger zuverlässiges, aber minimalistischer ...
Danke für Ideen!
[1]: Ссылка
[2]: Ссылка
[3]: Ссылка
5 Antworten
Hier sind einige Arbeiten, die wahrscheinlich mit Ihrer Frage zusammenhängen:
- Geometrische Musteranpassung unter euklidischer Bewegung (1993) von L. Paul Chew, Michael T. Goodrich, Daniel P. Huttenlocher, Klara Kedem, Jon M. Kleinberg, Dina Kravets.
- Ein schnell erwarteter Zeitalgorithmus für das 2-D-Punktmuster (2004) von Wamelena, Iyengarb.
- Einfache Algorithmen zur partiellen Punktmusteranpassung unter steifer Bewegung (2006) von Bishnua, Dasb, Nandyb, Bhattacharyab.
- Genaue und ungefähre geometrische Musteranpassung für Punktmengen in der Ebene unter Ähnlichkeitstransformationen (2007) von Aiger und Kedem.
und übrigens erinnerte mich deine letzte Referenz an:
- Eine Anwendung der Punktmusteranpassung in der Raumfahrt (1994) von G. Weber, L. Knipping und H. Alt.
Ich denke, Sie sollten mit einer Teilmenge der Eingabepunkte beginnen und die erforderliche Transformation bestimmen, um mit einer Teilmenge der großen Menge übereinzustimmen. Zum Beispiel:
- Wählen Sie zwei beliebige Punkte der Eingabe, sagen Sie A und B.
- map A und B zu einem Paar des großen Satzes. Dies bestimmt den Maßstab und zwei Drehwinkel (im oder gegen den Uhrzeigersinn)
- wendet die gleiche Skalierung und Transformation auf einen dritten Eingabepunkt C an und prüft die große Menge, um zu sehen, ob dort ein Punkt existiert. Sie müssen zwei Positionen überprüfen, eine für jeden Rotationswinkel. Wenn der Punkt C in der großen Menge vorhanden ist, können Sie die restlichen Punkte überprüfen.
- Wiederholen Sie für jedes Punktepaar in der großen Menge
Ich denke, Sie könnten auch versuchen, eine Untermenge von drei Eingabepunkten zu finden, da Sie wissen, dass die Winkel eines Dreiecks unter Skalierung und Drehung invariant sind.
Das sind meine Ideen, ich hoffe, sie helfen Ihnen, Ihr Problem zu lösen.
Ich würde versuchen, den iterativen nächsten Punkt -Algorithmus zu verwenden. Eine einfache Version wie die, die Sie benötigen, sollte einfach zu implementieren sein.
Sehen Sie sich geometrisches Hashing an. Es ermöglicht das Auffinden geometrischer Muster unter verschiedenen Transformationen. Wenn Sie nur Rotation und Skalierung verwenden, ist das ganz einfach.
Die Hauptidee ist, das Muster zu kodieren "native" Koordinaten, die unter Transformationen invariant sind.
Tags und Links algorithm computer-vision pattern-matching point-clouds