GANzzle: Reframing jigsaw puzzle solving as a retrieval task using a generative mental image
This addresses the problem of scalable and size-agnostic puzzle solving for computer vision applications, though it is incremental as it builds on existing generative adversarial methods.
The paper tackles the combinatorial challenge of jigsaw puzzle solving by reframing it as a retrieval task using a generative mental image inferred from all pieces, achieving performance on par with deep learning methods while generalizing to multiple puzzle sizes.
Puzzle solving is a combinatorial challenge due to the difficulty of matching adjacent pieces. Instead, we infer a mental image from all pieces, which a given piece can then be matched against avoiding the combinatorial explosion. Exploiting advancements in Generative Adversarial methods, we learn how to reconstruct the image given a set of unordered pieces, allowing the model to learn a joint embedding space to match an encoding of each piece to the cropped layer of the generator. Therefore we frame the problem as a R@1 retrieval task, and then solve the linear assignment using differentiable Hungarian attention, making the process end-to-end. In doing so our model is puzzle size agnostic, in contrast to prior deep learning methods which are single size. We evaluate on two new large-scale datasets, where our model is on par with deep learning methods, while generalizing to multiple puzzle sizes.