Diskret Wavelet Transform

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 20 januari 2018; kontroller kräver 4 redigeringar .

I numerisk och funktionell analys avser diskreta wavelet-transformationer (DWTs) wavelet-transformer där wavelets representeras av diskreta signaler (sampel).

Den första DWT skapades av den ungerske matematikern Alfred Haar . För en insignal representerad av en array med 2n tal, grupperar Haar wavelet-transformen helt enkelt elementen med 2 och summerar och skiljer sig från dem. Grupperingen av summor utförs rekursivt för att bilda nästa nivå av nedbrytning. Resultatet är 2 n −1 skillnad och 1 totalsumma.

Denna enkla DWT illustrerar de allmänna användbara egenskaperna hos wavelets. För det första kan omvandlingen göras i verksamheter. För det andra sönderdelar den inte bara signalen till någon form av frekvensband (genom att analysera den på olika skalor), utan representerar också tidsdomänen, det vill säga ögonblicken för förekomsten av vissa frekvenser i signalen. Tillsammans kännetecknar dessa egenskaper den snabba wavelet-transformen, ett möjligt alternativ till den vanliga snabba Fourier-transformen . När villkoret för slumpmässighet för signalen X accepteras, beräknas spektraldensiteten för dess amplituder Y baserat på Yates-algoritmen: matris Y = matris(± X ), den omvända matrisen X = matris (± Y ) är också sann . $n\log _{2}(n)$

Den vanligaste uppsättningen av diskreta wavelet-transformationer formulerades av den belgiska matematikern Ingrid Daubechies 1988. Den är baserad på användningen av återfallsrelationer för att beräkna allt mer exakta sampel av den implicit givna modervågsfunktionen med fördubbling av upplösningen när man går till nästa nivå (skala). I sitt framstående verk härleder Daubechies en familj av wavelets, varav den första är Haar wavelet. Sedan dess har intresset för detta område vuxit snabbt, vilket har lett till skapandet av många ättlingar till den ursprungliga Daubechies wavelet-familjen.

Andra former av diskret wavelet-transform inkluderar icke-decimerad wavelet-transform (där ingen signaldecimering utförs), Newland-transform (där en ortonormal wavelet-bas härleds från speciellt konstruerade filter av typen "top-hat" i frekvensdomänen). Packet wavelet-transformer är också relaterade till DWT. En annan form av DWT är den komplexa wavelet-transformen.

Den diskreta wavelet-transformen har många tillämpningar inom naturvetenskap, teknik och matematik (inklusive tillämpade sådana). DWT används mest vid signalkodning, där transformeringsegenskaper används för att minska redundans i representationen av diskreta signaler, ofta som det första steget i datakomprimering.

Definition

En nivå av transformation

DWP för signalen erhålls genom att applicera en uppsättning filter. Först leds signalen genom ett lågpassfilter (lågpass) med ett impulssvar och en faltning erhålls : $x$ $g$

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

Samtidigt bryts signalen ned med hjälp av ett högpassfilter (högpass) . Resultatet är detaljkoefficienter (efter högpassfiltret) och approximationskoefficienter (efter lågpassfiltret). Dessa två filter är relaterade och kallas kvadraturspegelfilter (QMF). $h$

Eftersom hälften av signalens frekvensområde filtrerades, kan signalräkningen, enligt Kotelnikov-satsen , tunnas ut med två gånger:

y_{{{\mathrm {låg}}}}[n]=\summa \limits _{{k=-\infty }}^{\infty }{x[k]g[2n-k]}

y_{{{\mathrm {hög}}}}[n]=\summa \limits _{{k=-\infty }}^{\infty }{x[k]h[2n-k]}

Denna expansion halverade tidsupplösningen på grund av signaldecimering. Var och en av de resulterande signalerna representerar dock halva frekvensbandbredden av den ursprungliga signalen, så frekvensupplösningen fördubblas.

Använda gallringsoperatorn $\nedåtpil$

(y\nedåt k)[n]=y[kn]

ovanstående summor kan skrivas kortare:

y_{{{\mathrm {låg}}}}=(x*g)\nedåtpil 2

y_{{{\mathrm {hög}}}}=(x*h)\nedåtpil 2

Att beräkna en fullständig faltning följt av gallring är ett slöseri med beräkningsresurser. $x*g$

Lyftschemat är en optimering som bygger på att dessa två beräkningar alterneras.

Kaskad- och filterbanker

Denna nedbrytning kan upprepas flera gånger för att ytterligare öka frekvensupplösningen med ytterligare decimering av koefficienterna efter lågpass- och högpassfiltrering. Detta kan representeras som ett binärt träd, där löv och noder motsvarar utrymmen med olika tidsfrekvenslokalisering. Detta träd representerar strukturen för banken (kammen) av filter .

På varje nivå i diagrammet ovan bryts signalen upp i låga och höga frekvenser. På grund av den dubbla decimeringen måste signallängden vara en multipel av , där är antalet nedbrytningsnivåer. $2^{n}$ $n$

Till exempel, för en 32-samplingssignal med ett frekvensområde på 0 till 3 nivåer, kommer expansionen att ge 4 utgångar på olika skalor: $f_n$

Nivå	Frekvenser	Signallängd
3	$0$ … ${{f_{n}}}/8$	fyra
3	${{f_{n}}}/8$ … ${{f_{n}}}/4$	fyra
2	${{f_{n}}}/4$ … ${{f_{n}}}/2$	åtta
ett	${{f_{n}}}/2$ … $f_n$	16

Programexempel

Haars algoritm

Ett exempel på en snabb endimensionell wavelet-transform, med användning av Haar wavelet , för en uppsättning initiala data av storlek 2 N (antal filtersteg är N) i C#:

public static List < Double > DirectTransform ( List < Double > SourceList ) { if ( SourceList . Count == 1 ) return SourceList ; List < Double > RetVal = new List < Double >(); List < Double > TmpArr = new List < Double >(); for ( int j = 0 ; j < SourceList . Count - 1 ; j += 2 ) { RetVal . Lägg till (( SourceList [ j ] - SourceList [ j + 1 ]) / 2.0 ); TmpArr . Lägg till (( SourceList [ j ] + SourceList [ j + 1 ]) / 2.0 ); } RetVal . AddRange ( DirectTransform ( TmpArr )); returnera RetVal ; }

På liknande sätt, ett exempel på den inversa wavelet-transformen:

public static List < Double > InverseTransform ( List < Double > SourceList ) { if ( SourceList . Count == 1 ) return SourceList ; List < Double > RetVal = new List < Double >(); List < Double > TmpPart = new List < Double >(); för ( int i = SourceList . Count / 2 ; i < SourceList . Count ; i ++ ) TmpPart . Lägg till ( SourceList [ i ]); List < Double > SecondPart = InverseTransform ( TmpPart ); for ( int i = 0 ; i < SourceList . Count / 2 ; i ++ ) { RetVal . Lägg till ( SecondPart [ i ] + SourceList [ i ]); RetVal . Lägg till ( SecondPart [ i ] - SourceList [ i ]); } returnera RetVal ; }

Tvådimensionell wavelet-transform

Vid utvecklingen av den nya JPEG-2000- standarden valdes wavelet-transformen för bildkomprimering. Wavelet-transformen i sig komprimerar inte data, utan tillåter att ingångsbilden transformeras på ett sådant sätt att dess redundans kan reduceras utan en märkbar försämring av bildkvaliteten.

Se även

Kontinuerlig Wavelet Transform

Anteckningar

↑ Schema på ryska

Litteratur

Stephane Mallat. En Wavelet-rundtur av signalbehandling
Zakharov S. I. , Kholmskaya A. G. Förbättring av effektiviteten vid bearbetning av vibrations- och brussignaler under testning av mekanismer // Vestnik mashinostroeniya : zhurnal. - M . : Mashinostroenie, 2001. - Nr 10 . - S. 31-32 . — ISSN 0042-4633 .

Länkar

Sensor för vibroakustik och vibrodiagnostik av produkter: Pat nr. 95116U1, IPC G 01 H 1/08.
Snabb diskret biortogonal CDF 9/7 wavelet framåt och invers transformering (liftimplementering) är en C-implementering för snabb lyft av en diskret biortogonal CDF 9/7 wavelet som används i JPEG-2000 -bildkomprimeringsalgoritmen .
En ny trend i konvertering av data från sensorer av mekaniska och fysiska storheter. M: Maskinteknik//Bulletin för maskinteknik, 2004, nr 4, s.78.
Yuen Ch., Beacham K., Robinson J. Mikroprocessorsystem och deras tillämpning inom signalbehandling. M: Radio och kommunikation. 1986. 296 sid.
Dhonson N., Lyon F. Statistik och planering av experiment inom teknik och vetenskap. Experimentera planeringsmetoder. M: Fred. 1981. 512 sid.
Brokh ET Användning av mätsystem av Brüel & Kjær för analys av mekaniska svängningar och stötar. Söborg; Larsen och son. 1973. 235 sid.
Bute P.-A. Mätning av chockimpulser. En ny metod för att övervaka tillståndet av rullningslager under drift. Rapportera. SKF företag. 1971. 7 sid.
Kharkevich A. A. Spektra och analys. M: Fizmatgiz.1963. 432 sid.

Kompressionsmetoder _

Teori

Information	Egen Ömsesidig Entropi Villkorlig entropi Komplexitet Redundans
Enheter	Bit Nat Knapra Hartley Hartley formel

Förlust mindre

Entropikompression	Asymmetriska talsystem Huffman algoritm Adaptiv Huffman-algoritm Shannon-Fano algoritm Shannons algoritm Aritmetisk kodning ( intervall ) Golomb-koder Delta Universell kod Elias fibonacci
Ordboksmetoder	RLE Töm luften LZ ( LZ77/LZ78 LZSS LZW LZWL LZO LZMA LZX LZRW LZJB LZT LZ4 Brotli zstandard )
Övrig	RLE CTW BWT MTF PPM DMC

Audio

Teori	Veck PCM Aliasing Provtagning Kotelnikovs teorem
Metoder	LPC LAR LSP WLPC CELP ACELP En lag μ-lag ADPCM MDCT Fouriertransform Psykoakustisk modell
Övrig	Ljudkompressor Talkompression Bandkodning

Bilder

Villkor	färg rymd Pixel Mättnad delsampling Kompressionsartefakter
Metoder	RLE DPCM fraktal vågkomponent EZW SPIHT LP PrEP PCL
Övrig	Bithastighet Standard testbild PSNR Kvantisering

Video

Villkor	Videoegenskaper Ram Ramtyper Videokvalitét
Metoder	Rörelsekompensation PrEP Kvantisering vågkomponent
Övrig	Video codec Rate distortion theory CBR ABR VBR