臺灣博碩士論文加值系統

　　立體視覺廣泛的運用在許多領域，例如自走機器人、自動追蹤的攝影機、甚至於立體電視。由於許多的應用需要即時的立體視覺系統，因此需要設計一個能滿足高運算以及高頻寬的積體電路。
　　本篇研究提出了一個適合硬體設計的演算法，係基於適應性權重的計算(Adaptive Weight Generation)演算法結合微型普查(Mini-Census)的比對方式、兩次聚合(Two-Pass Aggregation)以及量子化指數曼哈頓距離(Quantized Manhattan Color Distance)等技巧。微型普查可以減少運算量，從原來的一個視窗的運算變成只有六個點運算。除此之外，他還加強了原本演算法中對於光線所造成的問題。兩階段資料匯集和量子化指數曼哈頓距離分別減少了88.7%和64.2%的運算複雜度。相較於原本的權重產生函式，量子化指數曼哈頓距離可以被實現成查表的硬體電路。
　　最後在聯華電子90奈米製程下，提出的設計可以在100MHz的工作時脈下達到每秒計算43張CIF畫面大小及64個階層的深度估測。晶片總共需要562,642個邏輯閘，以及21.3K的晶片記憶體。

Stereo matching has been widely used in many fields, such as automatic robots, auto-tracking system, and even the 3D-TV. With these real time application demands, VLSI implementation becomes necessary to fulfill the high complexity and high bandwidth requirements of stereo matching algorithms.
In this thesis, we propose a hardware friendly algorithm, based on adaptive support weight (ADSW), with mini-census, two-pass aggregation, and quantized exponential Manhattan distance techniques. The mini-census reduces the computation complexity from a matching block to only 6 points. Besides, it also improves the capability of ADSW to deal with the radiometric problem. The two-pass aggregation and the quantized Manhattan color distance reduce about 88.7% and 64.2% computation of the cost aggregation respectively. Comparing to the original weight generation function, the quantized Manhattan color distance can be easily implemented by a table based circuit.
The final design implemented by UMC 90nm CMOS technology can achieve 43 frames per second and 64 disparities with CIF image size under 100MHz clock rate. The chip consumes totally 562,642 K gate counts and 21.3K Bytes internal memory.

1. INTRODUCTION 1
1.1. BACKGROUND 1
1.2. MOTIVATION AND CONTRIBUTION 1
1.3. ORGANIZATION OF THE THESIS 2
2. INTRODUCTION OF COMPUTATIONAL STEREO 3
2.1. OVERVIEW 3
2.2. EPIPOLAR GEOMETRY 3
2.3. THE GENERAL FLOW OF MATCHING ALGORITHMS 4
2.3.1. Matching Cost Computation 4
2.3.2. Cost Aggregation 6
2.3.3. Disparity Computation 6
2.4. A TAXONOMY EVALUATION 6
3. RELATED WORK 9
3.1. OVERVIEW 9
3.2. LOCAL APPROACH 9
3.3. GLOBAL APPROACH 10
3.4. ADAPTIVE SUPPORT WEIGHT 12
3.5. REAL-TIME IMPLEMENTATIONS 13
3.5.1. General Purpose Processor 14
3.5.2. Graphic Processing Unit 14
3.5.3. Digital Signal Processing Processor 14
3.5.4. Application-Specific Integrated Circuit 15
3.6. SUMMARY 16
4. PROPOSED MINI-CENSUS ADAPTIVE SUPPORT WEIGHT 17
4.1. INTRODUCTION 17
4.2. THE FLOW OF THE PROPOSED ALGORITHM 17
4.3. MINI-CENSUS 18
4.4. WEIGHT GENERATION AND APPROXIMATION 19
4.4.1. The Performance with Different Color Space 20
4.4.2. The Color Distance 21
4.4.3. The Effect of Proximity Weight 22
4.4.4. Quantized Exponential Function 22
4.4.5. The Final Weight Table 24
4.5. AGGREGATION ITERATION 25
4.6. TWO-PASS COST AGGREGATION APPROXIMATION 28
4.7. OVERALL SIMULATION RESULT 28
5. DATA REUSE ANALYSIS OF HARDWARE IMPLEMENTATION 29
5.1. OVERVIEW 29
5.2. ARCHITECTURE OVERVIEW 29
5.3. MATCHING COST COMPUTATION REUSE 31
5.3.1. Disparity-Order Reuse 31
5.3.2. Pixel-Order Reuse 32
5.4. COST AGGREGATION DATA REUSE 33
5.4.1. Partial Column Reuse (PCR) 33
5.4.2. Vertically Expanded Row Reuse (VERR) 34
5.5. COMPARISON 35
5.6. SUMMARY 35
6. HARDWARE IMPLEMENTATION 37
6.1. OVERVIEW 37
6.2. FUNCTIONAL BLOCK 38
6.2.1. Mini-Census Transform 38
6.2.2. Weight Generation 39
6.2.3. Aggregation and Winner-Takes-All 40
6.2.4. Input and Output Control 41
6.3. HANDSHAKING 42
6.4. ARBITRATION 43
6.5. MEMORY 45
6.5.1. Memory Update Mechanism 45
6.5.2. Memory Size 46
6.6. IMPLEMENTATION RESULT 48
6.6.1. External Bandwidth 48
6.6.2. Area and Gate Counts 49
6.7. PERFORMANCE RESULT 50
CONCLUSION 53
FUTURE WORK 53
REFERENCE 55

[1] P. Kauff, N. Brandenburg, M. Karl, and O. Schreer, “Fast hybrid block- and pixel recursive disparity analysis for real-time applications in immersive teleconference scenarios,” in Proceedings of 9 th International Conference in Central Europe on Computer Graphics Visualization and Computer Vision, pp. 198-205, 2001.
[2] T. Kanade, A. Yoshida, K. Oda, H. Kano, and M. Tanaka, “A stereo machine for video-rate dense depth mapping and its new applications,” in Proceedings of the IEEE International Conference on Computer Vision and Pattern Recognition, 1996.
[3] M.Z. Brown, D. Burschka, and G. Hager, “Advances in Computational Stereo,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 25, no.8, pp. 993-1008, August 2003.
[4] D. Scharstein and R. Szeliski, "A Taxonomy and Evaluation of Dense Two-Frame Stereo Correspondence Algorithms," International Journal of Computer Vision, vol. 47, pp. 7-42, 2002.
[5] H. Hirschmuller and D. Scharstein, "Evaluation of Cost Functions for Stereo Matching," in Proceedings of IEEE Conference on Computer Vision and Pattern Recognition, pp. 1-8, 17-22 June 2007
[6] R. Zabih and J. Woodfill, “Non-parametric Local Transforms for Computing Visual Correspondence,” in Proceedings of third European Conference on Computer Vision, vol. 2, pp. 151–158, 1994.
[7] G. Egnal, "Mutual information as a stereo correspondence measure," Computer and Information Science, University of Pennsylvania, Philadelphia, USA, Tech. Rep. MS-CIS-00-20, 2000.
[8] M. Hariyama, H. Sasaki, and M.Kameyama, “Architecture of a stereo matching VLSI processor based on hierarchically parallel memory access,” The 2004 47th Midwest Symposium on Circuits and Systems, vol 2, pp. II245- II247, 2004.
[9] M. Okutomi and T. Kanade, "A locally adaptive window for signal matching," International Journal of Computer Vision, vol. 7, pp. 143-162, 1992.
[10] M. Hariyama, T. Takeuchi, and M. Kameyama, "Reliable stereo matching for highly-safe intelligent vehicles and its VLSI implementation," in Proceedings of the IEEE Intelligent Vehicles Symposium. IV, pp. 128-133, 2000.
[11] P. B. Chou and C. M. Brown, "The theory and practice of Bayesian image labeling," International Journal of Computer Vision, vol. 4, pp. 185-210, 1990.
[12] H. Tao, H. S. Sawhney, and R. Kumar, "A global matching framework for stereo computation," Proc. Int’l Conf. Computer Vision, vol. 1, pp. 532-539, 2001.
[13] A. F. Bobick and S. S. Intille, "Large Occlusion Stereo," International Journal of Computer Vision, vol. 33, pp. 181-200, 1999.
[14] S. B. Kang, R. Szeliski, and J. Chai, "Handling Occlusions in Dense Multi-View Stereo," in Proceedings of IEEE Computer Society Conference on Computer Vision and Pattern Recognition, vol. 1, 2001.
[15] K.J. Yoon and I.S. Kweon, “Adaptive Support-weight Approach for Correspondence search,” IEEE Transactions on Pattern Analysis and Machine Intelligence, 2006.
[16] M. Gerrits, and P. Bekaert, "Local Stereo Matching with Segmentation-based Outlier Rejection," in Proceedings of the 3rd Canadian Conference on Computer and Robot Vision, pp. 66-66, 07-09 June 2006.
[17] F. Tombari, S. Mattoccia, and L. Di Stefano, "Segmentation-Based Adaptive Support for Accurate Stereo Correspondence," Lecture Notes in Computer Science, vol. 4872, p. 427, 2007.
[18] F. Tombari, S. Mattoccia, L. Di Stefano, and E. Addimanda, “Classification and evaluation of cost aggregation methods for stereo correspondence," in Proceedings of IEEE International Conference on Computer Vision and Pattern Recognition, June 24-26, 2008
[19] ISO/IEC JTC1/SC29/WG11 N6501, "Requirements on Multi-view Video Coding," Redmond, USA, July 2004.
[20] O. Veksler, "Fast variable window for stereo correspondence using integral images," in Proceedings of IEEE Computer Society Conference on Computer Vision and Pattern Recognition, vol.1, pp. I-556-I-561
[21] S. Kang, R. Szeliski, and J. Chai, “Handling occlusions in dense multi-view stereo,” in Proceedings of IEEE Computer Society Conference on Computer Vision and Pattern Recognition, pp. 103–110, 2001.
[22] H. Hirschmuller, P. R. Innocent, and J. Garibaldi, "Real-Time Correlation-Based Stereo Vision with Reduced Border Errors," International Journal of Computer Vision, vol. 47, pp. 229-246, 2002.
[23] S. Chan, Y. Wong, and J. Danie, "Dense stereo correspondence based on recursive adaptive size multi-windowing," Image and Vision Computing New Zealand, pp. 26-28, 2003.
[24] M. Gong and R. Yang, "Image-gradient-guided real-time stereo on graphics hardware," in Proceedings of Fifth International Conference on 3-D Digital Imaging and Modeling, pp. 548-555, 2005.
[25] C. Demoulin and M. Van Droogenbroeck. “A method based on multiple adaptive windows to improve the determination of disparity maps,” in Proceedings of IEEE Workshop on Circuit, Systems and Signal Processing, pp. 615–618, 2005.
[26] Y. Boykov, O. Veksler, and R. Zabih, "A variable window approach to early vision," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 20, pp. 1283-1294, 1998.
[27] 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 Proceedings of IEEE Computer Society Conference on Computer Vision and Pattern Recognition, vol. 2, 2005.
[28] M. Okutomi, Y. Katayama, and S. Oka, "A Simple Stereo Algorithm to Recover Precise Object Boundaries and Smooth Surfaces," International Journal of Computer Vision, vol. 47, pp. 261-273, 2002.
[29] Y. Ohta and T. Kanade, "Stereo by intra- and inter-scanline search using dynamic programming," IEEE transactions on pattern analysis and machine intelligence, vol. 7, pp. 139-154, 1985.
[30] S. Roy and I. J. Cox, "A Maximum-Flow Formulation of the N-Camera Stereo Correspondence Problem," in Proceedings of the Sixth International Conference on Computer Vision, 1998.
[31] Y. Boykov, O. Veksler, and R. Zabih, "Fast Approximate Energy Minimization via Graph Cuts," IEEE transactions on pattern analysis and machine intelligence, pp. 1222-1239, 2001.
[32] Y. Boykov and V. Kolmogorov, "An Experimental Comparison of Min-Cut/Max-Flow Algorithms for Energy Minimization in Vision," IEEE transactions on pattern analysis and machine intelligence, pp. 1124-1137, 2004.
[33] H. Hirschmuller, "Improvements in real-time correlation-based stereo vision," IEEE Workshop on Stereo and Multi-Baseline Vision, pp. 141-148, 2001.
[34] G. Minglun and Y. Yee-Hong, "Near real-time reliable stereo matching using programmable graphics hardware," in Proceedings of IEEE Computer Society Conference on Computer Vision and Pattern Recognition, vol.1, pp. 924-931, 2005.
[35] S. Forstmann, Y. Kanou, O. Jun, S. Thuering, and A. Schmitt, "Real-Time Stereo by using Dynamic Programming," in Proceedings of Computer Vision and Pattern Recognition Workshop on Real-Time 3D Sensor and Their Use, , 2004, pp. 29-29, 2004.
[36] L. Jiangbo, G. Lafruit, and F. Catthoor, "Fast Variable Center-Biased Windowing for High-Speed Stereo on Programmable Graphics Hardware," in Proceedings of IEEE International Conference on Image Processing, pp. VI - 568-VI – 571, 2007
[37] L. Jiangbo, S. Rogmans, G. Lafruit, and F. Catthoor, "Real-Time Stereo Correspondence using a Truncated Separable Laplacian Kernel Approximation on Graphics Hardware," in Proceedings of IEEE International Conference on Multimedia and Expo, pp. 1946-1949, 2007.
[38] L. Wang, M. Liao, M. Gong, R. Yang, and D. Nister, "High-quality real-time stereo using adaptive cost aggregation and dynamic programming," in Proceedings of the Third International Symposium on 3D Data Processing, Visualization, and Transmission (3DPVT'06), pp. 798-805, 2006.
[39] K. Konolige, “Small Vision Systems: Hardware and Implementation,” in Proceedings of Eighth Int'l Symp. Robotics Research, Oct. 1997.
[40] N. Chang, T. M. Lin, T. H. Tsai, Y. C. Tseng, and T. S. Chang, "Real-Time DSP Implementation on Local Stereo Matching," in Proceedings of IEEE International Conference on Multimedia and Expo, pp. 2090-2093, 2007.
[41] M. Hariyama, T. Takeuchi, and M. Kameyama, "VLSI processor for reliable stereo matching based on adaptive window-size selection," in Proceedings of IEEE International Conference on Robotics and Automation, vol. 2, 2001.
[42] Q. Yang, L. Wang, R. Yang, S. Wang, M. Liao, and D. Nister, "Real-time global stereo matching using hierarchical belief propagation," in Proceedings of The British Machine Vision Conference, 2006.
[43] S Park, C Chen, and H Jeong. “VLSI Architecture for MRF Based Stereo Matching,” Lecture Notes in Computer Science, vol.4599, no., pp.55-64 2007
[44] M. Gong, R. Yang, and L. Wang, "A Performance Study on Different Cost Aggregation Approaches Used in Real-Time Stereo Matching," International Journal of Computer Vision, vol. 75, pp. 283-296, 2007.
[45] S. Park, H. Jeong, K. Pohang, and S. Korea, "Real-time Stereo Vision FPGA Chip with Low Error Rate," Proceedings of the 2007 International Conference on Multimedia and Ubiquitous Engineering, pp. 751-756, 2007.
[46] F. Tombari, S. Mattoccia, L. Di Stefano, and E. Addimanda. “Near real-time stereo based on effective cost aggregation,” in Proceedings of the IEEE International Conference on Computer Vision and Pattern Recognition, 2008.