Einleitung
Die Hough-Transformation ist eine Technik, die dazu dienen soll,
geometrische Merkmale aus einer Menge von Punkten herauszufiltern.
Ihr Grundprinzip lässt sich mit einer Art Abstimmung vergleichen.
Dabei werden für jeden Token aus einer Menge alle geometrischen
Figuren betrachtet, die durch ihn laufen. Diese Figuren erhalten
eine Stimme. Ziel ist es, Objekte mit vielen Stimmen zu finden.
In diesem Applet soll dies beispielhaft an Hand von Linien und Kreise verdeutlicht
werden. Man sucht demzufolge alle Linien bzw. Kreise, die durch einen im Bildraum
gegebenen Pixel laufen. Diese enthalten eine Stimme im so genannten
Hough-Raum oder auch Akkumulator. Die Elemente dieses Raumes ähneln
einem Stimmbehälter. Dabei zählt jeder Behälter die Stimmen
für eine bestimmte Linie hoch. Dieser Prozess wird für jeden Pixel des
Ausgangsbildes wiederholt. Je mehr Stimmen ein Objekt am Ende
besitzt, desto mehr Punkte liegen auf der dazugehörigen Linie bzw. Kreis.
In den folgenden Schritten soll der gesamte Prozess je nach Auswahl für Linien bzw. für Kreise visualisiert
und die einzelnen Schritte genauer erläutert werden.
Was genau ist der Hough-Raum?
Im Hough-Raum werden die Informationen aus einem Bild in etwas anderer
Form dargestellt. Jede im Bildraum vorhandene Gerade wird im Hough-Raum
nur noch als Punkt dargestellt. Dieser Punkt wird gewichtet und enthält
umso mehr Stimmen, je mehr Punkte auf der im Bild vorhandenen Linie liegen.
Bei der Suche eines Kreises ist der Akkumulator 3-dimensional, da nun zur Position zusätzlich der
Radius bestimmt werden muss. Die Dimensionen sind abhängig von den Unbekannten.
Eine Elipse würde bereits einen Akkumulator mit 5 Dimensionen erfordern.
Das Prinzip bleibt aber gleich, wie bei den Linien.
2. Kreise
Um aus einem Kreis im Bildraum einen Punkt im Hough-Raum zu erhalten, sind folgene Schritte notwendig:
2.1 Schritt
Ein Kreis hat die Gleichung r² = x² + y². Die (x,y)-Koordinaten beschreiben den Kreismittelpunkt. Diese beiden
Werte sind im Hough-Raum und im Bildraum identisch. Nun bleibt jedoch im Gegensatz zur Linie ein weiterer Parameter übrig.
Der Radius beschreibt demzufolge den 3.Parameter. Insgesamt ergibt sich ein 3-dimensionaler Hough-Raum.
Für den Radius muss zuvor ein Wertebereich festgelegt werden, beispielsweise von 5 bis 20. Nun wird für jeden Bildpixel vom
Bildraum im Hough-Raum ein Kreis gezeichnet mit dem Radius 5.
Links Bildraum mit gegebener Pixelmenge, rechts der Akkumulator/Houghraum, zur Vereinfachung befinden wir uns bereits in der exakten Ebene des Radius
2.2 Schritt
Mit diesem Vorgehen wird nun der gesamte Wertebereich für den Radius abgearbeitet.
Jeder Schnittpunkt der Kreise untereinander, führt zu einer Erhöhung der Wertigkeit im Hough-Raum.
Falls ein Kreis existiert, der durch mehr als einen Punkt verläuft, hat dieser für alle Punkte die gleichen Werte für x,y und r.
Demzufolge existieren für diese Punkte im Hough-Raum mehrere Kreise, die alle durch den gleichen Punkt (x,y,r) verlaufen müssen.
Beispiel:
Ein exakter Kreis würde den Wert im Hough-Raum an diesem Punkt maximal steigern, da alle Schnittpunkt im gleichen Punkt liegen.
Im Hough-Raum wäre nun ein Punkt mit der Position (x,y,r) des exakten Kreises eingezeichnet.
2.3 Schritt
Wenn alle Punkte des Bildes durchlaufen wurden, werden aus dem Hough-Raum diejenigen
Punkte ausgewählt, die die meisten Bewertungen haben. Diese gehören jeweils
zu einem Kreismittelpunkt mit dem entsprechenden Radius im Bildraum. Die Anzahl an Punkten (Schnittpunkte), die auf diesem Kreis liegen,
entspricht genau der im Hough-Raum angegebenen Wertigkeit.