3
$\begingroup$

I just can't get my head around Fourier transform and convolution in 2D. I am trying to implement image convolution using fast Fourier transform (in julia). So the first thing I need to do is to pad the image with zeros. Let's assume that the image is $N\times P$ and the kernel $s \times q$, so I would pad the image so that it is of size $(N+s-1)\times (P+q-1)$.

(N, P) = size(image)
(s, q) = size(kernel)
image_padded = zeros(N+s-1, P+q-1)
image_padded[1:N, 1:P] = image

Then I need to make the kernel the same size as the image, so I pad it with zeros, too, but this time, I have to put the kernel in the center of the huge block of zeros.

kernel_padded = zeros(N+s-1, P+s-1)
Npul = Int((N+s-2)/2) #both image and kernel have odd sizes
Ppul = Int((P+s-2)/2)
spul = Int((s-1)/2)
qpul = Int((q-1)/2)
kernel_padded[Npul-spul+1:Npul+spul+1, Ppul-spul+1:Ppul+spul+1] = k

Then I take fft of both padded image and padded kernel, take their Hadamard product and use inverse fft to get the result back to image domain.

real.(ifft(fft(image_padded).*fft(kernel_padded)))

But the result does not look as I would expect, there is like a cross in the middle of my resulting image. Actually, it looks like there is one quater of the image in each corner but rotated so that the border effect creates the dark cross in the middle. The only way I can get rid of it is to pad the image and kernel to $(N+N+1)\times(P+P+1)$.

So do I understand the process wrong or is something wrong with my code? Thanks for any advice.

Improve this question
$\endgroup$
6
  • $\begingroup$ Try rounding the sizes up to the next power of two. Also wouldn't you want the kernel to be in the $(0,0)$ corner as well. If its non-causal those points should wrap around. I.E. $(-1,-1)$ in the kernel to $(255,255)$ if you had 256 points in the resulting FFT. $\endgroup$
    – IanJ
    Apr 1, 2021 at 22:31
  • $\begingroup$ @IanJ You were right about putting the kernel in the corner! But it seems contraintuive to me, putting center of the original kernel somewhere else than in the center of the padded kernel seems to me like changing the original kernel. $\endgroup$
    – Avec
    Apr 2, 2021 at 15:15
  • $\begingroup$ The origin of the kernel has to be in the top-left corner, which is the origin of the coordinate system for the DFT (and by extension the FFT). Use ifftshift to move the kernel from the middle of the image (as you correctly did) to the corner (I presume this is a function in Julia too, I don’t know Julia). This splits the kernel to all four corners of the image, which looks weird but is correct. Putting the kernel in the top-left corner still leaves a shift in the convolution result, though much smaller than the one you experienced. $\endgroup$
    – Cris Luengo
    Apr 2, 2021 at 16:44
  • $\begingroup$ Now I get it, my intuition was based on linear convolution, but in this case I have to assume that the signal i periodic. Thanks guys! $\endgroup$
    – Avec
    Apr 3, 2021 at 14:07
  • 1
    $\begingroup$ @Royi Yes, indeed, you can crop the right area after inverse filtering. But that requires the kernel being padded to the right and bottom as you did. If the kernel is in the middle of the padded image, as OP did, you can’t fix it by cropping any more. $\endgroup$
    – Cris Luengo
    Jul 8 at 19:10

1 Answer 1

Reset to default
1
$\begingroup$

First, You use fft() which is 1D DFT.
For 2D convolution you need 2D DFT which is implemented in fft2().

A reference implementation is given in Replicate MATLAB's conv2() in Frequency Domain.

You seem to be after the full case which means you need to pad signals as you did.

Improve this answer
$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.