作者简介:赵宏伟(1962-),男,教授,博士生导师.研究方向:智能信息系统与嵌入式技术.E-mail:zhaohw@jlu.edu.cn
提出了用基于局部邻域约束的空间验证方法去验证错误的匹配特征。首先,计算匹配特征对的局部邻域范围,根据局部邻域内相关匹配特征对的数量定义该匹配对的局部邻域约束值,并判断是否满足局部邻域的约束条件。若满足,则基于局部邻域内的所有相关匹配特征的排列顺序,验证其是否满足一致的几何变换关系。实验结果表明:SVLRC方法具有较低的时间复杂度,改善了最终检索结果的精确度。
A Spatial Verification method based on Local Regional Constraints (SVLRC) is developed to remove false positive matches. First, the local region range of a center match pair is calculated. Then, the constraint value of the centre matches is defined according to the number of other matches in the local regions and whether the center match pairs satisfy the condition of local region constraint is judged. If the condition is met, whether all the matches in the local regions follow consistent geometric transformation is estimated based on geometric order. Extensive experiments demonstrate that the SVLRC can improve the retrieval accuracy significantly with low computation cost.
随着多媒体信息的迅速发展, 图像检索技术已成为研究热点[1, 2], 然而大多数图像检索系统都是基于Bag of Words(BoW)模型[3]实现, 即将图像中的局部特征量化为视觉词并建立直方图检索图像。然而, 由于量化后的视觉词缺少了特征间的空间关系, 降低了局部特征的辨别能力, 会产生错误的匹配结果并影响检索性能。因此, 目前很多研究在得到匹配特征后, 通过几何约束的方式在后验证步骤中过滤错误的匹配特征对。这些方法通常计算整幅图像中的所有匹配特征对是否满足一致的几何变换关系, 并且可以分为全匹配和弱匹配两种方式。
全匹配方法通常基于Ransac算法[4]计算查询图像与候选图像的仿射变换, 这种方式可以有效地验证匹配特征的几何一致性, 但耗时太长, 只适用于验证少量图像。弱匹配方法可以在不显示计算仿射变换矩阵的情况下验证匹配特征的几何一致性, Jegou等[5]提出了Weak geometric consistency(WGC)方法, 假设在不同的尺度和旋转角度变换下, 会出现明显的峰值, 以此过滤错误的匹配特征。Tsai等[6]提出了Location geometric similarity scoring(LGSS)方法使用任意两点特征的欧式距离比, 验证几何一致性, 有效地提高了运算效率。进而, Zhao等[7]提出了Triangle spatial pattern(TSP)方法, 利用更多的点探索匹配特征间的几何关系, 通过验证相似三角形的数量来度量几何一致性。Zhou等[8]提出了新的几何编码方法(GC), 通过轴线编码和方形编码严格地描述了局部特征间的几何关系。
无论是全匹配还是弱匹配, 都是计算整幅图像中所有匹配特征间的空间关系; 然而在后验证步骤中, 有些不相关匹配特征的计算对于改善检索性能的作用不大。不论相似区域是部分图像还是整幅图像, 均要满足相似的局部区域中所有正确匹配形变相似的特点。因此只需要验证局部区域内的匹配特征是否满足一致的几何关系即可, 没有必要计算局部区域外的不相关匹配特征。
针对上述现象, Xie等[9]提出了Local geometric consistency(LGC)方法, 假设图像发生形变时, 基于局部区域特征相似的特点, 考虑了匹配特征相邻区域特征点的信息, 精确计算了匹配特征间的变换矩阵。然而, 对于一对匹配特征, LGC方法只是计算了最邻近的10对匹配特征的相关信息。如果局部区域内并不存在匹配特征, 这种方法很难描述局部区域内特征间的空间关系, 因此不相关特征仍然参与到在后验证步骤中。
本文通过局部邻域内匹配特征对的数量, 定义局部邻域约束值, 以此判断是否满足局部邻域的约束条件。若满足约束条件, 则计算局部邻域内的所有相关匹配特征是否满足一致的几何变换, 并以此建立后验证准则, 并对检索结果重新排序。
图1为局部邻域约束的处理流程, 其中(a)表示查询图像与候选图像的9个匹配特征对。(b)中红色圆表示匹配对(q1, d1')基于特征的尺度参数得到的局部邻域。(c)表示局部邻域内共同匹配特征作用于中心匹配对(q1, d1')的约束关系, 粗实线双箭头所指的特征点位于中心匹配对的局部邻域内, 被视为相关匹配的特征, 线虚细双箭头指的特征则表示不相关的匹配特征。
在查询图像Iq与候选图像Id中, Q=(q1, q2, …, qK), D=(d1', d2', …, dK')分别表示特征集合。以此为基础, 进行SIFT特征的匹配, 进而得到两幅图像的匹配特征集M(Q, D)=
首先, 选择一个匹配对(qi(xi, yi, desi, scli, θ i), di'(xi', yi', desi', scli', θ i'))作为测试中心匹配对, 验证其是否为正确匹配对。然后, 选取测试中心匹配特征的局部邻域, 其范围定义如下:
式中:scli与scli'分别表示qi与di'中尺度参数。σ constant是控制局部邻域大小的参数, 在实验2.3部分进行分析。
其次, 筛选局部邻域中的共同匹配特征, 并对测试中心匹配特征约束。共同匹配特征定义如下:
其中dist(· , · )指一对特征描述符的欧氏距离。最后计算该匹配对的局部邻域约束值。
式中:CM(Q, D)是查询图像与候选图像匹配特征对的数量, 在图1示例中, CM(Q, D)=9。
本文通过测试中心匹配对的局部邻域内共同匹配特征在横向与纵向中的排列顺序是否一致, 验证该测试匹配特征是否正确。
首先, 建立查询图像与候选图像间匹配特征点的排序列表。该列表是根据查询图像与候选图像匹配特征点的位置信息, 并以横向与纵向两种方式将特征点的坐标升序排列, 生成特征点的横向排列序号#num_x与纵向排列序号#num_y。图2给出查询图像中匹配特征点的排序列表的实例。
然后, 根据以上得到的测试中心匹配对的局部邻域内共同匹配特征与匹配特征点在排序列表中的特征排列序号, 计算测试中心匹配中, 局部邻域内共同匹配特征间的位置关系, 计算如下:
其中, (qm, dm')∈ ComMatc
进一步, 根据得到的查询图像与候选图像中测试中心匹配对的局部邻域内共同匹配对间的横向坐标关系与纵向坐标关系, 对其验证是否一致, 验证定义式如下:
当查询图像中D_x(qi, qm, qn)与候选图像中D_x(di', dm', dn')同时大于0, 或者D_x(qi, qm, qn), D_x(di', dm', dn')同时小于0时, 该匹配特征对(qm, dm'), (qn, dn'), 在横向坐标关系中, 验证正确, Verify_x((qi, di'), (qm, dm'), (qn, dn'))=1, 即cond1; 若D_x(qi, qm, qn)大于0, D_x(di', dm', dn')小于0, 或者D_x(qi, qm, qn)小于0, D_x(di', dm', dn')大于0时, 验证错误, Verify_x((qi, di'), (qm, dm'), (qn, dn'))=0, 即cond2。
同理, 当D_y(qi, qm, qn), D_y(di', dm', dn')同时大于0, 或者同时小于0时, 匹配特征对在纵向坐标关系中, 验证正确, Verify_y((qi, di'), (qm, dm'), (qn, dn'))=1, 即cond3; 反之, 验证错误, Verify_y((qi, di'), (qm, dm'), (qn, dn'))=0, 即cond4。
从而, 根据局部邻域中匹配特征在横向与纵向的验证信息, 计算该测试中心匹配特征在局部邻域内的几何得分, 如下:
其中, m→ n表示局部邻域匹配特征中, id号为n的特征与id号为m的特征之间的约束关系。为了提高计算效率, 本文并非验证共同匹配对中所有特征点间的约束关系, 只是计算了共同匹配特征点的排序列表中相邻特征id号间的约束关系。因此该约束关系可表示为, 特征id号为n是大于特征id号为m的最小id号。如图1所示, 当测试中心匹配对为(q1, d1'), m=3时, 在查询图像的局部邻域内共同匹配特征{q3, q5, q9}中, 大于特征q3的id号3的最小id号为特征q5id号5, 因此n=5。几何得分Score(qi, di')表示中心匹配对(qi, di')的局部邻域内所有共同匹配特征点在横向坐标关系与纵向坐标关系中, 排列顺序一致的最多数量。
假设如果该得分大于阈值δ 2, 判断测试匹配对(qi, di')正确; 反之, 错误。本文定义阈值δ 2=0.3×
本文通过检索精确度与检索时间验证SVLRC的检索性能。并与目前几种普遍的几何验证方法[4, 5, 6, 7, 8, 9]作比较。实验中计算初始检索后的前1000幅图像的几何得分, 并重排序。在CPU为Core i5, 3.30 GHz, 8 GRAM, 64位的WIN7操作系统, Matlab R2012a中进行测试。
实验数据为两组数据集:第一组为DupImage数据集[10], 包含1104幅图像, 并分为33组。本文随机选择100幅作为测试图像, 并以mAP[11]作为检索精度的度量方式。第二组为Mobile数据集[12], 包含400幅图像。同时也提供了手机拍摄的2500幅测试图像集。以Top-10作为衡量精确度的标准。每组测试集从图像库Ukbenchc中选取一定数量的图像作为混淆图像, 最终两组数据集的图像总数均为10 000幅。
本文是在传统的BoW检索模型的基础上提取SIFT特征。同时记录特征点的位置信息, 尺度作为几何验证的计算条件。提取特征前, 将大尺寸图像降采样为小于500* 500。并采用分级树形的方法[11]生成1 M个视觉词。使用倒排文件方式索引图像, 如图3所示, 每个视觉词都与多个索引特征相链, 其中每个索引特征包含图像的ID、特征位置、尺度参数。实验中所有几何验证方法都是对基于BoW得到初始检索结果的前1000幅图像进行验证重排序的。
在本文SVLRC的方法中, 参数σ constant是通过控制局部邻域的大小范围确定相关匹配特征的个数, 并影响检索性能。本文测试不同的σ constant值所对应的检索性能, 并确定最优的σ constant。
不同σ constant值对第一组数据集DupImage检索性能的影响见图4, 同时给出了不同σ constant值所对应的在后验证阶段中的计算时间。
从图4可知σ constant值越大, 中心匹配特征对的局部邻域范围越大, 在过滤不相关匹配特征的前提下, 可以得到更多相关匹配特征, 并提高检索的精确度。然而, 过大的σ constant值, 也可能导致一些不相关的匹配特征参与在后验证阶段中, 最终影响检索性能。对于时间消耗, σ constant值越大, 在后验证阶段计算匹配特征的数量越多, 并导致消耗更多的计算时间。基于上述的考虑, 对于SVLRC方法, 当σ constant=40时, mAP为0.8109, 计算时间为0.8697 s, 此时为参数σ constant的最优选择, 并在下面的实验中均采用这个参数设定。
本文分析了SVLRC方法对检索性能的影响, 并与其他7种几何验证方法(BoW[3], LGSS[6], WGC[5], LGC[9], TSP[7], RANSAC[4], GC[8])的检索精确度和计算时间进行了比较, 如表1所示。若所比较算法的程序中含有参数, 则采用它们的默认值, 并且在第一组DupImage数据集中, 以mAP作为精确度的衡量标准, 在第二组Mobile数据集中, 以Top-10作为精确度的衡量标准。由于RANSAC耗时较大, 因此只对初始检索结果的前300幅图像进行验证重排序。
通过表1中检索精确度的值可以明显看出, 传统的BoW算法忽略了特征间的几何关系而使检索效率较低。而本文所提出的基于局部邻域约束的空间验证方法, 重点强调特征描述子之间的几何关系, 从而进一步提高了检索性能。关于其他几何验证方法, LGSS两点编码时, 验证特征匹配很不稳定; WGC主要假设查询图像与候选图像的变换一致, 却无法处理图像间的非刚性形变; RANSAC与TSP都是只编码了特征点的位置信息, 无法全面反应匹配特征间的空间关系; 虽然GC完全利用特征的几何信息(尺度、方向、空间位置), 但不相关特征在后验证中的计算也对检索性能产生了影响; 对于LGC, 在几何编码中只是计算了最邻近的10对匹配特征的相关信息, 如果局部区域内并不存在匹配特征, 此时不相关特征仍然会计算在后验证步骤中; 以上叙述的原因都会影响检索性能。
对表1关于每幅图像的平均查询时间的分析, 在众多几何验证方法的对比中可看出, 相比WGC(0.3237 s), LGSS(0.4008 s)计算的是两点的距离比, 而不是简单的加减运算; LGC(0.5261 s)又额外考虑了最邻近的10对匹配特征的信息, 精确计算了匹配特征间的变换矩阵; GC(2.4377 s)提出了更加复杂的编码方法(轴线编码和方形编码), 严格地描述了局部特征间的几何关系; TSP(7.7272 s)通过更多的点计算特征间的几何关系; 由于RANSAC(15.1747 s)通过大量的随机取样, 计算仿射变换, 因此耗时最多。最后, SVLRC在验证特征间几何关系的前提下, 通过定义匹配特征中局部邻域的约束方法, 过滤不相关的匹配特征对, 不仅减少了后验证阶段特征的计算数量, 也提高了验证错误匹配特征的准确度。
在复杂背景的目标检索的研究中, 由于传统检索模型(BoW)忽略了特征间的几何关系, 导致检索效率降低。而且, 目前大多数几何验证方法都是计算整幅图像中所有匹配特征间的空间关系, 然而, 在后验证步骤中, 不相关匹配特征的计算对于改善检索性能的作用不大。因此, 本文提出基于局部邻域约束的空间验证方法, 通过定义匹配特征的局部邻域范围, 过滤不相关的匹配特征对, 最后计算相关匹配特征是否满足一致的几何变换。实验中, 利用DupImage和Mobile数据集, 与其他常用的几何验证方法作比较, 结果表明, 本文提出的方法可以在保证检索速度的前提下, 提高检索的精确度。
The authors have declared that no competing interests exist.
[1] |
|
[2] |
|
[3] |
|
[4] |
|
[5] |
|
[6] |
|
[7] |
|
[8] |
|
[9] |
|
[10] |
|
[11] |
|
[12] |
|