在擴增實境(Augmented Reality)應用中，視覺里程計或同步定位及地圖建構是一項關鍵的演算法提供相機姿態使得虛擬物件能定位於真實世界。由於此應用需求，任何定位誤差或延遲會導致虛擬物件和真實世界不自然地疊合;因此最大的挑戰能達到即時的運算速度同時要求可靠的定位準確度。
本論文使用迭代最近點演算法 (Iterative closest point, ICP) 來追蹤相機姿態，此法很容易受到選點結構性不足或雜訊的影響，導致姿態估測結果不佳。已有針對結構性問題而提出的選點策略，然其需要計算各點的法向量，計算量龐大。本論文提出於影像中邊緣或進邊區域 (near-edge region) 隨機取點，來增加各個物體(方向)被取樣的機率，進而有效提升其結構性。此外，為了降低深度傳感器軸向雜訊的影響，只會從所定義的感興趣區域 (ROI) 內之近邊區域來取樣點，此感興趣區域由深度最小區域開始決定，並基於結構性強弱適應性延伸或收縮達到最小化雜訊影響之效果。本論文另外針對ICP匹配之演算法降低運算複雜度。基於多重解析度匹配方法，提出適應性搜尋範圍選擇之策略，當相機移動量小時，可降低多餘的ICP迭代次數;同時有效利用ICP在穩定狀態的時間連續性提供初始估計，降低每個來源點搜索候選配對次數。最後，本論文也考慮關鍵幀的選擇策略，解決在傳統方法中，新關鍵幀只有在當前幀和參考關鍵幀距離大時才產生的問題。針對在預估前無法預測當前幀與參考關鍵幀之距離所導致的錯誤預估，本論文提出有效切換關鍵幀並重新計算的策略以提升匹配品質，進而提高視覺里程計的可靠性。本論文所提出的視覺里程計演算法經過公開的資料集評估，整體軌跡誤差小於其他競爭對手，同時在單執行緒上之執行達到平均136 FPS的速度。

Visual odometry (VO) or Simultaneous localization and mapping (SLAM) for camera poses estimation plays an important role in virtual object registration of augmented reality (AR) applications. One of the main challenges of the algorithm is to keep the tracking errors as small as possible for reducing the discrepancy between virtual and real objects which can be easily recognized in practical application. Moreover, it is hard to keep up with the camera frame rate while trying to maintain small error. Therefore, implementing a fast and robust visual odometry algorithm is pursued.
The proposed VO algorithm is based on iterative closest point (ICP) algorithm, which is a widely used registration algorithm but the quality of ICP estimation is easily affected by insufficient structural constraint and noise. Several methods have been proposed to sample points with enough transformation constraints; however heavy computation is necessary for knowing normal vectors of every pixels. In this thesis, we propose to sample points from near-edge regions, which can effectively increase constraints by increasing the possibility of sampling points from various objects in the scene. Besides, to decrease the influence of axial noise, we only sample points from near-edge regions inside the region of interest (ROI) which is extended from the near-end of the view, and then is adaptively extended or shrunk to ensure sufficient constraints while minimizing the influence of axial noise.
Secondly, we aim at reducing the complexity of matching stage in ICP. Based on multi-resolution scheme, an idea of adaptive searching area determination is proposed to reduce the redundant iterations as a smaller searching area is sufficient to search for true match in small camera motion. In addition, through using temporal correlation of ICP in steady state at the initial estimate for finding the closest point, number of search for each source points can be furthered reduced.
Finally, the proposed scheme is extended to the keyframe-based method where a keyframe is generated when the distance between the current frame and the last keyframe is large. Howerver, since the distance is unknown before estimation, a poor matching quality may occur, which results in large error; Hence, a strategy of efficiently changing keyframe and then performing re-estimation is proposed to increase the matching quality.
The proposed VO algorithm is evaluated on publicly available benchmark dataset. Compared with other VO algorithms, the proposed one exhibits competitive performance and achieves an average frame rate of 136 FPS using only a single CPU thread.

[1] H. Durrant-Whyte and T. Bailey, "Simultaneous localization and mapping: part I," IEEE Robotics & Automation Magazine, vol. 13, no. 2, pp. 99-110, June 2006.
[2] 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.
[3] D. Nister, O. Naroditsky and J. Bergen, "Visual odometry," Proceedings of the 2004 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 2004. CVPR 2004., 2004, pp. I-652-I-659 Vol.1.
[4] D. Scaramuzza and F. Fraundorfer, "Visual Odometry [Tutorial]," IEEE Robotics & Automation Magazine, vol. 18, no. 4, pp. 80-92, Dec. 2011.
[5] Henry, Peter, et al. "RGB-D mapping: Using depth cameras for dense 3D modeling of indoor environments." 12th International Symposium on Experimental Robotics (ISER). 2010.
[6] Kerl, Christian, Jurgen Sturm, and Daniel Cremers. "Dense visual SLAM for RGB-D cameras." Intelligent Robots and Systems (IROS), 2013 IEEE/RSJ International Conference on. IEEE, 2013.
[7] Henry, Peter, et al. "RGB-D mapping: Using Kinect-style depth cameras for dense 3D modeling of indoor environments." The International Journal of Robotics Research 31.5 (2012): 647-663.
[8] Endres, Felix, et al. "3-D mapping with an RGB-D camera." IEEE Transactions on Robotics 30.1 (2014): 177-187.
[9] Kerl, Christian, Jürgen Sturm, and Daniel Cremers. "Robust odometry estimation for RGB-D cameras." Robotics and Automation (ICRA), 2013 IEEE International Conference on. IEEE, 2013.
[10] Besl, Paul J., and Neil D. McKay. "A method for registration of 3-D shapes." IEEE Transactions on pattern analysis and machine intelligence 14.2 (1992): 239-256.
[11] Rusinkiewicz, Szymon, and Marc Levoy. "Efficient variants of the ICP algorithm." 3-D Digital Imaging and Modeling, 2001. Proceedings. Third International Conference on. IEEE, 2001.
[12] Besl, Paul J., and Neil D. McKay. "A method for registration of 3-D shapes." IEEE Transactions on pattern analysis and machine intelligence 14.2 (1992): 239-256.
[13] Newcombe, Richard A., et al. "KinectFusion: Real-time dense surface mapping and tracking." Mixed and augmented reality (ISMAR), 2011 10th IEEE international symposium on. IEEE, 2011.
[14] Gelfand, Natasha, et al. "Geometrically stable sampling for the ICP algorithm." 3-D Digital Imaging and Modeling, 2003. 3DIM 2003. Proceedings. Fourth International Conference on. IEEE, 2003.
[15] Rodolà, Emanuele, et al. "A simple and effective relevance-based point sampling for 3D shapes." Pattern Recognition Letters 59 (2015): 41-47.
[16] Guehring, Jens. "Reliable 3D surface acquisition, registration and validation using statistical error models." 3-D Digital Imaging and Modeling, 2001. Proceedings. Third International Conference on. IEEE, 2001.
[17] Simon, David A. Fast and accurate shape-based registration. Pittsburgh, Pennsylvania: Carnegie Mellon University, 1996.
[18] Choi, Changhyun, Alexander JB Trevor, and Henrik I. Christensen. "RGB-D edge detection and edge-based registration." Intelligent Robots and Systems (IROS), 2013 IEEE/RSJ International Conference on. IEEE, 2013.
[19] Bose, Laurie, and Arthur Richards. "Fast depth edge detection and edge based RGB-D SLAM." Robotics and Automation (ICRA), 2016 IEEE International Conference on. IEEE, 2016.
[20] Mallick, Tanwi, Partha Pratim Das, and Arun Kumar Majumdar. "Characterizations of noise in Kinect depth images: A review." IEEE Sensors journal 14.6 (2014): 1731-1740.
[21] Nguyen, Chuong V., Shahram Izadi, and David Lovell. "Modeling kinect sensor noise for improved 3d reconstruction and tracking." 3D Imaging, Modeling, Processing, Visualization and Transmission (3DIMPVT), 2012 Second International Conference on. IEEE, 2012.
[22] Konolige, Kurt, and Motilal Agrawal. "FrameSLAM: From bundle adjustment to real-time visual mapping." IEEE Transactions on Robotics 24.5 (2008): 1066-1077.
[23] Stückler, Jörg, and Sven Behnke. "Integrating depth and color cues for dense multi-resolution scene mapping using rgb-d cameras." Multisensor Fusion and Integration for Intelligent Systems (MFI), 2012 IEEE Conference on. IEEE, 2012.
[24] Benzun Wisely Babu, Soohwan Kim, and Zhixin Yan. “σ-DVO: Sensor Noise Model Meets Dense Visual Odometry” Mixed and augmented reality (ISMAR), 2016 15th IEEE international symposium on. IEEE, 2016.
[25] Mitra, Niloy J., and An Nguyen. "Estimating surface normals in noisy point cloud data." Proceedings of the nineteenth annual symposium on Computational geometry. ACM, 2003.
[26] Zhang, Zhengyou. "Iterative point matching for registration of free-form curves and surfaces." International journal of computer vision 13.2 (1994): 119-152.
[27] Turk, G. and Levoy, M. “Zippered Polygon Meshes from Range Images,” Proc. SIGGRAPH, 1994.
[28] Masuda, T., Sakaue, K., and Yokoya, N. “Registration and Integration of Multiple Range Images for 3-D Model Construction,” Proc. CVPR, 1996.
[29] Benjemaa, R. and Schmitt, F. “Fast Global Registration of 3D Sampled Surfaces Using a Multi-Z-Buffer Technique,” Proc. 3DIM, 1997.
[30] Jost, Timothée, and Heinz Hugli. "A multi-resolution ICP with heuristic closest point search for fast and robust 3D registration of range images." 3-D Digital Imaging and Modeling, 2003. 3DIM 2003. Proceedings. Fourth International Conference on. IEEE, 2003.
[31] Pulli, Kari. "Multiview registration for large data sets." 3-D Digital Imaging and Modeling, 1999. Proceedings. Second International Conference on. IEEE, 1999.
[32] Chalidabhongse, Junavit, and C-CJ Kuo. "Fast motion vector estimation using multiresolution-spatio-temporal correlations." IEEE transactions on circuits and systems for video technology 7.3 (1997): 477-488.
[33] Kim, Daehwan, and Daijin Kim. "A fast ICP algorithm for 3-D human body motion tracking." IEEE Signal Processing Letters 17.4 (2010): 402-405.
[34] Li, Reoxiang, Bing Zeng, and Ming L. Liou. "A new three-step search algorithm for block motion estimation." IEEE transactions on circuits and systems for video technology 4.4 (1994): 438-442.
[35] Sturm, Jürgen, et al. "A benchmark for the evaluation of RGB-D SLAM systems." Intelligent Robots and Systems (IROS), 2012 IEEE/RSJ International Conference on. IEEE, 2012.
[36] Prakhya, Sai Manoj, et al. "Sparse depth odometry: 3D keypoint based pose estimation from dense depth data." Robotics and Automation (ICRA), 2015 IEEE International Conference on. IEEE, 2015.
[37] B. Horn, “Closed-form solution of absolute orientation using unit quaternions,” Journal of the Optical Society of America A, vol. 4, pp. 629–642, 1987