Блог

Свертка-одна из важнейших математических операций, используемых при обработке сигналов. Эта простая математическая операция появляется во многих научных и промышленных приложениях, начиная с ее использования в крупном CNN с миллиардным слоем и заканчивая простым шумоподавлением изображений. Свертка может быть как аналоговой, так и дискретной по своей природе, но из-за цифровой природы современных компьютеров дискретная свертка-это та, которую мы видим повсюду!

Дискретная свертка двух одномерных векторов a[n] и b[n], y[n] ределяется как

Поскольку для этого требуется умножение двух векторов, временная сложность дискретной свертки с использованием умножения(при условии, что векторы длины n) равна O(n²). Вот где на помощь приходит быстрое преобразование Фурье(БПФ). Используя БПФ, мы можем уменьшить эту сложность с O(n²) до О(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 раз быстрее, чем выходные данные, генерируемые обычной дискретной сверткой!