Besoin d'une convolution FFT circulaire en Python

Question

je besoin d'un analogue plus rapide de

scipy.signal.convolve2d(data, filter, boundary="wrap", mode="same") 

Tu ne peux pas me conseiller comment le remplacer?

P.S. scipy.signal.fftconvolve est assez rapide, mais il n'a pas l'option boundary et je ne peux pas le faire fonctionner en mode de convolution circulaire.

Answer 1

Si vous calculez les éléments suivants:

from scipy.fftpack import fft2, ifft2 

f2 = ifft2(fft2(data, shape=data.shape) * fft2(filter, shape=data.shape)).real 

alors f2 contient les mêmes valeurs que convolve2d(data, filt, boundary='wrap', mode='same'), mais les valeurs sont décalées (« roulées », dans la terminologie numpy) dans chaque axe. (Ceci est une application du convolution theorem.)

Voici une courte fonction qui roule le résultat à la donner même résultat que l'appel de fonction convolve2d:

def fftconvolve2d(x, y): 
    # This assumes y is "smaller" than x. 
    f2 = ifft2(fft2(x, shape=x.shape) * fft2(y, shape=x.shape)).real 
    f2 = np.roll(f2, (-((y.shape[0] - 1)//2), -((y.shape[1] - 1)//2)), axis=(0, 1)) 
    return f2 

Par exemple,

In [91]: data = np.random.rand(256, 256) 

In [92]: filt = np.random.rand(16, 16) 

In [93]: c2d = convolve2d(data, filt, boundary='wrap', mode='same') 

In [94]: f2 = fftconvolve2d(data, filt) 

Vérifiez que les résultats sont les mêmes:

In [95]: np.allclose(c2d, f2) 
Out[95]: True 

Vérifiez la performance:

In [96]: %timeit c2d = convolve2d(data, filt, boundary='wrap', mode='same') 
44.9 ms ± 77.3 µs per loop (mean ± std. dev. of 7 runs, 10 loops each) 

In [97]: %timeit f2 = fftconvolve2d(data, filt) 
5.23 ms ± 11.2 µs per loop (mean ± std. dev. of 7 runs, 100 loops each) 

La version FFT est beaucoup plus rapide (mais notez que j'ai choisi les dimensions de data être une puissance de 2).