  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.
