CN109934120A - A step-by-step point cloud noise removal method based on spatial density and clustering - Google Patents

Abstract

The invention discloses a step-by-step point cloud noise removal method based on spatial density and clustering, comprising: S1, extracting a point cloud with a preset proportion of the total point cloud data to calculate the point cloud density, which is taken as the average of the whole point cloud data. Density, count the average number Q of point clouds in the r×r×r cube space, take Q as the reference value of the density threshold of the spatial density denoising method, and define the threshold O; S2, traverse each point in the point cloud data, find Take the number K of point clouds in the r×r×r cube space of the point. If K is less than the threshold O, it is determined as a point-like noise point and removed; The initial denoising point cloud data of the noise point; S3, cluster the initial denoising point cloud data, and read the point cloud data set; S4, count the number M of point clouds in each set, if M is less than the reference value Q, then judge It is a cluster noise point and removed; if M is greater than or equal to the reference value Q, it is reserved to obtain the final denoising result. The invention can filter out point noise and cluster noise at the same time.

Description

A step-by-step point cloud noise removal method based on spatial density and clustering

technical field

The invention relates to the technical field of geographic space information systems, in particular to a step-by-step point cloud noise removal method based on spatial density and clustering.

Background technique

Airborne LiDAR (LiDAR, Light Detection and Ranging) system is an active earth observation system that integrates laser ranging technology, computer technology, inertial measurement unit (IMU)/DGPS differential positioning technology. The system can not only measure the three-dimensional coordinates of the ground object, but also obtain the reflection intensity information of the laser point. It has the advantages of high degree of automation, little influence by weather, short data production cycle, high precision, and is not affected by external conditions, so it is widely used to obtain surface spatial information. However, when it acquires surface spatial information, the acquired point cloud data often contains noise due to the LiDAR system itself or the environment of the survey area.

Noise points can be divided into two categories according to their aggregation characteristics. The first category is point noise, which is further divided into high-level noise and low-level noise, which are characterized by irregular and discrete distribution in the entire survey area. This type of noise is caused by the LiDAR system generating distance outliers or receiving multiple invalid laser diffuse reflections during laser emission and return; the second type is cluster noise points, which are characterized by a small number of noise points clustered together. Most of this kind of noise is caused by the laser pulse signal hitting the flying object.

Noise points will have a great impact on the subsequent processing of point cloud data. For example, most of the LiDAR point cloud data filtering algorithms are based on the assumption that the lowest point of local elevation is the ground point. If the low-level noise is not removed, it will cause some terrain. Points are mistakenly identified as feature points and filtered out. In 3D modeling, the existence of noise points also affects the accuracy of modeling.

In order to avoid the influence of noise points on subsequent work such as point cloud data filtering and modeling, the prior art provides a variety of denoising methods, such as: ① A distance-based denoising method, which is mainly based on the different distribution characteristics of noise points and valid points to denoise. Due to the scattered distribution of noise points, their distance from the adjacent points is much larger than the distance between the effective points and the adjacent points, so a distance threshold can be set to distinguish and eliminate them. ②Denoising method based on mathematical morphology, which mainly uses open operation and closed operation for filtering, and can be used to filter out noise points when the window size is set very small.

However, the above denoising methods can only remove some noise points, and their performance in removing cluster noise is not ideal, that is, there is a problem that point noise and cluster noise cannot be filtered at the same time.

SUMMARY OF THE INVENTION

The purpose of the present invention is to solve the problem that point noise and cluster noise cannot be filtered out at the same time, and propose a step-by-step point cloud noise removal method based on spatial density and clustering.

A step-by-step point cloud noise removal method based on spatial density and clustering, including the following steps:

S1, extract the point cloud with a preset proportion of the total point cloud data to calculate its point cloud density, take the point cloud density as the average density of the entire point cloud data, and count the average number Q of point clouds in the r×r×r cube space, Take Q as the reference value of the density threshold of the spatial density denoising method, and define the threshold value O according to the reference value;

S2, traverse each point in the point cloud data, and obtain the number K of point clouds in the r×r×r cube space of the point. If K is less than the threshold O, it is determined as a point-like noise point and removed; if K is greater than is equal to the threshold value O, then keep it to obtain the initial denoising point cloud data with point-like noise points removed;

S3, cluster the above-mentioned initial denoising point cloud data, and read the point cloud data set;

S4, count the number M of point clouds in each set. If M is less than the reference value Q, it is determined as a cluster noise point and removed; if M is greater than or equal to the reference value Q, it is retained to obtain the final denoising result.

Wherein, the step S1 specifically includes the following steps:

S11, extract 10% of the total point cloud data and calculate its point cloud density to represent the average density of the entire point cloud data, and count the average number Q of point clouds in the r×r×r cube space as the spatial density for denoising Reference value for normal density threshold;

S12, define an r×r×r cube space, if the coordinates of the current judgment point X ₁ are X ₁ , Y ₁ , Z ₁ , then the X, Y of any point in the r×r×r cube space range of the point X ₁ , the Z coordinate satisfies the condition of formula (1);

S13, after traversing the point cloud data, accumulate the total number of points that satisfy the _{X 1} , X ₂ . . . 2) is obtained by formula;

where N is 10% of the number of points in this point cloud data, and K _N is the total number of points that exist in the r×r×r cube space of point _XN .

Wherein, in the step S2, the threshold value O is preferably 1/4 of the reference value Q.

Wherein, the step S3 specifically includes the following steps:

S31, read the set I of the initial denoising point cloud data, the number of point clouds in the set I at this time is P, construct the r×r×r cube space of the first read-in point x ₀ , and put the points in this area and point x ₀ are put into the same empty set A ₁ , and the set A ₁ is deleted from the set I, this is the first clustering, if the number of points added to the clustering is M ₁ at this time, then the set A ₁ is at this time The coordinates (x ₁ , y ₁ , z ₁ ) of the newly added M ₁ points satisfy the condition of formula (3);

Where k is the number of clustering times, at this time k=1; x ₀ , y ₀ , z ₀ are the coordinates of the first read-in point, and the number P _s of the remaining points in the set I is shown in formula (4);

Where k is the number of clustering times, at this time k=1; M _k is the number of points added to the set A ₁ by the kth clustering;

S32, perform the second clustering, traverse the remaining points in the set I, add the points whose coordinates conform to the formula (3) into the set A ₁ , and delete the M ₂ points added to the set A ₁ from the set I, At this time, the total number of points M in the set A ₁ is shown in formula (5);

S33, judge whether the point was added to the set A ₁ in the last clustering, and the judgment condition is as in formula (6). If m>0, it means that the point was added to the set A ₁ in the previous clustering, then continue the next clustering and add the set to the set A 1 . The remaining points satisfying the formula (3) in I are added to the set A ₁ , and the newly added M _k points are deleted from the set I;

S34, repeat step S33 until m=0, at this time set A1 is the _first point cloud set in set I to complete the clustering, and has been deleted from set I.

Wherein, the step S4 specifically includes the following steps:

S41, determine whether the number of point clouds in set A ₁ is greater than a threshold, where the value of the threshold is the reference value Q in step S1, if it is greater than the threshold, add set A ₁ to the empty set B, if not, do not perform the operation;

S42, judge whether the remaining number P _s of the point cloud of set I is greater than 0, if so, repeat steps S31-S34, if not, the algorithm ends, and finally the point cloud data is classified into set A ₁ , set A ₂ ...... set A _i number Sets with different number of point clouds, of which the set with the number of point clouds greater than the threshold is added to set B, and set B is the point cloud data that does not contain cluster noise.

According to the step-by-step point cloud noise removal method based on spatial density and clustering provided by the present invention, the method uses original point cloud data, according to the different characteristics of noise points and effective points, using point-like noise density less than effective point density, and clustering Since the number of clustered noises is smaller than the number of effective point clusters, point noises are first removed based on spatial density, and then clustered noises are further removed based on clustering, so as to achieve step-by-step removal of pointy noise and clustered noise. Experiments show that this method can Not only can the above two types of noises be effectively filtered out, but also effective points can be protected from being misjudged and eliminated, resulting in a smaller denoising error and high robustness.

Description of drawings

The above and/or additional aspects and advantages of embodiments of the present invention will become apparent and readily understood from the following description of the embodiments in conjunction with the accompanying drawings, wherein:

1 is a flowchart of a step-by-step point cloud noise removal method based on spatial density and clustering provided according to an embodiment of the present invention;

Figure 2 is a view of experimental data, wherein, (a) samp21 view; (b) samp24 view; (c) samp41 view;

Figure 3 is a comparison chart of two denoising results of three groups of experimental data, among which, (a) a comparison chart of two denoising results of samp21; (b) a comparison chart of two denoising results of samp24; (c) two denoising results of samp41 comparison chart;

Figure 4 is a comparison diagram of samp21 denoising results, wherein (a) original data; (b) SOR denoising method results; (c) results of the methods provided by the present invention;

Figure 5 is a comparison diagram of samp24 denoising results, wherein (a) original data; (b) SOR denoising method results; (c) results of the methods provided by the present invention;

Fig. 6 is a comparison diagram of samp41 denoising results, wherein (a) original data; (b) SOR denoising method result; (c) result of the method provided by the present invention.

Detailed ways

In order to make the purposes, technical solutions and advantages of the embodiments of the present invention clearer, the technical solutions in the embodiments of the present invention will be clearly and completely described below with reference to the accompanying drawings in the embodiments of the present invention. Obviously, the described embodiments These are some embodiments of the present invention, but not all embodiments. Based on the embodiments of the present invention, all other embodiments obtained by those of ordinary skill in the art without creative efforts shall fall within the protection scope of the present invention.

Referring to FIG. 1, the step-by-step point cloud noise removal method based on spatial density and clustering provided by an embodiment of the present invention includes steps S1-S4:

S1, extract the point cloud with a preset proportion of the total point cloud data to calculate its point cloud density, take the point cloud density as the average density of the entire point cloud data, and count the average number Q of point clouds in the r×r×r cube space, Take Q as the reference value of the density threshold of the spatial density denoising method, and define the threshold value O according to the reference value;

Compared with the effective point cloud, the point-like noise has a discrete and irregular distribution. Using this feature, a spatial density threshold can be set to remove the point-like noise with small density. Since different point cloud data have different point cloud densities, in order to apply to point cloud data with different point cloud densities, before performing the spatial density denoising method, first extract the point cloud calculation with a preset proportion of the total point cloud data. The point cloud density represents the average density of the entire point cloud data. Preferably, 10% of the total point cloud data is extracted first to calculate the point cloud density to represent the average density of the entire point cloud data.

Specifically, step S1 includes steps S11 to S13:

S11, extract 10% of the total point cloud data and calculate its point cloud density to represent the average density of the entire point cloud data, and count the average number Q of point clouds in the r×r×r cube space as the spatial density for denoising Reference value for normal density threshold;

S12, define an r×r×r cube space, if the coordinates of the current judgment point X ₁ are X ₁ , Y ₁ , Z ₁ , then the X, Y of any point in the r×r×r cube space range of the point X ₁ , the Z coordinate satisfies the condition of formula (1);

S13, after traversing the point cloud data, accumulate the total number of points that satisfy the _{X 1} , X ₂ . . . 2) is obtained by formula;

where N is 10% of the number of points in this point cloud data, and K _N is the total number of points that exist in the r×r×r cube space of point _XN .

S2, traverse each point in the point cloud data, and obtain the number K of point clouds in the r×r×r cube space of the point. If K is less than the threshold O, it is determined as a point-like noise point and removed; if K is greater than is equal to the threshold value O, then keep it to obtain the initial denoising point cloud data with point-like noise points removed;

Among them, when the value of the threshold O is too large, the type II error will be too large, and if it is too small, the ideal denoising effect may not be achieved. Preferably, the threshold value O is 1/4 of the reference value Q.

S3, cluster the above-mentioned initial denoising point cloud data, and read the point cloud data set;

Among them, after the denoising of S1-S2, some point cloud data still have cluster noise, because the density of cluster noise is similar to the density of effective points, it cannot be effectively distinguished only by the characteristic of density. The purpose of noise is to remove residual cluster noise.

The idea of denoising method based on clustering is: put multiple points with close distances into a set, and finally the entire point cloud data can be divided into multiple sets according to the distance, and at the same time, the data contained in each set can be known. Number of point clouds. Since most of the cluster noise points are caused by the laser pulse signal hitting the flying object, the number of the clustered points is much smaller than that of the effective points. Setting a threshold for the number of point clouds contained in a set distinguishes cluster noise from other valid points.

Specifically, step S3 includes steps S31 to S34:

S31 , read the set I of the initial denoising point cloud data, the number of point clouds in the set I at this time is P, construct the r×r×r cube space of the first read-in point x ₀ , and put the points in this area and point x ₀ are put into the same empty set A ₁ , and the set A ₁ is deleted from the set I, this is the first clustering, if the number of points added to the clustering is M ₁ at this time, then the set A ₁ is at this time The coordinates (x ₁ , y ₁ , z ₁ ) of the newly added M ₁ points satisfy the condition of formula (3);

Where k is the number of clustering times, at this time k=1; x ₀ , y ₀ , z ₀ are the coordinates of the first read-in point, and the number P _s of the remaining points in the set I is shown in formula (4);

Where k is the number of clustering times, at this time k=1; M _k is the number of points added to the set A ₁ by the kth clustering;

S32, perform the second clustering, traverse the remaining points in the set I, add the points whose coordinates conform to the formula (3) into the set A ₁ , and delete the M ₂ points added to the set A ₁ from the set I, At this time, the total number of points M in the set A ₁ is shown in formula (5);

S33, judge whether the point was added to the set A ₁ in the last clustering, and the judgment condition is as in formula (6). If m>0, it means that the point was added to the set A ₁ in the previous clustering, then continue the next clustering and add the set to the set A 1 . The remaining points satisfying the formula (3) in I are added to the set A ₁ , and the newly added M _k points are deleted from the set I;

S34, repeat step S33 until m=0, at this time set A1 is the _first point cloud set in set I to complete the clustering, and has been deleted from set I.

S4, count the number M of point clouds in each set. If M is less than the reference value Q, it is determined as a cluster noise point and removed; if M is greater than or equal to the reference value Q, it is retained to obtain the final denoising result.

Wherein, step S4 specifically includes steps S41-42:

S41, determine whether the number of point clouds in set A ₁ is greater than a threshold, where the value of the threshold is the reference value Q in step S1, if it is greater than the threshold, add set A ₁ to the empty set B, if not, do not perform the operation;

S42, judge whether the remaining number P _s of the point cloud of set I is greater than 0, if so, repeat steps S31-S34, if not, the algorithm ends, and finally the point cloud data is classified into set A ₁ , set A ₂ ...... set A _i number Sets with different number of point clouds, of which the set with the number of point clouds greater than the threshold is added to set B, and set B is the point cloud data that does not contain cluster noise.

In order to verify the effectiveness of the method provided in this example, three sets of data provided in the ISPRS website were selected for testing (https://www.itc.nl/isprs/wgIII-3/filtertest/downloadsites/). The experimental point cloud data was acquired by the OptechALTM airborne LiDAR system, and the point spacing was between 1-1.5m. The three sets of test samples contain different terrain features. For example, the sample samp21 contains bridges, irregular buildings, low vegetation, etc., with a total of 12960 points; the sample samp24 contains large buildings and stepped terrain, with a total of 7492 points; samp41 contains data blank, irregular buildings, a total of 11231 points. These three groups of sample data all contain high-bit noise and low-bit noise, point noise and cluster noise, as shown in Figure 2. Therefore, it is advantageous to check the effectiveness and robustness of the method of the present invention.

The above-mentioned step-by-step point cloud noise removal method based on spatial density and clustering is mainly divided into two stages. The first stage is based on the idea of spatial density to remove point-like noise; At the expense of type II error, the cluster noise not removed in the first stage is removed. Judgment criteria are determined by Type I error (T ₁ ), Type II error (T ₂ ) and total error (T ₃ ). The specific formula is shown in formula (7).

Among them, a is the number of noise points that are incorrectly determined as valid points, b is the number of noise points that are correctly determined to be noise points, c is the number of valid points that are incorrectly determined to be noise points, and d is the number of valid points that are correctly determined to be valid points.

Table 1 shows the accuracy evaluation results of primary denoising and secondary denoising for three groups of experimental data:

Table 1 Accuracy evaluation of primary denoising and secondary denoising

It can be seen from the above data that after the second denoising, the type I errors in the three sets of experimental data are effectively reduced, and the total error is slightly reduced. Among them, the two sets of data of samp21 and samp24 reduce the type I error without increasing the type II error. Although the type II error of samp41 has increased, the type I error has been greatly reduced, and the total error has also been reduced. . The type I error of the experimental data of samp21 and samp41 is greatly reduced because there are unremoved cluster noise points in the initial denoising, and the reduction of type I error of the samp24 experimental group is smaller, because most of the noise It is point noise, and the ideal effect has been obtained in the initial denoising. Based on the evaluation results of the three sets of experimental data, it can be found that the secondary denoising can effectively reduce the type I error without increasing the type II error as much as possible.

Figure 3 shows the comparison of the three sets of experimental data after denoising twice.

It can be seen from the comparison charts of the three sets of experimental data samp21, samp24 and samp41 that the cluster noise that was not removed after the first denoising can be effectively removed by the second denoising, and the effective points are not significantly lost. .

The StatisticalOutlierRemoval (SOR) denoising method that comes with Cloud Compare software (https://www.danielgm.net/cc/) is used for comparison. The principle of the SOR denoising method is to find the distance from the judgment point to its nearest neighbors. The average value of , and some points whose distance average exceeds a certain range of the overall point cloud distance average are removed as noise points. FIG. 4 , FIG. 5 and FIG. 6 are comparison diagrams of the results of three sets of experimental data using the SOR denoising method and the present invention.

By comparing the original data in Figure 4, Figure 5 and Figure 6 (a) with the data in (b) using the SOR denoising method, it can be seen that the SOR denoising method can effectively remove point noise, but cannot remove cluster noise. . By comparing the original data of Fig. 4, Fig. 5 and Fig. 6 (a), the data of group (b) using the SOR denoising method and the results of the method provided by the present invention in group (c), it can be found that the method provided by the present invention not only Point noise can be removed, and cluster noise can also be removed effectively.

Table 2 is the error comparison between the SOR denoising method and the method provided by the present invention. From Table 2, it can be seen that the type II error of the SOR denoising method is larger than that of the method provided by the present invention. The noise points are removed; the type I error of the method provided by the present invention is smaller than the type I error of the SOR denoising method. Combining the two, the SOR denoising method cannot effectively remove the cluster noise, and will easily remove the effective points excessively, while the method provided by the present invention can not only remove the cluster noise, but also protect the effective points from being excessively removed.

Table 2 Error comparison between the SOR denoising method and the method provided by the present invention

The above experiments show that the method provided by the present invention can effectively remove point noise and cluster noise in a variety of complex terrains, and will not filter out effective points and damage the original terrain. It can also be seen from the comparison with the SOR denoising method that the method provided by the present invention can obtain smaller denoising errors and has higher robustness.

To sum up, according to the step-by-step point cloud noise removal method based on spatial density and clustering provided by the present invention, the method uses the original point cloud data, and according to the different characteristics of noise points and valid points, the point-like noise density is smaller than the valid point density. , and the characteristic that the number of clustered noises is less than the number of valid point clusters, firstly remove pointy noise based on spatial density, and then further remove clustered noise based on clustering, so as to achieve step-by-step removal of pointy noise and clustered noise. Experiments show that , the method can not only effectively filter the above two types of noise, but also can protect the effective points from being rejected by misjudgment, obtain smaller denoising errors, and have high robustness.

In the description of this specification, description with reference to the terms "one embodiment," "some embodiments," "example," "specific example," or "some examples", etc., mean specific features described in connection with the embodiment or example , structure, material or feature is included in at least one embodiment or example of the present invention. In this specification, schematic representations of the above terms do not necessarily refer to the same embodiment or example. Furthermore, the particular features, structures, materials or characteristics described may be combined in any suitable manner in any one or more embodiments or examples.

Although embodiments of the present invention have been shown and described, it will be understood by those of ordinary skill in the art that various changes, modifications, substitutions and alterations can be made in these embodiments without departing from the principles and spirit of the invention, The scope of the invention is defined by the claims and their equivalents.

Claims (5)

1. a step-by-step point cloud noise removal method based on spatial density and clustering, is characterized in that, comprises the following steps: S1, extract the point cloud with a preset proportion of the total point cloud data to calculate its point cloud density, take the point cloud density as the average density of the entire point cloud data, and count the average number Q of point clouds in the r×r×r cube space, Take Q as the reference value of the density threshold of the spatial density denoising method, and define the threshold value O according to the reference value; S2, traverse each point in the point cloud data, and obtain the number K of point clouds in the r×r×r cube space of the point. If K is less than the threshold O, it is determined as a point-like noise point and removed; if K is greater than is equal to the threshold value O, then keep it to obtain the initial denoising point cloud data with point-like noise points removed; S3, cluster the above-mentioned initial denoising point cloud data, and read the point cloud data set; S4, count the number M of point clouds in each set. If M is less than the reference value Q, it is determined as a cluster noise point and removed; if M is greater than or equal to the reference value Q, it is retained to obtain the final denoising result. 2. The step-by-step point cloud noise removal method based on spatial density and clustering according to claim 1, wherein the step S1 specifically comprises the following steps: S11, extract 10% of the total point cloud data and calculate its point cloud density to represent the average density of the entire point cloud data, and count the average number Q of point clouds in the r×r×r cube space as the spatial density for denoising Reference value for normal density threshold; S12, define an r×r×r cube space, if the coordinates of the current judgment point X ₁ are X ₁ , Y ₁ , Z ₁ , then the X, Y of any point in the r×r×r cube space range of the point X ₁ , the Z coordinate satisfies the condition of formula (1); S13, after traversing the point cloud data, accumulate the total number of points that satisfy the _{X 1} , X ₂ . . . 2) is obtained by formula; where N is 10% of the number of points in this point cloud data, and K _N is the total number of points that exist in the r×r×r cube space of point _XN . 3. The step-by-step point cloud noise removal method based on spatial density and clustering according to claim 2, wherein in the step S2, the threshold value O is 1/4 of the reference value Q. 4. The step-by-step point cloud noise removal method based on spatial density and clustering according to claim 3, wherein the step S3 specifically comprises the following steps: S31, read the set I of the initial denoising point cloud data, the number of point clouds in the set I at this time is P, construct the r×r×r cube space of the first read-in point x ₀ , and put the points in this area and point x ₀ are put into the same empty set A ₁ , and the set A ₁ is deleted from the set I, this is the first clustering, if the number of points added to the clustering is M ₁ at this time, then the set A ₁ is at this time The coordinates (x ₁ , y ₁ , z ₁ ) of the newly added M ₁ points satisfy the condition of formula (3); Where k is the number of clustering times, at this time k=1; x ₀ , y ₀ , z ₀ are the coordinates of the first read-in point, and the number P _s of the remaining points in the set I is shown in formula (4); Where k is the number of clustering times, at this time k=1; M _k is the number of points added to the set A ₁ by the kth clustering; S32, perform the second clustering, traverse the remaining points in the set I, add the points whose coordinates conform to the formula (3) into the set A ₁ , and delete the M ₂ points added to the set A ₁ from the set I, At this time, the total number of points M in the set A ₁ is shown in formula (5); S33, judge whether the point was added to the set A ₁ in the last clustering, and the judgment condition is as in formula (6). If m>0, it means that the point was added to the set A ₁ in the previous clustering, then continue the next clustering and add the set to the set A 1 . The remaining points satisfying the formula (3) in I are added to the set A ₁ , and the newly added M _k points are deleted from the set I; S34, repeat step S33 until m=0, at this time set A1 is the _first point cloud set in set I to complete the clustering, and has been deleted from set I. 5. The step-by-step point cloud noise removal method based on spatial density and clustering according to claim 4, wherein the step S4 specifically comprises the following steps: S41, determine whether the number of point clouds in set A ₁ is greater than a threshold, where the value of the threshold is the reference value Q in step S1, if it is greater than the threshold, add set A ₁ to the empty set B, if not, do not perform the operation; S42, judge whether the remaining number _Ps of the point cloud of set I is greater than 0, if so, repeat steps S31-S34, if not, the algorithm ends, and finally the point cloud data is classified into set A ₁ , set A ₂ . . . set A _i number Sets with different number of point clouds, of which the set with the number of point clouds greater than the threshold is added to set B, and set B is the point cloud data that does not contain cluster noise.