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

^*Corresponding author for this work

Department of Computer Science and Engineering

Research output: Contribution to conference › 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
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

Keywords

Curve reconstruction
Probabilistic analysis
Sampling

Access to Document

10.1145/777792.777838

Cite this

@conference{9da5c29e69094ae1951312e23fb6cce9,

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",

year = "2003",

doi = "10.1145/777792.777838",

language = "English",

pages = "302--311",

note = "Nineteenth Annual Symposium on Computational Geometry ; Conference date: 08-06-2003 Through 10-06-2003",

}

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

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://openalex.org/W2203555918

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

U2 - 10.1145/777792.777838

DO - 10.1145/777792.777838

M3 - Conference Paper

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

Keywords

Access to Document

Other files and links

Fingerprint

Cite this