Hough-Transformation

Mittels der Hough-Transformation (1962 von Paul Hough entwickelt) kann man in einem Bild Geraden, Kreise oder sonstige Objekte erkennen, die mathematisch mit Hilfe einer Parametrisierung beschrieben werden können.

Dieses Verfahren ist robust in dem Sinne, dass es auch bei Fehlern noch gute Ergebnisse liefert. In der Praxis sind ggf. noch weitere Anpassungen nötig, im Folgenden geht es um die Grundidee.

„Wenn du ein Problem nicht direkt lösen kannst, versuche es indirekt.“

Das Grundprinzip der Transformation ist schnell erklärt, es ist ähnlich wie bei einer Wahl:

  1. Erstelle ein Rasterfeld möglicher Parameterwerte (Die Politiker, die sich zur Wahl stellen)
  2. Jeder Kantenpunkt gibt eine Stimme  für einen Kandidaten im Raster und erhöht diesen (Stimmenanzahl)
  3. Bestimmte lokale oder globale Maxima im Raster (Wer hat gewonnen?)

Diese globalen oder lokalen Maxima entsprechen der gesuchten Form im Bild 🙂

Beispiel – Problemsituation

Angenommen, ein System bekommt Bilder von Münzen vorgelegt und soll deren Ort (a,b) auf einer Platte identifizieren. Das sind die beiden gesuchten Parameter.

Eine weitere Information, die uns vorliegt: Die gesuchten Münzen haben einen Radius von 11 mm. Damit bleibt es bei zwei Parametern. Übersetzt man die Situation in ein mathematisches Modell sind wir auf der Suche nach dem Mittelpunkten von (beliebig vielen) Kreisen.

IMG_2898

Mit Hilfe einiger Vorverarbeitungsschritte wird die wesentliche Information extrahiert. Dies  geschieht hier mit einem Hochpass und anschließender Schwellwertoperation, in der Praxis ist die Kantenerkennung mittels der Sobel-Filter oder des Canny-Algorithmus üblich.

IMG_2898b

IMG_2898eNun liegen uns eine Menge von Punkten vor, die als Kanten erkannt worden sind.

Wählen wir eine Teilmenge dieser Punkte aus, können wir mit der Hough-Transformation starten.

Der Einfachheit halber wird das Verfahren zunächst für eine Münze gezeigt:

Gegeben sei eine Menge von Kantenpunkten \{(x_i,y_i)\}_i

Baue den Akkumulator-, Dual-, Hough- oder ab-Raum auf: Dieser ist zweidimensional und sammelt die möglichen Kreismittelpunkte der Kreise im ursprünglichen Bild.

In der Praxis muss man das stetige Problem hier diskretisieren, da nur endlich viel Speicherplatz zur Verfügung steht. In unserem Fall könnte der Raum A[a][b] mit endlich vielen Werten

a = 0,\Delta a, 2 \Delta a, \cdots

b=0, \Delta b, 2 \Delta b, \cdots

mit  \Delta a = \Delta b = 0.1 gewählt werden. Benötigt man eine höhere Genauigkeit, muss die Diskretisierung verfeinert werden.

Jeder dieser Kantenpunkte (x_k,y_k) kann Randpunkt eines Kreises sein, dessen Mittelpunkt im Abstand r (bekannt) liegt. Für jeden Wert dieser Kreismittelpunkte zählen wir im Akkumulator die entsprechende Zelle bzw. tragen einen Wert ein.

(\begin{array}{c}a\\b\end{array})=(\begin{array}{c} x_i -r cos(\phi)\\y_i -r cos(\phi)\end{array})

 Auch der Winkel \phi muss hier geeignet diskretisiert werden, die folgende Animation (Klick!) veranschaulicht den Prozess. hough_1_akku

Für alle weiteren Kantenpunkte wird genauso verfahren (hier nur zwei weitere):

hough_1_akku2

Wir suchen im Akkumulator nun nach Häufungen und ermitteln den Punkt H. Dieser ist der Mittelpunkt der gesuchten Münze im Ausgangsbild – fertig!

Unbenannt

Würde man im Vorfeld nicht wissen, wie groß die gesuchten Kreise sind, würde der Hough-Raum dreidimensional werden. Dennoch könnte man auch hier nach Häufungspunkten suchen (Verschiebe einmal den Regler folgendes GeoGebra-Applets – Wann bilden sich wo Häufungen?)

Der Verlauf der Hough-Transformation in Bildern:

detection
oben: Original und Kantenbild nach Canny-Algorithmus,  unten: Akkumulator und Ergebnis. Quelle: [1]
Es gibt noch viele weitere Verfahren, die sich mit Fragen der Effizienz beschäftigen. Damit können sich interessierte Teilnehmer im Rahmen eines Projektkurs ausführlicher befassen.

[1] Vorlesungsskript Wintersemester 2013

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.