Jakie współczynniki czasowo-częstotliwościowe oblicza transformata Wavelet?

Fast Fourier Transform wykonuje $\mathcal O(N \log N)$ operacji, podczas gdy szybko WAVELET Transform wykonuje $\mathcal O(N)$ . Ale co konkretnie oblicza FWT?

Chociaż często się je porównuje, wydaje się, że FFT i FWT to jabłka i pomarańcze. Jak rozumiem, bardziej odpowiednie byłoby porównanie STFT (FFT małych kawałków w czasie) ze złożonym Morletem WT , ponieważ oba są reprezentacjami czasowo-częstotliwościowymi opartymi na złożonych sinusoidach (proszę mnie poprawić, jeśli się mylę ). Jest to często pokazane za pomocą takiego schematu:

( Inny przykład )

Po lewej pokazuje, jak STFT jest wiązką FFT ułożonych jedna na drugiej w miarę upływu czasu (ta reprezentacja jest początkiem spektrogramu ), podczas gdy po prawej pokazuje dyadyczny WT, który ma lepszą rozdzielczość czasową przy wysokich częstotliwościach i lepszą częstotliwość. rozdzielczość przy niskich częstotliwościach (ta reprezentacja nazywa się skalogramem ). W tym przykładzie $N$ dla STFT jest liczbą pionowych kolumn (6), a pojedyncza operacja \ matematyczna FFT oblicza pojedynczy rząd współczynników z próbek. Łącznie jest to 8 FFT po 6 punktów każda lub 48 próbek w dziedzinie czasu.$\mathcal O(N \log N)$$N$$N$

Czego nie rozumiem:

• Ile współczynników oblicza pojedyncza matematyczna operacja FWT i gdzie się one znajdują na powyższym wykresie czasowo-częstotliwościowym? $\mathcal O(N)$

• Które prostokąty wypełnia jedno obliczenie?

• Jeśli obliczymy blok współczynników czasowo-częstotliwościowych o równej powierzchni przy użyciu obu, czy otrzymamy taką samą ilość danych?

• Czy FWT jest nadal bardziej wydajny niż FFT?

Konkretny przykład z wykorzystaniem 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.        ]))

Tworzy dwa zestawy 4 współczynników, więc jest taki sam jak liczba próbek w oryginalnym sygnale. Ale jaki jest związek między tymi 8 współczynnikami a kafelkami na schemacie?

Aktualizacja:

Właściwie prawdopodobnie robiłem to źle i powinienem używać wavedec(), który dokonuje wielopoziomowego rozkładu DWT:

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.        ])]

Masz rację, że FWT lepiej jest traktować jako „kuzyna” STFT niż FT. W rzeczywistości FWT jest po prostu dyskretnym próbkowaniem CWT (ciągła transformata falkowa), ponieważ FFT / DFT jest dyskretnym próbkowaniem transformaty Fouriera. Może się to wydawać subtelną kwestią, ale ma znaczenie przy wyborze sposobu dyskretyzacji transformacji.

Zarówno CWT, jak i STFT są redundantnymi analizami sygnału. Innymi słowy, masz więcej „współczynników” (w przypadku dyskretnym), niż musisz w pełni reprezentować sygnał. Jednak transformata Fouriera (lub powiedzmy transformata falkowa przy użyciu tylko jednej skali) integruje sygnał od-nieskończoności do + nieskończoności. Nie jest to bardzo przydatne w sygnałach z prawdziwego świata, więc obcinamy (tj. Okno) transformacje do krótszych długości. Okienkowanie sygnału zmienia transformację - mnożymy przez okno w czasie / przestrzeni, więc w przestrzeni transformacji masz splot transformaty okna z transformacją sygnału.

W przypadku STFT, okna mają (zwykle) tę samą długość (zakres niezerowy) przez cały czas i są niezależne od częstotliwości (okienko sygnału 10 Hz ma taką samą szerokość jak sygnał 10 kHz). Otrzymujesz prostokątny spektrogram siatki, tak jak narysowałeś.

CWT ma to okienkowanie wbudowane w fakt, że falki stają się krótsze (w czasie lub przestrzeni) wraz ze spadkiem skali (jak wyższa częstotliwość). Tak więc dla wyższych częstotliwości efektywne okno jest krótsze i kończysz się skalogramem, który wygląda tak, jak narysowałeś dla FWT.

To, jak dyskretyzujesz CWT, zależy od ciebie, choć myślę, że istnieją minimalne próbki zarówno w przesunięciu, jak i skali, aby w pełni reprezentować sygnał. Zazwyczaj (przynajmniej sposób, w jaki ich użyłem), dla najniższej skali (najwyższej częstotliwości), próbkujesz we wszystkich lokalizacjach przesunięcia (czas / przestrzeń). W miarę zwiększania skali (niższej częstotliwości) możesz próbkować rzadziej. Uzasadnieniem jest to, że niskie częstotliwości nie zmieniają się tak szybko (pomyślmy o zderzeniu talerza z gitarą basową - zderzenie talerza ma bardzo krótkie transjenty, podczas gdy gitara basowa zajęłaby więcej czasu). W rzeczywistości, w najkrótszej skali (zakładając, że próbkujesz we wszystkich lokalizacjach zmiany), masz pełną reprezentację sygnału (możesz go zrekonstruować, używając tylko współczynników w tej skali). Nie jestem pewien co do uzasadnienia próbkowania skali. JA' widzieliśmy to sugerowane jako logarytmiczne, z (chyba) bliższymi odstępami między krótszymi skalami. Myślę, że dzieje się tak, ponieważ falki w dłuższych skalach mają szerszą transformatę Fouriera (dlatego „wychwytują” więcej częstotliwości).

Przyznaję, że nie do końca rozumiem FWT. Mam przeczucie, że w rzeczywistości jest to minimalne próbkowanie w przesunięciu / skali i nie jest to zbędna reprezentacja. Ale potem myślę, że tracisz zdolność analizowania sygnału (i bałagania się) w krótkim czasie bez wprowadzania niepożądanych artefaktów. Przeczytam o tym więcej i, jeśli nauczę się czegoś przydatnego, zgłoś się. Mam nadzieję, że inni będą chcieli komentować.

Rozważ przypadek falki Haar. Szybka transformata falkowa rekurencyjnie dzieli sygnał i za każdym razem oblicza sumę i różnicę obu połówek. Różnica polega na wielkości transformacji dla bieżącej falki, a suma jest zwracana do osoby dzwoniącej w celu obliczenia wielkości transformacji dla rozszerzonej falki z połową częstotliwości. Zatem FWT obejmuje płaszczyznę czasowo-częstotliwościową przy użyciu wzoru opisanego na schemacie, który podałeś.

Pamiętaj, że schemat, który podałeś, jest nieco mylący. To, co naprawdę próbują ci powiedzieć, to to, że dostajesz jedną próbkę o najniższej częstotliwości, dwie próbki o podwójnej częstotliwości, cztery próbki czterokrotnie i tak dalej. Właściwości czasowo-częstotliwościowe każdej falki nie są takie, że pokrywają ich płytkę. W praktyce każda falka obejmie nieskończony obszar, ponieważ ma kompaktowe wsparcie, a zatem musi być całkowicie delokalizowana pod względem częstotliwości. Powinieneś więc pomyśleć o środkach tych płytek.

Ponadto FWT wymaga odrębnej falki, która musi spełniać znacznie bardziej restrykcyjne kryterium dopuszczalności niż ciągłe falki dla CWT. W konsekwencji właściwości czasowo-częstotliwościowe dyskretnych falek są ogólnie okropne (np. Falki Daubechies są albo pełne ostrych cech lub mają zmienną częstotliwość), a użyteczność płaszczyzny czas-częstotliwość jest znacznie zmniejszona w kontekście FWT. Jednak ciągłe falki są używane do obliczania reprezentacji czasowo-częstotliwościowych sygnałów.

Twoje referencje to:

Sekwencja współczynników oparta na ortogonalnej podstawie małych skończonych fal lub falek.

Więcej informacji może Ci się spodobać na stronie DWT . Tam wprowadza falki Haar, falki Daubechies i inne. Wskazuje jak

• Falki mają położenie - falka (1,1, –1, –1) odpowiada „lewej stronie” kontra „prawej stronie”, podczas gdy dwie ostatnie falki mają podparcie po lewej lub prawej stronie, a jedna jest tłumaczeniem z drugiej.
• Fale sinusoidalne nie mają położenia - rozpościerają się po całej przestrzeni - ale mają fazę - druga i trzecia fala są przesunięciami względem siebie, odpowiadającymi 90 ° poza fazą, jak cosinus i sinus, z których są to wersje dyskretne .

Jeśli zamiast dyskretnych falek chcesz teraz mówić o falach ciągłych lub falach złożonych, możesz zacząć od serii falek .

Oprócz wikipedii, podręcznik i kurs mogą ci dobrze poradzić.

$O(N^2)$

$O(N)$$O(N\log(N))$$O(\cdot)$

Zacznij od ogólnego STFT w oknie (forma ciągła). Po podłączeniu nieskończonego okna o wysokości jednostki odzyskujesz transformatę Fouriera jako specjalny przypadek. Które możesz zdyskretyzować (i uzyskać DFT) i sprawić, by było szybkie (i uzyskać FFT).

Zacznij od CWT (forma ciągła). Ciągły CWT dopuszcza niewiarygodną liczbę potencjalnych kształtów falek. Można je dyskretyzować dokładnie tylko z wzorcami próbkowania (w czasie lub skali), które respektują pewne nierówności „Heisenberga”: jedna próbka na jednostkę powierzchni. Wzory te zależą od falki. W większości przypadków wzory tworzą dyskretny CWT, który jest zbędny i dają ramkę falkową.

Niektórzy chcieli, aby nie był zbędny, ze skalą diadad (DWT). Tylko kilka falek (wciąż liczba nieskończona, ale nie można ich przypadkowo znaleźć) pozwala na to. Wśród pierwszych były falki Haar, Franklin i Meyer. Jeśli następnie narzucisz wsparcie falkowe za skończone, to Haar był jedyny przez długi czas. Prawie niemożliwe jest uzyskanie ortogonalnej falki z „naturalnych ciągłych fal”, dlatego zbudowano te Daubechies , a później Symmlety i Coiflety . Te dziwnie ukształtowane falki nie mają ładnych i prostych wzorów, takich jak falka Morleta.

$O(N)$

W rzeczywistości FWT jest po prostu dyskretnym próbkowaniem CWT

DWT (lub FWT) jest dokładny, podobnie jak DFT / FFT. Większość innych dyskretnych CWT (z dowolną falką) jest w przybliżeniu taka (bez większych szkód, jeśli masz wystarczającą redundancję).

Więc:

• $k$$k$$k$$8$$0$$4T$$2\times 4$$2$$4$$[\omega/2,\omega]$$4$$2\times2$$2$$[\omega/8,\omega/4]$$[1,1,2,4]$
• prostokąty byłyby wypełnione CWT. Dzięki DWT nie są one wypełnione, mają tylko$k$
• $+$$\times$$O(N)$ . Do analizy sinusoidalnej? FWT nigdy nie jest dobry (szczególnie ze względu na filtry o skończonej długości). Ale w przypadku zwartej reprezentacji obrazów, takich jak JPEG2000, mogą być całkiem dobre. Tam możesz użyć nieco szybszego schematu, takiego jak schemat podnoszenia.

Poniższe zdjęcia pokazują, jak ciągła wersja falki Haar

można próbkować w ortogonalną, dyskretną falkę:

Zauważ, że niektóre dyskretne falki, zwłaszcza długie (jak splajny), są czasami obliczane przy użyciu FFT :)