Equivalent of zero padding in frequency space

I was wondering if instead of zero padding an image in space domain and then taking its FT, I could take the FT first and the do something to simulate the 0 padding? This is for template matching function that I'm writing. I need zero padding because I perform convolution by taking FT of both the template and data image and then find the product of the transforms, so the 2 transforms need to match in size. I don't use conv2 function because I perform template matching with approximately 100 different scales of the template image and conv2 takes too long. I would really appreciate any suggestions. Thank you very much!

Answer 1

[Star Strider]

Since zero-padding in the space domain increases the frequency resolution in the frequency domain, the equivalent in the frequency domain seems to me to create a frequency vector of the appropriate increased length (using linspace with the same frequency limits as the original frequency-domain result to create the appropriate vectors in each dimension) and then interpolate to it, creating a frequency-comain result with increased frequency resolution. That is how I would do it with a one-dimensional signal (such as in signal processing), so a similar approach should work with a two-dimensional signal. Note that you would have to do this on the complex result if you wanted to invert it later.

I have never actually done this on a two-dimensional signal, so experiment with it to see how well it works.

[KT]

Thank you very much for your answer Star Strider! I did 2D interpolation using interp2 where:

Xq = linspace(1, size(bigger, 1), size(bigger, 1) + 100);

Yq = linspace(1, size(bigger, 2), size(bigger, 2) + 100);

result = interp2d(bigger, Yq, Xq(:));

bigger is an FFT of my original image. When I take the ifft2 of the result and conver it to an image, that image is a scaled version of the original image. Instead of scaling I would just like to zero-pad the original image. Should I be using interp2 differently? Thank you again very much for your suggestions! I'm new to image processing so I'm not interile sure how to properly work with an FFT of an image.

[Star Strider]

My pleasure!

Rescaling in the frequency domain will not result in zero-padding the original space (or time) domain signal. It simply interpolates it to the new spatial dimensions. If you want to zero-pad the original image, do just that.

I suppose it could be possible to downsample the upsampled frequency-domain signal, then invert it and insert it into an existing zeros matrix, however that seems to me to be more trouble than it’s worth.

[KT]

Thank you Star Strider! I apologize, I didn't explain my code well in the previous post. I already perfom image scaling in frequency domain. After I scale the image through its FT, I want to also zero pad the image through its FT. I tried interpolating the FT as shown in the code in my previous post, but that just scaled the image. The reason I do not want to zero pad in space domain is because that would cause my code to run slower. Thank you again very much! I appreciate your help!

[Star Strider]

I’m lost.

It’s certainly possible to zero-pad in the frequency domain as well, if you want to. See: 2-D Inverse Transform of Matrix . This would likely have the effect of interplating the inverted matrix. It would not zero-pad it.

[KT]

What I would like it to do is something like:

Approach 1

imagePadded = padarray(image, [100 50], 0, 'post');

imageFFT = fft2(imagePadded);

Approach 2

imageFFT = fft2(image);

imagePadded = some_function(imageFFT)

Result

imageFFT (approach 1) = imagePadded (approach 2)

I'm sorry for the confusion. Thank you for your help!

[Star Strider]

Go for it!

Experiment until you get the result you want.

[KT]

Do you have any ideas for what that some_function could be? I tried using interp2 but it did not work. I read that 0 padding in space domain is equivalent to sinc interpolation in frequency domain, but interp2 does not have an option for sinc interpolation? Thank you again so much!

[Star Strider]

You would have to write ‘some_function’ yourself, depending on the result you want.

The sinc function is just the Fourier transform of an even square pulse. I am not certain how it could be used to interpolate anything.

Inverting the matrix would not automatically include zero-padding. You would have to do that yourself, inserting the inverted matrix into a zeros matrix, as I mentioned previously.

[KT]

Great, thank you very much for all of your help! I'll test that out.

[Star Strider]

As always, my pleasure!