- 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.
- 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
python 3.7+
numpy 1.16+
opencv-python 4.1.2+
pip install -r requirements.txt
bash demo.shcreate_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 [OPTION] ${keystring}-v: increase verbosity
-a: show animation
-t: show minimum spanning tree on top of the animation
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)
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-force index mapping hashmap |
Prim's MST max-heap |
Prim's MST linked-hashmap matrix 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) |
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