Transformada wavelet rápida

Algoritmo

La transformada rápida de wavelets es un algoritmo matemático diseñado para convertir una forma de onda o señal en el dominio del tiempo en una secuencia de coeficientes basada en una base ortogonal de pequeñas ondas finitas, u wavelets . La transformada se puede extender fácilmente a señales multidimensionales, como imágenes, donde el dominio del tiempo se reemplaza por el dominio del espacio. Este algoritmo fue introducido en 1989 por Stéphane Mallat . ^[1]

Tiene como fundamento teórico el dispositivo de un análisis multirresolución (MRA) ortogonal y finitamente generado. En los términos dados allí, se selecciona una escala de muestreo J con una frecuencia de muestreo de 2 ^J por intervalo unitario y se proyecta la señal dada f sobre el espacio ; en teoría, calculando los productos escalares ${\displaystyle V_{J}}$

${\displaystyle s_{n}^{(J)}:=2^{J}\langle f(t),\varphi (2^{J}t-n)\rangle ,}$

donde es la función de escala de la transformada wavelet elegida; en la práctica, mediante cualquier procedimiento de muestreo adecuado bajo la condición de que la señal esté altamente sobremuestreada, por lo que ${\displaystyle \varphi }$

${\displaystyle P_{J}[f](x):=\sum _{n\in \mathbb {Z} }s_{n}^{(J)}\,\varphi (2^{J}x-n)}$

es la proyección ortogonal o al menos una buena aproximación de la señal original en . ${\displaystyle V_{J}}$

El MRA se caracteriza por su secuencia de escalado

${\displaystyle a=(a_{-N},\dots ,a_{0},\dots ,a_{N})}$o, como transformada Z , ${\displaystyle a(z)=\sum _{n=-N}^{N}a_{n}z^{-n}}$

y su secuencia wavelet

${\displaystyle b=(b_{-N},\dots ,b_{0},\dots ,b_{N})}$o ${\displaystyle b(z)=\sum _{n=-N}^{N}b_{n}z^{-n}}$

(algunos coeficientes pueden ser cero). Estos permiten calcular los coeficientes wavelet , al menos en algún rango k=M,...,J-1 , sin tener que aproximar las integrales en los productos escalares correspondientes. En cambio, uno puede directamente, con la ayuda de operadores de convolución y decimación, calcular esos coeficientes a partir de la primera aproximación . ${\displaystyle d_{n}^{(k)}}$ ${\displaystyle s^{(J)}}$

DWT hacia adelante

Para la transformada wavelet discreta (DWT), se calcula recursivamente , comenzando con la secuencia de coeficientes y contando hacia atrás desde k = J - 1 hasta algún M < J , ${\displaystyle s^{(J)}}$

Aplicación única de un banco de filtros wavelet, con filtros g=a ^* , h=b ^*

${\displaystyle s_{n}^{(k)}:={\frac {1}{2}}\sum _{m=-N}^{N}a_{m}s_{2n+m}^{(k+1)}}$o ${\displaystyle s^{(k)}(z):=(\downarrow 2)(a^{*}(z)\cdot s^{(k+1)}(z))}$

y

${\displaystyle d_{n}^{(k)}:={\frac {1}{2}}\sum _{m=-N}^{N}b_{m}s_{2n+m}^{(k+1)}}$o , ${\displaystyle d^{(k)}(z):=(\downarrow 2)(b^{*}(z)\cdot s^{(k+1)}(z))}$

para k=J-1,J-2,...,M y todos . En la notación de la transformada Z: ${\displaystyle n\in \mathbb {Z} }$

aplicación recursiva del banco de filtros

• El operador de submuestreo reduce una secuencia infinita, dada por su transformada Z , que es simplemente una serie de Laurent , a la secuencia de coeficientes con índices pares, . ${\displaystyle (\downarrow 2)}$ ${\displaystyle (\downarrow 2)(c(z))=\sum _{k\in \mathbb {Z} }c_{2k}z^{-k}}$
• El polinomio de Laurent con asterisco denota el filtro adjunto , tiene coeficientes adjuntos invertidos en el tiempo , . (El adjunto de un número real es el número mismo, de un número complejo su conjugado, de una matriz real la matriz transpuesta, de una matriz compleja su adjunto hermítico). ${\displaystyle a^{*}(z)}$ ${\displaystyle a^{*}(z)=\sum _{n=-N}^{N}a_{-n}^{*}z^{-n}}$
• La multiplicación es una multiplicación polinómica, que es equivalente a la convolución de las secuencias de coeficientes.

Resulta que

${\displaystyle P_{k}[f](x):=\sum _{n\in \mathbb {Z} }s_{n}^{(k)}\,\varphi (2^{k}x-n)}$

es la proyección ortogonal de la señal original f o al menos de la primera aproximación sobre el subespacio , es decir, con una frecuencia de muestreo de 2 ^k por unidad de intervalo. La diferencia con la primera aproximación viene dada por ${\displaystyle P_{J}[f](x)}$ ${\displaystyle V_{k}}$

${\displaystyle P_{J}[f](x)=P_{k}[f](x)+D_{k}[f](x)+\dots +D_{J-1}[f](x),}$

donde las señales de diferencia o detalle se calculan a partir de los coeficientes de detalle como

${\displaystyle D_{k}[f](x):=\sum _{n\in \mathbb {Z} }d_{n}^{(k)}\,\psi (2^{k}x-n),}$

con la que se denota la ondícula madre de la transformada ondícula. ${\displaystyle \psi }$

DWT inversa

Dada la secuencia de coeficientes para algún M  <  J y todas las secuencias de diferencias , k  =  M ,..., J  − 1, se calcula recursivamente ${\displaystyle s^{(M)}}$ ${\displaystyle d^{(k)}}$

${\displaystyle s_{n}^{(k+1)}:=\sum _{k=-N}^{N}a_{k}s_{2n-k}^{(k)}+\sum _{k=-N}^{N}b_{k}d_{2n-k}^{(k)}}$o ${\displaystyle s^{(k+1)}(z)=a(z)\cdot (\uparrow 2)(s^{(k)}(z))+b(z)\cdot (\uparrow 2)(d^{(k)}(z))}$

para k = J  − 1, J  − 2,..., M y todos . En la notación de la transformada Z: ${\displaystyle n\in \mathbb {Z} }$

• El operador de sobremuestreo crea huecos llenos de ceros dentro de una secuencia dada. Es decir, cada segundo elemento de la secuencia resultante es un elemento de la secuencia dada, cada segundo elemento es cero o . Este operador lineal es, en el espacio de Hilbert , el operador adjunto del operador de submuestreo . ${\displaystyle (\uparrow 2)}$ ${\displaystyle (\uparrow 2)(c(z)):=\sum _{n\in \mathbb {Z} }c_{n}z^{-2n}}$ ${\displaystyle \ell ^{2}(\mathbb {Z} ,\mathbb {R} )}$ ${\displaystyle (\downarrow 2)}$

Véase también

• Esquema de elevación
• Transformada rápida de Fourier

Referencias

1. "Algoritmo de transformada wavelet rápida (FWT)". MathWorks . Consultado el 20 de febrero de 2018 .

• SG Mallat "Una teoría para la descomposición de señales multiresolución: la representación wavelet" IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 2, no. 7. Julio de 1989.
• I. Daubechies, Diez conferencias sobre wavelets. SIAM, 1992.
• AN Akansu Multiplierless Suboptimal PR-QMF Design Proc. SPIE 1818, Comunicaciones visuales y procesamiento de imágenes, pág. 723, noviembre de 1992
• Filtro de espejo en cuadratura de reconstrucción perfecta de dos bandas sin multiplicador de Akansu (PR-QMF) Patente de Estados Unidos 5.420.891, 1995
• AN Akansu Multiplierless PR Quadrature Mirror Filters for Subband Image Coding IEEE Trans. Procesamiento de imágenes, pág. 1359, septiembre de 1996
• MJ Mohlenkamp, ​​MC Pereyra Wavelets, sus amigos y lo que pueden hacer por usted (EMS 2008) pág. 38
• BB Hubbard El mundo según las wavelets: La historia de una técnica matemática en desarrollo (1998 Peters) p. 184
• SG Mallat Un recorrido wavelet por el procesamiento de señales (1999 Academic Press) p. 255
• A. Teolis Procesamiento computacional de señales con wavelets (1998 Birkhäuser) p. 116
• Y. Nievergelt Wavelets Made Easy (1999 Springer) pág. 95

Lectura adicional

G. Beylkin , R. Coifman , V. Rokhlin , "Transformadas wavelet rápidas y algoritmos numéricos" Comm. Pure Appl. Math. , 44 (1991) págs. 141–183 doi :10.1002/cpa.3160440202 (Este artículo ha sido citado más de 2400 veces).