Diskrétní vlnková transformace

Z Wikipedie, otevřené encyklopedie

Skočit na: Navigace, Hledání

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 2n čí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 2n − 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ě. V jejích seminárních pracích odvozuje rodinu vlnek, první z nich je Haarův wavelet.

Mezi další formy diskrétní vlnkové transformace patří stacionární vlnková transformace (kde je vynecháno podvzorkování), paketová vlnková transformace (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ší použití DWT je pro 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.

Obsah

[editovat] Definice

[editovat] Jeden stupeň transformace

DWT signálu x je spočítána jeho průchodem skrze sérii filtrů. Nejprve se vzorky nechají projít skrze dolní propusť (low pass filtr) s impulzní odezvou g vyplývající z konvoluce:

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

Signál je také současně dekomponován použitím horní propusti (high pass filtru) h. Výstupy dávají detailní (podrobné) koeficienty (z horní propusti) a aproximované (přibližné) koeficienty (z dolní propusti). Je důležité, že tyto dva filtry jsou vzájemně komplementární a splňují další podmínky – označují se jako kvadraturně zrcadlové filtry.

Polovina frekvencí signálu byla odebrána a tedy polovina vzorků může být s využitím Nyquistova pravidla zahozena. Výstupy filtru 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] g[2 n - k]}
y_{\mathrm{high}} [n] = \sum\limits_{k = - \infty }^\infty {x[k] h[2 n - k]}
Blokový diagram analýzy filtru


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.

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

Počítání celé konvoluce x * g s následným podvzorkováním může mrhat výpočetním časem. Optimalizace, kde jsou tyto dva výpočty prokládány, se označuje jako lifting.

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

K dalšímu zvýšení frekvenčního rozlišení se tato dekompozice opakuje. Což je 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ů.

3 stupňová banka filtrů


Na každém stupni v diagramu výše je signál rozložen do nízkých (low) a vysokých (high) frekvencí. Kvůli procesu dekompozice musí být vstupní signál násobkem 2n, kde n je počet stupňů.

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

Úrověň Frekvence Vzorky
3 0 až fn / 8 4
fn / 8 až fn / 4 4
2 fn / 4 až fn / 2 8
1 fn / 2 až fn 16


Frekvenční doména reprezentace DWT


[editovat] Příklad kódu

Haarův wavelet, jazyk C:

[editovat] Dopředná

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);
	}
}

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

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

[editovat] Reference

[editovat] Související články

Citováno z „http://cs.wikipedia.org/wiki/Diskr%C3%A9tn%C3%AD_vlnkov%C3%A1_transformace“