本論文以加速強健特徵(SURF)建立擴張型卡爾曼過濾器(EKF)為基礎的視覺式同時定位與建圖(SLAM)所需之稀疏與續存性地圖。SURF是尺度與方向不變的特徵，在移動攝影機所擷取的序列影像中，相較其他方法所偵測的特徵，具有重現性高的優點，適合做為SLAM的地圖特徵。本論文的研究議題包括三個部份：第一部份修改SURF特徵的偵測、描述與比對程序，提高影像處理的運算速度與特徵比對的成功率。第二部份規劃有效率的資料關聯與地圖管理策略，提高機器人狀態估測的準確率。第三部份使用兩個攝影機做為SLAM感測器，左攝影機進行影像平面上預測與估測特徵的狀態，新增特徵時則使用左右攝影機所構成的立體視覺求算影像深度，加速新增特徵的初始化。所發展的演算法最後整合成為雙眼視覺式EKF SLAM系統，也在室內環境中成功測試系統的基本功能、地面基準的誤差、路徑閉合的現象、以及長距離執行SLAM任務的能力。

In this thesis, a sparse and persistent map is established using the method of speeded-up robust features (SURF) and applied on the visual simultaneous localization and mapping (SLAM) based on the extended Kalman filter (EKF). Since SURF are scale- and orientation-invariant features, they have higher repeatability than that of the features obtained by other detection methods. Even in the cases of using moving camera, the SURF method can robustly extract image features from the image sequences. Therefore, it is suitable to be utilized as the map features in SLAM. The research topic of this thesis consists of three parts: first, the procedures of detection, description and matching of the SURF method are modified to improve the image processing speed and feature recognition rate. Second, the effective procedures of data association and map management for EKF SLAM are designed to improve the accuracy of robot state estimation. Finally, two cameras are employed as the only sensor of the SLAM system. The state prediction and estimation of features on image plane is performed using only the left camera. When new features are going to be added to the map, the image depth of these new features are calculated using a stereo vision formed by the left and right cameras. The EKF SLAM with SURF-based map is developed and implemented on a binocular vision system. The integrated system has successfully tested the basic capabilities of SLAM system, including ground truth and loop closure, as well as the ability of navigating over a long distance in indoor environments.

目錄
中文摘要	Ⅰ
英文摘要	Ⅱ
目錄	Ⅳ
	圖目錄	Ⅵ
	表目錄	Ⅸ
第1章 序論	1
1.1 研究動機與研究目的	1
1.2 文獻探討	1
1.3 研究範圍	2
第2章 SURF特徵偵測、描述與比對	4
2.1 影像特徵偵測、描述、與比對	4
2.2 靜態場景實驗設計	8
2.3 最小尤基里德距離門檻值dmatch設定程序	25
2.4 本章結論	26
第3章 雙眼視覺EKF SLAM	27
3.1 擴張型卡爾曼過濾器	27
3.2 狀態運動模型	28
3.3 單眼視覺量測模型	29
3.4 地標初始化	32
3.5 資料關聯與地圖管理策略	35
3.5.1 建立影像特徵資訊	35
3.5.2 資料關聯程序	36
3.5.3 刪除地標策略	37
3.5.4 新增地標策略	38
3.5.5 動態Dthreshold值調整機制	39
3.6 系統流程	39
3.7 本章結論	40
第4章 測試結果與分析	41
4.1 範例一：SLAM系統功能	43
4.2 範例二：地面基準(ground truth)	50
4.3 範例三：室內環境原地旋轉SLAM	54
4.4 範例四：室內環境繞行櫃子SLAM	60
4.5 範例五：圖書館環境長距離SLAM	66
4.6 範例六：圖書館環境繞行書櫃SLAM	74
4.7本章結論	82
第5章 研究成果與未來研究方向	83
5.1 研究成果	83
5.2 未來研究方向	83
參考文獻	84
附錄A Jacobian矩陣	86
A.1 EKF SLAM單眼視覺量測矩陣Hk細部推導	86

圖目錄
圖2.1 盒子濾波器	5
	圖2.2 音階層數與盒子濾波器尺寸關係圖	5
	圖2.3 低音階特徵偵測	5
	圖2.4 高音階特徵偵測	5
	圖2.5 Haar小波濾波器	6
	圖2.6 特徵方向定義	6
	圖2.7 64維描述向量	7
	圖2.8 中心2×2子區域	7
	圖2.9 16維描述向量	7
	圖2.10 範例圖片	9
	圖2.11 間隔視窗	9
	圖2.12 地圖特徵	9
	圖2.13 地圖特徵影像	10
	圖2.14 被比對影像	10
	圖2.15 Dthreshold值差異測試	10
	圖2.16 各層音階之特徵偵測	11
	圖2.17 Octaves值差異測試	12
	圖2.18 描述向量計算時間	13
	圖2.19 節省時間百分比	13
	圖2.20 比對結果分析圖	15
	圖2.21 特徵比對時間	16
	圖2.22 比對結果分析圖	17
	圖2.23 特徵比對時間	18
	圖2.24 搜尋視窗	19
	圖2.25 比對結果分析圖	20
	圖2.26 比對結果分析圖	21
	圖2.27 比對結果分析圖	23
	圖2.28 比對結果分析圖	24
	圖2.29 實驗室環境	25
	圖2.30 圖書館環境	26
	圖3.1 新增地標狀態與共變異數	29
	圖3.2 刪除地標狀態與共變異數	29
	圖3.3 透視投影法	31
	圖3.4 左攝影機與地標相對位置	32
	圖3.5 世界座標與初始左攝影機座標相對位置	32
	圖3.6 標準立體視覺幾何架構	33
	圖3.7 左右影像地標特徵比對	34
	圖3.8 雙眼攝影機與地標相對位置	34
	圖3.9 雙眼攝影機視線向量	34
	圖3.10 地標投影	36
	圖3.11 搜尋視窗	36
	圖3.12 動態搜尋視窗	37
	圖3.13 間隔視窗	38
	圖3.14 雙眼視覺EKF SLAM系統流程圖	40
	圖4.1 雙眼立體視覺系統	41
	圖4.2 解說圖	43
	圖4.3 SLAM系統功能二十一張截圖	49
	圖4.4 地面基準路徑圖	50
	圖4.5 地面基準實驗結果上視地圖	51
	圖4.6 地面基準實驗結果上視地圖	52
	圖4.7 地面基準實驗結果上視地圖	52
	圖4.8 地面基準實驗結果上視地圖	53
	圖4.9 室內環境原地旋轉SLAM十一張截圖	57
	圖4.10 室內環境原地旋轉SLAM結果圖	58
	圖4.11 地圖地標數與系統取樣頻率	59
	圖4.12 攝影機三維位置標準差	59
	圖4.13 實驗室繞行環境	60
	圖4.14 室內環境繞行櫃子SLAM十一張截圖	63
	圖4.15 室內環境繞行櫃子SLAM結果圖	64
	圖4.16 地圖地標數與系統取樣頻率	65
	圖4.17 攝影機三維位置標準差	65
	圖4.18 圖書館環境長距離SLAM九張截圖	71
	圖4.19 圖書館環境長距離SLAM結果圖	72
	圖4.20 地圖地標數與系統取樣頻率	73
	圖4.21 攝影機三維位置標準差	73
	圖4.22 圖書館環境繞行書櫃SLAM十九張截圖	79
	圖4.23 圖書館環境繞行書櫃SLAM結果圖	80
	圖4.24 地圖地標數與系統取樣頻率	81
	圖4.25 攝影機三維位置標準差	81

表目錄
表2.1 前視型單眼攝影機規格表	9
	表2.2 筆記型電腦規格表	9
	表2.3 Dthreshold值差異測試	11
	表2.4 Octaves值差異測試	12
	表2.5 描述向量差異測試	14
	表3.1 地標資料關聯狀況	38
	表4.1 左攝影機內部參數	41
	表4.2 右攝影機內部參數	42
	表4.3 左影像修正模型參數	42
	表4.4 右影像修正模型參數	42

[Bay et al. 2008] H. Bay, A. Ess, T. Tuytelaars and L. Van Gool, “SURF: Speeded-Up Robust Features”, Computer Vision and Image Understanding, vol.110, pp.346-359, 2008.

[Bouguet 2010] J.Y. Bouguet, Camera Calibration Toolbox for Matlab, http://www.vision.caltech.edu/ bouguetj/calib_doc/, 2010.

[Civera et al. 2008] J. Civera, A.J. Davison and J.M.M. Montiel, “Inverse Depth Parametrization for Monocular SLAM”, IEEE Transactions on Robotics, vol.24, no.5, pp.932-945, 2008.

[Davison et al. 2007] A.J. Davison, I.D. Reid, N.D. Molton and O. Stasse, “MonoSLAM: Real Time Single Camera SLAM”, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol.29, no.6, pp.1052-1067, 2007.

[Gil et al. 2010] A. Gil, O.M. Mozos, M. Ballesta and O. Reinoso, “A comparative evaluation of interest point detectors and local descriptors for visual SLAM”, Machine Vision and Applications, vol.21, pp.905-920, 2010.

[Harris and Stephens 1988] C. Harris and M. Stephens, “A combined corner and edge detector”, In Proceedings of the 4th Alvey Vision Conference, pp.147-151, 1988.

[Hutchinson et al. 1996] S. Hutchinson, G.D. Hager and P.I. Corke, “A Tutorial on Visual Servo Control”, IEEE Transactions on Robotics and Automation, vol.12, no.5, pp.651-670, 1996.

[Karlsson et al. 2005] N. Karlsson, E. Di Bernardo, J. Ostrowski, L. Goncalves, P. Pirjanian and M.E. Munich, “The vSLAM Algorithm for Robust Localization and Mapping”, In Proceedings of the IEEE International Conference on Robotics and Automation, pp.24-29, 2005.

[Lindeberg 1998] T. Lindeberg, “Feature detection with automatic scale selection”, International Journal of Computer Vision, vol.30, no.2, pp79-116, 1998.

[Lowe 2004] D.G. Lowe, “Distinctive Image Features from Scale-Invariant Keypoints”, International Journal of Computer Vision, vol.60, no.2, pp. 91-110, 2004.

[Lucas and Kanade 1981] B.D. Lucas and T. Kanade, “An Iterative Image Registration Technique with an Application to Stereo Vision”, International Joint Conference on Artificial Intelligence, pp.674-679, 1981.

[Murillo et al. 2007] A.C. Murillo, J.J. Guerrero and C. Sagues, “SURF features for efficient robot localization with omnidirectional images”, In Proceedings of the IEEE International Conference on Robotics and Automation, pp.3901-3907, 2007.

[Paz et al. 2008] L.M. Paz, P. Pinies, J.D. Tardos and J. Neira, “Large-Scale 6-DOF SLAM with Stereo-in-Hand”, IEEE Transactions on Robotics, vol.24, no.5, pp.946-957, 2008.

[Sciavicco and Siciliano 1996] L. Sciavicco and B. Siciliano, “Modeling and Control of Robot Manipulators”, McGraw-Hill, 1996.


[Shakhnarovich et al. 2005] G. Shakhnarovich, T. Darrell and P. Indyk, “Nearest-neighbor methods in learning and vision”, The MIT Press, 2005.

[Smith et al. 1990] R. Smith, M. Self and P. Cheeseman, “Estimating Uncertain Spatial Relationships in Robotics,” In Autonomous Robot Vehicles, I.J. Cox and G.T. Wilfong, Eds., Springer-Verlog, pp.167-193, 1990.

[Sola et al. 2008] J. Sola, A. Monin, M. Devy and T. Vidal-Calleja, ”Fusing Monocular Information in Multicamera SLAM”, IEEE Transactions on Robotics, vol.24, no.5, pp.958-968, 2008.

[Viola and Jones 2001] P.A. Viola and M.J. Jones, “Rapid object detection using a boosted cascade of simple features”, In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp.511-518, 2001.

[Wang et al. 2011] Y.T. Wang, D.Y. Hung, and C.H. Sun, “Improving Data Association in Robot SLAM with Monocular Vision”, Journal of Information Science and Engineering, vol.27, pp.1-15, 2011.

[Williams et al. 2007] B. Williams, G. Klein and I. Reid, “Real-Time SLAM Relocalisation”, In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp.511-518, 2007.

[Wu and Fu 2007] C.Y. Wu and L.C. Fu, “An integrated robotic vSLAM system to realize exploration in large indoor environment”, In Proceedings of the CACS International Automatic Control Conference, 2007.

[洪敦彥 2010] 洪敦彥，基於擴張型卡爾曼過濾器的機器人視覺式同時定位、建圖、與移動物體追蹤，淡江大學機械與機電工程學系碩士論文，2010。

[邱明璋 2011] 邱明璋，基於極線限制條件之單眼視覺式移動物體偵測與追蹤，淡江大學機械與機電工程學系碩士論文，2011。