基於改進最小生成樹架構與遮擋處理之非區域立體匹配演算法

A Non-Local Stereo Matching Algorithm Based on Improved Minimum Spanning Tree Structure and Occlusion Handling

謝正宏(Cheng-Hung Hsieh)

指導教授 ： 郭天穎

國立臺北科技大學/電資學院/電機工程系所/碩士(2014年)

摘要

本論文提出一個基於非區域(non-local)立體匹配之演算法來計算視差圖。非區域方法主要特色在於使用一樹狀結構來傳遞加權過的匹配成本，使其可有全域(global)方法的準確度與區域(local)方法的速度。
本論文定義一個全新的最小生成樹之生成方法。此方法改用8鄰網格建樹法，並藉由左右眼匹配成本資訊提供一信心值，來改變最小生成樹之建樹順序。相較於原始非區域演算法論文，提出方法所估算的視差圖在Middlebury標準測試平台上，錯誤率從5.48%降至4.85%。在視差圖精煉(disparity refinement)部分，本論文也提出多次左右檢查法來有效找出遮擋點以精煉視差圖，錯誤率可從4.85%再降至4.80%。在運算時間不超過原始非區域演算法論文1.24倍的情況下，我們能提供較準確的視差圖。

關鍵字

視差計算 ； 立體匹配 ； 非區域立體匹配 ； 最小生成樹架構 ； 深度估測

並列摘要

The work proposed a non-local-based stereo matching algorithm for disparity computation. The feature of non-local stereo matching method is to utilize a tree structure to propagate weighted matching cost, and thus it can achieve both the merits of accuracy and speed in global and local methods respectively.
In this work, a new minimum spanning tree forming method is proposed. Our method adopts 8-connected rather than 4-connected grid to construct the minimum spanning tree, and we also exploit the stereo matching cost as the confidence value, to prioritize tree built-up order from the increased connection possibilities of 8-connected grid. Compared to the original non-local stereo matching method in literature, our proposed tree built-up method significantly improves the error rate of disparity from 5.48 to 4.85 by the Middlebury benchmark. This work also proposed a multiple left-right consistency checking method to identify occlusion points efficiently for further refining their disparity. After applying it, our error rate is further decreased from 4.85 to 4.80, while the overall complexity of ours is only 1.24 times of the original non-local method.

並列關鍵字

Disparity computation ； stereo matching ； non-local stereo matching ； minimum spanning tree structure ； depth estimation

參考文獻

[1]C. Fehn, “Depth-image-based Rendering (DIBR)”, Compression, and Transmission for A New Approach on 3D-TV,” Proc. of the SPIE, vol. 5291, pp. 93-104, 2004.

[4]Y. Chen, M. M. Hannuksela, T. Suzuki, and S. Hattori, “Overview of theMVC+D 3D video coding standard,” J. Vis. Commun. Image Represent. Apr. 2013..

[6]A. Saxena, S. H. Chung, and A. Y. Ng, “3-D Depth Reconstruction from a Single Still Image,” Int. J. of Computer Vision, 2007.

[7]Qing-xiong Yang, “A non-local cost aggregation method for stereo matching” IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2012, pp. 1402 - 1409, June 2012.

[8]Y. Boykov, O. Veksler, R. Zabih, “Fast Approximate Energy Minimization via Graph Cuts,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 23, pp. 1222-1239, 2001.