Sage Journals: Discover world-class research

Abstract

Motivated by the high speed but insufficient precision of the existing fast point feature histogram algorithm, a new fast point feature histogram registration algorithm based on density optimization is proposed. In this method, a 44-section blank feature histogram is first established, and then a principal component analysis is implemented to calculate the normal of each point in the point cloud. By translating the coordinate system in the established local coordinate system, the normal angle of each point pair and its weighted neighborhood are obtained, and then a fast point feature histogram with 33 sections is established. The reciprocal of the volume density for the central point and its weighted neighborhood are calculated simultaneously. The whole reciprocal space is divided into 11 sections. Thus, a density fast point feature histogram with 44 sections is obtained. On inputting the testing models, the initial pose of the point cloud is adjusted using the traditional fast point feature histogram and the proposed algorithms, respectively. Then, the iterative closest point algorithm is incorporated to complete the fine registration test. Compared with the traditional fine registration test algorithm, the proposed optimization algorithm can obtain 44 feature parameters under the condition of a constant time complexity. Moreover, the proposed optimization algorithm can reduce the standard deviation by 8.6% after registration. This demonstrates that the proposed method encapsulates abundant information and can achieve a high registration accuracy.

Keywords

Volume density fast point feature histogram iterative closest point registration

Introduction

Motivation

With the increasing demands for applications of point clouds, map-making,^1,2 cultural relic research, geological research,³ autonomous driving, and medical simulation rely heavily on high-quality point cloud data. Although a point cloud can be obtained via a scanner, binocular camera, or optical radar, a full point cloud model cannot be obtained through a single measurement, owing to the immobility of the scanning target and the large size of the model. To obtain full point cloud data, the original point cloud data acquired from various perspectives or coordinates should be transformed into a unified reference system. Manual and automatic registration algorithms represent two common methods used for point cloud registration. However, the manual registration algorithm requires several punctuation points attached to the surface of the target, which leads to low efficiency. For this reason, the automatic registration algorithm has attracted the attention of many researchers.

Literature review

Solving the transformation matrix between two (or more) sets of point clouds represents the core of a point cloud registration algorithm. In 1992, Besl and Mckay proposed a classic registration algorithm called iterative closest point (ICP).⁴ The corresponding relationship between two point clouds (corresponding point pair) is obtained by finding the overlapping parts of the two point clouds, and then the transformation matrix of the overall point clouds is solved.

However, the ICP algorithm has several limitations, such as the requirement for overlapping regions between two point clouds and strict requirements on the initial poses of the point clouds. If the initial poses do not satisfy the requirements, then the registration may fall into a local optimum or provide an incorrect registration. The most common current solution to this issue is to perform a coarse registration operation on the point cloud to obtain a suitable initial pose before employing the ICP. For example, this point could involve the variable metric⁵ registration algorithm, integrated feature descriptors registration algorithm,⁶ or using the Plücker straight line to calculate the relative pose parameters.⁷ Unfortunately, these proposed methods are limited to specific situations. Radu Bogdan Rusu proposed a universal coarse registration algorithm, in which the coordinates and normal information of corresponding point pairs are considered as features.⁸ The parameters of the description information are reduced from 12 to 4 by shifting the coordinate system, and then the four obtained eigenvalues are equally divided into five intervals. The number of points in a point cloud falling into each interval is counted to construct the point feature histogram. This algorithm can extract sufficient information and features, but is highly time-consuming. For this reason, Rusu proposed the fast point feature histogram (FPFH) algorithm.⁹ This method only calculates the normal information of the center point and its neighborhood points so that the speed of the algorithm is significantly improved. Meanwhile, the accuracy of the point feature histogram (PFH) is considerably reduced owing to a partial loss of information.

To enhance the accuracy of FPFH, some researchers have employed the Bhattacharyya distance of the FPFH feature for two point clouds as a new metric optimization parameter.¹⁰ Combined with the color texture direction feature histogram and viewpoint feature histogram,¹¹ a new algorithm can be constructed. To obtain a high-speed registration algorithm, researchers have attempted to utilize pre-processing clustering to obtain effective information points,¹² calculate the surface normal vector to optimize the FPFH feature,¹³ and combine the transformation matrix between point clouds and sequential images¹⁴ to enhance the accuracy of FPFH. Although the particle swarm algorithm^15,16 has recently been implemented for point cloud registration, it is easy to fall into a local optimum and difficult to find optimal parameters to complete point cloud registration, owing to the inherent drawbacks of the particle swarm algorithm. It should be noted that there is currently no proposed method that can simultaneously achieve a high registration speed and accuracy. Thus, an approach to building a point cloud registration algorithm with a high speed and accuracy has become the focus of researchers.

Contributions and organization

The proposed method has two major contributions. (1) Considering the good rotational and scale invariance of a density, an FPFH based on the density optimization algorithm is proposed, which can achieve high-accuracy registration results. (2) The algorithm can ensure that the proposed method and traditional FPFH algorithm have the same time complexity by calculating the volume density features of a central point and its neighborhood points.

In the next section, this article will introduce the principles of the proposed algorithm and then illustrate its advantages in detail. Simulations will be described in the third section. The fourth section will analyze the simulation results and compare the density-FPFH algorithm with other algorithms. The fifth section will present a discussion on the robustness of the proposed method. Finally, conclusions will be provided in the last section.

FPFH algorithm based on volume density optimization

Algorithm overview

Prior to the fine registration of a point cloud, it is necessary to obtain a suitable initial pose. The common approach is to apply the classic FPFH algorithm. The surface normal and curvature of a point cloud are the most important features and simple to calculate, only requiring the extraction of the information of the central point and its neighborhood using principal component analysis algorithm.¹⁷ However, the normals of each surface are reasonably close to each other owing to the huge amount of data in a point cloud. If only either the normal or curvature is considered, then a large number of approximate points are obtained. Moreover, the normal and curvature of the center point are obtained using the k-domain approximation, which is not sufficiently accurate. Therefore, it is difficult to find the correct corresponding pose simply by using the normal line. The PFH containing the point cloud normal interaction information and statistical information becomes a significant local feature descriptor of the point cloud¹⁸ during this operation. However, the PFH is required to calculate the interconnections between all the pairs of points in the point cloud. Suppose that any query point has K neighborhood points, and its computational complexity is $σ (K^{2})$ . If the point cloud has n points, then its complexity is $σ (n K^{2})$ .

If the size of the point cloud increases, the number of required calculations increases dramatically. Therefore, an accelerated version of the PFH, called the FPFH algorithm, is more widely used in practice. The FPFH algorithm reduces the required amount of calculation by reducing the amount of acquired information. Thus, the calculation speed of FPFH is improved at the expense of reducing point cloud features. Moreover, the feature calculations of FPFH and PFH need to traverse the point cloud from 0 to each point in a pair. Taking each point as the center with the query point being the starting point or critical point, the normal deviation is 0 for both FPFH and PFH. Therefore, an FPFH based on volume density optimization is proposed.

Calculation of three deflections

The interactive normal deviation between any two points in the point cloud is calculated according to the traditional FPFH algorithm proposed by Rusu. Suppose that, for a point coded as $P_{t}$ in the point cloud, there exist points P_t₁, P_t₂, P_t₃, P_t₄, P_t₅, and P_t₆ in its neighborhood, with a search radius of r, as shown in Figure 1. Points P₁, P₂, P₃, P₄, and P₅ denote other central points.

Figure 1.

Schematic diagram of overall calculation.

Let the normals of $P_{t}$ and $P_{t 1}$ be $N_{t}$ and $N_{t 1}$ , respectively. It is obvious that the angular projections of the two normals are different. To obtain the relationship between the points $P_{t}$ and $P_{t 1}$ , the coordinate system $u - v - w$ is established with the origin at point $P_{t}$ , as shown in Figure 2. $α$ is the angle between the normal of the origin and the translation axis, $β$ is the angle between the normal of the target point and the v-axis, and $γ$ is the angle between the projection of the normal of the target point in the u–v plane and the u-axis.

u = N_{t}

(1)

v = \frac{[P_{t 1} - P_{t}]}{{‖ P_{t 1} - P_{t} ‖}_{2}} \times u

(2)

w = u \times v

(3)

Figure 2.

Schematic diagram of normal declination calculation.

The interactive normal deviation between the points $P_{t}$ and $P_{t 1}$ can be calculated by moving the origin from $P_{t}$ to $P_{t 1}$ , and $α, β, and γ$ are used as descriptors.

Assume

d = ‖ P_{t 1} - P_{t} ‖_{2}

(4)

α = \frac{(P_{t 1} - P_{t})}{d} \cdot u

(5)

β = v \cdot N_{t 1}

(6)

γ = \arctan (w \cdot N_{t 1}, u \cdot N_{t 1})

(7)

where d represents the distance between the two points in a point cloud.

The process is divided into three steps. (1) The normal deviation relationship between the point $P_{t}$ and its neighborhood points is calculated centered on point $P_{t}$ , coded as $SPFH (P_{t})$ (simple point feature histogram). (2) The normal deviation relationships between P_t₁, P_t₂, P_t₃, P_t₄, P_t₅, and P_t₆ and their neighborhood points are calculated centered on points P_t₁, P_t₂, P_t₃, P_t₄, P_t₅, and P_t₆, respectively, coded as $SPFH (P_{ti})$ . (3) The obtained relationships are supplemented by weights (coded as the fast point feature histogram $FPFH (P_{t})$ ), as follows

FPFH (P_{t}) = SPFH (P_{t}) + \frac{1}{K} \sum_{i = 1}^{K} \frac{1}{w_{i}} \cdot SPFH (P_{ti})

(8)

where $w_{i}$ is the weight for points $P_{t}$ and $P_{ti}$ , which is inversely proportional to the distance, and K is the number of neighborhood points.

Therefore, the normal deviation relationship ( $α, β, and γ$ ) at any point in the point cloud is successfully obtained, and the time complexity is only $σ (K)$ . If the size of the point cloud is n, then the time complexity is $σ (nK)$ .

Volume density calculation

In this section, the fourth metric, called the volume density, will be calculated. The new volume density metric is proposed because the number of neighborhood points has been calculated during the calculation of $α, β, and γ$ . In the traditional definition, the density $ρ$ is defined as the ratio of mass m to volume v. In this study, the volume density is defined as the number of points per unit volume. In fact, the FPFH is calculated with a specified radius r, and thus K-dimensional tree searching is performed with the same radius r to calculate the volume density of the central point

ρ_{VD} = \frac{K}{V}

(9)

V = r^{3}

(10)

where $ρ_{VD}$ is the volume density and V is the volume.

If the features of the whole point cloud are calculated using the same radius r, then the volume V can be deemed as a constant. Furthermore, $ρ_{VD}$ is completely determined by K and can be simplified as follows

ρ_{VD} = K

(11)

It is concluded that if the FPFH feature is calculated by the radius r neighborhood query, the center point volume density can use the number of its neighborhood points K to represent.

Taking the point $P_{t}$ in the point cloud as the center, a sphere of radius r is obtained. Taking a point $P_{t 1}$ in the neighborhood of $P_{t}$ to be used as the center of a sphere, another sphere of radius r is obtained. The number of points in each sphere gives the volume density of the point $P_{i}$ , and the specific plane diagram is shown in Figure 3.

Figure 3.

Schematic diagram of density.

The volume density of the center point is not sufficient to represent the volume density of the sphere, and thus the volume densities of all neighborhood points at the center point are calculated. The reciprocal of the sum for the volume densities of each neighborhood point is added to the central point’s volume density, and the result is adopted as the final feature. To improve the calculation speed, the actual volume density calculation is performed synchronously with the calculation of $α, β, and γ$ . Figure 1 illustrates the proposed method, where $P_{t}$ is the center point and K is the number of neighborhood points searched with a radius of r (recorded as the center point density $ρ_{VD} (P_{t})$ ). The neighborhood points obtained according to $P_{t}$ are utilized as center points in the next loop. The number of neighborhood points queried with the same radius r is used to calculate the neighborhood volume density (denoted as the neighborhood point density $ρ_{VD} (P_{ti})$ ). The final feature $ρ_{VDF} (P_{t})$ is obtained

ρ_{VDF} (P_{t}) = ρ_{VD} (P_{t}) + \frac{1}{\sum_{i = 1}^{6} ρ_{VD} (P_{ti})}

(12)

Finally, the volume density feature is combined with the three deviation angles $α, β, and γ$ to obtain the 44-interval FPFH algorithm, as shown in Figure 4.

Figure 4.

Schematic diagram of feature combination.

Compared with the traditional FPFH algorithm, the time complexity of the proposed algorithm is unchanged, and the number of required calculations is increased slightly. Moreover, the information missing in the traditional FPFH algorithm is preserved. Density information that can be used for registration is still available even if the current query point has no normal deviation.

Algorithm registration

Although the point cloud is adjusted using the density-FPFH algorithm to obtain a good initial pose, it is still necessary to subsequently perform secondary fine registration. The core principle of the ICP algorithm is the calculation of the point cloud transformation matrix.¹⁹ A good initial pose, which can be obtained by the density-FPFH algorithm, is required for its application.²⁰ Thus, the ICP algorithm is adopted to perform the secondary fine registration. To verify the speed and accuracy of the proposed algorithm, a registration simulation test is performed.

Volume density–optimized FPFH registration test

Registration scheme design

The classic Stanford rabbit model (the size of two point cloud models is 35,974) is adopted to verify the speed and accuracy of the proposed algorithm. A C++ compiler is used for the registration test, while Geomagic Studio 12 is used for the error analysis. The algorithm is designed as follows:

Input: Two rabbit point cloud models with different initial poses (the source point $P_{S}$ and the target point $P_{T}$ ).

Output: The registered point cloud $P_{F}$ and source point cloud $P_{S}$ .

Step 1: Any point $P_{t}$ is selected from the point clouds $P_{S}$ and $P_{T}$ , respectively. Using the search radius r, $P_{t}$ and its neighborhood points $P_{ti}$ are obtained using the K-dimensional tree searching method.

Step 2: According to the above-mentioned steps for solving the three deviation angles, any point $P_{t}$ and its neighborhood points are traversed to calculate the angular features, and then the deviation descriptors $α, β, and γ$ are obtained. The first three metrics of $P_{s}$ and $P_{T}$ are obtained and divided into 11 intervals so that the number of points falling into each interval is calculated.

Step 3: K-dimensional tree searching is employed to search for $P_{S}$ and $P_{T}$ under the same radius r. The number of neighborhood points is calculated for every center point $P_{t}$ in both point cloud models. Then, the number of neighborhood points for each searched point $P_{ti}$ will be calculated in the next loop. The fourth metric value, the volume density, is obtained according to equation (12).

Step 4: The upper and lower limits of the volume density are calculated for each point cloud. The value interval is divided equally into 11 parts, and the number of points falling into each interval is counted.

Step 5: The interval value of $α, β, and γ$ is extracted at each point, and the density value $ρ_{VDF} (P_{t})$ obtained in Step 4 is added to the histogram. Then, every point in the two point clouds has a different value of $α$ , $β$ , $γ$ , and $ρ_{VDF} (P_{t})$ , and intervals are obtained, as described in detail in the density-FPFH algorithm.

Step 6: The sample consensus initial alignment,^21,22 which is characteristic in the density-FPFH algorithm, is used to perform the coarse registration test. The point cloud pose is adjusted to obtain the coarse point cloud $P_{c}$ .

Step 7: The registered point cloud $P_{F}$ is obtained using the ICP algorithm to register $P_{S}$ and $P_{c}$ .

Registration parameter design

The utilized test data consist of the classic Stanford rabbit model, where the total number of points is 35,974. If the whole point cloud is implemented to perform the registration test, this will be time-consuming. Therefore, the point cloud should first be sampled. Generally speaking, the remaining point cloud can represent the features of the whole model with a smaller size. The sampling radius is set to a suitable value of 1 mm after several tests. The size of the remaining point clouds is 819. To ensure the accuracy of the test results, the volume density is set as a variable. The remainder of the registration algorithm parameters are the same, as shown in Table 1.

Table 1.

Registration algorithm parameters.

Algorithm parameter comparison	Density radius (mm)	Feature radius	Maximum number of iterations	Minimum corresponding point distance
Traditional FPFH	None	50	500	0.01
Density-FPFH	1	50	500	0.01

FPFH: fast point feature histogram.

Analysis of results

Feature histogram effect comparison

According to the proposed algorithm, the density-FPFH feature of each point in the point cloud should have 11 more parameters than the traditional FPFH, which represent the volume density feature. To verify its validity, a point of the rabbit model is selected to calculate its FPFH and density-FPFH features. The two results are illustrated in Figures 5 and 6, respectively.

Figure 5.

Traditional FPFH feature.

Figure 6.

Density-FPFH feature.

As shown in Figure 5, the traditional FPFH has 33 parameters, and mutations are present at the starting point. Most of the features are concentrated in the middle and rear portions, which are utilized as features for registration in the FPFH algorithm.

Compared with the 33-section eigenvalues of the traditional FPFH algorithm, density-FPFH has 11 new volume density features as shown in Figure 6, which significantly enhances the traditional FPFH content. It can be concluded that density-FPFH has more complete and important information than the traditional FPFH algorithm.

Registration effect comparison

Registration fit analysis

According to the number of features, it can be inferred whether the feature information of the optimization algorithm is rich. However, the performances of the two algorithms should be determined by testing. Based on the Point Cloud Library platform, coarse registration is performed for the sampled rabbit model using the density-FPFH and FPFH algorithms, respectively. The registration results are illustrated in Figure 7. It should be noted that the red model represents the source point cloud, and the black one is the registered point cloud.

Figure 7.

Coarse registration results: (a) traditional FPFH and (b) density-FPFH.

According to Figure 7, the traditional FPFH registration algorithm exhibits prominent deviations in the tail and ear contours of the rabbit. The point cloud obtained by density-FPFH is closer to the source point cloud.

On this basis, the coarse registration results of the point cloud are utilized to perform fine registration using the ICP algorithm, as shown in Figure 8.

Figure 8.

Fine registration results: (a) traditional FPFH + ICP and (b) density-FPFH + ICP.

According to Figure 8, no overlap is observed in the tail of the rabbit using the traditional algorithm. The cloud registered by density-FPFH coincides with the source point cloud, and the difference can barely be observed with the naked eye. Thus, the performance of the proposed algorithm is superior to that of the traditional algorithm.

To demonstrate the universality of the proposed algorithm, more detailed scenarios will be considered, such as fish, cattle, deer, microphones, workpieces, and vertebrae. Moreover, to ensure the accuracy of the comparison results, the same number of iterations and search radius are utilized for the two algorithms so that the algorithm type is the only variable, as shown in Figure 9.

Figure 9.

Comparison of coarse registration effects.

According to Figure 9, the results of the density-FPFH registration yield a higher recognition, and the point cloud obtained by density-FPFH is closer to the source point cloud. It can be concluded that the proposed algorithm can handle various scenarios and achieve a better registration result than the traditional algorithm.

Registration error analysis

According to the coarse registration results presented above, the density-FPFH algorithm can obtain a better pose, but the degree of optimization is unknown. To obtain the quantitative index of the optimization degree, standard deviation obtained according to Geomagic is used to research, which can be expressed as follows

σ = \sqrt{\frac{\sum_{i = 1}^{n} {D_{i}}^{2}}{n}}

(13)

where D represents the distance between the point of the registered point cloud and the source point cloud model, $σ$ represents the standard deviation of the registered point cloud and the source point cloud, and n represents the number of point cloud.

The relative error $e_{r}$ is defined as follows

e_{r} = (\frac{| σ_{F} - σ_{S} |}{σ_{S}}) \times 100 %

(14)

where $σ_{F}$ represents the standard deviation of the optimization algorithm and $σ_{S}$ represents the standard deviation of the traditional algorithm.

The standard deviation analysis results are shown in Table 2.

Table 2.

Standard deviation for coarse registration.

Number of iterations	Standard deviation of traditional FPFH	Standard deviation of density-FPFH	Relative error (%)
400	0.435	0.420	3.4
450	0.435	0.420	3.4
500	0.438	0.409	6.6

FPFH: fast point feature histogram.

According to Table 2, the standard deviation of the volume density optimization algorithm is always lower than that of the traditional algorithm. After 500 iterations, the standard deviation after the density-FPFH coarse registration is significantly smaller and the result is more accurate, which is consistent with the conclusions of the presented diagrams. More precisely, in the coarse registration stage, the FPFH algorithm based on volume density optimization yields a smaller registration standard deviation than the traditional FPFH algorithm and can reduce the standard deviation by 6.7%. It can be concluded that the coarse registration results are more accurate for the density-FPFH algorithm.

To analyze the effect on the final registration results, the same parameters are utilized for ICP registration. The point clouds that have been coarsely registered for 500 iterations with the density-FPFH and traditional FPFH algorithms are considered. The obtained standard deviation results are presented in Table 3.

Table 3.

Standard deviation for fine registration.

Standard deviation of traditional FPFH + ICP	Standard deviation of density-FPFH + ICP	Relative error
0.304	0.278	8.6%

FPFH: fast point feature histogram; ICP: iterative closest point.

Observing the final standard deviation results obtained by the proposed and traditional algorithms, it is found that the standard deviation obtained by the proposed algorithm is reduced by 8.6%, and its registration result is more accurate.

Registration density radius effect analysis

The density-FPFH algorithm proposed in this study is based on the volume density feature and utilized to optimize the traditional FPFH algorithm. The degree of optimization is closely related to the point cloud’s volume density. As the calculation of the volume density depends on the radius, to obtain better optimization results, the registration calculation is performed with different radii. It is noted that the other registration parameters are the same. The obtained test results are presented in Table 4.

Table 4.

Radius effect analysis results.

Density calculation radius (mm)	Standard deviation (mm)	Running time (ms)
0.7	0.450	3828
0.8	0.450	3791
0.9	0.428	3791
1.0	0.420	3763
1.05	0.423	3758

The analysis consists of two parts. First, the relationship between the radius and standard deviation is explored. According to Table 4, as the radius increases within a certain range, the standard deviation decreases. Moreover, the standard deviation increases sharply when the density calculation radius exceeds 1 mm. This is because when the radius is too large, the densities of all points in the point cloud are almost the same, and the volume density characteristic has a small effect on the algorithm. Thus, the precision is decreased. To maximize the effect of the volume density feature on the proposed algorithm, the registration test density should be 1 mm.

Second, the relationship between the running time of the algorithm and the radius of the density calculation is explored. According to Table 4, as the radius increases, the running time of the algorithm gradually decreases. The larger the radius, the easier it is to calculate the volume density characteristics. However, it is necessary for the registration to consider the dual factors of time and precision. Therefore, the final running time of the test is 3763 ms. At this time, the traditional FPFH algorithm running time is 3515 ms. Although the speed is slightly reduced, the final result of the registration is more sensitive to the standard deviation, and the accuracy is significantly improved.

Therefore, it can be concluded that when the point cloud’s volume density is utilized as a feature, the selection of the density calculation radius is highly important. If the radius is too large, then the error sharply increases and the feature becomes invalid. If it is too small, then the speed is reduced and the error is increased. The key of the density-FPFH algorithm is the selection of the radius of the volume density.

Discussion

According to the above experiments, the density-FPFH algorithm has a higher precision and speed. To study the stability of the proposed algorithm, a classical particle swarm optimization (PSO) algorithm is utilized to perform the registration experiment.

Taking the rabbit model as an example, the traditional FPFH, density-FPFH, and particle swarm algorithm are employed to register the point cloud. Because the particle swarm algorithm is considerably faster than the FPFH and density-FPFH algorithms, to ensure the algorithms are only compared in terms of a single variable, the number of iterations of the FPFH and density-FPFH algorithms is reduced so that the running times of all algorithms are the same. The experimental results are illustrated in Figure 10.

Figure 10.

Standard deviation comparison.

Based on Figure 10, it can be observed that the proposed algorithm is the most accurate and stable method, and the traditional algorithm achieves a moderate performance. The registration results obtained for PSO are highly unstable. The reason that the proposed method outperforms the traditional FPFH algorithm is because the volume density is introduced, which can maintain the same time complexity and preserve the missing information of the traditional algorithm. PSO has a wide range of related applications.^23,24 The reason for outperforming the PSO algorithm is mainly down to the inherent drawbacks of particle swarm algorithm, which involves randomness during operations. There are two main problems for PSO: (1) how to choose the appropriate registration parameters and (2) how to avoid becoming trapped in local optima. Thus, it can be concluded that stability is a major advantage of the density-FPFH algorithm.

Conclusion

According to the shortcomings of the current popular combined FPFH and ICP registration algorithm, an FPFH algorithm based on the volume density is proposed. The coarse registration results are obtained by volume density optimization and then incorporated into the ICP algorithm to perform fine registration. By combining the traditional FPFH algorithm and the point cloud volume density, the proposed method increases the number of features in the point cloud registration and enriches the feature histogram information to optimize the traditional FPFH algorithm. A point cloud library is then employed to perform a coarse registration test on the optimized and traditional FPFH algorithms and adjust the test registration parameters until the optimal coarse registration result is obtained. Finally, Geomagic is utilized to perform an error analysis on the registration test. The experimental results show that the density-FPFH algorithm proposed in this study can improve the coarse registration accuracy and obtain better initial point cloud poses under the constraints of time complexity when compared with the traditional FPFH algorithm. The ICP algorithm is incorporated to perform fine registration in the later stage, the overall standard deviation can be reduced by 8.6% within a short time, and the high-precision registration results can be obtained. Compared with the PSO²⁵ algorithm, the proposed algorithm achieves a high stability. In summary, the volume density feature of point cloud plays an important role in the registration and can be utilized to optimize the FPFH algorithm to achieve high-quality registration results.

Footnotes

Appendix 1 Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This work was supported by the National Natural Science Youth Fund (No.51705229).

ORCID iD

Yun Hu

References

Bueno

Bosché

González-Jorge

, et al. 4-plane congruent sets for automatic registration of as-is 3D point clouds with 3D BIM models. Automat Constr 2018; 89: 120–134.

Goebbels

Pohle-Fröhlich

Pricken

. Iterative closest point algorithm for accurate registration of coarsely registered point clouds with CityGML models. ISPRS Ann Photogramm Remote Sens Spatial Inf Sci 2019; IV-2/W5: 201–208.

Ahmad Fuad

Yusoff

Ismail

, et al. Comparing the performance of point cloud registration methods for landslide monitoring using mobile laser scanning data. Int Arch Photogramm 2018; XLII-4/W9: 11–21.

Besl

Kay

. A method for registration of 3-D shapes. IEEE T Pattern Anal 1992; 14(2): 239–256.

Zhao

Zhou

. Optimal registration algorithm for point cloud model of cultural relics. Appl Res Comp 2017; 34(12): 3885–3888.

Huo

G-y

Jiang

, et al. A novel coarse-to-fine registration for 3D point cloud based on feature points. In: 2018 3rd international conference on computational modeling, simulation and applied mathematics (CMSAM 2018), Wuhan, China, 27–28 September 2018, pp. 385–392.

Sheng

Chen

Liu

, et al. LiDAR point cloud registration based on Plücker line. Acta Geod Cartogr Sin 2016; 45(1): 58–64.

Rusu

Marton

Z-C

Blodow

, et al. Persistent point feature histograms for 3D point clouds. In: ICIAS proceedings of the 10th international conference on intelligent autonomous systems, Nice, 23–25 July 2008, pp. 119–128.

Rusu

Blodow

Beetz

. Fast point feature histograms (FPFH) for 3D registration. In: Proceedings of the IEEE international conference on robotics and automation, Kobe, Japan, 12–17 May 2009, pp. 3212–3217.

10.

Liu

. Improved method of point cloud registration based on FPFH feature. Comp Modern 2017(11): 46–50.

11.

Deng

. Point cloud target recognition algorithm based on viewpoint histogram feature optimization. J Henan Univ Scie Tech 2018; 39(5): 45–50.

12.

Shen

. Point cloud registration algorithm based on normal feature histogram. In: 2015 Forum on Optical Precision Engineering, Changchun, China, 10 July 2015, pp. 592–599.

13.

Peng

Dong

, et al. The registration algorithm of point cloud based on optimal extraction of FPFH feature. J New Ind 2014; 4(7): 75–81.

14.

Shao

Zhang

Zhu

, et al. Fast registration of terrestrial LIDAR point cloud and sequence images. In: Proceedings of the international archives of the photogrammetry, remote sensing and spatial information sciences—ISPRS archives, Wuhan, China, 18–22 September 2017, pp. 875–879.

15.

Ali Kashefi

Hamid Reza

Gholam Hossein

. Optimal sizing of a stand-alone wind/photovoltaic generation unit using particle swarm optimization. Simulation 2009; 85(2): 89–99.

16.

Baghaee

Mirsalim

Gharehpetian

, et al. Security/cost-based optimal allocation of multi-type FACTS devices using multi-objective particle swarm optimization. Simulation 2012; 88(8): 999–1010.

17.

Yan

. Research on plane segmentation algorithm based on PCA algorithm from airborne LiDAR point cloud data. Urban Geotech Invest Surv 2018(1): 41–451.

18.

Xiong

. Research on 3D point cloud registration technology. Taiyuan, China: North University of China, 2018.

19.

Sun

Xie

Liu

, et al. Automatic 3D point cloud registration based on hierarchical block global search. Optics Precision Eng 2013; 21(1): 174–180.

20.

. Point cloud-based non-cooperative target extraction and pose solution. Harbin, China: Harbin Institute of Technology, 2017.

21.

Chen

Zhu

, et al. The point cloud registration technology based on SAC-IA and improved ICP. J Xi'an Polytech Univ 2017; 31(3): 395–401.

22.

Qian

Zheng

. A new automatic registration method of scanning point cloud. J Water Resour Archit Eng 2013(3): 162–164.

23.

Baghaee

Mirsalim

Gharehpetian

, et al. MOPSO/FDMT-based Pareto-optimal solution for coordination of overcurrent relays in interconnected networks and multi-DER microgrids. IET Gener Transm Dis 2018; 12(12): 2871–2886.

24.

Baghaee

Mirsalim

Gharehpetian

. Multi-objective optimal power management and sizing of a reliable wind/PV microgrid with hydrogen energy storage using MOPSO. J Intell Fuzzy Syst 2017; 32(3): 1753–1773.

25.

Zhang

. Satellite cloud image registration by combining curvature shape representation with particle swarm optimization. J Softw 2011; 6(3): 483–489.

Iterative closest point registration for fast point feature histogram features of a volume density optimization algorithm

Abstract

Keywords

Introduction

Motivation

Literature review

Contributions and organization

FPFH algorithm based on volume density optimization

Algorithm overview

Calculation of three deflections

Volume density calculation

Algorithm registration

Volume density–optimized FPFH registration test

Registration scheme design

Registration parameter design

Analysis of results

Feature histogram effect comparison

Registration effect comparison

Registration fit analysis

Registration error analysis

Registration density radius effect analysis

Discussion

Conclusion

Footnotes

Appendix 1

Declaration of conflicting interests

Funding

ORCID iD

References