Hough-Transformation

Die Hough-Transformation (Sprechweise [hʌf]) ist ein robustes globales Verfahren zur Erkennung von Geraden, Kreisen oder beliebigen anderen parametrisierbaren geometrischen Figuren in einem binären Gradientenbild, also einem Schwarz-Weiß-Bild, nach einer Kantenerkennung. Das Verfahren wurde 1962 von Paul V. C. Hough unter dem Namen „Method and Means for Recognizing Complex Patterns“ patentiert.^[1]

Zur Erkennung von geometrischen Objekten wird ein Dualraum erschaffen (speziell: Parameterraum, Hough-Raum), in den für jeden Punkt im Bild, der auf einer Kante liegt, alle möglichen Parameter der zu findenden Figur im Dualraum eingetragen werden. Jeder Punkt im Dualraum entspricht damit einem geometrischen Objekt im Bildraum. Bei der Geraden kann das z. B. die Steigung und der y-Achsen-Abschnitt sein, beim Kreis der Mittelpunkt und Radius. Danach wertet man den Dualraum aus, indem man nach Häufungen sucht, die dann der gesuchten Figur entsprechen.

Geradenerkennung

Darstellung einer Hough-Transformation eines Pixelbildes mit zwei Linien zu einem Raum aus Winkel und Abstand zum Bildmittelpunkt. Die beiden hellen Punkte sind Häufungspunkte im Ergebnisraum, sie entsprechen den beiden Eingabelinien.

Bei der Geradenerkennung mittels der Hough-Transformation muss man zuerst geeignete Parameter für eine Gerade finden. Steigung und y-Achsen-Abschnitt eignen sich nur bedingt, da zur y-Achse parallele Geraden eine unendliche Steigung haben und daher im (für die Berechnung zwangsläufig) endlichen Parameterraum nicht mehr abgebildet werden können. Dieses Problem kann man umgehen, wenn man eine zweite Hough-Transformation auf dem um 90° gedrehten Bildraum durchführt, was aber recht umständlich ist. In der neueren Literatur überwiegt daher der Ansatz, Geraden durch ihre hessesche Normalform zu repräsentieren. Als Parameter wählt man den Winkel $\alpha$ und den (euklidischen) Abstand d, wobei $\alpha$ der Winkel zwischen der Normalen der Gerade (= Lot) und der x-Achse ist, und $d$ den Abstand vom Ursprung zum Lotfußpunkt auf der Gerade bezeichnet.

Damit ergibt sich die Parametergleichung $d=x\cdot \cos(\alpha )+y\cdot \sin(\alpha )$ , mit der man für alle Punkte auf Kanten im Bild die entsprechende Kurve im Dualraum einzeichnet. Dabei bezeichnen $\alpha$ und $d$ die Variablen, während x und y jetzt zu Parametern umfunktioniert wurden. x und y sind die Koordinaten der vorher detektierten Kantenpunkte. Das Ausgangsbild wird zunächst einem Kantendetektions-Algorithmus unterzogen (z. B. Canny- oder Sobel-Filter) und dadurch der zu untersuchende Punktraum auf mögliche Kanten eingeschränkt.

Der Dualraum wird nun also von $\alpha$ und $d$ aufgespannt. Zu jedem errechneten Wert $d$ wird jetzt im Dualraum (repräsentiert als Matrix) an der Stelle $(\alpha |d)$ der Wert um 1 erhöht, also quasi für die dadurch repräsentierte Gerade „gevotet“. Deshalb nennt man die Matrix auch oft „Voting-Matrix“.

Der nächste Schritt besteht in der Analyse des Dualraums, bei der man nach Häufungspunkten in der Voting-Matrix sucht. Diese Häufungspunkte im Dualraum repräsentieren mögliche Geraden im Bildraum, da sie offensichtlich unter dem gleichen Winkel $\alpha$ mit der gleichen Entfernung $d$ vom Ursprung repräsentiert werden.

Aufgrund der Unabhängigkeit der einzelnen Zellen des Parameterraumes zueinander bei der Berechnung der Häufungspunkte ist die Hough-Transformation leicht parallelisierbar.

Einfacher Algorithmus

Ein einfacher Algorithmus, um eine Hough-Akkumulation durchzuführen, könnte etwa so aussehen:

max_d := sqrt((bildhöhe)^2 + (bildbreite)^2)
min_d := max_d * -1
houghRaum[0 $\ldots \pi$ ][min_d $\ldots$ max_d] := 0
foreach pixel != 0 do
   for  $\alpha$  := 0 to  $\pi$  do
      d := pixel_x * cos( $\alpha$ ) + pixel_y * sin( $\alpha$ )
      houghRaum[ $\alpha$ ][d]++
   end
end

Das Resultat der Akkumulation ist ein zweidimensionales Array, welches die Häufigkeit des Auftretens für jede Kombination aus $\alpha$ und $d$ enthält. Weil die Geraden nicht gerichtet sind, muss nur der Bereich von 0 bis $\pi$ ausgewertet werden, da sich danach die Geraden mit den bereits berechneten decken. In der Praxis wird häufig die Bildmitte als Koordinatenursprung verwendet.

Kantenerkennung

Im Allgemeinen lässt sich die Gerade $y=m\cdot x+b$ als Punkt $(b,m)$ im Parameterraum darstellen. Vertikale Linien stellen jedoch ein Problem dar. Sie würden zu unbeschränkten Werten des Steigungsparameters $m$ führen. Aus rechnerischen Gründen schlugen Duda und Hart daher die Verwendung der Hesse-Normalform

r=x\cdot \cos(\theta )+y\cdot \sin(\theta )

vor, wobei $r$ der Abstand vom Koordinatenursprung zum nächsten Punkt auf der Geraden und $\theta$ der Winkel zwischen der x-Achse und der den Koordinatenursprung verbindenden Linie ist mit diesem nächsten Punkt.

Die Intuition für diese Form ist, ähnlich wie bei der Ebenengleichung, dass jeder Vektor auf der Geraden orthogonal zu der vom Koordinatenursprung ausgehenden Geraden der Länge $r$ sein muss. Es ist leicht zu erkennen, dass der Schnittpunkt der Funktionsgeraden und der vom Koordinatenursprung ausgehenden Senkrechten bei $P_{0}=(r\cdot \cos(\theta ),r\cdot \sin(\theta ))$ liegt. Für jeden Punkt $P$ auf der Geraden muss der Vektor $P-P_{0}$ also orthogonal zum Vektor $P_{0}-0=P_{0}$ sein. Daher muss für jeden Punkt $P=(x,y)$ auf der Funktionsgeraden die Gleichung $(P-P_{0})\cdot P_{0}=0$ erfüllt sein. Daraus folgt $P\cdot P_{0}=P_{0}\cdot P_{0}$ . Wegen $P=(x,y)$ und $P_{0}=(r\cdot \cos(\theta ),r\cdot \sin(\theta ))$ erhalten wir $r\cdot (x\cdot \cos(\theta )+y\cdot \sin(\theta ))=r^{2}\cdot (\cos ^{2}(\theta )+\sin ^{2}(\theta ))$ . Wegen $\cos ^{2}(\theta )+\sin ^{2}(\theta )=1$ erhalten wir die endgültige Form von $x\cdot \cos(\theta )+y\cdot \sin(\theta )=r$ .

Es ist daher möglich, jeder Bildzeile ein Paar $(r,\theta )$ zuzuordnen. Die $(r,\theta )$ -Ebene wird manchmal als Hough-Raum für die Menge von geraden Linien in zwei Dimensionen bezeichnet. Diese Darstellung macht die Hough-Transformation konzeptionell der zweidimensionalen Radon-Transformation sehr nahe. Tatsächlich ist die Hough-Transformation mathematisch der Radon-Transformation äquivalent, aber die beiden Transformationen haben unterschiedliche rechnerische Interpretationen, die traditionell mit ihnen verbunden sind. Bei einem einzelnen Punkt in der Ebene entspricht die Menge aller durch diesen Punkt verlaufenden Geraden einer Sinuskurve in der $(r,\theta )$ -Ebene, die für diesen Punkt eindeutig ist. Eine Menge von zwei oder mehr Punkten, die eine gerade Linie bilden, erzeugt Sinuskurven, die sich bei $(r,\theta )$ für diese Linie schneiden. Somit kann das Problem des Erfassens kollinearer Punkte in das Problem des Auffindens gleichzeitiger Kurven umgewandelt werden.^[2]

Hough-Transformation für Kreise und generalisierte Hough-Transformation

Wie oben erwähnt kann die Hough-Transformation – in abgewandelter Weise – nicht nur für das Detektieren von Geraden, sondern z. B. auch von Kreisen eingesetzt werden. Ausgehend vom Kantenbild wird jedes Kantenpixel als von Kreisen eines bestimmten Radius erzeugt angesehen. Die Transformation in den Hough-Raum funktioniert so, dass man im Akkumulator alle Kreismittelpunkte einträgt, die zu diesem Kantenpixel führen könnten (jedes Akkumulatormittelpunktpixel um 1 erhöhen). Wenn nun die Punkte im Kantenbild einen Kreis repräsentieren, ist in der Akkumulatormatrix ein besonders hoher Wert an der dazugehörigen Stelle des Kreismittelpunkts eingetragen, da dort sehr viele Kantenpixel des Kreises für den Mittelpunkt abgestimmt haben. Die Maxima im Hough-Raum repräsentieren also die Kreismittelpunkte.

Die ersten zwei Dimensionen des Hough-Raums entsprechen in diesem Fall denen des Bildraums, da die (x,y)-Koordinaten in beiden Fällen die Lage des Kreismittelpunktes beschreiben. Zusätzlich dazu ist laut der Kreisgleichung $x^{2}+y^{2}=r^{2}$ der Radius r der dritte Parameter, der beachtet werden muss. Man spricht bei Kreisen daher von einem 3-dimensionalen Hough-Raum (xc, yc, r). Die Wertegrenzen für den Radius müssen fest vorgegeben werden (z. B. mittels A-priori-Wissen).

Für Ellipsen und jede andere durch eine parametrische Gleichung darstellbare Form kann dieses Verfahren ebenfalls angewendet werden. Jedoch steigt die Dimension des Hough-Raums mit der Variablenzahl (bei Ellipsen: 5), was den Rechenaufwand deutlich steigert.

Es ist ebenfalls möglich, eine nicht durch parametrische Repräsentation darstellbare Struktur zu finden. Dieses Verfahren wird generalisierte Hough-Transformation (GHT) genannt. So können beliebige Formen in einem Bild gefunden werden. Das Prinzip hierbei ist, dass man eine formabhängige Lookup-Tabelle errechnet. In dieser sind die möglichen Vektoren zu einem Referenzpunkt den unterschiedlichen Gradientenrichtungen zugeordnet. Durch einige Umformungen der Tabelle kann man auch rotierte bzw. skalierte Versionen der gesuchten Formen finden, was zu einer hohen Robustheit führt. Mittels der Lookup-Tabelle kann man nun das Kantenbild in den Hough-Raum überführen; Maxima stellen die gefundenen Referenzpunkte dar.

Nachteile der Hough-Transformation

Die Hough-Transformation ist eine Art „Brute-Force-Ansatz“ und damit sehr rechenaufwändig.
In ihrer ursprünglichen Form ist die Hough-Transformation daher selbst in einem Parallelrechner z. B. nicht zur Analyse von Videosequenzen in Echtzeit geeignet, wie sie zur Erkennung von Fahrbahnmarkierungen beim autonomen Fahren notwendig ist. Es gibt jedoch eine kaum überschaubare Zahl von Weiterentwicklungen der Hough-Transformation, häufig „Fast Hough Transform“ benannt, die sich dieses Problems annehmen.
Der Speicherbedarf des klassischen Ansatzes ist sehr groß. Auch diese Eigenschaft wurde in diversen wissenschaftlichen Publikationen verbessert.
Bei der Hough-Transformation werden statt der gewünschten Geraden oftmals viele gleichartige Geraden erkannt. Dieses Phänomen liegt im diskreten Bildraum begründet, in dem sich viele mögliche Geraden die gleichen Pixel teilen – was dazu führt, dass sich im Parameterraum keine Häufungspunkte, sondern (im 2D-Fall bei der Erkennung von Geraden) Häufungsplateaus bilden. Ein akzeptables Ergebnis erhält man daher nur, wenn man diese Häufungsplateaus vor der Überführung in eine Geradenliste auf einen Punkt zusammenzieht. Dies kann durch einen lokalen Operator in Fenstertechnik erreicht werden.
Die Hough-Transformation für Geraden liefert, wie ihr Name schon aussagt, Geraden – also unendlich lange Linien ohne Start- und Endpunkt. In einem realen Kantenbild ist die Erkennung von Anfang und Endpunkt einer Kante jedoch meist von entscheidender Bedeutung, es ist also noch eine Nachverarbeitung der Geradenliste erforderlich. Ein möglicher Ansatz ist das sogenannte Tracking: Hierbei wird ein Fenster der Länge $l$ über die erkannte Gerade geschoben und das mittlere Pixel innerhalb dieses Fensters nur dann in die Ergebnismenge aufgenommen, wenn mehr als ${\tfrac {l}{2}}$ Pixel im Kantenbild gesetzt waren.

Software

In freien Software-Bibliotheken zur Bildverarbeitung wie Scikit-image^[3], Dlib^[4] und OpenCV^[5] ist die Hough-Transformation enthalten.

Programmierung

Das folgende Programm in der Programmiersprache C++ zeigt eine Implementierung der Hough-Transformation.^[6]

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>

#define _USE_MATH_DEFINES
#include <math.h>

#define GR(X,Y) (d[(*s)*(Y)+bpp*(X)+((2)%bpp)])
#define GG(X,Y) (d[(*s)*(Y)+bpp*(X)+((1)%bpp)])
#define GB(X,Y) (d[(*s)*(Y)+bpp*(X)+((0)%bpp)])
#define SR(X,Y) (ht[4*tw*((Y)%th)+4*((X)%tw)+2])
#define SG(X,Y) (ht[4*tw*((Y)%th)+4*((X)%tw)+1])
#define SB(X,Y) (ht[4*tw*((Y)%th)+4*((X)%tw)+0])
#define RAD(A)  (M_PI*((double)(A))/180.0)

uint8_t* houghtransform(uint8_t* d, int* w, int* h, int* s, int bpp)
{
	int rho, theta, y, x, W = *w, H = *h;
	int th = sqrt(W * W + H * H) / 2.0;
	int tw = 360;
	uint8_t* ht = (uint8_t*)malloc(th * tw * 4);
	memset(ht, 0, 4 * th * tw);
	for (rho = 0; rho < th; rho++)
	{
		for (theta = 0; theta < tw; theta++)
		{
			double C = cos(RAD(theta));
			double S = sin(RAD(theta));
			uint32_t totalred = 0;
			uint32_t totalgreen = 0;
			uint32_t totalblue = 0;
			uint32_t totalpix = 0;
			if (theta < 45 || (theta > 135 && theta < 225) || theta > 315)
			{
				for (y = 0; y < H; y++)
				{
					double dx = W / 2.0 + (rho - (H / 2.0 - y) * S) / C;
					if (dx < 0 || dx >= W)
					{
						continue;
					}
					x = floor(dx + .5);
					if (x == W)
					{
						continue;
					}
					totalpix++;
					totalred += GR(x, y);
					totalgreen += GG(x, y);
					totalblue += GB(x, y);
				}
			}
			else
			{
				for (x = 0; x < W; x++)
				{
					double dy = H / 2.0 - (rho - (x - W / 2.0) * C) / S;
					if (dy < 0 || dy >= H)
					{
						continue;
					}
					y = floor(dy + .5);
					if (y == H)
					{
						continue;
					}
					totalpix++;
					totalred += GR(x, y);
					totalgreen += GG(x, y);
					totalblue += GB(x, y);
				}
			}
			if (totalpix > 0)
			{
				double dp = totalpix;
				SR(theta, rho) = (int)(totalred / dp) & 0xff;
				SG(theta, rho) = (int)(totalgreen / dp) & 0xff;
				SB(theta, rho) = (int)(totalblue / dp) & 0xff;
			}
		}
	}
	*h = th;
	*w = tw;
	*s = 4 * tw;
	return ht;
}

Literatur

Thomas Bräunl, Stefan Feyrer, Wolfgang Rapf, Michael Reinhardt: Parallele Bildverarbeitung. Addison-Wesley, Bonn 1995, ISBN 3-89319-951-9, S. 99ff.
Rafael C. Gonzales, Richard E. Woods: Digital Image Processing. Prentice Hall, New Jersey 2002, ISBN 0-201-18075-8, S. 587ff.
Bernd Jähne: Digitale Bildverarbeitung. 5. überarbeitete und erweiterte Auflage. Springer, Berlin 2002, ISBN 3-540-41260-3, S. 459ff.

Weblinks

Commons: Hough-Transformation – Sammlung von Bildern, Videos und Audiodateien

Peter E. Hart: How the Hough transform was invented. IEEE Signal Processing Magazine, November 2009, S. 18–22 (PDF; 268 kB).

Einzelnachweise

↑ Patent US3069654A: Method and means for recognizing complex patterns. Angemeldet am 25. März 1960, veröffentlicht am 18. Dezember 1962, Erfinder: Paul V. C. Hough.‌
↑ M. van Ginkel, C. L. Luengo Hendriks, L. J. van Vliet: A short introduction to the Radon and Hough transforms and how they relate to each other
↑ Straight line Hough transform. In: scikit-image – docs. Abgerufen am 12. Dezember 2018 (englisch).
↑ dlib C++ Library - hough_transform_ex.cpp. Abgerufen am 8. Januar 2019.
↑ Hough Circle Transform. In: OpenCV documentation. Abgerufen am 12. Dezember 2018 (englisch).
↑ Rosetta Code: Example:Hough transform/C

[1] Patent US3069654A: Method and means for recognizing complex patterns. Angemeldet am 25. März 1960, veröffentlicht am 18. Dezember 1962, Erfinder: Paul V. C. Hough.‌

[2] M. van Ginkel, C. L. Luengo Hendriks, L. J. van Vliet: A short introduction to the Radon and Hough transforms and how they relate to each other

[3] Straight line Hough transform. In: scikit-image – docs. Abgerufen am 12. Dezember 2018 (englisch).

[4] dlib C++ Library - hough_transform_ex.cpp. Abgerufen am 8. Januar 2019.

[5] Hough Circle Transform. In: OpenCV documentation. Abgerufen am 12. Dezember 2018 (englisch).

[6] Rosetta Code: Example:Hough transform/C

[1]

[2]

[3]

[4]

[5]

[6]