Journal of Signal and Information Processing, 2013, 4, 5257 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 MultiTemplate ChinSheng Chen, JianJhe Huang, ChienLiang Huang Graduate Institute of Automation Technology, National Taipei Unive r si ty of Technology. Email: saint@ntut.edu.tw, t100618009@ntut.edu.tw, t97669026@ntut.edu.tw Received April, 2013. ABSTRACT This paper represents a template matching using statistical model and parametric template for multitemplate. 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 multitemplate. The advantage of PCA is to re duce the variances of multitemplate. In the matching phase, the normalized cross correlation (NCC) is employed to find the candidates in inspection images. The relationship between image block and multitemplate 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: MultiTemplate; 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 sumtable 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 (multitemplate) 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 ringprojection transform, but the rotation angle cannot be estimated. They [4] fur ther introduced a subpixel template matching with rota tion invariance using the parametric template and the ringprojection transform methods. It relies on the ring projection vectors of the eight neighbors around the matching point to estimate the subpixel position, but the rotation angle also cannot be estimated. However, the traditional NCC and the parametric template method are time consuming for multitemplate. 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 multitemplate 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 multitemplate. 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 Copyright © 2013 SciRes. JSIP
Template Mat ching using Statistica l Mode l a n d Parametric Templat e for MultiTemplate 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 multitemplate 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 multitemplate. 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 titemplate; the matrix of variations and corre sponding parameters . is a set of linear inde pendent eigenvectors, obtained from covariance ma trix , socalled eigenspace . Subsequently, the ei genvectors are calculated by singular value decomposi tion [8] of a covariance matrix: A pA ΘA Θ (ET Θuu ) (2) whereuis a set of normalized template images: 0n u= [(u u)(u u)] (3) where n is account of the multitemplate. 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 pixelbypixel 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 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 xiyj mnITij mnT (5) wher e the size of the ap pearan ce mod el is ; nmI and T are the graylevel 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 multitemplate. 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 Copyright © 2013 SciRes. JSIP
Template Mat ching using Statistica l Mode l a n d Parametric Templat e for MultiTemplate 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 multitemplate. The correlation vector , includes normalized cross correlation values between an evaluated image block and multitemplate, 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 multitemplate. G 2.4. Procedures of the Proposed Algorithm The procedures of proposed template matching using statistical model and parametric template for multitem plate are illustrated as following. Step 1: Generating the statistical model from a set of multitemplate. 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 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: Reestimate 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 250220 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 multitemplate 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 Copyright © 2013 SciRes. JSIP
Template Mat ching using Statistica l Mode l a n d Parametric Templat e for MultiTemplate 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 Copyright © 2013 SciRes. JSIP
Template Mat ching using Statistica l Mode l a n d Parametric Templat e for MultiTemplate Copyright © 2013 SciRes. JSIP 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 MultiTemplate 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 multitemplate. 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 titemplate 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. 26252631. doi:10.1016/S01678655(03)001065 [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,1315 June, 2000, pp. 620627. [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. 24132421. 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. 29212930. doi:10.1088/09570233/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, 1618 May 2007, pp. 412415. [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. 6373. doi:10.1007/s0013801103664 [8] I. T. Jolliffe, “Principal Component Analysis,” Springer, New York, 1986. doi:10.1007/9781475719048. Copyright © 2013 SciRes. JSIP
