==formel====formel==

Tutorium Bildverarbeitung/Mustererkennung

Tutor/in:

Jordan Zapf

Ziel des Tutoriums:

Verständnisaufbau von der Hough-Transformation und der Diskreten Wavelet Transformation

Adressaten des Lehrangebotes:

Interessierte Studenten der Fakultät Informatik

Teilnahme:

Wird durch Rundmail bekannt gegeben.

Veranstaltungsinhalte:

Hough-Transformation

• 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==-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

• 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 ==formel==y==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==α==formel== und den (euklidischen) Abstand ==formel==d==formel==, wobei ==formel==α==formel== der Winkel zwischen der Normalen der Gerade (= Lot) und der ==formel==x==formel==-Achse ist, und ==formel==d==formel== den 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==α==formel== und ==formel==d==formel== die Variablen, während ==formel==x==formel== und ==formel==y==formel== jetzt zu Parametern umfunktioniert wurden. ==formel==x==formel== und ==formel==y==formel== sind 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==α==formel== und ==formel==d==formel== aufgespannt. Zu jedem errechneten Wert ==formel==d==formel== wird jetzt im Dualraum (repräsentiert als Matrix) an der Stelle ==formel==(α|d)==formel== 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 ==formel==α==formel== mit der gleichen Entfernung ==formel==d==formel== 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.

Probabilistische Hough Linien Transformation

• Eine der einfachsten probabilistischen Methoden ist die Auswahl von ==formel==m==formel== Kantenpunkten aus den eingestellten ==formel==M==formel== Kantenpunkten. Die Komplexität der Abstimmungsstufe reduziert sich von ==formel==O(M.N_θ)==formel== auf ==formel==O(m.N_θ)==formel==. Dies funktioniert, weil eine zufällige Teilmenge von ==formel==M==formel== die 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==formel== in Bezug auf ==formel==M==formel== entsprechend gewählt werden.
• Kiryati et al. führten eine Analyse durch, die auf das Vorhandensein eines Schwelleneffekts für den Wert von ==formel==m==formel== schloss. Werte von ==formel==m==formel== unterhalb 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 ==formel==m==formel== muss jedoch pro Problem ermittelt werden.

Durchführung

• Kantendetektion z.B. Canny Edge Detector
• Eine Linie kann im Bildraum mit zwei Variablen ausgedrückt werden. Zum Beispiel:
1. Im kartesischen Koordinatensystem: Parameter: ==formel==(m,b)==formel==
2. Im Polarkoordinatensystem: Parameter: ==formel==(r,θ)==formel==
• Für Hough Transforms werden wir Linien im Polarsystem ausdrücken. Daher kann eine Liniengleichung wie folgt beschrieben werden:


Umgeformt/umgestellt:






• Im Allgemeinen können wir für jeden Punkt ==formel==(x_0,y_0)==formel== die Familie der Linien, die durch diesen Punkt verläuft, festlegen als: ==formel==r_θ=x_0·cos(θ)+y_0·sin(θ)==formel== Das bedeutet, dass jedes Paar ==formel==(r_θ,θ)==formel== jede Zeile repräsentiert, die an ==formel==(x_0,y_0)==formel== vorbeikommt. Wenn wir für einen gegebenen ==formel==(x_0,y_0)==formel== die Familie der Linien zeichnen, die durch ihn hindurchgeht, erhalten wir ein Sinusoid. Zum Beispiel erhalten wir für ==formel==x=8==formel== und ==formel==y=6==formel== die folgende Darstellung (in einer Ebene ==formel==θ-r==formel==):

• Wir können die gleiche Operation für alle Punkte in einem Bild durchführen. Wenn sich die Kurven zweier verschiedener Punkte in der Ebene ==formel==θ-r==formel== schneiden, bedeutet das, dass beide Punkte zu einer gleichen Linie gehören. Zum Beispiel, wenn wir dem obigen Beispiel folgen und die Grafik für zwei weitere Punkte zeichnen: ==formel==x_1=4==formel==, ==formel==y_1=9==formel== und ==formel==x_2=12==formel==, ==formel==y_2=3==formel==, erhalten wir:

• Das bedeutet im Allgemeinen, dass eine Linie erkannt werden kann, indem man die Anzahl der Schnittpunkte zwischen den Kurven ermittelt, und je mehr Kurven sich schneiden, desto mehr Punkte hat die durch diesen Schnittpunkt dargestellte Linie. Im Allgemeinen können wir einen Schwellenwert für die minimale Anzahl von Schnittpunkten definieren, die zum Erkennen einer Linie erforderlich sind.
• Das ist es, was die Hough Line Transformation bewirkt. Es verfolgt den Schnittpunkt der Kurven jedes Punktes im Bild. Wenn die Anzahl der Kreuzungen über einem Schwellenwert liegt, wird sie als Linie mit den Parametern ==formel==(θ,r_θ)==formel== des Kreuzungspunktes deklariert.

Einfacher Algorithmus

Resultate HLT und PHLT

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 ==formel==(x,y)==formel==-Koordinaten in beiden Fällen die Lage des Kreismittelpunktes beschreiben. Zusätzlich dazu ist laut der Kreisgleichung ==formel==x^2+y^2=r^2==formel== der Radius ==formel==r==formel== der dritte Parameter, der beachtet werden muss. Man spricht bei Kreisen daher von einem 3-dimensionalen Hough-Raum ==formel==(xc,yc,r)==formel==. 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.

Resultate HCT

Diskrete Wavelet-Transformation

• Als Wavelet-Transformation (WT, englisch wavelet transform) wird eine Familie von linearen Zeit-Frequenz-Transformationen in der Mathematik und den Ingenieurwissenschaften (primär: Nachrichtentechnik, Informatik) bezeichnet. Die WT setzt sich zusammen aus der Wavelet-Analyse, welche den Übergang der Zeitdarstellung in die Spektral- bzw. Waveletdarstellung bezeichnet, und der Wavelet-Synthese, welche die Rücktransformation der Wavelettransformierten in die Zeitdarstellung bezeichnet.
• Der Begriff Wavelet bezeichnet die für die Transformation benutzte Basisfunktion, mit der das zu analysierende Signal oder Bild – im Allgemeinen eine N-dimensionale Funktion – „verglichen“ wird.
• Die Wurzeln der Waveletschule liegen in Frankreich, wo auch der ursprünglich französische Begriff ondelette geprägt wurde, dessen englisches Pendant wavelet sich jedoch später als Bezeichnung durchgesetzt hat. Ins Deutsche übersetzt bedeutet Wavelet so viel wie kleine Welle oder Wellchen und drückt den Umstand aus, dass man im Gegensatz zur Fourier-Transformation zeitlich lokalisierte Wellen bzw. Funktionen als Basis benutzt, wodurch die eingangs erwähnte Zeit- und Frequenzauflösung möglich wird. Wie alle linearen Zeit-Frequenz-Transformationen unterliegt auch die Wavelettransformierte der Unschärferelation der Nachrichtentechnik, d. h. ein Ereignis kann nicht gleichzeitig beliebig genau in Zeit und Frequenz lokalisiert werden. Es gibt immer nur einen Kompromiss aus guter zeitlicher Auflösung oder guter Auflösung im Frequenzbereich.
• Die Wavelet-Transformation unterteilt sich in erster Linie in zwei Lager, nämlich die kontinuierliche Wavelet-Transformation, welche ihre Hauptanwendung in der Mathematik und der Datenanalyse hat, und die diskrete Wavelet-Transformation, welche eher in den Ingenieurswissenschaften zu finden ist und deren Anwendung im Bereich der Datenreduktion, Datenkompression und Signalverarbeitung liegt.
• Die Diskrete Wavelet-Transformation oder DWT ist eine Wavelet-Transformation, die zeit- und frequenzdiskret durchgeführt wird.
• Die Wavelet-Analyse kann verwendet werden, um die Informationen eines Bildes in Approximations- und Detail-Subsignal zu unterteilen.
• Das Approximations-Subsignal zeigt den allgemeinen Trend der Pixelwerte und drei Detail-Subsignale auf den horizontalen, vertikalen und diagonalen Details.
• Wenn diese Details klein sind, können sie auf Null gesetzt werden, ohne dass sich das Bild wesentlich verändert. Dadurch können Filterung und Kompression erreicht werden.

Wavelets

Zerlegung 2D DWT

Darstellung

Rekonstruktion 2D DWT

Nyquist-Shannon-Abtasttheorem

• Das von Shannon formulierte Abtasttheorem besagt, dass eine Funktion, die keine Frequenzen höher als ==formel==f_{max}==formel== enthält, durch eine beliebige Reihe von Funktionswerten im Abstand ==formel==τ<{1 \above 1pt 2f_{max}}==formel== eindeutig bestimmt ist. Eine hinreichende Bedingung dafür ist die Quadratintegrierbarkeit der Funktion.
• Der Funktionsverlauf kann dann rekonstruiert werden, indem jeder Abtastwert ==formel==x̂(kτ)==formel== durch eine sinc-Funktion ==formel==si(2πf_{max}(t-kτ))·x̂(kτ)==formel== mit gleicher Amplitude ersetzt und anschließend über alle ==formel==k==formel== aufsummiert wird.
• In der Signalverarbeitung entspricht dies der Abtastung mit einer Abtastrate ==formel==f_{abtast}>2f_{max}==formel==. Die so erhaltene Signaldarstellung wird Pulsamplitudenmodulation genannt. Zur Rekonstruktion wird dieses Signal durch einen idealen Tiefpass mit Grenzfrequenz ==formel==f_{max}==formel== gefiltert.
• Bei Nicht-Basisband-Signalen, d. h. solchen mit minimaler Frequenz ==formel==f_{min}==formel== größer als 0 Hz, gilt das Abtasttheorem in ähnlicher Form, da durch geeignete Wahl der Abtastfrequenz, das Bandpasssignal im Basisband nach der Abtastung erscheint. Die Abtastfrequenz muss dann lediglich größer als die doppelte Bandbreite sein (siehe auch Unterabtastung). Bei der Rekonstruktion wird hier statt eines idealen Tiefpasses ein idealer Bandpass verwendet.
• Bei der Unterabtastung eines Bandpasssignals gilt:

• In der Praxis wird ein Signal vor der Abtastung meist tiefpassgefiltert, damit die (Basis-)Bandbreite der Abtastrate genügt. Analog gilt das Abtasttheorem auch bei Bildern und Videos, wobei die Abtastfrequenz dann in Linien (bzw. Pixel) pro Längeneinheit bestimmt werden kann.

Ausgangsbild

Resultat 1D DWT mit DS

Resultat Level 1

Resultat Level 2

Resultat Level 3

Resultat Rekonstruktion

Quellen

https://de.wikipedia.org/wiki/Hough-Transformation
https://docs.opencv.org/2.4/doc/tutorials/imgproc/imgtrans/hough_lines/hough_lines.html
https://de.wikipedia.org/wiki/Wavelet-Transformation#Diskrete_Wavelet-Transformation
https://de.wikipedia.org/wiki/Nyquist-Shannon-Abtasttheorem

---

CategoryTutorienFKITWS1819;CategoryTutorienFKITSS18