臺灣博碩士論文加值系統

本論文的目標是探討利用電腦視覺技術來完成自動車在室內環境所做定位工作。其最主要的概念在於建立架設於自動車上的攝影機所擷取之影像與工作空間環境兩者的平面投影轉換關係，以求出自動車在空間中的正確位置。更具體來說，我們提供兩種定位的方法：1.對每一張所擷取的影像特徵反覆計算其對應於工作空間之平面轉換關係，以此來計算自動車在地圖中的位置。2.利用單一的平面轉換矩陣計算特徵點在空間中相對於自動車的運動向量，以此推估自動車位置。其中第一種方法，相較於早先我們所曾經使用的Cross-Ratio定位方法，兩者在使用最少特徵點數目（4點）之下有等價關係，但對於特殊情況的處理，實驗結果顯示本論文所提之方法，有著較優的處理效能以及精確性。而第二種方法的特色在於能夠對自動車較小範圍的運動提供簡單的定位，其精確性雖然不及第一種方法，卻仍能提供使用者一定程度的定位結果作為參考。

The goal of this study is to automatically calculate robot locations in an indoor environment using computer vision-based techniques. The main concept is based on homographies that model the geometric transformations between images captured by a camera and the workspace of a planar environment. Specifically, we propose two localization methods: (i) localization based on repeated computation of homographies using image features in each frame and (ii) localization based on a single planar transformation by evaluating relative motion of landmarks in the workspace w.r.t. the robot. For (i), one can show that it is equivalent to the localization method based cross-ratio proposed previously. If minimum number of image features are used. While (i) can be extended directly to take into account more image point features, extensions of the cross-ratio based method is not straightforward. On the other hand, experimental results show that (i) is more accurate than (ii); however (ii) is more simple and can provide useful localization results by locating robot positions in small range.

目 錄 1
圖目錄 3
一、背景 5
1.1 相關研究 5
1.1.1 室內導航（Indoor Environment Navigation） 5
1.1.2 戶外導航（Outdoor Environment Navigation） 8
1.2 Cross-Ratio方法簡介 9
1.3 Homography方法簡介 11
1.4 研究目的與動機 12
1.4.1 以工作空間為中心定位方法與以Cross-Ratio定位方法比較 13
1.4.2 在同一組參考點下兩者方法等效性 13
二、自動車導航系統介紹 15
2.1 系統簡介 15
2.2 應用範圍 16
2.3 夜間影像前置處理 16
2.4 自動車定位演算法 17
2.5 環境限制 18
三、以工作空間座標系為中心之平面轉換定位方法 19
3.1 平面投影轉換 20
3.1.1 最小對應點數 21
3.1.2 Over-determined 21
3.1.3 DLT (Direct Linear Transformation) 22
3.2 自動車定位估算 23
四、以自動車座標系為中心之平面轉換定位方法 26
4.1 以自動車座標系為中心之平面轉換定位方法流程 27
4.2 最小平方法（Least Squares Solution Method） 29
4.3 離群值（Outliers）的偵測 30
4.3.1 利用特徵點在空間平面中的走向做篩選 31
4.3.2 主成分分析法（Principal Components Analysis） 32
4.3.3 利用環境的分佈特性做矯正 34
4.4 總結 36
五、實驗結果與探討 37
5.1 以工作空間座標系為中心之平面轉換定位方法探討 37
5.1.1 自動車定位結果比較 38
5.1.2 效能與時間複雜度討論 41
5.2 以自動車座標系為中心之平面轉換定位方法討論 42
5.3 以工作空間座標系與以自動車座標系為中心之定位方法比較 45
5.4 自動車實際定位探討 46
六、結論 48
6.1 總結 48
6.2 未來工作 48
參考文獻 50

[1] M. Hashima, F. Hasegawa, S. Kanda, T. Maruyama, and T. Uchiyama, “Localization and Obstacle Detection for a Robot for Carrying Food Trays,” in Proc. IEEE Int’l Conf. Intelligent Robots and Systems, pp. 345-351, 1997.
[2] W. Chen, X. Wang, T. Wu, and X. Xu, “Visual Protractor Based Localization Algorithm for Mobile Robot,” in Proc. Sixth Int’l Conf. Intelligent Systems Design and Applications, pp. 67-71, 2006
[3] A. Bias, R. Sablatnig, and J. Gu, “Single Landmark Based Self-localization,” in Proc. 3rd Canadian Conf. Computer and Robot Vision, pp.67-67, 2006.
[4] H. Moravec, “Obstacle Avoidance and Navigation in the Real World by a Seeing Robot Rover,” PhD thesis, Stanford Univ., 1980.
[5] H. Moravec and A. Elfes, “High Resolution Maps from Wide Angle Sonar,” in Proc. IEEE Int’l Conf. Robotics and Automation, pp. 116-121, 1985.
[6] H. Choset, I. Konukseven, and A. Rizzi, “Sensor Based Planning: A Control Law for Generating the Generalized Voronoi Graph,” in Proc. Eighth IEEE Int’l Conf. Advanced Robotics, pp. 333-338, 1997.
[7] S. Thrun, “Learning Metric-Topological Maps for Indoor Mobile Robot Navigation,” Int’l Journal of Artificial Intelligence, pp. 21-71, 1998.
[8] G. Wichert, “Mobile Robot Localization Using a Selforganized Visual Environment Representation, ” in Proc. EUROMICRO workshop, pp.29-36, 1997.
[9] G. Adorni, M. Mordonini, S. Cagnoni, and A. Sgorbissa, “Omnidirectional Stereo Systems for Robot Navigation,” in Proc. IEEE Workshop on Omnidirectional Vision and Camera Networks, pp. 79, 2003.

[10] J. B. Hayet, F. Lerasle, and M. Devy, “Visual Landmarks Detection and Recognition for Mobile Robot Navigation,” in Proc. IEEE Conf. Computer Vision and Pattern Recognition Workshop, pp. 313-318, 2003.
[11] S. Tsugawa, T. Yatabe, T. Hirose, and S. Matsumoto, “An Automobile with Artificial Intelligence,” in Proc. Int’l Joint Conf. Artificial Intelligence, pp. 893-895, 1979.
[12] N. Simond, and P. Rives, “Homography from a Vanishing Point in Urban Scenes,” in Proc. IEEE/RSJ Int’l Conf. Intelligent Robots and Systems, pp. 1005-1010, 2003.
[13] L. Lorigo, R. A. Brooks, and W. E. L. Grimsou “Visually-guided Obstacle Avoidance in Unstructured Environments,” in Proc. IEEE/RSJ Int’l Conf. Intelligent Robots and Systems, pp. 373-379, 1997.
[14] C. Thorpe, M. Herbert, T. Kanade, and S. Shafer, “Vision and Navigation for the Carnegie-Mellon Navlab,” IEEE Trans. Pattern Analysis and Machine Intelligence, pp. 362-372, 1988.
[15] H. Mori, K. Kobayashi, N. Ohtuki, and S. Kotani, “Color Impression Factor: An Image Understanding Method for Outdoor Mobile Robots,” in Proc. IEEE Int’l Conf. Intelligent Robots and Systems, pp. 380-386, 1997.
[16] M. Brand, “Incremental Singular Value Decomposition of Uncertain Data with Missing Values,” in Proc. European Conf. Computer Vision, pp. 707-720, 2002.