numpy - señales - convolucion rapida

¿Cuáles son las desventajas de la convolución por FFT en comparación con la convolución del espacio real?

Question

Así que soy consciente de que una convolución por FFT tiene una complejidad computacional menor que una convolución en el espacio real. ¿Pero cuáles son las desventajas de una convolución FFT?

¿El tamaño del kernel siempre tiene que coincidir con el tamaño de la imagen, o hay funciones que se ocupan de esto, por ejemplo, en los paquetes de pythons numpy y scipy? ¿Y qué pasa con los efectos anti-aliasing?

Answer 1

Mientras que la convolución rápida tiene mejor complejidad de "gran O" que la convolución de forma directa; Hay algunos inconvenientes o advertencias. Pensé un poco en este tema para un artículo que escribí hace un tiempo.

1. Mejor complejidad "grande O" no siempre es mejor. La convolución de forma directa puede ser más rápida que usar FFT para filtros más pequeños que un tamaño determinado. El tamaño exacto depende de la plataforma y las implementaciones utilizadas. El punto de cruce está generalmente en el rango de 10-40 coeficientes.

2. Estado latente. La rápida convolución es inherentemente un algoritmo de bloques. Poner en cola cientos o miles de muestras a la vez antes de transformarlas puede ser inaceptable para algunas aplicaciones en tiempo real.

3. Complejidad de implementación. La forma directa es más simple en términos de memoria, espacio de código y en el fondo teórico del escritor / mantenedor.

4. En una plataforma DSP de punto fijo (no es una CPU de propósito general): las consideraciones de tamaño de palabra limitado de FFT de punto fijo hacen que las FFT de punto fijo grandes sean casi inútiles. En el otro extremo del espectro de tamaño, estos chips tienen instrucciones MAC especializadas que están bien diseñadas para realizar el cálculo FIR de forma directa, lo que aumenta el rango en el que la forma directa O O (N ^ 2) es más rápida que O (NlogN). Estos factores tienden a crear un "punto dulce" limitado donde las FFT de puntos fijos son útiles para la Convolución rápida.

Answer 2

Las convoluciones de FFT se basan en el teorema de convolución , que establece que dan dos funciones f y g , si Fd() y Fi() denotan la transformada de Fourier directa e inversa, y * y . convolución y multiplicación, entonces:

f*g = Fi(Fd(d).Fd(g))

Para aplicar esto a una señal f y un kernel g , hay algunas cosas que debes cuidar:

• f y g tienen que ser del mismo tamaño para que el paso de multiplicación sea posible, por lo que es necesario rellenar el kernel con un cero.
• Cuando se realiza una DFT, que es lo que hace la FFT, la representación resultante en el dominio de la frecuencia de la función es periódica. Esto significa que, de forma predeterminada, su kernel se envuelve alrededor del borde al hacer la convolución. Si quieres esto, entonces todo es genial. Pero si no, tienes que agregar un relleno adicional de cero del tamaño del kernel para evitarlo.
• La mayoría (¿todos?) Los paquetes FFT solo funcionan bien (en cuanto a rendimiento) con tamaños que no tienen factores primarios importantes. Redondear la señal y el tamaño del kernel a la siguiente potencia de dos es una práctica común que puede resultar en una (muy) importante aceleración.

Si sus tamaños de señal y kernel son g_l y g_l , hacer una convolución directa en el dominio del tiempo requiere g_l * (f_l - g_l + 1) multiplicaciones y (g_l - 1) * (f_l - g_l + 1) adiciones.

Para el enfoque de FFT, tiene que hacer 3 FFT de tamaño al menos f_l + g_l , así como las multiplicaciones de f_l + g_l .

Para tamaños grandes de f y g , la FFT es claramente superior con su complejidad n*log(n) . Para los granos pequeños, el enfoque directo puede ser más rápido.

scipy.signal tiene métodos de convolve y fftconvolve para que juegues. Y fftconvolve maneja todo el relleno descrito anteriormente de manera transparente para usted.