TY  - JOUR
T1  - Jigsaw puzzle solving with template matching
TT  - Şablon eşleştirme ile yapboz çözme
AU  - Uçar, Kürşad
PY  - 2025
DA  - October
Y2  - 2025
DO  - 10.28948/ngumuh.1641237
JF  - Niğde Ömer Halisdemir Üniversitesi Mühendislik Bilimleri Dergisi
JO  - NÖHÜ Müh. Bilim. Derg.
PB  - Niğde Ömer Halisdemir Üniversitesi
WT  - DergiPark
SN  - 2564-6605
SP  - 1559
EP  - 1570
VL  - 14
IS  - 4
LA  - en
AB  - 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.
KW  - Puzzle reassembly
KW  - Template matching
KW  - Jigsaw puzzle
KW  - Puzzle solving
N2  - 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.
CR  - 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
CR  - 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
CR  - 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
CR  - 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
CR  - 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
CR  - 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
CR  - 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.
CR  - 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.
CR  - 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
CR  - 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
CR  - 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
CR  - 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
CR  - 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
CR  - 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
CR  - 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
CR  - 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.
CR  - 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
CR  - 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
CR  - 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
CR  - 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.
CR  - 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
CR  - G. Bradski and A. Kaehler, OpenCV. Dr. Dobb’s Journal of Software Tools, 2000. https://www.drdobbs.com
UR  - https://doi.org/10.28948/ngumuh.1641237
L1  - https://dergipark.org.tr/tr/download/article-file/4615774
ER  -