The Crust and the β-Skeleton: Combinatorial Curve Reconstruction

doi:10.1006/gmip.1998.0465

Graphical Models and Image Processing

Volume 60, Issue 2, March 1998, Pages 125-135

Graphical Models and...

https://doi.org/10.1006/gmip.1998.0465 Get rights and content

Abstract

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. The required sampling density varies with thelocal feature sizeon 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 thecrust, and the β-skeleton, using a specific value of β.

References (21)

J. Brandt et al.
Continuous skeleton computation by Voronoi diagram
Comput. Vision, Graphics Image Process
(1992)
R.C. Veltkamp
The γ-neighborhood graph
Comput. Geom
(1992)
D.G. Kirkpatrick et al.
A framework for computational morphology
Computational Geometry
(1988)
F. Preparata et al.
Computational Geometry: An Introduction
(1985)
H. Edelsbrunner
Algorithms in Combinatorial Geometry
(1987)
J. O'Rourke
Computational Geometry in
(1994)
J. R. Shewchuk, Triangle.http://www.cs.cmu.edu/∼...
G.P. Robinson et al.
Integrated skeleton and boundary shape representation for medical image interpretation
Proc. European Conf. Comput. Vision
(1992)
R.L. Ogniewicz
Skeleton-space: A multiscale shape description combining region and boundary information
Proc. Comput. Vision Pattern Recognition
(1994)
J. O'Rourke et al.
Connect-the-dots: A new heuristic
Comput. Vision, Graphics Image Process
(1984)

There are more references available in the full text version of this article.

Cited by (349)

Automated geometric digital twinning of bridges from segmented point clouds by parametric prototype models
2023, Automation in Construction
Digital Twins (DTs) provide a promising solution for the maintenance and operation of bridges, thanks to their ability to mirror physical/structural conditions. A bridge DT generally consists of a geometric-semantic model whose creation, however, requires extensive manual effort. This paper presents an automated framework to generate the parametric model of bridges from their segmented point clouds. Following the concept of reverse engineering with parametric modeling, Parametric Prototype Models (PPMs) are proposed as tools to extract parameter values from point clouds. A local and global optimization problem is defined to adjust and assemble PPMs into an integrated model. The proposed approach has been validated by applying it to the point cloud of bridge components as well as point clouds captured from six concrete bridges in Bavaria, Germany. The results show that the proposed approach can generate the parametric model of bridges with a mean absolute error (MAE) of 8.71 cm.
A Data and Knowledge-driven framework of the intelligent process design for special-shaped features of complex aviation parts
2023, Procedia CIRP
While the safety and reliability of aviation equipment are directly determined by the performance of complex aviation parts, these kinds of components still contain lots of special-shaped features, which refer to the machining features that need to be completed by unique process and non-standard cutting tools. In addition, the traditional process design of special-shaped features of complex aviation parts (SFCAP) heavily relies on manual experience, which leads to low machining efficiency and unstable machining quality. To solve this problem, this paper takes SFCAP as the study object and proposes a framework of intelligent process design, which can effectively guarantee the processing quality to support the performance of complex aviation equipment by realizing active adaptive adjustment, rapid iteration, and upgrading of process planning based on the machining data and relative knowledge. Four key-enabling technologies are set forth to support the design, which include the special-shaped feature-process knowledge mapping model, 3D feature recognition and geometric parameter extraction, knowledge uncertainty-based evaluation, and digital twin-based verification and optimization. What's more, the benefits and challenges of the design are analyzed, and the contribution and deficiencies are given at the end of this paper.
A new section line extraction method of ring forgings based on normal vector and L<inf>1</inf>-median
2021, Measurement: Journal of the International Measurement Confederation
Ring forgings are widely used in industrial fields. It is an important way that the key dimensions of ring forgings are obtained by laser scanning to ensure the processing quality. It is difficult to extract high-precision section line of ring forgings from laser point clouds with a lot of noise. This paper presents a new method for extracting section line from raw point cloud of ring forging. An optimization algorithm is created based on the normal vector and L_1-median, which is used to iteratively shrink the sampling points for obtaining the section line of ring forgings. L₁-median has the characteristics of noise immunity, adding normal vector can get more detailed features. The extraction of high-precision section line of ring forgings is realized. Taking the second-order ring forging and the third-order ring forging as the experimental object, experiments are carried out to verify the effectiveness of the model.
Detecting and approximating decision boundaries in low-dimensional spaces
2024, Numerical Algorithms
Improving SDSS Cosmological Constraints through β-Skeleton Weighted Correlation Functions
2024, arXiv
MEDIAL PARAMETRIZATION OF ARBITRARY PLANAR COMPACT DOMAINS WITH DIPOLES
2024, arXiv

View all citing articles on Scopus

^☆: G. Toussaint

¹: Most of this work was done at Xerox PARC, partially supported by NSF Grant CCR-9404113.

²: Work supported in part by NSF Grant CCR-9258355 and by matching funds from Xerox Corp. and performed in part while visiting Xerox PARC.

View full text

Regular ArticleThe Crust and the β-Skeleton: Combinatorial Curve Reconstruction☆

Abstract

Comput. Vision, Graphics Image Process

Comput. Geom

A framework for computational morphology

Computational Geometry

Computational Geometry: An Introduction

Algorithms in Combinatorial Geometry

Computational Geometry in

Integrated skeleton and boundary shape representation for medical image interpretation

Proc. European Conf. Comput. Vision

Skeleton-space: A multiscale shape description combining region and boundary information

Proc. Comput. Vision Pattern Recognition

Connect-the-dots: A new heuristic

Comput. Vision, Graphics Image Process

Regular Article
The Crust and the β-Skeleton: Combinatorial Curve Reconstruction☆