To compute the cross-correlation directly from the definition, first take:

$X≔\mathrm{Matrix}\left(3\,2\,\left[\left[2\,-2+\mathrm{I}\right]\,\left[-\mathrm{I}\,2-\mathrm{I}\right]\,\left[0\,2-2\mathrm{I}\right]\right]\right)$

$X≔\left[\right]$

$Y≔\mathrm{Matrix}\left(4\,3\,\left[\left[1+\mathrm{I}\,2+2\mathrm{I}\,-1-\mathrm{I}\right]\,\left[-2-\mathrm{I}\,1-\mathrm{I}\,-2\mathrm{I}\right]\,\left[2\mathrm{I}\,1+2\mathrm{I}\,1+\mathrm{I}\right]\,\left[-1\,-\mathrm{I}\,2-\mathrm{I}\right]\right]\right)$

$Y≔\left[\right]$

$a,b≔\mathrm{upperbound}\left(X\right)$

$a,b≔3,2$

$c,d≔\mathrm{upperbound}\left(Y\right)$

$c,d≔4,3$

$p≔a+c-1$

$p≔6$

$q≔b+d-1$

$q≔4$

We will need to assume X and Y are both 0 when their indices are out of bounds, and take the complex conjugate of the Y values:

$\mathrm{XX}≔\left(i\&comma;j\right)\mapsto \mathrm{`if`}\left(i<1\mathbf{or}a<i\mathbf{or}j<1\mathbf{or}b<j\&comma;0\&comma;X\left[i,j\right]\right)\&colon;$

$\mathrm{YY}≔\left(i\&comma;j\right)\mapsto \mathrm{`if`}\left(i<1\mathbf{or}c<i\mathbf{or}j<1\mathbf{or}d<j\&comma;0\&comma;\mathrm{conjugate}\left(Y\left[i,j\right]\right)\right)\&colon;$

The cross-correlation can now be found directly:

C1 := Matrix( p, q, proc(i,j) local r, s; add( add( XX(r,s) * YY(r-i+c,s-j+d), s = 1 .. b ), r = 1 .. a ); end proc ):

This corresponds to that found with the command:

$\mathrm{C2}≔\mathrm{CrossCorrelation2D}\left(X\&comma;Y\right)\&colon;$

$\mathrm{err}≔\max \left(\mathrm{abs}\left(\mathrm{C1}-\mathrm{C2}\right)\right)$

$\mathrm{err}≔3.55271367880050\times {10}^{\mathrm{-15}}$

The cross-correlation is computed with FFTs when the dimensions of the final Matrix, namely p and q above, are both powers of 2 and no smaller than 4 in size, and DFTs in the remainder of cases. In the following example, we will compute a cross-correlation both directly (which will use DFTs) and by padding one of the input Matrices (which will use FFTs). The indices 1 and 2 will be used to distinguish the original and padded versions of quantities.

First, define the original Matrices:

$\mathrm{unassign}\left('a'\&comma;'b'\&comma;'c'\&comma;'d'\&comma;'p'\&comma;'q'\&comma;'A'\&comma;'B'\&comma;'C'\right)$

$a\left[1\right]≔60\&colon;$

$b\left[1\right]≔62\&colon;$

$A\left[1\right]≔\mathrm{LinearAlgebra}:-\mathrm{RandomMatrix}\left(a\left[1\right]\&comma;b\left[1\right]\&comma;\mathrm{datatype}=\mathrm{complex}\left[8\right]\right)\&colon;$

$c≔65\&colon;$

$d≔60\&colon;$

$B≔\mathrm{LinearAlgebra}:-\mathrm{RandomMatrix}\left(c\&comma;d\&comma;\mathrm{datatype}=\mathrm{complex}\left[8\right]\right)\&colon;$

Second, compute the cross-correlation with no padding:

$C\left[1\right]≔\mathrm{CrossCorrelation2D}\left(A\left[1\right]\&comma;B\right)\&colon;$

Now, the dimensions are just a little smaller than powers of 2:

$p\left[1\right]≔a\left[1\right]+c-1$

$p_1≔124$

$q\left[1\right]≔b\left[1\right]+d-1$

$q_1≔121$

So, we will pad A[1] (padding B would also work) so that the computed cross-correlation Matrix has dimensions that are powers of 2:

$a\left[2\right]≔a\left[1\right]+2^{-\mathrm{ilog2}\left(\frac{1}{\max \left(4\&comma;p\left[1\right]\right)}\right)}-p\left[1\right]$

$a_2≔64$

$b\left[2\right]≔b\left[1\right]+2^{-\mathrm{ilog2}\left(\frac{1}{\max \left(4\&comma;q\left[1\right]\right)}\right)}-q\left[1\right]$

$b_2≔69$

$p\left[2\right]≔a\left[2\right]+c-1$

$p_2≔128$

$q\left[2\right]≔b\left[2\right]+d-1$

$q_2≔128$

$A\left[2\right]≔\mathrm{ArrayTools}:-\mathrm{Alias}\left(A\left[1\right]\right)\&colon;$

$A\left[2\right]\left(a\left[1\right]+1..a\left[2\right]\&comma;..\right)≔0\&colon;$

$A\left[2\right]\left(..\&comma;b\left[1\right]+1..b\left[2\right]\right)≔0\&colon;$

Finally, find the cross-correlation using FFTs, and extract the appropriate submatrix:

$C\left[2\right]≔\mathrm{CrossCorrelation2D}\left(A\left[2\right]\&comma;B\right)\left[..p\left[1\right],..q\left[1\right]\right]\&colon;$

Both results are the same:

$\mathrm{err}≔\max \left(\mathrm{abs}\left(C\left[1\right]-C\left[2\right]\right)\right)$

$\mathrm{err}≔8.16983452975878\times {10}^{\mathrm{-10}}$

The CrossCorrelation2D command can be reduced to the 1-D version with a couple of minor modifications. Take, for example, the following Vectors:

$A≔\mathrm{Vector}\left[\mathrm{row}\right]\left(\left[5\&comma;-2\&comma;3\&comma;4\&comma;1\right]\right)$

$A≔\left[\right]$

$B≔\mathrm{Vector}\left[\mathrm{row}\right]\left(\left[7\&comma;0\&comma;2\right]\right)$

$B≔\left[\right]$

$b≔\mathrm{numelems}\left(B\right)$

$b≔3$

The 2-D cross-correlation returns the following:

$\mathrm{C\_\_2D}≔\mathrm{CrossCorrelation2D}\left(A\&comma;B\right)$

$\mathrm{C\_\_2D}≔\left[\right]$

The 1-D cross-correlation, however, gives:

$\mathrm{CrossCorrelation}\left(A\&comma;B\right)$

If we switch the arguments for CrossCorrelation, and choose the appropriate value of lowerlag, the two cross-correlations agree:

$\mathrm{C\_\_1D}≔\mathrm{CrossCorrelation}\left(B\&comma;A\&comma;1-b\right)$

$\mathrm{C\_\_1D}≔\left[\right]$

A classic application of two-dimensional cross-correlation is the lining up of two or more images, for example, images of fingerprint fragments. Consider the following image:

$\mathrm{with}\left(\mathrm{ImageTools}\right)\&colon;$

$\mathrm{imgfile}≔\mathrm{cat}\left(\mathrm{kernelopts}\left(\mathrm{mapledir}\right)\&comma;\mathrm{kernelopts}\left(\mathrm{dirsep}\right)\&comma;\mathrm{data}\&comma;\mathrm{kernelopts}\left(\mathrm{dirsep}\right)\&comma;''images''\&comma;\mathrm{kernelopts}\left(\mathrm{dirsep}\right)\&comma;''fingerprint.jpg''\right)\&colon;$

$\mathrm{img1}≔\mathrm{Matrix}\left(\mathrm{Read}\left(\mathrm{imgfile}\right)\&comma;\mathrm{datatype}=\mathrm{float}\left[8\right]\right)\&colon;$

$\mathrm{Preview}\left(\mathrm{img1}\right)$

First, determine the dimensions:

$a,b≔\mathrm{upperbound}\left(\mathrm{img1}\right)$

$a,b≔240,256$

We will also use the mean later:

$\mathrm{\mu }≔\frac{\mathrm{add}\left(\mathrm{img1}\right)}{\mathrm{numelems}\left(\mathrm{img1}\right)}\&colon;$

Second, let's choose some bounds for a fragment of the fingerprint, extract the subimage (fingerprint fragment), and then add some noise (to make our task a little more realistic):

$\mathrm{cL}≔85\&colon;$

$\mathrm{cU}≔205\&colon;$

$\mathrm{dL}≔120\&colon;$

$\mathrm{dU}≔180\&colon;$

$\mathrm{img2}≔\mathrm{Matrix}\left(\mathrm{img1}\left[\mathrm{cL}..\mathrm{cU},\mathrm{dL}..\mathrm{dU}\right]+0.5\mathrm{\mu }\mathrm{ArrayTools}:-\mathrm{RandomArray}\left(\mathrm{cU}-\mathrm{cL}+1\&comma;\mathrm{dU}-\mathrm{dL}+1\&comma;\mathrm{distribution}=\mathrm{normal}\right)\&comma;\mathrm{datatype}=\mathrm{float}\left[8\right]\right)\&colon;$

$\mathrm{Preview}\left(\mathrm{img2}\right)$

Suppose now that we do not know whether the fragment is part of the larger image, and wish to determine if the fragment is a "match". To do this, compute the cross-correlation of the tempered data (formed by subtracting the mean from all elements):

$\mathrm{\mu }≔\frac{\mathrm{add}\left(\mathrm{img1}\right)}{\mathrm{numelems}\left(\mathrm{img1}\right)}\&colon;$

$C≔\mathrm{RealPart}\left(\mathrm{CrossCorrelation2D}\left(\mathrm{`~`}\left[\mathrm{`-`}\right]\left(\mathrm{img1}\&comma;\mathrm{`\; \$`}\&comma;\mathrm{\mu }\right)\&comma;\mathrm{`~`}\left[\mathrm{`-`}\right]\left(\mathrm{img2}\&comma;\mathrm{`\; \$`}\&comma;\mathrm{\mu }\right)\right)\right)\&colon;$

The maximum correlation occurs here, which, as expected, coincides with the bottom-right corner of the fragment:

$\mathrm{\alpha },\mathrm{\beta }≔\max \left[\mathrm{index}\right]\left(C\right)$

$\mathrm{\alpha },\mathrm{\beta }≔205,180$

Visually:

$\mathrm{plots}:-\mathrm{surfdata}\left(C\&comma;\mathrm{title}=''Cross-Correlation\; -\; Full''\right)$

$r≔25\&colon;$

$\mathrm{plots}:-\mathrm{surfdata}\left(C\left[\mathrm{\alpha }-r..\mathrm{\alpha }+r,\mathrm{\beta }-r..\mathrm{\beta }+r\right]\&comma;\mathrm{title}=''Cross-Correlation\; -\; Zoomed''\right)$