Ist ein Wavelet-basiertes Korrelationsmaß einen zusätzlichen Rechenaufwand wert?

9

Ich habe sowohl Korrelation als auch Kohärenz als Maß für die Korrelation zwischen Signalen verwendet. Ich dachte, dass ein Zeit-Frequenz-Ansatz mir das Beste aus diesen Welten geben würde.

Meine Frage ist, ob diese zusätzlichen Daten genug zum Gesamtbild des Signals beitragen, um die erhöhten Rechenkosten zu rechtfertigen, die mit der Durchführung der Wavelet-Transformationen als Teil der Berechnung verbunden sind.

Referenz: eine ArXiv- Arbeit: "Eine Kreuzkorrelationstechnik im Wavelet-Bereich zum Nachweis stochastischer Gravitationswellen" von S.Klimenko, G.Mitselmakher, A.Sazonov

jonsca
quelle
Wie viel zusätzliche Rechenkosten? Können Sie es mit FFTs oder FWTs schneller machen?
Endolith
@endolith Angenommen, ich würde diese Algorithmen bereits einbauen, denke ich.
Jonsca
1
Nun, Kohärenz und Korrelation könnten beide FFT verwenden, was O (N log N) ist, während FWT O (N) ist, also könnte die Wavelet-Methode tatsächlich schneller sein ? Ich habe jedoch kein klares Verständnis dafür, obwohl ich zweimal gefragt habe: math.stackexchange.com/questions/28581/… stackoverflow.com/questions/1787536/…
Endolith
1
Auf jeden Fall sollten Sie das verwenden, was für das, was Sie tun möchten, am besten geeignet ist. Das ist so, als würde man fragen: "Was ist besser? Schraubendreher oder Hämmer?"
Endolith
1
@jonsca Deine Intuition ist eigentlich richtig. Anscheinend ist die DWT-Transformation eine Zeitvariante, und diese Eigenschaft kann zu einer gewissen Ausnutzung führen. Ich mache genau das Gleiche für ein Projekt, an dem ich arbeite. Das Ziel ist es, TDOA (Time Delay of Arrival) zwischen zwei Signalen zu schätzen. Zuerst habe ich sie mit (einer handgeschriebenen) DWT transformiert und dann kreuzkorreliert. Hier ist ein Link zu einem Artikel, den Sie in meiner öffentlichen Dropbox lesen können. ( dl.dropbox.com/u/4724281/waveletBasedTDOA.pdf )
Spacey

Antworten:

5

Zunächst sollten Sie das für den Job geeignete Werkzeug verwenden. Korrelation gegen Kohärenz gegen Wavelet-basierte Korrelation sind alles verschiedene Dinge. Diese Frage ist also so etwas wie die Frage: "Was ist besser? Schraubendreher oder Hämmer?" Es hängt davon ab, was Sie versuchen und ob Sie sich für zeitliche Ähnlichkeit, Frequenzspektren oder beides interessieren.

Zweitens habe ich nur ein minimales Verständnis von Wavelets, aber Ihre Annahme, dass Wavelets mehr Berechnungen erfordern, könnte falsch sein. Die schnelle Fourier - Transformation nimmt Operationen , während die schnelle Wavelet - Transformation nimmt . Die Wavelet-Methode erfordert möglicherweise weniger Berechnungen, je nachdem, ob Sie die Informationen verwenden können, die Sie daraus erhalten.O(nlogn) O(n)

Empirisch , die Herstellung von n Ausgaben von n realen Eingängen, die Multi-Level - Wavelet - Transformation in PyWavelets schneller als NumPy des FFT , wenn n größer als etwa 4096 ist.

Geben Sie hier die Bildbeschreibung ein

jedoch

  1. Es ist Python, und die beiden Implementierungen können sehr unterschiedlich effizient sein. Ich weiß nicht einmal, ob wavedec()dies als schnelle Wavelet-Transformation angesehen werden würde. Sie verwenden in ihrer Dokumentation die Abkürzung DWT . Sind Haar DWT und FWT dasselbe?
  2. Die Zeit variiert je nach verwendetem Wavelet. Meyer Wavelet benötigt sechsmal so lange wie Daubechies, um die gleiche Datenmenge zu erzeugen.
  3. Ich verstehe immer noch nicht, wie die FWT die Zeit-Frequenz-Ebene kachelt oder ob die Erzeugung von n Ausgängen ausreicht, um die gleiche Art von Ähnlichkeitsmessung wie eine n- Punkt-Kreiskorrelation unter Verwendung von FFTs zu erhalten. (Technisch gesehen ist es eine Zeitskalenebene, keine Zeitfrequenz, aber ich denke, sie sind für das komplexe Morlet-Wavelet gleich ?) FWT ist eine "kritische Abtastung" der Ebene und erzeugt die gleiche Datenmenge wie FFT. es scheint also fair, sie zu vergleichen.

Der Hauptpunkt ist, dass die Rechenzeit für beide zumindest ungefähr gleich ist, daher denke ich nicht, dass Sie sich darüber Gedanken machen sollten, wenn Sie sich für eine Verwendung entscheiden.

Endolith
quelle
3

Das ist sehr spät, aber vielleicht lohnt es sich trotzdem ...

Die Zeitskalenebene ist nicht dieselbe wie die Zeit-Frequenz-Ebene, obwohl sie auch nützlich sein könnte. Signale an verschiedenen Stellen in der Zeitskalenebene werden durch in Beziehung gesetzt , wobei Sie in der Skala nach oben (oder unten) bewegt und verschiebt Sie rechtzeitig. Die gleiche Transformation in der Zeit-Frequenz-Ebene ist , wobei eine Frequenzverschiebung ist. Wenn Ihr Signal eine Sinuswelle ist, sind die beiden Transformationen gleich.x(t)x(Δs(tΔt))ΔsΔtx(t)x(tΔt)eiΔωtΔωx(t)

Die DWT oder diskrete Wavelet-Transformation berechnet nur diskrete Skalen, genauso wie die FFT nur diskrete Frequenzen berechnet. Und der Kommentar, den @Spacey oben gemacht hat, dass die DWT nicht übersetzungsinvariant ist, ist korrekt. Dies liegt daran, dass in jeder Phase der DWT das Signal um zwei dezimiert wird. Dies macht die DWT schneller als die FFT, , zerstört aber auch die Translationsinvarianz.O(N)

Die Verwendung des DWT zur Untersuchung der Zeitskalenebene bringt Sie also nicht sehr weit. Dies gilt insbesondere, weil die vom DWT "besuchten" Skalen durch zwei Faktoren getrennt sind und viel weniger dicht sind als die Abdeckung, die Sie in der Zeit-Frequenz-Ebene mit der FFT erhalten können. Sie müssen eine Wavelet-Transformation verwenden, die translatorisch invariant ist und unter vielen anderen Namen manchmal als nicht dezimierte Wavelet-Transformation bezeichnet wird. Selbst dann haben Sie immer noch die Sparsamkeit der berechneten Skalenproben, mit denen Sie fertig werden müssen.

Darüber hinaus ist es oft wünschenswert, sich Orte in der Zeitskalenebene mit einer Energiedichte vorzustellen. Dieser Ansatz wird durch die Verwendung eines analytischen Wavelets wie des zuvor erwähnten komplexen Morlet-Wavelets erleichtert. Eine Methode, die Translationsinvarianz und Analytizität mit der Rechenzeit in Einklang bringt, ist die komplexe Dual-Tree-Wavelet-Transformation . Dasselbe in der Zeit-Frequenz-Ebene zu tun, ist vielleicht einfacher: Führen Sie zuerst eine ungefähre Hilbert-Transformation für Ihr Signal durch, indem Sie eine FFT durchführen, alle negativen Frequenzen auf Null setzen, gefolgt von einer IFFT.

Wenn die Intuition, dass Korrelation nach Ähnlichkeit in der Zeit und Kohärenz nach Ähnlichkeit in der Frequenz sucht, richtig ist, ist es möglicherweise besser, sich an die Zeit-Frequenz-Ebene zu halten. Es ist sicherlich einfacher zu berechnen und die Abtastung entlang der Frequenzachse zu verfeinern. Keiner der oben genannten Ansätze befasst sich mit einer dichteren Abtastung der Skalenachse. Um das zu tun, müssen Sie so ziemlich zur kontinuierlichen Wavelet-Transformation gehen , obwohl es möglicherweise noch etwas anderes gibt, das mir nicht bewusst ist. Wenn Sie Matlab haben, folgen Sie dem Link oben und haben Sie es.

Rodney Preis
quelle