# Implementing Convolution in Frequency Domain?

Suppose, we have a bitmap image represented as a 2D integer array, int [,] image2D; whose FFT is Complex[,] fftImage2D;

Suppose, we have an kernel represented as a 2D integer array, int [,] kernel2D; whose FFT is Complex[,] fftKernel2D;

We know that, the convolution (in spatial domain) of image2D and kernel2D would be,

int Rows = image2D.GetLength(0);
int Cols = image2D.GetLength(1);

for(int i=0 ; i<Rows ; i++)
{
for(int j=0 ; j<Cols ; j++)
{
//sweep the kernel2D across image2D
//...........................
}
}


We also know that, convolution in frequency domain would be, multiplication between fftImage2D and fftKernel2D.

How can I do this multiplication?

How can I multiply two Complex [,] type 2D arrays of different dimensions? I have understood the theory. My problem is practical implementation. As I described in the question,

1. Are DFT of the image and DFT of the kernel going to be of different sizes? I guess so. So, how can I multiply them element by element?

2. In my code, each of the DFTs are represented by 2D Complex numbers. Should, I multiply them according to complex-number's multiplication rule? Probably yes. But, only when their dimensions are same. Right?

## 1 Answer

IDFT the smaller or both of the DFTs if needed. Zero pad one or both of the kernel and image to make them the same dimension and size. Re-DFT as needed, and now you can complex multiply the 2 DFT arrays element-by-element because they will now be the same size.

• But, if I zero-pad the smaller one (in most cases, the kernel), should I keep the kernel at the center and surround them with zeros, or should I shift the kernel in one of the corners?
– user18425
Jun 12, 2016 at 22:23
• Depends on how you want the result offset. I typically zero-pad both up to a factorable-into-small-primes size that is equal or greater than N+M-1, with the originals centered in the zero padding, or fftshift one or both. Jun 12, 2016 at 23:34
• What is the common/standard/general procedure?
– user18425
Jun 12, 2016 at 23:38