CS297 Proposal
A Square Jigsaw Puzzle Problem Solver
Zayd Hammoudeh (zayd.hammoudeh@sjsu.edu)
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:
Week 1:
Feb. 1-7 | Project kickoff meeting with Dr. Pollett. Begin work on the puzzle parser. |
Week 2:
Feb. 8-14 | Deliverable #1: Jigsaw Puzzle Parser Complete |
Week 3:
Feb. 15-21 | Begin literature review of existing approaches to solve the jigsaw puzzle problem. |
Week 4:
Feb. 22-28 | Continue working on presentation of jigsaw puzzle problem literature review. |
Week 5:
Feb. 29 - Mar. 6 | Deliverable #2: Complete presentation of existing literature |
Week 6:
Mar. 7-13 | Begin work on a bottom-up jigsaw puzzle solver. |
Week 7:
Mar. 14-20 | Continue work on the jigsaw puzzle solver. Present initial work. |
Week 8:
Mar. 21-27 | Continue work on the solver. Implement a testing architecture to ensure the correctness of the implementation. |
Week 9:
Mar. 28 - Apr. 3 | SJSU Spring Break. Deliverable #3: Complete first pass of a jigsaw puzzle solver. |
Week 10:
Apr. 4-10 | Additional literature review on jigsaw puzzle solution metrics. |
Week 11:
Apr. 11-17 | Begin implementing three metrics for comparing jigsaw puzzle results. |
Week 12:
Apr. 18-24 | Deliverable #4: Complete jigsaw puzzle solution comparison across multiple
images (with different characteristics) using the implemented metrics. |
Week 13:
Apr. 25 - May 1 | Finalize all work on the jigsaw puzzle solver in preparation for writing the
CS297 final report. |
Week 14:
May 2-8 | Begin work on CS297 final report. |
Week 15:
May 9-15 | Deliverable 5: Complete CS297 Final Report |
Deliverables:
The full project will be done when CS298 is completed. The following will
be done by the end of CS297:
- Jigsaw Puzzle Generator: Given a source image, the generator will:
- Import a bitmap image
- Parse the image into a specified number of equal size tiles (Note:
some of the picture may be cropped during this process)
- Perform a Fisher-Yates shuffle of the pieces
- Optionally rotate each tile randomly
- Display the shuffled image (with optional borders for clarity)
- Literature Review Presentation: Create a presentation describing different, existing
techniques that are used to solve the jigsaw puzzle problem.
- 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.
- 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.)
- CS297 Final Report: This is the culminating document for this semester's activities.
It will include:
- An overview of the project problem
- Summary of previous work and solutions of the problem
- Discuss the strategies I plan to use to solve the problem
- Discuss the solution quality and metrics that will be used to
compare solved puzzles.
- 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. |