An Automatic Solver for Very Large Jigsaw Puzzles Using Genetic Algorithms
In this paper we propose the first effective genetic algorithm (GA)-based jigsaw puzzle solver. We introduce a novel crossover procedure that merges two "parent" solutions to an improved "child" configuration by detecting, extracting, and combining correctly assembled puzzle segments. The solver proposed exhibits state-of-the-art performance, as far as handling previously attempted puzzles more accurately and efficiently, as well puzzle sizes that have not been attempted before. The extended experimental results provided in this paper include, among others, a thorough inspection of up to 30,745-piece puzzles (compared to previous attempts on 22,755-piece puzzles), using a considerably faster concurrent implementation of the algorithm. Furthermore, we explore the impact of different phases of the novel crossover operator by experimenting with several variants of the GA. Finally, we compare different fitness functions and their effect on the overall results of the GA-based solver.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
A Generalized Genetic Algorithm-Based Solver for Very Large Jigsaw Puzzles of Complex Types
In this paper we introduce new types of square-piece jigsaw puzzles, where in addition to the unknown location and orientation of each piece, a piece might also need to be flipped. These puzzles, which are associated wit…
A Genetic Algorithm-Based Solver for Very Large Jigsaw Puzzles
In this paper we propose the first effective automated, genetic algorithm (GA)-based jigsaw puzzle solver. We introduce a novel procedure of merging two "parent" solutions to an improved "child" solution by detecting, ex…
Genetic Algorithm-Based Solver for Very Large Multiple Jigsaw Puzzles of Unknown Dimensions and Piece Orientation
In this paper we propose the first genetic algorithm (GA)-based solver for jigsaw puzzles of unknown puzzle dimensions and unknown piece location and orientation. Our solver uses a novel crossover technique, and sets a n…
Solving Multiple Square Jigsaw Puzzles With Missing Pieces
Jigsaw-puzzle solving is necessary in many applications, including biology, archaeology, and every-day life. In this paper we consider the square jigsaw puzzle problem, where the goal is to reconstruct the image from a s…
Solving Convex Partition Visual Jigsaw Puzzles
Jigsaw puzzle solving requires the rearrangement of unordered pieces into their original pose in order to reconstruct a coherent whole, often an image, and is known to be an intractable problem. While the possible impact…