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.

我们提出了一种用于新颖图像发现的快速、无需训练的算法，该算法将图像集合构建成一个知觉距离加权图，通过解决 K - 稀疏特征向量问题，在显著降低内存占用的同时，能够更准确地挖掘新颖图像。