最近隨著機器人的高度發展，他們已經開始具備部分的思維以及辨識能力，
甚至可以模仿人類所能做的事情。尤其可以在未知的環境中準確且安全的移動，是這些機器人重要的基本能力之一。本論文的目的，就是要讓機器人可以準確且快速的知道周遭物體的遠近位置。有別於使用雷射光和雷達感應器有搜索角度和觀測距離較小以及解析度不夠等缺點，我們將使用CCD攝影機擷取影像的方法來讓系統更有強健性。
這篇論文的基本概念是利用兩台攝影機由於架設位置不同而導致成像時的視差來做物體3D位置的重建。依據在實做上，我們首先做攝影機校正， 包括像機鏡頭失真以及架設位置的調校。接著將樣本影像切成區塊，然後利用皮爾森相關係數法在參考影像中尋找對應區塊以後得到區塊位置的偏移距離。若是該區塊的影像變異數太大，我們會繼續切成更小的區塊來尋找對應區塊。我們也提出了減小區塊搜尋區域的演算法來增加執行速度。在得到該區塊的偏移距離後，利用數學上的相似三角形原理來推得該區塊的實際3D位置。比較平行和非平行攝影機的重建結果也是本篇的重點之一。我們用實驗證明了依照本篇的方法，平行攝影機可以有更大的可重建範圍以及更準確的重建結果。
跟目前常見的重建3D立體場景的方法比起來，我們所採用的無特徵區塊比對的方法不只速度更快，在光源不足或者特徵不明顯的場景中依然可以有不錯的表現。本論文所採用的方法皆是在低運算量的前提下，做到最精準的估測，以達到即時輔助機器人的行動效果。此方法判斷物體3D位置可做到90%的可重建區域達到90%以上的準確率。

With the high development of robots, they begin to have basic thinking and recognition ability, even to imitate some works that human can do. To move accurately and safely in an unknown environment is one of the important functionality of the robots. The main purpose of this thesis is to let these robots can precisely and immediately know the locations of the objects surround them. Being different from the laser and radar sensors that are limited by the searching angle and observation distance, we use the CCD cameras to capture images to increase the robustness of our 3D scenes reconstruction system.
The basic idea of this thesis is to utilize the imaging parallax of the two cameras caused by the different setup locations to accomplish 3D scenes reconstruction. While implementing this idea, we first do camera calibration such as lens distortion restoration and setup location adjustment of the cameras. Then we divide the template image into blocks and adopt the Pearson product moment correlation coefficient to find the corresponding blocks in the reference image. If the variance of the current block is too big, we further partition the block into sub-blocks recusively. We also propose an efficient searching algorithm to reduce the execution time of block matching. When we find the parallax of the corresponding blocks, we reconstruct the real 3D location by use of similar triangle calculations. The comparison of paralleled and non-paralleled cameras is also an important topic in this thesis. We prove by experiments that paralleled cameras can provide larger reconstructable area and higher accuracy then the non-paralleled cameras.
Comparing with existing popular methods, our featureless block matching method not only performs faster but also better when the luminance is low or the object features are unapparent. Besides, all methods and algorithms presented in this thesis all based on the prerequisite of low computation cost to attain the most precise 3D location estimation as to help robots move immediately. The reconstruction precision of our method can reach over 90%.

[1] S. T. Barnard and M. A. Fischler, “Computation stereo,” Computing Surveys,
vol. 14, pp. 553-572, 1982.
[2] A. P. Pentland, “A new sense for depth of field,” IEEE Transations on Pattern Analysis and Machine Intelligence, vol. 9, no. 4, pp. 523-531, 1987.
[3] M. K. Leung, Y. Liu, and T. S. Huang, “Estimating 3D vehicle motion in an outdoor scene from monocular and stereo image sequences,” Proceedings of the IEEE Workshop on Visual Motion, New-Jersey, USA, pp. 62-68, 1991.
[4] E. Grosso and M. Tistarelli, “Active/dynamic stereo vision,” IEEE Transations on Pattern Analysis and Machine Intelligence, vol. 179, no. 11, pp. 868-879, 1995.
[5] M. Bertozzi and A. Broggi, “GOLD: a parallel real-time stereo vision system for generic obstacle and lane detection,” IEEE Transations on Image Processing, vol. 71, no. 1, pp. 62-81, 1998.
[6] A. Elfes, “Using occupancy grids for mobile robot perception and navigation,” Computer Magazine, vol. 22, no. 6, pp. 46-57, 1989.
[7] J. Hancock, M. Hebert, and C. Thorpe, “Laser intensity-based obstacle detection intelligent robots and systems,” IEEE/RSJ International Conference on Intelligent Robotic Systems, Butchart, Canada, vol. 3, pp. 1541-1546, 1998.
[8] E. Elkonyaly, F. Areed, Y. Enab, and F. Zada, “Range sensory-based navigation in unknown terrains,” Proceedings of SPIE, vol. 2591, pp. 76-85, 1995.
[9] D. Wang, Y. M. Chen, M. L. Fang, and Y. Y. He, “A study of robot remote monitoring system,” Intelligent Control and Automation, Proceedings of the 4th World Congress, Shanghai, P. R. China, vol. 2, pp. 129-1295, 2002.
[10] J. L. Marble, D. J. Bruemmer, and D. A. Few, “Lessons learned from usability tests with a collaborative cognitive workspace for human-robot teams,” IEEE International Conference on Systems, Man and Cybernetics, Idaho Fall, ID, vol. 1, pp. 448-453, 2003.
[11] R. G. Yang and Z. Y. Zhang, “Eye gaze correction with stereovision for video-teleconferencing,” IEEE Transations on Pattern Analysis and Machine Intelligence, vol. 26, no. 7, pp. 956-960, 2004.
[12] T. Fong, C. Thorpe, and C. Baur, “Multi-robot remote driving with collaborative control,” IEEE Transations on Industrial Electronics, vol. 50, no. 4, pp. 699-704, 2003.
[13] Q. M. Ruan, R. J. He, Y. J. Tan, Y. G. Chen, and X. Liu, “Coordinating Remote Sensing for Earth Observing Satellites,” The 1st International Symposium on Systems and Control in Aerospace and Astronautics, pp. 389-394, 2006.
[14] Y. C. Go, J. C. Sohn, and Y. J. Cho, “Probabilistic approach to model intelligent robot services,” The 8th International Conference on Advanced Communication Technology, vol. 2, pp. 1221-1224, 2006.
[15] M. Bjorkman and J. -O. Eklundh, “Real-time epipolar geometry estimation of binocular stereo heads,” IEEE Computer Society, vol. 24, no. 3, pp. 425-432, 2002.
[16] M. X. Hu, G. H. Zou, and B. Z. Yuan, “A 3-D reconstruction method based on epipolar geometry,” 5th International Conference on Signal Processing Proceedings, vol. 2, pp. 1277-1280, 2000.
[17] R. Bunschoten and B. Krose, “Robust scene reconstruction from an omnidirectional vision system,” IEEE Transactions on Robotics and Automation, vol. 19, no. 2, pp. 351-357, 2003.
[18] R. C. Gongalez and R. E. Woods, Digital Image Processing, 2nd Edition, Prentice-Hall, Upper Saddle River, New-Jersey, 2002.
[19] J. Canny, “A computational approach to edge detection,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 8, no. 6, pp. 679-698, 1986.
[20] R. Deriche, “Fast algorithms for low-level vision,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 12, no. 1, pp. 78-87, 1990.
[21] M. Trajkovic and M. Hedley, “Fast corner detection,” Image and Vision Computing, vol. 16, no. 2, pp. 75-87, 1998.
[22] C. J. Wu, “Real-time obstacle detection and sign recognition,” Master Thesis, Department of Engineering Science, National Cheng Kung university, Tainan, Taiwan, 2002.
[23] W. Zhang, Q. B. Zhang, L. Qu, S. Wei, “A stereo matching algorithm based on multiresolution and epipolar constraint,” IEEE Computer Society, pp. 180-183, 2004.
[24] Y. P. Hung and K. Y. Cheng, “Face reconstruction using computer vision techniques,” Master Thesis, Department of Computer Science, National Taiwan university, Taipei, Taiwan, 2000.
[25] H. G. Nguyen, ”Obtaining range from visual motion using local image derivatives,” Technical Document 2918, RDT&E Division, Navel Command, Control, and Ocean Surveillance Center, San Diego, California, pp. 1-16, 1996.
[26] B. D. Lucas and T. Kanade, “An iterative image registration technique with application to stereo vision,” Proceedings of the DARPA Image Understanding Workshop, Vancouver, British Columbia, pp. 121-130, 1981.
[27] W. C. Chang and S. A. Lee, “Real-time feature-based 3D map reconstruction for stereo visual guidance and control of mobile robots in indoor environments,” IEEE International Conference on Systems, Man and Cybernetics, vol. 6, no. 6, pp. 5386-5391, 2004.
[28] G. Egnal and R. P. Wildes, “Detecting binocular half-occlusions: empirical comparisons of five approaches,” IEEE Transations on Pattern Analysis and Machine Intelligence, vol. 24, no. 8, pp. 1127-1133, 2002.
[29] H. Zhang and S. Negahdaripour, “Fast and robust progressive stereo reconstruction by symmetry guided fusion, ”Oceans 2005-Euroup, vol. 1, no. 1, pp. 551-556, 2005.
[30] F. C. Tien, ”Using neural network for three-dimensional measurement in stereo vision systems,” Ph.D. Dissertation, University of Missouri-Columbia , 1996.
[31] K. G. Maver, K. B. Rasmussen, and S. A. Petersen, “Globally optimised seismic inversion of up-going P-wave reflected VSP data,” Proceedings of the NPF Biannual Conference, Kristianssand, 1996.
[32] D. A. Forsyth and J. Ponce, Computer Vision: A Modern Approach, Pearson Education international, Prentice Hall, 2001.
[33] R. Klette and P. Zamperoni, Handbook of Image Processing Operators, John Wiley & Sons, New York, pp. 148-156, 1996.
[34] L. M. G. Fonseca and B. S. Manjunath, “Registration techniques for multisensor remotely sensed imagery,” Photogrammetric Engineering and Remote Sensing, vol. 62, no. 9. pp. 1049–1056, 1996.
[35] W. K. Pratt, Digital Image Processing, 2nd Edition, John Wiley & Sons, New York, 1991.
[36] B. Zitova and J. Flusser, “Image registration methods: a survey,” Image and Vision Computing, vol. 21, pp. 977-1000, 2003.
[37] R. C. Gonzalez and R. E. Woods, Digital Image Processing, Addison-Wesley, Reading, Massachusetts, 1st Edition, 1992.