Die von Paul V. C. Hough 1962 patentierte Methode zur Erkennung von komplexen Strukturen [1] verwendet ein Parameterraum in dem jeder Punkt im Bild der auf einer Kante liegt, jede mögliche zu findende Form durch diesen Punkt zugewiesen bekommt. Das sind bei unterschiedlichen Formen unterschiedliche Parameter, bei einer Gerade zum Beispiel Steigung und Y Achsenabschnitt oder bei einem Kreis Radius und Mittelpunkt. Wenn alle Kantenpunkte im Parameterraum abgebildet sind, werden durch eine Häufigkeitsanalyse die Parameter der gesuchten Figuren bestimmt. [2] In Software wird der Parameterraum häufig durch ein mehrdimensionales Array von Ganzzahlen ausgedrückt. Das Kantenbild liegt häufig als 2 dimensionales binäres Array vor. Dadurch sind die Raumtransformation und die Maximafindung einfach zu lösen. Um eine Gerade in einem Bild zu beschreiben gibt es mehrere Möglichkeiten.
Die Gerade $$ l_{m_0 b_0} : y = m_0 x + b_0 $$ im \(xy\) − Raum kann als Punkt \(( m_0 ,b_0 )\) im \(mb\)-Raum interpretiert werden. Ein Kantenpunkt lässt sich durch unendlich viele Geraden mit der Eigenschaft $$ y_i = mx_i + b$$ erzeugen, die allgemein als Gerade \( b = − mx_i + y_i\) im \(mb\)-Raum
dargestellt werden können. Jeder Punkt einer Geraden \(l_{m_0 b_0}\) im Bild führt zu einer Geraden im \(mb\)-Raum. Diese Geraden schneiden sich im Punkt \(( m_0 ,b_0 )\) .
Den \(mb\)-Raum bezeichnet man als Akkumulator für die Geradenfindung, da die Werte aller Punkte dort Zusammengezählt werden.
 |
| Abb. 1 Gerade im xy-Raum als Schnittpunkt im mb-Raum (a) Punkte, (b) Schnittpunkt, (c) Gerade |
Zu den in Abbildung 1a gezeigten Punkten soll die dazugehörige Gerade ermittelt werden. Die Punkte werden als Geraden im \(mb\)-Raum (Abbildung 1b) betrachtet und der Schnittpunkt bei ( 1,1 ) entspricht den Parametern der Ausgangsgeraden (Abbildung 2a).
$$y = mx + b → b = − xm + y $$
Um den Berechnungsaufwand zu reduzieren, können nun die einzelnen Kantenpunkte vorher auf eventuelle Nachbarpunkte untersucht werden und der Akkumulator darauf hin aufgebaut werden. Hierzu können die acht benachbarten Felder eines Kantenpunktes betrachtet werden. Wenn ein Nachbarfeld auch ein Kantenpunkt ist, besteht die Wahrscheinlichkeit, dass durch diese beiden Punkte eine Gerade läuft. Wenn das Nachbarfeld kein Kantenpunkt ist, ist die Wahrscheinlichkeit gering, dass durch diese Punkte eine Gerade verläuft. Hier muss ein Kompromiss getroffen werden, wie genau man die Geradende-
tektion durchführen möchte. Ein weiterer Nachteil der gezeigten Methode ist, dass senkrechte Geraden eine
unendliche Steigung haben. Dies kann durch die Abbildung in der Hess’schen Normalform mit \(0 ≤ ρ ≤ 2π;l ≥ 0\) umgangen werden.
$$ l = xcosρ + ysinρ $$
Jeder Punkt impliziert eine Reihe von Geraden. Transferiert in den \(ρl)\-Raum ergibt sich eine sinusförmige Kurve.
 |
| Abb. 2 Gerade im \(xy\)-Raum als Schnittpunkt im \(ρl)-Raum |
Diese Werte werden in einem diskreten Akkumulator \(H [ ρ ][ l ]\) mit endlich vielen Werten \(ρ = 0,∆ρ,2∆ρ,…\) und \(l = 0,∆l,2∆l,…\) abgebildet. Die binären Kantenpunkte des Bildes sind bekannt: \(K : {( x_1 ,y_1 ) ; ( x_2 ,y_2 ) ; … ; ( x_n ,y_n )}\) . Man setzt alle Werte des Akkumulators \(H\) auf \(0\). Für alle Kantenpunkte in \( K \) berechnet man zuerst \( ρ \) und \( l \), dann erhöht man den Wert in \(H [ ρ ][ l ]\) um \( 1 \). Nachdem alle Kantenpunkte berücksichtigt wurden sucht man auffällig hohe Werte in \(H\). Man kann davon ausgehen, dass jeder lokale Spitzenwert in \(H\) eine Gerade im Bild beschreibt. Ein Beispiel zu dieser Methode zeigt Abbildung 2. Hier wurden die Punkte im Bild 2a als Sinuskurven transformiert. Schnittpunkte im \(ρl\)-Raum führen zu lokalen Maxima im Akkumulator. Das Parameterpaar eines Maximums im Akkumulator (Schnittpunkt in 2b) kann als eine Gerade \(l_{ρ_0 l_0} : l_0 = x /cosρ_0 + y /sinρ_0\) im \(xy\)-Raum betrachtet werden.
Um die Genauigkeit der Formdetektion zu erhöhen, kann anstelle einer Binär Matrix zur Kantenerkennung ein Graustufenbild verwendet werden. Hier können die Grauwerte eine Aussage über die Kantenstärke geben. Je stärker die Kante ist, desto mehr wird der Akkumulator für diese Stelle erhöht. So ergibt sich ein gewichtetes Bild, in dem kontrastreichere Kanten stärker herausstechen.
Literatur
[1] Hough, P. V. C.: US3069654: Method and Means for Recognizing Complex Pat-
terns, 1962.
[2] Prof. Dr. Xiaoyi Jiang, Michael Schmeing und Sönke Schmid: Computer
Vision und Mustererkennung: Einführung – Kapitel 7: Bildsegmentierung: Hough,
Okt. 2012.