Journal of Signal and Information Processing, 2013, 4, 52-57
doi:10.4236/jsip.2013.43B009 Published Online August 2013 (http://www.scirp.org/journal/jsip)
Template Matching using Statistical Model and Parametric
Template for Multi-Template
Chin-Sheng Chen, Jian-Jhe Huang, Chien-Liang Huang
Graduate Institute of Automation Technology, National Taipei Unive r si ty of Technology.
Received April, 2013.
ABSTRACT
This paper represents a template matching using statistical model and parametric template for multi-template. This al-
gorithm consists of two phases: training and matching phases. In the training phase, the statistical model created by
principal component analysis method (PCA) can be used to synthesize multi-template. The advantage of PCA is to re-
duce the variances of multi-template. In the matching phase, the normalized cross correlation (NCC) is employed to
find the candidates in inspection images. The relationship between image block and multi-template is built to use para-
metric template method. Results show that the proposed method is more efficient than the conventional template
matching and parametric template. Furthermore, the proposed method is more robust than conventional template
method.
Keywords: Multi-Template; Template Matching; Parametric Template; Normalized Cross Correlation; Principal
Component Analysis; Statistical Model
1. Introduction
Template matching is an essential task in imag e process-
ing in many applications, including remote sensing,
computer vision, medical imaging, and industrial inspec-
tion. Many template matching approaches have been
proposed over the past few decades. The NCC is widely
used in template matching, but it is ti me consu ming. Tsai
and Lin [1] proposed a sum-table scheme to reduce the
computation cost for NCC method. In addition, the tradi-
tional NCC method is applied in the case of single tem-
plate; therefore, Tanaka and Sano [2] proposed a para-
metric template method for template matching. In this
method, the parametric space is constructed from the
given vertex images (multi-template) that contain rota-
tion and scale variances, but it is a time consuming me-
thod. Lin and Chen [3] proposed parametric template
vector for template matching with translation, rotation,
and scale invariance using the ring-projection transform,
but the rotation angle cannot be estimated. They [4] fur-
ther introduced a sub-pixel template matching with rota-
tion invariance using the parametric template and the
ring-projection transform methods. It relies on the ring
projection vectors of the eight neighbors around the
matching point to estimate the sub-pixel position, but the
rotation angle also cannot be estimated. However, the
traditional NCC and the parametric template method are
time consuming for multi-template. Bukovec, Spiclin,
Pernus and Likar [5, 6] proposed the g eometrical and th e
statistical methods to detect the surface defect of im-
printed tablets that generates by imprinted shape and
PCA method from a priori tablet data. Mozina, Toma-
zevic, Pernus and Likar [7] proposed a statistical method
to inspect the imprint quality that incorporates the rota-
tion information.
In this paper, template matching using statistical mod-
el and parametric template for multi-template is proposed.
The statistical model is used to synthesize the varied
templates; consequently, parametric template is em-
ployed to measure the similarity b etween the varied tem-
plates and image block. The aim of this paper is to im-
prove the efficiency and the robustness of the similarity
measurement for multi-template.
The rest of this paper is organized as follows: Section
2 provides the architecture of proposed algorithm for the
template matching. Section 3 shows the detail of each
procedure in the proposed algor ithm. Section 4 discusses
the experimental results of the proposed algorithm. Fi-
nally, conclusions are presented in Section 5.
2. The Architecture of Proposed Template
Matching Algorithm
The architecture of the proposed template matching algo-
rithm is shown in Figure 1. The proposed method in-
cludes two phases: (1) the training phase and (2) the

Template Mat ching using Statistica l Mode l a n d Parametric Templat e for Multi-Template 53
Figure 1. The architecture of the proposed template
matching algorithm.
matching phase. In the training phase, the statistical
model is obtained via PCA method. The appearance
model is reconstructed by the any specified template and
fed into the matching phase, which combines the entire
feature from difference templates. In the matching phase,
the NCC method is used to find out the optimal location
of the object that is most similar to the appearance model,
and the image block is generated by optimal location in
the inspection images. Then, the parametric parameters
are calculated by the multi-template and the i mage block
with the original template images is synthesized to esti-
mate the final NCC. The detail of the proposed method
has been discussed in following subsectio ns.
2.1. Statistical Model
In training phase, the statistical model is derived from a
priori template database, which contains multi-template.
The PCA is used for the statistical model, as defined by
u=u Ap
i (1)
where the statistical model is generated from a set of n
template images, ;
,...,
0n
uu
u is the mean of mul-
ti-template; the matrix of variations and corre-
sponding parameters . is a set of linear inde-
pendent eigenvectors, obtained from covariance ma-
trix , so-called eigenspace . Subsequently, the ei-
genvectors are calculated by singular value decomposi-
tion [8] of a covariance matrix:
A
pA
ΘA
Θ
(ET Θuu ) (2)
whereuis a set of normalized template images:
0n
u= [(u- u)(u- u)] (3)
where n is account of the multi-template.
The appearance model of , a specified tem-
plate, can be approximated by t most significant eigen-
vectors:
T

u


t

 t T(u )=uApu
 (4)
where t is t most significant eigenvectors of ; t
is the corresponding approximation parameters, i.e. pro-
jection components of
AAp
(

T
t
Auu) to the corresponding
t eigenvectors. The complete appearance model will
be constructed for the matching phase as a template in
the NCC method.
T

2.2. Normalized Cross Correlation
Here, the NCC method has been used to estimate the
similarity between appearance model and inspection im-
age block. The appearance model is applied in a large
inspection image by sliding the template window in a
pixel-by-pixel basis, and the NCC value is further com-
puted. The maximum values or peaks of the computed
correlation values indicate the matching between the ap-
pearance model of size , , and the win-
dowed search image of the inspection image which size
is
mn(, )Txy

M
N

, , in the size of . The NCC is
defined as (,)Ixy m
n
11
222
11 11
(, )
(, )(,)
(, )(,)
mn
ij
mn mn
ij ij
xy
Ixiyj TijmnIT
2
I
xiyj mnITij mnT


 

 

  

 


(5)
wher e the size of the ap pearan ce mod el is ; nmI and
T are the gray-level means of the appearance model
and the windowed search imag e, respectively, i.e.,
11
1
(, )(,)
mn
ij
IxyIx iyj
mn 



11
1
(, )(,)
mn
ij
Txy Tij
mn 
 
The optimum location (x, y) will be got when the NCC
value is a maximum value. And then the corresponding
image block g is segmented.
2.3. Parametric Template
In this paper, the parametric template is employed for the
calculation of similarity measure between the variant
templates and the image block. The parametric template
space is constructed from a given set of multi-template.
The parametric template is a set of linear parameters i

that satisfies the condition of
0
1
n
i
i



 (6)
where 0.0 1.0
i


.
Therefore, each template in parametric template space
is uniquely represented by parameteri

. A parametric

Template Mat ching using Statistica l Mode l a n d Parametric Templat e for Multi-Template
54
template Twith linear parameters
Pi

,is
defined as {0,1,, }in
00 11
00 11
nn
nn
uu u
uu u
T
P







 (7)
where refers to norm of a given function.
To cons ider the maximu m of the similarity coefficient
between T and the evaluated image, this can be solved
by the Lagrange multiplier method. The solution
P


is

-1
-1
HG
ω=(nH G)



 (8)
whereω, , , and are
HG

n

0
n







ω
 (9)
00 0
0
(,) (,)
(,) (,)
n
nn





uu uu
H
uu uu


n


(10)
0
(, )
(, )
n
g
g





u
G
u

 (11)
1
1





n
 (12)
The term denotes the dot product be-
tween and . The normalized cross correlation
matrix is among the multi-template. The correlation
vector , includes normalized cross correlation values
between an evaluated image block and multi-template,
can be calculated by Equation (5). The synthesized NCC
value
-1 (nH G)


-1
HG

n

H
G

*

of parametric template can be found in terms
of the following equation:
*
0
n
ii
i



 (13)
where , {0,1,,}
iin

, are the different NCC values
of , n is account of the multi-template. G

2.4. Procedures of the Proposed Algorithm
The procedures of proposed template matching using
statistical model and parametric template for multi-tem-
plate are illustrated as following.
Step 1: Generating the statistical model from a set of
multi-template.
Step 2: Appearance model is generated by any speci-
fied template.
Step 3: Using NCC method to find the maximum NCC
coefficient sliding over the inspection images. This op-
timal match position will be used in step 4.
Step 4: The image block
g
is constructed by the op-
timal match position. Then it is applied to calculate the
normalized cross correlation vectorG
.
Step 5: Using Equation (8) to determine the parameter


of parametric template.
Step 6: Re-estimate NCC value from Equation (13).
3. Experimental Results
The proposed method was applied to the LED die images
were carried out two kinds of test images for the per-
formance evaluation. Figure 2 and Figure 3 showed two
cases of the original inspection images; the sizes of these
two inspection images are 250220 and 220

220, re-
spectively. Figure 4 and Figure 5 showed two cases of
the template images with illumination changes, and their
sizes are 114

76 and 114

50, respectively. In this ex-
periment, the NCC coefficient is used to evaluate the
performance outperform the traditional NCC and the
parametric method. The experiments were performed
with MATLAB 2010a on Intel core Pentium D CPU 3.40
GHz with 3.25GB of memory.
In the experiment, Case 1 and Case 2, the numbers of
multi-template are 5 and 9 respectively. The appearance
model is shown in Figures 6(a)-(b). The results of the
proposed method are shown in Figures 7(a)-(c) and
Figures 8(a)-(c), respectively. There are 10 and 15 in-
spection images in Case1 and Case 2, respectively. Next,
two kinds of the performance indices which are the NCC
coefficient and the execute time will be shown. The NCC
coefficient results are illustrated in Figures 9(a)-(b),
respectively. In the traditional NCC method, the NCC
coefficient is obtained from different templates; therefore,
they individually have a maximum and a minimum NCC
coefficient compared to 5 templates in Case 1 and 9 tem-
plates in Case 2. Figures 9(a)-(b) show that the frustra-
tions 0.079 exists in index 9 of Case 1; while 0.065 exists
in index 14 of Case 2. And the experimental results show
that the proposed method is more robust than the tradi-
tional NCC method against the illumination change. In
order to demonstrate the improved performance of our
proposed algorithm, the following example in Case 1 is
shown; the different templates, column 2 and 3 in Figure
4, and the inspection image in row 2, column 4 in Figure
2, are used to estimate the NCC coefficient using tradi-
tional NCC; the NCC coefficients are 0.775 and 0.854,
respectively. The NCC coefficient of the proposed me-
thod is 0.873. The results show that the proposed method
is more robust under clutter environment.
The computation efficiency for different methods is
illustrated in Table 1. Here, the computation time of the

Template Mat ching using Statistica l Mode l a n d Parametric Templat e for Multi-Template 55
proposed method for Case 1 and 2 are 5.68 and 5.03
seconds, respectively. Then the computation time of the
traditional NCC and parametric templates in Case 1 and
2 are 29.7, 35.2, 40.8 and 50.7 seconds, respectively.
Thus, the proposed method indicates the computation
advantages for proposed method and traditional NCC and
parametric template in Case 1 and 2 being 5.23, 6.2 and
8.1, 10.8 times faster, respectively. In contrast, Table 2
shows the matching locations and scores in detail. The
proposed method is verified to be effectively used in real
world applications by the above analysis.
Figure 2. Inspection images of Case 1.
Figure 3. Inspection images of Case 2.
Figure 4. Template images of Case 1.
Figure 5. Template images of Case 2.
)a( )b(
Figure 6. Appearance model: (a) Case 1; (b) Case 2.
(a)
(b)
(c)
Figure 7. Result of template matching by Case1: (a) Tradi-
tional NCC; (b) Parametric template; (c) Proposed method.
(a)
(b)
(c)
Figure 8. Result of template matching by Case2: (a) Tradi-
ional NCC; (b) Parametric template; (c) Proposed method. t

Template Mat ching using Statistica l Mode l a n d Parametric Templat e for Multi-Template
56
Table 1. The comparison of computation time.
Execute time (sec)
Image Traditional NCC Parametric Template Proposed method
Case 1 29.7 35.2 5.68
Case 2 40.8 50.7 5.03
Table 2. Comparison results on the accuracy and NCC coefficient with image for the three methods studied.
Matching location (pixel) NCC coefficient
Image number
(row, column) Traditional NCC Parametric
Template Proposed methodTraditional NCC (Min, Max) Parametric Template Proposed method
"Case 1" (1,1) (68,64) (67,64) (67,63) (0.815,0.856) 0.881 0.879
(1,2) (67,67) (67,67) (67,66) (0.827,0.855) 0.889 0.886
(1,3) (62,71) (61,71) (61,71) (0.813,0.841) 0.879 0.879
(1,4) (67,61) (67,61) (67,61) (0.812,0.841) 0.876 0.876
(1,5) (67,67) (66,67) (66,66) (0.826,0.853) 0.884 0.882
(2,1) (73,64) (72,64) (72,64) (0.821,0.849) 0.885 0.885
(2,2) (66,63) (65,63) (65,62) (0.828,0.852) 0.889 0.875
(2,3) (74,63) (74,63) (74,63) (0.789,0.829) 0.868 0.868
(2,4) (67,57) (67,56) (67,56) (0.775,0.854) 0.873 0.873
(2,5) (70,63) (69,63) (69,63) (0.828,0.882) 0.903 0.903
"Case 2" (1,1) (53,84) (52,84) (52,84) (0.870,0.931) 0.951 0.951
(1,2) (58,84) (58,85) (58,85) (0.897,0.931) 0.958 0.958
(1,3) (60,85) (60,86) (59,86) (0.855,0.913) 0.925 0.924
(1,4) (49,81) (49,81) (49,81) (0.905,0.938) 0.963 0.963
(1,5) (51,89) (51,89) (51,89) (0.877,0.929) 0.944 0.944
(2,1) (47,84) (47,84) (47,84) (0.905,0.946) 0.970 0.970
(2,2) (50,88) (51,88) (51,88) (0.897,0.950) 0.964 0.964
(2,3) (50,79) (50,80) (50,79) (0.878,0.940) 0.960 0.959
(2,4) (52,89) (52,89) (52,89) (0.876,0.936) 0.954 0.954
(2,5) (52,89) (52,89) (52,89) (0.893,0.936) 0.962 0.962
(3,1) (53,83) (53,84) (53,83) (0.882,0.939) 0.955 0.953
(3,2) (42,84) (42,84) (42,84) (0.876,0.927) 0.958 0.958
(3,3) (46,82) (46,82) (46,82) (0.871,0.932) 0.956 0.956
(3,4) (50,87) (50,87) (50,87) (0.873,0.938) 0.959 0.959
(3,5) (47,88) (47,88) (47,88) (0.867,0.904) 0.933 0.933

Template Mat ching using Statistica l Mode l a n d Parametric Templat e for Multi-Template 57
(a)
(b)
Figure 9. The comparison of NCC coefficient with different
methods (a) Case 1; (b) Case 2.
4. Conclusions
In this paper, we have proposed a template matching
algorithm based on multi-template. This algorithm in-
cludes two phases: training and matching phases. The
experimental results show that the proposed method is
more robust for object recognition. The proposed method
can accurately find out the matching location by using
the appearance model, which combines all mul-
ti-template features and the computation of proposed
algorithm more efficient than the traditional template
matching method and parametric template method. In
addition, the proposed method is more robust against
illumination change.
It implies that the proposed algorithm is suitable to
deal with the template matching with tiny variance of
templates’ surface in real world applications.
REFERENCES
[1] D. M. Tsai and C. T. Lin, “Fast Normalized Cross Corre-
lation for Defect Detection,” Pattern Recognition Letters,
Vol. 24, No. 15, 2003, pp. 2625-2631.
doi:10.1016/S0167-8655(03)00106-5
[2] K. Tanaka, M. Sano, S. Ohara and M. Okudaira, “A Pa-
rametric Template Method and Its Application to Robust
Matching,” Proceedings of the IEEE Computer Society
Conference on Computer Vision and Pattern Recognition,
Hilton Head Island,13-15 June, 2000, pp. 620-627.
[3] Y. H. Lin, C. H. Chen and C. C. Wei, “New Method for
Subpixel Image Matching with Rotation Invariance by
Combining the Parametric Template Method and the Ring
Projection Transform Process,” Optical Engineering, Vol.
45, No. 6, 2006. doi:10.1117/1.2213609
[4] Y. H. Lin and C. H. Chen, “Template Matching Using the
Parametric Template Vector with Translation, Rotation
and Scale Invariance,” Pattern Recognition, Vol. 41, No.
7, 2008, pp. 2413-2421.
doi:10.1016/j.patcog.2008.01.017
[5] M. Bukovec, Z. Spiclin, F. Pernus and B. Likar, “Auto-
mated Visual Inspection of Imprinted Pharmaceutical
Tablets,” Measurement Science and Technology, Vol. 18,
No. 9, 2007, pp. 2921-2930.
doi:10.1088/0957-0233/18/9/023
[6] M. Bukovec, Z. Spiclin, F. Pernus and B. Likar, “Geo-
metrical and Statistical Visual Inspection of Imprinted
Tablets,” Proceedings of IAPR Conference on Machine
Vision Applications, Tokyo, 16-18 May 2007, pp.
412-415.
[7] M. Mozina, D. Tomazevic, F. Pernus and B. Likar,
“Automated Visual Inspection of Imprint Quality of
Pharmaceutical Tablets,” Machine Vision and Applica-
tions, Vol. 24, No. 1, 2013, pp. 63-73.
doi:10.1007/s00138-011-0366-4
[8] I. T. Jolliffe, “Principal Component Analysis,” Springer,
New York, 1986. doi:10.1007/978-1-4757-1904-8.