本論文針對視覺自主之小型人形機器人提出一個在RoboCup足球場上基於人形機器人視覺之定位方法。在Linux環境下，以機器人作業系統(Robot Operating System, ROS)建構人形機器人的定位架構，在視覺方面，本論文利用邊緣偵測與拉普拉斯轉換(Laplace transform)進行影像前處理，接著透過掃描線來找出場地線上的特徵點，並利用逆透視映射法(Inverse Perspective Mapping, IPM)計算出特徵點與機器人間的距離，以此作為定位所需的觀測資訊。在定位系統中，本論文使用蒙地卡羅定位(Monte-Carlo Localization, MCL)作為其主要架構，並改進其三大問題：(1)粒子數量的調整、(2)陷入區域最佳解、(3)機器人綁架。粒子數量的多寡會影響蒙地卡羅定位的速度，本論文利用KL散度(Kullback-Leibler Divergence, KLD)根據定位對環境的相似度來調整粒子數量；為了解決區域最佳解問題，本論文使用競爭選取法(Tournament Selection)作為蒙地卡羅定位重新取樣的方法，該採樣方式可有效使蒙地卡羅定位在搜尋位置時保持粒子的多樣性；機器人綁架為機器人定位常見的問題，本論文採用Augmented-MCL中的方法來解決此問題，藉由加入滑動平均(moving average)來解決機器人綁架問題。綜合以上三點，本論文提出一種改良型蒙地卡羅定位法來解決以上三種問題。從實驗結果可知，改良型蒙地卡羅定位可以有效地解決以上三種問題。

In this thesis, a localization system is proposed to implement on RoboCup soccer field for vision-based autonomous small-sized humanoid robot. In the Linux environment, Robot Operating System (ROS) is used to establish the localization system for the humanoid robot system. In visual system, edge detection and Laplace transform are used for image preprocessing, and Inverse Perspective Mapping (IPM) is used to calculate the distance between the feature point and robot. In localization system, Monte-Carlo Localization (MCL) is used for the main algorithm, but there are three problems need to improve in MCL: (1) the adjustment of the number of particles, (2) the local optimal solution, and (3) the robot kidnapped. Kullback-Leibler Divergence (KLD) is used to adjust the number of particles according to the similarity of localization and environment. In order to solve the problem of local optimal solution, Tournament Selection is used as the method of resampling in MCL. In order to solve robot kidnapped, the method in Augmented-MCL is used to solve the robot kidnapped by adding moving average. Base on the above three points, Improved Monte-Carlo Localization (IMCL) is proposed to solve the three problems in this thesis. In the experimental results, IMCL can effectively solve the three problems.

中文摘要 I
英文摘要 II
目錄	III
圖目錄	VI
表目錄	IX
第一章	緒論 1
1.1	研究背景 1
1.2	研究動機 2
1.3	論文架構 4
第二章	人形機器人之平台介紹 5
2.1	前言 5
2.2	人形機器人機構介紹 6
2.3	人形機器人核心控制板介紹 9
2.3.1	IPC工業電腦 9
2.3.2	SoC FPGA開發板 10
2.4	人形機器人電路介紹 11
2.4.1	四肢馬達控制訊號 12
2.4.2	頭部馬達控制訊號 12
2.4.3	感測器資訊接收 13
第三章	人形機器人之系統架構 16
3.1	前言 16
3.2	影像處理模組 17
3.2.1	影像擷取 18
3.2.2	圖像增強 19
3.2.3	背景濾除 22
3.2.4	影像二值化 23
3.2.5	侵蝕膨脹 24
3.2.6	Canny邊緣偵測 26
3.2.7	搜尋白線特徵點 27
3.3	策略與資料收送 29
第四章	人形機器人之影像定位 30
4.1	前言 30
4.2	蒙地卡羅定位 30
4.3	改良型蒙地卡羅定位 33
4.3.1	粒子數量的調整 34
4.3.2	陷入區域最佳解 39
4.3.3	機器人綁架 43
4.3.4	定位流程與步驟 47
4.4	定位應用 50
4.4.1	觀測模型 50
4.4.2	運動模型 61
第五章	實驗結果 63
5.1	前言 63
5.2	粒子數量調整與程式效能之關係 63
5.3	區域最佳解 65
5.4	機器人綁架 68
5.5	定位實驗 69
5.5.1	原地定位 69
5.5.2	動態定位 72
第六章	結論與未來展望 75
參考文獻 76
圖目錄
圖2.1、人形機器人機構設計與尺寸圖 8
圖2.2、人形機器人之馬達位置配置 8
圖2.3、IPC工業電腦實體圖 9
圖2.4、SoC FPGA開發板實體圖 10
圖2.5、轉接電路板實體圖 11
圖2.6、四肢馬達控制訊號流程圖 12
圖2.7、頭部馬達控制訊號流程圖 13
圖2.8、感測器資訊接收訊號流程圖 15
圖3.1、第十一代小型人形機器人系統架構圖 17
圖3.2、拉普拉斯運算卷積核 20
圖3.3、本論文使用之拉普拉斯運算卷積核 21
圖3.4、圖像增強結果 21
圖3.5、背景濾除流程 22
圖3.6、背景濾除結果 23
圖3.7、影像二值化結果 24
圖3.8、影像膨脹示意圖 25
圖3.9、影像侵蝕示意圖 25
圖3.10、侵蝕膨脹結果 26
圖3.11、邊緣偵測結果 27
圖3.12、搜尋白線特徵點流程 28
圖3.13、尋找白線特徵點結果 29
圖4.1、蒙地卡羅定位流程 33
圖4.2、KLD採樣之虛擬程式碼 38
圖4.3、輪盤法示意圖 39
圖4.4、競爭選取法示意圖 41
圖4.5、競爭選取法之虛擬程式碼 42
圖4.6、Augmented-MCL中解決機器人綁架之虛擬程式碼 46
圖4.7、改良型蒙地卡羅定位流程 49
圖4.8、Robocup足球賽場地 50
圖4.9、攝影機與地面幾何關係示意圖 51
圖4.10、影像畫面與地面幾何關係示意圖 52
圖4.11、人形機器人側視示意圖 53
圖4.12、人形機器人正前方距離測量誤差 56
圖4.13、人形機器人左右兩邊距離測量誤差 57
圖4.14、可視範圍示意圖 58
圖4.15、特徵點位置示意圖 59
圖4.16、模擬觀測結果 60
圖5.1、執行效能比較 64
圖5.2、兩種定位演算法陷入區域最佳解之比較 67
圖5.3、機器人綁架恢復結果 68
圖5.4、原地定位位置圖 69
圖5.5、最大距離誤差比較 70
圖5.6、平均距離誤差比較 71
圖5.7、行走路徑示意圖 72
圖5.8、人形機器人實際位置與定位位置比較 73 
表目錄
表2.1、第十一代小型人形機器人規格 5
表2.2、MX-64與XM430馬達比較 7
表2.3、IPC工業電腦規格 10
表2.4、SoC FPGA開發板規格 11
表2.5、GY-87規格表 14
表2.6、TAL230A規格表 14
表3.1、C922網路攝影機規格 18
表3.2、邊緣偵測的OpenCV函式列表 26
表4.1、輪盤法採樣範例 40
表4.2、競爭選取法之取樣結果 43
表4.3、人形機器人正前方測量距離誤差表 55
表4.4、人形機器人左右兩邊距離測量誤差表 56
表5.1、粒子數量與執行速率關係 64
表5.2、陷入區域最佳解之權重與誤差關係 66
表5.3、人形機器人實際位置與定位位置之誤差 73

[1]R. E. Kalman, “A new approach to linear filtering and prediction problems,” Trans. of the ASM-Journal of basic engineering, no. 82, pp. 34-45, Mar. 1960.
[2]D. Fox, W. Burgard, and S. Thrun, “Markov localization for mobile robots in dynamic environments,” Journal of Artificial Intelligence Research, vol. 11, pp. 391-427, 1999.
[3]F. Dellaert, D. Fox, W. Burgard, and S. Thrun, “Monte Carlo localization for mobile robots,” Proceedings 1999 IEEE International Conference on Robotics and Automation, Detroit, MI, USA, vol. 2, pp. 1322-1328, 10-15 May 1999.
[4]S. J. Russell and P. Norvig, “Probabilistic reasoning over time,” Artificial Intelligence: A Modern Approach, Upper Saddle River, vol. 15, pp. 566-609, 2003.
[5]J. K. David, T. Ernst, and O. B. Thomas, “Stereovision and navigation in building for mobile robots,” IEEE Transaction on Robotics and Automation, vol. 5, no. 6, pp. 792-803, Dec. 1989.
[6]H. S. Baek, J. M. Choi, and B. S. Lee, “Improvement of distance measurement algorithm on stereo vision system (SVS),” International Conference on Ubiquitous Information Technologies and Applications, Sanya, China, no. 5678176, pp. 1-3, 16-18 Dev. 2010.
[7]Y. Matsumoto, K. Ikeda, M. Inaba, and H. Inoue, “Visual navigation using omnidirectional view sequence,” IEEE/RSJ International Conference on Intelligent Robots and Systems, Kyongju, South Korea, vol. 1, pp. 317-322, 17-21 Oct. 1999.
[8]J. Huber and V. Graefe, “Motion stereo for mobile robots,” IEEE Transactions on Industrial Electronics, vol. 41, pp. 378-383, 1994.
[9]T. Li, S. Sun, and J. Duan, “Monte Carlo localization for mobile robot using adaptive particle merging and splitting technique,” IEEE International Conference on Information and Automation, Harbin, China, pp. 1913-1918, 20-23 Jun. 2010.
[10]D. Fox, “Adapting the sample size in particle filters through KLD-sampling,” The international Journal of robotics research, vol. 22, no. 12, pp. 985-1003, 2003.
[11]T. Li, S. Sun, and T. P. Sattar, “Adapting sample size in particle filters through KLD-resampling,” Electronics Letters, vol. 49, no. 12, pp. 740-742, 6 Jun 2013.
[12]A. C. Almeida, S. R. J. Neto, and R. A. C. Bianchi, “Comparing vision-based Monte-Carlo localization methods,” Latin American Robotic Symposium, Brazilian Symposium on Robotics and Workshop on Robotics in Education, Joao Pessoa, pp. 437-442, 2018.
[13]C. C. Hsu, C. C. Wong, H. C. Teng, and C. Y. Ho, “Localization of mobile robots via an enhanced particle filter incorporating tournament selection and nelder-mead simplex search,” International Journal of Innovative Computing, Information and Control, vol. 7, no. 7A, pp. 3725-3737, Jul. 2011.
[14]黎乃仁，結合單體搜尋法之改良式粒子濾波器及其在非線性函數追蹤及機器人定位之研究，淡江大學電機工程學系碩士論文(指導教授：許陳鑑)，2009。
[15]郭家瑞，增強型蒙地卡羅定位法及其在單板電腦之實現，臺灣師範大學應用電子科技學系碩士論文(指導教授：許陳鑑)，2014。
[16]J. -S. Gutmann and D. Fox, “An experimental comparison of localization methods continued,” IEEE/RSJ International Conference on Intelligent Robots and Systems, Lausanne, Switzerland, vol. 1, pp. 454-459, 30-4 Oct. 2002.
[17]T. Kwon, J. Yang, J. Song, and W. Chung, “Eifficiency improvement in Monte Carlo localization through topological information,” IEEE/RSJ International Conference on Intelligent Robots and Systems, Beijing, China, pp. 424-429, 9-15 Oct. 2006.
[18]L. Zhang, R. Zapata, and P. Lépinay, “Self-adaptive Monte Carlo localization for mobile robots using range sensors,” IEEE/RSJ International Conference on Intelligent Robots and Systems, St. Louis, USA, pp. 1541-1546, 11-15 Oct. 2009
[19]L. Zhang, R. Zapata, and P. Lepinay, “Self-adaptive Monte Carlo for single-robot and multi-robot localization,” IEEE International Conference on Automation and Logistics, Shenyang, China, pp.1927-1933, 5-7 Aug. 2009.
[20]ROBOTIS, URL: http://www.robotis.us/
[21]C. Topal, C. Akınlar, and Y. Genç, “Edge drawing: a heuristic approach to robust real-time edge detection,” IEEE International Conference on Pattern Recongnition, Istanbul, Turkey, pp. 2424-2427, 23-26 Aug. 2010.
[22]M. S. Arulampalam, S. Maskell, N. Gordon, and T. Clapp, “A tutorial on particle filters for online nonlinear/non-Gaussian Bayesian tracking,” IEEE Transaction on Signal Processing, vol. 50, no. 2, pp.174-188, Feb. 2002.
[23]J. Baltes, C. T. Cheng, M. C. Lau, and A. Espinola, “Real-time navigation for a humanoid robot using particle filter,” ICETI Applied Mechanics and Materials, Kaohsiung, Taiwan, vol. 284-287, pp. 1914-1918, 02 Nov. 2012.
[24]N. Metropolis, and S. Ulam, “The Monte Carlo method,” Journal of the American Statistical Association, vol. 44, no. 247, pp. 335-341, 1949.
[25]N. J. Gordon, D. J. Salmond, and A. F. Smith, “Novel approach to nonlinear/non-Gaussian Bayesian state estimation,” IEE Proceedings F - Radar and Signal Processing, vol. 140, no. 2, pp. 107-113, 1993.
[26]J. S. Liu and R. Chen, “Sequential Monte Carlo methods for dynamic systems,” Journal of the American Statistical Association, vol. 93, no. 443, pp. 1032-1044, 1998.
[27]J. A. Rice, “Distributions derived from the normal distribution,” Mathematical Statistics and Data Analysis, vol. 6, pp. 192-198, 1995.
[28]N. Johnson, S. Kotz, and N. Balakrishnan, “Continuous univariate distributions,” John Wiley & Sons, New York, vol. 1, 1994.
[29]J. E. Baker, “Reducing bias and inefficiency in the selection algorithm,” Proceedings of the Second International Conference on Genetic Algorithms and their Application, pp. 14-21, Oct. 1987.
[30]B. L. Miller and D. E. Goldberg, “Genetic algorithms, selection schemes, and the varying effects of noise,” Evolutionary Computation, vol. 4, no. 2, pp. 113-131, Jun. 1996.
[31]S. Lenser and M. Veloso, “Sensor resetting localization for poorly modeled mobile robots,” IEEE International Conference on Robotics and Automation, San Francisco, vol. 2, pp. 1225-1232, 24-28 Apr. 2000.
[32]簡瑜萱，基於ROS之人形機器人的影像定位與導航，淡江大學電機工程學系碩士論文(指導教授：翁慶昌)，2017。
[33]A. C. Almeida, A. H. R. Costa, and R. A. C. Bianchi, “Vision-based Monte-Carlo Localization for humanoid soccer robots,” Latin American Robotics Symposium and Brazilian Symposium on Robotics, Curitiba, pp. 1-6, 2017.
[34]溫泯毅，視覺自主人形機器人之定位與導航，淡江大學電機工程學系碩士論文(指導教授：翁慶昌、鄭吉泰)，2016。