Label Projection based on Hadamard Codes for Online Hashing

International Journal of Computer Science and Engineering

© 2023 by SSRG - IJCSE Journal

Volume 10 Issue 1

Year of Publication : 2023

Authors : Nannan Wu, Zhen Wang, Xiaohan Yang, Wenhao Liu, Xinyi Chang, Dongrui Fan

10.14445/23488387/IJCSE-V10I1P101

How to Cite?

Nannan Wu, Zhen Wang, Xiaohan Yang, Wenhao Liu, Xinyi Chang, Dongrui Fan, "Label Projection based on Hadamard Codes for Online Hashing," SSRG International Journal of Computer Science and Engineering , vol. 10,  no. 1, pp. 1-16, 2023. Crossref, https://doi.org/10.14445/23488387/IJCSE-V10I1P101

Abstract:

When new data streaming arrives, traditional hashing methods should retrain the hashing functions based on all samples. That leads to high training time complexity. In contrast, the online hashing algorithm re-computes the hashing functions just based on the new arrival streaming data and has been widely applied in large-scale image retrieval tasks. However, differences exist in numbers and labels between new arrival and old datasets, which causes the data imbalance problem while establishing their similarity matrix. This paper proposes a novel supervised online hashing method, Label Projection, based on Hadamard Codes for Online Hashing (LHOH), which jointly employs the label projection and similarity preservation mechanism to solve the data imbalance problem. In addition, LHOH considers the Hadamard codes as the label projection target domains to avoid the problem of difficult discrete optimization of the objective function. Then, LHOH employs the label projection matrix as label weight values, which can solve the data imbalance problem while computing the similarity matrix between new arrival and old datasets and preserve the consistency of Hamming and semantic space similarity. To increase the distinguishability among the hash codes, LHOH designs triple supervision learning mechanisms, including assigning Hadamard codes, projecting labels, and embedding labels. To validate the performance of the proposed LHOH method, this paper sets up the approximate nearest neighbor (ANN) search comparative experiments on two widely used datasets. The final results show that LHOH outperforms six current state-of-the-art online methods.

Keywords:

Online hashing, Hadamard code, Label projection, Triple supervision, Image retrieval.

References:

[1] Fumin Shen et al., “Supervised Discrete Hashing,” IEEE Conference on Computer Vision and Pattern Recognition, pp. 37-45, 2015. Crossref, https://doi.org/10.1109/cvpr.2015.7298598
[2] Jie Gui et al., “Fast Supervised Discrete Hashing,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 40, no. 2, pp. 490-496, 2017. Crossref, https://doi.org/10.1109/tpami.2017.2678475
[3] Xin Luo, Ye Wu, and Xin-Shun Xu, “Scalable Supervised Discrete Hashing for Large-Scale Search,” Proceedings of the 2018 World Wide Web Conference, pp. 1603-1612, 2018. Crossref, https://doi.org/10.1145/3178876.3186072
[4] Wei Liu et al., “Hashing With Graphs,” Proceedings of the 28th International Conference on Machine Learning, vol. 12, no. 3, 2011.
[5] Jun Wang, Sanjiv Kumar, and Shih-Fu Chang, “Semi-Supervised Hashing for Large-Scale Search,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 34, no. 12, pp. 2393-2406, 2012. Crossref, https://doi.org/10.1109/tpami.2012.48
[6] Jae-Pil Heo et al., “Spherical Hashing: Binary Code Embedding with Hyperspheres,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 37, no. 11, pp. 2304-2316, 2015. Crossref, https://doi.org/10.1109/tpami.2015.2408363
[7] Mengyang Yu, Li Liu, and Ling Shao, “Structure-Preserving Binary Representations for RGB-D Action Recognition,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 38, no. 8, pp. 1651-1664, 2015. Crossref, https://doi.org/10.1109/tpami.2015.2491925
[8] Wengang Zhou et al., “Scalable Feature Matching by Dual Cascaded Scalar Quantization for Image Retrieval,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 38, no. 1, pp. 159-171, 2016. Crossref, https://doi.org/10.1109/tpami.2015.2430329
[9] Hong Liu et al., “Towards Optimal Binary Code Learning Via Ordinal Embedding,” in Thirtieth AAAI Conference on Artificial Intelligence, vol. 30, no. 1, pp. 1258-1265, 2016. Crossref, https://doi.org/10.1609/aaai.v30i1.10167
[10] Xianlong Liu et al., “Multi-View Complementary Hash Tables for Nearest Neighbor Search,” in Proceedings of the IEEE International Conference on Computer Vision, pp. 1107-1115, 2015. Crossref, Https://Doi.Org/10.1109/ICCV.2015.132
[11] Li Liu, Mengyang Yu, and Ling Shao, “Multiview Alignment Hashing for Efficient Image Search,” IEEE Transactions on Image Processing, vol. 24, no. 3, pp. 956-966, 2015. Crossref, Https://Doi.Org/10.1109/TIP.2015.2390975
[12] Fumin Shen et al., “Asymmetric Binary Coding for Image Search,” IEEE Transactions on Multimedia, vol. 19, no. 9, pp. 2022-2032, 2017. Crossref, https://doi.org/10.1109/tmm.2017.2699863
[13] Long-Kai Huang, Qiang Yang, Wei-Shi Zheng, "Online Hashing," Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, pp. 1422-1428, 2013.
[14] Fatih Cakir, and Stan Sclaroff, “Adaptive Hashing for Fast Similarity Search,” 2015 IEEE International Conference on Computer Vision (ICCV), pp. 1044-1052, 2015. Crossref, https://doi.org/10.1109/iccv.2015.125
[15] Fatih Cakir, Sarah Adel Bargal, and Stan Sclaroff, “Online Supervised Hashing,” Computer Vision and Image Understanding, vol. 156, pp. 162-173, 2017. Crossref, https://doi.org/10.1016/j.cviu.2016.10.009
[16] Mingbao Lin et al., “Supervised Online Hashing via Hadamard Codebook Learning,” Proceedings of the 26th ACM International Conference on Multimedia, pp. 1635-1643, 2018. Crossref, https://doi.org/10.1145/3240508.3240519
[17] Mingbao Lin et al., “Towards Optimal Discrete Online Hashing with Balanced Similarity,” in Proceedings of the AAAI Conference on Artificial Intelligence, vol. 33, no. 01, pp. 8722-8729, 2019. Crossref, https://doi.org/10.1609/aaai.v33i01.33018722
[18] Qing-Yuan Jiang, and Wu -Jun Li, “Asymmetric Deep Supervised Hashing,” Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, vol. 32, no. 1, pp. 3342-3349, 2018. Crossref, http://dx.doi.org/10.1609/aaai.v32i1.11814
[19] Y. Fang, H. Zhang, and L. Liu, "Label Projection Online Hashing for Balanced Similarity," Journal of Visual Communication and Image Representation, vol. 80, pp. 103314, 2021. Crossref, https://doi.org/10.1016/j.jvcir.2021.103314
[20] Yuzhi Fang, and Li Liu, “Scalable Supervised Online Hashing for Image Retrieval,” Journal of Computational Design and Engineering, vol. 8, no. 5, pp. 1391-1406, 2021. Crossref, https://doi.org/10.1093/jcde/qwab052 [21] Cong Leng et al., “Online Sketching Hashing,” Proceedings of the 2015 IEEE Conference on Computer Vision and Pattern Recognition, pp. 2503-2511, 2015. Crossref, https://doi.org/10.1109/cvpr.2015.7298865
[22] Xixian Chen, Irwin King, and Michael R. Lyu, “FROSH: Faster Online Sketching Hashing,” in UAI, pp. 1-10, 2017.
[23] Yuzhi Fang, and Li Liu, “Angular Quantization Online Hashing for Image Retrieval,” IEEE Access, vol. 10, pp. 72577-72589, 2022. Crossref, https://doi.org/10.1109/access.2021.3095367
[24] Edo Liberty, “Simple and Deterministic Matrix Sketching,” Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 581-588, 2013. Crossref, https://doi.org/10.1145/2487575.2487623
[25] Yichao Lu et al., “Faster Ridge Regression via the Subsampled Randomized Hadamard Transform,” Advances in Neural Information Processing Systems, vol. 26, pp. 369-377, 2013.
[26] Fatih Cakir et al., “Mihash: Online Hashing With Mutual Information,” in Proceedings of the IEEE International Conference on Computer Vision, pp. 437-445, 2017. Crosssref, https://doi.ieeecomputersociety.org/10.1109/iccv.2017.55
[27] Zhenyu Weng, and Yuesheng Zhu, “Online Hashing With Bit Selection for Image Retrieval,” IEEE Transactions on Multimedia, vol. 23, pp. 1868-1881, 2021. Crossref, https://doi.org/10.1109/tmm.2020.3004962
[28] R C. Veena, and S H. Brahmananda, “A Significant Detection of APT Using MD5 Hash Signature and Machine Learning Approach,” International Journal of Engineering Trends and Technology, vol. 70, no. 4, pp. 95-106, 2022. Crossref, https://doi.org/10.14445/22315381/ijett-v70i4p208
[29] Mingbaea Lin et al., “Fast Class-Wise Updating for Online Hashing,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 44, no. 5, pp. 2453-2467, 2022. Crossref, https://doi.org/10.1109/tpami.2020.3042193
[30] Leon Bottou, “Large-Scale Machine Learning with Stochastic Gradient Descent,” in Proceedings of COMPSTAT'2010: Springer, pp. 177-186, 2010. Crossref, https://doi.org/10.1007/978-3-7908-2604-3_16
[31] Koby Crammer et al., “Online Passive Aggressive Algorithms,” Journal of Machine Learning Research, vol. 7, pp. 551-585 2006.
[32] Robert E. Schapire, “Using Output Codes to Boost Multiclass Learning Problems,” Proceedings of the Fourteenth International Conference on Machine Learning, vol. 97, pp. 313-321, 1997.
[33] J. Kittler et al., “Face Verification Using Error Correcting Output Codes,” Proceedings of the 2001 IEEE Computer Society Conference on Computer Vision and Pattern Recogonition 2001, vol. 1, pp. 7555-7560, 2001. Crossref, https://Doi.Org/10.1109/CVPR.2001.990552
[34] Jiayan Jiang, and Zhuowen Tu, “Efficient Scale Space Auto-Context for Image Segmentation and Labeling,” in 2009 IEEE Conference on Computer Vision and Pattern Recognition, pp. 1810-1817, 2009. Crossref, https://doi.org/10.1109/cvpr.2009.5206761
[35] Hong Liu et al., “Ordinal Constraint Binary Coding for Approximate Nearest Neighbor Search,” IEEE Transactions on Pattern Analysis & Machine Intelligence, vol. 41, no. 4, pp. 941-955, 2018. Crossref, https://doi.org/10.1109/tpami.2018.2819978
[36] Hong Liu et al., “Dense Auto-Encoder Hashing for Robust Cross-Modality Retrieval,” Proceedings of the 26th ACM International Conference on Multimedia, pp. 1589-1597, 2018. Crossref, https://doi.org/10.1145/3240508.3240684
[37] A. Hedayat, and W. D. Wallis, “Hadamard Matrices and Their Applications,” The Annals of Statistics, vol. 6, no. 6, pp. 1184-1238, 1978. Crossref, https://doi.org/10.1214/aos/1176344370
[38] Aristides Gionis, Piotr Indyk, and Rajeev Motwani, “Similarity Search in High Dimensions Via Hashing,” Proceedings of the 25th International Conference on Very Large Data Bases, vol. 99, no. 6, pp. 518-529, 1999.
[39] Wang-Cheng Kang, Wu-Jun Li, and Zhi-Hua Zhou, “Column Sampling Based Discrete Supervised Hashing,” Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, vol. 30, no. 1, pp. 1230-1236, 2016. Crossref, https://doi.org/10.1609/aaai.v30i1.10176
[40] Karen Simonyan, and Andrew Zisserman, “Very Deep Convolutional Networks for Large-Scale Image Recognition,” in International Conference on Learning Representations, 2015.
[41] Y. Lecun et al., “Gradient-Based Learning Applied to Document Recognition," Proceedings of the IEEE, vol. 86, no. 11, pp. 2278- 2324, 1998. Crossref, https://doi.org/10.1109/5.726791
[42] Alex Krizhevsky, Ilya Sutskever, and Geoffrey E. Hinton, “Image net Classification With Deep Convolutional Neural Networks,” Advances in Neural Information Processing Systems, vol. 60, no. 6, pp. 84-90, 2017. Crossref, https://doi.org/10.1145/3065386
[43] Mingbao Lin et al., “Hadamard Matrix Guided Online Hashing,” International Journal of Computer Vision, vol. 128, no. 8, pp. 2279- 2306, 2020. Crosssref, https://doi.org/10.1007/s11263-020-01332-z