Feature Based Dense Stereo Matching using Dynamic Programming and Color
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%.
[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.
[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.
@article{"International Journal of Information, Control and Computer Sciences:55972", author = "Hajar Sadeghi and Payman Moallem and S. Amirhassn Monadjemi", title = "Feature Based Dense Stereo Matching using Dynamic Programming and Color", 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.", volume = "2", number = "6", pages = "1958-8", }
