›› 2017, Vol. 32 ›› Issue (6): 1305-1318.doi: 10.1007/s11390-017-1765-4

Special Issue: Computer Architecture and Systems; Artificial Intelligence and Pattern Recognition

• Regular Paper • Previous Articles     Next Articles

A Configurable Circuit for Cross-Correlation in Real-Time Image Matching

Quan Zhou, Liang Yang, Hui Cao   

  1. Department of Integrated Circuit Design, Xi'an Microelectronics Technology Institute, Xi'an 710065, China
  • Received:2016-05-04 Revised:2017-07-22 Online:2017-11-05 Published:2017-11-05
  • Contact: 10.1007/s11390-017-1765-4
  • About author:Quan Zhou received his B.S.degree in electronic information science and technology from China University of Mining and Technology,Xuzhou,in 2011,and M.S.degree in computer architecture from Xi'an Microelectronics Technology Institute,Xi'an,in 2014 where he is currently pursuing his Ph.D.degree in computer architecture.His research interests include chip architecture and data-intensive computing.
  • Supported by:

    This work is supported by the Innovation Research Project of Reconfigurable Computing Cluster for On-Orbit Information Processing of China Aerospace Science and Technology Corporation under Grant No. YY2014-001.

Cross-correlation (CC) is the most time-consuming in the implementation of image matching algorithms based on the correlation method. Therefore, how to calculate CC fast is crucial to real-time image matching. This work reveals that the single cascading multiply-accumulate (CAMAC) and concurrent multiply-accumulate (COMAC) architectures which have been widely used in the past, actually, do not necessarily bring about a satisfactory time performance for CC. To obtain better time performance and higher resource efficiency, this paper proposes a configurable circuit involving the advantages of CAMAC and COMAC for a large amount of multiply-accumulate (MAC) operations of CC in exhaustive search. The proposed circuit works in an array manner and can better adapt to changing size image matching in real-time processing. Experimental results demonstrate that this novel circuit which involves the two structures can complete vast MAC calculations at a very high speed. Compared with existing related work, it improves the computation density further and is more flexible to use.

[1] Chen J Y, Hung K F, Lin H Y et al. Real-time FPGAbased template matching module for visual inspection application. In Proc. IEEE/ASME International Conference on Advanced Intelligent Mechatronics, July 2012.

[2] Alam M S, Bal A. Improved multiple target tracking via global motion compensation and optoelectronic correlation. IEEE Trans. Industrial Electronics, 2007, 54(1):522-529.

[3] Po L M, Ma W C. A novel four-step search algorithm for fast block motion estimation. IEEE Trans. Circuits and Systems for Video Technology, 1996, 6(3):313-317.

[4] Zhu S, Ma K K. A new diamond search algorithm for fast block-matching motion estimation. IEEE Trans. Image Processing, 2000, 9(2):287-290.

[5] Mori M, Kashino K. Fast template matching based on normalized cross correlation using adaptive block partitioning and initial threshold estimation. In Proc. IEEE International Symposium on Multimedia (ISM), Dec. 2010, pp.196-203.

[6] Gao X Q, Duanmu C J, Zou C R. A multilevel successive elimination algorithm for block matching motion estimation. IEEE Trans. Image Processing, 2000, 9(3):501-504.

[7] Li W, Salari E. Successive elimination algorithm for motion estimation. IEEE Trans. Image Processing, 1995, 4(1):105-107.

[8] Lewis J P. Fast template matching. In Proc. Vision Interface, May 1995, pp.120-123.

[9] Viola P, Jones M. Robust real-time object detection. In Proc. International Workshop on Statistical & Computational Theories of Vision-modeling, Learning, Computing, and Sampling, Apr. 2001.

[10] Wu T, Toet A. Speed-up template matching through integral image based weak classifiers. Journal of Pattern Recognition Research, 2014, 9(1):1-12.

[11] Luo J, Konofagou E E. A fast normalized cross-correlation calculation method for motion estimation. IEEE Trans. Ultrasonics, Ferroelectrics, and Frequency Control, 2010, 57(6):1347-1357.

[12] Tsai D M, Lin C T. Fast normalized cross correlation for defect detection. Pattern Recognition Letters, 2003, 24(15):2625-2631.

[13] Luo J, Konofagou E E. A fast motion and strain estimation method. In Proc. IEEE Ultrasonics Symposium (IUS), Oct. 2010, pp.1608-1611.

[14] Goshtasby A, Gage S H, Bartholic J F. A two-stage cross correlation approach to template matching. IEEE Trans. Pattern Analysis and Machine Intelligence, 1984, 6(3):374-378.

[15] Lindoso A, Entrena L, Lopze-Ongil C et al. Correlationbased fingerprint matching using FPGAs. In Proc. IEEE International Conference on Field Programmable Technology, Dec. 2005.

[16] Lindoso A, Entrena L. High performance FPGA-based image correlation. Journal of Real-Time Image Processing, 2007, 2(4):223-233.

[17] Bailey D. Design for Embedded Image Processing on FPGAs. Wiley-IEEE Press, 2011, pp.299-301.

[18] Gupta N. A VLSI architecture for image registration in real time. IEEE Trans. Very Large Scale Integration (VLSI) Systems, 2007, 15(9):981-989.

[19] Joanblanq C, Senn P, Colaitis M J. A 54-MHz CMOS programmable video signal processor for HDTV applications. IEEE Journal of Solid-State Circuits, 1990, 25(3):730-734.

[20] Arambepola B, Patel V B, Cheung G. Cascadable one/twodimensional digital convolver. IEEE Journal of Solid-State Circuits, 1988, 23(2):351-357.

[21] Yang K M, Sun M T, Wu L. A family of VLSI designs for the motion compensation block-matching algorithm. IEEE Trans. Circuits and Systems, 1989, 36(10):1317-1325.
No related articles found!
Full text



[1] Liu Mingye; Hong Enyu;. Some Covering Problems and Their Solutions in Automatic Logic Synthesis Systems[J]. , 1986, 1(2): 83 -92 .
[2] Chen Shihua;. On the Structure of (Weak) Inverses of an (Weakly) Invertible Finite Automaton[J]. , 1986, 1(3): 92 -100 .
[3] Gao Qingshi; Zhang Xiang; Yang Shufan; Chen Shuqing;. Vector Computer 757[J]. , 1986, 1(3): 1 -14 .
[4] Chen Zhaoxiong; Gao Qingshi;. A Substitution Based Model for the Implementation of PROLOG——The Design and Implementation of LPROLOG[J]. , 1986, 1(4): 17 -26 .
[5] Huang Heyan;. A Parallel Implementation Model of HPARLOG[J]. , 1986, 1(4): 27 -38 .
[6] Min Yinghua; Han Zhide;. A Built-in Test Pattern Generator[J]. , 1986, 1(4): 62 -74 .
[7] Tang Tonggao; Zhao Zhaokeng;. Stack Method in Program Semantics[J]. , 1987, 2(1): 51 -63 .
[8] Min Yinghua;. Easy Test Generation PLAs[J]. , 1987, 2(1): 72 -80 .
[9] Zhu Hong;. Some Mathematical Properties of the Functional Programming Language FP[J]. , 1987, 2(3): 202 -216 .
[10] Li Minghui;. CAD System of Microprogrammed Digital Systems[J]. , 1987, 2(3): 226 -235 .

ISSN 1000-9000(Print)

CN 11-2296/TP

Editorial Board
Author Guidelines
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
E-mail: jcst@ict.ac.cn
  Copyright ©2015 JCST, All Rights Reserved