Scalable Visual Instance Mining with Instance Graph

In this paper we address the problem of visual instance mining, which is to automatically
discover frequently appearing visual instances from a large collection of images.
We propose a scalable mining method by leveraging the graph structure with images as
vertices. Different from most existing work that focused on either instance-level similarities
or image-level context properties, our graph captures both information. The
instance-level information is integrated during the construction of a weighted and undirected
instance graph based on the similarity between augmented local features, while
the image-level context is explored with a greedy breadth-first search algorithm to discover
clusters of visual instances from the graph. This method is capable of mining
challenging small visual instances with diverse variations. We evaluated our method on
two fully annotated datasets and outperformed the state of the arts on both datasets with
higher recalls. We also applied our method on a one-million Flickr dataset and proved
its scalability.