Sept. 14, 2005

BACK

Publications in Archaeology on Shape modelling of sherds, pots, etc. :

• Joukowsky, M.S.:
  • A Complete Manual of Field Archaeology, 1980.
• Rice, P.M. :
  • Pottery Analysis: A Sourcebook, 1987.

Publications in Digital Archaeology (or related fields) on Shape reconstruction (re-assembly) & modelling of sherds :

• Brogni, A. et al. :
  • An Interactive System for the Presentation of a Virtual Egyptian Flute in a Real Museum, 1998.
• Cooper, D., Willis, A. et al.:
  • Stochastic 3D Geometric Models for Classification, Deformation, and Estimation, 2004.
    
  • Bayesian Assembly of 3D Axially Symmetric Shapes from Fragments, 2004.
  • Alignment of Multiple Non-overlapping Axially Symmetric 3D Datasets, 2004.
    
  • Bayesian Virtual Pot-Assembly from Fragments, 2002.
  • Assembling Virtual Pots from 3D Measurements of their Fragments, 2001.
• Glassner, A.:
  • Putting the Pieces Together, 2002.
• Kimia, B. et al. :
  • Archaeological Fragment Re-Assembly Using Curve Matching, 2002
  • On Solving 2D and 3D Puzzles Using Curve Matching, 2001.
• Levoy, M. et al. :
  • Digitizing the Forma Urbis Romae, 2000.
• Papaioannou, G. et al. :
  • On the automatic assemblage of arbitrary broken solid artefacts, 2003.
  • Reconstruction of Three-Dimensional Objects through Matching of Their Parts, 2002.
  • Virtual Archaeologist: Assembling the Past , 2001.
  • Automatic Reconstruction of Archaeological Finds - A Graphics Approach, 2000.
• Sablatnig, R. et al. :
  • Automated Segmentation of Archaeological Profiles for Classification, 2002.
  • 3D Modeling of Archaeological Vessels using Shape from Silhouette, 2001.
  • Color Classification of Archaeological Fragments, 2000.
  • Classification of Archaeological Fragments Using a Description Language, 1998.
• Steckner, C.:
  • Form and Fabric, the Real and the Virtual, 1998.
• Stolfi, J. et al.:
  • Information contents of fracture lines, 2000.
  • Automatic reassembly of irregular fragments, 1998.
• Ucoluk, G. et al. :
  • Automatic reconstruction of broken 3-D surface objects, 1999.

BibTeX references.

A. Brogni, E. Bresciani, M. Bergamasco, F. Silvano
Virtual Reality in Archaeology
Proceedings of a Conference held in Barcelona, in March 1998 (part of the CAA'98).
Published by Archaeopress, publishers of British Archaeological Reports (BAR).
BAR International Series 843, Spring 2000,
Edited by J.A.Barcelo, M.Forte & D.H.Sanders, pp. 129-134.

---

Stochastic 3D Geometric Models for Classification, Deformation, and Estimation

Andrew Willis
Ph.D. thesis, Division of Engineering, Brown University, Providence, RI, USA, May 2004.

---

Bayesian Assembly of 3D Axially Symmetric Shapes from Fragments

Andrew Willis and David B. Cooper
CVPR, Vol.1, pp. 82--89, June 2004.

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.

---

Alignment of Multiple Non-overlapping Axially Symmetric 3D Datasets

Andrew Willis and David B. Cooper
ICPR, Vol.4, pp. 96--99, August 2004.

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.

Web link for the paper.

Web link

We present a method for automatically reconstructing 2D archaeological fragments such as the ones recovered during recent expeditions to the Temple at Petra in Jordan. The first part of the problem involves pairwise matching of fragments in order to find fragments that were adjacent in the original object. This is done by using a modified elastic curve-matching technique to identify portions of fragment boundaries which are similar and assign them a similarity value. In the second part of the problem, we attempt to rebuild the object by searching for a globally optimal arrangement of fragments. This is done by rank-ordering the pairwise matches and using a best-first search method. Because of its enormous complexity, we constrain the problem by using techniques that rely on certain key properties of fractured materials such as triple junctions and corners. In addition we introduce a method for enhancing pairwise matching by using color and texture information from the fragment image.

web link

Weblink @ Stanford

Presented here is a fast method that combines curve matching techniques with a surface matching algorithm to estimate the positioning and respective matching error for the joining of three-dimensional fragmented objects. Furthermore, this paper describes how multiple joints are evaluated and how the broken artefacts are clustered and transformed to form potential solutions of the assemblage problem.

Author Keywords: Curve matching; Depth buffer; Range maps; Optimisation methods; Surface matching.

The problem of reassembling an object from its parts or fragments has never been addressed with a unified computational approach, which depends on the pure geometric form of the parts and not application-specific features. We propose a method for the automatic reconstruction of a model based on the geometry of its parts, which may be computer-generated models or range-scanned models. The matching process can benefit from any other external constraint imposed by the specific application.

Reconstruction of archaeological monuments from fragments found at archaeological sites is a tedious task requiring many hours of work from archaeologists and restoration personnel. For large constructions, such as the Parthenon at the Acropolis of Athens, the restoration process takes longer due to the mass of fragments. To test large building blocks against others for potential matching, sometimes archaeologists and site architects must move the cumbersome stones 50 meters or more away from their original locations using cranes. Fragments missing or deteriorated because of erosion or impact damage further hinder archaeological reconstruction.

Until now, computers have provided archaeologists tools for the digitization and archiving of artifacts, visualization and virtual manipulation of 3D or 2D scanned objects, visual representation of historical sites through VR, image processing, and restoration of frescos. However, not much work has been conducted on automatic reconstruction of complete objects from arbitrary fragments.

Existing algorithms focus on the reconstruction of vases and rely either on classification of certain qualitative features of the fragments, as in Sablatnig et al., or on a comparison of the broken surface boundary curves to match and align the vase pieces. The first method assumes that the structure of the final, complete object is known a priori and fragments are extensively labeled and categorized beforehand. The second completely disregards the interior of the broken surface and therefore is restricted to thin-walled objects.

Currently, the Digital Michelangelo team is investigating approaches to assemble the Forma Urbis Romaea marble map of ancient Rome from 1,163 fragments. The team plans to face the problem as a jigsaw puzzle based on broken surface border signatures, while exploiting additional features of the fragments, such as thickness or marble veining.

Generally, the reconstruction of arbitrary objects from their fragments can be regarded as a 3D puzzle, taking into account the following considerations:

• parts (fragments) have arbitrary shapes,
• the shape and number of the final objects are unknown,
• there's an arbitrary number of fractured faces per fragment,
• some fragments may be missing,
• surfaces are probably flawed or weathered,
• no strict assemblage rules exist.

In this article we present a complete method encapsulated in our Virtual Archaeologist system for the full reconstruction of archaeological finds from 3D scanned fragments. Virtual Archaeologist is designed to assist archaeologists in reconstructing monuments or smaller finds by avoiding unnecessary manual experimentation with fragile and often heavy fragments. An automated procedure can't completely replace the archaeology expert, but provides a useful estimation of valid fragment combinations, and accurately measures fragment matches.

In Virtual Archaeologist, we regard the reconstruction problem from a general, geometric point of view, relying on the broken surface morphology to determine correct matches between fragments. This approach doesn't require specific object information, but is versatile enough to exploit any other data available. A brief preliminary sketch of the underlying algorithms used in Virtual Archaeologist appears elsewhere.

Our program (i) detects candidate fractured faces, (ii) matches fragments one by one, and (iii) assembles (clusters) fragments into complete or partially complete entities. The only input data our system requires are the polygonal meshes of the original fragments. We acquired meshes with a 3D scanner or digitizer. Modeling or curve interpolation may be required in cases where only blueprints of cut sections of the fragments are available as part of the standard archiving procedure. An optional set of constraints such as material or structural fragment attributes significantly improves the overall accuracy and performance. Our system doesn't require human intervention, but users can clarify the reconstruction by interactively fine-tuning the clustering and poses of the fragments.

Weblink @ TUW

Web link: Reconstruction of fragmented objects

Reassembling unknown broken objects from a large collection of fragments is a common problem in archaeology and other fields. Computer tools have recently been developed, by the authors and by others, which try to help by identifying pairs of fragments with matching outline shapes. These tools have been succesfully tested on small collections of fragments; here we address the question of whether they can be expected to work also for practical instances of the problem ($10^3$ to $10^5$ fragments). To that end, we describe here a method to measure the average amount of information contained in the shape of a fracture line of given length. This parameter tells us how many false matches we can expect to find for that fracture among a given set of fragments. In particular, the numbers we obtained for ceramic fragments indicate that fragment outline comparison should give useful results even for large instances.

This report addresses the following problem: given one or more unknown objects that have been broken or torn into a large number of irregular fragments, find the pairs of fragments that were adjacent in the original objects.

Our approach is based on information extracted from the fragment outlines, which is used to compute the mismatch between pairs of pieces of contour. In order to asymptotically reduce the cost of matching, we use a multiple scales technique: after filtering and resampling the fragment outlines at several different scales of detail, we look for initial matchings at the coarsest possible scale. We then repeatedly select the most promising pairs, and re-match them at the next finer scale of detail. In the end, we are left with a small set of fragment pairs that are most likely to be adjacent in the original object.

The problem of reconstruction of broken surface objects embedded in 3-D space is handled. A coordinate independent representation for the crack curves is developed. A new robust matching algorithm is proposed which serves for finding matching pieces even when some brittle pieces are missing. A prototype system having an X-based GUI has been developed. This system generates artifical wire-frame data of broken pieces (with some noise) for a pot-shaped 3-D object and then recombines it using the proposed algorithms.

Keywords: Broken object reconstruction; 3-D surface object; Surface matching; Curvature; Torsion

BACK

Page created & maintained by Frederic Leymarie, 2000-5.
Comments, suggestions, etc., mail to: ffl at gold dot ac dot uk