Двумерная свертка и корреляция на основе FFT в Python

Существует ли двустрочная корреляционная или сверточная функция на основе FFT, встроенная в scipy (или другую популярную библиотеку)?

Существуют такие функции, как:

  • scipy.signal.correlate2d - "прямой метод, реализованный convolveND, будет медленный для больших данных "
  • scipy.ndimage.correlate - "Массив сопоставлен с данным ядром, используя точный расчет (т.е. не БПФ).
  • scipy.fftpack.convolve.convolve, который я действительно не понимаю, но кажется неправильным

В numarray была функция correlate2d() с ключом fft=True, но я думаю, что numarray был сложен в numpy, и я не могу найти, включена ли эта функция.

Ответы

Ответ 1

Я нашел scipy.signal.fftconvolve, также отмеченный магнусом, но в то время не понял, что он n-мерный. Поскольку он встроен и дает правильные значения, он кажется идеальным решением.

От Пример 2D-свертки:

In [1]: a = asarray([[ 1, 2, 3],
   ...:              [ 4, 5, 6],
   ...:              [ 7, 8, 9]])

In [2]: b = asarray([[-1,-2,-1],
   ...:              [ 0, 0, 0],
   ...:              [ 1, 2, 1]])

In [3]: scipy.signal.fftconvolve(a, b, mode = 'same')
Out[3]: 
array([[-13., -20., -17.],
       [-18., -24., -18.],
       [ 13.,  20.,  17.]])

Правильно! С другой стороны, версия STSCI требует некоторой дополнительной работы, чтобы сделать границы правильными?

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

(Метод STSCI также требует компиляции, с которой я не увенчался успехом (я просто прокомментировал части, отличные от python), имеет некоторые ошибки типа this и изменение входов ([1, 2] становится [[1, 2]]) и т.д. Поэтому я изменил принятый ответ на встроенную функцию fftconvolve().)

Корреляция, разумеется, такая же, как свертка, но с одним обратным обращением:

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

и последняя версия была ускорена за счет использования двух-трех размеров внутри (а затем я ускорил ее больше на с использованием реального FFT для реального ввода и используя 5-гладкие длины вместо полномочий из 2: D).

Ответ 2

посмотрите на scipy.signal.fftconvolve, signal.convolve и signal.correlate(есть signal.correlate2d, но он возвращает возвращенный массив, а не центрирован).

Ответ 4

Я потерял информацию о статусе этого пакета в scipy, но я знаю, что мы добавляем ndimage как часть пакета выпуска stsci_python в качестве удобства для наших пользователей:

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

или вы можете извлечь его из репозитория, если хотите:

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

Ответ 5

Я написал обертку с взаимной корреляцией/сверткой, которая заботится о заполнении и nans и включает в себя простую гладкую оболочку здесь. Это не популярный пакет, но он также не имеет зависимостей помимо numpy (или fftw для более быстрых ffts).

Я также внедрил код проверки скорости FFT здесь в случае, если кто-то заинтересован. Это удивительно показывает, что numpy fft быстрее, чем scipy, по крайней мере на моей машине.

EDIT: переместил код в N-мерную версию здесь