Curve reconstruction from noisy samples

Siu Wing Cheng; Stefan Funke; Mordecai Golin; Piyush Kumar; Sheung Hung Poon; Edgar Ramos

doi:10.1145/777792.777838

Curve reconstruction from noisy samples

Siu Wing Cheng
, Stefan Funke
, Mordecai Golin
, Piyush Kumar
, Sheung Hung Poon
, Edgar Ramos

Research output: Contribution to conference › Paper › peer-review

13 Citations (Scopus)

Abstract

We present an algorithm to reconstruct a collection of disjoint smooth closed curves from n noisy samples. Our noise model assumes that the samples are obtained by first drawing points on the curves according to a locally uniform distribution followed by a uniform perturbation of each point in the normal direction with a magnitude smaller than the minimum local feature size. The reconstruction is faithful with a probability that approaches 1 as n increases. We expect that our approach can lead to provable algorithms under less restrictive noise models and for handling non-smooth features.

Original language	English
Pages	302-311
Number of pages	10
DOIs	https://doi.org/10.1145/777792.777838
Publication status	Published - 2003
Externally published	Yes
Event	Nineteenth Annual Symposium on Computational Geometry - san Diego, CA, United States Duration: 8 Jun 2003 → 10 Jun 2003

Conference

Conference	Nineteenth Annual Symposium on Computational Geometry
Country/Territory	United States
City	san Diego, CA
Period	8/06/03 → 10/06/03

Free Keywords

Curve reconstruction
Probabilistic analysis
Sampling

ASJC Scopus subject areas

Theoretical Computer Science
Geometry and Topology
Computational Mathematics

Access to Document

10.1145/777792.777838

Cite this

@conference{d0c0312c9f76498bbc38cb1bcf11bd1a,

title = "Curve reconstruction from noisy samples",

abstract = "We present an algorithm to reconstruct a collection of disjoint smooth closed curves from n noisy samples. Our noise model assumes that the samples are obtained by first drawing points on the curves according to a locally uniform distribution followed by a uniform perturbation of each point in the normal direction with a magnitude smaller than the minimum local feature size. The reconstruction is faithful with a probability that approaches 1 as n increases. We expect that our approach can lead to provable algorithms under less restrictive noise models and for handling non-smooth features.",

keywords = "Curve reconstruction, Probabilistic analysis, Sampling",

author = "Cheng, \{Siu Wing\} and Stefan Funke and Mordecai Golin and Piyush Kumar and Poon, \{Sheung Hung\} and Edgar Ramos",

note = "Funding Information: * Corresponding author. E-mail addresses: scheng@cs.ust.hk (S.-W. Cheng), funke@mpi-sb.mpg.de (S. Funke), golin@cs.ust.hk (M. Golin), piyush@ams.sunysb.edu (P. Kumar), hung@cs.ust.hk (S.-H. Poon), eramosn@cs.uiuc.edu (E. Ramos). 1 Research of S.-W. Cheng and S.-H. Poon are partly supported by Research Grant Council, Hong Kong, China (project no. HKUST 6190/02E and HKUST 6169/03E). Research of M. Golin is partly supported by Research Grant Council, Hong Kong, China (project no. HKUST 6082/01E and HKUST 6206/02E). 2 Partly supported by the IST Programme of the EU as a Shared-cost RTD (FET Open) Project under Contract No IST-2000-26473 (ECG—Effective Computational Geometry for Curves and Surfaces).; Nineteenth Annual Symposium on Computational Geometry ; Conference date: 08-06-2003 Through 10-06-2003",

year = "2003",

doi = "10.1145/777792.777838",

language = "English",

pages = "302--311",

}

TY - CONF

T1 - Curve reconstruction from noisy samples

AU - Cheng, Siu Wing

AU - Funke, Stefan

AU - Golin, Mordecai

AU - Kumar, Piyush

AU - Poon, Sheung Hung

AU - Ramos, Edgar

N1 - Funding Information: * Corresponding author. E-mail addresses: scheng@cs.ust.hk (S.-W. Cheng), funke@mpi-sb.mpg.de (S. Funke), golin@cs.ust.hk (M. Golin), piyush@ams.sunysb.edu (P. Kumar), hung@cs.ust.hk (S.-H. Poon), eramosn@cs.uiuc.edu (E. Ramos). 1 Research of S.-W. Cheng and S.-H. Poon are partly supported by Research Grant Council, Hong Kong, China (project no. HKUST 6190/02E and HKUST 6169/03E). Research of M. Golin is partly supported by Research Grant Council, Hong Kong, China (project no. HKUST 6082/01E and HKUST 6206/02E). 2 Partly supported by the IST Programme of the EU as a Shared-cost RTD (FET Open) Project under Contract No IST-2000-26473 (ECG—Effective Computational Geometry for Curves and Surfaces).

PY - 2003

Y1 - 2003

N2 - We present an algorithm to reconstruct a collection of disjoint smooth closed curves from n noisy samples. Our noise model assumes that the samples are obtained by first drawing points on the curves according to a locally uniform distribution followed by a uniform perturbation of each point in the normal direction with a magnitude smaller than the minimum local feature size. The reconstruction is faithful with a probability that approaches 1 as n increases. We expect that our approach can lead to provable algorithms under less restrictive noise models and for handling non-smooth features.

AB - We present an algorithm to reconstruct a collection of disjoint smooth closed curves from n noisy samples. Our noise model assumes that the samples are obtained by first drawing points on the curves according to a locally uniform distribution followed by a uniform perturbation of each point in the normal direction with a magnitude smaller than the minimum local feature size. The reconstruction is faithful with a probability that approaches 1 as n increases. We expect that our approach can lead to provable algorithms under less restrictive noise models and for handling non-smooth features.

KW - Curve reconstruction

KW - Probabilistic analysis

KW - Sampling

UR - https://www.scopus.com/pages/publications/0037700433

U2 - 10.1145/777792.777838

DO - 10.1145/777792.777838

M3 - Paper

AN - SCOPUS:0037700433

SP - 302

EP - 311

T2 - Nineteenth Annual Symposium on Computational Geometry

Y2 - 8 June 2003 through 10 June 2003

ER -

Curve reconstruction from noisy samples

Abstract

Conference

Free Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this