CN118212139B - A laser point cloud ground filtering method based on convex and concave terrain classification - Google Patents

Abstract

The invention discloses a laser point cloud ground filtering method based on convex-concave terrain classification. According to the invention, the ground surface is classified into concave topography and convex topography, and different ground point discriminants are provided for different terrains, so that the extraction of ground points is realized. Compared with the existing ground filtering technology, the method provided by the invention has good self-adaptability, and different parameters do not need to be set for specific terrains; the ground points of the terrains such as the ridge tops and the cliff tops in the terrains abrupt change areas can be effectively extracted, and the ground points are not misjudged to be non-ground points; meanwhile, the extraction of the mountain top ground points of the small mountain can be ensured, and the loss of mountain bodies is prevented.

Description

A laser point cloud ground filtering method based on convex and concave terrain classification

Technical Field

The invention belongs to the technical field of point cloud data classification, and in particular relates to a laser point cloud ground filtering method based on convex-concave terrain classification.

Background technique

Topographic maps are essential for engineering planning and construction. Digital elevation models (DEMs), as the basic data of national geographic information, are also widely used in various industries, such as industry planning, hydrological analysis, and geomorphological analysis.

In recent years, with the popularization of 3D laser scanning technology, this technology has become one of the main means of obtaining topographic maps and DEM results. This technology can quickly and efficiently obtain the coordinate data of the 3D solid surface in the scene. This data is dense discrete coordinate point data, also known as point cloud data, which includes ground, objects, noise and other data. In order to produce corresponding topographic maps or DEM results, it is necessary to extract the elevation data reflecting the surface from the massive point cloud data, and remove the object data and noise, such as houses, trees, grass, electric towers, power lines, flying points, etc. This technology is point cloud filtering.

At present, the mainstream point cloud filtering technology is the progressive encryption filtering algorithm based on irregular triangulated network (TIN) proposed by Axelsso. The main problems of this method are: 1. Ground points are missing in areas with sudden terrain changes. For example, the top ground points of broken terrain such as steep steps and cliffs will be misjudged as non-ground points; 2. This filtering technology is greatly affected by the size parameters of buildings. When the size parameters of buildings are small, some large objects will be misjudged as ground points. When the size parameters of buildings are too large, some small ground points on hills will be judged as non-ground points, resulting in the loss of mountains; 3. This technology is also affected by the angle parameters. When the angle is small, the ground points with sudden elevation changes are seriously lost. When the angle is large, many low vegetation points will be misjudged as ground points.

In addition, the more popular ones include the filtering algorithm based on mathematical morphology, the cloth model algorithm, and the laser point cloud automatic classification algorithm based on deep learning. Among them, the mathematical morphology filter is more dependent on the window size parameter, has weak adaptability, is easily affected by the local terrain, and the filtering results are inaccurate for complex buildings and large slopes. The cloth model has poor adaptability to terrain, especially in complex mountainous areas, and the filtering effect is not ideal. The laser point cloud automatic classification algorithm based on deep learning needs to rely on a large number of learning samples, and its accuracy needs to be improved.

To solve the above problems, the present invention provides a laser point cloud ground filtering method based on convex and concave terrain classification, which can effectively avoid the error of non-ground points being judged as ground points, and at the same time can fully avoid the misjudgment of ground points as non-ground points with high accuracy.

Summary of the invention

The present invention aims to provide a laser point cloud ground filtering method based on convex-concave terrain classification.

The present invention is achieved through the following technical solutions:

The laser point cloud ground filtering method based on convex-concave terrain classification of the present invention comprises the following steps:

S1: Preprocess the laser point cloud data, remove the point cloud data below the ground surface, and mark all point clouds as unclassified points;

S2: Construct a large-size square grid covering the point cloud range, extract the lowest point cloud in the grid as the ground point to construct the initial surface triangulation model;

S3: Use the surface triangulation model to perform plane segmentation on the point cloud data, determine the convex and concave characteristics of the surface within each triangle, and use different ground point identification methods to determine and mark the ground points based on the convex and concave characteristics of the surface;

S4: through the ground points marked in step S3, the marked ground points are selected to update the surface triangulated network model;

S5: Repeat steps S3 and S4 until the maximum side length point of the ground triangulation network is less than the given threshold or there are no points to be classified in the triangulation network, and then stop judging.

The method of the present invention divides the ground surface into convex terrain and concave terrain for processing.

The convex terrain described in the present invention means that the ground points in this area satisfy that the spatial plane constructed by any three ground points should be lower than all ground points within the range of these three points; the concave terrain means that the ground points in this area satisfy that the spatial plane constructed by any three ground points should not be lower than all ground points within the range of these three points.

The size of the large-sized grid in step S2 of the present invention should be larger than the maximum building size.

The specific method of step S3 of the present invention is:

(1) Interpolate the elevation data of each point cloud through the triangulation network ;

(2) Each triangle in the triangulated network is classified as a flat triangle, a concave triangle, or a convex triangle according to the true elevation value of all point clouds within the triangle. Determine the triangle type using the interpolated elevation value;

(3) According to the types of triangles, select different ground point identification methods to identify ground points.

In the specific method of step S3 of the present invention, the calculation method of the interpolated elevation in step (1) is as follows: suppose point i is located in the jth triangle of the triangulation network, and the three vertices of the triangle are Sj1 (xj1, yj1, zj1), Sj2 (xj2, yj2, zj2), and Sj3 (xj3, yj3, zj3). The spatial plane equation of the triangle can be obtained based on the three points Sj1, Sj2, and Sj3 as Z=F(x, y). Suppose the real coordinates of point i are (xi, yi, zi), then the interpolated elevation is .

In the specific method of step S3 of the present invention, the triangle type determination method in step (2) is as follows:

Within a certain threshold µ, the vertical distance between all point clouds in the triangle and the triangle is less than the threshold, that is, all points in the triangle satisfy , then the triangle is a flat triangle;

For non-flat triangles, if the true value of the point cloud elevation within the triangle All greater than interpolated elevation , that is, if the point cloud in the i-th triangle satisfies And the triangle is a non-flat triangle, then the terrain inside the i-th triangle is a convex terrain, and the triangle is a convex triangle;

If the true value of the point cloud elevation exists in the triangle Less than interpolated elevation , that is, the point cloud within the i-th triangle exists And it is a non-flat triangle, then the terrain inside the i-th triangle is concave, and the triangle is a concave triangle.

The threshold value µ in step (2) of step S3 of the present invention is 10 cm.

In the specific method of step S3 of the present invention, the ground point identification method in step (3) is as follows:

Flat triangle determination method: All point clouds within the triangle are determined to be ground points;

Method for identifying ground points in concave triangles: select the point whose real elevation of the point cloud is lower than the interpolated elevation of the triangle and whose elevation difference is the largest as the ground point. and The largest point is taken as the ground point;

Method for identifying ground points in convex triangles: construct three triangles through the point to be determined and the three vertices of the original triangle in which it is located. If any of the three triangles is still a convex triangle, mark the point to be determined as a temporary ground point, traverse all the points to be determined in the original triangle, screen out all temporary ground points, and compare the absolute value of the difference between the real elevation and the interpolated elevation of all temporary ground points. If all the absolute values are greater than the minimum distance from the top of the building to the ground, mark these temporary ground points as ground points, otherwise mark these temporary ground points as building points; at the same time, if all the three triangles are concave triangles, they are determined as non-ground points; other points are regarded as unclassified points and await further determination.

The threshold in step S5 of the present invention is generally the ground point spacing or the minimum size of the negligible landform.

Compared with the prior art, the present invention has the following beneficial effects:

1. Compared with the existing ground filtering technology, the point cloud ground filtering method provided by the present invention has good adaptability and is suitable for both mountainous and plain terrains. It has fewer parameters and does not need to set different parameters for specific terrains.

2. Compared with the existing ground filtering technology, the extraction results of the point cloud ground filtering method provided by the present invention are not overly dependent on parameter settings. It only needs to ensure that the grid size is larger than the maximum building parameter when extracting the lowest point of the grid. The operation results are relatively stable.

3. Compared with the existing ground filtering technology, especially the conventional asymptotic triangulation encryption filtering algorithm, the point cloud ground filtering method provided by the present invention can effectively extract ground points in areas with sudden changes in terrain, such as the top of steps and cliffs, and will not cause ground points to be misjudged as non-ground points.

4. Compared with the existing ground filtering technology, the point cloud ground filtering method provided by the present invention can ensure that the ground points on the top of the hill are extracted.

5. The point cloud ground filtering method provided by the present invention proposes different ground discrimination methods for convex and concave terrains. Its discriminant formula has a theoretical basis. As long as there are ground points, the points that meet the discriminant formula must be ground points. It can effectively avoid the error of discriminating non-ground points as ground points, and can also fully avoid the ground points in the terrain mutation area from being misjudged as non-ground points, with high accuracy.

BRIEF DESCRIPTION OF THE DRAWINGS

Figure 1 Schematic diagram of the process of laser point cloud ground filtering method based on convex and concave terrain classification;

Figure 2 Schematic diagram of any vertical section within a convex-concave triangle;

Figure 3 Schematic diagram of concave terrain ground point discrimination method;

Figure 4 Schematic diagram of convex terrain ground point discrimination method;

Figure 5 Schematic diagram of updating iterative triangulation network and extracting corresponding ground points in concave terrain;

Figure 6 Schematic diagram of updating iterative triangulation of convex terrain and extracting corresponding ground points;

Figure 7 Schematic diagram of updating the iterative triangulation network and extracting corresponding ground points when there are both convex and concave terrains;

Figure 8. Result of extracting corresponding ground points by constructing triangulated network at one time (left is the point cloud before ground point extraction, right is the result of ground point extraction);

Figure 9. Convex terrain extracted by constructing a triangulated network in one go and its corresponding ground point results (the left is the point cloud before convex terrain ground point extraction, and the right is the convex terrain ground point extraction result).

Detailed ways

The technical solution of the present invention is further described in detail below through specific embodiments in combination with the drawings in the embodiments.

Example 1

The present invention provides a laser point cloud ground filtering method, the process of which is shown in FIG1 . The specific steps are as follows:

Step 101: Remove the point cloud data below the ground surface (more than 0.5m below the ground). This can be done manually or based on a certain denoising algorithm. These low points have a great impact on the accuracy of the classification results. All low points should be deleted. Then mark all point cloud data as unclassified point clouds.

Step 102: construct a large-size xy plane grid (such as a 100m*100m grid) covering the point cloud range, extract the lowest point cloud in the grid as the ground point to construct an initial surface Delaunay triangulation model.

Step 103: Plane-dividing the point cloud data using the surface Delaunay triangulation model, that is, projecting the triangulation network and point cloud onto the xy plane, each point cloud will fall into a different triangulation triangle (a triangle after projection), such as the i-th point cloud is located in the j-th triangulation triangle, marking the corresponding relationship between each point cloud and the triangulation triangle; judging the convex and concave characteristics of the surface within each triangle, and using different ground point discrimination methods to determine the ground points and mark them according to the convex and concave characteristics of the surface;

(1) Interpolate the elevation data of each point cloud through the Delaunay triangulation , assume that point i is located in the jth triangle of the triangulation network, and the three vertices of the triangle are Sj1 (coordinates are xj1, yj1, zj1), Sj2 (coordinates are xj2, yj2, zj2), and Sj3 (coordinates are xj3, yj3, zj3). The spatial plane equation of the triangle can be obtained based on the three points Sj1, Sj2, and Sj3 as Z=F(x,y). Suppose the real coordinates of point i are (xi, yi, zi), then the interpolated elevation is .

(2) In implementation, we classify each triangle in the triangulated network into the following three categories: flat triangle, concave triangle, and convex triangle.

A flat triangle can be defined as a triangle whose vertical distance from all point clouds within a certain threshold µ (such as 0.1m) is less than the threshold, that is, all points in the triangle satisfy , then the triangle is a flat triangle.

For non-flat triangles, if the true value of the point cloud elevation within the triangle All greater than interpolated elevation , that is, if the point cloud in the i-th triangle satisfies And the triangle is a non-flat triangle, then the terrain inside the i-th triangle is a convex terrain, and the triangle is a convex triangle;

If the true value of the point cloud elevation exists in the triangle Less than interpolated elevation , that is, the point cloud within the i-th triangle exists If the ith triangle is a non-flat triangle, the terrain inside the ith triangle is concave, and the triangle is a concave triangle. As shown in Figure 2, it is a schematic diagram of any vertical section inside a convex and concave triangle.

(3) According to the type of triangle, select different ground point identification methods. The specific identification methods are as follows:

Flat triangle determination method: All point clouds within the triangle are determined to be ground points.

Method for identifying ground points in concave triangles: select the point whose real elevation of the point cloud is lower than the interpolated elevation of the triangle and whose elevation difference is the largest as the ground point. and The largest point is taken as the ground point, as shown in Figure 3. In implementation, if and (such as 0.1m), all point clouds below the triangle can be determined as ground points.

Method for identifying ground points in convex triangles: construct three triangles through the point to be determined and the three vertices of the original triangle in which it is located. If any of the three triangles is still a convex triangle, mark the point to be determined as a temporary ground point, traverse all the points to be determined in the original triangle, filter out all temporary ground points, and compare the absolute value of the difference between the real elevation and the interpolated elevation of all temporary ground points. If all the absolute values are greater than a certain threshold (the minimum distance from the top of the building to the ground), mark these temporary ground points as ground points, otherwise mark these temporary ground points as building points. At the same time, if all three triangles are concave triangles, they are determined as non-ground points (this step can be implemented when the maximum side length of the triangle is less than a certain value, such as the landform size can be ignored). Other points are regarded as unclassified points and await further determination. As shown in Figure 4.

During the implementation process, convexity judgment can adopt certain accuracy indicators. For example, if there are points lower than the triangle, but the absolute value of the difference between the true elevation and the interpolated elevation is no more than 10 cm, the triangle can be considered to meet the convexity.

Step 104: Update the surface Delaunay triangulation model through the ground points marked in step 103;

Step 105: Repeat steps 103 and 104 until the maximum side length of the ground triangulation network is less than a given threshold or there are no points to be classified in the triangulation network, and then stop judging. The given threshold can generally be set as the ground point spacing or the minimum size of the landform that can be ignored. Figures 5, 6, and 7 are schematic diagrams of updated iterative triangulation networks and selected ground points for different terrains; Figure 8 is a result map of corresponding ground points extracted by constructing a triangulation network once; Figure 9 is a result map of convex terrain extracted by constructing a triangulation network once and its corresponding ground points.

Although the present invention has been described in detail above by means of general description, specific implementation methods and experiments, it is obvious to those skilled in the art that some modifications or improvements can be made to the present invention. Therefore, these modifications or improvements made without departing from the spirit of the present invention all fall within the scope of protection claimed by the present invention.

Claims (5)

1. A laser point cloud ground filtering method based on convex and concave terrain classification, characterized in that the method comprises the following steps: S1: Preprocess the laser point cloud data, remove the point cloud data below the ground surface, and mark all point clouds as unclassified points; S2: Construct a large-size square grid covering the point cloud range, extract the lowest point cloud in the grid as the ground point to construct the initial surface triangulation model; S3: Use the surface triangulation model to perform plane segmentation on the point cloud data, determine the convex and concave characteristics of the surface within each triangle, and use different ground point identification methods to determine and mark the ground points based on the convex and concave characteristics of the surface. The specific methods are as follows: S3-1: Calculate the interpolated elevation value of each point cloud through triangulation interpolation ; S3-2: Each triangle in the triangulation network is classified as a flat triangle, a concave triangle, or a convex triangle, according to the true elevation value of all point clouds within the triangle. With interpolated elevation values Determine the triangle type. The specific method is as follows: Within a certain threshold µ, the vertical distance between all point clouds in the triangle and the triangle is less than the threshold, that is, all points in the triangle satisfy , then the triangle is a flat triangle; For non-flat triangles, if the true value of the point cloud elevation within the triangle All greater than the interpolated elevation value , that is, if the point cloud in the i-th triangle satisfies And the triangle is a non-flat triangle, then the terrain inside the i-th triangle is a convex terrain, and the triangle is a convex triangle; If the true value of the point cloud elevation exists in the triangle Less than the interpolated elevation value , that is, the point cloud within the i-th triangle exists and it is a non-flat triangle, then the terrain inside the i-th triangle is concave, and the triangle is a concave triangle; S3-3: According to each triangle category, different ground point identification methods are selected to identify the ground points. The identification methods are as follows: Flat triangle determination method: All point clouds within the triangle are determined to be ground points; Method for identifying ground points in concave triangles: select the point whose true value of point cloud elevation is lower than the interpolated elevation value of the triangle and whose elevation difference is the largest as the ground point. and The largest point is taken as the ground point; Method for identifying ground points in convex triangles: construct three triangles through the point to be determined and the three vertices of the original triangle in which it is located. If any of the three triangles is still a convex triangle, mark the point to be determined as a temporary ground point, traverse all the points to be determined in the original triangle, screen out all temporary ground points, and compare the absolute value of the difference between the true value of the elevation of all temporary ground points and the interpolated elevation value. If all the absolute values are greater than the minimum value of the distance from the top of the building to the ground, mark these temporary ground points as ground points, otherwise mark these temporary ground points as building points; at the same time, if all the three triangles are concave triangles, they are determined as non-ground points; other points are regarded as unclassified points and await further determination; S4: through the ground points marked in step S3, the marked ground points are selected to update the surface triangulated network model; S5: Repeat steps S3 and S4 until the maximum side length point of the ground triangulation network is less than the given threshold or there are no points to be classified in the triangulation network, and then stop judging. 2. According to the laser point cloud ground filtering method based on convex and concave terrain classification as described in claim 1, it is characterized in that the size of the large-size grid in step S2 should be larger than the maximum building size. 3. According to the laser point cloud ground filtering method based on convex and concave terrain classification described in claim 1, it is characterized in that the calculation method of the interpolated elevation value in step S3-1 is: suppose that point i is located in the jth triangle of the triangulation network, and the three vertices of the triangle are Sj1 (xj1, yj1, zj1), Sj2 (xj2, yj2, zj2), and Sj3 (xj3, yj3, zj3). The spatial plane equation of the triangle can be obtained based on the three points Sj1, Sj2, and Sj3 as Z=F(x, y). Suppose the real coordinates of point i are (xi, yi, zi), then the interpolated elevation value . 4. According to the laser point cloud ground filtering method based on convex and concave terrain classification described in claim 1, it is characterized in that the threshold μ in step S3-2 is 10 cm. 5. According to the laser point cloud ground filtering method based on convex and concave terrain classification as described in claim 1, it is characterized in that the threshold value in step S5 is the ground point spacing or the minimum size of the negligible landform.