3

I'm pretty new to Image Processing and found out that the FFT convolution speeds up the convolution with large kernel sizes a lot.

My question is, how can I apply a kernel to a image in frequency space when using kissFFT?

I already did the following:

//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<height; i++) {
    for(unsigned int l=0; l<width; l++) {
        float red = intToFloat((int)Input(i,l)->Red);
        float green = intToFloat((int)Input(i,l)->Green);
        float blue = intToFloat((int)Input(i,l)->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);

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).

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 ?

The way I think:

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

CharlesB
  • 86,532
  • 28
  • 194
  • 218
Marco
  • 301
  • 4
  • 15
  • It sounds like you have the right idea. When you say in your last sentence "that doesn't really work", what do you mean exactly ? – Paul R Aug 09 '11 at 13:16
  • Well, after the inverse transform the image looks like rubbish. I still recognize the image, but there are many colors, a greyscale inverted image and some other things in it, so not really useful ^^ – Marco Aug 09 '11 at 13:41
  • I've read some more things about the FFT convolution now and some say that I need to pad out the source image too, why do I need to do that and to which size? – Marco Aug 09 '11 at 13:42
  • 1
    THere are some useful diagrams in this PDF which should help to explain: http://developer.download.nvidia.com/compute/cuda/2_2/sdk/website/projects/convolutionFFT2D/doc/convolutionFFT2D.pdf - the actual implementation is for CUDA but the introductory details are pretty general. – Paul R Aug 09 '11 at 14:07

1 Answers1

4

The convolution performed in the frequency domain is really a circular convolution. So when your non-zero elements of the kernel reach the edge of the picture it wraps around and includes the pixels from the other side of the picture, which is probably not what you want. To deal with this just zero pad the input with as many elements as you have non-zero elements in the kernel (actually one less will do). With a 3x3 kernel you need to add 3-1=2 zero pixels in each dimension.

Jens
  • 409
  • 4
  • 11