Finde Eckpunkte eines Quadrilaterals aus einer Menge von Punkten
Ich versuche, die Eckpunkte eines Quadrilateralen aus einer Menge von Punkten zu bekommen.
- Die Menge der Punkte ist geordnet und beschreibt eine Gliederung
- Manchmal hat der Umriss etwas Rauschen (siehe 2. Bild)
- Die gesuchten Eckpunkte müssen keine Punkte außerhalb der vorgegebenen Punktzahl sein (siehe 3. Bild unten links)
- Die gesuchten Eckpunkte beschreiben ein konvexes Viereck, nicht unbedingt ein Rechteck
Das zweite Bild ist ein bisschen extrem, aber die "Qualität" meiner Punkte liegt zwischen dem ersten und dem zweiten Bild.
Zuerst dachte ich an ein Histogramm von über 1-360 ° und Länge, zwei folgende Punkte beschreiben. Die vier höchsten Peaks würden die Länge jeder Linie beschreiben. Aber mit dem iam verliere die Ordnungspunkte, weiß nur über Grad und Länge oder eine Linie und weiß nicht, zu welcher Position eine Linie gehört.
Dann dachte ich daran, zwei folgende Linien zusammenzufassen, wenn sie mehr oder weniger den gleichen Grad haben, aber ich weiß nicht, wie ich hier mit dem Rauschen umgehen oder eine Ecke vorhersagen soll.
Kennt jemand einen Algorithmus, der dieses Problem oder etwas Ähnliches behandelt?
1 Antwort
Sie können dies als ein Clusterproblem behandeln, bei dem die Cluster "Zentren" tatsächlich gerade Linien sind. Um das Clustering zu berechnen, können Sie einen k-Means-Algorithmus verwenden:
- Wähle 4 zufällige Punktepaare. Passen Sie jeweils eine Linie an, so dass Sie 4 Linien durch die Punktwolke ziehen.
- Wiederholen Sie den Vorgang, bis die Lösung konvergiert zu sein scheint:
- Berechnen Sie für jeden der Punkte den Abstand zu jeder der 4 Linien.
- Weisen Sie den Punkt einem Bucket zu, der der Linie entspricht, der er am nächsten liegt.
- Passen Sie 4 neue Zeilen an die Punkte in jedem der 4 Buckets an (Sie können lineare Regression oder SVD verwenden)
Um den ersten Schritt zu verbessern, könnten Sie die Idee haben, ein Histogramm über die Winkel zu ziehen und jeden Punkt zunächst einem Bucket zuzuordnen, der dem nächsten Peak entspricht. Dann passen Sie die Linien an die vier Eimer an und beginnen Sie zu iterieren.
Sie können dies auch als Optimierungsproblem behandeln: Wählen Sie 4 Punkte, so dass die Fläche der Differenz (weiße Fläche innerhalb und schwarze Fläche außerhalb des Vierecks) möglichst klein ist. Generische Optimierungsalgorithmen funktionieren wahrscheinlich, aber um es schnell zu machen, brauchen Sie einen vernünftigen Algorithmus, um Bereiche zu berechnen.
Tags und Links algorithm math trigonometry corner-detection