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.
1. Linien
Um aus einer Linie im Bildraum einen Punkt im Hough-Raum zu erhalten, sind einige mathematische Umformungen nötig:
1.1 Schritt
Eine Gerade hat die Gleichung f(x): y = mx + n.
Für einen festen Punkt P(x,y) lassen sich mit verschiedenen Werten für
m und n unterschiedliche Geraden darstellen, die durch diesen Punkt laufen.
Zuerst wird die Gleichung nach dem Anstieg umgestellt:
Davon ausgehend, dass x und y gegeben sind, entsteht nach dieser Umwandlung eine
Geraden-Gleichung. Diese Gerade gehört zum Hough-Raum und präsentiert
alle Linien, die durch den Punkt (x,y) im Bildraum verlaufen. Alle Punkte (m,n)
einer Gerade im Hough-Raum erhalten eine Gewichtung, beginnend bei eins. Diese
Wertigkeit gewinnt im weiteren Verlauf noch an Bedeutung.
Links Bildraum mit gegebener Pixelmenge, rechts der Akkumulator/Houghraum
1.2 Schritt
Als nächstes wird der erste Schritt für alle Punkte im Bildraum fortgesetzt.
Falls eine Gerade existiert, die durch mehr als einen Punkt verläuft, hat diese
für alle Punkte die gleichen Werte für m und n. Demzufolge existieren für
diese Punkte im Hough-Raum mehrere Geraden, die alle durch den gleichen Punkt (m,n)
verlaufen müssen. Jede Funktion, die durch diesen Schnittpunkt verläuft,
erhöht dessen Wertigkeit um eins.
1.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 einer Geraden im Bildraum. Die Anzahl an Punkten, die auf dieser Geraden liegen,
entspricht genau der im Hough-Raum angegebenen Wertigkeit.
1.4 Schritt
Die Umstellung der Geradengleichung nach m hat jedoch einen entscheidenden Nachteil.
Wenn ein Punkt direkt auf der x-Achse liegt, wird der Anstieg m demzufolge unendlich
groß. Das hätte wiederum zur Folge, dass auch der Hough-Raum unendlich groß wird
und eine Implementierung so nicht möglich wäre. Deswegen wird die Gleichung
noch ein weiteres Mal umgeformt. Die resultierende Gleichung beschreibt eine Linie durch
den kürzesten Abstand d zum Ursprung und den Winkel α zwischen Linie und x-Achse.
Somit ist eine Darstellung gefunden, die den Hough-Raum auf eine endliche Größe
begrenzt, da der Winkel α nur in einem Wertebereich von 0 bis 2π alle möglichen Linien
repräsentiert. Der kürzeste Abstand d der Linie zum Ursprung kann auch nicht
größer werden, als die Bilddiagonale. Daraus resultierend treten im Hough-Raum
keine Linien mehr auf, sondern nur noch Kurven fon folgender Form:
Ansonsten gibt es keine wesentlichen Veränderungen.