How can I implement convolution in frequency domain?

Question

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
        //...........................
    }
}

The following links are all about convolution in spatial domain:

http://www.codeproject.com/Articles/2008/Image-Processing-for-Dummies-with-C-and-GDI-Part http://www.gutgames.com/post/Matrix-Convolution-Filters-in-C.aspx https://softwarebydefault.com/2013/05/01/image-convolution-filters/

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?

Answer 1

To perform linear convolution by using multiplication in the frequency domain you must first make sure the two complex 2D arrays have the same dimensions. This can be achieved by padding the two spatial domain arrays (image2D and kernel2D) to the same size. Note that you already have to pad your spatial domain arrays to a minimum of one less than the sum of the two arrays dimensions (along each dimension) to perform linear convolution rather than circular convolution.

So the process looks like:

• Compute padded number of rows: image2D.GetLength(0)+kernel2D.GetLength(0)-1
• Compute padded number of columns: image2D.GetLength(1)+kernel2D.GetLength(1)-1
• Pad image2D to this new size, repeating border elements
• Pad kernel2D to this new size, filling in zeros
• Compute FFT of the padded image2D and kernel2D
• Perform multiplication of padded fftImage2D and fftKernel2D which are now of the same size
• Compute inverse FFT
• Optionally truncate result to original image2D size (this is only required if you are interested in a obtaining an image filtered by kernel2D without the edge effects that comes with a full convolution).

For a sample implementation, future readers may have a look at this other question from @anonymous together with the changes I indicated in my answer.

Answer 2

You have to use the multiplication of two complex numbers.

Here is a little java code that do the work for two 1D arrays, with such encoding: [R1, C1, R2, C2, ..., Rn, Cn]:

public void Multiply(double[] object1, double[] object2, double[] result)
{
double img_r, img_i, mask_r, mask_i ;

for (int pos=0 ; pos < result.length ; pos+=2)
    {
    img_r = object1[pos] ;
    img_i = object1[pos+1] ;

    mask_r = object2[pos] ;
    mask_i = object2[pos+1] ;

    result[pos]   = img_r*mask_r - img_i*mask_i;
    result[pos+1] = img_r*mask_i + img_i*mask_r ;
    }
}