# 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?

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 '16 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 '16 at 23:34
• What is the common/standard/general procedure?
– user18425
Jun 12 '16 at 23:38