Efficient Binary Coding for Subspace-based Query-by-Image Video Retrieval

ABSTRACT

Subspace representations have been widely applied for videos in many tasks. In particular, the subspace-based query-by-image video retrieval (QBIVR), facing high challenges on similarity-preserving measurements and efficient retrieval schemes, urgently needs considerable research attention. In this paper, we propose a novel subspace-based QBIVR framework to enable efficient video search. We first define a new geometry-preserving distance metric to measure the image-to-video distance, which transforms the QBIVR task to be the Maximum Inner Product Search (MIPS) problem. The merit of this distance metric lies in that it helps to preserve the genuine geometric relationship between query images and database videos to the greatest extent. To boost the efficiency of solving the MIPS problem, we introduce two asymmetric hashing schemes which can bridge the domain gap of images and videos properly. The first approach, termed Inner-product Binary Coding (IBC), achieves high-quality binary codes by learning the binary codes and coding functions simultaneously without continuous relaxations. The other one, Bilinear Binary Coding (BBC) approach, employs compact bilinear projections instead of a single large projection matrix to further improve the retrieval efficiency. Extensive experiments on four real-world video datasets verify the effectiveness of our proposed approaches, as compared to the state-of-the-art methods.

References

1. Ronen Basri, Tal Hassner, and Lihi Zelnik-Manor. 2011. Approximate Nearest Subspace Search. TPAMI, Vol. 33, 2 (2011), 266--278.
2. Martin Bäuml, Makarand Tapaswi, and Rainer Stiefelhagen. 2013. Semi-supervised Learning with Constraints for Person Identification in Multimedia Data CVPR. 3602--3609.
3. Andre F. de Araújo, Jason Chaves, Roland Angst, and Bernd Girod. 2015. Temporal aggregation for large-scale query-by-image video retrieval ICIP. 1519--1522.
4. Andre F. de Araújo, Mina Makar, Vijay Chandrasekhar, David M. Chen, Sam S. Tsai, Huizhong Chen, Roland Angst, and Bernd Girod. 2014. Efficient video search using image queries. In ICIP. 3082--3086.
5. Guiguang Ding, Yuchen Guo, and Jile Zhou. 2014. Collective Matrix Factorization Hashing for Multimodal Data CVPR. 2083--2090.
6. Yunchao Gong, Sanjiv Kumar, Henry A. Rowley, and Svetlana Lazebnik. 2013 a. Learning Binary Codes for High-Dimensional Data Using Bilinear Projections CVPR. 484--491.
7. Yunchao Gong, Sanjiv Kumar, Vishal Verma, and Svetlana Lazebnik. 2012. Angular Quantization-based Binary Codes for Fast Similarity Search NIPS. 1205--1213.
8. Yunchao Gong, Svetlana Lazebnik, Albert Gordo, and Florent Perronnin. 2013 b. Iterative Quantization: A Procrustean Approach to Learning Binary Codes for Large-Scale Image Retrieval. TPAMI, Vol. 35, 12 (2013), 2916--2929.
9. Richang Hong, Yang Yang, Meng Wang, and Xian-Sheng Hua. 2015. Learning Visual Semantic Relationships for Efficient Visual Retrieval. TBD, Vol. 1, 4 (2015), 152--161.
10. Yiqun Hu, Ajmal S. Mian, and Robyn A. Owens. 2011. Sparse approximated nearest points for image set classification CVPR. 121--128.
11. Zi Huang, Heng Tao Shen, Jie Shao, Xiaofang Zhou, and Bin Cui. 2009. Bounded coordinate system indexing for real-time video clip search. TOIS, Vol. 27, 3 (2009), 17:1--17:33.
12. Jianqiu Ji, Jianmin Li, Qi Tian, Shuicheng Yan, and Bo Zhang. 2015. Angular-Similarity-Preserving Binary Signatures for Linear Subspaces. TIP, Vol. 24, 11 (2015), 4372--4380.
13. Jianqiu Ji, Jianmin Li, Shuicheng Yan, Qi Tian, and Bo Zhang. 2014. Similarity-Preserving Binary Signature for Linear Subspaces AAAI. 2767--2772.
14. Qing-Yuan Jiang and Wu-Jun Li. 2015. Scalable Graph Hashing with Feature Transformation IJCAI. 2248--2254.
15. Yu-Gang Jiang, Zuxuan Wu, Jun Wang, Xiangyang Xue, and Shih-Fu Chang. 2015. Exploiting Feature and Class Relationships in Video Categorization with Regularized Deep Neural Networks. CoRR Vol. abs/1502.07209 (2015).
16. Hanjiang Lai, Yan Pan, Ye Liu, and Shuicheng Yan. 2015. Simultaneous feature learning and hash coding with deep neural networks CVPR. 3270--3278.
17. Alan J. Laub. 2005. Matrix analysis - for scientists and engineers. SIAM.
18. Wu-Jun Li, Sheng Wang, and Wang-Cheng Kang. 2016. Feature Learning Based Deep Supervised Hashing with Pairwise Labels IJCAI. 1711--1717.
19. Yan Li, Ruiping Wang, Zhiwu Huang, Shiguang Shan, and Xilin Chen. 2015. Face video retrieval with image query via hashing across Euclidean space and Riemannian manifold CVPR. 4758--4767.
20. Zijia Lin, Guiguang Ding, Mingqing Hu, and Jianmin Wang. 2015. Semantics-preserving hashing for cross-view retrieval CVPR. 3864--3872.
21. Venice Erin Liong, Jiwen Lu, Gang Wang, Pierre Moulin, and Jie Zhou. 2015. Deep hashing for compact binary codes learning. In CVPR. 2475--2483.
22. Wei Liu, Jun Wang, Rongrong Ji, Yu-Gang Jiang, and Shih-Fu Chang. 2012. Supervised hashing with kernels. In CVPR. 2074--2081.
23. Wei Liu, Jun Wang, Sanjiv Kumar, and Shih-Fu Chang. 2011. Hashing with Graphs ICML. 1--8.
24. Mohammad Norouzi and David J. Fleet. 2011. Minimal Loss Hashing for Compact Binary Codes. In ICML. 353--360.
25. Florent Perronnin, Jorge Sánchez, and Thomas Mensink. 2010. Improving the Fisher Kernel for Large-Scale Image Classification ECCV. 143--156.
26. Mohammad Rastegari, Jonghyun Choi, Shobeir Fakhraei, Hal Daumé III, and Larry S. Davis. 2013. Predictable Dual-View Hashing. In ICML. 1328--1336.
27. Fumin Shen, Wei Liu, Shaoting Zhang, Yang Yang, and Heng Tao Shen. 2015. Learning Binary Codes for Maximum Inner Product Search ICCV. 4148--4156.
28. Fumin Shen, Xiang Zhou, Yang Yang, Jingkuan Song, Heng Tao Shen, and Dacheng Tao. 2016. A Fast Optimization Method for General Binary Code Learning. TIP, Vol. 25, 12 (2016), 5610--5621.
29. Anshumali Shrivastava and Ping Li. 2014. Asymmetric LSH (ALSH) for Sublinear Time Maximum Inner Product Search (MIPS) NIPS. 2321--2329.
30. Anshumali Shrivastava and Ping Li. 2015. Improved Asymmetric Locality Sensitive Hashing (ALSH) for Maximum Inner Product Search (MIPS). In UAI. 812--821.
31. Jingkuan Song, Yang Yang, Yi Yang, Zi Huang, and Heng Tao Shen. 2013. Inter-media hashing for large-scale retrieval from heterogeneous data sources SIGMOD. 785--796.
32. Raviteja Vemulapalli, Jaishanker K. Pillai, and Rama Chellappa. 2013. Kernel Learning for Extrinsic Classification of Manifold Features CVPR. 1782--1789.
33. Ruiping Wang and Xilin Chen. 2009. Manifold Discriminant Analysis. In CVPR. 429--436.
34. Zhongwen Xu, Yi Yang, and Alexander G. Hauptmann. 2015. A discriminative CNN video representation for event detection CVPR. 1798--1807.
35. Yang Yang, Yadan Luo, Weilun Chen, Fumin Shen, Jie Shao, and Heng Tao Shen. 2016. Zero-Shot Hashing via Transferring Supervised Knowledge ACM MM. 1286--1295.
36. Yang Yang, Fumin Shen, Heng Tao Shen, Hanxi Li, and Xuelong Li. 2015. Robust Discrete Spectral Hashing for Large-Scale Image Semantic Indexing. TBD, Vol. 1, 4 (2015), 162--171.
37. Yang Yang, Zheng-Jun Zha, Yue Gao, Xiaofeng Zhu, and Tat-Seng Chua. 2014. Exploiting Web Images for Semantic Video Indexing Via Robust Sample-Specific Loss. TMM, Vol. 16, 6 (2014), 1677--1689.
38. Litao Yu, Yang Yang, Zi Huang, Peng Wang, Jingkuan Song, and Heng Tao Shen. 2016. Web Video Event Recognition by Semantic Analysis from Ubiquitous Documents. TIP, Vol. 25, 12, 5689--5701.
39. Dongqing Zhang and Wu-Jun Li. 2014. Large-Scale Supervised Multimodal Hashing with Semantic Correlation Maximization AAAI. 2177--2183.
40. Yi Zhen and Dit-Yan Yeung. 2012. A probabilistic model for multimodal hash function learning SIGKDD. 940--948.
41. Jile Zhou, Guiguang Ding, and Yuchen Guo. 2014. Latent semantic sparse hashing for cross-modal similarity search SIGIR. 415--424.
42. Xiaofeng Zhu, Zi Huang, Heng Tao Shen, and Xin Zhao. 2013. Linear cross-modal hashing for efficient multimedia search ACM MM. 143--152.

Index Terms

• Information systems

  • Information retrieval

    • Specialized information retrieval

      • Multimedia and multimodal retrieval