En análisis numérico y análisis funcional , una transformada de ondículas discretas ( DWT ) es cualquier transformada de ondículas para las que se muestrean discretamente las ondículas . Al igual que con otras transformadas de ondículas, una ventaja clave que tiene sobre las transformadas de Fourier es la resolución temporal: captura tanto la información de frecuencia como de ubicación (ubicación en el tiempo).
Ejemplos de
Ondas de Haar
El primer DWT fue inventado por el matemático húngaro Alfréd Haar . Para una entrada representada por una lista denúmeros, se puede considerar que la transformada de ondas de Haar empareja los valores de entrada, almacena la diferencia y pasa la suma. Este proceso se repite de forma recursiva, emparejando las sumas para probar la siguiente escala, lo que conduce a diferencias y una suma final.
Ondas de Daubechies
El conjunto de transformaciones de ondículas discretas más comúnmente utilizado fue formulado por la matemática belga Ingrid Daubechies en 1988. Esta formulación se basa en el uso de relaciones de recurrencia para generar muestras discretas progresivamente más finas de una función de ondícula madre implícita; cada resolución es el doble que la escala anterior. En su artículo fundamental, Daubechies deriva una familia de wavelets , la primera de las cuales es la wavelet de Haar. El interés en este campo se ha disparado desde entonces, y se desarrollaron muchas variaciones de las ondas originales de Daubechies. [1] [2]
La transformada de ondas complejas de árbol dual (DℂWT)
La transformada de ondículas complejas de árbol dual (ℂWT) es una mejora relativamente reciente de la transformada de ondículas discretas (DWT), con importantes propiedades adicionales: es casi invariante de desplazamiento y direccionalmente selectiva en dos dimensiones o más. Lo logra con un factor de redundancia de solo, sustancialmente más bajo que el DWT no calculado. El ℂWT de árbol dual multidimensional (MD) no es separable, pero se basa en un banco de filtros separables (FB) computacionalmente eficiente. [3]
Otros
Otras formas de transformada de ondículas discretas incluyen la ondícula LeGall-Tabatabai (LGT) 5/3 desarrollada por Didier Le Gall y Ali J. Tabatabai en 1988 (utilizada en JPEG 2000 ), [4] [5] [6] el Binomial QMF desarrollado por Ali Naci Akansu en 1990, [7] el algoritmo de partición de conjuntos en árboles jerárquicos (SPIHT) desarrollado por Amir Said con William A. Pearlman en 1996, [8] la transformada wavelet no o indecimada (donde se omite el submuestreo), y la transformada de Newland (donde una base ortonormal de ondículas se forma a partir de filtros de sombrero de copa debidamente construidos en el espacio de frecuencias ). Las transformaciones de paquetes de ondículas también están relacionadas con la transformada de ondículas discretas. La transformada de ondas complejas es otra forma.
Propiedades
El Haar DWT ilustra las propiedades deseables de las ondículas en general. Primero, se puede realizar enoperaciones; en segundo lugar, captura no sólo una noción del contenido de frecuencia de la entrada, examinándola a diferentes escalas, sino también el contenido temporal, es decir, los momentos en los que ocurren estas frecuencias. Combinadas, estas dos propiedades hacen de la transformada de ondícula rápida (FWT) una alternativa a la transformada rápida de Fourier convencional (FFT).
Problemas de tiempo
Debido a los operadores de cambio de velocidad en el banco de filtros, el WT discreto no es invariante en el tiempo, pero en realidad es muy sensible a la alineación de la señal en el tiempo. Para abordar el problema de las transformaciones de ondículas que varían en el tiempo, Mallat y Zhong propusieron un nuevo algoritmo para la representación de ondículas de una señal, que es invariante a los cambios de tiempo. [9] Según este algoritmo, que se denomina TI-DWT, solo se muestrea el parámetro de escala a lo largo de la secuencia diádica 2 ^ j (j∈Z) y se calcula la transformada de ondícula para cada punto en el tiempo. [10] [11]
Aplicaciones
La transformada de ondículas discretas tiene una gran cantidad de aplicaciones en ciencia, ingeniería, matemáticas e informática. En particular, se utiliza para la codificación de señales , para representar una señal discreta en una forma más redundante, a menudo como un preacondicionamiento para la compresión de datos . También se pueden encontrar aplicaciones prácticas en el procesamiento de señales de aceleraciones para el análisis de la marcha, [12] [13] procesamiento de imágenes, [14] [15] en comunicaciones digitales y muchos otros. [16] [17] [18]
Se muestra que la transformación de ondas discretas (discreta en escala y desplazamiento, y continua en el tiempo) se implementa con éxito como banco de filtros analógicos en el procesamiento de señales biomédicas para el diseño de marcapasos de baja potencia y también en comunicaciones inalámbricas de banda ultraancha (UWB). [19]
Ejemplo de procesamiento de imágenes
Las wavelets se utilizan a menudo para eliminar el ruido de señales bidimensionales, como imágenes. El siguiente ejemplo proporciona tres pasos para eliminar el ruido gaussiano blanco no deseado de la imagen ruidosa que se muestra. Se utilizó Matlab para importar y filtrar la imagen.
El primer paso es elegir un tipo de ondícula y un nivel N de descomposición. En este caso, se eligieron ondículas biortogonales de 3,5 con un nivel N de 10. Las ondículas biortogonales se utilizan comúnmente en el procesamiento de imágenes para detectar y filtrar el ruido gaussiano blanco, [20] debido a su alto contraste de los valores de intensidad de píxeles vecinos. Usando estas ondículas, se realiza una transformación de ondículas en la imagen bidimensional.
Después de la descomposición del archivo de imagen, el siguiente paso es determinar los valores de umbral para cada nivel de 1 a N. La estrategia de Birgé-Massart [21] es un método bastante común para seleccionar estos umbrales. Usando este proceso, se establecen umbrales individuales para N = 10 niveles. La aplicación de estos umbrales constituye la mayor parte del filtrado real de la señal.
El último paso es reconstruir la imagen a partir de los niveles modificados. Esto se logra usando una transformada de ondícula inversa. La imagen resultante, con el ruido blanco gaussiano eliminado, se muestra debajo de la imagen original. Al filtrar cualquier forma de datos, es importante cuantificar la relación señal / ruido del resultado. [ cita requerida ] En este caso, el SNR de la imagen con ruido en comparación con el original fue 30,4958%, y el SNR de la imagen sin ruido es 32,5525%. La mejora resultante del filtrado de ondículas es una ganancia de SNR del 2,0567%. [22]
Es importante tener en cuenta que la elección de otras ondículas, niveles y estrategias de umbral puede resultar en diferentes tipos de filtrado. En este ejemplo, se eligió eliminar el ruido blanco gaussiano. Aunque, con diferentes umbrales, podría haberse amplificado con la misma facilidad.
Para ilustrar las diferencias y similitudes entre la transformada ondícula discreta con la transformada discreta de Fourier , considere el DWT y DFT de la siguiente secuencia: (1,0,0,0), un impulso unitario .
La DFT tiene una base ortogonal ( matriz DFT ):
mientras que el DWT con ondas de Haar para datos de longitud 4 tiene una base ortogonal en las filas de:
(Para simplificar la notación, se utilizan números enteros, por lo que las bases son ortogonales pero no ortonormales ).
Las observaciones preliminares incluyen:
- Las ondas sinusoidales difieren solo en su frecuencia. El primero no completa ningún ciclo, el segundo completa un ciclo completo, el tercero completa dos ciclos y el cuarto completa tres ciclos (lo que equivale a completar un ciclo en la dirección opuesta). Las diferencias de fase se pueden representar multiplicando un vector base dado por una constante compleja.
- Las wavelets, por el contrario, tienen frecuencia y ubicación. Como antes, el primero completa cero ciclos y el segundo completa un ciclo. Sin embargo, el tercero y el cuarto tienen la misma frecuencia, el doble que el primero. En lugar de diferir en frecuencia, difieren en ubicación : el tercero es distinto de cero sobre los dos primeros elementos y el cuarto es distinto de cero sobre los dos segundos elementos.
El DWT demuestra la localización: el término (1,1,1,1) da el valor medio de la señal, el (1,1, –1, –1) coloca la señal en el lado izquierdo del dominio y el (1 , –1,0,0) lo coloca en el lado izquierdo del lado izquierdo, y truncar en cualquier etapa produce una versión reducida de la señal:
La DFT, por el contrario, expresa la secuencia mediante la interferencia de ondas de varias frecuencias, por lo que al truncar la serie se obtiene una versión filtrada de paso bajo de la serie:
En particular, la aproximación media (2 términos) difiere. Desde la perspectiva del dominio de la frecuencia, esta es una mejor aproximación, pero desde la perspectiva del dominio del tiempo tiene inconvenientes - exhibe un subimpulso - uno de los valores es negativo, aunque la serie original no es negativa en todas partes - y suena , donde el lado derecho no es cero, a diferencia de la transformada wavelet. Por otro lado, la aproximación de Fourier muestra correctamente un pico, y todos los puntos están dentro dede su valor correcto, aunque todos los puntos tienen error. La aproximación de ondículas, por el contrario, coloca un pico en la mitad izquierda, pero no tiene pico en el primer punto, y aunque es exactamente correcto para la mitad de los valores (ubicación reflectante), tiene un error de para los otros valores.
Esto ilustra los tipos de compensaciones entre estas transformaciones y cómo, en algunos aspectos, el DWT proporciona un comportamiento preferible, en particular para el modelado de transitorios.
Definición
Un nivel de la transformación
El DWT de una señal se calcula pasándolo por una serie de filtros. Primero, las muestras pasan a través de un filtro de paso bajo con respuesta de impulso. resultando en una convolución de los dos:
La señal también se descompone simultáneamente utilizando un filtro de paso alto. . Las salidas dan los coeficientes de detalle (del filtro de paso alto) y los coeficientes de aproximación (del paso bajo). Es importante que los dos filtros estén relacionados entre sí y se les conoce como filtro de espejo en cuadratura .
Sin embargo, dado que ahora se ha eliminado la mitad de las frecuencias de la señal, la mitad de las muestras se pueden descartar de acuerdo con la regla de Nyquist. La salida de filtro del filtro de paso bajoen el diagrama de arriba, luego se submuestrea por 2 y se procesa más pasándolo nuevamente a través de un nuevo filtro de paso bajo y un filtro de paso alto con la mitad de la frecuencia de corte del anterior, es decir:
Esta descomposición ha reducido a la mitad el tiempo de resolución ya que solo la mitad de cada salida de filtro caracteriza la señal. Sin embargo, cada salida tiene la mitad de la banda de frecuencia de la entrada, por lo que la resolución de frecuencia se ha duplicado.
Con el operador de submuestreo
el resumen anterior se puede escribir de forma más concisa.
Sin embargo, calculando una convolución completa con la posterior reducción de la resolución, se desperdiciaría tiempo de cálculo.
El esquema de elevación es una optimización en la que estos dos cálculos están intercalados.
Bancos de filtros y en cascada
Esta descomposición se repite para aumentar aún más la resolución de frecuencia y los coeficientes de aproximación se descomponen con filtros de paso alto y bajo y luego se muestrean hacia abajo. Esto se representa como un árbol binario con nodos que representan un subespacio con una localización de tiempo-frecuencia diferente. El árbol se conoce como banco de filtros .
En cada nivel del diagrama anterior, la señal se descompone en frecuencias altas y bajas. Debido al proceso de descomposición, la señal de entrada debe ser un múltiplo de dónde es el número de niveles.
Por ejemplo, una señal con 32 muestras, rango de frecuencia de 0 a y 3 niveles de descomposición, se producen 4 escalas de salida:
Nivel | Frecuencias | Muestras |
---|---|---|
3 | a | 4 |
a | 4 | |
2 | a | 8 |
1 | a | dieciséis |
Relación con la ondícula madre
La implementación del banco de filtros de ondículas puede interpretarse como el cálculo de los coeficientes de ondículas de un conjunto discreto de ondículas secundarias para una determinada ondícula madre.. En el caso de la transformada de ondícula discreta, la ondícula madre se desplaza y escala por potencias de dos
dónde es el parámetro de escala y es el parámetro de desplazamiento, ambos enteros.
Recuerde que el coeficiente de ondículas de una señal es la proyección de en una wavelet y dejar ser una señal de longitud . En el caso de una ondícula infantil en la familia discreta anterior,
Ahora arregla a una escala particular, de modo que es una función de solo. A la luz de la ecuación anterior,puede verse como una convolución de con una versión dilatada, reflejada y normalizada de la ondícula madre, , muestreado en los puntos . Pero esto es precisamente lo que dan los coeficientes de detalle a nivelde la transformada de ondícula discreta. Por lo tanto, para una elección adecuada de y , los coeficientes de detalle del banco de filtros corresponden exactamente a un coeficiente de ondículas de un conjunto discreto de ondículas secundarias para una determinada ondícula madre .
Como ejemplo, considere la ondícula discreta de Haar , cuya ondícula madre es. Entonces la versión dilatada, reflejada y normalizada de esta ondícula es, que es, de hecho, el filtro de descomposición de paso alto para la transformada de ondícula discreta de Haar.
Complejidad del tiempo
La implementación del banco de filtros de la Transformada de Onda Discreta solo toma O ( N ) en ciertos casos, en comparación con O ( N log N ) para la transformada rápida de Fourier .
Tenga en cuenta que si y son ambos una longitud constante (es decir, su longitud es independiente de N), entonces y cada uno toma O ( N ) tiempo. El banco de filtros de ondículas hace cada una de estas dos circunvoluciones O ( N ) y luego divide la señal en dos ramas de tamaño N / 2. Pero sólo divide recursivamente la rama superior convolucionada con(en contraste con la FFT, que divide recursivamente tanto la rama superior como la rama inferior). Esto conduce a la siguiente relación de recurrencia
lo que conduce a un tiempo O ( N ) para toda la operación, como puede mostrarse mediante una expansión en serie geométrica de la relación anterior.
Como ejemplo, la transformada de ondícula discreta de Haar es lineal, ya que en ese caso y son de longitud constante 2.
La localidad de las ondículas, junto con la complejidad O ( N ), garantiza que la transformación se pueda calcular en línea (sobre una base de transmisión). Esta propiedad contrasta fuertemente con FFT, que requiere acceso a toda la señal de una vez. También se aplica a la transformada multiescala y también a las transformadas multidimensionales (por ejemplo, 2D DWT). [23]
Otras transformaciones
- El algoritmo Adam7 , utilizado para entrelazar en el formato Portable Network Graphics (PNG), es un modelo multiescala de los datos que es similar a un DWT con ondas Haar . A diferencia del DWT, tiene una escala específica: comienza desde un bloque de 8 × 8 y reduce la resolución de la imagen, en lugar de diezmar ( filtrado de paso bajo , luego reducción de resolución). Por lo tanto, ofrece un peor comportamiento de frecuencia, mostrando artefactos ( pixelación ) en las primeras etapas, a cambio de una implementación más simple.
- La transformada de ondícula discreta multiplicativa (o geométrica) [24] es una variante que se aplica a un modelo de observaciónque involucran interacciones de una función regular positiva y un ruido positivo independiente multiplicativo , con . Denotar, una transformada de ondículas. Desde, luego la transformada de ondícula discreta estándar (aditiva) es tal que donde coeficientes de detalle no puede considerarse escasa en general, debido a la contribución de en la última expresión. En el marco multiplicativo, la transformada de ondículas es tal queEsta "incrustación" de ondículas en un álgebra multiplicativa implica aproximaciones multiplicativas generalizadas y operadores de detalle: por ejemplo, en el caso de las ondículas de Haar, luego hasta el coeficiente de normalización, el estandar aproximaciones ( media aritmética )y detalles ( diferencias aritméticas )se convierten en aproximaciones de medias geométricas respectivamentey diferencias geométricas (detalles) cuando usas .
Ejemplo de código
En su forma más simple, el DWT es muy fácil de calcular.
La wavelet de Haar en Java :
public static int [] discreteHaarWaveletTransform ( int [] input ) { // Esta función asume que input.length = 2 ^ n, n> 1 int [] output = new int [ input . longitud ] ; para ( int longitud = entrada . longitud / 2 ; ; longitud = longitud / 2 ) { // longitud es la longitud actual de la zona de trabajo de la matriz de salida. // la longitud comienza en la mitad del tamaño de la matriz y cada iteración se reduce a la mitad hasta que sea 1. for ( int i = 0 ; i < length ; ++ i ) { int sum = input [ i * 2 ] + input [ i * 2 + 1 ] ; int diferencia = entrada [ i * 2 ] - entrada [ i * 2 + 1 ] ; salida [ i ] = suma ; salida [ longitud + i ] = diferencia ; } if ( length == 1 ) { return output ; } // Intercambia matrices para hacer la siguiente iteración System . arraycopy ( salida , 0 , entrada , 0 , longitud ); } }
El código Java completo para un DWT 1-D y 2-D con ondas de Haar , Daubechies , Coiflet y Legendre está disponible en el proyecto de código abierto: JWave . Además, aquí se puede encontrar una implementación de elevación rápida de la transformada de ondículas CDF 9/7 biortogonal discreta en C , utilizada en el estándar de compresión de imágenes JPEG 2000 (archivado el 5 de marzo de 2012).
Ejemplo de código anterior
Esta figura muestra un ejemplo de cómo aplicar el código anterior para calcular los coeficientes de ondas de Haar en una forma de onda de sonido. Este ejemplo destaca dos propiedades clave de la transformada wavelet:
- Las señales naturales a menudo tienen cierto grado de suavidad, lo que las hace escasas en el dominio de las ondículas. Hay muchos menos componentes significativos en el dominio de ondículas en este ejemplo que en el dominio del tiempo, y la mayoría de los componentes significativos están hacia los coeficientes más gruesos de la izquierda. Por tanto, las señales naturales son comprimibles en el dominio de ondículas.
- La transformada de ondícula es una representación de paso de banda de múltiples resoluciones de una señal. Esto se puede ver directamente en la definición del banco de filtros de la transformada de ondícula discreta dada en este artículo. Para una señal de largo, los coeficientes en el rango representan una versión de la señal original que está en la banda de paso . Esta es la razón por la que hacer zoom en estos rangos de coeficientes de ondícula se ve tan similar en estructura a la señal original. Rangos que están más cerca de la izquierda (más grandes en la notación anterior), son representaciones más burdas de la señal, mientras que los rangos a la derecha representan detalles más finos.
Ver también
- Transformada de coseno discreta (DCT)
- Wavelet
- Serie wavelet
- Compresión wavelet
- Lista de transformadas relacionadas con wavelets
Referencias
- ^ AN Akansu, RA Haddad y H. Caglar, Transformada QMF-Wavelet binomial de reconstrucción perfecta , Proc. SPIE Comunicaciones visuales y procesamiento de imágenes, págs. 609–618, vol. 1360, Lausana, septiembre de 1990.
- ↑ Akansu, Ali N .; Haddad, Richard A. (1992), Descomposición de señales multiresolución: transformadas, subbandas y ondas, Boston, MA: Academic Press, ISBN 978-0-12-047141-6
- ^ Selesnick, IW; Baraniuk, RG; Kingsbury, NC, 2005, La transformada de ondículas del complejo de árbol dual
- ^ Sullivan, Gary (8 a 12 de diciembre de 2003). "Características generales y consideraciones de diseño para la codificación de video de subbanda temporal" . ITU-T . Grupo de expertos en codificación de videos . Consultado el 13 de septiembre de 2019 .
- ^ Bovik, Alan C. (2009). La guía esencial para el procesamiento de video . Prensa académica . pag. 355. ISBN 9780080922508.
- ^ Gall, Didier Le; Tabatabai, Ali J. (1988). "Codificación de subbanda de imágenes digitales mediante filtros de núcleo corto simétricos y técnicas de codificación aritmética". ICASSP-88., Conferencia internacional sobre acústica, habla y procesamiento de señales : 761–764 vol.2. doi : 10.1109 / ICASSP.1988.196696 . S2CID 109186495 .
- ^ Ali Naci Akansu , Una estructura eficiente de QMF-Wavelet (Binomial-QMF Daubechies Wavelets), Proc. 1er Simposio de NJIT sobre Wavelets, abril de 1990.
- ^ Dijo, A .; Pearlman, WA (1996). "Un códec de imagen nuevo, rápido y eficiente basado en la partición de conjuntos en árboles jerárquicos" . Transacciones IEEE sobre circuitos y sistemas para tecnología de video . 6 (3): 243–250. doi : 10.1109 / 76.499834 . ISSN 1051-8215 . Consultado el 18 de octubre de 2019 .
- ↑ S. Mallat, A Wavelet Tour of Signal Processing, 2da ed. San Diego, CA: Académico, 1999.
- ^ SG Mallat y S. Zhong, "Caracterización de señales de bordes multiescala", IEEE Trans. Patrón Anal. Mach. Intell., Vol. 14, no. 7, págs. 710–732, julio de 1992.
- ^ Ince, Kiranyaz, Gabbouj, 2009, Un sistema genérico y robusto para la clasificación automatizada específica del paciente de señales de ECG
- ^ "Método novedoso para la estimación de la longitud de la zancada con acelerómetros de red de área corporal" , IEEE BioWireless 2011 , págs. 79-82
- ^ Nasir, V .; Genial, J .; Sassani, F. (octubre de 2019). "Monitoreo de mecanizado inteligente utilizando señal de sonido procesada con el método Wavelet y una red neuronal autoorganizada" . IEEE Robotics and Automation Letters . 4 (4): 3449–3456. doi : 10.1109 / LRA.2019.2926666 . ISSN 2377-3766 .
- ^ Broughton, S. Allen. "Métodos basados en wavelets en el procesamiento de imágenes" . www.rose-hulman.edu . Consultado el 2 de mayo de 2017 .
- ^ Chervyakov, NI; Lyakhov, PA; Nagornov, NN (1 de noviembre de 2018). "Ruido de cuantificación de filtros de transformación de ondas discretas multinivel en el procesamiento de imágenes" . Optoelectrónica, instrumentación y procesamiento de datos . 54 (6): 608–616. doi : 10.3103 / S8756699018060092 . ISSN 1934-7944 .
- ^ AN Akansu y MJT Smith, Transformaciones de subbanda y wavelet: diseño y aplicaciones , Kluwer Academic Publishers, 1995.
- ^ AN Akansu y MJ Medley, Wavelet, subbanda y transformaciones de bloque en comunicaciones y multimedia , Kluwer Academic Publishers, 1999.
- ^ AN Akansu, P. Duhamel, X. Lin y M. de Courville Transmultiplexores ortogonales en comunicación: una revisión , IEEE Trans. Sobre procesamiento de señales, número especial sobre teoría y aplicaciones de bancos de filtros y wavelets. Vol. 46, No 4, págs. 979–995, abril de 1998.
- ^ AN Akansu, WA Serdijn e IW Selesnick, Transformaciones de ondas en el procesamiento de señales: una revisión de aplicaciones emergentes , Comunicación física, Elsevier, vol. 3, número 1, págs. 1 a 18, marzo de 2010.
- ^ Pragada, S .; Sivaswamy, J. (1 de diciembre de 2008). "Reducción de ruido de imagen usando ondas biortogonales emparejadas". 2008 Sexta Conferencia India sobre Visión por Computador, Procesamiento de Imágenes Gráficas : 25–32. doi : 10.1109 / ICVGIP.2008.95 . S2CID 15516486 .
- ^ "Umbrales para wavelet 1-D utilizando la estrategia de Birgé-Massart - MATLAB wdcbm" . www.mathworks.com . Consultado el 3 de mayo de 2017 .
- ^ "cómo obtener SNR para 2 imágenes - MATLAB Answers - MATLAB Central" . www.mathworks.com . Consultado el 10 de mayo de 2017 .
- ^ Barina, David (2020). "Transformada wavelet en tiempo real para tiras de imágenes infinitas" . Revista de procesamiento de imágenes en tiempo real . Saltador. 18 (3): 585–591. doi : 10.1007 / s11554-020-00995-8 . S2CID 220396648 . Consultado el 9 de julio de 2020 .
- ^ Atto, Abdourrahmane M .; Trouvé, Emmanuel; Nicolas, Jean-Marie; Lê, Thu Trang (2016). "Operadores de ondículas y modelos de observación multiplicativa: aplicación al análisis de series de tiempo de imágenes SAR" (PDF) . Transacciones IEEE sobre geociencias y teledetección . 54 (11): 6606–6624. doi : 10.1109 / TGRS.2016.2587626 .
enlaces externos
- WaveLab de Stanford en matlab
- libdwt , una biblioteca DWT multiplataforma escrita en C
- Introducción concisa a Wavelets por René Puschinger