A Research on MBES data classification denoising algorithm based on Octree index

For the Multi-Beam Echo Sounder (MBES) data denoising problem, the noise is divided into near-ground noise and outlier noise away from the seabed. The algorithm in this paper considers the spatial distribution characteristics of noise and removes two kinds of noise by initial denoising and precise denoising. The algorithm first uses the octree index to organize the point cloud and removes the outlier noise. Then combined with Bayesian estimation theory and statistical methods to remove near-ground noise. This paper designs experiments to process MBES data and compare it with the statistical filter of PCL point cloud library. The experimental results show that compared with the PCL statistical filter, the algorithm used in this paper has good denoising effect and can better preserve the information such as regional boundaries.

with the residual of the seabed trend surface. However, the sensitivity of the method to noise and the efficiency of data processing are related to the size of the detection window, and the window size needs to be manually and repeatedly adjusted. Zhang Zhiwei et al proposed an algorithm based on the estimation of the weighted iteration to fit the trend surface [11]. The algorithm is highly sensitive to noise, but it is difficult to guarantee the computational efficiency when iteratively processing the massive point cloud. Zhang Zhiheng introduced the natural point influence domain and improved the trend surface filtering method [12]. The method is sensitive to noise, but this method needs to search for the natural neighbors of each sounding point. The algorithm is complex and it is not efficient to process massive data.
Through the analysis of a large number of MBES data noise, this paper divides the MBES data noise into two categories: 1. Near-ground noise. This kind of noise is close to the surface of the seabed topography; 2. Obvious outlier noise. This noise is far from the terrain and is sparse. Based on the above analysis, this paper designs algorithms to remove two types of noise according to the characteristics of them. The algorithm is divided into two steps: Initial denoising and precise denoising, respectively removing obvious outlier noise and near-ground noise. Firstly, the octree index is built to construct the topological relationship of the scattered point cloud, and use the number of points in the voxel as a standard to receive or reject the point to remove obvious outlier noise. Then bayesian dynamic estimation theory and statistical methods are used to remove near-surface noise close to the terrain. Design experiments to analyze the execution efficiency and denoising effect of the algorithm.

Algorithm principle
The basic idea of the algorithm: First, the octree is used to establish the topological relationship between scattered point clouds, and the number of points in the voxels of all water depth points is counted until the point cloud traversal ends, then remove significant outlier noise outside of given threshold range. Then create a spatial grid, and the depth value of the grid node is estimated based on Bayesian prediction, and the depth difference between each water depth point and the grid node in the node voxel is calculated. According to the statistical characteristics of the point cloud, noise outside the given error range is removed. When the point cloud traverses, the hash table is used to improve the execution efficiency.
The algorithm has the following characteristics: (1) The applicability of the algorithm is wide, and the effect of removing sparse noise is good; (2) The water depth prediction algorithm based on Bayesian estimation is robust and can distinguish between terrain and near-surface noise; (3) The octree tree is simple to build and has a high level of automation, which is suitable for the processing of massive point cloud data. The algorithm principle is described in detail below.

2.1Initial denoising
The basis for removing outlier noise is to establish an octree index. An octree is a tree-like data structure used to describe three-dimensional space. Each node of the octree represents a volume element of a cube, and each node has eight child nodes. The volume elements represented by the eight child nodes are added together to be equal to the volume of the parent node. The topological relationship of point cloud data can be constructed by establishing an octree. By obtaining the neighborhood information of the voxels at each water depth point and setting an appropriate threshold, the apparent outlier noise can be easier removed. The effect of MBES data to establish octree index is shown in Figure 2.

Precise denoising
2.2.1 Node depth estimation. Take the octree tree voxel center point as a node of the grid to establish a spatial grid. The Bayesian dynamic model theory is used to estimate the depth value of the grid nodes, and the dynamic linear model is established to dynamically predict and update grid nodes. Let : ∈ 0 , … , 1 be the predicted sequence of water depth points for the grid nodes, , 0 is the prediction information of the ℎ water depth point to the grid node. The current mesh node's depth estimate is ̂ | , | , and the node update is performed by the following steps: σ n|n 1 σ n 1|n 1 (1) z n|n 1 z n 1|n 1 σ n|n K n σ n (6) According to the above method, the calculation is completed when all neighborhood information participates in the water depth estimation. Finally, get the estimated results of the grid nodes that contain all the neighborhood information.

Statistical denoising.
After all grid nodes have been estimated, the depth difference between the grid nodes and the water depth points in their voxels needs to be calculated and counted. Since the near-ground noise is distributed on both sides of the terrain, the depth difference distribution is symmetrical. The statistical analysis of depth difference is performed on the measured data of 7986215 data points. The resolution of the octree is 0.5m, and the depth difference distribution is shown in Figure 3. The abscissa indicates the depth difference and the ordinate indicates the probability density. It can be found that the depth difference approximates the normal distribution.   Figure 4. algorithm flow.

Program optimization
The thresholds involved in the algorithm are determined as follows: 1) The neighborhood number threshold 1  is to remove the low-density point cloud while avoiding accidental deletion of the surface and edge of the seabed topography, and in the case of the resolution of the octree is 0.5m, 1  takes 2; 2) The denoising threshold 2  determines is typically taken as 2 .

4.1Experimental data and environment
The experimental data is the measured point cloud collected by the R2Sonic2024 multi-beam system, and the measurement area is about 8 square kilometers. The basic configuration of the experimental computer is CPU: 1.8GHz, Intel(R) Core(TM) i7-4500U; RAM: 8GB. The experimental software environment is based on Qt4.8.7+VS2013 compiler +PCL (Ver1.8.0).

Algorithm execution efficiency analysis.
In this experiment, the same experimental data is processed by the algorithm and PCL statistical filter, and the execution time of the two methods is compared. The PCL filter parameters are 100  k and double medium error. The octree resolution of this algorithm is 5m. The experimental results are shown in Table 1 and Figure 5.   Figure 5. Experimental result diagram. It can be obtained from the experimental results that as the number of points clouds increases, the time consumption of the PCL algorithm and the algorithm increase linearly. However, the execution time of the algorithm in this paper grows faster than the PCL algorithm, but eventually the difference between the two tends to be stable. This is because the efficiency of the algorithm in this paper is affected by the number of water depth points involved in the estimation. As the number of point clouds grows, the number of voxels increases, but the number of water depth points in voxels does not change significantly. Therefore, the execution efficiency of this algorithm increases linearly with the increase of point cloud number. The difference between algorithm efficiency and PCL algorithm is controlled at around 8%.

4.2.2
Algorithm denoising effect analysis. The purpose of this experiment was to analyze the denoising quality of the algorithm used in this paper and compare it with the PCL algorithm. In this experiment, a multi-beam point cloud containing 302062 data points with dense noise in the survey area is selected to demonstrate the denoising effect. The following are the experimental results.
(a) Pre-treatment effect (b) Initial denoising effect (c) Precise denoising effect Figure 6. Point cloud overall rendering: before denoising (a) and after denoising (b), (c).   Figure 6 shows the overall effect before and after denoising. Figure6 (a) shows the point cloud effect before denoising, Figure6 (b) shows the point cloud effect after initial denoising, and Figure6 (c) shows the point cloud effect after precise denoising. It can be found that after initial denoising, obvious outlier noise can be removed, and topographic and near-ground noise are preserved. After precise denoising, near-ground noise is removed and topographic features are preserved. Figure 7(d) and Figure 7 (e) shows the denoising details of the algorithm. The algorithm can distinguish terrain and noise better. Figure 7(f) is the denoising effect diagram of PCL algorithm. Denoising using PCL algorithm is difficult to preserve regional boundary information.
In this paper, 1422 noises are removed by initial denoising, 962 noises are removed by precise denoising, 299678 inner points are confirmed, and 298827 inner points are confirmed by PCL algorithm. Calculate the proportion of terrain that is considered to be a noise point. The algorithm error rate is 0.09% and the PCL algorithm error rate is 0.48%. In summary, it can be seen that the algorithm is superior to the PCL algorithm in terms of boundary reservation.

Conclusion
Aiming at the problem of multi-beam point cloud denoising, this paper divides the noise into nearground noise and outlier noise according to the spatial distribution characteristics of noise. After initial denoising and precise denoising, two types of noise are removed respectively. The experimental results show that the algorithm has good denoising effect. Compared with the PCL statistical filter, the algorithm can better preserve the region boundary information. However, it is found that the denoising effect of the algorithm is not good when dealing with strip edges and data staggered layers. These situations will be the focus of subsequent research.