# Applying a 2D Convolution Using 2D FFT

So I was following the article Victor Podlozhnyuk (nVidia) - FFT Based 2D Convolution (Page 7).

I have expanded the kernel to the correct way they have done it. However when it comes to the part on clamping to the edge its very confusing. I would love for someone to explain this as i require the image convolved as the same shape before the padding, but in this article it just shows how to convolve with clamp to edge but not how to recover it.

code as of now

def circExt(k, rows, cols):
radiusV = np.floor(k.shape[0] / 2)
radiusH = np.floor(k.shape[1] / 2)

k_c = k

k_c = np.pad(k_c,((0, int(rows-k.shape[0])), (0, int(cols-k.shape[1]))))

k_c = np.roll(k_c, int(-radiusV), axis = 0)
k_c = np.roll(k_c, int(-radiusH), axis = 1)

return k_c

def testfft2(image, kernel):
imageC = image.copy()
kSize = (kernel.size // 2) + 1
kernelShape = tuple(ti//2 for ti in kernel.shape)

k_width = kernel.shape[1]
k_height = kernel.shape[0]

centery ,centerx = kernelShape

imageC = np.pad(imageC, ((0, int(centery)), (0, int(centerx))) , mode = "edge")

imageC = np.pad(imageC,((0, int(k_height-centery-1)), (0, int(k_width-centerx-1))), mode = "wrap" )

kernelShift = circExt(kernel, imageC.shape[0], imageC.shape[1])

imageC = np.fft.fft2(imageC)
kernel= np.fft.fft2(kernelShift)
output = np.real(np.fft.ifft2(np.multiply(imageC, kernel)))

return output


You may follow the answers to the following questions which implements the paper you linked above:

All the above include code you may use to implement the paper.

• Nearly perfect, it breaks down when I use non square kernels, but thanks a lot for the resources. Nov 18 '21 at 7:19
• @SimonBalfe, What breaks down? Please let me know what's missing to mark this answer.
– Royi
Nov 21 '21 at 17:19
• Its not perfect convolution thats all compare to scipys one, for non square kernels Nov 23 '21 at 3:09
• @SimonBalfe, Could you give example? It is perfectly imitating convolution.
– Royi
Nov 26 '21 at 5:52
• well in my code above that is, if its not a square kernel, the image is not perfectly the same as scipy.convolve, I followed your matlab code specifically unless there was a kernel edge case I missed. Nov 28 '21 at 18:44