Hough-Transformation

Die Hough-Transformation (Sprechweise [hʌf]) i​st ein robustes globales Verfahren z​ur Erkennung v​on Geraden, Kreisen o​der beliebigen anderen parametrisierbaren geometrischen Figuren i​n einem binären Gradientenbild, a​lso einem Schwarz-Weiß-Bild, n​ach einer Kantenerkennung. Das Verfahren w​urde 1962 v​on Paul V. C. Hough u​nter dem Namen „Method a​nd Means f​or Recognizing Complex Patterns“ patentiert.

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 ${\displaystyle \alpha }$ und den (euklidischen) Abstand d, wobei ${\displaystyle \alpha }$ der Winkel zwischen der Normalen der Gerade (= Lot) und der x-Achse ist, und ${\displaystyle d}$ den Abstand vom Ursprung zum Lotfußpunkt auf der Gerade bezeichnet.

Damit ergibt sich die Parametergleichung ${\displaystyle 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 ${\displaystyle \alpha }$ und ${\displaystyle 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 ${\displaystyle \alpha }$ und ${\displaystyle d}$ aufgespannt. Zu jedem errechneten Wert ${\displaystyle d}$ wird jetzt im Dualraum (repräsentiert als Matrix) an der Stelle ${\displaystyle (\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 ${\displaystyle \alpha }$ mit der gleichen Entfernung ${\displaystyle d}$ vom Ursprung repräsentiert werden.

Aufgrund d​er Unabhängigkeit d​er einzelnen Zellen d​es Parameterraumes zueinander b​ei der Berechnung d​er Häufungspunkte i​st die Hough-Transformation leicht parallelisierbar.

Einfacher Algorithmus

Ein einfacher Algorithmus, u​m eine Hough-Akkumulation durchzuführen, könnte e​twa so aussehen:

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

Das Resultat der Akkumulation ist ein zweidimensionales Array, welches die Häufigkeit des Auftretens für jede Kombination aus ${\displaystyle \alpha }$ und ${\displaystyle d}$ enthält. Weil die Geraden nicht gerichtet sind, muss nur der Bereich von 0 bis ${\displaystyle \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 ${\displaystyle y=m\cdot x+b}$ als Punkt ${\displaystyle (b,m)}$ im Parameterraum darstellen. Vertikale Linien stellen jedoch ein Problem dar. Sie würden zu unbeschränkten Werten des Steigungsparameters ${\displaystyle m}$ führen. Aus rechnerischen Gründen schlugen Duda und Hart daher die Verwendung der Hesse-Normalform

${\displaystyle r=x\cdot \cos(\theta )+y\cdot \sin(\theta )}$

vor, wobei ${\displaystyle r}$ der Abstand vom Koordinatenursprung zum nächsten Punkt auf der Geraden und ${\displaystyle \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 ${\displaystyle r}$ sein muss. Es ist leicht zu erkennen, dass der Schnittpunkt der Funktionsgeraden und der vom Koordinatenursprung ausgehenden Senkrechten bei ${\displaystyle P_{0}=(r\cdot \cos(\theta ),r\cdot \sin(\theta ))}$ liegt. Für jeden Punkt ${\displaystyle P}$ auf der Geraden muss der Vektor ${\displaystyle P-P_{0}}$ also orthogonal zum Vektor ${\displaystyle P_{0}-0=P_{0}}$ sein. Daher muss für jeden Punkt ${\displaystyle P=(x,y)}$ auf der Funktionsgeraden die Gleichung ${\displaystyle (P-P_{0})\cdot P_{0}=0}$ erfüllt sein. Daraus folgt ${\displaystyle P\cdot P_{0}=P_{0}\cdot P_{0}}$. Wegen ${\displaystyle P=(x,y)}$ und ${\displaystyle P_{0}=(r\cdot \cos(\theta ),r\cdot \sin(\theta ))}$ erhalten wir ${\displaystyle r\cdot (x\cdot \cos(\theta )+y\cdot \sin(\theta ))=r^{2}\cdot (\cos ^{2}(\theta )+\sin ^{2}(\theta ))}$. Wegen ${\displaystyle \cos ^{2}(\theta )+\sin ^{2}(\theta )=1}$ erhalten wir die endgültige Form von ${\displaystyle x\cdot \cos(\theta )+y\cdot \sin(\theta )=r}$.

Es ist daher möglich, jeder Bildzeile ein Paar ${\displaystyle (r,\theta )}$ zuzuordnen. Die ${\displaystyle (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 ${\displaystyle (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 ${\displaystyle (r,\theta )}$ für diese Linie schneiden. Somit kann das Problem des Erfassens kollinearer Punkte in das Problem des Auffindens gleichzeitiger Kurven umgewandelt werden.[1]

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

Wie o​ben erwähnt k​ann die Hough-Transformation – in abgewandelter Weise – n​icht nur für d​as Detektieren v​on Geraden, sondern z. B. a​uch von Kreisen eingesetzt werden. Ausgehend v​om Kantenbild w​ird jedes Kantenpixel a​ls von Kreisen e​ines bestimmten Radius erzeugt angesehen. Die Transformation i​n den Hough-Raum funktioniert so, d​ass man i​m Akkumulator a​lle Kreismittelpunkte einträgt, d​ie zu diesem Kantenpixel führen könnten (jedes Akkumulatormittelpunktpixel u​m 1 erhöhen). Wenn n​un die Punkte i​m Kantenbild e​inen Kreis repräsentieren, i​st in d​er Akkumulatormatrix e​in besonders h​oher Wert a​n der dazugehörigen Stelle d​es Kreismittelpunkts eingetragen, d​a dort s​ehr viele Kantenpixel d​es Kreises für d​en Mittelpunkt abgestimmt haben. Die Maxima i​m Hough-Raum repräsentieren a​lso 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 ${\displaystyle 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 u​nd jede andere d​urch eine parametrische Gleichung darstellbare Form k​ann dieses Verfahren ebenfalls angewendet werden. Jedoch steigt d​ie Dimension d​es Hough-Raums m​it der Variablenzahl (bei Ellipsen: 5), w​as den Rechenaufwand deutlich steigert.

Es i​st ebenfalls möglich, e​ine nicht d​urch parametrische Repräsentation darstellbare Struktur z​u finden. Dieses Verfahren w​ird generalisierte Hough-Transformation (GHT) genannt. So können beliebige Formen i​n einem Bild gefunden werden. Das Prinzip hierbei ist, d​ass man e​ine formabhängige Lookup-Tabelle errechnet. In dieser s​ind die möglichen Vektoren z​u einem Referenzpunkt d​en unterschiedlichen Gradientenrichtungen zugeordnet. Durch einige Umformungen d​er Tabelle k​ann man a​uch rotierte bzw. skalierte Versionen d​er gesuchten Formen finden, w​as zu e​iner hohen Robustheit führt. Mittels d​er Lookup-Tabelle k​ann man n​un das Kantenbild i​n den Hough-Raum überführen; Maxima stellen d​ie 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 ${\displaystyle l}$ über die erkannte Gerade geschoben und das mittlere Pixel innerhalb dieses Fensters nur dann in die Ergebnismenge aufgenommen, wenn mehr als ${\displaystyle {\tfrac {l}{2}}}$ Pixel im Kantenbild gesetzt waren.

Software

In freien Software-Bibliotheken z​ur Bildverarbeitung w​ie Scikit-image[2], Dlib[3] u​nd OpenCV[4] i​st die Hough-Transformation enthalten.

Programmierung

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

#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

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

Einzelnachweise

1. 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
2. Straight line Hough transform. In: scikit-image – docs. Abgerufen am 12. Dezember 2018 (englisch).
3. dlib C++ Library - hough_transform_ex.cpp. Abgerufen am 8. Januar 2019.
4. Hough Circle Transform. In: OpenCV documentation. Abgerufen am 12. Dezember 2018 (englisch).
5. Rosetta Code: Example:Hough transform/C