TEN: Twin Embedding Networks for the Jigsaw Puzzle Problem with Eroded Boundaries
This addresses real-world puzzle-like problems by bridging the gap between low accuracy of classical methods and high computational complexity of neural networks, though it is incremental in nature.
The paper tackles the jigsaw puzzle problem with eroded boundaries by proposing a Twin Embedding Network (TEN) for improved pairwise compatibility, achieving up to 8.5% and 16.8% higher reconstruction accuracy in two variants and matching classical methods in speed.
This paper introduces the novel CNN-based encoder Twin Embedding Network (TEN), for the jigsaw puzzle problem (JPP), which represents a puzzle piece with respect to its boundary in a latent embedding space. Combining this latent representation with a simple distance measure, we demonstrate improved accuracy levels of our newly proposed pairwise compatibility measure (CM), compared to that of various classical methods, for degraded puzzles with eroded tile boundaries. We focus on this problem instance for our case study, as it serves as an appropriate testbed for real-world scenarios. Specifically, we demonstrated an improvement of up to 8.5% and 16.8% in reconstruction accuracy, for so-called Type-1 and Type-2 problem variants, respectively. Furthermore, we also demonstrated that TEN is faster by a few orders of magnitude, on average, than a typical deep neural network (NN) model, i.e., it is as fast as the classical methods. In this regard, the paper makes a significant first attempt at bridging the gap between the relatively low accuracy (of classical methods and the intensive computational complexity (of NN models), for practical, real-world puzzle-like problems.