{'fraction_non_alphanumeric': 0.019427872112589874, 'fraction_numerical': 0.005048187241854061, 'mean_word_length': 4.908269317668323, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
The Semi-dense ICP Algorithm Based on the SIFT Feature Points Neighborhood

The ICP algorithm based on RGB-D images is one of the most widely used and the most effective point cloud registration algorithms. How to improve the registration accuracy, registration speed and robustness of the ICP algorithm has become an important research hotspot at present. However, existing algorithms have low computational efficiency under large-scale point cloud data, and when the overlap between point clouds is small, the registration accuracy is low. To deal with these problems, this paper proposes a semi-dense ICP algorithm based on SIFT feature points neighbourhood. First, the algorithm selects the SIFT feature point matching algorithm as the rough registration method of ICP, because the SIFT feature points have the advantage of rotation invariance, illumination invariance, and scale invariance; then based on the SIFT feature points, the algorithm selecting its neighbourhood as the matching range. The experimental result shows that this algorithm has the better registration accuracy and computational efficiency.


Introduction
The Point cloud registration has been applied in many important fields, such as medical inspection, computer vision, positioning and mapping of mobile robots [1]. Iterative closest point (ICP) is one of the earliest and most commonly used algorithms in the point cloud registration fields. ICP algorithm was proposed by Besl and Mckay in 1992 [2]. It has the advantages of high accuracy and simple implementation. It is mainly used in the reconstruction of the three-dimensional model of objects and the calculation of the pose transformation between cameras in the front-end visual odometer (VO) of the visual SLAM system [3]. How to improve the registration accuracy, registration efficiency and the robustness of the ICP algorithm has become a research hotspot for many scholars and researchers.
3D point cloud data is usually obtained by scanning the target object with a laser sensor, but due to a series of advantages such as low cost, high accuracy and fast speed, RGB-D cameras have begun to gradually replace laser sensors as the main method of acquiring 3D point cloud data [4]. Therefore, the research of ICP algorithm has also turned to point cloud registration based on RGB-D images.
There are two main methods for ICP registration: sparse method and dense method. The sparse method computes registration based on the feature points [5][6][7][8]. In contrast, the dense method uses all point clouds to compute registration which makes full use of point cloud data. However, in large-scale data registration, the dense method requires a large amount of calculation and it is difficult to ensure real-time performance. The sparse method can reduce a big amount of the data which needs to be calculated, and can also greatly improve the calculation speed [9][10][11]. But the sparse method can't be used when there are few feature points. In order to solve the problem of large registration error and low registration efficiency in the original ICP algorithm, in this paper, we combine the advantages of the dense method and the sparse method, propose a semi-dense ICP algorithm based on the SIFT feature points neighborhood.

The ICP Algorithm
The ICP algorithm is the optimal registration means based on the least squares. It iteratively updates the correspondence between two point clouds, and calculates the transformation relationship between two point clouds to obtain the optimal rotation transformation matrix R and translation transformation matrix t. The ICP algorithm is divided into two processes: rough registration and precise registration [12]. Rough registration mainly includes three steps as follow: extracting feature points, matching feature points, and calculating the initial transformation matrix. Precise registration mainly includes three steps: point cloud data conversion, matching range selection, and calculating transformation matrix with iterative closest point. The ICP algorithm is mainly used in the precise registration stage. The matching range should be selected in the first image (reference point cloud) and the matching search range should be determined in the second image (target point cloud). There are many ways to select the matching range. According to the number of participating points in the matching range, it can be divided into: dense matching method and sparse matching method.
The matching range of the dense ICP algorithm is the entire point cloud. There are several reasons for this algorithm that will affect the registration accuracy: • When the amount of point cloud data is relatively large, it will cause a very large amount of calculation and it is difficult to meet real-time performance.
• There will be non-overlapping parts of the point cloud acquired by the same object under different viewing angles. If these parts are also involved in finding matching points, it will get wrong matching points and cause errors in the calculation results.
• When the overlap between the point clouds of the two pictures is very small, besides all the points in the target point cloud are still selected as matching search area, which will increase the additional calculation.
Because of the shortcomings of the ICP algorithm, some scholars [13] proposed that SIFT feature points can be used to improve classical ICP algorithm. In the precise registration stage, only the threedimensional points corresponding to the SIFT feature points in the reference point cloud are extracted to participate in matching step.
The ICP algorithm based on the SIFT feature point extraction can reduce the amount of calculation. However, when the amount of images' texture information is relatively small or the overlapping area is small, the number of SIFT feature points will be very small. These feature points are only a small part of the entire point cloud data. It makes the final calculation result tend to be local optimization and lead to wrong calculation results.

Semi-dense ICP Algorithm
To overcome the defects of the classic ICP algorithm and the ICP algorithm based on SIFT feature points, this paper advances an ICP iterative algorithm based on the SIFT feature points neighborhood. The proposed algorithm screens the reference point cloud that participates in the iterative calculation in the ICP algorithm, so this algorithm is a semi-dense ICP algorithm. In addition, this algorithm improves the method of selecting the matching search area of the target point cloud, which can greatly reduce the amount of calculation and the number of iteration. When the overlapping part is relatively small, the algorithm has good robustness and accuracy.

Process of The Algorithm
The process of the algorithm is as follows: • Record two RGB images from different angles acquired by the RGB-D camera as I1 and I2,the Since the SIFT feature point pair matching from the target point cloud and the reference point cloud must belong to overlapping part of two point clouds in different perspectives, its x nearest neighbor points should also belong to the point cloud overlapping part. Similarly, the matching points of these neighborhood points must also belong to the x nearest neighbor points of the SIFT matching point of the target point cloud. In order to ensure that every point in Ui can find the correct matching point, the number of neighboring points of the SIFT point on the target point cloud should be set larger, which is 2x instead. Using the above method, the points in the non-overlapping part of the point cloud do not participate in the ICP iterative calculation, which greatly reduces unnecessary calculations and mismatches and improves the robustness of the algorithm.

The Outlier Rejection Algorithm
During each iteration of the matching operation, there will be certain outliers when searching for the closest point match, which needs to be removed by the mismatch removal algorithm [14]. This paper uses a dynamic threshold removal algorithm, which calculates a dynamic threshold tk based on the 3D Euclidean distance of matching point pairs and the spatial distance of SIFT point pairs (Where k represents the kth iteration of the ICP algorithm). Matching point pairs whose 3D Euclidean distance is larger than the dynamic threshold tk are mismatching point pairs, which need to be eliminated and don't participate in the calculation of the transformation matrix R and t. For the point with a 3D Euclidean distance larger than 5 times the dynamic threshold tk, it is considered that the point belongs to the point in the non-overlapping area of the point cloud. Such a point will not find the correct matching point, so this point will no longer participate in finding the closest matching point in the subsequent iteration process.
The calculation process of the dynamic threshold tk is as follows: This paper first calculates and sorts the Euclidean distance of all the matching feature point pairs, selects the first 60% of the SIFT feature point pairs with smaller Euclidean distance, and calculates the average Euclidean distance difference df k . Finally, the dynamic threshold tk is calculated according to df k and er k .(Where c is a fixed value).

Experiment Result
In this paper, OPENCV is used to implement a semi-dense ICP algorithm based on the SIFT feature points neighborhood, and related experiments are carried out. The test object used in the experiment is RGB-D data taken by Kinect camera, from RGB-D Object Dataset [15]. Each object in the data set is placed on a slowly rotating round turntable. The Kinect camera shoots at a frequency of 30Hz to obtain a sequence of 640*480 RGB pictures and the depth information of the pictures. In this paper, the food can data set is selected as the test object for the experiment. The 3D point clouds at different angles are shown in figures 1 and 2. Figures 1 and 2 are two initial point cloud data to be registered, using dense ICP algorithm, sparse ICP algorithm based on SIFT feature points, semi-dense ICP algorithm based on the SIFT feature points neighborhood to perform point cloud registration. The calculation time and the registration errors of the three algorithms are shown in figure 3.   As shown in figure 5, the ICP algorithm based on the SIFT feature point neighborhood proposed in our paper has the smallest registration error among the three ICP algorithms. In figure 3, the dense ICP algorithm has the longest calculation time. The calculation time of the ICP algorithm based on the SIFT feature points neighborhood proposed in this paper is a little bit higher than the calculation time of ICP algorithm based on SIFT feature point, but they are all within 10ms. Part of the reason is that because the ICP algorithm based on the SIFT feature points neighborhood needs to calculate the dynamic threshold when removing the mismatched points, proposed algorithm increases the registration accuracy while also increasing a certain amount of calculation.
The ICP algorithm based on the SIFT feature points neighborhood proposed in our paper can obtain good registration accuracy even when the overlap between a reference point cloud and a target point cloud is small. It is shown in figures 4 and 5, there is less overlap between the two point clouds. As shown in figures 6, the registration error of the ICP algorithm based on the SIFT feature point neighborhood proposed in this paper is the smallest of the three algorithms, which is 0.0034m. Therefore, the improved ICP algorithm proposed in this paper has a small overlap between the two    Except the registration of point clouds, the ICP algorithm and its improved algorithm can also be applied to the registration between consecutive point clouds of sequential RGB-D images to obtain the relative conversion relationship. This application is a visual odometer, which can be used as the frontend of the SLAM system. The most widely used test data set for visual odometry and SLAM systems is the TUMRGB-D data set [16]. The test data set in this paper is the fr1_xyz image set in TUMRGB-D. The image set was calculated using the classic ICP algorithm, the ICP algorithm based on SIFT feature points, and the ICP algorithm based on the SIFT feature points neighborhood, and the experimental results were evaluated using the automatic evaluation tool provided by the TUM website. The evaluation results are shown in table 1. It can be seen that the ICP algorithm based on SIFT feature points neighborhood proposed in this paper is superior to the other two algorithms except that only std (RPErot) is slightly lower than the ICP algorithm based on SIFT feature points. Therefore, as a whole, the ICP algorithm based on SIFT feature points neighborhood proposed in this paper has better accuracy and smaller registration error.

Conclusion
This paper proposes a semi-dense ICP algorithm based on the SIFT feature points neighborhood, which selects the neighborhood of SIFT feature points as the matching range of the ICP algorithm in