Matching Apictorial Puzzle Pieces Using Deep Learning
DOI:
https://doi.org/10.24193/subbi.2024.1.01Keywords:
U-Net, Siamese architecture, Edge-matching, Puzzle PiecesAbstract
Finding matches between puzzle pieces is a difficult problem relevant to applications that involve restoring broken objects. The main difficulty comes from the similarity of the puzzle pieces and the very small difference between a pair of pieces that almost match and one that does. The proposed solution is based on deep learning models and has two steps: firstly, the pieces are segmented from images with a U-Net model; then, matches are found with a Siamese Neural Network. To reach our goal, we created our own dataset, containing 462 images and just as many masks. With these masks, we built 3318 pairs of images, half of them representing pieces that fit together and half that do not. Our most relevant result is estimating correctly for 290 out of 332 pairs whether they match.
Received by the editors: 23 October 2023.
2010 Mathematics Subject Classification. 68T45, 68U10.
1998 CR Categories and Descriptors. I.2.10 Artificial Intelligence: Vision and Scene Understanding – Shape; I.4.6 Image Processing and Computer Vision: Segmentation – Edge and feature detection.
References
Alagrami, A., Palmieri, L., Aslan, S., Pelillo, M., and Vascon, S. Reassembling broken objects using breaking curves, 06 2023.
Biswas, A., Bhowmick, P., and Bhattacharya, B. Reconstruction of torn documents using contour maps. In IEEE International Conference on Image Processing 2005 (2005), vol. 3, pp. III–517.
Bromley, J., Bentz, J., Bottou, L., Guyon, I., Lecun, Y., Moore, C., Sackinger, E., and Shah, R. Signature verification using a "siamese" time delay neural network. International Journal of Pattern Recognition and Artificial Intelligence 7 (08 1993), 25.
Dey, S., Dutta, A., Toledo, J. I., Ghosh, S. K., Llados, J., and Pal, U. Signet: Convolutional siamese network for writer independent offline signature verification, 2017.
Grim, A., O’Connor, T., Olver, P., Shakiban, C., Slechta, R., and Thompson, R. Automatic reassembly of three-dimensional jigsaw puzzles. International Journal of Image and Graphics 16 (04 2016), 1650009.
Hoff, D., and Olver, P. Automatic solution of jigsaw puzzles. Journal of Mathematical Imaging and Vision 49 (05 2014).
Illig, P., Thompson, R., and Yu, Q. Application of integral invariants to apictorial jigsaw puzzle assembly. Journal of Mathematical Imaging and Vision 65 (2021), 340– 353.
Jampy, F., Hostein, A., Eric, F., Laligant, O., and Truchetet, F. 3d puzzle reconstruction for archaeological fragments. Proceedings of SPIE - The International Society for Optical Engineering 9393 (03 2015).
Kass Michael, Witkin Andrew, T. D. Snakes: Active contour models. International Journal of Computer Vision 1 (1988), 321–331.
Kingma, D., and Ba, J. Adam: A method for stochastic optimization. International Conference on Learning Representations (12 2014).
Li, R., Liu, S., Wang, G., Liu, G., and Zeng, B. Jigsawgan: Auxiliary learning for solving jigsaw puzzles with generative adversarial networks. IEEE Transactions on Image Processing 31 (2022), 513–524.
Makridis, M., and Papamarkos, N. A new technique for solving a jigsaw puzzle. In 2006 International Conference on Image Processing (2006), pp. 2001–2004.
Markaki, S., and Panagiotakis, C. Jigsaw puzzle solving techniques and applications: a survey. The Visual Computer 39, 10 (2023), 4405–4421.
Ostertag, C., and Marie, B.-A. Matching ostraca fragments using a siamese neural network. Pattern Recognition Letters 131 (2020), 336–340.
Papaioannou, G., Schreck, T., Andreadis, A., Mavridis, P., Gregor, R., Sipiran, I., and Vardis, K. From reassembly to object completion: A complete systems pipeline. ACM Journal on Computing and Cultural Heritage 10 (2017), 8:1–8:22.
Paszke, A., Gross, S., Massa, F., Lerer, A., Bradbury, J., Chanan, G., Killeen, T., Lin, Z., Gimelshein, N., Antiga, L., Desmaison, A., Kopf, A., Yang, E., DeVito, Z., Raison, M., Tejani, A., Chilamkurthy, S., Steiner, B.,
Fang, L., Bai, J., and Chintala, S. Pytorch: Crossentropyloss. https://pytorch.org/docs/stable/generated/torch.nn.CrossEntropyLoss.html, 2021.
Pintus, R., Pal, K., Yang, Y., Weyrich, T., Gobbetti, E., and Rushmeier, H. A survey of geometric analysis in cultural heritage. Computer Graphics Forum 35, 1 (2016), 4–31.
Pirrone, A., Aimar, M. B., and Journet, N. Papy-s-net: A siamese network to match papyrus fragments. In Proceedings of the 5th International Workshop on Historical Document Imaging and Processing (New York, NY, USA, 2019), HIP ’19, Association for Computing Machinery, pp. 78–83.
Ronneberger, O., P.Fischer, and Brox, T. U-net: Convolutional networks for biomedical image segmentation. In Medical Image Computing and Computer-Assisted Intervention (MICCAI) (2015), vol. 9351 of LNCS, Springer, pp. 234–241.
Willis, A. R., and Cooper, D. B. Computational reconstruction of ancient artifacts. IEEE Signal Processing Magazine 25, 4 (2008), 65–83.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2024 Studia Universitatis Babeș-Bolyai Informatica
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
