A Robust Template Matching Algorithm Based on Reducing Dimensions


Template matching is a fundamental problem in pattern recognition, which has wide applications, especially in industrial inspection. In this paper, we propose a 1-D template matching algorithm which is an alternative for 2-D full search block matching algorithms. Our approach consists of three steps. In the first step the images are converted from 2-D into 1-D by summing up the intensity values of the image in two directions horizontal and vertical. In the second step, the template matching is performed among 1-D vectors using the similarity function sum of square difference. Finally, the decision will be taken based on the value of similarity function. Transformation template image and sub-images in the source image from 2-D grey level information into 1-D information vector reduce the dimensionality of the data and accelerate the computations. Experimental results show that the computational time of the proposed approach is faster and performance is better than three basic template matching methods. Moreover, our approach is robust to detect the target object with changes of illumination in the template also when the Gaussian noise added to the source image.

Share and Cite:

Fouda, Y. (2015) A Robust Template Matching Algorithm Based on Reducing Dimensions. Journal of Signal and Information Processing, 6, 109-122. doi: 10.4236/jsip.2015.62011.

Conflicts of Interest

The authors declare no conflicts of interest.


[1] Du-Ming, T. and Chien-Ta, L. (2003) Fast Normalized cross Correlation for Detect Detection. Pattern Recognition Letters, 24, 2625-2613. http://dx.doi.org/10.1016/S0167-8655(03)00106-5
[2] Costa, C.E. and Petrou, M. (2000) Automatic Registration of Ceramic Tiles for the Prop Use of Fault Detection. Machine Vision and Applications, 11, 225-230. http://dx.doi.org/10.1007/s001380050105
[3] Li, R., Zeng, B. and Liou, M.L. (1994) A New Three-Step Search Algorithm for Block Motion Estimation. IEEE Transactions on Circuits and Systems for Video Technology, 4, 438-442.
[4] Chen, Y., Hung, Y. and Fuh, C. (2001) Fast Block Matching Algorithm Based on the Winner-Update Strategy. IEEE Transactions on Image Processing, 10, 1212-1222.
[5] Koga, T., Inuma, K., Hirano, A., Iijima, Y. and Ishiguro, T. (1981) Motion Compensated Interframe Coding for Video Conferencing. Proc. Nat. Telecommunications Conf., 4, G5.3.1-G5.3.5.
[6] Jain, J.R. and Jain, A.K. (1981) Displacement Measurement and Its Application in Interframe Image Coding. IEEE Transactions on Communications, 29, 1799-1808.
[7] Ghanbari, M. (1990) The Cross-Search Algorithm for Motion Estimation [Image Coding]. IEEE Transactions on Communications, 38, 950-953. http://dx.doi.org/10.1109/26.57512
[8] Liu, B. and Zaccarin, A. (1993) New Fast Algorithms for the Estimation of Block Motion Vectors. IEEE Transactions on Circuits and Systems for Video Technology, 3, 148-157.
[9] Bei, C.D. and Gray, R.M. (1985) An Improvement for the Minimum Distortion Encoding Algorithm for Vector Quantization. IEEE Transactions on Communications, 33, 1132-1133.
[10] Gersho, A. and Gray, R.M. (1992) Vector Quantization and Signal Compression. Kluwer, Norwell.
[11] Shi, Y.Q. and Xia, X. (1997) A Thresholding Multiresolution Block Matching Algorithm. IEEE Transactions on Circuits and Systems for Video Technology, 7, 437-440.
[12] Nam, K.M., Kim, J.S., Park, R.H. and Shim, Y.S. (1995) A Fast Hierarchical Motion Vector Estimation Algorithm Using Mean Pyramid. IEEE Transactions on Circuits and Systems for Video Technology, 5, 344-351. http://dx.doi.org/10.1109/76.465087
[13] Lin, Y.-H. and Chen, C.-H. (2008) Template Matching Using the Parametric Template Vector with Translation, Rotation, and Scale Invariance. Pattern Recognition, 41, 2413-2421.
[14] Fouda, Y.M. (2014) One-Dimensional Vector Based Template Matching. International Journal of Computer Science and Information Technology, 6, 47-58. http://dx.doi.org/10.5121/ijcsit.2014.6404
[15] Tsai, D. and Lin, C. (2003) Fast Normalized cross Correlation for Defect Detection. Pattern Recognition Letters, 24, 2625-2631. http://dx.doi.org/10.1016/S0167-8655(03)00106-5
[16] Sebe, N., Lew, M.S. and Huijsmans, D.P. (2000) Toward Improved Ranking Metrics. IEEE Transactions on Pattern Analysis and Machine Intelligence, 22, 1132-1143. http://dx.doi.org/10.1109/34.879793
[17] Mahmood, A. and Khan, S. (2012) Correlation Coefficient Based Fast Template Matching through Partial Elimination. IEEE Transactions on Image Processing, 21, 2099-2108.
[18] Rosenfeld, A. and Vanderbrug, G.J. (1977) Coarse-Fine Template Matching. IEEE Transactions on Systems, Man and Cybernetics, 7, 104-107.
[19] Vanderbrug, G.J. and Rosenfeld, A. (1977) Two-stage Template Matching. IEEE Transactions on Computers, C-26, 384-393. http://dx.doi.org/10.1109/TC.1977.1674847
[20] Lee, C. and Chen, L. (1997) A Fast Motion Estimation Algorithm Based on the Block Sum Pyramid. IEEE Transactions on Image Processing, 6, 1587-1591. http://dx.doi.org/10.1109/83.641419
[21] Gonzalez, R.C. and Woods, R.E. (1992) Digital Image Processing. Addison-Wesley, Reading.
[22] Atallah, M.J. (2001) Faster Image Template Matching in the Sum of the Absolute Value of Differences Measure. IEEE Transactions on Image Processing, 10, 659-663. http://dx.doi.org/10.1109/83.913600

Copyright © 2020 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.