Jigsaw puzzle solving with template matching

Abstract

Reassembling fragmented objects is a crucial problem in fields like archaeology, often approached through jigsaw puzzle solutions. This study presents two novel template-matching-based methods for solving jigsaw puzzles. The first method employs a two-stage approach: Principal Component Analysis (PCA) determines the rotation of scattered pieces, followed by template matching to align and position them. The second method directly locates pieces using template matching. Three test puzzles were used to evaluate the effectiveness of these approaches. The results demonstrate that both methods accurately identified piece positions in all cases, proving their robustness and reliability. However, the proposed methods are currently limited to cases where the appearance of pieces is not heavily affected by noise, occlusion, or large-scale rotation.

Keywords

• Puzzle reassembly
• Template matching
• Jigsaw puzzle
• Puzzle solving

Şablon eşleştirme ile yapboz çözme

Öz

Parçalanmış nesneleri yeniden bir araya getirmek, arkeoloji gibi alanlarda sıklıkla yapboz bulmacası çözümleri yoluyla ele alınan önemli bir sorundur. Bu çalışma, yapboz bulmacalarını çözmek için iki yeni şablon eşleştirme tabanlı yöntem sunmaktadır. İlk yöntem iki aşamalı bir yaklaşım kullanır: Temel Bileşen Analizi, dağılmış parçaların dönüşünü belirler, ardından bunları hizalamak ve konumlandırmak için şablon eşleştirme yapılır. İkinci yöntem, şablon eşleştirmeyi kullanarak parçaları doğrudan bulur. Bu yaklaşımların etkinliğini değerlendirmek için üç test bulmacası kullanıldı. Sonuçlar, her iki yöntemin de tüm durumlarda parça konumlarını doğru bir şekilde belirlediğini ve sağlamlıklarını ve güvenilirliklerini kanıtladığını göstermektedir. Ancak önerilen yöntemler şu anda parçaların görünümünün gürültü, tıkanıklık veya büyük ölçekli rotasyondan çok fazla etkilenmediği durumlarla sınırlıdır.

Anahtar Kelimeler

• Yapboz yeniden birleştirme
• Şablon eşleştirme
• Yapboz
• Yapboz çözme

References

1. R. Li, S. Liu, G. Wang, G. Liu, and B. Zeng, JigsawGAN: Auxiliary learning for solving jigsaw puzzles with generative adversarial networks. IEEE Transactions on Image Processing, 31, 513–524, 2021. https://doi.org/10.1109/TIP.2021.3120052
2. I. Ahmad, S.-S. Hwang, and S. Shin, Determining jigsaw puzzle state from an image based on deep learning. Proceedings of 2022 International Conference on Artificial Intelligence in Information and Communication (ICAIIC), pp. 30–32, Jeju Island, Korea, 2022. https://doi.org/10.1109/ICAIIC54071.2022.9722672
3. X. Song, X. Yang, J. Ren, R. Bai, and X. Jiang, Solving jigsaw puzzle of large eroded gaps using puzzlet discriminant network. Proceedings of ICASSP 2023–IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 1–5, Rhodes Island, Greece, 2023. https://doi.org/10.1109/ICASSP49357.2023.10096300
4. S. Markaki and C. Panagiotakis, Jigsaw puzzle solving techniques and applications: a survey. The Visual Computer, 39, 4405–4421, 2023. https://doi.org/10.1007/s00371-022-02598-9
5. M. Makridis and N. Papamarkos, A new technique for solving puzzles. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 40, 789–797, 2009. https://doi.org/10.1109/TSMCB.2009.2029868
6. H. Wolfson, E. Schonberg, A. Kalvin, and Y. Lamdan, Solving jigsaw puzzles by computer. Annals of Operations Research, 12, 51–64, 1988. https://doi.org/10.1007/BF02186360
7. K. Zhang, W. Yu, M. Manhein, W. Waggenspack, and X. Li, 3D fragment reassembly using integrated template guidance and fracture-region matching. Proceedings of the IEEE International Conference on Computer Vision, pp. 2138–2146, Santiago, Chile, 2015.
8. K. Son, J. Hays, and D.B. Cooper, Solving square jigsaw puzzles with loop constraints. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 383–390, Portland, USA, 2013.

9. D.A. Kosiba, P.M. Devaux, S. Balasubramanian, T.L. Gandhi, and K. Kasturi, An automatic jigsaw puzzle solver. Proceedings of the 12th International Conference on Pattern Recognition (ICPR), pp. 616–618, Jerusalem, Israel, 1994. https://doi.org/10.1109/ICPR.1994.576377
10. M.-M. Paumard, D. Picard, and H. Tabia, Jigsaw puzzle solving using local feature co-occurrences in deep neural networks. Proceedings of the 25th IEEE International Conference on Image Processing (ICIP), pp. 1018–1022, Athens, Greece, 2018. https://doi.org/10.1109/ICIP.2018.8451094
11. P. Nagaraj, V. Muneeswaran, K. Muthamil Sudar, S. Hammed, D.L. Lokesh, and V.S. Simha Reddy, An exemplary template matching techniques for counterfeit currency detection. Proceedings of the Second International Conference on Image Processing and Capsule Networks (ICIPCN), pp. 370–378, Madurai, India, 2021. https://doi.org/10.1007/978-3-030-84760-9_32
12. A. Goshtasby, Template matching in rotated images. IEEE Transactions on Pattern Analysis and Machine Intelligence, PAMI-7(3), 338–344, 1985. https://doi.org/10.1109/TPAMI.1985.4767663
13. M.G. Chung, M.M. Fleck, and D.A. Forsyth, Jigsaw puzzle solver using shape and color. Proceedings of the Fourth International Conference on Signal Processing (ICSP), pp. 877–880, Beijing, China, 1998. https://doi.org/10.1109/ICOSP.1998.770951
14. A.C. Gallagher, Jigsaw puzzles with pieces of unknown orientation. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 382–389, Providence, USA, 2012. https://doi.org/10.1109/CVPR.2012.6247699
15. M.-M. Paumard, D. Picard, and H. Tabia, Deepzzle: Solving visual jigsaw puzzles with deep learning and shortest path optimization. IEEE Transactions on Image Processing, 29, 3569–3581, 2020. https://doi.org/10.1109/TIP.2020.2963378
16. D. Bridger, D. Danon, and A. Tal, Solving jigsaw puzzles with eroded boundaries. Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pp. 3526–3535, Seattle, USA, 2020.
17. D. Rika, D. Sholomon, E. David, and N.S. Netanyahu, TEN: Twin embedding networks for the jigsaw puzzle problem with eroded boundaries. arXiv preprint, arXiv:2203.06488, 2022. https://doi.org/10.48550/arXiv.2203.06488
18. Y. Chen, X. Shen, Y. Liu, Q. Tao, and J.A. Suykens, Jigsaw-ViT: Learning jigsaw puzzles in vision transformer. Pattern Recognition Letters, 166, 53–60, 2023. https://doi.org/10.1016/j.patrec.2022.12.023
19. M.-M. Paumard, H. Tabia, and D. Picard, Alphazzle: Jigsaw puzzle solver with deep Monte-Carlo tree search. arXiv preprint, arXiv:2302.00384, 2023. https://doi.org/10.48550/arXiv.2302.00384
20. C. Doersch, A. Gupta, and A.A. Efros, Unsupervised visual representation learning by context prediction. Proceedings of the IEEE International Conference on Computer Vision (ICCV), pp. 1422–1430, Santiago, Chile, 2015.
21. W. Yi and S. Marshall, Principal component analysis in application to object orientation. Geo-spatial Information Science, 3, 76–78, 2000. https://doi.org/10.1007/BF02826615
22. G. Bradski and A. Kaehler, OpenCV. Dr. Dobb’s Journal of Software Tools, 2000. https://www.drdobbs.com