臺灣博碩士論文加值系統

本論文為了實現無人載具能夠具備自主辨識環境之能力，因此透過圖形化程式編譯平台LabVIEW與商業數學軟體MATLAB，共同研發出一套適用於任何環境下的二維環境顯示介面系統，經由此系統所建構的環境地圖，能夠讓無人載具及監控端迅速掌握其周遭環境之概況，由此可知，環境地圖之建立為整體系統之核心所在，所以本文希望藉由開發建構環境地圖之方法，進而使載具可從系統中獲得到最正確之環境地形資訊。
本研究室最初使用最佳化直線分群法，雖然能建構出完整的線段特徵式環境地圖，但卻無法有效的判斷出環境可通行之區域，還會造成環境地形的複雜度影響其建構地圖之效率，因此本論文利用一套斷點探測以及資料點簡化之方法，期望能改善上述之問題。最後，將以上兩種建立環境地圖的方法，透過雷射測距儀於不同環境地形及旋轉角度下作測試，並分別對其環境地圖建構之準確度及效率進行研究探討，以確保二維環境顯示介面系統在搭配斷點探測與資料點簡化之方法後，能夠快速建構出更加準確的環境地圖。

The purpose of this paper is to realize the unmanned vehicles are actually possessed of the ability to perceive environment. In order to test the actuality, a two-dimensional graphical user interface system is developed by using LabVIEW and MATLAB software. The system allows unmanned vehicles and monitoring to rapidly obtain data and construct a map of the environment surrounded. The challenge is the construction of the mapping which is the core of the entire system. Therefore, this study is focus on investigating which map-building method could best assists the unmanned vehicles to obtain the most accurate information and data of the environment.
An optimal linear clustering method was used to construct a complete geometric primitives-based map. However, it lacks the ability to precisely determine the accessible regions in the environment. Also the mapping efficiency decreased as the complexity of the environment increased. A method of breakpoint detection with data point simplification is proposed to solve the aforementioned issues. This method will be further tested by laser ranger finder in different specified rotation angles and testing environments. Subsequently, the experimental results are conferred on the accuracy and efficiency of the map-building to ensure that the system coupled with this new approach is enabling to construct a high accuracy environment map promptly.

摘要 i
ABSTRACT ii
目錄 iii
表目錄 vi
圖目錄 vii
第一章 緒論 1
第二章 文獻回顧 3
2.1 環境地圖之介紹 (Environmental Mapping) 3
2.2 群聚技術 (Clustering Technology) 7
2.2.1 K-Means演算法之介紹 (K-Means Algorithm) 9
2.3 相關係數 (Correlation Coefficient) 10
2.4 線段萃取演算法 (Line Extraction Algorithms) 13
2.5 應用虛擬儀控於環境地圖建立 15
2.6 研究目的 16
第三章 建立環境地圖之方法 18
3.1 座標系統之轉換 18
3.1.1 極座標系統 (Polar Coordinate System) 18
3.1.2 笛卡爾座標系統 (Cartesian Coordinate System) 19
3.1.3 座標轉換 20
3.2 局部環境地圖建立 22
3.2.1 最佳化直線分群法 22
3.2.2 方位角之環境地圖資料點處理法 32
第四章 實驗設備介紹 46
4.1 硬體設備 46
4.1.1 雷射測距儀 SICK LMS100 47
4.1.2 雷射測距原理 50
4.1.3 雷射測距儀資料傳輸方式 54
4.2 軟體程式 60
4.2.1 圖形化程式編譯平台 LabVIEW 60
4.2.2 商業數學軟體 MATLAB 65
4.3 研究方法 67
第五章 實驗測試與結果 68
5.1 測試環境與設備架設 68
5.2 實驗測試與結果 70
5.3 結果分析與討論 100
第六章 結論與未來展望 103
6.1 結論 103
6.2 未來展望 103
參考文獻 105

【1】Alberto Elfes, “Using Occupancy Grids for Mobile Robot Perception and Navigation,” Proceedings of the IEEE Computer, pp. 46-57, 1989.
【2】Lejla Banjanović Mehmedović, Ivan Petrović, and Edouard Ivanjko, “Mobile Robot Localization using Local Occupancy Grid Maps Transformations,” Proceedings of the IEEE Conference on Power Electronics and Motion Control, pp.1307-1312, 2006.
【3】Hans P. Moravec, and Alberto Elfes, “High Resolution Maps from Wide Angle Sonar,” Proceedings of the IEEE International Conference on Robotics and Automation , pp.116-121, 1985.
【4】Zezhong Xu, Jilin Liu, Zhiyu Xiang, and Han Li, “Map Building for Indoor Environment with Laser Range Scanner,” Proceedings of the IEEE International Conference on Intelligent Transportation Systems, pp.136-140, 2002.
【5】Li Zhang, and Bijoy K. Ghosh, “Line Segment Based Map Building and Localization Using 2D Laser Rangefinder,” Proceedings of the IEEE International Conference on Intelligent Robots and Automation, vol. 3, pp. 2538-2543, 2000.
【6】J. Vandorpe, H. Van Brussel, and H. Xu, “Exact Dynamic Map Building for a Mobile Robot using Geometrical Primitives Produced by a 2D Range Finder,” Proceedings of the IEEE International Conference on Robotics and Automation, pp. 901-908, 1996.
【7】G. M. Youngblood, L. B. Holder, and D. J. Cook, “A Framework for Autonomous Mobile Robot Exploration and Map Learning Through the Use of Place-Centric Occupancy,” Proceedings of the ICML Workshop on Machine Learning of Spatial Knowledge, 2000.
【8】R. Baath, and B. Johansson, “Making a map-making robot: Using the IKAROS System to Implement the Occupancy Grid Algorithm,” Proceedings of the Swedish Artificial Intelligence Society Workshop, 2010.
【9】Geovany Araujo Borges, and Marie Jose Aldon, “Line Extraction in 2D Range Images for Mobile Robotics,” Proceedings of the Journal of Intelligent and Robotic Systems, vol. 40, pp. 267-297, 2004.
【10】A. Jain, M. Marty, and P. Flynn, “Data Clustering：A Review,” Proceedings of the ACM Comput. Surveys, vol. 31(3), pp. 264-323, 1999.
【11】J. B. MacQueen, “Some Methods for Classification and Analysis of Multivariate Observations,” Proceedings of the 5-th Berkeley Symposium on Mathematical Statistics and Probability, Berkeley, University of California Press, pp. 1:281-297, 1967.
【12】P. S. Bradley, and U. M. Fayad, “Refining initial points for k-means clustering,” Proceedings of the 15th Int. Conf. on Machine Learning, Morgan Kaufmann Press, pp. 91-99, 1998.
【13】Shi Na, Liu Xu-min, and Guan Yong, “Research on K-means Clustering Algorithm：An Improved K-means Clustering Algorithm,” Proceedings of the Third International Symposium on Intelligent Information Technology and Security Informatics, IITSI, pp. 63-67, 2010.
【14】馬秀蘭, 吳德邦, “統計學 : 以Microsoft Excel為例, ” 新文京開發出版股份有限公司, 第五版, 2008.
【15】Correlation and Dependence
http://en.wikipedia.org/wiki/Correlation_and_dependence
【16】Young D. Kwon, and Jin S. Lee, “A Stochastic Environment Modeling Method for Mobile Robot by using 2-D Laser Scanner,” Proceedings of the IEEE International Conference on Robotics and Automation, pp. 1688-1693, 1997.
【17】Viet Nguyen, Agostino Martinelli, Nicola Tomatis, and Roland Siegwart, “A Comparison of Line Extraction Algorithms using 2D Laser Rangefinder for Indoor Mobile Robotics,” Proceedings of the IEEE International Conference on Intelligent Robots and Systems, pp. 1929-1934, 2005.
【18】Theodosios Pavlidis, and Steven L. Horowitz, “Segmentation of Plane Curves,” Proceedings of the IEEE Transactions on Computers, pp. 860-870, 1974.
【19】Ali Siadat, Axel Kaske, Siegfried Klausmann, Michel Dufaut, and Rene Husson, “An Optimized Segmentation Method for a 2D Laser-Scanner Applied to Mobile Robot Navigation,” Proceedings of the 3rd IFAC Symposium on Intelligent Components and Instruments for Control Applications, 1997.
【20】G.A. Borges, and M. J. Aldon, “A Split-and-Merge Segmentation Algorithm for Line Extraction in 2-D Range Images,” Proceedings of the 15th Int. Conf. on Pattern Recognition, Barcelona, 2000.
【21】Ahad Harati, and Roland Siegwart, “A New Approach to Segmentation of 2D Range Scans into Linear Regions,” Proceedings of the IEEE International Conference on Intelligent Robots and Systems, pp. 2083-2088, 2007.
【22】吳柏彥, “應用LabVIEW虛擬儀控於環境地圖之建立,” 逢甲大學航太與系統工程研究所碩士論文,2009.
【23】黃源港, “應用LabVIEW虛擬儀控於環境地圖建立之最佳化, ” 逢甲大學航太與系統工程研究所碩士論文,2010.
【24】A. L. Schawlow, and C. H. Townes, “Infrared and Optical Masers,” Proceedings of the Phys. Rev., vol. 29, pp. 1940-1949, 1958.
【25】SICK Sensor Intelligence, “Product Information,” 2008.
【26】丁勝懋, “雷射工程導論,” 中央圖書出版社, 第二版, 1986.
【27】林建忠, “雷射測距技術與研究現況,” 光連雙月刊(OptoLink) , 19期, 30-33頁, 1999.
【28】Aloysius Wehr, and Uwe Lohr, “Airborne Laser Scanning—An Introduction and Overview,” Proceedings of the ISPRS Journal of Photogrammetry and Remote Sensing, vol. 54, pp. 68-82, 1999.
【29】黃文鈺, “RS-232串列設備連網解決方案—Serial To Ethernet,” 文魁資訊股份有限公司, 初版二刷, 2004.
【30】林蓬�, “LabVIEW 基礎程式設計及應用,” 全華科技圖書股份有限公司, 修訂三版, 2008.
【31】蕭子健, 王智昱, 儲昭偉, “虛擬儀控程式設計 LabVIEW 8X,” 高立圖書有限公司, 初版, 2007.
【32】王晉中, “MATLAB 7在工程上的應用,” 高立圖書有限公司,初版一刷, 2005.
【33】洪維恩, “MATLAB 7 程式設計, ” 旗標出版股份有限公司, 初版, 2005.
【34】陳冠羽, “應用LabVIEW虛擬儀控於環境地圖資料點擬合之分析, ” 逢甲大學航太與系統工程研究所碩士論文,2010.