ADS: Approximate Densest Subgraph for Novel Image Discovery
This addresses the need for a lightweight tool to discover unique images in growing repositories, though it appears incremental as it builds on existing graph-based methods with efficiency improvements.
The paper tackles the problem of discovering distinct images from large repositories by proposing a fast, training-free algorithm that formulates the task as finding the K-densest subgraph in a perceptual distance-weighted graph, and it shows the algorithm is considerably faster with smaller memory footprint while mining novel images more accurately compared to state-of-the-art methods.
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.