Solving Image Puzzles with a Simple Quadratic Programming Formulation

References

[1] E. Demaine and M. Demaine, “Jigsaw puzzles, edge matching, and polyomino packing: Connections and complexity,” Graphs and Combinatorics, vol. 23, pp. 195–208, 2007.

[2] E. Justino, L. Oliveira, and C. Freitas, “Reconstructing shredded documents through feature matching,” Forensic science international, vol. 160, no. 2, pp. 140–147, 2006.

[3] J. McBride and B. Kimia, “Archaeological fragment reconstruction using curve-matching,” in Conference on Computer Vision and Pattern Recognition Workshop. (CVPRW), vol. 1, 2003, pp. 3–3.

[4] H. Freeman and L. Garder, “Apictorial jigsaw puzzles: The computer solution of a problem in pattern recognition,” IEEE Transactions on Electronic Computers, no. 2, pp. 118–127, 1964.

[5] D. Goldberg, C. Malon, and M. Bern, “A global approach to automatic solution of jigsaw puzzles,” in Proceedings of the eighteenth annual symposium on Computational geometry, 2002, pp. 82–87.

[6] D. Kosiba, P. Devaux, S. Balasubramanian, T. Gandhi, and K. Kasturi, “An automatic jigsaw puzzle solver,” in Proceedings of the 12th International Conference on Pattern Recognition (IAPR), vol. 1, 1994, pp. 616–618.

[7] T. Nielsen, P. Drewsen, and K. Hansen, “Solving jigsaw puzzles using image features,” Pattern Recognition Letters, vol. 29, no. 14, pp. 1924– 1933, 2008.

[8] T. Cho, S. Avidan, and W. Freeman, “A probabilistic image jigsaw puzzle solver,” in Conference on Computer Vision and Pattern Recognition (CVPR), 2010, pp. 183–190.

[9] D. Pomeranz, M. Shemesh, and O. Ben-Shahar, “A fully automated greedy square jigsaw puzzle solver,” in IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2011, pp. 9–16.

[10] E. Seneta, Non-negative matrices and Markov chains. Springer Verlag, 2006.

[11] J. Rosen, “The gradient projection method for nonlinear programming. part i. linear constraints,” Journal of the Society for Industrial and Applied Mathematics, vol. 8, no. 1, pp. 181–217, 1960.

[12] https://dailypuzzlecheats.com/

[13] https://dailypuzzlecheats.com/shuffle-puzzle-play-online

@article{1703842,
      author = {Meerja Maqbul Baig, Shahela Osmani},
      title = {Solving Image Puzzles with a Simple Quadratic Programming Formulation},
      journal = {Iconic Research And Engineering Journals},
      year = {2022},
      volume = {6},
      number = {4},
      pages = {49-54},
      issn = {2456-8880},
      url = {https://www.irejournals.com/formatedpaper/1703842.pdf},
      abstract = {We present a new formulation to automatically solve jigsaw puzzles considering only the information contained on the image. Our formulation maps the problem of solving a jigsaw puzzle to the maximization of a constrained quadratic function that can be solved by a numerical method. The proposed method is deterministic and it can handle arbitrary rectangular pieces. We tested the validity of the method to solve problems up to 3300 puzzle pieces, and we compared our results to the current state-of-the-art, obtaining superior accuracy.},
      month = {October},
  }