Publications
Bayesian Assembly of 3D
Axially Symmetric Shapes from Fragments
Andrew Willis and
David B. Cooper
Abstract
We
present a complete system for the purpose of automatically
assembling 3D pots given 3D measurements of their fragments commonly
called sherds. A Bayesian approach is formulated which, at present,
models the data given a set of sherd geometric parameters. Dense sherd
measurement data is obtained by scanning the outside surface of each
sherd with a laser scanner. Mathematical models, specified by a set of
geometric parameters, represent the sherd outer surface and break
curves on the outer surface (where two sherds have broken apart).
Optimal alignment of assemblies of sherds, called configurations, is
implemented as maximum likelihood estimation (MLE) of the surface and
break curve parameters given the measured sherd data for all sherds in
a configuration. The assembly process starts with a fast clustering
scheme which approximates the MLE solution for all sherd pairs, i.e.,
configurations of size 2, using a subspace of the geometric parameters,
i.e., the sherd break curves. More accurate MLE values based on all
parameters, i.e., sherd alignments, are computed when sherd pairs are
merged with other sherd configurations. Merges take place in order of constant probability starting at the
most probable configuration.
This method is robust to missing sherds or groups of sherds which
contain sherds from more than one pot. The system represents at least
three significant advances over previous 3D puzzle solving approaches :
(1) a Bayesian framework which allows for easily combining diverse
types of information extracted from each sherd, (2) a search which
reduces comparisons on false positives, i.e., incorrect matches of high
probability, and (3) a robust computationally reasonable method for
aligning break curves and sherd outer surfaces simultaneously. In
addition, a number of insights are given which have not previously been
discussed and significantly reduce computation. Methods proposed for
(1),(2), and (3) represent important contributions to the field of
puzzle assembly, 3D geometry learning, and dataset alignment and are
critical to making 3D puzzle solutions tractable to compute. Results
are presented which include assembling a 13 sherd pot where only an
incomplete set of 10 sherds is available.
BiBTeX Citation Entry
@InProceedings{CVPR:3DPuzzleSolving:Willis:2004,
author = {Willis, A.
and Cooper, D.},
title =
{Bayesian Assembly of 3D Axially Symmetric Shapes from Fragments},
booktitle = {{CVPR}},
volume = {I},
pages =
{pp. 82--89},
month =
{June},
year =
{2004},
}
PDF file of the
article (~410k)
Surface Sculpting with
Stochastic Deformable 3D Surfaces
Andrew Willis , Jasper Speicher,
and
David B. Cooper
Abstract
This
paper introduces a new stochastic surface model for deformable 3D
surfaces and demonstrates its utility for the purpose of 3D sculpting.
This is the problem of simple-to-use, intuitively interactive 3D
free-form model building. A 3D surface is a sample of a Markov Random
Field (MRF) defined on the vertices of a 3D mesh where MRF sites
coincide with mesh vertices and the MRF cliques consist of subsets of
sites. Each site has 3D coordinates (x,y,z) as random variables and is
a
member of one or more clique potentials which are functions of the
vertices in a clique and describe stochastic dependencies among sites.
Data,
which is used to deform the surface, can consist of, but is not limited
to, an unorganized set of 3D points and is modeled by a conditional
probability distribution given the 3D surface. A deformed surface is a
MAP (Maximum A posteriori Probability) estimate of the joint
distribution of the MRF surface model and the data. The generality and
simplicity of the MRF model provides the ability to incorporate
unlimited local and global deformation properties. Included in our
development is the introduction of new data models, new anisotropic
clique potentials, and cliques which involve sites that are spatially
far apart.
BiBTeX Citation Entry
@InProceedings{ICPR:3DMRFSculpting:Willis:2004,
author = {Willis, A.
and Speicher, J. and Cooper, D.},
title =
{Surface Sculpting with Stochastic Deformable 3D Surfaces},
booktitle = {{ICPR}},
volume = {II},
pages =
{pp. 249--252},
month =
{August},
year =
{2004},
}
PDF file of the
article
(~400k)
Alignment of Multiple Non-overlapping Axially Symmetric 3D
Datasets
Andrew Willis and
David B. Cooper
Abstract
Uknown to
us, an axially-symmetric surface is broken into disjoint
pieces along a set of break-curves, i.e., the curves along which the
surface locally breaks into two pieces. A subset of the pieces are
available and for each of them we obtain noisy measurements of its
surface and break-curves. Using the piece measurements and knowledge of
which pieces share a common break-curve, we propose a method for
automatically estimating the unknown axially-symmetric global surface.
Surface and break-curve estimation is then an alignment problem where
we must estimate the unknown axially-symmetric surface and break-curves
while simultaneously estimating the Euclidean transformation that
positions each measured piece with respect to the a-priori unknown
surface. A stochastic approach is taken which computes the Maximum
Likelihood Estimate (MLE) of the unknown parameters given the measured
data where the unknown parameters are : (1) the parameters of the
axially-symmetric surface, which are the coefficients of an
axially-symmetric implicit polynomial surface; (2) the true
break-curve, modeled as a sequence of 3D points; and (3) the Euclidean
transformation parameters for each of the pieces. This new approach is
robust, fast, and accurate. It handles chipped, eroded free-form pieces
and noisy data. Experimental results are presented which solves an
application of interest, specifically the reconstruction of
archaeological pots from subsets of their surface pieces.
BiBTeX Citation Entry
@InProceedings{ICPR:AxialAlignment:Willis:2004,
author = {Willis, A.
and Cooper, D.},
title =
{Alignment of Multiple Non-overlapping Axially Symmetric 3D Datasets},
booktitle = {{ICPR}},
volume = {IV},
pages =
{pp. 96--99},
month =
{August},
year =
{2004},
}
PDF file of the article
(~380k)
Accurately Estimating Sherd 3D Surface Geometry with
Application to Pot Reconstruction
Andrew Willis , Xavier Orriols ,
and
David B. Cooper
CVPR 2003 Workshop
Madison, Wisconsin June 16--20, 2003
Abstract
This paper deals with the problem of precise automatic estimation of
the surface geometry of pot sherds uncovered at archaeological
excavation sites using dense 3D laser-scan data. Critical to ceramic
fragment analysis is the ability to geometrically classify excavated
sherds, and, if possible, reconstruct the original pots using the sherd
fragments. To do this, archaelogists must estimate the pot geometry in
terms of an axis and associated profile curve from the discovered
fragments. In this paper, we discuss an automatic method for accurately
estimating an axis/profile curve pair for each archeological sherd
(even
when they are small) based on axially symmetric implicit polynomial
surface models. Our method estimates the axis/profile curve for a sherd
by finding the axially symmetric algebraic surface which best fits the
measured set of dense 3D points and associated normals. We note that
this method will work on 3D point data alone and does not require any
local surface computations such as differentiation. Axis/profile curve
estimates are accompanied by a detailed statistical error analysis.
Estimation and error analysis are illustrated with application to a
number of sherds. These fragments, excavated from Petra, Jordan, are
chosen as exemplars of the families of geometrically diverse sherds
commonly found on an archeological excavation site. We then briefly
discuss how the estimation results may be integrated into a larger pot
reconstruction program.
@InProceedings{CVPR:AxisStatistics:Willis:2002,
author = {Willis, A.
and Cooper, D. and others},
title =
"{Accurately Estimating Sherd {3D} Surface Geometry with Application to
Pot Reconstruction}",
booktitle = {{CVPR Workshop : ACVA}},
month =
{June},
year =
{2003},
}
PDF
file of the
article (~540k)
Bayesian Pot-Assembly from
Fragments as Problems in Perceptual-Grouping and Geometric-Learning
David B. Cooper, Andrew Willis,
Stuart
Andrews, Jill Baker, Yan Cao, Dongjin Han, Kongbin Kang, Weixin Kong,
Frederic F. Leymarie, Xavier Orriols, Senem Velipasalar, Eileen L.
Vote,
Martha S. Joukowsky, Benjamin B. Kimia, David H. Laidlaw, David Mumford
ICPR 2002
International Conference on Pattern
Recognition -
Quebec City, Canada - August 11-14, 2002
Abstract
A
heretofore unsolved problem of great archaeological importance
is
the automatic assembly of pots made on a wheel from the hundreds (or
thousands) of sherds found at an excavation site. An approach is
presented to the automatic estimation of mathematical models of such
pots from 3D measurements of sherds. A Bayesian approach is formulated
beginning with a description of the complete set of geometric
parameters
that determine the distribution of the sherd measurement data. Matching
of fragments and aligning them geometrically into configurations is
based on matching break-curves (curves on a pot surface separating
fragments), estimated axis and profile curve pairs for individual
fragments and configurations of fragments, and a number of features of
groups of break-curves. Pot assembly is a bottom-up maximum likelihood
performance-based search. Experiments are illustrated on pots which
were broken for the purpose, and on sherds from an archaeological dig
located in Petra, Jordan. The performance measure can also be an
aposteriori probability, and many other types of information can be
included, e.g., pot wall thickness, surface color, patterns on the
surface, etc. This can also be viewed as the problem of learning a
geometric object from an unorganized set of free-form fragments of the
object and of clutter, or as a problem of perceptual grouping.
BiBTeX Citation Entry
@InProceedings{ICPR:3DPuzzle:Willis:2002,
author = {Willis, A.
and Cooper, D. and others},
title =
{Bayesian Pot-Assembly from Fragments as Problems in
Perceptual-Grouping
and Geometric-Learning},
booktitle = {{ICPR}},
volume = {III},
pages =
{pp. 297--302},
month =
{August},
year =
{2002},
}
PDF
file of the article (~400k)
Assembling
Virtual Pots from 3D Measurements of their Fragments
David Cooper, Andrew Willis ,
Stuart Andrews,
Jill Baker, Yan Cao, Dongjin Han, Kongbin Kang, Weixin Kong, Frederic
F.
Leymarie, Xavier Orriols, Senem Velipasalar, Eileen Vote, Martha
S. Juokowsky, Benjamin B. Kimia, David H. Laidlaw, David Mumford
VAST Conference 2001
Conference on Virtual Archaeology and
Cultural Heritage
- Athens, Greece - November 28-30, 2001
Abstract
A heretofore unsolved problem of great
archaeological
importance is the automatic assembly of pots made on a wheel from the
hundreds (or thousands) of sherds found at an excavation site. An
approach is presented to the automatic estimation of mathematical
models of such pots from 3D measurements of sherds. The overall
approach
is formulated and described and some detail is provided on the elements
of the procedure. The end result is a representation suitable for
comparisons, geometric feature extraction, visualization and digital
archiving. Matching of fragments and aligning them geometrically is
based on matching break-curves (curves on a pot surface separating
fragments), estimated axes and profile curves for individual fragments
and groups of matched fragments, and a number of features of groups of
break-curves. Pot assembly is a bottom-up maximum likelihood
performance-based search. In our case, associated with subassemblies of
fragments is a loglikelihood which is a sum of energy functions.
Experiments are illustrated on pots which were broken for the purpose,
and on sherds from an archaeological dig located in Petra, Jordan.
BiBTeX Citation Entry
@InProceedings{VAST:3DPuzzle:Willis:2001,
author = {Willis, A.
and Cooper, D. and others},
title =
{Assembling Virtual Pots from {3D} Measurements of their Fragments},
booktitle = {{VAST} International Symposium on
Virtual Reality
Archaeology and Cultural Heritage},
pages =
{pp. 241--253},
year =
{2001},
}
PDF
file of the article (~550Kb)
Extracting Axially
Symmetric Geometry From Limited 3D Range Data
Andrew Willis , Xavier Orriols , Senem
Velipasalar, David B. Cooper, Xavier Binefa
SHAPE Lab Technical Report 2000-01
Abstract
This paper describes a new, novel low
computational-cost approach for recovering geometric structure and pose
information of a 3D surface rotationally symmetric about an axis given
an unorganized set of 3D range data which covers only a small patch of
the surface. Self occluding contours are not seen here. All the
parameters necessary to completely define the corresponding surface are
estimated. The estimated parameters of the data patch consist of a line
describing the axis and a set of parameters which describe the
profile curve with respect to the axis. Global algebraic surfaces and
local splines consisting of frustrums of cones are used as models for
the surface estimation.
BiBTeX Citation Entry
@TECHREPORT{TR:AxisEstimate:Willis:2001,
author = {Willis, A.
and Orriols, X. and Velipasalar, S. and Cooper, D. and Binefa, X.},
title =
{Extracting Axially Symmetric 3D Geometry from Limited 3D Range Data},
institution = {{SHAPE} Lab, Brown University,
Providence, RI},
type =
{{SHAPE-TR-2001-01}},
year =
{2001},
note =
{http://www.lems.brown.edu/vision/publications/index.html}
}
PDF file of the article (~540Kb)