一种基于形状交互矩阵的图像错误匹配检验方法

摘要

本发明公布了一种基于形状交互矩阵(SIM)的图像错误匹配检验方法，通过两幅图像之间匹配的特征点对计算得到两幅图像关于标准化齐次坐标的两个形状交互矩阵，通过欧氏距离法或余弦相似法计算两个形状交互矩阵逐列之间的差异，得到两幅图像的错误匹配对。在去除错误匹配后，可利用剩余的正确匹配对，针对不同应用背景做进一步的处理。本发明提供的方法可应用于图像检索、三维点云配准和图像或视频中的物体识别等领域，扩展了应用范围；模型简单，理论性好，对于仿射几何变换具有较强的鲁棒性，实时性能显著，适用于对实时性要求较高的应用场合。

说明书

技术领域

本发明涉及图像匹配与图像检索领域，尤其涉及一种基于形状交互矩阵(Shape InteractionMatrix，简称SIM)的图像错误匹配检验方法，该方法具有仿射变换不变性，用 于检测一对图像之间局部特征点的错误匹配对。

背景技术

从给定的两个匹配点集中去除错误匹配对是计算机视觉、模式识别、多媒体领域 中的一项基本问题，其应用广泛，例如从运动恢复结构、图像配准、立体匹配、跟踪、目标识 别以及部分重复图像检索等。在各种应用场景中，首先要做的就是得到点集之间的两两对 应匹配关系。这里的点集既可以是由二维图像中提取到的局部特征点，也可以是三维点云 数据中的提取到的三维关键点。候选点之间的匹配关系，通常需要通过两个假设条件作为 约束来确定，一个是相似性假设，另一个则是空间一致性假设。相似性假设要求匹配对中的 两个点的描述子彼此之间应该尽量相似，而空间一致性假设则要求所有正确匹配对之间应 该满足一个统一的几何变换关系。通常我们用相似性假设作为一个充分条件来选取候选匹 配对的范围，而用空间一致性假设作为一个必要条件来过滤候选匹配对中的错误匹配。造 成错误匹配对的原因，主要包括以下三点：

(1)两个点集间通常存在未知的几何变换，这些变换可能包括平移变换、旋转变 换、尺度变换、错切变换及投影变换等。

(2)由于受到如二维图像或三维场景中物体色调、光照、材质、纹理等客观条件的 影响，相应的二维或三维特征检测器检测到的特征，其位置通常存在精度偏差。

(3)二维图像或三维场景中的内容可能存在相互遮挡，由此引入了许多本身没有 匹配点的干扰特征点。

由于错误匹配对的存在，匹配精度有所下降，这成为了制约其诸多应用场景性能 的一个瓶颈。去除错误匹配方法因此需要克服由上述原因带来的强噪声、大量离群点以及 强几何变换以适应复杂的应用场景。为了解决这一问题，人们提出了很多使用空间一致性 假设来检测和去除错误匹配的方法，我们将这些方法归为以下两类：迭代逼近方法与非迭 代过滤方法。

第一类方法希望通过交替迭代的方式来同时估计几何变换模型与正确匹配对的 集合。由于估计得到的几何变换模型受离群点所占比例的影响很大，这类方法所面临的主 要困难时如何在离群点比例较高的情况下鲁棒地去除错误匹配点。经典的随机抽样一致性 方法(RANSAC，参见引用文献[1])以及其变种方法最大似然估计抽样一致性方法(MLESAC， 参见引用文献[2])可以在离群点比例相对不高的情况下估计仿射或投影变换模型并去除 错误匹配。一致性函数鉴别法(ICF，参见引用文献[3])以及基于矢量场一致性的三种方法 VFC、Fast-VFC、Sparse-VFC(参见引用文献[4])甚至可以在离群点比例较高的情况下估计 非刚体变换模型并去除错误匹配。这类方法通过迭代的方式能够估计较为复杂的几何变换 模型，却也因此会在计算上较为耗时。

第二类方法则考虑用一种非迭代的方式，直接利用几何先验知识来过滤错误匹配 点，而无需精确估计几何变换模型。该类方法由于耗时较少，一直以来广泛运用于大规模图 像检索领域来提升检索精度，该领域的研究者也为此提出了很多有效的方法。其中，基于相 似几何变换先验假设的方法有：弱几何一致性法(WGC，参见引用文献[5])、强化弱几何一致 性法(EWGC，参见引用文献[6])、强几何一致性法(SGC，参见引用文献[7])以及成对几何匹 配法(PGM，参见引用文献[8])。上述方法均使用了特征点的主方向及主尺度信息来有效地 过滤错误匹配，但都是从孤立的特征匹配对的角度出发设计的过滤方法。还有一些基于较 强相似变换模型的方法包括：几何编码法(GC，参见引用文献[9])、低秩全局几何一致性法 (LRGGC，参见引用文献[10])以及一范数全局几何一致性法(L1GGC，参见引用文献[11])可 有效利用孤立特征点之间的全局空间信息，利用全局几何信息统一地快速地过滤错误匹 配，但是，当点集之间的几何变换(仿射变换或投影变换)较复杂时，往往达不到良好效果。

引用文献：

[1]M.A.FischlerandR.C.Bolles,“Randomsampleconsensus:aparadigm formodelfittingwithapplicationstoimageanalysisandautomated cartography,”CommunicationsoftheACM,vol.24,no.6,pp.381–395,1981.

[2]P.H.TorrandA.Zisserman,“MLESAC:Anewrobustestimatorwith applicationtoestimatingimagegeometry,”ComputerVisionandImage Understanding,vol.78,no.1,pp.138–156,2000.

[3]X.LiandZ.Hu,“Rejectingmismatchesbycorrespondencefunction,” InternationalJournalofComputerVision,vol.89,no.1,pp.1–17,2010.

[4]J.Ma,J.Zhao,J.Tian,A.Yuille,andZ.Tu,“Robustpointmatchingvia vectorfieldconsensus,”IEEETransactionsonImageProcessing,vol.23,no.4, pp.1706–1721,2014.

[5]HerveJegou,MatthijsDouze,andCordeliaSchmid,“Hammingembedding andweakgeometricconsistencyforlargescaleimagesearch,”inEuropean ConferenceonComputerVision,2008,vol.5302,pp.304–317.

[6]Wan-LeiZhao,XiaoWu,andChong-WahNgo,“Ontheannotationofweb videosbyefficientnear-duplicatesearch,”IEEETransactionsonMultimedia, vol.12,no.5,pp.448–461,2010.

[7]JunqiangWang,JinhuiTang,andYu-GangJiang,“Stronggeometrical consistencyinlargescalepartialduplicateimagesearch,”inProceedingsof the21stACMInternationalConferenceonMultimedia,2013,pp.633–636.

[8]X.Li,M.Larson,andA.Hanjalic,“Pairwisegeometricmatchingfor large-scaleobjectretrieval,”inComputerVisionandPatternRecognition, 2015.

[9]WengangZhou,HouqiangLi,YijuanLu,andQiTian,“SIFTmatch verificationbygeometriccodingforlargescalepartial-duplicatewebimage search,”ACMTrans.onMultimediaComput.Commun.Appl.,vol.9,no.1,pp.4:1–4:18, 2013.

[10]L.Yang,Y.Lin,Z.Lin,andH.Zha,“Lowrankglobalgeometric consistencyforpartial-duplicateimagesearch,”inInternationalConference onPatternRecognition,2014,pp.3939–3944.

[11]Y.Lin,C.Xu,L.Yang,Z.Lin,andH.Zha,“l1-normglobalgeometric consistencyforpartial-duplicateimageretrieval,”inInternational ConferenceonImageProcessing,2014,pp.3033–3037.

[12]D.NisterandH.Stewenius,“Scalablerecognitionwithavocabulary tree,”inComputerVisionandPatternRecognition,vol.2,2006,pp.2161–2168.

[13]G.YuandJ.-M.Morel,“ASIFT:Analgorithmforfullyaffine invariantcomparison,”ImageProcessingOnLine,vol.1,2011,http://dx.doi.org/ 10.5201/ipol.2011.my-asift.

[14]D.G.Lowe,“Distinctiveimagefeaturesfromscale-invariant keypoints,”InternationalJournalofComputerVision,vol.60,no.2,pp.91–110, 2004.

发明内容

为了克服上述现有技术的不足，本发明提供一种基于形状交互矩阵(Shape InteractionMatrix，简称SIM)的具有仿射变换不变性的错误匹配检验方法，采用形状交 互矩阵，通过比较特征点的位置信息得到错误匹配对，本发明模型简单，理论性好，实时性 能显著。

本发明提供的技术方案是：

一种基于形状交互矩阵(ShapeInteractionMatrix，简称SIM)的图像错误匹配 检验方法，通过两幅图像之间匹配的特征点对计算得到两幅图像关于齐次坐标的两个形状 交互矩阵，再通过比较两个形状交互矩阵逐列之间的差异，得到两幅图像的错误匹配对，包 括如下步骤：

1)输入两幅图像作为待比较图像，其中一幅为待查询图片，另一幅为对照图片；利 用仿射-尺度不变特征变换方法(Affine-SIFT，参见引用文献[13])提取所述两幅待比较图 像中的对仿射变换不敏感的局部特征点并计算各特征点的128维SIFT局部描述子(Local featuredescriptor)；根据SIFT提供的特征匹配方法(参见引用文献[14])，通过寻找两特 征点之间描述子的欧氏距离较为接近，而与其他特征点描述子间欧氏距离较远的特征点 对，作为两幅图像间的候选特征匹配对(putativematchedfeaturepairs)；进一步得到 两幅图像中匹配的各特征点的坐标，分别用式1和式2表示：

$X_1=\left(\begin{array}{cccc}{x}_{11}& x_{12}& \mathrm{...}& x_{1n}\\ y_{11}& y_{12}& \mathrm{...}& y_{1n}\end{array}\right)$(式1)

$X_2=\left(\begin{array}{cccc}{x}_{21}& x_{22}& \mathrm{...}& x_{2n}\\ y_{21}& y_{22}& \mathrm{...}& y_{2n}\end{array}\right)$(式2)

式1和式2中，x_ij与y_ij分别为两幅图像中特征点的坐标值；X₁、X₂的 每一列对应为一组匹配特征点的坐标(例如一幅图像中坐标为(x₁₁,y₁₁)的特征点与另一幅 图像中坐标为(x₂₁,y₂₁)的特征点相互匹配，以此类推)；n为匹配对的总数；

接下来对两组齐次坐标X₁,X₂分别做标准化处理，得到标准化后的齐次坐标

${\bar{X}}_1=\left(\begin{array}{cccc}{\bar{x}}_{11}& {\bar{x}}_{12}& \mathrm{...}& {\bar{x}}_{1n}\\ {\bar{y}}_{11}& {\bar{y}}_{12}& \mathrm{...}& {\bar{y}}_{1n}\\ 1& 1& \mathrm{...}& 1\end{array}\right)$(式3)

${\bar{X}}_2=\left(\begin{array}{cccc}{\bar{x}}_{21}& {\bar{x}}_{22}& \mathrm{...}& {\bar{x}}_{2n}\\ {\bar{y}}_{21}& {\bar{y}}_{22}& \mathrm{...}& {\bar{y}}_{2n}\\ 1& 1& \mathrm{...}& 1\end{array}\right)$(式4)

式3和式4中，齐次坐标的第三行均为1，也即[X]_3,c≡1；i∈{1,2},j∈ [1,n],与为标准化后的坐标值，标准化的计算公式为：

${\bar{x}}_{ij}=\frac{x_{ij}-{\mu }_{x_i}}{{\sigma }_{x_i}}$(式5)

${\bar{y}}_{ij}=\frac{y_{ij}-{\mu }_{y_i}}{{\sigma }_{y_i}}$(式6)

式5和式6中，和分别为x_ij与y_ij的平均值与标准差，其计算公式为：

${\mu }_{x_i}=\frac{1}{n}{\Sigma }_{j=1}^n{x}_{ij}$(式7)

${\mu }_{y_i}=\frac{1}{n}{\Sigma }_{j=1}^n{y}_{ij}$(式8)

${\sigma }_{x_i}=\frac{1}{n}{\Sigma }_{j=1}^n{(x_{ij}-{\mu }_{x_i})}^2$(式9)

${\sigma }_{y_i}=\frac{1}{n}{\Sigma }_{j=1}^n{(y_{ij}-{\mu }_{y_i})}^2$(式10)

2)分别计算得到两幅图像关于齐次坐标的两个形状交互矩阵，所述两个形状交互 矩阵分别由式11和式12求得：

$Z_1={{\bar{X}}_1}^T{\left({\bar{X}}_1{{\bar{X}}_1}^T\right)}^{-1}{\bar{X}}_1$(式11)

$Z_2={{\bar{X}}_2}^T{\left({\bar{X}}_2{{\bar{X}}_2}^T\right)}^{-1}{\bar{X}}_2$(式12)

式11和式12中，X₁、X₂的每一列对应为一组匹配特征点的齐次坐标；Z₁和Z₂为两个 形状交互矩阵，分别由式13和式14表示：

(式13)

(式14)

式13和式14中，表示矩阵的摩尔－彭若斯广义逆，当X矩阵各行线性无关时，即 XX^T可逆时，表示为式15：

(式15)

3)通过欧氏距离法或余弦相似法计算两个形状交互矩阵逐列之间的差异，得到两 幅图像的错误匹配对。

上述基于形状交互矩阵的图像错误匹配检验方法，进一步地，所述对照图片为图 像数据库中的被检索图片。

上述基于形状交互矩阵的图像错误匹配检验方法，进一步地，步骤1)所述提取所 述两幅待比较图像中的局部特征点，具体是通过Affine-SIFT方法提取所述两幅待比较图 像中的局部特征点；所述Affine-SIFT方法为文献“G.YuandJ.-M.Morel,“ASIFT:An algorithmforfullyaffineinvariantcomparison,”ImageProcessingOnLine, vol.1,2011”中所记载的方法；步骤1)所述局部特征点之间的匹配方法，具体为文献 “D.G.Lowe,“Distinctiveimagefeaturesfromscale-invariantkeypoints,” InternationalJournalofComputerVision,vol.60,no.2,pp.91–110,2004.”中所记载 的方法。

上述基于形状交互矩阵的图像错误匹配检验方法，进一步地，步骤3)所述欧氏距 离法通过计算所述形状交互矩阵Z₁和Z₂的欧氏距离，再设定阈值截断点进行比较，得到两幅 图像的错误匹配对，具体包括如下步骤：

11)分别计算Z₁的第i个列向量与Z₂的第i个列向量之间的欧氏距离d_i：

$d_i=\left|\right|{\left[Z_1\right]}_{:,i}-{\left[Z_2\right]}_{:,i}|{|}_2^2$(式16)

式16中，Z₁和Z₂分别为形状交互矩阵Z₁和Z₂；[·]_:,i代表矩阵的第i个列向量；代表向量二范数的平方；i∈[1,n]，即一共需要计算n个欧氏距离值，n为匹配对的总数；

12)将各列向量之间的欧氏距离d_i由大到小排列，如式17：

d_sort＝SORT(d)(式17)

式17中，SORT(·)表示对一组数值降序排列；d_sort为降序后的距离值，满足 d_sort_i>d_sort_i+1；

13)计算得到距离坐标原点最近点的位置，将所述位置相应的点作为阈值截断点， 所述阈值截断点通过式18确定(如图3所示)：

(式18)

式18中，i_t表示阈值截断点位于d_sort中的第i_t个；d_sort_i表示Z₁和Z₂的第i个列 向量间降序后的欧氏距离；max_j∈[1,n]dist_sort_j表示n个d_sort_i里的最大值；

14)在得到这个阈值截断点i_t后，dist_sort中所有大于的前k个距离值 所对应的匹配对为错误匹配，由此得到两幅图像的错误匹配对。

上述基于形状交互矩阵的图像错误匹配检验方法，进一步地，步骤3)所述余弦相 似法通过计算所述形状交互矩阵Z₁和Z₂的余弦相似度，再设定固定阈值进行比较，得到两幅 图像的错误匹配对，具体包括如下步骤：

21)计算Z₁的第i个列向量与Z₂的第i个列向量之间的余弦相似度s_i：

$S_i=\frac{-{\left[Z_1\right]}_{:,i}{\left[Z_2\right]}_{:,i}}{\left|\right|{\left[Z_1\right]}_{:,i}\left|{|}_2^2\right|\left|{\left[Z_2\right]}_{:,i}\right|{|}_2^2}$(式19)

式19中，s_i为Z₁的第i个列向量与Z₂的第i个列向量之间的余弦相似度， Z₁和Z₂分别为形状交互矩阵Z₁和Z₂；[·]_:,i代表矩阵的第i个列向量；代表 向量二范数的平方；i∈[1,n]，即一共需要计算n个余弦相似度值，n为匹配对的总数；

22)设定一个不大于1的固定阈值τ，将s_i中所有小于τ的余弦相似度值所对应的匹 配对为错误匹配，由此得到两幅图像的错误匹配对。

上述余弦相似法中，进一步地，所述固定阈值τ根据错误匹配对在所有匹配对中所 占的比例来相应设定，错误匹配对在所有匹配对中所占的比例越大，设定所述固定阈值τ为 越靠近1的值。在本发明实施例中，所述固定阈值τ的阈值范围为[0.5,0.75]。

上述基于形状交互矩阵的图像错误匹配检验方法可应用于图像检索、三维点云配 准和图像或视频中的物体识别等领域。

在去除错误匹配后，可以利用剩余的正确匹配对，针对不同应用背景，做进一步的 处理。如在图像检索中，可以利用剩余匹配的个数作为排序依据，对检索结果进行重排序。

将本发明提供方法基于形状交互矩阵(ShapeInteractionMatrix，简称SIM)的 图像错误匹配检验方法应用于图像检索，包括步骤如下：

A1)对图像数据库中所有图片进行特征点的检测与描述；

A2)训练得到一个视觉字字典并量化所有检测到的特征点，过滤掉在数据库中出 现次数最多5％与最少10％的视觉字，以不同视觉字为节点，以图像中出现的所有特征点为 元素，建立便于检索的倒排索引(InvertedIndex)；

A3)在标准图像数据库上分别加入一千、一万、十万以及一百万规模的冗杂图片， 利用倒排索引确定查询图片与被检索图片之间的候选匹配关系；

A4)输入两幅图像作为待比较图像，针对两幅图像之间匹配的特征点对，得到两幅 图像中各特征点的齐次坐标；

A5)分别计算得到两幅图像关于齐次坐标的两个形状交互矩阵；

A6)通过欧氏距离法或余弦相似法计算两个形状交互矩阵逐列之间的差异，得到 两幅图像的错误匹配对；

A7)去除其中的错误匹配，过滤后得到正确匹配对数；

A8)反复执行步骤A4)至A7)，并统计通过当前查询图片与数据库中所有被检索图 片之间正确匹配对的数量，将正确匹配对的数量由大到小进行重排序，得到图像检索结果。

与现有技术相比，本发明的有益效果是：

本发明提供一种基于形状交互矩阵(ShapeInteractionMatrix，简称SIM)的具 有仿射变换不变性的错误匹配检验方法，通过两幅图像之间匹配的特征点对计算得到两幅 图像关于齐次坐标的两个形状交互矩阵，再通过比较两个形状交互矩阵逐列之间的差异， 得到两幅图像的错误匹配对；本发明模型简单，理论性好，实时性能显著。本发明提供方法 的有点主要有：

(一)模型简单：本发明仅用特征点的位置信息作为输入来最终过滤出错误匹配， 而无需其他几何先验信息(如特征点的主方向、主尺度信息)，与特征点的检测方法及描述 方法完全无关，大大扩展了其应用范围；

(二)本发明方法的有效性得到理论上的验证：形状交互矩阵最初被用于聚类分 析，它能够刻画和表示各点之间的几何关系；进一步地，当两个点集之间存在仿射变换时 (包括平移、旋转、尺度及错切变换)，其形状交互矩阵保持不变；因此，本发明提供方法对于 仿射几何变换具有较强的鲁棒性；

(三)本发明在计算速度上性能非常显著：本发明采用非迭代方式进行计算，避免 了较为耗时的迭代拟合估计过程；两个点集的形状交互矩阵可以分别通过简单直接的公式 计算得到，而随后的形状交互矩阵比较过程效率很高，适用于对实时性要求较高的应用场 合。

附图说明

图1是本发明实施例中采用的基于形状交互矩阵的图像错误匹配检验方法的流程 框图。

图2是本发明实施例中采用的基于形状交互矩阵的图像错误匹配检验方法的方法 步骤示意图；

其中，各图中的1～9为9个不同的候选特征点匹配对；(a)为候选匹配对，(a)中上 下两幅示例图分别表示两张图像中检测到的特征点各自在图像中所处的位置，可以发现下 图中的点与上图中的点之间存在一个明显的仿射变换(AffineTransformation)，而5号特 征匹配对的位置似乎不满足这个统一的仿射变换，可能是错误匹配对；(b)为SIM矩阵，(b) 中Z₁与Z₂分别为用齐次坐标计算得到的两个形状交互矩阵；(c)为差异项，(c)中上图为Z₁与 Z₂逐元素(element-wise)之间的差异大小，越接近白色表示差异越显著，越接近黑色表示 差异越不明显，(c)中下图为Z₁与Z₂逐列(column-wise)之间的差异，可以发现5号特征匹配 对逐列间的差异较其他特征点很显著；(d)为检测到的错误匹配，(d)图中标出了通过本发 明提供方法检测得到的错误匹配对，也即5号匹配对，用虚线标出。

图3是本发明实施例中阈值截断点选取方法的示意图；

其中，10为降序排列的欧氏距离曲线到坐标原点的距离最近处，11表示将上述到 坐标原点的距离最近处的点设定为阈值截断点，12为错误匹配对在形状交互矩阵中所对应 的欧氏距离值，13为正确匹配对在形状交互矩阵中所对应的欧氏距离值。

图4为已有的十一种方法与本发明提供方法在三个数据库上平均检索时间的比较 示意图；

其中，[0]为本发明；[1]～[11]分别为RANSAC、MLESAC、ICF、VFC(包括VFC、 FastVFC、SparseVFC，由于这三种方法出自同一文献[4]，我们用[4-1]、[4-2]、[4-3]加以区 别)、WGC、EWGC、SGC、PGM、GC、LRGGC、L1GGC、BOF，[1]～[11]所代表的方法分别与引用文献 [1]～[11]相对应。

图5为本发明提供方法[0]与方法BoF[12]在三个数据库上的检索结果及准确率- 召回率曲线对比示意图；

其中，(a)为GCDup数据库；(b)为Holiday数据库；(c)为Oxford5k数据库；[0]为本 发明提供方法；[12]为方法BoF。

具体实施方式

下面结合附图，通过实施例进一步描述本发明，但不以任何方式限制本发明的范 围。

本发明提供一种基于形状交互矩阵的具有仿射变换不变性的图像错误匹配检验 方法，图1是本发明提供方法的流程框图，包括如下步骤：

步骤1：输入两幅图像，其中一幅为查询图片，另一幅为数据库中的被检索图片之 一。首先采用业界已有的仿射-尺度不变特征变换方法(Affine-ScaleInvariantFeature Transformation，简称Affine-SIFT，参见引用文献[13])，分别对每幅图像做不同程度的仿 射变换得到几幅仿射变换采样图，在这些仿射变换采样图像上使用引用文献[14]提出的方 法，进一步做不同程度的尺度变换得到几幅尺度变换采样图；继而使用的高斯差分 (DifferentofGauussian，简称DoG，参见引用文献[14])检测出在多个尺度空间下的极值 点作为局部特征点，这些点对平移、旋转及尺度变换具有一定的不变性；再将各尺度不变的 局部特征点在仿射-尺度变换采样图像中的坐标位置反变换回原始图像空间中，以获得在 仿射变换空间下具有一定不变性的局部特征点；依循文献[14]所述，根据特征点像素梯度 分布来确定特征点的主方向和主尺度，之后以主方向为基准，以主尺度为范围，在各特征点 4×4的邻域内分别求取8个方向上的梯度分布，得到共128维的直方图向量作为该特征点的 “特征描述子”。接下来，依据文献[14]所述，在寻找特征匹配时，比较与某特征点的特征描 述子在欧氏距离意义下最近和次近的特征点，如果最近的欧氏距离除以次近的欧氏距离小 于某个比例阈值(文献[14]中给出的经验阈值为0.5，如果对匹配对的精度要求较高可设为 0.4，若对匹配对数目要求比较多可设为0.6)，则接受这一对匹配点，如此可得到两幅图像 之间的候选特征匹配对(图2(a))。设两幅图像中相互匹配的各特征点的坐标如下：

$X_1=\left(\begin{array}{cccc}{x}_{11}& x_{12}& \mathrm{...}& x_{1n}\\ y_{11}& y_{12}& \mathrm{...}& y_{1n}\end{array}\right)$(式1)

$X_2=\left(\begin{array}{cccc}{x}_{21}& x_{22}& \mathrm{...}& x_{2n}\\ y_{21}& y_{22}& \mathrm{...}& y_{2n}\end{array}\right)$(式2)

式1和式2中，X₁、X₂的每一列对应为一组匹配特征点的坐标(例如一 幅图像中坐标为(x₁₁,y₁₁)的特征点与另一幅图像中坐标为(x₂₁,y₂₁)的特征点相互匹配，以 此类推)，n为匹配对的总数。

接下来对两组其次坐标X₁,X₂分别做标准化得到标准化后的齐次坐标

${\bar{X}}_1=\left(\begin{array}{cccc}{\bar{x}}_{11}& {\bar{x}}_{12}& \mathrm{...}& {\bar{x}}_{1n}\\ {\bar{y}}_{11}& {\bar{y}}_{12}& \mathrm{...}& {\bar{y}}_{1n}\\ 1& 1& \mathrm{...}& 1\end{array}\right)$(式3)

${\bar{X}}_2=\left(\begin{array}{cccc}{\bar{x}}_{21}& {\bar{x}}_{22}& \mathrm{...}& {\bar{x}}_{2n}\\ {\bar{y}}_{21}& {\bar{y}}_{22}& \mathrm{...}& {\bar{y}}_{2n}\\ 1& 1& \mathrm{...}& 1\end{array}\right)$(式4)

其中齐次坐标的第三行均为1，也即[X]_3,c≡1；i∈{1,2},j∈[1,n],与为标准化后的坐标值，标准化的计算公式为：

${\bar{x}}_{ij}=\frac{x_{ij}-{\mu }_{x_i}}{{\sigma }_{x_i}}$(式5)

${\bar{y}}_{ij}=\frac{y_{ij}-{\mu }_{y_i}}{{\sigma }_{y_i}}$(式6)

其中和分别为x_ij与y_ij的平均值与标准差，其计算公式为：

${\mu }_{x_i}=\frac{1}{n}{\Sigma }_{j=1}^n{x}_{ij}$(式7)

${\mu }_{y_i}=\frac{1}{n}{\Sigma }_{j=1}^n{y}_{ij}$(式8)

${\sigma }_{x_i}=\frac{1}{n}{\Sigma }_{j=1}^n{(x_{ij}-{\mu }_{x_i})}^2$(式9)

${\sigma }_{y_i}=\frac{1}{n}{\Sigma }_{j=1}^n{(y_{ij}-{\mu }_{y_i})}^2$(式10)

步骤2：分别计算两幅图像的形状交互矩阵(图2(b)):

(式11)

(式12)

其中表示矩阵的摩尔－彭若斯广义逆(Moore-Penrosepseudo-inverse)，当X 矩阵各行线性无关时，也即XX^T可逆时，有：

(式13)

故形状交互矩阵可由下述公式求得：

$Z_1={{\bar{X}}_1}^T{\left({\bar{X}}_1{{\bar{X}}_1}^T\right)}^{-1}{\bar{X}}_1$(式14)

$Z_2={{\bar{X}}_2}^T{\left({\bar{X}}_2{{\bar{X}}_2}^T\right)}^{-1}{\bar{X}}_2$(式15)

步骤3：根据形状交互矩阵的性质，正确匹配对在形状交互矩阵中的表示向量之间 应该比较类似，而错误匹配对在形状交互矩阵中的表示向量则应该差异较大。因此我们可 以通过计算两个形状交互矩阵Z₁与Z₂逐列之间的差异，来判定哪些匹配对为错误匹配(图2 (c))。本步骤可以有两种实现方式：

方式1，欧氏距离法：

11)分别计算Z₁的第i个列向量与Z₂的第i个列向量之间的欧氏距离d_i：

$d_i=\left|\right|{\left[Z_1\right]}_{:,i}-{\left[Z_2\right]}_{:,i}|{|}_2^2$(式16)

式16中，Z₁和Z₂表示步骤2中得到的形状交互矩阵，[·]_:,i代表矩阵的第i个列向 量，代表向量二范数的平方，i∈[1,n]，也即一共需要计算n个欧氏距离值，n为匹配对 的总数。

12)如图3所示，将各列向量之间的欧氏距离由大到小排列:

d_sort＝SORT(d)(式17)

式17中，SORT(·)表示对一组数值降序排列，d_sort为降序后的距离值，满足 d_sort_i>d_sort_i+1。

13)如图3所示，计算出距离坐标原点最近点的位置，并将该点作为阈值截断点，其 确定方式如下：

(式18)

式18中，i_t表示阈值截断点位于d_sort中的第i_t个，d_sort_i表示Z₁和Z₂的第i个列 向量间的欧氏距离，max_j∈[1,n]dist_sort_j表示n个d_sort_i里的最大值。

14)在得到这个阈值截断点i_t后，dist_sort中所有大于的前k个距离值 所对应的匹配对为错误匹配。

方式2，余弦相似法：

21)计算Z₁的第i个列向量与Z₂的第i个列向量之间的余弦相似度s_i：

$S_i=\frac{-{\left[Z_1\right]}_{:,i}{\left[Z_2\right]}_{:,i}}{\left|\right|{\left[Z_1\right]}_{:,i}\left|{|}_2^2\right|\left|{\left[Z_2\right]}_{:,i}\right|{|}_2^2}$(式19)

式19中，Z₁和Z₂表示步骤2中得到的形状交互矩阵，[·]_:,i代表矩阵的第i个列向 量，代表向量二范数的平方，i∈[1,n]，也即一共需要计算n个余弦相似度值，n为匹配 对的总数。

22)由于故我们可以方便的设一个固定阈值τ，将s_i中所有小于τ的余 弦相似度值所对应的匹配对为错误匹配。τ的选取可以根据错误匹配对在所有匹配对中所 占的比例做出相应的调整，具体来说，比例越大τ也相应需要选取较靠近1的值，对于图像检 索这一应用场景中，我们给出τ的参考阈值范围为[0.5,0.75]。

在去除错误匹配后，可以利用剩余的正确匹配对(图2(d))，针对不同应用背景，做 进一步的处理。如在图像检索中，可以利用剩余匹配的个数作为排序依据，对检索结果进行 重排序。

以下通过实施例对本发明在图像检索问题中的实施过程进行详细描述，本发明还 可应用于图像及三维点云配准及物体识别等领域中，其实施也可以参考下述实施示例中的 部分内容，这里不再详述。

本实施例中，数据库采用了三个较广泛采用的数据库作为被检索数据库，分别为 GCDup数据库、Holiday数据库和Oxford5k数据库。其中，GCDup数据库一共含有1104张图片， 相似图片组共33组；Holiday数据库一共含有1491张图片，相似图片组共500组；Oxford5k数 据库一共含有5062张图片，相似图片共55组。此外，为更贴近实验，我们额外采用了一个冗 杂图片数据库MIRFlickr-1M，其中含有一百万张从网络中获取的图片。实施中，使用每个相 似图片组中的一张图片作为查询图片，将同一相似图片组中的其他图片与冗杂图片库随机 打乱顺序进行融合作为目标图像库，再通过本发明提供方法从中检索出与查询图片相关的 图片。

针对本发明提供方法的性能评价，我们使用的评价指标为平均准确率(mean averageprecision,简称mAP)和平均检索时间，通过比较本发明提供方法与其他业界已有 优秀方法在性能上的差异来进行性能评价。

本实施例的实施步骤如下：

a)使用仿射不变特征变换方法(Affine-SIFT，参见引用文献[13])对所有图片(包 括上文所述的三个被检索数据库以及冗杂图片数据库)进行特征点的检测与描述，具体为： 首先对每幅图像分别做不同程度的仿射变换得到几幅仿射变换采样图，在这些仿射变换采 样图像上使用引用文献[14]提出的方法，进一步做不同程度的尺度变换得到几幅尺度变换 采样图；继而使用的高斯差分(DifferentofGauussian，简称DoG，参见引用文献[14])检 测出在多个尺度空间下的极值点作为局部特征点，这些点对平移、旋转及尺度变换具有一 定的不变性；再将各尺度不变的局部特征点在仿射-尺度变换采样图像中的坐标位置反变 换回原始图像空间中，以获得在仿射变换空间下具有一定不变性的局部特征点；依循文献 [14]所述，根据特征点像素梯度分布来确定特征点的主方向和主尺度，之后以主方向为基 准，以主尺度为范围，在各特征点4×4的邻域内分别求取8个方向上的梯度分布，得到共128 维的直方图向量作为该特征点的“SIFT特征描述子”；

b)基于词袋模型(BagofFeatures,简称BoF，参见引用文献[12])，以所有被检索 数据库中的图像中检测到的所有特征点的128维SIFT描述子作为输入，使用“分层K均值聚 类”算法(HierarchicalK-Means,可参见引用文献[12])，首先从所有作为输入的SIFT描述 子中随机选取10个作为初始的聚类中心，通过迭代的方式，不断将各特征点归到与其SIFT 描述子距离最近的一个聚类中心中，当所有特征点都分别归到这10个类中以后，再对属于 同一类别下的所有特征点求其SIFT描述子的均值作为10个新的聚类中心，如此反复迭代直 至所有特征点的所属类别不在变化；接下来对每个聚类下的所有特征点再随机选取10个聚 类中心，重复上述步骤，找到第二层级下的10个聚类结果；这里我们一共在6个层级上做上 述聚类算法，当算法收敛时，我们就得到了10⁶个聚类中心，由此构成了一个大小为一百万 规模的视觉字字典(为了降低，可以过滤掉在数据库中出现次数最多5％与最少10％的视觉 字)；此时对每个输入的特征点，我们可以求取与其128维的SIFT描述子距离最近的聚类中 心，并将该特征点归为这个聚类中，当我们为所有归入同一聚类的特征点用相同的编码编 号后，就完成了对特征点的量化，图像中的所有特征点就都可以用不同的视觉字来简单表 示了；用图像总数目除以包含每个视觉字(聚类中心)在所有图像中出现的总次数，再把商 数取对数，就得到了每个视觉字的逆文档频率(InverseDocumentFrequency，IDF，可参见 引用文献[12])；用统计每幅图片中各视觉字出现的次数可以得到词频分布的直方图向量 (TermFrequency,TF)；用每幅图片的TF乘以相应的IDF，就得到了信息检索中常用的词频- 逆文档频率向量(TF-IDF)；

c)以不同视觉字为节点，以图像中出现的所有特征点为节点中的单元，以图像ID、 特征点在图像中的坐标、特征点的SIFT主尺度、主方向、特征点所属视觉字词频(TF)、特征 点所属视觉字逆文档频率(IDF)等信息作为单元中的具体存储内容，在三个标准图像数据 库上分别加入一千、一万、十万以及一百万规模的冗杂图片，分别建立便于检索的倒排索引 表(InvertedIndex，可参见引用文献[6])；

d)对每一幅查询图片，利用倒排索引表快速查找与查询图片有视觉字交集的所有 被检索图片，划定检索子集A；在子集A中使用传统方法计算查询图片与被检索图片的词频- 逆文档频率向量(TF-IDF)之间的余弦距离(可参见引用文献[12])，按照从小到大的顺序排 序，得到粗略的检索结果并记录检索时间；

e)在粗略检索结果中，进一步选取前1000～5000个被检索图片作为范围更小的检 索子集B，进行接下来的几何校验重排序过程：首先通过查找倒排表，获取当前查询图片及 子集B中的被检索图片之间特征点的候选匹配关系及匹配特征点的坐标信息；

f)按照本发明提供方法中的步骤1所述，对当前查询图片及每个被检索图片,分别 按照两幅图片之间特征点匹配顺序构造两个匹配特征点的齐次坐标矩阵；

g)按照本发明提供方法中的步骤2所述，利用当前查询图片与每个被检索图片中 候选匹配特征点的齐次坐标矩阵，分别计算得到两个形状交互矩阵；

h)按照本发明提供方法中的步骤3所述，使用欧氏距离法或余弦相似法计算两个 形状交互矩阵逐列之间的差异，来判定哪些匹配对为错误匹配，哪些匹配为正确匹配，由此 得到错误匹配对和正确匹配对；

i)反复执行步骤(f)至(h)，并统计通过当前查询图片与数据库中所有被检索图片 之间正确匹配对的数量，将正确匹配对的数量由大到小进行重排序，得到精确的检索结果， 计算检索准确度，并记录检索时间；

j)反复执行步骤(e)至(i)，对所有经过本发明处理前后的检索准确度和检索时间 求平均，得到平均检索准确度及平均检索时间；

k)反复执行步骤(d)至(j)，记录采用本发明提供方法在三个标准图像数据库、四 种不同冗杂图片规模情况下的平均检索准确度及平均检索时间；

l)通过比较本发明与其他业界已有优秀方法在平均准确度及平均检索时间上的 表现，分析我们的发明与业界已有优秀方法的性能。

对以上实施例进行性能结果分析：

上述实施例的性能比较结果如表1所示，针对所有标准数据库和所有不同规模冗 杂数据库进行检索，本发明提供方法取得了优于其他业界已有优秀方法的检索平均准确 度。

表1业界已有优秀方法及本发明在三个标准数据库上不同规模检索精度(mAP)的 比较

如图4所示，可以看出，我们的发明保证检索准确度的情况下，在平均检索时间上 也明显优于大部分业界已有优秀方法。图5是从三个数据集中各自选取的一组检索结果图 以及对应的准确率-召回率曲线图(ROC)，通过对比该图中原始的词袋模型方法(BoF)以及 本发明提供方法[0]，可以说明本发明对原始方法在检索精度上的提升非常显著。

需要注意的是，公布实施例的目的在于帮助进一步理解本发明，但是本领域的技 术人员可以理解：在不脱离本发明及所附权利要求的精神和范围内，各种替换和修改都是 可能的。因此，本发明不应局限于实施例所公开的内容，本发明要求保护的范围以权利要求 书界定的范围为准。