Segmentation of Laser Point Clouds in Urban Areas by a Modified Normalized Cut Method

Area of Science:

• Computer Vision
• Geospatial Data Analysis
• Computational Geometry

Background:

• Normalized Cut is a standard image segmentation technique.
• Existing methods struggle with segmenting urban laser point clouds, especially polyhedral objects with planar surfaces.
• Normalized Cut's preference for short cut lines is suboptimal for point cloud segmentation.

Purpose of the Study:

• To adapt and improve the Normalized Cut algorithm for segmenting urban laser point clouds.
• To address the limitations of Normalized Cut in handling planar surfaces and cut line lengths.
• To introduce a modified segmentation method, Distance-weighted Cut (DWCut), for enhanced point cloud analysis.

Main Methods:

• Modification of the Normalized Cut target function by incorporating distance-dependent weights.
• Development of the Distance-weighted Cut (DWCut) minimization problem.
• Application of a Krylov subspace method for efficient numerical solution of the generalized eigenvalue problem.
• Integration of aggregation techniques to optimize computational efficiency and robustness.

Main Results:

• The Distance-weighted Cut (DWCut) method effectively segments polyhedral objects with planar surfaces in urban laser point clouds.
• DWCut overcomes the limitations of Normalized Cut by optimizing cut surface properties.
• Numerical solutions via Krylov subspace methods are efficient.
• Combined DWCut and aggregation show successful application and improved segmentation accuracy.

Conclusions:

• Distance-weighted Cut (DWCut) offers a significant improvement over Normalized Cut for urban laser point cloud segmentation.
• The modified target function provides better interpretability and overcomes drawbacks of the original method.
• Efficient numerical solutions and aggregation strategies make DWCut practical for real-world applications.
• The method demonstrates successful application and validates its effectiveness through comparison with manual segmentations.