ADS: Approximate Densest Subgraph for Novel Image Discovery

• URL: http://arxiv.org/abs/2402.08743v1
• Date: Tue, 13 Feb 2024 19:27:34 GMT
• Title: ADS: Approximate Densest Subgraph for Novel Image Discovery
• Abstract summary: We propose a fast and training-free algorithm for novel image discovery. The key of our algorithm is formulating a collection of images as a distance-weighted graph, within which our task is to locate the K-densest subgraph. We show that it is considerably faster to run with a smaller memory footprint while able to mine novel images more accurately.
• Score: 1.7839986996686323
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The volume of image repositories continues to grow. Despite the availability of content-based addressing, we still lack a lightweight tool that allows us to discover images of distinct characteristics from a large collection. In this paper, we propose a fast and training-free algorithm for novel image discovery. The key of our algorithm is formulating a collection of images as a perceptual distance-weighted graph, within which our task is to locate the K-densest subgraph that corresponds to a subset of the most unique images. While solving this problem is not just NP-hard but also requires a full computation of the potentially huge distance matrix, we propose to relax it into a K-sparse eigenvector problem that we can efficiently solve using stochastic gradient descent (SGD) without explicitly computing the distance matrix. We compare our algorithm against state-of-the-arts on both synthetic and real datasets, showing that it is considerably faster to run with a smaller memory footprint while able to mine novel images more accurately.

Related papers

• Image Understanding Makes for A Good Tokenizer for Image Generation [62.875788091204626]
  We introduce a token-based IG framework, which relies on effective tokenizers to project images into token sequences. We show that tokenizers with strong IU capabilities achieve superior IG performance across a variety of metrics, datasets, tasks, and proposal networks.
  arXiv  Detail & Related papers  (2024-11-07T03:55:23Z)
• A Mirror Descent-Based Algorithm for Corruption-Tolerant Distributed Gradient Descent [57.64826450787237]
  We show how to analyze the behavior of distributed gradient descent algorithms in the presence of adversarial corruptions. We show how to use ideas from (lazy) mirror descent to design a corruption-tolerant distributed optimization algorithm. Experiments based on linear regression, support vector classification, and softmax classification on the MNIST dataset corroborate our theoretical findings.
  arXiv  Detail & Related papers  (2024-07-19T08:29:12Z)
• ZeroSearch: Local Image Search from Text with Zero Shot Learning [0.0]
  This paper presents a solution that utilizes zero shot learning to create image queries with only user provided text descriptions. The paper's primary contribution is the development of an algorithm that utilizes pre-trained models to extract features from images. The algorithm's output is a list of images sorted in descending order of similarity, helping users to locate specific images more efficiently.
  arXiv  Detail & Related papers  (2023-05-01T08:27:24Z)
• {\mu}Split: efficient image decomposition for microscopy data [50.794670705085835]
  muSplit is a dedicated approach for trained image decomposition in the context of fluorescence microscopy images. We introduce lateral contextualization (LC), a novel meta-architecture that enables the memory efficient incorporation of large image-context. We apply muSplit to five decomposition tasks, one on a synthetic dataset, four others derived from real microscopy data.
  arXiv  Detail & Related papers  (2022-11-23T11:26:24Z)
• Fast Key Points Detection and Matching for Tree-Structured Images [4.929206987094714]
  This paper offers a new authentication algorithm based on image matching of nano-resolution visual identifiers with tree-shaped patterns. The proposed algorithm is applicable to a variety of tree-structured image matching, but our focus is on dendrites, recently-developed visual identifiers.
  arXiv  Detail & Related papers  (2022-11-07T00:22:56Z)
• Cherry-Picking Gradients: Learning Low-Rank Embeddings of Visual Data via Differentiable Cross-Approximation [53.95297550117153]
  We propose an end-to-end trainable framework that processes large-scale visual data tensors by looking emphat a fraction of their entries only. The proposed approach is particularly useful for large-scale multidimensional grid data, and for tasks that require context over a large receptive field.
  arXiv  Detail & Related papers  (2021-05-29T08:39:57Z)
• UltraSR: Spatial Encoding is a Missing Key for Implicit Image Function-based Arbitrary-Scale Super-Resolution [74.82282301089994]
  In this work, we propose UltraSR, a simple yet effective new network design based on implicit image functions. We show that spatial encoding is indeed a missing key towards the next-stage high-accuracy implicit image function. Our UltraSR sets new state-of-the-art performance on the DIV2K benchmark under all super-resolution scales.
  arXiv  Detail & Related papers  (2021-03-23T17:36:42Z)
• Image Retrieval for Structure-from-Motion via Graph Convolutional Network [13.040952255039702]
  We present a novel retrieval method based on Graph Convolutional Network (GCN) to generate accurate pairwise matches without costly redundancy. By constructing a subgraph surrounding the query image as input data, we adopt a learnable GCN to exploit whether nodes in the subgraph have overlapping regions with the query photograph. Experiments demonstrate that our method performs remarkably well on the challenging dataset of highly ambiguous and duplicated scenes.
  arXiv  Detail & Related papers  (2020-09-17T04:03:51Z)
• Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
  We introduce a novel learning problem for dense subgraph discovery. We first propose a edge-time algorithm that obtains a nearly-optimal solution with high probability. We then design a more scalable algorithm with a theoretical guarantee.
  arXiv  Detail & Related papers  (2020-06-24T11:37:33Z)
• A Survey on Patch-based Synthesis: GPU Implementation and Optimization [0.0]
  This thesis surveys the research in patch-based synthesis and algorithms for finding correspondences between small local regions of images. One of the algorithms we have studied is PatchMatch, can find similar regions or "patches" of an image one to two orders of magnitude faster than previous techniques. In computer graphics, we have explored removing unwanted objects from images, seamlessly moving objects in images, changing image aspect ratios, and video summarization.
  arXiv  Detail & Related papers  (2020-05-11T19:25:28Z)

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.