Solving Jigsaw Puzzles By the Graph Connection Laplacian
Solving Jigsaw Puzzles By the Graph Connection Laplacian
复制标题
DOI：
10.1137/19m1290760
复制
发表时间：
2018-11
期刊：
影响因子：
--
通讯作者：
Vahan Huroyan;Gilad Lerman;Hau‐Tieng Wu
中科院分区：
文献类型：
--
作者：
Vahan Huroyan;Gilad Lerman;Hau‐Tieng Wu
我们提出了一个新的数学框架来解决自动解决大型拼图游戏的问题。这个问题假设一个大的图像被切割成相等的正方形块，这些块被任意旋转和移位，并要求在给定变换后的块的情况下恢复原始图像。这项工作的主要贡献是一个理论上有保证的方法，通过使用与拼图相关的图形连接拉普拉斯算子来恢复拼图块的未知方向。迭代应用这种方法和其他方法来恢复未知的变化，结果在一个大拼图问题的解决方案。这个解决方案并不贪婪，不像其他许多解决方案。数值实验证明了该方法的优越性。
We propose a novel mathematical framework to address the problem of automatically solving large jigsaw puzzles. This problem assumes a large image which is cut into equal square pieces that are arbitrarily rotated and shifted and asks to recover the original image given the transformed pieces. The main contribution of this work is a theoretically-guaranteed method for recovering the unknown orientations of the puzzle pieces by using the graph connection Laplacian associated with the puzzle. Iterative application of this method and other methods for recovering the unknown shifts result in a solution for the large jigsaw puzzle problem. This solution is not greedy, unlike many other solutions. Numerical experiments demonstrate the competitive performance of the proposed method.