应用多索引加法量化编码的近邻检索算法

目的 海量图像检索技术是计算机视觉领域研究热点之一，一个基本的思路是对数据库中所有图像提取特征，然后定义特征相似性度量，进行近邻检索。海量图像检索技术，关键的是设计满足存储需求和效率的近邻检索算法。为了提高图像视觉特征的近似表示精度和降低图像视觉特征的存储空间需求，提出了一种多索引加法量化方法。方法 由于线性搜索算法复杂度高，而且为了满足检索的实时性，需把图像描述符存储在内存中，不能满足大规模检索系统的需求。基于非线性检索的优越性，本文对非穷尽搜索的多索引结构和量化编码进行了探索新研究。利用多索引结构将原始数据空间划分成多个子空间，把每个子空间数据项分配到不同的倒排列表中，然后使用压缩编码的加法量化方法编码倒排列表中的残差数据项，进一步减少对原始空间的量化损失。在近邻检索时采用非穷尽搜索的策略，只在少数倒排列表中检索近邻项，可以大大减少检索时间成本，而且检索过程中不用存储原始数据，只需存储数据集中每个数据项在加法量化码书中的码字索引，大大减少内存消耗。结果 为了验证算法的有效性，在3个数据集SIFT、GIST、MNIST上进行测试，召回率相比近几年算法提升4%~15%，平均查准率提高12%左右，检索时间与最快的算法持平。结论 本文提出的多索引加法量化编码算法，有效改善了图像视觉特征的近似表示精度和存储空间需求，并提升了在大规模数据集的检索准确率和召回率。本文算法主要针对特征进行近邻检索，适用于海量图像以及其他多媒体数据的近邻检索。

Applying multi-index additive quantization encoding method for approximate nearest neighbor search