{'fraction_non_alphanumeric': 0.027522935779816515, 'fraction_numerical': 0.0081913499344692, 'mean_word_length': 4.9312087057909055, '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}}
A Novel Coarse-to-fine Registration for 3D Point Cloud Based on Feature Points

This paper proposes a coarse-to-fine registration algorithm for 3D point cloud. A novel feature points extraction method is presented, following an integrated local feature descriptor including Gaussian curvature, average curvature and point density for each point, through which we can achieve the coarse registration. Then, the ICP method is employed to refine the registration results with a good initial guess. Experiments including different simulated data sets demonstrate the applicability of the proposed methods. Meanwhile, the proposed coarse-to-fine registration algorithm is demonstrated to be robust to common nuisances, including noise and varying point cloud resolutions, and can achieve high accuracy and computation efficiency. Introduction Registration of point clouds captured by 3D scanner devices is a fundamental problem in 3D computer vision. Numerous application have been developed, including 3D modeling [1,2], object recognition [3,4], pose estimation [5], face recognition [6] and surface alignment [7,8]. The goal of the registration is to find the optimal transformation matrix to align two range images as close as possible. The transformation matrix includes rotation and translation parameters. According to the matching accuracy, registration can be divided into coarse registration and fine registration. In general, the coarse registration is an approximate matching to provide good initial position for fine registration. In coarse registration, the property of each point is extracted to search the correspondence between two point clouds. To improve the efficiency, generally, only the points which can effectively contribute to finding the good corresponding point pairs are used. In literature, the normal and curvature are the popular information for point description [9,10]. However, they are difficult to describe the distinctive points for the highly symmetric or planar models, and the process might result in selecting many points that essentially contain the same information. Rusu [11] et al. proposed a persistent feature histograms (PFH) to match point clouds from different views, and each point was estimated by a 16D features based on the normal. Guo [4] et al. presented a rotational projection statistics (RoPS) for local feature description of point set. Yang [12] et al. proposed a local feature statistics histogram (LFSH) for registration, and in LFSH the local depth, point density, and normal were encoded to describe the local shape geometries. In fine registration, iterative closest point (ICP) [13] is the best known method. A lot of its variants have also been developed to define better distance between two data sets [14,15,16]. The necessity of coarse registration can be demonstrated in two aspects. First, the ICP algorithms may get trapped in a local minimum if two point clouds are not spatially close. Second, a good initial transformation can significantly improve the computational efficiency of the ICP algorithm. In the literature, there are many effective representations to encode local shape geometry to do the coarse


Introduction
Registration of point clouds captured by 3D scanner devices is a fundamental problem in 3D computer vision. Numerous application have been developed, including 3D modeling [1,2], object recognition [3,4], pose estimation [5], face recognition [6] and surface alignment [7,8]. The goal of the registration is to find the optimal transformation matrix to align two range images as close as possible. The transformation matrix includes rotation and translation parameters. According to the matching accuracy, registration can be divided into coarse registration and fine registration. In general, the coarse registration is an approximate matching to provide good initial position for fine registration.
In coarse registration, the property of each point is extracted to search the correspondence between two point clouds. To improve the efficiency, generally, only the points which can effectively contribute to finding the good corresponding point pairs are used. In literature, the normal and curvature are the popular information for point description [9,10]. However, they are difficult to describe the distinctive points for the highly symmetric or planar models, and the process might result in selecting many points that essentially contain the same information. Rusu [11] et al. proposed a persistent feature histograms (PFH) to match point clouds from different views, and each point was estimated by a 16D features based on the normal. Guo [4] et al. presented a rotational projection statistics (RoPS) for local feature description of point set. Yang [12] et al. proposed a local feature statistics histogram (LFSH) for registration, and in LFSH the local depth, point density, and normal were encoded to describe the local shape geometries. In fine registration, iterative closest point (ICP) [13] is the best known method. A lot of its variants have also been developed to define better distance between two data sets [14,15,16].
The necessity of coarse registration can be demonstrated in two aspects. First, the ICP algorithms may get trapped in a local minimum if two point clouds are not spatially close. Second, a good initial transformation can significantly improve the computational efficiency of the ICP algorithm. In the literature, there are many effective representations to encode local shape geometry to do the coarse registration, including local depth, normal, curvature and point density. Most existing efforts focus on describing the local shape geometry from a single aspect using 2D or 1D representations, and therefore suffer from limited descriptiveness and/or poor robustness. In this context, we integrate the curvature and point density to describe the point feature. On the other hand, the computation of these local features is time-consuming and can be inaccurate for raw input datasets. To solve this problem, we first extract some feature points from the source point cloud. Finally, a coarse-to-fine registration method is proposed, with high computation efficiency and good robustness. The contributions of this work are as follows: (1) A novel feature point extraction method is proposed. It is significantly fast for computation and quite distinctive.
(2) The defined feature points are extracted, followed by an integrated local feature descriptor for each point.
(3) A coarse-to-fine registration algorithm for 3D point cloud is proposed. The experiments demonstrate that the algorithm is fast and precise. The remainder of this paper is organized as follows. Section 2 introduces the details of the coarse-to-fine registration algorithm. In Section 3, experiments to verify the applicability of our method are conducted including different simulated data sets. Conclusion and future work are discussed in Section 4.

Coarse-to-fine Registration Algorithm for 3D Point Cloud
In practice, a state-of-the-art point clouds registration algorithm should be able to automatically and accurately align two point clouds under a variety of nuisances, including small overlaps, noise and varying point cloud resolution [12]. The goal of 3D registration is to find the transformation matrix that can minimize the distance between two point clouds, i.e., the source point cloud s P and the target point cloud t P . The registration is usually conducted in two steps: coarse registration and fine registration. Coarse registration can be conducted manually or based on geometric characteristics of the surface. In fine registration, the transformation parameters are achieved iteratively to minimize the sum of the squared errors between the localized measurement points and their corresponding (closest) points on the design surface [17]. In this section, we will detail the proposed coarse-to-fine registration process for 3D point cloud.

Feature Points Based Coarse Registration
When the measurement coordinate system is quite different from the design coordinate system, three-dimensional shape searching is required to match the measurement points with the design surface. Three-dimensional shape searching is a key research subject in engineering and computer graphics. In most of the developed shape search techniques, geometry characteristic of the freeform surface are described by simple geometrical evaluation measures. In coarse registration, the intrinsic geometric properties that are independent of coordinate system, such as curvatures, are often used to align the digitized manufactured surface with the design surface.
The geometrical evaluation process is time-consuming and can be inaccurate for raw input datasets. In this subsection, we will first extract some feature points from the source point cloud, and then find out the corresponding points in the target point cloud. At last, the coarse transformation matrix can be achieved through a non-linear optimization problem for the four pairs of points Feature points extraction. Given a source point cloud s P and a target point cloud t P , the first process is to extract local features for the two point clouds. In most cases, the raw input datasets are extremely large for matching algorithms, and would cause high computation costs. In general, there are two speed-up strategies [12]. One is to randomly sample points from the source data and then match these sample points against all the points in the target data [18]. The other is to select a set of feature points from the raw data sets, e.g., THRIFT [19] and MeshHOG [20]. In this paper, we propose a new method to select the feature points. From [17], we know that the minimum number of required source measurement points for rough localization is four. Among all the measurement points, selection of the proper locations of these feature points plays an important role on the quality of coarse registration. The feature points can be selected manually. In this paper, a heuristic methods has developed to automatically select the four feature points.
Since the approximated curvature measures at the boundaries of the point cloud can be inaccurate, the feature points should not be selected on the boundaries. Our intuitive idea is to select four feature points which forms a skeleton-like structure for the source point cloud The four feature points selected by our method for a point cloud of a mannequin are shown in Figure 1. Local feature extraction. Local feature-based methods for 3D registration align models by using consistent point-to-point correspondences. They are usually generated via matching feature descriptors. The feature descriptor should be invariant to rigid transformation. In addition, the feature descriptor should be distinctive and robust to various nuisances such as noise and varying point cloud resolution, in order to provide sufficient correct correspondences. It is well known in mathematics that topology structure and differential structure are invariant to rigid transformation, so we will introduce a fast and robust local feature descriptor by computing the statistics of three local invariant features.
We select curvature as our first and second local features, which can be treated as part of the differential structure of the surface. The computation of curvature of the selected point p concludes three steps. First, we find out the k nearest points of p in the point cloud. Then, we use a quadric parametric surface ( , ) S u v to fit the k+1 points, i.e., the point p and its k nearest points. At last, the curvature of p can be achieved, Kcurv is the Gaussian curvature, and Hcurv is the average curvature.
The ICP Based Fine Registration Through coarse registration, an initial guess is obtained and will be used for the subsequent optimization-based fine localization. In most of the optimization methods, an accurate initial guess is needed to obtain the global optimum because inaccurate initial guess increases the risk of obtaining a local optimum. Having roughly registered two point clouds, we are left with the task of further minimizing the registration error between them. In this paper, the ICP algorithm is used, where a non-linear local optimization problem is solved to minimize the residual error. Assume the current point cloud is r P after the coarse registration, and the transformation for the fine registration is f T . The fine registration process is to find the transformation between r P and t P with the help of the ICP method, which is a two-step method. First, for each point ,

Results and Discussion
In this section, we validate the performance of the proposed method on the simulated data sets. Simulated data sets are employed from surfaces of known parametric expressions but varying complexity, and different distributions of the point cloud data are considered. We generate the simulated models by sampling randomly on two parametric surfaces. Denote the parametric surface by ( , ) S u v . Without loss of generality, we assume the parametric domain is and v direction. Obtain the 3D point cloud 1 P by sampling randomly on each of the kk  meshes. Repeat the process, and two different 3D point clouds 12 , PP both with kk  points are achieved. We can also set two different number 12 , kk for the two-step sampling. 1 P is treated as our target point t P . The point cloud 2 P is then transformed from their initial position by rotating 0.2 , 0.1 , and 0.3 about the x, y and z axis, respectively, and translating 20, 50 and 40 along the x, y, and z axis, respectively, and the point cloud 3 P is obtained, which will be treated as the source point cloud  15 15 30 20    (1). The red one is the target point cloud, the blue one is the source point cloud, the green one is the point cloud after coarse registration, and the black one is the point cloud after fine registration. Figure 2. Registration results for case (2). The red one is the target point cloud, the blue one is the source point cloud, the green one is the point cloud after coarse registration, and the black one is the point cloud after fine registration.
As the Figure 2 and Figure 3 show, the red one is the target point cloud, the blue one is the source point cloud, the green one is the point cloud after coarse registration, and the black one is the point cloud after fine registration. We can see that the coarse registration gives an accurate guess for the localization, following the fine registration to complete the final registration results.

Conclusion
In this paper, a fast and robust coarse-to-fine registration algorithm was proposed for the 3D point cloud. A novel feature points extraction method was present, and an integrated local feature descriptor was defined for each point. The result of the coarse registration verified the applicability of the two parts. Then, the ICP method was employed to refine the registration results. The experiments including different simulated data sets demonstrated the high accuracy and computation efficiency of our methods. In the future work, the effects of the local features we used will be discussed, and actual scanned data sets will be employed to test our method further.