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

8 visualizaciones (últimos 30 días)
jsmith1110
jsmith1110 el 25 de Mzo. de 2016
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

Respuestas (0)

Categorías

Más información sobre Fourier Analysis and Filtering en Help Center y File Exchange.

Productos

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by