Dyskretna transformata falkowa - Discrete wavelet transform

Przykład 2D dyskretnej transformacji falkowej, która jest używana w JPEG2000 . Oryginalny obraz jest filtrowany górnoprzepustowo, co daje trzy duże obrazy, z których każdy opisuje lokalne zmiany jasności (szczegóły) na oryginalnym obrazie. Następnie jest filtrowany dolnoprzepustowo i skalowany w dół, co daje obraz przybliżony; obraz ten jest filtrowany górnoprzepustowo, aby uzyskać trzy mniejsze obrazy szczegółów, oraz filtrem dolnoprzepustowym, aby uzyskać ostateczny obraz przybliżenia w lewym górnym rogu.

W analizie numerycznej i analizy funkcjonalnej , A dyskretnej transformaty falkowej ( DWT ) jest dowolnym falkowej przekształcić w którym wavelets się dyskretne próbki. Podobnie jak w przypadku innych transformat falkowych, kluczową przewagą nad transformatami Fouriera jest rozdzielczość czasowa: przechwytuje zarówno informacje o częstotliwości, jak i lokalizacji (lokalizacja w czasie).

Przykłady

Falki Haara

Pierwsze DWT zostało wynalezione przez węgierskiego matematyka Alfreda Haara . W przypadku danych wejściowych reprezentowanych przez listę liczb można uznać , że transformata falkowa Haara łączy w pary wartości wejściowe, przechowując różnicę i przekazując sumę. Proces ten powtarza się rekursywnie, łącząc sumy w pary, aby udowodnić następną skalę, co prowadzi do różnic i ostatecznej sumy. ${\ Displaystyle 2 ^ {n}}$ ${\ Displaystyle 2 ^ {n} -1}$

Falki Daubechies

Najczęściej używany zestaw dyskretnych przekształceń falkowych został sformułowany przez belgijską matematykę Ingrid Daubechies w 1988 roku. To sformułowanie jest oparte na wykorzystaniu relacji rekurencyjnych do generowania coraz dokładniejszych dyskretnych próbkowania niejawnej macierzystej funkcji falkowej; każda rozdzielczość jest dwa razy większa niż w poprzedniej skali. W swojej przełomowej pracy Daubechies wywodzi rodzinę falek , z których pierwszą jest falka Haara. Zainteresowanie tą dziedziną eksplodowało od tego czasu i powstało wiele odmian oryginalnych fal Daubechies.

Złożona transformata falkowa podwójnego drzewa (DℂWT)

Złożona transformata falkowa z podwójnym drzewem (ℂWT) jest stosunkowo niedawnym ulepszeniem dyskretnej transformacji falkowej (DWT), z ważnymi dodatkowymi właściwościami: jest prawie niezmienna względem przesunięcia i selektywna kierunkowo w dwóch i wyższych wymiarach. Osiąga to przy współczynniku redundancji wynoszącym tylko , znacznie niższym niż niepodzielony DWT. Wielowymiarowe (MD) podwójne drzewo ℂWT jest nieseparowalne, ale opiera się na wydajnym obliczeniowo, separowalnym banku filtrów (FB). ${\ Displaystyle 2 ^ {d}}$

Inni

Inne formy dyskretnej transformacji falkowej obejmują falkę LeGall-Tabatabai (LGT) 5/3 opracowaną przez Didiera Le Galla i Ali J. Tabatabai w 1988 (używaną w JPEG 2000 lub JPEG XS ), dwumianową QMF opracowaną przez Ali Naci Akansu w 1990 , algorytm partycjonowania zbiorów w drzewach hierarchicznych (SPIHT) opracowany przez Amira Saida wraz z Williamem A. Pearlmanem w 1996 roku, niedzielona transformacja falkowa (gdzie pominięto próbkowanie w dół) oraz transformatę Newlanda (gdzie powstaje ortonormalna baza falek). z odpowiednio skonstruowanych filtrów top-hat w przestrzeni częstotliwości ). Transformacje pakietów falkowych są również powiązane z dyskretną transformatą falkową. Inną formą jest transformacja falkowa zespolona .

Nieruchomości

Haar DWT ilustruje ogólnie pożądane właściwości falek. Po pierwsze, można to wykonać w operacjach; po drugie, ujmuje nie tylko pojęcie zawartości częstotliwościowej wejścia, badając ją w różnych skalach, ale także zawartość czasową, tj. czasy, w których te częstotliwości występują. W połączeniu te dwie właściwości sprawiają, że szybka transformata falkowa (FWT) jest alternatywą dla konwencjonalnej szybkiej transformacji Fouriera (FFT). ${\ Displaystyle O (n)}$

Problemy z czasem

Ze względu na operatory zmiany szybkości w banku filtrów, dyskretny terminal WT nie jest niezmienny w czasie, ale w rzeczywistości jest bardzo wrażliwy na wyrównanie sygnału w czasie. Aby rozwiązać zmienny w czasie problem transformacji falkowej, Mallat i Zhong zaproponowali nowy algorytm reprezentacji falkowej sygnału, który jest niezmienny w stosunku do przesunięć czasowych. Zgodnie z tym algorytmem, który nazywa się TI-DWT, tylko parametr skali jest próbkowany wzdłuż sekwencji dwuczłonowej 2^j (j∈Z), a transformacja falkowa jest obliczana dla każdego punktu w czasie.

Aplikacje

Dyskretna transformata falkowa ma ogromną liczbę zastosowań w nauce, inżynierii, matematyce i informatyce. Przede wszystkim jest on używany do kodowania sygnału , aby przedstawić dyskretny sygnał w bardziej redundantnej formie, często jako wstępne uwarunkowanie kompresji danych . Praktyczne zastosowania można również znaleźć w przetwarzaniu sygnałów przyspieszeń do analizy chodu, przetwarzaniu obrazu, w komunikacji cyfrowej i wielu innych.

Wykazano, że dyskretna transformata falkowa (dyskretna w skali i przesunięciu oraz ciągła w czasie) jest z powodzeniem wdrażana jako analogowy bank filtrów w biomedycznym przetwarzaniu sygnałów do projektowania stymulatorów małej mocy, a także w ultraszerokopasmowej (UWB) komunikacji bezprzewodowej.

Przykład przetwarzania obrazu

Obraz z szumem Gaussa.

Obraz z usuniętym szumem Gaussa.

Falki są często używane do odszumiania sygnałów dwuwymiarowych, takich jak obrazy. Poniższy przykład zawiera trzy kroki, aby usunąć niechciany biały szum Gaussa z zaszumionego obrazu. Matlab został użyty do importu i filtrowania obrazu.

Pierwszym krokiem jest wybór typu falki i poziomu N rozkładu. W tym przypadku wybrano falki biortogonalne 3,5 o poziomie N równym 10. Falki biortogonalne są powszechnie stosowane w przetwarzaniu obrazu do wykrywania i filtrowania białego szumu Gaussa, ze względu na ich wysoki kontrast wartości intensywności sąsiednich pikseli. Wykorzystując te falki, na dwuwymiarowym obrazie przeprowadzana jest transformacja falkowa .

Po rozłożeniu pliku obrazu następnym krokiem jest określenie wartości progowych dla każdego poziomu od 1 do N. Strategia Birgé-Massarta jest dość powszechną metodą wyboru tych progów. Wykorzystując ten proces tworzone są indywidualne progi dla N = 10 poziomów. Zastosowanie tych progów stanowi większość faktycznego filtrowania sygnału.

Ostatnim krokiem jest rekonstrukcja obrazu ze zmodyfikowanych poziomów. Osiąga się to za pomocą odwrotnej transformacji falkowej. Wynikowy obraz z usuniętym białym szumem Gaussa jest pokazany poniżej oryginalnego obrazu. Podczas filtrowania dowolnej formy danych ważne jest, aby określić ilościowo stosunek sygnału do szumu wyniku. W tym przypadku SNR obrazu zaszumionego w porównaniu z oryginałem wyniósł 30,4958%, a SNR obrazu odszumionego 32,5525%. Wynikająca z tego poprawa filtrowania falkowego to wzmocnienie SNR o 2,0567%.

Należy zauważyć, że wybór innych falek, poziomów i strategii progowania może skutkować różnymi rodzajami filtrowania. W tym przykładzie do usunięcia wybrano biały szum Gaussa. Chociaż przy innym progowaniu można by go równie dobrze wzmocnić.

Aby zilustrować różnice i podobieństwa między dyskretną transformatą falkową a dyskretną transformatą Fouriera , rozważ DWT i DFT następującej sekwencji: (1,0,0,0), impuls jednostkowy .

DFT ma bazę ortogonalną ( macierz DFT ):

{\ Displaystyle {\ zacząć {bmatrix} 1 i 1 i 1 i 1 \ \ 1 i 1 i 1 i 1 \ \ 1 i 1 i 1 i 1 \ \ 1 i i 1 i 1 i 1 \ koniec {b macierzy}}}

podczas gdy DWT z falkami Haara dla danych o długości 4 ma bazę ortogonalną w rzędach:

{\ Displaystyle {\ zacznij {bmatrix} 1 i 1 i 1 i 1 \ \ 1 i 1 i 1 i 1 \ \ 1 i 1 i 0 i 0 \ \ 0 i 0 i 1 i 1 \ koniec {bmatrix}}}

(Aby uprościć notację, używane są liczby całkowite, więc bazy są ortogonalne, ale nie ortonormalne ).

Wstępne obserwacje obejmują:

Fale sinusoidalne różnią się jedynie częstotliwością. Pierwszy nie kończy żadnego cyklu, drugi kończy jeden pełny cykl, trzeci kończy dwa cykle, a czwarty kończy trzy cykle (co jest równoznaczne z ukończeniem jednego cyklu w przeciwnym kierunku). Różnice faz można przedstawić mnożąc dany wektor bazowy przez stałą zespoloną.
Natomiast falki mają zarówno częstotliwość, jak i lokalizację. Tak jak poprzednio, pierwszy kończy cykle zero, a drugi kończy jeden cykl. Jednak trzeci i czwarty mają tę samą częstotliwość, dwukrotnie większą niż pierwsza. Zamiast różnić się częstotliwością, różnią się lokalizacją — trzecia jest niezerowa na pierwszych dwóch elementach, a czwarta jest niezerowa na drugich dwóch elementach.

{\ Displaystyle {\ zacząć {wyrównany} (1, 0, 0, 0) i = {\ Frac {1} {4}} (1, 1, 1, 1) + {\ Frac {1} {4}} (1,1,-1,-1)+{\frac {1}{2}}(1,-1,0,0)\qquad {\text{Haar DWT}}\\(1,0,0) ,0)&={\frac {1}{4}}(1,1,1,1)+{\frac {1}{4}}(1,i,-1,-i)+{\frac {1}{4}}(1,-1,1,-1)+{\frac {1}{4}}(1,-i,-1,i)\qquad {\text{DFT}}\ koniec{wyrównany}}}

DWT pokazuje lokalizację: termin (1,1,1,1) podaje średnią wartość sygnału, (1,1,–1,–1) umieszcza sygnał po lewej stronie domeny, a (1 ,–1,0,0) umieszcza go po lewej stronie po lewej stronie, a obcięcie na dowolnym etapie daje downsamplingową wersję sygnału:

{\ Displaystyle {\ zacząć {wyrównany} i \ lewo ({\ Frac {1} {4}}, {\ Frac {1} {4}}, {\ Frac {1} {4}}, {\ Frac { 1}{4}}\right)\\&\left({\frac {1}{2}},{\frac {1}{2}},0,0\right)\qquad {\text{2 -term obcięcie}}\\&\left(1,0,0,0\right)\end{aligned}}}

Funkcja sinc , pokazująca artefakty w dziedzinie czasu ( niedociągnięcie i dzwonienie ) obcinania szeregu Fouriera.

Natomiast DFT wyraża sekwencję poprzez interferencję fal o różnych częstotliwościach – w ten sposób obcięcie serii daje wersję serii z filtracją dolnoprzepustową :

{\ Displaystyle {\ zacząć {wyrównany} i \ lewo ({\ Frac {1} {4}}, {\ Frac {1} {4}}, {\ Frac {1} {4}}, {\ Frac { 1}{4}}\right)\\&\left({\frac {3}{4}},{\frac {1}{4}},-{\frac {1}{4}},{ \frac {1}{4}}\right)\qquad {\text{skrócenie dwuczłonowe}}\\&\left(1,0,0,0\right)\end{aligned}}}

Warto zauważyć, że średnie przybliżenie (2-okresowe) jest różne. Z perspektywy w dziedzinie częstotliwości, jest to lepsze przybliżenie, ale z punktu widzenia domeny razem ma wady - wykazuje undershoot - jedna z wartości jest ujemna, choć oryginalna seria jest nieujemna wszędzie - i dzwoni , gdzie po prawej stronie jest niezerowa, w przeciwieństwie do transformacji falkowej. Z drugiej strony aproksymacja Fouriera poprawnie pokazuje szczyt, a wszystkie punkty mieszczą się w ich poprawnej wartości, chociaż wszystkie punkty mają błąd. W przeciwieństwie do tego przybliżenie falkowe umieszcza pik na lewej połowie, ale nie ma piku w pierwszym punkcie i chociaż jest dokładnie poprawne dla połowy wartości (lokalizacja odbicia), ma błąd dla innych wartości. ${\ Displaystyle 1/4}$ ${\ Displaystyle 1/2}$

Ilustruje to rodzaje kompromisów między tymi transformacjami oraz to, jak pod pewnymi względami DWT zapewnia preferowane zachowanie, szczególnie w przypadku modelowania stanów nieustalonych.

Definicja

Jeden poziom transformacji

DWT sygnału oblicza się, przepuszczając go przez szereg filtrów. Najpierw próbki przechodzą przez filtr dolnoprzepustowy z odpowiedzią impulsową, co powoduje splot dwóch: $x$ $g$

{\ Displaystyle y [n] = (x * g) [n] = \ suma \ limity _ {k = - \ infty} ^ {\ infty} {x [k] g [nk]}}

Sygnał jest również rozkładany jednocześnie za pomocą filtra górnoprzepustowego . Na wyjściach podawane są współczynniki szczegółowe (z filtra górnoprzepustowego) i współczynniki aproksymacji (z filtra dolnoprzepustowego). Ważne jest, aby oba filtry były ze sobą powiązane i są znane jako filtr kwadraturowy . ${\ Displaystyle h}$

Schemat blokowy analizy filtrów

Jednak ponieważ połowa częstotliwości sygnału została usunięta, połowa próbek może zostać odrzucona zgodnie z regułą Nyquista. Wyjście filtru filtru dolnoprzepustowego na powyższym schemacie jest następnie podpróbkowane przez 2 i dalej przetwarzane przez przepuszczenie go ponownie przez nowy filtr dolnoprzepustowy i filtr górnoprzepustowy z połową częstotliwości odcięcia poprzedniego filtru , tj: $g$ $g$ ${\ Displaystyle h}$

{\ Displaystyle y_ {\ operatorname {niski}} [n] = \ suma \ limity _ {k = - \ infty} ^ {\ infty} {x [k] g [2n-k]}}

{\ Displaystyle y_ {\ operatorname {wysoki}} [n] = \ suma \ limity _ {k = - \ infty} ^ {\ infty} {x [k] h [2n-k]}}

Ta dekompozycja zmniejszyła o połowę rozdzielczość czasową, ponieważ tylko połowa każdego wyjścia filtra charakteryzuje sygnał. Jednak każde wyjście ma połowę pasma częstotliwości wejściowego, więc rozdzielczość częstotliwości została podwojona.

Z operatorem podpróbkowania $\downarrow$

(y\downarrow k)[n]=y[kn]

powyższe podsumowanie można zapisać bardziej zwięźle.

{\ Displaystyle y_ {\ operatorname {niski}} = (x * g) \ strzałka w dół 2}

{\ Displaystyle y_ {\ operatorname {wysoki}} = (x * h) \ strzałka w dół 2}

Jednak obliczenie pełnego splotu z późniejszym próbkowaniem w dół spowodowałoby stratę czasu obliczeniowego. $x*g$

Schemat podnoszenia jest optymalizacja gdzie te dwa obliczenia są przeplatane.

Kaskadowanie i banki filtrów

Ta dekompozycja jest powtarzana w celu dalszego zwiększenia rozdzielczości częstotliwości i współczynników aproksymacji rozłożonych za pomocą filtrów górno- i dolnoprzepustowych, a następnie próbkowania w dół. Jest to reprezentowane jako drzewo binarne z węzłami reprezentującymi podprzestrzeń o różnej lokalizacji czasowo-częstotliwościowej. Drzewo jest znane jako bank filtrów .

3-poziomowy bank filtrów

Na każdym poziomie na powyższym schemacie sygnał jest rozkładany na niskie i wysokie częstotliwości. Ze względu na proces dekompozycji sygnał wejściowy musi być wielokrotnością gdzie to liczba poziomów. ${\ Displaystyle 2 ^ {n}}$ ${\ Displaystyle n}$

Na przykład sygnał z 32 próbkami, zakres częstotliwości od 0 do i 3 poziomy dekompozycji, wytwarzane są 4 skale wyjściowe: $f_{n}$

Poziom	Częstotliwości	Próbki
3	${\ Displaystyle 0}$ do ${\ Displaystyle {f_ {n}}/8}$	4
3	${\ Displaystyle {f_ {n}}/8}$ do ${\ Displaystyle {f_ {n}}/4}$	4
2	${\ Displaystyle {f_ {n}}/4}$ do ${\ Displaystyle {f_ {n}}/2}$	8
1	${\ Displaystyle {f_ {n}}/2}$ do $f_{n}$	16

Reprezentacja w dziedzinie częstotliwości DWT

Związek z falką matki

Implementację falek w banku filtrów można interpretować jako obliczanie współczynników falkowych dyskretnego zbioru falek potomnych dla danej falki macierzystej . W przypadku dyskretnej transformacji falkowej falka matka jest przesuwana i skalowana o potęgi dwójki ${\ Displaystyle \ psi (t)}$

${\ Displaystyle \ psi _ {j, k} (t) = {\ Frac {1} {\ sqrt {2 ^ {j}}}} \ psi \ lewo ({\ Frac {t-k2 ^ {j}} {2^{j}}}\prawo)}$

gdzie jest parametrem skali i jest parametrem przesunięcia, które są liczbami całkowitymi. $j$ $k$

Przypomnijmy, że współczynnik falkowy sygnału jest rzutem na falkę i niech będzie sygnałem o długości . W przypadku falki dziecięcej w rodzinie dyskretnej powyżej, ${\ Displaystyle \ gamma}$ $x(t)$ $x(t)$ $x(t)$ ${\ Displaystyle 2 ^ {N}}$

${\ Displaystyle \ gamma _ {jk} = \ inft _ {- \ infty} ^ {\ infty} x (t) {\ Frac {1} {\ sqrt {2 ^ {j}}}} \ psi \ lewo ( {\frac {t-k2^{j}}{2^{j}}}\right)dt}$

Teraz ustal w określonej skali, więc jest to tylko funkcja . W związku z powyższym równaniem można traktować jako splotu o z powiększeniem, odbicie i znormalizowanej wersji falkowej macierzystego , próbkowanego z punktów . Ale to jest dokładnie to, co współczynniki szczegółów dają na poziomie dyskretnej transformacji falkowej. Dlatego dla odpowiedniego doboru i , współczynniki szczegółowe banku filtrów odpowiadają dokładnie współczynnikowi falkowemu dyskretnego zbioru falek potomnych dla danej falki macierzystej . $j$ ${\ Displaystyle \ gamma _ {jk}}$ $k$ ${\ Displaystyle \ gamma _ {jk}}$ $x(t)$ ${\ Displaystyle h (t) = {\ Frac {1} {\ sqrt {2 ^ {j}}}} \ psi \ lewo ({\ Frac {-t} {2 ^ {j}}} \ prawej)}$ ${\ Displaystyle 1,2 ^ {j}, 2 ^ {2 j}, ..., 2 ^ {N}}$ $j$ $h[n]$ $g[n]$ ${\ Displaystyle \ psi (t)}$

Jako przykład rozważmy dyskretną falkę Haara , której falka macierzysta to . Następnie rozszerzoną, odbitą i znormalizowaną wersją tej falki jest , co w rzeczywistości jest górnoprzepustowym filtrem dekompozycji dla dyskretnej transformacji falkowej Haara. ${\ Displaystyle \ psi = [1,-1]}$ ${\ Displaystyle h [n] = {\ Frac {1} {\ sqrt {2}}} [-1,1]}$

Złożoność czasu

Implementacja banku filtrów Discrete Wavelet Transform przyjmuje w pewnych przypadkach tylko O( N ) w porównaniu z O( N log N ) dla szybkiej transformacji Fouriera .

Zauważ, że jeśli i mają stałą długość (tj. ich długość jest niezależna od N), to i każde z nich zajmuje O( N ) czasu. Bank filtrów falkowych wykonuje każdy z tych dwóch splotów O( N ) , a następnie dzieli sygnał na dwie gałęzie o rozmiarze N/2. Ale tylko rekurencyjnie dzieli gałąź górną z konwojowaną (w przeciwieństwie do FFT, która rekurencyjnie dzieli zarówno gałąź górną, jak i dolną). Prowadzi to do następującej relacji nawrotu $g[n]$ $h[n]$ ${\ Displaystyle x * h}$ $x*g$ $g[n]$

{\ Displaystyle T (N) = 2N + T \ lewo ({\ Frac {N} {2}} \ po prawej)}

co prowadzi do czasu O( N ) dla całej operacji, co można wykazać poprzez rozwinięcie szeregu geometrycznego powyższej relacji.

Na przykład dyskretna transformata falkowa Haara jest liniowa, ponieważ w tym przypadku i ma stałą długość 2. $h[n]$ $g[n]$

{\ Displaystyle h [n] = \ lewo [{\ Frac {-{\ sqrt {2}}} {2}}, {\ Frac {\ sqrt {2}} {2}} \ prawej] g [n] =\lewo[{\frac {\sqrt {2}}{2}},{\frac {\sqrt {2}}{2}}\prawo]}

Lokalność falek w połączeniu ze złożonością O( N ) gwarantuje, że transformację można obliczyć online (na zasadzie przesyłania strumieniowego). Ta właściwość jest w ostrym kontraście do FFT, która wymaga dostępu do całego sygnału na raz. Dotyczy to również przekształceń wieloskalowych, a także przekształceń wielowymiarowych (np. 2-D DWT).

Inne przekształcenia

Adam7 , stosowany do usuwania przeplotu w Portable Network Graphics formacie (PNG), to wieloskalowego model danych, który jest podobny do DWT z falki Haara . W przeciwieństwie do DWT, ma określoną skalę – zaczyna się od bloku 8×8 i zamiast decymacji ( filtrowanie dolnoprzepustowe , a następnie próbkowanie w dół) obniża próbkowanie obrazu . W związku z tym oferuje gorsze zachowanie częstotliwości, pokazując artefakty ( pikselację ) na wczesnych etapach, w zamian za prostszą implementację.
Mnożnikowy (lub geometryczna) dyskretnej transformaty falkowej jest wariant, który ma zastosowanie do modelu obserwacyjnym obejmującym interakcje pozytywnym regularnej funkcji i multiplikatywnego niezależnego pozytywnego szumu , z . Oznaczamy transformatę falkową. Ponieważ , standardowe (addytywne) dyskretnej transformaty falkowe jest taki, że , gdy współczynniki szczegółowo , nie mogą być uważane jako rozrzedzony w ogóle ze względu na wpływ na drugim ekspresji. W modelu multiplikatywnym transformacja falkowa jest taka, że „osadzenie” falek w algebrze multiplikatywnej obejmuje uogólnione przybliżenia multiplikatywne i operatory szczegółów: Na przykład, w przypadku falek Haara, aż do współczynnika normalizacji , aproksymacji standardowych ( średnia arytmetyczna ) i szczegóły ( różnice arytmetyczne ) stają się odpowiednio przybliżeniami średniej geometrycznej i różnicami geometrycznymi (szczegóły) przy użyciu . ${\ Displaystyle {\ bf {y}} = f {\ bf {X}}}$ $f$ ${\ Displaystyle X}$ ${\ Displaystyle \ mathbb {E} X = 1}$ ${\ Displaystyle {\ cal {W}}}$ ${\ Displaystyle f {\ bf {X}} = f + {f ({\ bf {X}} -1)}}$ ${\ Displaystyle {\ cal {W ^ {+}}}}$ ${\ Displaystyle {\ cal {W ^ {+}}} {\ bf {y}} = {\ cal {W ^ {+}}} f + {\ cal {W ^ {+}}} {f ({\ bf {X}}-1)},}$ ${\ Displaystyle {\ cal {W ^ {+}}} {f ({\ bf {X}} -1)}}$ $f$ ${\ Displaystyle {\ cal {W ^ {\ razy}}} {\ bf {y}} = \ lewo ({\ cal {W ^ {\ razy}}} f \ prawej) \ razy \ lewo ({\ cal {W^{\times }}}{\bf {X}}\prawo).}$ ${\ Displaystyle \ alfa}$ ${\ Displaystyle {\ cal {W ^ {+}}}}$ ${\ Displaystyle c_ {k} = \ alfa (y_ {k} + y_ {k-1})}$ ${\ Displaystyle d_ {k} = \ alfa (y_ {k}-y_ {k-1})}$ ${\ Displaystyle c_ {k} ^ {\ ast} = (y_ {k} \ razy y_ {k-1}) ^ {\ alfa}}$ ${\ Displaystyle d_ {k} ^ {\ ast} = \ lewo ({\ Frac {y_ {k}} {y_ {k-1}}} \ prawej) ^ {\ alfa}}$ ${\ Displaystyle {\ cal {W ^ {\ razy}}}}$

Przykład kodu

W swojej najprostszej formie DWT jest niezwykle łatwe do obliczenia.

Haar falkowych w Javie :

public static int[] discreteHaarWaveletTransform(int[] input) {
    // This function assumes that input.length=2^n, n>1
    int[] output = new int[input.length];

    for (int length = input.length / 2; ; length = length / 2) {
        // length is the current length of the working area of the output array.
        // length starts at half of the array size and every iteration is halved until it is 1.
        for (int i = 0; i < length; ++i) {
            int sum = input[i * 2] + input[i * 2 + 1];
            int difference = input[i * 2] - input[i * 2 + 1];
            output[i] = sum;
            output[length + i] = difference;
        }
        if (length == 1) {
            return output;
        }

        //Swap arrays to do next iteration
        System.arraycopy(output, 0, input, 0, length);
    }
}

Kompletny kod Java dla 1-D i 2-D DWT przy użyciu falek Haar , Daubechies , Coiflet i Legendre jest dostępny w projekcie open source: JWave . Ponadto można znaleźć tutaj szybko podnoszącą się implementację dyskretnej biortogonalnej transformacji falkowej CDF 9/7 w C , stosowanej w standardzie kompresji obrazu JPEG 2000 (archiwum 5 marca 2012 r.).

Przykład powyższego kodu

Przykład obliczania dyskretnych współczynników falkowych Haara dla sygnału dźwiękowego osoby mówiącej „Kocham falki”. Oryginalny przebieg jest pokazany na niebiesko w lewym górnym rogu, a współczynniki falkowe są pokazane na czarno w prawym górnym rogu. Na dole pokazane są trzy powiększone obszary współczynników falkowych dla różnych zakresów.

Ten rysunek przedstawia przykład zastosowania powyższego kodu do obliczenia współczynników falkowych Haara na przebiegu dźwiękowym. Ten przykład podkreśla dwie kluczowe właściwości transformacji falkowej:

Sygnały naturalne często mają pewien stopień gładkości, co czyni je rzadkimi w domenie falkowej. W tym przykładzie jest znacznie mniej znaczących składowych w domenie falkowej niż w domenie czasu, a większość znaczących składowych jest w kierunku grubszych współczynników po lewej stronie. Stąd naturalne sygnały są ściśliwe w domenie falkowej.
Transformacja falkowa to wielorozdzielcza, pasmowo-przepustowa reprezentacja sygnału. Można to zobaczyć bezpośrednio z definicji banku filtrów dyskretnej transformacji falkowej podanej w tym artykule. W przypadku sygnału o długości współczynniki w zakresie reprezentują wersję oryginalnego sygnału, który znajduje się w paśmie przepustowym . Dlatego przybliżanie tych zakresów współczynników falkowych wygląda tak podobnie w strukturze do oryginalnego sygnału. Zakresy bliższe lewej stronie (większe w powyższym zapisie) są bardziej zgrubnymi reprezentacjami sygnału, natomiast zakresy po prawej reprezentują drobniejsze szczegóły. ${\ Displaystyle 2 ^ {N}}$ ${\ Displaystyle [2 ^ {Nj}, 2 ^ {N-j + 1}]}$ ${\ Displaystyle \ lewo [{\ Frac {\ pi} {2 ^ {j}}}, {\ Frac {\ pi {2 ^ {j-1}}} \ prawej]}$ $j$

Zobacz też

Bibliografia

Linki zewnętrzne

WaveLab Stanforda w programie Matlab
libdwt , wieloplatformowa biblioteka DWT napisana w C
Zwięzłe wprowadzenie do falek autorstwa René Puschingera

^ Prasad, Achilesz; Maan, Jeetendrasingh; Verma, Sandeep Kumar (2021). "Transformacje Wavelet powiązane z indeksem transformacji Whittakera" . Metody matematyczne w naukach stosowanych . nie dotyczy (nie dotyczy). doi : 10.1002/mma.7440 . ISSN 1099-1476 .

[26] Prasad, Achilesz; Maan, Jeetendrasingh; Verma, Sandeep Kumar (2021). "Transformacje Wavelet powiązane z indeksem transformacji Whittakera" . Metody matematyczne w naukach stosowanych . nie dotyczy (nie dotyczy). doi : 10.1002/mma.7440 . ISSN 1099-1476 .

Languages

In other projects