imported>Nukelavee: /* growthexperiments-addlink-summary-summary:3|0|0 */

2024-09-21T13:09:37Z

growthexperiments-addlink-summary-summary:3|0|0

Neue Seite

Die '''schnelle Wavelet-Transformation,''' englisch ''fast wavelet transform,'' ist ein effizientes Verfahren zur Berechnung einer diskreten [[Wavelet-Transformation]]. Sie kann mit der Anwendung der [[Schnelle Fourier-Transformation|schnellen Fourier-Transformation]] zur Berechnung der Koeffizienten einer [[Fourier-Reihe]] verglichen werden.

== Konstruktion ==
[[Bild:Wavelets_-_DWT.png|thumb|400px|Analyse-Filterbank, <math>g=a^{-}, h=b^{-}</math>]]
[[Bild:Wavelets_-_Filter_Bank.png|thumb|400px|Rekursive Anwendung einer Analyse-Filterbank]]

Ein gegebenes kontinuierliches Signal <math>f</math> wird zunächst durch [[Orthogonalprojektion|orthogonale Projektion]] auf einen Unterraum <math>V_{-J}</math> einer orthogonalen [[Multiskalenanalyse]] in eine zeitdiskrete Koeffizientenfolge <math>s^{(-J)}</math> umgewandelt. Je größer <math>J</math> ist, desto genauer ist die dadurch erzielte [[Approximation]]. In vielen Fällen ist es ausreichend,

:<math>s^{(-J)}_n:=2^{-J/2}\,f(n/2^J)</math>

zu setzen. Nun wird rekursiv aus jedem Tiefpasssignal <math>s^{(k)}</math> ein neues Tiefpasssignal

:<math>s^{(k+1)}=\frac1{\sqrt2}(\downarrow2)(a_-*s^{(k)})</math>

und das Hochpasssignal

:<math>d^{(k+1)}=\frac1{\sqrt2}(\downarrow2)(b_-*s^{(k)})</math>

erzeugt. Zusammen bilden diese eine Analyse-Filterbank, die Operationen darin werden weiter unten erklärt.

Nach <math>M</math> Schritten der [[Rekursion]] ergeben sich die Folgen

:<math>d^{(-J+1)},\dots,d^{(-J+M)}</math>   und   <math>s^{(-J+M)}</math>.

Das Ziel dieser Transformation ist, dass die <math>d^{(k)}</math> „dünn“ besetzt sind und sich daher gut komprimieren lassen.

Sind die Filter <math>a</math> und <math>b</math> ausreichend frequenzselektiv, war das Ausgangssignal bandbeschränkt und wurde dem WKS-[[Abtasttheorem]] entsprechend die erste Koeffizientenfolge <math>s^{(-J)}_n</math> gewonnen, so enthält das erste Tiefpassergebnis alle Signalbestandteile bis zur halben [[Nyquist-Frequenz]], das Hochpassergebnis die darüberliegenden, beide Male mit einer der [[Bandbreite]] entsprechenden [[Abtastrate]].

== Analyse und Synthese ==
Der Fischgrätenzerlegung in der [[Multiskalenanalyse]] entspricht eine aus dem [[Tiefpass]] <math>a</math> und dem [[Hochpass]] <math>b</math> zusammengesetzte zeitdiskrete Filterbank, es wird ein zeitdiskretes Signal <math>x</math> aufgeteilt in ein hohes Band <math>b^-*x</math> und ein tiefes Band <math>a^-*x</math> (Faltung von Folgen). Danach werden beide Signale heruntergetaktet (englisch ''downsampling'') zu

:<math>s=(\downarrow2)(a^-*x)</math>   und   <math>d=(\downarrow2)(b^-*x)</math>.

Mit <math>a^-</math> sei dabei die zeitinvertierte Folge

:<math>a^-=\{\dots,a_{2},a_{1},a_{0},a_{-1},a_{-2},\dots\}</math>

bezeichnet. Das Heruntertakten einer Folge bedeutet, dass eine neue Folge aus den Gliedern mit geradem Index gebildet wird,

:<math>(\downarrow2)(y)=\{\dots,y_{-4},y_{-2},y_{0},y_{2},y_{4},\dots\}</math>.

Alle diese Operationen zusammengefasst ergibt sich eine gliedweise Berechnungsvorschrift der Analyse-Filterbank

:<math>s_n=\sum_k a_k\cdot x_{2n+k}</math>   und   <math>d_n=\sum_k b_k\cdot x_{2n+k}</math>.

Aus der Orthogonalität ergibt sich, dass das Ausgangssignal <math>x</math> zurückgewonnen werden kann, zuerst werden die Tiefpass- und Hochpassanteile <math>s</math> und <math>d</math> in der Abtastrate hochgerechnet, dies wird als [[Upsampling]] bezeichnet, mit den Skalierungs- und Waveletmasken gefaltet und dann addiert,

:<math>2x=a*(\uparrow2)s+b*(\uparrow2)d</math>

oder koeffizientenweise

:<math>2x_n=\sum_k a_{n-2k}\cdot s_k+\sum_k b_{n-2k}\cdot d_k</math>.

Der Übergang von <math>x</math> zu <math>(s, d)</math> heißt Analyse, der inverse Synthese. Es ist ersichtlich, dass die Transformierte <math>(s, d)</math> eines endlichen Signals nun etwa genauso viele Samples wie das Signal <math>x</math> selbst hat, also genauso viel Information enthält.

== Erweiterungen ==
Es ist nicht erforderlich, dass die Folgen in der Analyse-Filterbank mit denen in der Synthese-Filterbank wie oben übereinstimmen, nur ist dann nicht garantiert, dass die Kombination beider Filterbänke das Ausgangssignal rekonstruiert. Ist dies doch der Fall, spricht man von vollständiger Rekonstruktion (englisch ''perfect reconstruction'') oder von Biorthogonalität der Wavelet-Basen.

[[Kategorie:Numerische Mathematik]]
[[Kategorie:Wavelet]]
[[Kategorie:Diskrete Transformation]]

Schnelle Wavelet-Transformation - Versionsgeschichte

imported>Nukelavee: /* growthexperiments-addlink-summary-summary:3|0|0 */