4. 案例4

任务说明

本案例实现三种卷积算法——直接滑窗卷积、im2col+GEMM卷积、FFT卷积，并在不同卷积核尺寸下比较其浮点运算耗时。输入为固定尺寸的单通道特征图（H=256, W=256），卷积核尺寸分别取3×3、7×7、15×15、31×31，stride=1，padding=核尺寸一半（保持输出尺寸不变）。目标是通过实测耗时曲线，明确FFT卷积在较大卷积核下的优势区间。

算法实现

import numpy as np
import time

def direct_conv(img, kernel):
    """直接滑窗卷积，img: (H,W), kernel: (K,K)"""
    H, W = img.shape
    K = kernel.shape[0]
    P = K // 2
    out = np.zeros_like(img)
    padded = np.pad(img, P, mode='constant')
    for i in range(H):
        for j in range(W):
            out[i, j] = np.sum(padded[i:i+K, j:j+K] * kernel)
    return out

def im2col_conv(img, kernel):
    """im2col + GEMM 卷积"""
    H, W = img.shape
    K = kernel.shape[0]
    P = K // 2
    padded = np.pad(img, P, mode='constant')
    # 构建im2col矩阵
    cols = np.zeros((H*W, K*K))
    idx = 0
    for i in range(H):
        for j in range(W):
            cols[idx] = padded[i:i+K, j:j+K].flatten()
            idx += 1
    kernel_flat = kernel.flatten()
    out = cols @ kernel_flat
    return out.reshape(H, W)

def fft_conv(img, kernel):
    """FFT卷积：频域相乘后逆变换"""
    H, W = img.shape
    K = kernel.shape[0]
    # 计算FFT所需尺寸（避免循环卷积混叠）
    fH = H + K - 1
    fW = W + K - 1
    # 找2的幂次加速
    fH = 1 << int(np.ceil(np.log2(fH)))
    fW = 1 << int(np.ceil(np.log2(fW)))
    # 频域相乘
    img_fft = np.fft.fft2(img, s=(fH, fW))
    kernel_pad = np.zeros((fH, fW))
    kernel_pad[:K, :K] = kernel
    kernel_fft = np.fft.fft2(kernel_pad)
    prod = img_fft * kernel_fft
    out = np.fft.ifft2(prod).real
    # 裁剪到原尺寸（去掉padding影响）
    P = K // 2
    return out[P:P+H, P:P+W]

def benchmark():
    """性能对比：不同核尺寸下三种算法耗时"""
    H = W = 256
    np.random.seed(42)
    img = np.random.rand(H, W).astype(np.float32)
    kernel_sizes = [3, 7, 15, 31]
    results = {k: [] for k in ['direct', 'im2col', 'fft']}
    
    for K in kernel_sizes:
        kernel = np.random.rand(K, K).astype(np.float32)
        
        # 预热
        direct_conv(img, kernel)
        im2col_conv(img, kernel)
        fft_conv(img, kernel)
        
        # 计时（取3次最优）
        t0 = time.perf_counter()
        for _ in range(3):
            direct_conv(img, kernel)
        results['direct'].append((time.perf_counter()-t0)/3)
        
        t0 = time.perf_counter()
        for _ in range(3):
            im2col_conv(img, kernel)
        results['im2col'].append((time.perf_counter()-t0)/3)
        
        t0 = time.perf_counter()
        for _ in range(3):
            fft_conv(img, kernel)
        results['fft'].append((time.perf_counter()-t0)/3)
    
    return kernel_sizes, results

if __name__ == '__main__':
    sizes, res = benchmark()
    print(f"{'核大小':<8}{'直接卷积(ms)':<16}{'im2col(ms)':<16}{'FFT(ms)':<16}")
    for i, K in enumerate(sizes):
        print(f"{K:<8}{res['direct'][i]*1000:<16.3f}{res['im2col'][i]*1000:<16.3f}{res['fft'][i]*1000:<16.3f}")

实现说明

三种算法均针对单通道2D卷积实现，输出尺寸与输入一致（same padding）。直接卷积使用四重循环完成滑窗累加；im2col将每个窗口展平为矩阵行后与展平的卷积核做矩阵乘法；FFT卷积将输入和卷积核补零至相同尺寸（取2的幂以加速），在频域逐点相乘后逆变换并裁剪。三者结果在数值上一致（浮点误差范围内）。

SVG：FFT卷积计算流程与数据布局

运行与验证

直接运行脚本即可输出三种算法在不同核尺寸下的耗时对比。判定标准：

三种算法输出结果一致（np.allclose，误差<1e-4）；
核尺寸较小时（3×3、7×7），直接卷积或im2col耗时低于FFT；
核尺寸增大到15×15以上时，FFT卷积耗时明显低于直接卷积，且核越大优势越显著；
im2col在核较小时与直接卷积相当，核增大后因内存展开开销增加而劣化。

预期输出趋势（非实测值）：核尺寸从3增至31时，直接卷积耗时呈近似K²增长，FFT耗时增长平缓，交叉点通常出现在K=7~15之间。实际数值取决于硬件与NumPy的FFT实现，以本机运行为准。