Version [95301]
Dies ist eine alte Version von TutoriumBildverarbeitungMustererkennungSoSe19 erstellt von MoD am 2019-08-13 18:53:43.
- Die Hough-Transformation 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.
- 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
formel
y
formel Geradenerkennung formely
formel-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
formelα
formelund den (euklidischen) Abstand
formeld
formel, wobei
formelα
formelder Winkel zwischen der Normalen der Gerade (= Lot) und der
formelx
formel-Achse ist, und
formeld
formelden Abstand vom Ursprung zum Lotfußpunkt auf der Gerade bezeichnet.
- Damit haben wir die Parametergleichung
formel
d=x·cos(α)+y·sin(α)
formel, mit der wir für alle Punkte auf Kanten im Bild die entsprechende Kurve im Dualraum einzeichnen. Dabei bezeichnen
formelα
formelund
formeld
formeldie Variablen, während
formelx
formelund
formely
formeljetzt zu Parametern umfunktioniert wurden.
formelx
formelund
formely
formelsind die Koordinaten der vorher detektierten Kantenpunkte. Das Ausgangsbild wird zunächst einem Kantendetektor-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
formel
α
formelund
formeld
formelaufgespannt. Zu jedem errechneten Wert
formeld
formelwird jetzt im Dualraum (repräsentiert als Matrix) an der Stelle
formel(α|d)
formelder 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
formel
α
formelmit der gleichen Entfernung
formeld
formel Probabilistische Hough Linien Transformation formelm
formelKantenpunkten aus den eingestellten
formelM
formelKantenpunkten. Die Komplexität der Abstimmungsstufe reduziert sich von
formelO(M.N_θ)
formelauf
formelO(m.N_θ)
formel. Dies funktioniert, weil eine zufällige Teilmenge von
formelM
formeldie Kantenpunkte und das umgebende Rauschen und die Verzerrung weitgehend repräsentiert.
- Ein kleinerer Wert von m führt zu einer schnellen Berechnung bei geringerer Genauigkeit. Daher sollte der Wert von
formel
m
formelin Bezug auf
formelM
formelentsprechend gewählt werden.
- Kiryati et al. führten eine Analyse durch, die auf das Vorhandensein eines Schwelleneffekts für den Wert von
formel
m
formelschloss. Werte von
formelm
formelunterhalb der Schwelle lieferten schlechte Ergebnisse, während Werte oberhalb der Schwelle sehr gute Ergebnisse lieferten. Dieser Schwelleneffekt wurde experimentell bestätigt, wobei gute Ergebnisse erzielt wurden, wobei nur 2% der Kantenpunkte erfasst wurden. Der Wert von
formelm
formel Durchführung formel(m,b)
formel - Im Polarkoordinatensystem: Parameter:
formel
(r,θ)
formel
