目前大部分图像检索系统都是基于Bag of Words(BoW)模型实现^{[1, 2]}.该模型将数据库所有图像的局部特征量化为视觉词, 然后建立直方图进行比较.但是量化后的视觉词通常降低了局部特征的辨别能力, 并且也不具备特征间的几何关系, 影响检索的准确率.为了提高检索准确率, 通常使用几何验证的办法, 建立检索图像与结果图像之间的几何规则, 通过特征间的几何关系计算结果图像的验证得分, 并以此为依据排序检索结果.由于几何验证方法在原始的检索模型中对局部特征间的几何关系进行判断, 因此提高了检索的准确率.

近几年, 出现了多种几何验证方法用以优化图像检索的效果.基于Ransac^[3]的矩阵转换非常普遍, 但是由于运算开销较大, 只适用于处理前几幅检索图像, 不适于大型数据库.Philbin等^[4]建立了完全的几何一致性约束(Full geometric consistency constraints, FGC), 在查询图像和检索图像间建立仿射变换, 缺点同样是计算开销太大.针对Ransac仅可应用于少量图像的缺陷, Perdoch等^[5]利用在几何空间上离散化的局部几何表示, 有效保持了图像间的几何变换关系, 但在重心向量不确定的条件下, 对于旋转和仿射变换不具备不变性.为了解决这一问题, Jegou等^[6]提出了弱几何一致性(Weak geometric consistency, WGC)方法, 假设正确匹配之间尺度和方向变换具有相同关系, 因此角度和尺度差异直方图有明显的峰值, 以此用于结果优化.Zhao等^[7]改进了Jegou等的弱几何一致性算法, 提出了E-WGC(Enhanced weak geometry consis-tency)方法, 在弱几何一致性基础上考虑了平移变换, 假设正确的匹配之间还具备一致的平移变换关系.Tsai等^[8]提出了位置几何相似性得分(Location geometric similarity scoring, LGSS)算法, 利用距离比例测量几何相似性, 但由于需要枚举局部特征点并构建得分直方图, 因此时间花费稍大.

综上, 现有的几种几何验证方法存在计算开销太大, 难以保证在多种图像变换中的不变性等问题.另外, 对于日常生活中的目标检索, 如图书馆中图书查询, 商店中食品查询, 街道中的车标检索, 医学图像挖掘等, 需要查询的目标均在复杂的背景中, 因此冗余信息过滤成为目标检索的重要研究内容.为了解决这些问题, 本文利用显著区域特征间的距离相似度衡量查询图像与数据库图像的几何一致性.提出了特征点显著性约束的图像检索方法(Feature saliency constraint, FSC), 目的是在复杂背景中快速定位显著目标, 仅利用显著特征的位置关系, 设计一个快速有效的几何验证方法, 提高检索结果的准确度.本文利用最大熵方法自适应地提取图像的显著目标, 过滤冗余特征点, 并在空间金字塔框架下进行图像检索.在获得初始检索结果后利用匹配的显著特征对计算显著区域内任意两对特征点的距离比, 保留满足阈值的比值, 最终得到检索图像几何得分, 并重新排序检索图像.

使用FSC的图像检索方法整体流程如图1所示.首先, 将空间金字塔模型^[9]与基于最大熵的显著目标提取方法^[10]结合, 在视觉单词量化时对其进行编码, 构成了显著空间金字塔模型(Salient spatial pyramid, SSPM).此检索模型可以在复杂的背景中快速定位显著目标, 过滤掉非显著特征, 同时在视觉单词量化时加入了简单空间分布关系, 初步提高了检索的准确度.然后, 提出显著特征间的几何验证方法, 在显著区域内得到最匹配的特征对, 将图像间满足匹配关系的特征点欧氏距离作比较, 在满足阈值的条件下求和算得最终的验证得分.

图1

Fig.1

	Figure Option ViewDownloadNew Window
	图1 基于显著空间的显著几何约束方法整体流程图Fig.1 Complete flow chart of feature saliency constraint based image retrieval

对图像金字塔每级进行空间分层, 并按照网格划分的精细程度对匹配结果加权.由于加入了空间关系, 因而初步提高了检索的精确度.但是由于此检索框架只是在空间格中构造视觉单词直方图, 并没有表现出特征间的空间联系, 因此只能在有限程度上提高检索效率.针对这个问题, 本文讨论使用基于显著信息的几何约束方法.

首先, 提取显著特征如下:

Qs={SqiSqi⊆G(Iq)}(6)

Ds={SdiSdi⊆G(IDB)}(7)

式(6)(7)分别表示查询图像与数据库图像落入图像显著区域的SIFT特征集合. G(Iq)、G(IDB)分别表示查询图像与数据库图像中的显著区域.

如图2所示, a表示处理前的查询图像, b为显著处理后的查询图像, c为处理前的数据库图像, d为处理后的数据库图像.图中的黑色圆点表示图像的SIFT特征, b与d的白色区域则表示查询图像与数据库图像的显著区域.

根据显著特征进行匹配, 在匹配时判断匹配特征是否位于显著区域内, 最后保留显著区域内匹配的特征对, 可以过滤掉非显著区域误匹配的特征对.将最匹配的特征对存储到匹配列表Match list中.式(6)(7)中得到了查询图像与数据库图像的显著特征集合QS, DS, 建立对应的匹配关系为:

Matchlist=QSΘDS(8)

式中: Θ为特征间欧氏距离匹配方法.

如图3所示, Match list中存放的是满足匹配关系的SIFT特征点, 表中的两列分别表示查询图像与检索图像的特征集合, 每行表示两幅图像最匹配的显著特征对.

图3

Fig.3

	Figure Option ViewDownloadNew Window
	图3 匹配列表Fig.3 Matching list

图4为显著特征匹配过滤冗余特征的过程, 图中a表示处理前查询图像中匹配上的特征点, b表示显著性提取后查询图像在显著区域内匹配上的特征点, c表示处理前检索图像中匹配上的特征点, d表示显著性提取后检索图像在显著区域内匹配上的特征点.经过显著特征提取后, 从b和d可以明显看出, 虚线连线表示的非显著匹配的特征对(1, 1'), (6, 6')被去除, 这种过滤方法可以去除误匹配并且减少冗余的特征对, 同时降低了几何验证过程的运算量且提高了检索的精确度.

图4

Fig.4

	Figure Option ViewDownloadNew Window
	图4 显著特征匹配Fig.4 An illustrate of matching salient features

特征点间的距离比满足在尺度, 旋转以及平移变换的不变性, 与建立图像间完整几何变换关系的Ransac等算法相比, 复杂性大大降低^[8].因此, 在下一步操作中本文利用显著区域内匹配特征间任意两点欧式距离的比值验证查询图像和检索结果之间的几何一致性.具体方法如下:

查询图像I_q 经过显著空间金字塔方法获得了检索结果A_q={I_DB1, et al.I_DBn}, 这里, 仅考虑前n个检索结果.I_q 与A_q 中的图像I_DBi进行特征匹配, 建立Match list, 称为 Mi。几何验证算法可以用下式说明:

Di=dist(la, lb)dist(la', lb')(la, la'), (lb, lb')∈Mi, dist(la, lb)dist(la', lb')→ε(9)

式中:dist(., .)表示特征点的欧氏距离; M_i为由式(8)得到的匹配列表; (la, la'), (lb, lb')为匹配列表M_i中的任意两行.为了限定距离验证只发生在正确匹配之上, D_i表示匹配列表中任意两个显著特征点间的欧氏距离比值趋近于阈值 ε的集合, 其中 ε是一个小于1的常数, 与特征间的尺度比例相关, 在实验中根据数据集确定.若M_i中有 Count(Mi)个匹配对, 则D_i中最多具有 CCount(Mi)2个元素.将D_i中的所有元素汇总即为 IDBi的几何验证得分, 如下式所示:

Scorei=∑Z∈DiZ(10)

这种显著性约束的几何验证方法可以用图5说明.假设匹配列表M_i中有4对匹配特征对, 图5中a表示查询图像I_q特征点两两之间的欧式距离, 图中的不同线型表示不同的距离值, b表示查询图像中相关特征点间欧式距离的比值满足阈值条件的集合, c表示检索图像中相关特征点间任意两点的欧式距离, d表示检索图像中满足阈值条件的特征点间的欧式距离.图5中的a和c中相同线型的线段长度代表匹配列表中的两个匹配对构成的线段分别在查询图像与检索图像中相关特征点间的欧氏距离.例如, 在Match list中得到两组特征对(2, 2')(3, 3'), 因此查询图像中(2, 3)两点之间的连线距离表示两个特征点2和3间的欧氏距离 dist(l2, l3), 数据库图像中(2', 3')两点间的连线距离表示两个特征点2'和3'间的欧式距离 dist(l2', l3')。特征点间相同线型的连线距离可以计算比值 v=dist(l2, l3)/dist(l2', l3'),根据阈值 ε,将距离比值趋近于阈值的特征对保留.如果查询图像中特征点(2, 3), (2, 4)与检索图像中匹配的特征点(2', 3'), (2', 4')间的距离比值不满足阈值要求, 连线被去除, 如图5中的b和d所示.最后, 计算保留的特征对间距离比值的总和即为最终的几何得分.

图5

Fig.5

	Figure Option ViewDownloadNew Window
	图5 几何距离约束算法Fig.5 Geometric distance constraint verification method

为了验证FSC算法的检索性能, 将本文与目前几种常用的几何验证方法^{[3, 8, 11, 12, 13]}作性能对比.每种方法均对检索结果的前100幅图像做几何验证.在实验中, 选用DupImage^[14]和University of Kentucky的测试集作为图像数据库.该测试集共包含11 304幅图像.实验环境如下:CPU为Core i3, 2.27 GHz, 2G RAM, 32位操作系统, Matlab R2010a.

为了评价算法在复杂背景中检索显著物体的鲁棒性, 随机选取DupImage图片库中6组数据集中任意10幅图像(共60幅图像)作为查询图像, 并以Precision和Recall, 以及运行时间作为衡量标准.实验中 ε设为0.85.此外, 与SPM的做法相同^[9], 实验中设定视觉词大小为400.

实验中, 将BoW/SPM/SSPM三种检索方法分别应用Ransac/LGSS/FCS几何验证算法, 构成A~H共8种检索框架进行性能对比.具体算法构成如表1所示.

表1

Table 1

表1(Table 1)

表1 实验中使用的检索方法 Table 1 Retrieval methods in experiments 方法名称 特征提取算法 检索方法 几何验证方法 A SIFT BoW - B SIFT SPM - C SIFT& Saliency SSPM - D SIFT SPM Ransac E SIFT SPM LGSS F SIFT& Saliency SSPM Ransac G SIFT& Saliency SSPM LGSS H SIFT& Saliency SSPM FCS

表1 实验中使用的检索方法 Table 1 Retrieval methods in experiments

图6给出了FSC算法与其他检索算法的检索结果.其中箭头左边为查询图像, 箭头右边为检索结果的前10幅图像.

图6

Fig.6

	Figure Option ViewDownloadNew Window
	图6 与传统检索模型对比图Fig.6 Contrast diagram with the traditional retrieval model

A组表示用BoW模型检索的结果, 有8幅错误图像.B组表示使用空间金字塔模型检索后的结果, 有6幅错误图像.C组则是显著空间金字塔模型检索后的结果, 显示7幅错误图像.D组表示在空间金字塔模型检索后使用Ransac^[3]进行几何验证的检索结果, E组为LGSS几何验证方法对检索图像重新排序.F组, G组分别表示在显著空间金字塔检索框架基础上, 使用Ransac和LGSS进行几何验证的结果.H组则是本文提出的FSC算法.

表2给出了FSC算法与其他检索方法的在6个图像集中的检索性能比较, 表3为各个方法的检索时间对比.

表2

Table 2

表2(Table 2)

表2 检索性能比较 Table 2 Retrieval performance comparison% 图像库 Precision/Recall A B C D E F G H 1.Gothic 37.74 8.91 50.00 11.80 51.00 12.44 77.00 17.12 79.00 18.24 79.00 18.24 80.00 18.52 81.00 19.76 2.Apple 21.39 8.56 31.00 12.40 53.00 21.20 50.00 20.00 55.00 22.00 68.00 26.08 84.00 33.60 85.00 34.00 3.Starbucks 5.28 0.91 7.00 1.21 19.00 3.28 20.00 3.45 31.00 5.34 56.00 68.00 11.13 70.00 12.07 4.all-star 31.87 7.59 51.00 12.14 51.25 12.96 58.00 13.81 57.00 13.57 81.25 19.48 89.00 21.19 90.00 21.43 5.Beijing 9.41 2.05 13.00 2.83 31.00 6.74 22.00 4.78 24.00 5.22 54.00 10.61 55.00 11.96 56.00 12.17 6.Sam 21.62 6.21 31.25 8.68 37.00 10.28 51.00 14.17 52.00 14.44 55.00 15.33 60.00 16.67 61.25 17.01

表2 检索性能比较 Table 2 Retrieval performance comparison%

从表2可以看到, FSC算法的检索准确度明显超过传统的BoW检索模型.同时, 通过(B, C), (D, F), (E, G)之间的比较可知, 在局部特征中加入显著信息过滤了冗余的特征, 从而提高了检索的准确度, 最终FSC算法的检索性能优于以上提出的检索方法.从表3的计算时间可以看出, 加入显著性约束的检索方法总体耗时较短, 特别是将显著性加入几何验证算法中效果更为明显.由于SPM特征量化时添加了空间布局信息, 每幅图像均匹配8400bin直方图, 相比实验中传统BoW检索方法(400个视觉词)匹配400bin直方图需要较多的计算时间, 基于SPM方法, 本次实验使用VLfeat工具箱的Ransac算法.在 N个特征点构成的数据集中每次采样其中的4个数据点, 时间复杂性为 O(N4),LGSS和FSC算法则在 N个匹配对中任取两点做距离匹配, 时间复杂性为O(N²).而FSC算法是在显著区域内任取两点做距离比, 其特征点数目相比LGSS算法大幅缩小, 同时在计算几何得分时没有使用LGSS算法的构建软直方图的方式, 而是利用阈值 ε约束特征对的选取, 更为简单.

表3

Table 3

表3(Table 3)

表3 运行时间比较 Table 3 Running time comparison s 项目 A B C D E F G H 特征提取(特征点数) 0.2384 (1135) 0.2384 (1135) 0.7606 (513) 0.2384 (1135) 0.2384 (1135) 0.7606 (513) 0.7606 (513) 0.7606 (513) 检索 0.1682 1.9334 1.7575 1.9334 1.9334 1.7575 1.7575 1.7575 几何验证 - - - 52.1986 4.4812 11.6467 2.3464 2.1296 总计 0.4066 2.1718 2.5181 54.3704 6.6530 14.1648 4.8645 4.6477

表3 运行时间比较 Table 3 Running time comparison s

提出了一种显著性约束的图像检索方法.该算法使用视觉显著目标的自适应分割方法, 定位显著目标, 结合空间金字塔模型, 构成显著空间金字塔模型, 在初步检索中提高了精确度.利用显著特征内互相匹配并且满足距离比值阈值的匹配对集合, 求其和作为几何验证方法.根据几何得分重新排列检索结果.该方法不仅能在复杂背景下准确检索所需图像, 同时提高了几何验证过程的运算效率.实验中, 使用DupImage和University of Kentucky测试集与其他几何验证方法作比较, 本文检索方法在保证速度的前提下, 提高了检索的精确度.

在未来的工作中, 将针对图像中显著物体形态相近难以区分的大规模数据库提出更严格的几何验证方法, 以实现鲁棒性更好的几何变换方法.