TEN: Twin Embedding Networks for the Jigsaw Puzzle Problem with Eroded Boundaries

• URL: http://arxiv.org/abs/2203.06488v1
• Date: Sat, 12 Mar 2022 17:18:47 GMT
• Title: TEN: Twin Embedding Networks for the Jigsaw Puzzle Problem with Eroded Boundaries
• Authors: Daniel Rika, Dror Sholomon, Eli David, Nathan S. Netanyahu
• Abstract summary: The jigsaw puzzle problem (JPP) is a well-known research problem, which has been studied for many years. Many effective CMs, which apply a simple distance measure, based merely on the information along the piece edges, have been proposed. However, the practicality of these classical methods is rather doubtful for problem instances harder than pure synthetic images. To overcome this significant deficiency, a few deep convolutional neural network (CNN)-based CMs have been recently introduced. The paper makes a significant first attempt at bridging the gap between the relatively low accuracy (of classical methods) and the intensive computational complexity (
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The jigsaw puzzle problem (JPP) is a well-known research problem, which has been studied for many years. Solving this problem typically involves a two-stage scheme, consisting of the computation of a pairwise piece compatibility measure (CM), coupled with a subsequent puzzle reconstruction algorithm. Many effective CMs, which apply a simple distance measure, based merely on the information along the piece edges, have been proposed. However, the practicality of these classical methods is rather doubtful for problem instances harder than pure synthetic images. Specifically, these methods tend to break down in more realistic scenarios involving, e.g., monochromatic puzzles, eroded boundaries due to piece degradation over long time periods, missing pieces, etc. To overcome this significant deficiency, a few deep convolutional neural network (CNN)-based CMs have been recently introduced. Despite their promising accuracy, these models are very computationally intensive. Twin Embedding Networks (TEN), to represent a piece with respect to its boundary in a latent embedding space. Combining this latent representation with a simple distance measure, we then demonstrate a superior performance, in terms of accuracy, of our newly proposed pairwise CM, compared to that of various classical methods, for the problem domain of eroded tile boundaries, a testbed for a number of real-world JPP variants. Furthermore, we also demonstrate that TEN is faster by a few orders of magnitude, on average, than the recent NN models, i.e., it is as fast as the classical methods. In this regard, the paper makes a significant first attempt at bridging the gap between the relatively low accuracy (of classical methods) and the intensive computational complexity (of NN models), for practical, real-world puzzle-like problems.

Related papers

• Sparsity May Cry: Let Us Fail (Current) Sparse Neural Networks Together! [100.19080749267316]
  "Sparsity May Cry" Benchmark (SMC-Bench) is a collection of carefully-curated 4 diverse tasks with 10 datasets. SMC-Bench is designed to favor and encourage the development of more scalable and generalizable sparse algorithms.
  arXiv  Detail & Related papers  (2023-03-03T18:47:21Z)
• A Comprehensively Improved Hybrid Algorithm for Learning Bayesian Networks: Multiple Compound Memory Erasing [0.0]
  This paper presents a new hybrid algorithm, MCME (multiple compound memory erasing) MCME retains the advantages of the first two methods, solves the shortcomings of the above CI tests, and makes innovations in the scoring function in the direction discrimination stage. A large number of experiments show that MCME has better or similar performance than some existing algorithms.
  arXiv  Detail & Related papers  (2022-12-05T12:52:07Z)
• Edge2Vec: A High Quality Embedding for the Jigsaw Puzzle Problem [0.0]
  Pairwise compatibility measure (CM) is a key component in solving the jigsaw puzzle problem (JPP) This paper derives an advanced CM model (based on modified embeddings and a new loss function, called hard batch triplet loss) for closing the gap between speed and accuracy.
  arXiv  Detail & Related papers  (2022-11-14T22:05:09Z)
• Graph Neural Networks for Propositional Model Counting [1.0152838128195467]
  Graph Networks (GNNs) have been recently leveraged to solve logical reasoning tasks. We present an architecture based on the GNN framework for belief propagation (BP) of Kuch et al., extended with self-attentive GNN and trained to approximately solve the #SAT problem.
  arXiv  Detail & Related papers  (2022-05-09T17:03:13Z)
• Provable Reinforcement Learning with a Short-Term Memory [68.00677878812908]
  We study a new subclass of POMDPs, whose latent states can be decoded by the most recent history of a short length $m$. In particular, in the rich-observation setting, we develop new algorithms using a novel "moment matching" approach with a sample complexity that scales exponentially. Our results show that a short-term memory suffices for reinforcement learning in these environments.
  arXiv  Detail & Related papers  (2022-02-08T16:39:57Z)
• Learning to Detect Critical Nodes in Sparse Graphs via Feature Importance Awareness [53.351863569314794]
  The critical node problem (CNP) aims to find a set of critical nodes from a network whose deletion maximally degrades the pairwise connectivity of the residual network. This work proposes a feature importance-aware graph attention network for node representation. It combines it with dueling double deep Q-network to create an end-to-end algorithm to solve CNP for the first time.
  arXiv  Detail & Related papers  (2021-12-03T14:23:05Z)
• DeFRCN: Decoupled Faster R-CNN for Few-Shot Object Detection [17.326702469604676]
  Few-shot object detection aims at detecting novel objects rapidly from extremely few examples of previously unseen classes. Most existing approaches employ the Faster R-CNN as basic detection framework. We propose a simple yet effective architecture named Decoupled Faster R-CNN (DeFRCN)
  arXiv  Detail & Related papers  (2021-08-20T06:12:55Z)
• DeepSplit: Scalable Verification of Deep Neural Networks via Operator Splitting [70.62923754433461]
  Analyzing the worst-case performance of deep neural networks against input perturbations amounts to solving a large-scale non- optimization problem. We propose a novel method that can directly solve a convex relaxation of the problem to high accuracy, by splitting it into smaller subproblems that often have analytical solutions.
  arXiv  Detail & Related papers  (2021-06-16T20:43:49Z)
• Learning to Accelerate Heuristic Searching for Large-Scale Maximum Weighted b-Matching Problems in Online Advertising [51.97494906131859]
  Bipartite b-matching is fundamental in algorithm design, and has been widely applied into economic markets, labor markets, etc. Existing exact and approximate algorithms usually fail in such settings due to either requiring intolerable running time or too much computation resource. We propose textttNeuSearcher which leverages the knowledge learned from previously instances to solve new problem instances.
  arXiv  Detail & Related papers  (2020-05-09T02:48:23Z)
• Seismic horizon detection with neural networks [62.997667081978825]
  This paper is an open-sourced research of applying binary segmentation approach to the task of horizon detection on multiple real seismic cubes with a focus on inter-cube generalization of the predictive model. The main contribution of this paper is an open-sourced research of applying binary segmentation approach to the task of horizon detection on multiple real seismic cubes with a focus on inter-cube generalization of the predictive model.
  arXiv  Detail & Related papers  (2020-01-10T11:30:50Z)

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.