Point Cloud Thinning
Challenge
Our client is a university that trains specialists in geosciences, optical technologies, economics, information systems, geomonitoring, and the sustainable development of territories.
Laser scanning is a popular method in modern geodesy used to obtain information about an area such as a canyon, road, building, etc.
As a result, there is a rapidly emerging market for processing and visualizing the laser scanning results, which are referred to as point clouds. Point clouds are usually represented as a set of three-dimensional coordinates (that can include additional data such as intensity, color, etc.). One of the major steps in processing the data is to thin the data, that is, to reduce the number of points while preserving important information (without losing any essential data about the object). If large amounts of data are reduced, further processing and visualization is simplified.
Axmor was given the task of designing software that would handle the thinning procedure.
Solution
We needed to create an application that takes a cloud data file in one of the predefined formats (.obj or similar) and the desired density value for the output (i.e. degree of thinning) and outputs a file with thinned data of the given density. An important requirement was that the borders of the object (the edges of a road or a pit) could not be thinned so that the object’s edges would be clearly visible. We were not asked to visualize the final results; the client planned to do this using third-party tools.
Algorithms Used
Based on the preliminary assumptions about the nature of the input data, Axmor developers selected one of the iterative simplification algorithms described in Meshfree Thinning of 3D Point Clouds, (Dyn and Iske, 2007). For this algorithm, the least significant points are removed one by one from the array of points. The least significant points are determined by a recursive thinning procedure described below.
- For each point, find an estimated tangent plane in the local neighborhood of the point using principal component analysis.
- Reconstruct the local surface with the center at the point using only active close points (those that were not filtered out at an earlier step). Here, the radial basis function method is used.
- Calculate the significance of the given point as the deviation of the reconstructed local surface approximation from the current point and from close points that have been removed during thinning.
It is important to note that we only use a limited number of close points to determine the significance of any point. Therefore, we could be sure that this procedure would not be unduly complex. Moreover, the significance was determined in a way that satisfied an important intuitive notion: points have less significance in areas where the surface fluctuates less, and more in areas with high fluctuations. Therefore, those points were removed earlier.
Computer implementation for this process required additional data structures, namely, the red-black balanced binary tree and the three-dimensional kd-tree. The red-black balanced binary tree is used to order points by significance and quickly find and remove the minimum element, and the three-dimensional kd-tree is used to store points and find neighbors. Moreover, we had to re-calculate the maximum cubic density of the data (the number of points in a cubic meter) at each step and compare it with the desired value.
The limitation of this algorithm resulting from computer implementation is that at some point it starts to remove significant information. Therefore, once this threshold is reached, we stop calculating significances. When the density of points is higher than the desired value, the rest of the points are thinned using the Monte Carlo method (probabilistic uniform data thinning without consideration of geometrical features).
At the first step of the process, we filter the border points using the open-angle criterion. It states that a point is a border point if the projection of the close points within a local neighborhood to the tangent plane lies within a segment with a sufficiently large angle (for example, 160°). See the figure below for an illustration.
