三維立體影像的運用中，如何得到準確的深度圖是個關鍵，區域性立體匹配(local stereo-matching)是解決此問題的方法之一。本論文旨在降低區域性立體匹配的運算複雜度，並估算初始的視差搜尋區間以及適應性區塊的最大面積。進行區域性的比對動作時(area-based matching)，估算適應性區塊的形狀有許多部分都在進行重覆的運算。本論文將這些重複的運算量去除後，估算適應性區塊的形狀的運算時間減少了大約一半。初始的視差搜尋區間(disparity search range)以及比對區塊的大小都會對區域性立體匹配(area-based local stereo matching)帶來很大的影響。所設計的演算法利用視差的統計特性估算出初始的視差搜尋區間，並利用偽黃金深度圖估算出適應性區塊的最大面積。這可避免搜尋區間或適應性區塊的最大面積設定過大所帶來的時間上的損失。

Depth map are crucial to 3D video, local stereo-matching is one of the methods to obtain the depth map. This thesis proposes a fast algorithm to reduce the computation complexity of local stereo-matching, estimates the initial disparity search range and the maximum area of the block size. There are a lot of repetition calculations when finding the shape of the adaptive blocks, this thesis avoids those repeat steps so the complexity is lowered greatly. Area-based local stereo matching is sensitive to the initial disparity search range and the adaptive block size. These design estimate the initial disparity search range by the statistic feature of the disparities and find out the maximum area of the adaptive block by using the pseudo golden depth map. Adequate disparity search range and maximum area of the adaptive block reduce the times wasted by wide search range and area. The purpose of area-based local stereo matching is measuring the depth of left image and right image, area-based local stereo matching is well suits to the real-time application.

[1] B. Cyganek and J. P. Siebert, 3D Computer Vision Techniques and Algorithms. New York : Wiley. 2009, pp. 9-10.
[2] M. Z. Brown, D. Burschka, and G. D. Hager, “Advances in computational stereo,” IEEE Trans. Pattern Anal. Mach. Intell., vol. 25, pp. 993-1008, Aug. 2003.
[3] R. Hartley and A. Zisserman, Multiple View Geometry in Computer Vision. Cambridge, U.K.: Cambridge Univ. Press, 2000.
[4] A. Donate, X. Liu, and E. G. Collins, “Efficient path-based stereo matching with subpixel accuracy,” IEEE Trans. Syst. Man Cybern. Part B-Cybern., vol. 41, pp. 183-194, Feb. 2011.
[5] J. Lu, G. Lafruit, and F. Catthoor, “Anisotropic local high-confidence voting for accurate stereo correspondence,” in Proc. SPIE-IS&T Electron. Imaging, Jan. 2008, pp. 605822-1-605822-10.
[6] 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. 2002.
[7] P. Mordohai, “The self-aware matching measure for stereo,” in Proc. IEEE ICCV, Sept. 2009, pp. 1841-1848.
[8] K. Zhang, J. Lu, G. Lafruit, R. Lauwereins and L.V. Gool, “Accurate and efficient stereo matching with robust piecewise voting,” in Proc. IEEE ICME, July 2009, pp. 93-96.
[9] H. C. Shih and H. F. Hsiao, “A depth refinement algorithm for multi-view video synthesis,” in Proc. IEEE ICASSP, Mar. 2010, pp.742-746.
[10] Middlebury stereo vision research page, [Online] Available: http://vision.middlebury.edu/stereo/eval/.
[11] O. Veksler, “Fast variable window for stereo correspondence using integral images,” in Proc. IEEE CVPR, June 2003, pp. 556-561.
[12] A. Fusiello, V. Roberto, and E. Trucco, “Efficient stereo with multiple windowing,” in Proc. IEEE CVPR, June 1997, pp.858-863.
[13] S. B. Kang, R. Szeliski, and J. Chai, “Handling occlusions in dense multi-view stereo,” in Proc. IEEE CVPR, Apr. 2001, pp. 103-110.
[14] K. Zhang, J. Lu, and G. Lafruit, “Cross-based local stereo matching using orthogonal integral images,” IEEE Trans. Circuits Syst. Video Technol., vol. 19, pp. 1073-1079, Sept. 2009.
[15] F. Tombari, S. Mattoccia, and L. D. Stefano, “Segmentation based adaptive support for accurate stereo correspondence,” in Proc. PSIVT, Dec. 2007, pp. 427-438.
[16] F. Tombari, S. Mattoccia, L. D. Stefano, and E. Addimanda, “Classification and evaluation of cost aggregation methods for stereo correspondence,” in Proc. IEEE CVPR, June 2008, pp. 1-8.
[17] C. Harris and M. Stephens, “A combined corner and edge detector,” in Proc. 4th Alvey Vis. Conf., Aug. 1988, pp. 147-151.
[18] J. Canny, “A computational approach to edge detection,” IEEE Trans. Pattern Anal. Mach. Intell., vol. PAMI-8, pp. 679-698, Nov. 1986.
[19] D. G. Lowe, “Object recognition from local scale-invariant features,” in Proc. IEEE ICCV, June 1999, pp. 1150-1157.
[20] Y. Lin and X. Fang, “A stereo matching method based on chain code vector,” in Proc. IEEE WCSE, Oct. 2009, pp. 372-375.
[21] M. Gerrits and P. Bekaert, “Local stereo matching with segmentation based outlier rejection,” in Proc. IEEE CRV, June 2006, pp. 66-72.
[22] 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, Oct. 2010.
[23] M. Kuhn, S. Moser, O. Isler, F. K. Gurkaynak, A. Burg, N. Felber, H. Kaeslin, and W. Fichtner, “Efficient ASIC implementation of a real time depth mapping stereo vision system,” in Proc. IEEE MWSCAS, Dec. 2003, pp. 1478-1481.
[24] J. I. Woodfill, G. Gordon, and R. Buck, “Tyzx DeepSea high speed stereo vision system,” in Proc. IEEE CVPRW, June 2004, pp. 41-45.
[25] R. C. T. Lee, S. S. Tseng, R. C. Chang, and Y. T. Tsai, Introduction to the Design and Analysis of Algorithms. New York : McGraw-Hill. 2008.
[26] Z. Zhao, J. Katupitiya, and J. Ward, “Global correlation based ground plane estimation using V-disparity image,” in Proc. IEEE ROBOT , Apr. 2007, pp. 529-534.
[27] D. Scharstein and R. Szeliski, “A taxonomy and evaluation of dense two-frame stereo correspondence algorithms,” Int. J. Comput. Vis., vol. 47, pp. 7-42, May 2002.