Matching Apictorial Puzzle Pieces Using Deep Learning
Abstract
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.
References
[2] 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.
[3] 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.
[4] 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.
[5] 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.
[6] Hoff, D., and Olver, P. Automatic solution of jigsaw puzzles. Journal of Mathematical Imaging and Vision 49 (05 2014).
[7] 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.
[8] Jampy, F., Hostein, A., Eric, F., Laligant, O., and Truchetet, F. 3d puzzle reconstruction for archeological fragments. Proceedings of SPIE - The International Society for Optical Engineering 9393 (03 2015).
[9] Kass Michael, Witkin Andrew, T. D. Snakes: Active contour models. International Journal of Computer Vision 1 (1988), 321–331.
[10] Kingma, D., and Ba, J. Adam: A method for stochastic optimization. International Conference on Learning Representations (12 2014).
[11] 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.
[12] Makridis, M., and Papamarkos, N. A new technique for solving a jigsaw puzzle. In 2006 International Conference on Image Processing (2006), pp. 2001–2004.
[13] Markaki, S., and Panagiotakis, C. Jigsaw puzzle solving techniques and applications: a survey. The Visual Computer 39, 10 (2023), 4405–4421.
[14] Ostertag, C., and Marie, B.-A. Matching ostraca fragments using a siamese neural network. Pattern Recognition Letters 131 (2020), 336–340.
[15] 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.
[16] 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.
[17] 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.
[18] 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.
[19] 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.
[20] Willis, A. R., and Cooper, D. B. Computational reconstruction of ancient artifacts. IEEE Signal Processing Magazine 25, 4 (2008), 65–83.
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
When the article is accepted for publication, I, as the author and representative of the coauthors, hereby agree to transfer to Studia Universitatis Babes-Bolyai, Series Informatica, all rights, including those pertaining to electronic forms and transmissions, under existing copyright laws, except for the following, which the author specifically retain: the right to make further copies of all or part of the published article for my use in classroom teaching; the right to reuse all or part of this material in a review or in a textbook of which I am the author; the right to make copies of the published work for internal distribution within the institution that employs me.
