CN115409969A - Long-distance-measurement ground laser point cloud plane segmentation algorithm - Google Patents

Abstract

The invention discloses an algorithm for plane segmentation of long-range ground laser point clouds, which specifically includes the following steps: T1, determining the best neighborhood based on the dynamic search range, T2, designing a region growth algorithm based on dimensional features and the best neighborhood , The present invention relates to the technical field of laser point cloud data processing and application. The long-range ground laser point cloud plane segmentation algorithm is density-adaptive, and the neighborhood search range is automatically generated based on the theoretical point spacing, which can meet the needs of point cloud search for neighbors at different scanning distances; the construction of the best neighborhood is guaranteed The calculation of the local features of the point cloud is not affected by the density change; the estimation of the sampling interval is in line with the acquisition principle of the ground laser scanner, which enhances the rationality of the theoretical point spacing; the best neighborhood is added to the region growth, so that the plane segmentation algorithm is suitable for high Density change point cloud has wide applicability of dynamic search range, and the determination of neighborhood search range starts from a single point without analyzing the overall density change of point cloud.

Description

A Plane Segmentation Algorithm of Long Range Ground Laser Point Cloud

technical field

The invention relates to the technical field of laser point cloud data processing and application, in particular to a long-range ground laser point cloud plane segmentation algorithm.

Background technique

Laser scanning technology is one of the main ways of building information collection. Since the point clouds collected by laser scanners are scattered and disordered, how to effectively extract building information from them has very important research significance for the construction of smart cities.

According to different carriers, laser scanning technology can be divided into airborne laser scanning technology, vehicle laser scanning technology and ground laser scanning technology. According to the data collection method, airborne laser scanning technology can collect building top surface information from the air, lacking facade information, and ground laser scanning technology can collect rich building facade information, which is an important data source for refined 3D reconstruction.

Plane segmentation is an important means to extract building facades, including region growing, model fitting and feature clustering, etc. The region growing method is a process in which the seed point grows according to certain rules in its neighborhood. First, the seed point is selected according to the minimum curvature [Besl, 1988] and the highest surface saliency intensity [Wu Hao, 2019], and then according to the growth The rule finds growing points in its neighborhood, normal vectors, Euclidean distance [CL Kang, 2020], point-to-plane distance [Lu Weixin, 2015], plane fitting residuals [XNing, 2009] and other features are widely used in growth rules , and at the same time use the growth points that have not been grown as new seed points until all points are traversed; model fitting is to achieve segmentation by fitting the original point cloud with a specific model, and the model is composed of geometric primitives [S Xia, 2020]. Among them, the algorithm with better effect is Hough transform [D Borrmann, 2011], random sampling consistency [LLi, 2017] and its derivative algorithm [B Zhao, 2020]; the feature clustering method is divided into two steps: boundary extraction and clustering. The boundary can be effectively detected according to the local characteristics of the point. For example, the angle between the normal vector of the boundary point and the adjacent point is large, while the angle between the normal vector of the point on the same plane is small [E Che,2017], centered on the boundary point Neighborhood, the angle between the start and end directions of the enclosing path is less than 360° [C Mineo, 2019]. Clustering algorithms include k-means algorithm, k-nearest neighbor algorithm, and density-based algorithm (DBSCAN), etc. [Jin Jianguo, 2014].

The existing building plane segmentation methods have the following deficiencies:

1. Less consideration is given to the impact of high-density changes on segmentation. With the continuous optimization of scanner hardware, the measurement range of terrestrial laser scanning has been increased, which has also brought about the problem of high-density changes. For example, the angle between scanning lines is 0.06°, the maximum scanning distance is 1km, and the point spacing can be realized from millimeters to meters The leaping of levels leads to high-density changes in the scene, which brings about the problem that the size of the neighborhood is difficult to unify. Region growing and feature clustering are very sensitive to neighborhood selection, and neighborhood size selection affects the quality of plane segmentation.

2. It is difficult to balance efficiency and precision. The model fitting method has higher robustness, but has higher requirements on the quality of the original point cloud. Due to the occlusion of ground objects, the ground laser point cloud has certain defects in integrity, and as the scanning distance increases, the collected points are relatively sparse. Therefore, the use of this algorithm on the long-range ground-based point cloud requires optimization of the point cloud. affect the efficiency of the algorithm. The region growing algorithm is simple in principle and high in efficiency. It is widely used in point cloud segmentation of large scenes. The selection of seed points and growth rules affect the efficiency and quality of segmentation. A reasonable method of seed point selection can greatly reduce the time-consuming algorithm. The quality of the segmentation plane is determined by Growth rules determine. In addition, feature fitting requires the point cloud to have a uniform density. If the density is uneven or too low, the boundary will be missing, which will affect the quality and stability of the segmentation.

Contents of the invention

(1) Solved technical problems

Aiming at the deficiencies of the existing technology, the present invention provides a plane segmentation algorithm of long-range ground laser point cloud, which solves the problem that the long-range ground-based point cloud scan distance is long, and the point cloud density changes greatly with the increase of the scan distance. Problem, existing planar segmentation methods are rarely designed for this type of situation, based on this, the present invention designs a density adaptive segmentation method to solve the following problems:

1) Design a dynamic search range to find the best neighborhood to solve the problem of neighborhood size selection caused by density changes. The high-density change characteristics of long-range ground-based point clouds make point clouds in different density areas have different neighborhood sizes, which affects plane segmentation. Finding the best neighborhood of each point by setting the search range is an effective way to solve such problems. At the same time, the search range is determined by the theoretical point spacing, and the search range is constructed based on a single point, so that the algorithm is suitable for ground laser point clouds with different longest scanning distances.

2) Improve the region growth algorithm to balance accuracy and efficiency. Model fitting and feature clustering have certain requirements on the quality of the original point cloud. The quality of the ground laser point cloud is difficult to meet the requirements, and the design of optimization measures is difficult. However, the principle of regional growth is simple and can be improved according to different requirements, with high efficiency. Improve the segmentation quality, use principal component analysis to calculate dimensional features to solve the situation of boundary point misclassification, and design growth rules based on the best neighborhood to improve the accuracy of local feature calculation and make the plane segmentation results more reasonable.

(2) Technical solution

In order to achieve the above object, the present invention is realized through the following technical solutions: a plane segmentation algorithm of long-range ground laser point cloud, which specifically includes the following steps:

T1. Determine the best neighborhood based on the dynamic search range. The specific determination method includes the following steps:

e1. Ground filtering: use the cloth filtering algorithm to separate non-ground points from ground points, and eliminate non-ground point clouds;

e2. Sampling interval estimation: According to the acquisition principle, randomly select N points in the non-ground point cloud, and use the k nearest neighbor algorithm to find k nearest neighbor points respectively. The formula is:

S(p _m )={p _mn ,n=1,2,…,k}, m=1,2,…,N

In the formula, p _m is a random point, p _mn is the neighbor point of p _m , and S(p _m ) is the neighbor point set.

In the scanner coordinate system, according to the three-dimensional coordinates of p _m and p _mn , calculate its horizontal angle Δα _mn and vertical angle Δβ _mn , Δα _mn , Δβ _mn ∈ [0°,180°], if Δα _mn ≥ 180 °, use 360° -Δα _mn to represent the horizontal angle

p_m点的理论点间距

为

e3. Establishment of dynamic search range: The point spacing of the point cloud collected by the ground laser scanner is related to the scanning distance and sampling interval. The point spacing directly affects the point cloud density. Using this feature, on the basis of the sampling interval, calculate the theoretical Point spacing, combined with scan distance

Theoretical point spacing of p _m points

for

确定为：

According to the existing experiments, select the neighborhood in the point spacing of 1-10 times to make the local features the most obvious. Based on this, the dynamic search range of p _m points

identified as:

中选取

作为聚类半径，使用KNN法对点云进行聚类，并使用内外指标对聚类结果进行评价，选取最佳聚类结果，内指标基于聚类后各类的空间关系对结果进行评价，考虑到点云海量性对算法效率的影响，在内部指标中选取DB指数，在外指标中选取Rand指数验证DB指数的合理性；e4. Optimal Neighborhood Search for Joint Cluster Analysis Inner and Outer Indicators and Shannon Entropy: In

select from

As the clustering radius, use the KNN method to cluster the point cloud, and use the internal and external indicators to evaluate the clustering results, select the best clustering results, and use the internal indicators to evaluate the results based on the spatial relationship of various types after clustering. Consider Considering the impact of point cloud mass on algorithm efficiency, select DB index as internal index and Rand index as external index to verify the rationality of DB index;

If the point cloud is divided into m categories M={M1,M2,...,Mm} after clustering, and manually classified into n categories N={N1,N2,...,Nn}, the calculation of DB index and Rand index is as follows:

Among them, avg(M _i ), avg(M _j ) represent the average point spacing of Mi _and M _j , dcen(M _i , M _j ) is the centroid distance between _Mi and M _j , and n _ij is the distance between _Mi and N _j The number of common points, nj and ni. are the points of M _i and N _j respectively, and N is the total number of point clouds; the smaller the DB index, the larger the Rand index, the better the clustering result.

为左右跨度提取动态搜索范围中的有效子集；At this time, the integer int corresponding to the neighborhood radius corresponding to the best clustering result is

Extract valid subsets in the dynamic search range for left and right spans;

Shannon entropy represents the amount of information in the neighborhood of a certain point. The smaller the value, the more obvious the local features. The calculation of Shannon entropy is as follows:

的间隔取值作为邻域半径，通过PCA计算邻域拟合平面的协方差矩阵，将矩阵的特征值开方得到三轴方向的拟合残差δ₁，δ₂，δ₃，根据香农熵的计算公式计算香农熵，选取Ef最小时的邻域半径

即确定出最佳邻域为：Among them, Ef is the Shannon entropy, δ ₁ , δ ₂ , and δ ₃ are the plane fitting residuals of the point neighborhood, which are calculated by principal component analysis, and δ ₁ ≥ δ ₂ ≥ _{δ 3} . In a valid subset of the dynamic search range, starting with

The value of the interval is taken as the neighborhood radius, and the covariance matrix of the neighborhood fitting plane is calculated by PCA, and the square root of the eigenvalues of the matrix is obtained to obtain the fitting residuals δ ₁ , δ ₂ , δ ₃ in the three-axis direction, according to the Shannon entropy The calculation formula of Shannon entropy is calculated, and the neighborhood radius when Ef is the smallest is selected

That is, the best neighborhood is determined as:

At this time, the local characteristics of the point are the most obvious, and the dimension feature Dim of the point is analyzed according to the fitting residual

Among them, Dim∈[0, 2] corresponds to linear points, planar points and discrete points respectively, and λ ₁ ≥λ ₂ ≥λ ₃ .

T2. Design of region growth algorithm based on dimensional features and optimal neighborhood. The specific determination method includes the following steps:

p1. Building extraction: The clustering results include not only buildings, but also disturbances such as street lights and trees. Since most of the points of buildings are plane points, street lights, trees and other disturbances have more discrete points and linear points. , based on this, the building class is selected according to the proportion of plane points in each class. Different classes have different colors in the figure, and gray is the rendering result;

p2. Seed point selection and growth rule setting: in the building, select the seed point according to the best neighborhood, dimension features, normal vector and point-to-plane distance;

p3. Over-segmentation plane merging: Due to the transmittance of the laser, the window appears as a hole in the point cloud, and the discontinuity in space makes the initial plane obtained by segmentation appear over-segmented.

Preferably, the sampling interval in e2 is the horizontal or vertical angle between adjacent scanning lines of the scanner, and the corresponding radian is the angular resolution.

Preferably, in the step e2, according to the acquisition principle, in the spherical neighborhood S( _pm ) determined by KNN, the adjacent points on the adjacent scanning line of p _m are the most, and at the same time, the distribution of horizontal angles is counted in several intervals, Create a histogram with interval width Δ. Select the interval with the most points in the histogram, and calculate the average value α _avg of the horizontal angles in the interval.

Preferably, the rationality of the parameter Δ setting affects the estimation quality of the sampling interval, so that Δ takes values at intervals of 0.001° in the range of [0.005°, 0.015°], calculates α _avg respectively, and finally takes the middle of all α _avg The value med(α _avg ) is the final sampling interval.

Preferably, in the step e4, the internal index is based on the spatial relationship of various types after clustering, which is Dunn index index, silhouette coefficient and Davidson-Fort index, and the external index uses the manual classification result as reference data, and compares it with the clustering result, To analyze the validity of clustering results, it is divided into standard mutual information index, F-Measure index, Rand index and Jacarrd coefficient.

Preferably, the specific setting method of the growth rule in the step p2 is as follows;

U1. Select the seed point: in the construction class, the plane point is used as the initial seed point, and all the growth points are used as the new seed point during the growth process, and only one growth operation is performed for any point;

U2. Set the growth rules: first, the growth point must be a plane point as a prerequisite, and then the growth point must meet the distance requirements, normal vector requirements and point-to-plane distance requirements:

是种子点最佳邻域半径，φ是生长点与种子点的法向量夹角，φ_th是法向量夹角阈值，d’是点面距的较大值，d’_th是点面距阈值。Among them, D is the Euclidean distance between the growth point and the seed point,

is the optimal neighborhood radius of the seed point, φ is the normal vector angle between the growth point and the seed point, φ _th is the normal vector angle threshold, d' is the larger value of the point-to-plane distance, d' _th is the point-to-plane distance threshold .

U3. Allocation of linear points: linear points are also part of the plane. After all the plane points are grown, the linear points are allocated to the nearest adjacent plane to obtain the initial segmentation result.

Preferably, the over-segmentation problem in the step p3 is to optimize the initial result by plane merging, and the plane merging needs to meet the following requirements:

(1) Plane normal vector angle requirements: Calculate the normal vector angle between two planes, and the angle must be smaller than the threshold φ _th ;

(2) Point-to-plane distance requirements: For two planes P ₁ and P ₂ , the geometric centers C ₁ and C ₂ are obtained respectively, and the point-to-plane distance is calculated as follows:

为两平面的法向量，点面距需小于阈值d′_th；where D _c is the space distance between C ₁ and C ₂ ,

is the normal vector of the two planes, and the point-to-plane distance must be smaller than the threshold d′ _th ;

(3) Plane distance requirement: over-segmentation is caused by missing windows, and the maximum height of windows in the scene is used as the distance threshold.

Preferably, firstly, a balanced binary tree is established with a point in P ₁ as the center, and a search range is constructed with a distance threshold, and then the points in P ₂ within this range are queried, and the existence of a point satisfies the plane distance requirement.

(3) Beneficial effects

The invention provides an algorithm for plane segmentation of long-range ground laser point clouds. Compared with the prior art, it has the following beneficial effects:

(1) The long-range ground laser point cloud plane segmentation algorithm is density-adaptive, and the neighborhood search range is automatically generated based on the theoretical point spacing (this scheme uses 1-10 times the theoretical point spacing as the dynamic search of the neighborhood range), which can meet the needs of point cloud search for neighbors at different scanning distances; the construction of the best neighborhood ensures that the calculation of local features of point clouds is not affected by density changes; the estimation of sampling interval conforms to the acquisition principle of ground laser scanners, and enhances The rationality of the theoretical point spacing is confirmed; the best neighbor is added to the region growth, so that the plane segmentation algorithm is suitable for high-density changing point clouds.

(2) The plane segmentation algorithm of the long-range ground laser point cloud has wide applicability of the dynamic search range. The determination of the neighborhood search range starts from a single point without analyzing the overall density change of the point cloud, which avoids the need for different distance measurements. The repeated setting of the search range of the ground-based point cloud has stronger applicability.

(3) The long-range ground laser point cloud plane segmentation algorithm, through the use of internal and external indicators of cluster analysis, through the reasonable analysis of cluster results, eliminates the dynamic search on the basis of ensuring the best neighborhood extraction quality Scope invalid subset avoids the calculation of Shannon entropy on the invalid subset and reduces the search time of the best neighbor.

(4) The plane segmentation algorithm of the long-range ground laser point cloud has both efficiency and accuracy, and the boundary points are extracted through dimensional features, which solves the problem of inaccurate estimation of the boundary normal vector; on the basis of the clustering results, through various The overall dimensional characteristics of the class, extract the building class, and only divide the building class into a plane, which significantly reduces the amount of data and improves the processing efficiency; select the plane point as the seed point and the growth point, effectively eliminate the discrete points, and finally assign the boundary points The closest plane improves the accuracy of the segmentation results at the boundary; the mesh merging condition is designed based on the window size, which effectively solves the over-segmentation problem caused by the lack of window information, making the plane segmentation results more reasonable.

Description of drawings

FIG. 1 is a flowchart of plane segmentation based on a dynamic search range according to an embodiment of the present invention;

Fig. 2 is a schematic diagram of the calculation of the horizontal angle and the vertical angle between a random point and a neighboring point according to an embodiment of the present invention;

Fig. 3 is a schematic diagram of building a horizontal angle histogram according to an embodiment of the present invention;

FIG. 4 is a schematic diagram of determining the best neighborhood according to an embodiment of the present invention;

5 is a schematic diagram of building extraction according to an embodiment of the present invention;

Fig. 6 is a schematic diagram of the regional growth effect of the embodiment of the present invention;

Fig. 7 is a schematic diagram of merging dough pieces according to an embodiment of the present invention.

Detailed ways

The following will clearly and completely describe the technical solutions in the embodiments of the present invention with reference to the accompanying drawings in the embodiments of the present invention. Obviously, the described embodiments are only some of the embodiments of the present invention, not all of them. Based on the embodiments of the present invention, all other embodiments obtained by persons of ordinary skill in the art without making creative efforts belong to the protection scope of the present invention.

Please refer to Figures 1-7, an embodiment of the present invention provides a technical solution: a plane segmentation algorithm for long-range ground laser point clouds, which specifically includes the following steps:

T1. Determine the best neighborhood based on the dynamic search range. The specific determination method includes the following steps:

e1. Ground filtering: Use the cloth filtering algorithm to separate non-ground points from ground points, and eliminate non-ground point clouds.

e2. Sampling interval estimation: The sampling interval is the horizontal or vertical angle between adjacent scanning lines of the scanner, and the corresponding radian is the angular resolution. According to the acquisition principle, N points are randomly selected in the non-ground point cloud, Use the k-nearest neighbor algorithm to find k neighbor points respectively, the formula is:

S(p _m )={p _mn ,n=1,2,…,k}, m=1,2,…,N

In the formula, p _m is a random point, p _mn is the neighbor point of p _m , and S(p _m ) is the neighbor point set.

In the scanner coordinate system, according to the three-dimensional coordinates of p _m and p _mn , calculate its horizontal angle Δα _mn and vertical angle Δβ _mn , Δα _mn , Δβ _mn ∈ [0°,180°], if Δα _mn ≥ 180 °, use 360° -Δα _mn to represent the horizontal angle

According to the collection principle, in the spherical neighborhood S(p _m ) determined by KNN, the adjacent points on the adjacent scan line of p _m are the most, as shown in Figure 2. At the same time, the distribution of horizontal angles is counted in several intervals, and a histogram is established. The interval width is Δ. Select the interval with the most points in the histogram, and calculate the average value α _avg of the horizontal angles in the interval.

The rationality of the parameter Δ setting affects the estimation quality of the sampling interval, so that Δ takes values at intervals of 0.001° in the range of [0.005°, 0.015°], calculates α _avg respectively, and finally takes the median value of all α _avg med( α _avg ) is the final sampling interval.

p_m点的理论点间距

为

e3. Establishment of dynamic search range: The point spacing of the point cloud collected by the ground laser scanner is related to the scanning distance and sampling interval. The point spacing directly affects the point cloud density. Using this feature, on the basis of the sampling interval, calculate the theoretical Point spacing, combined with scan distance

Theoretical point spacing of p _m points

for

可确定为：

According to the existing experiments, select the neighborhood in the point spacing of 1-10 times to make the local features the most obvious. Based on this, the dynamic search range of p _m points

Can be determined as:

中选取

作为聚类半径，使用KNN法对点云进行聚类，并使用内外指标对聚类结果进行评价，选取最佳聚类结果。e4. Optimal Neighborhood Search for Joint Cluster Analysis Inner and Outer Indicators and Shannon Entropy: In

select from

As the clustering radius, the KNN method is used to cluster the point cloud, and the internal and external indicators are used to evaluate the clustering results, and the best clustering results are selected.

The internal index evaluates the results based on the spatial relationship of various types after clustering. There are mainly the following types: Dunn index, Silhouette coefficient (Silhouette coefficient) and Davidson's Boding index (DB Index), etc. The external index will be The manual classification results are used as reference data, compared with the clustering results, and the effectiveness of the clustering results is analyzed, which are divided into standard mutual information index (NMI), F-Measure index, Rand index and Jacarrd coefficient, etc., considering the mass of point clouds For the impact on the efficiency of the algorithm, the DB index is selected as the internal index, and the Rand index is selected as the external index to verify the rationality of the DB index.

If the point cloud is divided into m categories M={M1,M2,...,Mm} after clustering, and manually classified into n categories N={N1,N2,...,Nn}, the calculation of DB index and Rand index is as follows:

Among them, avg(M _i ), avg(M _j ) represent the average point spacing of Mi and _{M j ,} dcen(M _i , M _j ) is the centroid distance between _Mi and M _j , and n _ij is the distance between _Mi and N _j The number of common points, nj and ni. are the points of M _i and N _j respectively, and N is the total number of point clouds. The smaller the DB index, the larger the Rand index, the better the clustering result. Figure 4 is the optimal neighborhood determination diagram, in which Figure 4(a) is the internal and external indicators, and Figure 4(b) is the Shannon entropy.

为左右跨度提取动态搜索范围中的有效子集，如图4(a)；At this time, the integer int corresponding to the neighborhood radius corresponding to the best clustering result is

Extract valid subsets in the dynamic search range for the left and right spans, as shown in Figure 4(a);

Shannon entropy represents the amount of information in the neighborhood of a certain point. The smaller the value, the more obvious the local features. The calculation of Shannon entropy is as follows:

的间隔取值作为邻域半径，通过PCA计算邻域拟合平面的协方差矩阵，将矩阵的特征值开方得到三轴方向的拟合残差δ₁，δ₂，δ₃，根据式(6)计算香农熵，如图4(b)，选取Ef最小时的邻域半径

即确定出最佳邻域。Among them, Ef is the Shannon entropy, δ ₁ , δ ₂ , and δ ₃ are the plane fitting residuals of the point neighborhood, which can be calculated by principal component analysis (PCA) [5], and δ ₁ ≥ _{δ 2} ≥ δ ₃ . In a valid subset of the dynamic search range, starting with

The value of the interval is taken as the neighborhood radius, and the covariance matrix of the neighborhood fitting plane is calculated by PCA, and the square root of the eigenvalues of the matrix is obtained to obtain the fitting residuals δ ₁ , δ ₂ , δ ₃ in the three-axis direction, according to the formula ( 6) Calculate the Shannon entropy, as shown in Figure 4(b), select the neighborhood radius when Ef is the smallest

That is, the best neighborhood is determined.

At this time, the local characteristics of the point are the most obvious, and the dimension feature Dim of the point can be analyzed according to the fitting residual

Among them, Dim∈[0, 2] corresponds to linear points, planar points and discrete points respectively, and λ ₁ ≥λ ₂ ≥λ ₃ .

T2, Design of Region Growth Algorithm Based on Dimensional Features and Optimal Neighborhood

p1. Building extraction: The clustering results include not only buildings, but also disturbances such as street lights and trees. Since most of the points of buildings are plane points, street lights, trees and other disturbances have more discrete points and linear points. , based on this, the building class is selected according to the proportion of plane points in each class, as shown in Figure 5, different classes have different colors in the figure, and gray is the rendering result;

p2. Seed point selection and growth rule setting: In the building, select the seed point according to the best neighborhood, dimension features, normal vector and point-to-plane distance, and set the growth rule, the specific method is as follows;

1) Select the seed point. In the building class, the plane point is used as the initial seed point, and all the growth points are used as the new seed point during the growth process, and any point only performs one growth operation.

2) Set the growth rules. First, the growth point must be a plane point as a prerequisite, and then the growth point must meet the distance requirements, normal vector requirements and point-to-plane distance requirements:

是种子点最佳邻域半径，φ是生长点与种子点的法向量夹角，φ_th是法向量夹角阈值，d’是点面距的较大值，d’_th是点面距阈值。Among them, D is the Euclidean distance between the growth point and the seed point,

is the optimal neighborhood radius of the seed point, φ is the normal vector angle between the growth point and the seed point, φ _th is the normal vector angle threshold, d' is the larger value of the point-to-plane distance, d' _th is the point-to-plane distance threshold .

3) Assign linear points. The linear points are also part of the plane. After all the plane points are grown, the linear points are assigned to the nearest adjacent plane to obtain the initial segmentation results, as shown in Figure 6(b)

p3. Over-segmented plane merging: Due to the transmittance of the laser, the window appears as a hole in the point cloud, and the discontinuity in space makes the initial plane obtained by segmentation appear over-segmented, as shown in Figure 7(a). For the over-segmentation problem, the initial results are optimized by plane merging. The plane merging needs to meet the following requirements:

(1) Requirements for the included angle of the plane normal vector. Calculate the angle between the normal vectors of the two planes, and the angle must be smaller than the threshold φ _th .

(2) Point-to-plane distance requirements. For two planes P ₁ , P ₂ , the geometric centers C ₁ , C ₂ are obtained respectively, and the point-to-plane distance is calculated as follows:

为两平面的法向量，点面距需小于阈值d′_th。where D _c is the space distance between C ₁ and C ₂ ,

is the normal vector of the two planes, and the point-to-plane distance must be smaller than the threshold d′ _th .

(3) Plane distance requirements. Over-segmentation is caused by missing windows, and the maximum height of windows in the scene can be used as the distance threshold. First, build a balanced binary tree centered on a point in _P1 , and build a search range with a distance threshold. Then, query the points within this range of _P2 , and the existence of the points meets the plane distance requirement. Figure 7 is a patch merging diagram, in which Figure 7(a) is the initial segmentation result, Figure 7(b) is the distance threshold of 1.8m; Figure 7(c) is the distance threshold of 0.5m, and Figure 7(b) represents the distance threshold setting When the mesh size is 1.8m, the merge effect can effectively solve the over-segmentation situation. Figure 7(c) represents the patch merging effect when the distance threshold is 0.5m, and there is still over-segmentation.

At the same time, the content not described in detail in this specification belongs to the prior art known to those skilled in the art.

It should be noted that in this article, relational terms such as first and second are only used to distinguish one entity or operation from another entity or operation, and do not necessarily require or imply that there is a relationship between these entities or operations. any such actual relationship or order exists between them. Furthermore, the term "comprises", "comprises" or any other variation thereof is intended to cover a non-exclusive inclusion such that a process, method, article, or apparatus comprising a set of elements includes not only those elements, but also includes elements not expressly listed. other elements of or also include elements inherent in such a process, method, article, or apparatus.

Although the embodiments of the present invention have been shown and described, those skilled in the art can understand that various changes, modifications and substitutions can be made to these embodiments without departing from the principle and spirit of the present invention. and modifications, the scope of the invention is defined by the appended claims and their equivalents.

Claims (8)

1. A long-distance ground laser point cloud plane segmentation algorithm is characterized in that: the method specifically comprises the following steps:

t1, determining the optimal neighborhood based on the dynamic search range, wherein the specific determination method comprises the following steps:

e1, ground filtering: separating non-ground points and ground points by using a cloth filtering algorithm, and rejecting non-ground point clouds;

e2, sampling interval estimation: according to the collection principle, N points are randomly selected from non-ground point cloud, k nearest neighbor points are searched by using a k nearest neighbor algorithm respectively, and the formula is as follows:

S(p _m )＝{p _mn ，n＝1，2，...，k}，m＝1,2,…,N

in the formula, p _m As random points, p _mn Is p _m Of (2), S (p) _m ) Is a neighbor point set.

In the scanner coordinate system, according to p _m And p _mn Calculating the horizontal included angle delta alpha of the three-dimensional coordinate _mn And angle of vertical separation Δ β _mn ，Δα _mn ，Δβ _mn ∈[0°,180°]If Δ α _mn Not less than 180 deg., 360-delta alpha _mn Indicating horizontal included angle

e3, establishing a dynamic search range: the point distance of the point cloud collected by the ground laser scanner is related to the scanning distance and the sampling interval, the point distance directly influences the point cloud density, the theoretical point distance is calculated on the basis of the sampling interval by utilizing the characteristic, and the scanning distance is combined

p _m Theoretical dot spacing of dots

Is composed of

According to the existing experiment, neighborhood is selected from 1-10 times of point spacing to make local features most obvious, based on which, p _m Dynamic search range of points

The determination is as follows:

e4, performing joint clustering analysis on the internal and external indexes and the best neighborhood search of the Shannon entropy: in that

In selection

As a clustering radius, clustering point clouds by using a KNN method, evaluating a clustering result by using internal and external indexes, selecting an optimal clustering result, evaluating the result by using the internal index based on various spatial relations after clustering, selecting a DB index from the internal index in consideration of the influence of the point cloud massiveness on algorithm efficiency, and selecting a Rand index from the external index to verify the rationality of the DB index;

if the point cloud is classified into M types M = { M1, M2, \8230;, mm } after clustering, the point cloud is manually classified into N types N = { N1, N2, \8230;, nn }, and the DB index and the Rand index are calculated as follows:

wherein, avg (M) _i )，avg(M _j ) Represents M _i ，M _j The average dot pitch of (a) is,dcen(M _i ,M _j ) Is M _i And M _j Distance of center of mass, n _ij Is M _i And N _j The number of common points, n.j, ni, is M _i ，N _j N is the total number of point clouds;

at this time, the integer int corresponding to the neighborhood radius corresponding to the best clustering result is used to calculate the best clustering result

Extracting a valid subset in the dynamic search range for the left and right spans;

the shannon entropy expresses the information quantity of a certain point neighborhood, the smaller the value is, the more obvious the local characteristic is, and the shannon entropy is calculated as follows:

wherein Ef is Shannon entropy, delta ₁ ，δ ₂ ，δ ₃ Is the plane fitting residual error of the point neighborhood, is calculated by a principal component analysis method, and delta ₁ ≥δ ₂ ≥δ ₃ . In a valid subset of the dynamic search range to

The interval value of (2) is used as the neighborhood radius, the covariance matrix of the neighborhood fitting plane is calculated through PCA, and the characteristic value of the matrix is squared to obtain the fitting residual error delta in the three-axis direction ₁ ，δ ₂ ，δ ₃ Calculating the Shannon entropy according to the calculation formula of the Shannon entropy, and selecting the neighborhood radius when the Ef is minimum

Namely, the optimal neighborhood is determined as:

at the moment, the local feature of the point is most obvious, and the dimensional feature Dim of the point is analyzed according to the fitting residual error

Wherein Dim ∈ [0,2 ]]Corresponding to a linear point, a planar point and a discrete point, respectively, and λ ₁ ≥λ ₂ ≥λ ₃ 。

T2, designing a region growing algorithm based on dimensional features and an optimal neighborhood, wherein the specific determination method comprises the following steps:

p1, building extraction, namely selecting a building class according to the proportion of plane points in each class;

p2, seed point selection and growth rule setting: in a building, selecting seed points according to an optimal neighborhood, dimensional characteristics, a normal vector and a point-to-surface distance;

p3, over-segmentation plane merging: due to the transmission of the laser, the window appears as a hollow in the point cloud, and the discontinuity in space causes the initial plane obtained by the segmentation to be over-segmented.

2. The long-range ground laser point cloud plane segmentation algorithm of claim 1, wherein: and the sampling interval in the e2 is a horizontal included angle or a vertical included angle between adjacent scanning lines of the scanner, and the corresponding radian is the angular resolution.

3. The long-range ground laser point cloud plane segmentation algorithm of claim 1, wherein: in the step e2, according to the collecting principle, a spherical neighborhood S (p) determined by KNN _m ) In, p _m The number of the adjacent points on the adjacent scanning lines is the most, and the distribution condition of the horizontal included angle is counted by a plurality of intervals to establish a histogram, wherein the interval width is delta. Selecting the interval with the most points in the histogram, and calculating the average value alpha of the horizontal included angles in the interval _avg 。

4. The long-range ground laser point cloud plane segmentation algorithm of claim 3, wherein: rationality shadow of parameter Δ settingsResponsive to the estimated mass of the sampling interval, Δ is set at [0.005 °,0.015 °]Are taken at intervals of 0.001 DEG in the range of (A), alpha is respectively calculated _avg Finally take all alpha _avg Middle value of (a) _avg ) Is the final sampling interval.

5. The long-range ground laser point cloud plane segmentation algorithm of claim 1, wherein: and e4, enabling the internal indexes to be dunen index indexes, contour coefficients and davisenburg indexes based on the spatial relations of the clustered indexes, enabling the external indexes to take the manual classification results as reference data, comparing the reference data with the clustering results, analyzing the effectiveness of the clustering results, and dividing the clustering results into standard mutual information indexes, F-Measure indexes, rand indexes and Jacard coefficients.

6. The long-range ground laser point cloud plane segmentation algorithm of claim 1, wherein: the specific setting method of the growth rule in the step p2 is as follows;

u1, selecting seed points: taking a plane point as an initial seed point in a building class, taking all growing points as new seed points in the growing process, and performing growing operation once at any point;

u2, setting a growth rule: firstly, taking a growing point as a plane point as a precondition, and then meeting the distance requirement, normal vector requirement and point-to-plane distance requirement of the growing point:

wherein D is the Euclidean distance between the growing point and the seed point,

is the optimum neighborhood radius of the seed point, phi is the normal vector angle between the growing point and the seed point, phi _th Is a normal vector angle threshold, d 'is a larger value of the point-to-surface distance, d' _th Is the point-to-area distance threshold.

U3, assigning line points: the linear points are also part of the plane, and after all the plane points are grown, the linear points are distributed to the nearest plane to obtain an initial segmentation result.

7. The long-range ground laser point cloud plane segmentation algorithm of claim 1, wherein: the over-segmentation problem in step p3 is to optimize an initial result by plane merging, where the plane merging needs to meet the following requirements:

(1) The requirements of the included angle of the normal vectors of the planes are as follows: calculating the normal vector included angle of the two planes, wherein the included angle needs to be less than a threshold value phi _th ；

(2) The requirement of point-surface distance: for two planes P ₁ ，P ₂ Respectively find out the geometric center C ₁ ，C ₂ The dot-to-face distance is calculated as follows:

wherein D _c Is C ₁ ，C ₂ The spatial distance of (a) is,

the distance between points and planes is less than a threshold value for normal vectors of two planes

(3) The plane distance requirement is as follows: over-segmentation is caused by the absence of windows, and the maximum height of a window in a scene is used as a distance threshold.

8. The long-range ground laser point cloud plane segmentation algorithm of claim 7, wherein: first, with P ₁ Establishing a balanced binary tree by taking a middle point as a center, constructing a search range by using a distance threshold value, and then inquiring P ₂ At points within this range, the points exist, i.e., meet the plane distance requirement.

Images