Segmentation and Clustering

The goal of this chapter is to turn an undifferentiated cloud of roughly a billion points into a set of coherent candidate regions. Until that partition exists, a heritage TLS scan carries no notion of which points describe a wall, which a column, which a vault rib, and which the wooden pew standing in the nave on the day of the campaign. Segmentation gives that flat list of measurements structure, and the cost of getting it wrong compounds: a mis-segmented capital is mis-classified as an ornament, then recorded incorrectly in the heritage inventory, and finally costed wrongly in the restoration estimate. The numbers set the scale of the task. On a single nave bay I routinely produce 800 to 1500 segments at the architectural level, and on noisy walls 30% of the initial RANSAC planes are rejected on inspection because they fit the noise envelope better than the masonry surface.

Stated precisely, given a point cloud and a homogeneity criterion (normal similarity, adherence to a parametric primitive, spatial proximity, or local density), segmentation is the partition of the cloud into maximal regions that are each homogeneous under the chosen criterion, so that merging any two adjacent regions would violate it. The regions carry no semantic labels. Attaching a meaning such as wall or tree to a region is the separate task of classification. Segmentation is the bridge between geometry and meaning in the processing pipeline. It consumes the normals and curvatures of Chapter 7, on which region growing and supervoxels depend directly, it leans on the spatial indexes of Chapter 4 for its millions of neighbourhood queries, and it works best once the ground filtering of Chapter 9 has separated terrain from the objects standing on it. Its output feeds nearly everything that follows: the classifiers of Chapter 12 attach labels to its regions, the modelling methods of Chapter 16 fit parametric objects to them, and the learned pipelines of Chapter 18 use its over-segmentations as input.

The chapter works through the geometric family first (region growing, RANSAC primitive fitting, Euclidean clustering, supervoxels, graph cuts), pauses on the metrics by which a partition is judged, then turns to the density and proximity-based family (DBSCAN, HDBSCAN, $k$-means, mean shift, hierarchical clustering), and ends where handcrafted criteria give way to learned ones.

Motivation and two families of methods

A raw point cloud is an undifferentiated mass of coordinates. The partition defined above answers the question of which points belong together, and the resulting structure is the prerequisite for almost every analytical task that follows. Object detection requires that individual objects, such as buildings, trees, and vehicles, can be isolated from each other before they can be counted or measured. Surface reconstruction is much easier on a single planar wall than on an unsegmented building, because the fitting algorithm no longer has to discover where one surface ends and another begins. Simplification reduces millions of points to a handful of geometric parameters per segment, which is why a CAD model of a building is several orders of magnitude smaller than the LiDAR scan it was built from. Segment-level features such as area, orientation, and shape (several of which build on the eigenvalue-based descriptors of Chapter 10) are also far more robust descriptors than point-level features, because they average out the noise that any single point carries.