Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

In the FFT2D paper (Fast Fourier transform used for a convolution with a kernel in the frequency domain), I'm lost at the second page first picture:

http://developer.download.nvidia.com/compute/cuda/2_2/sdk/website/projects/convolutionFFT2D/doc/convolutionFFT2D.pdf

The paper states:

The DSP theorem applies to input data (both the image and the convolution kernel) of same size. Therefore, assuming the image is bigger than the convolution kernel, which is usually the case in practice, the convolution kernel needs to be expanded to the image size and padded according to Figure 1. As can be seen on figures 2 and 3 (see below), cyclic convolution with the expanded kernel is equivalent to cyclic convolution with initial convolution kernel.

Explained: Convolution of two functions is equal to multiplication of each function's FFT transform, but only if the functions have the same amount of samples (in my case, I have to make kernel and image same size). This is clear enough... but if you look at the image figure 1 and figure 2 it's said that a "cyclic" (I read somewhere that is the normal convolution, is this correct?) convolution between the kernel and the image is equivalent to the cyclic convolution of the image with the expanded kernel.

I tried with numbers and this isn't true for me. And why did the author "mirrored" the expanded kernel like that?

I can't figure it out and there's no link in the pdf helping me out

share|improve this question
    
I recommend that you ask the moderators to move this to dsp.SE –  Dilip Sarwate Jul 3 '12 at 19:12
    
Thank you, if someone moves it I'll be grateful –  Marco A. Jul 3 '12 at 20:04

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.