Свертка-одна из важнейших математических операций, используемых при обработке сигналов. Эта простая математическая операция появляется во многих научных и промышленных приложениях, начиная с ее использования в крупном CNN с миллиардным слоем и заканчивая простым шумоподавлением изображений. Свертка может быть как аналоговой, так и дискретной по своей природе, но из-за цифровой природы современных компьютеров дискретная свертка-это та, которую мы видим повсюду!
Дискретная свертка двух одномерных векторов a[n] и b[n], y[n] ределяется как
Поскольку для этого требуется умножение двух векторов, временная сложность дискретной свертки с использованием умножения(при условии, что векторы длины n) равна O(n2). Вот где на помощь приходит быстрое преобразование Фурье(БПФ). Используя БПФ, мы можем уменьшить эту сложность с O(n2) до О(nlog(n))!
Интуиция, лежащая в основе использования БПФ для свертки
Один из наиболее фундаментальных результатов обработки сигналов гласит, что свертка во временной области эквивалентна умножению в частотной области. Для выполнения свертки мы можем преобразовать оба сигнала в их представления в частотной области, а затем использовать обратное преобразование Фурье для преобразования произведения Адамара (или точечного произведения) для получения сложного ответа. Рабочий процесс можно резюмировать следующим образом
Установка:
Для целей этой статьи мы будем использовать некоторые встроенные функции из библиотек Python numpy и scipy. Вы можете использовать менеджер пакетов pip для их установки.
pip install scipy numpyСвертка БПФ в Python
Для вычисления свертки с использованием FFT мы будем использовать функцию fftconvolve() в библиотеке scipy.signal на Python.
Синтаксис: scipy.signal.fftconvolve(a, b, mode=’full’’)
Параметры:
- a: 1-й входной вектор
- b: 2-й входной вектор
- режим: Помогает указать размер и тип вывода свертки
- ‘full’: Функция вернет полный вывод свертки
- same«: Функция вернет вывод с размерами, такими же, как вектор «a», но с центром в центре вывода из режима «полный»
- ‘valid’: Функция возвращает только те значения, для вычисления которых не требовалось заполнение нуля
Ниже приводится реализация:
from scipy import signal
a = [1, 2, 3]
b = [4, 5, 6]
y = signal.fftconvolve(a, b, mode = 'full')
print('The convoluted sequence is ', y)
Выход:
Запутанная последовательность такова [ 4. 13. 28. 27. 18.]Сравнение производительности свертки БПФ с нормальной дискретной сверткой
- Для вычисления нормальной линейной свертки двух векторов мы будем использовать np.свернуть .
- В %timeit магическая функция записных книжек Jupyter использовалась для вычисления общего времени, требуемого каждой из 2 функций для заданных векторов.
Ниже приводится реализация:
import numpy as np
from scipy import signal
a = np.random.randn(10**5)
b = np.random.randn(10**5)
print('Time required for normal discrete convolution:')
%timeit np.convolve(a, b)
print('Time required for FFT convolution:')
%timeit signal.fftconvolve(a, b)
Выход:
Время, необходимое для нормальной дискретной свертки:
1,1 с ± 245 мс на цикл (среднее значение ± std. dev. из 7 запусков, по 1 циклу в каждом)
Время, необходимое для свертки БПФ:
17,3 мс ± 8,19 мс на цикл (среднее значение ± std. dev. из 7 запусков, по 10 циклов в каждом)Вы можете видеть, что выходные данные, генерируемые сверткой FFT, в 1000 раз быстрее, чем выходные данные, генерируемые обычной дискретной сверткой!
