本論文的目的在於提高基於雙眼攝影機之視覺里程計準確性與即時性。本論文使用加速強健特徵(speeded up robust features,SURF)演算法擷取環境地標，並使用三點透視(perspective-3-point, P3P)以及隨機取樣一致(random sample consensus, RANSAC)演算法來定位機器人的位置。在本論文中使用直立式加速強健特徵(upright speeded-up robust features, U-SURF)、限制盒子濾波器的門閥值、參數化三點透視以及隨機化隨機取樣一致(Randomized random sample consensus, R-RANSAC)來降低視覺里程計的計算時間。藉由高效率加速強健特徵的較高計算次數進而提高準確性。同時參數化三點透視亦可以提高視覺里程計的準確性。改善的演算法將實現在二輪差速驅動機器人之上。

The purpose of this thesis is to improve the accuracy and instantaneity of the binocular-camera-based visual odometry (VO). The speeded-up robust features (SURF) algorithm was used to capture environment landmarks, and the perspective-3-point(P3P) algorithm and random sample consensus (RANSAC) method were used to the robot localization. The Upright-SURF, threshold of box filter, novel parametrizated P3P algorithm and randomized random sample consensus (R-RANSAC) algorithm were used to reduce computing time of the VO. The revised SURF can increase the frequency of landmark localization and then improve accuracy of the VO. The novel parametrizated P3P algorithm also improves accuracy of the VO. The improved VO was implemented on the two-wheeled mobile robot to verify accuracy and instantaneity of the VO.

目錄
中文摘要 ................................................................................................................... I
英文摘要 .................................................................................................................. II
目錄 ........................................................................................................................ III
圖目錄 ......................................................................................................................V
表目錄 .................................................................................................................. VIII
第1章 緒論 ........................................................................................................... 1
1.1 研究目的與動機.................................................................................... 1
1.2 文獻探討 ............................................................................................... 2
1.3 研究範圍 ............................................................................................... 3
第2章 系統流程及架構 ....................................................................................... 4
2.1 視覺里程計 ........................................................................................... 4
2.2 主要改善流程 ....................................................................................... 5
第3章 視覺地標管理 ........................................................................................... 7
3.1 SURF演算法 ........................................................................................ 7
3.1.1 SURF地標偵測 ......................................................................... 7
3.1.2 SURF地標描述 ....................................................................... 10
3.1.3 SURF地標比對 ....................................................................... 12
3.2 地標點位置 ......................................................................................... 12
3.2.1 攝影機鏡頭校正 ...................................................................... 12
3.2.2 透視投影.................................................................................. 13
3.3 地標管理 ............................................................................................. 16
3.3.1 地標新增.................................................................................. 16
3.3.2 地標更新.................................................................................. 17
3.3.3 地標刪除.................................................................................. 17
3.4 盒子濾波器抑制值 .............................................................................. 19
3.5 主方向角剔除 ..................................................................................... 19
3.6 盒子濾波器之抑制值以及主方向角剔除模擬 ................................... 20
第4章 攝影機定位改善 ..................................................................................... 21
4.1 3點透視問題(P3P) .............................................................................. 21
4.2 正確攝影機位置.................................................................................. 24
4.2.1 RANSAC ................................................................................. 24
4.2.2 使用RANSAC求合適之P3P解 ............................................ 25
4.3 參數化3點透視問題(P3P) ................................................................. 25
4.4 隨機化隨機取樣一致(R-RANSAC) .................................................... 32
4.5 低量測誤差空間.................................................................................. 34
4.6 低量測誤差空間實驗 .......................................................................... 35
4.6.1 深度實驗.................................................................................. 35
4.6.2 視角實驗.................................................................................. 35
4.7 RANSAC改善模擬比較 ..................................................................... 38
第5章 實驗及硬體設備 ..................................................................................... 41
5.1 硬體設備 ............................................................................................. 41
5.1.1 機器人規格 .............................................................................. 41
5.1.2 PC及視覺感測器 .................................................................... 43
5.2 視覺里程計改善比較實驗 .................................................................. 44
第6章 結論與未來展望 ..................................................................................... 54
6.1 結論 ..................................................................................................... 54
6.2 未來展望 ............................................................................................. 54
參考文獻 .............................................................................................................. 55
圖目錄
圖2.1 視覺里程計示意圖 .................................. 4
圖2.2 視覺里程計流程圖 .................................. 5
圖2.3 主要改善內容流程圖.................................. 6
圖3.1 視覺地標管理流程 ................................... 7
圖3.2 積分影像 .................................. 9
圖3.3 利用積分影像取範圍.................................. 9
圖3.4 盒子濾波器 .................................. 9
圖3.5 改變濾波器大小示意圖 .................................. 10
圖3.6 音階層數與盒子濾波器尺寸關係圖 ....................... 10
圖3.7 非最大值抑制示意圖.................................. 10
圖3.8 Haar 小波濾波器 .................................. 11
圖3.9 地標主方向角示意圖.................................. 11
圖3.10 16 維描述向量 .................................... 12
圖3.11 雙眼攝影機視線向量示意圖 ........................... 14
圖3.12 世界座標與攝影機座標示意圖[8] ....................... 16
圖3.13 地標新增策略 (左圖為新增前，右圖為新增後)[8] .......... 17
圖3.14 地標點跳動情形[8] ...................... 18
圖3.15 虛擬程式碼 ...................... 19
圖4.1 三點透視定位 ................................ 21
圖4.2W位置求解示意圖[8] ............................ 23
圖4.3RANSAC 演算法 ................................... 24
圖4.4 P3P 問題示意圖 ......................... 26
圖4.5 攝影機以及地標點座標示意圖 ......................... 27
圖4.6半平面 關係圖..............................	28
圖4.7將 平面沿著 旋轉 角度.......................	29
圖4.8 現成雙眼立體視覺設備及距離誤差圖 .................. 34
圖4.9 低量測誤差空間示意圖 ............................. 34
圖4.10 深度實驗數據圖 ................... 35
圖4.11 左眼之切向及徑向誤差總合圖 ........... 36
圖4.12 右眼之切向及徑向誤差總合圖 .......................... 36
圖4.13 雙眼誤差0.7piexel 扭曲疊合 ..... 37
圖4.14 低量測誤差空間 .......................... 38
圖4.15 RANSAC 所需比對數量圖 ........... 39
圖4.16 R-RANSAC(含影像平面限制)所需比對數量圖 ............... 40
圖4.17 R-RANSAC(含影像平面限制)+低量測誤差限制所需比對數量圖 .... 41
圖5.1 硬體架構 ...................................... 41
圖5.2Pioneer3-DX 機器人機構 ................ 42
圖5.3Pioneer3-DX 本體外觀 .................... 42
圖5.4 雙眼視覺感測器 ............................ 43
圖5.5 改善前路徑估測比較(1) ............. 45
圖5.6 改善前誤差比較(1) ......................... 45
圖5.7 改善前路徑估測比較(2) .................. 46
圖5.8 改善前誤差比較(2) .......................... 46
圖5.9 改善前路徑估測比較(3) .................. 47
圖5.10 改善前誤差比較(3) ......................... 47
圖5.11 改善後路徑估測比較(1) ................ 48
圖5.12 改善後誤差比較(1) ....................... 48
圖5.13 改善後路徑估測比較(2) ............... 49
圖5.14 改善後誤差比較(2) ....................... 49
圖5.15改善後路徑估測比較(3) ................ 50
圖5.16改善後誤差比較(3) ....................... 50
圖5.17改善前後平均誤差比較 ................ 51
圖5.18改善前後誤差百分比比較 ............. 51
表目錄
表3.1左攝影機內部參數 .......................... 12
表3.2右攝影機內部參數 .......................... 13
表3.3地標點時刻與穩定關係[8] .............. 18
表3.4主方向角剔除以及盒子濾波器抑制值限制時間比 ................. 20
表3.5主方向角剔除以及盒子濾波器抑制值效率比 .................... 20
表4.1 R-RANSAC 機率(受汙染機率0.2)................... 32
表4.2 R-RANSAC 機率(受汙染機率0.5)................. 32
表4.3 R-RANSAC 機率(受汙染機率0.8)........... 32
表4.4 R-RANSAC 機率 ................................ 33
表4.5低量測誤差空間表 ................................ 37
表4.6 RANSAC效率改善比較表 ..................... 39
表5.1Pioneer3-DX規格 ............................... 42
表5.2 PC規格 ............................................. 43
表5.3C120網路攝影機規格表 .................... 43
表5.4改善前後與編碼器誤差比較表 ........... 52
表5.5改善前後時間比較表......................... 53

[1]J.Y. Bouguet. Camera Calibration Toolbox for Matlab. http://www.vision.caltech.edu/bouguetj/calib_doc/(2014/7/20)
[2] http://ww2.ptgrey.com/stereo-vision/bumblebee-2/  (2014/7/20)
[3]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.
[4]H. Park, H. Mitsumine and M. Fujii, “Fast Detection of Robust Features by Reducing the Number of Box Filtering in SURF, ”IEICE Trans. Information and systems, vol. 94, pp.725-728,2011.
[5]M. Agrawal, K. Konolige, and M. Rufus Blas, “CenSurE: Center surround extremas for realtime feature detection and matching ”Proc. European Conf. computer vision 2008, vol. 5305, pp. 102-115, 2008.
[6]林冠瑜，"使用低階攝影機實現機器人視覺式SLAM"，淡江大學機械與機電工程學系碩士論文，2012。
[7]洪景泰，"基於FPGA之視覺定位及建圖於移動式機器人"，淡江大學機械與機電工程學系碩士論文，2012。
[8]蕭恩哲，"基於視覺式里程計之二輪式機器人控制"，淡江大學機械與機電工程學系碩士論文，2013。
[9]M.A. Fishier and R.C. Bolles, “Random sample consensus: A paradigm for model fitting with applications to image analysis and automated 	cartography” Communications of the ACM, vol.24, pp.381-395,1981.
[10]L. Kneip, D. Scaramuzza, R. Siegwart, “A novel parametrization of the 	perspective-three-point problem for a direct computation of absolute camera position and orientation” Proc. IEEE Conf. Computer Vision and 	Pattern Recognition, pp. 2969-2976, 2011.
[11]J. Matas and O. Chum, “Randomized RANSAC with Td,d test” Image and vision computing, vol.22, pp. 837-842, 2004.