A Review on Stereo Vision Algorithm: Challenges and Solutions

Main Article Content

Kai Yit Kok
Parvathy Rajendran

Abstract

This paper presents a survey on existing stereo vision algorithms. The existing stereo vision algorithms are discussed in terms of concept, performance and related improvements. Also, a brief analysis of performance comparison among existing stereo vision algorithms is presented. Moreover, available improvements and solutions for stereo vision challenges such as computational complexity, occlusion, radiometric distortion, depth discontinuity and textureless region are reviewed.

Article Details

How to Cite
[1]
K. Y. Kok and P. Rajendran, “A Review on Stereo Vision Algorithm: Challenges and Solutions”, ECTI-CIT Transactions, vol. 13, no. 2, pp. 112–128, Aug. 2019.
Section
Review Article

References

Y. Sumi, Y. Kawai, T. Yoshimi, F. Tomita, 3D object recognition in cluttered environments by segment-based stereo vision, International Journal of Computer Vision, 46 (2002) 5-23.

C. Georgoulas, I. Andreadis, FPGA based disparity map computation with vergence control, Microprocessors and Microsystems, 34 (2010) 259-273.

S.N. Sinha, P. Mordohai, M. Pollefeys, Multi-view stereo via graph cuts on the dual of an adaptive tetrahedral mesh, in: Computer Vision, 2007. ICCV 2007. IEEE 11th International Conference on, IEEE, 2007, pp. 1-8.

S.G. Bahnemiri, A. Mousavinia, Environment mapping with stereo vision and Belief Propagation algorithm, in: Knowledge-Based Engineering and Innovation (KBEI), 2017 IEEE 4th International Conference on, IEEE, 2017, pp. 0101-0107.

B.H. Bodkin, Real-Time Mobile Stereo Vision, (2012).

D. Scharstein, R. Szeliski, A taxonomy and evaluation of dense two-frame stereo correspondence algorithms, International journal of computer vision, 47 (2002) 7-42.

M.Z. Brown, D. Burschka, G.D. Hager, Advances in computational stereo, IEEE transactions on pattern analysis and machine intelligence, 25 (2003) 993-1008.

M. Gong, R. Yang, L. Wang, M. Gong, A performance study on different cost aggregation approaches used in real-time stereo matching, International Journal of Computer Vision, 75 (2007) 283-296.

L. Nalpantidis, G.C. Sirakoulis, A. Gasteratos, Review of stereo matching algorithms for 3D vision, in: 16th International Symposium on Measurement and Control in Robotics 21-23 June 2007-Warsaw, POLAND, 2007.

F. Tombari, S. Mattoccia, L. Di Stefano, E. Addimanda, Classification and evaluation of cost aggregation methods for stereo correspondence, in: Computer Vision and Pattern Recognition, 2008. CVPR 2008. IEEE Conference on, IEEE, 2008, pp. 1-8.

N. Lazaros, G.C. Sirakoulis, A. Gasteratos, Review of stereo vision algorithms: from software to hardware, International Journal of Optomechatronics, 2 (2008) 435-462.

J. Fang, A.L. Varbanescu, J. Shen, H. Sips, G. Saygili, L. Van Der Maaten, Accelerating cost aggregation for real-time stereo matching, in: 2012 IEEE 18th International Conference on Parallel and Distributed Systems, IEEE, 2012, pp. 472-481.

D. Kumari, K. Kaur, A survey on stereo matching techniques for 3D vision in image processing, Int. J. Eng. Manuf, 4 (2016) 40-49.

R.A. Hamzah, H. Ibrahim, Literature survey on stereo vision disparity map algorithms, Journal of Sensors, 2016 (2016).

M. Hariyama, T. Takeuchi, M. Kameyama, VLSI processor for reliable stereo matching based on adaptive window-size selection, in: Proceedings 2001 ICRA. IEEE International Conference on Robotics and Automation (Cat. No. 01CH37164), IEEE, 2001, pp. 1168-1173.

L. Wang, M. Gong, M. Gong, R. Yang, How far can we go with local optimization in real-time stereo matching, in: 3D Data Processing, Visualization, and Transmission, Third International Symposium on, IEEE, 2006, pp. 129-136.

Q. Yang, P. Ji, D. Li, S. Yao, M. Zhang, Fast stereo matching using adaptive guided filtering, Image and Vision Computing, 32 (2014) 202-211.

A.F. Bobick, S.S. Intille, Large occlusion stereo, International Journal of Computer Vision, 33 (1999) 181-200.

H. Hirschmüller, P.R. Innocent, J. Garibaldi, Real-time correlation-based stereo vision with reduced border errors, International Journal of Computer Vision, 47 (2002) 229-246.

K.-J. Yoon, I.-S. Kweon, Locally adaptive support-weight approach for visual correspondence search, in: Computer Vision and Pattern Recognition, 2005. CVPR 2005. IEEE Computer Society Conference on, IEEE, 2005, pp. 924-931.

C.C. Pham, J.W. Jeon, Domain transformation-based efficient cost aggregation for local stereo matching, IEEE Transactions on Circuits and Systems for Video Technology, 23 (2013) 1119-1130.

O. Veksler, Fast variable window for stereo correspondence using integral images, in: Computer Vision and Pattern Recognition, 2003. Proceedings. 2003 IEEE Computer Society Conference on, IEEE, 2003, pp. I-I.

R.K. Gupta, S.-Y. Cho, Window-based approach for fast stereo correspondence, IET Computer Vision, 7 (2013) 123-134.

N. Einecke, J. Eggert, A multi-block-matching approach for stereo, in: Intelligent Vehicles Symposium (IV), 2015 IEEE, IEEE, 2015, pp. 585-592.

K. Zhang, J. Lu, G. Lafruit, Cross-based local stereo matching using orthogonal integral images, IEEE transactions on circuits and systems for video technology, 19 (2009) 1073-1079.

F. Tombari, S. Mattoccia, L. Di Stefano, E. Addimanda, Near real-time stereo based on effective cost aggregation, in: Pattern Recognition, 2008. ICPR 2008. 19th International Conference on, IEEE, 2008, pp. 1-4.

R. Trapp, S. Drüe, G. Hartmann, Stereo matching with implicit detection of occlusions, in: European Conference on Computer Vision, Springer, 1998, pp. 17-33.

R.P. Wildes, Direct recovery of three-dimensional scene geometry from binocular stereo disparity, IEEE Transactions on Pattern Analysis & Machine Intelligence, (1991) 761-774.

B.L. Anderson, K. Nakayama, Toward a general theory of stereopsis: binocular matching, occluding contours, and fusion, Psychological review, 101 (1994) 414.

D. Geiger, B. Ladendorf, A. Yuille, Occlusions and binocular stereo, International Journal of Computer Vision, 14 (1995) 211-226.

K. Mühlmann, D. Maier, J. Hesser, R. Männer, Calculating dense disparity maps from color stereo images, an efficient implementation, International Journal of Computer Vision, 47 (2002) 79-88.

M.J. Hannah, Computer matching of areas in stereo images, in, STANFORD UNIV CA DEPT OF COMPUTER SCIENCE, 1974.

M. Gong, R. Yang, Image-gradient-guided real-time stereo on graphics hardware, in: 3-D Digital Imaging and Modeling, 2005. 3DIM 2005. Fifth International Conference on, IEEE, 2005, pp. 548-555.

P. Pandey, A. Goel, Novel method for occlusion reduction and disparity refinement, in: Image Information Processing (ICIIP), 2017 Fourth International Conference on, IEEE, 2017, pp. 1-4.

D.K. Hoa, L. Dung, N.T. Dzung, Efficient determination of disparity map from stereo images with modified sum of absolute differences (SAD) algorithm, in: Advanced Technologies for Communications (ATC), 2013 International Conference on, IEEE, 2013, pp. 657-660.

V.G. Posugade, R.P. Patil, A novel framework for disparity estimation in FPGA, in: Automatic Control and Dynamic Optimization Techniques (ICACDOT), International Conference on, IEEE, 2016, pp. 1102-1105.

R.A. Hamzah, M.S. Hamid, A. Kadmin, S.F.A. Ghani, S.S. Fakulti, Matching cost computation based on sum of absolute RGB differences, in: 2018 IEEE Symposium on Computer Applications & Industrial Electronics (ISCAIE), IEEE, 2018, pp. 317-320.

P. Anandan, A computational framework and an algorithm for the measurement of visual motion, International Journal of Computer Vision, 2 (1989) 283-310.

L. Matthies, T. Kanade, R. Szeliski, Kalman filter-based algorithms for estimating depth from image sequences, International Journal of Computer Vision, 3 (1989) 209-238.

H. Hirschmuller, D. Scharstein, Evaluation of cost functions for stereo matching, in: Computer Vision and Pattern Recognition, 2007. CVPR'07. IEEE Conference on, IEEE, 2007, pp. 1-8.

S.i. Satoh, Simple low-dimensional features approximating NCC-based image matching, Pattern Recognition Letters, 32 (2011) 1902-1911.

J. Banks, M. Bennamoun, P. Corke, Non-parametric techniques for fast and robust stereo matching, in: TENCON'97. IEEE Region 10 Annual Conference. Speech and Image Technologies for Computing and Telecommunications., Proceedings of IEEE, IEEE, 1997, pp. 365-368.

H. Hirschmüller, D. Scharstein, Evaluation of stereo matching costs on images with radiometric differences, IEEE Transactions on Pattern Analysis & Machine Intelligence, (2008) 1582-1599.

R. Zabih, J. Woodfill, Non-parametric local transforms for computing visual correspondence, in: European conference on computer vision, Springer, 1994, pp. 151-158.

C. Banz, S. Hesselbarth, H. Flatt, H. Blume, P. Pirsch, Real-time stereo vision system using semi-global matching disparity estimation: Architecture and FPGA-implementation, in: Embedded Computer Systems (SAMOS), 2010 International Conference on, IEEE, 2010, pp. 93-101.

S.H. Lee, S. Sharma, Real-time disparity estimation algorithm for stereo camera systems, IEEE transactions on Consumer electronics, 57 (2011).

J. Lim, Y. Kim, S. Lee, A census transform-based robust stereo matching under radiometric changes, in: Signal and Information Processing Association Annual Summit and Conference (APSIPA), 2016 Asia-Pacific, IEEE, 2016, pp. 1-4.

S. Gautama, S. Lacroix, M. Devy, Evaluation of stereo matching algorithms for occupant detection, in: Recognition, Analysis, and Tracking of Faces and Gestures in Real-Time Systems, 1999. Proceedings. International Workshop on, IEEE, 1999, pp. 177-184.

H. Hirschmuller, Improvements in real-time correlation-based stereo vision, in: Stereo and Multi-Baseline Vision, 2001.(SMBV 2001). Proceedings. IEEE Workshop on, IEEE, 2001, pp. 141-148.

C. Murphy, D. Lindquist, A.M. Rynning, T. Cecil, S. Leavitt, M.L. Chang, Low-cost stereo vision on an FPGA, in: Field-Programmable Custom Computing Machines, 2007. FCCM 2007. 15th Annual IEEE Symposium on, IEEE, 2007, pp. 333-334.

J.I. Woodfill, G. Gordon, R. Buck, Tyzx deepsea high speed stereo vision system, in: Computer Vision and Pattern Recognition Workshop, 2004. CVPRW'04. Conference on, IEEE, 2004, pp. 41-41.

M.A. Ibarra-Manzano, D.-L. Almanza-Ojeda, M. Devy, J.-L. Boizard, J.-Y. Fourniols, Stereo vision algorithm implementation in fpga using census transform for effective resource optimization, in: Digital System Design, Architectures, Methods and Tools, 2009. DSD'09. 12th Euromicro Conference on, IEEE, 2009, pp. 799-805.

C. Zinner, M. Humenberger, K. Ambrosch, W. Kubinger, An optimized software-based implementation of a census-based stereo matching algorithm, in: International Symposium on Visual Computing, Springer, 2008, pp. 216-227.

D. Hernandez-Juarez, A. Chacón, A. Espinosa, D. Vázquez, J.C. Moure, A.M. López, Embedded real-time stereo estimation via semi-global matching on the GPU, Procedia Computer Science, 80 (2016) 143-153.

K. Song, X. Wen, Y. Zhao, Z. Dong, Y. Yan, Noise robust image matching using adjacent evaluation census transform and wavelet edge joint bilateral filter in stereo vision, Journal of Visual Communication and Image Representation, 38 (2016) 487-503.

E.-T. Baek, Y.-S. Ho, Occlusion and error detection for stereo matching and hole-filling using dynamic programming, Electronic Imaging, 2016 (2016) 1-6.

Q.-Q. Yang, L.-H. Wang, D.-X. Li, M. Zhang, Hybrid stereo matching by dynamic programming with enhanced cost entry for real-time depth generation, in: Audio, Language and Image Processing (ICALIP), 2012 International Conference on, IEEE, 2012, pp. 557-563.

R.L. Rivest, C.E. Leiserson, Introduction to algorithms, McGraw-Hill, Inc., 1990.

S.-F. Hsiao, W.-L. Wang, P.-S. Wu, VLSI implementations of stereo matching using dynamic programming, in: VLSI Design, Automation and Test (VLSI-DAT), 2014 International Symposium on, IEEE, 2014, pp. 1-4.

Y.-C. Fan, Y.-H. Jiang, C.-L. Chen, Disparity measurement using dynamic programming, in: Instrumentation and Measurement Technology Conference (I2MTC), 2012 IEEE International, IEEE, 2012, pp. 2683-2686.

J.C. Kim, K.M. Lee, B.T. Choi, S.U. Lee, A dense stereo matching using two-pass dynamic programming with generalized ground control points, in: Computer Vision and Pattern Recognition, 2005. CVPR 2005. IEEE Computer Society Conference on, IEEE, 2005, pp. 1075-1082.

E.F. Sawires, A.M. Hamdy, F.Z. Amer, E. Bakr, Disparity map using suboptimal cost with dynamic programming, in: Signal Processing and Information Technology (ISSPIT), 2010 IEEE International Symposium on, IEEE, 2010, pp. 209-214.

J. Witt, U. Weltin, Sparse stereo by edge-based search using dynamic programming, in: ICPR, 2012, pp. 3631-3635.

J.K. Suhr, H.G. Jung, Dense stereo-based robust vertical road profile estimation using Hough transform and dynamic programming, IEEE Transactions on Intelligent Transportation Systems, 16 (2015) 1528-1536.

Y. Boykov, O. Veksler, R. Zabih, Fast approximate energy minimization via graph cuts, IEEE Transactions on pattern analysis and machine intelligence, 23 (2001) 1222-1239.

L. Hong, G. Chen, Segment-based stereo matching using graph cuts, in: Computer Vision and Pattern Recognition, 2004. CVPR 2004. Proceedings of the 2004 IEEE Computer Society Conference on, IEEE, 2004, pp. I-I.

D.A. Altantawy, M. Obbaya, S. Kishk, A fast non-local based stereo matching algorithm using graph cuts, in: Computer Engineering & Systems (ICCES), 2014 9th International Conference on, IEEE, 2014, pp. 130-135.

L. Feng, K. Qin, Superpixel-based graph cuts for accurate stereo matching, in: IOP Conference Series: Earth and Environmental Science, IOP Publishing, 2017, pp. 012161.

F.-z. Wang, D.-g. Huang, S. Ge, Belief propagation stereo matching based on differential geometry constraint of disparity, in: Digital Manufacturing and Automation (ICDMA), 2010 International Conference on, IEEE, 2010, pp. 324-327.

S.-S. Wu, C.-H. Tsai, L.-G. Chen, Efficient hardware architecture for large disparity range stereo matching based on belief propagation, in: Signal Processing Systems (SiPS), 2016 IEEE International Workshop on, IEEE, 2016, pp. 236-241.

M. Sarkis, K. Diepold, Sparse stereo matching using belief propagation, in: Image Processing, 2008. ICIP 2008. 15th IEEE International Conference on, IEEE, 2008, pp. 1780-1783.

C. Liang, L. Wang, H. Liu, Stereo matching with cross-based region, hierarchical belief propagation and occlusion handling, in: Mechatronics and Automation (ICMA), 2011 International Conference on, IEEE, 2011, pp. 1999-2003.

C. Luo, J. Lei, G. Hu, K. Fan, S. Bu, Stereo Matching with Semi-limited Belief Propagation, in: Genetic and Evolutionary Computing (ICGEC), 2012 Sixth International Conference on, IEEE, 2012, pp. 1-4.

J.-F. Nezan, A. Mercat, P. Delmas, G. Gimelfarb, Optimized belief propagation algorithm onto embedded multi and many-core systems for stereo matching, in: Parallel, Distributed, and Network-Based Processing (PDP), 2016 24th Euromicro International Conference on, IEEE, 2016, pp. 332-336.

A. Miron, S. Ainouz, A. Rogozan, A. Bensrhair, A robust cost function for stereo matching of road scenes, Pattern Recognition Letters, 38 (2014) 70-77.

M.F. Tappen, W.T. Freeman, Comparison of graph cuts with belief propagation for stereo, using identical MRF parameters, in: null, IEEE, 2003, pp. 900.

Y. Boykov, V. Kolmogorov, An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision, in: International workshop on energy minimization methods in computer vision and pattern recognition, Springer, 2001, pp. 359-374.

J. Sun, N.-N. Zheng, H.-Y. Shum, Stereo matching using belief propagation, IEEE Transactions on pattern analysis and machine intelligence, 25 (2003) 787-800.

A. Klaus, M. Sormann, K. Karner, Segment-based stereo matching using belief propagation and a self-adapting dissimilarity measure, in: Pattern Recognition, 2006. ICPR 2006. 18th International Conference on, IEEE, 2006, pp. 15-18.

K. Briechle, U.D. Hanebeck, Template matching using fast normalized cross correlation, in: Optical Pattern Recognition XII, International Society for Optics and Photonics, 2001, pp. 95-103.

K. Zhang, J. Lu, G. Lafruit, R. Lauwereins, L. Van Gool, Robust stereo matching with fast normalized cross-correlation over shape-adaptive regions, in: Image Processing (ICIP), 2009 16th IEEE International Conference on, IEEE, 2009, pp. 2357-2360.

E. Binaghi, I. Gallo, G. Marino, M. Raspanti, Neural adaptive stereo matching, Pattern Recognition Letters, 25 (2004) 1743-1758.

C. Cigla, A.A. Alatan, Information permeability for stereo matching, Signal Processing: Image Communication, 28 (2013) 1072-1088.

L. Wang, M. Liao, M. Gong, R. Yang, D. Nister, High-quality real-time stereo using adaptive cost aggregation and dynamic programming, in: null, IEEE, 2006, pp. 798-805.

M. Gong, Y.-H. Yang, Real-time stereo matching using orthogonal reliability-based dynamic programming, IEEE Transactions on Image Processing, 16 (2007) 879-884.

D. Wang, K.B. Lim, A new segment-based stereo matching using graph cuts, in: Computer Science and Information Technology (ICCSIT), 2010 3rd IEEE International Conference on, IEEE, 2010, pp. 410-416.

T. Taniai, Y. Matsushita, T. Naemura, Graph cut based continuous stereo matching using locally shared labels, in: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2014, pp. 1613-1620.

E.-T. Baek, Y.-S. Ho, Temporal stereo disparity estimation with graph cuts, in: Signal and Information Processing Association Annual Summit and Conference (APSIPA), 2015 Asia-Pacific, IEEE, 2015, pp. 184-187.

Y. Geng, Y. Zhao, H. Chen, Improved belief propagation based on RGB vector measure for stereo matching, in: Wireless Communications and Signal Processing (WCSP), 2011 International Conference on, IEEE, 2011, pp. 1-5.

J. Kopf, M.F. Cohen, D. Lischinski, M. Uyttendaele, Joint bilateral upsampling, ACM Transactions on Graphics (ToG), 26 (2007) 96.

K. Song, Y. Yan, M. NIU, C. LIU, Effective stereo matching method with equicrural triangle census transform, J. Comput. Inform. Syst, 8 (2015) 7769-7780.

B. Recht, M. Fazel, P.A. Parrilo, Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization, SIAM review, 52 (2010) 471-501.

L. Fućek, I. Marković, I. Cvišić, I. Petrović, Dense Disparity Estimation in Ego-motion Reduced Search Space, IFAC-PapersOnLine, 50 (2017) 10122-10127.

B.J. Tippetts, D.-J. Lee, J.K. Archibald, K.D. Lillywhite, Dense disparity real-time stereo vision algorithm for resource-limited systems, IEEE Transactions on Circuits and Systems for Video Technology, 21 (2011) 1547-1555.

M. Kuhn, S. Moser, O. Isler, F.K. Gurkaynak, A. Burg, N. Felber, H. Kaeslin, W. Fichtner, Efficient ASIC implementation of a real-time depth mapping stereo vision system, in: Circuits and Systems, 2003 IEEE 46th Midwest Symposium on, IEEE, 2003, pp. 1478-1481.