资讯

历史

科技

环境与自然

成长

游戏

财经

文学与艺术

美食

健康

家居

文化

情感

汽车

三农

军事

旅行

运动

教育

生活

星座命理

离散卷积与快速傅里叶变换(FFT)详解

创作时间:

作者:

@小白创作中心

离散卷积与快速傅里叶变换(FFT)详解

引用

CSDN

https://blog.csdn.net/2301_82023330/article/details/143719666

卷积是一种常见的数学运算，在信号处理、图像处理和机器学习等领域都有广泛应用。本文将介绍离散卷积的定义、实现方法，以及如何使用快速傅里叶变换（FFT）来加速卷积计算。

在信号处理、图像处理和机器学习等领域，卷积是一种常见的数学运算。无论是平滑、滤波还是提取特征，卷积都能扮演重要角色。然而，当信号长度变长时，直接计算卷积的效率会大大降低。幸运的是，快速傅里叶变换(FFT)提供了一种高效的替代方法，可以在频域中快速求解卷积。本篇文章将带你了解离散卷积的定义、实现，以及如何使用 FFT 加速卷积计算。

1. 什么是离散卷积？

在离散信号处理中，卷积是一种将两个信号序列相互组合以生成新序列的运算。它用于测量两个序列的相似性、检测信号中的特征或执行滤波操作。

离散卷积的定义

给定两个离散信号序列 ( x[n] ) 和 ( h[n] )，它们的卷积 ( y[n] ) 定义为：

y [ n ] = ( x ∗ h ) [ n ] = ∑ k = − ∞ ∞ x [ k ] h [ n − k ] y[n] = (x * h)[n] = \sum_{k=-\infty}^{\infty} x[k] h[n - k]y[n]=(x∗h)[n]=k=−∞∑∞ x[k]h[n−k]

这个定义描述了将序列 ( h ) 反转并平移后与序列 ( x ) 的逐元素乘积再求和。对于有限长度的信号，我们可以将公式简化为：

y [ n ] = ∑ k = 0 N − 1 x [ k ] h [ n − k ] y[n] = \sum_{k=0}^{N-1} x[k] h[n - k]y[n]=k=0∑N−1 x[k]h[n−k]

一个简单的例子

假设我们有两个序列 ( x = [1, 2, 3] ) 和 ( h = [0, 1, 0.5] )。它们的卷积可以通过以下步骤手动计算：

将 ( h ) 反转得到 ([0.5, 1, 0])。
按照平移的方式计算逐元素乘积并累加，得到卷积结果 ( y )。

此过程虽然简单，但当信号长度增加时，直接计算卷积会变得非常耗时。这也是引入快速傅里叶变换（FFT）的原因。

2. 手动计算卷积的过程

在理解卷积的定义后，我们可以通过滑动窗口的方法计算卷积。对于每个平移位置，反转的 ( h ) 序列逐项与 ( x ) 的对应项相乘并求和。下图展示了滑动窗口的示例：


x:      [1, 2, 3]
h:      [0, 1, 0.5]
Result: [0, 1, 2.5, 4, 1.5]

对于大规模数据（如高分辨率图像），这种直接计算方式效率较低。因此，我们可以利用卷积的频域性质来加速计算。

3. 快速傅里叶变换（FFT）的原理

在频域中，卷积运算可以转化为简单的乘法。傅里叶变换的卷积定理表明：

F ( x ∗ h ) = F ( x ) ⋅ F ( h ) \mathcal{F}(x * h) = \mathcal{F}(x) \cdot \mathcal{F}(h)F(x∗h)=F(x)⋅F(h)

即时域中的卷积运算在频域中相当于点对点的乘法。这一性质让我们可以通过以下步骤来快速计算卷积：

使用 FFT 将信号从时域转到频域。
在频域中逐点相乘。
使用逆 FFT 将结果转换回时域。

FFT 的计算效率

直接卷积的时间复杂度是 (O ( N 2 ) O(N^2)O(N2))，而 FFT 的复杂度是 (O ( N log ⁡ N ) O(N \log N)O(NlogN))。对于长信号，FFT 可以大大降低计算成本。

4. 使用 FFT 计算离散卷积

下面我们用 Python 和 NumPy 实现基于 FFT 的离散卷积计算。以下是具体步骤和代码示例：

步骤分解

将信号序列 ( x ) 和 ( h ) 使用零填充扩展至相同长度（通常是最近的 2 的幂次长度）。
使用
np.fft.fft
函数将两个信号转换到频域。
频域逐点相乘。
使用
np.fft.ifft
将结果转换回时域，得到卷积结果。

实现代码


import numpy as np
# 定义信号序列 x 和 h
x = np.array([1, 2, 3])
h = np.array([0, 1, 0.5])
# 计算填充长度（2 的幂次）
N = len(x) + len(h) - 1
X = np.fft.fft(x, N)
H = np.fft.fft(h, N)
# 频域相乘并转换回时域
Y = X * H
y = np.fft.ifft(Y)
print("卷积结果:", np.real(y))

此代码将返回卷积结果，展示了如何通过 FFT 实现卷积的高效计算。

5. 实际应用：边缘检测


import numpy as np
import matplotlib.pyplot as plt
from scipy.signal import convolve2d
from scipy.ndimage import gaussian_filter
# 创建一个示例图像（灰度渐变加上一些边界）
image = np.zeros((100, 100))
image[25:75, 25:75] = 1  # 添加一个正方形区域
image = gaussian_filter(image, sigma=2)  # 增加平滑效果
# 定义一个卷积核（例如，边缘检测核）
kernel = np.array([[-1, -1, -1],
                   [-1,  8, -1],
                   [-1, -1, -1]])
# 对图像进行卷积操作
convolved_image = convolve2d(image, kernel, mode='same', boundary='wrap')
# 可视化原始图像和卷积后图像的效果
plt.figure(figsize=(10, 5))
# 显示原始图像
plt.subplot(1, 2, 1)
plt.title("Original Image")
plt.imshow(image, cmap='gray')
plt.axis('off')
# 显示卷积后的图像
plt.subplot(1, 2, 2)
plt.title("Convolved Image (Edge Detection)")
plt.imshow(convolved_image, cmap='gray')
plt.axis('off')
plt.tight_layout()
plt.show()

上图展示了一个示例图像卷积的效果：