字典学习、视觉词袋特征提取方法及检索系统

摘要

本发明提供一种字典学习方法，包括：1)基于维度将图像的局部特征向量分为第一分段和第二分段；2)用多个局部特征向量的第一分段构造第一数据矩阵，用多个局部特征向量的第二分段构造第二数据矩阵；3)对第一数据矩阵进行稀疏非负矩阵分解，得到用于对局部特征向量的第一分段进行稀疏编码的第一字典；对第二数据矩阵进行稀疏非负矩阵分解，得到用于对局部特征向量的第二分段进行稀疏编码的第二字典。本发明还提供了基于上述两个字典对图像局部特征进行分段稀疏表示的视觉词袋特征提取方法和相应的检索系统。本发明能够大幅减少内存占用，降低词表训练时间和特征提取时间，特别适合应用于移动终端。

说明书

技术领域

本发明涉及多媒体内容分析与检索技术领域，具体地说，本发明涉及 一种字典学习、视觉词袋特征提取方法及检索系统。

背景技术

视觉搜索简单地说就是“以图搜图”。为实现视觉搜索，首先需要对 大规模图像库提取特征建立索引库，在用户搜索时，对查询图像提取特征， 在特征索引库中快速检索并按相关性(即相似度)排序，返回结果。这个 结果是一个排序的库中图像列表，其中每个结果图像可能包含与查询图像 相关、结合用户特征和搜索场景的关联信息。目前，面向PC的传统视觉 搜索已经积累了大量算法和技术方案可供选择。然而，随着移动互联网的 快速发展，人们对移动视觉搜索有了越来越高的需求。移动视觉搜索具有 移动化、网络化和智能化等特点，它通过为用户提供“所见即所知”的新 一代搜索服务，便捷地将身边现实世界的视觉对象关联至互联网信息世界 的视觉对象，成为链接现实世界和信息世界的桥梁和纽带。图1示出了一 种典型的移动视觉搜索的构架，它通过智能手机、平板电脑等移动终端获 取现实世界中对象的图像或视频，然后进行特征提取，再通过移动互联网 将所提取的特征传输至服务器，服务器基于大规模数据库进行大规模视觉 搜索，再将搜索结果返回给移动终端，从而实现“所见即所知”的效果。 例如在一个应用场景中，用手机拍摄一个古董，然后对所拍摄图片进行检 索，即可快速便捷地获得该古董的名称、形状尺寸、历史典故、评论等相 关信息，这极大地提升了用户体验，真正地实现了“所见即所知”的效果。 可以说，移动视觉搜索极具想象空间，具有广阔的应用前景。

然而，移动视觉搜索还面临一系列需要克服的难点，主要体现在：

(1)移动终端拍摄随意性较大，旋转缩放、内容删减和背景干扰、 尤其是视角变化造成的仿射形变等因素往往导致查询图像与库图像之间 存在严重的视觉形变，全局颜色、纹理等传统特征很难适用，因而需要研 究更为鲁棒的局部特征提取方法。

(2)面对无线网络环境的带宽有限、带宽波动、时延和获取等方面 挑战，需要研究视觉查询的紧凑表示。发送图像的紧凑视觉签名，比传送 整张图像更具优势，不仅可降低资费，且可避免不必要的大量上行数据传 输造成的传输延迟，大幅提升用户体验。

(3)移动终端的处理器性能、内存和电力资源有限，因此需要研究 适合于移动终端的特征提取与表示算法，以满足实际应用中对移动终端内 存占用、处理速度和精度的需求。

综上所述，围绕移动智能终端，针对视觉查询进行鲁棒特征提取和紧 凑表示，在不损失基于原始图像的检索性能前提下，亟待突破特征提取速 度慢、内存开销大、数据不紧致的瓶颈；这也是多媒体信号处理、图像分 析与检索等多个交叉研究领域共同关注的问题。

视觉特征的鲁棒性、区分性和紧凑性和提取算法的高效性是保证移动 视觉搜索系统精度的重要前提。由于前述移动终端拍摄的随意性造成的巨 大视觉差异，对特征的鲁棒性提出了更高的要求，全局颜色、纹理等传统 特征很难适用。局部特征是指从角点、边缘、斑块等局部显著结构的图像 区块中提取的视觉特征。与图像分割产生的区域不同，局部区块允许互相 重叠，而且在不同图像条件下检测到的局部区块具有很高的可重复性。局 部特征对旋转平移、尺度缩放、光照变化、视角变化、物体运动、遮挡、 裁剪等具有较好的鲁棒性，已成为近几年来的研究热点。

文献K.Mikolajczyk and C.Schmid.“A performance evaluation of local descriptors”,IEEE  Transactions on Pattern Analysis and Machine Intelligence(TPAMI),27(10):615-1630,2005.对一些著 名的局部区块检测算法和描述算法进行了比较和总结，并指出最好的描述 子是SIFT描述子。它由Lowe在ICCV’99提出、2004年IJCV完善总结。 SIFT描述子对图像尺度缩放、旋转变换和光照变化情况都能保持较好鲁棒 性，并被证明是现有描述子中稳定性和区分性最好的局部特征描述子。但 是SIFT描述子最大的缺陷是高维，存储和欧式距离的计算都成问题，对 大规模检索，这构成性能的瓶颈。SIFT特征高达128维，传输每个SIFT特 征都至少需要1024比特(8比特/维)。而一幅512×512的普通图像中提取 的SIFT特征点数通常高达上千个，传输SIFT特征所需比特数甚至超过传 输JPEG图像本身。因此，为了采用尽可能少的特征比特数传递尽可能多 的查询图像信息，特征量化成为减少传输流量、降低网络延迟、和降低服 务器端特征存储占用的重要手段。

文献B.Girod,V.Chandrasekhar,D.M.Chen,N.M.Cheung,R.Grzeszczuk,Y.Reznik,G.Takacs, S.S.Tsai,and R.Vedantham.“Mobile Visual Search”；IEEE Signal Processing Magazine,Special Issue on  Media Search in Mobile Devices,28(4):61-76,July2011.指出：2003年J.Sivic提出的视觉词 袋(BoW,Bag of Visual Words)特征量化方法目前基于内容图像检索中最为 成功和广泛应用的方法。该方法借鉴文本检索领域的BoW方法，通过 K-Means聚类将局部特征采用矢量量化(Vector quantization)为特征聚类的 类别标号，即视觉关键词，避免了存储海量的图像特征，并避免了计算高 维特征相似性所带来的时间开销，非常适合于大规模数据环境下的局部近 似图像检索。但是，该在特征量化时产生了量化损失，降低了特征的区分 性，影响了检索效果。

针对这一问题，近年来，研究者们普遍采取增大词表(字典)规模(即 视觉关键词总数)的方法增强BoW的区分性。实践证明在视觉词表规模 达到100,000以上时，具有良好的区分性，从而能够支持海量高维特征的 低比特数存储。值得注意的是：Arandjelovic等最近基于对SIFT描述子进 行l₁归一化和求平方根，提出RootSIFT(可参考文件：Arandjelovic,R.and Zisserman, A.,“Three things everyone should know to improve object retrieval”,In Proc.IEEE Conf.on Computer  Vision and Pattern Recognition(CVPR),2012)，分别在Oxford5K和105K、Paris6K数 据集上实现高达0.929、0.891、0.910(非软分配BoW)的检索平均精度 MAP。

词表规模的增大给词表训练和特征量化带来了巨大的压力。学者们采 用了多种层次结构对传统的K-Means聚类方法进行改进、以及各种近似最 近邻搜索方法取代精确最近邻搜索，对词表训练和特征量化过程进行加速。 例如：2006年Nister等提出层次聚类的HKM，2007年Philbin等提出近 似最近邻AKM，2010年Li等通过记录字典学习迭代的中间结果提出了 RAKM方法，2012年Avrithis年提出了近似混合高斯模型的AGM方法， 2013年Mikulik等结合HKM和AKM方法构建了一个两层的字典(下文 中简称Mikulik方案)，每层字典的规模是8K，共有64M个视觉关键词。

然而，上述改进方法仍然需要大量的高维局部特征训练词表，存在词 表训练非常耗时、词表内存占用大等问题。以构建1M维BoW为例，对 于AKM方法，词表(1M×128)占内存高达512M；对于二级的HKM方 法，词表训练需要聚类1025次，生成1025个1024×128维的词表(包含 1个一级词表和1024个二级词表)，占用内存也超过512M。而Mikulik方 案的64M维层次化大词表，其占用内存高达32G，需要20台机器组成的 机群训练一整天。同时，由于K-Means聚类集中倾向于数据高密度区域， 使得有些特征显著但数据量少的区域被合并，这导致描述子的区分性极大 下降。

综上所述，尽管大词表BoW在PC机视觉检索领域取得了很大的成功 但是，目前所有大词表BoW方法都不能应用于计算资源受限的移动终端， 最大的障碍是其存在词表占用内存过大问题。现有大词表BoW方法，1M 维的词表(1M×128)占内存高达512M，即使手机内存能存放这么大的词 表，内存载入和计算时间也是很大的问题。

因此，当前迫切需要一种内存占用少的基于大词表BoW的移动视觉 搜索解决方案。

发明内容

本发明的任务是提供一种内存占用少的基于大词表BoW的移动视觉 搜索解决方案。

本发明提供了一种字典学习方法，包括下列步骤：

1)基于维度将图像的局部特征向量分为第一分段和第二分段；

2)用多个局部特征向量的第一分段构造第一数据矩阵，其中，第一 数据矩阵的每个列向量为训练集中一个局部特征向量的第一分段，用多个 局部特征向量的第二分段构造第二数据矩阵，其中，第二数据矩阵的每个 列向量为训练集中一个局部特征向量的第二分段；

3)对第一数据矩阵进行稀疏非负矩阵分解，得到用于对局部特征向 量的第一分段进行稀疏编码的第一字典；对第二数据矩阵进行稀疏非负矩 阵分解，得到用于对局部特征向量的第二分段进行稀疏编码的第二字典。

其中，所述步骤3)中，稀疏非负矩阵分解采用在线学习算法、MOD 算法或者KSVD算法实现。

其中，所述步骤3)中，所述稀疏非负矩阵分解包括：基于组稀疏编 码优化目标函数，求解使组稀疏编码优化目标函数最小化的用于对向量进 行稀疏编码的字典及相应的稀疏编码系数矩阵。

其中，所述步骤3)中，所述组稀疏编码优化目标函数中加入了表达 组内稀疏编码系数值差异的正则化项。

本发明还提供了一种基于前述的字典学习方法的视觉词袋特征提取 方法，包括下列步骤：

1)从图像中提取局部特征点及其局部特征向量，并对该局部特征向 量进行分段，得到相应的第一分段和第二分段；

2)基于第一字典，对当前局部特征向量的第一分段进行稀疏编码， 得到相应的第一稀疏编码系数向量，基于第二字典，对当前局部特征向量 的第二分段进行稀疏编码，得到相应的第二稀疏编码系数向量；

3)根据第一稀疏编码系数向量和第二稀疏编码系数向量中的非零元素 所对应的字典基元索引号，将当前局部特征向量分配到视觉词袋中对应的 视觉关键词。

其中，所述步骤3)中，找出第一稀疏编码系数向量中最大非零元素 所对应的字典基元索引号I₁，以及第二稀疏编码系数向量中最大非零元素所 对应的字典基元索引号I₂，根据索引号组合[I₁、I₂]将当前局部特征向量分 配到视觉词袋中对应的一个视觉关键词。

其中，所述步骤3)中，找出第一稀疏编码系数向量中最大的两个非 零元素所对应的字典基元索引号I₁₁和I₁₂，以及第二稀疏编码系数向量中最 大的两个非零元素所对应的字典基元索引号I₂₁和I₂₂，根据索引号组合[I₁₁、 I₂₁]，[I₁₁、I₂₂]，[I₁₂、I₁₁]和[I₁₂、I₂₂]将当前局部特征向量软分配到视觉词 袋中对应的四个视觉关键词。

其中，所述视觉词袋特征提取方法还包括步骤：

4)对于由第一稀疏编码系数向量中非零元素所对应的字典基元索引号 I_a和第二稀疏编码系数向量中非零元素所对应的字典基元索引号I_b组成的 索引号组合[I_a、I_b]，令Index＝I_a×K+I_b，其中K为第二稀疏编码系数向量 中元素的个数，用Index表示索引号组合[I_a、I_b]所对应的视觉关键词。

本发明还提供了一种基于前述的视觉词袋特征提取方法的检索方法， 包括下列步骤：

1)对于查询图片，基于所述的视觉词袋特征提取方法，将其各个局 部特征点分配到视觉词袋中对应的视觉关键词，并提取该查询图片的用于 几何验证的元信息；

2)基于倒排索引进行特征匹配，进而进行几何一致性校验，获得查 询结果；所述倒排索引基于视觉关键词建立，其中对于每个视觉关键词， 记录包含该视觉关键词的图像的标识和该图像中该视觉关键词(即相应的局 部特征点)用于几何验证的元信息。

其中，所述用于几何验证的元信息包括局部特征点的在图像中的位置、 尺度和主方向等。

本发明还提供了一种基于前述的视觉词袋特征提取方法的检索系统， 其特征在于，包括通过互联网连接的终端模块和服务端模块，

所述终端模块用于所述的视觉词袋特征提取方法将当前图像的各个局 部特征向量分配到视觉词袋中对应的视觉关键词，并将所述包括视觉关键 词信息的紧凑视觉签名发送至服务端模块；

所述服务端模块用于根据从移动终端模块接收到的所述紧凑视觉签名 进行特征匹配，获得查询关联信息，并将该查询关联信息返回给终端模块。

其中，所述服务端模块还用于通过字典学习得到所述第一字典和所述 第二字典。

与现有技术相比，本发明具有下列技术效果：

1、本发明能够大幅减少内存占用，缩短词表训练时间和特征提取时 间，特别适合应用于移动终端。

2、本发明提供的面向局部特征匹配的协同字典学习算法能够帮助提 高检索系统的查全率。

3、本发明的软分配方法能够大幅提高视觉搜索的检索性能。

附图说明

以下，结合附图来详细说明本发明的实施例，其中：

图1示出了现有技术中一种典型的移动视觉搜索的构架；

图2示出了本发明一个实施例的二层聚类的一个示例；

图3示出了本发明一个实施例的一个字典学习过程的示例图；

图4示出了本发明一个实施例中基于第一字典和第二字典进行高维视 觉词袋特征量化的示例图；

图5示出了本发明一个实施例中的图像高维视觉词袋特征量化的示意 图；

图6示出了本发明一个实施例中的BoW软分配方法的示意图；

图7示出了本发明一个实施例的基于大词表BoW的移动视觉检索系 统的示意图；

图8示出了本发明一个实施例的基于大词表BoW的移动视觉检索系 统在400万ImageNet数据集上的检索效果图；

图9示出了本发明一个实施例的检索方法中一个倒排索引文档示意图。

具体实施方式

根据本发明的一个实施例，提出了一种基于分段稀疏编码的高维视觉 词袋特征表示方法。视觉词袋特征表示是指采用矢量量化方法将图像的高 维局部特征向量映射为大词表BoW中的视觉关键词，从而减少终端至服 务器端的传输流量、降低网络延迟，以及降低服务器端特征存储占用。而 本实施例的高维视觉词袋特征量化方法开创性地提出“小码表大词表”的 思想，使得特征量化计算对终端内存的占用和耗时大幅减少，原创性地解 决了目前现有方法因占用内存过大而不能用于移动终端的问题，从而使 BoW广泛应用于移动视觉搜索成为可能。

本实施例采用了一种特殊的两层聚类方法，实现高维局部特征向量与 大词表BoW之间的映射。本实施例中，将高维视觉局部特征向量分成两 段，每一段分别对应于一个稀疏编码字典。以SIFT特征为例进行说明， SIFT特征共有128维，分段后可获得两个64维的分段，这两个64维的分 段也可以看成两个64维的特征向量。为便于描述，本文中将特征向量的 前半段称为特征向量第一分段，所对应的稀疏编码字典称为一级字典，将 特征向量的前半段称为特征向量第二分段，所对应的稀疏编码字典称为二 级字典。

图2示出了本实施例的二层聚类的一个示例。如图2所示，假设一级 字典包括K个字典基元，那么基于一级字典的基元序号I₁就可以映射为K 个子类，即任意一个高维视觉局部特征均可以根据其特征向量第一分段的 稀疏编码最大非零元对应的基元序号I₁进行第一层分类。并且这个第一层 可按序号I₁分成K个一级子类。在每个一级子类下，再根据特征向量第二 分段进行第二层分类，假设二级字典也包括K个字典基元，那么每个一级 子类下还可以进一步划分为K个二级子类。这样，整个高维视觉局部特征 能够映射为K²个二级子类，如果将每个二级子类标记为BoW中的一个视 觉关键词，那么就能将一个高维视觉局部特征向量量化为具有K²规模的 大词表BoW中的一个视觉关键词。

一级字典和二级字典均可利用已知的训练集采用基于稀疏编码和字 典学习技术进行字典学习而获得。图3示出了一个字典学习过程的示例图， 包括下列步骤：

1)对已知图像进行局部特征提取，获得图像中的局部特征点及其局 部特征向量(描述子)。

2)基于维度将每个局部特征向量分成第一分段和第二分段，从训练 集中提取的所有局部特征点的特征向量第一分段组成第一数据矩阵，所有 局部特征点的特征向量第二分段组成第二数据矩阵。参考图3，假设训练 集的所有图像共提取出N个局部特征点，局部特征向量的维度为d,则第一 数据矩阵中的行代表第1至第d/2维度，第一数据矩阵中的列代表第1至 第N个局部特征点，第二数据矩阵中的行代表第d/2+1至第d维度，第二 数据矩阵中的列代表第1至第N个局部特征点。在图3中，用P₁、P₂、…、 P_N代表第一或第二数据矩阵的列向量。

3)对于第一数据矩阵，基于在线学习算法(Online Dictionary Learning)， 进行稀疏非负矩阵分解(Sparse NMF)，得到第一字典D₁，对于第二数据矩 阵，基于在线学习算法，进行稀疏非负矩阵分解，得到第二字典D₂。字典 学习采用稀疏非负矩阵分解(Sparse NMF)进行字典学习，得到稀疏编码的 字典。其中，在线学习算法可参考文献：J.Mairal,F.Bach,J.Ponce,and G.Sapiro,“Online  learning for matrix factorization and sparse coding,”Journal of Machine Learning Research(JMLR),11:19– 60,March2010.。

设表示由N个局部特征组成的第一或第二数据矩阵，x_i表示第i个局部特征的特征向量分段。表示K个基元组成的字 典，α为样本i的稀疏编码α_i构成的系数矩阵，则图像的Sparse NMF分解可 表示为：

X≈αD,s.t.D＞0,α＞0

则D和α的求解可转化为优化问题：

$\underset{D,{\alpha }_i}{\min }\underset{i=1}{\overset{N}{\Sigma }}(\frac{1}{2}{\left|\right|x_i-{\alpha }_{i}D\left|\right|}^2+\lambda {\left|\right|{\alpha }_i\left|\right|}_0),s.t.D>0,\forall {\alpha }_i>0---\left(1\right)$

当D和α_i均未知时，求两者称为字典学习，在每次迭代时，交替固定D 和α_i，便可迭代求解D和α_i。当字典D已知，求α_i则称为稀疏编码。本实施 例可用在线字典学习算法求解D。当求出D后，(1)式转化为Lasso问题，可 用高效的LARS-Lasso算法求解样本i的稀疏编码α_i。LARS-Lasso算法可参考 文献：T.J.I.Efron,Bradley；Hastie and R.Tibshirani,“Least angle regression,”Annals of Statistics, 32(2):407–499,2004.。在线的字典学习方法非常高效，加上求解稀疏编码的 LARS-LASSO算法也非常高效，对于10M个SIFT特征，训练仅约为半小时， 因而大幅提高了词表训练的效率。

图4示出了基于第一字典和第二字典进行高维视觉词袋特征量化的示 意图。如图4所示，基于字典学习得到的第一字典和第二字典，进行高维 视觉词袋特征量化方法包括下列步骤：

1)从图像中提取局部特征点及其局部特征向量，并对该局部特征向 量进行分段，得到相应的特征向量第一分段和第二分段。

2)基于第一字典，对特征向量第一分段进行稀疏编码，得到相应的 稀疏编码系数向量α₁＝[α₁₁，α₁₂，...，α_1K]。基于第二字典，对特征向量第二分 段的进行稀疏编码，得到相应的稀疏编码系数向量α₂＝[α₂₁，α₂₂，...，α_2K]。

3)选择α₁＝[α₁₁，α₁₂，...，α_1K]、α₂＝[α₂₁，α₂₂，...，α_2K]这两个稀疏编码系数中 最大的元素所对应的字典基元索引号I₁和I₂。

4)用整数形式的索引号Index来表示字典基元索引号I₁和I₂的组合。

本步骤中，用

Index＝I₁×K+I₂     (2)

惟一地表示最大稀疏基元对应的组合[I₁，I₂]。这样，每一个局部特征点通过分 段稀疏编码表示成一个由式(2)生成整数形式的索引号Index，Index即可作为 该局部特征点聚类的视觉关键词索引号，从而完成高维局部特征的量化。根 据字典基元索引号I₁和I₂进行一级分类和二级分类，即可得到相应的大词表 BoW的视觉关键词，从而将当前局部特征点分配到大词表BoW中与索引 号组合[I₁，I₂]一一对应的视觉关键词中。需要说明的是，式(2)的编码方 式可以被任何能够携带字典基元索引号I₁和I₂信息的编码方式替代，只要每 个索引号的组合[I₁，I₂]所对应的编码唯一即可。

本实施例中，一级字典、二级字典均为稀疏编码字典，稀疏编码字典 也可称为冗余字典。以64维的分段SIFT特征向量为例进行说明，冗余字 典实际上是一个64*1024的变换矩阵，该变换矩阵，主要将一个非稀疏的 向量变换到一个稀疏向量，稀疏就是指这个向量中绝大部分元素为0。用 冗余字典将64维的分段SIFT特征向量分段(其中大部分维度的值不为0， 因而不稀疏)变成一个1024维的稀疏向量(只有少数几个非零元)，然后 用最大非零元对应的列号作为相应的子集编号I₁或I₂(即字典基元索引号I₁、 I₂)。因为1024>64，也就是列向量个数大于列向量维数，因此这个变换矩 阵不是方阵(传统的DCT、小波变换矩阵都是方阵，行数等于列数)，是 冗余的，所以称为冗余字典。冗余字典共有1024个64维的列向量组成， 每个64维的列向量就是一个字典基元，一个字典基元可以看成一个64维 分段SIFT特征向量分段的视觉关键词。这样，一级字典和二级字典各有 1024个视觉关键词，二者组合可以表示1024×1024，即1M个视觉关键词， 也就是说，上述一级字典和二级字典的组合即可对应于具有1M个视觉关 键词的大词表BoW。

通常评价一个检索系统的好坏不能单独只看准确率(Precision)或查全 率(Recall)，而是应该同时考虑准确率和查全率，也就是通常说的ROC曲 线。通常用同时反映两者折衷的平均精度AP(Average Precision)来表示， 多个查询图像的AP，称为MAP(Mean AP)。实验表明，本实施例的检索 效果(MAP)优于其它层次化的视觉检索方案(例如HKM方案)，并且 在移动终端处，对高维局部特征进行稀疏表示所用的两个字典所占用内存 只有512K,为现有所有方法的约1/1000，这使得特征量化计算对终端内存 的占用和耗时大幅减少，原创性地解决了目前现有方法因占用内存过大而 不能用于移动终端的问题，从而使BoW广泛应用于移动视觉搜索成为可 能。

图5示出了图像BoW特征生成的示意图。图像BoW特征生成时，首 先统计图像在词表上的频率直方图，词表规模K²，当K＝1024(最后可通过 实验确定最佳的字典大小K)，该词表高达上百万维(1M)，可以直接记录 非零元的索引(即Index)作为图像的特征，每一个索引对应图像中的一个 局部特征点，记录m个索引，就表示该图像具有m个局部特征点，服务器 端在接收到这m个索引后，即可根据m个索引通过倒排文档进行匹配和几 何一致性校验，查找到和查询图像相似的图像，并进而实现图像的视觉搜索。 需说明的是，图像的视觉搜索不仅查找局部特征点，而且要在库中查找与查 询图像相似度最高(通常情况下特征点匹配得最多的库中图像与查询图像最 相似)的图像。一般根据相似度从高到低排序。图8示出了一个基于大词表 BoW的移动视觉检索系统在400万ImageNet数据集上的检索效果图，图 8中，右边窗口的第一行对应排序为1～4，第二行为5～8，依此类推。排序 越靠前，检索到的图像和查询图像的相似度越高。

图4的实施例中，其步骤3)中选择了稀疏编码系数中最大的元素所对 应的字典基元的索引号来代表相应局部特征点的索引信息，这样，每个局部 特征点会被分配到BoW中一个聚类(对应于一个视觉关键词)。而图6示出 了根据本发明的另一个实施例的BoW软分配方法的示意图。这种分配方 法下，每个局部特征点会被分配到BoW中的四个聚类(对应于四个视觉关 键词)。图6的实施例中，在进行高维视觉词袋特征量化时，步骤3)中， 从α₁＝[α₁₁，α₁₂，...，α_1K]中选出前两大元素所对应的字典基元索引号，记为I₁₁和I₁₂，从α₂＝[α₂₁，α₂₂，...，α_2K]中也选出前两大元素所对应的字典基元索引号， 记为I₂₁和I₂₂，对于一个局部特征点，可以将之软分配到图6箭头所示的四 个视觉关键词中：[I₁₁、I₂₁][I₁₁、I₂₂][I₁₂、I₁₁]和[I₁₂、I₂₂]中。在步骤4)中， 按式(2)分别计算[I₁₁、I₂₁][I₁₁、I₂₂][I₁₂、I₁₁]和[I₁₂、I₂₂]的索引号，从而用 整数形式的索引号分别表示[I₁₁、I₂₁][I₁₁、I₂₂][I₁₂、I₁₁]和[I₁₂、I₂₂]。图6的 实施例使用了BoW软分配技术，在进行高维视觉词袋特征量化的同时保 留了局部特征点更多的原始信息，实验表明，这种做法能够大幅提高视觉 搜索的检索性能(MAP能提高8％-10％)。

图7示出了根据本发明一个实施例所提出的一种基于大词表BoW的移 动视觉检索系统，该移动视觉检索系统包括移动终端模块和服务端模块， 移动终端模块和服务端模块之间通过移动互联网连接。

移动终端模块用于提取图像的局部特征点及其局部特征向量，基于第 一字典、第二字典获得局部特征向量的分段稀疏表示，根据分段稀疏编码 系数中的非零元素的索引号进行BoW提取与压缩，从而获得代表所提取的 局部特征点的紧凑视觉签名(紧凑视觉签名包括为局部特征点所分配的视 觉关键词信息，另外还包括后续几何验证的特征点位置、尺度和主方向等 信息)，并将该紧凑视觉签名发送至服务器端。移动终端模块还用于接收 服务器端查询关联信息，并显示搜索结果。其中分段稀疏表示可参考前文 的描述，此处不再赘述。

服务端模块用于基于大规模图像库进行局部特征提取，通过字典学习 获得相应的冗余字典(即用于一级分类的第一字典和用于二级分类的第二 字典)，基于冗余字典对局部特征点进行分段稀疏表示，进而根据其中的 非零元素的Index序号建立BoW倒排索引，即将包含该视觉关键词的图像id 和相应后续几何验证的局部特征点位置、尺度和主方向等信息保存到相应 的第Index个链表中，图9示出了一个倒排索引文档的示意图。服务端模块 还用于根据从移动终端模块接收到的紧凑视觉签名，基于倒排索引进行特 征匹配，进而进行几何一致性校验，最终获得查询关联信息，并将该查询 关联信息返回给移动终端模块。

在一个实施例中，基于大词表BoW的移动视觉检索方法包括下列步骤：

步骤1：建立倒排索引。倒排索引本质上是链表的集合，是文本检索中 最基本的数据结构，使用单词(Word)快速检索到包含该单词的文档 (Document)。如图9所示，对于视觉检索来说，每个视觉关键词(相当于 文本检索中的单词，对应一个局部特征量化后的Index)对应一个链表，用 以存储包该视觉关键词的图像(相当于文本检索中的文档)id，以及该局 部特征的元信息(如图9中的f1、f2等)。该信息包括后续几何验证的特征 点位置、尺度和主方向等信息。

步骤2：对于查询图片，按照前文记载的方法提取各局部特征点的紧凑 视觉签名。紧凑视觉签名包括为所有局部特征点所分配的视觉关键词信息， 另外还包括后续几何验证的特征点位置、尺度和主方向等信息。

步骤3：对于查询图片各局部特征点的紧凑视觉签名，基于倒排索引进 行特征匹配，进而进行几何一致性校验，最终获得查询关联信息。

需要说明的是，本发明中，在字典学习过程所采用的在线字典学习算法 也可用MOD算法或者KSVD算法等其它算法替代。MOD算法可参考文献： K.Engan,S.O.Aase,and J.Hakon Husoy.Method of optimal directions for frame design.In  IEEE Int.Conf.Acoust.,Speech,Signal Process-Volume05,ICASSP’99,pages2443–2446, Washington,DC,USA,1999.IEEE Computer Society.。KSVD算法可参考文献：M. Aharon,M.Elad,and A.Bruckstein.K-SVD:An Algorithm for Designing Overcomplete  Dictionaries for Sparse Representation.Signal Processing,IEEE Transactions on[see also  Acoustics,Speech,and Signal Processing,IEEE Transactions on],54(11):4311–4322,2006.。

另外，视觉关键词一般对应一个连续空间的索引号，如1M的BoW， 每个视觉关键词(可以看成一个桶，桶里装的是倒排文档中的一个链表) 的索引号构成的全集就是:0～1024²-1这1M个连续整数。基于公式(2)用 整数形式的索引号Index来表示字典基元索引号I₁和I₂的组合，能够巧妙地将 一级和二级的两个桶号(即索引号I₁和I₂)组成的二维数组一一映射到一维 1M个连续整数所构成空间中的索引号。

另外，本发明的一个优选实施例中，还提出了一种协同字典学习方法。 该方法中，采用稀疏非负矩阵分解(Sparse NMF)进行字典学习时，为了使 得学习到的字典对于相互匹配的局部特征点对，得到的稀疏编码尽可能一 致，利用组稀疏编码(GSC，Group Sparse Coding)技术，通过对同一组内 特征在同一个字典基元上的稀疏表达系数进行正则化，使得优化目标的结 果对于同一组特征稀疏表达所使用的基元是一致的，即可以使同组内的 SIFT特征使用相同的字典基元进行稀疏编码。为了保证同一组对应于同一 个字典基元的稀疏表达系数尽可能相同，本优选实施例中提出在GSC的 优化目标中新加入稀疏编码系数值差异的正则化项，得到优化目标函数：

$\arg \underset{A}{\min }\frac{1}{2}\underset{i1}{\overset{\left|G\right|}{\Sigma }}{\left|\right|x_t-\underset{j=1}{\overset{\left|D\right|}{\Sigma }}{d}_j{\alpha }_{i,j}\left|\right|}_2^2+\lambda \underset{j=1}{\overset{\left|D\right|}{\Sigma }}({\left|\right|{\alpha }_j\left|\right|}_1+\underset{i=1}{\overset{\left|G\right|}{\Sigma }}|{\alpha }_{i,j}-{\alpha }_{i+1,j}\left|\right)---\left(3\right)$

s.t.||α_j||₀≤l,D≥0,A≥0

其中，X＝{x_t}为分段局部特征数据矩阵(即前文中的第一数据矩阵或 第二数据矩阵)，x_t为分段局部特征数据矩阵X中的第t个列向量，每个x_t代表一个局部特征点的特征向量分段。D为待求的冗余字典(即前文中的 第一字典或第二字典)，d_j为冗余字典D的第j个列向量，A为待求的稀疏 编码系数矩阵，α_i,j为稀疏编码系数矩阵A中的元素。λ为正则化系数，用于 调节稀疏性和重构误差之间的权重。为新加入的稀疏编码系数 值差异的正则化项，它起到稳定稀疏编码系数的作用，使得同一个组内的 局部特征向量(例如SIFT局部特征向量)的稀疏编码系数的差异尽可能小。 其中j表示组序号，i表示组内局部特征点的序号。G描述了 训练集X中的分组信息，|G|表示训练集X组的个数。|D|表示冗余字典D中 字典基元向量的个数。l为稀疏编码系数向量α_j中的最大非零元个数，本实 施例中l取4。该优选实施例能够使得优化目标的结果对于同一组局部特征 进行稀疏表达时所使用的基元尽可能一致，从而使生成的BoW特征尽可能 一致。基于本实施例所得到的第一字典和第二字典进行高维视觉词袋特征 量化和匹配搜索，能够进一步地提升检索效果(MAP)，实验表明检索效 果(MAP)大约比采用普通稀疏字典的方案(即采用式(1)的优化目标函 数的方案)提升了3％。

需要说明的是，图像的高维视觉局部特征不仅可以采用128维的SIFT 描述子，也可以采用其它的高维描述子，例如64维的SURF描述子。在 基于维度对局部特征向量进行分段时，两个分段的维度可以是一致的，也 可以不一致，这都是本领域技术人员易于理解的。

最后应说明的是，以上实施例仅用以描述本发明的技术方案而不是对 本技术方法进行限制，本发明在应用上可以延伸为其它的修改、变化、应 用和实施例，并且因此认为所有这样的修改、变化、应用、实施例都在本 发明的精神和教导范围内。