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

4 ビュー (過去 30 日間)
William Thielicke
William Thielicke 2022 年 7 月 21 日
編集済み: Bruno Luong 2022 年 7 月 23 日
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
Bruno Luong 2022 年 7 月 21 日
編集済み: Bruno Luong 2022 年 7 月 23 日
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 件のコメント
William Thielicke
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