Hough Transformation

[chrishawaii]

Hi liebe Leute,

ich befasse mich gerade etwas mit der Hough-Transformation. Ich denke, daß ich das grob verstanden habe. Wenn der Radius eines zu erkennenden Kreises bekannt ist, dürfte das lles kein Problem sein, nachdem mittels Kantenoperatoren ein Punkt der potentiellen Kreiskante gefunden wurde. Auf diese Weise läßt sich easy der Kreismittelpunkt bestimmen.
Was ist aber, wenn der Radius des zu suchenden Kreises nicht bekannt ist, sondern lediglich, daß ein Kreis vorhanden ist.
Wie läßt sich dann die Hough-Transformation nutzen bzw. wie läßt sich dann der Kreis finden?

Bin für jeden Tip dankbar.
Gruß und Danke für jeden Tip!
Christian

[ogni42]

Nimm die Kante und wirf sie einem Kreisausgleichverfahren vor. Du löst dabei numerisch die Kreisgleichung mit den Punkten so, dass die Interpolation der Punkte einen Kreis ergeben.

danke ogni42 für die antwort, aber was ist ein kreisausgleichsverfahren?
ich habe mir folgendes überlegt:
jeden kantenpunkt (erzeugt mit canny-operator) als kreismittelpunkt annehmen, den radius in einer schleife vergrößern und sämtliche schnittpunkte der kreise mit kantenpunkten speichern. der kantenpunkt, der die meisten schnittpunkte mit einem kreis aufweisen kann, ist der gesuchte kreismittelpunkt.
was hälst du von diesem ansatz? vermutlich ist er allerdings extrem rechenaufwendig (vielleicht zu rechenaufwendig?).
wie ich das algorithmisch umsetze, weiß ich noch nicht so genau.

gruss chris

[ogni42]

Vielleicht habe ich was falsch verstanden:
Möchtest Du Punkte auf einem Kreisrunden Kante erkennen (bzw. die Kreisparameter für eine solche Kante bestimmen), oder suchst Du einen Kreis bei dem einige Punkte den Mittelpunkt bilden, andere auf der Kante liegen?

[5_String]

bei der Hough-Transformation löst man das problem so das du den Parameterraum um einen dritten parameter erweiterst nämlich den radius.
nun findest du alle kreise mit allen radien.

[5_String]

hähme ja an das du für einen kreis durch 2 parameter definiert hast a und b, also (x-a)^2 + (y-b)^2 = r^2

[CowZ]

Genau. Du musst den Radius als dritten Parameter nehmen (neben X- und Y-Wert vom (potentiellen) Mittelpunkt).

Ich habe dazu mal ein kleines Progrämmchen geschrieben, als ich darüber im Informatikunterricht ein Referat gehalten habe.
http://www.cowz.de/vbnet/Hough.exe
Anleitung:
Starten -> Init -> Redraw -> Process Origin -> PreDraw -> Process Result

Links ist das Ursprungsbild, in der Mitte der Houghraum, Rechts das Ursprungsbild mit überlegtem Kreis (in rot).
Die Scrolleiste scrollt den Houghraum in Z-Richtung (Radius)
Redraw zeichnet die Felder neu, wenn die weiß geworden sind.

Bei Fragen zum Programm einfach melden :)

Gruß CowZ
PS: Natürlich liegen alle Rechte vom Programm bei mir ;) Wenn ihr das irgendwo vorführen wollt, einfach Bescheid sagen, hab kein Problem damit und stelle euch dann auch gerne den Sourcecode zur Verfügung.

Also m.E. geht das mit Ausgleichsrechnung (s. Wikipedia oder Mathebuch f. ingenieure und Physiker) wesentlich einfacher, sofern man eine Kante hat, von der man annimmt, dass sie auf einem Kreis liegt (da habe ich zumindest so verstanden). Dann geht es nur darum, die Kreisgleichung mit den Punkten zu lösen, was mathematisch das numerische Lösen eines überbestimmten Gleichungssystems ist.

[ogni42]

Post oben ist von mir.

[CowZ]

ogni42: Hast du dich schon mit der Houghtransformation beschäftigt?

Die Houghtransformation ist sowieso alles andere als effektiv, da BruteForce. Und wenn man die Houghtransformation als Weg nimmt, dann muss man den Radius als dritten Parameter, also als dritte Dimension im Houghraum nehmen.

Mir is natürlich klar, dass es effektivere Methoden gibt. Aber bei der Houghtransformation hast du auch keine Kanten etc. sondern einfach nur Punkte, die auf dem Kreis liegen könnten.

Gruß, CowZ

[ogni42]

Nee, ich laber hier nur so rum :)

Wenn bekannt ist, dass ein Kreis vorhanden ist UND man den Mittelpunkt kennt, kann man die Hough Transformation für Linien verwenden. Der Radius des Kreises ist dann der Mittelwert der gefundenen Radien, da ein Punkt in der xy-Ebene sich auf eine Linie in der r,phi Ebene abbildet. Damit das funktioniert, muss der Ursprung des xy Koordinatensystems im Mittelpunkt des Kreises liegen.

Man braucht halt immer soviele Dimensionen im Hough-Raum, wie man Unbekannte im Ursprungsraum hat.

[CowZ]

Ja, ok, kann so sein (versteh ich aber nich, egal ;))

Aber er ist oben ja davon ausgegangen, dass er erst einen Kreis sucht, bei dem der Radius vorgegeben ist, und dann einen Kreis mit variablem Durchmesser.

Gruß, CowZ