A multiscale method for the reassembly of two-dimensional fragmented objects
IEEE Transactions on Pattern Analysis and Machine IntelligencePublished 1 September 2002
Helena Cristina da Gama Leitão, Jorge Stolfi
Citations188
SJR quartileQ1
SJR score3.91
SNIP5.99
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
An efficient procedure for reassembling unknown two-dimensional objects that have been broken or torn into a large number of irregular fragments, a problem that often arises in archaeology, art restoration, forensics, and other disciplines is described.
Abstract
We describe an efficient procedure for reassembling unknown two-dimensional objects that have been broken or torn into a large number of irregular fragments, a problem that often arises in archaeology, art restoration, forensics, and other disciplines. The procedure compares the curvature-encoded fragment outlines, at progressively increasing scales of resolution, using an incremental dynamic programming sequence-matching algorithm. The total cost gets reduced by a factor proportional to the mean number of samples per segment, which makes the method viable for problems of practical size (thousands of fragments). The performance of our method is illustrated with an artificial but realistic example.
Keywords
Computer ScienceEarth and Planetary Sciences
Journal of the ACMThe String-to-String Correction Problem
3,063 Citations1974Robert A. Wagner, Michael J. Fischer
An algorithm is presented which solves the string-to-string correction problem in time proportional to the product of the lengths of the two strings.
Elsevier eBooksSCALE-SPACE FILTERING
2,353 Citations1987Andrew Witkin
Scale-space filtering is a method that describes signals qualitatively, managing the ambiguity of scale in an organized and natural way.
Zippered polygon meshes from range images
1,317 Citations1994Greg Turk, Marc Levoy
A method for combining a collection of range images into a single polygonal mesh that completely describes an object to the extent that it is visible from the outside is presented.
IEEE Transactions on Pattern Analysis and Machine IntelligenceA theory of multiscale, curvature-based shape representation for planar curves
932 Citations1992Farzin Mokhtarian, Alan K. Mackworth
A shape representation technique suitable for tasks that call for recognition of a noisy curve of arbitrary shape at an arbitrary scale or orientation is presented and several evolution and arc length evolution properties of planar curves are discussed.
Introduction to Computational Molecular Biology
690 Citations1997João Carlos Setúbal, João Meidânis
This chapter discusses the construction of phylogenetic trees, a type of tree-building based on DNA assembly, and its applications in medicine, dentistry, and neuroscience.
IEEE Transactions on Pattern Analysis and Machine IntelligenceOn curve matching
223 Citations1990Haim J. Wolfson
Two algorithms to find the longest common subcurve of two 2D curves are presented, based on conversion of the curves into shape signature strings and application of string matching techniques to find long matching substrings, followed by direct curve matching of the corresponding candidate subcurves to finding the longest matching subCurve.
IEEE Transactions on Pattern Analysis and Machine IntelligenceSilhouette-based isolated object recognition through curvature scale space
213 Citations1995Farzin Mokhtarian
A complete, fast and practical isolated object recognition system has been developed which is very robust with respect to scale, position and orientation changes of the objects as well as noise and local deformations of shape (due to perspective projection, segmentation errors and non-rigid material used in some objects).
The International Journal of Robotics ResearchTwo-Dimensional, Model-Based, Boundary Matching Using Footprints
168 Citations1986Alan D. Kalvin, Edith Schonberg +2 more
A technique for geometrically hash ing two-dimensional model objects selected from large data bases of model objects without significant performance degradation when the database is enlarged is described.
Pattern RecognitionApplications of approximate string matching to 2D shape recognition
141 Citations1993Horst Bunke, Ulrich Bühler
A new method for the recognition of arbitrary two-dimensional shapes based on string edit distance computation is described, which is invariant under translation, rotation, scaling and partial occlusion.
Model-Based Object Recognition - A Survey of Recent Research
126 Citations1994Arthur R. Pope
There is still much room for improvement in the scope, robustness, and efficiency of object recognition methods, and what are the ways improvements will be achieved are identified.
Methods in enzymology on CD-ROM/Methods in enzymology[27] Dynamic programming algorithms for biological sequence comparison
102 Citations1992William R. Pearson, Webb Miller
Methods for calculating similarity scores and distances that use gap penalties of the form g = rk are discussed, which are much slower than the heuristic approach used by the RDF2 program and should take less than 1 hr to complete.
IEEE Computer Graphics and ApplicationsVirtual Archaeologist: assembling the past
96 Citations2001Γεώργιος Παπαϊωάννου, Evaggelia-Aggeliki Karabassi +1 more
This work presents a complete method, encapsulated in the Virtual Archaeologist system, for the full reconstruction of archaeological finds from 3D scanned fragments, relying on the broken surface morphology to determine correct matches between fragments.
Computers & GraphicsAutomatic reconstruction of broken 3-D surface objects
93 Citations1999Göktürk Üçoluk, İsmail Hakkı Toroslu
A new robust matching algorithm is proposed which serves for finding matching pieces even when some brittle pieces are missing and a prototype system having an X-based GUI has been developed.
IEEE Transactions on Pattern Analysis and Machine IntelligencePartial surface and volume matching in three dimensions
88 Citations1997Gill Barequet, Micha Sharir
IEEE Transactions on Robotics and AutomationSolving jigsaw puzzles by a robot
65 Citations1989B.G. Burdea, Haim J. Wolfson
An integrated vision-manipulation algorithm for assembly of apictorial jigsaw puzzles using vision, combinatorial optimization, and fine assembly techniques and the problem of assembling pieces with unpredictable shape is discussed.
IEEE Transactions on Systems Man and CyberneticsIsthmus critical points for solving jigsaw puzzles in computer vision
51 Citations1991Roger Webster, Paul S. LaFollette +1 more
A computer vision system that can assemble canonical jigsaw puzzles is described, which derives a new set of critical points that define a feature that can be used in matching partial boundaries (or contours) of planar regions.
Joint detection for potsherds of broken earthenware
31 Citations2003K. Hori, Michita Imai +1 more
A new strategy for detecting the joint among two potsherds is proposed, in which each contour is segmented for partial verification without making any assumption about the shape of a potsherd, unlike previous jigsaw puzzle assembling methods.
IEEE Transactions on Pattern Analysis and Machine IntelligenceOptimal local weighted averaging methods in contour smoothing
28 Citations1997R. Legault, C.Y. Suen
A new and simple digitization noise model is proposed to derive the best set of weights for different window sizes, for each computational task, and estimates of the fraction of the noise actually removed by these optimum weights are obtained.
Lecture notes in computer scienceJigsaw puzzle solving using approximate string matching and best-first search
22 Citations1993Horst Bunke, G. Kaufmann
A new method for jigsaw puzzle solving that takes real images of puzzle pieces as input data and resolves ambiguities that may result from local shape matching using a best-first tree search procedure with backtracking.
Pattern RecognitionExtracting natural scales using fourier descriptors
22 Citations1993Paul L. Rosin, Svetha Venkatesh
These natural scales are determined by examining the Fourier descriptors of the contour and searching for significant bands that correspond to bandwidths required to extract features at qualitatively significant resolution.
Computer Vision Graphics and Image ProcessingLocal matching of surfaces using a boundary-centered radial decomposition
14 Citations1989Gerald M. Radack, Norman I. Badler
A heuristic solution is presented that is intended for use on complex surfaces that has been implemented using surfaces represented by polygonal networks as input and has been successfully applied to synthetically produced surfaces.
Reconstrução automatica de objetos fragmentados
3 Citations1996Helena Cristina da Gama Leitão
A new method for recognizing and locating objects by searching longest paths
2 Citations2003Fatia Boussofiane, Gilles Bertrand
Presents a new method for recognizing and locating an object in an image by generating paths in a table where the columns represent the model segments and the rows the scene segments.