Doctoral seminars

< back

Tuesday October 18 2005, 10h00 - 11h00 (Celestijnenlaan 200A 03.14(Cafeteria), 3001 Leuven (Heverlee))

Detection of feature lines in a point cloud by combination of first order segmentation and graph theory

By Kris Demarsin (TWR)

Abstract:

In reverse engineering a physical 3D object is scanned which results in a point cloud. We only know the points and no information about the shape of the object is known. Knowledge about the feature lines, which indicate the sharp edges in a point cloud, gives additional information which is useful in many applications. For example, point clouds are visually easier to understand if the feature lines are indicated in the visualization. In addition, feature lines define the boundaries of the area where a patch, e.g. a B-spline, can be fitted. Shape recognition and quality control are other application areas of feature line extraction.

In this talk, we present an algorithm to reconstruct polygonal lines which indicate the sharp edges in a point cloud. Our prime focus is to detect closed feature lines in order to make patch fitting possible in a following step. We start with a first order segmentation of the point cloud which results in different clusters of points (segments). These segments give a strong indication of the location of the feature lines, so we build a weighted graph structure at the level of segments: vertices correspond to segments and edges connect neighbouring segments. Building the minimum spanning tree of this graph gives, after pruning, an initial reconstruction of the feature lines. Additionally, we introduce a 'grow and connect' algorithm to obtain closed feature lines. A clean up step results in the final graph which approximates the feature lines. The algorithm is applied to different point clouds to illustrate some results.