Fast Image Retrieval: Query Pruning and Early Termination

Efficiency is of great importance for image retrieval systems. For this pragmatic issue, this paper proposes a fast image retrieval framework to speed up the online retrieval process. To this end, an impact score for local features is proposed in the first place, which considers multiple properties of a local feature, including TF-IDF, scale, saliency, and ambiguity. Then, to decrease memory consumption, the impact score is quantized to an integer, which leads to a novel inverted index organization, called Q-Index. Importantly, based on the impact score, two closely complementary strategies are introduced: query pruning and early termination. On one hand, query pruning discards less important features in the query. On the other hand, early termination visits indexed features only with high impact scores, resulting in the partial traversing of the inverted index. Our approach is tested on two benchmark datasets populated with an additional 1 million images to account as negative examples. Compared with full traversal of the inverted index, we show that our system is capable of visiting less than 10% of the “should-visit” postings, thus achieving a significant speed-up in query time while providing competitive retrieval accuracy.