Profil, das in einer Punktwolke zusammenbringt

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 .

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 = \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2+(z_1 - z_2)^2}$

$2000 \choose 2$

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.

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).