Welche Zeit-Frequenz-Koeffizienten berechnet die Wavelet-Transformation?

26

Die schnelle Fourier - Transformation nimmt Operationen, während die schnelle Wavelet - Transformation nimmt . Aber was genau berechnet die FWT?O ( N )O(NlogN)O(N)

Obwohl sie oft verglichen werden, scheinen FFT und FWT Äpfel und Orangen zu sein. Soweit ich weiß, ist es sinnvoller, die STFT (FFTs von kleinen Brocken über die Zeit) mit der komplexen Morlet-WT zu vergleichen , da es sich um Zeit-Frequenz-Darstellungen handelt, die auf komplexen Sinuskurven basieren (bitte korrigieren Sie mich, wenn ich mich irre.) ). Dies wird häufig mit einem Diagramm wie dem folgenden gezeigt:

Gitter zeigen, wie die Koeffizienten der FFT und der WT der Zeit-Frequenz-Ebene entsprechen

( Ein weiteres Beispiel )

Die linke Abbildung zeigt, wie die STFT eine Reihe von FFTs ist , die im Laufe der Zeit übereinander gestapelt sind (diese Darstellung ist der Ursprung des Spektrogramms ), während die rechte Abbildung die dyadische WT zeigt, die bei hohen Frequenzen eine bessere Zeitauflösung und eine bessere Frequenz aufweist Auflösung bei niedrigen Frequenzen (diese Darstellung wird Skalogramm genannt ). In diesem Beispiel ist für die STFT die Anzahl der vertikalen Spalten (6), und eine einzelne -FFT-Operation berechnet eine einzelne Reihe von Koeffizienten aus Abtastwerten. Die Gesamtsumme beträgt 8 FFTs mit jeweils 6 Punkten oder 48 Abtastungen im Zeitbereich.O ( N log N ) N NNO(NlogN)NN

Was ich nicht verstehe:

  • Wie viele Koeffizienten berechnet eine einzelne FWT-Operation und wo befinden sie sich in der obigen Zeit-Frequenz-Tabelle? O(N)

  • Welche Rechtecke werden durch eine einzelne Berechnung ausgefüllt?

  • Wenn wir mit beiden einen flächengleichen Block von Zeit-Frequenz-Koeffizienten berechnen, erhalten wir dann die gleiche Datenmenge?

  • Ist die FWT noch effizienter als die FFT?

Konkretes Beispiel mit PyWavelets :

In [2]: dwt([1, 0, 0, 0, 0, 0, 0, 0], 'haar')
Out[2]:
(array([ 0.70710678,  0.        ,  0.        ,  0.        ]),
 array([ 0.70710678,  0.        ,  0.        ,  0.        ]))

Es werden zwei Sätze mit 4 Koeffizienten erstellt, sodass dies der Anzahl der Abtastwerte im Originalsignal entspricht. Aber in welcher Beziehung stehen diese 8 Koeffizienten zu den Kacheln im Diagramm?

Aktualisieren:

Eigentlich habe ich das wahrscheinlich falsch gemacht und sollte verwenden wavedec(), was eine mehrstufige DWT-Zerlegung bewirkt:

In [4]: wavedec([1, 0, 0, 0, 0, 0, 0, 0], 'haar')
Out[4]: 
[array([ 0.35355339]),
 array([ 0.35355339]),
 array([ 0.5,  0. ]),
 array([ 0.70710678,  0.        ,  0.        ,  0.        ])]
Endolith
quelle
2
Um besser zu verstehen, wie diese Zerlegung von Wavelets funktioniert, wäre es ein nützliches Werkzeug, in der Lage zu sein, dies mit realen Signalen zu tun: zum Beispiel Audiosignalen (ich habe hier eine Frage in diese Richtung. Dsp.stackexchange.com/ questions / 12694 / stft-and-dwt-
wavets
@endolith Haben Sie noch Fragen? Wenn ja, kann ich andere Hinweise hinzufügen
Laurent Duval
@LaurentDuval Ja, es ist immer noch offen und ich verstehe es immer noch nicht. Ich kann verwirrt sein, weil CWT Dinge wie Morlet verwendet und DWT nur Dinge wie Haar oder Daubechies verwendet. Ich bin mir nicht sicher, ob die schnelle FWT nur Haar ist oder auch andere Arten von Wavelets verwenden kann.
Endolith
2
@ndolith Nur ein Kommentar zu diesem: Die kontinuierliche CWT lässt eine unglaubliche Menge möglicher Wavelet-Formen zu. Sie können nur dann genau diskretisiert werden, wenn Stichprobenmuster (in Bezug auf Zeit oder Maßstab) eine gewisse "Heisenberg" -Ungleichung berücksichtigen. Diese Muster hängen vom Wavelet ab. In den meisten Fällen machen die Muster eine diskretisierte CWT überflüssig. Einige wollen es nicht redundant, mit einer dyadischen Skala. Das erlauben nur sehr wenige Wavelets. Wenn Sie dann die Wavelet-Unterstützung als endlich auferlegen, dann ist Haar eine, fast unmöglich zu erhaltende, natürliche Wavelet, weshalb die von Daubechies gebaut wurden
Laurent Duval

Antworten:

13

Sie haben Recht, dass die FWT eher als "Cousin" der STFT denn als die FT angesehen wird. Tatsächlich ist die FWT nur eine diskrete Abtastung der CWT (kontinuierliche Wavelet-Transformation), da die FFT / DFT eine diskrete Abtastung der Fourier-Transformation ist. Dies mag wie ein subtiler Punkt erscheinen, ist jedoch relevant, wenn Sie festlegen, wie Sie die Transformation diskretisieren möchten.

Die CWT und die STFT sind beide redundante Analysen eines Signals. Mit anderen Worten, Sie haben mehr "Koeffizienten" (im diskreten Fall), als Sie zur vollständigen Darstellung eines Signals benötigen. Eine Fourier-Transformation (oder sagen wir eine Wavelet-Transformation mit nur einer Skala) integriert jedoch ein Signal von -unendlich bis + unendlich. Dies ist für Signale der realen Welt nicht sehr nützlich, daher kürzen wir die Transformationen (dh das Fenster) auf kürzere Längen. Das Fenstern eines Signals verändert die Transformation - Sie multiplizieren mit dem Fenster in Zeit / Raum, so dass Sie im Transformationsraum die Faltung der Transformation des Fensters mit der Transformation des Signals haben.

Im Fall der STFT haben die Fenster (normalerweise) zu jeder Zeit die gleiche Länge (Ausdehnung ungleich Null) und sind frequenzunabhängig (Sie fenster ein 10-Hz-Signal mit der gleichen Breite wie ein 10-kHz-Signal). So erhalten Sie das rechteckige Gitterspektrogramm, wie Sie es gezeichnet haben.

Die CWT hat dieses Fenster eingebaut durch die Tatsache, dass die Wavelets kürzer werden (zeitlich oder räumlich), wenn der Maßstab abnimmt (wie bei höheren Frequenzen). Für höhere Frequenzen ist das effektive Fenster daher kürzer und Sie erhalten ein Skalogramm, das so aussieht, wie Sie es für die FWT gezeichnet haben.

Wie Sie das CWT diskretisieren, liegt etwas bei Ihnen, obwohl ich denke, dass es minimale Abtastwerte sowohl in der Verschiebung als auch in der Skala gibt, um ein Signal vollständig darzustellen. In der Regel (zumindest wie ich sie verwendet habe) werden Sie für die niedrigste Skala (höchste Frequenz) an allen Schichtpositionen (Zeit / Raum) Samples erstellen. Je höher die Skalierung ist (je niedriger die Frequenz), desto seltener können Sie Samples erstellen. Das Grundprinzip ist, dass sich niedrige Frequenzen nicht so schnell ändern (denken Sie an einen Beckencrash im Vergleich zu einer Bassgitarre - der Beckencrash hat sehr kurze Einschwingzeiten, während der Wechsel der Bassgitarre länger dauern würde). Tatsächlich haben Sie auf der kürzesten Skala (sofern Sie an allen Schichtpositionen abtasten) die vollständige Darstellung eines Signals (Sie können es nur mit den Koeffizienten auf dieser Skala rekonstruieren). Ich bin mir nicht so sicher, warum ich die Skala abtasten soll. ICH' Ich habe dies als logarithmisch empfunden, mit (glaube ich) engerem Abstand zwischen kürzeren Skalen. Ich denke, das liegt daran, dass die Wavelets in längeren Maßstäben eine breitere Fourier-Transformation haben (daher "nehmen" sie mehr Frequenzen auf).

Ich gebe zu, dass ich die FWT nicht vollständig verstehe. Meine Vermutung ist, dass es sich tatsächlich um die minimale Stichprobe in Schicht / Maßstab handelt und keine redundante Darstellung ist. Aber dann glaube ich, dass Sie die Fähigkeit verlieren, ein Signal in kurzer Zeit zu analysieren (und damit herumzuspielen), ohne unerwünschte Artefakte einzuführen. Ich werde mehr darüber lesen und, wenn ich etwas Nützliches erfahre, berichten. Hoffentlich werden andere gerne kommentieren.

Patrick
quelle
1
"es ist eigentlich die minimale Abtastung in Verschiebung / Skala und ist keine redundante Darstellung." Ah! Ich denke, Sie haben Recht, und dies würde erklären, warum es immer mit der FFT verglichen wird, die auch eine minimale Darstellung ist.
Endolith
3
Die FWT ist eine kritische Stichprobe der CWT. Ich versuche immer noch, es besser zu verstehen, aber ich habe gelernt, dass STFT und CWT beide Frames sind. Die Rahmentheorie geht über mich hinaus, aber ein interessanter Begriff ist die Unsicherheitsformel, dass für die STFT dw * dt> C ist (dw ist die Frequenzauflösung und dt ist die Zeitauflösung). Mit anderen Worten, wenn Sie versuchen, die Frequenz besser aufzulösen, verlieren Sie die Zeitauflösung. Das CWT hat diese Einschränkung nicht. Ich werde weiterlesen und versuchen, meine obige Antwort zu klären, sobald ich sie in meinem Kopf klargestellt habe.
1
Soweit ich weiß, hat CWT die gleiche Einschränkung, nutzt jedoch einen besseren Kompromiss.
Endolith
1
"STFT sind beide redundante Analysen eines Signals". Ich glaube nicht, dass das stimmt. Wenn Sie ein 100-Punkte-Signal haben, teilen Sie es in 10-Punkte-Blöcke auf und führen Sie jeweils eine 10-Punkte-FFT durch. Sie haben immer noch die gleichen Informationen in der gleichen Anzahl von Samples gespeichert.
Endolith
11

Betrachten Sie den Haar-Wavelet-Fall. Die schnelle Wavelet-Transformation unterteilt Ihr Signal rekursiv und berechnet jedes Mal die Summe und Differenz der beiden Hälften. Die Differenz ist die Größe der Transformation für das aktuelle Wavelet und die Summe wird für den Aufrufer zurückgegeben, um die Größe der Transformation für ein dilatiertes Wavelet mit der halben Frequenz zu berechnen. Somit deckt die FWT die Zeit-Frequenz-Ebene mit dem in dem von Ihnen angegebenen Diagramm beschriebenen Muster ab.

Beachten Sie, dass das von Ihnen angegebene Diagramm etwas irreführend ist. Was sie Ihnen wirklich sagen wollen, ist, dass Sie einen Abtastwert mit der niedrigsten Frequenz, zwei Abtastwerte mit der doppelten Frequenz, vier Abtastwerte mit der vierfachen Frequenz und so weiter erhalten. Die Zeit-Frequenz-Eigenschaften jedes Wavelets sind nicht so, dass sie die Kachel bedecken. In der Praxis wird jedes Wavelet einen unendlichen Bereich abdecken, da es eine kompakte Unterstützung hat und daher hinsichtlich der Frequenz vollständig delokalisiert werden muss. Denken Sie also nur an die Zentren dieser Fliesen.

Darüber hinaus erfordert die FWT ein diskretes Wavelet, das sich an ein weitaus restriktiveres Zulässigkeitskriterium halten muss als kontinuierliche Wavelets für die CWT. Folglich sind die Zeit-Frequenz-Eigenschaften diskreter Wavelets im Allgemeinen schrecklich (z. B. sind die Daubechies-Wavelets entweder voll von scharfen Merkmalen oder haben sich ändernde Frequenzen), und die Nützlichkeit der Zeit-Frequenz-Ebene ist im Kontext der FWT stark verringert. Kontinuierliche Wavelets werden jedoch verwendet, um Zeit-Frequenz-Darstellungen von Signalen zu berechnen.


quelle
Ja, ich verstehe die Lokalisierung der Koeffizienten. Das ist das gleiche wie bei der FFT. Wenn Sie sagen "muss einhalten", was meinen Sie damit? Ist es nur eine Voraussetzung, wenn Sie versuchen, eine minimale / nicht redundante Darstellung des Signals zu erhalten? Was ist, wenn Sie nur versuchen, es zu analysieren / zu visualisieren? Ich werde der Frage ein konkreteres Beispiel hinzufügen.
Endolith
1
Die Einhaltung des Zulässigkeitskriteriums stellt sicher, dass eine Auflösung der Identität vorliegt, dh dass alle Signale aus ihren Wavelet-Transformationen wiederhergestellt werden können. Wenn Sie sich nicht daran halten, können Sie ein Signal nicht von seiner Transformation wiederherstellen. An diesem Punkt müssen Sie sich fragen, was genau Sie analysieren (gibt es überhaupt Informationen wieder, die sich im Signal befanden ?!). Wenn Sie keine minimale / nicht redundante Darstellung benötigen, können Sie das Kriterium der laxen Zulässigkeit aus der CWT verwenden (mit dem Sie mehr "ideale" Wavelets definieren können).
1
Ich denke, Sie würden meine Doktorarbeit wirklich nützlich finden. Ich werde es für Sie online stellen ...
Hast du es online gestellt? :)
Endolith
2
Ich habe es wirklich
3

Ihre Referenz hat es:

Eine Folge von Koeffizienten, die auf einer orthogonalen Basis kleiner endlicher Wellen oder Wavelets basieren.

Für mehr mögen Sie vielleicht die DWT-Seite . Dort werden Haar Wavelets, Daubechies Wavelets und andere vorgestellt. Es zeigt auf, wie

  • Wavelets haben Position - das (1,1, –1, –1) Wavelet entspricht der „linken Seite“ gegenüber der „rechten Seite“, während die letzten beiden Wavelets Unterstützung auf der linken Seite oder der rechten Seite haben und eines eine Übersetzung ist des anderen.
  • Sinuswellen haben keinen Ort - sie breiten sich über den gesamten Raum aus - haben jedoch eine Phase - die zweite und die dritte Welle sind Translationen voneinander, die 90 ° phasenverschoben sind, wie Cosinus und Sinus, von denen es sich um diskrete Versionen handelt .

Wenn Sie statt diskreter Wavelets nun kontinuierliche Wavelets oder komplexe Wavelets verwenden möchten, beginnen Sie möglicherweise mit Wavelet-Reihen .

Jenseits von Wikipedia könnten ein Lehrbuch und ein Kurs für Sie von Vorteil sein.


quelle
Ich verstehe diese Antwort nicht. Beantwortet es meine Fragen? Linke und rechte Seite von was? Was hat das mit der Zeit-Frequenz-Darstellung zu tun?
Endolith
Die Beschreibung "linke Seite versus rechte Seite" ist eine auszugsweise Vorschau der DWT-Seite, die zeigt, dass diese Seite ein einfaches Beispiel enthält, um die relativen Vorzüge der Sinusbasis und der Haar-Wavelets-Basis zu erläutern. Sie haben nach der Art der Koeffizienten in einer Wavelet-Transformation gefragt. Es klang, als suchten Sie nach Intuition. Ich dachte, Sie könnten dieses Beispiel (in seinem ursprünglichen Kontext) nützlich finden.
Ja, ich habe die Wikipedia-Artikel mehrmals gelesen, bevor ich diese Frage gestellt habe. Ich weiß nicht, ob / was Ihre Antwort mit meiner Frage nach der Zeit-Frequenz-Darstellung zu tun hat. Wenn ja, könnten Sie die Punkte verbinden? Eine FFT von n Abtastwerten erzeugt n Koeffizienten, die eine einzelne Spalte des STFT-Spektrogramms bilden. Gibt es eine entsprechende Beziehung zwischen den vom WT erzeugten Koeffizienten und dem Skalogramm? Wenn ja, was ist das? Welche der Felder in der unteren rechten Tabelle werden bei einem einzelnen Lauf durch die FWT ausgefüllt?
Endolith
1
Fast alles auf den Wikipedia-Seiten, was mit Wavelets zu tun hat, ist derzeit falsch.
3

O(N2)

O(N)O(Nlog(N))O()

Beginnen Sie mit der generischen Fenster-STFT (Endlosformular). Wenn Sie ein unendliches Fenster mit Einheitshöhe einstecken, stellen Sie die Fourier-Transformation als Sonderfall wieder her. Was Sie diskretisieren können (und die DFT bekommen) und es schnell machen können (und die FFT bekommen).

Beginnen Sie mit einem CWT (Endlosformular). Die kontinuierliche CWT lässt eine unglaubliche Menge möglicher Wavelet-Formen zu. Sie können nur mit Stichprobenmustern (nach Zeit oder Maßstab) diskretisiert werden, die eine gewisse "Heisenberg" -Ungleichung berücksichtigen: eine Stichprobe pro Flächeneinheit. Diese Muster hängen vom Wavelet ab. In den meisten Fällen machen die Muster eine diskretisierte CWT überflüssig und ergeben einen Wavelet-Frame.

Einige wollten es nicht redundant, mit einer dyadischen Skala (DWT). Nur sehr wenige Wavelets (immer noch eine unendliche Zahl, aber Sie können sie nicht zufällig finden) lassen dies zu. Unter den ersten waren die Haar-, Franklin- und Meyer-Wavelets. Wenn Sie dann die Wavelet-Unterstützung als endlich festlegen, war Haar lange Zeit die einzige. Es ist fast unmöglich, ein orthogonales Wavelet aus "natürlichen kontinuierlichen Wavelets" zu erhalten. Deshalb wurden Daubechies ' Wavelets und später Symmlets und Coiflets gebaut . Diese seltsam geformten Wavelets haben keine schönen und einfachen Formeln wie das Morlet-Wavelet.

O(N)

In der Tat ist die FWT nur eine diskrete Abtastung der CWT

DWT (oder FWT) ist genau wie die DFT / FFT. Die meisten anderen diskretisierten CWT (mit einem beliebigen Wavelet) sind genau so (ohne großen Schaden, wenn Sie über eine ausreichende Redundanz verfügen).

So:

  • kkk804T2×424[ω/2,ω]42×22[ω/8,ω/4][1,1,2,4]
  • k
  • +×O(N)

Die folgenden Bilder zeigen, wie eine kontinuierliche Version des Haar-Wavelets aussieht kontinuierliches Haar-Wavelet

kann in ein orthogonales, diskretes Wavelet abgetastet werden: diskrete kritische Haar-Wavelet

Beachten Sie, dass einige diskrete Wavelets, insbesondere die langen (wie Splines), manchmal mit einer FFT berechnet werden :)

Laurent Duval
quelle