Version [95308]
Dies ist eine alte Version von TutoriumBildverarbeitungMustererkennungSoSe19 erstellt von MoD am 2019-08-13 19:52:37.
- 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 - Für Hough Transforms werden wir Linien im Polarsystem ausdrücken. Daher kann eine Liniengleichung wie folgt beschrieben werden:
- Im Allgemeinen können wir für jeden Punkt
formel
(x_0,y_0)
formeldie Familie der Linien, die durch diesen Punkt verläuft, festlegen als:
formelr_θ=x_0·cos(θ)+y_0·sin(θ)
formelDas bedeutet, dass jedes Paar
formel(r_θ,θ)
formeljede Zeile repräsentiert, die an
formel(x_0,y_0)
formelvorbeikommt. Wenn wir für einen gegebenen
formel(x_0,y_0)
formeldie Familie der Linien zeichnen, die durch ihn hindurchgeht, erhalten wir ein Sinusoid. Zum Beispiel erhalten wir für
formelx=8
formelund
formely=6
formeldie 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
formelschneiden, 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:
formelx_1=4
formel,
formely_1=9
formelund
formelx_2=12
formel,
formely_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 Einfacher Algorithmus
Resultate HLT und PHLT
max_d := sqrt((bildhöhe)^2 + (bildbreite)^2)
min_d := max_d * -1
houghRaum[0…π][min_d…max_d] := 0
foreach pixel != 0 do
for α := 0 to π do
d := pixelx * cos(α) + pixely * sin(α)
houghRaum[α][d]++
end
end
Kreise und generalisierte Hough-Transformation formel
(x,y)
formel-Koordinaten in beiden Fällen die Lage des Kreismittelpunktes beschreiben. Zusätzlich dazu ist laut der Kreisgleichung
formelx^2+y^2=r^2
formelder Radius
formelr
formelder dritte Parameter, der beachtet werden muss. Man spricht bei Kreisen daher von einem 3-dimensionalen Hough-Raum
formel(xc,yc,r)
formel Resultate HCT
- 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.
Attachments File Last modified Size 1d.jpg 2023-10-06 18:37 69Kb Reverse.jpg 2023-10-06 18:37 131Kb darstellung1.png 2023-10-06 18:37 30Kb dwt_formula.png 2023-10-06 18:37 3Kb grey.jpg 2023-10-06 18:37 59Kb hough1.jpg 2023-10-06 18:37 5Kb hough2.jpg 2023-10-06 18:37 6Kb hough3.jpg 2023-10-06 18:37 8Kb hough_formula1.png 2023-10-06 18:37 7Kb hough_formula2.png 2023-10-06 18:37 3Kb hough_result1.png 2023-10-06 18:37 160Kb hough_result2.png 2023-10-06 18:37 644Kb hough_result2_new.png 2023-10-06 18:37 643Kb hough_result3.png 2023-10-06 18:37 581Kb hough_result3_new.png 2023-10-06 18:37 580Kb hough_result4.png 2023-10-06 18:37 500Kb hough_result4_new.png 2023-10-06 18:37 499Kb hough_result5.png 2023-10-06 18:37 888Kb hough_result5_new.png 2023-10-06 18:37 887Kb level1.jpg 2023-10-06 18:37 41Kb level2.jpg 2023-10-06 18:37 37Kb level3.jpg 2023-10-06 18:37 40Kb nyquist.png 2023-10-06 18:37 153Kb rekonstruktion.png 2023-10-06 18:37 29Kb wavelet_types.jpg 2023-10-06 18:37 108Kb zerlegung.png 2023-10-06 18:37 27Kb
Umgeformt/umgestellt:
Wir berücksichtigen nur Punkte, bei denen
formel.
r>0
formelund
formel0<θ<2π
formel.
Die drei Diagramme schneiden sich in einem einzigen Punkt
formel.
(0.925,9.6)
formel, diese Koordinaten sind die Parameter
formel(θ,r)
formeloder die Linie, auf der
formel(x_0,y_0)
formel,
formel(x_1,y_1)
formelund
formel(x_2,y_2)
formel.
Diese Seite wurde noch nicht kommentiert.
