Schätzung eines Bildbereichs, der von einer Menge von Punkten erzeugt wird (Alpha shapes ??)
Ich habe eine Reihe von Punkten in einer Beispiel-ASCII-Datei , die ein 2D-Bild zeigt .
Ich möchte die Gesamtfläche schätzen, die diese Punkte ausfüllen. Es gibt einige Stellen innerhalb dieser Ebene, die durch keinen Punkt gefüllt sind, da diese Regionen ausgeblendet wurden. Was ich für die Schätzung der Fläche für praktisch halten könnte, wäre eine alpha -Wert zu finden und folglich den Bereich zu schätzen.
Ich bekomme dieses Ergebnis, aber ich möchte, dass diese Methode das Loch in der Mitte erkennen kann.
Aktualisieren
So sehen meine realen Daten aus:
Meine Frage ist, was ist der beste Weg, um einen Bereich der oben genannten Form zu schätzen? Ich kann nicht herausfinden, was schief gelaufen ist, dass dieser Code nicht richtig funktioniert? !! Jede Hilfe wird geschätzt.
4 Antworten
Okay, hier ist die Idee. Eine Delaunay-Triangulation wird Dreiecke erzeugen, die wahllos groß sind. Es wird auch problematisch sein, da nur Dreiecke erzeugt werden.
Deshalb erzeugen wir eine "unscharfe Delaunay-Triangulation". Wir setzen alle Punkte in einen kd-Baum und schauen für jeden Punkt p auf seine nächsten Nachbarn. Der kd-Baum macht das schnell.
Finden Sie für jeden dieser k Nachbarn die Entfernung zum Brennpunkt k . Verwenden Sie diese Entfernung, um eine Gewichtung zu generieren. Wir möchten, dass nahegelegene Punkte gegenüber entfernteren Punkten bevorzugt werden, daher ist hier eine Exponentialfunktion p angebracht. Verwenden Sie die gewichteten Abstände, um eine Wahrscheinlichkeitsdichtefunktion zu erstellen, die die Wahrscheinlichkeit beschreibt, jeden Punkt zu zeichnen.
Zeichnen Sie nun aus dieser Verteilung eine große Anzahl von Malen. Nahe gelegene Punkte werden oft ausgewählt, während weiter entfernte Punkte seltener ausgewählt werden. Notieren Sie für einen gezeichneten Punkt, wie oft er für den Brennpunkt gezeichnet wurde. Das Ergebnis ist ein gewichteter Graph, bei dem jede Kante im Graph benachbarte Punkte verbindet und gewichtet wird, wie oft die Paare ausgewählt wurden.
Selektiere nun alle Kanten des Graphen, deren Gewichte zu klein sind. Dies sind die Punkte, die wahrscheinlich nicht verbunden sind. Das Ergebnis sieht folgendermaßen aus:
Nun werfen wir alle verbleibenden Kanten in formschön . Wir können dann die Kanten in sehr kleine Polygone umwandeln, indem wir sie puffern. Wie so:
Wenn Sie die Polygone mit einem großen Polygon abgleichen, das die gesamte Region abdeckt, erhalten Sie Polygone für die Triangulation. DAS KANN EINE WEILE DAUERN. Das Ergebnis sieht folgendermaßen aus:
Abschließend alle zu großen Polygone aussortieren:
Hier ist ein Gedanke: Verwenden Sie k-means clustering .
Sie können dies in Python wie folgt erreichen:
%Vor%Mit Ihren Daten erhalten Sie folgendes Ergebnis:
Nun können Sie die konvexe Hülle des oberen Clusters und des unteren Clusters nehmen und die einzelnen Bereiche separat berechnen. Das Hinzufügen der Bereiche wird dann zu einem Schätzer des Bereichs ihrer Vereinigung, vermeidet aber geschickt das Loch in der Mitte.
Zur Feinabstimmung Ihrer Ergebnisse können Sie mit der Anzahl der Cluster und der Anzahl der verschiedenen Starts zum Algorithmus spielen (der Algorithmus ist randomisiert und wird normalerweise mehrmals ausgeführt).
Sie haben zum Beispiel gefragt, ob zwei Cluster immer das Loch in der Mitte verlassen. Ich habe den folgenden Code verwendet, um damit zu experimentieren. Ich erzeuge eine gleichmäßige Verteilung der Punkte und hole dann eine zufällige Größe und orientierte Ellipse aus, um ein Loch zu simulieren.
%Vor%Betrachten Sie die Ergebnisse für K-Means:
Zumindest für mein Auge scheint es, als ob die Verwendung von zwei Clustern am schlechtesten ist, wenn das "Loch" die Daten in zwei separate Blobs trennt. (In diesem Fall tritt das auf, wenn die Ellipse so orientiert ist, dass sie zwei Kanten des rechteckigen Bereichs überlappt, der die Abtastpunkte enthält.) Die Verwendung von drei Clustern löst die meisten dieser Schwierigkeiten.
Sie werden auch bemerken, dass K-means einige nicht-intuitive Ergebnisse in der 1. Spalte, 3. Zeile sowie in der 3. Spalte, 4. Zeile, erzeugt. Eine Übersicht über die Clustering-Methoden von sklearn hier zeigt das folgende Vergleichsbild:
Von diesem Bild scheint es, als ob SpectralClustering Ergebnisse produziert, die mit dem übereinstimmen, was wir wollen. Wenn Sie dies auf den gleichen Daten oben versuchen, werden die genannten Probleme behoben (siehe 1. Spalte, 3. Zeile und 3. Spalte, 4. Zeile).
Das Vorangegangene legt nahe, dass das spektrale Clustering mit drei Clustern für die meisten Situationen dieser Art angemessen sein sollte.
Erstellen Sie eine Funktion, die als Argument verwendet (int radiusOfInfluence). Innerhalb der Funktion führe einen Voxel-Filter mit dem Radius aus. Dann multipliziere einfach die Fläche dieses Kreises (pi * AOI ^ 2) mit der Anzahl der verbleibenden Punkte in der Wolke. Dies sollte Ihnen eine relativ robuste Schätzung der Fläche geben und wäre sehr widerstandsfähig gegenüber Löchern und seltsamen Kanten.
Einige Dinge zu beachten:
-Dadurch erhalten Sie ein positives Überschwingen der Fläche aufgrund überreichender Kanten um genau einen Radius. Eine Modifikation, um dies anzupassen, könnte darin bestehen, einen statistischen Ausreißerentfernungsfilter (in einem inversen Modus) zu betreiben, um statistische Kantenpunkte zu erhalten. Dann kann eine Annahme gemacht werden, dass ungefähr die Hälfte jedes Kantenpunktes außerhalb der Form liegt, subtrahiere die Hälfte der Anzahl von Punkten, die von deiner Gesamtanzahl vor dem Multiplizieren in der Fläche gefunden wurden.
-Der Radius des Einflusses bestimmt weitgehend die Locherkennung dieser Funktion, da ein größerer Punkt einzelne Punkte über größere Bereiche abdeckt. Durch das Abstimmen des std-Cutoffs auf den stat outlier-Filter können Sie jedoch auch Innenlöcher aggressiver erkennen und anpassen Bereich auf diese Weise.
Es stellt sich wirklich die Frage nach dem, was Sie suchen, da dies eher eine Schussgenauigkeits / Schussgruppierungstyp-Beurteilung ist, die eine vernünftig verteilte Menge von Proben annimmt. Ihre Methode geht davon aus, dass Ihre äußeren Randpunkte die absoluten Grenzen dessen sind, was möglich ist (was je nach Situation eine faire Annahme sein kann).
BEARBEITEN -----------------------
Ich habe keine Zeit, Beispielcode zu schreiben, aber ich kann weiter erklären, um das Verständnis zu erleichtern.
Im Mittelpunkt steht der Voxel-Filter . Ganz einfach, es legt einen Startpunkt in x, y Koordinaten fest und erstellt dann ein Raster über den gesamten Raum, der Einheiten (Rasterabstand) auf beiden Achsen eines benutzerdefinierten Filterradius hat. Innerhalb jeder Gitterbox werden alle Punkte auf einen einzelnen Punkt gemittelt. Dies ist sehr wichtig für dieses Konzept, weil es das Problem der Überlappung fast vollständig beseitigt.
Der zweite Teil (die inverse Entfernung des statistischen Ausreißers ) ist nur ein bisschen clever, um Ihre Kantenanpassung zu verbessern . Grundsätzlich ist stat outlier so konstruiert, dass Rauschen entfernt wird, indem die Entfernung von jedem Punkt zu seinen (k) nächsten Nachbarn betrachtet wird. Nach dem Generieren der durchschnittlichen Entfernung zu k nächsten Nachbarn für jeden Punkt, richtet es ein Histogramm ein und ein benutzerdefinierter Parameter agiert als eine binäre Schwelle zum Halten oder Entfernen von Punkten. Wenn invertiert und auf einen vernünftigen Cut-Off eingestellt ist (~ 0,75 Std sollte funktionieren), löscht er stattdessen alle Punkte, die sich in der Masse des Objekts befinden (dh nur Kantenpunkte belassen). Der Grund dafür ist, dass diese Punkte die Grenze Ihres Objekts technisch um 1 Radius überschreiten. Obwohl einige auf scharfen und einige auf stumpfen Kantenwinkeln (dh mehr als oder weniger als ein halber Überfüllungskreis) liegen, sollte eine halbe Kreisfläche pro Punkt über das gesamte Objekt hinaus eine ziemlich gute Verbesserung der Kantenanpassung ergeben .
Denken Sie daran, dass Sie am Ende des Tages nur eine Nummer erhalten werden. Was Stresstests betrifft, schlage ich vor, künstliche Punktwolken mit bekanntem Bereich zu erstellen und / oder eine grafische Ausgabe zu erstellen, die anzeigt, wo Sie Kreise und Halbkreise abwerfen (wenn Sie Lust auf das Innere des Objekts haben).Die Knöpfe, die Sie drehen möchten, um diese Methode zu verbessern, sind: Voxel-Filterradius, Einflussbereich pro Punkt (könnte eigentlich getrennt vom vox-Filterradius gesteuert werden, obwohl sie ziemlich nahe beieinander bleiben sollten), std cutt-off.
Ich hoffe, das hat geholfen, zu klären, Prost!
Bearbeiten:
Ich habe bemerkt, dass Sie Ihren eigenen Code haben, um die Alpha-Form zu berechnen, und die Bereiche der Delaunay-Dreiecke sind gerade da, so dass die Berechnung der Fläche der Form noch einfacher ist ...
Fügen Sie einfach die Bereiche von Dreiecken hinzu, wenn Sie dem Alpha-Polygon ein Dreieck hinzufügen möchten.
Wenn Sie Löcher erkennen möchten ... fügen Sie einen sekundären Schwellenwert hinzu, um zu vermeiden, dass Dreiecke mit einem Bereich größer als der Schwellenwert hinzugefügt werden. In diesem Beispiel wird ein Wert von max_area = 99999 die Lücke entfernen.
Das einzige Problem ist die Art, wie Sie die Grafikausgabe erstellen, weil Sie das Loch nicht sehen.
%Vor%Das
Alte Antwort:
Um die Fläche eines unregelmäßigen einfachen Polygons zu berechnen, können Sie die Formel für die Schnürsenkel und die CCW-Koordinaten der Grenze als Eingabe.
Wenn Sie Löcher in Ihrer Wolke erkennen möchten, müssen Sie die Delaunay-Dreiecke mit einem Umkreisradius von mehr als einem sekundären Schwellenwert entfernen. Das Ideal ist: Berechnen Sie die Delaunay-Triangulation und filtern Sie mit Ihrer aktuellen Alpha-Form. Dann berechne den Umkreisradius jedes Dreiecks und entferne diese Dreiecke mit einem Umkreisradius, der viel größer ist als der durchschnittliche Radius.
Um die Fläche eines unregelmäßigen Polygons mit Löchern zu berechnen, verwenden Sie die Shoelace-Formel für jede Lochgrenze. Geben Sie die externe Grenze in CCW (positive) Reihenfolge ein, um die Fläche zu erhalten. Geben Sie dann die Grenze jedes Lochs in CW-Reihenfolge (negativ) ein, um einen (negativen) Wert für die Fläche zu erhalten.
Tags und Links python computer-vision scipy shapely concave-hull