Gegeben sei eine Menge von Punkten (2D) dh Punktwolke (PC), ist die Frage nach ein robust, accurateund computing-friendlyVerfahren Kreisen zu finden (oder Ellipsen in erweiterte Version).
Die intuitive Idee ist, die Brute-Force-Suche für alle möglichen Punkte (als Mittelpunkt) {unendlich!} Und Radien (wieder unendlich!) Zu verwenden. Dies ist extrem langsam und ineffizient.
Wie unten gezeigt, wird jeder angepasste Kreis basierend auf der Anzahl der Punkte ( nn) auf dem Kreisumfang in einem Abstand kürzer als ein Schwellenwert ( t) eingestuft. Es ist also derreine durchschnittliche Entfernung vorzulegen.
In fortgeschrittener Form sind Ellipsen von Interesse, die angepasst werden sollen.
Irgendwelche Ideen, Brainstorming, Erfahrungen, Kommentare?
quelle
Antworten:
Die besten Ideen, die genau versuchen, dieses Problem zu lösen, sind Hough Transform .
Grundsätzlich wird das Signal im Weltraum
r, x, ykoordiniert. Hierrsteht für Radius undx,ysteht für Mitte. Jeder Punkt kann zu einem oder mehreren Kreisen gehören. Gehen Sie also in der Hough-Ebene durch alle möglichen Kreise, zu denen dieser Punkt gehören könnte, und geben Sie einfach +1. Dies ist keine Suche, nur eine Sammlung.Wenn nun ein echter Kreis existiert, addieren sich so viele Punkte und die Punktzahl eines solchen
r, x, yist viel höher als bei allen anderen. Wenn Sie einen solchen Punkt auswählen, können Sie die richtigen Kreise auswählen.Hier ist ein klassischer Papierweg aus dem Jahr 1971 (bevor ich geboren wurde!), Der dieses Konzept erfand.
Für das Tutorial würde ich folgende Referenzen vorschlagen:
Speziell für die Kreiserkennung können Sie sich auf Folgendes beziehen:
Diese Methoden sind sehr effizient und sehr computerfreundlich.
quelle