How to properly perform convolution on bitmap image?

Question

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

Answer 1

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