臺灣博碩士論文加值系統

同步定位與建圖是自駕車研究中重要的一個課題，環境的資訊會藉由各種感測器收集並運算來找到對自駕車與環境皆一致的狀態。同步地位與建圖的研究使用了多種類型的感測器，包含相機和光達，光達可以量測精準的深度資訊，但資訊密度小於相機影像。
基於光達的同步定位與建圖演算法主要有兩種:直接法以及切割點雲後擬和模型。直接法會先選取感興趣的點來縮小點雲的數量，例如邊緣或角落的點，接著使用迭代最近點演算法或卡爾曼型濾波器來估測幀與幀的轉換。即便直接法可以被使用在任何情境中，其估測的好壞卻很難評價。相對於直接使用原始的點雲，擬和模型法會先將點雲切割成數個子集合，再將子集合擬和成預先設定的模型，最後再使用這些模型完成幀與幀之間的轉換估測。然而當環境中缺乏預先定義模型相關的物體時，擬和模型法就會失效。
在這篇論文中，僅使用光達並且基於特徵的同步定位與建圖演算法被提出，靈感來自 ORB 同步定位與建圖演算法。在此演算法中，諸如地板、阻擋點之不必要的點會先被點雲預處理程序排除，接著關鍵點會基於分割比例被挑選，並且使用二進制方向直方圖特徵描述子描述選取的關鍵點，最後幀到地圖的轉換會藉由特徵描述子的配對、對位以及迭代最近點演算法微調來估測。實驗結果顯示此演算法在較具結構性的工業技術研究院資料集中可以得到一致的估測結果。

Simultaneous localization and mapping is a basic and essential part of the autonomous driving research. Environment information gathered from sensors is computed and derives a consistent state of both self-driving car and the environment. Many types of sensor have been utilized in SLAM research, including camera and LiDAR. LiDAR can provide precise depth information, but suffers from the sparsity compared to camera images.
Two main methods have been used in LiDAR-based SLAM: direct method and modeling after segmentation. Direct method first extracts interesting points, such as edge points or corner points, to reduce the point cloud size. ICP or Kalman-based filter are then applied to estimate the transformation from frame to frame. Although this method can be adopted in every scenario, the quality of estimation is hard to evaluate. Instead of directly using original point cloud, model-based method first segment point cloud into subsets, and then models each subset with a defined model. Finally, frame-to-frame transformation is estimated from models. However, the model-based method is prone to the environment which has less defined models.
In this thesis, a feature-based SLAM algorithm, which is inspired from ORB-SLAM, is proposed on only LiDAR data. In the proposed algorithm, unnecessary points, such as ground points and occluded edge points, are removed by point cloud preprocessing module. Next, the keypoints are selected according to their segment ratio and encoded by B-SHOT feature descriptor. Frame-to-local-map transformation is then estimated based on the B-SHOT feature and refined by iterative closest point algorithm. The experimental results show that the estimated result of the proposed algorithm is consistent in the structural scenarios of ITRI dataset.

摘要 ii
ABSTRACT iv
CONTENTS vi
LIST OF FIGURES viii
LIST OF TABLES xiii
Chapter 1 Introduction 1
1.1 Motivation 1
1.2 Problem Formulation 3
1.3 Contributions 5
1.4 Organization of the Thesis 6
Chapter 2 Background and Literature Survey 7
2.1 Autonomous Driving Systems 7
2.2 Simultaneous Localization and Mapping 8
2.2.1 Front End: Motion Odometry 9
2.2.2 Back End: Optimization 13
Chapter 3 Related Algorithms 16
3.1 Ground Point Segmentation 16
3.1.1 Find Threshold Points 17
3.1.2 Find Start Points 19
3.2 Occluded Edge Point Detection 20
3.3 B-SHOT Feature Descriptor 23
3.4 3D-3D Pose Estimation 24
3.4.1 Matching 25
3.4.2 Alignment 26
3.5 Graph Optimization 29
Chapter 4 Point Cloud Preprocessing 32
4.1 System Architecture 32
4.2 Modified Ground Point Segmentation 33
4.2.1 Modified Initial Position of Start Point 33
4.2.2 Modified Start Point Condition 37
4.3 Host Car Point Removal 39
Chapter 5 Motion Estimation by Feature-Based Algorithm 41
5.1 System Architecture 41
5.2 Segment Ratio Keypoint Detection 43
5.3 Reference Keypoint Searching 48
5.4 Correspondence Motion Estimation and Global Keypoint Map Update 51
Chapter 6 Experimental Results and Analysis 56
6.1 System Overview 56
6.2 Hardware and Software Platform 58
6.2.1 Velodyne HDL-32 58
6.2.2 Computation Platform and Software Libraries 60
6.3 Experimental Scenes Analysis 60
6.4 Point Cloud Preprocessing 65
6.4.1 Modified Initial Position of Start Point 65
6.4.2 Low Point Threshold for Start Point 87
6.5 Motion Estimation by Feature-Based Algorithm 92
6.5.1 Segment Ratio 92
6.5.2 Keypoint Selection in Real Scenarios 99
6.5.3 Comparison of Different Keypoint Detection Method 101
6.5.4 B-SHOT Correspondence and ICP Refinement Tests 107
6.6 Entire System Test 120
6.7 Summary 121
Chapter 7 Conclusions and Future Works 124
7.1 Conclusions 124
7.2 Future Works 126
References 128

[1: Arun et al. 1987]
K. S. Arun, T. S. Huang and S. D. Blostein, “Least-Squares Fitting of Two 3-D Point Sets,” in IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. PAMI-9, no. 5, pp. 698-700, Sept. 1987.
[2: Atia et al. 2015]
M. M. Atia, S. Liu, H. Nematallah, T. B. Karamat and A. Noureldin, “Integrated Indoor Navigation System for Ground Vehicles with Automatic 3-D Alignment and Position Initialization,” in IEEE Transactions on Vehicular Technology, vol. 64, no. 4, pp. 1279-1292, Apr. 2015.
[3: Besl & McKay 1992]
P. J. Besl and N. D. McKay, “A method for registration of 3-D shapes,” in IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 14, no. 2, pp. 239-256, Feb. 1997.
[4: Bresson et al. 2017]
G. Bresson, Z. Alsayed , L. Yu and S. Glaser, “Simultaneous Localization and Mapping: A Survey of Current Trends in Autonomous Driving,” in IEEE Transactions on Intelligent Vehicles, vol. 2, no. 3, pp. 194-220, Sept. 2017.
[5: Cadena et al. 2016]
C. Cadena, L. Carlone, H. Carrillo, Y. Latif, D. Scaramuzza, J. Neira, I. Reid and J. J. Leonard, “Past, Present, and Future of Simultaneous Localization and Mapping: Toward the Robust-Perception Age,” in IEEE Transactions on Robotics, vol. 32, no. 6, pp. 1309-1332, Dec. 2016.
[6: Cao et al. 2018]
F. Cao, Y. Zhuang, H. Zhang and W. Wang, “Robust Place Recognition and Loop Closing in Laser-Based SLAM for UGVs in Urban Environments,” in IEEE Sensors Journal, vol. 18, no. 10, pp. 4242-4252, May 2018.
[7: Cheng 2011]
H. Cheng, “Autonomous Intelligent Vehicles Theory, Algorithms, and Implementation,” Springer, London, 2011.
[8: Chu et al. 2017]
P. Chu, S. Cho, S. Sim, K. Kwak and K. Cho, “A Fast Ground Segmentation Method for 3D Point Cloud,” in Journal of Information Processing Systems, vol. 13, no. 3, pp. 491-499, June 2017.
[9: Dine et al. 2016]
A. Dine, A. Elouardi, B. Vincke and S. Bouaziz, “Graph-Based Simultaneous Localization and Mapping: Computational Complexity Reduction on a Multicore Heterogeneous Architecture,” in IEEE Robotics Automation Magazine, vol. 23, no. 4, pp. 160-173, Dec. 2016.
[10: Dubbelman & Browning 2015]
G. Dubbelman and B. Browning, “COP-SLAM: Closed-Form Online Pose-Chain Optimization for Visual SLAM,” in IEEE Transactions on Robotics, vol. 31, no. 5, pp. 1194-1213, Oct. 2015.
[11: Engel et al. 2014]
J. Engel, T. Schops and D. Cremers, “LSD-SLAM: Large-Scale Direct Monocular SLAM,” in Proceedings of the European Conference on Computer Vision (ECCV), Zurich, Switzerland, pp 834-849, Sept. 2014.
[12: Galvez-Lopez and Tardos 2012]
D. Galvez-Lopez and J. D. Tardos, “Bags of Binary Words for Fast Place Recognition in Image Sequences,” in IEEE Transactions on Robotics, vol. 28, no. 5, pp. 1188–1197, Oct. 2012.
[13: Grisetti et al. 2010]
G. Grisetti, R. Kummerle. C. Stachniss and W. Burgard, “A Tutorial on Graph-Based SLAM,” in IEEE Intelligent Transportation Systems Magazine, vol. 2, no. 4, pp. 31-43, winter 2010.
[14: Grisetti et al. 2007]
G. Grisetti, C. Stachniss and W. Burgard, “Improved Techniques for Grid Mapping With Rao-Blackwellized Particle Filters, ” in IEEE Transactions on Robotics, vol. 23, no. 1, pp. 34-46, Feb. 2007.
[15: Guo et al. 2009]
R. Guo, F. Sun and J. Yuan, “ICP based on Polar Point Matching with application to Graph-SLAM,” in Proceedings of International Conference on Mechatronics and Automation, Changchun, China, pp. 1122-1127, Aug. 2009.
[16: Guo et al. 2016]
Y. Guo, M. Bennamoun, F. Sohel, M. Lu, J. Wan and N. M. Kwok, “A Comprehensive Performance Evaluation of 3D Local Feature Descriptors,” in International Journal of Computer Vision, vol. 116, no. 1, pp. 66-89, Jan. 2016.
[17: Horn 1987]
B. K. P. Horn, “Closed-form solution of absolute orientation using unit quaternions,” in Journal of Optical Society of America, vol. 4, no. 4, pp. 629-642, Apr. 1987.
[18: Kechagias-Stamatis et al. 2017]
O. Kechagias-Stamatis, N. Aouf and L. Chermak, “B-HoD: A lightweight and fast binary descriptor for 3D object recognition and registration,” in Proceedings of IEEE International Conference on Networking, Sensing and Control (ICNSC), Calabria, Italy, pp. 37-42, May 16-18, 2017.
[19: Kümmerle et al. 2011]
R. Kümmerle, G. Grisetti, H. Strasdat, K. Konolige and W. Burgard, “G2o: A general framework for graph optimization” in Proceedings of IEEE International Conference on Robotics and Automation, Shanghai, China, pp. 3607-3613, May 9-13, 2011.
[20: Li et al. 2016]
L. Li, M. Yang, L. Guo, C. Wang and B. Wang, “Hierarchical Neighborhood Based Precise Localization for Intelligent Vehicles in Urban Environments,” in IEEE Transactions on Intelligent Vehicles, vol. 1, no. 3, pp. 220-229, Sept. 2016.
[21: Li & Lee 2016]
S. Li and D. Lee, “Fast Visual Odometry Using Intensity-Assisted Iterative Closest Point,” in IEEE Robotics and Automation Letters, vol. 1, no. 2, pp. 992-999, July 2016.
[22: Li & Lee 2017]
S. Li and D. Lee, “RGB-D SLAM in Dynamic Environments Using Static Point Weighting,” in IEEE Robotics and Automation Letters, vol. 2, no. 4, pp. 2263-2270, Oct. 2017.
[23: Maligo & Lacroix 2017]
A. Maligo and S. Lacroix, “Classification of Outdoor 3D Lidar Data Based on Unsupervised Gaussian Mixture Models,” in IEEE Transactions on Automation Science and Engineering, vol. 14, no. 1, pp. 5-16, Jan. 2017.
[24: Mur-Artal et al. 2015]
R. Mur-Artal, J. M. M. Montiel and J. D. Tardos, “ORB-SLAM: A Versatile and Accurate Monocular SLAM System,” in IEEE Transactions on Robotics, vol. 31, no. 5, pp. 1147-1163, Oct. 2015.
[25: Mur-Artal & Tardos 2017]
R. Mur-Artal and J. D. Tardos, “Visual-Inertial Monocular SLAM With Map Reuse,” in IEEE Robotics and Automation Letters, vol. 2, no. 2, pp. 796-803, Apr. 2017.
[26: Prakhya et al. 2017]
S. M. Prakhya, J. Lin, V. Chandrasekhar, W. Lin and B. Liu, “3DHoPD: A Fast Low-Dimensional 3-D Descriptor,” in IEEE Robotics and Automation Letters, vol. 2, no. 3, pp. 1472-1479, July 2017.
[27: Prakhya et al. 2015]
S. M. Prakhya, B. Liu and W. Lin, “B-SHOT: A binary feature descriptor for fast and efficient keypoint matching on 3D point clouds,” in Proceedings of IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), Hamburg, Germany, pp. 1929-1934, Sept. 28-Oct. 2, 2015.
[28: Rusinkiewicz & Levoy 2001]
S. Rusinkiewicz and M. Levoy, “Efficient variants of the ICP algorithm,” in Proceedings of Third International Conference on 3-D Digital Imaging and Modeling, Quebec, Canada, pp. 145-152, May 28-June 1, 2001.
[29: Serafin et al. 2016]
J. Serafin, E. Olson and G. Grisetti, “Fast and robust 3D feature extraction from sparse point clouds,” in Proceedings of IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), Daejeon, South Korea, pp. 4105-4112, Oct. 9-14, 2016.
[30: Strasdat et al. 2012]
H. Strasdat, J.M.M. Montiel and A. J. Davison, “Visual SLAM: Why filter?” in Image and Vision Computing, vol. 30, no. 2, pp. 65-77, Feb. 2012.
[31: Tombari et al. 2010]
F. Tombari, S. Salti and L. D. Stefano, “Unique Signatures of Histograms for Local Surface Description,” in Proceedings of European Conference on Computer Vision, Crete, Greece, pp. 356-369, Sept. 6-9 2010.
[32: Tombari et al. 2013]
F. Tombari, S. Salti and L. D. Stefano, “Performance Evaluation of 3D Keypoint Detectors,” in International Journal of Computer Vision, vol. 102, no. 1, pp. 198-220, March 2013.
[33: Wolf & Sukhatme 2004]
D. Wolf and G. S. Sukhatme, “Online simultaneous localization and mapping in dynamic environments,” in Proceedings of IEEE International Conference on Robotics and Automation, LA, USA, pp. 1301–1307, Apr. 26-May 1, 2004.
[34: Wu et al. 2017]
F. Wu, C. Wen, Y. Guo, J. Wang, Y. Yu, C. Wang and J. Li, “Rapid Localization and Extraction of Street Light Poles in Mobile LiDAR Point Clouds: A Supervoxel-Based Approach,” in IEEE Transactions on Intelligent Transportation Systems, vol. 18, no. 2, pp. 292-305, Feb. 2017.
[35: Xia & Wang 2017]
S. Xia and R. Wang, “A Fast Edge Extraction Method for Mobile Lidar Point Clouds,” in IEEE Geoscience and Remote Sensing Letters, vol. 14, no. 8, pp. 1288-1292, Aug. 2017.
[36: Zhang & Singh 2017]
J. Zhang and S. Singh, “Low-drift and real-time lidar odometry and mapping,” in Autonomous Robots, vol. 41, no. 2, pp. 401-416, Feb. 2017.
[37: Zhong 2009]
Y. Zhong, “Intrinsic shape signatures: A shape descriptor for 3D object recognition,” in IEEE 12th International Conference on Computer Vision Workshops (ICCV), Kyoto, Japan, pp. 689-696, Sept. 27-Oct. 4, 2009.
[38: Zhuang et al. 2013]
Y. Zhuang, N. Jiang, H. Hu and F. Yan, “3-D-Laser-Based Scene Measurement and Place Recognition for Mobile Robots in Dynamic Indoor Environments,” in IEEE Transactions on Instrumentation and Measurement, vol. 62, no. 2, pp. 438-450, Feb. 2013.
[39: Zou et al. 2016]
Y. Zou, T. Zhang, X. Wang, Y. He and J. Song, “BRoPH: A compact and efficient binary 3D feature descriptor,” in IEEE International Conference on Robotics and Biomimetics (ROBIO), Qingdao, China, pp. 1093-1098, Dec. 3-7, 2016.