Convolution 2D et corrélation 2D basée sur FFT en Python

Existe-t-il une fonction de corrélation croisée ou de convolution 2D basée sur FFT intégrée dans scipy (ou une autre bibliothèque populaire)?Convolution 2D et corrélation 2D basée sur FFT en Python

Il y a des fonctions comme celles-ci:

scipy.signal.correlate2d - « la méthode directe mis en œuvre par convolveND sera lent pour les grandes données »
scipy.ndimage.correlate - « Le tableau est en corrélation avec le noyau donné en utilisant exactement calcul (c'est-à-dire non FFT). "
scipy.fftpack.convolve.convolve, que je ne comprends pas vraiment, mais il semble mal

numarray avait un correlate2d() function with an fft=True switch, mais je suppose que numarray était plié en numpy, et je ne trouve pas si cette fonction a été incluse.

Source

2009-07-08 endolith

Notez que l'utilisation calcul exact (pas FFT) est exactement la même chose que dire qu'il est lent :) Plus exactement, la méthode FFT sera beaucoup plus rapide si vous avez un signal et un noyau de taille approximativement égale (si le noyau est beaucoup plus petit que l'entrée, alors la FFT peut être plus lente que le calcul direct). –

Idéalement, l'algorithme FFT prend automatiquement en charge les opérations de remplissage à zéro pour obtenir la meilleure vitesse. – endolith

Oh, vous ne parlez pas de zéro rembourrage, vous parlez de faire correspondre une image 5x5 avec une image 2000x2000. Pourquoi l'algorithme ne peut-il pas deviner si la FFT serait plus efficace et le faire de la manière la plus rapide? – endolith

J'ai trouvé scipy.signal.fftconvolve, as also pointed out by magnus, mais je n'avais pas réalisé à ce moment-là que c'est n -dimensional. Depuis qu'il est intégré et produit les bonnes valeurs, il semble que la solution idéale.

De Example of 2D Convolution:

Correct! D'autre part, la version STSCI nécessite un travail supplémentaire pour que les limites soient correctes?

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

(La méthode STSCI exige également la compilation, que j'a échoué avec (je viens de parler les parties non-python), a quelques bugs comme this et modifier les entrées ([1, 2] devient [[ 1, 2]]), etc. Je suis donc changé ma réponse acceptée à la fftconvolve() fonction intégrée)

corrélation, bien sûr, est la même chose que convolution, mais avec une entrée inversée.

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]])

et the latest revision a été accélérée en utilisant en interne des puissances de deux tailles (et puis j'ai accéléré plus par using real FFT for real input et using 5-smooth lengths instead of powers of 2: D).

Source

2009-11-20 03:22:54 endolith

Je pense que vous voulez que le paquet 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

Source

2009-07-08 20:07:59 ars

J'ai vu ça aussi, mais ça ne marche pas t semble être inclus dans SciPy plus? >>> import scipy.stsci.convolve retraçage (le plus récent appel dernier): Fichier "", ligne 1, dans ImportError: Aucun module nommé convolve – endolith

Salut - J'ai collé la sortie de mon message ci-dessus. Quelle est ta version? – ars

Clairement quelque chose ne va pas: http://pastebin.com/mdd2bc6d Bon de savoir qu'il existe, cependant. – endolith

J'ai perdu la trace de l'état de ce paquet dans scipy, mais je sais que nous incluons ndimage dans le cadre du stsci_python package de libération à titre de commodité pour nos utilisateurs:

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

ou vous devriez être en mesure de traction à partir du repositor y si vous préférez:

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

Source

2009-07-09 03:53:20

Selon SciPy docs, il n'est pas basé sur FFT, cependant, comme je l'ai mentionné dans la question. http://www.scipy.org/SciPyPackages/Ndimage – endolith

Le package convolve est également disponible dans le référentiel stsci_python. Il inclut la fonction correlate2d qui a le commutateur fft = True que vous avez également mentionné. https://www.stsci.edu/svn/ssb/stsci_python/stsci_python/trunk/convolve/lib/Convolve.py –

Oh! Je peux juste importer ce fichier python directement, si je supprime la référence à _correlate. La corrélation FFT est tout en Python. Maintenant je l'ai fonctionné. :) Merci! – endolith

regard sur scipy.signal.fftconvolve, signal.convolve et signal.correlate (il y a un signal.correlate2d mais il semble retourner un tableau décalé, non centré).

Source

2009-09-25 13:22:24

J'ai changé ma réponse acceptée à cela, comme expliqué ci-dessous http://stackoverflow.com/questions/1100100/fft-based-2d-convolution-and-correlation-in-python/1768140#1768140 – endolith

J'ai écrit un wrapper de corrélation croisée/convolution qui prend soin de rembourrage & nans et comprend un emballage lisse simple here. Ce n'est pas un paquet populaire, mais il n'a pas non plus de dépendances autres que numpy (ou fftw pour des ffts plus rapides).

J'ai également mis en œuvre un code de test de vitesse FFT here dans le cas où quelqu'un est intéressé. Cela montre - étonnamment - que fft numpy est plus rapide que scipy, au moins sur ma machine.

EDIT: déplacé le code à la version N-dimensionnelle here

Source

2011-12-10 02:45:41 keflavich

Convolution 2D et corrélation 2D basée sur FFT en Python

Répondre

Questions connexes