Siamese-Discriminant Deep Reinforcement Learning for Solving Jigsaw Puzzles with Large Eroded Gaps

Jigsaw puzzle solving has recently become an emerging research area. The developed techniques have been widely used in applications beyond puzzle solving. This paper focuses on solving Jigsaw Puzzles with Large Eroded Gaps (JPwLEG). We formulate the puzzle reassembly as a combinatorial optimization problem and propose a Siamese-Discriminant Deep Reinforcement Learning (SD2RL) to solve it. A Deep Q-network (DQN) is designed to visually understand the puzzles, which consists of two sets of Siamese Discriminant Networks, one set to perceive the pairwise relations between vertical neighbors and another set for horizontal neighbors. The proposed DQN considers not only the evidence from the incumbent fragment but also the support from its four neighbors. The DQN is trained using replay experience with carefully designed rewards to guide the search for a sequence of fragment swaps to reach the correct puzzle solution. Two JPwLEG datasets are constructed to evaluate the proposed method, and the experimental results show that the proposed SD2RL significantly outperforms state-of-the-art methods.

Authors

• Xingke Song The University of Nottingham Ningbo China
• Jiahuan Jin University of Nottingham Ningbo China
• Chenglin Yao The University of Nottingham Ningbo China
• Shihe Wang University of Nottingham Ningbo China
• Jianfeng Ren The Digital Port Technologies Lab, School of Computer Science, University of Nottingham Ningbo China Beacons of Excellence Research and Innovation Institute, University of Nottingham Ningbo China
• Ruibin Bai The Digital Port Technologies Lab, School of Computer Science, University of Nottingham Ningbo China Beacons of Excellence Research and Innovation Institute, University of Nottingham Ningbo China

Keywords

• CV: Learning & Optimization for CV
• CV: Visual Reasoning & Symbolic Representations
• ML: Deep Neural Network Algorithms
• SO: Other Foundations of Search & Optimization