Wavelets Ursprung und Entwicklung: - „ondelette“ (frz. kleine Welle, Wellchen); „onde“ (Wave) und „lette“ (let) ins engl.übertragen - Bereits zu Beginn des 20.Jh. schuf Alfred Haar das nach ihm benannte Haar-Wavelet (1909) - in den 80ern Funktionsfamilien von Morlet und Grossmann zur lokalen Frequenzanalyse seismischer Signale zur Auffindung von Erdöl - Stephane Mallat schuf die Voraussetzung und Grundlage der Multiskalen-Analyse - Ingrid Daubechies konstruierte Familien von orthogonalen Wavelet-Basisfunktionen, die eine schnelle Wavelet-Transformation (FWT) ermöglichten (1990) Kurzbeschreibung der WFT (Windowed Fourier Transformation) - die WFT kann nicht gleichzeitig Zeit- und Frequenzraster verändern und analysieren (bei schmalen Zeitfenstern gehen niedrige Frequenzen verloren, bei breiten Fenstern lässt die Empfindlichkeit der Zeit nach) - das Inputsignal (Funktion) wird in Frequenzsektionen aufgeteilt – jede Sektion wird auf ihren Frequenzinhalt separat analysiert - Fenstereinheitsgröße zur Betrachtung von Zeit und Frequenz Fenstergröße bleibt gleich bei veränderten Frequenzen
Transcript
Wavelets
Ursprung und Entwicklung:
- „ondelette“ (frz. kleine Welle, Wellchen); „onde“ (Wave) und „lette“ (let) ins
engl.übertragen - Bereits zu Beginn des 20.Jh. schuf Alfred Haar das nach ihm benannte Haar-Wavelet
(1909) - in den 80ern Funktionsfamilien von Morlet und Grossmann zur lokalen
Frequenzanalyse seismischer Signale zur Auffindung von Erdöl - Stephane Mallat schuf die Voraussetzung und Grundlage der Multiskalen-Analyse - Ingrid Daubechies konstruierte Familien von orthogonalen Wavelet-Basisfunktionen,
die eine schnelle Wavelet-Transformation (FWT) ermöglichten (1990)
Kurzbeschreibung der WFT (Windowed Fourier Transformation)
- die WFT kann nicht gleichzeitig Zeit- und Frequenzraster verändern und analysieren
(bei schmalen Zeitfenstern gehen niedrige Frequenzen verloren, bei breiten Fenstern lässt die Empfindlichkeit der Zeit nach)
- das Inputsignal (Funktion) wird in Frequenzsektionen aufgeteilt – jede Sektion wird auf ihren Frequenzinhalt separat analysiert
- Fenstereinheitsgröße zur Betrachtung von Zeit und Frequenz
Fenstergröße bleibt gleich bei veränderten Frequenzen
periodische Funktion und Grundschwingungen, Fourier
Wavelets
- sowohl für FFT als auch für WT werden Basisfunktionen (FFT : Sinus und Cosinus;
WT : wavelets, Mutter-Wavelets, Analyse-wavelets) genutzt - Basisfunktionen bei FFT sind begrenzt, die der WT hingegen unendlich - Wavelets als Analyse- und Kompressionswerkzeug (z.B.: jpeg2000, bessere
Komprimierungsrate bei gegebener Qualität, zwangloser Übergang von verlustbehafteter zu verlustloser Kompression, Möglichkeit, bestimmten Bildregionen von Interesse in höherer Qualität zu komprimieren und zu dekomprimieren)
Filterfunktionen
- Basisfunktion ist ein sog. Mutter-Wavelet (Beispiele von wikipedia)
fraktale Struktur des Daubechies-Wavelets (amara.com)
Kontinuierliche WT (KWT)
a staucht das Wavelet
b verschiebt es
- die KWT überführt ein Signal f(t) in eine Funktion, die von Stauchung (a) und Zeit (b) abhängt
Diskrete WT
- Wavelets werden mit ganzen Zahlen (meistens dyadisch mit Faktor 2) gestaucht und verschoben
- je länger ein Wavelet ist, desto tiefer ist dessen Frequenz und desto länger ist die Zeitfenstergröße
- die WT analysiert das Eingangssignal in Fenstern und misst die Energie in jedem einzelnen Wavelet und deren Frequenzen
Wie gehts?
- Das Mutter-Wavelet erzeugt durch Stauchen und Strecken Verwandte, die, je nach
Stauchungs- bzw. Streckungsgrad unterschiedliche Frequenzen repräsentieren ( z.B. Stauchen auf die Hälfte des Mutter-Wavelets doppelte Frequenz, Hälfte der Zeit, halbierte Fenstergröße)
- Die Skalierungsfunktion (Vater-Wavelet, um bei der Familie zu bleiben) angewendet auf das Mutterwavelet liefert o.a. Verwandte und also eine Mehrfachauflösung
Multi Resolution Analysis - Um die Koeffizienten der Wavelet-Analyse zu erhalten, wird das Signal mit Mutter-
Wavelet und dessen Kindern und Verwandten gefaltet, was Informationen über die Frequenzen liefert (wie Fourier, Koeffizienten bestimmen die Veränderung der analysierenden Funktion)
recht lange Rechenzeit
schnelle WT
- Zerlegung des Signals in zwei gleich große Teile (1.Teil: grober Verlauf mithilfe der Skalierungsfunktion Hälfte der Auflösung, 2.Teil: Details mithilfe des kleinsten Wavelets)
- Weitere Zerlegungen (und Glättungen) bis nur noch ein Mittelwert (bei jeder „Halbierung“ verringert sich auch die Anzahl der Koeffizienten) übrig bleibt
WT mit dem Haar-Wavelet
Faltung von Signal und unterschiedlichen Waveletskalierungen
- eine vollständige Multi Resolution Analysis ist mit einem Filterpaar vergleichbar (Skalierungsfunktion = Tiefpassfilter, Wavelet = Hochpassfilter)
die Tiefpassfilterkoeffizienten (Gk) erhält man aus den Koeffizienten der Skalierung
die Hochpassfilterkoeffizienten (Hk) erhält man aus den Koeffizienten des Wavelets
- Tiefpass- und Hochpassfilterkoeffizienten arbeiten sowohl als Tiefpass- als auch als Hochpassfilter
Das Hochpassband eines diskreten Signals Si mit H (Hochpassoperator)
Das Tiefpassband eines diskreten Signals Si mit G (Tiefpassoperator)
Mehrere Filterungsschritte (level) unter Anwendung des Pyramiden-Algo
Grundoperationen des Pyramiden-Algorithmus (wikipedia)
• REDUCE wendet ein glättendes Filter an und reduziert die Abtastrate, z.B. indem ein 2D-Pixelbild in 2x2-Blöcke zerlegt wird und aus den Mittelwerten jedes Blocks ein neues Bild zusammengesetzt wird. Es entsteht ein um den Faktor 2 verkleinertes Bild.
• EXPAND ist in gewisser Weise die Umkehroperation zu REDUCE. Die Abtastrate wird erhöht und die auftretenden Lücken werden durch Anwenden eines weiteren Filters sinnvoll gefüllt. In Fortsetzung des Beispiels würde jedem Pixel ein 2x2-Block zugeordnet, welcher konstant mit dem Wert des Pixels gefüllt wird. Es entsteht ein um den Faktor 2 vergrößertes Bild.
• DIFFERENCE berechnet die Differenz zweier (als gleichgroß vorausgesetzter) Pixelbilder.
- Ausgangssignal wird mit 2 Filtern in 2 Teile zerlegt (Tiefpass und Hochpass), die addiert die Gesamtdauer des Ausgangssignals besitzen
Analyse
len y low(yi)
= x(xi) clow (-xi+2*yi)
xi=0 len
yhigh(yi)
= x(xi) chigh (-xi+2*yi)
xi=0
Synthese
Inf
x(xi) = yi=-Inf
c: Filter-Koeffizienten des Hoch- oder Tiefpass-Filters y: Hoch- oder Tiefpass- gefiltertes Signal n: Anzahl der Filter- Koeffizienten in c len: Anzahl Samples in x (Anzahl Samples in y = len/2) x: Ausgangssignal offset: Filter-Offset = n_high/2 (halbe Länge des Hochpass-Filters)
clow(-xi+2*yi) + y high (yi) chigh (-xi+2*yi) y low (yi)
Zweidimensionale DWT mit mehreren Filterungsschritten (Level)
Ausgangsbild
Alle Zeilen gefiltert (links Level-1-Tiefpass, rechts Level-1-Hochpass)
Selbes Verfahren für den verbleibenden Tiefpass- Anteil (links oben: Level-4-Tiefpass)
Kompression
- wenn man Hochpass-Informationen unterschiedlicher Analyseebenen weglässt, wird das Bild unschärfer
- dadurch, dass z.B. Nachbarpixel eines Objekts sich ähneln oder gar gleich sind, sind die Koeffizienten nach der WT Null oder in der Nähe von Null
Original Aus 25% der Gesamt-Information
(ohne die Hochpass-Anteile der ersten beiden Levels)
Aus 12.5% der Information
(ohne Levels 1 bis 3) Aus 6.25% der Information
(ohne Levels 1 bis 4)
Vergleich von Original, JPEG und WT-Kompression
Denoising mit Wavelets (www.amara.com)
- o.a. Dekomponieren des Signals mithilfe von Skalierungs-(Glättungs-) und Waveletfilter (Detailfilter)
- wenn die Abweichungen von Glättungs- und Detailkoeffizienten gering sind (also das geglättete Signal vom Original kaum abweicht), dann könnten letztere ausgelassen werden, ohne wesentliche Auswirkungen auf das Original
- alle unter einem bestimmten Schwellenwert (threshold) liegenden Koeffizienten werden auf Null gesetzt
- wichtige Details (scharfe Konturen, etc) des Signals bleiben erhalten
Fig. 6. "Before" and "after" illustrations of a nuclear magnetic resonance signal. The original signal is at the top, the denoised signal at the bottom. (Images courtesy David Donoho, Stanford University, NMR data courtesy Adrian Maudsley, VA Medical Center, San Francisco).
Fig. 7. Denoising an image of Ingrid Daubechies' left eye. The top left image is the original. At top right is a close-up image of her left eye. At bottom left is a close-up image with noise added. At bottom right is a close-up image, denoised. The photograph of Daubechies was taken at the 1993 AMS winter meetings with a Canon XapShot video still-frame camera. (Courtesy David Donoho)
(C.Roads – CMT)
Wavelet-Resynthese
- wie in der FFT gibt es zwei Möglichkeiten:
1.) überlappend-addierend (man benötigt so viele Oszillatoren, wie es überlappende Wavelets gibt)
2.) addierend (jede Frequenzkomponente bekommt einen eigenen Oszillator zugewiesen)
Manipulation der Resynthese
- filterähnliche Unterdrückung bestimmter Frequenzen (durch das logarithmische
Frequenzraster lassen sich auf einfache Weise leicht Akkorde extrahieren) - durch eine Art von Mischsynthese (Amplitude eines Sounds wird mit der Phase eines
anderen Sounds kombiniert und so ein Zwitter-Sound erzeugt) - Resynthese durch Veränderung des Frequenzgitters (Multiplizieren mit einem anderen
Skalierungsfaktor, Phasenkomponenten müssen mit demselben Faktor multipliziert werden)
- durch time compression/expansion (Veränderung des Zeitgitters, Multiplizieren mit einem anderen Skalierungsfaktor, Phasenkomponenten müssen mit demselben Faktor multipliziert werden)
- ( Phase unwrapping)
weitere Anwendungsbeispiele:
- beat detection - fingerabdrücke FBI - „Neuere Untersuchungen zeigen eine verblüffende Ähnlichkeit zwischen der Wavelet-
Transformation und der biologischen Informationsverarbeitung, die dem menschlichen Hören und Sehen zugrunde liegt“ (thomas fischer-brennpunkt wavelets)
- „In der Astronomie versucht man, mit Hilfe von schnellen Wavelet-Transformationen die hierarchische Ordnung dieser ungeheuren Datenmengen zu entschlüsseln und die einzelnen Cluster und Supercluster automatisch zu katalogisieren“ (thomas fischer-brennpunkt wavelets)
- „Eine weitere, außerordentlich nützliche Eigenschaft von Wavelets ist ihre Fähigkeit, Singularitäten in einem Signal aufzuspüren und ihre Stärke quantitativ zu messen. Man macht sich diese Besonderheit bei der Turbulenzanalyse zunutze, indem man die multifraktalen Eigenschaften turbulenter Strömungen bestimmt und somit versucht, den Energietransport bei voll entwickelter Turbulenz besser zu verstehen und zu modellieren. Wavelet-Cospektren werden verwendet, um Intermittenz zu untersuchen“ (thomas fischer-brennpunkt wavelets)
- „Im Bereich numerischer Simulationen werden Wavelets zur Lösung partieller Differentialgleichungen und zur Generierung adaptiver Netze eingesetzt. Die Vorteile von Wavelets kommen besonders dann zum Tragen, wenn Funktionen approximiert werden sollen, die in ihrem Verlauf oder in dessen Ableitungen Sprünge aufweisen. Daher ist zu erwarten, daß Wavelet-Galerkin-Verfahren bei hyperbolischen Differentialgleichungen oder bei starken Anisotropien interessant werden“ (thomas fischer-brennpunkt wavelets)
Literatur zu Wavelets: http://www.wavelet.org/phpBB2/gallery.php (bücher) http://www-ocean.tamu.edu/~baum/wavelets.html#C1.2 (software) http://www.ibr.cs.tu-bs.de/courses/ss03/skm/ausarbeitungen/wavelets.pdf www.amara.com (einführung und vieles mehr ) http://www.cosy.sbg.ac.at/~uhl/wav.html (rund um wavelets) http://imagemagic.salamandersoftware.co.uk/ (software zur bildkomprimierung) http://lmb.informatik.uni-freiburg.de/lectures/bildverarbeitung/DBV-I_Kap7.pdf http://user.cs.tu-berlin.de/~rammelt/wavelets/index.html http://www.princeton.edu/~icd/publications/74.ps (daubechies-where do wavelets come from) http://www.princeton.edu/~icd/publications/ (weitere dokumente zum thema) http://www.math.wustl.edu/wavelet/ (www-verweise zum thema)
