立體匹配是一種利用雙鏡頭獲取影像並產生景深資訊的演算法。雖然有越來越多的研究致力於景深的最佳化，但卻鮮少有文獻提出能以超大型積體電路實現之低複雜度立體匹配演算法。在許多基於視窗匹配的演算法中，通常需要很大的視窗才能得到較佳的景深圖，然而其硬體成本也隨之提高，因此本篇論文考量到硬體限制採用小視窗匹配運算，並引進景深可靠程度的概念輔助我們找出可靠的景深資訊，並在低複雜度的情況下實現還能擁有一定品質的景深圖。
為了降低硬體實現的成本，在平行化的硬體架構中採用了低面積記憶體合併技術。此外，在平行運算處理中藉由共用運算電路大量降低73%的處理單元，讓整體執行時間與硬體成本均有顯著的降低，從合成結果可以發現記憶體的合併降低了32.7%的記憶體成本、邏輯閘總數為183k、記憶體大小為6.72 kB且操作頻率可達至166MHz，支援每秒71張畫面而解析度為480×540且視差搜索範圍為56像素點之圖片。

Stereo matching algorithms attempt to generate the depth information from stereo image pairs captured by dual or multiple cameras. Although many advances have been made for the optimization of the stereo matching quality, there are only few researches addressing the development of low complexity flow for very large scale integration (VLSI) realization. In this thesis, we proposed a low complexity stereo matching algorithm and its efficient hardware implementation. To obtain better quality, the window size should be large enough in many window-based stereo matching algorithms while large window inducing the hardware cost dramatically. Instead of adopting large window, small matching window combined with depth reliability is utilized in our algorithm which achieves good depth quality and low hardware complexity.
Several hardware cost reduction methodologies are also proposed in this thesis, an area efficient memory-merging technique is applied for 32.7% storage area saving. Moreover, processing elements (PEs) consist common computations are shared in the parallel architecture which acquiring 73% PE cost reduction. Synthesis results report the gate-count and memory size is 183k and 6.72kB, respectively. The operation frequency is 166 MHz. and can support 71fps for image size of 480×540 (2×2 downsampling of Full HD side-by-side 3D format) with 56 disparity range levels.

[1] M. Z. Brown, D. Burschka, and G. D. Hager, “Advances in computational stereo,” IEEE Tran. Pattern Analysis and Machine Intelligence, vol. 25, no.8, pp. 993-1008, Aug. 2003.
[2] T. H. Cormen, C. E. Leiserson, and R. L. Rivest, “Introduction to Algorithms,” New York: McGraw-Hill, 1990.
[3] Y. Y. Boykov and M. Jolly, “Interactive graph cuts for optimal boundary & region segmentation of objects in N-D images,” in Proc. Int. Conf. Computer Vision, pp. 105-112, Jul. 2001.
[4] J. Sun, N. N. Zheng, and H. Y. Shum, “Stereo matching using belief propagation,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 25, pp. 787-800, Jul. 2003.
[5] D. Scharstein, R. Szeliski, and R. Zabih, “A taxonomy and evaluation of dense two-frame stereo correspondence algorithms,” Int. J. Computer Vision, vol. 47, no. 1, pp. 7-42, Apr. 2002.
[6] Y. Ohta and T. Kanade, “Stereo by intra- and inter-scanline search using dynamic programming,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 7, pp. 139-154, Mar. 1985.
[7] I. J. Cox, S. L. Hingorani, S. B. Rao, and B. M. Maggs, “A maximum likelihood stereo algorithm,” Computer Vision and Image Understanding, vol. 63, pp. 542-567, 1996.
[8] S. S. Intille and A. F. Bobick, “Incorporating intensity edges in the recovery of occlusion regions,” in Proc. Int. Conf. Pattern Recognition, vol. 1, pp. 674-677, Oct. 1994.
[9] O. Veksler, “Stereo correspondence with compact windows via minimum ratio cycle,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 24, no. 12, pp. 1654-1660, Dec. 2002.
[10] R. K. Gupta and S. Y. Cho, “Real-time stereo matching using adaptive binary window,” in Proc. Int. Symposium 3D Data Processing Visualization and Transmission, vol. 1, pp. 1-8, 2010.
[11] K. J. Yoon and I. S. Kweon, “Adaptive support-weight approach for correspondence search,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 28, pp. 650-656, Apr. 2006.
[12] R. Zabih and J. Woodfill, “Non-parametric local transforms for computing visual correspondence,” in Proc. Third European Conf. Computer Vision, pp. 150-158, May. 1994.
[13] P. Fua, “A parallel stereo algorithm that produces dense depth maps and preserves image features,” Machine Vision and Applications, vol. 6, pp. 35-49, 1993.
[14] N. Jacobson, “An online learning approach to occlusion boundary detection,” IEEE Trans. Image Processing, vol. 21, no.1, pp. 252-261, Jan. 2012.
[15] Y. Sugaya, “Stereo by integration of two algorithms with/without occlusion handling,” in Proc. Int. Conf. Pattern Recognition, vol. 1, pp. 109-113, Sep. 2000.
[16] 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. Symposium 3D Data Processing Visualization and Transmission, pp. 798-805, Jun. 2006.
[17] N.-C. Chang , T.-H. Tsai , B.-H. Hsu , Y.-C. Chen and T.-S. Chang, "Algorithm and architecture of disparity estimation with mini-census adaptive support weight," IEEE Trans. Circuits Syst. Video Technol., vol. 20, pp. 792-805, Jun. 2010.
[18] M. Hariyama et al., “1000 frame-sec stereo matching VLSI processor with adaptive window-size control,” in Proc. Conf. Asian Solid-State Circuits, pp. 123-126, Nov. 2006.
[19] M. Hariyama, “VLSI processor for reliable stereo matching based on window-parallel logic-in-memory architecture,” in Proc. IEEE Conf. Symposium on VLSI Circuit Digest of Technical Paper, pp. 166-169, Jun. 2004.
[20] S. K. Han, S. Woo, M. H. Jeong and B. J. You, “Improved-quality real-time stereo vision processor,” in Proc. 22nd Int. Conf. VLSI Design, pp. 287-292, Jan. 2009.
[21] M. Tomasi et al., “Real-time architecture for a robust multi-scale stereo engine on FPGA,” IEEE Trans. Very Large Scale Integration Systems, vol. 20, no.12, pp. 2208-2219, Dec. 2012.
[22] A. Darabiha, W. MacLean, and J. Rose, “Reconfigurable hardware implementation of a phase-correlation stereo algorithm,” Machine Vision and Applications, vol. 17, no.2, 116-132, Apr. 2006.
[23] C. Ttofis, “Towards accurate hardware stereo correspondence: areal-time FPGA implementation of a segmentation-based adaptive support weight algorithm,” in Proc. Design Automation and Test in Europe Conf. and Exhibition (DATE), pp. 703-708, Mar. 2012.
[24] Middlebury Stereo Datasets. [Online]. Avaliable: http://vision.middlebury.edu/stereo/data/
[25] Epipolar geometry: http://en.wikipedia.org/wiki/Epipolar_geometry