Profil, das in einer Punktwolke zusammenbringt

14

Eine Punktwolke wird mit einer einheitlichen Zufallsfunktion für erzeugt (x,y,z). Wie in der folgenden Abbildung gezeigt, wird eine flache Schnittebene ( Profil ) untersucht, die einem Zielprofil, dh in der linken unteren Ecke, als das beste (auch wenn nicht das exakte) Profil entspricht. Also die Frage ist:

1- Wie ein solches Spiel gegebener finden target 2D point mapdurch point cloudBerücksichtigung der folgenden Hinweise / Bedingungen?
2- Was sind dann die Koordinaten / Orientierungen / Ähnlichkeitsgrade usw.?

Anmerkung 1: Das interessierende Profil kann sich an einer beliebigen Stelle mit Drehung entlang der Achsen befinden und je nach Position und Ausrichtung auch eine andere Form aufweisen, z. B. ein Dreieck, ein Rechteck oder ein Viereck. In der folgenden Demonstration wird nur ein einfaches Rechteck gezeigt.

Hinweis 2: Ein Toleranzwert kann als Abstand der Punkte vom Profil betrachtet werden. Um dies für die folgende Abbildung zu demonstrieren, sei eine Toleranz von 0.01mal der kleinsten Abmessung (~1)so angenommen tol=0.01. Wenn wir also den Rest entfernen und alle verbleibenden Punkte auf die Ebene des untersuchten Profils projizieren, können wir die Ähnlichkeit mit dem Zielprofil überprüfen.

Hinweis 3: Ein verwandtes Thema finden Sie unter Punktmustererkennung .

Bildbeschreibung hier eingeben

Entwickler
quelle
@Developer Off Topic, aber welche Software verwenden Sie, um diese Plots zu erstellen?
Spacey
1
@ Mohammad Ich benutze Python+ MatPlotLib, um meine Nachforschungen anzustellen und die Grafiken usw. zu generieren.
Entwickler
@Developer Fantastisch - es ist durch Python, aber was bedeuten sie "Python-Shell ala Matlab"?
Spacey
Wie werden die Punktwolken gespeichert? Als ein Satz von Koordinaten für die Mitte jedes Punktes oder als ein Volumendatensatz, dessen Koordinaten um die Punkte Werte ungleich Null haben?
Endolith
@endolith Allen Punkten sind Koordinaten zugeordnet als P:{x,y,z}. Sie sind in der Tat dimensionslose Punkte. Mit einer gewissen Annäherung könnten sie jedoch als 3D-Arrays zu einer Ein-Pixel-Dimension diskretisiert werden. Sie können auch andere Attribute (wie Gewichte usw.) über Koordinaten einbeziehen.
Entwickler

Antworten:

4

Dies ist immer sehr rechenintensiv, insbesondere wenn Sie bis zu 2000 Punkte verarbeiten möchten. Ich bin mir sicher, dass es bereits hochoptimierte Lösungen für diese Art des Mustervergleichs gibt, aber Sie müssen erst herausfinden, wie es heißt, um sie zu finden.

Da es sich nicht um ein Bild, sondern um eine Punktwolke (spärliche Daten) handelt, trifft meine Kreuzkorrelationsmethode nicht wirklich zu (und wäre rechnerisch noch schlimmer). So etwas wie RANSAC findet wahrscheinlich schnell eine Übereinstimmung, aber ich weiß nicht viel darüber.

Mein Lösungsversuch:

Annahmen:

  • Sie möchten die beste Übereinstimmung finden, nicht nur eine lockere oder "wahrscheinlich richtige" Übereinstimmung
  • Die Übereinstimmung weist aufgrund von Rauschen bei der Messung oder Berechnung einen geringen Fehler auf
  • Quellpunkte sind koplanar
  • Alle Quellenpunkte in Ziel vorhanden sein muss (= jeder unerreichter Punkt ist eine Nichtübereinstimmung für das gesamte Profil)

Sie sollten also in der Lage sein, viele Abkürzungen zu verwenden, indem Sie Dinge disqualifizieren und die Rechenzeit verkürzen. Zusamenfassend:

  1. Wähle drei Punkte aus der Quelle
  2. Durchsuchen Sie die Zielpunkte und finden Sie Sätze von 3 Punkten mit derselben Form
  3. Wenn eine Übereinstimmung von 3 Punkten gefunden wird, überprüfen Sie alle anderen Punkte in der Ebene, die sie definieren, um festzustellen, ob es sich um eine enge Übereinstimmung handelt
  4. Wird mehr als eine Übereinstimmung aller Punkte gefunden, wählen Sie diejenige mit der geringsten Summe der 3D-Abstandsfehler

Genauer:

pick a point from the source for testing s1 = (x1, y1)
Find nearest point in source s2 = (x2, y2)
d12 = (x1-x2)^2 + (y1-y2)^2
Find second nearest point in source s3 = (x3, y3)
d13 = (x1-x3)^2 + (y1-y3)^2
d23 = (x2-x3)^2 + (y2-y3)^2

for all (x,y,z) test points t1 in target:
    # imagine s1 and t1 are coincident
    for all other points t2 in target:
        if distance from test point > d12:    
            break out of loop and try another t2 point
        if distance ≈ d12:
            # imagine source is now rotated so that s1 and s2 are collinear with t1 and t2
            for all other points t3 in target:
                if distance from t1 > d13 or from t2 > d23:
                    break and try another t3
                if distance from t1 ≈ d13 and from t2 ≈ d23:
                    # Now you've found matching triangles in source and target
                    # align source so that s1, s2, s3 are coplanar with t1, t2, t3
                    project all source points onto this target plane 
                    for all other points in source:
                        find nearest point in target
                        measure distance from source point to target point
                        if it's not within a threshold:
                            break and try a new t3
                        else:
                            sum errors of all matched points for this configuration (defined by t1, t2, t3)

Welche Konfiguration den kleinsten Fehlerquadrat für alle anderen Punkte aufweist, ist die beste Übereinstimmung

Da wir mit 3 Testpunkten für den nächsten Nachbarn arbeiten, können übereinstimmende Zielpunkte vereinfacht werden, indem überprüft wird, ob sie sich innerhalb eines bestimmten Radius befinden. Wenn wir zum Beispiel aus (0, 0) nach einem Radius von 1 suchen, können wir (2, 0) basierend auf x1 - x2 disqualifizieren, ohne den tatsächlichen euklidischen Abstand zu berechnen, um ihn etwas zu beschleunigen. Dies setzt voraus, dass die Subtraktion schneller ist als die Multiplikation. Es gibt auch optimierte Suchen, die auf einem willkürlicheren festen Radius basieren .

function is_closer_than(x1, y1, z1, x2, y2, z2, distance):
    if abs(x1 - x2) or abs(y1 - y2) or abs(z1 - z2) > distance:
        return False
    return (x1 - x2)^2 + (y1 - y2)^2 + (z1 - z2)^2 > distance^2 # sqrt is slow

d=(x1-x2)2+(y1-y2)2+(z1-z2)2

(20002)

Da Sie diese ohnehin alle berechnen müssen, unabhängig davon, ob Sie Übereinstimmungen finden oder nicht, und da Sie sich für diesen Schritt nur um die nächsten Nachbarn kümmern, ist es wahrscheinlich besser, diese Werte mit einem optimierten Algorithmus vorab zu berechnen, wenn Sie über den Speicher verfügen . So etwas wie eine Delaunay- oder Pitteway-Triangulation , bei der jeder Punkt im Ziel mit den nächsten Nachbarn verbunden ist. Speichern Sie diese in einer Tabelle und suchen Sie sie für jeden Punkt, wenn Sie versuchen, das Quellendreieck an eines der Zieldreiecke anzupassen.

Es sind viele Berechnungen erforderlich, aber es sollte relativ schnell gehen, da nur die Daten verarbeitet werden, die dünn sind, anstatt viele bedeutungslose Nullen miteinander zu multiplizieren, wie dies bei einer Kreuzkorrelation von Volumendaten der Fall wäre. Dieselbe Idee würde für den 2D-Fall funktionieren, wenn Sie zuerst die Mittelpunkteder Punkte fanden und sie als Satz von Koordinaten speicherten.

Endolith
quelle
1
Der erste Teil Ihrer Antwort ist eine Brute-Force-Methode, mit der nahegelegene Punkte (in Bezug auf einen Schwellenwert) um alle möglichen Ebenen durch die Punktwolke gesucht werden. Es ist extrem rechenintensiv, zB für nur 2000 Punkte wird eine Anzahl von 2.662.668.000.000 (Formel) Entfernungsberechnungen benötigt!
Entwickler
@Developer: Ja, es wird eine Menge Berechnungen erfordern, besonders wenn Sie Tausende von Punkten haben. Ja, für 2000 Punkte würden Sie 2.658.673.998.000 Berechnungen durchführen, wenn Sie keine Flugzeuge finden. Vermutlich würden Sie jedoch Flugzeuge finden, die die Zeit verkürzen würden, da sie anhalten, sobald genügend Punkte gefunden wurden. Aber trotzdem habe ich darüber nachgedacht und wahrscheinlich eine bessere Idee, und ich werde die Antwort ändern.
Endolith
1
Sie haben den Punkt absolut richtig verstanden. Nur um hinzuzufügen, dass die Stoppkriterien nicht gelten können, selbst wenn ein geeignetes Flugzeug gefunden wurde, obwohl es möglicherweise eine viel bessere Übereinstimmung gibt. Daher müssen alle möglichen Flugzeuge überprüft werden. Ich habe diese Idee bereits umgesetzt und festgestellt, dass es auch mit Hilfe von FortranZahlen über 500Punkten unmöglich sein wird, Erfahrungen mit dem PC zu sammeln.
Entwickler
2

Ich würde @ mirror2image description zu der alternativen Lösung neben RANSAC hinzufügen. Sie können den ICP-Algorithmus (iterativer nächster Punkt) in Betracht ziehen. Eine Beschreibung finden Sie hier !

Ich denke, die nächste Herausforderung bei der Verwendung dieses ICP besteht darin, Ihre eigene Kostenfunktion und die Startposition der Zielebene in Bezug auf die 3D-Wolkenpunktdaten zu definieren. Ein praktischer Ansatz besteht darin, während der Iteration ein zufälliges Rauschen in die Daten einzufügen, um eine Konvergenz mit den falschen Minima zu vermeiden. Dies ist der heuristische Teil, den Sie vermutlich entwerfen müssen.

Aktualisieren:

Die Schritte in vereinfachter Form sind:

  1. Finden Sie den nächsten Punkt für jeden Eingabepunkt.
  2. Berechnen Sie die Transformation von der Eingabe zum Ziel und verschieben Sie dann die Eingabepunkte mithilfe der Transformation.
  3. Berechnen Sie die Ähnlichkeitsfunktion (z. B. die Entfernung für jeden Eingabepunkt in Bezug auf den entsprechenden Paar-Zielpunkt).
  4. Überprüfen Sie den Stoppzustand.

Wiederholen Sie die Schritte 1-4.

Es gibt eine Bibliothek, die Sie hier ansehen können ! (Ich habe es noch nicht ausprobiert), es gibt einen Abschnitt im Registrierungsteil (einschließlich anderer Methoden).

kuskus
quelle
Danke für den Link und den Vorschlag. Solche nützlichen Ideen helfen uns als Nachwuchsforschern immer, etwas schneller zu lernen. Ich freue mich immer über weitere Erklärungen.
Entwickler