FEATURE EXTRACTION FROM POINT CLOUDSÆStefan Gumhold, Xinlong Wang & Rob MacLeo dÆWSI/GRISUniversityofT[email protected] Scientic Computing and Imaging InstituteUniversity of Salt Lake City, [email protected]@cvrti.utah.eduABSTRACTThis pap er describ es a new metho d to extract feature lines directly from a surface point cloud. No surface recon-struction is needed in advance, only the inexpensive computation of a neighbor graph connecting nearby p oints.The feature extraction is performed in two stages. The rst stage consists of assigning a p enaltyweight to each pointthat indicates the unlikelihoo d that the p oint is part of a feature and assigning these p enaltyweights to the edgesof a neighb or graph. Extracting a sub-graph of the neighbor graph that minimizes the edge p enaltyweights thenproduces a set of feature patterns. The second stage is especially useful for noisy data. It recovers feature lines andjunctions by tting wedges to the crease lines and corners to the junctions.As the method works on the lo cal neighbor graph only, it is fast and automatically adapts to the sampling resolution.This makes the approach ideal as a prepro cessing step in mesh generation.Keywords: Feature Detection, Scattered Data, Crease Recovery, Border Detection, Edge Linking1. INTRODUCTIONFigure 1. dierent elements in the crease and b orderpatternsIn this paper we consider the feature detection and re-construction problem for the case of the input surfacebeing described by a point cloud. Figure 1 illustratesfor the surface of the well known Stanford bunny thedifferent types of feature elements that we want to ex-tract. The crease pattern, shown in dark blue, consistsof crease lines that either terminate in junctions or sin-gleton ends or they close to form a loop. The borderpattern consists only of border loops. Input points thatlay on a crease are called crease points, points on theborder loops are border points. At a junction the corre-sponding data point is called a corner or junction pointand at singleton ends we find end points.Feature reconstruction on a point cloud is a usefulpreprocessing step for surface reconstruction. Thedetected and reconstructed features enable splittingthe surface reconstruction problem into simpler sub-problems on smooth surface patches. Another possi-bility to exploit reconstructed features is to enrich thepoint cloud around feature lines in order to ensure asufficient sampling density. The feature extraction al-gorithm that we describe here is fully automated andno seed or junction points need to be marked by theuser.Figure 2 illustrates our feature extraction pipeline. Theinput is a point cloud a); in this case the underlyingsurface is a model of the human torso. In the anal-ysis stage we construct a neighbor graph b) on thepoint cloud that reflects proximity and compute the lo-cal sampling density. The feature extraction stage c),d) and e) first fits ellipsoids c) to the neighborhoodsof the input points, approximates the surface curva-ture and the maximum open angle; the latter is usedto detect border points. From these vertex propertiescrease, corner and border penalty functions are de-fined that measure the unlikelihoodthat a specific pointis on a crease or border line, respectively. From thepenalty functions at the vertices penalty weights arecomputedfor the edges of the neighbor graph. The fea-ture line linkage d) finds a minimum spanning graph inthe neighbor graph that minimize the crease or borderpenalty weights, respectively. The minimum spanninggraph is similar to a minimum spanning tree but allowsfor significantly long cycles, which are needed to de-tect feature patterns with loops. A pruning algorithmcuts off short branches e). For noisy data the extractedcrease lines are jittery because no input points lay di-rectly on the actual crease line, in which case we ap-ply the crease line and junction recovery stage. Herewedges, a simple crease representation consisting oftwo half planes meeting at a line, are fit to the creaseneighborhood along the crease lines. Then the neigh-borhoods of junction points are fit to corners that con-sist of a corner point and several incident planes. Thenumber of planes incident to a corner equals the degreeof the crease junction. The crease points with jitter areprojected onto the wedges and corners. In a final stepthe feature lines and loops are converted to a splinerepresentation f) by a least squares fitting approach.Our feature detection and recoveryapproachis tailoredas a preprocessing stage for surface reconstruction andoptimized for fast execution. Two complexity mea-sures influence the overall run time: the total numbernof input points from the point cloud and the numbermof output points on the feature patterns. As the pointcloud describes a surface and the feature patterns setsof lines,mis of the orderO(pn). It is obvious that wehave to consider every input point as we do not knowwhere the features are and that therefore our algorithmhas to be at least linear inn. Our approach tries tokeep the computational cost per input point as low aspossible by computing only some penalty functions,which reject instantly most of the edges in the neigh-bor graph. In this way the run time for the computationof the minimum spanning graph already depends onmand not onn.1.1 Related WorkThe feature extraction problem is closely related tosurface reconstruction, which has important applica-tions in laser range scanning, scientific computing,computer vision, medical imaging, and computer as-sisted surgical planning. Our algorithm addressessome of the problems that arise in surface reconstruc-tion of datasets that contain creases and corners [19,10, 18, 6, 3]. For these approaches it is very helpful toextract the feature lines and junctions beforehand.Most of the reconstruction algorithms that can accom-modate creases and corners do so either implicitly orin a post processing step. The graph-based surface re-construction of Mencl and M¨uller [15] handles sharpedges by maximizing for each point the sum of dihe-dral angles of the incident faces. The optimization isperformed only locally and depends on the order inwhich the input points are processed. Especially indegenerate cases this approach can produce ”crispy”crease lines i.e., lines that are broken by notches. Aproblematic constellation of points that often arises atsharp edges occurs when two points on the crease forman equilateral