1	Archaeological Fragment Reassembly Using Curve-Matching Jonah McBride and Benjamin Kimia June 17, 2003
2	Motivation: Why Fragment Reassembly? Archaeology Pots, Vessels Walls, Murals Statues, Buildings Other Applications Forensics, Ballistics, Failure Analysis Reconstructive Surgery Art Restoration
3	Our Research 2D fragments Cast as a problem in “Puzzle-Solving” Applications to broken murals, tablets or other flat artifacts Takes advantage of specific properties of archaeological materials
4	Related Work STITCH Project in the SHAPE Lab at LEMS http://www.lems.brown.edu/vision/extra/SHAPE Forma Urbis Romae, Stanford University Reconstructing a giant stone map of Rome (60 x 43 feet) http://formaurbis.stanford.edu Leitão & Stolfi, São Paulo, Brazil Reconstructing 2D ceramic tiles http://www.dcc.unicamp.br/~stolfi/EXPORT/projects/fragments/Welcome.html
5	Problem Formulation In reconstructing an object from fragments, there are two stages: Searching for adjacent fragments by measuring local pairwise affinity (similarity) of fragments. Using local information to build a global arrangement fragments. Challenges: Accuracy: How do we measure affinity? Complexity: Can we handle hundreds of fragments? Thousands? Ambiguity: How do we separate correct matches from incorrect ones?
6	Talk Overview Review fracture properties in natural materials. Present technique for measuring pairwise affinity using a multi-scale approach. Describe a robust search for a global arrangment. Introduce the use of color information into pairwise affinity measurement.
7	Ceramic Fracture Archeological puzzles differ from jigsaw puzzles! Jigsaw Puzzles: Have macroscopic interlocking parts. Have well defined borders. Matching portion of boundary easy to segments using corners Archaeological Puzzles Macroscopic fractures tend to be much straighter. Have microscopic interlocking pairs. Border is unknown if it exists at all. Harder to partition boundary based on corners.
8	Primacy of Junctions & Corners Conjecture: Archeological fragments generically come together at most three at a time. Junctions can significantly constrain search. Junctions Mostly triple junctions of type T and Y Key assumption in the search for a global solution. Corners : 2 corners arise from every T junction and 3 arise from every Y junction. Easily detectable features.
9	Matching Types Type 1: Common boundary begins and ends at a pair of corners. Type 2: Pair of corners at one end only. Type 3: Pair of corners at neither end.
10	Partial Curve Matching Only a portion of the boundaries of adjacent fragments will be similar.
11	Elastic Open Curve-Matching Sebastian et. al. Symmetric alignment using an alignment curve.
12	Elastic Deformation Energy Stretching Energy (η) = Difference in Arclength Bending Energy (γ) = Difference in Curvature
13	Specification of Sub-Contours Brute Force Method: Match all possible sub-contours. Problems: For contours with n sample points, this has complexity O(n⁴). For a given set of sub-contours, the total elastic deformation energy always increases with the length of the match. This favors short sub-contours. Novel Normalized Cost Method Uses a modified energy function to favor both length and similarity in a match. Contributes positive energy if curves are locally similar and negative energy if they are locally dissimilar. Reduces complexity to O(n²) by automatically determining the end points of the sub-contours once start-points have been specified.
14	Normalized Energy
15	Optimal Sub-Contour Localization Algorithm: Initialized at a pair of start points Continues until total cost is no longer decreasing.
16	A Multi-Scale Approach Use multiscale to reduce computational cost Fragments Represented at 4 levels Level I: Corners Only (~5 points) Level II: Coarse Scale (~100 points) Level III: Fine Scale (~400 points) Level IV: Finest Scale (~1000 points)
17	Multi-Scale Cont. Three steps in the multi-scale process Partial curve-matching at level I/II Fine scale curve matching at level III Iterative Euclidean refinement at level IV Only the best matches from coarse scale matching are kept to be matched at the other two levels.
18	Global Search Best-First Method: Too simple
19	Global Confidence Pairwise measures too brittle, need more of the global context. Reward the occurrence of: Additional adjacency Closed Junctions Triple Junctions
20	Best-Global-First
21
22
23
24
25
26
27
28
29
30	Multiple Hypothesis Testing Add stability by taking the best k matches. Given k possible configurations, iterate on each one and take the top L from the best global list. From the resulting kL configurations, prune down to k again. Below, k=L=4:
31
32
33
34
35
36
37
38	Results…
39	Tile B – 7 Pieces
40	Tile B – 7 Pieces
41	Tile E – 13 Pieces
42	Tile E – 13 Pieces
43	Tile C – 15 Pieces
44	Tile C – 15 Pieces
45	Brazilian Data – 22 Pieces From Leitão & Stolfi
46	Brazilian Data – 22 Pieces
47	Enhancing Shape-Based Matching with Color Information Goal is to detect continuation of color and texture over a fracture. Use luminance because it is more robust. Use image gradient to detect edges.
48	Use of a Mask Smoothing is needed both to reduce noise in the luminance image and also for edge detection Data from the background is not meaningful, so we exclude with a mask taken from image segmentation.
49	Contour Sampling Data is unreliable near the edge of the fragment. Erode contour and sample just inside the boundary. From contour C(s), sample the quantities L(s) and G_xy(s). L is luminance and G_xy is the gradient vector.
50	Gradient Continuation Rotate gradient vectors by 90^o in order to follow edge. We care most about edges that cross the fracture and are thus closer to normal with the boundary tangent. Scale gradient by magnitude of cross product with tangent vector. Gradient vectors sampled along eroded contour (unscaled) shown below.
51	Color Based Alignment We now create a new alignment using the same framework as elastic curve matching, but replace bending and stretching with change in luminance and edge continuation. Use simple difference for change in luminance. For edge continuation, use Euler Completion Curve [Kimia, et. al.]. Given two point-tangent pairs, returns an energy related to total change in curvature. Edges that are co-circular will result in zero energy from the completion curve. Also include difference in gradient magnitude. Only include completion curve energy if both edges are strong, otherwise not meaningful.
52	Results From a small database of fragments from Petra, all pairs were matched. The following three matches which had already been found manually, returned the lowest color alignment energy. Need more fragments to be digitized in order to build the mural.