The Crust and the ß-Skeleton: Combinatorial Curve Reconstruction

GRAPHICAL MODELS AND IMAGE PROCESSING

Vol. 60/2, No. 2, March, pp. 125–135, 1998 ARTICLE NO. IP980465

The Crust and the β-Skeleton: Combinatorial Curve Reconstruction
Nina Amenta1
Computer Sciences Department, University of Texas at Austin, Austin, Texas 78712

Marshall Bern
Xerox PARC, 3333 Coyote Hill Road, Palo Alto, California 94304

and David Eppstein 2
Department ofInformation and Computer Science, University of California at Irvine, Irvine, California 92697 Received March 18, 1997; revised December 1, 1997; accepted December 30, 1997

We construct a graph on a planar point set, which captures its shape in the following sense: if a smooth curve is sampled densely enough, the graph on the samples is a polygonalization of the curve, with no extraneous edges. Therequired sampling density varies with the local feature size on the curve, so that areas of less detail can be sampled less densely. We give two different graphs that, in this sense, reconstruct smooth curves: a simple new construction which we call the crust, and the β-skeleton, using a specific value of β.
c 1998 Academic Press

The reconstruction of curves in the plane is important in computervision. Simple edge detectors select image pixels which are likely to belong to edges, often delimiting the boundaries of objects. Grouping these pixels into likely curves is an area of active research. Extension of our ideas to three dimensions would be useful for constructing three-dimensional models from laser range data, stereo measurements, and medical images. 2. DEFINITIONS In this paper, wewill consider closed, compact, twice-differentiable 1-manifolds, without boundary, embedded in the plane; we shall call such a manifold a smooth curve. According to our definition, then, a smooth curve can have several connected components, but no endpoints, branches, or self-intersections. Let F be a smooth curve and S ⊂ F a finite set of sample points on F. DEFINITION. A polygonal reconstruction ofF from S is a graph that connects every pair of samples adjacent along F, and no others. Clearly no algorithm can reconstruct any curve from any set of samples; we need some condition on the quality of S. Our condition will be that the distance from any point p on F to the nearest sample s ∈ S is at most a constant factor r times the local feature size at p, which we define to be the distance fromp to the medial axis of F (see Section 4). This condition has the attractive property that less detailed sections of the curve do not have to be sampled as densely. Given a sample S from a smooth curve which meets the sampling condition for an appropriately small value of r , we show that a polygonal reconstruction is given by either of the two graphs defined below.
1077-3169/98 $25.00 Copyright c1998 by Academic Press All rights of reproduction in any form reserved.

1. INTRODUCTION There are many situations in which a set of sample points lying on or near a surface is used to reconstruct a polygonal approximation to the surface. In the plane, this problem becomes a sort of unlabeled version of connect-the-dots: we are given a set of points and asked to connect them into the mostlikely polygonal curve. We show that under fairly generous and well-defined sampling conditions either of two proximity-based graphs defined on the set of points is guaranteed to reconstruct a smooth curve. These two graphs are the crust, which we define below, and the β-skeleton, defined 10 years ago by Kirkpatrick and Radke [1], with an appropriately chosen value of β. Figure 1 shows an example of apoint set and its crust. The points were chosen by hand. Notice that fewer samples are required on the goose’s back than on its head and foot.

1 Most of this work was done at Xerox PARC, partially supported by NSF Grant CCR-9404113. 2 Work supported in part by NSF Grant CCR-9258355 and by matching funds from Xerox Corp. and performed in part while visiting Xerox PARC.

125

126

AMENTA,...