File Exchange

image thumbnail

xcorr2_fft(a,b)

version 1.2.0.0 (1.06 KB) by Alessandro Masullo
Two-dimensional cross-correlation evaluated with FFT algorithm

24 Downloads

Updated 19 Oct 2015

View Version History

View License

xcorr2_fft(A,B) computes the cross-correlation of matrices A and B using the FFT algorithm.
When matrices A and B are real, xcorr2_fft is numerically equivalent to xcorr2, but much faster.
For big matrices, the speed improvement can be up to 100 times!
The correlation is simply evaluated padding matrices a and b with zeros according to the size of the correlation map. In this way, the periodicity of the circular cross-correlation evaluated with the FFT becomes equivalent to the linear cross-correlation evaluated with conv2.
% Example:
a = rand(122); b=rand(332);
a = a-mean(a(:));
b = b-mean(b(:));

tic,cl = xcorr2(a,b);toc
Elapsed time is 0.223502 seconds.
tic,cf = xcorr2_fft(a,b);toc
Elapsed time is 0.030935 seconds.

max(abs(cf(:)-cl(:)))
ans = 4.1922e-13

Cite As

Alessandro Masullo (2020). xcorr2_fft(a,b) (https://www.mathworks.com/matlabcentral/fileexchange/53570-xcorr2_fft-a-b), MATLAB Central File Exchange. Retrieved .

Comments and Ratings (6)

Rocco DePietro

Try it with >1000 x1000 matrices is devastes matlab's time by minutes.

Daniel Midtvedt

Great! By converting apad and bpad on lines 37-38 to gpuArray the code also has gpu compatibility!

Chuck37

ZIQIANG YANG

great

I must admit, I was shocked by the speed.
Well done!! Very useful!

June Chen

MATLAB Release Compatibility
Created with R2012b
Compatible with any release
Platform Compatibility
Windows macOS Linux

Community Treasure Hunt

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

Start Hunting!