Automatic Reassembly of Three-Dimensional Jigsaw Puzzles

Anna Grim, Timothy O'Connor, Peter J. Olver, Chehrzad Shakiban, Ryan Slechta, Robert Thompson

Research output: Contribution to journalArticlepeer-review

13 Scopus citations

Abstract

In this paper, we present an effective algorithm for reassembling three-dimensional apictorial jigsaw puzzles obtained by dividing a curved surface into a finite number of interlocking pieces. As such, our algorithm does not make use of any picture or design that may be painted on the surface; nor does it require a priori knowledge of the overall shape of the original surface. A motivating example is the problem of virtually reconstructing a broken ostrich egg shell. In order to develop and test the algorithm, we also devise a method for constructing synthetic three-dimensional puzzles by randomly distributing points on a compact surface with respect to surface area measure, then determining the induced Voronoi tessellation, and finally curving the Voronoi edges by using Bezier curves with selected control points. Our edge-matching algorithm relies on the method of Euclidean signature curves. The edges of the puzzle pieces are divided into bivertex arcs, whose signatures are directly compared. The algorithm has been programmed in Matlab and is able to successfully reassemble a broad range of artificial puzzles, including those subjected to a reasonable amount of noise. Moreover, significant progress has been made on reassembly of the real-world ostrich egg data.

Original languageEnglish (US)
Article number1650009
JournalInternational Journal of Image and Graphics
Volume16
Issue number2
DOIs
StatePublished - Apr 1 2016

Bibliographical note

Funding Information:
We would like to thank Marshall Bern for sending us the broken ostrich egg data that inspired this work. The work of the first, third, and fifth authors was supported in part by NSF grant DMS–1108894. The work of the sixth author was supported in part by NSF grant DMS–0839966.

Publisher Copyright:
© 2016 World Scientific Publishing Company.

Keywords

  • Bezier curve
  • Euclidean signature
  • Jigsaw puzzle
  • Voronoi tessellation
  • bivertex arc
  • curvature
  • torsion

Cite this