SegSemPuzzle: Solving Jigsaw Puzzles with Semantic Segmentation
Resumo
The traditional Jigsaw Puzzle is a challenging task performed by humans, mainly due to its hardness and proven to be a NP-Complete problem. Even so, recent efforts show better performance in this task using different methods involving complex computer vision and machine learning techniques. In this sense, this paper proposes new approaches based on the semantic segmentation (SS) task to solve jigsaw puzzles (visual puzzles) in reduced training scenario. To the best of our knowledge, this is the first work in the literature that uses SS for the target application. In the performed experiments, it was possible to demonstrate that SegSemPuzzle and SegSemPuzzle-G obtained excellent results when compared with other approaches existing in literature for 3 × 3 puzzle solving tasks.
Palavras-chave:
semantic segmentation, shortest path algorithm, deep learning, greedy algorithm, Jigsaw Puzzle
Referências
D. Kosiba et al., “An automatic jigsaw puzzle solver,” in 12th ICPR, vol. 1, 1994, pp. 616–618.
R. Tybon, “Generating solutions to the jigsaw puzzle problem,” PhD thesis, Griffith University, Australia, 2004.
J. Gras, “Puzzle reassembly using model based reinforcement learning,” 2019. [Online]. Available: [link]
V. Pammer et al., “Designing for engaging bci training: A jigsaw puzzle,” in the 2015 Annual Symposium on Computer-Human Interaction in Play, 2015, pp. 667–672.
L. Yang et al., “Jigsaw puzzle: Selective backdoor attack to subvert malware classifiers,” in IEEE Symposium on Security and Privacy (SP), 2023, pp. 719–736.
A. R. Willis and D. B. Cooper, “Computational reconstruction of ancient artifacts,” IEEE Signal processing magazine, vol. 25, no. 4, pp. 65–83, 2008.
C. Doersch et al., “Unsupervised visual representation learning by context prediction,” in IEEE ICCV, December 2015, pp. 1422–1430.
M. Noroozi and P. Favaro, “Unsupervised learning of visual representations by solving jigsaw puzzles,” in Computer Vision – ECCV 2016, 2016, pp. 69–84.
F. A. Andaló et al, “PSQP: Puzzle solving by quadratic programming,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 39, no. 2, pp. 385–396, 2017.
——, “Solving image puzzles with a simple quadratic programming formulation,” in Conference on Graphics, Patterns and Images (SIBGRAPI), 2012, pp. 63–70.
F. A. Andaló and S. Goldenstein, “Computer vision methods applicable to forensic science,” in Workshop of Theses and Dissertations, Conference on Graphics, Patterns and Images (WTD/SIBGRAPI), 2013.
F. A. Andaló et al, “Automatic reconstruction of ancient Portuguese tile panels,” Instituto Nacional de Matemática Pura e Aplicada (IMPA), Tech. Rep. A773/2016, 2016.
D. Sholomon et al., “An automatic solver for very large jigsaw puzzles using genetic algorithms,” Genetic Programming and Evolvable Machines, vol. 17, no. 3, pp. 291–313, Sep 2016.
M. Paumard et al., “Image reassembly combining deep learning and shortest path problem,” in Computer Vision – ECCV 2018, 2018, pp. 155–169.
——, “Deepzzle: Solving visual jigsaw puzzles with deep learning and shortest path optimization,” IEEE Transactions on Image Processing, vol. 29, pp. 3569–3581, 2020.
——, “Alphazzle: Jigsaw puzzle solver with deep monte-carlo tree search,” arXiv preprint, 2023.
C. Park et al., “Generating 2d lego compatible puzzles using reinforcement learning,” IEEE Access, vol. 8, pp. 180 394–180 410, 2020.
F. Jampy et al., “3d puzzle reconstruction for archeological fragments,” in Three-Dimensional Image Processing, Measurement (3DIPM), and Applications 2015, vol. 9393. SPIE, 2015, pp. 56–64.
M. Siam et al., “A comparative study of real-time semantic segmentation for autonomous driving,” in the IEEE CVPR workshops, 2018, pp. 587–597.
K. Khan et al., “Crowd counting using end-to-end semantic image segmentation,” Electronics, vol. 10, no. 11, p. 1293, 2021.
R. Miyamoto et al., “Vision-based road-following using results of semantic segmentation for autonomous navigation,” in IEEE ICCEBerlin, 2019, pp. 174–179.
T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, 2nd ed. The MIT Press, 2001.
K. He, X. Zhang, S. Ren, and J. Sun, “Deep residual learning for image recognition,” in 2016 IEEE CVPR, 2016, pp. 770–778.
J. Deng et al., “Imagenet: A large-scale hierarchical image database,” in IEEE CVPR, 2009, pp. 248–255.
D. Bank, N. Koenigstein, and R. Giryes, “Autoencoders,” Machine Learning for Data Science Handbook: Data Mining and Knowledge Discovery Handbook, pp. 353–374, 2023.
Y. Guo, Y. Liu, T. Georgiou, and M. S. Lew, “A review of semantic segmentation using deep neural networks,” International journal of multimedia information retrieval, vol. 7, pp. 87–93, 2018.
J. Wang et al., “Deep high-resolution representation learning for visual recognition,” IEEE Transactions on Pattern Analysis & Machine Intelligence, vol. 43, no. 10, pp. 3349–3364, oct 2021.
J.-C. Chen, “Dijkstra’s shortest path algorithm,” Journal of formalized mathematics, vol. 15, no. 9, pp. 237–247, 2003.
Ypsilantis et al, “The met dataset: Instance-level recognition for artworks,” in Neural Information Processing Systems Track on Datasets and Benchmarks, vol. 1, 2021, pp. 1–12.
R. Mottaghi et al, “The role of context for object detection and semantic segmentation in the wild,” in IEEE CVPR, 2014, pp. 891–898.
R. Tybon, “Generating solutions to the jigsaw puzzle problem,” PhD thesis, Griffith University, Australia, 2004.
J. Gras, “Puzzle reassembly using model based reinforcement learning,” 2019. [Online]. Available: [link]
V. Pammer et al., “Designing for engaging bci training: A jigsaw puzzle,” in the 2015 Annual Symposium on Computer-Human Interaction in Play, 2015, pp. 667–672.
L. Yang et al., “Jigsaw puzzle: Selective backdoor attack to subvert malware classifiers,” in IEEE Symposium on Security and Privacy (SP), 2023, pp. 719–736.
A. R. Willis and D. B. Cooper, “Computational reconstruction of ancient artifacts,” IEEE Signal processing magazine, vol. 25, no. 4, pp. 65–83, 2008.
C. Doersch et al., “Unsupervised visual representation learning by context prediction,” in IEEE ICCV, December 2015, pp. 1422–1430.
M. Noroozi and P. Favaro, “Unsupervised learning of visual representations by solving jigsaw puzzles,” in Computer Vision – ECCV 2016, 2016, pp. 69–84.
F. A. Andaló et al, “PSQP: Puzzle solving by quadratic programming,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 39, no. 2, pp. 385–396, 2017.
——, “Solving image puzzles with a simple quadratic programming formulation,” in Conference on Graphics, Patterns and Images (SIBGRAPI), 2012, pp. 63–70.
F. A. Andaló and S. Goldenstein, “Computer vision methods applicable to forensic science,” in Workshop of Theses and Dissertations, Conference on Graphics, Patterns and Images (WTD/SIBGRAPI), 2013.
F. A. Andaló et al, “Automatic reconstruction of ancient Portuguese tile panels,” Instituto Nacional de Matemática Pura e Aplicada (IMPA), Tech. Rep. A773/2016, 2016.
D. Sholomon et al., “An automatic solver for very large jigsaw puzzles using genetic algorithms,” Genetic Programming and Evolvable Machines, vol. 17, no. 3, pp. 291–313, Sep 2016.
M. Paumard et al., “Image reassembly combining deep learning and shortest path problem,” in Computer Vision – ECCV 2018, 2018, pp. 155–169.
——, “Deepzzle: Solving visual jigsaw puzzles with deep learning and shortest path optimization,” IEEE Transactions on Image Processing, vol. 29, pp. 3569–3581, 2020.
——, “Alphazzle: Jigsaw puzzle solver with deep monte-carlo tree search,” arXiv preprint, 2023.
C. Park et al., “Generating 2d lego compatible puzzles using reinforcement learning,” IEEE Access, vol. 8, pp. 180 394–180 410, 2020.
F. Jampy et al., “3d puzzle reconstruction for archeological fragments,” in Three-Dimensional Image Processing, Measurement (3DIPM), and Applications 2015, vol. 9393. SPIE, 2015, pp. 56–64.
M. Siam et al., “A comparative study of real-time semantic segmentation for autonomous driving,” in the IEEE CVPR workshops, 2018, pp. 587–597.
K. Khan et al., “Crowd counting using end-to-end semantic image segmentation,” Electronics, vol. 10, no. 11, p. 1293, 2021.
R. Miyamoto et al., “Vision-based road-following using results of semantic segmentation for autonomous navigation,” in IEEE ICCEBerlin, 2019, pp. 174–179.
T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, 2nd ed. The MIT Press, 2001.
K. He, X. Zhang, S. Ren, and J. Sun, “Deep residual learning for image recognition,” in 2016 IEEE CVPR, 2016, pp. 770–778.
J. Deng et al., “Imagenet: A large-scale hierarchical image database,” in IEEE CVPR, 2009, pp. 248–255.
D. Bank, N. Koenigstein, and R. Giryes, “Autoencoders,” Machine Learning for Data Science Handbook: Data Mining and Knowledge Discovery Handbook, pp. 353–374, 2023.
Y. Guo, Y. Liu, T. Georgiou, and M. S. Lew, “A review of semantic segmentation using deep neural networks,” International journal of multimedia information retrieval, vol. 7, pp. 87–93, 2018.
J. Wang et al., “Deep high-resolution representation learning for visual recognition,” IEEE Transactions on Pattern Analysis & Machine Intelligence, vol. 43, no. 10, pp. 3349–3364, oct 2021.
J.-C. Chen, “Dijkstra’s shortest path algorithm,” Journal of formalized mathematics, vol. 15, no. 9, pp. 237–247, 2003.
Ypsilantis et al, “The met dataset: Instance-level recognition for artworks,” in Neural Information Processing Systems Track on Datasets and Benchmarks, vol. 1, 2021, pp. 1–12.
R. Mottaghi et al, “The role of context for object detection and semantic segmentation in the wild,” in IEEE CVPR, 2014, pp. 891–898.
Publicado
13/11/2023
Como Citar
TACIANO, Miguel Silva; PUGLIESE, Victor; FARIA, Fabio Augusto.
SegSemPuzzle: Solving Jigsaw Puzzles with Semantic Segmentation. In: WORKSHOP DE VISÃO COMPUTACIONAL (WVC), 18. , 2023, São Bernardo do Campo/SP.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2023
.
p. 131-136.
DOI: https://doi.org/10.5753/wvc.2023.27545.
