# How to properly perform convolution on bitmap image?

Correct me if I'm wrong, I should read bitmap into matrix of float values where I would get numbers up to little more than 16*10^6, then I should expand my image matrix to size 2^k putting the original image matrix into top left corner of the new expanded matrix.

I should then expand given filter to that size (you could help me on this one I'm not sure how to do it, with what to fill it and how to reorganize it), then apply 2 dimensional fft on both matrices, then multiply them dot by dot and finally do inverse 2 dimensional fft to get wanted picture! Where do I get wrong? If I have filter like this:

0   0.2  0
0.2 0.2 0.2
0   0.2  0


What would this filter transformed to 16x16 filter looked like? Thanks for help, fft part was easy for me but this...

-

## migrated from stackoverflow.comDec 26 '12 at 19:07

This question came from our site for professional and enthusiast programmers.

You don't need to expand the filter kernel.

Just flip the filter matrix (otherwise it would result in correlation, not convolution), then perform FFT on the filter. In case of symmetric kernels like your, the flipping is obviously irrelevant.

Before multiplying the two spectra, make sure their DC components are aligned, i.e. the transformed kernel is centered in the transformed image.

Maybe the lower frequencies are located in image corners. In that case, you have to split the transformed kernel in four squares and put each square in the respective corner of the image. (Please edit my answer if you know better than me).

-
First thanks for answering! This is all about faculty programming assignment, and I was told that the hard part would be to implement 2d fft but... An I was also told that if I have image matrix NxN and filter matrix MxM that I should expand both matrices (with zeros) to N+M-1xN+M-1, then to nearest power of 2 (again with zeros) and then apply 2d fft, multiply dot per dot and finally apply inverse 2d fft and extract N+M-1xN+M-1 matrix from result matrix (I understood from top left corner). I will of course flip filter as you say but is rest OK? –  Ognjen Kocic Dec 27 '12 at 16:29