本論文以增加狀態卡爾曼過濾器(augmented state Kalman filter, ASKF)建立視覺式同時定位與建圖系統。此SLAM系統的感測器使用單眼視覺系統為唯一的感測裝置，搭配加速強健特徵(speeded-up robust features, SURF)的偵測方法進行環境中影像特徵的偵測，並且依據影像訊息求算特徵在空間中的三維座標，以建立SURF特徵式地圖。對於特徵式地圖中有關資料關聯、資料新增、刪除與更新等問題，皆有提出本研究之解決策略。
本研究對SLAM系統所發展出的相關技術，對於地圖資料庫中的3D影像特徵，透過狄勞尼三角化(Delaunay triangulation)之理論建立有限的馬賽克(mosaic)網格，實現單眼視覺系統於運動中探知結構(structure from motion, SFM)的分析。
最後，本論文也提出實測範例，驗證所提方案的可行性。首先，使用單眼視覺實現具備未知輸入之系統的同時自我定位與特徵式地圖建立，同時也解決單眼視覺的影像深度量測問題。最後，整合ASKF估測方法、特徵式地圖管理策略與馬賽克方法，實現單眼視覺式在3D空間中同時定位、建圖與運動中探知結構之任務。

In this thesis, the visual simultaneous localization and mapping (SLAM) is established by using the augmented state Kalman filter (ASKF). The theory and methodology of vision sensing and state estimation system will be investigated in this thesis. First of all, the visual system is the only sensing device in the system. Meanwhile, the detection of image features, the speeded-up robust features (SURF) with high-dimensional description vectors are utilized to describe the map features, and build the feature-based map. In data association, a tracking window is planned based on the prediction of map features in spatial location, and then the nearest neighbor method is employed to match the high-dimensional descriptor vector of the measured features with that of the features in the map. Secondly, the ASKF is employed to predict and update the states of the robot and the features recursively. Furthermore, the procedures of adding, erasing and updating the data of the SURF in the map are planned. Finally, we use feature-based map to establish mosaicing by using Delaunay triangulation and present the structure from motion of monocular vision.

序言	                                              Ⅰ
中文摘要	                                              Ⅱ
英文摘要	                                              Ⅲ
目錄	                                              Ⅴ
圖目錄	                                              Ⅶ
表目錄	                                              Ⅷ
第1章	序論	                                      1
1.1	研究動機與研究目的     	                    1
1.2	文獻探討	                                      2
1.2.1	狀態估測器	                             2
1.2.2	影像特徵偵測、追蹤與描述	                    2
1.2.3	資料關聯	                                      3
1.2.4	運動中探知結構	                             3
1.2.5	運動中探知結構	                             4
1.3	研究範圍	                                      4
1.4	論文架構	                                      4
第2章	機器人ASKF SLAM	                             6
2.1 SLAM系統的運動模型	                             6
2.2 SLAM系統的量測模型	                             7
2.3 地圖特徵初始化	                                     10
2.4 建立環境地圖	                                     12
	    2.4.1 地圖特徵的偵測與描述	          12
	2.4.2 資料關聯問題與方法                                                      13
	2.4.3 刪除地圖特徵                                                      15
	2.4.4 新增地圖特徵                                                      16
2.5 特徵點的維度轉換	                             19
第3章	運動中探知結構	                             22
3.1馬賽克圖案資料的定義與更新	                    22
3.2環境結構的建立	                                      23
3.3 SFM系統架構	                                      24
第4章	ASKF MonoSLAM與SFM的應用	                    27
4.1 軟、硬體設備規格說明	                             27
4.2 系統啟動程序說明	                             28
4.3 實驗範例說明	                                      29
	4.3.1範例一：物件與環境之結構建立	           30
	4.3.2範例二：方型立體物件之結構建立                                                       35
	4.3.3範例三：室內區域環境之結構建立                                                       39
	4.3.4範例四：相異位置物件之結構建立                                                       44
4.4 結果分析	                                       48
第5章	研究成果與未來研究方向	                     49
5.1 研究成果	                                       49
5.2 未來研究方向	                                       49
參考文獻	                                                50
附錄A 擴張型卡爾曼過濾器	                              52
附錄B  Jacobian矩陣	                              53
B.1 機器人EKF SLAM：量測矩陣 細部推導                                                       53
B.2 機器人EKF SLAM：特徵初始化 矩陣細部推導                                                       57
B.3 機器人EKF SLAM：特徵點狀態轉換 矩陣細部推導                                                       59
附錄C  SURF影像區域特徵之偵測與追蹤	                    60
附錄D 佛洛以圖與狄勞尼三角形	                    64
D.1 佛洛以圖                                             64
D.2 狄勞尼三角形                                         65

圖目錄
圖2.1 透視投影法示意圖	                              9
圖2.2攝影機與特徵點三維示意圖	                    10
圖2.3 世界座標與初始攝影機座標示意圖	                    10
圖2.4角度 與 示意圖	                             11
圖2.5角度 與 示意圖	                             11
圖2.6 SURF描述向量                      	           13
圖2.7使用SURF方法所偵測的影像特徵	                    13
圖2.8特徵追蹤視窗	                                      14
圖2.9間隔視窗示意圖	                             17
圖2.10間隔視窗的例外情形	                             17
圖2.11建立環境地圖之流程圖	                             18
圖2.12視差角 示意圖	                             20
圖3.1馬賽克網格資料更新之範例說明	                    23
圖3.2建立全景影像	                                      24
圖3.3 SFM系統架構	                                      26
圖4.1預存在資料庫中的4個地圖標誌	                    28
圖4.2系統啟動：(a)資料關聯矢敗；(b)資料關聯成功	  29
圖4.3物件與環境結構建立的八張截圖	                    33
圖4.4物件與環境結構建立的馬賽克圖	                    35
圖4.5方型立體物件結構建立的六張截圖	                    37
圖4.6方型立體物件結構建立的馬賽克圖	                    39
圖4.7室內區域環境結構建立的八張截圖	                    42
圖4.8室內區域環境結構建構的馬賽克圖	                    44
圖4.9相異位置物件結構建立的六張截圖	                    46
圖4.10相異位置物件結構建立的馬賽克圖	                    48
圖C.1積分影像定義及積分影像應用	                    60
圖C.2  9X9盒子過濾器	                             61
圖C.3 SIFT與SURF尺度空間變化的差異	                    62
圖C.4特徵點的方位分配	                             62
圖C.5 Haar小波過濾器	                             63
圖C.6特徵點的特徵描述向量	                             63
圖D.1佛洛以圖示意圖	                             65
圖D.2不同的狄勞尼三角形圖形	                             65
圖D.3狄勞尼三角形檢測法示意圖	                    66
圖D.4狄勞尼三角形檢測法範例	                             67
圖D.5物件的輪廓	                                      67

表目錄
表2.1刪除地圖特徵	                                      15
表4.2筆記型電腦規格	                             27
表4.2前視型單眼攝影機規格	                             27

參考文獻

[1]	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.
[2]	J. Civera, A.J. Davison, J.A. Magallon, J. M. M. Montiel “Drift-Free Real-Time Sequential Mosaicing” International Journal of Computer Vision, vol. 81(2), pp. 128-137, February 2009.
[3]	R.H. Deaves, “Covariance bounds for augmented state Kalman filter application,” IEE Electronics Letters, vol.35, no.23, pp.2062-2063, 1999.
[4]	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.
[5]	D.G. Lowe, “Distinctive Image Features from Scale-Invariant Keypoints,” International Journal of Computer Vision, 60, 2, pp. 91-110, 2004.
[6]	H. Bay, A. Ess, T. Tuytelaars, L. Van Gool, “SURF: speeded up robust features,” Computer Vision and Image Understanding, vol.110, pp.346-359, 2008.
[7]	A. Baumberg, “Reliable feature matching across widely separated views,” Proceedings Computer Vision and Pattern Recognition, pp.774-781, 2000.
[8]	K. Mikolajczyk, and C. Schmid, “A performance evaluation of local descriptors,” Proceedings Computer Vision and Pattern Recognition, pp.257-263, 2003.
[9]	J. Shi, and C. Tomasi, “Good Features to Track,” IEEE Conference on Computer Vision and Pattern Recognition, pp 593-600, 1994.
[10]	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.
[11]	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.
[12]	K. Mikolajczyk, and C. Schmid, “Indexing based on scale invariant interest points,” Proceedings of International Conference on Computer Vision, vol.1, pp.525-531, 2001.
[13]	G. Shakhnarovich, T. Darrell, and P. Indyk, “Nearest-neighbor methods in learning and vision,” MIT Press, 2005.
[14]	Intel, website: http://en.wikipedia.org/wiki/Delaunay_triangulation (2010/02/04)
[15]	OpenCV, Intel, website: http://opencv.willowgarage.com/wiki/ (2010/02/04)
[16]	Intel, website: http://www.cs.wustl.edu/~pless/546/lectures/L11.html (2010/02/04)
[17]	L. J. Guibas and J. Stolfi, 1985, “Primitives for the Manipulation of General Subdivisions and the Computation of Voronoi Diagrams,” ACM Transactions on Graphics vol. 4, no. 2, pp.74-123, April 1985.
[18]	R. Szeliski and H. Shum. “Creating full view panoramic image mosaics and enviorment maps,” In Proc SIGRAPH, pp 251-258, 1997.
[19]	R. Marks, S. Rock, and M. Lee. “Real-time video mosaicking of the ocean flooor,”. IEEE Journal of Oceanic Engineering, vol.20,no.3, pp 229-241, Jul 1995.
[20]	Wu, C., Sun, Y., Chang, C.: “Three-dimension modeling from endoscopic video using geometric constrains via feature positioning,” IEEE Transactions on Biomedical Engineering vol.54, no7, 2007
[21]	O.G. Grasa, J. Civera, A. Guemes, V. Munoz, and J.M.M Montiel, “EKF Monocular SLAM 3D Modeling, Measuring and Augmented Reality from Endoscope Image Sequences,” 5th Workshop on Augmented Environments for Medical Imaging including Augmented Reality in Computer-Aided Surgery; held jointly with 12th International Conference on Medical Image Computing and Computer Assisted Intervention, (MICCAI2009), London (UK), 2009.
[22]	洪敦彥，基於擴張型卡爾曼過濾器的機器人視覺式同時定位、建圖與移動物體追蹤，淡江大學機械與機電工程學系碩士論文，2010。
[23]	鄭聖賢，機器人單眼視覺式同時定位與建圖的資料關聯問題研究，淡江大學機械與機電工程學系碩士論文，2010。