How to center a kernel when using FFT for circular convolution.

8 views (last 30 days)
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?
%%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

Answers (0)

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!