Difference of Normals as a Multi-Scale Operator in Unorganized Point Clouds

Yani Ioannou, Babak Taati, Robin Harrap, Michael A. Greenspan

TL;DR

This paper introduces the Difference of Normals (DoN), a computationally efficient multi-scale operator for unorganized 3D point clouds. DoN effectively segments large point clouds into scale-salient clusters, proving useful for tasks like semi-automatic annotation and pre-processing for object recognition, especially in challenging urban LIDAR datasets.

What Problem Does This Paper Address?

The proliferation of 3D sensors, particularly LIDAR, has led to an explosion of unorganized 3D point cloud data. Processing these massive datasets (millions to billions of points) for applications like autonomous driving or urban mapping is computationally demanding. Traditional methods often rely on mesh-based or graph-based algorithms, which are memory-intensive. There's a need for efficient, scale-aware operators that can work directly on raw point clouds to extract salient features before applying more complex algorithms. Existing scale-space operators, while successful in 2D, are not easily or efficiently transferable to the irregular structure of 3D point clouds.

Methods

The core contribution is the Difference of Normals (DoN) operator. It's inspired by the Difference of Gaussians (DoG) operator used in 2D computer vision. DoN leverages the fact that surface normals estimated at different support radii capture geometry at different scales. Specifically, for a point p, DoN calculates the difference between normals estimated with a small support radius ($r_1$) and a large support radius ($r_2$):

$\Delta n(p, r_1, r_2) = \frac{\hat{n}(p, r_1) - \hat{n}(p, r_2)}{2}$

where $\hat{n}(p, r)$ is the surface normal estimate at point p with support radius r. The magnitude of this difference vector, $||\Delta n(p, r_1, r_2)||$, indicates the degree of change in surface geometry between the two scales, thus highlighting scale-salient features.

Key methodological aspects include:

  • Normal Estimation: The paper uses Principal Component Analysis (PCA) on local neighborhoods defined by a fixed support radius to estimate normals. This ensures that normals at different points are estimated at the same scale, which is crucial for DoN.
  • Normal Ambiguity Resolution: A simple method is proposed to resolve the inherent two-directional ambiguity of surface normals by ensuring they point in roughly the same hemisphere.
  • Parameter Selection: A data-driven approach is used to select optimal $r_1$ and $r_2$ values by maximizing intra-class response distance and minimizing inter-class responses, using ground truth data.
  • Segmentation: DoN filtering is used as a pre-processing step for segmentation. After filtering points with low DoN magnitudes, a standard Euclidean clustering algorithm is applied to group salient points into objects.

Datasets

  • TITAN Urban Mobile LIDAR Data: Used for initial qualitative demonstrations and development. This dataset consists of dense, real-world urban LIDAR scans.
  • KITTI Vision Benchmark Suite: Used for quantitative evaluation of the segmentation performance. This dataset provides sparser, unorganized point clouds from Velodyne scanners, along with annotated 3D bounding boxes for objects of interest.

Key Insights and Ideas

  • Scale is Implicit in Normal Estimation: The paper's fundamental insight is that the choice of support radius for normal estimation directly encodes geometric scale. This is a powerful observation that allows for scale-space analysis without explicit scale-space kernels.
  • DoN as a General-Purpose Operator: DoN is presented not just as a filtering tool but as a versatile operator that can be used for saliency detection, edge detection, and planar region segmentation.
  • Efficiency for Large Point Clouds: The parallelizable nature of normal estimation and DoN computation makes it highly efficient for processing massive point clouds, a significant advantage over mesh-based methods.
  • Effective Urban Scene Segmentation: DoN proves particularly effective in segmenting complex urban environments with varying object scales and point densities, demonstrating its robustness.

Key Results

  • Qualitative Results: DoN filtering successfully highlights objects of interest (cars, people, lamp posts, curbs) in urban LIDAR scenes, while discarding larger planar surfaces. Figures 3 and 4 visually demonstrate this scale-based filtering.
  • Segmentation Performance: When applied to the KITTI dataset, DoN-based segmentation achieved high precision (>0.9) across various object classes. Recall varied with object scale and DoN parameters, with smaller objects benefiting from smaller radii and larger objects from larger radii.
  • Computational Efficiency: The paper highlights that DoN computation is highly efficient, especially with GPU acceleration. A preliminary GPU implementation was found to be an order of magnitude faster than a CPU implementation. Sub-sampling techniques further improve efficiency with minimal error.

Limitations and Future Work

  • Parameter Sensitivity: While a parameter selection method is proposed, the performance of DoN is still dependent on the choice of $r_1$ and $r_2$.
  • Normal Estimation Robustness: The paper notes that PCA-based normal estimation is not robust to outliers, and for highly noisy data, more robust methods might be necessary.
  • Future Work: The authors suggest developing a DoN-based surface descriptor that exploits multiple radii and integrating DoN with object recognition methods. They also envision an interactive tool for semi-automated annotation of large 3D point clouds.

Summary updated

Abstract

A novel multi-scale operator for unorganized 3D point clouds is introduced. The Difference of Normals (DoN) provides a computationally efficient, multi-scale approach to processing large unorganized 3D point clouds. The application of DoN in the multi-scale filtering of two different real-world outdoor urban LIDAR scene datasets is quantitatively and qualitatively demonstrated. In both datasets the DoN operator is shown to segment large 3D point clouds into scale-salient clusters, such as cars, people, and lamp posts towards applications in semi-automatic annotation, and as a pre-processing step in automatic object recognition. The application of the operator to segmentation is evaluated on a large public dataset of outdoor LIDAR scenes with ground truth annotations.
BibTeX
@inproceedings{ioannou2012difference,
  author = {Yani Ioannou and Babak Taati and Robin Harrap and Michael A. Greenspan},
  title = {{Difference of Normals as a Multi-Scale Operator in Unorganized Point Clouds}},
  booktitle = {3DIMPVT},
  year = {2012},
  url = {https://openreview.net/forum?id=VY-UdaKsYq6},
}
Figure