P5-T2 — Neighborhoods and Geometric Features

Learning objectives

After this lesson, you should be able to:

• Define the k-nearest and radius neighbourhoods and discuss how to choose their size.
• Compute the neighbourhood covariance, its eigenvalues and eigenvectors, and the surface normal.
• Derive and apply the linearity, planarity and scatter features and the curvature estimate.
• Explain how noise, density and edges affect local features and how to orient normals.

The idea: the shape of the neighbourhood

Pick a point on a wall and look at the points near it. They form a thin sheet. Pick a point on a cable: a thin rod. A point in foliage: a cloud with no preferred direction. The three shapes differ in how the points spread along the principal directions.

A neighbourhood needs a definition:

• k nearest neighbours: the k closest points. Adapts to density (a larger region where points are sparse) but covers a different physical size in different places.
• Radius neighbourhood: all points within distance r. A fixed physical size, but a very different number of points near and far: dense nearby, a handful far away, possibly none.

A neighbourhood must be large enough to average the noise and small enough to lie on one surface. Where the points are sparse, those requirements cannot both be met.

The mathematics: covariance, eigenvalues and features

For the neighbours p₁, …, p_n of a point with centroid p̄, compute the 3 × 3 covariance matrix

p̄

the centroid (mean) of the neighbourhood. Subtracting it makes C describe the shape, not the position.

C

a symmetric positive semi-definite matrix, so its eigenvalues are real and non-negative and its eigenvectors are orthogonal.

λ1, λ2, λ3

the variances of the points along the three principal axes v1, v2, v3.

Normal and curvature

The normal of the best-fit plane through the neighbourhood is the direction of least variance, the eigenvector v₃ of the smallest eigenvalue. An eigenvector has no sign, so it is oriented towards the sensor: flip it if v₃ · (s − p) < 0, where s is the sensor position. The change of curvature is estimated by the fraction of the variance along the normal:

The curvature estimate is 0 for a perfect plane and about 1/3 for isotropic scatter. It is large at edges and corners, where the neighbourhood is not a single sheet.

Shape features

With the eigenvalues normalised by the largest, three scale-free features describe the shape (Weinmann et al.’s “dimensionality features” normalise by λ1 in the form below):

The largest of the three tells whether the neighbourhood is line-like, plane-like or volumetric. In Lab P5-L1 the simpler rule used the ratios λ3/λ1 and λ2/λ1 with thresholds, which is equivalent in spirit and easier to tune.

Noise, density and edges

A worked example: the normal of five points

Five points lie close to the plane z = 0.1 x (a slope of 5.7°), with about 3 mm of noise: (0, 0, 0.002), (1, 0, 0.102), (0, 1, -0.003), (1, 1, 0.098), (0.5, 0.5, 0.053).

The centroid is (0.500, 0.500, 0.050). The covariance matrix is

Its eigenvalues are λ1 = 0.2020, λ2 = 0.2000 and λ3 = 1.72e-6. The smallest is thousands of times smaller than the others: the points are in a plane. The eigenvector of λ3 is (-0.100, 0.004, 0.995), which should be the normal of the plane z = 0.1x, namely (−0.1, 0, 1)/√1.01 = (−0.0995, 0, 0.995). The estimate matches to within the noise.

Features

Planarity is the largest feature (about 0.99), scatter is close to 0, and the curvature is very small: a plane. Because the points lie on a square, λ1 ≈ λ2 (the square is not elongated), so linearity is small: if the same five points were stretched along one direction (a thin strip) linearity would grow and planarity fall. With noisy, unevenly sampled points the three features of a real plane can come out close to one another, which is why Lab P5-L1 uses thresholds on the ratios λ3/λ1 and λ2/λ1 instead of picking the largest feature.

Noise limit

Noise on the points is σ = 2 cm. The smallest eigenvalue of a perfect plane is then σ² = 4.0e-4. If the neighbourhood spread is about 0.1 m (λ1 ≈ 0.1²/12 ≈ 8.3e-4), λ3/λ1 ≈ 0.48: nearly half, the plane no longer looks like a plane. At a spread of 0.5 m (λ1 ≈ 0.021) the ratio is 0.019. The same noise requires a neighbourhood of at least several tens of centimetres to see a plane, which is bigger than a curb or a step. Size matters.

Engineering implications and limitations

Choose neighbourhood size from the noise and the density. Estimate σ from a flat region of your sensor and take a radius that gives a spread at least ten times σ. In sparse regions use a larger radius or accumulate scans; do not trust normals computed from fewer than about ten points.

Compute at several scales. A multi-scale set of features (small, medium, large radius) separates fine structure (cables, edges) from large structure (walls, ground) and is more robust than any single scale. Many classifiers use all of them.

Orient normals consistently. Towards the sensor for one scan; with a consistent propagation rule for merged clouds, since a flipped normal breaks lighting, registration and plane tests that use the sign.

Mark unreliable estimates. Return the eigenvalues or a confidence with the normal. Edges (high curvature), sparse neighbourhoods and neighbourhoods that include points from very different ranges should be flagged or skipped.

Use the structure when you have it. A range image gives neighbours for free; computing normals from adjacent pixels with a depth-discontinuity check is far faster than a k-d tree and is standard for real-time ground segmentation.

Test with synthetic data. Generate planes, edges, cables and noise with known normals, as in the lab, and measure the angular error against neighbourhood size and noise before trusting the features on real data.

Common misconceptions

Engineering takeaways

1. The covariance of a point’s neighbours (about their mean) has eigenvalues λ1 ≥ λ2 ≥ λ3 that describe its shape: plane (λ3 ≈ 0), line (λ2, λ3 ≈ 0), scatter (all comparable).
2. The normal is the eigenvector of λ3, oriented towards the sensor; curvature ≈ λ3/(λ1 + λ2 + λ3).
3. Linearity, planarity and scatter are scale-free features from the eigenvalue ratios.
4. Noise gives λ3 ≥ σ²; the neighbourhood must be several times wider than the noise, but not so wide that it spans several surfaces.
5. Use multi-scale features, flag edges and sparse neighbourhoods, orient normals consistently and use the range-image grid when you have it.

References and further reading

The five-point example and the noise figures were computed for this lesson.

• Pauly, M., Gross, M. and Kobbelt, L. P. (2002). Efficient simplification of point-sampled surfaces. IEEE Visualization: covariance-based surface variation (curvature) of a point neighbourhood.
• Hoppe, H., DeRose, T., Duchamp, T., McDonald, J. and Stuetzle, W. (1992). Surface reconstruction from unorganized points. SIGGRAPH: normal estimation by local plane fitting and orientation propagation.
• Weinmann, M., Jutzi, B., Hinz, S. and Mallet, C. (2015). Semantic point cloud interpretation based on optimal neighborhoods, relevant features and efficient classifiers. ISPRS Journal of Photogrammetry and Remote Sensing 105: dimensionality features and neighbourhood selection.
• Rusu, R. B. (2010). Semantic 3D Object Maps for Everyday Manipulation in Human Living Environments. KI – Künstliche Intelligenz: normal and feature estimation for point clouds.

Knowledge check

Three conceptual questions. Write an answer, then reveal the explanation. Your answers stay in your browser.

What’s next

Next: finding the ground: fitting a plane to points when much of the cloud is not ground.

Related content

Nothing below is required to finish this lesson.

• Before
  P5-T1: 3D Point-Cloud Representations

  Compare raw points, voxel grids, range images and meshes and what each is good for.

• Lab
  P5-L1: Estimate Surface Normals and Planarity

  Compute local normals and classify points as planar, linear or scattered.