Solving Jigsaw Puzzles with Linear Programming
This addresses the challenge of robustly assembling jigsaw puzzles for computer vision applications, though it appears incremental as it builds on existing formulations with a new solver.
The authors tackled the problem of solving jigsaw puzzles by proposing a Linear Programming (LP) formulation that handles pieces with unknown positions and orientations, outperforming state-of-the-art methods on public datasets.
We propose a novel Linear Program (LP) based formula- tion for solving jigsaw puzzles. We formulate jigsaw solving as a set of successive global convex relaxations of the stan- dard NP-hard formulation, that can describe both jigsaws with pieces of unknown position and puzzles of unknown po- sition and orientation. The main contribution and strength of our approach comes from the LP assembly strategy. In contrast to existing greedy methods, our LP solver exploits all the pairwise matches simultaneously, and computes the position of each piece/component globally. The main ad- vantages of our LP approach include: (i) a reduced sensi- tivity to local minima compared to greedy approaches, since our successive approximations are global and convex and (ii) an increased robustness to the presence of mismatches in the pairwise matches due to the use of a weighted L1 penalty. To demonstrate the effectiveness of our approach, we test our algorithm on public jigsaw datasets and show that it outperforms state-of-the-art methods.