We approach the problem of 2D and 3D puzzle solving by matching the geometric features of puzzle pieces three at a time. First, we define an affinity measure for a pair of pieces in two stages, one based on a coarse-scale representation of curves and one based on a fine-scale elastic curve matching method. This re-examination of the top coarse-scale matches at the fine scale results in an optimal relative pose as well as a matching cost which is used as the affinity measure for a pair of pieces. Pairings with overlapping boundaries are impossible and are removed from further consideration, resulting in a set of top valid candidate pairs. Second, triples arising from generic junctions are formed from this rank-ordered list of pairs. The puzzle is solved by a recursive grouping of triples using a best-first search strategy, with backtracking in the case of overlapping pieces. We also generalize aspects of this approach to matching of 3D pieces. Specifically, ridges of 3D fragments scanned using a laser range finder are detected using a dynamic programming method. A pair of ridges are matched using a generalization of the 2D curve matching approach to space curves by using an energy solution involving curvature and torsion, which are computed using a novel robust numerical method. The reconstruction of map fragments and broken tiles using this method is illustrated.
On solving 2D and 3D puzzles using curve matching
01.01.2001
940477 byte
Aufsatz (Konferenz)
Elektronische Ressource
Englisch
On Solving 2D and 3D Puzzles Using Curve Matching
British Library Conference Proceedings | 2001
|NTRS | 2014
|Sequential Monte Carlo for Maximum Weight Subgraphs with Application to Solving Image Jigsaw Puzzles
British Library Online Contents | 2015
|