Near Duplicate Image Detection: min-Hash and tf-idf Weighting

By Ondřej Chum, James Philbin, Andrew Zisserman. 2008

522 citations recorded by the source corpus.

This paper proposes two novel image similarity measures for fast indexing via locality sensitive hashing. The similarity measures are applied and evaluated in the context of near duplicate image detection. The proposed method uses a visual vocabulary of vector quantized local feature descriptors (SIFT) and for retrieval exploits enhanced min-Hash techniques. Standard min-Hash uses an approximate set intersection between document descriptors was used as a similarity measure. We propose an efficient way of exploiting more sophisticated similarity measures that have proven to be essential in image / particular object retrieval. The proposed similarity measures do not require extra computational effort compared to the original measure. We focus primarily on scalability to very large image and video databases, where fast query processing is necessary. The method requires only a small amount of data need be stored for each image. We demonstrate our method on the TrecVid 2006 data set which contains approximately 146K key frames, and also on challenging the University of Kentucky image retrieval database.

Subfields: Computer Vision and Pattern Recognition

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Vision and Pattern Recognition

Citations in the corpus

Aggregating Local Image Descriptors into Compact Codes (2012, methodology): “The efficiency problem was partially addressed by the min-Hash approach [13], [14] and the prefiltering method of Torresani et al.”
Image ranking based on user browsing behavior (2012, background): “A number of alternatives has been explored to improve the result of the Web ranking task, including visual diversification [28, 31], near duplicate detection [8], query expansion [12], visual position [7], faceted detection [29], and re-rank based on click data [13].”
Large-scale image retrieval with compressed Fisher vectors (2010, background): “[3] [5] propose to apply min-hash to binary vectors.”
Scalar quantization for large scale image search (2012, methodology): “To further reduce the memory cost of inverted file structure, a visual word vector is mapped to a low-dimensional representation by a group of min-hash functions [18] [19].”
Canu: scalable and accurate long-read assembly via adaptive k-mer weighting and repeat separation (2016, methodology): “Mostchromosomesareinlessthanthreecontigs,indicatingstructuralagreementwiththereference. use in the natural language field and other MinHash applications (Chum et al. 2008).”
Guilt by association: large scale malware detection by mining file-relation graphs (2014, background): “MinHashing has been proven to work well for large scale real-world applications, such as detecting duplicate images [8] and clustering users on Google news [10].”
Learning to Hash for Indexing Big Data—A Survey (2015, methodology): “By converting rank lists to a triplet tensor matrix, listwise hashing is designed to preserve the ranking in the Hamming space [76].”
Packing bag-of-features (2009, methodology): “85 obtained in [2] for 512 “sketches”, that require an order of magnitude more memory.”
Learning query-dependent prefilters for scalable image retrieval (2009, methodology): “Either the original quantization is generated using a large W , or a new vocabulary of metawords (“phrases” [21], “configurations” [20, 19], “min-hashes” [1, 2], “triplets” [23]) is defined.”
Ranking consistency for image matching and object retrieval (2014, background): “To address issue (ii), many retrieval systems apply fast computation of similarity measure between query/response image pairs, e.g. the dotproduct similarity of the weighted BoW representations [1,5], or approximate similarity measures [6].”
Kernelized locality-sensitive hashing for scalable image search (2009, background): “Vision researchers have shown the effectiveness of this class of methods for various image searc h applications, including shape matching, pose inference, a nd bag-of-words indexing [25, 24, 12, 16, 4].”
Geometric min-Hashing: Finding a (thick) needle in a haystack (2009, background): “A brief overview of the min-Hash algorithm follows; for detailed description see [2, 7].”
Evaluation of GIST descriptors for web-scale image search (2009, methodology): “Another strategy is to use approximate search, as done in [7] by using a two-level inverted file structure or in [2] using min-Hash.”
Discriminative Orderlet Mining for Real-Time Recognition of Human-Object Interaction (2014, methodology): “Order representation has been successfully employed in image indexing and searching [2][3].”
Hello neighbor: Accurate object retrieval with k-reciprocal nearest neighbors (2011, methodology): “As can be seen by the green lines in Figures 6,7,8,9,10 this gives an improvement on all datasets for small k .”
Spherical hashing (2012, methodology): “This technique is extended to various hashing functions [3, 1, 13, 2, 20].”
Hashing for Similarity Search: A Survey (2014, methodology): “LSH, as a probabilistic dimension reduction method, has been used in various CV applications which often reduce to approximate nearest neighbor search [17], [18].”