臺灣博碩士論文加值系統

在使用裝設 RGB-D 攝影機的機器人探索未知環境，最關鍵的問題是如何整合包含在取得的一系列影像中的資訊。由於攝影機的視角能拍攝到的區域有限，所以需進行局部區域的貼合 (Registration)。若將攝影機每一個拍攝位置取得的影像表為一個節點，而每兩張影像的貼合結果視為連結兩個節點的邊，則完成的貼合結果即可表為一個貼合圖 (Registration Graph)。建構 3-D 場景的貼合圖可大幅化簡 3-D 場景的建構問題，其主要的關鍵是決定場景中的任兩節點是否有拍攝到重疊的場景，若有則需執行兩兩貼合的運算並連結兩個節點。在本研究中，我們是使用兩張影像間各自的 SIFT 特徵點的配對數粗略篩選可能有重疊的影像對，但是傳統的比對方法複雜度過高，所以我們提出一個基於視覺詞 (Visual Words，簡稱 VW) 的比對方法來加速運算。首先，我們先對兩張影像間各自的所有特徵點進行向量量化 (Vector Quantization)，以 VW 表示每一個特徵點。若兩個來自不同影像的特徵點都被量化成不同 VW，即表示這兩個特徵不可能配對。所以在配對運算時，只需對被量化成同一個 VW 的特徵點進行比對，計算量可大幅度降低。最後，因為這些特徵配對點裡會有包含錯誤的特徵配對點，所以需要使用 RANSAC 方法濾除錯誤配對點，找到之間較佳的三維資訊轉換關係來進行貼合。實驗結果顯示使用 VW 來對特徵進行特徵比對的方式可以提高運算的效能，並且不會損失太多特徵點配對精確度。

The key problem of using a mobile robot equipped with an RGB-D camera to explore an unknown environment is how to fuse the information contained in the acquired images. Due to the limited field of view of the camera, it is inevitable to register the acquired images. If we represent each image as a node and each pairwise registration result as an edge linking two registered images, then the completed registration results can be expressed as a registration graph. Constructing a registration graph from a series of input images can greatly simplify the 3-D scene reconstruction problem. Notably, the critical issue of registration graph construction is to determine whether a pair of given images are overlapped. If two images are determined to be overlapped, then the second problem is to determine their registration parameters and to add an edge to link those two images. In this work, we use the number of SIFT feature correspondences to select possibly overlapped images. However, the computational complexity of the traditional SIFT feature matching method is too high. Hence, we propose a fast SIFT feature matching algorithm based on the visual word (VW) technique. We first quantize the SIFT features via the vector quantization method with a specified codebook. If two SIFT features are quantized to different VWs, then those two SIFT features are deemed as not matched. Therefore, when matching SIFT features, we only have to consider those features having the same VW and, thus, the computation cost can be greatly reduced.The matched SIFT features computed with the VW approach are further verified with the RANSAC algorithm to remove incorrect matching results and to estimate the registration parameters. Experimental results show that the proposed method can improve the computation speed for 38 times without sacrificing two much matching accuracy.

目 錄
致謝 ................................................................................................................................... i
論文摘要............................................................................................................................ ii
Abstract ............................................................................................................................. iii
目 錄 .................................................................................................................................. v
圖 目 錄 ............................................................................................................................. vii
表 目 錄 ............................................................................................................................. ix
第一章 緒論...................................................................................................................... 1
1.1 研究動機 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 文獻探討 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 研究目標 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.4 論文架構 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
第二章 系統介紹.............................................................................................................. 6
2.1 系統設備 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.1.1 深度攝影機 (RGB-D Camera) . . . . . . . . . . . . . . . . . . . . 7
2.1.2 Parrot AR.Drone 1.0 2.0 . . . . . . . . . . . . . . . . . . . . . . . 7
2.2 系統流程 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
第三章 研究方法.............................................................................................................. 9
3.1 局部特徵的抽取 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
3.2 編碼表的建立 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
3.3 局部特徵的編碼 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
3.4 關鍵點的配對 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
3.4.1 傳統徹底比對 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
3.4.2 KD-Tree 比對 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
3.4.3 Visual Words 比對 . . . . . . . . . . . . . . . . . . . . . . . . . . 16
3.5 影像之相關性 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
3.6 轉換矩陣的計算 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.6.1 RANSAC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.6.2 ICP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.7 關聯圖的建立 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
第四章 實驗結果.............................................................................................................. 25
4.1 編碼表的建立 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
4.2 SIFT 特徵之三種比對方法 . . . . . . . . . . . . . . . . . . . . . . . . . 26
4.2.1 傳統徹底比對方法 . . . . . . . . . . . . . . . . . . . . . . . . . 26
4.2.2 KD-Tree 比對方法 . . . . . . . . . . . . . . . . . . . . . . . . . . 27
4.2.3 基於 visual words 比對方法 . . . . . . . . . . . . . . . . . . . . . 27
4.3 光譜之相關程度 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
4.4 3D 場景貼合 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
第五章 結論與未來方向.................................................................................................. 34
5.1 結論 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
5.2 未來方向 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
參 考 文 獻 ........................................................................................................................ 36

圖 目 錄
1.1 兩兩貼合之圖例:(a)(b) 為未貼合之 3D 場景圖, (c) 為兩兩貼合之結果 . 4
1.2 Swallow - PUAS [1] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.1 機器人設備圖 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.2 ASUS Xtion PRO [2] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.3 AR.Drone 1.0 和 AR.Drone 2.0 (參考資料: [3] ) . . . . . . . . . . . . . . 8
2.4 室內場景貼合的系統流程圖 . . . . . . . . . . . . . . . . . . . . . . . . 8
3.1 局部特徵的抽取之圖例. (a) 為偵測到的 SIFT 關鍵點呈現圖, (b) 為
SIFT 描述子示意圖. (圖片來源： [4] ) . . . . . . . . . . . . . . . . . . . 10
3.2 建置 Visual words 的流程示意圖 . . . . . . . . . . . . . . . . . . . . . . 11
3.3 局部特徵的編碼流程圖 . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
3.4 一維空間中 Binary Search Tree 和 KD-Tree 的差異 (圖片來源： [6] ) . . 13
3.5 KD-Tree 基於 BBF 數量搜尋示意圖 (圖片來源： [5] ) . . . . . . . . . . 14
3.6 基於 SIFT 特徵之關鍵點配對結果圖 (a) 最短距離之配對 (b) 定義臨界
值過濾些許錯誤的配對 . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3.7 KD-Tree 範圍搜尋示意圖 (圖片來源： [6] ) . . . . . . . . . . . . . . . . 16
3.8 舉例圖 3.6 在 VW table 中特徵數量分布圖. (a) 為圖 3.6 左側影像之關
鍵點的分布, (b) 為圖 3.6 右側影像之關鍵點的分布, (c) 為關鍵點配對
後，關鍵點的分布. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
3.9 建置光譜之示意圖 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.10 進行配對的兩張影像之 RGB 和 D 示意圖. (a)(b) 為兩張 RGB 的彩色影
像, (c)(d) 為兩張 D 的深度影像. . . . . . . . . . . . . . . . . . . . . . . 19
3.11 圖 3.6 經 過 RANSAC 後， 保 留 到 最 後 的 最 佳 配 對 點. (a) 未 經 過
RANSAC 過濾之特徵點配對結果 (b) 經過 RANSAC 過濾錯誤配對
後結果 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
3.12 2 維之 RANSAC 迭代示意圖. (a) 一開始，隨機抽取 k 個樣本點 (k = 2)；
(b) 利用這些樣本點定義出一個模型，在此，定義兩點間的連線為模
型以及有效的面積為臨界值；(c) 對每個點評估其誤差，在此，定義點
到直線的距離為誤差. 最後，將所有點分成 Inliers 和 Outliers 兩個子集
合，再利用所有的 Inliers 重新計算模型 . . . . . . . . . . . . . . . . . . 21
3.13 迭代最近點演算法範例 [7] . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.14 多張貼合之關聯圖範例 . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
4.1 訓練 VW 的範例影片，總共 381681 個特徵 . . . . . . . . . . . . . . . . 25
4.2 測試影像之局部特徵的抽取 . . . . . . . . . . . . . . . . . . . . . . . . 26
4.3 傳統徹底比對方法的配對結果圖 . . . . . . . . . . . . . . . . . . . . . . 26
4.4 KD-Tree 比對方法的配對結果圖 . . . . . . . . . . . . . . . . . . . . . . 27
4.5 KD-Tree 比對方法的配對結果圖 . . . . . . . . . . . . . . . . . . . . . . 27
4.6 正確光譜之相關程度範例圖一 . . . . . . . . . . . . . . . . . . . . . . . 29
4.7 正確光譜之相關程度範例圖二 . . . . . . . . . . . . . . . . . . . . . . . 29
4.8 錯誤光譜之相關程度範例圖 . . . . . . . . . . . . . . . . . . . . . . . . 30
4.9 要進行 3D 場景兩兩貼合之影像特徵配對之範例圖 . . . . . . . . . . . 30
4.10 要進行 3D 場景兩兩貼合之影像個自 3D 場景 . . . . . . . . . . . . . . . 31
4.11 3D 場景兩兩貼合之結果圖 . . . . . . . . . . . . . . . . . . . . . . . . . 31
4.12 錯誤的兩兩貼合之配對點 . . . . . . . . . . . . . . . . . . . . . . . . . . 32
4.13 錯誤的兩兩貼合之間的轉換矩陣 . . . . . . . . . . . . . . . . . . . . . . 32
4.14 進行全域貼合前的關聯圖 . . . . . . . . . . . . . . . . . . . . . . . . . . 32
4.15 進行全域貼合的結果圖 . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

表 目 錄
1.1 現有特徵擷取的簡介 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
3.1 比較 SIFT、SURF 和 ORB 特徵執行時間 . . . . . . . . . . . . . . . . . 10
4.1 比較 SIFT 特徵之三種比對方法執行效能 . . . . . . . . . . . . . . . . . 28
4.2 各步驟平均所需時間 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

[1] http://www.uaver.com/tw/aerial-mapping-uas.html.
[2] http://tw.asus.com/Multimedia/Motion_Sensor/Xtion_PRO_LIVE/.
[3] http://cdn.ardrone2.parrot.com/.
[4] D. G. Lowe, “Distinctive image features from scale-invariant keypoints,” Comput. Vis. Image Underst., vol. 60, no. 2, pp. 91–110, 2008.
[5] J. S. Beis and D. G. Lowe, “Shape indexing using approximate nearest-neighbour search in high-dimensional spaces,” Department of Computer Science University of British Columbia Vancouver, B.C., Canada V6T 1Z4, 1997.
[6] http://www.csie.ntnu.edu.tw/~u91029/PointInterval.html.
[7] S.-W. Shih and Y.-T. Chuang, “Relaxation of global registration error of 3d models with trust-region algorithm,” National Central Library, July 2006.
[8] K. Konolige and M. Agrawal, “Frameslam:from bundle adjustment to real-time visual mapping,” IEEE Transactions on Robotics, vol. 24, no. 5, pp. 1066–1077, 2008.
[9] J. M. M. M. Hauke Strasdat and A. J. Davison, “Scale drift-aware large scale monocular slam,” In Matsuoka, Yoky and Durrant-Whyte, Hugh F. and Neira, José, editor, Robotics: Science and Systems. The MIT Press, 2010.
[10] http://en.wikipedia.org/wiki/Simultaneous_localization_and_mapping.
[11] I. Hugh Durrant-Whyte, Fellow and T. Bailey, “Simultaneous localisation and mapping(slam): Part i the essential algorithms,” Robotics Automation Magazine, IEEE, vol. 13, pp. 99–110, June 2006.
[12] T. Bailey and H. Durrant-Whyte, “Simultaneous localisation and mapping (slam): Part ii state of the art,” Robotics Automation Magazine, IEEE, vol. 13, pp. 108–117, September 2006.
[13] C. Harris and M. Stephens, “A combined corner and edge detector,” In Proceedings of the 4th Alvey Vision Conference, pp. 147–151, 1988.
[14] C. S. M. Calonder, V. Lepetit and P. Fua, “Brief: Binary robust independent elementary features,” In European Conference on Computer Vision, September 2010.
[15] T. T. Herbert Bay, Andreas Ess and L. V. Gool, “Speeded-up robust features (surf),” International Journal of Computer Vision, vol. 110, pp. 346–359, June 2008.
[16] K. K. B. Steder, R. B. Rusu and W. Burgard, “Narf: 3d range image features for object recognition,” In Workshop on Defining and Solving Realistic Perception Problems in Personal Robotics at the IEEE/RSJ Int. Conf. on Intelligent Robots and Systems (IROS), Taipei, Taiwan, 2010.
[17] K. K. Ethan Rublee, Vincent Rabaud and G. Bradski, “Orb: an efficient alternative to sift or surf,” Computer Vision (ICCV), pp. 2564–2571, November 2011.
[18] C. Silpa-Anan and R. Hartley, “Optimised kd-trees for fast image descriptor matching,” Computer Vision and Pattern Recognition, 2008. CVPR 2008. IEEE Conference on, pp. 1–8, June 2008.
[19] F. Jurie and B. Triggs, “Creating efficient codebooks for visual recognition,” Computer Vision, 2005. ICCV 2005. Tenth IEEE International Conference on, vol. 1, pp. 604–610, October 2005.
[20] E. M. B. Bart Thomee and M. S. Lew, “Top-surf: a visual words toolkit,” ACM, vol. 2, pp. 1473–1476, October 2010.
[21] J. Sivic and A. Zisserman, “Video google: A text retrieval approach to object matching in videos,” Proc. IEEE International Conference on Computer Vision, 2003.
[22] T. S. H. K. S. Arun and S. D. Blostein, “Least squares fitting of two 3-d point sets,” IEEE Transactions on Pattern Analysis and Machine Intelligence PAMI-9, vol. 2, 1987.
[23] B. L. Torsten Sattler, Tobias Weyand and L. Kobbelt, “Image retrieval for image-based localization revisited,” British Machine Vision Conference (BMVC’12), 2012.
[24] J. MACQUEEN, “Some methods for classification and analysis of multivariate observations,” Proceedings of 5th Berkeley Symposium on Mathematical Statistics and Probability 1. University of California Press., pp. 281–297, 1967.
[25] E. M. B. Bart Thomee and M. S. Lew, “Random sample consensus: A paradigm for model fitting with applications to image analysis and automated cartography.,” Commun. ACM, vol. 24, no. 2, pp. 381–395, 1981.
[26] A. Aydemir, “Building a 3d map from rgb-d sensors,” Computer Vision and Active Perception Laboratory Royal Institute of Technology (KTH), Stockholm, Sweden.
[27] P. H. S. Torr and A. Zisserman, “Mlesac: A new robust estimator with application to estimating image geometry,” Computer Vision and Image Understanding, vol. 78, no. 2, pp. 138–156, 2000.
[28] Z. ZHANG, “Iterative point matching for registration of free-form curves,” 1992.
[29] E. H. X. R. Peter Henry, Michael Krainin and D. Fox, “Rgb-d mapping: Using depth cameras for dense 3d modeling of indoor environments,” Delhi, India, 2010.
[30] N. D. M. P. J. Besl, “A method for registration of 3-d shapes,” Pattern Analysis and Machine Intelligence, IEEE Transactions on, vol. 14, pp. 239–256, August 1992.