CAMPINO — A skeletonization method for point cloud processing

A new algorithm for deriving skeletons and segmentations from point cloud data in O(n) time is explained in this publication. This skeleton is represented as a graph, which can be embedded into the point cloud. The CAMPINO method, (C)ollapsing (A)nd (M)erging (P)rocedures (IN) (O)ctree-graphs, is based on cycle elimination in a graph as derived from an octree based space division procedure. The algorithm is able to extract the skeleton from point clouds generated from either one or multiple viewpoints. The correspondence between the vertices of the graph and the original points of the point cloud is used to derive an initial segmentation of these points. The principle of the algorithm is demonstrated on a synthetic point cloud consisting of 3 connected tori. Initially this algorithm was developed to obtain skeletons from point clouds representing natural trees, measured with the terrestrial laser scanner IMAGER 5003 of Zoller+Fröhlich. The results show that CAMPINO is able to automatically derive realistic skeletons that fit the original point cloud well and are suited as a basis for e.g. further automatic feature extraction or skeleton-based registration.