How to center a kernel when using FFT for circular convolution.
8 views (last 30 days)
Show older comments
I've got Conway's Game of Life running, using conv2. In order to make the convolution circular, I apply conv2 to [m m m; m m m; m m m] where 'm' is the grid of 1 and 0s.
I would like to get this to work with FFT, since I understand that ifft2(fft2(m).*fft2(k)) should give the circular convolution.
However it seems that padding kernel, k, with zeros is not enough, and that I need to do some kind of centering to get the same results as with conv2.
I found some code that does what I want on the file exchange, but I don't understand why the kernel is recentered 'so that y(1,1) corresponds to mask centred on A(1,1)'. The code seems to pad k with zeros, then apply a circular shift. Maybe someone could explain this?
Code (edited) from http://www.mathworks.com/matlabcentral/fileexchange/31012-2-d-convolution-using-the-fft (David Young):
%%Compute circular conv with conv2:
rng(1)
A = randi(5,5);
K = randi(5,5);
A2 = [A,A,A;A,A,A;A,A,A];
convTwo = conv2(A2,K,'same');
convTwo = convTwo(6:10,6:10);
%%Same result with FFT:
Asize = size(A);
Ksize = size(K);
% zero pad K
if any(Ksize < Asize)
K = exindex(K, 1:Asize(1), 1:Asize(2), {0});
end
% recentre K so that y(1,1) corresponds to mask centred on A(1,1)
Kc = 1 + floor(Ksize/2);
Ke = Kc + Asize - 1;
K = exindex(K, Kc(1):Ke(1), Kc(2):Ke(2), 'circular');
y = ifft2(fft2(A) .* fft2(K)); % central operation, basic form
% trim to correct output size
if ~isequal(Asize, size(y))
y = y(1:Asize(1), 1:Asize(2));
end
% y = convTWO
0 Comments
Answers (0)
See Also
Categories
Find more on Fourier Analysis and Filtering in Help Center and File Exchange
Products
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!