2016-06-17 36 views
0

Also, ich habe eine Aufgabe: Verwenden Sie die Modifikation des Kruskal-Algorithmus, um ein Bild in Regionen zu trennen und zu identifizieren, welche von ihnen Kreise sind und ihre Radien drucken.Wie überprüfe ich, ob eine Region ein Kreis ist?

Finden von Regionen ist relativ einfach, das habe ich getan. Das Finden von Kreisen ist jedoch komplizierter. Meine Idee ist es, alle Grenzpunkte einer Region zu finden, einen Durchschnittspunkt zu finden - mögliche Mitte dieses Kreises - und Abstände zwischen jedem Grenzpunkt und "Zentrum" zu berechnen. Wenn sie sich nicht sehr unterscheiden, ist das tatsächlich ein Kreis.

Vor allem ist das überhaupt möglich? Zweitens wird diese Methode sehr dünne Ringe auch als Kreise erkennen, und das will ich nicht. Wie behebe ich das?

UPD: Wie finde ich effektiv Grenzpunkte? Letzte Schicht von BFS? Punkte mit weniger als 6 Nachbarn (sieht für mich allerdings wie Bruteforce aus)?

+0

Sie können auch überprüfen, ob die Anzahl der Umfangspunkte in der Nähe von '2 * Pi * r' liegt, wobei' r' der Radius in Pixeln ist (die Hälfte der Bounding Box) ... es ist nicht notwendig, die Entfernung für alle Punkte zu überprüfen. Das gleiche gilt für den Bereich ... Siehe auch http://StackOverflow.com/a/37858301/2521214 – Spektre

+0

Die Bounding Box ist absolut nicht robust, zum Beispiel eine dünne Linie in der Region wird die Bounding Box machen viel größer und führt dazu, dass die Kreiserkennung fehlschlägt. – galinette

Antwort

3

Sobald Sie den Radius geschätzt haben durch den Abstand von Grenzpunkten zum Zentrum von durchschnittlich berechnen:

  • Die Fläche A1 der Schnittstelle zwischen der Region und dem Kreis
  • Die Fläche A2 des Kreises
  • der Bereich A3 der Region

Dann Verhältnisse von diesen Bereichen nahe 1 sein sollen, wenn dies eine Platte ist. Sie können einige Toleranzen definieren. Zum Beispiel:

  • A1/A2> 0,98
  • A1/A3> 0,97

Alternativ kann der Radius ohne Grenzpunkte geschätzt werden. Berechnen Sie einfach die durchschnittliche Entfernung von jedem Regionspunkt zum Mittelpunkt und multiplizieren Sie mit 3/2.

+0

Das funktionierte wirklich gut, auch ohne die Grenze zu finden, denn der Durchschnitt aller Punkte vom Zentrum ist 2/3R. Und mit 95% Toleranzen habe ich eine perfekte Anerkennung bekommen! – Akiiino

+0

Guter Punkt, vermeidet die Mühe der Grenzerkennung, die schwierig ist, robust zu machen! Ich habe die Antwort bearbeitet, um Ihre Idee einzubeziehen. – galinette