Каковы недостатки свертки БПФ по сравнению с сверткой в реальном пространстве?

Итак, я знаю, что свертка БПФ имеет более низкую вычислительную сложность, чем свертка в реальном пространстве. Но каковы недостатки свертки БПФ?

Всегда ли размер ядра должен соответствовать размеру изображения, или есть функции, которые позаботятся об этом, например, в пакетах pythons numpy и scipy? А как насчет эффектов сглаживания?

Ответ 1

Свертки БПФ основаны на теореме свертки , которая гласит, что givem выполняет две функции f и g, если Fd() и Fi() обозначают прямого и обратного преобразования Фурье и свертки и умножения * и ., то:

f*g = Fi(Fd(d).Fd(g))

Чтобы применить это к сигналу f и к ядру g, вам нужно позаботиться о некоторых вещах:

f и g должны быть одинакового размера, чтобы шаг умножения был возможен, поэтому вам нужно с нуля заполнить ядро.
При выполнении DFT, что делает FFT, результирующее частотное представление функции является периодическим. Это означает, что по умолчанию ваше ядро обматывает край при выполнении свертки. Если вы этого хотите, тогда все отлично. Но если нет, вам нужно добавить дополнительный нулевой размер ядра, чтобы избежать его.
Большинство (все?) пакетов FFT работают хорошо (по производительности) с размерами, которые не имеют больших основных факторов. Закругление сигнала и размера ядра до следующей мощности двух - это обычная практика, которая может привести к (очень) значительному ускорению.

Если ваш размер сигнала и ядра f_l и g_l, для выполнения простой свертки во временной области требуется g_l * (f_l - g_l + 1) умножения и дополнения (g_l - 1) * (f_l - g_l + 1).

Для подхода FFT вам нужно сделать 3 БПФ размером не менее f_l + g_l, а также f_l + g_l умножения.

Для больших размеров как f, так и g, FFT явно превосходит свою сложность n*log(n). Для небольших ядер прямой подход может быть быстрее.

scipy.signal имеет методы convolve и fftconvolve для вас. И fftconvolve обрабатывает все описанные выше надписи, прозрачно для вас.

Ответ 2

В то время как быстрая свертка имеет большую сложность "большой О", чем прямая свертка; Есть несколько недостатков или предостережений. Я немного подумал об этой теме для статьи, которую я написал некоторое время назад.

Лучшая "большая О" сложность не всегда лучше. Прямая свертка формы может быть быстрее, чем использование БПФ для фильтров меньше определенного размера. Точный размер зависит от платформы и используемых реализаций. Точка пересечения обычно находится в диапазоне 10-40 коэффициентов.
Задержка. Быстрая свертка по своей сути является блочным алгоритмом. Постановка в очередь сотен или тысяч сэмплов за раз перед их преобразованием может быть неприемлемой для некоторых приложений реального времени.
Сложность реализации. Прямая форма проще с точки зрения памяти, пространства кода и теоретического фона автора/сопровождающего.
На платформе DSP с фиксированной точкой (не ЦП общего назначения): соображения ограниченного размера слова для БПФ с фиксированной точкой делают большие БПФ с фиксированной точкой практически бесполезными. На другом конце спектра размеров эти микросхемы имеют специализированные схемы MAC-управления, которые хорошо спроектированы для выполнения вычислений FIR прямой формы, увеличивая диапазон, в котором прямая форма O (N ^ 2) быстрее, чем O (NlogN). Эти факторы имеют тенденцию создавать ограниченную "точку отсчета", в которой БПФ с фиксированной точкой полезны для быстрой свертки.