Print

发布时间: 2018-05-16
摘要点击次数:
全文下载次数:
DOI: 10.11834/jig.170297
2018 | Volume 23 | Number 5




    图像处理和编码    




  <<上一篇 




  下一篇>> 





应用多索引加法量化编码的近邻检索算法
expand article info 刘恒1,2, 姚宇2, 曾玲1,2, 陶攀1,2
1. 中国科学院大学, 北京 100049;
2. 中国科学院成都计算机应用研究所, 成都 610041

摘要

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

关键词

倒排索引; 压缩编码; 加法量化; 近似最近邻检索; 矢量量化

Applying multi-index additive quantization encoding method for approximate nearest neighbor search
expand article info Liu Heng1,2, Yao Yu2, Zeng Ling1,2, Tao Pan1,2
1. University of Chinese Academy of Sciences, Beijing 100049, China;
2. Chengdu Institute of Computer Application, Chinese Academy of Sciences, Chengdu 610041, China

Abstract

Objective As the amount of image data produced every day increases, large-scale image retrieval technology is one of the hot topics in the field of computer vision. The basic idea is to extract features from all the images in the database and define the similarity measure to perform nearest neighbor search. The key of massive image retrieval is to design a nearest neighbor search algorithm that can meet efficiency and storage needs. An approximate nearest neighbor search based on multi-index additive quantization method is presented to improve the approximate representation accuracy and reduce the storage space requirements of image visual features. Method If each image is described by a set of local descriptors, then an exhaustive search is prohibitive as we need to index billions of descriptors and perform multiple queries. The image descriptors should be stored in memory to ensure real-time retrieval; however, this approach creates a storage problem. Artificial neural network (ANN) algorithms, which mainly include index structure and quantization methods, are typically compared based on the trade-off between search quality and efficiency. On the basis of the superiority of nonlinear search, we employ an inverted multi-index structure to avoid an exhaustive search. The multi-index structure divides the original data space into multiple subspaces. Each subspace that uses an inverted index stores the list of vectors that lie in the proximity of each codeword as each entry of the multi-index table corresponds to a part of the original vector space and contains a list of points that fall within that part. The purpose of a multi-index structure is to generate a list of data vectors that lie close to any query vector efficiently by only searching in a small dataset in which the near neighbors of the query vector most likely lie, thus ensuring a substantial speed-up over the exhaustive search. As a solution to the storage problem, compact code representations of descriptors are used. Vector quantization is an effective and efficient ANN search method. These methods quantize data by using codewords to reduce the cardinality of the data space. Among the vector quantization methods, additive quantization that approximates the vectors using sums of M codewords from M different codebooks generalizes product quantization and further improves product quantization accuracy while retaining its computational efficiency to a large degree. In this study, we use the additive quantization encoding method to encode the residual data produced by the multi-index structure, which further reduces the quantitative loss of original space. We regard the method mentioned previously as a two-stage quantizer that approximates the residual vector of the preceding stage using one of the centroids in the stage codebook and generates a new residual vector for the succeeding quantization stage. The multi-index structure is used as the first-order quantizer to approximate the vectors, and the additive quantization method is utilized as the second-order quantizer to approximate the residual. The non-exhaustive search strategy retrieves only the near neighbors in a few inverted lists, which can significantly reduce the retrieval time cost. With the use of the additive quantization method in the retrieval process, the original data need not be stored in memory and only the index of the codeword in the codebook should be stored, the sum of which is nearest the data item, significantly reducing memory consumption. Result Experiments on three datasets, i.e., SIFT1M, GIST1M, and MNIST, were conducted to verify the effectiveness of the proposed algorithm. The recall rate of the proposed algorithm is approximately 4% to 15% higher and its average precision is approximately 12% higher than that of existing algorithms. The search time of the proposed algorithm is the same as that of the fastest algorithm. Conclusion An approximate nearest neighbor search based on the multi-index additive quantization method proposed in this study can effectively improve the approximate representation accuracy and reduce the storage space requirements of image visual features. The proposed method also improves retrieval accuracy and recall in large-scale datasets. The proposed algorithm focuses on the nearest neighbor search, which is suitable for large-scale images and other multimedia data.

Key words

multi-index; compact encoding; additive quantization; approximate nearest neighbor search; vector quantization

0 引言

随着多媒体技术的进步,互联网上的数据量大幅增长,来自各大网站的文本、图像、视频等多媒体数据每天以惊人的速度迅猛增长,如何高效地存储、索引和检索越来越重要,设计一个满足海量数据实时检索的索引结构来有效组织图像的视觉内容对提高检索速度具有重要意义。对于大规模图像检索系统,索引结构的内存占用是检索系统一个重要性能指标,而图像检索的实时性需求要求图像描述符一直保存在计算机内存中,从而限制的索引结构可以处理的图像规模。因此如何将图像描述符进行高效的组织和量化,在保证图像描述符区分度的同时缩减存储空间,对在内存中实现大规模图像的索引结构和提高查询准确率具有根本性意义。目前近邻检索算法主要分为基于树结构的索引、基于哈希的索引和基于词袋模型的倒排索引。

基于树结构[1]的检索方法利用特殊的数据结构实现了非穷尽搜索,大大提高了搜索速度,但不能适用于高维的数据集。而计算机视觉上的数据大多都是高维,树搜索的方法不太适用。哈希方法把原始空间中的数据点映射到汉明超立方体上[2],使用较少的比特近似代替原始数据,使用非常小的内存消耗,但由于汉明空间的局限性,这种方法的检索准确率都较低。

本文主要探究压缩编码方法实现非穷尽搜索,提出了一种基于多索引的加法量化方法,使用较少的内存消耗、提高检索速度和检索准确率。算法的主要流程如下:

1) 利用多索引技术把原始数据空间划分成很多密集的小区域,在检索阶段只需在少量的小区域中搜索。

2) 使用加法量化方法编码多索引阶段产生的残差,在搜索阶段不用存储整个数据集,大大减少内存消耗。

在多个数据集上实验表明,本文算法在较少内存消耗条件下,不仅能降低检索时间而且有效提高检索准确率。

1 量化编码问题定义

在数字信号处理领域,量化是将信号的连续取值(或大量可能的离散取值)近似为有限多个(或较少的)离散值的过程,矢量量化也是这种思想,是将数据集合$ \mathit{\boldsymbol{X}}\left\{ {{\mathit{\boldsymbol{x}}}_{1}}, {{\mathit{\boldsymbol{x}}}_{2}}, \cdots, {{\mathit{\boldsymbol{x}}}_{N}} \right\},{{\boldsymbol{x}}_{i}}\in {{\mathbb{R}}^{D}}$$ X\in {{\mathbb{R}}^{D\times N}}$映射到一个有限集合中的函数[3],即

$ q({{\mathit{\boldsymbol{x}}}_{i}})\in \mathit{\boldsymbol{C}}=\{{{\mathit{\boldsymbol{c}}}_{i}}|{{\mathit{\boldsymbol{c}}}_{i}}\in {{\mathbb{R}}^{D}};i=1, 2\text{, }\cdots \text{, }K\} $ (1)

式(1)映射称为量化编码,记作$ \mathit{\boldsymbol{x}} →c(i(x)) $,集合$ \mathit{\boldsymbol{C}} $称为码书(codebook),集合中的元素${{\mathit{\boldsymbol{c}}}_{i}} $称为码字(codeword),在其他文献中也称$ {{\mathit{\boldsymbol{c}}}_{i}} $为中心(centroid),本文涉及多索引码书和加法量化码书,为了区分这两个码书,本文用$ \mathit{\boldsymbol{W}} $表示多索引量化码书,$ \mathit{\boldsymbol{C}} $表示加法量化码书。$ \mathit{\boldsymbol{C}} $总共有 $K$ 个码字,这些码字对空间进行划分,每个码字对应一个Voronoi区域。Voronoi区域定义为:平面上 $n$ 个不重合种子点,把平面分为 $n$ 个区域,使得每个区域内的点到它所在区域的种子点的距离比到其他区域种子点的距离近,每个区域称为该种子点的Voronoi区域。

量化器$ q(·) $的质量通常由它产生的量化损失(quantization distortion)进行度量,即

$ E=\sum\limits_{x\in X}{\left\| x-c\left( i\left( x \right) \right) \right\|_{2}^{2}} $ (2)

映射函数 $i(·)$ 称为编码器(encoder),将矢量映射到码字在码书中的索引, $c(·)$ 称作解码器(decoder),根据索引解码出对应的码字[3],本文使用 $ \mathit{\boldsymbol{C}} (k)$ 表示在码书中第 $k$ 个码字。 $E$ 越小,量化器 $q(·)$ 的质量越高。最小化量化损失 $E$ 必须满足劳埃德最优性的两个条件[2]

1) $x$ 必须编码到在码书中与 $x$ 距离最小的码字。

2) 在编码器 $i(·)$ 固定的情况下,码字 $c(i)$ 是索引到第 $i$ 个Voronoi区域的所有矢量的平均值。

常用的矢量量化方法是k均值方法[4],使用EM方法寻找最优的码书,E步:将 $ \mathit{\boldsymbol{X}} $ 中的矢量映射到码书中最近的码字;M步:对映射到同一个码字的矢量求均值来更新码字。自从乘积量化[5]编码方法出来以后,多码书的编码方法很受青睐,效果提升很大,乘积量化将原来的数据集合按照维度划分多个子空间,独立量化每一个子空间,在解码的时候将每个子空间对应的编码码字连接起来,可以近似重构原空间的数据。乘积量化利用码书间笛卡尔乘积运算,可以产生指数级增长的码字。对于第 $m$ 个码书的编码和解码使用下标表示: $i_m(·)$ $ \mathit{\boldsymbol{C}} _m(·)$

2 多索引加法量化编码介绍

2.1 建立多索引结构

多索引结构也称为倒排多索引(IMI)[6],是在倒排索引的基础上发展起来的一种更加密集细化的空间划分方法。乘积量化[5]将全空间表示为低维子空间的笛卡尔乘积,利用k均值量化每一个子空间。但是在大规模数据集中使用穷尽搜索并不是高效的方法。IVFADC[5]使用倒排索引的结构可以很方便地实现非穷尽搜索。倒排索引结构的建立过程形式化描述为:从一个给定的数据集合 $ \mathit{\boldsymbol{X }}\{\boldsymbol{x }_1, \boldsymbol{x }_2, \cdots , \boldsymbol{x } _N\}$ 中,使用k均值方法学习一个包含 $υ$ 个码字的码书 $ \mathit{\boldsymbol{W }}(\mathit{\boldsymbol{\omega }}_1, \mathit{\boldsymbol{\omega }}_2, \cdots , \mathit{\boldsymbol{\omega }} _υ)$ ,将 $ \mathit{\boldsymbol{X}}$ 中的每个数据项分配到与 $ \mathit{\boldsymbol{W }} $ 中最近的码字对应的Voronoi区域中,可将原始空间划分成 $υ$ 个倒排列表 $ \mathit{\boldsymbol{L}}_1, \cdots , \mathit{\boldsymbol{L}}_υ$ ,每一个列表 $ \mathit{\boldsymbol{L}}_i$ 包含 $ \mathit{\boldsymbol{X}}$ 中映射到 $ \mathit{\boldsymbol{\omega }} _i$ 的所有数据项。即: $ {\mathit{\boldsymbol{L}}_i} = \left\{ {\mathit{\boldsymbol{x}} \in \mathit{\boldsymbol{X|}}i = \arg \mathop {\min }\limits_j d\left( {\mathit{\boldsymbol{x, }}{\boldsymbol{\omega } _j}} \right)} \right\}$ ,式中 $d(·)$ ${\mathbb{R}}^D$ 空间的一个距离度量函数。考虑到使用k均值算法计算码书的速度,一般 $K$ 的取值在1 000~1 000 000[5] $υ$ 的取值满足不了超大规模而且高维的数据集需要,必须使用更密集而且细化的空间划分。

倒排多索引结构采用类似乘积量化的编码思想,在建立索引结构之前把原始空间划分成多个子空间,在每个子空间中独立学习一个码书,将原始数据集的每个子空间映射到相应码书的码字中,建立倒排列表。考虑到检索的时间成本,倒排多索引根据维度的先后顺序将原始空间划分成两个子空间,每个子空间维度相同,即 $ \mathit{\boldsymbol{X }}=[\mathit{\boldsymbol{X }}_1, \mathit{\boldsymbol{X }}_2] $ $ \mathit{\boldsymbol{X }} _1, \mathit{\boldsymbol{X }} _2 \in {{\mathbb{R}}^{\frac{D}{2}\times N}}$ ,使用建立倒排索引的方法建立 $ \mathit{\boldsymbol{X }} _1$ 的到排列表 $ \mathit{\boldsymbol{U }}(\mathit{\boldsymbol{u }}_1, \mathit{\boldsymbol{u }}_2, \cdots , \mathit{\boldsymbol{u }}_υ)$ $ \mathit{\boldsymbol{X }} _2$ 的倒排列表 $ \mathit{\boldsymbol{V }}(\mathit{\boldsymbol{v }}_1, \mathit{\boldsymbol{v }}_2, , \cdots , \mathit{\boldsymbol{v }}_υ)$ 。使用笛卡儿乘积,在全空间会形成 $υ^2$ 个码字的码书 $ \mathit{\boldsymbol{W }} _{i, j}=( \mathit{\boldsymbol{u }}_i, \mathit{\boldsymbol{v }}_j), i=1, \cdots , υ, j=1, \cdots , υ$ 。每个数据项 $ \mathit{\boldsymbol{x }} =[\mathit{\boldsymbol{x }}_1, \mathit{\boldsymbol{x }}_2]$ 映射到最近的 $[\mathit{\boldsymbol{u }}_i, \mathit{\boldsymbol{v }}_j]$ 形成倒排列表即

$ \begin{align} & {{\mathit{\boldsymbol{L}}}_{i, j}}=\{\mathit{\boldsymbol{x}}=\left[{{\mathit{\boldsymbol{x}}}_{1}}, {{\mathit{\boldsymbol{x}}}_{2}} \right]\in \mathit{\boldsymbol{X }}\!\!|\!\!\text{ }, \\ & i=\arg \underset{k}{\mathop{\min }}\, {{d}_{1}}({{\mathit{\boldsymbol{x}}}_{1}}, {{\mathit{\boldsymbol{u}}}_{k}})且 \\ & j=\arg \underset{k}{\mathop{\min }}\, {{d}_{2}}({{\mathit{\boldsymbol{x}}}_{2}}, {{\mathit{\boldsymbol{v}}}_{k}})\} \\ \end{align} $ (3)

考虑到索引结构建立好后,需对原始数据进行加法量化,这里改进倒排多索引,在每个列表中存放的是原始数据项映射到索引码字的残差,即

$ \begin{array}{c} {\mathit{\boldsymbol{L}}_{i, j}} = \{ r\left( \mathit{\boldsymbol{x}} \right) = [{\mathit{\boldsymbol{x}}_1}-{\mathit{\boldsymbol{u}}_i}, {\mathit{\boldsymbol{x}}_2}-{\mathit{\boldsymbol{v}}_j}]\\ \mathit{\boldsymbol{|x}} = \left[{{\mathit{\boldsymbol{x}}_1}, {\mathit{\boldsymbol{x}}_2}} \right] \in \mathit{\boldsymbol{X}}, \\ i = \arg \mathop {\min }\limits_k {d_1}\left( {{\mathit{\boldsymbol{x}}_1}, {\mathit{\boldsymbol{u}}_k}} \right) 且 \\ j = \arg \mathop {\min }\limits_k {d_2}({\mathit{\boldsymbol{x}}_2}, {\mathit{\boldsymbol{v}}_k})\} \end{array} $ (4)

通过建立多索引结构,在搜索阶段采用非穷尽搜索策略,即一次搜索不需要访问所有数据。当数据库规模特别大时(例如数十亿),采用线性搜索将会显著降低搜索效率,这是因为线性搜索的耗时与数据量成正比。本文首先用非线性搜索在全部倒排列表中找出一个被称为“候选集”的子集(少量倒排列表),再用线性搜索候选集,找出最近邻。只需在与待检索矢量距离最小的几个码字列表中搜索,不用在全空间搜索,大大提高了检索速度,而且多索引相比倒排索引能具有更好的检索结构,检索准确率更高。

2.2 加法量化编码

图像特征往往是高维的数据,对于海量图像检索,使用非线性搜索能加快检索速度,但不能满足存储需求,需要结合压缩编码算法。目前常用的压缩编码是哈希、乘积量化和加法量化算法。由于汉明空间的局限性,哈希算法的检索准确率不太高。乘积量化算法将全空间表示为低维子空间的笛卡儿乘积,检索准确率大大提升。加法量化在乘积量化的基础上放松了编码限制,不对全空间进行划分,检索准确率更高。因此本文使用加法量化对多索引编码产生的残差进行编码,进一步提高图像视觉特征的表示精度。

加法量化(AQ)[7]与乘积量化相似的地方是,都分成了M个子码书,每个子码书包括$ K $个码字,但是加法量化没有空间分解,所有的码字和原始矢量的维度相同。给定子码书$ \left\{ {{\mathit{\boldsymbol{C}}}_{m}}\in {{\mathbb{R}}^{D*K}} \right\}_{_{m=1}}^{^{M}} $,总码书$\mathit{\boldsymbol{C}} $表示为

$ \mathit{\boldsymbol{C}} = \{ \mathit{\boldsymbol{c}} = \sum\limits_{m = 1}^M {{\mathit{\boldsymbol{C}}_m}} \left( {{i_m}} \right)|{i_m} \in \{ 1, \cdots, k\} \} $ (5)

加法量化对矢量$\mathit{\boldsymbol{x}} $量化之后重构的副本表示为

$ \mathit{\boldsymbol{\tilde x}} = \sum\limits_{m = 1}^M {{\mathit{\boldsymbol{C}}_m}} ({i_m}(\mathit{\boldsymbol{x}})) $ (6)

式中,$ {{i}_{m}}(\mathit{\boldsymbol{x}})$表示矢量$\mathit{\boldsymbol{x}} $映射到第$m$个子码书中的码字索引,最后重构$\mathit{\boldsymbol{x}} $的副本$\mathit{\boldsymbol{\tilde{x}}} $为这$ M $个码字的加和。由于加法量化压缩编码是有损压缩,加法量化的目标函数是最小化重构误差,即

$ \mathop {\min }\limits_{{C_1}, {C_2}, \cdots, {C_M}} \sum\limits_{j = 1}^N {\left\| {{\mathit{\boldsymbol{x}}_j}-\sum\limits_{m = 1}^M {{\mathit{\boldsymbol{C}}_m}} \left( {{i_m}\left( {{\mathit{\boldsymbol{x}}_j}} \right)} \right)} \right\|} _{_2}^{^2} $ (7)

利用EM方法优化目标函数,E步:固定$ {{\left\{ {{\mathit{\boldsymbol{C}}}_{m}} \right\}}_{m=1, \cdots, M}} $,优化$ \left\{ {{i}_{m}}\left( {{\mathit{\boldsymbol{x}}}_{j}} \right) \right\}_{_{j=1, \cdots, N}}^{^{m=1, \cdots, M}} $,M步:固定$ \left\{ {{i}_{m}}\left( {{\mathit{\boldsymbol{x}}}_{j}} \right) \right\}_{_{j=1, \cdots, N}}^{^{m=1, \cdots, M}} $,优化$ {{\left\{ {{\mathit{\boldsymbol{C}}}_{m}} \right\}}_{m=1, \cdots, M}} $

优化$ {{\left\{ {{\mathit{\boldsymbol{C}}}_{m}} \right\}}_{m=1, \cdots, M}} $是一个最小二乘问题,在每一步迭代都有最优解。但是优化$ \left\{ {{i}_{m}}\left( {{\mathit{\boldsymbol{x}}}_{j}} \right) \right\}_{_{j=1, \cdots, N}}^{^{m=1, \cdots, M}} $,也就是加法量化的矢量编码,是一个全连接的离散高阶马尔可夫随机场问题,这是一个NP难问题。本文使用集束搜索的方法寻找加法量化矢量编码的近似最优解,集束搜索是一种启发式图搜算法。集束搜索使用$ N $个组 $\{ \mathit{\boldsymbol{I }} _1, \mathit{\boldsymbol{I }} _2, \cdots ,\mathit{\boldsymbol{I }} _N\}$ ,每个组中存放着编码矢量 $x$ 的一种可选方案,最后在这 $N$ 个组中选择编码最好的一个组。集束搜索算法具体步骤:

初始化: $ {{\mathit{\boldsymbol{I}}}_{n}}=\{\varnothing \} $ ,在 $ \mathit{\boldsymbol{C}}=\bigcup\limits_{m=1}^{M}{{{\mathit{\boldsymbol{C}}}_{m}}} $ 中选 $N$ 个与矢量 $x$ 距离最小的不同码字在对应码书中的索引 $\{\mathit{\boldsymbol{i}}_{_{{{m}_{1}}}}^{^{1}}, \mathit{\boldsymbol{i}}_{_{{{m}_{2}}}}^{^{2}}, \cdots, \mathit{\boldsymbol{i}}_{_{{{m}_{N}}}}^{^{N}}\}$ ,这些节点作为搜索的起始节点,将这些索引平均分配给这 $N$ 个组 $ {{\mathit{\boldsymbol{I}}}_{n}}={{\mathit{\boldsymbol{I}}}_{n}}\cup \{\mathit{\boldsymbol{i}}_{_{{{m}_{n}}}}^{^{n}}\}$ ,每个组保留一个残差 $ {{\mathit{\boldsymbol{e}}}_{n}}=x-\sum\limits_{{{i}_{m}}\in {{\mathit{\boldsymbol{I}}}_{n}}}{{{\mathit{\boldsymbol{C}}}_{m}}({{\mathit{\boldsymbol{i}}}_{m}})}$ 。然后独立优化每一个组,每次从未取过矢量的子码书并集中选 $N$ 个与该组残差矢量 ${{\mathit{\boldsymbol{e}}}_{n}} $ 距离最小的子码字 $ \left\{ {{\mathit{\boldsymbol{c}}}_{{{m}_{k}}}} \right\}_{_{k=1}}^{^{N}}$ ,计算残差$ \mathit{\boldsymbol{e}}{{\mathit{\boldsymbol{ }}\!\!'\!\!\text{ }}_{n}}=\{{{\mathit{\boldsymbol{e}}}_{n}}={{\mathit{\boldsymbol{e}}}_{n}}-{{\mathit{\boldsymbol{c}}}_{mk}}\}_{_{k=1}}^{^{N}}, I{{'}_{n}}=\{{{\mathit{\boldsymbol{I}}}_{n}}\cup \{{{\mathit{\boldsymbol{i}}}_{m}}({{\mathit{\boldsymbol{c}}}_{mk}})\}\}_{_{k=1}}^{^{N}} $。这样每个组有 $N$ 个残差, $N$ 个组共有 $N^2$ 个残差,选择前 $N$ 个最小的残差,和这些残差对应的码字索引集合,循环执行,直到 $N$ 个组中每个组集合元素个数为M。最后在 $N$ 个组中选择量化损失最小的一个组作为编码矢量 $\mathit{\boldsymbol{x}} $ 的量化编码索引。

集束搜索使用广度优先策略建立搜索树,在树的每一层,按照启发代价对搜索结果进行排序,然后仅留下预先确定的个数,仅这些节点在下一层继续扩展,其他节点被剪掉。

2.3 多索引加法量化编码分析

多索引结构对原始数据空间建立高效索引,可以认为倒排多索引是对数据集的一阶近似,加法量化是对多索引结构量化残差的近似,倒排多索引和加法量化相结合即是对数据集的二阶近似。使用$ {{q}_{\text{IMI}}}\left( \cdot \right) $表示倒排多索引量化,$ q_{aq}(·) $表示加法量化。对矢量$\mathit{\boldsymbol{x}} $,倒排多索引对矢量的一阶量化为

$ \begin{array}{c} {q_{{\rm{IMI}}}}\left( \mathit{\boldsymbol{x}} \right) = \{ [{\mathit{\boldsymbol{u}}_i}, {\mathit{\boldsymbol{v}}_j}]|\\ i = \arg \mathop {\min }\limits_k {d_1}\left( {{\mathit{\boldsymbol{x}}_1}, {\mathit{\boldsymbol{u}}_k}} \right) \wedge \\ j = \arg \mathop {\min }\limits_k {d_2}({\mathit{\boldsymbol{x}}_2}, {\mathit{\boldsymbol{v}}_k})\} \end{array} $ (8)

量化残差为

$ \mathit{\boldsymbol{r}}\left( x \right) = [{\mathit{\boldsymbol{x}}_1}-{\mathit{\boldsymbol{u}}_i}, {\mathit{\boldsymbol{x}}_2}-{\mathit{\boldsymbol{v}}_j}] $ (9)

使用加法量化对残差进行量化

$ {q_{aq}}\left( {r\left( \mathit{\boldsymbol{x}} \right)} \right) = \sum\limits_{m = 1}^M {{\mathit{\boldsymbol{C}}_m}} ({i_m}(r(\mathit{\boldsymbol{x}}))) $ (10)

所以多索引和加法量化相结合的最终量化结果为

$ \mathit{\boldsymbol{\tilde x}} \buildrel \Delta \over = {q_{{\rm{IMI}}}}\left( \mathit{\boldsymbol{x}} \right) + {q_{aq}}(\mathit{\boldsymbol{x}}-{q_{{\rm{IMI}}}}(\mathit{\boldsymbol{x}})) $ (11)

尽管矢量被多索引建立到不同的索引中,但加法量化是在所有数据的残差上训练得到的,本文只使用单一的加法量化器。

2.4 相似性度量

检索的本质就是进行相似排序,而度量相似性的常用方法是距离测度,比如欧氏距离、余弦距离、曼哈顿距离等,本文采用欧氏距离度量相似性。查询矢量$\mathit{\boldsymbol{y}} $与数据库矢量$\mathit{\boldsymbol{x}} $之间的平方距离近似为

$ \begin{array}{l} \tilde d{\left( {\mathit{\boldsymbol{x}}, \mathit{\boldsymbol{y}}} \right)^2} = d{\left( {\mathit{\boldsymbol{\tilde x}}, \mathit{\boldsymbol{y}}} \right)^2} = \left\| {\mathit{\boldsymbol{\tilde x}}-\mathit{\boldsymbol{y}}} \right\|_{_2}^{^2} = \\ d((\mathit{\boldsymbol{y}}-{q_{{\rm{IMI}}}}\left( \mathit{\boldsymbol{x}} \right), {q_{aq}}(\mathit{\boldsymbol{x}}-{q_{{\rm{IMI}}}}(\mathit{\boldsymbol{x}}))) \end{array} $ (12)

式(12)可以理解为将 $\mathit{\boldsymbol{y}} $ 分配到 $\mathit{\boldsymbol{x}} $ 所在倒排列表中并计算残差,然后计算这个残差与加法量化重构 $r( \mathit{\boldsymbol{x}} )$ 之间的距离。如果使用穷尽搜索的方法,需要计算出 $\mathit{\boldsymbol{x}} $ 与数据库中所有矢量的近似距离,然后对距离重排序。但在大规模近邻检索中,穷尽搜索非常耗时。由于倒排多索引的性质,同一个倒排列表中的数据项在高维空间中距离很小,可以先用倒排多索引对 $\mathit{\boldsymbol{y}} $ 做一个一阶近似,将 $\mathit{\boldsymbol{y}} $ 映射到最近的到排列表中,然后在对应的倒排列表中搜索。由于共有 $K^2$ 个倒排列表,假设倒排列表中的数据量分布较均衡,那么只需要计算 $N/K^2$ 个距离即可,相比于穷尽搜索,时间减少了 $K^2$ 倍。但考虑到可能与 $\mathit{\boldsymbol{x}} $ 相似的数据项映射到不同的倒排列表中,在最后搜索时候,改进这个缺点,并不是只在一个列表中搜索,而是搜索一定量的候选数据项。将倒排列表与查询矢量的距离从小到大排序,依次从近邻项最可能出现的列表开始搜索。设定一个阈值 $r$ ,如果搜索了 $r$ 个候选数据项,则搜索结束,从这 $r$ 个候选中筛选出与查询矢量距离最小的前 $k$ 个,作为查询矢量的近似最近邻。本文算法利用多索引结构的优势,在同一个倒排列表中的数据项相比其他数据项具有更高的相似性。

2.5 算法流程

在大规模检索系统中,本文算法共分为线上和线下两个部分:1)线下:建立倒排多索引列表、学习加法量化码书、使用加法量化编码倒排列表中的残差矢量。2)线上:(1)计算待查询数据项与多索引码书的距离,按从小到大的顺序排列多索引列表,并保存查询数据项映射到每个倒排列表的残差; (2)按照多索引列表的排列顺序,按式(12)计算倒排列表中的数据项与查询矢量的近似距离,并作为候选; (3)从这 $r$ 个候选中筛选出与查询矢量距离最小的前 $k$ 个,作为最终的检索结果。算法流程如图 1所示,上部分是倒排列表建立以及对残差量化编码,下部分是检索近邻项。

图 1 本文算法的总体结构图
Fig. 1 Overview of the algorithm

3 实验结果和分析

3.1 实验数据集

本文在3个公开的数据集SIFT1M[5]、GIST1M[5]、MNIST[8]上测试算法的准确性。MNIST数据集是手写的数字图片,大小都是归一化到28× 28像素矩阵,并将像素矩阵拉成一个784维的矢量。SIFT和GIST数据集分别是由sift特征点和gist描述子组成的。表 1详细表示了这3个数据集的信息。

表 1 数据集的详细信息
Table 1 The description of the dataset

下载CSV
MNIST SIFT GIST
维度 784 128 960
描述子类型 像素 局部描述子 全局描述子
数据集大小 60 000 1 000 000 1 000 000
查询数据量 1 000 10 000 1 000

3.2 实验参数设置

为了与近几年的近邻检索方法进行对比,本文实验的参数设置参考了近几年近似最近邻检索算法。在建立多索引时,将原始空间划分成两个子空间, $υ$ 取值为1 024。加法量化每个码书的码字个数 $K$ 为256,这样存储每个码书中的码字索引只需要一个字节,存储一个矢量的编码需要 $M$ 个字节。加法量化的码书个数 $M$ 需能被维度整除, $M$ 取值为4、8、16,这样存储一个矢量需要32、64、128 bit。在搜索时,设置 $r$ $k$ 为10 000, $r$ 的取值越大准确率越高,相反搜索时间也就越长。为了后续对比实验描述方便,将本文的检索算法称为IMI-AQ。

3.3 量化损失对比

量化编码是有损压缩,其过程实质上是输入矢量与码字的匹配过程。模式匹配的一个关键问题是重构矢量和输入矢量间差异的度量,也就是量化损失,它决定了量化器的质量,在一定程度上决定了算法在检索上的性能。

加法量化器的学习是一个迭代优化的过程,从图 2可以更直观地查看算法在每次迭代的量化损失。在训练加法量化器的时候,需要初始化子码书$\left\{ {{\mathit{\boldsymbol{C}}}_{m}}\in {{\mathbb{R}}^{D\times K}} \right\}_{_{m=1}}^{^{M}} $,本文使用两种初始化方法,一种是使用优化的乘积量化方法(OPQ)[9]初始化,另一种是随机初始化。从图 2中可以看出使用OPQ初始化,经过几步迭代量化损失能快速收敛,因此本文采用OPQ初始化的方法训练加法量化器,加快算法收敛。

图 2 多次迭代加法量化的量化损失($ M $=8)
Fig. 2 Convergence curve of additive quantization

表 2从量化损失上对比了本文算法与近几年表现优秀的算法,这些算法都是在SIFT1M数据集上使用64 bit编码得到的最后的量化损失。可以看出本文算法的量化损失是最小的。

表 2 在SIFT1M上64比特编码的量化损失比较
Table 2 Comparisons of the distortion with 64 bits code length on SIFT1M dataset

下载CSV
算法 量化损失
TC[10] 33 070.2
OPQ[9] 22 239.8
MPCA-E[11] 16 339.1
KSSQ[12] 15 253.1
IMI-AQ 13 719.1
注:表中加粗表示本文算法的量化损失最小。

3.4 召回率与查准率

召回率也叫查全率,是检索系统常用的评价标准,在近似近邻检索中常用的召回率标准是recall@r。recall@r是在众多的查询矢量中,最近邻排在返回结果前r个中的查询矢量比率。通过改变r,可以得到不同的recall@r值,recall@1是recall@r最重要的指标,因为recall@1代表的是众多的查询矢量中返回的结果第一个就是最近邻的比率,recal@r越高说明算法效果越好。

表 3表 4对比了本文算法和近几年提出的一些近似最近邻检索算法在SIFT1M和GIST1M数据集上recall@1,recall@10,recall@100性能差异,每种算法$M $取值为4或8,意味着编码矢量使用的是32 bit和64 bit,数据分别来源于原始论文和CompQ[13]。可以看出本文算法在SIFT1M数据集上32 bit编码和64 bit编码的表现性能是最优的,比次优的CompQ提升了2 % 4 %,在GIST1M上64 bit编码性能略低于CompQ, 但本文算法在32 bit编码比CompQ和其他算法性能都要好。

表 3 SIFT1M数据集上$ M $ =4, 8, recall@r性能对比
Table 3 Comparisons of recall@r on SIFT1M with 32 and 64 bit codes

下载CSV
算法 recall@1 recall@10 recall@100
PQ 0.052, 0.224 0.230, 0.599 0.595, 0.924
TC 0.057, 0.205 0.197, 0.535 0.519, 0.877
CKM/OPQ 0.068, 0.243 0.273, 0.638 0.658, 0.940
KSSQ 0.145, 0.325 0.434, 0.754 0.802, 0.923
IVFADC[5] 0.155, 0.296 0.461, 0.714 0.825, 0.960
CompQ[13] 0.135, 0.352 0.435, 0.795 0.831, 0.987
IMI-AQ 0.224, 0.388 0.608, 0.834 0.926, 0.986
注:加粗字体表示结果最优。

表 4 GIST1M数据集上 $M$ =4, 8, recall@r性能对比
Table 4 Comparisons of recall@r on GIST1M with $M$ equals 4 and 8

下载CSV
算法 recall@1 recall@10 recall@100
PQ 0.023, 0.076 0.068, 0.218 0.176, 0.504
TC 0.053, 0.096 0.104, 0.223 0.291, 0.547
CKM/OPQ 0.054, 0.118 0.142, 0.334 0.396, 0.715
KSSQ 0.078, 0.136 0.149, 0.396 0.345, 0.741
IVFADC 0.590, 0.910 0.155, 0.238 0.397, 0.511
CompQ 0.080, 0.157 0.214, 0.421 0.534, 0.808
IMI-AQ 0.100, 0.148 0.252, 0.401 0.560, 0.734
注:加粗字体表示结果最优。

由于只有PQ、IVFADC和OPQ公开了源码,图 3显示了在3个数据集上,本文算法(IMI-AQ)、IVFADC、OPQ和PQ分别在32、64、128比特编码上的recall@r曲线,可以直观的看出本文算法相比其他3种算法是最优的。

图 3 不同算法在三大数据集上的recall@r曲线
Fig. 3 reacall@r curves for different algorithms on three datasets((a) SIFT1M; (b)GIST1M; (c) MNIST)

图 4给出了不同算法在三大数据集上的平均查准率,可以看出本文算法平均查准率明显高于对比算法的性能,尤其在SIFT1M和MNIST数据集上比次优的IVFADC提高了12 %左右,在GIST1M数据集上提升了6 %~11 %。

图 4 不同算法在三大数据集上的平均查准率
Fig. 4 mAP curves for different algorithms on three datasets((a) SIFT1M; (b)GIST1M; (c) MNIST)

实验还对检索结果的准确率—召回率曲线进行了分析,从图 5的准确率—召回率曲线可看出,本文提出的IMI-AQ算法随着召回率的增大其检索结果准确率的下降幅度比对比算法下降幅度要平缓,在SIFT1M和MNIST数据集上表现的尤为突出。即本文算法的准确率受召回率的影响较小,也就是当检索结果的召回率增大时,本文算法仍能保持较高的准确率。

图 5 不同算法在三大数据集上采用64比特编码的准确率—召回率曲线
Fig. 5 Precision-recall curves for different algorithms on three datasets with code length of 64 bits
((a) SIFT1M; (b)GIST1M; (c) MNIST)

3.5 检索时间对比

比较算法的检索时间相对比较困难,比如OPQ、AQ使用了查找表技术,查找表、加减运算、乘除运算的复杂度无法直接进行比较,而且不同算法研究者使用的硬件条件以及编程语言不同,也有些用了加速库。本文的检索时间对比实验只和公开代码的OPQ,IVFADC,AQ算法进行比较。为了让这些算法进行公平的比较,本文将这些算法的检索部分改成了C语言实现。图 6为本文算法在32、64、128 bit编码时的平均检索时间,可以看出本文算法在32和64 bit编码时的平均检索时间略低于OPQ,但在128 bit编码时耗时最小。

图 6 SIFT1M数据集上平均检索时间
Fig. 6 Average query search time on SIFT1M

3.6 内存消耗分析

不同算法的内存消耗对比如表 5所示,使用 $M$ 个字节进行编码,本文算法在检索阶段只需存储多索引码书、加法量化码书以及多索引列表中残差矢量在加法量化码书中的编码索引。多索引码书内存消耗为 ${\rm{O}}(υD)$ ,加法量化码书的内存消耗为 ${\rm{O}}(MKD)$ ,存储索引编码内存消耗为 ${\rm{O}}(MN)$ ,在大规模的数据集中 ${\rm{O}}(MN) \gg {\rm{O}}(MKD)+{\rm{O}}(υD)$ ,因此这些算法在内存消耗上的复杂度近似相同。多索引码书和加法量化码书的内存消耗与数据维度有关而与数据集的大小无关,索引编码的内存消耗与原始数据集的维度无关,只与数据集大小和码书个数有关。对于高维度的GIST1M数据集,使用32 bit编码时共消耗内存11.3 MB,而存储GIST1M数据需要消耗内存3.6 GB, 内存消耗大大降低。

表 5 不同算法的内存消耗对比
Table 5 Comparisons of memory consumption for different algorithm

下载CSV
算法 内存消耗
OPQ ${\rm{O}}(D^2+KD)+{\rm{O}}(MN)$
AQ ${\rm{O}}(MKD)+{\rm{O}}(MN)$
IVFADC ${\rm{O}}(υD+KD)+{\rm{O}}(MN)$
IMI-AQ ${\rm{O}}(υD+MKD)+{\rm{O}}(MN)$

4 结论

本文提出的基于多索引结构的加法量化检索算法,利用多索引结构将原始数据空间划分为多个小区域,检索时只在相似数据可能存在的几个少数区域中搜索,实现了非线性搜索。结合加法量化进一步减少多索引阶段产生的残差,不仅减少内存消耗,而且提高了编码能力。在SIFT1M、GIST1M和MNIST上的实验,验证了本文算法能有效的提高检索的召回率和准确率,而且检索时间几乎与耗时最少的OPQ持平。尤其是本文将特殊的索引结构与量化算法相结合,能够实现非穷尽搜索,也就说随着数据集的扩大,检索时间上几乎没有变化。

本文使用的加法量化在矢量编码上是一个NP难问题,虽然采用次优的集束搜索解决这个问题,但是集束搜索的复杂度仍然较高。集束搜索复杂度为 ${\rm{O}}(M^2K^2(M+\log MK))$ ,与 $M$ 是三次方的关系,对于较大的 $M$ 需要更好的矢量编码方法。

本文算法适用于海量近邻检索系统,若将文本、图像、视频、语音等多媒体数据,高维表征成一个矢量,则该算法皆适用这些数据集的相似搜索。由于加法量化的矢量编码复杂度高,而且加法量化每一个子码书的编码长度应依据不同的数据分布赋予不同的值,因此未来工作将关注降低加法量化的编码复杂度和最优的编码长度分配。

参考文献

  • [1] Silpa-Anan C, Hartley R. Optimised KD-trees for fast image descriptor matching[C]//Proceedings of IEEE Conference on Computer Vision and Pattern Recognition. Anchorage, AK: IEEE, 2008: 1-8. [DOI: 10.1109/CVPR.2008.4587638]
  • [2] Guo Q Z, Zeng Z, Zhang S W, et al. Adaptive bit allocation product quantization[J]. Neurocomputing, 2016, 171: 866–877. [DOI:10.1016/j.neucom.2015.07.062]
  • [3] Gray R M. Vector quantization[J]. IEEE ASSP Magazine, 1984, 1(2): 4–29. [DOI:10.1109/MASSP.1984.1162229]
  • [4] Du Q, Emelianenko M, Ju L L. Convergence of the Lloyd algorithm for computing centroidal voronoi tessellations[J]. SIAM Journal on Numerical Analysis, 2006, 44(1): 102–119. [DOI:10.1137/040617364]
  • [5] Jégou H, Douze M, Schmid C. Product quantization for nearest neighbor search[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2011, 33(1): 117–128. [DOI:10.1109/TPAMI.2010.57]
  • [6] Babenko A, Lempitsky V. The inverted multi-index[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2015, 37(6): 1247–1260. [DOI:10.1109/TPAMI.2014.2361319]
  • [7] Babenko A, Lempitsky V. Additive quantization for extreme vector compression[C]//Proceedings of 2014 IEEE Conference on Computer Vision and Pattern Recognition. Columbus, OH: IEEE, 2014: 931-938. [DOI: 10.1109/CVPR.2014.124]
  • [8] Lécun Y, Bottou L, Bengio Y, et al. Gradient-based learning applied to document recognition[J]. Proceedings of the IEEE, 1998, 86(11): 2278–2324. [DOI:10.1109/5.726791]
  • [9] Ge T Z, He K M, Ke Q F, et al. Optimized product quantization[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2014, 36(4): 744–55. [DOI:10.1109/TPAMI.2013.240]
  • [10] Brandt J. Transform coding for fast approximate nearest neighbor search in high dimensions[C]//Proceedings of 2010 IEEE Conference on Computer Vision and Pattern Recognition. San Francisco, CA: IEEE, 2010: 1815-1822. [DOI: 10.1109/CVPR.2010.5539852]
  • [11] Ozan E C, Kiranyaz S, Gabbouj M. M-PCA binary embedding for approximate nearest neighbor search[C]//Proceedings of 2015 IEEE Trustcom/BigDataSE/ISPA. Helsinki, Finland: IEEE, 2015: 1-5. [DOI: 10.1109/Trustcom.2015.554]
  • [12] Ozan E C, Kiranyaz S, Gabbouj M. K-subspaces quantization for approximate nearest neighbor search[J]. IEEE Transactions on Knowledge and Data Engineering, 2016, 28(7): 1722–1733. [DOI:10.1109/TKDE.2016.2535287]
  • [13] Ozan E C, Kiranyaz S, Gabbouj M. Competitive quantization for approximate nearest neighbor search[J]. IEEE Transactions on Knowledge and Data Engineering, 2016, 28(11): 2884–2894. [DOI:10.1109/TKDE.2016.2597834]