《基于内容的图像检索系统的设计与实现分析研究计算机科学与技术专业.docx》由会员分享，可在线阅读，更多相关《基于内容的图像检索系统的设计与实现分析研究计算机科学与技术专业.docx（33页珍藏版）》请在三一办公上搜索。
1、目录HU1131 j2右41.1 基于内容的图像检索41.2 图像检索评价指标6第2章BoF模型72.1 基于视觉单词的匹配72.2 投票机制92.3 倒排索引10第3章汉明嵌入123.1 原始模型的缺点123.2 基于汉明嵌入的匹配13第4章几何重排164.1 弱几何致性164.1.1 弱几何一致性的原理164.1.2 考虑弱几何一致性的相似度计算184.2 基于几何信息的重排204.2.1 随机抽样一致算法204.2.2 错配点剔除21第5章实验过程245.1 开发环境245.2 框架设计245.3 实现25第6章结论28参考文献29致谢错误!未定义书签。通常的，图像检索可以分为两大类：基
2、于文本的图像检索和基于内容的图像检索。本文的主要内容是设计并实现了一个基于内容的图像检索系统。现在主流的图像检索技术主要是对图像提取局部特征，并利用特征袋模型对特征进行处理，以获得检索精度和检索性能之间的平衡。一个检索系统的运作主要包括数据集预处理和正式的检索过程。其中预处理过程包含：图像特征提取、视觉词典构建以及图像特征编码。检索过程会对待检索的图像进行类似处理，同时还有对特征的相似度比对，之后返回结果。本文基于前人的研究成果，做出的主要工作如下：1 .搭建一个基于flask框架的在线检索系统。2 .图像数据集处理阶段，对每幅图像提取ROotSlFT特征，并对特征进行k-means聚类，用来
3、构建特征袋模型。3 .利用UkbenCh数据集，比较了基础特征袋模型，汉明嵌入，弱几何一致性校验，空间几何重排等的检索效果，并对效果进行mAP评价。关键词：图像检索；特征袋模型；汉明嵌入；弱几何一致性；几何重排AbstractIngeneral,imageretrievalcanbedividedintotwomajorcategories:text-basedimageretrievalandcontent-basedimageretrieval.Themaincontentofthispaperistodesignandimplementacontentbasedimageretrieva
4、lsystem.Currently,themainstreamimageretrievaltechnologymainlyextractslocalfeaturesfromtheimagesandusestheBagofFeature(BoF)modeltoprocessthefeaturestoobtainabalancebetweenretrievalprecisionandretrievalperformance.Theoperationofaretrievalsystemmainlyincludesdatasetpreprocessingandformalretrievalproces
5、s.Thepreprocessingprocessincludes:imagefeatureextraction,visualdictionaryconstruction,andimagefeaturecoding.Theretrievalprocesswillperformsimilarprocessingontheretrievedimages,aswellascomparethesimilaritiesofthefeatures,andthenreturntheresults.Basedonpreviousresearchresults,themainworkofthispaperisa
6、sfollows:1. Buildanonlinewebretrievalsystembasedonflaskframework.2. Attheimagedatasetprocessingstage,RootSIFTfeaturesareextractedfromeachimage,andthefeaturesareclusteredusingk-meansalgorithmtoconstructtheBoFmodel.3. Usingukbenchdataset,wecomparethesearchresultsofthebasicBoFmodel,HE,WGC,spatialgeomet
7、ricre-rankingandsoon,andevaluatetheirefficiencybymAP.Keywords：imageretrieval;bagoffeature;hammingembedding;weakgeometricconsistency;reranking随着诸如智能手机、数码相机、平板电脑等电子设备的普及，人们可以用越来越容易的方式创作以及获取图片。同时，社交网站的兴起，如国外的InStagram、FaCebook和国内的QQ等，直接催生了人们分享照片的兴趣。这些原因无疑导致了图像数据库的规模迅猛增长，例如，nickr作为一个照片分享网站，单是2017年就有用户上传
8、了高达6亿张图片，中国最大的电商网站淘宝同样保存着数十亿计的用户图片。海量的图像规模不仅在存储方面增加了难度，同时在应用方面，也对能够让用户精准、快速的查找感兴趣的图片提出了挑战。因此，针对大规模图像数据库的信息检索，成为了当前数字图像处理技术方向的研究热点。到目前为止，大规模图像检索的主流是基于内容的图像检索技术，主要方式是类似于文本处理方面的词袋模型，本文下面即对此展开介绍，并解释其他的扩展方法。本文下面的组织如下：第1章介绍基于内容的图像检索技术的基本内涵，并介绍图像检索的评价指标，第2章介绍了利用提取图像局部特征的基本BOF模型检索方法，以及相应的索引、相似度计算方式，第3章介绍了对聚
9、类的改进，即汉明嵌入，第4章介绍了基于几何信息的重排，第5章则展示了实验效果，对所采用的方法进行相应的实验，并利用评价指标进行效果评价。第1章绪论本章介绍了传统图像检索方法的缺陷，并展示了基于内容的图像检索技术的要点。本章还展示了检索系统的基本工作流程，以及对检索结果的评价方法。1.1 基于内容的图像检索传统的图像检索方法主要是基于关键字的图像检索方法，这种方法主要是通过人工对要处理的图像进行关键字标注，让每幅图像添加对应的关键字，检索时就将对图像内容的检索转化成了对关键字文本的检索，无疑要容易许多。这种方法有时候效果可能会很好，它也曾被百度等搜索引擎采用过，但是它有一些显著的缺点。首先人工标
10、注耗时耗力，今天的大规模图像数据库显然是无法应用的，其次，所谓一图胜千言，一幅图像的内涵有很多，往往无法用几个关键字描述完全，并且每个人对图像内容的理解也不一样，因此检索时会导致误差。这些缺点导致上述技术无法更广泛的应用。而现在的商用的图像检索系统使用的技术主要是基于内容的图像检索(COntentBasedImageRetrieval,CBIR)lo基于内容的图像检索技术基本不需要人工干预，并且是对图像内容本身的理解。一个基本的在线CBlR系统检索流程如图1-1所示2：图LI在线CBIR系统的检索流程首先选取初始的图像数据集，需要对它进行特征提取，本文这里选取了ukbench,共10200幅图
11、片，每四幅一组，每组都是类似物体在不同角度和尺度的图像。下文的内容都是基于这一数据集的5000幅图子集来做效果评估。接着是对选取好的数据集进行图像特征提取。图像特征有很多种，常见的包括颜色特征，纹理特征，形状特征等等，称为底层特征，以前的CBlR系统主要基于此实现，综述性文献对此有叙述。这些底层特征都比较易受环境影响，像是光照、尺度、视角，以及一些背景方面的变化都会对检索结果造成较大的影响，所以图像检索时会选择局部特征，这种特征的抗干扰性比较好。LOWe提出的SIFT特征4就是这样一种在实践中被证明效果较好的局部特征，它具有很好的尺度，旋转，和平移不变性，基于LOWe的工作，后人提出了许多的改
12、进，其中文献5提出了RootSIFT特征，它仅仅是对原始SIFT特征的一种代数扩展(对每个计算出来的原始SlFT描述子进行LI归一化并取平方根)，但是却能够改进检索效果。由于RootSIFT对SIFT特征的兼容性和易于计算的特点，本文进行图像特征提取时，对SlFT进行处理转换成了RootSIFT特征。SIFT特征和ROotSlFT特征一样，每个描述子都是128维，每幅图包含成百上千个这样的特征描述子，一个基本的数据集，比如UkbenCh,包含上千万维这样的高维向量，如果查询图片依靠暴力匹配每个向量的距离来计算相似度，性能上无法接受。为了处理大规模图像数据集，SiViC等人基于文本处理领域的词袋
13、模型，提出了特征袋(BagOfFeatUre,BoF)模型，利用k-means算法对所有描述子进行聚类，聚类之内的描述子具有较高的相似度，聚类之间的描述子具有较高的离散度，量化形成k个视觉单词。对于一幅包含几个描述子的图片，每个描述子被划分到最近的视觉单词，统计形成视觉单词的频率直方图，用频率向量来代表这幅图片，这样所有几个图像特征就被一个Z维向量代替，大大减少了计算量。图像查询时可以简单的计算向量之间的欧几里得距离或者余弦距离来获得最终的相似度得分。原始的BoF模型可以获得比较满意的检索精度。一般来说特征聚类过程中，利用k-means算法时选取的聚类数k值设的越高，检索效果越好，但是由于算法
14、本身是。(1)这样一个比较大的复杂度，导致大数据集聚类时间较长，针对k-means本身的https:/archive.org/download7ukbench/ukbench.zip改进有层次k-means和近似k-means等，本文这里介绍的是Jegou等人在文献中提出的另一种思路，即首先对描述子进行较粗的聚类，接着通过添加汉明编码对描述子应用汉明嵌入，来进一步改进粗聚类的视觉单词，这种方法可以获得比原始模型更好的结果。量化描述子形成视觉单词的过程中，原始图像本身的视觉几何信息被丢失掉了，这无疑会限制检索的效果。针对这一问题，很多人做出了利用空间几何信息的改进，文献提出了弱几何一致性约束，即
15、简单的增加了关键点角度和尺度信息的校验，对前面模型得到的结果进行重排。文献则提出了对已有结果的前若干幅图片增加进一步的空间验证过程，重新排序来获得更高的精度。1.2 图像检索评价指标对图像检索返回的结果，本文利用的评价指标为平均精度均值指标(meanAveragePrecision,mAP)指标9。mAP是指的是平均精度(AVeragePrecision,AP)的均值：mAP=吟1-错误!未定义书签。Q代表查询次数。AR则是第i次查询的平均精度。一般检索最重要的两个指标是精度(PreCiSion)和召回率(ReCan),若用X轴表示召回率，y轴表示精度，可得到精度召回率曲线(PreCiSiOn
16、-Recallcurve,PRcurve)AP结合精度和召回率两方面的特征，代表的是PR曲线下的面积：AP=P(r)drI-错误!未定义书签。实现中，积分会被一个有限和代替：n-lAP=WPO)Ar(/)I-错误!未定义书签。J=On表示取回的图像结果的个数，/是取回图像的序列，Po)就代表前/个图像的精度，Aro)则是从第幅图到第/幅图召回率的变化值，这代表当召回率不变时相应的精度也不计入。AP就代表每召回一幅图就计入其精度，最后精度和除以召回数的值。mAP作为所有AP的均值，可以更好的衡量检索效果。本文下面都将采用这个指标。第2章BoF模型BOF模型来自于文本处理领域的词袋模型，其主要思想
17、是将所有描述子聚类形成视觉词典，再根据视觉单词对描述子进行量化，最后根据量化的特征进行检索。本章展示了如何根据已有图像局部特征来进行视觉词典的构建，形成频率直方图，以及利用倒排索引和投票机制进行特征匹配10。2.1 基于视觉单词的匹配原始的BoF模型的处理流程有下面几步：首先对于原始图片，可以先进行增强、分割以及统一格式的处理以方便下面的操作。原始图片处理完成后，对它们提取RootSIFT特征，假设共Tn幅图像，每幅图则可以获取几个RootSIFT的关键点(keypoint)和对应的描述子(descriptor),每个描述子128维。所有图片的特征组合作为训练集，对其进行k-means聚类，聚
18、类数k根据实际训练效果选取，一般来说Z的值越大越好，但也不宜过大，表2-1是对5000幅图的评估结果：kmAP20000.68676150000.70617680000.718785100000.730512120000.726284表2-1对5000幅图像选取不同k值后的检索效果评估可以看到对原始的BOF模型来说，k值的增大，对后面的检索效果提升已经不是那么大了，而且大的Zc值会显著的增加聚类时间。通过聚类可以获得Zc个128维的聚类中心(通常称为视觉单词)和量化函数q：q:xERdq(x)0,k)2-错误!未定义书签。q的作用是将一个特征描述子映射到距离最近的聚类中心，值q(%)是聚类中心
19、的索引。量化过程避免了通过计算向量距离匹配特征的暴力匹配方式，而是通过比较视觉单词的方式来匹配。直观的讲，如果两个描述子和y在特征空间中距离很近，那么就很有可能满足q(%)=q(y)这个条件。两个描述子的匹配函数分可以简单的定义为对他们量化后的索引的比较：fq(x,y)=Lif,qM=2-错误!未定义书签。对一幅图像九个描述子进行量化可以获得一个九维向量，如果再统计每个维度的视觉单词索引，每幅图就可用一个k维的频率向量表征，这里称为一个BoF向量。视觉单词之间的重要性是不一样的。一般来说一幅图中出现次数最多的视觉单词是重要的，但如果一个视觉单词在每幅图中都会出现，那它的重要性就会降低。换句话说
20、，仅在一幅图中出现多次的视觉单词更加具有鉴别力，也就可以赋予其更高的权重。因此，这里对视觉单词应用文本处理中的tf-idf权重。tf(termfrequency)指的是文档词频，对文档d中出现的单词tf(t,d)计算方式如下:tf(t, d)=2-错误!未定义书签。t,d为这个单词在文档d中的频率，Hd加d是所有单词的总频率。idf(inversedocumentfrequency)指的是逆文档词频，本文这里采用Skleam?的计算方式：idf(ttD)=log+1)+12-错误!未定义书签。+Tit/N为文档总数，是出现过该单词的文档数，越大则说明这个单词越常见，相应的就会降低权重。一个单词
21、的tf-idf权重就可以计算为:tf-idf = tf idf2-错误!未定义书签。添加tfidf权重后，匹配函数22可以进一步表示为：)=虱月2.错误!未定义书签。tdf(q(y)表示如果描述子X和y匹配，匹配函数等于y所属视觉单词的idf权重。由于所有描述子匹配之后的结果本身就带有视觉单词的频率信息，因此这里不需要乘上tf权重。hup:/scikit-leam.org/stable/modules/generated/sklearn.feature_extraction.text.TfidfTransformer.html2.2 投票机制投票机制应用在计算最终的查询图像和己有图像数据集之间
22、的相似度得分上。假设整个数据集共有m幅图，相似度得分的计算方式如下：1 .初始化m幅图中每幅图像对应的分数i0,加）为0。2 .根据查询图像的特征集和每幅图像的特征集的匹配结果来更新分数项：Si = Si+ fqxij,yk)2-错误!未定义书签。假设数据集每幅图有小个描述子，查询图像有几个描述子，上面的更新方式即表示将每幅图的描述子MJj0,为）和查询图像的描述子九次0,n）一一匹配，用匹配函数值进行分数投票。对匹配函数添加tf-idf权重，应用公式26：St = St + A-id(xiyc)2-错误!未定义书签。Si最后就是匹配函数值的和:Si = WW FSid c=O ；=0可以进一
23、步的对分数Si进行处理可以得到S；:n-lLi2-错误!未定义书签。2-错误!未定义书签。之所以有这样的处理是由于匹配函数只有idf权重，还没有考虑到图像特征个数的影响。对此有多种选择，可以类似式23那样的处理，即sj=sni,也可以除以特征个数（BoF向量LI范数）的平方根：s；=SJR最好的方法是除以BoF向量的L2范数，文献提到，对大规模词汇而言L2范数与Ll范数的平方根是近似的，但是本文经过比对测试发现还是L2范数的效果比较好，因此采用L2范数：s；=VIIFoFdI2O综合上述公式，相似度的最终得分s：可以计算为：*=%SW,k）iV,Wid）SiI由。用I?I8oF2HFoFdI2
24、BoF22-错误!未定义书签。BoFBOFHFoFdI2FoF2上式实际上就是经过tfidf加权后的两个BoF向量之间的余弦距离。在实现中,需要保存每个BoF向量的L2范数，最后在计算Sa寸，只需计算两个向量的内积BoFiBoF,并除以相应的范数即可。2.3倒排索引在计算相似度得分s：的时候，通过计算查询图像和参考图像对应的BoF向量之间的余弦相似度能够快速的得到分数，这里还可以利用倒排索引结构。利用倒排索引可以很有效的计算相似度，这主要是因为BoF向量的稀疏性。一幅图的描述子只会对应很少的聚类，比如ukbench00005.jpg的频率向量直方图如图2-1所示：2 -O OIOOO 2000
25、3000VWlD400050006 4 2 0 8 6IlllAou7-3-错误!未定义书签。XVZfCzvO投影向量Z的每一维都和所属聚类的中值向量比较，如果有ZiTq(X)V汉明编码相应维度就为1。至此，描述子X不仅可以用量化索引q(%)来代表，还包含了汉明编码b(x)。大大提高了区分能力。对式26的匹配函数，可以进一步的改进：-E(%y)=fdf(q(y),ifq(x)=q(y)and(b(%),b(y)ht3-错误!未定义书签。I1else如果描述子和y的映射到同一视觉单词，进一步比较他们汉明编码的汉明距离，如果距离小于阈值上，才认为这两个描述子真的匹配，否则它们将被拒绝。阈值儿OSb
26、)是一个固定值，表示对汉明编码匹配的接受程度，当儿=d匕时即表示对匹配到同一视觉单词的描述子全部接受，这相当于原始BOF模型的效果。也不能太高，这样才能过滤掉许多因为量化误差归类到一个聚类的描述子，也不能太低，以保证匹配到足够的欧几里得距离相近的描述子。图3-1表现了这样的折中：图31是对5000幅图在聚类数k为5000的时候，选取不同汉明阈值的检索评价。可以看到瓦=23时,效果是最好的。在阈值较小的时候,比如比=10时，实验的mAP=0.767888,这说明一些正常的匹配被误过滤了，阈值达到23时，m/P为最大值0.877311,此后阈值增大m4P一直缓慢下降，当增大到64之后，等于0.70
27、6176,也就是未采用汉明嵌入方法时聚类数为5000的水平。同时对比表2-1可以发现，使用了汉明嵌入方法的粗聚类数为5000时的精度水平最好是0877311,未使用汉明方法的聚类数为12000时的精度水平为0.726284,汉明嵌入对检索效果有极大的提升。本文实验还发现，如果一开始就设一个很高的聚类数K对其应用汉明嵌入，其效果不见得比不应用好，这符合预期，因为汉明嵌入是对属于一个聚类空间的描述子进一步的划分，对于已经过聚类的描述子而言，划分不能够剔除噪声的影响。基于汉明嵌入的良好效果，本文下面的实验将采用这个方法，并采用九广23这个阈值。汉明嵌入方法可以很好的和倒排索引结构结合起来。上文中，倒
28、排列表的索引与视觉单词是对应的，在汉明嵌入中就对应一个中值向量。每个列表项是一个链表。链表中的每个条目都对应某幅图片中的一个描述子，因此在条目中可以加入汉明编码。在实现过程中，由于汉明编码是一个64维的二值向量，可以将这个向量压缩为64位整型存储。在匹配的过程中，利用投票机制计算相似度分数，遍历倒排列表的每一个条目，需要用到式33的匹配函数。可以先计算查询图像描述子的汉明编码与遍历的汉明编码的距离，一旦汉明距离大小超出了阈值瓦，那么就不会再更新相似度分数。实验中，利用了汉明嵌入的查询过程甚至比没有利用的，即单一的倒排索引遍历查询的时间更短。这主要是由于计算汉明距离仅仅是对两个64位整型的汉明编
29、码进行异或操作后再统计1的个数，这里的计算代价要小于更新相似度分数的代价，而利用汉明嵌入，使用一个较小的阈值，可以显著过滤大量量化误差较大的描述子，避免了很多分数更新操作。汉明嵌入也不会增加多少空间复杂度，每个描述子添加一个8字节汉明编码即可，因此值得采用。第4章几何重排无论是原始BoF模型，还是增加了汉明嵌入了改进版模型，尽管图像检索效果已经不错，但是它们仍然没有利用到图像的空间几何特征。如果要进一步的改进检索效果，应该考虑到图像几何信息，因此本章接下来对汉明嵌入之后得到的结果进一步添加了基于图像空间几何的重排序阶段。4.1 弱几何一致性前面提到过，加入集合信息能够对检索效果很好的提升，但是
30、却无法实际应用，因为和暴力匹配算法一样，几何匹配算法的计算代价都很高昂。即使有不少工作都基于对几何匹配算法的优化，但是到目前为止，还是只能应用于几百张规模的数据集，没有大规模利用的可能性。为了解决这个问题，文献提出了弱几何一致性(WeakGeometricConsistancy,WGC)匹配。4.1.1 弱几何一致性的原理顾名思义，弱几何一致性仅仅只利用了一部分的几何信息，即角度和尺度信息。对于SlFT(或者RoOtSlFT)局部特征而言，每个不变的感兴趣区域的检测都具有相关的尺度和旋转角度信息12,这里具有特征尺度和主导方向。相应的，一对匹配图像之间会有一个尺度和角度方面的差异，并且就全局图
31、像而言，尺度和角度的变化大致是一致的。下面进行一个比较：图4l(a)和图4-l(b)是一对匹配图像，图4-1对他们之间的匹配点之间进行了连线。对这两幅图片图像基于角度差进行直方图统计，可以得到图4-2：20 -10 -0-20angle difference2O 87060504030 SgIPjBIU jo .JBqErIU图4-2图4-1和图4-l(b)所有的匹配描述子基于角度差的频率统计图4-2有一个很明显的峰值出现，峰值出现在大约-加/4附近，即在角度差大约为-r4的位置，两幅图像匹配到的描述子是最多的，这符合肉眼观察到的现象，两幅图有个一致的旋转关系。对匹配图像图4-3(a)和图4-
32、3(b)而言：O-100 -200 -300 -400 -020040060080010001200图4-3图像a和b之间的匹配如果对它们进行基于尺度差统计形成频率直方图，可以得到图4-4：O 1/81/41/212scale difference48Oooo 8 6 4 2图4-4图4-3(a)和图4-3(b)所有的匹配描述子基于尺度差的频率统计同样有峰值出现在大约3/4附近，这表示在尺度差(尺度差是关键点半径的对数差)3/4附近匹配到的描述子最多，这同样符合肉眼观察到的缩放现象。可以认为峰值附近的值就是特征尺度和主导方向，如果加入权重考量，在特征尺度和主导方向的相似度得分就是最高的峰值，其
33、余位置的匹配都是噪声，将它们都过滤掉，不计入投票分数。4.1.2 考虑弱几何一致性的相似度计算考虑一对匹配的图像，它们之间会有一个一致性的变化，弱几何一致性会过滤掉角度和尺度方面变换不一致的特征，这是通过假设以下变换分别估计查询图像和参考图像之间的旋转和缩放参数来完成的口引：?=Sc0s2-sinX阴+ttx4-错误!未定义书签。1.yqLsinCOSJLytLCyJ&，%),和(M%)T是查询图像和参考图像的匹配位置，S和。以及是尺度、角度以及平移信息14。弱几何一致性考虑其中的尺度、角度信息。将弱几何一致性应用到倒排索引中，修改式27的分数更新函数，得到：si(afs)=si)+(xi-,
34、-lyk)4-错误!未定义书签。心和6s是量化后的角度差和尺度的对数差，注意这里需要对角度差和尺度差做一些处理。首先是角度差需要限制在-r,兀的区间，那么给定角度差，可以对其正切值反正切，正切值需要对应正确的象限，这可以从正弦值和余弦值中得出。其次，对于尺度，保存其对数，然后再计算的是对数差，即两个尺度比值的对数，对数差限制在-3,3的区间，也就是只计算1/8,8这个区间放缩关系的分数。对应式2-10,最后的分数是：s：=g(m%(si(6t2,a)4-错误!未定义书签。Si这个初始分数是一个二维的直方图，角度和尺度差量化后的值作为矩阵的索引，确定位置后往该处加上匹配函数的值，最后取所有位置的
35、分数当中的最大值作为最后分数s：。这么做的动机就是尽量利用角度和尺度信息剔除不属于一致变换的特征，找到Si这个二维直方图的分数峰值，并认为这个峰值所在位置的角度差和尺度差就是式2-1所展现的变换的值S和d其余位置对应的特征被认为不符合估计得到的变换模型，就不计入投票分数。这相当于变相的给属于一致变换的特征的匹配函数值增加了权重。在实验中，角度和尺度信息分别都是独立变化的，因此没有必要在一个二维的直方图上投票，可以将它们分开计算，更新方式如下：Si()=Si()+f(%,”)SG)=si(s)+f(xij,yk)4-错误!未定义书签。即分别在角度差和尺度差对应的一维直方图上投票计算相似度分数，将
36、它们看作是二维的直方图的边缘概率。之后将两者统一起来，得到最后的分数：5- =g(minmax(si(a),max(si(s)4-错误!未定义书签。角度差对应的分数和尺度差对应的分数都是取各自直方图中的最大值，两者之间再取一个最小值，就作为最后的分数。二维转化为维计算可以降低内存和CPU的消耗，上式也是对式4-3的合理估计。弱几何一致性方法同样很好的利用了倒排索引结构，在汉明嵌入的基础上，继续向倒排列表每个列表项中的每个条目加上弱几何信息，即弧度形式的角度和尺度的对数，并没有增加多少空间消耗。在查询时间方面，弱几何一致性拖慢了查询的速度。尤其是对没有利用到汉明嵌入时的单一弱几何一致性的应用来说
37、，查询一幅图的时间可以达到十秒左右，这主要是由于它利用的是式4-4来计算投票分数，即对两个直方图的更新，而直方图的更新访问具有随机性，这就无法利用到缓存。没有经过汉明嵌入过滤的原始特征数量很多，大量的直方图更新操作增加了运行的时间。而在同时添加汉明嵌入和弱几何一致性后，时间相较于原来BOF模型来说，只是略微有所增加，还可以接受。不同于完整的几何重排，弱几何一致性方法能够被利用到大规模图像数据集。4.2基于几何信息的重排几何匹配算法由于计算代价高昂不适用于大规模图像检索，但是它还是能够应用于重排序的过程，也就是对用前面所有的算法检索得到的结果，选取前若干幅结果，然后对它们根据空间几何信息进行重排
38、序。对几十幅图像进行空间重排序的过程不会让查询时间增长多少，但却是很好的增加检索精度的方式。下面是详细的介绍。4.2.1 随机抽样一致算法RANSAC(RANdomSAmpleConsensus,RANSAC)算法15诞生于1981年，由FiSCMer和BOneS首次提出，这是一种需要迭代的方法，作用是从一组观测数据中估计数学模型的参数，观测数据可以包含异常值，并且异常值不会影响估计值。RANSAC并不会产生固定的结果，它只能是在一定概率的情况下产生相对合理的结果，但是如果整个过程包含更多的迭代，产生合理的结果概率会增加4。一般要从包含异常值较少的数据集当中拟合出适当的数学模型，可以应用最小二
39、乘法，但如果数据包含很多的异常值，即噪声较大，最小二乘法就显得力不从心，这时候RANSAC就可以派上用场。RANSAC算法本身就假设了数据集中既包含正常值(inliers),又包含异常值(outliers),正常值可以被数学模型很好的描述(数学模型本身就来自正常值)，而异常https:/en.wikipedia.org/wiki/Random_sample_consensus值偏离了正常值的范围很远，并且无法适应由正常值得到的数学模型。如果给定一组可信的观测数据，RANSAC算法假设存在一个能够解释数据的数学模型。RANSAC算法基本步骤如下：1 .首先从输入数据集中随机的选择一个子集，称之为假设正常值(hypotheticalinliers)o2 .对在假设正常值中的元素，拟合出相应的数学模型，获取模型参数，其中假设正常值中的元素个数确保能够得到一个确定的模型。3 .对所有其他数据针对拟合模型进行测试。根据拟合模型对应的损失函数，适合拟合模型的，就认为与假设正常值是一致的，将其加入到一个集合中，称为一致集(COnSenSUSset)。4 .如果有足够多的数据都被归类于一致集，那就说明由假设正常值估计得到的模型是适当的。对不在一致集的数据，可以认为它们就是异常值。而对在一致
