Abstract
The puzzle-assembly problem has many application areas such as restoration and reconstruction of archeological findings, repairing of broken objects, solving jigsaw type puzzles, molecular docking problem, etc. The puzzle pieces usually include not only geometrical shape information but also visual information such as texture, color, and continuity of lines. This paper presents a new approach to the puzzle-assembly problem that is based on using textural features and geometrical constraints. The texture of a band outside the border of pieces is predicted by inpainting and texture synthesis methods. Feature values are derived from these original and predicted images of pieces. An affinity measure of corresponding pieces is defined and alignment of the puzzle pieces is formulated as an optimization problem where the optimum assembly of the pieces is achieved by maximizing the total affinity measure. A Fast Fourier Transform based image registration technique is used to speed up the alignment of the pieces. Experimental results are presented on real and artificial data sets.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Ballester A, Bertalmio M, Caselles V et al (2001a) Filling in by joint interpolation of vector fields and gray levels. IEEE Trans Image Process 10(1). doi:10.1.1.32.8659
Ballester A, Bertalmio M, Caselles V et al (2001b) A variational model for filling-in gray level and color images. In: Proc of ICCV, p 10
Bertalmio M, Bertozzi AL, Sapiro G (2001) Navier Stokes fluid dynamics and image and video inpainting. In: Proc of conf computer vision pattern recognition, Hawai, December 2001, pp 355–365
Chung MG, Fleck MM, Forsyth DD (1998) Jigsaw puzzle solver using shape and color. In: Proc of ICSP
Criminisi A, Perez P, Toyama K (2003) Object removal by exemplar-based inpainting. In: CVPR, pp 721–728
Freeman H, Gardner L (1964) A pictorial Jigsaw puzzles: The computer solution of a problem in pattern recognition. IEEE Trans Electron Comput 13:118–127
Fornasier M, Toniolo D (2005) Fast, robust and efficient 2D pattern recognition for re-assembling fragmented images. Pattern Recognit 38:2074–2087
Goldenberg D, Malon C, Bern M (2002) A global approach to automatic solution of jigsaw puzzles. In: Proc of conf on computational geometry, pp 82–87
Kong W, Kimia BB (2001) On solving 2D and 3D puzzles using curve matching. In: Proc of CVPR, Hawaii, USA
Kosiba AD, Devaux PM, Balasubramanian S, Gandhi TL, Kasturi R (2001) An automatic jigsaw puzzle solver. In: Proc int conf pattern recognition
Krüger S, Calway A (1998) Image registration using multiresolution frequency domain correlation. In: Proc of British machine vision conf
Levin A, Zomet A, Weiss Y (2003) Learning how to inpaint from global image statistics. In: Proc of ninth international conference on computer vision, vol 2, p 305
Levoy M (2000) The digital Michelangelo project: 3D scanning of large statues. Computer graphics. In: Proc SIGGRAPH, New York, pp 131–144
Makadia A, Daniilidis K (2003) Direct 3D rotation estimation from spherical images via a generalized shift theorem. In: Proc of CVPR, vol 2, June 2003, pp 217–224
Oliveira MM, Bowen B, McKenna R, Chang YS (2001) Fast digital image inpainting. In: Proc of visualization, imaging, and image processing, Marbella, Spain, September 2001, pp 261–266
Papaioannou G, Karabassi EA, Theoharis T (2001) Virtual archaeologist: assembling the past. IEEE Comput Graph Appl 21(2):53–59
Radack GM, Badler NI (1982) Jigsaw puzzle matching using a boundary-centered polar encoding. Comput Graph Image Process 19:1–17
Sağıroglu MŞ (2006) Computer aided puzzle assembly based on shape and texture information. PhD Thesis
Sağıroglu M, Ercil A (2005) A texture based approach to reconstruction of archaeological finds. In: Virtual reality, archaeology, and cultural heritage (VAST)
Sağıroglu MŞ, Ercil A (2006) A texture based matching approach for automated assembly of puzzles. In: Proceedings of ICPR2006
Sapiro G (2002) Image inpainting. SIAM News 35(4)
Stol, Leitao H (2002) A multiscale method for the reassembly of two-dimensional fragmented objects. IEEE Trans Pattern Anal Mach Intell 24:1239–1251
Üçoluk G, Toroslu IH (1999) Automatic reconstruction of broken 3-D surface objects. Comput Graph 23:573–582
Willis A, Cooper D (2002) Bayesian pot-assembly from fragments as problems in perceptualgrouping and geometric-learning. In: ICPR, vol 3, pp 297–302
Willis A, Cooper D (2003) Accurately estimating sherd 3D surface geometry with application to pot reconstruction. In: CVPR Workshop: ACVA, June 2003
Wolberg G, Zokai S (2000) Robust image registration using log-polar transform. In: Proc of IEEE ICIP
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Sağıroğlu, M.Ş., Erçil, A. Optimization for automated assembly of puzzles. TOP 18, 321–338 (2010). https://doi.org/10.1007/s11750-010-0156-6
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11750-010-0156-6