Iteratively weighted principal component analysis and orientation consistency for normal estimation in point cloud

The problem

A point cloud is only a set of 3D coordinates. Many later steps, such as denoising, segmentation, surface reconstruction and visualisation, also need a surface normal at every point, so normal estimation is a basic operation in point cloud processing. The classical method, by Hoppe et al., fits a plane to each point’s nearest neighbours with principal component analysis (PCA) and takes the plane’s normal. It assumes the neighbourhood is close to a plane, and it does not perform well where points are sparse or where the surface has sharp edges: for example, normals can turn gradually around a right angle instead of following the true edge (Fig. 2).

Where point density varies and sharp features occur, the normal directions of adjacent points can also be inconsistent, some pointing inside and some outside. Reconstruction methods such as ball-pivoting and Poisson need consistently oriented normals. Wrong normals at sharp features blur those features after reconstruction, and inconsistent orientations can break the reconstructed surface.

How it works

The method keeps PCA plane fitting as its core and adds two things around it. To make the normals more robust and reliable, it weights every neighbour by distance and by normal similarity and repeats the weighted fit a few times; the authors call this Iteratively Weighted PCA (IWPCA). To make the orientation consistent, it first flips normals using the centre of the cloud and then propagates orientation along a minimal spanning tree (MST).

1. Local plane fit. A Kd-tree finds the k nearest neighbours of each point, and a least-squares plane is fitted to them. The normal is the eigenvector belonging to the smallest eigenvalue of the neighbourhood covariance matrix.
2. Bilateral weights. IWPCA centres the covariance matrix on the point itself and weights each neighbour twice. The spatial weight decreases with the neighbour’s distance from the point, controlled by σ_d, usually half the kNN search radius. The normal weight decreases as the neighbour’s normal departs from the point’s normal, controlled by σ_n, usually 15° to 30°. In the first pass every point’s normal is set to (1, 0, 0), so the normal weight starts out uniform.
3. Iterate. Each new pass uses the normals of the previous pass in the normal weight. More iterations give a better estimate but cost more time; the authors recommend 2 or 3, and the last pass is the result.
4. Pre-flip towards the outside. The centre of the whole cloud is computed, and every normal that points towards it is flipped.
5. Propagate along a minimal spanning tree. Prim’s algorithm builds an MST over neighbouring points, with edge weight 1 − |n_i · n_j|. Starting from the root, each child’s normal is flipped when its dot product with its parent’s normal is negative.

For sharp parts, the normals can additionally be smoothed with the same spatial and normal weights (bilateral weighted smoothing). In the authors’ tests this made the normals on sharp parts more robust but lowered their reliability, so they recommend it only when needed, since IWPCA already improves robustness at edges by itself.

Results

The comparisons in the paper are visual. On the cube, IWPCA improves the robustness of the normals at the sharp edges, and after the MST re-orientation the reliability, robustness and orientation consistency of all normals improve and the shape of the cube is clearer (Fig. 7). When the cube is reconstructed with the Poisson method, the edges and corners obtained from IWPCA normals are sharper and clearer than those from classical PCA normals (Fig. 8). On the sharp cone, classical PCA gives unsatisfactory normals at the tip, leaves some normals uncomputed and points many bottom normals inward; IWPCA improves robustness at both the top and the bottom (Fig. 9). On the scanned surface, the pre-flip and MST propagation (steps 4–5) turn inconsistent normals so that the vast majority point to the raised side (Fig. 11).

IWPCA costs more computation than classical PCA, and its runtimes include the normal re-orientation. With one iteration it is slower than PCA; with three iterations it is somewhat faster than running classical PCA three times. The experiments ran on Windows 7 (64-bit) with an Intel Core i7-5650U CPU at 2.20 GHz and 8 GB RAM. The neighbourhood size k and the weight parameters σ_d and σ_n are hard to determine and were chosen from experience; the authors suggest deriving them from local curvature, noise distribution and point density in future work.