Abstract
In the world of big data, large amounts of images are available in social media, corporate and even personal collections. A collection may grow quickly as new images are generated at high rates. The new images may cause changes in the distribution of existing classes or the emergence of new classes, resulting in the collection being dynamic and having concept drift. For efficient image retrieval from an image collection using a query, a hash table consisting of a set of hash functions is needed to transform images into binary hash codes which are used as the basis to find similar images to the query. If the image collection is dynamic, the hash table built at one time step may not work well at the next due to changes in the collection as a result of new images being added. Therefore, the hash table needs to be rebuilt or updated at successive time steps. Incremental hashing (ICH) is the first effective method to deal with the concept drift problem in image retrieval from dynamic collections. In ICH, a new hash table is learned based on newly emerging images only which represent data distribution of the current data environment. The new hash table is used to generate hash codes for all images including old and new ones. Due to the dynamic nature, new images of one class may not be similar to old images of the same class. In order to learn new hash table that preserves within-class similarity in both old and new images, incremental hashing with sample selection using dominant sets (ICHDS) is proposed in this paper, which selects representative samples from each class for training the new hash table. Experimental results show that ICHDS yields better retrieval performance than existing dynamic and static hashing methods.
Similar content being viewed by others
References
Hong L, Ji RR, Wang JD, Shen CH (2019) Ordinal constraint binary coding for approximate nearest neighbor search. IEEE Trans Pattern Anal Mach Intell 41(4):941–955
Huang LK, Yang Q, Zheng WS (2013) Online hashing. In: International joint conference on artificial intelligence, pp 1422–1428
Leng C, Wu JX, Cheng J, Bai X, Lu HQ (2015) Online sketching hashing. Proc IEEE Comput Soc Conf Comput Vis Pattern Recognit 7–12:2503–2511
Ng WWY, Tian X, Lv YM, Yeung DS, Pedrycz W (2017) Incremental hashing for semantic image retrieval in nonstationary environments. IEEE Trans Cybern 47(11):3814–3826
Mayur D, Indyk P, Immorlica N, Mirrokni VS (2004) Locality-sensitive hashing scheme based on P-stable distributions. In: Proceedings of the annual symposium on computational geometry, pp 253–262
Brian K, Grauman K (2012) Kernelized locality-sensitive hashing. IEEE Trans Pattern Anal Mach Intell 34(6):1092–1104
Yair W, Torralba A, Fergus R (2009) Spectral hashing. In: International conference on neural information processing systems, pp 1753–1760
Gong YC, Svetlana L, Albert G, Florent P (2013) Iterative quantization: a procrustean approach to learning binary codes for large-scale image retrieval. IEEE Trans Pattern Anal Mach Intell 35(12):2916–2929
Shen FM, Liu W, Zhang ST, Yang Y, Shen HT (2015) Learning binary codes for maximum inner product search. In: IEEE international conference on computer vision, pp 4148–4156
Liu XL, Mu YD, Zhang DC, Lang B, Li XL (2015) Large-scale unsupervised hashing with shared structure learning. IEEE Trans Cybern 45(9):1811–1822
Lopamudra M, Sathya RN, Vamsi IK, Tyler H, Vikas S (2015) An NMF perspective on binary hashing. In: IEEE international conference on computer vision, pp 4184–4192
Liu XL, Huang L, Deng C, Lang B, Tao DC (2016) Query-adaptive hash code ranking for large-scale multi-view visual search. IEEE Trans Image Process 25(10):4514–4524
Liu W, Wang J, Ji RR, Jiang YG, Chang SF (2012) Supervised hashing with kernels. In: Proceedings of the IEEE computer society conference on computer vision and pattern recognition, pp 2074–2081
Song DJ, Liu W, Ji RR, David MA, John RS (2015) Top rank supervised binary coding for visual search. In: IEEE international conference on computer vision, pp 1922–1930
Shen FM, Shen CH, Liu W, Shen HT (2015) Supervised discrete hashing. In: Proceedings of the IEEE computer society conference on computer vision and pattern recognition, pp 37–45
Gui J, Liu TL, Sun ZN, Tao DC, Tan TN (2018) Fast supervised discrete hashing. IEEE Trans Pattern Anal Mach Intell 40(2):490–496
Cheng KW, Li WJ, Zhou ZH (2016) Column sampling based discrete supervised hashing. In: Thirtieth AAAI conference on artificial intelligence, pp 1230–1236
Jiang QY, Cui X, Li WJ (2018) Deep discrete supervised hashing. IEEE Trans Image Process 27(12):5996–6009
Wang J, Kumar S, Chang SF (2012) Semi-supervised hashing for large-scale search. IEEE Trans Pattern Anal Mach Intell 34(12):2393–2406
Wang J, Kumar S, Chang SF (2010) Sequential projection learning for hashing with compact codes. In: Proceedings of the international conference on machine learning, pp 127–1134
Wu CX, Zhu JK, Cai D, Chen C, Bu JJ (2013) Semi-supervised nonlinear hashing using bootstrap sequential projection learning. IEEE Trans Knowl Data Eng 25(6):1380–1393
Ng WWY, Lv YM, Zeng ZQ, Yeung DS, Chan PPK (2017) Sequential conditional entropy maximization semi-supervised hashing for semantic image retrieval. Int J Mach Learn Cybern 8(2):571–586
Li P, Cheng J, Lu HQ (2013) Hashing with dual complementary projection learning for fast image retrieval. Neurocomputing 120:83–89
Zhang CH, Zheng WS (2017) Semi-supervised multi-view discrete hashing for fast image search. IEEE Trans Image Process 26(6):2604–2617
Ng WWY, Zhou XC, Tian X, Wang XZ, Yeung DS (2018) Bagging–boosting-based semi-supervised multi-hashing with query-adaptive re-ranking. Neurocomputing 27:916–923
Ng WWY, Li JC, Feng SY, Yeung DS, Chan PPK (2015) Sensitivity based image filtering for multi-hashing in large scale image retrieval problems. Int J Mach Learn Cybern 6(5):777–794
Zhang J, Peng YX (2019) SSDH: semi-supervised deep hashing for large scale image retrieval. IEEE Trans Circuits Syst Video Technol 29(1):212–225
Huang LK, Yang Q, Zheng WS (2018) Online hashing. IEEE Trans Neural Netw Learn Syst 29(6):2309–2322
Cakir F, He S, Bargal A, Sclaroff S (2017) MIHash: online hashing with mutual information. In: IEEE international conference on computer vision, pp 437–445
Weng ZY, Zhu YS (2019) Online supervised sketching hashing for large-scale image retrieval. IEEE Access 7:88369–88379
Cakir F, Sclaroff S (2015) Online supervised hashing. IEEE Int Conf Image Process 2015:2606–2610
Cakir F, Sclaroff S (2015) Adaptive hashing for fast similarity search. In: IEEE international conference on computer vision, pp 1044–1052
Ng WWY, Tian X, Pedrycz W, Wang XZ, Yeung DS (2019) Incremental hash-bit learning for semantic image retrieval in nonstationary environments. IEEE Trans Cybern 49(11):3844–3858
Liu XL, He JF, Lang B, Chang SF (2013) Hash bit selection: a unified solution for selection problems in hashing. In: Proceedings of the IEEE computer society conference on computer vision and pattern recognition, pp 1570–1577
Jhuo IH, Weng L, Cheng WH, Lee DT (2016) A feature fusion framework for hashing. In: International conference on pattern recognition, pp 2288–2293
Pavan M, Pelillo M (2003) A new graph-theoretic approach to clustering and segmentation. In: Proceedings of the IEEE computer society conference on computer vision and pattern recognition, vol 1, pp I–I
Pavan M, Pelillo M (2007) Dominant sets and pairwise clustering. IEEE Trans Pattern Anal Mach Intell 29(1):167–172
Jiang XX, Ng WWY, Tian X, Kwong S, Wang H (2019). Incremental hashing with undersampling. In: IEEE international conference on systems, man, and cybernetics, pp 616–622
Acknowledgements
This work was supported in part by the National Natural Science Foundation of China under Grants 61876066, 61772344, and 61672443, the Guangzhou Science and Technology Plan Project under Grant 201804010245, Guangdong Province Science and Technology Plan Project (Collaborative Innovation and Platform Environment Construction) 2019A050510006, EU Horizon 2020 Programme (700381, ASGARD), and the Hong Kong RGC General Research Funds under Grants 9042489 (CityU 11206317), 9042816 (CityU 11209819) and 9042322 (CityU 11200116).
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Ng, W.W.Y., Jiang, X., Tian, X. et al. Incremental hashing with sample selection using dominant sets. Int. J. Mach. Learn. & Cyber. 11, 2689–2702 (2020). https://doi.org/10.1007/s13042-020-01145-z
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s13042-020-01145-z