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

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

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.

Introduction

The proliferation of 3D data from LIDAR sensors on autonomous vehicles and GIS mapping platforms has created a critical need for efficient algorithms to process unorganized point clouds. These datasets typically consist of millions of $(x, y, z)$ coordinates without inherent topological structure. Traditional processing methods often rely on building complex meshes or connected graphs, which are computationally expensive and memory-intensive. This paper introduces the Difference of Normals (DoN) operator, a simple yet powerful multi-scale tool that serves as a 3D analogue to the "Difference of Gaussians" used in 2D image processing.

Methods: The Difference of Normals Operator

The core intuition behind the DoN operator is that surface normals estimated at different scales capture different geometric properties. For any point $p$ in a point cloud $P$, the surface normal $\hat{n}(p, r)$ is estimated using a neighborhood of radius $r$.

The DoN operator is defined as the vector difference between two normals calculated at a small radius ($r_s$) and a large radius ($r_l$): $$\Delta_{\hat{n}}(p, r_s, r_l) = \frac{\hat{n}(p, r_s) - \hat{n}(p, r_l)}{2}$$

The Difference of Normals operator compares surface normals at two scales to identify geometric features.

A small radius captures fine-grained details but is sensitive to noise, while a large radius captures the underlying global geometry. When these normals are subtracted, the resulting magnitude is low for points on flat surfaces (where normals at both scales align) and high for points near features that are salient at the chosen scales. This operator is highly parallelizable and suitable for GPU acceleration.

Experimental Results

The authors evaluated the DoN operator using the TITAN Urban Mobile LIDAR dataset and the KITTI Vision Benchmark Suite.

Scale-Based Filtering

By thresholding the magnitude of the DoN operator, a scene can be filtered to retain only points that are salient at specific scales. This effectively removes "background" elements like flat roads and building faces, significantly reducing the number of points for subsequent processing steps.

Filtering a point cloud using DoN at different scales. Thresholding the magnitude significantly reduces point count while preserving salient objects.

As shown in Figure 3, applying the DoN operator with different radii pairs allows for the isolation of various features. For instance, a pair like $(0.1\text{m}, 1.0\text{m})$ can reduce a scene from over 600,000 points to approximately 135,000, focusing on objects like cars and pedestrians.

Performance and Accuracy

On the KITTI dataset, DoN-based segmentation achieved high precision, often exceeding 0.9. Computationally, the method is very efficient. A scene with ~478,000 points was processed in 7.8 seconds on a standard CPU, which was further reduced to 3.4 seconds using decimation. A preliminary GPU implementation achieved a processing time of 565ms, demonstrating its potential for real-time applications.

Conclusion

The Difference of Normals operator provides a computationally efficient way to perform multi-scale analysis on unorganized 3D point clouds. By isolating features based on physical scale, it serves as an effective pre-processing step for object recognition and semi-automatic annotation. Future work includes addressing parameter sensitivity and improving robustness in sparse data environments.

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},
}

Loading related content...

Figure