Multi-Phase Relaxation Labeling for Square Jigsaw Puzzle Solving

Abstract

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.

Paper

Vardi, B., Torcinovich, A., Khoroshiltseva, M., Pelillo, M. and Ben-Shahar, O. Multi-Phase Relaxation Labeling for Square Jigsaw Puzzle Solving. In Proceedings of the 18th International Joint Conference on Computer Vision, Imaging and Computer Graphics Theory and Applications (VISIGRAPP 2023).

Supplementary Material

Supplementary material is available here.

Code

The project code is available here.

Related Papers

  • Khoroshiltseva, M., Vardi, B., Torcinovich, A., Traviglia, A., Ben-Shahar, O. and Pelillo, M., 2021. Jigsaw puzzle solving as a consistent labeling problem. In Computer Analysis of Images and Patterns: 19th International Conference, CAIP 2021, Virtual Event, September 28–30, 2021, Proceedings, Part II 19 (pp. 392-402). Springer International Publishing.

Acknowledgments

This project has received funding from the European Union’s Horizon 2020 research and innovation programme under grant agreement No 964854, the Helmsley Charitable Trust through the ABC Robotics Initiative, and the Frankel Fund of the Computer Science Department at Ben-Gurion University.