¿Qué coeficientes de tiempo-frecuencia calcula la transformada Wavelet?

26

La Transformada rápida de Fourier toma operaciones , mientras que la Transformación rápida Wavelet toma O ( N ) . Pero, ¿qué calcula específicamente el FWT?O(NlogN)O(N)

Aunque a menudo se comparan, parece que el FFT y el FWT son manzanas y naranjas. Según tengo entendido, sería más apropiado comparar el STFT (FFT de pequeños fragmentos a lo largo del tiempo) con el Morlet WT complejo , ya que ambos son representaciones de frecuencia de tiempo basadas en sinusoides complejas (corríjame si me equivoco ) Esto a menudo se muestra con un diagrama como este:

Cuadrículas que muestran cómo los coeficientes de FFT y WT corresponden al plano de frecuencia de tiempo

( Otro ejemplo )

La izquierda muestra cómo el STFT es un montón de FFT apilados uno encima del otro a medida que pasa el tiempo (esta representación es el origen del espectrograma ), mientras que la derecha muestra el WT diádico, que tiene una mejor resolución de tiempo a altas frecuencias y mejor frecuencia resolución a bajas frecuencias (esta representación se llama escalograma ). En este ejemplo, para el STFT es el número de columnas verticales (6), y una sola operación O ( N log N ) FFT calcula una sola fila de N coeficientes de N muestras. El total es de 8 FFT de 6 puntos cada una, o 48 muestras en el dominio del tiempo.NO(NlogN)NN

Lo que no entiendo:

  • ¿Cuántos coeficientes calcula una sola operación FWT y dónde están ubicados en el gráfico de frecuencia de tiempo anterior? O(N)

  • ¿Qué rectángulos se completan con un solo cálculo?

  • Si calculamos un bloque de área igual de coeficientes de frecuencia de tiempo usando ambos, ¿obtenemos la misma cantidad de datos?

  • ¿Es el FWT aún más eficiente que el FFT?

Ejemplo concreto usando PyWavelets :

In [2]: dwt([1, 0, 0, 0, 0, 0, 0, 0], 'haar')
Out[2]:
(array([ 0.70710678,  0.        ,  0.        ,  0.        ]),
 array([ 0.70710678,  0.        ,  0.        ,  0.        ]))

Crea dos conjuntos de 4 coeficientes, por lo que es igual al número de muestras en la señal original. Pero, ¿cuál es la relación entre estos 8 coeficientes y los mosaicos en el diagrama?

Actualizar:

En realidad, probablemente estaba haciendo esto mal, y debería estar usando wavedec(), lo que hace una descomposición DWT de varios niveles:

In [4]: wavedec([1, 0, 0, 0, 0, 0, 0, 0], 'haar')
Out[4]: 
[array([ 0.35355339]),
 array([ 0.35355339]),
 array([ 0.5,  0. ]),
 array([ 0.70710678,  0.        ,  0.        ,  0.        ])]
endolito
fuente
2
Para tener una mejor comprensión de cómo funcionan estas ondas de descomposición, una herramienta útil sería poder hacerlo en señales de la vida real: señal de audio, por ejemplo (tengo una pregunta en esta dirección aquí dsp.stackexchange.com/ preguntas / 12694 / stft-and-dwt-wavelets )
Basj
@endolith ¿Se sigue preguntando? Si es así, puedo añadir otros consejos
Laurent Duval
@LaurentDuval Sí, todavía está abierto y todavía no entiendo. Puedo estar confundido porque CWT usa cosas como Morlet y DWT solo usa cosas como Haar o Daubechies. No estoy seguro si el FWT rápido es solo Haar o si también puede usar otros tipos de wavelets.
Endolito
2
@ndolith Solo un comentario para este: el CWT continuo admite una increíble cantidad de formas de wavelet potenciales. Se pueden discretizar exactamente solo con patrones de muestreo (en tiempo o escala) que respeten alguna desigualdad "Heisenberg". Estos patrones dependen de la wavelet. En la mayoría de los casos, los patrones crean un CWT discretizado que es redundante. Algunos lo quieren no redundante, con una escala diádica. Solo muy pocas wavelets lo permiten. Si luego impones que el soporte de wavelets sea finito, entonces Haar es uno, casi imposible de obtener con "wavelets naturales", por eso se construyeron los Daubechies
Laurent Duval

Respuestas:

13

Tiene razón en que el FWT se considera mejor como un "primo" del STFT, en lugar del FT. De hecho, el FWT es solo un muestreo discreto del CWT (transformada de wavelet continua), ya que el FFT / DFT es un muestreo discreto de la transformada de Fourier. Esto puede parecer un punto sutil, pero es relevante al elegir cómo discretiza la transformación.

El CWT y el STFT son análisis redundantes de una señal. En otras palabras, tiene más "coeficientes" (en el caso discreto) de los que necesita para representar completamente una señal. Sin embargo, una transformada de Fourier (o digamos una transformada wavelet usando solo una escala) integra una señal de infinito a infinito. Esto no es muy útil en las señales del mundo real, por lo que truncamos (es decir, la ventana) las transformaciones a longitudes más cortas. La ventana de una señal cambia la transformación: multiplica por la ventana en tiempo / espacio, por lo que en el espacio de transformación tienes la convolución de la transformación de la ventana con la transformación de la señal.

En el caso del STFT, las ventanas tienen (generalmente) la misma longitud (extensión distinta de cero) en todo momento, y son independientes de la frecuencia (usted abre una señal de 10 Hz del mismo ancho que una señal de 10 kHz). Entonces obtienes el espectrograma de cuadrícula rectangular como lo has dibujado.

El CWT tiene esta ventana incorporada por el hecho de que las wavelets se acortan (en el tiempo o en el espacio) a medida que la escala disminuye (como una frecuencia más alta). Por lo tanto, para frecuencias más altas, la ventana efectiva es más corta en duración, y terminas con un diagrama de escala que se parece a lo que has dibujado para el FWT.

La forma de discretizar el CWT depende de usted, aunque creo que hay muestreos mínimos tanto en cambio como en escala para representar completamente una señal. Típicamente (al menos cómo los he usado), para la escala más baja (frecuencia más alta), tomará muestras en todas las ubicaciones de turno (tiempo / espacio). A medida que aumenta la escala (menor frecuencia), puede muestrear con menos frecuencia. La razón es que las bajas frecuencias no cambian tan rápidamente (piense en un crash de platillo versus un bajo: el crash de platillo tiene transitorios muy cortos, mientras que el bajo tardaría más en cambiar). De hecho, en la escala más corta (suponiendo que muestreas en todas las ubicaciones de turno), tienes la representación completa de una señal (puedes reconstruirla usando solo los coeficientes en esta escala). No estoy tan seguro sobre la razón de muestrear la escala. YO' He visto esto sugerido como logarítmico, con (creo) un espacio más cercano entre escalas más cortas. Creo que esto se debe a que las wavelets a escalas más largas tienen una transformada de Fourier más amplia (por lo tanto, "captan" más frecuencias).

Admito que no entiendo completamente el FWT. Mi presentimiento es que en realidad es el muestreo mínimo en shift / scale, y no es una representación redundante. Pero luego creo que pierde la capacidad de analizar (y meterse con) una señal en poco tiempo sin introducir artefactos no deseados. Leeré más al respecto y, si aprendo algo útil, informaré. Esperemos que a otros les guste comentar.

Patricio
fuente
1
"en realidad es el muestreo mínimo en desplazamiento / escala, y no es una representación redundante". Ah! Creo que tienes razón, y esto explicaría por qué siempre se compara con el FFT, que también es una representación mínima.
endolito el
3
El FWT es una muestra crítica del CWT. Todavía estoy tratando de entenderlo mejor, pero he aprendido que STFT y CWT son marcos. La teoría de marcos me supera, pero una noción interesante es la fórmula de incertidumbre, que para el STFT, dw * dt> C (dw es la resolución de frecuencia y dt es la resolución de tiempo). En otras palabras, a medida que intenta resolver mejor la frecuencia, pierde resolución de tiempo. El CWT no tiene esta limitación. Seguiré leyendo e intentaré aclarar mi respuesta anterior una vez que la aclare en mi cabeza.
1
Por lo que entiendo, CWT tiene la misma limitación, pero utiliza una mejor compensación.
endolito
1
"STFT son análisis redundantes de una señal". No creo que sea verdad. Si tiene una señal de 100 puntos, divídala en trozos de 10 puntos, luego realice una FFT de 10 puntos en cada uno, todavía tiene la misma información almacenada en la misma cantidad de muestras.
endolito
11

Considere el caso de la wavelet de Haar. La Transformada rápida Wavelet subdivide recursivamente su señal y calcula la suma y la diferencia de las dos mitades cada vez. La diferencia es la magnitud de la transformación para la wavelet actual y la suma se devuelve para que la persona que llama calcule la magnitud de la transformación para una wavelet dilatada con la mitad de la frecuencia. Por lo tanto, el FWT cubre el plano de frecuencia de tiempo utilizando el patrón descrito en el diagrama que proporcionó.

Tenga en cuenta que el diagrama que dio es un poco engañoso. Lo que realmente están tratando de decirte es que obtienes una muestra a la frecuencia más baja, dos muestras al doble de esa frecuencia, cuatro muestras al cuádruple de esa frecuencia y así sucesivamente. Las propiedades de frecuencia de tiempo de cada wavelet no son tales que cubran su mosaico. En la práctica, cada wavelet cubrirá un área infinita porque tiene un soporte compacto y, por lo tanto, debe estar completamente deslocalizada en términos de frecuencia. Así que solo debes pensar en los centros de esas fichas.

Además, el FWT requiere una wavelet discreta que debe cumplir con un criterio de admisibilidad mucho más restrictivo que las wavelets continuas para el CWT. En consecuencia, las propiedades de frecuencia de tiempo de las wavelets discretas son generalmente horribles (por ejemplo, las wavelets de Daubechies están llenas de características nítidas o tienen una frecuencia cambiante) y la utilidad del plano de frecuencia de tiempo disminuye enormemente en el contexto del FWT. Sin embargo, las wavelets continuas se usan para calcular representaciones de señales de frecuencia de tiempo.


fuente
Sí, entiendo la localización de los coeficientes. Eso es lo mismo que el FFT. Cuando dice "debe adherirse", ¿qué quiere decir? ¿Es solo un requisito si está tratando de obtener una representación mínima / no redundante de la señal? ¿Qué pasa si solo estás tratando de analizarlo / visualizarlo? Agregaré un ejemplo más concreto a la pregunta.
endolito
1
La adhesión al criterio de admisibilidad asegura que existe una resolución de la identidad, es decir, que todas las señales pueden recuperarse de sus transformaciones wavelet. Si no se adhiere a él, entonces no puede recuperar una señal de su transformación, en ese momento debe cuestionar qué es exactamente lo que está analizando (¿incluso refleja alguna información que estaba en la señal?). Si no necesita una representación mínima / no redundante, entonces podría usar el criterio de admisibilidad más laxo del CWT (que le permite definir más wavelets "ideales").
1
Creo que encontrarías mi tesis doctoral realmente útil. Lo pondré en línea para usted ...
¿Lo pusiste en línea? :)
endolith
2
Claro
3

Su referencia lo tiene:

Una secuencia de coeficientes basada en una base ortogonal de pequeñas ondas finitas u ondas pequeñas.

Para más información, puede que le guste la página DWT . Allí presenta las wavelets de Haar, las wavelets de Daubechies y otras. Señala cómo

  • Las wavelets tienen ubicación: la wavelet (1,1, –1, –1) corresponde al “lado izquierdo” versus el “lado derecho”, mientras que las dos últimas wavelets tienen soporte en el lado izquierdo o en el lado derecho, y una es una traducción del otro.
  • Las ondas sinusoidales no tienen ubicación, se extienden por todo el espacio, pero tienen fase, la segunda y la tercera ondas son traslaciones entre sí, que corresponden a una desviación de 90 °, como el coseno y el seno, de las cuales estas son versiones discretas. .

Si, en lugar de wavelets discretas, desea ahora sobre wavelets continuas o wavelets complejas, puede comenzar con series de wavelets .

Más allá de wikipedia, un libro de texto y un curso pueden ser útiles.


fuente
No entiendo esta respuesta. ¿Responde mis preguntas? Lado izquierdo y lado derecho de qué? ¿Qué tiene esto que ver con la representación de frecuencia de tiempo?
Endolith
La descripción "lado izquierdo versus lado derecho" es una vista previa extraída de la página DWT, que muestra que esa página incluye un ejemplo simple para explicar los méritos relativos de la base sinusoidal y la base de las ondas de Haar. Estaba preguntando sobre la naturaleza de los coeficientes en una transformada wavelet. Parecía que estabas buscando intuición. Pensé que podría encontrar ese ejemplo (en su contexto original) útil.
Sí, he leído los artículos de Wikipedia varias veces antes de publicar esta pregunta. No sé si / qué tiene que ver su respuesta con mi pregunta sobre la representación de frecuencia de tiempo. Si es así, ¿podría conectar los puntos? Una FFT de n muestras producirá n coeficientes, que forman una sola columna del espectrograma STFT. ¿Existe una relación correspondiente entre los coeficientes producidos por el WT y el escalograma? Si es así, ¿qué es? ¿Cuál de los cuadros en el cuadro inferior derecho se completa con una sola ejecución a través del FWT?
endolito el
1
Casi todo en las páginas de Wikipedia relacionadas con wavelets está mal actualmente.
3

O(N2)

O(N)O(Nlog(N))O()

Comience desde la ventana STFT genérica (forma continua). Si conecta una ventana infinita de altura de unidad, recupera la transformación de Fourier como un caso especial. Que puede discretizar (y obtener el DFT) y hacerlo rápido (y obtener el FFT).

Comience desde un CWT (forma continua). El CWT continuo admite una increíble cantidad de formas potenciales de wavelet. Se pueden discretizar exactamente solo con patrones de muestreo (en tiempo o escala) que respeten alguna desigualdad de "Heisenberg": una muestra por unidad de superficie. Estos patrones dependen de la wavelet. En la mayoría de los casos, los patrones crean un CWT discretizado que es redundante y producen un marco wavelet.

Algunos lo querían no redundante, con una escala diádica (DWT). Solo unas pocas wavelets (todavía un número infinito, pero no puedes encontrarlas por casualidad) lo permiten. Entre las primeras estaban las wavelets Haar, Franklin y Meyer. Si luego impones que el soporte de wavelet sea finito, Haar fue el único durante mucho tiempo. Es casi imposible obtener una wavelet ortogonal a partir de "wavelets continuas naturales", por eso se construyeron las Daubechies , y más tarde Symmlets y Coiflets . Esas wavelets de forma extraña no tienen fórmulas agradables y simples como la wavelet de Morlet.

O(N)

De hecho, el FWT es solo una muestra discreta del CWT

DWT (o FWT) es exacto, como el DFT / FFT. La mayoría de los otros CWT discretizados (con cualquier wavelet) son aproximadamente aproximadamente (sin mucho daño si tiene suficiente redundancia).

Asi que:

  • kkk804T2×424[ω/2,ω]42×22[ω/8,ω/4][1,1,2,4]
  • k
  • +×O(N)

Las siguientes imágenes revelan cómo una versión continua de la wavelet de Haar wavelet continua de Haar

se puede muestrear en una wavelet discreta y ortogonal: wavelet crítico discreta de Haar

Tenga en cuenta que algunas wavelets discretas, especialmente las largas (como las splines), a veces se calculan utilizando una FFT :)

Laurent Duval
fuente