Abstract

The main aim of this study is to propose efficient algorithms for image template matching on parallel machines. To our knowledge there is no a template matching algorithm that converts the template image and all candidate blocks in the source image from two-dimensions into one-dimension. This study proposes a Template Matching Vectoring Algorithm (TMVA) that reduces the amount of data to be analyzed by transforming 2-D images into 1-D images. Moreover, to speed up the vectoring pattern matching algorithm this study implements it in parallel. Complexity analysis and experimental results demonstrate that the performance of the proposed algorithm is superior to the other basic template matching algorithms.

Keywords:

Image dimensions reduction , image processing , parallel processing, template matching,

References

1. Alsaade, F. and Y. Fouda 2012. Template matching based on SAD and pyramid. Int. J. Comput. Sci. Inform. Secur., 10(4): 11-16.
   
2. Alsaade, F., Y. Fouda and A.R. Khan, 2012. Efficient cellular automata algorithm for template matching. J. Artif. Intell., 5(3): 122-129.
   CrossRef    
3. Anderson, R.F., J.S. Kirtzic and O. Daescu, 2010. Applying parallel design techniques to template matching with GPUs. Proceeding of 9th International Conference on High Performance Computing for Computational Science (VECPAR'10), pp: 456-468.
   
4. Armstrong, J.B., A. Maheswaran, M.D. Theys, M.A. Nichols and K.H., 1998. Casey: Parallel image correlation: Case study to examine trade-offs in algorithm-to-machine mappings. J. Supercomput., 12: 7-35.
   CrossRef    
5. Brunelli, R., 2009. Template Matching Techniques in Computer Vision: Theory and Practice. John Wiley and Sons Ltd., ISBN: 978-0-470-51706-2.
   CrossRef    
6. Chen, Y.S., Y.P. Huang and C.S. Fuh, 2001. A fast block matching algorithm based on the winner-update strategy. IEEE T. Image Process., 10(8): 1212-1222.
   CrossRef    PMid:18255538    
7. Costa, C.E. and M. Petrou, 2000. Automatic registration of ceramic tiles for the prop use of fault detection. Mach. Vision Appl., 11: 225-230.
   CrossRef    
8. Du-Ming, T. and L. Chien-Ta, 2003. Fast normalized cross correlation for detect detection. Pattern Recogn. Lett., 24: 2625-2631.
   CrossRef    
9. Essannouni, F., R.O.H. Thami, D. Aboutajdine and A. Salam, 2007. Adjustable SAD matching algorithm using frequency domain. J. Real-Time Image Proc., 1(4): 257-265.
   CrossRef    
10. Fang, Z., X. Li and L.M. Ni, 1985. Parallel algorithms for image template matching on hypercube SIMD computers. Proceeding of the IEEE Workshop on Computer Architecture for Pattern Analysis and Image Database Management, pp: 33-40.
    
11. Horng, S.J., W.T. Chen and M.Y. Fang, 1991. Optimal speed-up algorithms for template matching on SIMD hypercube multiprocessors with restricted local memory. Inform. Process. Lett., 38(1): 29-37.
    CrossRef    
12. Jenq, J.F. and S. Sahni, 1991. Reconfigurable mesh algorithms for image shrinking, expanding, clustering and template matching. Proceeding of the International Parallel Processing Symposium, pp: 208-215.
    
13. Kidorf, H. and W. Peigorsch, 1984. A practical Fast Fourier Transform (FFT)-based implementation for image correlation. Proceeding of SPIE 0504, Applications of Digital Image Processing VII, pp: 135.
    
14. Kumar, V.K.P. and V. Krishnan, 1987. Efficient image template matching on hypercube SIMD arrays. Proceeding of International Conference on Processing, pp: 765-771.
    
15. Li, R., B. Zeng and M.L. Liou, 1994. A new three-step search algorithm for block motion estimation. IEEE T. Circ. Syst. Vid., 4(4): 438-442.
    CrossRef    
16. Mahmood, A. and S. Khan, 2012. Correlation coefficient based fast template matching through partial elimination. IEEE T. Image Process., 21(4): 2099-2108.
    CrossRef    PMid:21997266    
17. Mendez, J., J. Lorenzo and M. Castrillon, 2011. Comparative performance of GPU, SIMD and OpenMP systems for raw template matching in computer vision. Proceeding of 19th International Conference on Computer Graphics, Visualization and Computer, pp: 9-18.
    
18. Mikhail, I.A., 2001. Faster image template matching in the sum of the absolute value of differences measures. IEEE T. Image Process., 10(2): 659-663.
    
19. Niblack, W., 1986. An Introduction to Digital Image Processing. Prentice-Hall International, Englewood Cliffs, N.J.
    
20. Pacheco, P., 2011. An Introduction to Parallel Programming. 1st Edn., Morgan Kaufmann, Amsterdam, Boston.
    
21. Ranganathan, P., S. Adve and N.P. Jouppi, 1999. Performance of image and video processing with general-purpose processors and media ISA extensions. Proceeding of 26th Annual International Symposium on Computer Architecture (ISCA'99).
    CrossRef    
22. Ranka, S. and S. Sahni, 1988. Image template matching on SIMD hypercube computers. Proceeding of International Conference on Parallel Process, pp: 84-91.
    
23. Wei, S. and S. Lai, 2008. Fast template matching based on normalized cross correlation with adaptive multilevel winner update. IEEE T. Image Process., 17(11): 2227-2235.
    CrossRef    PMid:18972660    
24. Zitova, B.F., 2003. Image registration methods: A survey. Image Vision Comput., 21(11): 977-1000.
    CrossRef    

Competing interests

The authors have no competing interests.

Open Access Policy

This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.

Copyright

The authors have no competing interests.