PSQP: Puzzle Solving by Quadratic Programming

In this article we present the first effective method based on global optimization 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...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on pattern analysis and machine intelligence 2017-02, Vol.39 (2), p.385-396
Main Authors: Andalo, Fernanda A., Taubin, Gabriel, Goldenstein, Siome
Format: Article
Language:English
Subjects:
Ascent
Computer simulation
constrained optimization
Electronic mail
Global optimization
Image color analysis
Image puzzle
Image reconstruction
Image resolution
Measurement
Quadratic equations
Quadratic programming
Shape
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In this article we present the first effective method based on global optimization 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.
ISSN:0162-8828
1939-3539
2160-9292
DOI:10.1109/TPAMI.2016.2547394