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

Question

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

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

Answer 1

БПФ свертки основаны на теореме свертки, которая утверждает, что дают две функции 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) дополнения.

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

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

scipy.signal имеет оба convolve а также fftconvolve методы для вас, чтобы поиграть. А также fftconvolve обрабатывает все отступы, описанные выше, прозрачно для вас.

Answer 2

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

1. Лучшая "большая О" сложность не всегда лучше. Прямая свертка формы может быть быстрее, чем использование БПФ для фильтров меньше определенного размера. Точный размер зависит от платформы и используемых реализаций. Точка пересечения обычно находится в диапазоне 10-40 коэффициентов.

2. Задержка. Быстрая свертка по своей сути является блочным алгоритмом. Постановка в очередь сотен или тысяч сэмплов за раз перед их преобразованием может быть неприемлемой для некоторых приложений реального времени.

3. Сложность реализации. Прямая форма проще с точки зрения памяти, пространства кода и теоретического фона автора / сопровождающего.

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