总结

      当处理大规模图像数据时,最近邻搜索是最基本也是最主要的处理方式。其主要步骤是根据相应的数据集,建立高效的索引机制,当给定的查询特征的条件下,能够快速的检索反馈与其最相似的数据。其中,经典的工作有K-D树算法,VP树、RP树、M树等等树形结构算法。然而,这类算法的查询时间复杂度随着特征维度的增加呈指数级别的增长,导致在高维空间的检索效率甚至低于直接通过原始特征进行线性搜索。为了解决这一问题,近年来越来越多的研究者开始关注大规模数据的哈希编码学习算法,以解决在超大规模数据集中最近邻居搜索的问题。目前,哈希算法已经被应用于许多重要的应用场景中。例如,基于内容的图像和视频的检索和匹配、以及涉及数百万或数十亿个图像数据分析等应用场景。课题组近年来提出了多种二进制哈希编码算法,适应于单模态数据、多模态数据、在线数据和跨模态数据的哈希编码。

近期研究

       a) 基于排序的二值编码学习 [1-5]: 提出排序保持的哈希学习,研究对偶排序约束和顺序嵌入的无监督哈希学习的理论瓶颈和效率问题,利用了数据点之间的顺序约束并将此类关系保留到汉明空间中。

       b) 跨模态二值编码学习 [6-8]: 提出基于异质模态关系约束的跨模态哈希学习,研究混合模态相似度约束条件下的离散矩阵分解的理论瓶颈和效率问题,保证了矩阵分解后的二值空间保留给定相似度关系。

       c) 在线二值编码学习 [9-10]: 提出了基于Hadamard编码论的在线哈希学习、以及在线数据平衡相似性技术,研究伴随实时视觉数据更新的哈希编码机制、以及在线视觉数据更新过程中的数据分布不平衡问题,有效地保证在线编码后特征分布的不变性。

性能评估

      下图显示了具有不同哈希算法的多个哈希表的评估结果。使用一个灵活高效的库(例如EFANNA)对大型数据进行近似最近邻搜索,我们展示了在两个大型数据集上提出的OCH方法 [5] 可以实现性能提升。

参与人员

       Rongrong Ji, Hong Liu, Dongjing Song, Mingbao Lin

代表论文

      [1] Dongjin Song, Wei Liu, Rongrong Ji, David Meyer, John Smith. Top Rank Supervised Binary Coding for Visual Search. ICCV, 2015.

      [2] Dongjin Song, Wei Liu, David A. Meyer, Dacheng Tao, and Rongrong Ji. Rank Preserving Hashing for Rapid Image Search. DCC, 2015.

      [3] Hong Liu; Rongrong Ji; Yongjian Wu; Wei Liu. Towards Optimal Binary Code Learning via Ordinal Embedding. AAAI, 2016.

      [4] Hong Liu; Rongrong Ji; Yongjian Wu; Feiyue Huang. Ordinal Constrained Binary Code Learning for Nearest Neighbor Search. AAAI, 2017.

     [5] Hong Liu, Rongrong Ji, Jingdong Wang, and Chunhua Shen. Ordinal Constraint Binary Coding for Approximate Nearest Neighbor Search. IEEE TPAMI 2019.

    [6] Hong Liu, Mingbao Lin, Shengchuan Zhang, Yongjian Wu, Feiyue Huang, and Rongrong Ji. Dense Auto-Encoder Hashing for Robust Cross-Modality Retrieval. ACM MM, 2018.

     [7] Hong Liu; Rongrong Ji; Yongjian Wu; Gang Hua. Supervised Matrix Factorization for Cross-Modality Hashing. IJCAI, 2016.

     [8] Hong Liu; Rongrong Ji; Yongjian Wu; Feiyue Huang; Baochang Zhang. Cross-Modality Binary Code Learning via Fusion Similarity Hashing. CVPR, 2017.

     [9] Mingbao Lin, Rongrong Ji, Hong Liu, and Yongjian Wu. Supervised Online Hashing via Hadamard Codebook Learning. ACM MM, 2018.

   [10] Mingbao Lin, Rongrong Ji, Hong Liu, Xiaoshuai Sun, Yongjian Wu, and Yunsheng Wu. Towards Optimal Discrete Online Hashing with Balanced Similarity. AAAI, 2019.