IEEE Trans Pattern Anal Mach Intell. 2019 Sep;41(9):2222-2235. doi: 10.1109/TPAMI.2018.2857776. Epub 2018 Jul 19.
We present a novel computational puzzle solver for square-piece image jigsaw puzzles with no prior information such as piece orientation or anchor pieces. By "piece" we mean a square $d$d x $d$d block of pixels, where we investigate pieces as small as 7 × 7 pixels. To reconstruct such challenging puzzles, we propose to find maximum geometric consensus between pieces, specifically hierarchical piece loops. The proposed algorithm seeks out loops of four pieces and aggregates the smaller loops into higher order "loops of loops" in a bottom-up fashion. In contrast to previous puzzle solvers which aim to maximize compatibility measures between all pairs of pieces and thus depend heavily on the pairwise compatibility measures used, our approach reduces the dependency on the pairwise compatibility measures which become increasingly uninformative for small scales and instead exploits geometric agreement among pieces. Our contribution also includes an improved pairwise compatibility measure which exploits directional derivative information along adjoining boundaries of the pieces. We verify the proposed algorithm as well as its individual components with mathematical analysis and reconstruction experiments.
我们提出了一种新的计算拼图游戏解决方案，用于解决没有先验信息（如碎片方向或锚定碎片）的方形图像拼图游戏。我们所说的“碎片”是指一个 $d$d x $d$d 像素的正方形块，其中我们研究的碎片小至 7 x 7 像素。为了重建如此具有挑战性的谜题，我们建议在碎片之间找到最大的几何一致性，特别是层次化的碎片循环。所提出的算法寻找四个碎片的循环，并以自下而上的方式将较小的循环聚合为更高阶的“循环的循环”。与之前的拼图求解器不同，后者旨在最大化所有碎片对之间的兼容性度量，因此严重依赖于所使用的成对兼容性度量，我们的方法减少了对成对兼容性度量的依赖，因为这些度量对于小尺度变得越来越没有信息量，而是利用了碎片之间的几何一致性。我们的贡献还包括一种改进的成对兼容性度量，该度量利用了碎片相邻边界的方向导数信息。我们通过数学分析和重建实验验证了所提出的算法及其各个组件。
