Solving Jigsaw Puzzles using Paths and Cycles
In Proceedings British Machine Vision Conference 2014
http://dx.doi.org/10.5244/C.28.117
Abstract
There has been a growing interest in image jigsaw puzzles with square shaped pieces recently. A solver takes as input square shaped patches of the same size belonging to an image and attempts to reconstruct the image. The key components of a jigsaw solver are a compatibility metric which assigns a numerical value to a given pair of pieces which represents the likelihood of them being neighbors in the correct assembly, and an assembly algorithm. Several compatibility metrics and assembly algorithms have been proposed previously. A shortcoming observed in existing work is that the information provided by compatibility metrics is not exploited to a great extent and as a result assembly degrades as the piece size gets smaller. Our work attempts to make inferences from the information provided by a metric to improve its neighbor identification accuracy. We introduce the concept of paths and cycles in jigsaw puzzles and show that they provide a means of identifying correct and incorrect matches. We propose refinement techniques based on this idea which improve the neighbor identification accuracy of a given compatibility metric. We also propose a means of combining the strengths of multiple compatibility metrics which may use distinct image features to score piece pairs. Whereas recently proposed greedy solvers use the cost values produced by the metric directly to greedily pick piece pairs for assembly, we define a new measure of piece pair compatibility and use it to guide a greedy solver. The proposed solver beats state of the art performance, achieving a mean improvement of more than 15% in absolute placement accuracy for 14 piece size puzzles.
Session
Poster Session
Files
Extended Abstract (PDF, 1 page, 1.5M)Paper (PDF, 11 pages, 6.1M)
Supplemental Materials (ZIP, 8.0M)
Bibtex File
Citation
Lajanugen Logeswaran. Solving Jigsaw Puzzles using Paths and Cycles. Proceedings of the British Machine Vision Conference. BMVA Press, September 2014.
BibTex
@inproceedings{BMVC.28.117
title = {Solving Jigsaw Puzzles using Paths and Cycles},
author = {Logeswaran, Lajanugen},
year = {2014},
booktitle = {Proceedings of the British Machine Vision Conference},
publisher = {BMVA Press},
editors = {Valstar, Michel and French, Andrew and Pridmore, Tony}
doi = { http://dx.doi.org/10.5244/C.28.117 }
}