Efficient normalized cross correlation calculation method for stereo vision based robot navigation

doi:10.1007/s11704-011-9190-2

Front Comput Sci Chin

0, Vol.

Issue () : 227-235 https://doi.org/10.1007/s11704-011-9190-2

RESEARCH ARTICLE

Efficient normalized cross correlation calculation method for stereo vision based robot navigation

Yehu SHEN(

)

Department of System Integration and IC Design, Suzhou Institute of Nano-tech and Nano-bionics, Chinese Academy of Sciences, Suzhou 215125, China

Download: PDF(258 KB) HTML
Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks

Abstract

Stereo vision systems are widely used for autonomous robot navigation. Most of them apply local window based methods for real-time purposes. Normalized cross correlation (NCC) is notorious for its high computational cost, though it is robust to different illumination conditions between two cameras. It is rarely used in real-time stereo vision systems. This paper proposes an efficient normalized cross correlation calculation method based on the integral image technique. Its computational complexity has no relationship to the size of the matching window. Experimental results show that our algorithm can generate the same results as traditional normalized cross correlation with a much lower computational cost. Our algorithm is suitable for planet rover navigation.

Keywords normalized cross correlation (NCC) stereo matching integral image

Corresponding Author(s): SHEN Yehu,Email:yhshen2009@sinano.ac.cn

Issue Date: 05 June 2011

Cite this article:

Yehu SHEN. Efficient normalized cross correlation calculation method for stereo vision based robot navigation[J]. Front Comput Sci Chin, 0, (): 227-235.

URL:

https://academic.hep.com.cn/fcs/EN/10.1007/s11704-011-9190-2
https://academic.hep.com.cn/fcs/EN/Y0/V/I/227

Fig.1 Element at (, ) of integral image is the sum of all the elements in the black area of the original image

Fig.2 Demonstration of calculating the sum of values in block D from the original image with its corresponding integral image

Fig.3 Comparison of computational costs between our proposed algorithm and the simple NCC calculation method for (a) different matching window sizes; (b) different disparity search ranges; (c) different image sizes

Tab.1 Comparison of computational times between SAD and NCC

Fig.4 3rd stereo pair. (a) Left image; (b) right image; (c) disparity image of GCP+ENCC; (d) disparity image of DP; (e) disparity image of GC; (f)–(h) 3D reconstruction views from the disparity image (c)

Fig.5 4th stereo pair. (a) Left image; (b) right image; (c) disparity images of GCP+ENCC; (d) disparity image of DP; (e) disparity image of GC; (f–h) 3D reconstruction views from the disparity image in (c)

Tab.2 Comparison of computational costs for GCP+ENCC, DP and GC

1	Urmson C, Anhalt J, Bagnell D, et al. Autonomous driving in urban environments: boss and the urban challenge. Journal of Field Robotics , 2008, 25(8): 425–466 doi: 10.1002/rob.20255
2	Thrun S, Montemerlo M, Dahlkamp H, et al. Stanley, the robot that won the DARPA grand challenge. Journal of Field Robotics , 2006, 23(9): 661–692 doi: 10.1002/rob.20147
3	Scharstein D, Szeliski R. A taxonomy and evaluation of dense two-frame stereo correspondence algorithms. International Journal of Computer Vision , 2002, 47(1/3): 7–42 doi: 10.1023/A:1014573219977
4	Brown M, Burschka D, Hager G. Advances in computational stereo. IEEE Transactions on Pattern Analysis and Machine Intelligence , 2003, 25(8): 993–1008 doi: 10.1109/TPAMI.2003.1217603
5	Bellutta P, Manduchi R, Matthies L, et al. Terrain perception for DEMO III. In: Proceedings of 2000 IEEE Intelligent Vehicles Symposium . 2000, 326–331
6	Goldberg S, Maimone M, Matthies L. Stereo vision and rover navigation software for planetary exploration. In: Proceedings of 2002 IEEE Aerospace Conference . 2002, 2025–2036
7	Zabih R, Woodfill J. Non-parametric local transforms for computing visual correspondence. In: Proceedings of 3rd European Conference on Computer Vision . 1994, 151–158
8	Point Grey Triclops. http://www.ptgrey.com/
9	Small Vision System. http://www.videredesign.com/
10	Matthies L, Maimone M, Johnson A, et al. Computer vision on Mars. International Journal of Computer Vision , 2007, 75(1): 67–92 doi: 10.1007/s11263-007-0046-z
11	Woodfill J, Gordon G, Jurasek D, et al. The Tyzx DeepSea G2 vision system, a taskable, embedded stereo camera. In: Proceedings of the IEEE Computer Society Workshop on Embedded Computer Vision, Conference on Computer Vision and Pattern Recognition . 2006, 126–132
12	Faugeras O, Hotz B, Mahieu H, et al. Real time correlation-based stereo: algorithm, implementations and applications. Technical report, INRIA, Sophia-Antipolis , 1993
13	Lewis J. Fast normalized cross-correlation. Online , 1995, Available: http://www.idiom.com/~zilla/Work/nvisionInterface/nip.pdf
14	Hii A J, Hann C E, Chase J G, et al. Fast normalized cross correlation for motion tracking using basis functions. Computer Methods and Programs in Biomedicine , 2006, 82(2): 144–156 doi: 10.1016/j.cmpb.2006.02.007 pmid:16581152
15	Briechle K, Hanebeck U. Template matching using fast normalized cross correlation. In: Proceedings of the Society for Photo- Instrumentation Engineers , 2001, 4387: 95–102
16	Viola P, Jones M. Robust real-time face detection. International Journal of Computer Vision , 2004, 57(2): 137–154 doi: 10.1023/B:VISI.0000013087.49260.fb
17	Crow F. Summed-area tables for texture mapping. In: Proceedings of 11th Annual Conference on Computer Graphics and Interactive Techniques . 1984, 207–212
18	Veksler O. Fast variable window for stereo correspondence using integral images. In: Proceedings of 2003 IEEE Computer Society Conference on Computer Vision and Pattern Recognition . 2003, 556–561
19	MER Analyst's Notebook. http://anserver1.eprsl.wustl.edu/
20	Chen Q, Medioni G. Building 3-D human face models from two photographs. Journal of VLSI Signal Processing , 2001, 27(1/2): 127–140 doi: 10.1023/A:1008131816432
21	Kolmogorov V, Zabih R. Computing visual correspondence with occlusions using Graph Cuts. In: Proceedings of 8th IEEE International Conference on Computer Vision . 2001, 508–515

[1]	Gaochang WU, Yipeng LI, Yuanhao HUANG, Yebin LIU. Joint view synthesis and disparity refinement for stereo matching[J]. Front. Comput. Sci., 2019, 13(6): 1337-1352.

Viewed

Full text

Abstract

Cited

Shared

Discussed