18.14.2 Algorithms (2D Correlation)

2D Correlation is typically used to detect similarities between two 2D signals, which are often saved in matrices. The 2D correlation of two matrices, a and b, can be defined as follows:

r(i,j)=\sum_{m=1}^M \sum_{n=1}^N a(m,n)b(m-i.n-j)

There are two methods for 2D correlation computation: FFT and Shift-Accumulation. If shift accumulation is chosen, the result will be computed from the definition of correlation. If FFT is chosen, the computation of 2D correlation is actually carried out as follows:

  1. The discrete Fourier transforms of both 2D signals are computed using 2D FFT.
  2. Multiply the Fourier coefficients of the first signal with the conjugated coefficients of the second signal.
  3. Perform inverse discrete Fourier transform on the product.

Generally speaking, the FFT method can accelerate the computation for large data, but it is sometimes inaccurate for some data points near the boundaries due to the nature of FFT.

English | Deutsch | 日本語