Nash Meets Wertheimer: Using Good Continuation in Jigsaw Puzzles

• URL: http://arxiv.org/abs/2410.16857v1
• Date: Tue, 22 Oct 2024 09:46:09 GMT
• Title: Nash Meets Wertheimer: Using Good Continuation in Jigsaw Puzzles
• Authors: Marina Khoroshiltseva, Luca Palmieri, Sinem Aslan, Sebastiano Vascon, Marcello Pelillo,
• Abstract summary: 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.
• Score: 7.716132543734369
• License:
• Abstract: Jigsaw puzzle solving is a challenging task for computer vision since it requires high-level spatial and semantic reasoning. To solve the problem, existing approaches invariably use color and/or shape information but in many real-world scenarios, such as in archaeological fresco reconstruction, this kind of clues is often unreliable due to severe physical and pictorial deterioration of the individual fragments. This makes state-of-the-art approaches entirely unusable in practice. On the other hand, in such cases, simple geometrical patterns such as lines or curves offer a powerful yet unexplored clue. In an attempt to fill in this gap, in this paper we introduce a new challenging version of the puzzle solving problem in which one deliberately ignores conventional color and shape features and relies solely on the presence of linear geometrical patterns. The reconstruction process is then only driven by one of the most fundamental principles of Gestalt perceptual organization, namely Wertheimer's {\em law of good continuation}. In order to tackle this problem, we formulate the puzzle solving problem as the problem of finding a Nash equilibrium of a (noncooperative) multiplayer game and use classical multi-population replicator dynamics to solve it. The proposed approach is general and allows us to deal with pieces of arbitrary shape, size and orientation. We evaluate our approach on both synthetic and real-world data and compare it with state-of-the-art algorithms. The results show the intrinsic complexity of our purely line-based puzzle problem as well as the relative effectiveness of our game-theoretic formulation.

Related papers

• Disentangled Representation Learning with the Gromov-Monge Gap [65.73194652234848]
  Learning disentangled representations from unlabelled data is a fundamental challenge in machine learning. We introduce a novel approach to disentangled representation learning based on quadratic optimal transport. We demonstrate the effectiveness of our approach for quantifying disentanglement across four standard benchmarks.
  arXiv  Detail & Related papers  (2024-07-10T16:51:32Z)
• 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)
• A Data-dependent Approach for High Dimensional (Robust) Wasserstein Alignment [10.374243304018794]
  We propose an effective framework to compress the high dimensional geometric patterns. Our idea is inspired by the observation that high dimensional data often has a low intrinsic dimension. Our framework is a data-dependent'' approach that has the complexity depending on the intrinsic dimension of the input data.
  arXiv  Detail & Related papers  (2022-09-07T03:29:26Z)
• 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)
• 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)
• Multi-view 3D Reconstruction of a Texture-less Smooth Surface of Unknown Generic Reflectance [86.05191217004415]
  Multi-view reconstruction of texture-less objects with unknown surface reflectance is a challenging task. This paper proposes a simple and robust solution to this problem based on a co-light scanner.
  arXiv  Detail & Related papers  (2021-05-25T01:28:54Z)
• 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)
• Pictorial and apictorial polygonal jigsaw puzzles: The lazy caterer model, properties, and solvers [14.08706290287121]
  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.
  arXiv  Detail & Related papers  (2020-08-17T22:07:40Z)

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.