Почему scipy.signal.correlate2d () использует такой неэффективный алгоритм?

Question

Через несколько дней после go я запустил сценарий, использующий scipy.signal.correlate2d для вычисления двухмерной автокорреляции изображения 4096x4096. Точный звонок:

zauto = signal.correlate2d(image, image, mode='full', boundary='wrap')

Три дня спустя он все еще работает, и конца не видно. В конце концов я понял, что это должна быть поэлементная свертка методом перебора, процедура, которая идет с N ^ 2, таким образом, 4096 ^ 4 = 281 триллион умножается и складывается.

Тем временем я в конце концов понял, что могу получить желаемый результат, взяв 2-мерное БПФ изображения, преобразовав его в 2-мерный спектр мощности, а затем используя обратное БПФ; т.е.

image -= np.mean(image)            # remove constant bias
zfft = np.fft.fft2(image)          # take 2-D FFT (complex)
zpower = zfft*np.conjug(zfft)      # convert to power spectrum
zauto = np.real(np.ifft2(zpower))  # take inverse FFT
zauto /= zauto[0,0]                # normalize

Для выполнения приведенных выше строк требуется менее одной минуты.

Мой вопрос: почему scipy.signal.correlate2d не включает хотя бы возможность использовать гораздо более эффективный алгоритм, когда это возможно, вместо того, чтобы позволить пользователю обнаружить на собственном опыте, что его просто нельзя использовать для больших изображений?

Answer 1

Поздравляю, вы заново открыли теорему свертки !

Шутки в сторону, scipy дает ли возможность выполнять свертку либо в сигнале, либо в Домен Фурье, но не с явным выбранным вами методом 2D. Функция signal.correlate будет обрабатывать N-мерную свертку и либо попытается выбрать для вас хороший метод (аргумент method="auto"), либо вы можете заставить его использовать тот, который вам нужен.

Но учтите, что метод Фурье не всегда самый эффективный. Хотя свертка на основе БПФ имеет лучшую асимптотику c сложность, чем прямой метод, постоянные коэффициенты больше. Для выполнения БПФ требуется значительный объем бухгалтерского учета и настройки, в то время как прямой метод чрезвычайно прост. Это причина использования опции "auto" и функции choose_conv_method: «лучший» метод зависит от размеров входных данных.

Что касается почему ? На самом деле я не могу ответить на этот вопрос, кроме как сказать, что авторы библиотеки, возможно, чувствовали, что большинство людей, использующих эти инструменты, будут знать о компромиссах. Модуль scipy.signal предоставляет ряд аналогичных методов, и в нескольких частях документации четко указывается, что свертка на основе БПФ не является панацеей.