Feature Based Dense Stereo Matching using Dynamic Programming and Color

Authors: Hajar Sadeghi, Payman Moallem, S. Amirhassn Monadjemi

Abstract:

This paper presents a new feature based dense stereo matching algorithm to obtain the dense disparity map via dynamic programming. After extraction of some proper features, we use some matching constraints such as epipolar line, disparity limit, ordering and limit of directional derivative of disparity as well. Also, a coarseto- fine multiresolution strategy is used to decrease the search space and therefore increase the accuracy and processing speed. The proposed method links the detected feature points into the chains and compares some of the feature points from different chains, to increase the matching speed. We also employ color stereo matching to increase the accuracy of the algorithm. Then after feature matching, we use the dynamic programming to obtain the dense disparity map. It differs from the classical DP methods in the stereo vision, since it employs sparse disparity map obtained from the feature based matching stage. The DP is also performed further on a scan line, between any matched two feature points on that scan line. Thus our algorithm is truly an optimization method. Our algorithm offers a good trade off in terms of accuracy and computational efficiency. Regarding the results of our experiments, the proposed algorithm increases the accuracy from 20 to 70%, and reduces the running time of the algorithm almost 70%.

Keywords: Chain Correspondence, Color Stereo Matching, Dynamic Programming, Epipolar Line, Stereo Vision.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1332800

References:

[1] D. Scharstein, and R. Szeliski, "A taxonomy and evaluation of dense two-frame stereo correspondence algorithms", International journal of computer vision, 2002, 47(1-3), pp. 7-42.
[2] A. Koschan, "What is New in Computational Stereo Since 1989:A Survey on Current Stereo Papers", Technische Universität Berlin, Technischer Bericht, August 1993, pp. 93-22.
[3] K.I. Tsutsui, M. Taira, and H. Sakata, "Neural mechanisms of threedimensional vision", Neuroscience Research 51, 2005, pp. 221-229.
[4] R. Klette, A. Koschan, K. Schl├╝ns, and V. Rodehorst, "Surface Reconstruction based on Visual Information", Department of Computer Science, Technical Report 95/6, Perth, Western Australia, July 1995, pp. 1-52.
[5] A. Bensrhair, P. Miche, and R. Debrie, "Fast and automatic stereo vision matching algorithm based on dynamic programming method", Pattern Recognition Letters, 1996, 17, pp. 457-466.
[6] S. Birchfield and C. Tomasi, "Depth discontinuities by pixel-to-pixel stereo", International Journal of Computer Vision, 1999, pp. 269-293.
[7] Y. Ohta and T. Kanade, "Stereo by Intra- and Interscanline Search Using Dynamic Programming", IEEE Transactions on PAMI, 1985, 7, pp. 139-154.
[8] O. Veksler, "Stereo Correspondence by Dynamic Programming on a Tree", Proceedings of the 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'05), Volume 2, 2005, pp. 384-390.
[9] C. V. Jawahar and P. J. Narayanan, "A Multifeature Correspondence Algorithm Using Dynamic Programming", ACCV2002: The 5th Asian Conference on Computer Vision, January 2002, pp. 23-25.
[10] B. Tang, D. Ait-Boudaoud, B. J. Matuszewski, and L. k Shark, "An Efficient Feature Based Matching Algorithm for Stereo Images", Proceedings of the Geometric Modeling and Imaging-New Trends (GMAI-06), 2006, pp. 195-202.
[11] R.A.Lane, and N.A.Thacker, "Tutorial: Overview of Stereo Matching Research", Imaging Science and Biomedical Engineering Division, Medical School, University of Manchester, M13 9PT, 1998, pp. 1-10.
[12] C. J. Taylor, "Surface Reconstruction from Feature Based Stereo", Proceedings of the Ninth IEEE International Conference on Computer Vision (ICCV-03), Vol. 1, 2003, pp. 184-190.
[13] S. S. Tan, and D. P. Hart, "A fast and robust feature-based 3D algorithm using compressed image correlation", Pattern Recognition Letters 26, 2005, pp. 1620-1631.
[14] S. brandt, and J. Heikkonen, "Multi-Resolution Matching of Uncalibrated images utilizing epipolar geometry and its uncertainty", IEEE International Conference on image Processing (ICIP), Vol. 2, 2001, pp. 213-216.
[15] B. Tang, D. Ait-Boudaoud, B. J. Matuszewski, and L. k Shark, "An Efficient Feature Based Matching Algorithm for Stereo Images", Proceedings of the Geometric Modeling and Imaging-New Trends (GMAI-06), 2006, 195-202.
[16] R.A.Lane, and N.A.Thacker, "Tutorial: Overview of Stereo Matching Research", Imaging Science and Biomedical Engineering Division, Medical School, University of Manchester, M13 9PT, 1998, 1-10.
[17] C. J. Taylor, "Surface Reconstruction from Feature Based Stereo", Proceedings of the Ninth IEEE International Conference on Computer Vision (ICCV-03), Vol. 1, 2003, 184-190.
[18] L. Di Stefano, M. Marchionni, and S. Mattoccia, "A Fast Area-Based Stereo Matching Algorithm", Image and Vision Computing (JIVC), Vol. 22, No 12, pp 983-1005, October 2004.
[19] V. Kolmogorov, and R. Zabih, "Computing visual corresponding with occlusions using graph cuts", ICCV 2001. Proceedings. Eighth IEEE International Conference on Computer Vision, 2001, Volume 2, 508- 515.
[20] L. Di Stefano, and S. Mattoccia, "Fast stereo matching for the videt system using a general purpose processor with multimedia extensions", Proceedings of the Fifth IEEE International Workshop on Computer Architectures for Machine Perception (CAMP'00), 2000, 356.
[21] O. Faugeras et al, "Real-time correlation-based stereo: algorithm, implementation and applications", Technical Report 2013, Unite derecherche INRIA Sophia-Antipolis, France, Aout, 1993.
[22] T. Kanade, H. Kato, S. Kimura, A. Yoshida, and K. Oda, "Development of a video-rate stereo machine", In Proc. Of International Robotics and Systems Conference (IROS -95), volume 3, pages 95 - 100, August 1995.
[23] K. Konolige. Small vision systems: Hardware and implementation. In 8th Int. Symposium on Robotics Research, pages 111-116, 1997.
[24] P. Moallem, K. Faez, and J. Haddadnia, "Fast Edge-Based Stereo Matching Algorithms through Search Space Reduction", IEICE Trans. INF. & SYST, Vol.E85-D, No. 11, November 2002, 1859-1871.
[25] P. Moallem and K. Faez, "Effective Parameters in Search Space Reduction Used in a Fast Edge-Based Stereo Matching", Journal of Circuits, Systems, and Computers, Vol. 14, No. 2, 2005, 249-266.
[26] P. Moallem, M. Ashorian, B. Mirzaeian, and M.Ataei, "A Novel Fast Feature Based Stereo Matching Algorithm with Low Invalid Matching", WSEAS Transaction on Computers, Issue 3, Vol. 5,March 2006, pp. 469-477.
[27] X. Hua, M. Yokomichi, and M. Kono, "Stereo Correspondence Using Color Based on Competitive-cooperative Neural Networks", Proceedings of the Sixth International Conference on Parallel and Distributed Computing Applications and Technologies, 2005, pp. 856- 860.
[28] Q. Yang, L. Wang, R. yang, H. Stewenius, and D. nister, "Stereo Matching with Color-Weighted correlation, hierarchical Belief Propagation and occlusion Handling", Proceedings of the 2006 IEEE Computer society Conference on Computer Vision and Pattern recognition (CVPR-06), 2006, pp. 2347-2354.
[29] I. Cabani, G. Toulminet, and A. Bensrhair, "A Fast and Self-adaptive Color Stereo Vision Matching; a first step for road Obstacle Detection", Intelligent vehicles symposium, 2006, pp. 13-15.
[30] Stereo data sets with ground truth, Middlebury College, Available: http://cat.middlebury.edu/stereo/data.html.