6
$\begingroup$

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?

$\endgroup$

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$
    – user18425
    Jun 12, 2016 at 22:23
  • 1
    $\begingroup$ 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. $\endgroup$
    – hotpaw2
    Jun 12, 2016 at 23:34
  • $\begingroup$ What is the common/standard/general procedure? $\endgroup$
    – user18425
    Jun 12, 2016 at 23:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.