Principal component and Voronoi skeleton alternatives for curve reconstruction from noisy point sets

Abstract

Surface reconstruction from noisy point samples must take into consideration the stochastic nature of the sample. In other words, geometric algorithms reconstructing the surface or curve should not insist on matching each sampled point precisely. Instead, they must interpret the sample as a “point cloud” and try to build the surface as passing through the best possible (in the statistical sense) geometric locus that represents the sample. This work presents two new methods to find a piecewise linear approximation from a Nyquist-compliant stochastic sampling of a quasi-planar C ¹ curve C(u):R → R ³, whose velocity vector never vanishes. One of the methods combines principal component analysis (PCA) (statistical) and Voronoi-Delaunay (deterministic) approaches in an entirely new way. It uses these two methods to calculate the best possible tape-shaped polygon covering the flattened point set, and then approximates the manifold using the medial axis of such a polygon. The other method applies PCA to find a direct piecewise linear approximation of C(u). A complexity comparison of these two methods is presented, along with a qualitative comparison with previously developed ones. The results show that the method solely based on PCA is both simpler and more robust for non-self-intersecting curves. For self-intersecting curves, the Voronoi-Delaunay based medial axis approach is more robust, at the price of higher computational complexity. An application is presented in the integration of meshes created from range images of a sculpture to form a complete unified mesh.

Keywords:

• Curve reconstruction
• Surface reconstruction
• Unorganised points
• Range imaging
• Principal component analysis
• Delaunay triangulation
• Voronoi skeleton