本論文規劃單眼視覺式同時定位與建圖(simultaneous localization and mapping, SLAM)系統的地圖建立程序，處理包括影像特徵偵測方法以及量測與地圖的資料關聯等問題。影像特徵偵測方面，將偵測快速強健特徵(Speeded-Up Robust Features, SURF)，以高維度特徵描述向量描述地圖特徵，並且建立特徵式地圖。資料關聯方面，將以地圖特徵在空間位置的預測規劃追蹤視窗，再使用最鄰近(nearest-neighbor, NN)方法進行量測資料與地圖特徵的高維度特徵描述向量之搜尋比對，也將使用Lucas-Kanade演算法輔助在影像平面上的特徵之追蹤。最後，也將擴充所發展的單眼視覺式SLAM系統之功能，使之具備偵測與追蹤移動物體(detection and tracking of moving object, DATMO)的功能，可以執行同時定位、建圖、與移動物體追蹤(simultaneous localization mapping, and moving object tracking, SLAMMOT)的任務。

In this thesis, the algorithms of map building are developed for a simultaneous localization and mapping (SLAM) system with monocular vision. The algorithms include the method of feature detection and data association in between the measured features and features in the map. For 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. The Lucas-Kanade algorithm is also utilized to improve the performance of feature tracking in the image plane. Finally, the developed SLAM system with monocular vision is integrated with the function module of detection and tracking of moving objects (DATMO), in order to perform the tasks of simultaneous localization mapping, and moving object tracking (SLAMMOT).

目錄
中文摘要	I
英文摘要	II
目錄	III
圖目錄	V
表目錄	IX
第1章 序論	1
1.1 研究動機與研究目的	1
1.2 文獻探討	1
1.2.1影像特徵偵測與描述的相關文獻	1
1.2.2資料關聯與特徵追蹤的相關文獻	2
1.3 研究範圍	3
1.4 論文架構	3
第2章 SLAM的資料關聯問題	4
2.1  EKF SLAM	4
2.2 運動模型與感測模型	4
2.3 特徵式地圖建立	6
2.4 資料關聯問題	7
2.4.1 資料關聯方法	7
2.4.2  Lucas-Kanade光流演算法	10
2.5 實測結果	12
2.5.1 影像特徵比對實測	13
2.5.2 資料關聯實測	16
2.5.3  MonoSLAM實測	19
2.6 本章結論	22
第3章 單眼視覺式SLAMMOT	23
3.1  SLAMMOT系統的地圖管理	23
3.1.1 單眼視覺影像特徵初始化	24
3.2  SLAM with GO	27
3.3  SLAM with DATMO	27
3.3.1  SLAM with DATMO的系統流程	28
3.4 實測範例	29
3.5 本章結論	34
第4章 研究成果與未來研究方向	35
4.1 研究成果	35
4.2 未來研究方向	36
參考文獻	37
附錄A  SURF影像區域特徵之偵測與追蹤	39
附錄B  Lucas-Kanade光流演算法	43
B.1 遞迴式光流計算方法	46
B.2  Lucas-Kanade光流演算法流程	49


圖目錄
圖2.1 SURF描述向量	7
圖2.2 使用SURF方法所偵測的影像特徵	7
圖2.3 特徵追蹤視窗	8
圖2.4 資料關聯方法流程圖	9
圖2.5 特徵相近排除示意圖	10
圖2.6 (a)未排除過近的地圖特徵	10
圖2.6 (b)排除過近的地圖特徵	10
圖2.7 地圖特徵位置示意圖	10
圖2.8 Lucas–Kanade演算法流程圖	11
圖2.9 原始特徵位置	12
圖2.10 特徵追蹤錯誤	12
圖2.11 (a) Microsoft LifeCam VX6000攝影機	13
圖2.11 (b) ASUS W5Fseries 筆記型電腦	13
圖2.12 樣本SURF特徵位置	13
圖2.13 (a) Rmatch=0.7	14
圖2.13 (b) Rmatch=0.6	14
圖2.13 (c) Rmatch=0.5	14
圖2.13 (d) Rmatch=0.4	14
圖2.13 (e) Rmatch=0.3	14
圖2.13 (f) Rmatch=0.2	14
圖2.13 (g) Rmatch=0.1	14
圖2.13 (h) Rmatch=0.05	14
圖2.13 (i) Rmatch=0.01	14
圖2.14樣本SURF特徵位置	16
圖2.15 150th NN方法偵測(左) NN方法偵測，Lucas-Kanade方法追蹤(右) 	17
圖2.16 230th NN方法偵測(左) NN方法偵測，Lucas-Kanade方法追蹤(右) 	17
圖2.17 500th NN方法偵測(左) NN方法偵測，Lucas-Kanade方法追蹤(右)	17
圖2.18 240th 攝影機順時鐘方向旋轉60度	18
圖2.19 450th 攝影機順時鐘方向旋轉90度	18
圖2.20 900th 攝影機順時鐘方向旋轉225度	18
圖2.21 1200th 攝影機順時鐘方向旋轉360度	19
圖2.22地圖資料庫預存的4個標誌	20
圖2.23 系統啟動(a)資料關聯失敗	20
圖2.23 系統啟動(b)資料關聯成功	20
圖2.24 MonoSLAM上視圖	21
圖2.25 MonoSLAM前視圖	21
圖2.26 MonoSLAM三維立體圖	21
圖2.27 方形閉迴路連續截圖(a) 91th影像：系統啟動	21
圖2.27 方形閉迴路連續截圖(b) 140th影像：影像特徵初始化	21
圖2.27 方形閉迴路連續截圖(c) 420th影像	21
圖2.27 方形閉迴路連續截圖(d) 496th影像	21
圖2.27 方形閉迴路連續截圖(e) 683th影像	21
圖2.27 方形閉迴路連續截圖(f) 746th影像	21
圖2.27 方形閉迴路連續截圖(g) 855th影像	22
圖2.27 方形閉迴路連續截圖(h) 947th影像	22
圖3.1 狀態向量x與共變異數矩陣P示意圖	26
圖3.2 量測向量z與Jacobian矩陣H示意圖	26
圖3.3 清除特徵速度向量與其共變異數參數	28
圖3.4 清除矩陣H中量測向量相對於特徵速度的偏微分	28
圖3.5 單眼視覺SLAM with DATMO系統流程圖	29
圖3.6 SLAM(a) 293th影像	30
圖3.6 SLAM(b) 309th影像	30
圖3.6 SLAM(c) 358th影像	30
圖3.7 SLAM with DATMO(a) 293th影像	30
圖3.7 SLAM with DATMO(b) 309th影像	30
圖3.7 SLAM with DATMO(c) 358th影像	30
圖3.8 SLAM with GO(a) 293th影像	30
圖3.8 SLAM with GO(b) 309th影像	30
圖3.8 SLAM with GO(c) 358th影像	30
圖3.9 SLAMwithDATMO 上視圖	31
圖3.10 SLAMwithDATMO前視圖	31
圖3.11 SLAMwithDATMO三維立體圖	32
圖3.12 SLAM with DATMO十張截圖(a) 52th影像：系統啟動	32
圖3.12 SLAM with DATMO十張截圖(b) 98th影像：影像特徵初始化	32
圖3.12 SLAM with DATMO十張截圖(c) 330th影像：持續執行自我定位與建圖任務	32
圖3.12 SLAM with DATMO十張截圖(d) 526th影像：物體移動	32
圖3.12 SLAM with DATMO十張截圖(e) 563th影像：物體移動停止	32
圖3.12 SLAM with DATMO十張截圖(f) 615th影像：新增特徵至移動物體	32
圖3.12 SLAM with DATMO十張截圖(g) 621th影像：物體特徵持續收斂深度	32
圖3.12 SLAM with DATMO十張截圖(h) 634th影像：特徵狀態轉換且加入運動模型	32
圖3.12 SLAM with DATMO十張截圖(i) 657th影像：物體持續右移	33
圖3.12 SLAM with DATMO十張截圖(j) 684th影像	33
圖3.13 以SLAM實現SLAMMOT (a) 615th	33
圖3.13 以SLAM實現SLAMMOT (b) 621th	33
圖3.13 以SLAM實現SLAMMOT (c) 657th	33
圖3.13 以SLAM實現SLAMMOT (d) 684th	33
圖3.14 以SLAMwithDATMO實現SLAMMOT(a) 615th	34
圖3.14 以SLAMwithDATMO實現SLAMMOT(b) 621th	34
圖3.14 以SLAMwithDATMO實現SLAMMOT(c) 657th	34
圖3.14 以SLAMwithDATMO實現SLAMMOT(d) 684th	34
圖3.15 以SLAMwithGO實現SLAMMOT(a) 615th	34
圖3.15 以SLAMwithGO實現SLAMMOT(b) 621th	34
圖3.15 以SLAMwithGO實現SLAMMOT(c) 657th	34
圖3.15 以SLAMwithGO實現SLAMMOT(d) 684th	34
圖A.1 積分影像定義及積分影像應用	39
圖A.2 9×9盒子過濾器	40
圖A.3 SIFT與SURF尺度空間變化的差異	41
圖A.4 特徵點的方位分配	41
圖A.5 Haar小波過濾器	42
圖A.6 特徵點的特性描述向量	42
圖B.1 金字塔圖層	45
圖B.2 金字塔影像圖層之間的關係	45
圖B.3 虛擬像素	46
圖B.4 各層像素位移值計算	46

表目錄
表2.1 SURF特徵半徑	12
表2.2筆記型電腦規格表	12
表2.3 Microsoft LifeCam VX6000攝影機規格表	12
表2.4不同Rmatch的實測結果	15
表2.5最鄰近搜尋方法的實測比較	16

參考文獻

[1]	T. Bailey and H. Durrant-Whyte, “Simultaneous Localization and Mapping: Part2,” IEEE Robotics and Automation Magazine, 2006.
[2]	A. Baumberg, “Reliable feature matching across widely separated views,” Proceedings Computer Vision and Pattern Recognition, pp.774-781, 2000.
[3]	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.
[4]	J.Y. Bouguet, “Pyramidal Implementation of the Lucas Kanade Feature Tracker,” Website: http://robots.stanford.edu/cs223b04/algo_tracking.pdf, 1997.
[5]	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.
[6]	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.
[7]	R.H. Deaves, “Covariance bounds for augmented state Kalman filter application,” IEE Electronics Letters, vol.35, no.23, pp.2062-2063, 1999.
[8]	H. Durrant-Whyte, and T. Bailey, “Simultaneous Localization and Mapping: Part 1,” IEEE Robotics and Automation Magazine, 2006.
[9]	C. Harris and M. Stephens, A combined corner and edge detector, Proceedings of the 4th Alvey Vision Conference, pp.147-151, 1988.
[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]	N. Karlsson, E. Di Bernardo, J. Ostrowski, L. Goncalves, P. Pirjanian, and M.E. Munich, “The vSLAM Algorithm for Robust Localization and Mapping,” IEEE International Conference on Robotics and Automation, 2005.
[12]	T. Lindeberg, “Feature detection with automatic scale selection,” International Journal of Computer Vision, vol.30, no.2, pp79-116, 1998.
[13]	D.G. Lowe, “Distinctive Image Features from Scale-Invariant Keypoints,” International Journal of Computer Vision, 60, 2, pp. 91-110, 2004.
[14]	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.
[15]	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.
[16]	K. Mikolajczyk, and C. Schmid, “A performance evaluation of local descriptors,” Proceedings Computer Vision and Pattern Recognition, pp.257-263, 2003.
[17]	M. Muja, and D.G. Lowe, “Fast approximate nearest nrighbors with automatic algorithm configuration,” Computer Science Department, University of British Columbia, Vancouver, B.C., Canada, 2009.
[18]	OpenCV, Intel, website: http://opencv.willowgarage.com/wiki/ (2010/02/04)
[19]	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.
[20]	P. Pinies, J.D. Tardos, “Large Scale SLAM Building Conditionally Independent Local Maps: Application to Monocular Vision,” IEEE Transactions on Robotics, vol.24, no.5, 2008.
[21]	G. Shakhnarovich, T. Darrell, and P. Indyk, “Nearest-neighbor methods in learning and vision,” MIT Press, 2005.
[22]	J. Shi, and C. Tomasi, “Good Features to Track,” IEEE Conference on Computer Vision and Pattern Recognition, pages 593-600, 1994.
[23]	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.
[24]	C.C. Wang, C. Thorpe, S. Thrun, M. Hebert, and H. Durrant-Whyte, “Simultaneous Localization, Mapping and Moving Object Tracking,” The International Journal of Robotics Research, vol. 26, no. 09, pp. 889-916, 2007
[25]	Y.T. Wang, D.Y. Hung, and S.H. Cheng, “Image Feature Tracker for SLAM with Monocular Vision,” Proceedings of The SICE Annual Conference, 2010.
[26]	洪敦彥，基於擴張型卡爾曼過濾器的機器人視覺式同時定位、建圖、與移動物體追蹤，淡江大學機械與機電工程學系碩士論文，2010。