- rotate by 1, follow by
- add the first/last element by the new entry - the value of other side
Speed improvement of repeated cross-correlation of an "almost same area" ?
7 views (last 30 days)
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):
%% Generate artificial texture images that are displaced by 5 pixels
B=circshift(A,5,1)*0.9 + rand(200,200,1)*0.1;
%% select a sub-region in the image
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);
for i = -1:1
A_sub_stack(:,:,cntr) = A(selected_rows+i,selected_cols+j);
B_sub_stack(:,:,cntr) = B(selected_rows+i,selected_cols+j);
%% 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!!
Bruno Luong on 21 Jul 2022
Edited: Bruno Luong on 23 Jul 2022
Shift by 1 can be decomposed
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.