圖形切割方法常被運用於解決立體匹配的問題。它將匹配問題轉換至對全域能量函數之最小化。雖然在準確率上提供顯著的改善，但計算成本也相對提高。在本論文中，我們提出一個階層式二分視差架構將透過對視差範圍做迭代式二分法來增進圖形切割之效率。在此方法中，影像像素被高效率之圖形切割粗分為前景層和背景層。其餘，在兩個生成層中的像素將繼續透過二分圖形切割法來進行像素分群，而整個視差估測過程可以被階層式地建構。此外，在精進階段，對產生之視差圖再提出不可靠前景邊界之處理。最後，所提出的方法基於Middlebury 資料集來進行評估，並且會於其他近期被提出之方法來進行比較。而結果顯示，所提出的方法能有效率地提供準確的視差圖。

Graph cuts techniques have been widely used to solve the stereo matching problem. It transforms the matching problem to the minimization of the global energy function. Although it provides a significant improvement in accuracy, the computational cost is relatively high. In this thesis, we propose a hierarchical bilateral disparity structure (HBDS) to improve the efficiency of graph cuts through iterative bipartitions of disparity ranges. In this approach, the image pixels are coarsely separated into the foreground layer and the background layer by the efficient graph cuts. The rest pixels of two generated layers will continue to be separated by the bilateral graph cuts and the whole process of disparity estimation can be constructed hierarchically. In addition, a refinement stage is proposed to handle the unreliable boundaries of the foreground objects in the generated disparity map. The proposed method is evaluated using the benchmark Middlebury dataset and compared with several recently proposed methods. The results show that the proposed method can provide accurate disparity map efficiently.

[1] D. Scharstein and R. Szeliski, “A Taxonomy and Evaluation of Dense Two-Frame Stereo Correspondence Algorithms”, International Journal of Computer Vision, vol. 47, no. 1, pp. 7-42, 2002.
[2] O. Veksler, “Fast Variable Window for Stereo Correspondence using Integral Images,” Proc. IEEE Conf. Computer Vision and Pattern Recognition, vol. 1, pp. 556-561, 2003.
[3] T. Kanade and M. Okutomi, “A stereo matching algorithm with an adaptive window: theory and experiment”, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 16, no. 9, pp. 920–932, 1994.
[4] Y. Ohta and T. Kanade, “Stereo by intra- and inter- scanline search using dynamic programming”, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 7, no. 2, pp. 139–154, 1985.
[5] O. Veksler, “Stereo correspondence by dynamic programming on a tree”, IEEE Conference on Computer Vision and Pattern Recognition, vol. 2, pp. 384-390, 2005.
[6] Y. Boykov, O. Veksler, and R. Zabih, “Fast Approximate Energy Minimization via Graph Cuts”, IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 23, no. 11, 2001.
[7] Y. Boykov and V. Kolmogorov, “An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision”, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 26, no. 9, pp. 1124–1137, 2004.
[8] V. Kolmogorov and R. Zabih, “What energy functions can be minimized via graph cuts?”, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 26, no. 2, pp. 147-159, 2004.
[9] V. Kolmogorov and R. Zabih, “Computing Visual Correspondence with Occlusions using Graph Cuts”, In IEEE International Conference on Computer Vision, vol. 2, pp. 508–515, 2001.
[10] Sun, J., Zheng, N.N., and Shum, H.Y., “Stereo matching using belief propagation”, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 25, no. 7, pp. 787–800, 2003.
[11] P. F. Felzenszwalb and D. P. Huttenlocher, “Efficient Belief Propagation for Early Vision”, IEEE Conference on Computer Vision and Pattern Recognition, vol. 1, pp. 261-268, 2004.
[12] M. F. Tappen and W. T. Freeman, “Comparison of graph cuts with belief propagation for stereo, using identical MRF parameters”, In IEEE International Conference on Computer Vision, vol. 2, pp. 900–906, 2003.
[13] L. Hong and G. Chen, “Segment-based stereo matching using graph cuts”, IEEE Conference on Computer Vision and Pattern Recognition, vol. 1, pp. 74-81, 2004.
[14] W. Daolei and K. Bin Lim, “Obtaining depth map from segment-based stereo matching using graph cuts”, Journal of Visual Communication and Image Representation, vol. 22, no. 4, pp. 325-331, 2011.
[15] H. Lombaert, Y. Sun, L. Grady, and C. Xu., “A Multilevel Banded Graph Cuts Method for Fast Image Segmentation”, In IEEE Int. Conf. on Comp. Vision, pp. 259–265, 2005.
[16] A. Zureiki, M. Devy, and R. Chatila, “Stereo matcing using reduced graph cuts,” In International Conference on Image Processing, 2007.
[17] Collins. T, “Graph Cut Matching In Computer Vision”, University of Edinburgh, February 2004.
[18] S. Birchfield, C. Tomasi, “Depth discontinuities by pixel-to-pixel stereo”, In IEEE Int. Conf. on Comp. Vision, pp. 1073–1080, 1998.
[19] H. Mayer, “Analysis of means to improve cooperative disparity estimation”, In ISPRS Conference on Photogrammetric Image Analysis, vol. 34, pp. 25-31, 2003.
[20] N. Otsu, “A threshold selection method from gray-level histograms”, IEEE Transactions on Systems, Man and Cybernetics, vol. 9, pp. 62C66, 1979.
[21] XY. Xu, SZ. Xu, LH. Jin, and Enmin. Song, “Characteristic analysis of Otsu threshold and its applications”, “Pattern Recognition Letters”, vol. 32, pp. 956-961, 2011.
[22] H. Ng., “Automatic thresholding for defect detection”, Pattern Recognition Letters, vol. 27, pp. 1644–1649, 2007.
[23] G. Blanchet, A. Buades, B. Coll, J. M. Morel and B. Rouge, “Fattening free block matching”, Journal of Mathematical Imaging and Vision, vol. 40, 2011.
[24] YS. Heo, KM. Lee, SU. Lee, “Robust stereo matching using adaptive normalized cross-correlation”, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 33, pp. 807-822, 2011.
[25] Gu, Z., Su, X.Y., Liu, Y.K., Zhang, Q.C., “Local stereo matching with adaptive support-weight, rank transform and disparity calibration”, Pattern Recognition Letters, vol. 29, pp. 1230–1235, 2008.
[26] K.-J. Yoon and I.-S. Kweon, “Adaptive support-weight approach for correspondence search”, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 28, pp. 650–656, 2006.
[27] P. Felzenszwalb and D. Huttenlocher, “Efficient graph-based image segmentation.” International Journal of Computer Vision, vol. 59, no. 2, pp. 167–181, 2004.
[28] Middlebury website, http://vision.middlebury.edu/stereo/