Eurographics Symposium on Geometry Processing (2006)
Konrad Polthier, Alla Sheffer (Editors)
Overfitting Control for Surface Reconstruction
Yunjin Lee
1
Seungyong Lee
1
Ioannis Ivrissimtzis
2
Hans-Peter Seidel
3
1
POSTECH
2
Coventry University
3
MPI Informatik
Abstract
This paper proposes a general framework for overfitting control in surface reconstruction from noisy point data.
The problem we deal with is how to create a model that will capture as much detail as possible and simultaneously
avoid reproducing the noise of the input points. The proposed framework is based on extra-sample validation. It
is fully automatic and can work in conjunction with any surface reconstruction algorithm. We test the framework
with a Radial Basis Function algorithm, Multi-level Partition of Unity implicits, and the Power Crust algorithm.
Categories and Subject Descriptors
(according to ACM CCS): I.3.5 [Computer Graphics]: Computational Geometry
and Object Modeling; I.6.5 [Simulation and modeling]: Model Development
1. Introduction
In this paper, we deal with the problem of data overfitting in
surface reconstruction. Overfitting appears when we model a
given sample so faithfully that we capture not only informa-
tion about the underlying surface but also the idiosyncrasies
of the sample, that is, the noise in the points. Fig. 1 shows an
example of overfitting.
Instead of modifying any of the existing algorithms, we
propose a general framework for handling overfitting, which
can be used in conjunction with any surface reconstruc-
tion technique. Our framework is based on a simple and
accurate method for error estimation, extra-sample valida-
tion [HTF01]. The initial data set is randomly subdivided
into two distinct subsets, the training set and the validation
set. Data from the training set are used for trials of surface re-
construction, while the quality of reconstruction is assessed
using the validation set. To have trials of reconstruction with
increasing surface complexity, we use a hierarchical parti-
tion of the training data, based on an octree. We compute a
representative training sample for each octree cell and a sur-
face is created by applying a reconstruction algorithm to the
training samples from the leaf cells of the octree.
1.1. Related work
In the area of surface reconstruction, [HDD
∗
92, TL94,
BBX95, CL96] are some of the earlier algorithms that influ-
enced the field. More recently, implicit techniques emerged
Figure 1: Curve reconstruction: (a) sample points; (b) un-
derfitted model; (c) correct model; (d) overfitted model.
as the fastest and more stable techniques. The most common
choices of implicits are the radial basis functions (RBFs)
[CBC
∗
01,OBS03] and quadrics [OBA
∗
03]. Delaunay tetra-
hedrization has also been successfully used for surface re-
construction [ACK01, DG03]. In this paper, we experiment
with the the techniques in [OBS03] and [OBA
∗
03] and the
Power Crust algorithm [ACK01].
In the literature of surface reconstruction, relatively little
attention has been paid to the problem of overfitting. Ohtake
et al. [OBS04] proposed an algorithm which penalizes over-
fitting by adding a regularization term to the usual distance
error metric between the model and a sample. However, they
did not present an automatic method to control the regu-
larization term. Steinke et al. [SSB05] use Support Vector
c
The Eurographics Association 2006.