Manifold extraction from point clouds

Point clouds are produced by many applications such as 3D scanners or volume processing tools. If the points are located on a surface, it is interesting to explicitly extract this surface for further analysis.

The challenge is to design a method that

• extracts smooth "manifolds" from noisy point clouds
• does not need a-priori knowledge on the number of existing manifolds
• does not need other information than point coordinates
• robustly handles complex, (self)intersecting manifolds
• can handle very large point clouds efficiently

Algorithm

We have developed an algorithm which complies with the above requirements. Its steps are as follows:

• compute normals for all possible "patch" orientations around each point
• cluster normals and patches using a Gauss map
• group clusters into point sets representing large, connected, smooth manifolds
• use ball pivoting to reconstruct each manifold separately

The image below shows the overall pipeline of the method. From left to right: from a point cloud (1), local surface estimations are computed (2). A Gauss map is next computed from these (3). This map is then segmented (4,5). Finally, the extracted manifolds emerge (6).

Results

The image below shows our method used to extract distinct and separated 3D skeletal manifolds from a 3D skeleton unstructured point cloud - a very complex problem given that these manifolds are arbitrarily shaped, arbitrarily many, and intersect at any kinds of angles. The results show that our method can cleanly separate such manifolds.

Finally, the image below shows surfaces reconstructed from the (cleaned) point-clouds extracted by our method (top row) and other state-of-the-art methods (other rows). Our method can extract far smoother surfaces, even from noisy point clouds.

Discussion

The above algorithm has several desirable properties:

• a point can belong to one or more clusters, thus, manifolds. This allows transparent handling of self-intersecting manifolds
• since we output a set of independent manifolds, it is easy to select the "n" most important ones e.g. based on surface. This is useful for extracting large surfaces from very noisy point clouds.
• the clustering process can be stopped based on local conditions e.g. angles. This allows controlling where a manifold stops
• any surface reconstruction method can be used once we have points clustered in different sets

Acknowledgements

This research was done together with Jacek Kustra (Philips Research) and Andrei Jalba (TU Eindhoven).

Publications

Robust Segmentation of Multiple Manifolds from Unoriented Noisy Point Clouds J. Kustra, A. Jalba, A. Telea, Computer Graphics Forum, vol. 33, no. 1, pp. 73-87, 2014