Why I got a big MSE when I try to verify convolution theorem in matlab?

Question

I want to verify the convolution theorem in matlab.

Firstly, I do a 2D discrete convolution of a 2D Gaussian with an image graymap(x, y).

Secondly, I compute the Fourier Transform of the same 2D Gaussian and of the original image. Then perform a scalar multiplication of these two Fourier Transforms, followed by an inverse Fourier Transform of the result.

Finally, I will calculate the MSE between the two results. However, I found the err is 800+.

This is my code:

[row, col] = size(graymap);
[row_2, col_2] = size(z);
result = zeros(row, col);
for i = 1: col
    for j = 1:row
    accumulation_value = 0;
    for k = -4:4
        for h = -4:4
            if ((i+k > 0 && i+k < col + 1) && (j+h > 0 && j+h < row + 1))
                value_image = double(graymap(i+k, j+h));
            else
                value_image = 0;
            end
            accumulation_value = accumulation_value + value_image * double(z(5 + k, 5 + h));
            weighted_sum = weighted_sum + z(5 + k, 5 + h);
        end
    end
    result(i,j) = (accumulation_value);
end
result_blur_1 = uint8(255*mat2gray(result));

M = size(graymap,1);
N = size(graymap,2);

resIFFT = ifft2(fft2(double(graymap), M, N) .* fft2(double(z), M, N));
result_blur_2 = uint8(255*mat2gray(resIFFT));
err = immse(result_blur_1, result_blur_2);

z is the 9*9 gaussian kernel. I don't flip it because it is symmetric.

I think my implementation of convolution is correct because the result is same as conv2(graymap, z, 'same').

Therefore, I believe there are something wrong with the second part. In fact, I am confused on how padding works. May it is the cause of the big MSE.

J. R. C. J. R. C. · Accepted Answer · 2017-10-23T17:05:47

There are indeed problems with your implementation of the second part. The most important rule to remember when implementing convolution via fft is that you are actually calculating a circular convolution, not a linear convolution. Fortunately, there is a condition under which the two become equivalent. This condition is that the two arrays should be zero-padded to have a size equal to the sum of the sizes of each minus 1 (in all dimensions). So if you are working with an image X of size MxN, and a mask Z of size PxQ, then you should pad the two arrays with zeros to so they have at least dimensions M+P-1xN+Q-1. Any additional zeros won't hurt, so it's convenient to match a 'fft-friendly' size if possible (using nextpow2 for example). You just have to take the first M+P-1xN+Q-1 values.

Now, that would work straight forward if you just wanted the full result of the convolution. But because you want the central part of the convolution (the option 'same'), you need to select the correct indexes. The first index will be ceil(([P Q] - 1)/2) + 1, and then you take as many consecutive indexes as the image size.

Here is an example putting all together:

M = randperm(1024,1);
N = randperm(1024,1);

X = rand(M,N);

P = randperm(64,1);
Q = randperm(64,1);

Z = rand(P,Q);

% 'standard' convolution with option 'same'
C1 = conv2(X,Z,'same');


R = 2^nextpow2(M+P-1);
S = 2^nextpow2(N+Q-1);

% convolution with fft. Notice the zero-padding to R,S
C2 = real(ifft2(fft2(X,R,S) .* fft2(Z,R,S)));

n       = ceil(([P Q] - 1)/2);
ind{1}  = n(1) + (1:M);
ind{2}  = n(2) + (1:N);

C2 = C2(ind{:});

err = immse(C1,C2)

I get errors of the order of 1e-26

Why I got a big MSE when I try to verify convolution theorem in matlab?

1 Answers