schliessen Tags

öffnen Kategorien

Vom WebReader vorlesen lassen

Geradenerkennung in Bildern

27. Jan 2010, 00:52

Es gibt viele Gründe, warum man Geraden in Bildern erkennen möchte, die Hough-Transformation stellt ein robustes Verfahren zur Verfügung. Sie arbeitet auf einem vor verarbeiteten Bild, in dem Kanten segmentiert wurden.
Ich musste dieses Verfahren in der letzten Übungsserie Bildverarbeitung implementieren. Da es recht interessant ist werde ich es jetzt einmal vorstellen.

Als Eingabebild dient im Allgemeinen ein Binärbild, in dem Pixel entweder den Wert "ist Kante" oder "ist keine Kante" haben. Die Aufgabe besteht nun also darin, aus den Punkten die eine Kante repräsentieren, eine Geradengleichung zu bestimmen. Zur Darstellung von Geraden wird häufig eine lineare Funktion der Form y = mx + n verwendet. Diese Gleichung hat ein großes Problem, sie kann keine senkrechten Geraden darstellen, denn eine unendliche Steigung ist mit dem Parameter m nur schwer realisierbar. Aus diesem Grund verwende ich hier die Hessesche Normalform mit den Parametern alpha, als Winkel der Normalen mit der x-Achse, und d, als Länge des Lots vom Koordinaten-Ursprung auf die Gerade.


Die Idee der Hough-Transformation ist nun, dass zwei Punkte, die auf einer Geraden liegen, die selben Parameter zur Erzeugung dieser Geraden benötigen. Hierbei wird brute-force-artig vorgegangen, man bestimmt die Parameter aller möglichen Geraden, die durch einen Kantenpunkt gehen und vergleicht die Parameter mit denen von anderen Kantenpunkten. Im rechten Bild könnte man 4 verschiedene Geraden erkenne. Eine durch die Punkte A, B und C, und jeweils eine von diesen Punkten durch den Punkt C. Diese Punkte sollen auch im weiteren als Beispiel dienen.

Die Parameter lassen sich leicht aus den Koordinaten der kantenrepräsentierenden Pixel herleiten: d = y * sin(alpha) + x * cos(alpha). Setzt man nun alle Mögliche Winkel ein (0 bis 2*Pi bzw. bis 360°) bekommt man den passenden Parameter d für die Gerade durch den aktuellen Pixel heraus. Aus alpha und d lässt sich jetzt also ein Parameterraum aufspannen, in dem die einzelnen Punkte also sinoide Kurven repräsentieren.


Im Bild kann man die 4 möglichen Geraden als Schnittpunkte der Parameterkurven erkennen. Wer nachzählt findet 8 Schnittpunkte, denn jede Gerade kommt in diesem Bild zweimal vor, für jede Richtung einmal. Es reicht also den Parameterraum von 0 bis Pi zu betrachten. Jeder Schnittpunkt im Parameterraum bedeutet also eine Gerade durch 2 oder mehr Punkte im Bildraum, die sich aus den Parametern rekonstruieren lässt.
Zeichnet man nun wirklich für jeden der Schnittpunkte eine Gerade in das Bild wird es schnell unübersichtlich. Da zwei Punkte immer auf einer Geraden liegen würde man also jeden segmentierten Punkt mit jedem anderen verbinden. Daher schwellwertet man den Parameterraum und zeichnet nur Geraden, deren Schnittpunkt aus genügend vielen Geraden entstanden ist. Ein geeigneter Schwellwert für das Beispiel ist vielleicht die 3. Die Gerade durch A, B und C würde also erkannt, die anderen geraden durch jeweils nur 2 Punkte würden verworfen.


Da es hier um Bildverarbeitung und automatisieren usw. geht, muss man natürlich auch den Parameterraum geeignet diskretisieren. Dies geschieht natürlich in einer Matrix. Wie groß man diese bestenfalls wählt, also wie stark man alpha unterteilt, kann ich leider nicht sagen. Ich denke dies hängt stark von der Art der Aufgabe ab. Wählt man eine zu große Auflösung, läuft man Gefahr Geraden zu verlieren die Aufgrund des diskreten Bildes nicht genau im Binärbild segmentiert wurden, ist die Auflösung zu gering, fallen vielleicht verschiedene Geraden zusammen und man hat ausserdem das Problem den richtigen Wert für alpha bzw. d zu wählen. Auch für die Bestimmung des Schwellwertes kann ich kein allgemeines Konzept anbieten, man könnte vielleicht die Anzahl der Geraden beschränken oder aufwändige Wahrscheinlichenkeiten berechnen.
Im Bild rechts habe ich mal für ein Beispiel die Geraden berechnet. Als Schwellwert dienten hier 35 Votes (ein Punkt votet für ein Feld in der Matrix des Parameterraums), alpha ist in 0.1 Schritten diskrtetisiert und d in ganzen Zahlen.

Der nächste Schritt ist nun die Geraden in Segmente zu unterteilen, so dass man die genauen Strecken erhält. Hierfür könnte man in der Matrix des Parameterraums neben den Votes auch speichern welcher Punkt für diese Parameter gevotet hat. Aus den Informationen lässt sich nun Anfangs- und Endpunkt der Strecke herausbekommen.

Tags: Bildverarbeitung Media Software

Kategorien: Media Software

© 2009-2017 by Martin Scharm