问如何使用FFT加速2D卷积？

EN

# Zero-pad an image
def zero_pad(image, pad_height, pad_width)：
    H, W = image.shape
    out = np.zeros((H+2*pad_height, W+2*pad_width))
    out[pad_height:H+pad_height,pad_width:W+pad_width] = image
    return out

# An step-by-step implementation of convolution filter
def conv(image, kernel):
    Hi, Wi = image.shape
    Hk, Wk = kernel.shape
    out = np.zeros((Hi, Wi))
    image_pad = zero_pad(image, (Hk-1)//2, (Wk-1)//2)
    for i in range(Hi):
        for j in range(Wi):
            out[i,j] = np.sum(kernel*image_pad[i:Hk+i,j:Wk+j])
    return out

# accelerate convolution using FFT
def conv_faster(image, kernel)： 
    Hi, Wi = image.shape
    Hk, Wk = kernel.shape
    out = np.zeros((Hi, Wi))

    # expand image and kernel by zero-padding
    if( (Hi+Hk) % 2 == 0):
        x = (Hi+Hk)
    else:
        x = (Hi+Hk)-1
    if( (Wi+Wk) % 2 == 0):
        y = (Wi+Wk)
    else:
        y = (Wi+Wk)-1
    image_pad = np.zeros((x,y))
    kernel_pad = np.zeros((x,y))
    image_pad[0:Hi,0:Wi] = image
    kernel_pad[0:Hk,0:Wk] = kernel

    # make image and kernel at the center of frequency domain
    for p in range(Hi):
        for q in range(Wi):
            image_pad[p,q]*=(-1)**(p+q)
    for p in range(Hk):
        for q in range(Wk):
            kernel_pad[p,q]*=(-1)**(p+q)

    # do fft for image and kernel
    image_pad_fft = np.fft.fft2(image_pad)
    kernel_pad_fft = np.fft.fft2(kernel_pad) 


    # get the imaginary part of kernel's transformation
    kernel_pad_fft = 1j*np.imag(kernel_pad_fft)

    # multiply the two in frequency domain
    out_pad = np.fft.ifft2(image_pad_fft*kernel_pad_fft)

    # get he real part of result 
    out = np.real(out_pad[0:Hi,0:Wi])

    # Counteract the preceding centralization
    for p in range(Hi):
        for q in range(Wi):
            out[p,q]*=(-1)**(p+q)
    return out