Pictorial and apictorial polygonal jigsaw puzzles: The lazy caterer model, properties, and solvers

• URL: http://arxiv.org/abs/2008.07644v2
• Date: Thu, 16 Dec 2021 15:32:53 GMT
• Title: Pictorial and apictorial polygonal jigsaw puzzles: The lazy caterer model, properties, and solvers
• Authors: Peleg Harel and Ohad Ben-Shahar
• Abstract summary: We formalize a new type of jigsaw puzzle where the pieces are general convex polygons generated by cutting through a global polygonal shape/image with an arbitrary number of straight cuts. We analyze the theoretical properties of such puzzles, including the inherent challenges in solving them once pieces are contaminated with geometrical noise.
• Score: 14.08706290287121
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Jigsaw puzzle solving, the problem of constructing a coherent whole from a set of non-overlapping unordered visual fragments, is fundamental to numerous applications and yet most of the literature of the last two decades has focused thus far on less realistic puzzles whose pieces are identical squares. Here we formalize a new type of jigsaw puzzle where the pieces are general convex polygons generated by cutting through a global polygonal shape/image with an arbitrary number of straight cuts, a generation model inspired by the celebrated Lazy caterer's sequence. We analyze the theoretical properties of such puzzles, including the inherent challenges in solving them once pieces are contaminated with geometrical noise. To cope with such difficulties and obtain tractable solutions, we abstract the problem as a multi-body spring-mass dynamical system endowed with hierarchical loop constraints and a layered reconstruction process. We define evaluation metrics and present experimental results on both apictorial and pictorial puzzles to show that they are solvable completely automatically.

Related papers

• Re-assembling the past: The RePAIR dataset and benchmark for real world 2D and 3D puzzle solving [46.073519734119266]
  Our dataset has unique properties that are uncommon to current benchmarks for 2D and 3D puzzle solving. The fragments and fractures are realistic, caused by a collapse of a fresco during a World War II bombing at the Pompeii archaeological park. The dataset is multi-modal providing high resolution images with characteristic pictorial elements.
  arXiv  Detail & Related papers  (2024-10-31T15:10:38Z)
• Nash Meets Wertheimer: Using Good Continuation in Jigsaw Puzzles [7.716132543734369]
  Jigsaw puzzle solving is a challenging task for computer vision since it requires high-level spatial and semantic reasoning. We introduce a new challenging version of the puzzle solving problem in which one deliberately ignores conventional color and shape features. We evaluate our approach on both synthetic and real-world data and compare it with state-of-the-art algorithms.
  arXiv  Detail & Related papers  (2024-10-22T09:46:09Z)
• Multi-Phase Relaxation Labeling for Square Jigsaw Puzzle Solving [73.58829980121767]
  We present a novel method for solving square jigsaw puzzles based on global optimization. The method is fully automatic, assumes no prior information, and can handle puzzles with known or unknown piece orientation.
  arXiv  Detail & Related papers  (2023-03-26T18:53:51Z)
• Automated Graph Genetic Algorithm based Puzzle Validation for Faster Game Desig [69.02688684221265]
  This paper presents an evolutionary algorithm, empowered by expert-knowledge informeds, for solving logical puzzles in video games efficiently. We discuss multiple variations of hybrid genetic approaches for constraint satisfaction problems that allow us to find a diverse set of near-optimal solutions for puzzles.
  arXiv  Detail & Related papers  (2023-02-17T18:15:33Z)
• Video Anomaly Detection by Solving Decoupled Spatio-Temporal Jigsaw Puzzles [67.39567701983357]
  Video Anomaly Detection (VAD) is an important topic in computer vision. Motivated by the recent advances in self-supervised learning, this paper addresses VAD by solving an intuitive yet challenging pretext task. Our method outperforms state-of-the-art counterparts on three public benchmarks.
  arXiv  Detail & Related papers  (2022-07-20T19:49:32Z)
• GANzzle: Reframing jigsaw puzzle solving as a retrieval task using a generative mental image [15.132848477903314]
  We infer a mental image from all pieces, which a given piece can then be matched against avoiding the explosion. We learn how to reconstruct the image given a set of unordered pieces, allowing the model to learn a joint embedding space to match an encoding of each piece to the cropped layer of the generator. In doing so our model is puzzle size agnostic, in contrast to prior deep learning methods which are single size.
  arXiv  Detail & Related papers  (2022-07-12T16:02:00Z)
• Learning to Assemble Geometric Shapes [40.2815083025929]
  Assembling parts into an object is a problem that arises in a variety of contexts in the real world and involves numerous applications in science and engineering. Previous work tackles limited cases with identical unit parts or jigsaw-style parts of textured shapes. In this work, we introduce the more challenging problem of shape assembly, which involves textureless fragments of arbitrary shapes with indistinctive junctions.
  arXiv  Detail & Related papers  (2022-05-24T06:07:13Z)
• Relaxation Labeling Meets GANs: Solving Jigsaw Puzzles with Missing Borders [13.98838872235379]
  We propose JiGAN, a GAN-based method for solving Jigsaw puzzles with eroded or missing borders. 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.
  arXiv  Detail & Related papers  (2022-03-28T00:38:17Z)
• Graph Jigsaw Learning for Cartoon Face Recognition [79.29656077338828]
  It is difficult to learn a shape-oriented representation for cartoon face recognition with convolutional neural networks (CNNs) We propose the GraphJigsaw that constructs jigsaw puzzles at various stages in the classification network and solves the puzzles with the graph convolutional network (GCN) in a progressive manner. Our proposed GraphJigsaw consistently outperforms other face recognition or jigsaw-based methods on two popular cartoon face datasets.
  arXiv  Detail & Related papers  (2021-07-14T08:01:06Z)
• Non-Rigid Puzzles [50.213265511586535]
  We present a non-rigid multi-part shape matching algorithm. We assume to be given a reference shape and its multiple parts undergoing a non-rigid deformation. Experimental results on synthetic as well as real scans demonstrate the effectiveness of our method.
  arXiv  Detail & Related papers  (2020-11-26T00:32:30Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.