Solving Jigsaw Puzzles via Nonconvex Quadratic Programming With the Projected Power Method
Solving Jigsaw Puzzles via Nonconvex Quadratic Programming With the Projected Power Method
复制标题
DOI：
10.1109/tmm.2020.3009501
复制
发表时间：
2021
影响因子：
7.3
通讯作者：
Fang Yan;Yuanjie Zheng;Jinyu Cong;Liu Liu-Liu;D. Tao;Sujuan Hou
中科院分区：
文献类型：
--
作者：
Fang Yan;Yuanjie Zheng;Jinyu Cong;Liu Liu-Liu;D. Tao;Sujuan Hou
拼图游戏包括重建一幅被分成许多连锁碎片的图片。本文提出了一种求解正方形拼图问题的自动全局方法，其中拼图块的方向和位置都是未知的。这个困难的组合排序任务制定为一个非凸二次规划问题，通过投影功率法解决。具体来说，这项工作的目的是指定的位置和方向的拼图块通过最大化的约束二次函数，解决了优化的排列矩阵组成的噪声成对的亲和力拼图块。在MIT，麦吉尔和Pomeranz数据集上获得的实验结果表明，我们的方法优于最先进的技术。
Jigsaw puzzles consist of reconstructing a picture that has been divided into many interlocking pieces. This paper describes an automatic global method for solving the square-piece jigsaw puzzle problem in which neither the orientations nor the locations of the jigsaw pieces are known. This hard combinatorial sorting task is formulated as a nonconvex quadratic programming problem that is solved via the projected power method. Specifically, this work aims to specify the locations and orientations of puzzle pieces by maximizing a constrained quadratic function that resolves an optimized permutation matrix composed of the noisy pairwise affinities between jigsaw pieces. The experimental results obtained in the MIT, McGill and Pomeranz datasets indicate that our method outperforms state-of-the-art techniques.