本論文提出一種快速立體匹配演算法，不同於傳統立體匹配方式需要處理圖中的每一個像素，本方法僅處理部分的像素，以此來節省大量的運算時間。以往的立體匹配技術需要耗費大量的運算資源，本論文藉由快速產生得粗略深度圖，找出邊界處並加以修正，並產生高品質的深度圖。
首先以跳躍搜尋之方式快速產生一張稀疏的深度圖，再經由簡單的左右填補，生成兩張粗略的深度圖，接著比較此兩張粗略深度圖，找出深度圖的邊緣區域，將此區域限制搜尋範圍，接著重做後並修正不一致區域，最後可產生精準的深度圖。在不同設定下最少可節省約74%之計算量，並能維持平均錯誤率在8%以下。
本論文也依照此演算法設計出一硬體架構，並以TSMC 0.18 μm製程合成，此硬體架構共需約3.97M個邏輯閘，當系統運作於40 MHz時，解析度434 × 383且深度搜尋範圍為20的圖片可達到每秒30張以上的處理速度。

In this thesis, a fast local stereo matching algorithm and its VLSI implementation are proposed. Unlike the traditional stereo matching methods which process all pixels in the image, the proposed algorithm only processed a part of the image to reduce the computation complexity.
The proposed algorithm generates a sparse depth map by a skip technology. For each image, this method estimates the skip region in two directions and generates two rough depth maps. We compare these two rough depth maps to find the edge of depth map. Then, re-compute the depth information of these regions with the restricted search range. Final, we adopt the left right consistency check to fetch the mismatch regions and refine them by neighboring pixels to generate an accurate depth map. Therefore, the proposed method can reduce at least 74% computation with different settings. The error rates of the depth maps are less than 8%. The VLSI implementation of the proposed algorithm is also proposed. The designed hardware supports the disparity range up to 20 levels and can perform over 30 frames per second each image pair with the resolution of 434 × 383 in 40 MHz.

[1] C. Fehn, “Depth-image-based rendering (DIBR), compression, and transmission for a new approach on 3D-TV,” in Proc. SPIE Conf. Electron. Imaging, May 2004, pp. 93–104.
[2] 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.
[3] 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.
[4] I. P. Howard and B. J. Rogers, Binocular Vision and Stereopsis. New York: Oxford University Press, 1995.
[5] 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.
[6] 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.
[7] O. Veksler, “Stereo correspondence with compact windows via minimum ratio cycle,” IEEE Trans. Pattern Anal. Mach. Intell., vol. 24, pp. 1654–1660, Dec. 2002.
[8] 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.
[9] O. Veksler, “Fast variable window for stereo correspondence using integral images,” in Proc. IEEE Conf. Comput. Vis. Pattern Recogn., June 2003, pp. 556–561.
[10] Y. Zhang and C. Kambhamettu, “Stereo matching with segmentation-based cooperation,” in Proc. Eur. Conf. Comput. Vis., May 2002, pp. 556–571.
[11] H. S. Lim and H. Park, “A dense disparity estimation method using color segmentation and energy minimization,” in Proc. IEEE Int. Conf. Image Process., Oct. 2006, pp. 1033–1036.
[12] M. Gong and Y. H. Yanh, “Fast stereo matching using reliability-based dynamic programming and consistency constraints,” in Proc. IEEE Int. Conf. Comput. Vis., Oct. 2003, pp. 610–617.
[13] K. Zhang, J. Lu, and G. Lafruit, “Scalable stereo matching with locally adaptive polygon approximation,” in Proc. IEEE Int. Conf. Image Process., Oct. 2008, pp. 313–316.
[14] 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. Vis. Pattern Recogn., June 2005, pp. 1075–1082.
[15] Y. Wei and L. Quan, “Region-based progressive stereo matching,” in Proc. IEEE Conf. Comput. Vis. Pattern Recogn., June 2004, pp. 106 –113.
[16] S. Xun, M. Xing, J. Shaohui, Z. Mingcai, and W. Haitao, “Stereo matching with reliable disparity propagation,” in Proc. IEEE Int. Conf. 3D Imaging, Model., Process., Vis. Transm., May 2011, pp. 132–139.
[17] A. F. Bobick and S. S. Intille, “Large occlusion stereo,” Int. J. Comput. Vis., vol. 33, pp. 181–200, Sept. 1999.
[18] 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.
[19] P. F. Felzenszwalb and D. R. Huttenlocher, “Efficient belief propagation for early vision,” in Proc. IEEE Conf. Comput. Vis. Pattern Recogn, June 2004, pp. 261–268.
[20] K. Muhlmann, D. Maier, J. Hesser, and R. Manner, “Calculating dense disparity maps from color stereo images, an efficient implementation,” Int. J. Comput. Vis., vol.47, pp. 79–88, Dec. 2002.
[21] A. S. Ogale and Y. Aloimonos, “Shape and the stereo correspondence problem.” Int. J. Com. Vis., vol. 65, pp. 147–162, Dec. 2005.
[22] C. Georgoulas and I. Andreadis, “A real-time occlusion aware hardware structure for disparity map computation,” in Proc. Conf. Image Anal. Process, June 2009, pp. 721–730.
[23] K. Ambrosch, M. Humenberger, W. Kubinger, and A. Steininger, “A SAD-based stereo matching using FPGAs,” in Proc. Conf. Embed. Comput. Vis., Dec. 2009, pp. 121–138.
[24] 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.
[25] 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.
[26] K. Ambrosch and W. Kubinger, “Accurate hardware-based stereo vision,” Comput. Vis. Image Und., vol. 115, pp. 1303–1316, Feb. 2011.
[27] 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. IEEE Conf. Design, Autom. Test., Mar. 2012, pp. 703–708.
[28] P. L. Chu, “Stereo matching algorithm with fast disparity propagation under homogeneous texture detection and its VLSI implementation,” M.S. thesis, National Cheng Kung University, Taiwan, Jul. 2012.
[29] L. Wang, M. Liao, M. Gong, R. Yang, and D. Nister “High-quality real-time stereo using adaptive cost aggregation and dynamic programming,” in Proc. Int. Symp. 3D Data Process Vis. Transm., June 2006, pp. 798–805.
[30] 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. IEEE Conf. Emerging Signal Process. Appl., Jan. 2012, pp. 9–12.
[31] C. C. Tien, “A fast coarse-to-fine stereo matching algorithm and its VLSI implementation,” M.S. thesis, National Cheng Kung University, Taiwan, July 2013.
[32] C. O. Park, J. H. Heo, D. H. Lee, and J. D. Cho, “Dynamic search range using sparse disparity map for fast stereo matching,” in Proc IEEE Int. Symp. Broadband Multimedia Syst. Broadcast., June 2012, pp. 1–4.
[33] 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.
[34] D. Scharstein and R. Szeliski, “High-accuracy stereo depth maps using structured light,” in Proc. IEEE Conf. Comput. Vis. Pattern Recogn., June 2003, pp. 195–202.
[35] D. Scharstein and C. Pal, “Learning conditional random fields for stereo,” in Proc. IEEE Conf. Comput. Vision and Pattern Recogn., June 2007, pp. 1–8.
[36] H. Hirschmuller and D. Scharstein, “Evaluation of cost functions for stereo matching,” in Proc. IEEE Comput. Vision and Pattern Recogn., June 2007, pp. 1–8.
[37] Middlebury Stereo Vision Page [Online]. Availale: http://vision.middlebury.edu/stereo
[38] J. Kowalczuk, E. Psota, and L. Perez, “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.
[39] C. Ttofis and T. Teocharides, “High-quality real-time hardware stereo matching based on guided image filtering,” in Proc. IEEE Des., Autom. Test Eur. Conf. Exhibition, Mar. 2014, pp. 1–6.