A Filter of Minhash for Image Similarity Measures

Jun Long, Qunfeng Liu, Xinpan Yuan, Chengyuan Zhang, Junfeng Liu

TL;DR

This paper introduces a novel "dynamic threshold filter" for Minwise Hashing, significantly speeding up image similarity searches by intelligently terminating comparisons. By setting adaptive lower and upper thresholds at intermediate comparison points, the filter can predict whether image pairs are likely to exceed a similarity threshold, thus avoiding unnecessary computations.

What Problem Does This Paper Address?

In the age of ubiquitous image sharing, efficiently searching for similar images and detecting near-duplicates in massive datasets is a critical challenge. While techniques like Minwise Hashing (Minhash) have proven effective for estimating image similarity, they often require a large number of pairwise comparisons, which can be computationally expensive and slow down retrieval systems. This paper addresses the need for a faster approach to image similarity measurement, specifically for scenarios where we are only interested in identifying pairs that exceed a certain similarity threshold.

Methods

The core contribution of this paper is the dynamic threshold filter for Minwise Hashing. The standard Minwise Hashing algorithm computes a fixed number of hash comparisons (fingerprints) to estimate the Jaccard similarity between two sets (representing images). This new filter introduces a strategy to stop comparisons early.

Here's how it works:

  • Adaptive Thresholds: At intermediate comparison points (k out of K total comparisons), the filter calculates lower ($T_L(k)$) and upper ($T_U(k)$) thresholds.
  • Early Filtering: If the estimated similarity at point k ($R_M(k)$) falls below the lower threshold ($T_L(k)$), the algorithm predicts that the final similarity will be below the target threshold T and filters out the pair.
  • Early Output: Conversely, if $R_M(k)$ exceeds the upper threshold ($T_U(k)$), the algorithm predicts that the final similarity will be above T and outputs the pair, again avoiding further comparisons.
  • Binomial Distribution Assumption: The filter's effectiveness relies on the fact that the number of matching fingerprints in Minwise Hashing follows a binomial distribution. This allows for statistical prediction of the final similarity based on partial comparisons.
  • Generalizability: The authors note that this filtering approach can be extended to other hashing algorithms that also satisfy the binomial distribution property.
  • Image Representation: The paper uses the Bag-of-Visual-Words (BoVW) model with Scale Invariant Feature Transform (SIFT) descriptors to represent images as sets of visual words.

Datasets

The experiments were conducted on the Caltech256 dataset, which contains 30,607 object images. This dataset was used for evaluating the performance of the proposed filter.

Key Insights and Ideas

  • Early Termination is Key: The most significant insight is that by intelligently predicting similarity outcomes at intermediate stages, a substantial portion of comparisons can be avoided, leading to dramatic speedups.
  • Statistical Prediction: The filter leverages the statistical properties of Minwise Hashing (binomial distribution) to make these predictions, turning partial results into reliable early decisions.
  • Trade-off Between Speed and Accuracy: The filter introduces a small probability of error (controlled by parameter e), but the experiments show that this error is negligible in practice, while the speed gains are substantial.
  • Effectiveness for Extreme Similarities: The filter is particularly effective for image pairs with very low or very high similarities, as these are more likely to trigger early filtering or output.

Key Results

  • Significant Speedup: The dynamic threshold filter reduced the comparison time by up to 69% compared to the original Minwise Hashing. For instance, with a small probability $\epsilon=10^{-3}$, the calculation time was reduced to 31% of the original.
  • High Accuracy: The accuracy of the filter was found to be extremely close to 1.0, with negligible error. The authors observed that smaller values of $\epsilon$ lead to higher accuracy.
  • Filtering Rate: The filtering rate (probability of early exclusion or output) increases with the similarity threshold T and decreases with the comparison point k. It also increases as the small probability $\epsilon$ increases. For example, at $k=100$ and $T=0.3$, a filtering rate of 72% was achieved with $\epsilon=10^{-3}$, meaning 72% of pairs were decided early.

Limitations and Future Work

  • Small Probability Event: The paper acknowledges that the filter relies on "small probability events" (when the observed similarity deviates significantly from the predicted outcome). While experiments show these are rare, they represent a theoretical limitation.
  • Generalizability to Other Hashing: While the paper states the filter can be extended to other hashing algorithms satisfying the binomial distribution, the experimental validation is primarily focused on Minwise Hashing.
  • Future Work: The paper doesn't explicitly detail future work, but the demonstrated effectiveness of the dynamic threshold filter suggests its application to other large-scale similarity search problems and its integration with more advanced hashing techniques.

Summary updated

Abstract

Image similarity measures play an important role in nearest neighbor search and duplicate detection for large-scale image datasets. Recently, Minwise Hashing (or Minhash) and its related hashing algorithms have achieved great performances in large-scale image retrieval systems. However, there are a large number of comparisons for image pairs in these applications, which may spend a lot of computation time and affect the performance. In order to quickly obtain the pairwise images that theirs similarities are higher than the specific threshold T (e.g., 0.5), we propose a dynamic threshold filter of Minwise Hashing for image similarity measures. It greatly reduces the calculation time by terminating the unnecessary comparisons in advance. We also find that the filter can be extended to other hashing algorithms, on when the estimator satisfies the binomial distribution, such as b-Bit Minwise Hashing, One Permutation Hashing, etc. In this pager, we use the Bag-of-Visual-Words (BoVW) model based on the Scale Invariant Feature Transform (SIFT) to represent the image features. We have proved that the filter is correct and effective through the experiment on real image datasets.
BibTeX
@article{long2018filter,
  author = {Jun Long and Qunfeng Liu and Xinpan Yuan and Chengyuan Zhang and Junfeng Liu},
  title = {{A Filter of Minhash for Image Similarity Measures}},
  journal = {J. Adv. Comput. Intell. Intell. Informatics},
  year = {2018},
  url = {https://openreview.net/forum?id=XQUVe9iKOH},
}
Figure