簡易檢索 / 詳目顯示

回結果列表
研究生： 田峻萁
Tien, Chun-Chih
論文名稱： 快速階層式立體匹配演算法及其VLSI實現
A Fast Coarse-to-Fine Stereo Matching Algorithm and Its VLSI Implementation
指導教授： 劉濱達
Liu, Bin-Da
楊家輝
Yang, Jar-Ferr
學位類別： 碩士
Master
系所名稱： 電機資訊學院 - 電機工程學系
Department of Electrical Engineering
論文出版年： 2013
畢業學年度： 101
語文別： 英文
論文頁數： 110
中文關鍵詞： 3D 、立體匹配 、深度圖 、深度不連續 、視差
外文關鍵詞： 3D, Stereo matching, depth map, depth discontinuous, disparity
相關次數： 點閱：102  下載：0 
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報

    • 本論文提出快速階層式立體匹配演算法，捨棄傳統立體匹配每一像素皆進行處理的方式，而採用階層式之快速演算法，以節省大量的運算。以往技術在進行立體匹配時，需要大量的運算資源，因此，本論文提出了以深度不連續區域修正基礎之跳躍式立體匹配演算法，依不同設定而降低85~92%的計算量，且能維持深度圖之平均錯誤率在10%內。
    本論文之階層式演算法先快速的產生一張粗略深度圖，並透過該深度圖上既有資訊做為修正條件，加以重做、修正、及調整。本演算法可以巨觀地來分成粗略深度圖產生及深度圖修正調整兩個主要部分，最後產生我們所求之深度圖。透過本論文之演算法計算，可快速且精準地產生的深度圖。
    除此之外，本論文依可靠的演算法設計，提出一特別之硬體架構，經過模擬驗證後，其結果也與原始演算法相當接近。此硬體架構共需約80K個邏輯閘，當運作於100MHz時，處理解析度為450 × 375且深度搜尋範圍為60的圖片時，可達到每秒處理60張的速度。

    In this thesis, a fast stereo matching algorithm and its VLSI implementation are proposed. The traditional stereo matching methods need a lot of computation time and are not suitable for real time applications. Therefore, a fast coarse-to-fine stereo matching algorithm is proposed such that it can reduce about 85%~92% computation time with different settings while it only suffers less than 10% error rate in depth map quality.
    The proposed algorithm mainly can be divided into two, the rough depth map generation and the fast depth map refinement, stages. The rough depth map is classified into several cases for the refinements to get the fine depth map. By two stages design, we can generate the depth map fast and accurately.
    Besides, the VLSI implementation of the proposed algorithm is also proposed. Synthesis result shows the number of implemented gate counts is about 80k and the maximum operation frequency can reach 100MHz. The designed hardware supports the disparity range up to 64 levels and it can perform over 50 frames per second on an image pair with the resolution of 450 × 375.

    Abstract (Chinese) i Abstract (English) iii Acknowledgement v Table of Contents vii List of Figures ix List of Tables xiii Chapter 1 Introduction 1 1.1 Motivation 1 1.2 Organization of the Thesis 3 Chapter 2 Basic Concepts of Stereo Matching 5 2.1 Introduction Basic Concept of Stereopsis 5 2.2 Fundamental Theorem of Stereo Matching 8 2.3 Introduction of Stereo Matching 10 2.3.1 Cost initialization 13 2.3.2 Cost aggregation 13 2.3.3 Disparity optimization 15 2.3.4 Disparity refinement 17 2.4 Related Works 17 2.4.1 Global stereo matching algorithm 18 2.4.2 Local stereo matching algorithm 19 2.4.3 Adaptive support weight (ASW) 20 2.4.4 Hardware implementation algorithms 23 Chapter 3 The Proposed Stereo Matching Algorithm 25 3.1 Overview of Proposed Algorithm 26 3.2 Rough Depth Map Generation Stage 28 3.2.1 Modified adaptive support weight in power of 2 28 3.2.2 Skip stereo matching method 40 3.2.3 Disparity estimation for skip pixels 45 3.3 Depth Map Re-computation Stage 50 3.3.1 Discontinuous region detection method 50 3.3.2 Disparity search range restriction 55 3.3.3 Overall process of depth map re-computation 59 3.4 Disparity Refinement 61 3.5 VLSI Implementation 66 3.5.1 Introduction of the design methodology 67 3.5.2 Architecture of VLSI implementation 69 3.5.3 Design of the modules 70 Chapter 4 Simulation Results and Comparisons 73 4.1 Simulation Environment Settings 73 4.2 Parameter Settings and Comparison in Proposed Algorithm 78 4.2.1 Control parameters selection of modified adaptive support 79 4.2.2 Comparison of different jump ranges and expansion window sizes 81 4.2.3 Comparison of different window sizes 87 4.3 Simulation Results for Proposed Coarse-to-Fine Algorithm 89 4.4 Simulation Results for VLSI Implementation 95 Chapter 5 Conclusions and Future Work 101 5.1 Conclusions 101 5.2 Future Work 103 References 105

    [1] J. Ramesh, K. Rangachar, and B. G. Schunck. Machine Vision. Vol. 5. New York: McGraw-Hill, 1995, pp. 1¬–24.
    [2] C. Fehn, K. Hopf, and B. Quante, “Key technologies for an advanced 3D TV system,” in Proc. SPIE Three-Dimensional TV, Video, and Display Ⅲ, Oct. 2004, pp. 66–80.
    [3] C. Fehn, R. D. L. Barre, and S. Pastoor, “Interactive 3-DTV: concepts and key technologies,” Proc. IEEE, vol. 94, pp. 524–538, Mar. 2006.
    [4] D. Min, D. Kim, and K. Sohn, "2D/3D freeview video generation for 3DTV system." Journal of Signal Process : Image communication, vol. 24, pp. 31–48, Jan. 2009.
    [5] C. Fehn, "Depth-image-based rendering (DIBR), compression, and transmission for a new approach on 3D-TV," in Proc. SPIE Conf. Electron. Imaging, 2004, pp. 93–104.
    [6] L. H. Wang, X. J. Huang, M. Xi, D. X. Li, and M. Zhang, “An asymmetric edge adaptive filter for depth generation and hole filling in 3DTV,” IEEE Trans. Broadcast., vol. 56, pp. 425–431, Sept. 2010.
    [7] K. J. yoon and I. S. Kweon, “Adaptive support-weight approach for correspondence search,” IEEE Trans. Pattern Anal. Mach. Intell., vol. 28, pp. 650–656, Apr. 2006.
    [8] I. P. Howard, and B. J. Rogers. Binocular Vision and Stereopsis. New York: Oxford University Press, 1995, pp. 1–13.
    [9] T. Kanade and M. Okutomi, “A stereo matching algorithm with an adaptive window: theory and experiment,” IEEE Trans. Pattern Anal. Mach. Intell., vol. 16, pp. 920–932, Sept. 1994.
    [10] Y. Boykov, O. Veksler, and R. Zabih, “A variable window approach to early vision,” IEEE Trans. Pattern Anal. Mach. Intell., vol. 20, pp. 1283–1294, Dec. 1998.
    [11] O. Veksler, “Stereo correspondence with compact windows via minimum ratio cycle,” IEEE Trans. Pattern Anal. Mach. Intell., vol. 24, pp. 1654–1660, Dec. 2002.
    [12] Z. Ke, L. Jiangbo, and G. Lafruit, “Cross-based local stereo matching using orthogonal integral images,” IEEE Trans. Circuits Syst. Video Technol., vol. 19, pp. 1073–1079, July 2009.
    [13] A. Fusiello, V.Roberto, and E. Trucco, "Efficient stereo with multiple windowing," in Proc. IEEE Conf. Comput. Vision Pattern Recogni., pages 858–863, June 1997.
    [14] O. Veksler, “Fast variable window for stereo correspondence using integral images,” in Proc. IEEE Conf. on Computer Vision and Pattern Recognition, pp. 556–561, 2003.
    [15] Y. Zhang and C. Kambhamettu, “Stereo matching with segmentation-based cooperation,” in Proc. Eur. Conf. Comput. Vision, Copenhagen, Denmark, May 2002, pp. 556–571.
    [16] H. S. Lim and H. Park, “A dense disparity estimation method using color segmentation and energy minimization,” in Proc. IEEE Int. Conf. Image Process., 2006, pp. 1033–1036.
    [17] M. Gong and Y. H. Yanh, “Fast stereo matching using reliability-based dynamic programming and consistency constraints,” in Proc. of the Ninth IEEE Int. Conf. Comput. Vision, vol.1, pp.610–617, 2003.
    [18] K. Zhang, J. Lu, and G. Lafruit, "Scalable stereo matching with locally adaptive polygon approximation." in Proc. IEEE Int. Conf. Image Process., pp.313–316, 2008.
    [19] J. C. Kim, K. M. LEE, B. T. Choi, and S. U. Lee, “A dense stereo matching using two-pass dynamic programming with generalized ground control points,” in Proc. IEEE Conf. Comput. Vision Pattern Recogni., pp. 1075–1082, June 2005.
    [20] Y. Wei and L. Quan, “Region-based progressive stereo matching,” in Proc. IEEE Conf. Compute. Vision Pattern Recogni., 2004, pp. I-106 – I-113.
    [21] S. Xun, M. Xing, J. Shaohui, Z. Mingcai, and W. Haitao, “Stereo matching with reliable disparity propagation,” in Proc. IEEE Int. Conf. 3D Imaging, Modeling, Processing, Visualization and Transmission, May 2011, pp. 132–139.
    [22] A. F. Bobick and S. S. Intille, “Large occlusion stereo,” Inte. J. Comput. Vision, vol. 33, pp. 181–200, Sept. 1999.
    [23] Y. Boykov, O. Veksler, and R. Zabih, “Fast approximate energy minimization via graph cuts,” IEEE Trans. Pattern Anal. Mach. Intell., vol. 23, pp. 1222–1239, Aug. 2001.
    [24] P. F. Felzenszwalb and D. R. Huttenlocher, “Efficient belief propagation for early vision,” in Proc. IEEE Conf. Comput. Vision Pattern Recogni., June 2004, pp. I-261–I-268.
    [25] K. Muhlmann, D. Maier, J. Hesser, and R. Manner, "Calculating dense disparity maps from color stereo images, an efficient implementation." Int. J. of Comput. Vision, vol.47, pp. 79–88, 2002.
    [26] A. S. Ogale, and Y. Aloimonos, "Shape and the stereo correspondence problem." International Journal of Computer Vision, vol.65, pp.147–162, 2005.
    [27] C. Georgoulas and I. Andreadis, “A real-time occlusion aware hardware structure for disparity map computation,” in Proc. Conf. Image Anal. Process., Vietri sul Mare, Italy, June 2009, pp. 721–730.
    [28] K. Ambrosch, M. Humenberger, W. Kubinger, and A. Steininger, “A SAD-based stereo matching using FPGAs,” in Proc. Conf. Embedded Comput. Vision, Kyoto, Japan, 2009, pp. 121–138.
    [29] A. Darabiha, J. MacLean, and J. Rose, “Reconfigurable hardware implementation of a phasecorrelation stereo algorithm,” Mach. Vision Appl., vol. 17, pp. 116–132, Apr. 2006.
    [30] X. Li, and J. Jia, "Stereo matching: An outlier confidence approach." in Proc. Eur. Conf. Comput. Vision, 2008, pp.775–787.
    [31] S. Jin, J. Cho, X. D. Pham, K. M. Lee, S-K. Park, M. Kim, and J. W. Jeon, “FPGA design and implementation of a real-time stereo vision system,” IEEE Trans. Circuits Syst. Video Technol., vol. 20, pp. 15–26, Jan. 2010.
    [32] K. Ambrosch and W. Kubinger, “Accurate hardware-based stereo vision,” Comput. Vis. Image Und., vol. 115, Feb. 2011, pp. 1303–1316.
    [33] C. Ttofis and T. Theocharides, "Towards accurate hardware stereo correspondence: A real-time FPGA implementation of a segmentation-based adaptive support weight algorithm.", in Proc. Conf. Design, Aut. Test in Eur., 2012, pp.703–708.
    [34] P. L. Chu, “Stereo Matching Algorithm with Fast Disparity Propagation Under Homogeneous Texture Detection and Its VLSI Implementation” M.S. thesis, Dept. Electrical Engineering, National Cheng Kung University, Taiwan, 2012.
    [35] L. Wang, M. Liao, M. Gong, R. Yang, and D. Nister "High-quality real-time stereo using adaptive cost aggregation and dynamic programming." in Int. Symposium on 3D Data Process Vis. Transmi., 2006, pp. 798–805.
    [36] K. H. Chen, C. H. Chen, C. H. Chang, and Y. C. Yang ,"Choose your own viewpoint: A high-quality/low-complexity free-viewpoint 3D visual system." in Proc. 2012 IEEE Conf. Emerging Signal Process. Applicati., pp.9–12.
    [37] D. Scharstein, R. Szeliski, and R. Zabih, “A taxonomy and evaluation of dense two-frame stereo correspondence algorithms,” in Proc. IEEE Stereo and Multi-Baseline Vision, Dec. 2001, pp. 131–140.
    [38] D. Scharstein and R. Szeliski, “High-accuracy stereo depth maps using structured light,” in Proc. IEEE Conf. Comput. Vision and Pattern Recogni., June 2003, pp. I-195–I-202.
    [39] D. Scharstein and C. Pal, “Learning conditional random fields for stereo,” in Proc. IEEE Conf. Comput. Vision and Pattern Recogni., June 2007, pp. 1–8.
    [40] H. Hirschmuller and D. Scharstein, “Evaluation of cost functions for stereo matching,” in Proc. IEEE Comput. Vision and Pattern Recogni., June 2007, pp. 1–8.
    [41] J. Kowalczuk, E. Psota, and L. Pérez. “Real-time stereo matching on CUDA using an iterative refinement method for adaptive support-weight correspondences,” IEEE Trans. Circuits Syst. Video Technol., vol. 23, pp. 94–104, Jan. 2013.
    [42] Middlebury Stereo Vision Page [Online]. Availale: http://vision.middlebury.edu/stereo

    無法下載圖示 校內：2018-08-27公開
    校外：不公開
    電子論文尚未授權公開，紙本請查館藏目錄
    QR CODE