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.

1. [1] H. Jégou, M. Douze, C. Schmid et al., “Aggregating local descriptors into a compact image representation,” Computer Vision and Pattern Recognition, IEEE, pp. 3304-3311, 2010.
2. [2] L. Zheng, S. Wang, Z. Liu, and Q. Tian, “Fast image retrieval: query pruning and early termination,” IEEE Trans. on Multimedia, Vol.17, No.5, pp. 648-659, 2015.
3. [3] L. Zheng, S. Wang, W. Zhou, and Q. Tian, “Bayes merging of multiple vocabularies for scalable image retrieval,” IEEE Conf. on Computer Vision and Pattern Recognition, pp. 1963-1970, 2014.
4. [4] D. G. Lowe, “Distinctive Image Features from Scale-Invariant Keypoints,” Int. J. of Computer Vision, Vol.60, No.2, pp. 91-110, 2004.
5. [5] L. Kabbai, A. Azaza, M. Abdellaoui et al., “Image matching based on LBP and SIFT descriptor,” Int. Multi-Conf. on Systems, Signals & Devices, IEEE, 2015.
6. [6] E. Karami, S. Prasad, and M. Shehata, “Image Matching Using SIFT, SURF, BRIEF and ORB: Performance Comparison for Distorted Images,” arXiv:1710.02726, 2017.
7. [7] W. Zhou, H. Li, Y. Lu et al., “SIFT match verification by geometric coding for large-scale partial-duplicate web image search,” Acm Trans. on Multimedia Computing Communications & Applications, Vol.9, No.1, p. 4, 2013.
8. [8] Z. Liu, H. Li, L. Zhang et al., “Cross-Indexing of Binary SIFT Codes for Large-Scale Image Search,” IEEE Trans. on Image Processing A Publication of the IEEE Signal Processing Society, Vol.23, No.5, p. 2047, 2014.
9. [9] A. Broder, “On the Resemblance and Containment of Documents,” Proc. of the Compression and Complexity of Sequences 1997, pp. 21-29, 1997.
10. [10] A. Z. Broder, S. C. Glassman, M. S. Manasse, and G. Zweig, “Syntactic clustering of the web,” Computer Networks, Vol.29, pp. 1157-1166, 1997.
11. [11] M. R. Henzinger, “Finding near-duplicate web pages: a large-scale evaluation of algorithms,” Proc. 29th ACM SIGIR Conf. on Research and Development in Information Retrieval, pp. 284-291, 2006.
12. [12] R. J. Bayardo, Y. Ma, and R. Srikant, “Scaling up all pairs similarity search,” Proc. of the 16th Int. Conf. on World Wide Web , pp. 131-140, 2007.
13. [13] P. Indyk and R. Motwani, “Approximate nearest neighbors: Towards removing the curse of dimensionality,” Proc. 13th ACM Symposium on Theory of Computing (STOC), pp. 604-613, 1998.
14. [14] P. Li, A. Shrivastava, J. L. Moore, and A. C. Konig, “Hashing algorithms for large-scale learning,” Proc. 25th Advances in Neural Information Processing Systems, pp. 2672-2680, 2011.
15. [15] P. Jain, B. Kulis, and K. Grauman, “Fast image search for learned metrics,” IEEE Conf. on Computer Vision and Pattern Recognition (CVPR) 2008, pp. 1-8, 2008.
16. [16] J. Matas, “ Fast computation of min-Hash signatures for image collections,” IEEE Conf. on Computer Vision and Pattern Recognition, pp. 3077-3084, 2012.
17. [17] W. L. Zhao and G. Gravier, “Sim-min-hash: an efficient matching technique for linking large image collections,” ACM Int. Conf. on Multimedia, pp. 577-580, 2013.
18. [18] Y. Qu, S. Song, J. Yang, et al., “Spatial min-Hash for similar image search,” Int. Conf. on Internet Multimedia Computing and Service, pp. 287-290, 2013.
19. [19] Y. Wang, X. Lin, L. Wu, et al., “LBMCH: Learning Bridging Mapping for Cross-modal Hashing,” Int. ACM SIGIR Conf. on Research and Development in Information Retrieval, 2015.
20. [20] L. Wu and Y. Wang, “Robust Hashing for Multi-View Data: Jointly Learning Low-Rank Kernelized Similarity Consensus and Hash Functions,” Image & Vision Computing, Vol.57, pp. 58-66, 2016.
21. [21] L. Wu and Y. Wang, “Structured Deep Hashing with Convolutional Neural Networks for Fast Person Re-identification,” arXiv:1702.04179, 2017.
22. [22] J. Sivic and A. Zisserman, “Video Google: A text retrieval approach to object matching in videos,” Proc. 9th IEEE Int. Conf. on Computer Vision, pp. 1470-1477, 2003.
23. [23] D. Nister and H. Stewenius, “Scalable recognition with a vocabulary tree,” Proc. of the 2006 IEEE Computer Society Conf. on Computer Vision and Pattern Recognition, pp. 2161-2168, 2006.
24. [24] J. Philbin, O. Chum, M. Isard, J. Sivic, and A. Zisserman, “Object retrieval with large vocabularies and fast spatial matching,” IEEE Conf. on Computer Vision and Pattern Recognition, pp. 1-8, 2007.
25. [25] O. Chum, J. Philbin, and A. Zisserman, “Near duplicate image detection: min-hash and tf-idf weighting,” Proc. the British Machine Vision Conf., pp. 1-10, 2008.
26. [26] P. Li, “b-Bit minwise hashing,” Int. Conf. on World Wide Web (WWW) 2010, Raleigh, North Carolina, pp. 671-680, 2010.
27. [27] P. Li, A. B. Owen, and C. H. Zhang, “One permutation hashing,” Advances in Neural Information Processing Systems, pp. 113-3121, 2012.
28. [28] http://www.vision.caltech.edu/Image_Datasets/Caltech256/ [accessed September 3, 2018]