EUROGRAPHICS 2003 / P.Brunet and D. Fellner Volume 22 (2003), Number 3
(Guest Editors)
Multi-scale Feature Extraction on Point-sampled Surfaces
Mark Pauly Richard Keiser Markus Gross
ETH Zürich
Abstract
We present a new technique for extracting line-type features on point-sampled geometry. Given an unstruc-
tured point cloud as input, our method first applies principal component analysis on local neighborhoods to
classify points according to the likelihood that they belong to a feature. Using hysteresis thresholding, we then
compute a minimum spanning graph as an initial approximation of the feature lines. To smooth out the features
while maintaining a close connection to the underlying surface, we use an adaptation of active contour mod-
els. Central to our method is a multi-scale classification operator that allows feature analysis at multiple
scales, using the size of the local neighborhoods as a discrete scale parameter. This significantly improves the
reliability of the detection phase and makes our method more robust in the presence of noise. To illustrate the
usefulness of our method, we have implemented a non-photorealistic point renderer to visualize point-sampled
surfaces as line drawings of their extracted feature curves.
1. Introduction
Point-sampled surfaces have emerged in recent years as a
versatile representation for geometric models in computer
graphics. The surface of a 3D object is described by a set of
sample points without further topological information such
as triangle mesh connectivity or a parameterization. Reduc-
ing the representation to the essentials, i.e. the geometric
position of the sample points, is particularly useful when
dealing with large data sets generated by modern acquisi-
tion devices [15]. To display such models, numerous point-
based rendering systems have been developed, e.g. [20, 21,
25, 1]. Apart from acquisition and rendering, a variety of
geometry processing applications have been introduced
recently [18, 19, 26] that demonstrate the versatility of
points as a geometric modeling primitive.
In this paper, we present a new method for detecting and
extracting line-type features on point-sampled surfaces.
This type of information can serve as input for many pro-
cessing applications such as meshing, model segmentation,
or anisotropic fairing. Feature lines can also be used for
visualization to enhance the semantics of renditions of 3D
objects. In Section 4 we will show how artistic line draw-
ings of point-sampled surfaces can be created using the
extracted feature curves.
Features are usually defined as entities of an object that
are considered important by a human for an accurate
description of the object. This definition is highly subjec-
tive, however, and very difficult to express in algorithmic
form. Our goal was to design a feature extraction algorithm
that requires no additional semantic information about the
object. Also, our method should be semi-automatic, i.e.
only require the user to specify a few thresholding parame-
ters. Additional interaction with the object, such as setting
seed points or guiding feature movement, is not necessary.
We therefore base our feature definition on low-level infor-
mation using a statistical operator that measures local sur-
face variation. This operator classifies points according to
the likelihood that they belong to a feature. To improve the
robustness and reliability of the classification stage, we
apply this operator at multiple scales, which allows us to
measure the persistence of a feature [4]. Additionally,
multi-scale classification provides further structural infor-
mation per classified point, e.g. the characteristic scale at
which a feature is most prominent.
We concentrate on line-type features. These are probably
the most important features for surfaces, which are often
composed of patches that are framed by feature lines. A fea-
ture line approximately passes along a ridge of maximum
inflection, which is adequately captured in our surface vari-
ation estimate.
We believe that low-level feature extraction methods
such as ours always require some user feedback, in particu-
lar for our example application of an artistic line-drawing
renderer. To obtain visually pleasing renditions, the user has
to adjust the various parameters of our feature extraction
method until she is satisfied with the result. We therefore