PSQP – Puzzle Solving by Quadratic Programming

Each tile ti is assigned to a location j. The result is represented by a permutation π of the N = 9 tiles.

The traditional Jigsaw Puzzle is the problem of assembling several non-overlapping puzzle pieces that can be combined in order to obtain a single image. Despite that fact it is a NP-complete problem, much effort has been devoted to solve the problem and its scientific challenges. In this article, the authors introduce the Puzzle Solving by Quadratic Programming (PSQP) method as a new formulation to solve image puzzles.

The solution corresponds to the biunivocal association of tiles to locations, according to an energy function. Due to the complexity of this hard combinatorial problem, the authors reformulate it as a quadratic programming problem, which we solve using a Constrained Gradient Ascent algorithm. To evaluate it experimental results are shown and compared to the state-of-the-art approaches.

F. Andalo; G. Taubin; S. Goldenstein, “PSQP — Puzzle Solving by Quadratic Programming,” in IEEE Transactions on Pattern Analysis and Machine Intelligence. doi: 10.1109/TPAMI.2016.2547394

This entry was posted in blog, publications, science and tagged , , , , , , , , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s