Convolución 2D y correlación basadas en FFT en Python

¿Existe una función de convolución cruzada o convolución 2D basada en FFT incorporada en scipy (u otra biblioteca popular)?Convolución 2D y correlación basadas en FFT en Python

Hay algunas funciones como éstas:

scipy.signal.correlate2d - "el método directo ejecutado por convolveND será lento para grandes datos"
scipy.ndimage.correlate - "La matriz se correlaciona con el núcleo dado usando exacta cálculo (es decir, no FFT) ".
scipy.fftpack.convolve.convolve, lo que no entiendo muy bien, pero parece mal

numarray tenía una correlate2d() function with an fft=True switch, pero supongo numarray fue doblado en numpy, y no puedo encontrar si se incluye esta función.

Fuente

2009-07-08 endolith

nota que el uso de cálculo exacto (sin FFT) es exactamente lo mismo que decir que es lento :) Más exactamente, el método basado en FFT será mucho más rápido si usted tiene una señal y un kernel de aproximadamente el mismo tamaño (si el núcleo es mucho más pequeño que la entrada, entonces FFT en realidad puede ser más lento que el cálculo directo). –

Idealmente, el algoritmo de FFT se ocuparía automáticamente de las cosas sin relleno al tamaño correcto para obtener la mejor velocidad. – endolith

Oh, no estás hablando de cero relleno, estás hablando de hacer coincidir una imagen de 5x5 con una imagen de 2000x2000. ¿Por qué el algoritmo no puede adivinar si la FFT sería más eficiente y lo haría de la manera más rápida? – endolith

Encontré scipy.signal.fftconvolve, as also pointed out by magnus, pero no me di cuenta en el momento en que es n -dimensional. Dado que está integrado y produce los valores correctos, parece ser la solución ideal.

De Example of 2D Convolution:

correcta! La versión STSCI, por otro lado, requiere un trabajo adicional para hacer los límites correctos?

In [4]: stsci.convolve2d(a, b, fft = True) 
Out[4]: 
array([[-12., -12., -12.], 
     [-24., -24., -24.], 
     [-12., -12., -12.]])

(El método STSCI también requiere la compilación, que estaba sin éxito con (acabo comentada las partes no Python), tiene algunos errores como this y la modificación de las entradas ([1, 2] se convierte en [[ 1, 2]]), etc. Así que cambió mi respuesta aceptada a la correlación incorporada fftconvolve() función)

, por supuesto, es lo mismo que la convolución, pero con una entrada Invertida:.

In [5]: a 
Out[5]: 
array([[3, 0, 0], 
     [2, 0, 0], 
     [1, 0, 0]]) 

In [6]: b 
Out[6]: 
array([[3, 2, 1], 
     [0, 0, 0], 
     [0, 0, 0]]) 

In [7]: scipy.signal.fftconvolve(a, b[::-1, ::-1]) 
Out[7]: 
array([[ 0., -0., 0., 0., 0.], 
     [ 0., -0., 0., 0., 0.], 
     [ 3., 6., 9., 0., 0.], 
     [ 2., 4., 6., 0., 0.], 
     [ 1., 2., 3., 0., 0.]]) 

In [8]: scipy.signal.correlate2d(a, b) 
Out[8]: 
array([[0, 0, 0, 0, 0], 
     [0, 0, 0, 0, 0], 
     [3, 6, 9, 0, 0], 
     [2, 4, 6, 0, 0], 
     [1, 2, 3, 0, 0]])

y the latest revision ha sido acelerado usando internamente el poder de los dos tamaños (y luego lo aceleré más por using real FFT for real input y using 5-smooth lengths instead of powers of 2: D).

Fuente

2009-11-20 03:22:54 endolith

creo que desea que el paquete scipy.stsci:

http://docs.scipy.org/doc/scipy/reference/stsci.html

In [30]: scipy.__version__ 
Out[30]: '0.7.0' 

In [31]: from scipy.stsci.convolve import convolve2d, correlate2d

Fuente

2009-07-08 20:07:59 ars

Lo vi también, pero no funciona ¿Parece que ya está incluido en SciPy? >>> import scipy.stsci.convolve Rastreo (llamada más reciente pasado): Archivo "", línea 1, en ImportError: Sin módulo llamado convolución – endolith

Hola - pegar la salida de mi pronta anteriormente. ¿Cuál es tu versión? – ars

Claramente algo está mal: http://pastebin.com/mdd2bc6d Es bueno saber que existe, sin embargo. – endolith

He perdido la cuenta de la situación de este paquete en scipy, pero sé que incluimos ndimage como parte de la paquete de la versión stsci_python como una conveniencia para nuestros usuarios:

http://www.stsci.edu/resources/software_hardware/pyraf/stsci_python/current/download

o que debe ser capaz de tracción que desde el repositor Y si lo prefiere:

https://www.stsci.edu/svn/ssb/stsci_python/stsci_python/trunk/ndimage/

Fuente

2009-07-09 03:53:20

De acuerdo con los documentos de SciPy, no se basa en FFT, como mencioné en la pregunta. http://www.scipy.org/SciPyPackages/Ndimage – endolith

El paquete convolve también está disponible en el repositorio stsci_python. Incluye la función correlate2d que tiene el interruptor fft = True que también mencionaste. https://www.stsci.edu/svn/ssb/stsci_python/stsci_python/trunk/convolve/lib/Convolve.py –

¡Oh! Solo puedo importar ese archivo python directamente, si elimino la referencia a _correlate. La correlación FFT está todo en Python. Ahora lo tengo funcionando. :) ¡Gracias! – endolith

vistazo a scipy.signal.fftconvolve, signal.convolve y signal.correlate (hay un signal.correlate2d pero parece devolver una matriz cambiado, no centrado).

Fuente

2009-09-25 13:22:24

Cambié mi respuesta aceptada a esto, como se explica a continuación http://stackoverflow.com/questions/1100100/fft-based-2d-convolution-and-correlation-in-python/1768140#1768140 – endolith

Escribí una envoltura de correlación cruzada/convolución que se encarga de rellenar & nans e incluye una envoltura suave simple here. No es un paquete popular, pero tampoco tiene dependencias además de numpy (o fftw para ffts más rápidos).

También he implementado un código de prueba de velocidad FFT here en caso de que a alguien le interese. Muestra, sorprendentemente, que la fft de numpy es más rápida que la de scipy, al menos en mi máquina.

EDIT: movido código para N-dimensional versión here

Fuente

2011-12-10 02:45:41 keflavich

Convolución 2D y correlación basadas en FFT en Python

Respuesta

Cuestiones relacionadas