1 SSD
\mathbf{x}\in\left\{\left(x,y\right)|x,y\in[0,N)\subset\mathbb{Z}\right\},\mathbf{x}'\in\left\{\left(x,y\right)|x,y\in[0,n)\subset\mathbb{Z}\right\}
とする。
\begin{eqnarray}
R\left(\mathbf{x}\right) &=& \sum_{\mathbf{x}'}\left(T\left(\mathbf{x}'\right)-I\left(\mathbf{x}+\mathbf{x}'\right)\right)^{2}\\
&=& \sum_{\mathbf{x}'}\left(\left(T\left(\mathbf{x}'\right)\right)^{2}+\left(I\left(\mathbf{x}+\mathbf{x}'\right)\right)^{2}-2T\left(\mathbf{x}\right)I\left(\mathbf{x}+\mathbf{x}'\right)\right)\\
&=& \sum_{\mathbf{x}'}\left(T\left(\mathbf{x}'\right)\right)^{2}+\sum_{\mathbf{x}'}\left(I\left(\mathbf{x}+\mathbf{x}'\right)\right)^{2}-2\sum_{\mathbf{x}'}\left(T\left(\mathbf{x}\right)I\left(\mathbf{x}+\mathbf{x}'\right)\right)\\
&=& \sum_{\mathbf{x}'}\left(T\left(\mathbf{x}'\right)\right)^{2}+\sum_{\mathbf{x}'}o\left(\mathbf{x}’\right)\left(I\left(\mathbf{x}+\mathbf{x}'\right)\right)^{2}-2\left(T'*I\right)\left(\mathbf{x}\right)\\
&=& \sum_{\mathbf{x}'}\left(T\left(\mathbf{x}'\right)\right)^{2}+\left(o*I{}^{2}\right)\left(\mathbf{x}\right)-2\left(T'*I\right)\left(\mathbf{x}\right)
\end{eqnarray}
ここで、$T'\left(\mathbf{x}\right)\equiv T\left(\mathbf{x}\right),o\left(\mathbf{x'}\right)=o\left(-\mathbf{x}'\right)=1$。
2 NCC
\begin{eqnarray}
R\left(\mathbf{x}\right) &=& \frac{\sum_{\mathbf{x}'}T\left(\mathbf{x}'\right)I\left(\mathbf{x}+\mathbf{x}'\right)}{\sqrt{\sum_{\mathbf{x}'}\left(T\left(\mathbf{x}'\right)\right)^{2}\sum_{\mathbf{x}'}\left(I\left(\mathbf{x}+\mathbf{x}'\right)\right)^{2}}}\\
&=& \frac{\left(T'*I\right)\left(\mathbf{x}\right)}{\sqrt{\sum_{\mathbf{x}'}\left(T\left(\mathbf{x}'\right)\right)^{2}\left(o*I{}^{2}\right)\left(\mathbf{x}\right)}}
\end{eqnarray}
以下、opencvのmatchTemplateと比較。
from scipy.signal import *
import cv2
h = arange(4.)[:,None] * ones(4)
I = arange(10.)[:,None] * ones(10)
print cv2.matchTemplate(I.astype("uint8"), h.astype("uint8"), cv2.TM_SQDIFF)
print (h**2).sum() + fftconvolve(I**2,ones_like(h),"valid") - 2 * fftconvolve(I,h[::-1],"valid")
[[ 2.28881836e-05 2.28881836e-05 2.28881836e-05 2.28881836e-05
2.28881836e-05 2.28881836e-05 2.28881836e-05]
[ 1.60000305e+01 1.60000305e+01 1.60000305e+01 1.60000305e+01
1.60000305e+01 1.60000305e+01 1.60000305e+01]
[ 6.40000000e+01 6.40000000e+01 6.40000000e+01 6.40000000e+01
6.40000000e+01 6.40000000e+01 6.40000000e+01]
[ 1.44000000e+02 1.44000000e+02 1.44000000e+02 1.44000000e+02
1.44000000e+02 1.44000000e+02 1.44000000e+02]
[ 2.56000000e+02 2.56000000e+02 2.56000000e+02 2.56000000e+02
2.56000000e+02 2.56000000e+02 2.56000000e+02]
[ 4.00000000e+02 4.00000000e+02 4.00000000e+02 4.00000000e+02
4.00000000e+02 4.00000000e+02 4.00000000e+02]
[ 5.76000000e+02 5.76000000e+02 5.76000000e+02 5.76000000e+02
5.76000000e+02 5.76000000e+02 5.76000000e+02]]
[[ 9.94759830e-14 7.10542736e-14 5.68434189e-14 7.10542736e-14
7.10542736e-14 5.68434189e-14 1.42108547e-14]
[ 1.60000000e+01 1.60000000e+01 1.60000000e+01 1.60000000e+01
1.60000000e+01 1.60000000e+01 1.60000000e+01]
[ 6.40000000e+01 6.40000000e+01 6.40000000e+01 6.40000000e+01
6.40000000e+01 6.40000000e+01 6.40000000e+01]
[ 1.44000000e+02 1.44000000e+02 1.44000000e+02 1.44000000e+02
1.44000000e+02 1.44000000e+02 1.44000000e+02]
[ 2.56000000e+02 2.56000000e+02 2.56000000e+02 2.56000000e+02
2.56000000e+02 2.56000000e+02 2.56000000e+02]
[ 4.00000000e+02 4.00000000e+02 4.00000000e+02 4.00000000e+02
4.00000000e+02 4.00000000e+02 4.00000000e+02]
[ 5.76000000e+02 5.76000000e+02 5.76000000e+02 5.76000000e+02
5.76000000e+02 5.76000000e+02 5.76000000e+02]]
print cv2.matchTemplate(I.astype("uint8"), h.astype("uint8"), cv2.TM_CCORR_NORMED)
print fftconvolve(I,h[::-1],"valid")/sqrt((h**2).sum() * fftconvolve(I**2,ones_like(h),"valid"))
[[ 0.99999982 0.99999982 0.99999982 0.99999982 0.99999982 0.99999982
0.99999982]
[ 0.97589988 0.97589988 0.97589988 0.97589988 0.97589988 0.97589988
0.97589988]
[ 0.94561088 0.94561088 0.94561088 0.94561088 0.94561088 0.94561088
0.94561088]
[ 0.92222464 0.92222464 0.92222464 0.92222464 0.92222464 0.92222464
0.92222464]
[ 0.90476191 0.90476191 0.90476191 0.90476191 0.90476191 0.90476191
0.90476191]
[ 0.89148498 0.89148498 0.89148498 0.89148498 0.89148498 0.89148498
0.89148498]
[ 0.88113421 0.88113421 0.88113421 0.88113421 0.88113421 0.88113421
0.88113421]]
[[ 1. 1. 1. 1. 1. 1. 1. ]
[ 0.97590007 0.97590007 0.97590007 0.97590007 0.97590007 0.97590007
0.97590007]
[ 0.94561086 0.94561086 0.94561086 0.94561086 0.94561086 0.94561086
0.94561086]
[ 0.92222467 0.92222467 0.92222467 0.92222467 0.92222467 0.92222467
0.92222467]
[ 0.9047619 0.9047619 0.9047619 0.9047619 0.9047619 0.9047619
0.9047619 ]
[ 0.89148499 0.89148499 0.89148499 0.89148499 0.89148499 0.89148499
0.89148499]
[ 0.88113422 0.88113422 0.88113422 0.88113422 0.88113422 0.88113422
0.88113422]]