Advisor: Dr. Chris Pollett

Description:

Solving a jigsaw puzzle entails arranging a fixed set of pieces such that they reconstruct an original source image. With a traditional jigsaw puzzle, there are two primary factors that significantly reduce the difficulty of the problem, namely different piece shapes which mechanically limit the number of possible permutations as well as knowledge of the original source image, which allows the solver to determine with certainty whether two pieces are adjacent.

This project will develop a tool that will attempt to reconstruct a jigsaw puzzle of uniform, square pieces for an unknown image. It will avoid of the simplification of the problem done in existing research including: not allowing piece rotation, assuming knowledge of a low density version of the source image, and fixing the position of a subset of the puzzle pieces in their correct locations.

Schedule:

Deliverables:

The full project will be done when CS298 is completed. The following will be done by the end of CS297:

1. Jigsaw Puzzle Generator: Given a source image, the generator will:
   1. Import a bitmap image
   2. Parse the image into a specified number of equal size tiles (Note: some of the picture may be cropped during this process)
   3. Perform a Fisher-Yates shuffle of the pieces
   4. Optionally rotate each tile randomly
   5. Display the shuffled image (with optional borders for clarity)
   
   
2. Literature Review Presentation: Create a presentation describing different, existing techniques that are used to solve the jigsaw puzzle problem.
   
   
3. Basic Solver Framework: Develop a basic framework that will perform a bottom-up solution to the jigsaw problem. It will utilize the techniques described in the literature review.
   
   
4. Multiple Comparative Metrics Results Presentation: No one metric will sufficiently quantify the quality of a jigsaw puzzle solution. In this deliverable, I will implement at least three solution comparison metrics and compare the results of these metrics across images with different characteristics (e.g. high texture, images with duplicate pieces, etc.)
   
   
5. CS297 Final Report: This is the culminating document for this semester's activities. It will include:
   1. An overview of the project problem
   2. Summary of previous work and solutions of the problem
   3. Discuss the strategies I plan to use to solve the problem
   4. Discuss the solution quality and metrics that will be used to compare solved puzzles.
   5. Provide a description of the two tools implemented namely the image parser and the solver.
   
   

References:

D. Sholomon, O. David, and N. S. Netanyahu, "A genetic algorithm based solver for very large jigsaw puzzles," in IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2013.