Point clouds from several free sources were used. Outside laser scanning point clouds of a European village (Bildstein, Austria) were obtained from the database Semantic3D (bildstein_station1_xyz_intensity_rgb). Another point cloud (an inside scan of an office space) was obtained from ISPRS’s case study #5. Our own scans of geometric blocks were used as well.
Computations were carried out in MatLab R2018a on a 64-bit Windows 10 Pro with 64 GB RAM, an 8-core Intel Xeon E5 CPU and an NVIDIA Quadro P6000 GPU, with the latter relied on for most performance-heavy calculations.
Though LiDAR scans provide XYZIRGB coordinates, we decided to use only the 3 spatial coordinates (XYZ) because color and intensity interfere too heavily with clustering, as many changes in color due to shadows, different materials and angle of incidence do not correspond to meaningful cluster differentiation. We demonstrate this in Fig. 1, where in the original shots the color scale corresponds to intensity (I), while the coloring in the resulting shot corresponds to clustering done over all 7 of the XYZIRGB coordinates.
As can be discovered in Fig. 1, intensity of a point depends a lot on the angle of incidence of the laser beam, which is useful for clustering and discerning a roof from a façade (as seen by the booth), but when a façade wall is round, this is not useful. The same is true in the case of the back side of the car on the left of the image (Fig. 1).
Below in Fig. 2 we present the results of clustering the Bildstein scan into 25 clusters + 1 noise cluster using both techniques from “Materials and methods”: 5x5 and “in one go”. Note that light gray represents the noise cluster in all figures.
Instance 1/2 is the intermediate result, and we must look at instance 2/2 of the 5x5 technique, which shows that the 5x5 technique results in slightly better clustering (and much faster), when compared to the “in one go” method. Still, neither method is ideal: for example, parts of trees and buildings cluster together, while those objects themselves are split into different clusters. It must be pointed out that the algorithm proposed is useful only for clustering and not classification, and hence, in its basic form, is not intelligent enough to distinguish objects.
Furthermore, the positioning of the laser scanner has an enormous effect on the clustering. Local density of points is orders of magnitude higher at distances close to the scanner, and this has a large effect on the final result of the algorithm, since the weight of each cluster strongly depends on the relative number of points in it. In Fig. 2 we can easily identify where the scanner was placed, as it has many small-volume high-density clusters around it, and a result of the radial dispersion of laser rays from that center to the edges of the image can be seen.
A density readjustment through downsampling, voxeling or other methods could be performed to resolve this issue. Having multiple scans available from different points of view could also improve the result.
We tried downsampling, as well as removing the ground, both separately and together, though to no avail, which is a big surprise.
Additionally, we suspected that since the algorithm involves gradient ascent, it may stop at some local maximum and not a global one. In many cases this is generally avoided due to the vague-to-crisp aspect of the DL approach [17–19, 55]. Nonetheless, this phenomenon was tested by running the algorithm 50 times, each time using randomly initiated cluster centers, and comparing final likelihood function values. We did not notice any strong difference in the results, which actually illustrates a robustness of our algorithm.
We also tested our DL-based algorithm on a subset (1 room) of an ISPRS point cloud (Case Study #5). Below in Fig. 3 we demonstrate the results using the 5x5 technique. Noise, as previously, is colored gray.
The most interesting and unexpected thing about these results is how well the tabletops and several other entities are clustered and separated from other objects, though sometimes the tabletops belong to several different clusters. This can be seen more clearly from different points of view in Fig. 4, where, additionally, the tabletops are manually gathered into one cluster and recolored in blue for ease of visualization. The divider between tables is visualized in similar fashion and is colored in white. All other entities, which were clustered mediocrely, are removed from the visualization for clarity.
A comparison of clustering results of the outside (Bildstein) and indoor (ISPRS) scans shows that the DL algorithm works better on indoor data, where objects are separated better. There is less of chaotic splitting and overlapping, e.g., when half a tree and half a building are clustered together while the remainders of these objects are in other cluster. Splitting, however, is better than overlapping, as this can be corrected by merging clusters, as was done with the tabletop and presented above.
Relative to other methods, quick computation time of the proposed algorithm is one of the main advantages of using DL. For example, in clustering the 29.7 million points of the Bildstein point cloud over the 3 spatial dimensions, if the number of models (clusters) is preset to M = 25 + 1, then 1 iteration of the main loop of the algorithm is computed in just 34 seconds on our computer configuration. Moreover, setting the maximum main loop iterations to 10–20 generally achieves a decent result, but based on our experience we recommend 40–50. Halving the number of iterations from 40 to 20 reduces computation time by 2x gives a loss of the shifted log-likelihood of around 4%
In the same way, the 5x5 technique (restricted to 40 iterations per branch/instance) takes 512 seconds on our computer. Dividing this by 40, we obtain just 12.8 seconds, which is 2.7x faster than the 34 seconds of the first technique.
According to the DL theory, the computation time for a DL-based algorithm should be linear in the number of points in the cloud, as well as in the number of parameters and clusters. However, our test computations seem to give better results: a sublinear time in all three numbers. This may be explained by use of a graphics processing unit (GPU) on our computer, without which our computation times were linear in the number of points, clusters and parameters. It is possible that computation time is in fact sublinear with a GPU up to a certain data and model size, beyond which the computation time tends towards an asymptote, i.e. becomes linear. But this fact is difficult to verify rigorously, because the GPU would need to be utilized in several capacities.