立體視覺被廣泛的應用在移動式機器人、3D物體重建以及手勢辨識等，而立體視覺的基礎就是物體的深度，因此需要利用影像配對演算法來得到物體的距離，影像配對演算法，是利用兩張立體影像找尋每一點的對應點，將這些點的位移量轉換為物體的深度。在這篇論文中，我們將提出一個演算法，此演算法是利用邊緣偵測器來找尋特徵點，接著利用兩張立體影像的特徵點來計算這些點的深度，但是這樣只有稀疏的深度圖，因此我們利用影像內插演算法來將剩餘的點填補起來，首先，我們利用邊緣來找尋每個物體的連通區域，接著計算出每個物體適合的深度値，但是還是會有些許的邊緣點沒有配對到或填補到，所以我們使用最近點影像內插演算法來將還未被賦予値的點填入最相近的値，最後我們就可以獲得稠密的深度圖。比較其他的方法，我們所提出的方法可以迅速的得到完整的深度圖而且擁有較高的準確度，根據結果，我們所提出的方法所獲得的深度圖比較連續及準確。

Stereo vision is widely used in mobile robots, three dimensional reconstruction and hand gesture recognition, and depth information is a necessity for these systems. Therefore, stereo matching algorithms are proposed to obtain depth information, and use corresponding relationship between pixels from pair images in the same scene to extract the disparity information. In this thesis, we propose an edge-based sparse to dense disparity matching algorithm. Firstly, we use edge detector to find feature points in pair images and obtain disparity of these edge pixels. In order to obtain a dense disparity map, we use two interpolating methods to interpolate a sparse disparity map to a dense disparity map. We use edges to find connected-components of each object, and then assign a proper disparity value to each object. Because a few edge pixels still do not have disparity values, we use the nearest-neighbor interpolation to interpolate the remaining pixels. Finally, we can generate a dense disparity map. Compared with prior arts, the proposed method can fast generate dense disparity map with higher accuracy. In the experiments, the results demonstrate that the disparities of objects are more continuous and smoother with the proposed method.

[1] X. Zhu, H. Lu, X. Yang, Y. Li and H. Zhang, "Stereo Vision Based Traversable Region Detection for Mobile Robots," in Control Conference (CCC), 2013 32nd Chinese, Xi'an, 2013.
[2] T. Cao, Z.-Y. Xiang and J.-L. Liu, "Perception in Disparity: An Efficient Navigation Framework for Autonomous Vehicles With Stereo Cameras," IEEE Transactions on Intelligent Transportation Systems, vol. 16, no. 5, pp. 2935-2948, 5 2015.
[3] L. Wang, P. Wang, L. Cheng, Y. Ma, S. Wu, Y.-P. Wang and Z. Xu, "Detection and Reconstruction of an Implicit Boundary Surface by Adaptively Expanding A Small Surface Patch in a 3D Image," IEEE Transactions on Visualization and Computer Graphics, vol. 20, no. 11, pp. 1490-1506, 3 2014.
[4] Z. Ren, J. Meng and J. Yuan, "Depth camera based hand gesture recognition and its applications in Human-Computer-Interaction," in 2011 8th International Conference on Information, Communications and Signal Processing (ICICS), Singapore, 2011.
[5] A. Klaus, M. Sormann and K. Karner, "Segment-Based Stereo Matching Using Belief Propagation and a Self-Adapting Dissimilarity Measure," in 18th International Conference on Pattern Recognition, Hong Kong, 2006.
[6] I.-L. Jung and C.-S. Kim, "Robust view synthesis under varying illumination conditions using segment-based disparity estimation," in Signal & Information Processing Association Annual Summit and Conference (APSIPA ASC), 2012 Asia-Pacific, Hollywood, CA, 2012.
[7] G. Saygili, L. v. d. Maaten and E. A. Hendriks, "Improving segment based stereo matching using SURF key points," in 2012 19th IEEE International Conference on Image Processing, Orlando, FL, 2012.
[8] K. Subr, A. Majumder and S. Irani, "Greedy Algorithm for Local Contrast," in ICIAP'05 Proceedings of the 13th international conference on Image Analysis and Processing, 2005.
[9] A. Ray, S. Sanghavi and S. Shakkottai, "Improved Greedy Algorithms for Learning Graphical Models," IEEE Transactions on Information Theory, vol. 61, no. 6, pp. 3457-3468, 2015.
[10] F. Yi and I. Moon, "Image segmentation: A survey of graph-cut methods," in 2012 International Conference on Systems and Informatics (ICSAI), Yantai, 2012.
[11] A. Tuysuzoglu, W. C. Karl, I. Stojanovic, D. Castañòn and M. S. Ünlü, "Graph-Cut Based Discrete-Valued Image Reconstruction," IEEE Transactions on Image Processing, vol. 24, no. 5, pp. 1614-1627, 2015.
[12] H. Hirschmuller, "Accurate and efficient stereo processing by semi-global matching and mutual information," in IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 2005.
[13] G. A. Kordelas, D. S. Alexiadis, P. Daras and E. Izquierdo, "Content-Based Guided Image Filtering, Weighted Semi-Global Optimization, and Efficient Disparity Refinement for Fast and Accurate Disparity Estimation," IEEE Transactions on Multimedia, pp. 1520-9210, 2016.
[14] C. Stentoumis, A. Amditis and G. Karras, "Census-Based Cost on Gradients for Matching under Illumination Differences," in International Conference on 3D Vision (3DV), Lyon, 2015.
[15] M. M. Rahman, B. C. Desai and P. Bhattacharya, "A Feature Level Fusion in Similarity Matching to Content-Based Image Retrieval," in 9th International Conference on Information Fusion, Florence, 2006.
[16] M. Humenbergera, C. Zinnera, M. Webera and W. Kubingera, "A fast stereo matching algorithm suitable for embedded real-time systems," Computer Vision and Image Understanding, vol. 114, no. 11, pp. 1180-1202, 2010.
[17] I. Sobel, "An Isotropic 3x3 Image Gradient Operator," in Stanford A.I. Project, 1968.
[18] N. Otsu, "A Threshold Selection Method from Gray-Level Histograms," IEEE Transactions on Systems, Man, and Cybernetics, vol. 9, no. 1, pp. 62-66, Jan. 1979.
[19] D. Marv and T. Poggios, "Cooperative computation of stereo disparity," American Association for the Advancement of Science, vol. 194, no. 4262, pp. 283-287, 1976.
[20] J. Canny, "A Computational Approach to Edge Detection," IEEE Transactions on Pattern Analysis and Machine Intelligence, Vols. PAMI-8, no. 6, pp. 679-698, Nov. 1986.
[21] T. B. Moeslund, Introduction to Video and Image Processing: Building Real Systems, Springer-Verlag London, 2012.
[22] J. Serra, Image Analysis and Mathematical Morphology, Academic Press, Inc., 1983.
[23] R. C. Gonzalez and R. E. Woods, Digital Image Processing, 2/E, Pearson Education, 2002, p. 524.
[24] K. Wu, E. Otoo and K. Suzuki, "Optimizing two-pass connected-component labeling algorithms," Pattern Analysis & Applications, vol. 12, no. 2, pp. 117-135, 2009.
[25] K. Suzuki, I. Horiba and N. Sugie, "Linear-time connected-component labeling based on sequential local operations," Computer Vision and Image Understanding, vol. 89, no. 1, pp. 1-23, 2003.
[26] D. Peña and A. Sutherland, "Non-parametric image transforms for sparse disparity maps," in 14th IAPR International Conference on Machine Vision Applications, Tokyo, 2015.
[27] M. College, "http://vision.middlebury.edu/stereo/data/," Middlebury College. [Online].
[28] A. Aguilar-González, M. Pérez-Patricio, M. Arias-Estrada and J.-L. Camas-Anzueto, "An FPGA Correlation-Edge Distance approach for disparity map," in 2015 International Conference on Electronics Communications and Computers (CONIELECOMP), Cholula, 2015.
[29] C. Ttofis, S. Hadjitheophanous, A. S. Georghiades and T. Theocharides, "Edge-Directed Hardware Architecture for Real-Time Disparity Map Computation," IEEE Transactions on Computers , vol. 62, no. 4, pp. 690-704, 2013.
[30] S. Lee, J. H. Lee, J. Lim and I. H. Suh, "Robust stereo matching using adaptive random walk with restart algorithm," Image and Vision Computing, vol. 37, pp. 1-11, 2015.
[31] A. Hosni, C. Rhemann, M. Bleyer, C. Rother and M. Gelautz, "Fast Cost-Volume Filtering for Visual Correspondence and Beyond," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 35, no. 2, pp. 504-511, 2013.
[32] H. Hirschmüller, P. R. Innocent and J. Garibaldi, "Real-Time Correlation-Based Stereo Vision with Reduced Border Errors," International Journal of Computer Vision, vol. 47, no. 1, p. 229–246, 2002.
[33] J. Jiao, R. Wang, W. Wang, S. Dong, Z. Wang and W. Gao, "Local Stereo Matching with Improved Matching Cost and Disparity Refinement," IEEE MultiMedia, vol. 21, no. 4, pp. 16-27, 2014.
[34] C. Fiorio and J. Gustedt, "Memory Management for Union-Find Algorithms," in Proceedings of the 14th Annual Symposium on Theoretical Aspects of Computer Science, London, 1997.
[35] E. Trucco and A. Verri, Introductory Techniques For 3-D Computer Vision, Prentice Hall, 1998.