The Hong Kong University of Science and Technology
Department of Computer Science


PhD Thesis Defence


"Curve and Surface Reconstruction from Noisy Samples"

By

Mr. Sheung-Hung Poon


Abstract

Reconstructing an unknown curve or surface from a point cloud is an
important task in geometric modeling applications.  Point clouds obtained
from real applications are usually noisy. For example, when data sets are
obtained by scanning images in the plane or images in three dimensions.
In computer graphics, many curve and surface reconstruction algorithms
have been developed. However, their common drawback is the lack of
theoretical guarantees on the quality of the reconstruction.  This
motivates computational geometers to propose algorithms that return
provably faithful reconstructions. Algorithms of this type are known when
there is no noise in the input points.  This leaves the problem of noise
handling open.  We propose a probabilistic noise model for the curve
reconstruction problem. Based on this model, we design the first curve
reconstruction algorithm that can provably handle noisy input points.  The
reconstruction is faithful with probability approaching 1 as the sampling
density increases. Then we extend our approach to surface reconstruction
from noisy input points.  Not only do we improve the algorithm to make it
run faster, we also make the noise model deterministic which extends its
applicability and simplifies the analysis of the algorithm.  We show that
the surface reconstructed is faithful if the input points satisfy the
deterministic noise model.


Date:			Saturday, 22 May 2004

Time:			9:00a.m.-11:00a.m.

Venue:			Room 1402
			Lifts 25-26

Chairman:		Prof. Guo Wu Meng (MATH)

Committee Members:	Prof. Siu-Wing Cheng (Supervisor)
			Prof. Sunil Arya
			Prof. Mordecai Golin
			Prof. Beifang Chen (MATH)
			Prof. Tamal Krishna Dey (Comp. & Inf. Sci.,
						 Ohio State Univ.)


**** ALL are Welcome ****