Algorithmus zum Finden von Kreisen in Array

Question

Ich habe ein Array mit 600x600 Integer-Werten. Die Werte repräsentieren einen Kreis. Zum Beispiel: 0 ist außerhalb,> = 1 ist innerhalb des Kreises. Hier ist ein kurzes Beispiel:

0000110000000 
0001111000000 
0011111200000 
0112112110000 
1111111111000 
0111411110000 
0011131100000 
0000110000000 
0000000000000 
0000000000000 

Die Position und die Größe des Kreises in der Reihe unterscheidet. Jetzt suche ich nach einem schnellen Algorithmus, um das Zentrum und den Radius des Kreises zu finden. Schnell, weil ich viele Arrays verarbeiten muss.

Answer 1

Überlagern Sie ein Gitter, gehen Sie, (kleine Matrizen: jede Zeile und Spalte, große Matrizen jede X. Zeile und Spalte) und finden Sie die Punkte, an denen die Änderung (0 ->> = 1 oder umgekehrt) geschieht.

Wenn Ihr Raster symmetrisch und dicht genug ist, ist der Durchschnitt dieser Punkte gleich dem Mittelpunkt.

Die durchschnittliche Entfernung (sqr (x-xm) + sqr (y-ym))) der gefundenen Punkte und der Mitte ist ein Maß für den Radius.

Für größere Datasets reichen möglicherweise nur gehende Zeilen aus, und Sie scannen nur die X-te Zeile. Wenn Sie mit echten Bildern arbeiten, müssen Sie möglicherweise auf Rauschen und Helligkeitsschwankungen achten.

Answer 2

Es ist möglich, es schneller zu machen. Nach Ihrer Stichprobe ist es egal (und wir dürfen nicht schätzen), ob es einen Kreis oder ein Quadrat gibt.

Unter der Annahme, dass es eine Zwei dimention 0-basierten Array der Radius einfach sein wird, die die Anzahl der Nicht-Null (nicht leer) Zeilen (oder Spalten), dividiert durch 2.

Algo.

1. Findet die Anzahl der Nicht-Null-Reihen und ihren ersten (oben) Index. Teilen Sie diese Zahl durch zwei und addieren Sie die Anzahl der Nullzeilen mit Indizes kleiner als die niedrigste Zeile ungleich Null. Jetzt kennen Sie die Koordinaten radius und y.

2. Suchen Sie die erste (linke) Spalte ungleich Null und fügen Sie den Radius zu ihrem Index hinzu. Jetzt haben Sie die x Koordinate.

In dem mitgelieferten Beispiel.

1. Die Anzahl der Nicht-Null-Zeilen ist 8. Die radius ist 8/2 = 4. Es sind 0 Zeilen nach oben, bevor die Nicht-Null-Zeilen (in anderen Worten, die ID des ersten nicht Nullzeile ist 0). Die y Koordinate ist also 0 + 4 = 4.
2. Es gibt 0 leere Spalten links von der ersten Nicht-Null-Spalte (oder die ID der ersten Nicht-Null-Spalte ist 0). Die x Koordinate wird 4 + 0 = 4.

Um zu wissen, ob die Spalte Null ist, dass Sie eine Funktion wie diese verwenden:

IsEmpty := true; 
for i := 0 to High(Column) do 
if Column[i] > 0 then 
    begin 
    IsEmpty := false; 
    Break; 
    end;