An Improved Stereo Matching Algorithm Based on Graph Cuts
ZHANG Lingtao1,2,3, QU Daokui1,2, XU Fang1,2
1. Shenyang Institute of Automation, Chinese Academy of Sciences, Shenyang 110016, China; 2. Shenyang SIASUN Robot & Automation CO.LTD, Shenyang 110168, China; 3. Graduate School of the Chinese Academy of Sciences, Beijing 100049, China
Abstract:For the problem that stereo matching methods based on graph cuts are time consuming,this paper puts forward an improved stereo matching algorithm based on reduced graphs.First,the initial disparity for each pixel can be calculated by using local matching method.Then,we keep only some potential disparity values in the complete graph,and the reduced graph will contain a reduced number of vertices and edges.Therefore the graph capacity and execution time are decreased,and a wider disparity range is obtained.At last,it is proved by experiments that this algorithm can achieve a relatively ideal disparity map and save much time in stereo matching.
[1] Scharstein D,Szeliski R.A taxonomy and evaluation of dense two-frame stereo correspondence algorithms[J].International Journal of Computer Vision,2002,47(1/2/3):7-42.
[2] Boykov Y,Kolmogorov V.An experimental comparison of mincut/max-flow algorithms for energy minimization in vision[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2004,26(9):1124-1137.
[3] Hong L,Chen G.Segment-based stereo matching using graph cuts[C]//IEEE Computer Society Conference on Computer Vision and Pattern Recognition.Piscataway,N J,USA:IEEE,2004:74-81.
[4] Deng Y,Yang Q,Lin X Y,et al.Stereo correspondence with occlusion handling in a symmetric patch-based graph-cuts model[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2007,29(6):1068-1079.
[5] Kolmogorov V.Graph based algorithms for scene reconstruction from two or more views[D].Ithaca,NY,USA:Comell University,2003.
[6] Kolmogorov V,Zabih R.Computing visual correspondence with occlusions using graph cuts[C]//IEEE International Conference on Computer Vision.Piscataway,N J,USA:IEEE,2001:508-515.
[7] Greig D,Porteous B,Seheult A.Exact maximum a-posteriori estimation for binary images[J].Journal of the Royal Statistical Society,Series B,1989,51(2):271-279.
[8] Ford L R,Fulkerson D R.Flows in networks[M].USA:Princeton University Press,1962.
[9] Dinic E A.Algorithm for solution of a problem of maximum flow in networks with power estimation[J].Soviet Mathematics Doklady,1970,11:1277-1280.