Geometric min-Hashing: Finding a (thick) needle in a haystack

By Ondřej Chum, Michal Perdoch, Jiri Matas. 2009

289 citations recorded by the source corpus.

We propose a novel hashing scheme for image retrieval, clustering and automatic object discovery. Unlike commonly used bag-of-words approaches, the spatial extent of image features is exploited in our method. The geometric information is used both to construct repeatable hash keys and to increase the discriminability of the description. Each hash key combines visual appearance (visual words) with semi-local geometric information. Compared with the state-of-the-art min-hash, the proposed method has both higher recall (probability of collision for hashes on the same object) and lower false positive rates (random collisions). The advantages of geometric min-hashing approach are most pronounced in the presence of viewpoint and scale change, significant occlusion or small physical overlap of the viewing fields. We demonstrate the power of the proposed method on small object discovery in a large unordered collection of images and on a large scale image clustering problem.

Subfields: Aerospace Engineering, Computer Vision and Pattern Recognition, Information Retrieval & Search

How researchers see this paper

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

In Aerospace Engineering

In Computer Vision and Pattern Recognition

In Information Retrieval & Search

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.”
Unsupervised Visual Representation Learning by Context Prediction (2015, background): “Finally, a number of works focus on geometry as a method for verifying links between images [5, 36, 19].”
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].”
Iterative quantization: A procrustean approach to learning binary codes (2011, background): “Encoding high-dimensional image descriptors as compact binary strings can enable large efficiency gains in storage and computation speed for similarity search, and it can be accomplished with much simpler data structures and algorithms than alternative large-scale indexing methods [3, 7, 9, 10].”
Aggregating local descriptors into a compact image representation (2010, methodology): “The efficiency problem was partially addressed by the min-Hash approach [2, 3] and the method of Torresani et al.”
Image webs: Computing and exploiting connectivity in image collections (2010, methodology): “Content-Based Image Retrieval (CBIR) techniques based on Bag-of-Visual-Words models [13], global image descriptors [16] or geometric min-hashing [5] have been used to quickly ﬁlter out many images that are unlikely to match.”
Visual landmark recognition from Internet photo collections: A large-scale evaluation (2014, methodology): “ution of object categories (Fig.3a) shows that, not surprisingly, Landmark Buildings from the largest category, followed by Sculptures, Panoramas and Paintings. Seed-based object discovery algorithms [5,24,49] ﬁnd the most photographed objects ﬁrst, because when drawing a random image from an Intern”
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].”
Ranking consistency for image matching and object retrieval (2014, background): “Recently, there has been a great deal of research to increase the accuracy of object retrieval by measuring the spatial consistency between the query and result images [5,11,12].”
Avoiding Confusing Features in Place Recognition (2010, background): “Community photo-collections (such as Flickr) are now often used in computer vision tasks with the focus on clustering [20, 21, 5], 3D modelling [9, 7] and summarization [22].”
VocMatch: Efficient Multiview Correspondence for Structure from Motion (2014, unknown): “5% of the detected features in an image, which corresponds to what was observed in [2].”
Revisiting Oxford and Paris: Large-Scale Image Retrieval Benchmarking (2018, methodology): “Methods based on local invariant features [25, 26] and the Bag-of-Words (BoW) model [41, 33, 7, 34, 6, 27, 47, 4, 52, 54, 42] were dominating the field of image retrieval until the advent of CNN-based approaches [38, 3, 48, 20, 1, 10, 37, 28, 51].”
Visual Place Recognition with Repetitive Structures (2015, background): “Examples include: (i) learning better visual vocabularies [21, 28]; (ii) developing quantization methods less prone to quantization errors [14, 27, 44]; (iii) combining returns from multiple query images depicting the same scene [4, 6]; (iv) exploiting the 3D or graph structure of the database [11, ”
Recent developments in large-scale tie-point matching (2016, background): “Condition (i), which rejects only a negligible fraction of feature points thanks to the extremely fine quantization [6], ensures a one-to-many mapping from words to images, so that no ambiguities remain that would have to”
Image Classification and Retrieval are ONE (2015, methodology): “Popular post-processing approaches include geometric veriﬁcation [8], query expansion [9] and diﬀusion-based algorithms [23][60].”
Image retrieval with geometry-preserving visual phrases (2011, methodology): “While they consider local co-occurrences [ 3 ] or global co-occurrences [2], we encode more spatial information.”
SIFT Meets CNN: A Decade Survey of Instance Retrieval (2016, background): “r pipelines. For keypoint-based methods, the spatial context among the local features is important to discriminative target objects from others, especially in cases of rigid objects. Examples include [118], [119], [120]. Other effective methods include burstiness handling [77] (discussed in Section3”