面向图像检索的累加乘积量化方法研究

杜丹蕾，罗恩韬，唐雅媛，李延浚

（1.湖南科技学院电子与信息工程学院，湖南 永州 425100；2.中南大学信息科学与工程学院，长沙410083；3.朝阳科技大学，中国台湾 台中 41349）

面向图像检索的累加乘积量化方法研究

杜丹蕾1，罗恩韬2，唐雅媛1，李延浚3

（1.湖南科技学院电子与信息工程学院，湖南 永州 425100；2.中南大学信息科学与工程学院，长沙410083；3.朝阳科技大学，中国台湾 台中 41349）

针对经典的乘积量化方法易受数据相互依赖关系限制的问题，提出一种累加乘积量化方法。对高维特征向量进行正交分解，得到相互独立的特征向量子空间，依据压缩效率要求，对各特征向量子空间进行进一步分解，得到相互不独立的特征向量次子空间，对次子空间采用累加量化方法进行编码，对子空间采用乘积量化方法进行编码，在保障压缩效率的前提下降低数据相互依赖关系对量化精度的影响。实验结果表明，与经典的乘积量化方法和笛卡尔K-均值方法相比，该方法的编码误差较小，在图像检索应用中的查全率较高。

图像检索；特征提取；编码；乘积量化；非对称距离计算

DO I：10.3969/j.issn.1000-3428.2015.10.042

1 概述

近些年多媒体技术发展迅猛，图像作为最为基本的多媒体信息，应用非常广泛。随着图像数据规模的扩大，如何从海量图像数据中高效、准确地找到需要的图像数据成为迫切需要解决的问题。图像检索技术是解决这一问题的关键技术，已成为多媒体领域的研究热点［1］。按照检索内容进行分类，图像检索技术可分为2类：基于文本的图像检索（Text-based Image Retrieval，TBIR）［2］和基于内容的图像检索（Content-based Image Retrieval，CBIR）［3］。TBIR需要事先对图像进行文本注释，然后通过基于文本的数据库管理技术实现图像检索，但文本注释工作量大，且易受人的主观因素影响。CBIR通过理解图像内容来实现图像检索，基本思路是：首先从图像中提取特征，然后构建特征向量，最后通过计算特征向量

之间的距离来查询图像之间的相似度，寻找最相似的图像作为图像检索结果。CBIR的相似度查询过程可以看成特征向量空间的最近邻（Nearest Neighbor，NN）搜索问题［4］，通过计算查询向量与整个数据库中特征向量的距离，并按距离进行排序，筛选出距离最近的特征向量作为最近邻搜索的解。当特征向量维数较高时，最近邻搜索的计算量会大幅增加，引起“维数灾难”［5-6］，此时必须采用有效的高维数据索引机制来加速检索过程［7］。量化是降低特征向量维数、实现高维数据索引的有效途径［8］，其基本原理是：编码时构建码本，从中搜索与输入特征向量最匹配的码字，用其索引输入特征向量，进行传输、存储和处理；解码时采用简单的查表操作，还原出原特征向量。量化可以大幅降低特征维数，从而降低数据处理的空间复杂度，为面向高维数据的图像检索提供条件。

常用的量化方法可分为2类：一类是采用二值编码的思想［9-10］，将特征向量压缩为较短的比特流数据，降低数据存储空间，再采用压缩向量之间的汉明距离近似替代原始向量之间的欧氏距离，从而可以在低维空间上实现特征的检索。另一类是采用乘积量化（Product Quantization，PQ）的思想［11-13］，将特征向量进行正交分解，在分解后的低维正交子空间上进行量化，由于低维空间可以采用较小的码本进行编码，因此可以降低数据存储空间［14］。PQ方法采用基于查找表的非对称距离计算（Asymmetric Distance Computation，ADC）快速求取特征向量之间的距离，在压缩比相同的情况下，与采用汉明距离的二值编码方法，采用ADC的PQ方法的检索精度更高。然而，PQ方法假设各子空间的数据分布相互独立，当子空间数据的相互依赖较强时检索精度下降严重。

为了克服PQ方法受数据依赖关系影响大的问题，本文提出一种累加乘积量化（Cumulative Product Quantization，CPQ）方法。与PQ方法类似，CPQ方法也将特征向量分解为若干部分，每一部分采用独立的码本进行编码，再由各部分编码数据的累加和来表示原特征向量。特征向量之间的距离也可采用基于查找表的ADC方法快速求取。但在特征向量的分解过程中，CPQ只需将相互独立的数据划分到正交子空间，而各子空间的数据再进行分解时不受数据相互依赖关系的影响，但最终的压缩效率可以与PQ方法相当。另外，CPQ中的码本可以采用优化方法进行学习，从而提高检索精度。

2 乘积量化

一般地，特征向量维数越大，特征匹配效果越好，如尺度不变特征转换（Scale-invariant Feature Transform，SIFT）［15］特征。然而，维数的增大导致计算复杂度增加、存储空间占用增大。为解决这一问题，常采用量化技术对数据进行压缩处理，降低表示空间的基数。

设X∈RD表示一个D维向量，量化过程可以表示为：

其中，f表示量化函数；ci表示第i个码本；C为对应码本的质心，也称码字。

可见，量化是采用码字重构特征向量的过程。这一过程难免存在误差，常采用均方误差最小准则来选择失真最小的码字进行量化，即：

其中，向量χ为输入图像的向量表示。

均方误差越小，量化性能越好。因此，需要采用优化理论训练出最优的量化器，常用的是L loyd算法。但是当特征向量维数很大时，训练量化器的空间复杂度也很大。对于一个可产生64位（8 Byte）编码的量化器，对应码字为K=28个，此时，训练量化器的空间复杂度很大，采用Lloyd算法存储包含K个码字的D×K个浮点数据是很难实现的。此时可以采用乘积量化方法，降低量化器训练的空间复杂度。具体地，将特征向量X划分为M个子向量uj，1≤j≤M，这样每个子向量的维数下降为以前的1/M。然后每个子向量单独使用一个量化器进行量化，这样特征向量X被映射成如下形式：

其中，fj是第j个子向量的量化器，对应的码本为cj。这样，特征向量X的码本可以表示为各个子向量码本的乘积形式，即：

由于每一个子向量的维数大幅降低，采用L loyd算法训练各个子量化器的空间复杂度也大幅降低。在码字相同的情况下，存储空间消耗可降低为原来的1/M。

3 本文方法原理

3.1 CPQ介绍

据前一节所述，PQ方法通过将高维特征向量拆分为多个低维特征向量来降低向量编码的空间复杂度。然而，PQ方法有一个前提条件，即假设拆分后的各子空间相互独立。对于一个D维的特征向量，为了降低编码的空间复杂度，拆分后的子空间数量M越大越好。然而，在许多实际应用中，D维特征向

量很难拆分为许多相互独立的子向量。假设D维特征向量最多可以拆分为M1组相互独立的子向量，而空间复杂度要求是将其拆分为M（M大于M1）。如果拆分为M组子空间，那么这M组子空间的数据存在依赖关系，会影响量化精度。为了解决这一问题，本文提出CPQ方法，具体是将采用PQ方法拆分的M1个子空间再进行一次拆分，每个子空间拆分为M2个子空间，且M=M1×M2。在M2个子空间上，采用累加量化（Cumulative Quantization，CQ）方法进行量化处理，在保障量化效率的同时，降低空间复杂度和提高量化精度。

3.2 CQ原理

CQ与PQ方法一样，也是将D维向量划分为M个子向量，对应M个码本，每个码本包含K个码字。记第j个码本为cj，第i个码字中的第j个码本为cj（i）。然而，PQ中码字长度为D/M，而CQ中码字长度为D，与待编码特征向量长度一致。

对于特征向量X，采用CQ方法可以将其编码为M个码字的总和：

对于相同的参数M和K，CQ和PQ编码向量的内存占用相同，但CQ编码的精度更高。

本文提出的CPQ方法包含距离计算，向量编码和码本学习3个阶段：

（1）距离计算

在图像检索过程中，数据量庞大的特征向量数据库需要采用高效的量化方法进行压缩存储，同时，在进行特征检索时，还需要从数据库中快速找到与待查询的未压缩的特征向量相匹配的压缩特征向量，匹配准则一般为最近邻准则。PQ量化的最大优点是可以采用ADC算法快速计算待查询特征向量和量化后的特征向量数据库之间的距离，这一过程仅需要M次查表运算、M-1次加法运算和其他所需的少量运算，而 CQ量化也可具备这一优势。

假设q为量化前的特征向量，也称查询向量，y为量化后特征向量数据库中的任一向量，数据库中总样本数为L，q与y之间的欧氏距离为：

对于采用CQ方法得到的压缩向量y，可以表示为式（1）的形式。此时，可以采用查找表快速计算〈q，y〉，具体地，令：

则：

而当查询向量q确定时，Tm（i）可以预先计算

m并存储在查找表中。这样，遍历数据库计算〈q，y〉时，总的计算复杂度包括计算查找表的复杂度O（D×M×K）和计算实际内积的复杂度O（M×L）。尽管PQ中计算查找表的复杂度只有O（D×K），但实际应用中数据库中的样本数L远大于D×K，故O（M×L）的计算量远大于O（D×M×K），因此CQ和PQ方法在距离计算方面的计算量相当。的计算也可以采用查找表的方法进行，具体地：其中，式（9）右边的部分都是数据库中的已知项，可以预先计算并存储在查找表中。这样，计算大约需要M2/2次查表和加法运算。可见，的计算花费与空间维数 D无关。而且由于与待查询向量q无关，也即对于任意查询向量是相同的，可在构建数据库时一起计算并存储为查找表，这样在实际的特征向量检索过程中，的计算仅用一次查表运算即可。

（2）向量编码

对于特征向量y，给定码本为c1，c2，…，cm，寻找使编码误差E最小的码字来作为向量χ的CQ编码，其中：

将上式代入式（6），则：

M

对于给定的y，Um（im）和Vm（im）可以预先计算和存储，而是常量，对于最小化E没有意义，可以省略。故式（11）可以改写为：

上式可采用条件迭代模型（Iterative Model

Conditions，ICM）算法［16］和环路置信传播（Loopy Belief Propagation，LBP）算法［17］等常用的最优化方法求解。

（3）码本学习

码本学习就是寻找一组码本｛c1，c2，…，cm｝对特征向量Y=｛y1，y2，…，yn｝进行编码，使编码误差最小，也即：

与其他码本学习方法相似，本文采用块坐标下降策略，在imj和cm之间交替进行最小化。给定码本的编码变量最小化需要编码给定码本的向量 yj，而更新码本对应码字的过程可以等价于以下最小二乘问题：

当参数n和D较大时，上述最小二乘问题的求解非常困难。为此，将式（16）分解为 D个最小二乘问题，每个最小二乘问题涉及的变量只有 K和 M。这样，可以采用如下的线性方程求解：

其中，cm（k）表示第d个cm（k），同样向量y表示

d

j，d第d个向量yj。式（18）定义了n个关于变量K和M的方程，可以采用最小二乘法求解。另外，对于D个不同尺寸的最小二乘求解问题，由于式（18）在不同尺寸下存在递推关系，因此可以采用递推方法快速求解。

4 基于CPQ的图像检索

如图1所示，图像检索主要包括建库和检索2个过程：

（1）建库：对于给定的图像数据库，通过图像理解模块提取各个图像的特征向量，通过量化技术对特征向量进行压缩处理，建立图像数据库对应的特征数据库。

（2）检索：对于输入的待检索图像，通过与建库过程相同的图像理解模块提取图像的特征向量（查询向量），计算查询向量与特征数据库中量化后的各特征向量之间的距离，选择距离最近一个或多个的特征向量作为匹配的特征向量，再通过索引查找这些特征向量对应的图像，即可得到要检索的图像。

图1 图像检索流程

在上述过程中，图像的特征向量提取有很多种方法，譬如SIFT、Haar［18］等，特征向量提取的好坏对图像检索结果影响很大，但这部分不是本文的研究重点，这里不再赘述。

一般地，图像数据库中图像数量庞大。为提高图像查全率，需要对图像的特征向量进行压缩处理。本文采用CPQ方法进行压缩，步骤如下：

Step1 对D维特征向量进行正交分解，得到M1个子特征向量。

Step2 对M1个子特征向量进一步分解，得到M2个次子特征向量。

Step3 采用CQ方法，对M2个次子特征向量进行量化编码。

Step4 采用PQ方法，对M1个子特征向量的CQ编码结果进行进一步量化编码，最终得到含M= M1×M2个码本的编码结果。

在特征向量查询阶段，按前文所述的距离计算方法，求取查询向量与数据库中特征向量间的距离，返回距离最近的T个特征向量作为查询结果。

5 实验结果与分析

实验的目标为验证本文方法的性能。为了便于对比，本文不考虑图像特征的提取过程，直接选用文献［12］所述的SIFT特征库作为实验数据库，执行图像检索的建库和查询2个核心任务。该数据库包括100 000个SIFT特征向量和10 000个查询向量，每

个特征向量的维数D=128，每个查询向量在数据库中对应一个匹配向量，已事先标记。

实验中将本文提出的CPQ方法与经典的PQ［12］和笛卡尔K-均值（Cartesian K-means，CKM）［13］方法进行对比。在建库阶段，采用3种不同的量化方法对数据库中的SIFT特征向量进行压缩，计算采用不同方法产生的编码误差，评价不同方法的量化精度。在查询阶段，计算查询向量与数据库中采用不同量化方法得到的压缩向量之间的欧氏距离，采用最近邻搜索方法在数据库中搜索与查询向量距离最近的T个压缩向量，再与事先标记的匹配结果进行对比，统计查全率指标，评价不同方法的检索性能。

5.1 编码误差

量化是一种有损编码方法，普遍存在编码误差。编码误差越小，说明量化方法的性能越好。本文对比了不同量化方法在不同编码长度（即码本个数M）和码字尺寸（即每个码本码字个数 K）下的编码误差（原向量与量化后向量平方差），如图2和图3所示。

图2 编码长度不同时的编码误差对比

图3 码字尺寸不同时的编码误差对比

在图2中，取参数K=256，M分别取4，8和16，CPQ方法中M1和M2与M的对应关系如表1所示。

表1 CPQ方法中编码长度参数取值

在图3中，取参数M=4，K分别取32，64，128，256和512。从图中可以看出，在不同的编码长度和码字尺寸下，CPQ方法的编码误差都要低于PQ和CKM方法。

5.2 查全率

查全率是图像检索常用的评价指标［19］。假设数据库内特征向量总数为 L，对于第i个查询向量，数据库中相匹配的特征向量数量为Ni，检索输出相似度最大的Ni+T幅图像（T为检索余量）。如果输出图像中包含ni幅相匹配的图像，则查全率为：

图4和图5显示了不同方法在不同参数T下的查全率曲线，其中，图4所示为M=8的情况，图5所示为M=16的情况。CPQ方法中M1和M2与M的对应关系仍如表1所示，参数K都取为256。从图中可以看出，相同参数下CPQ方法的查全率要高于PQ和CKM方法。

图4 M为8时不同方法的查全率对比

图5 M为16时不同方法的查全率对比

表2对比了不同方法的检索耗时。为便于对比，以PQ方法为基准，其检索耗时记为1。从表中可见，CKM和CPQ方法检索耗时都要大于PQ方法，且CPQ方法耗时最多，可见CPQ方法还需要进一步提升。

表2 不同算法检索耗时对比

6 结束语

本文对经典的PQ方法进行改进，提出一种新的CPQ方法。通过对高维特征向量进行降维来提高压缩效率。为了克服PQ方法对数据独立性的依赖，先采用正交分解得到相互独立的子空间，再对不具备独立性的数据子空间采用普通分解，得到次子空间，最后在非正交的次子空间上采用CQ方法进行编码，而在正交的子空间上采用PQ方法进行编码，这样可以在压缩效率与PQ方法相当的情况下，降低数据相互依赖关系对量化精度的影响。实验结果表明，该方法在图像检索应用中编码误差较小，查全率较高。

［1］ Worring M，Santini S，Gupta A，et al.Content-based Image Retrieval at the End of the Early Years［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2000，22（12）：1349-1380.

［2］ 黄祥林，高 芸.一种基于关键词的中文文档图像检索方法［J］.中文信息学报，2007，21（4）：61-64.

［3］ 万华林，Chowdhury U M，胡 宏，等.图像纹理特征及其在CBIR中的应用［J］.计算机辅助设计与图形学学报，2003，15（2）：195-199.

［4］ Cover T.Nearest Neighbor Pattern Classification［J］.IEEE Transactions on Information Theory，1967，13（1）：21-27.

［5］ Laughlin D C.The Intrinsic Dimensionality of Plant Traits and Its Relevance to Community Assembly［J］. Journal of Ecology，2014，102（1）：186-193.

［6］ 薄树奎，李盛阳，朱重光.基于统计学的最近邻查询中维数灾难的研究［J］.计算机工程，2006，32（21）：6-8.

［7］ 薛向阳，罗航哉，吴立德.LIFT：一种用于高维数据的索引结构［J］.电子学报，2001，29（2）：192-195.

［8］ 叶航军，徐光祐.基于矢量量化的快速图像检索［J］.软件学报，2004，15（5）：712-719.

［9］ Buhler J.Efficient Large-scale Sequence Comparison by Locality-sensitive Hashing［J］.Bioinformatics，2001，17（5）：419-428.

［10］ Gong Y，Lazebnik S.Iterative Quantization：A Procrustean Approach to Learning Binary Codes［J］.IEEE Conference on Computer Vision and Pattern Recognition，2011，42（7）：817-824.

［11］ Ge Tiezheng.Optimized Product Quantization for Approximate Nearest Neighbor Search［J］.Conference on Computer Vision and Pattern Recognition，2013，36（4）：2946-2953.

［12］ Jegou H，Douze M.Product Quantization for Nearest Neighbor Search［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2011，33（1）：117-128.

［13］ Norouzi M，Fleet D J.Cartesian K-means［C］//Proceedings of IEEE Conference on Computer Vision& Pattern Recognition.Washington D.C.，USA：IEEE Press，2013：3017-3024.

［14］ 李 峰，蔡 琼.基于SIFT的图像盲取证方法［J］.计算机工程，2011，37（14）：233-235.

［15］ 纪 华，吴元昊.结合全局信息的SIFT特征匹配算法［J］.光学 精密工程，2009，17（2）：439-444.

［16］ Besag J.On the Statistical Analysis of Dirty Pictures［J］.Journal of the Royal Statistical Society B，1986，48（3）：48-259.

［17］ Andersen S K，Judea P.Probabilistic Reasoning in Intelligent System s：Networks of Plausible Inference［J］. Artificial Intelligence，1991，48（91）：117-124.

［18］ 甘 玲，朱 江，苗 东.扩展Haar特征检测人眼的方法［J］.电子科技大学学报，2010，39（2）：247-250.

［19］ 魏 海，沈兰荪.基于分类矢量量化的图像压缩和检索算法［J］.电子学报，2001，29（7）：933-936.

编辑 刘冰

Research on Cumulative Product Quantization Method for Image Retrieval

DU Danlei1，LUO Entao2，TANG Yayuan1，LEE Yenchun3
（1.School of Electronics and Information Engineering，Hunan University of Science and Engineering，Yongzhou 425100，China；2.School of Information Science and Engineering，Central South University，Changsha 410083，China；3.Chaoyang University of Technology，Taichung 41349，Taiwan，China）

For solving the problem that the classic Product Quantization（PQ）method is restricted on data’s independence，a Cumulative PQ（CPQ）method is proposed in this paper.Orthogonal decomposition is executed on the high-dimensional feature vectors to obtain independent sub-spaces of feature vectors，and decomposes every subspace again according to the compression efficiency，and obtains dependent sub-sub-spaces of feature vectors，uses Cumulative Quantization（CQ）method to quantify the vectors sub-sub-spaces，and uses PQ method to quantify the vectors from subspaces.The new method reduces the impact of data’s independence on accuracy of quantization，under the premise of maintaining the compression efficiency.Experimental results show that the new method has small code error compared with classical PQ and Cartesian K-means（CKM）methods，and high recall rate in the application of image retrieval.

image retrieval；feature extraction；encoding；Product Quantization（PQ）；Asymmetric Distance Computation（ADC）

杜丹蕾，罗恩韬，唐雅媛，等.面向图像检索的累加乘积量化方法研究［J］.计算机工程，2015，41（10）：226-231.

英文引用格式：Du Danlei，Luo Entao，Tang Yayuan，et al.Research on Cumulative Product Quantization Method for Image Retrieval［J］.Computer Engineering，2015，41（10）：226-231.

1000-3428（2015）10-0226-06

A

TP391

湖南省科技厅科技计划基金资助项目（2014FJ6095）；湖南省教育厅高校优秀青年基金资助项目（14B070）；湖南省教育厅科学研究基金资助项目（湘财教指［2011］91号）；永州市指导性科技计划基金资助项目（永科发［2013］17号）。

杜丹蕾（1981-），女，讲师、硕士，主研方向：图形图像处理；罗恩韬，副教授、博士；唐雅媛，讲师、硕士；李延浚，副教授、博士。

2015-04-10

2015-05-30E-m ail：dudanleihn@163.com