Speed improvement of repeated cross-correlation of an "almost same area" ?

Hi, my question is probably more a mathematical one:

I am calculating a cross-correlation of two sub-images to determine a displacement. Now I want to repeat this cross-correlation with very slightly shifted sub-images. Is there a way to "re-use" the part of the cross-correlation that was already calculated before the slight shift? Or do I really need to calculate a completely new cross-correlation? Here is the code that shows what I want to do (re-doing the cross-correlation for every slight shift):

clear;clc;close all;
%% Generate artificial texture images that are displaced by 5 pixels
A=rand(200,200,1);
B=circshift(A,5,1)*0.9 + rand(200,200,1)*0.1;
A=medfilt2(A);
B=medfilt2(B);

%figure;imagesc(A);figure;imagesc(B)

%% select a sub-region in the image
selected_rows=21:52;
selected_cols=51:82;
A_sub = A(selected_rows,selected_cols);
B_sub = B(selected_rows,selected_cols);

%% perform cross-correlation to determine the displacement 
correlation_matrix = fftshift(fftshift(real(ifft2(conj(fft2(A_sub)).*fft2(B_sub))), 1), 2); %the position of the peak shows the most probable displacement. It will be refined later by a sub-pixel estimator.

%% Now do the same as above, but with multiple, 1-pixel shifted sub-regions:

%% Generate a stack of 1-pixel shifted sub-regions (faster processing)
A_sub_stack = zeros(32,32,10);
B_sub_stack=A_sub_stack;
cntr=1;
for i = -1:1
    for j=-1:1
    A_sub_stack(:,:,cntr)  = A(selected_rows+i,selected_cols+j);
    B_sub_stack(:,:,cntr)  = B(selected_rows+i,selected_cols+j);
    cntr=cntr+1;
    end
end

%% perform cross-correlation of every sub image in the stack at once to determine the displacement 
correlation_matrix_stack = fftshift(fftshift(real(ifft2(conj(fft2(A_sub_stack)).*fft2(B_sub_stack))), 1), 2); %the position of the peak shows the most probable displacement. It will be refined later by a sub-pixel estimator.

%^^^^ can the speed of this operation be increased? I mean, the sub-images
% are only shifted by a single pixel, so most of the calculation operates
% on the same regions in the image.

Thank you very much for your input!!

Answer 1

[Bruno Luong]

Shift by 1 can be decomposed

• rotate by 1, follow by
• add the first/last element by the new entry - the value of other side

So the FFT can be recycle, the first operation multiply the spectrum by exp(+/-i*2*pi/N), the second add a constant to the spectrum.

You need to workout for details, but that is the idea.

[William Thielicke]

If this is true, then this would be wonderful. I'll try to search for some assistance from people that know more about math than me.