Performance Analysis between Basic Block Matching and Dynamic Programming of Stereo Matching Algorithm

Authors

  • Maged Aboali Machine Learning and Signal Processing (MLSP) Research Group, Center of Telecommunication Research & Innovation (CETRI), Fakulti Kejuruteraan Elektronik Dan Kejuruteraan Komputer (FKEKK), Universiti Teknikal Malaysia Melaka (UTeM), Malaysia.
  • Nurulfajar Abd Manap Machine Learning and Signal Processing (MLSP) Research Group, Center of Telecommunication Research & Innovation (CETRI), Fakulti Kejuruteraan Elektronik Dan Kejuruteraan Komputer (FKEKK), Universiti Teknikal Malaysia Melaka (UTeM), Malaysia.
  • Abd Majid Darsono Machine Learning and Signal Processing (MLSP) Research Group, Center of Telecommunication Research & Innovation (CETRI), Fakulti Kejuruteraan Elektronik Dan Kejuruteraan Komputer (FKEKK), Universiti Teknikal Malaysia Melaka (UTeM), Malaysia.
  • Zulkalnain Mohd Yusof Machine Learning and Signal Processing (MLSP) Research Group, Center of Telecommunication Research & Innovation (CETRI), Fakulti Kejuruteraan Elektronik Dan Kejuruteraan Komputer (FKEKK), Universiti Teknikal Malaysia Melaka (UTeM), Malaysia.

Keywords:

Basic Block Matching (BBM) algorithms, disparity map accuracy Dynamic Programming (DP), Performance analysis,

Abstract

One of the most important key steps of stereo vision algorithms is the disparity map implementation, where it generally utilized to decorrelate data and recover 3D scene framework of stereo image pairs. However, less accuracy of attaining the disparity map is one of the challenging problems on stereo vision approach. Thus, various methods of stereo matching algorithms have been developed and widely investigated for implementing the disparity map of stereo image pairs including the Dynamic Programming (DP) and the Basic Block Matching (BBM) methods. This paper mainly presents an evaluation between the Dynamic Programming (DP) and the Basic Block Matching (BBM) methods of stereo matching algorithms in term of disparity map accuracy, noise enhancement, and smoothness. Where the Basic Block Matching (BBM) is using the Sum of Absolute Difference (SAD) method in this research as a basic algorithm to determine the correspondence points between the target and reference images. In contrast, Dynamic Programming (DP) has been used as a global optimization approach. Besides, there will be a performance analysis including graphs results from both methods presented in this paper, which can show that both methods can be used on many stereo vision applications.

References

D. Murray and C. Jennings, “Stereo vision based mapping and navigation for mobile robots,” Robot. Autom. 1997. Proceedings., 1997 IEEE Int. Conf. on. Vol. 2. IEEE, 1997.

M. D. Yang, D. W., Chu, L. C., Chen, C. W., Wang, J., & Shieh, “Depth-Reliability-Based Stereo-Matching Algorithm and Its VLSI Architecture Design,” IEEE Trans. Circuits Syst. Video Technol. 25.6 1038-1050, 2015.

M. E. N. Yubo, Z. Guoyin, M. E. N. Chaoguang, L. I. Xiang, and M. A. Ning, “A Stereo Matching Algorithm Based on Four-Moded Census and Relative Confidence Plane Fitting,” Chinese J. Electron. 24.4 807-812, 2015.

L. Zhang, “Fast Stereo Matching Algorithm for Intermediate View Reconstruction of Stereoscopic Television Images,” IEEE Trans. circuits Syst. video Technol. 16.10 1259-1270, 2006.

M. Aboali, N. A. Manap, A. M. Darsono, and Z. M. Yusof, “Review on Three-Dimensional ( 3-D ) Acquisition and Range Imaging Techniques,” Int. J. Appl. Eng. Res. 12.10 2409-2421, 2017.

S. Hussain and R. Modi, “Advancement in Depth Estimation for Stereo Image Pair,” Int. J. Innov. Res. Comput. Commun. Eng. 1.4, 2013.

Q. Zhang, P. An, Y. Zhang, L. Shen, and Z. Zhang, “An improved depth map estimation for coding and view synthesis,” Image Process. (ICIP), 2011 18th IEEE Int. Conf. on. IEEE, 2011.

M. Rziza, A. Tamtaoui, L. Morin, and D. Aboutajdine, “Estimation and Segmentation of a Dense Disparity Map for 3D Reconstruction,” Acoust. Speech, Signal Process. 2000. ICASSP’00. Proceedings. 2000 IEEE Int. Conf. on. Vol. 4. IEEE, 2000.

D. Scharstein and R. Szeliski, “A taxonomy and evaluation of dense two-frame stereo correspondence algorithms,” Int. J. Comput. Vis. 47.1-3 7-42, 2002.

M. Gong and Y. Yang, “Fast Stereo Matching Using ReliabilityBased Dynamic Programming and Consistency Constraints,” Comput. Vision, 2003. Proceedings. Ninth IEEE Int. Conf. on. IEEE, 2003.

L. Di, M. Marchionni, and S. Mattoccia, “A fast area-based stereo matching algorithm,” Image Vis. Comput. 22.12 983-1005, 2004.

A. Donate, X. Liu, and E. G. Collins, “Efficient path-based stereo matching with subpixel accuracy,” IEEE Trans. Syst. Man, Cybern. Part B 41.1 183-195, 2011.

Q. Yang, “A Non-Local Cost Aggregation Method for Stereo Matching,” Comput. Vis. Pattern Recognit. (CVPR), 2012 IEEE Conf. (pp. 1402-1409). IEEE, 2012.

G. Li, “Stereo matching using normalized cross-correlation in LogRGB space,” Comput. Vis. Remote Sens. (CVRS), 2012 Int. Conf. on. IEEE, 2012.

R. Long, Y. Lei, and Z. Z. L. G. Jiaqi-fei, “An Improved Stereo Match Algorithm Based on Support-Weight Approach,” Instrum. Meas. Comput. Commun. Control (IMCCC), 2014 Fourth Int. Conf. on. IEEE, 2014.

N. Lazaros, G. C. Sirakoulis, and A. Gasteratos, “Review of Stereo Vision Algorithms : From Software to Hardware,” J. Real-Time Image Process. 11.1 5-25, 2008.

B. Tippetts, D. Jye, L. Kirt, and J. Archibald, “Review of stereo vision algorithms and their suitability for resource-limited systems,” J. Real-Time Image Process. 11.1 5-25, 2016.

D. Kumari and K. Kaur, “A Survey on Stereo Matching Techniques for 3D Vision in Image Processing,” Int. J. Eng. Manuf 4 40-49, 2016.

F. Tombari, L. Di Stefano, S. Mattoccia, A. Mainetti, and D. Arces, “A 3D Reconstruction System Based on Improved Spacetime Stereo,” Control Autom. Robot. Vis. (ICARCV), 2010 11th Int. Conf. on. IEEE, 2010.

J. Cai, “Fast Stereo Matching : Coarser to Finer with Selective Updating,” Image Vis. Comput. New Zealand, 2007.

S. N. Sinha, D. Scharstein, and R. Szeliski, “Efficient high-resolution stereo matching using local plane sweeps,” Proc. IEEE Conf. Comput. Vis. Pattern Recognition, 2014.

H. Hirschm and D. Scharstein, “Evaluation of Cost Functions for Stereo Matching,” Comput. Vis. Pattern Recognition, 2007. CVPR’07. IEEE Conf. on. IEEE, 2007.

L. Gomes Filho, J. C., Peiter, A. S., Pimentel, W. R. O., Soletti, J. I., Carvalho, S. H. V., & Meili, “Biodiesel production from Sterculia striata oil by ethyl transesterification method.,” Ind. Crop. Prod. 74 767-772, 2015.

F. Tombari, S. Mattoccia, L. Di Stefano, and E. Addimanda, “Classification and evaluation of cost aggregation methods for stereo correspondence,” Comput. Vis. Pattern Recognition, 2008. CVPR 2008. IEEE Conf. on. IEEE, 2008.

A. Hosni, M. Bleyer, and M. Gelautz, “Secrets of adaptive support weight techniques for local stereo matching q,” Comput. Vis. Image Underst., vol. 117, no. 6, pp. 620–632, 2013.

C. Rhemann, A. Hosni, M. Bleyer, C. Rother, and M. Gelautz, “Fast Cost-Volume Filtering for Visual Correspondence and Beyond,” IEEE Trans. Pattern Anal. Mach. Intell. 35.2 504-511, 2013.

L. De-maeztu, S. Mattoccia, and R. Cabeza, “Linear stereo matching,” Comput. Vis. (ICCV), 2011 IEEE Int. Conf. on. IEEE, 2011.

A. A. Cigla, C., & Alatan, “Information permeability for stereo matching,” Signal Process. Image Commun. 28.9 1072-1088, 2013.

K. Zhang, S. Member, J. Lu, and Q. Yang, “Real-Time and Accurate Stereo : A Scalable Approach with Bitwise Fast Voting on CUDA,” IEEE Trans. Circuits Syst. Video Technol. 21.7 867-878, 2011.

L. Torresani, V. Kolmogorov, and C. Rother, “A dual decomposition approach to feature correspondence,” IEEE Trans. pattern Anal. Mach. Intell. 35.2 259-271, 2013.

B. Potetz, “Efficient Belief Propagation for Vision Using Linear Constraint Nodes,” Comput. Vis. Pattern Recognition, 2007. CVPR’07. IEEE Conf. on. IEEE, 2007.

M. Bleyer and M. Gelautz, “A layered stereo matching algorithm using image segmentation and global visibility constraints,” ISPRS J. Photogramm. Remote Sens. 59.3 128-150, 2005.

R. Gouiaa and J. Meunier, “3D reconstruction by fusioning shadow and silhouette information,” Comput. Robot Vis. (CRV), 2014 Can. Conf. on. IEEE, 2014.

D. Neilson and Y. H. Yang, “A component-wise analysis of constructible match cost functions for global stereopsis,” IEEE Trans. pattern Anal. Mach. Intell. 33.11 2147-2159, 2011.

W. H. . Huat, T.C., bin Abd Manap, N. and Saad, “Analysis on Segment-Based Double Stage Filter Algorithm for Stereo Matching,” J. Eng. Appl. Sci., vol. 11, no. 10, pp. 6240–6245, 2016.

P. Ochs, J. Malik, and T. Brox, “Segmentation of moving objects by long termvideo analysis,” IEEE Trans. pattern Anal. Mach. Intell. 36.6 1187-1200, 2014.

Y. S. Chen, Y. P. Hung, and C. S. Fuh, “Fast block matching algorithm based on the winner-update strategy,” IEEE Trans. Image Process. 10.8 1212-1222, 2001.

D. G. and F. Girosi., “Parallel and deterministic al- gorithms from MRF’s: Surface reconstruction.,” IEEE Trans. Pattern Anal. Mach. Intell. 13.5 401-412, 1991.

V. Kolmogorov and R. Zabih, “Multi-camera scene reconstruction via graph-cuts,” Comput. Vision—ECCV 2002 8-40, 2002.

P. Felzenszwalb and D. Huttenlocher, “Belief Propagation for Early Vision,” Int. J. Comput. Vision, Vol. 70, No. 1, 2006.

O. Veksler, “Stereo Correspondence by Dynamic Programming on a Tree,” Comput. Vis. Pattern Recognition, 2005. CVPR 2005. IEEE Comput. Soc. Conf. on. Vol. 2. IEEE, 2005.

T. Hu, B. Qi, T. Wu, X. Xu, and H. He, “Stereo matching using weighted dynamic programming on a single-direction four-connected tree q,” Comput. Vis. Image Underst. 116.8 908-921, 2012.

M. Khaparde, A., Naik, A., Deshpande, M., Khar, S., Pandhari, K., & Shewale, “Performance Analysis of Stereo Matching Using Segmentation Based Disparity Map,” ICDT 2013 Eighth Int. Conf. Digit. Telecommun., 2013.

Downloads

Published

2017-09-27

How to Cite

Aboali, M., Abd Manap, N., Darsono, A. M., & Mohd Yusof, Z. (2017). Performance Analysis between Basic Block Matching and Dynamic Programming of Stereo Matching Algorithm. Journal of Telecommunication, Electronic and Computer Engineering (JTEC), 9(2-13), 7–16. Retrieved from https://jtec.utem.edu.my/jtec/article/view/2558

Most read articles by the same author(s)

1 2 > >>