A Distance-Weighted Graph-Cut Method for the Segmentation of Laser Point Clouds

Abstract. Normalized Cut according to (Shi and Malik 2000) is a well-established divisive image segmentation method. Here we use Normalized Cut for the segmentation of laser point clouds in urban areas. In particular we propose an edge weight measure which takes local plane parameters, RGB values and eigenvalues of the covariance matrices of the local point distribution into account. Due to its target function, Normalized Cut favours cuts with “small cut lines/surfaces”, which appears to be a drawback for our application. We therefore modify the target function, weighting the similarity measures with distant-depending weights. We call the induced minimization problem “Distance-weighted Cut” (DWCut). The new target function leads to a slightly more complicated generalized eigenvalue problem than in case of the Normalized Cut; on the other hand, the new target function is easier to interpret and avoids the just-mentioned drawback. DWCut can be beneficially combined with an aggregation in order to reduce the computational effort and to avoid shortcomings due to insufficient plane parameters.

Finally we present examples for the successful application of the Distance-weighted Cut principle. The method was implemented as a plugin into the free and open source geographic information system SAGA; for preprocessing steps the proprietary SAGA-based LiDAR software LIS was applied.