Simple Wavelet-Einführung



  • Hallo.

    Ich arbeite gerade mit einem neuen Codec, der für eine Phase im kodieren Hoch und Tiefpassfilter mithilfe einer Haar-Wavelet Transformation benutzt.

    Mit Wavelets (und auch FFT, etc.) habe ich mich allerdings noch nie auseinandergesetzt, und Unterlagen die ich dazu im Netz finden konnte sind für mich ein wenig zu mathematisch.

    Gibt es eventuell informellere/nicht auf die Mathematik konzentrierte Einführungen über Wavelet-Transformationen, und wie man diese anwendet um damit z.B. Bandpassfilter aufzustellen?



  • Notiz: Mir ist klar, dass Mathematik für Wavelets von großer Wichtigkeit sind, aber bei mir ist das gerade eine Frage der Zeit. Daher wäre eine kurze Einführung über die Funktionsweise und Beispiele wie man sie anwendet optimal.



  • Im Wesentlichen geht es darum, ein Signal als gewichtete Überlagerung von anderen Signalen darzustellen. Im Falle von Wavelets sind das eben kleine Wellchen, die in der Zeit (bzw im Ort) als auch im Frequenzbereich (bzw Wellenzahlbereich) einigermaßen lokalisiert sind.

    Das mit den Wavelets kann man als "Filterbank" begreifen. Man kann z.b. aus einem Signal mit Abtastrate 2f zwei Signale mit je Abtastrate f zaubern, wobei in dem einen der untere Frequenzanteil drin steckt und im abderen der obere Frequenzanteil. Das Haar-Wavelet ist in diesem Sinne aber ein recht schlechter Bandbassfilter.

    Worum -- also außer Literaturtipps, die ich leider nicht geben kann -- geht es dir eigentlich? Was hast du vor?



  • Einen decoder schreiben, d.h. die Wavelet-Transformation rückgängig zu machen.



  • Wenn das Problem nicht nur die Wavelets sind, sondern sogar schon die Fouriertransformationen, wie Du es andeutest, dann wird das vermutlich nicht in sehr kurzer Zeit ohne Mathematik erlernbar sein.

    Ich versuche es mal grob zu skizzieren:

    Im Prinzip geht es darum, Funktionen darzustellen. Als Ausgangspunkt hast Du ein Signal, oder meinetwegen eine Funktion f(t), die von der Zeit t abhaengt. Du hast diese Funktion praktisch als Wertetabelle gegeben. Bei der Fouriertransformation hast Du jetzt aber kein Interesse am Zeitverhalten der Funktion, sondern an ihrem Frequenzverhalten. Deshalb stellst Du die Funktion als Linearkombination von anderen Funktionan dar, die jeweils zu einer ganz bestimmten Frequenz gehoeren. Das ist eine Fouriertransformation. Ueber den Koeffizienten vor jeder dieser Funktionen erkennst Du dann, wie viel von der jeweiligen Frequenz in Deiner Funktion f(t) enthalten ist.

    Bei einer Fouriertransformation siehst Du allerdings das Zeitverhalten der Funktion nicht mehr so explizit, wie wenn Du sie als f(t) gegeben hast. Du hast nur globale Informationen ueber die Frequenzen, die in der Funktion vorhanden sind. Du kannst diese Frequenzen nicht bestimmten Zeitintervallen zuordnen. Hier setzt man jetzt mit den Wavelets ein. Das ist so etwas aehnliches wie lauter kleine Fouriertransformationen ueber kleine Zeitintervalle. Wobei man beim Wavelet noch einen Schritt weiter geht. Man macht die Breite der Zeitintervalle von den Frequenzen abhaengig, die man darin erkennen moechte. Letztendlich entwickelt man seine Funktion f(t) dann bezueglich Produktion von Funktionen, die die Frequenz repraesentieren mit frequenzabhaengigen Funktionen, die eine Fensterbreite repraesentieren. Also Zum Beispiel mit einem Produkt aus Sinus-/Cosinusfunktionen und Gaussfunktionen.

    Mit anderen Worten: Mit einem Wavelet kommst Du an zeitaufgeloeste Informationen ueber die Frequenzen Deiner Funktion heran. Dadurch kannst Du dann natuerlich auch bestimmte Frequenzen unterdruecken. Und damit landest Du dann bei einem Bandpassfilter.

    ...bei dem Text oben habe ich uebrigens nicht an Haar-Wavelets, sondern an Gabor-Wavelets gedacht.



  • PS: Falls Du doch eine ausfuehrlichere Einfuehrung suchst, kann ich Dir das Buch da empfehlen:
    A Wavelet Tour of Signal Processing: The Sparse Way | ISBN: 0123743702



  • Ich habe hier zwei Links mit Einführungen zu Wavelets, die mit eher wenig Mathematik auskommen:

    http://www.multires.caltech.edu/teaching/courses/waveletcourse/athome.pdf

    http://cse-lab.ethz.ch/images/teaching/mmc2011/wavelet_primer.pdf



  • waveletter schrieb:

    Einen decoder schreiben, d.h. die Wavelet-Transformation rückgängig zu machen.

    Einen Dekoder für was?
    Und wo hakt es?

    Bei Verfahren wie beispielsweise JPEG2000 ist der Wavelet-Kram typischerweise per "Lifting" implementiert. Das lässt sich recht einfach invertieren: Einfach alle Operationen in umgekehrter Reihenfolge invertieren.



  • nevermore schrieb:

    Ich habe hier zwei Links mit Einführungen zu Wavelets, die mit eher wenig Mathematik auskommen:

    http://www.multires.caltech.edu/teaching/courses/waveletcourse/athome.pdf

    http://cse-lab.ethz.ch/images/teaching/mmc2011/wavelet_primer.pdf

    Danke, die waren ziemlich genau das was ich gesucht habe.

    krümelkacker schrieb:

    waveletter schrieb:

    Einen decoder schreiben, d.h. die Wavelet-Transformation rückgängig zu machen.

    Einen Dekoder für was?
    Und wo hakt es?

    Dekoder für einen neuen Codec, den das Team mit dem ich gerade zusammenarbeite entwickelt hat.

    Es hakt noch an gar nix. Es ist nur meine erste Arbeitswoche, und ich bin damit beauftragt mich in den Codec einzulesen. Das beinhaltet diverse Themen, u.a. Wavelets.

    Ich hätte noch eine Frage zur Kompression: In einem der beiden Paper wurde für Kompression mittels Wavelet-Transformation folgendes Vorgeschlagen:

    1. Ausrechnen aller Koeffizienten eines Bildes
    2. Sortieren der Koeffizienten nach absteigender Größe
    3. So viele der hinteren Koeffizienten weglassen, dass einem die Bildqualität noch reicht.

    Dazu ein paar Fragen:

    1. Eine komplette Haar-Wavelet-Transformation wird in den beiden Artikeln so dargestellt, dass man in einem Signal so lange paarweise Durchschnitte und Differenzen bildet, bis man am Ende eine Form hat, in dem man nur noch "einen Durchschnitt" gefolgt von n-1 Differenzen hat. Macht man das in der Praxis so? Hört sich an, als könnte man nach "1 mal durchgehen" schon ordentlich was abschneiden.

    2. Wenn man einfach Koeffizienten weglässt, weiss man ja am Ende nicht mehr, wie viele Koeffizienten der Datensatz am Anfang umfing, und da man sie vor dem wegschneiden umsortiert, auch nicht mehr wo sie eigentlich hingehören. Hört sich für mich an, als müsste man zusätzlich die ursprünglichen Stellen der Koeffizienten mit abspeichern, was die Kompressionstechnik etwas merkwürdig erscheinen lässt, da man am Ende wohl mehr Speicher verbraucht als vor der Kompression. Was verstehe ich hier falsch?



  • waveletter schrieb:

    1. Eine komplette Haar-Wavelet-Transformation wird in den beiden Artikeln so dargestellt, dass man in einem Signal so lange paarweise Durchschnitte und Differenzen bildet, bis man am Ende eine Form hat, in dem man nur noch "einen Durchschnitt" gefolgt von n-1 Differenzen hat. Macht man das in der Praxis so? Hört sich an, als könnte man nach "1 mal durchgehen" schon ordentlich was abschneiden.

    Ich bin mir nicht ganz sicher, ob ich dich richtig verstanden habe, aber nach einem Schritt aufhören geht nicht. Es kann ja sein, dass dein Signal nur aus hohen Frequenzen besteht. Dann sind alle deine Differenzen klein, bis auf vielleicht eine Differenz die eben deine hohe Frequenz repräsentiert. Das kannst du aber erst wissen, wenn du alle Differenzen berechnet hast.

    waveletter schrieb:

    2. Wenn man einfach Koeffizienten weglässt, weiss man ja am Ende nicht mehr, wie viele Koeffizienten der Datensatz am Anfang umfing, und da man sie vor dem wegschneiden umsortiert, auch nicht mehr wo sie eigentlich hingehören. Hört sich für mich an, als müsste man zusätzlich die ursprünglichen Stellen der Koeffizienten mit abspeichern, was die Kompressionstechnik etwas merkwürdig erscheinen lässt, da man am Ende wohl mehr Speicher verbraucht als vor der Kompression. Was verstehe ich hier falsch?

    Im einfachsten Fall speicherst du Indizes und Koeffizienten ab. Wenn du dafür viele Koeffizienten wegschmeissen kannst, lohnt sich das schon. Es gibt bestimmt auch intelligentere Verfahren, dein Signal nach der Transformation zu kodieren.

    Hier ist eine sehr simple, anschauliche Implementierung einer Bildkompression mit Wavelets, die dir vielleicht hilft: http://cse-lab.ethz.ch/images/teaching/mmc2011/wavelet_solutioncode.zip


Log in to reply