title: FFT Convolution - How to apply Kernel
body: <p>I'm pretty new to Image Processing and found out that the FFT convolution speeds up the convolution with large kernel sizes a lot.</p>
  
  <p>My question is, how can I apply a kernel to a image in frequency space when using kissFFT?</p>
  
  <p>I already did the following:</p>
  
  <pre><code>//I have an image with RGB pixels and given width/height
  
  const int dim[2] = {height, width}; // dimensions of fft
  const int dimcount = 2; // number of dimensions. here 2
  kiss_fftnd_cfg stf = kiss_fftnd_alloc(dim, dimcount, 0, 0, 0); // forward 2d
  kiss_fftnd_cfg sti = kiss_fftnd_alloc(dim, dimcount, 1, 0, 0); // inverse 2d
  
  kiss_fft_cpx *a = new kiss_fft_cpx[width * height];
  kiss_fft_cpx *r = new kiss_fft_cpx[width * height];
  kiss_fft_cpx *g = new kiss_fft_cpx[width * height];
  kiss_fft_cpx *b = new kiss_fft_cpx[width * height];
  kiss_fft_cpx *mask = new kiss_fft_cpx[width * height];
  
  kiss_fft_cpx *outa = new kiss_fft_cpx[width * height];
  kiss_fft_cpx *outr = new kiss_fft_cpx[width * height];
  kiss_fft_cpx *outg = new kiss_fft_cpx[width * height];
  kiss_fft_cpx *outb = new kiss_fft_cpx[width * height];
  kiss_fft_cpx *outmask = new kiss_fft_cpx[width * height];
  
  for(unsigned int i=0; i&lt;height; i++) {
      for(unsigned int l=0; l&lt;width; l++) {
          float red = intToFloat((int)Input(i,l)-&gt;Red);
          float green = intToFloat((int)Input(i,l)-&gt;Green);
          float blue = intToFloat((int)Input(i,l)-&gt;Blue);
  
          int index = i * height + l;
  
          a[index].r = 1.0;
          r[index].r = red;
          g[index].r = green;
          b[index].r = blue;
      }
  }
  
  kiss_fftnd(stf, a, outa);
  kiss_fftnd(stf, r, outr);
  kiss_fftnd(stf, g, outg);
  kiss_fftnd(stf, b, outb);
  kiss_fftnd(stf, mask, outmask);
  
  
  kiss_fftnd(sti, outa, a);
  kiss_fftnd(sti, outr, r);
  kiss_fftnd(sti, outg, g);
  </code></pre>
  
  <p>When I set the rgb values again on an image I do get the original image back. So the transformation works.
  What should I do now if I want to apply a kernel, for example 
  a 9x9 box blur (1/9, 1/9, ... 1/9).</p>
  
  <p>I have read some things about Fast convolution, but they're all different, depending on the implementation of the FFT . Is there a kind of "list" what things I have to care before applying a filter ? </p>
  
  <p>The way I think:</p>
  
  <p>The imagesize must be a power of 2;
  I must create a kernel, the same size as the image. Put the 9 middle values to 1/9, the rest to 0 and then transform this kernel into frequency domain, multiply the source image with it, then transform the source image back. But that doesn't really work :DD</p>