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

26

Fast Fourier Transform wykonuje O(NlogN) operacji, podczas gdy szybko WAVELET Transform wykonuje 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:

Siatki pokazujące, w jaki sposób współczynniki FFT i WT odpowiadają płaszczyźnie czasowo-częstotliwościowej

( 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.NO(NlogN)NN

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? 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.        ])]
endolit
źródło
2
Aby lepiej zrozumieć, jak działa rozkład tych falek, jednym przydatnym narzędziem byłaby możliwość wykonania tego na rzeczywistych sygnałach: na przykład sygnał audio (mam pytanie w tym kierunku tutaj dsp.stackexchange.com/ pytania / 12694 / stft-and-dwt-
wavelets
@endolith Czy twoje pytanie jest nadal zadawane? Jeśli tak, mogę dodać inne wskazówki
Laurent Duval
@LaurentDuval Tak, wciąż jest otwarty i nadal nie rozumiem. Mogę się mylić, ponieważ CWT używa rzeczy takich jak Morlet, a DWT używa tylko takich rzeczy jak Haar lub Daubechies. Nie jestem pewien, czy szybki FWT to tylko Haar, czy może też używać innych rodzajów falek.
endolith
2
@ndolith Tylko komentarz do tego: ciągły CWT dopuszcza niewiarygodną liczbę potencjalnych kształtów falek. Można je dyskretyzować tylko z wzorcami próbkowania (w czasie lub skali), które szanują pewne nierówności „Heisenberga”. Wzory te zależą od falki. W większości przypadków wzorce tworzą dyskretny CWT, który jest zbędny. Niektórzy chcą, aby nie był zbędny, ze skalą diadad. Na to pozwala bardzo niewiele falek. Jeśli następnie narzucisz, że wsparcie falkowe jest skończone, to Haar jest jednym, prawie niemożliwym do uzyskania w / „falami naturalnymi”, dlatego właśnie te zostały zbudowane przez Daubechies
Laurent Duval

Odpowiedzi:

13

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ć.

Patrick
źródło
1
„w rzeczywistości jest to minimalne próbkowanie z przesunięciem / skalą i nie stanowi zbędnej reprezentacji”. Ach! Myślę, że masz rację, a to wyjaśniałoby, dlaczego zawsze jest porównywane do FFT, która jest również minimalną reprezentacją.
endolith
3
FWT jest krytycznym próbkowaniem CWT. Wciąż staram się to lepiej zrozumieć, ale nauczyłem się, że STFT i CWT są ramkami. Teoria klatek wychodzi poza mnie, ale jednym z interesujących pojęć jest wzór niepewności, że dla STFT, dw * dt> C (dw jest rozdzielczością częstotliwości, a dt jest rozdzielczością czasową). Innymi słowy, gdy próbujesz lepiej rozpoznać częstotliwość, tracisz rozdzielczość czasową. CWT nie ma tego ograniczenia. Będę czytał i spróbował wyjaśnić moją odpowiedź powyżej, kiedy wyjaśnię ją sobie w głowie.
1
Z tego, co rozumiem, CWT ma takie same ograniczenia, ale wykorzystuje lepszy kompromis.
endolith,
1
„STFT to nadmiarowe analizy sygnału”. Nie sądzę, że to prawda. Jeśli masz sygnał 100-punktowy, podziel go na kawałki po 10 punktów, a następnie wykonaj 10-punktowy FFT na każdym z nich, nadal masz te same informacje zapisane w tej samej ilości próbek.
endolith,
11

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.


źródło
Tak, rozumiem lokalizację współczynników. To to samo co FFT. Kiedy mówisz „musisz przestrzegać”, co masz na myśli? Czy to tylko wymóg, jeśli próbujesz uzyskać minimalną / nie redundantną reprezentację sygnału? Co jeśli próbujesz to analizować / wizualizować? Dodam bardziej konkretny przykład do pytania.
endolith
1
Przestrzeganie kryterium dopuszczalności zapewnia istnienie rozdzielczości tożsamości, tzn. Że wszystkie sygnały można odzyskać z ich przekształceń falkowych. Jeśli nie zastosujesz się do niego, nie możesz odzyskać sygnału z jego transformacji, w którym to momencie musisz zadać pytanie, co dokładnie analizujesz (czy to w ogóle odzwierciedla jakąkolwiek informację, która była w sygnale ?!). Jeśli nie potrzebujesz minimalnej / nie redundantnej reprezentacji, możesz użyć bardziej swobodnego kryterium dopuszczalności z CWT (co pozwala zdefiniować więcej „idealnych” falek).
1
Myślę, że bardzo przydatna byłaby moja praca doktorska. Umieszczę to dla ciebie w Internecie ...
Czy umieściłeś to online? :)
endolith,
3

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ć.


źródło
Nie rozumiem tej odpowiedzi. Czy to odpowiada na moje pytania? Lewa strona i prawa strona czego? Co to ma wspólnego z reprezentacją czasowo-częstotliwościową?
endolith
Opis „lewa strona kontra prawa strona” jest fragmentem podglądu strony DWT, pokazującym, że strona ta zawiera prosty przykład wyjaśniający względne zalety podstawy sinusoidalnej i podstawy fal Fal Haara. Pytałeś o naturę współczynników w transformacie falkowej. Brzmiało to tak, jakbyś szukał intuicji. Pomyślałem, że ten przykład (w oryginalnym kontekście) może ci się przydać.
Tak, przed opublikowaniem tego pytania przeczytałem wiele artykułów z Wikipedii. Nie wiem czy / co twoja odpowiedź ma wspólnego z moim pytaniem o reprezentację czasowo-częstotliwościową. Jeśli tak, czy możesz połączyć kropki? FFT n próbek da n współczynników, które tworzą pojedynczą kolumnę spektrogramu STFT. Czy istnieje odpowiedni związek między współczynnikami wytwarzanymi przez WT a skalogramem? Jeśli tak, co to jest? Które z pól w prawym dolnym wykresie są wypełnione pojedynczym przebiegiem przez FWT?
endolith
1
Prawie wszystko na stronach Wikipedii związanych z falkami jest obecnie nieprawidłowe.
3

O(N.2))

O(N.)O(N.log(N.))O()

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:

  • kkk804T.2)×42)4[ω/2),ω]42×22[ω/8,ω/4][1,1,2,4]
  • prostokąty byłyby wypełnione CWT. Dzięki DWT nie są one wypełnione, mają tylkok
  • +×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 ciągła falka Haara

można próbkować w ortogonalną, dyskretną falkę: dyskretna krytyczna falka Haara

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

Laurent Duval
źródło