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

5 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):
clear;clc;close all;
%% 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
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);
%% 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!!

Answers (1)

Bruno Luong
Bruno Luong on 21 Jul 2022
Edited: Bruno Luong on 23 Jul 2022
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.
  1 Comment
William Thielicke
William Thielicke on 23 Jul 2022
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.

Sign in to comment.


Find more on Execution Speed in Help Center and File Exchange




Community Treasure Hunt

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

Start Hunting!

Translated by