CN115409969A - Long-distance-measurement ground laser point cloud plane segmentation algorithm - Google Patents
Long-distance-measurement ground laser point cloud plane segmentation algorithm Download PDFInfo
- Publication number
- CN115409969A CN115409969A CN202210847780.8A CN202210847780A CN115409969A CN 115409969 A CN115409969 A CN 115409969A CN 202210847780 A CN202210847780 A CN 202210847780A CN 115409969 A CN115409969 A CN 115409969A
- Authority
- CN
- China
- Prior art keywords
- point
- distance
- points
- plane
- point cloud
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Pending
Links
Images
Classifications
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
- G06T17/00—Three dimensional [3D] modelling, e.g. data description of 3D objects
- G06T17/20—Finite element generation, e.g. wire-frame surface description, tesselation
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
- G06T7/00—Image analysis
- G06T7/10—Segmentation; Edge detection
- G06T7/12—Edge-based segmentation
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
- G06T2207/00—Indexing scheme for image analysis or image enhancement
- G06T2207/10—Image acquisition modality
- G06T2207/10028—Range image; Depth image; 3D point clouds
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
- G06T2207/00—Indexing scheme for image analysis or image enhancement
- G06T2207/20—Special algorithmic details
- G06T2207/20021—Dividing image into blocks, subimages or windows
Landscapes
- Engineering & Computer Science (AREA)
- Physics & Mathematics (AREA)
- General Physics & Mathematics (AREA)
- Theoretical Computer Science (AREA)
- Computer Vision & Pattern Recognition (AREA)
- Computer Graphics (AREA)
- Geometry (AREA)
- Software Systems (AREA)
- Image Analysis (AREA)
Abstract
The invention discloses a long-distance measuring ground laser point cloud plane segmentation algorithm, which specifically comprises the following steps: t1, determining an optimal neighborhood based on a dynamic search range, and T2, designing a region growing algorithm based on dimensional characteristics and the optimal neighborhood, and the invention relates to the technical field of laser point cloud data processing application. The long-distance-measurement ground laser point cloud plane segmentation algorithm has density self-adaptability, a neighborhood search range is automatically generated based on theoretical point spacing, and the requirement of point cloud neighborhood searching at different scanning distances can be met; the construction of the optimal neighborhood ensures that the calculation of the local characteristics of the point cloud is not influenced by density change; the estimation of the sampling interval accords with the acquisition principle of a ground laser scanner, and the rationality of the distance between theoretical points is enhanced; the optimal neighborhood is added into the region for increasing, so that the plane segmentation algorithm is suitable for high-density variable point cloud, the wide applicability of a dynamic search range is realized, the determination of the neighborhood search range is started from a single point, and the analysis of the overall density change of the point cloud is not needed.
Description
Technical Field
The invention relates to the technical field of laser point cloud data processing application, in particular to a long-distance measuring ground laser point cloud plane segmentation algorithm.
Background
Laser scanning technology is one of the main ways of building information collection. Because the point cloud collected by the laser scanner is scattered and disordered, how to effectively extract the building information from the point cloud has very important research significance for the construction of smart cities.
The laser scanning technology is divided into an airborne laser scanning technology, a vehicle-mounted laser scanning technology, a ground laser scanning technology and the like according to different carriers. According to a data acquisition mode, the airborne laser scanning technology can acquire building top surface information from the air, and lacks elevation information, and the ground laser scanning technology can acquire abundant building elevation information, so that the airborne laser scanning technology is an important data source for refined three-dimensional reconstruction.
Plane segmentation is an important means for extracting the facade of a building, and comprises region growing, model fitting, feature clustering and the like. The region growing method is a process that a seed point grows in a neighborhood according to certain rules, firstly, the seed point is selected according to the criteria of minimum curvature [ Besl,1988], highest surface significance strength [ Wu Hao,2019] and the like, then, the characteristics of a growing point, a normal vector, an Euclidean distance [ CL Kang,2020], a point-surface distance [ Luweixin, 2015], a plane fitting residual error [ X Ning,2009] and the like are widely used in a growth rule according to the growth rule, and meanwhile, the growing point which is not subjected to growth is used as a new seed point until all points are traversed; the model fitting is to realize segmentation by fitting the original point cloud and a specific model, and the model is composed of geometric elements [ S Xia,2020]. The algorithm with better effect is Hough transform [ D Borrmann,2011], random sampling consistency [ L Li,2017] and a derivative algorithm [ B ZHao,2020]; the characteristic clustering method comprises two steps: and extracting and clustering boundaries. The boundary can be effectively detected according to the local characteristics of the points, for example, the included angle between the boundary point and the normal vector of the adjacent point is larger, the included angle between the normal vector of the point on the same plane is smaller [ E Che,2017], and the included angle between the directions of the beginning and the end of the surrounding path is smaller than 360 degrees [ C Mineo,2019]. The clustering algorithm includes a k-means algorithm, a k-nearest neighbor algorithm, and a density-based algorithm (DBSCAN) [ national institute, 2014].
The existing building plane segmentation method has the following defects:
1. the impact of high density variations on segmentation is less of a consideration. Along with the continuous optimization of scanner hardware, the measuring range of ground laser scanning is increased, and the problem of high-density change is also brought, for example, the included angle of a scanning line is 0.06 degrees, the maximum scanning distance is 1km, and the span from millimeter level to meter level can be realized by the point spacing, so that the high-density change in a scene is caused, and the problem that the neighborhood size is difficult to unify is brought. Region growing and feature clustering are very sensitive to neighborhood selection, which affects the quality of plane segmentation.
2. It is difficult to compromise efficiency and accuracy. The model fitting method has higher robustness, but has higher requirement on the quality of the original point cloud. Due to the fact that ground objects are shielded, ground laser point cloud has certain defects in the integrity aspect, and collected points are sparse along with the increase of scanning distance, therefore, the point cloud needs to be optimized when the algorithm is used on the long-distance-measuring foundation point cloud, and the algorithm efficiency is affected. The region growing algorithm is simple in principle and high in efficiency, and is widely applied to large-scene point cloud segmentation, the seed point selection and the growth rule influence the segmentation efficiency and quality, the reasonable seed point selection method can greatly reduce the algorithm time consumption, and the quality of a segmented plane is determined by the growth rule. In addition, the feature fitting requires that the point cloud has uniform density, and if the density is not uniform or too low, the boundary is lost, and the quality and stability of segmentation are affected.
Disclosure of Invention
Technical problem to be solved
Aiming at the defects of the prior art, the invention provides a long-distance ground laser point cloud plane segmentation algorithm, which solves the problems that the scanning distance of the long-distance ground point cloud is long, and the point cloud density is greatly changed along with the increase of the scanning distance, and the existing plane segmentation method is rarely designed aiming at the situations, so that the invention designs a density self-adaptive segmentation method to solve the following problems:
1) And designing a dynamic search range to search the optimal neighborhood so as to solve the problem of neighborhood size selection caused by density change. The high-density change characteristic of the long-distance ground point cloud enables the point clouds in different density areas to have different neighborhood sizes, plane segmentation is affected, the effective idea for solving the problems is to set a search range to search the optimal neighborhood of each point, meanwhile, the search range is determined by the theoretical point distance, and the search range is constructed based on single points, so that the algorithm is suitable for ground laser point clouds with different longest scanning distances.
2) And improving a region growing algorithm, and overall planning precision and efficiency. The method has the advantages that the model fitting and the feature clustering have certain requirements on the quality of the original point cloud, the ground laser point cloud quality cannot meet the requirements easily, optimization measures are difficult to design, the region growing principle is simple, improvement can be performed according to different requirements, the efficiency is high, in order to improve the segmentation quality, the principal component analysis method is used for calculating the dimension features to solve the situation of boundary point misclassification, the growth rule is designed based on the optimal neighborhood, the accuracy of local feature calculation is improved, and the plane segmentation result is more reasonable.
(II) technical scheme
In order to achieve the purpose, the invention is realized by the following technical scheme: a long-distance ground laser point cloud plane segmentation algorithm 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 Is a random point, 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 delta beta mn ，Δα mn ，Δβ mn ∈[0°,180°]If Δ α is 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, the neighborhood is selected from the point spacing of 1-10 times to make the local features most obvious, and based on the local features, 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 relationships after clustering, selecting a DB index from the internal index in consideration of the influence of the cloud abundance 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 Average dot spacing of (d) 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; the smaller the DB index is, the larger the Rand index is, and the better the clustering result is.
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 represents the information quantity of a certain point neighborhood, the smaller the value is, the more obvious the local characteristics are, and the calculation of the shannon entropy is as follows:
wherein Ef is Shannon entropy, delta 1 ，δ 2 ，δ 3 Is a plane approximation of the neighborhood of the pointA resultant error calculated by principal component analysis, and δ 1 ≥δ 2 ≥δ 3 . 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 1 ，δ 2 ，δ 3 Calculating Shannon entropy according to Shannon entropy calculation formula, and selecting neighborhood radius when 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 λ 1 ≥λ 2 ≥λ 3 。
T2, designing a region growing algorithm based on dimensional features and an optimal neighborhood, wherein the specific determination method comprises the following steps:
p1, architectural extraction: the clustering result not only comprises buildings, but also comprises interferents such as street lamps, trees and the like, because most of the buildings are plane points, and the interferents such as the street lamps, the trees and the like have more discrete points and linear points, on the basis, the buildings are selected according to the proportion of the plane points in each class, different classes in the graph have different colors, and gray is a rendering result;
p2, seed point selection and growth rule setting: in a building, selecting seed points according to the optimal neighborhood, the dimensional characteristics, the normal vector and the point-surface distance;
p3, over-segmentation plane merging: due to the transmission of the laser, the window appears as a void in the point cloud, and the discontinuity in space causes the initial plane obtained by segmentation to be over-segmented.
Preferably, the sampling interval in e2 is a horizontal angle or a vertical angle between adjacent scanning lines of the scanner, and the radian corresponding to the horizontal angle or the vertical angle is an angular resolution.
Preferably, in the step e2, a spherical neighborhood S (p) determined in KNN according to the acquisition principle 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 。
Preferably, the rationality of the parameter Δ setting affects the quality of the estimation of the sampling interval such that Δ is at [0.005 °,0.015 °]Are taken at intervals of 0.001 DEG in the range of (A), alpha is calculated respectively avg Finally take all alpha avg Middle value of (a) avg ) The final sampling interval.
Preferably, the spatial relationship of the internal indexes in the step e4 based on various types after clustering is a dunen index, a contour coefficient and a davisenberg index, and the external indexes are used for comparing a manual classification result with a clustering result by using a manual classification result as reference data, analyzing the effectiveness of the clustering result and dividing the effectiveness into a standard mutual information index, an F-Measure index, a rank index and a Jacard coefficient.
Preferably, 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 growth rules: 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.
Preferably, the over-segmentation problem in step p3 is to optimize an initial result by plane merging, where the plane merging needs to satisfy 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 smaller than a threshold value phi th ；
(2) The requirement of point-surface distance: for two planes P 1 ，P 2 Respectively find out the geometric center C 1 ，C 2 The dot-to-face distance is calculated as follows:
wherein D c Is C 1 ，C 2 The spatial distance of (a) is greater than (b),
is a normal vector of two planes, and the point-to-surface distance is required to be less than a threshold value d' th ；
(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.
Preferably, first with P 1 Establishing a balanced binary tree by taking a middle point as a center, and constructing a search by using a distance threshold valueScope, then query P 2 At points within this range, the points exist, i.e., meet the plane distance requirement.
(III) advantageous effects
The invention provides a long-distance measuring ground laser point cloud plane segmentation algorithm. Compared with the prior art, the method has the following beneficial effects:
(1) The long-distance-measurement ground laser point cloud plane segmentation algorithm has density self-adaptability, a neighborhood search range is automatically generated based on the theoretical point distance (in the scheme, 1-10 times of the theoretical point distance is used as a dynamic search range of a neighborhood), and the requirement of point cloud searching neighborhoods at different scanning distances can be met; the construction of the optimal neighborhood ensures that the calculation of the local characteristics of the point cloud is not influenced by density change; the estimation of the sampling interval accords with the acquisition principle of a ground laser scanner, and the rationality of the distance between theoretical points is enhanced; adding the optimal neighborhood into the region for increasing, so that the plane segmentation algorithm is suitable for high-density change point cloud.
(2) The long-distance ground laser point cloud plane segmentation algorithm has wide applicability of a dynamic search range, the neighborhood search range is determined from a single point, the whole density change of point cloud does not need to be analyzed, repeated setting of different distance measurement ground point cloud search ranges is avoided, and the algorithm has stronger applicability.
(3) According to the long-distance-measurement ground laser point cloud plane segmentation algorithm, by using the indexes inside and outside the clustering analysis and reasonably analyzing the clustering result, on the basis of ensuring the extraction quality of the optimal neighborhood, the invalid subset in the dynamic search range is removed, the calculation of the Shannon entropy on the invalid subset is avoided, and the search time of the optimal neighborhood is shortened.
(4) The long-distance-measurement ground laser point cloud plane segmentation algorithm has the advantages that efficiency and precision are both considered, and the problem of inaccurate estimation of a boundary normal vector is solved by extracting boundary points through dimensional features; on the basis of clustering results, buildings are extracted through overall dimensional characteristics of the buildings, and only the buildings are subjected to plane segmentation, so that the data volume is remarkably reduced, and the processing efficiency is improved; selecting plane points as seed points and growth points, effectively eliminating discrete points, and finally distributing the boundary points to the nearest plane, thereby improving the accuracy of the segmentation result at the boundary; design the facet amalgamation condition based on window size, effectively solved the overdivision problem that the window information disappearance leads to, make the plane cut apart the result more reasonable.
Drawings
FIG. 1 is a flow chart of plane segmentation based on dynamic search range according to an embodiment of the present invention;
FIG. 2 is a schematic diagram illustrating the calculation of horizontal and vertical included angles between a random point and a neighboring point according to an embodiment of the present invention;
FIG. 3 is a schematic diagram of a horizontal angle histogram construction according to an embodiment of the present invention;
FIG. 4 is a schematic diagram illustrating determination of an optimal neighborhood according to an embodiment of the present invention;
FIG. 5 is a schematic diagram of a building extraction according to an embodiment of the present invention;
FIG. 6 is a schematic diagram illustrating a region growing effect according to an embodiment of the present invention;
fig. 7 is a schematic diagram of patch merging according to an embodiment of the present invention.
Detailed Description
The technical solutions in the embodiments of the present invention will be clearly and completely described below with reference to the drawings in the embodiments of the present invention, and it is obvious that the described embodiments are only a part of the embodiments of the present invention, and not all of the embodiments. All other embodiments, which can be derived by a person skilled in the art from the embodiments given herein without making any creative effort, shall fall within the protection scope of the present invention.
Referring to fig. 1-7, an embodiment of the present invention provides a technical solution: a long-distance ground laser point cloud plane segmentation algorithm 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: and separating non-ground points and ground points by using a cloth filtering algorithm, and rejecting the non-ground point clouds.
e2, sampling interval estimation: the sampling interval is a horizontal included angle or a vertical included angle between adjacent scanning lines of the scanner, the radian corresponding to the sampling interval is an angular resolution, N points are randomly selected in the non-ground point cloud according to the collection principle, 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 Is a random point, 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 delta beta mn ，Δα mn ，Δβ mn ∈[0°,180°]If Δ α is mn Not less than 180 deg., 360-delta alpha mn Indicating horizontal included angle
According to the acquisition principle, a spherical neighborhood S (p) is determined in KNN m ) In, p m The number of adjacent points on adjacent scan lines is the largest, as shown in fig. 2, and a histogram is built by counting the distribution of horizontal included angles in a plurality of intervals, wherein the interval width is Δ. 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 。
The rationality of the parameter delta setting affects the quality of the estimate of the sampling interval, making delta at 0.005 deg., 0.015 deg. °]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 (med (. Alpha.)) avg ) Is the final sampling interval.
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, the neighborhood is selected from the point spacing of 1-10 times to make the local features most obvious, and based on the local features, p m Dynamic search range of points
Can be determined as:
e4, performing joint clustering analysis on the internal and external indexes and the best neighborhood search of the Shannon entropy: in that
In selection
And as the clustering radius, clustering the point cloud by using a KNN method, evaluating the clustering result by using the internal and external indexes, and selecting the optimal clustering result.
The internal indexes evaluate the result based on various space relations after clustering, and the internal indexes mainly comprise the following indexes: the method comprises the steps of measuring a Dunn Index, a Denn Index (Dunn) Index, a contour coefficient (Silhouuette coefficient), a Davison burgh Index (DB Index) and the like, wherein the outer Index takes a manual classification result as reference data, compares the reference data with a clustering result, analyzes the effectiveness of the clustering result, and is divided into a standard mutual information Index (NMI), an F-Measure Index, a Rand Index, a Jacard coefficient and the like, the DB Index is selected from the inner Index in consideration of the influence of the cloud massiveness on algorithm efficiency, and the Rand Index is selected from the outer 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 Average dot spacing of (d) 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. The smaller the DB index is, the larger the Rand index is, the better the clustering result is, fig. 4 is an optimal neighborhood determination map, wherein fig. 4 (a) is an internal and external index, and fig. 4 (b) is shannon entropy.
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, as in fig. 4 (a);
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 1 ，δ 2 ，δ 3 Is the plane fitting residual of the neighborhood of the point, which can be calculated by Principal Component Analysis (PCA) [ 5]]And δ 1 ≥δ 2 ≥δ 3 . In a valid subset of the dynamic search range to
Is taken as the neighborhood radius, measured by PCACalculating a covariance matrix of a neighborhood fitting plane, and squaring the characteristic value of the matrix to obtain a fitting residual delta in the three-axis direction 1 ，δ 2 ，δ 3 The Shannon entropy is calculated according to equation (6), as shown in FIG. 4 (b), and the neighborhood radius when Ef is minimum is selected
I.e. the best neighbourhood is determined.
At this time, the local feature of the point is most obvious, and the dimensional feature Dim of the point can be 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 λ 1 ≥λ 2 ≥λ 3 。
T2, region growing algorithm design based on dimension characteristics and optimal neighborhood
p1, architectural extraction: the clustering result not only comprises buildings, but also comprises interferents such as street lamps, trees and the like, as most of the buildings are plane points, and the interferents such as street lamps, trees and the like have more discrete points and linear points, based on the fact that the buildings are selected according to the proportion of the plane points in each class, as shown in fig. 5, different classes in the graph have different colors, and gray is a rendering result;
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, and setting a growth rule, wherein the specific method comprises the following steps;
1) And selecting a seed point. The plane point is used as an initial seed point in the building class, all growing points are used as new seed points in the growing process, and any point only carries out one growing operation.
2) And setting a growth rule. Firstly, taking a growing point as a plane point as a precondition, and then the growing point needs to meet the requirements of distance, normal vector and point-to-plane distance:
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 the greater of the dot-to-face distance, d' th Is the point-to-area distance threshold.
3) A line shaped dot is assigned. The linear points are also part of the plane, and after all the plane points are grown, the linear points are assigned to the nearest plane to obtain the initial segmentation result, as shown in FIG. 6 (b)
p3, over-segmentation plane merging: due to the transmission of the laser, the window appears as a void in the point cloud, and the discontinuity in space causes the initial plane obtained by the segmentation to be over-segmented, as shown in fig. 7 (a). Aiming at the over-segmentation problem, an initial result is optimized through plane combination, and the plane combination needs to meet the following requirements:
(1) And (5) meeting the requirements of the included angle of the normal vectors of the planes. 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) And (5) meeting the requirement of point-surface distance. For two planes P 1 ，P 2 Respectively find out the geometric center C 1 ，C 2 The dot-to-face distance is calculated as follows:
wherein D c Is C 1 ，C 2 The spatial distance of (a) is greater than (b),
in two planesVector, point-to-surface distance needs to be less than threshold value d' th 。
(3) The plane distance requirement. Over-segmentation is caused by the absence of windows, and the maximum height of a window within a scene may be used as a distance threshold. First, with P 1 And establishing a balanced binary tree by taking the middle point as a center, and constructing a search range by using a distance threshold value. Then, query P 2 At points within this range, points exist, i.e., meet the plane distance requirement. FIG. 7 is a patch merge diagram, in which FIG. 7 (a) shows the initial segmentation result and FIG. 7 (b) shows the distance threshold of 1.8m; fig. 7 (c) shows a distance threshold of 0.5m, and fig. 7 (b) represents a patch merging effect when the distance threshold is set to 1.8m, which effectively solves the over-segmentation situation. Fig. 7 (c) represents the effect of the patch merging when the distance threshold is 0.5m, and there is still over-segmentation.
And those not described in detail in this specification are well within the skill of the art.
It should be noted that, in this document, relational terms such as first and second, and the like are used solely to distinguish one entity or action from another entity or action without necessarily requiring or implying any actual such relationship or order between such entities or actions. Also, the terms "comprises," "comprising," or any other variation thereof, are intended to cover a non-exclusive inclusion, such that a process, method, article, or apparatus that comprises a list of elements does not include only those elements but may include other elements not expressly listed or inherent to such process, method, article, or apparatus.
Although embodiments of the present invention have been shown and described, it will be appreciated by those skilled in the art that changes, modifications, substitutions and alterations can be made in these embodiments without departing from the principles and spirit of the invention, the scope of which is defined in 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 1 ，δ 2 ，δ 3 Is the plane fitting residual error of the point neighborhood, is calculated by a principal component analysis method, and delta 1 ≥δ 2 ≥δ 3 . 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 1 ，δ 2 ，δ 3 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 λ 1 ≥λ 2 ≥λ 3 。
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 1 ，P 2 Respectively find out the geometric center C 1 ，C 2 The dot-to-face distance is calculated as follows:
wherein D c Is C 1 ，C 2 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 1 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 2 At points within this range, the points exist, i.e., meet the plane distance requirement.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202210847780.8A CN115409969A (en) | 2022-07-19 | 2022-07-19 | Long-distance-measurement ground laser point cloud plane segmentation algorithm |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202210847780.8A CN115409969A (en) | 2022-07-19 | 2022-07-19 | Long-distance-measurement ground laser point cloud plane segmentation algorithm |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| CN115409969A true CN115409969A (en) | 2022-11-29 |
Family
ID=84157486
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN202210847780.8A Pending CN115409969A (en) | 2022-07-19 | 2022-07-19 | Long-distance-measurement ground laser point cloud plane segmentation algorithm |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN115409969A (en) |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN115661552A (en) * | 2022-12-12 | 2023-01-31 | 高德软件有限公司 | Point cloud processing method, point cloud anomaly detection method, medium and computing equipment |
-
2022
- 2022-07-19 CN CN202210847780.8A patent/CN115409969A/en active Pending
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN115661552A (en) * | 2022-12-12 | 2023-01-31 | 高德软件有限公司 | Point cloud processing method, point cloud anomaly detection method, medium and computing equipment |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN110443810B (en) | Point cloud plane segmentation method based on quick adjacent voxel query | |
| CN106780524B (en) | Automatic extraction method for three-dimensional point cloud road boundary | |
| Lee et al. | Fusion of lidar and imagery for reliable building extraction | |
| CN114332366B (en) | Digital urban single house point cloud elevation 3D feature extraction method | |
| CN111340723B (en) | Terrain-adaptive airborne LiDAR point cloud regularization thin plate spline interpolation filtering method | |
| CN110992341A (en) | Segmentation-based airborne LiDAR point cloud building extraction method | |
| CN111598780B (en) | Terrain adaptive interpolation filtering method suitable for airborne LiDAR point cloud | |
| CN109461207A (en) | A kind of point cloud data building singulation method and device | |
| CN112669333B (en) | Single wood information extraction method | |
| CN111738332B (en) | Underwater multi-source acoustic image substrate classification method and system based on feature level fusion | |
| CN113409332B (en) | Building plane segmentation method based on three-dimensional point cloud | |
| CN105956542B (en) | High-resolution remote sensing image road extraction method based on statistical matching of structural wire harnesses | |
| Li et al. | A branch-trunk-constrained hierarchical clustering method for street trees individual extraction from mobile laser scanning point clouds | |
| CN113486817A (en) | Coal face coal rock identification method based on laser scanning | |
| Yang et al. | A skeleton-based hierarchical method for detecting 3-D pole-like objects from mobile LiDAR point clouds | |
| CN100555326C (en) | A kind of image partition method of dimension self-adaption | |
| CN111738278B (en) | Underwater multi-source acoustic image feature extraction method and system | |
| CN111861946B (en) | Adaptive multi-scale vehicle-mounted laser radar dense point cloud data filtering method | |
| CN111950589B (en) | Point cloud region growing optimization segmentation method combined with K-means clustering | |
| CN115409969A (en) | Long-distance-measurement ground laser point cloud plane segmentation algorithm | |
| CN116579949B (en) | Airborne point cloud ground point filtering method suitable for urban multi-noise environment | |
| CN112070787A (en) | Aviation three-dimensional point cloud plane segmentation method based on opponent reasoning theory | |
| CN117932333A (en) | Urban building height extraction method considering different terrain scenes | |
| CN114005109B (en) | KNN-based adaptive noise filtering method | |
| Xu et al. | A method of 3d building boundary extraction from airborne lidar points cloud |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| PB01 | Publication | ||
| PB01 | Publication | ||
| SE01 | Entry into force of request for substantive examination | ||
| SE01 | Entry into force of request for substantive examination |