Notation of template matching using convolution

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\}

And.

\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}

Here, $ 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}

Below, compare with matchTemplate of opencv.

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]]

Recommended Posts

Notation of template matching using convolution
Calculation of normal vector using convolution
Example of using lambda
Template matching by OpenCV (CUDA)
Implementation of TF-IDF using gensim
python: Basics of using scikit-learn ①
Try using Django's template feature
Introduction of caffe using pyenv
A memorandum of using eigen3