Clustering for Sonar Data

Motivation

Digital ocean environment used to generate the 3D sonar point cloud data used for clustering approaches.

Cluster analysis is the grouping of multi-dimensional data points by a similarity metric. Both spatial or position information and non-spatial information like sizes, weights, colors or any other values that may be obtained from a measurement can be used to determine clusters in point clouds. Multi-beam sonar, which improves upon the one-dimensional depth sounding of single-beam sonar systems by processing the signals from multiple sonar transducers into directional beams, creates such point clouds.

In this Bachelor project, we compared the behavior of different clustering algorithms on idealized pointcloud data to illustrate their characteristic behaviors. Then, the algorithms were applied to multiple examples of sonar pointcloud data obtained from a physically-based sonar simulation software, with the goal of evaluating their ability to identify separate objects in the point clouds.

Comparison of Clustering Algorithms

Using an idealized dataset consisting of a point cloud representing an arangement of spheres and toruses, the k-Means algorithm, linkage clustering, DBSCAN, OPTICS and UMAP approaches were tested. For each algorithm, the effect of using a solid pointcloud or a pointcloud of only the shell of objects as well as the effects of adding noise to the dataset were compared. To quantify the performance of the algorithms, the found clusters were compared to a ground truth by calculating the intersection-over-union (IOU) across all possible found-ground-truth-pairs and using the Hungarian algorithm to find a best correspondence across all clusters.

k-Means was able to separate groups of objects but failed to separate a torus from a nearby sphere, because it assumes only spherical clusters. Additionally, it requires the number of clusters to be known. Linkage clustering similarly separates a known number of clusters, but could separate the torus and the sphere unless a large amount of noise points were added. DBSCAN behaved similarly, while also identifying isolated noise points as such. OPTICS ordered separate objects sequentially, but the reachability diagram contained only a limited number of discrete values due to the point cloud data being aligned to a grid. This made separating the clusters based on reachability impossible with the standard heuristic. Since UMAP is a dimensionality reduction algorithm, it was tested using not the positional information of the points but a 3x3x3 neighborhood of each position, which was converted into a two-dimensional embedding. However, no characteristic information for individual objects or object types was found in the embedding, which instead just represented the gradient in an arbitrary direction and local density of the point cloud.

Ground truth and predicted clusters on synthetically generated point clouds with different levels of overlap after applying DBSCAN clustering.

Results

Visualized sonar scan data, rendered as an (interpolated) 3D-point cloud and found clusters after linkage clustering.

Applying the clustering algorithms to the physically-based simulation data, we found that the clustering performance was affected by artifacts originating from the multibeam sonar principle, specifically the beam pattern, which is much larger than the resolution along the depth axis. Linkage clustering and DBSCAN separated targets in open water, but were not able to tell targets apart from nearby walls.

The gap between the assumptions these algorithms make and the structure of real sonar data could be bridged in future work by adapting the algorithms to account for specific kernels based on the a-priori knowledge of the expected correlation and beamforming patterns. Alternatively, the sonar scans can be pre-processed, for example by applying a form of de-convolution or noise reduction approaches such as Wiener filtering.

Participating Student

• Flemming Stäbler

Participating Supervisors

• Christian Kanarski
• Prof. Dr.-Ing Gerhard Schmidt