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.


    Access

    Check access

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    On solving 2D and 3D puzzles using curve matching


    Contributors:
    Weixin Kong, (author) / Kimia, B.B. (author)


    Publication date :

    2001-01-01


    Size :

    940477 byte





    Type of media :

    Conference paper


    Type of material :

    Electronic Resource


    Language :

    English



    On Solving 2D and 3D Puzzles Using Curve Matching

    Kong, W. / Kimia, B. B. / IEEE | British Library Conference Proceedings | 2001


    Enumeration Strategies in Constraint Programming for Solving Puzzles

    Crawford, Broderick / Aranda, Mary / Castro, Carlos et al. | IEEE | 2007


    Transient Puzzles

    Kouveliotou, Chryssa / Granot, J. / Racusin, J. L. et al. | NTRS | 2014


    Archaeological Fragment Reconstruction Using Curve-Matching

    McBride, Jonah C. / Kimia, Benjamin B. | IEEE | 2003


    Sequential Monte Carlo for Maximum Weight Subgraphs with Application to Solving Image Jigsaw Puzzles

    Adluru, N. / Yang, X. / Latecki, L. J. | British Library Online Contents | 2015