Diskrétní vlnková transformace

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání
Na tento článek je přesměrováno heslo DWT. Možná hledáte: DWT (jednotka).

Diskrétní vlnková transformace (anglicky discrete wavelet transform, 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). 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. Každé rozlišení je dvojnásobkem předchozího stupně. Ve svých pracech 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[editovat | editovat zdroj]

Jeden stupeň transformace[editovat | editovat zdroj]

DWT signálu x lze spočíst jeho průchodem skrze řetězec filtrů. Nejprve se vzorky nechají projít skrze dolní propust (low pass filter) 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 (high pass filter) g. Výstupy dávají podrobné (detailní) koeficienty (z horní propusti) a přibližné (aproximované) koeficienty (z dolní propusti). 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\, s následným podvzorkováním 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 lifting.

Kaskádování a banky filtrů[editovat | editovat zdroj]

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. 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 (low) a vysokých (high) 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 Vzorky
3 0{{f_n}}/8 4
{{f_n}}/8{{f_n}}/4 4
2 {{f_n}}/4{{f_n}}/2 8
1 {{f_n}}/2f_n 16
Pokrytí frekvenčního spektra signálu koeficienty DWT

Příklad kódu[editovat | editovat zdroj]

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

Dopředná[editovat | editovat zdroj]

Dopředná (forward) 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 < length; i++)
		{
			double sum = (input[i*2] + input[i*2+1])/2;
			double difference = (input[i*2] - input[i*2+1])/2;
			output[i] = sum;
			output[length+i] = difference;
		}
		if(length == 1) 
			return;
		memcpy(input, output, sizeof(double)*length);
	}
}

Zpětná[editovat | editovat zdroj]

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 <<= 1)
	{
		for(int i = 0; i < length; i++)
		{
			output[i*2] = (input[i] + input[length+i]);
			output[i*2+1] = (input[i] - input[length+i]);
		}
		if(length == LENGTH >> 1)
			return;
		memcpy(input, output, sizeof(double)*length*2);
	}
}

Pozn. Rychlá implementace (pomocí schématu lifting) diskrétní vlnkové transformace s biortogonální vlnkou CDF 9/7 v jazyce C (použitá mj. ve standardu JPEG 2000) je k dispozici zde.

Literatura[editovat | editovat zdroj]

  • MALLAT, Stéphane. A Wavelet Tour of Signal Processing: The Sparse Way. With contributions from Gabriel Peyré. 3. vyd. [s.l.] : Academic Press, c2009. xx, 805 s. ISBN 9780123743701. (anglicky) 
  • ADDISON, Paul S.. The Illustrated Wavelet Transform Handbook: Introductory Theory and Applications in Science, Engineering, Medicine and Finance. New York : Taylor & Francis, 2002. xiii, 353 s. ISBN 9780750306928. (anglicky) 
  • KOZUMPLÍK, Jiří. Vlnkové transformace a jejich využití pro filtraci signálů EKG. Brno : VUTIUM, 2005. 81 s. ISSN 1213-418X. Dostupné online.  

Související články[editovat | editovat zdroj]

Reference[editovat | editovat zdroj]

V tomto článku byl použit překlad textu z článku Discrete wavelet transform na anglické Wikipedii.