  We present a novel method for solving square jigsaw puzzles based on global
optimization. The method is fully automatic, assumes no prior information, and
can handle puzzles with known or unknown piece orientation. At the core of the
optimization process is nonlinear relaxation labeling, a well-founded approach
for deducing global solutions from local constraints, but unlike the classical
scheme here we propose a multi-phase approach that guarantees convergence to
feasible puzzle solutions. Next to the algorithmic novelty, we also present a
new compatibility function for the quantification of the affinity between
adjacent puzzle pieces. Competitive results and the advantage of the
multi-phase approach are demonstrated on standard datasets.
