search

guansanghai / CVX-Jigsaw

Solving jigsaw puzzles using Matlab and CVX toolbox (THU Convex Optimization Homework).
16 stars 3 forks source link

Unknown orientation of puzzle pieces #1

Open superhero1 opened 5 years ago

superhero1 commented 5 years ago

@guansanghai I want to enhance your code to automatically rotate pieces for each iteration if their orientation is unknown, how can I do that?

guansanghai commented 5 years ago

For the linear programming based solver, the puzzles with unknown orientation is introduced in Section 3.5.1 of [1]. The authors update the algorithm just by adding a pre-process step. Specifically, they make 4 copies for each piece corresponding to 4 orientations. Then they select one piece, and fix the (x,y) coordinates of its 4 copies as an extra constraint of the LP problem. Hence the solution is 4 pictures with different orientations. For my implementation, I think the post-processing step also requires some upgrades.

For the quadratic programming based solver, the authors of [2] listed this case as their future work. So, I think it is still a challenge for this solver.

[1] R. Yu, C. Russell, L. Agapito, "Solving Jigsaw puzzles with linear programming"

[2] F. A. Andalo, G. Taubin, S. Goldenstein, "PSQP: Puzzle solving by quadratic programming," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 39, no. 2, pp. 385-396, 2017.