Ein Mensch erkennt Linien in einem Bild auf einen Blick. Für einen Comuter besteht ein Bild jedoch zunächst aus einer Ansammlung von Daten, die für jedes Pixel dessen Graustufe oder Farbwerte angeben. Die Hough-Transformation ist ein Standardverfahren, mit dem ein Computer Geraden, Ellipsen und andere geometrische Objekte in einem digitalisierten Bild finden kann. Das robuste Hough-Verfahren kann auch in einem verrauschten Bild unvollständige oder teilweise verdeckte Linien finden.
Eine Gerade lässt sich mathematisch beschreiben durch ihren senkrechten Abstand r zum Koordinatenursprung sowie durch den Winkel φ zwischen der entsprechenden Verbindungstrecke und einer Koordinatenachse. Jedem Wertepaar (r,φ) entspricht demnach eine Gerade. Um Geraden im Bild zu finden, könnten wir für alle Wertekombinationen (r,φ) die Bildpunkte mit Koordinaten (x,y) zählen, die nahe der jeweiligen gedachten Linie liegen. (r,φ)-Kombinationen entsprechen dann einer Geraden im Bild, wenn zu ihnen viele Bildpunkte gehören..
Wenn ein Punkt (x,y) vorgegeben ist, gilt für eine Gerade mit dem Winkel φ, die durch diesen Punkt geht,
r=x·cos(φ)+y·sin(φ).
Das ist das Skalarprodukt des Ortsvektors (x,y) des Punktes auf der Geraden und des Normalenvektors (cos(φ),sin(φ)) der Geraden, der senkrecht auf ihr steht.
Normalen-Darstellung einer Geraden. r bezeichnet den senkrechten Abstand zum Koordinatenursprung und φ den Winkel zwischen der Verbindungsstrecke und der x-Achse. Geraden lassen sich durch ihre r- und φ-Werte charakterisieren. Somit sind auch alle Bildpunkte auf einer Geraden durch das Wertepaar (r,φ) charakterisiert. Es ist r=x·cos(φ)+y·sin(φ) (vgl. Haupttext). Für die blaue und rote Gerade sind diese Werte im rechten Graphen eingezeichnet.
Wie finden wir Linien im Bild?
Um die Datenmenge zu reduzieren, kann das Originalbild in ein schwarz-weißes Kantenbild umgewandelt werden, das nur die Helligkeis- oder Farbsprünge im Bild anzeigt. Wir bearbeiten solch ein s/w-Bild mit der vorher ermittelten Anzahl weißer Bildpunkte N mit den Koordinaten (x[1],y[1]), ..., (x[N],y[N]) oder abgekürzt (x[i],y[i]) mit i=1,...,N. Für jeden dieser Punkte verwenden wir φ-Werte, die in kleinen Schritten von 0 bis fast 2π gehen. Der Winkel φ=2π entspricht φ=0 und wird daher ausgelassen. Die Schrittweite darf nicht zu groß und nicht zu klein sein, damit weder die Rechenzeit zu lang ist, noch Geraden übersehen werden. Für jeden der φ-Werte berechnen wir r=x[i]·cos(φ)+y[i]·sin(φ). r muss sinnvoll gerundet werden, damit wir ähnlich wie bei φ nicht zu viel und nicht zu wenig r-Werte erhalten. Damit erhalten wir die (r,φ)-Werte der Geraden, die durch diese Punkte gehen. Wir summieren schließlich die Anzahl der Bildpunkte, die jeweils zu denselben (r,φ)-Paaren gehören. Diese Summen geben für die untersuchten (r,φ)-Paare an, wie viel Bildpunkten auf den gedachten Geraden liegen. Die Zuordnung (r,φ) -> Anzahl Bildpunkte wird auch Histogramm genannt und ist das Ergebnis der Hough-Transformation unseres Originalbildes. Eine große Summe lässt vermuten, dass im Bild tatsächlich eine Gerade mit dem zugehörigen (r,φ) verläuft. Wenn nicht ...
Zu viel Daten
Bei diesem Verfahren erhalten wir zu viel Daten. Eine große Summe von Bildpunkten für ein (r,φ)-Paar muss nicht immer zu einer sichtbaren Geraden im Bild gehören, beispielsweise wenn sich in einem Bereich Bildpunkte zufällig häufen. Wir versuchen daher unser Histogramm etwas auszumisten. Dazu suchen wir das (r,φ)-Paar mit der grösten Bildpunktzahl (Maximum) und berechnen hierfür die Bildkoordinaten der zugehörigen Gerade. Für die Bildpunkte, die auf dieser gedachten Gerade liegen, berechnen wir die (r,φ)-Werte und ziehen sie diesmal vom vorhandenen Histogramm ab. Dadurch verschwindet das Maximum und das Gesamtniveau des Histogramms wird abgesenkt. Mit den anderen Bildpunkten wird erneut die Hough-Transformation durchgeführt. Das ganze Verfahren wird so lange wiederholt, bis bis alle Punkte in Geraden aufgegangen sind oder die festgesetzte Maximalzahl Wiederholungen erreicht wurde.
Beispiel. In der Raster-Grafik sind 3 Bildpunkte mit den Koordinaten (1,8), (3,7) und (7,5) eingezeichnet. Durch jeden der Punkte können wir Geraden zeichnen, z. B. mit den Winkeln 0, 0,2π, 0,4π,..., 1,8π. Hier sind jedoch nur 3 Geraden durch den Punkt (7,5) eingezeichnet. r ist in der unteren Grafik für die 3 Geraden rot gezeichnet. Da r[i]=x[i]·cos(φ)+y[i]·sin(φ) mit i=1, 2, 3 (Index i der 3 Bildpunkte), sind uns alle Wertepaare (r,φ) sämtlicher Bildpunkte bekannt. Für den Punkt (x,y)=(7,5) z. B. haben wir (r,φ)=(7,0), (9, 0,2π), (7, 0,4π),... Diese Rechnungen führen wir für alle Bildpunkte und alle Winkel aus. Danach zählen wir, wie viel Bildpunkte insgesamt auf dieselben Wertepaare (r,φ) entfallen. Wir sehen dann, dass auf die Gerade mit (7, 0,4π) 3 Bildpunkte entfallen, auf andere (r,φ)-Paare nur 1 Bildpunkt. Wir interpretieren daher, dass es im Bild Punkte gibt, die eine Gerade mit (r,φ)=(7, 0,4π) bilden.
Link
XHoughtool
Softwarepaket rund um die Hough-Transformation zur Linienerkennung
http://www2.lut.fi/dep/tite/XHoughtool/
