STFT y DWT (Wavelets)

STFT se puede utilizar con éxito en datos de sonido (con un archivo de sonido .wav, por ejemplo) para hacer algunas modificaciones en el dominio de la frecuencia (ejemplo: eliminación de ruido).
Con N=441000(es decir, 10 segundos a la velocidad de muestreo fs=44100), windowsize=4096, overlap=4, STFT produce aproximativamente un 430x4096array (primera coordenada: marco de tiempo, segunda coordenada: bin de frecuencia). Se pueden hacer modificaciones en esta matriz, y la reconstrucción se puede hacer con overlap-add (*).

¿Cómo es posible hacer algo similar con las wavelets ? (DWT), es decir, obtener una matriz de forma similar a x b, con amarcos de tiempo y bintervalos de frecuencia, ¿realiza alguna modificación en esta matriz y, al final, recupera una señal? Cómo ? ¿Cuál es el wavelet equivalente a overlap-add ? ¿Cuáles serían las funciones de Python involucradas aquí (no he encontrado un ejemplo fácil de modificación de audio con pyWavelets...)?

(*): Aquí está el marco STFT que se puede usar:

signal = stft.Stft(x, 4096, 4)    # x is the input
modified_signal = np.zeros(signal.shape, dtype=np.complex)

for i in xrange(signal.shape[0]):    # Process each STFT frame
    modified_signal[i, :] =  signal[i, :] * .....  # here do something in order to
                                                   # modify the signal in frequency domain !
y = stft.OverlapAdd(modified_signal, 4)   # y is the output

El objetivo es encontrar un marco similar con wavelets.

fft wavelet dft python stft Basj
fuente

Un comentario secundario: hacer ese tipo de "filtrado" en el STFT es una muy mala idea. No es una excelente manera de hacer la mayoría de las cosas que realmente quieres hacer. ¿Qué estás tratando de lograr realmente?

Peter K.

Tenga en cuenta que PyWavelets es solo para la transformación de wavelet discreta. Si desea hacer cosas similares a STFT, comprendería más fácilmente la transformación de wavelet continua, como la transformación Q constante, que es una transformación de Gabor, esencialmente lo mismo que una transformación de wavelet continua Morlet compleja , pero está diseñada para ser invertible: grrrr.org/research/software/nsgt

endolith

(Esta pregunta revivida por "Comunidad".) En mi opinión, las wavelets se superponen y agregan de una manera muy similar a STFT. así que no entiendo la naturaleza de la pregunta.

Robert Bristow-Johnson

¿Se necesitan más detalles?

Laurent Duval

Respuestas:

La transformación de Fourier a corto plazo es generalmente una transformación redundante, generalmente implementada con el mismo submuestreo en cada frecuencia. Si la ventana está bien elegida, está completa: puede invertirla y recuperar cualquier señal inicial.

Como es redundante y completo, tiene muchas inversas perfectas. Se puede implementar y comprender utilizando herramientas más genéricas: bancos de filtros complejos (sobremuestreados). Dado un tipo y longitud de ventana más la superposición, le proporciona un banco de filtros de análisis para el que puede calcular si es invertible o no. Si lo hace, puede calcular un inverso natural y también inversos optimizados . La suma de superposición es solo una de las muchas inversas potenciales, probablemente la más común, que a menudo restringe la elección de la ventana.

Las transformaciones de wavelets discretas estándar también son bancos de filtros, con la diferencia de que el submuestreo no es el mismo en cada banda de frecuencia (o escala más adecuada). Esto se convierte en longitudes desiguales para cada escala. Sin embargo, existen implementaciones de wavelet redundantes que producen "una matriz rectangular" de coeficientes con los que puede trabajar. Los esquemas más conocidos se denominan con diferentes nombres: wavelets invariantes o invariantes en el tiempo, wavelets no diezmadas, transformada wavelet estacionaria(SWT), y algunas veces ciclo-spinning. Su reconstrucción estándar implica pasos similares a la superposición-adición, excepto que están más "incrustados" debido a los diferentes factores de muestreo en las escalas. Puede usarlos con cualquier wavelet discreta de una biblioteca, o incluso diseñando su propia wavelet. La razón es que las wavelets discretas estándar se diseñaron teniendo en cuenta la no redundancia, lo que restringe la elección de wavelets. Con la redundancia, aumenta la elección de wavelets, ya que las restricciones para cumplir son menos estrictas. El avatar "definitivo" es la transformada wavelet continua, que admite "casi" cada wavelet de síntesis inversa. Mi última oración es bastante mala, espero que entiendas el significado: cuando una matriz cuadrada es invertible, solo tiene una inversa. Cuando una matriz "rectangular" es invertible a la izquierda de forma generalizada,

Parece que hay una implementación en Python de la transformación de Wavelet estacionaria . Puede encontrar algunas referencias en 2.3.4. Capítulo de traducción de wavelets invariantes del artículo vinculado .

Generalmente es mucho más robusto para detección, eliminación de ruido o restauración en aplicaciones prácticas (geofísica, pruebas no destructivas, ultrasonidos, vibraciones).

Laurent Duval
fuente

¿El significado "redundante" "tiene más información en la salida que la necesaria para reproducir la entrada"?

endolito

Exactamente. Generalmente para una señal de muestra, obtienes coeficientes después de la transformación. Esto significa que puede usar esto para su beneficio. Por ejemplo, obtienes varias inversas potenciales, algunas más prácticas que otras. Más importante aún, cuando se procesa en el dominio de transformación (mejora, detección, eliminación de ruido, filtrado adaptativo, restauración, desconvolución, separación de fuente) se obtiene robustez y menor sensibilidad al ruido. Esto viene de la "diversidad" adicional en los datos transformados. Cuando solo se usa correctamente ...

N

$N$

M > N

$M> N$

Laurent Duval

La razón por la que necesita superponer agregar / superponer guardar para filtrar con la transformada de Fourier de tiempo breve es básicamente que las funciones básicas asociadas con los coeficientes que obtiene se definen en un cierto rango de tiempo (en oposición a un solo punto en el tiempo). La transformada de Fourier que utiliza para calcular los coeficientes de expansión también implementa la convolución en un dominio circular definido por la longitud de su trama de señal. Eso significa que los dos puntos finales del marco están realmente identificados y cerrados en un círculo. Es por eso que debe asegurarse de que las funciones básicas de los coeficientes que edite nunca afecten a ambos extremos del marco al ajustarlas.

Las wavelets no son vectores propios de traducción en el tiempo ni se calculan mediante convolución circular. Esto significa que no necesita superponer agregar o guardar ni ningún otro método que trate con los efectos secundarios de la convolución circular. En cambio, los vectores de base wavelet son solo una posible base para describir su señal. La transformada wavelet (completa, discreta, posiblemente ortogonal) no es más que un cambio de base del dominio del tiempo al dominio wavelet. Los cambios de base pueden invertirse (aplicando el inverso de la matriz de cambio de base que lo llevó allí) y puede volver al dominio del tiempo.

Los parámetros que proporcionó como tamaño de ventana, superposición, frecuencia de muestreo no son aplicables a la transformación wavelet. Lo único que necesitas es una wavelet madre. Si desea comparar los resultados con su salida STFT, puede elegir cualquiera de los vectores básicos STFT (es decir, su ventana multiplicada por una portadora exponencial compleja) como el prototipo de wavelet. Luego, aplica la transformada wavelet rápida, que descompondrá su señal en un árbol de señales filtradas y diezmadas de paso alto y bajo que finalmente se convertirán en sus coeficientes. Cada coeficiente está asociado con un vector base wavelet y sus parámetros (escala, tiempo) o (frecuencia, tiempo). Puede manipular los coeficientes y luego aplicar la transformada de wavelet discreta inversa. Tomará sus coeficientes y los ejecutará a través de un banco de filtros de resíntesis para producir una señal nuevamente.

Estos procesos no son triviales y posiblemente difíciles de digerir para un principiante. Pero debería poder encontrar bibliotecas / cajas de herramientas para su plataforma de elección que implementen la transformación wavelet rápida y su inversa. Sin embargo, si desea realizar su propia base de wavelet, deberá derivar los coeficientes de filtro para los bancos de filtros de descomposición y síntesis. Eso requiere una teoría profunda, y probablemente tendrá que estudiarla primero.

Hay otros sabores de la transformada wavelet, a saber, la transformada wavelet continua que funciona con una base sobrecompleta. Es mucho más lento de calcular y mucho más difícil de invertir, por lo que actualmente no es una opción para lo que desea hacer.

Jazzmaniac
fuente

Gracias por tu respuesta. La razón principal por la que estoy tratando de tener un marco de código es que siempre me he dado cuenta (desde mi infancia hasta hace unos años, cuando terminé mi doctorado (por supuesto, no relacionado con DSP, si es así, no preguntaría) ¡Así que las preguntas para novatos aquí!)) es que manipular material de la vida real (por ejemplo, señal de audio en DSP) ayuda mucho a comprender la teoría profunda. Lo que me gustaría código es: Audio sound -> Wavelet transform -> (do something on the array) -> Inversion -> Audio output. Con mucho (hacer algo en la matriz), estoy seguro de que entenderé un poco más cómo funciona la wavelet.

Basj

@Basj, entonces haz lo que dije. Encuentre una biblioteca de Python que admita la transformación de wavelet rápida y su inversa y luego juegue con el árbol de coeficientes generado. ¡Buena suerte y diviertete!

Jazzmaniac

"no todos son aplicables a la transformada wavelet" Son aplicables a CWT, ¿verdad?

Endolith

Hay muchas formas de definir una base wavelet. Por lo general, una wavelet se parece a:

w_{x_{0}, k_{0}} (x) = A \exp (i k_{0} x) e (k_{0} (x - x_{0}))

$w_{x_0,k_0}(x) = A\exp(ik_0x)e(k_0(x-x_0))$

En el que es el centro en el tiempo, es el centro en frecuencia y es una función de ventana. absorbe la fase y la normalización. La principal forma en que esto difiere de su STFT es que el ancho de la ventana depende de . $x_0$ $k_0$ $e$ $A$ $k$

Por lo general, uno usa puntos discretos para limitar el número de wavelets. Como en su STFT, a menudo es bueno usar una cantidad mayor de puntos que la dimensionalidad de la señal. El objetivo es aproximar la respuesta que obtendría utilizando todos los posibles , pero con recursos computacionales razonables. $(x_0,k_0)$ $(x_0,k_0)$

Debido a que la dimensionalidad de los datos transformados excede la de la señal, la base wavelet no será ortonormal. Es decir, lo siguiente será falso:

⟨ w_{k_{0}, x_{0}} | w_{k_{0}^{'}, x_{0}^{'}} ⟩ = δ (x_{0}, x_{0}^{'}) δ (k_{0}, k_{0}^{'})

$\left\langle w_{k_0, x_0} | w_{k_0',x_0'} \right\rangle = \delta(x_0,x_0')\delta(k_0,k_0')$

Sin embargo, para y adecuados , puede hacer arreglos para que la base se complete en exceso: $A$ $w$

\sum_{x_{0}, k_{0}} | w_{x_{0}, k_{0}} ⟩ \frac{1}{\sqrt{k_{0}}} ⟨ w_{x_{0}, k_{0}} | = identity

$\sum_{x_0,k_0} \left| w_{x_0,k_0} \right\rangle \frac{1}{\sqrt{k_0}} \left\langle w_{x_0,k_0} \right| = \text{identity}$

En otras palabras, puede reconstruir la señal perfectamente simplemente sumando sus wavelets constituyentes.

Su "modificación" simplemente se puede insertar en la suma anterior:

my_filter = \sum_{x_{0}, k_{0}} | w_{x_{0}, k_{0}} ⟩ f (x_{0}, k_{0}) ⟨ w_{x_{0}, k_{0}} |

$\text{my_filter} = \sum_{x_0,k_0} \left| w_{x_0,k_0} \right\rangle f(x_0,k_0) \left\langle w_{x_0,k_0} \right|$

Actualización 2013-11-19: Agregando detalles de implementación a continuación según lo solicitado.

Para alguna señal , deseamos calcular coeficientes: $f(x)$

c_{x_{0}, k_{0}} = ⟨ w_{x_{0}, k_{0}} | f ⟩

$c_{x_0,k_0} = \left\langle w_{x_0,k_0} | f \right\rangle$

Para un fijo , puede verse como una función de , y esta función es simplemente una versión filtrada de . Específicamente, es una convolución de con , que podemos calcular de manera eficiente utilizando un método de Fourier. Por lo tanto, podemos calcular eficientemente todos los siguiente manera: $k_0$ $c{x_0,k_0}$ $x_0$ $f$ $f$ $w_{0,k_0}$ $c_{x_0,k_0}$

Aplique una transformada de Fourier a para obtener . Probablemente quiera hacer esto una ventana a la vez, con superposición suficiente para poder tirar los artefactos de ventanas, etc., pero por simplicidad supongamos que hace toda la señal de una vez, y que su longitud es una potencia de dos. $f$ $\hat f$
Para cada en alguna progresión geométrica con un espacio de aproximadamente del ancho de banda del filtro (o más fino si lo desea):
- Forme el producto de con . $\hat f$ $\hat w_{0,k_0}$
- Trunca el espectro a algún intervalo cuya longitud sea una potencia de dos, y que contenga la porción distinta de cero de . $[k_l,k_r)$ $\hat w_{0,k_0}$
- Aplica una transformada inversa de Fourier a eso.
- Multiplique eso por para corregir la fase. El resultado es visto como una función de . $exp(ix\frac{k_l+k_r}{2})$ $c_{x_0,k_0}$ $x_0$

Esto calcula todos los coeficientes wavelet. Puede elegir la resolución en ajustando la relación en la progresión geométrica. La resolución en se establece por la longitud del espectro truncado, y cambiará dependiendo del ancho de banda de , que a su vez depende de . El esfuerzo computacional es una transformación de Fourier a alta resolución de tiempo, más una transformación inversa de Fourier para cada valor de a una resolución de tiempo mucho más baja. Funciona casi igual que STFT, tal vez más lento por algún pequeño factor que depende de la resolución que elija. $k_0$ $x_0$ $w_{0,k_0}$ $k_0$ $k_0$

Luego puede modificar como mejor le parezca, y puede reconstruir la señal invirtiendo el proceso anterior, sumando los espectros sobre antes de finalmente hacer una transformación de Fourier inversa general. $c_{x_0,k_0}$ $k_0$

Los espectros truncados a veces presentan problemas de normalización, dependiendo de cómo se defina su FFT. No intentaré cubrir todas las posibilidades aquí. La normalización es básicamente un problema fácil. ;-)

La única parte que queda es elegir una envoltura wavelet adecuada. Resulta que es más fácil acertar que acertar . Una definición adecuada (de muchas posibilidades) es: $\hat w_{x_0,k_0}(k)$ $w_{x_0,k_0}(x)$

{\hat{w}}_{x 0, k 0} = A e x p (- i (k - k_{0}) x_{0}) e x p (- (Q l o g (k / k_{0}))^{2})

$\hat w_{x0,k0} = A exp(-i(k-k_0)x_0) exp(-(Q log(k/k_0))^2)$

en el que es una constante adimensional que selecciona el ancho de banda de su filtro, es decir, la resolución de frecuencia de sus wavelets, y se elige según sea necesario para la normalización. Con esta definición y resolución suficientemente alta para , la condición de sobrecomplete se mantiene y la reconstrucción de la señal funcionará. $Q$ $A$ $k_0$

apt1002
fuente

Gracias por recordar estos puntos importantes sobre la teoría wavelet, que son realmente necesarios para comprender cómo funciona. Pero aquí la pregunta sería más sobre la construcción de un código marco que funcionaría en la señal de audio, por ejemplo. Las preguntas son: cómo lidiar con estas sumas infinitas, cómo elegir las ventanas (o más bien mother-wavelet ), cómo hacerlo usando pyWavelets en Python (u otro lenguaje equivalente, luego traduciré a Python), cómo elija los parámetros (como en mi ejemplo para audio: frecuencia de muestreo = 44100, ventana fft = 4096, superposición = 4, etc.)

Basj

Su noción de sobrecompletar no es precisa. Una base completa significa que el proyector canónico sobre la base es el operador de identidad. Pero escribir es como la suma del producto externo que necesita ortonormalidad. Para el sobrecompletado no puede tener ortonormalidad, por lo que la descomposición externa del producto no funciona. Pero puede hacerlo funcionar diciendo que una base está completa (y posiblemente sobrecompleta), si hay coeficientes para que

a_{k}

$a_k$

\sum_{k} | k ⟩ a_{k} ⟨ k | = I d

$\sum_k \left| k \rangle a_k \langle k \right| = \mathrm{Id}$

Jazzmaniac

hmm, has introducido una wavelet de morlet, pero todas las wavelet no tienen fb y fc, por lo que pueden tener una constante , también es imposible hacer un DWT con morlet, bx no es ortogonal, en realidad no pude obtener una buena resolución para estimar la frecuencia con DWT en comparación con cwt o STFT @ apt1002

K

$K$

Electricman

a_{k}

$a_k$

a_{k}

$a_k$

f

$f$

La mejor manera de ver si funciona o no sería proporcionar un ejemplo de código mínimo (con pyWavelet, por ejemplo, debería ser posible en unas pocas líneas, me imagino) (lo haré bien una vez que lo entienda, creo que ¡Necesito unos días más para leer sobre wavelets!)

Basj