基于局部邻域约束的空间验证方法-赵宏伟.pdf

《基于局部邻域约束的空间验证方法-赵宏伟.pdf》由会员分享，可在线阅读，更多相关《基于局部邻域约束的空间验证方法-赵宏伟.pdf（6页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第46卷第1期2016年1月吉林大学学报(工学版)Journal of Jilin University(Engineering and Technology Edition)V0146 No1Jan2016基于局部邻域约束的空间验证方法赵 宏伟12，李清亮1 ，汤寰宇1，臧雪柏1(1吉林大学计算机科学与技术学院，长春130012；2吉林大学符号计算与知识工程教育部重点实验室，长春130012)摘 要：提出了用基于局部邻域约束的空间验证方法去验证错误的匹配特征。首先，计算匹配特征对的局部邻域范围，根据局部邻域内相关匹配特征对的数量定义该匹配对的局部邻域约束值，并判断是否满足局部邻域的约束条件。

2、若满足，则基于局部邻域内的所有相关匹配特征的排列顺序，验证其是否满足一致的几何变换关系。实验结果表明：SVLRC方法具有较低的时间复杂度，改善了最终检索结果的精确度。关键词：计算机应用；图像检索；Bag of Words模型；局部邻域；空间约束；后验证中图分类号：TP39141 文献标志码：A 文章编号：16715497(2016)01026506DOI：1013229jcnkijdxbgxb201601040Spatial verification method based on local regional constraintZHAO Hongweil”，LI Qinglian91，TA

3、NG Huanyul，ZANG Xuebail(1College of Computer Science and Technology，Jilin University，Changchun 130012，China：2Key Laboratory ofSymbolic Computation and Knowledge Engineering of Ministry of Education，Jilin University，Changchun 130012，China)Abstract：A Spatial Verification method based on Local Regional

4、 Constraints(SVLRC)is developed toremove false positive matchesFirst，the local region range of a center match pair is calculatedThen，the constraint value of the centre matches iS defined according to the number of other matches in thelocal regions and whether the center match pairs satisfy the condi

5、tion of local region constraint isj udgedIf the condition is met，whether all the matches in the local regions follow consistentgeometric transformation is estimated based on geometric orderExtensive experiments demonstratethat the SVLRC can improve the retrieval accuracy significantly with low compu

6、tation costKey words：computer application；image retrieval；Bag of Words model；local regions；spatialconstraint；postprocessing收稿日期：20150306基金项目：国家自然科学基金项目(61101155)；吉林省自然科学基金项目(201215045，20140101184Jc)作者简介：赵宏伟(1962一)，男，教授，博士生导师研究方向：智能信息系统与嵌入式技术Email：zhaohwj lueducn通信作者：臧雪柏(1963一)，女，研究员，博士研究方向：智能信息系统E-m

7、ail：zangxbjlueducn万方数据266 吉林大学学报(工学版) 第46卷。 引 言随着多媒体信息的迅速发展，图像检索技术已成为研究热点12，然而大多数图像检索系统都是基于Bag of Words(Bow)模型3实现，即将图像中的局部特征量化为视觉词并建立直方图检索图像。然而，由于量化后的视觉词缺少了特征间的空间关系，降低了局部特征的辨别能力，会产生错误的匹配结果并影响检索性能。因此，目前很多研究在得到匹配特征后，通过几何约束的方式在后验证步骤中过滤错误的匹配特征对。这些方法通常计算整幅图像中的所有匹配特征对是否满足一致的几何变换关系，并且可以分为全匹配和弱匹配两种方式。全匹配方法通

8、常基于Ransac算法43计算查询图像与候选图像的仿射变换，这种方式可以有效地验证匹配特征的几何一致性，但耗时太长，只适用于验证少量图像。弱匹配方法可以在不显示计算仿射变换矩阵的情况下验证匹配特征的几何一致性，Jegou等口3提出了Weak geometricconsistency(WGC)方法，假设在不同的尺度和旋转角度变换下，会出现明显的峰值，以此过滤错误的匹配特征。Tsai等6提出了Locationgeometric similarity scoring(LGSS)方法使用任意两点特征的欧式距离比，验证几何一致性，有效地提高了运算效率。进而，Zhao等7提出了Triangle spati

9、al pattern(TSP)方法，利用更多的点探索匹配特征间的几何关系，通过验证相似三角形的数量来度量几何一致性。Zhou等凹1提出了新的几何编码方法(GC)，通过轴线编码和方形编码严格地描述了局部特征间的几何关系。无论是全匹配还是弱匹配，都是计算整幅图像中所有匹配特征间的空间关系；然而在后验证步骤中，有些不相关匹配特征的计算对于改善检索性能的作用不大。不论相似区域是部分图像还是整幅图像，均要满足相似的局部区域中所有正确匹配形变相似的特点。因此只需要验证局部区域内的匹配特征是否满足一致的几何关系即可，没有必要计算局部区域外的不相关匹配特征。针对上述现象，Xie等91提出了Localgeome

10、tric consistency(LGC)方法，假设图像发生形变时，基于局部区域特征相似的特点，考虑了匹配特征相邻区域特征点的信息，精确计算了匹配特征间的变换矩阵。然而，对于一对匹配特征，LGC方法只是计算了最邻近的10对匹配特征的相关信息。如果局部区域内并不存在匹配特征，这种方法很难描述局部区域内特征间的空间关系，因此不相关特征仍然参与到在后验证步骤中。本文通过局部邻域内匹配特征对的数量，定义局部邻域约束值，以此判断是否满足局部邻域的约束条件。若满足约束条件，则计算局部邻域内的所有相关匹配特征是否满足一致的几何变换，并以此建立后验证准则，并对检索结果重新排序。1基于局部约束的后验证方法11局

11、部邻域约束图1为局部邻域约束的处理流程，其中(a)表示查询图像与候选图像的9个匹配特征对。(b)中红色圆表示匹配对(q，d。，)基于特征的尺度参数得到的局部邻域。(c)表示局部邻域内共同匹配特征作用于中心匹配对(q。，d。，)的约束关系，粗实线双箭头所指的特征点位于中心匹配对的局部邻域内，被视为相关匹配的特征，线虚细双箭头指的特征则表示不相关的匹配特征。图1局部邻域的约束示例流程图Fig1 The flow example of local constraint method在查询图像f。与候选图像j。中，Q一(q。，q2，qK)，D一(d1，d2，d K，)分别表示特征集合。以此为基础，进行

12、SIFT特征的匹配，进而得到两幅图像的匹配特征集M(Q，D)一(q。，矗?)Q，di，D)，其中g；，df，分别表示查询图像与候选图像的特征。该特征描述包含4种信息：128维的SIFT描述符des，尺度参数wz，梯度方向参数口与特征在图像中的坐标(z，y)。首先，选择一个匹配对(qf(zi，Yf，des，scl，0f)，df(z?，Y。，des：，scl“Oi，)作为测试中心匹配对，验证其是否为正确匹配对。然后，选取测试中心匹配特征的局部邻域，其范围定义如下：万方数据第1期 赵宏伟，等：基于局部邻域约束的空间验证方法 267D。=仃。；m。*scli (1)Dd，=盯。m。f*sclf， (2

13、)式中：盯zi与scl，分别表示qi与di，中尺度参数。是控制局部邻域大小的参数，在实验23部分进行分析。其次，筛选局部邻域中的共同匹配特征，并对测试中心匹配特征约束。共同匹配特征定义如下：。mMa砌吨一，一c劬，出， (qj，d，)M(Q，D)1 dist(qi，劬)m。Dx(qi，q。，q。)，Dy(qi，q。，q。)分别表示在测试中心匹配对(吼，d，)的局部邻域内共同匹配对中，特征q。与特征q。间的横向坐标关系与纵向坐标关系。当Dx(qi，q。，q。)大于0时，表示中心匹配对(q，d，)的局部邻域内共同匹配对中特征q。在特征q。的右边；当Dy(qi，q。，q。)大于0时，表示中心匹配对(

14、qi，di，)中局部邻域内共同匹配对中特征q。在特征q。的上边；当Dx(qi，q。，q。)和DY(q；，q。，q。)都小于0时，反之。进一步，根据得到的查询图像与候选图像中测试中心匹配对的局部邻域内共同匹配对间的横向坐标关系与纵向坐标关系，对其验证是否一致，验证定义式如下：Verifyz(gf，de)，(q。，d。，)，(q。，d。，)=三篡 Verifyy(gi，d，)，(q。，d。，)，(口。，d。，)一点三篡 当查询图像中D_x(q。，q。，q。)与候选图像中Dx(d“d。，d。，)同时大于0，或者Dx(q。，q。，q。)，Dx(d“d。，d。，)同时小于0时，该匹配特征对(g。，d。，

15、)，(吼，d。，)，在横向坐标关系中，验证正确，Verifyz(口f，d，)，(q。，d。，)，(g。，d。，)一1，即condl；若Dx(qi，q。，q。)大于0，Dz(d，d。，d。，)小于0，或者Dx(qr，q。，q。)小于0，D_z(d，d。，d。，)大于0时，验证错误，Verifyz(q，d。，)，(口。，d。，)，(g。，d。，)一0，且口cond2。同理，当Dy(qf，q。，q。)，Dy(di,，d。，d。，)万方数据268 吉林大学学报(工学版) 第46卷同时大于0，或者同时小于0时，匹配特征对在纵向坐标关系中，验证正确，Verifyy(吼，d；，)，(q。，d，)，(吼，d。

16、，)一1，即cond3；反之，验证错误，Verify一了(g；，d：，)，(q辨，d。，)，(，d。，)一0，即cond4。从而，根据局部邻域中匹配特征在横向与纵向的验证信息，计算该测试中心匹配特征在局部邻域内的几何得分，如下：，Score(口i，d，)一max (口m，dm)ECam胁c(钆，di)(qnn)E CamMd“(口。一，)Verifyz(q。，de)，(q。，d。，)，(q。，d。，)，(dm)凸”胁“(qi，d(，d一)已m缸融(gIl，)Verifyy(g，d，)，(q。，d。，)，(q。，d。，)其中，m一赡表示局部邻域匹配特征中，id号为靠的特征与id号为?It的特征之

17、间的约束关系。为了提高计算效率，本文并非验证共同匹配对中所有特征点间的约束关系，只是计算了共同匹配特征点的排序列表中相邻特征id号间的约束关系。因此该约束关系可表示为，特征id号为，z是大于特征id号为优的最小id号。如图1所示，当测试中心匹配对为(g。，d，)，m一3时，在查询图像的局部邻域内共同匹配特征q。，q。，q。)中，大于特征q。的id号3的最小id号为特征q。id号5，因此咒一5。几何得分Score(吼，di，)表示中心匹配对(qi，d，)的局部邻域内所有共同匹配特征点在横向坐标关系与纵向坐标关系中，排列顺序一致的最多数量。假设如果该得分大于阈值&，判断测试匹配对(吼，d，)正确；

18、反之，错误。本文定义阈值&=03Cca。胁“，、。最后，根据正确匹配对的个数对初始检索结果重新排序。2实验结果及讨论本文通过检索精确度与检索时间验证SVLRC的检索性能。并与目前几种普遍的几何验证方法493作比较。实验中计算初始检索后的前1000幅图像的几何得分，并重排序。在CPU为Core i5，330 GHz，8 GRAM，64位的WIN7操作系统，Matlab R2012a中进行测试。21实验图像集实验数据为两组数据集：第一组为DupImage数据集口0【，包含1104幅图像，并分为33组。本文随机选择100幅作为测试图像，并以mAPElll作为检索精度的度量方式。第二组为Mobile数

19、据集口2|，包含400幅图像。同时也提供了手机拍摄的2500幅测试图像集。以Top一10作为衡量精确度的标准。每组测试集从图像库Ukbenche中选取一定数量的图像作为混淆图像，最终两组数据集的图像总数均为10 000幅。22实验准备本文是在传统的Bow检索模型的基础上提取SIFT特征。同时记录特征点的位置信息，尺度作为几何验证的计算条件。提取特征前，将大尺寸图像降采样为小于500*500。并采用分级树形的方法11生成1 M个视觉词。使用倒排文件方式索引图像，如图3所示，每个视觉词都与多个索引特征相链，其中每个索引特征包含图像的ID、特征位置、尺度参数。实验中所有几何验证方法都是对基于BoW得

20、到初始检索结果的前1000幅图像进行验证重排序的。图3倒排文件结构Fig3 Inverted file23参数测试在本文SVLRC的方法中，参数巧。是通过控制局部邻域的大小范围确定相关匹配特征的个数，并影响检索性能。本文测试不同的盯值所对应的检索性能，并确定最优的仃。不同口。值对第一组数据集DupImage检索性能的影响见图4，同时给出了不同盯值所对应的在后验证阶段中的计算时间。从图4可知盯。值越大，中心匹配特征对的局部邻域范围越大，在过滤不相关匹配特征的前提下，可以得到更多相关匹配特征，并提高检索的精确度。然而，过大的盯值，也可能导致一些不相关的匹配特征参与在后验证阶段中，最终影响检索性能。

21、对于时间消耗，盯。值越大，在后验证阶段计算匹配特征的数量越多，并导致消耗更多的计算时间。基于上述的考虑，对于万方数据第1期 赵宏伟，等：基于局部邻域约束的空间验证方法 269SVLRC方法，当口=40时，舭4P为08109，计算时间为08697 S，此时为参数。的最优选择，并在下面的实验中均采用这个参数设定。图4不同“。值的检索性能Fig4 The retrieval performance of different24与其他几何验证算法的性能对比本文分析了SVLRC方法对检索性能的影响，并与其他7种几何验证方法(BoW3，LGSS6，WGC5|，LGC，TSP7|，RANSAC4|，GC81

22、)的检索精确度和计算时间进行了比较，如表1所示。若所比较算法的程序中含有参数，则采用它们的默认值，并且在第一组DupImage数据集中，以mAP作为精确度的衡量标准，在第二组Mobile数据集中，以Top一10作为精确度的衡量标准。由于RANSAC耗时较大，因此只对初始检索结果的前300幅图像进行验证重排序。表1 两种数据集中。各种检索方法的精确度和查询时间Table 1 The accuracy and query time of each retrievalmethods in the two data sets通过表1中检索精确度的值可以明显看出，传统的BoW算法忽略了特征问的几何关系而

23、使检索效率较低。而本文所提出的基于局部邻域约束的空间验证方法，重点强调特征描述子之间的几何关系，从而进一步提高了检索性能。关于其他几何验证方法，LGSS两点编码时，验证特征匹配很不稳定；WGC主要假设查询图像与候选图像的变换一致，却无法处理图像问的非刚性形变；RANSAC与TSP都是只编码了特征点的位置信息，无法全面反应匹配特征间的空间关系；虽然GC完全利用特征的几何信息(尺度、方向、空间位置)，但不相关特征在后验证中的计算也对检索性能产生了影响；对于LGC，在几何编码中只是计算了最邻近的10对匹配特征的相关信息，如果局部区域内并不存在匹配特征，此时不相关特征仍然会计算在后验证步骤中；以上叙述

24、的原因都会影响检索性能。对表1关于每幅图像的平均查询时间的分析，在众多几何验证方法的对比中可看出，相比WGC(O3237 s)，LGSS(04008 s)计算的是两点的距离比，而不是简单的加减运算；LGC(05261s)又额外考虑了最邻近的10对匹配特征的信息，精确计算了匹配特征间的变换矩阵；GC(24377s)提出了更加复杂的编码方法(轴线编码和方形编码)，严格地描述了局部特征问的几何关系；TSP(77272 s)通过更多的点计算特征间的几何关系；由于RANSAC(151747 S)通过大量的随机取样，计算仿射变换，因此耗时最多。最后，SVLRC在验证特征问几何关系的前提下，通过定义匹配特征

25、中局部邻域的约束方法，过滤不相关的匹配特征对，不仅减少了后验证阶段特征的计算数量，也提高了验证错误匹配特征的准确度。25检索实例图5显示了SVLRC和其他方法的榆索结粕。w墨”圉簟零豳(b)LGSS l哆(。)WGC瞪(d)LGC I黧一k一(e)TSP圆iL一(f)RANSAC瀣(g)GC固(h)SVLRC国k一一斡图5 不同方法的检索结果Fig5 Comparison of performance for different methods赶霜曩两r一黼瓿群一一磷瑟j鞲_；_、瞥锶璺蚕囤囤闺簟豳陲一黩囤曩烫雕万方数据270 吉林大学学报(工学版) 第46卷果，图5中，箭头左边为查询图像，箭

26、头右边为前5幅检索图像。这些结果对于检索目标的颜色、尺度、方向的变化证明了本文方法在图像复杂变换中的有效性。3 结 论在复杂背景的目标检索的研究中，由于传统检索模型(BoW)忽略了特征间的几何关系，导致检索效率降低。而且，目前大多数几何验证方法都是计算整幅图像中所有匹配特征间的空间关系，然而，在后验证步骤中，不相关匹配特征的计算对于改善检索性能的作用不大。因此，本文提出基于局部邻域约束的空间验证方法，通过定义匹配特征的局部邻域范围，过滤不相关的匹配特征对，最后计算相关匹配特征是否满足一致的几何变换。实验中，利用DupImage和Mobile数据集，与其他常用的几何验证方法作比较，结果表明，本文

27、提出的方法可以在保证检索速度的前提下，提高检索的精确度。参考文献：1Zheng I，Wang S，Zhou W，et a1Bayes merging ofmultiple vocabularies for scalable image retrievaCf IEEE Conference on Computer Vision and PatternRecognition，Columbus，OH，2014：196319702赵宏伟，李清亮，刘萍萍基于分级显著信息的空间编码方法I-J电子学报，2014，42(9)：18631867Zhao HongweiLi Qingliang，Liu Pingp

28、ingSpatial encoding based on hierarchical salient informationJActa Electronica Sinica，2014，42(9)：186318673Sivic J，Zisserman AVideo Google：A text retrieval approach to object matching in videosCProceedings of 9th IEEE International Conference onComputer Vision，Nice，France，2003：147014774Fisehler M A，B

29、olles R CRandom sample consensus：a paradigm for model fitting with applicationsto image analysis and automated cartographyJCommunications of the ACM，1981，24(6)：381-3955Jegou H，Douze M，Schmid CHamming embedding and weak geometric consistency for large scaleimage searchCProceedings of the 2008 10thIEE

30、E European Conference on Computer VisionMarseille，France：IEEE，2008：3043176Tsai S S，Chen D，Takacs G，et a1Fast geometricreranking for imagebased retrievalCProceedings of the 2010 IEEE International Conference onImage ProcessingHong Kong：IEEE，2010：102910327Zhao H，Li Q，Liu PHierarchical geometry verific

31、ation via maximum entropy saliency in image retrievalJEntropy，2014，16(7)：3848 38658Zhou W，Li H，Lu Y，et a1Sift match verificationby geometric coding for large-scale partial-duplicateweb image searchJACM Transactions on Multimedia Computing，Communications，and Applications(TOMCCAP)，2013，9(1)：1-189Xie H

32、，Gao K，Zhang Y，et a1Local geometricconsistency constraint for image retrievalCProceedings of the 2011 18th IEEE International Conference on Image ProcessingBrussels，Belgium：IEEE，2011：101-10410https：d1dropboxusercontentcomu42311725DupGroundTruthDatasetrarDBOL，2014071011Philbin J，Chum O，Isard M，et a1O

33、bject retrievalwith large vocabularies and fast spatial matchingCIEEE Conference on Computer Vision and PatternRecognition，Barcelona，Spain，2007：1-812Wang x，Yang M，Cour T，et a1Contextualweighting for vocabulary tree based image retrievalCProceedings of the 20 1 1 1EEE InternationalConference on Computer Vision，Barcelona，Spain，2011：209216万方数据