Diskret Wavelet Transform

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 20. januar 2018; checks kræver 4 redigeringer .

I numerisk og funktionel analyse refererer diskrete wavelet-transformationer (DWT'er) til wavelet-transformationer, hvor wavelets er repræsenteret af diskrete signaler (samples).

Den første DWT blev udtænkt af den ungarske matematiker Alfred Haar . For et inputsignal repræsenteret af en matrix af 2n tal, grupperer Haar wavelet-transformationen simpelthen elementerne med 2 og summerer og adskiller sig fra dem. Grupperingen af summer udføres rekursivt for at danne det næste niveau af dekomponering. Resultatet er 2 n −1 forskel og 1 total sum.

Denne simple DWT illustrerer de generelle nyttige egenskaber ved wavelets. For det første kan transformationen ske i operationer. For det andet dekomponerer det ikke kun signalet i et eller andet udseende af frekvensbånd (ved at analysere det på forskellige skalaer), men repræsenterer også tidsdomænet, det vil sige tidspunkterne for forekomsten af visse frekvenser i signalet. Tilsammen karakteriserer disse egenskaber den hurtige wavelet-transformation, et muligt alternativ til den sædvanlige hurtige Fourier-transformation . Når man accepterer betingelsen om tilfældighed af signalet X , beregnes spektraltætheden af dets amplituder Y baseret på Yates-algoritmen: matrix Y = matrix (± X ), den omvendte matrix X = matrix (± Y ) er også sand . $n\log _{2}(n)$

Det mest almindelige sæt af diskrete wavelet-transformationer blev formuleret af den belgiske matematiker Ingrid Daubechies i 1988. Den er baseret på brugen af gentagelsesrelationer til at beregne stadig mere nøjagtige prøver af den implicit givne moder-wavelet-funktion med fordobling af opløsningen, når man går til næste niveau (skala). I sit skelsættende arbejde udleder Daubechies en familie af wavelets, hvoraf den første er Haar wavelet. Siden da er interessen for dette område vokset hurtigt, hvilket har ført til oprettelsen af adskillige efterkommere af den originale Daubechies wavelet-familie.

Andre former for diskret wavelet-transformation omfatter ikke-decimeret wavelet-transformation (hvor ingen signaldecimering udføres), Newland-transformation (hvor en ortonormal wavelet-basis er afledt af specielt konstruerede "top-hat"-type filtre i frekvensdomænet). Pakkebølgetransformationer er også relateret til DWT. En anden form for DWT er den komplekse wavelet-transformation.

Den diskrete wavelet-transformation har mange anvendelser inden for naturvidenskab, teknik og matematik (inklusive anvendte). DWT er mest udbredt i signalkodning, hvor transformationsegenskaber bruges til at reducere redundans i repræsentationen af diskrete signaler, ofte som det første trin i datakomprimering.

Definition

Et transformationsniveau

Signalets DWP opnås ved at anvende et sæt filtre. Først sendes signalet gennem et lavpas (lavpas) filter med en impulsrespons , og en foldning opnås : $x$ $g$

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

Samtidig dekomponeres signalet ved hjælp af et højpas (højpas) filter . Resultatet er detaljekoefficienter (efter højpasfilteret) og tilnærmelseskoefficienter (efter lavpasfilteret). Disse to filtre er relaterede og kaldes kvadraturspejlfiltre (QMF). $h$

Da halvdelen af signalets frekvensområde blev filtreret, kan signaltallet ifølge Kotelnikov-sætningen fortyndes 2 gange:

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

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

Denne udvidelse halverede tidsopløsningen på grund af signaldecimering. Hvert af de resulterende signaler repræsenterer dog halvdelen af frekvensbåndbredden af det originale signal, så frekvensopløsningen fordobles.

Brug af udtyndingsoperatoren $\pil ned$

(y\pil ned k)[n]=y[kn]

ovenstående summer kan skrives kortere:

y_{{{\mathrm {lav}}}}=(x*g)\pil ned 2

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

At beregne en fuld foldning efterfulgt af udtynding er spild af beregningsressourcer. $x*g$

Løfteordningen er en optimering baseret på vekslende mellem disse to beregninger.

Kaskade- og filterbanker

Denne dekomponering kan gentages flere gange for yderligere at øge frekvensopløsningen med yderligere decimering af koefficienterne efter lavpas- og højpasfiltrering. Dette kan repræsenteres som et binært træ, hvor blade og noder svarer til rum med forskellig tids-frekvens lokalisering. Dette træ repræsenterer strukturen af banken (kammen) af filtre .

På hvert niveau i diagrammet ovenfor er signalet opdelt i lave og høje frekvenser. På grund af den dobbelte decimering skal signallængden være et multiplum af , hvor er antallet af dekomponeringsniveauer. $2^{n}$ $n$

For eksempel, for et 32-sample signal med et frekvensområde på 0 til 3 niveauer, vil udvidelsen give 4 udgange på forskellige skalaer: $f_n$

Niveau	Frekvenser	Signallængde
3	$0$ … ${{f_{n}}}/8$	fire
3	${{f_{n}}}/8$ … ${{f_{n}}}/4$	fire
2	${{f_{n}}}/4$ … ${{f_{n}}}/2$	otte
en	${{f_{n}}}/2$ … $f_n$	16

Programeksempel

Haars algoritme

Et eksempel på en hurtig en-dimensionel wavelet-transformation, ved hjælp af Haar wavelet , for en række indledende data af størrelse 2 N (antallet af filtertrin er henholdsvis N) i C#:

public static List < Double > DirectTransform ( List < Double > SourceList ) { if ( SourceList . Count == 1 ) return SourceList ; Liste < Dobbelt > RetVal = ny liste < Dobbelt >(); Liste < Dobbelt > TmpArr = ny liste < Dobbelt >(); for ( int j = 0 ; j < Kildeliste . Antal - 1 ; j += 2 ) { RetVal . Tilføj (( Kildeliste [ j ] - Kildeliste [ j + 1 ]) / 2.0 ); TmpArr . Tilføj (( Kildeliste [ j ] + Kildeliste [ j + 1 ]) / 2.0 ); } RetVal . AddRange ( DirectTransform ( TmpArr )); returnere RetVal ; }

Tilsvarende et eksempel på den inverse wavelet-transformation:

public static List < Double > InverseTransform ( Liste < Double > SourceList ) { if ( SourceList . Count == 1 ) return SourceList ; Liste < Dobbelt > RetVal = ny liste < Dobbelt >(); Liste < Dobbelt > TmpPart = ny liste < Dobbelt >(); for ( int i = Kildeliste . Antal / 2 ; i < Kildeliste . Antal ; i ++ ) TmpPart . Tilføj ( Kildeliste [ i ]); Liste < Double > SecondPart = InverseTransform ( TmpPart ); for ( int i = 0 ; i < Kildeliste . Antal / 2 ; i ++ ) { RetVal . Tilføj ( Anden del [ i ] + Kildeliste [ i ]); RetVal . Tilføj ( Anden del [ i ] - Kildeliste [ i ]); } returnere RetVal ; }

Todimensionel wavelet transformation

Ved udviklingen af den nye JPEG-2000- standard blev wavelet-transformationen valgt til billedkomprimering. Wavelet-transformationen i sig selv komprimerer ikke dataene, men gør det muligt at transformere inputbilledet på en sådan måde, at dets redundans kan reduceres uden en mærkbar forringelse af billedkvaliteten.

Se også

Kontinuerlig Wavelet Transform

Noter

↑ Ordninger på russisk

Litteratur

Stephane Mallat. En Wavelet-rundvisning i signalbehandling
Zakharov S. I. , Kholmskaya A. G. Forbedring af effektiviteten af behandling af vibrations- og støjsignaler under test af mekanismer // Vestnik mashinostroeniya : zhurnal. - M . : Mashinostroenie, 2001. - Nr. 10 . - S. 31-32 . — ISSN 0042-4633 .

Links

Sensor for vibroakustik og vibrodiagnostik af produkter: Pat nr. 95116U1, IPC G 01 H 1/08.
Hurtig diskret biortogonal CDF 9/7 wavelet fremad og omvendt transformation (løfteimplementering) er en C-implementering til hurtig løft af en diskret biortogonal CDF 9/7 wavelet brugt i JPEG-2000 billedkomprimeringsalgoritmen .
En ny trend i konvertering af data fra sensorer af mekaniske og fysiske størrelser. M: Maskinteknik//Bulletin for maskinteknik, 2004, nr. 4, s.78.
Yuen Ch., Beacham K., Robinson J. Mikroprocessorsystemer og deres anvendelse i signalbehandling. M: Radio og kommunikation. 1986. 296 s.
Dhonson N., Lyon F. Statistik og planlægning af eksperimenter inden for teknologi og videnskab. Eksperimenter planlægningsmetoder. M: Fred. 1981. 512 s.
Brokh ET Brüel & Kjærs brug af målesystemer til analyse af mekaniske svingninger og stød. Söborg; Larsen og søn. 1973. 235 s.
Bute P.-A. Måling af stød (chok) impulser. En ny metode til overvågning af rullelejers tilstand under drift. Rapport. SKF selskab. 1971. 7 s.
Kharkevich A. A. Spektra og analyse. M: Fizmatgiz.1963. 432 s.

Kompressionsmetoder _

Teori

Information	Egen Gensidig Entropi Betinget entropi Kompleksitet Redundans
Enheder	Bit Nat Nappe Hartley Hartley formel

Tabsfri

Entropi kompression	Asymmetriske talsystemer Huffman algoritme Adaptiv Huffman-algoritme Shannon-Fano algoritme Shannons algoritme Aritmetisk kodning ( interval ) Golomb koder Delta Universel kode Elias fibonacci
Ordbogsmetoder	RLE Tøm luften ud LZ ( LZ77/LZ78 LZSS LZW LZWL LZO LZMA LZX LZRW LZJB LZT LZ4 Brotli zstandard )
Andet	RLE CTW BWT MTF PPM DMC

Lyd

Teori	Konvolution PCM Aliasing Prøveudtagning Kotelnikovs teorem
Metoder	LPC LAR LSP WLPC CELP ACELP En lov μ-lov ADPCM MDCT Fourier transformation Psykoakustisk model
Andet	Audio kompressor Talekompression Båndkodning

Billeder

Vilkår	farverum Pixel Mætningsundersampling Kompressionsartefakter
Metoder	RLE DPCM fraktal wavelet EZW SPIHT LP Forbered PCL
Andet	Bitrate Standard testbillede PSNR Kvantisering

Video

Vilkår	Video egenskaber Ramme Rammetyper Videokvalitet
Metoder	Bevægelseskompensation Forbered Kvantisering wavelet
Andet	Video codec Teori om prisforvrængning CBR ABR VBR