fast_jigsaw_puzzle_solver
fast_jigsaw_puzzle_solver copied to clipboard
Published
20 hours ago •
hj2choi
hj2choi
fragments image and re-assemble them back to original image. #Prim's MST algorithm
Fast Jigsaw Puzzle Solver with unknown orientation
- Divides image into N (row x col) pieces and jumbles them into 8 random orientations.
- Reconstructs N puzzle pieces back to the original image in O(N2) runtime.
Disclaimer: orientation of the final image is random. Successful reconstruction is not always guaranteed.
Features
- Euclidean distance metric for image boundary matching
-
Parallel 3D distance matrix (img x img x orientation) computation
- Prim's Minimum Spanning Tree algorithm with Linked-Hashmap implementation of the Priority Queue
Dependencies
python 3.7+
numpy 1.16+
opencv-python 4.1.2+
Execution guide
Quick demo with animation
pip install -r requirements.txt
bash demo.sh
create_jigsaw_pieces.py: read and slice image into equal-sized jigsaw pieces and apply random set of transformations.
create_jigsaw_pieces.py [OPTION] ${image_filename} ${x_slice} ${y_slice} ${keystring}
-v: increase verbosity
solve_puzzle.py: reconstruct puzzle pieces back to original image
solve_puzzle.py [OPTION] ${keystring}
-v: increase verbosity
-a: show animation
-t: show minimum spanning tree on top of the animation
image reconstruction algorithm
I[i,t]: all puzzle pieces (image, transformation)
S[i,j,t]: all-pairs puzzle piece similarity-matrix
G[y,x]: puzzle block
Q: priority queue
1 initialize S with similarity metric
2 set all nodes in G as inactive
3 root <- (im: I[0,0], pos: (0,0))
4 Q.enqueue(root)
5 while Q is not empty do
6 v <- Q.dequeue()
7 G[v.pos].activate(v)
8 for all w, dir in G.inactiveNeighbors(v) do
9 w.im <- arg_max(S[v.im,j,k] for all j and k)
10 w.pos <- (v.pos+dir)
11 Q.enqueue(w)
12 Q.removeAllDuplicates(v.im)
Time complexity analysis
N: number of images (puzzle pieces) C: total cache miss (number of duplicate puzzle pieces to be removed from queue) in all cases, C = O(N)
| Operations \ Algorithms | brute-force |
brute-forceindex mappinghashmap | Prim's MSTmax-heap |
Prim's MSTlinked-hashmapmatrix symmetry |
|---|---|---|---|---|
| similarity matrix | O(256N2) | O(32N2) | O(32N2) | O(16N2) |
| traverse all puzzle pieces | O(N) | O(N) | O(N) | O(N) |
| traverse all positions | O(4N) | O(4N) | - | - |
| argmax(img at pos(x,y)) | O(256N) | O(32N) | O(32N) | O(32N) |
| validate puzzle-block shape | O(4N) | O(1) | O(1) | O(1) |
| (PQueue) remove by ID | - | O(C) | O(ClogN) | O(C) |
| (PQueue) extract_min() | - | - | O(1) | O(1) |
| (PQueue) enqueue | - | - | O(logN) | O(N) |
| Total time complexity | O(256N2)+O(4096N4) | O(32N2)+O(32(C+N2))+O(128N3) | O(32N2)+O(32(C+N2))+O(3CNlog(N)) | O(16N2)+O(32(C+N2))+O(N(C+N)) |
| = | O(N4) | O(N3) | O(N2log(N)) | O(N2) |
references
http://chenlab.ece.cornell.edu/people/Andy/publications/Andy_files/Gallagher_cvpr2012_puzzleAssembly.pdf http://www.bmva.org/bmvc/2016/papers/paper139/paper139.pdf https://en.wikipedia.org/wiki/Prim%27s_algorithm https://en.wikipedia.org/wiki/Priority_queue https://github.com/python/cpython/blob/master/Lib/heapq.py
hj2choi