Min-hash sketch construction via nonparametric clustering

In partial duplicate image retrieval systems, min-Hash algorithms are widely used because of its high efficiency and robustness. In most of min-Hash algorithms, min-Hash functions are considered independent and grouped into tuples called sketches, the discriminative power of sketches are limited. By modeling correlations of min-Hash functions, we propose a novel sketch construction method called Nonpara-metric Clustering min-Hash (NCmH). In NCmH, the randomly generated min-Hash functions are clustered before grouping them into sketches, while spatial information is fully used in this process. The constructed sketches preserve abundant spatial information between visual words, thus NCmH achieves higher retrieval accuracy compared to the standard min-Hash. Furthermore, our method can be combined with other min-Hash algorithms such as GVP mH [1], PmH [2] and TmH [3] to further improve accuracy. In experiments, we show that our method outperforms the standard min-Hash and improves the state-of-the-art min-Hash algorithm on Oxford 5K dataset and University of Kentucky dataset.