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

4 ビュー (過去 30 日間)
William Thielicke 2022 年 7 月 21 日

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!!

サインインしてコメントする。

### 回答 (1 件)

Bruno Luong 2022 年 7 月 21 日

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 件のコメント-1 件の古いコメントを表示-1 件の古いコメントを非表示
William Thielicke 2022 年 7 月 23 日
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.

サインインしてコメントする。

### カテゴリ

Help Center および File ExchangeSpectral Measurements についてさらに検索

R2022a

### Community Treasure Hunt

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

Start Hunting!

Translated by