Diskrétní Wavelet Transform

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 20. ledna 2018; kontroly vyžadují 4 úpravy .

V numerické a funkční analýze se diskrétní vlnkové transformace (DWT) týkají vlnkových transformací, ve kterých jsou vlnky reprezentovány diskrétními signály (vzorky).

První DWT byl koncipován maďarským matematikem Alfredem Haarem . Pro vstupní signál reprezentovaný polem čísel 2n Haarova vlnková transformace jednoduše seskupuje prvky po 2 a sčítá a liší se od nich. Seskupování součtů se provádí rekurzivně za účelem vytvoření další úrovně rozkladu. Výsledkem je 2 n −1 rozdílu a 1 celkový součet.

Tento jednoduchý DWT ilustruje obecné užitečné vlastnosti vlnek. Za prvé, transformace může být provedena v operacích. Za druhé, nejenže rozkládá signál na nějaké zdání frekvenčních pásem (analýzou na různých měřítcích), ale také představuje časovou doménu, tedy okamžiky výskytu určitých frekvencí v signálu. Společně tyto vlastnosti charakterizují rychlou vlnkovou transformaci, možnou alternativu k obvyklé rychlé Fourierově transformaci . Při akceptování podmínky náhodnosti signálu X je spektrální hustota jeho amplitud Y vypočtena na základě Yatesova algoritmu: matice Y =matrix(± X ), platí i reverzní matice X =matrix(± Y ) . $n\log _{2}(n)$

Nejběžnější sadu diskrétních vlnkových transformací formulovala belgická matematička Ingrid Daubechies v roce 1988. Je založena na využití rekurentních vztahů k výpočtu stále přesnějších vzorků implicitně dané mateřské vlnkové funkce se zdvojnásobením rozlišení při přechodu na další úroveň (škálu). Ve své klíčové práci Daubechies odvozuje rodinu vlnek, z nichž první je vlnka Haar. Od té doby zájem o tuto oblast rychle vzrostl, což vedlo k vytvoření četných potomků původní rodiny vlnek Daubechies.

Mezi další formy diskrétní vlnkové transformace patří nedecimovaná vlnková transformace (kde se neprovádí decimace signálu), Newlandova transformace (kde je ortonormální vlnková báze odvozena ze speciálně konstruovaných filtrů typu „top-hat“ ve frekvenční doméně). Paketové vlnkové transformace také souvisí s DWT. Další formou DWT je komplexní vlnková transformace.

Diskrétní vlnková transformace má mnoho aplikací v přírodních vědách, inženýrství a matematice (včetně aplikovaných). DWT se nejvíce používá v kódování signálů, kde se vlastnosti transformace používají ke snížení redundance při reprezentaci diskrétních signálů, často jako první krok při kompresi dat.

Definice

Jedna úroveň transformace

DWP signálu se získá aplikací sady filtrů. Nejprve signál prochází dolní propustí (dolní propust) s impulsní odezvou a získá se konvoluce : $X$ $G$

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

Zároveň je signál rozložen pomocí horní propusti (horní propusti) . Výsledkem jsou podrobné koeficienty (za horní propustí) a aproximační koeficienty (za dolní propustí). Tyto dva filtry spolu souvisí a nazývají se kvadraturní zrcadlové filtry (QMF). $h$

Vzhledem k tomu, že polovina frekvenčního rozsahu signálu byla filtrována, lze podle Kotelnikovovy věty počet signálů ztenčit 2krát:

y_{{{\mathrm {low}}}}[n]=\sum \limits _{{k=-\infty }}^{\infty }{x[k]g[2n-k]}

y_{{{\mathrm {high}}}}[n]=\součet \limits _{{k=-\infty }}^{\infty }{x[k]h[2n-k]}

Toto rozšíření snížilo časové rozlišení na polovinu kvůli decimaci signálu. Každý z výsledných signálů však představuje polovinu frekvenčního pásma původního signálu, takže frekvenční rozlišení je dvojnásobné.

Pomocí operátoru probírky $\šipka dolů$

(y\šipka dolů k)[n]=y[kn]

výše uvedené součty lze psát kratší:

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

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

Počítání úplné konvoluce s následným ztenčováním je plýtváním výpočetními zdroji. $x*g$

Schéma zdvihu je optimalizace založená na střídání těchto dvou výpočtů.

Kaskádové a filtrační banky

Tento rozklad lze několikrát opakovat pro další zvýšení frekvenčního rozlišení s dalším decimováním koeficientů po filtraci dolní a horní propusti. To lze znázornit jako binární strom, kde listy a uzly odpovídají prostorům s různou časově-frekvenční lokalizací. Tento strom představuje strukturu banky (hřebenu) filtrů .

Na každé úrovni výše uvedeného diagramu je signál rozložen na nízké a vysoké frekvence. Kvůli dvojité decimaci musí být délka signálu násobkem , kde je počet úrovní rozkladu. $2^{n}$ $n$

Například pro 32vzorkový signál s frekvenčním rozsahem 0 až 3 úrovně poskytne rozšíření 4 výstupy v různých měřítcích: $f_n$

Úroveň	Frekvence	Délka signálu
3	$0$ … ${{f_{n}}}/8$	čtyři
3	${{f_{n}}}/8$ … ${{f_{n}}}/4$	čtyři
2	${{f_{n}}}/4$ … ${{f_{n}}}/2$	osm
jeden	${{f_{n}}}/2$ … $f_n$	16

Příklad programu

Haarův algoritmus

Příklad rychlé jednorozměrné vlnkové transformace pomocí Haarovy vlnky pro pole počátečních dat o velikosti 2 N (počet stupňů filtru je N) v C#:

public static List < Double > DirectTransform ( List < Double > SourceList ) { if ( SourceList . Count == 1 ) return SourceList ; List < Double > RetVal = new List < Double >(); Seznam < Double > TmpArr = new List < Double >(); for ( int j = 0 ; j < SourceList . Počet - 1 ; j += 2 ) { RetVal . Přidat (( SourceList [ j ] - SourceList [ j + 1 ]) / 2.0 ); TmpArr . Přidat (( SourceList [ j ] + SourceList [ j + 1 ]) / 2.0 ); } RetVal . AddRange ( DirectTransform ( TmpArr )); return RetVal ; }

Podobně příklad inverzní vlnkové transformace:

public static List < Double > InverseTransform ( List < Double > SourceList ) { if ( SourceList . Count == 1 ) return SourceList ; List < Double > RetVal = new List < Double >(); Seznam < Double > TmpPart = new List < Double >(); for ( int i = SourceList . Count / 2 ; i < SourceList . Count ; i ++ ) TmpPart . Přidat ( SourceList [ i ]); Seznam < Double > SecondPart = InverseTransform ( TmpPart ); for ( int i = 0 ; i < SourceList . Počet / 2 ; i ++ ) { RetVal . Přidat ( Druhá část [ i ] + Zdrojový seznam [ i ]); RetVal . Přidat ( SecondPart [ i ] - SourceList [ i ]); } return RetVal ; }

Dvourozměrná vlnková transformace

Při vývoji nového standardu JPEG-2000 byla pro kompresi obrazu zvolena vlnková transformace. Samotná vlnková transformace data nekomprimuje, ale umožňuje transformaci vstupního obrazu takovým způsobem, že lze snížit jeho redundanci bez znatelného zhoršení kvality obrazu.

Viz také

Spojitá vlnová transformace

Poznámky

↑ Schémata v ruštině

Literatura

Stephanem Mallatem. Waveletová prohlídka zpracování signálu
Zakharov S. I. , Kholmskaya A. G. Zlepšení účinnosti zpracování vibračních a hlukových signálů během testování mechanismů // Vestnik mashinostroeniya : zhurnal. - M .: Mashinostroenie, 2001. - č. 10 . - S. 31-32 . — ISSN 0042-4633 .

Odkazy

Snímač vibroakustiky a vibrodiagnostiky výrobků: Pat č. 95116U1, IPC G 01 H 1/08.
Rychlá diskrétní biortogonální vlnka CDF 9/7 vpřed a inverzní transformace (implementace liftingu) je implementace C pro rychlé zvednutí diskrétní biortogonální vlnky CDF 9/7 používané v algoritmu komprese obrazu JPEG-2000 .
Nový trend v převodu dat ze snímačů mechanických a fyzikálních veličin. M: Strojírenství//Bulletin strojírenství, 2004, č. 4, s.78.
Yuen Ch., Beacham K., Robinson J. Mikroprocesorové systémy a jejich aplikace při zpracování signálů. M: Rádio a komunikace. 1986. 296 str.
Dhonson N., Lyon F. Statistika a plánování experimentů v technice a vědě. Metody plánování experimentů. M: Mír. 1981. 512 s.
Brokh ET Využití měřicích systémů Brüel & Kjær k analýze mechanických kmitů a rázů. Söborg; Larsen a syn. 1973. 235 s.
Bute P.-A. Měření rázových (šokových) impulsů. Nová metoda sledování stavu valivých ložisek za provozu. Zpráva. společnost SKF. 1971. 7p.
Charkevich A. A. Spektra a analýza. M: Fizmatgiz.1963. 432 str.

Kompresní metody

Teorie

Informace	Vlastní Vzájemné Entropie Podmíněná entropie Složitost Nadbytek
Jednotky	Bit Nat Okusovat Hartley Hartleyho vzorec

Bezztrátový

Entropická komprese	Asymetrické číselné soustavy Huffmanův algoritmus Adaptivní Huffmanův algoritmus Shannon-Fano algoritmus Shannonův algoritmus Aritmetické kódování ( interval ) Golombovy kódy Delta Univerzální kód Eliáš fibonacci
Slovníkové metody	RLE Vyfouknout LZ ( LZ77/LZ78 LZSS LZW LZWL LZO LZMA LZX LZRW LZJB LZT LZ4 Brotli zstandard )
jiný	RLE CTW BWT MTF PPM DMC

Zvuk

Teorie	Konvoluce PCM Aliasing Vzorkování Kotelnikovova věta
Metody	LPC LAR LSP WLPC CELP ACELP Zákon μ-zákon ADPCM MDCT Fourierova transformace Psychoakustický model
jiný	Audio kompresor Komprese řeči Pásmové kódování

snímky

Podmínky	barevný prostor Pixel Saturační podvzorkování Kompresní artefakty
Metody	RLE DPCM fraktál vlnka EZW SPIHT LP Přípravka PCL
jiný	Bitová rychlost Standardní testovací obrázek PSNR Kvantování

Video

Podmínky	Vlastnosti videa Rám Typy rámů Kvalita videa
Metody	Kompenzace pohybu Přípravka Kvantování vlnka
jiný	Video kodek Teorie zkreslení sazby CBR ABR VBR