Diskrétní vlnková transformace

Technology

12 hours ago

Author

Diskrétní vlnková transformace ( zkratkou DWT) je v numerické a funkcionální analýze transformace odvozená z vlnkové transformace pro diskrétní vlnky (wavelety).

První DWT byla objevena maďarským matematikem jménem Alfréd Haar. Pro vstup reprezentovaný seznamem 2^n čísel je Haarova vlnková transformace považována za nejjednodušší spárování (tvořit pár) vstupních hodnot - uložením rozdílu a předáním součtu (do dalšího stupně transformace). +more Tento proces je opakován rekurzivně (na součty). Konečný výsledek transformace je 2^n-1 rozdílů a jeden celkový průměrný součet.

Nejznámější diskrétní vlnkové transformace byly formulovány belgickou matematičkou jménem Ingrid Daubechies v roce 1988. Tyto formulace jsou založeny na použití rekurentních vztahů ke generování postupně se zjemňujících diskrétních vzorků původní mateřské funkce. +more Každé rozlišení je dvojnásobkem předchozího stupně. Ve svých pracích odvozuje rodinu vlnek, první z nich je Haarova vlnka.

Mezi další formy diskrétní vlnkové transformace patří stacionární vlnková transformace (kde je vynecháno podvzorkování), paketová vlnková transformace (svazková, waveletové balíčky, rozkládá se výstup horní i dolní propusti) a např. komplexní vlnková transformace.

Diskrétní vlnková transformace má mnoho aplikací ve vědě, strojírenství, matematice a informatice. Nejvýznamnější je použití DWT ke kódování signálu, kde jsou vlastnosti této transformace využívány k reprezentaci diskrétního signálu ve více redundantních formách, často jako předběžná úprava pro kompresi dat.

Definice

Jeden stupeň transformace

DWT signálu x lze spočíst jeho průchodem skrze řetězec filtrů. Nejprve se vzorky nechají projít skrze dolní propust s impulzní odezvou h vyplývající z konvoluce:

: y[n] = (x * h)[n] = \sum\limits_{k = - \infty }^\infty {x[k] h[n - k]}

Signál je také současně rozložen s použitím horní propusti g. Výstupy dávají podrobné (detailní) koeficienty (z horní propusti) a přibližné (aproximované) koeficienty (z dolní propusti). +more Je důležité, že tyto dva filtry jsou vzájemně komplementární a také umožňují perfektní rekonstrukci signálu - označují se jako kvadraturně zrcadlové filtry.

Polovina frekvencí signálu byla v každé větvi odebrána a tedy polovina vzorků může být s využitím Nyquistova pravidla zahozena. Výstupy filtrů jsou tudíž dále podvzorkovány dvěma (každý druhý vzorek je zahozen):

: y_{\mathrm{low}} [n] = \sum\limits_{k = - \infty }^\infty {x[k] h[2 n - k]} : y_{\mathrm{high}} [n] = \sum\limits_{k = - \infty }^\infty {x[k] g[2 n - k]}

Jeden stupeň DWT

S podvzorkovacím operátorem \downarrow

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

mohou být výše uvedené rovnice zapsány stručněji jako

: y_{\mathrm{low}} = (x*h)\downarrow 2 : y_{\mathrm{high}} = (x*g)\downarrow 2 .

Počítání celé konvoluce (x*h)\downarrow 2\, a (x*g)\downarrow 2\, může mrhat výpočetním výkonem. Rychlý algoritmus, kde jsou tyto dva výpočty prokládány, se označuje jako . +more V obou případech má však diskrétní vlnková transformace má lineární časovou složitost. To platí i v případě více úrovní rozkladu a vícerozměrných signálů (např. obrázků).

Kaskádování a banky filtrů

K dalšímu zvýšení frekvenčního rozlišení se tento rozklad opakuje. To může být znázorněno jako binární strom s uzly reprezentujícími podprostor s rozdílným umístěním času/frekvence. +more Takovýto strom se označuje jako banka filtrů.

Tři stupně DWT

Na každém stupni v diagramu výše je signál rozložen do nízkých a vysokých frekvencí. Pro úplný rozklad musí být vstupní signál násobkem 2^n, kde n je počet stupňů rozkladu.

Například signál s 32 vzorky, frekvenčním rozsahem 0 až f_n a 3 úrovněmi rozkladu, výstupem jsou 4 různá měřítka signálu:

Úroveň . Frekvence . +more Vzorky
3 \| 0 až /8 \| 4
3 \| 0 až /8 \| 4
2 \| /4 až /2 \| 8
1 \| /2 až f_n \| 16

Pokrytí frekvenčního spektra signálu koeficienty DWT

Příklad kódu

Diskrétní vlnková transformace s Haarovou vlnkou (bez normalizace) v jazyce C:

Dopředná

Dopředná jednorozměrná transformace:

void fwt(const double *const_input, double *output) { static double input[LENGTH]; memcpy(input, const_input, sizeof(double)*LENGTH); for (int length = LENGTH >> 1; ; length >>= 1) { for (int i = 0; i

Zpětná

Zpětná (inverzní) jednorozměrná transformace:

void iwt(const double *const_input, double *output) { static double input[LENGTH]; memcpy(input, const_input, sizeof(double)*LENGTH); for (int length = 1; ; length