PSQP: Puzzle Solving by Quadratic Programming

IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI), 2017

Abstract

In this article we present the first effective global method for the reconstruction of image puzzles comprising rectangle pieces - Puzzle Solving by Quadratic Programming (PSQP). The proposed novel mathematical formulation reduces the problem to the maximization of a constrained quadratic function, which is solved via a gradient ascent approach. The proposed method is deterministic and can deal with arbitrary identical rectangular pieces. We provide experimental results showing its effectiveness when compared to state-of-the-art approaches. Although the method was developed to solve image puzzles, we also show how to apply it to the reconstruction of simulated strip-shredded documents, broadening its applicability.

BibTeX

@article{andalo17pami,
    authors      = “Fernanda A. Andal{\‘o} and Gabriel Taubin and Siome Goldenstein”,
    title        = “{PSQP}: Puzzle Solving by Quadratic Programming”,
    journal      = “{IEEE} Transactions on Pattern Analysis and Machine Intelligence ({PAMI})”,
    volume       = 39,
    number       = 2,
    pages        = “385–396”,
    year         = 2017,
}