Skip to main content
SpringerLink
Log in

Relaxation Labeling Meets GANs: Solving Jigsaw Puzzles with Missing Borders

  • Conference paper
  • First Online:
Image Analysis and Processing – ICIAP 2022 (ICIAP 2022)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 13233))

Included in the following conference series:

  • 1222 Accesses

Abstract

This paper proposes JiGAN, a GAN-based method for solving Jigsaw puzzles with eroded or missing borders. Missing borders is a common real-world situation, for example, when dealing with the reconstruction of broken artifacts or ruined frescoes. In this particular condition, the puzzle’s pieces do not align perfectly due to the borders’ gaps; in this situation, the patches’ direct match is unfeasible due to the lack of color and line continuations. JiGAN, is a two-steps procedure that tackles this issue: first, we repair the eroded borders with a GAN-based image extension model and measure the alignment affinity between pieces; then, we solve the puzzle with the relaxation labeling algorithm to enforce consistency in pieces positioning, hence, reconstructing the puzzle. We test the method on a large dataset of small puzzles and on three commonly used benchmark datasets to demonstrate the feasibility of the proposed approach.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution
Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 69.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 89.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Notes

  1. 1.

    Pretrained Boundless model from TensowrflowHub.

References

  1. Andaló, F.A., Taubin, G., Goldenstein, S.: PSQP: puzzle solving by quadratic programming. IEEE TPAMI 39(2), 385–396 (2017)

    Article  Google Scholar 

  2. Barnes, C., Shechtman, E., Finkelstein, A., Goldman, D.B.: PatchMatch: a randomized correspondence algorithm for structural image editing. ACM Trans. Graph. (Proc. SIGGRAPH) 28(3) (2009)

    Google Scholar 

  3. Brandão, S., Marques, M.: Hot tiles: a heat diffusion based descriptor for automatic tile panel assembly. In: Hua, G., Jégou, H. (eds.) ECCV 2016. LNCS, vol. 9913, pp. 768–782. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-46604-0_53

    Chapter  Google Scholar 

  4. Bridger, D., Danon, D., Tal, A.: Solving jigsaw puzzles with eroded boundaries (2019)

    Google Scholar 

  5. Cho, T.S., Avidan, S., Freeman, W.T.: A probabilistic image jigsaw puzzle solver. In: Proceedings of CVPR, pp. 183–190 (2010)

    Google Scholar 

  6. Clevert, D.A., Unterthiner, T., Hochreiter, S.: Fast and accurate deep network learning by exponential linear units (ELUs) (2016)

    Google Scholar 

  7. Deever, A., Gallagher, A.: Semi-automatic assembly of real cross-cut shredded documents. In: Proceedings of ICIP, pp. 233–236 (2012)

    Google Scholar 

  8. Demaine, E.D., Demaine, M.L.: Jigsaw puzzles, edge matching, and polyomino packing: Connections and complexity. Graphs Comb. 23(Suppl. 1), 195–208 (2007)

    Article  MathSciNet  Google Scholar 

  9. Derech, N., Tal, A., Shimshoni, I.: Solving archaeological puzzles. CoRR abs/1812.10553 (2018)

    Google Scholar 

  10. Gallagher, A.C.: Jigsaw puzzles with pieces of unknown orientation. In: Proceedings of CVPR, pp. 382–389 (2012)

    Google Scholar 

  11. Gur, S., Ben-Shahar, O.: From square pieces to brick walls: the next challenge in solving jigsaw puzzles. In: ICCV, pp. 4029–4037 (2017)

    Google Scholar 

  12. Hummel, R.A., Zucker, S.W.: On the foundations of relaxation labeling processes. IEEE TPAMI 5(3), 267–287 (1983)

    Article  Google Scholar 

  13. Khoroshiltseva, M., Vardi, B., Torcinovich, A., Traviglia, A., Ben-Shahar, O., Pelillo, M.: Jigsaw puzzle solving as a consistent labeling problem. In: Tsapatsoulis, N., Panayides, A., Theocharides, T., Lanitis, A., Pattichis, C., Vento, M. (eds.) CAIP 2021. LNCS, vol. 13053, pp. 392–402. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-89131-2_36

    Chapter  Google Scholar 

  14. Li, D., Yang, Y., Song, Y.Z., Hospedales, T.M.: Deeper, broader and artier domain generalization. In: Proceedings of the IEEE International Conference on Computer Vision (ICCV), October 2017

    Google Scholar 

  15. Li, R., Liu, S., Wang, G., Liu, G., Zeng, B.: Jigsawgan: self-supervised learning for solving jigsaw puzzles with generative adversarial networks. CoRR abs/2101.07555 (2021)

    Google Scholar 

  16. van den Oord, A., Kalchbrenner, N., Kavukcuoglu, K.: Pixel recurrent neural networks (2016)

    Google Scholar 

  17. Paikin, G., Tal, A.: Solving multiple square jigsaw puzzles with missing pieces. In: Proceedings of CVPR, pp. 4832–4839 (2015)

    Google Scholar 

  18. Paumard, M., Picard, D., Tabia, H.: Deepzzle: solving visual jigsaw puzzles with deep learning and shortest path optimization. CoRR abs/2005.12548 (2020)

    Google Scholar 

  19. Pelillo, M.: The dynamics of nonlinear relaxation labeling processes. J. Math. Imag. Vis. 7(4), 309–323 (1997)

    Article  MathSciNet  Google Scholar 

  20. Pomeranz, D., Shemesh, M., Ben-Shahar, O.: A fully automated greedy square jigsaw puzzle solver. In: Proceedings of CVPR, pp. 9–16 (2011)

    Google Scholar 

  21. Rosenfeld, A., Hummel, R.A., Zucker, S.W.: Scene labeling by relaxation operations. IEEE Trans. Syst. Man Cybern. 6, 420–433 (1976)

    Article  MathSciNet  Google Scholar 

  22. Sholomon, D., David, O.E., Netanyahu, N.S.: A generalized genetic algorithm-based solver for very large jigsaw puzzles of complex types. In: Proceedings of AAAI, pp. 2839–2845 (2014)

    Google Scholar 

  23. Sinkhorn, R., Knopp, P.: Concerning nonnegative matrices and doubly stochastic matrices. Pacific J. Math. 21(2), 343–348 (1967)

    Article  MathSciNet  Google Scholar 

  24. Son, K., Hays, J., Cooper, D.B.: Solving square jigsaw puzzle by hierarchical loop constraints. IEEE TPAMI 41(9), 2222–2235 (2018)

    Article  Google Scholar 

  25. Teterwak, P., et al.: Boundless: generative adversarial networks for image extension (2019)

    Google Scholar 

  26. Yu, J., Lin, Z., Yang, J., Shen, X., Lu, X., Huang, T.: Free-form image inpainting with gated convolution (2019)

    Google Scholar 

  27. Zhao, F., et al.: A jigsaw puzzle inspired algorithm for solving large-scale no-wait flow shop scheduling problems. Appl. Intell. 50(1), 87–100 (2019). https://doi.org/10.1007/s10489-019-01497-2

    Article  Google Scholar 

  28. Zhou, B., Lapedriza, A., Khosla, A., Oliva, A., Torralba, A.: Places: a 10 million image database for scene recognition. IEEE Trans. Pattern Anal. Mach. Intell. 40(6), 1452–1464 (2018). https://doi.org/10.1109/tpami.2017.2723009

    Article  Google Scholar 

Download references

Acknowledgements

This work has received funding from the European Union’s Horizon 2020 research and innovation programme under grant agreement No 964854.

Author information

Authors and Affiliations

  1. Università Ca’ Foscari, Dorsoduro 3246, 30123, Venice, Italy

    Marina Khoroshiltseva, Arianna Traviglia, Marcello Pelillo & Sebastiano Vascon

  2. Istituto Italiano di Tecnologia, CCHT, Via Torino 155, 30100, Mestre, Venice, Italy

    Marina Khoroshiltseva, Arianna Traviglia, Marcello Pelillo & Sebastiano Vascon

Authors
  1. Marina Khoroshiltseva
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Arianna Traviglia
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Marcello Pelillo
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Sebastiano Vascon
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Sebastiano Vascon .

Editor information

Editors and Affiliations

  1. Boston University, Boston, MA, USA

    Stan Sclaroff

  2. National Research Council, Lecce, Italy

    Cosimo Distante

  3. National Research Council, Lecce, Italy

    Marco Leo

  4. University of Catania, Catania, Italy

    Giovanni M. Farinella

  5. Technische Universität München, Garching, Germany

    Federico Tombari

Rights and permissions

Reprints and permissions

Copyright information

© 2022 The Author(s), under exclusive license to Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Khoroshiltseva, M., Traviglia, A., Pelillo, M., Vascon, S. (2022). Relaxation Labeling Meets GANs: Solving Jigsaw Puzzles with Missing Borders. In: Sclaroff, S., Distante, C., Leo, M., Farinella, G.M., Tombari, F. (eds) Image Analysis and Processing – ICIAP 2022. ICIAP 2022. Lecture Notes in Computer Science, vol 13233. Springer, Cham. https://doi.org/10.1007/978-3-031-06433-3_3

Download citation

  • DOI: https://doi.org/10.1007/978-3-031-06433-3_3

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-031-06432-6

  • Online ISBN: 978-3-031-06433-3

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation