Die Hough-Transformation (Sprechweise [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]
]) ist ein robustes globales Verfahren zur Erkennung vonZur 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.
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 und den (euklidischen) Abstand d, wobei der Winkel zwischen der Normalen der Gerade (= Lot) und der x-Achse ist, und den Abstand vom Ursprung zum Lotfußpunkt auf der Gerade bezeichnet.
Damit ergibt sich die Parametergleichung , mit der man für alle Punkte auf Kanten im Bild die entsprechende Kurve im Dualraum einzeichnet. Dabei bezeichnen und 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 und aufgespannt. Zu jedem errechneten Wert wird jetzt im Dualraum (repräsentiert als Matrix) an der Stelle 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 mit der gleichen Entfernung 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.
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][min_dmax_d] := 0 foreach pixel != 0 do for := 0 to do d := pixelx * cos() + pixely * sin() houghRaum[][d]++ end end
Das Resultat der Akkumulation ist ein zweidimensionales Array, welches die Häufigkeit des Auftretens für jede Kombination aus und enthält. Weil die Geraden nicht gerichtet sind, muss nur der Bereich von 0 bis ausgewertet werden, da sich danach die Geraden mit den bereits berechneten decken. In der Praxis wird häufig die Bildmitte als Koordinatenursprung verwendet.
Im Allgemeinen lässt sich die Gerade als Punkt im Parameterraum darstellen. Vertikale Linien stellen jedoch ein Problem dar. Sie würden zu unbeschränkten Werten des Steigungsparameters führen. Aus rechnerischen Gründen schlugen Duda und Hart daher die Verwendung der Hesse-Normalform
vor, wobei der Abstand vom Koordinatenursprung zum nächsten Punkt auf der Geraden und 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 sein muss. Es ist leicht zu erkennen, dass der Schnittpunkt der Funktionsgeraden und der vom Koordinatenursprung ausgehenden Senkrechten bei liegt. Für jeden Punkt auf der Geraden muss der Vektor also orthogonal zum Vektor sein. Daher muss für jeden Punkt auf der Funktionsgeraden die Gleichung erfüllt sein. Daraus folgt . Wegen und erhalten wir . Wegen erhalten wir die endgültige Form von .
Es ist daher möglich, jeder Bildzeile ein Paar zuzuordnen. Die -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 -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 für diese Linie schneiden. Somit kann das Problem des Erfassens kollinearer Punkte in das Problem des Auffindens gleichzeitiger Kurven umgewandelt werden.[2]
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 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.
In freien Software-Bibliotheken zur Bildverarbeitung wie Scikit-image[3], Dlib[4] und OpenCV[5] ist die Hough-Transformation enthalten.
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;
}