关键点匹配方法、装置、电子设备以及存储介质

摘要

本公开是关于一种关键点匹配方法、装置、电子设备以及存储介质，其中，所述的方法包括：获取第一图像的关键点和第二图像的关键点；对所述第一图像的关键点和所述第二图像的关键点进行匹配，获得初始匹配对集合；根据所述初始匹配对集合中任意两个匹配对之间的空间信息和预设关系，构造出目标矩阵；从所述目标矩阵中搜索出所述初始匹配对集合的最大子集合作为最终匹配对集合，其中，所述最大子集合中任意两个匹配对之间的空间信息均满足所述预设关系。本公开实施例在精度尤其是在速度方面有明显提升，并且不受限于匹配的点的数量，即使匹配的点较少时也能快速精准的进行关键点匹配。

权利要求

1.一种关键点匹配方法，其特征在于，包括：

获取第一图像的关键点和第二图像的关键点；

对所述第一图像的关键点和所述第二图像的关键点进行匹配，获得初始匹配对集合；

根据所述初始匹配对集合中任意两个匹配对之间的空间信息和预设关系，构造出目标矩阵，包括，根据所述初始匹配对集合中匹配对的个数构造初始矩阵；从所述初始匹配对集合中选取第i个匹配对和第j个匹配对；判断所述第i个匹配对和所述第j个匹配对之间的空间信息是否满足预设关系；若所述第i个匹配对和所述第j个匹配对之间的空间信息满足预设关系，则将所述初始矩阵中第i行和第j列的矩阵元赋值为第一数值；若所述第i个匹配对和所述第j个匹配对之间的空间信息不满足预设关系，则将所述初始矩阵中第i行和第j列的矩阵元赋值为第二数值，其中，所述第二数值与所述第一数值不相同；返回从所述初始匹配对集合中选取第i个匹配对和第j个匹配对的步骤，直至所述初始矩阵中每一个矩阵元均被赋值，得到目标矩阵；

从所述目标矩阵中搜索出所述初始匹配对集合的最大子集合作为最终匹配对集合，其中，所述最大子集合中任意两个匹配对之间的空间信息均满足所述预设关系。

2.根据权利要求1所述的关键点匹配方法，其特征在于，所述初始矩阵为对称矩阵，所述对称矩阵的行数和列数均为所述初始匹配对集合中匹配对的个数。

3.根据权利要求2所述的关键点匹配方法，其特征在于，所述将所述初始矩阵中第i行和第j列的矩阵元赋值为第一数值，包括：将所述初始矩阵中第i行和第j列的矩阵元以及第j行和第i列的矩阵元赋值为第一数值。

4.根据权利要求2所述的关键点匹配方法，其特征在于，将所述初始矩阵中第i行和第j列的矩阵元赋值为第二数值，包括：将所述初始矩阵中第i行和第j列的矩阵元以及第j行和第i列的矩阵元赋值为第二数值。

5.根据权利要求1所述的关键点匹配方法，其特征在于，所述预设关系为：

ABS(dxi-dxj+dyi-dyj)

6.根据权利要求1至5任意一项所述的关键点匹配方法，其特征在于，所述对所述第一图像的关键点和所述第二图像的关键点进行匹配，获得初始匹配对集合，包括：基于欧氏距离对所述第一图像的关键点和所述第二图像的关键点进行匹配，获得初始匹配对集合。

7.根据权利要求1至5任意一项所述的关键点匹配方法，其特征在于，所述从所述目标矩阵中搜索出所述初始匹配对集合的最大子集合作为最终匹配对集合，包括：基于贪心算法从所述目标矩阵中搜索出所述初始匹配对集合的最大子集合作为最终匹配对集合。

8.一种关键点匹配装置，其特征在于，包括：

关键点获取模块，被配置为获取第一图像的关键点和第二图像的关键点；

匹配模块，被配置为对所述第一图像的关键点和所述第二图像的关键点进行匹配，获得初始匹配对集合；

目标矩阵构造模块，被配置为根据所述初始匹配对集合中任意两个匹配对之间的空间信息和预设关系，构造出目标矩阵，所述目标矩阵构造模块包括：初始矩阵构造单元，被配置为根据所述初始匹配对集合中匹配对的个数构造初始矩阵；匹配对选取单元，被配置为从所述初始匹配对集合中选取第i个匹配对和第j个匹配对；执行单元，被配置为执行所述第i个匹配对和所述第j个匹配对之间的空间信息是否满足预设关系；第一判断单元，被配置为在所述第i个匹配对和所述第j个匹配对之间的空间信息满足预设关系时，将所述初始矩阵中第i行和第j列的矩阵元赋值为第一数值；第二判断单元，被配置为在所述第i个匹配对和所述第j个匹配对之间的空间信息不满足预设关系时，将所述初始矩阵中第i行和第j列的矩阵元赋值为第二数值，其中，所述第二数值与所述第一数值不相同；进入所述匹配对选取单元执行从所述初始匹配对集合中选取第i个匹配对和第j个匹配对的功能，直至所述初始矩阵中每一个矩阵元均被赋值，得到目标矩阵；

目标矩阵搜索模块，被配置为从所述目标矩阵中搜索出所述初始匹配对集合的最大子集合作为最终匹配对集合，其中，所述最大子集合中任意两个匹配对之间的空间信息均满足所述预设关系。

9.根据权利要求8所述的关键点匹配装置，其特征在于，所述初始矩阵为对称矩阵，所述对称矩阵的行数和列数均为所述初始匹配对集合中匹配对的个数。

10.根据权利要求9所述的关键点匹配装置，其特征在于，所述第一判断单元，被配置为在所述第i个匹配对和所述第j个匹配对之间的空间信息满足预设关系时，将所述初始矩阵中第i行和第j列的矩阵元以及第j行和第i列的矩阵元赋值为第一数值。

11.根据权利要求9所述的关键点匹配装置，其特征在于，所述第二判断单元，被配置为在所述第i个匹配对和所述第j个匹配对之间的空间信息不满足预设关系时，将所述初始矩阵中第i行和第j列的矩阵元以及第j行和第i列的矩阵元赋值为第二数值。

12.根据权利要求8所述的关键点匹配装置，其特征在于，所述预设关系为：

ABS(dxi-dxj+dyi-dyj)

13.根据权利要求8至12任意一项所述的关键点匹配装置，其特征在于，所述匹配模块，被配置为基于欧氏距离对所述第一图像的关键点和所述第二图像的关键点进行匹配，获得初始匹配对集合。

14.根据权利要求8至12任意一项所述的关键点匹配装置，其特征在于，所述目标矩阵搜索模块，被配置为基于贪心算法从所述目标矩阵中搜索出所述初始匹配对集合的最大子集合作为最终匹配对集合。

15.一种电子设备，其特征在于，包括：

处理器；

用于存储处理器可执行指令的存储器；

其中，所述处理器被配置为：当一个或多个程序被一个或多个处理器执行，使得所述一个或多个处理器实现如权利要求1至7中任意一项所述的关键点匹配方法。

16.一种非临时性计算机可读存储介质，当所述存储介质中的指令由移动终端的处理器执行时，使得移动终端能够执行如权利要求1至7中任意一项所述的关键点匹配方法。

说明书

关键点匹配方法、装置、电子设备以及存储介质

技术领域

[0001] 本公开涉及计算机技术领域，尤其涉及一种关键点匹配方法、装置、电子设备以及存储介质。

背景技术

[0002] 图像匹配是图像处理的一个领域，通过图像匹配，在同一场景的不同图像之间提取一致性的关键点，来确定图像之间对应的几何关系，得到一幅匹配后的图像。相关技术中，一般是通过RANSAC算法(andom sample consensus，随机抽样一致算法)或者VFC算法(Vector Field Consensus，向量场一致性算法)进行关键点匹配。其中，RANSAC算法采用迭代的方式从被观测数据中抽取子样本集，进而估算出整个样本分布的数学模型；VFC算法将匹配问题转换为鲁棒的向量场插值问题，自动估计向量场样本的inlier(内点)集合，并且依据该集合对整个向量场进行插值。但是上述两种方式都需要进行多次迭代，算法效率低，而且当匹配的点较少时均失效。

发明内容

[0003] 为克服相关技术中存在的问题，本公开提供一种关键点匹配方法、装置、电子设备以及存储介质。

[0004] 根据本公开实施例的第一方面，提供一种关键点匹配方法，包括：

[0005] 获取第一图像的关键点和第二图像的关键点；

[0006] 对所述第一图像的关键点和所述第二图像的关键点进行匹配，获得初始匹配对集合；

[0007] 根据所述初始匹配对集合中任意两个匹配对之间的空间信息和预设关系，构造出目标矩阵；

[0008] 从所述目标矩阵中搜索出所述初始匹配对集合的最大子集合作为最终匹配对集合，其中，所述最大子集合中任意两个匹配对之间的空间信息均满足所述预设关系。

[0009] 在一个实施例中，所述根据所述初始匹配对集合中任意两个匹配对之间的空间信息和预设关系，构造出目标矩阵，包括：

[0010] 根据所述初始匹配对集合中匹配对的个数构造初始矩阵；

[0011] 从所述初始匹配对集合中选取第i个匹配对和第j个匹配对；

[0012] 判断所述第i个匹配对和所述第j个匹配对之间的空间信息是否满足预设关系；

[0013] 若所述第i个匹配对和所述第j个匹配对之间的空间信息满足预设关系，则将所述初始矩阵中第i行和第j列的矩阵元赋值为第一数值；

[0014] 若所述第i个匹配对和所述第j个匹配对之间的空间信息不满足预设关系，则将所述初始矩阵中第i行和第j列的矩阵元赋值为第二数值，其中，所述第二数值与所述第一数值不相同；

[0015] 返回从所述初始匹配对集合中选取第i个匹配对和第j个匹配对的步骤，直至所述初始矩阵中每一个矩阵元均被赋值，得到目标矩阵。

[0016] 在一个实施例中，所述初始矩阵为对称矩阵，所述对称矩阵的行数和列数均为所述初始匹配对集合中匹配对的个数。

[0017] 在一个实施例中，所述将所述初始矩阵中第i行和第j列的矩阵元赋值为第一数值，包括：

[0018] 将所述初始矩阵中第i行和第j列的矩阵元以及第j行和第i列的矩阵元赋值为第一数值。

[0019] 在一个实施例中，将所述初始矩阵中第i行和第j列的矩阵元赋值为第二数值，包括：

[0020] 将所述初始矩阵中第i行和第j列的矩阵元以及第j行和第i列的矩阵元赋值为第二数值。

[0021] 在一个实施例中，所述预设关系为：

[0022] ABS(dxi-dxj+dyi-dyj)

[0023] 其中，xi为第i个匹配对中所述第一图像的第i个匹配点，yi为第i个匹配对中所述第二图像的第i个匹配点，xj为第j个匹配对中所述第一图像的第j个匹配点，yj为第j个匹配对中所述第二图像的第j个匹配点，dxi为xi的主方向，dxj为xj的主方向，dyi为yi的主方向，dyj为yj的主方向，ABS为绝对值函数，gdxixj为xi与xj连线与dxi的夹角，gdyiyj为yi与yj连线与dyi的夹角，t1和t2是两个大于0的阈值。

[0024] 在一个实施例中，所述对所述第一图像的关键点和所述第二图像的关键点进行匹配，获得初始匹配对集合，包括：

[0025] 基于欧氏距离对所述第一图像的关键点和所述第二图像的关键点进行匹配，获得初始匹配对集合。

[0026] 在一个实施例中，所述从所述目标矩阵中搜索出所述初始匹配对集合的最大子集合作为最终匹配对集合，包括：

[0027] 基于贪心算法从所述目标矩阵中搜索出所述初始匹配对集合的最大子集合作为最终匹配对集合。

[0028] 根据本公开实施例的第二方面，提供一种关键点匹配装置，包括：

[0029] 关键点获取模块，被配置为获取第一图像的关键点和第二图像的关键点；

[0030] 匹配模块，被配置为对所述第一图像的关键点和所述第二图像的关键点进行匹配，获得初始匹配对集合；

[0031] 目标矩阵构造模块，被配置为根据所述初始匹配对集合中任意两个匹配对之间的空间信息和预设关系，构造出目标矩阵；

[0032] 目标矩阵搜索模块，被配置为从所述目标矩阵中搜索出所述初始匹配对集合的最大子集合作为最终匹配对集合，其中，所述最大子集合中任意两个匹配对之间的空间信息均满足所述预设关系。

[0033] 在一个实施例中，所述目标矩阵构造模块，包括：

[0034] 初始矩阵构造单元，被配置为根据所述初始匹配对集合中匹配对的个数构造初始矩阵；

[0035] 匹配对选取单元，被配置为从所述初始匹配对集合中选取第i个匹配对和第j个匹配对；

[0036] 执行单元，被配置为执行所述第i个匹配对和所述第j个匹配对之间的空间信息是否满足预设关系；

[0037] 第一判断单元，被配置为在所述第i个匹配对和所述第j个匹配对之间的空间信息满足预设关系时，将所述初始矩阵中第i行和第j列的矩阵元赋值为第一数值；

[0038] 第二判断单元，被配置为在所述第i个匹配对和所述第j个匹配对之间的空间信息不满足预设关系时，将所述初始矩阵中第i行和第j列的矩阵元赋值为第二数值，其中，所述第二数值与所述第一数值不相同；

[0039] 进入所述匹配对选取单元执行从所述初始匹配对集合中选取第i个匹配对和第j个匹配对的功能，直至所述初始矩阵中每一个矩阵元均被赋值，得到目标矩阵。

[0040] 在一个实施例中，所述初始矩阵为对称矩阵，所述对称矩阵的行数和列数均为所述初始匹配对集合中匹配对的个数。

[0041] 在一个实施例中，所述第一判断单元，被配置为在所述第i个匹配对和所述第j个匹配对之间的空间信息满足预设关系时，将所述初始矩阵中第i行和第j列的矩阵元以及第j行和第i列的矩阵元赋值为第一数值。

[0042] 在一个实施例中，所述第二判断单元，被配置为在所述第i个匹配对和所述第j个匹配对之间的空间信息不满足预设关系时，将所述初始矩阵中第i行和第j列的矩阵元以及第j行和第i列的矩阵元赋值为第二数值。

[0043] 在一个实施例中，所述预设关系为：

[0044] ABS(dxi-dxj+dyi-dyj)

[0045] 其中，xi为第i个匹配对中所述第一图像的第i个匹配点，yi为第i个匹配对中所述第二图像的第i个匹配点，xj为第j个匹配对中所述第一图像的第j个匹配点，yj为第j个匹配对中所述第二图像的第j个匹配点，dxi为xi的主方向，dxj为xj的主方向，dyi为yi的主方向，dyj为yj的主方向，ABS为绝对值函数，gdxixj为xi与xj连线与dxi的夹角，gdyiyj为yi与yj连线与dyi的夹角，t1和t2是两个大于0的阈值。

[0046] 在一个实施例中，所述匹配模块，被配置为基于欧氏距离对所述第一图像的关键点和所述第二图像的关键点进行匹配，获得初始匹配对集合。

[0047] 在一个实施例中，所述目标矩阵搜索模块，被配置为基于贪心算法从所述目标矩阵中搜索出所述初始匹配对集合的最大子集合作为最终匹配对集合。

[0048] 根据本公开实施例的第三方面，提供一种电子设备，包括：

[0049] 处理器；

[0050] 用于存储处理器可执行指令的存储器；

[0051] 其中，所述处理器被配置为：当所述一个或多个程序被所述一个或多个处理器执行，使得所述一个或多个处理器实现上述任意一项所述的关键点匹配方法。

[0052] 根据本公开实施例的第四方面，提供一种非临时性计算机可读存储介质，当所述存储介质中的指令由移动终端的处理器执行时，使得移动终端能够执行上述任意一项所述的关键点匹配方法。

[0053] 根据本公开实施例的第五方面，提供一种计算机程序产品，当所述计算机程序产品中的指令由移动终端的处理器执行时，使得移动终端能够执行上述任意一项所述的关键点匹配方法。

[0054] 本公开的实施例提供的技术方案可以包括以下有益效果：先对第一图像和第二图像的关键点进行初步匹配，得到初始匹配对集合，然后根据初始匹配对集合和预设关系构造目标矩阵，最后对构造出的目标矩阵进行矩阵搜索，获得最终匹配对集合。该种关键点匹配方式不需要进行多次迭代，在精度尤其是在速度方面有明显提升，并且不受限于匹配的点的数量，即使匹配的点较少时也能快速精准的进行关键点匹配。

[0055] 应当理解的是，以上的一般描述和后文的细节描述仅是示例性和解释性的，并不能限制本公开。

附图说明

[0056] 此处的附图被并入说明书中并构成本说明书的一部分，示出了符合本发明的实施例，并与说明书一起用于解释本发明的原理。

[0057] 图1是根据一示例性实施例示出的一种关键点匹配方法的流程图；

[0058] 图2是根据一示例性实施例示出的一种关键点匹配装置的框图；

[0059] 图3是根据一示例性实施例示出的一种电子设备的框图。

具体实施方式

[0060] 这里将详细地对示例性实施例进行说明，其示例表示在附图中。下面的描述涉及附图时，除非另有表示，不同附图中的相同数字表示相同或相似的要素。以下示例性实施例中所描述的实施方式并不代表与本发明相一致的所有实施方式。相反，它们仅是与如所附权利要求书中所详述的、本发明的一些方面相一致的装置和方法的例子。

[0061] 图1是根据一示例性实施例示出的一种关键点匹配方法的流程图，如图1所示，该关键点匹配方法，包括以下步骤。

[0062] 在步骤S11中，获取第一图像的关键点和第二图像的关键点。

[0063] 关键点又称兴趣点、特征点，它是在图像中突出且具有代表意义的一些点，通过这些点我们可以用来识别图像、进行图像配准、进行3D(Dimensions，维)重建等。从第一图像和第二图像中提取关键点的方法有很多种，例如，可以采用SIFT(Scale-invariant feature transform，尺度不变特征变换)算法提取第一图像中的关键点和第二图像中的关键点。

[0064] 在步骤S12中，对所述第一图像的关键点和所述第二图像的关键点进行匹配，获得初始匹配对集合。

[0065] 对第一图像的关键点和第二图像的关键点进行粗略匹配，获得多个匹配对，多个匹配对构成初始匹配对集合。对所述第一图像的关键点和所述第二图像的关键点进行匹配的方法有很多种，例如，在一个实施例中，基于欧氏距离对所述第一图像的关键点和所述第二图像的关键点进行匹配，获得初始匹配对集合。欧氏距离(也称欧几里得度量)是一个通常采用的距离定义，指在m维空间中两个点之间的真实距离，或者向量的自然长度(即该点到原点的距离)。采用欧式距离对第一图像和第二图像的关键点进行匹配的具体方式可以采用现有技术中已有的方式实现。

[0066] 假设，第一图像为A，第二图像为B，对A和B两幅图像上的关键点进行粗略匹配，得到N个匹配对，图像A中的匹配点记为x(i)，也可写为xi，图像B中相应的匹配点记为yi，匹配对(xi，yi)记为p(i)，其组成的集合记为P，P也即是初始匹配对集合。

[0067] 在步骤S13中，根据所述初始匹配对集合中任意两个匹配对之间的空间信息和预设关系，构造出目标矩阵。

[0068] 假设从集合P中任取两个元素，pi和pj，两个匹配对之间的空间信息也即是pi和pj之间的空间信息。定义预设关系f。判断任意两个匹配对之间的空间信息是否满足预设关系f，根据判断的结果进行相应的赋值，从而构造出目标矩阵。为了方便后续描述，假设目标矩阵取名为kuaishou-matrix。

[0069] 在步骤S14中，从所述目标矩阵中搜索出所述初始匹配对集合的最大子集合作为最终匹配对集合，其中，所述最大子集合中任意两个匹配对之间的空间信息均满足所述预设关系。

[0070] 目标矩阵构建成功之后，在kuaishou-matrix上搜索P的最大子集合q，使得q中任意两个元素都满足预设关系f。集合q称为集合P的最大联通组，q即是最终需要求解的正确匹配对，也即是最终匹配对集合。

[0071] 从目标矩阵中搜索出最大子集合的方法有很种，例如，在一个实施例中，所述从所述目标矩阵中搜索出所述初始匹配对集合的最大子集合作为最终匹配对集合，包括：基于贪心算法从所述目标矩阵中搜索出所述初始匹配对集合的最大子集合作为最终匹配对集合。贪心算法是指在对问题求解时，总是做出在当前看来是最好的选择，也就是说，不从整体最优上加以考虑，它所做出的是在某种意义上的局部最优解。

[0072] 在一个实施例中，所述根据所述初始匹配对集合中任意两个匹配对之间的空间信息和预设关系，构造出目标矩阵，包括：

[0073] 在步骤S131中，根据所述初始匹配对集合中匹配对的个数构造初始矩阵。

[0074] 假设初始匹配对集合P中匹配对的个数为N，则构造出的初始矩阵的大小为N*N。初始矩阵可以是多种形式的矩阵，例如，所述初始矩阵为对称矩阵，所述对称矩阵的行数和列数均为所述初始匹配对集合中匹配对的个数。其中，对称矩阵(Symmetric Matrices)是指元素以主对角线为对称轴对应相等的矩阵。

[0075] 在步骤S132中，从所述初始匹配对集合中选取第i个匹配对和第j个匹配对。

[0076] 从初始匹配对集合P中选取两个元素，也即是选取两个匹配对，假设选取的两个匹配对为pi和pj，它们分别对应kaishou-matrix的第i行和第j列。从初始匹配对集合P中选取两个元素的规则可以根据用户需要进行自行设置。

[0077] 在步骤S133中，判断所述第i个匹配对和所述第j个匹配对之间的空间信息是否满足预设关系。

[0078] 定义关系f(pi，pj)，记为fij，如果初始矩阵为对称矩阵，则满足fij＝fji。判断pi和pj之间的空间信息是否满足关系f。

[0079] 对于pi＝(xi,yi)，pj＝(xj,yj)，在一个实施例中，所述预设关系f为：

[0080] ABS(dxi-dxj+dyi-dyj)

[0081] 其中，xi为第i个匹配对中所述第一图像的第i个匹配点，yi为第i个匹配对中所述第二图像的第i个匹配点，xj为第j个匹配对中所述第一图像的第j个匹配点，yj为第j个匹配对中所述第二图像的第j个匹配点，dxi为xi的主方向，dxj为xj的主方向，dyi为yi的主方向，dyj为yj的主方向，ABS为绝对值函数，gdxixj为xi与xj连线与dxi的夹角，gdyiyj为yi与yj连线与dyi的夹角，t1和t2是两个大于0的阈值，比如台标检测中两个值均为10。

[0082] 在步骤S134中，若所述第i个匹配对和所述第j个匹配对之间的空间信息满足预设关系，则将所述初始矩阵中第i行和第j列的矩阵元赋值为第一数值。

[0083] 如果pi和pj满足关系f，则将初始矩阵中第i行和第j列的矩阵元赋值为第一数值。第一数值可以根据实际需要进行设置，例如，第一数值为1。

[0084] 考虑到对称矩阵的特殊性，为了快速构建目标矩阵，在一个实施例中，所述将所述初始矩阵中第i行和第j列的矩阵元赋值为第一数值，包括：将所述初始矩阵中第i行和第j列的矩阵元以及第j行和第i列的矩阵元赋值为第一数值。

[0085] 在步骤S135中，若所述第i个匹配对和所述第j个匹配对之间的空间信息不满足预设关系，则将所述初始矩阵中第i行和第j列的矩阵元赋值为第二数值，其中，所述第二数值与所述第一数值不相同。

[0086] 如果pi和pj不满足关系f，则将初始矩阵中第i行和第j列的矩阵元赋值为第二数值。第二数值可以根据实际需要进行设置，例如，第二数值为0。

[0087] 考虑到对称矩阵的特殊性，为了快速构建目标矩阵，在一个实施例中，将所述初始矩阵中第i行和第j列的矩阵元赋值为第二数值，包括：将所述初始矩阵中第i行和第j列的矩阵元以及第j行和第i列的矩阵元赋值为第二数值。

[0088] 在步骤S136中，返回从所述初始匹配对集合中选取第i个匹配对和第j个匹配对的步骤，直至所述初始矩阵中每一个矩阵元均被赋值，得到目标矩阵。

[0089] 对初始矩阵中对应的矩阵元赋值以后，从初始匹配对集合P中再选取另外的两个匹配对，重新判断这两个匹配对之间的空间信息是否满足关系f，根据判断的结果对初始矩阵中对应的矩阵元赋值，依次重复，直至初始矩阵中每一个矩阵元均被赋值，得到目标矩阵。由于对称矩阵的对称性，构建kuaishou-matrix总共需要计算N*(N-1)/2次关系。

[0090] 图2是根据一示例性实施例示出的一种关键点匹配装置框图。参照图2，该装置包括关键点获取模块21，匹配模块22，目标矩阵构造模块23和目标矩阵搜索模块24。

[0091] 该关键点获取模块21被配置为获取第一图像的关键点和第二图像的关键点。

[0092] 关键点获取模块21从第一图像和第二图像中提取关键点的方法有很多种，例如，采用SIFT算法提取第一图像中的关键点和第二图像中的关键点。

[0093] 该匹配模块22被配置为对所述第一图像的关键点和所述第二图像的关键点进行匹配，获得初始匹配对集合。

[0094] 对第一图像的关键点和第二图像的关键点进行粗略匹配，获得多个匹配对，多个匹配对构成初始匹配对集合。对所述第一图像的关键点和所述第二图像的关键点进行匹配的方法有很多种，例如，在一个实施例中，所述匹配模块22被配置为基于欧氏距离对所述第一图像的关键点和所述第二图像的关键点进行匹配，获得初始匹配对集合。采用欧式距离对第一图像和第二图像的关键点进行匹配的具体方式可以采用现有技术中已有的方式实现。

[0095] 该目标矩阵构造模块23被配置为根据所述初始匹配对集合中任意两个匹配对之间的空间信息和预设关系，构造出目标矩阵。

[0096] 假设从初始匹配对集合中任取两个元素(即匹配对)，判断任意两个匹配对之间的空间信息是否满足预设关系，根据判断的结果进行相应的赋值，从而构造出目标矩阵。

[0097] 该目标矩阵搜索模块24被配置为从所述目标矩阵中搜索出所述初始匹配对集合的最大子集合作为最终匹配对集合，其中，所述最大子集合中任意两个匹配对之间的空间信息均满足所述预设关系。

[0098] 构建成功之后，在目标矩阵上搜索初始匹配对集合的最大子集合，使得最大子集合中任意两个元素都满足预设关系。最大子集合称为目标矩阵的最大联通组，最大子集合即是最终需要求解的正确匹配对，也即是最终匹配对集合。

[0099] 从目标矩阵中搜索出最大子集合的方法有很种，例如，在一个实施例中，所述目标矩阵搜索模块24基于贪心算法从所述目标矩阵中搜索出所述初始匹配对集合的最大子集合作为最终匹配对集合。

[0100] 在一个实施例中，所述目标矩阵构造模块23，包括：

[0101] 初始矩阵构造单元231，被配置为根据所述初始匹配对集合中匹配对的个数构造初始矩阵。

[0102] 假设初始匹配对集合中匹配对的个数为N，则构造出的初始矩阵的大小为N*N。初始矩阵可以是多种形式的矩阵，例如，可选的，所述初始矩阵为对称矩阵，所述对称矩阵的行数和列数均为所述初始匹配对集合中匹配对的个数。

[0103] 匹配对选取单元232，被配置为从所述初始匹配对集合中选取第i个匹配对和第j个匹配对。

[0104] 从初始匹配对集合中选取两个元素，也即是选取两个匹配对，假设选取的两个匹配对为pi和pj，它们分别对应目标矩阵的第i行和第j列。从初始匹配对集合P中选取两个元素的规则可以根据用户需要进行自行设置。

[0105] 执行单元233，被配置为执行所述第i个匹配对和所述第j个匹配对之间的空间信息是否满足预设关系。

[0106] 定义关系f(pi，pj)，记为fij，如果初始矩阵为对称矩阵，则满足fij＝fji。判断pi和pj之间的空间信息是否满足关系f。

[0107] 对于pi＝(xi,yi)，pj＝(xj,yj)，在一个实施例中，所述预设关系f为：

[0108] ABS(dxi-dxj+dyi-dyj)

[0109] 其中，xi为第i个匹配对中所述第一图像的第i个匹配点，yi为第i个匹配对中所述第二图像的第i个匹配点，xj为第j个匹配对中所述第一图像的第j个匹配点，yj为第j个匹配对中所述第二图像的第j个匹配点，dxi为xi的主方向，dxj为xj的主方向，dyi为yi的主方向，dyj为yj的主方向，ABS为绝对值函数，gdxixj为xi与xj连线与dxi的夹角，gdyiyj为yi与yj连线与dyi的夹角，t1和t2是两个大于0的阈值，比如台标检测中两个值均为10。

[0110] 第一判断单元234，被配置为在所述第i个匹配对和所述第j个匹配对之间的空间信息满足预设关系时，将所述初始矩阵中第i行和第j列的矩阵元赋值为第一数值。

[0111] 如果pi和pj满足关系f，则将初始矩阵中第i行和第j列的矩阵元赋值为第一数值。第一数值可以根据实际需要进行设置，例如，第一数值为1。

[0112] 考虑到对称矩阵的特殊性，为了快速构建目标矩阵，在一个实施例中，第一判断单元234被配置为将所述初始矩阵中第i行和第j列的矩阵元以及第j行和第i列的矩阵元赋值为第一数值。

[0113] 第二判断单元235，被配置为在所述第i个匹配对和所述第j个匹配对之间的空间信息不满足预设关系时，将所述初始矩阵中第i行和第j列的矩阵元赋值为第二数值，其中，所述第二数值与所述第一数值不相同。

[0114] 如果pi和pj不满足关系f，则将初始矩阵中第i行和第j列的矩阵元赋值为第二数值。第二数值可以根据实际需要进行设置，例如，第二数值为0。

[0115] 考虑到对称矩阵的特殊性，为了快速构建目标矩阵，在一个实施例中，所述第二判断单元235被配置为将所述初始矩阵中第i行和第j列的矩阵元以及第j行和第i列的矩阵元赋值为第二数值。

[0116] 进入所述匹配对选取单元232执行从所述初始匹配对集合中选取第i个匹配对和第j个匹配对的功能，直至所述初始矩阵中每一个矩阵元均被赋值，得到目标矩阵。

[0117] 对初始矩阵中对应的矩阵元赋值以后，从初始匹配对集合P中再选取不同的两个匹配对，重新判断两个匹配对之间的空间信息是否满足关系f，根据判断的结果对初始矩阵中对应的矩阵元赋值，依次重复，直至初始矩阵中每一个元素均被赋值，得到目标矩阵。由于对称矩阵的对称性，构建kuaishou-matrix总共需要计算N*(N-1)/2次关系。

[0118] 关于上述实施例中的装置，其中各个模块执行操作的具体方式已经在有关该方法的实施例中进行了详细描述，此处将不做详细阐述说明。

[0119] 本公开实施例还提供一种电子设备，包括：

[0120] 处理器；

[0121] 用于存储处理器可执行指令的存储器；

[0122] 其中，所述处理器被配置为：当所述一个或多个程序被所述一个或多个处理器执行，使得所述一个或多个处理器实现上述任意一项所述的关键点匹配方法。

[0123] 图3是根据一示例性实施例示出的一种用于关键点匹配的装置300的框图。例如，装置300可以被提供为一电子设备。参照图3，装置300包括处理组件322，其进一步包括一个或多个处理器，以及由存储器332所代表的存储器资源，用于存储可由处理组件322的执行的指令，例如应用程序。存储器332中存储的应用程序可以包括一个或一个以上的每一个对应于一组指令的模块。此外，处理组件322被配置为执行指令，以执行上述任意一项所述的关键点匹配方法。

[0124] 装置300还可以包括一个电源组件326被配置为执行装置300的电源管理，一个有线或无线网络接口350被配置为将装置300连接到网络，和一个输入输出(I/O)接口358。装置300可以操作基于存储在存储器332的操作系统，例如Windows ServerTM，Mac OS XTM，UnixTM,LinuxTM，FreeBSDTM或类似。

[0125] 本公开实施例还提供一种非临时性计算机可读存储介质，当所述存储介质中的指令由移动终端的处理器执行时，使得移动终端能够执行上述任意一项所述的关键点匹配方法。其中，所述存储介质包括但不限于任何类型的盘(包括软盘、硬盘、光盘、CD-ROM、和磁光盘)、ROM(Read-Only Memory，只读存储器)、RAM(Random AcceSS Memory，随即存储器)、EPROM(EraSable Programmable Read-Only Memory，可擦写可编程只读存储器)、EEPROM(Electrically EraSable Programmable Read-Only Memory，电可擦可编程只读存储器)、闪存、磁性卡片或光线卡片。也就是，存储介质包括由设备(例如，计算机)以能够读的形式存储或传输信息的任何介质。可以是只读存储器，磁盘或光盘等。

[0126] 本公开实施例还提供一种计算机程序产品，当所述计算机程序产品中的指令由移动终端的处理器执行时，使得移动终端能够执行上述任意一项所述的关键点匹配方法。

[0127] 本领域技术人员在考虑说明书及实践这里公开的发明后，将容易想到本发明的其它实施方案。本申请旨在涵盖本发明的任何变型、用途或者适应性变化，这些变型、用途或者适应性变化遵循本发明的一般性原理并包括本公开未公开的本技术领域中的公知常识或惯用技术手段。说明书和实施例仅被视为示例性的，本发明的真正范围和精神由下面的权利要求指出。

[0128] 应当理解的是，本发明并不局限于上面已经描述并在附图中示出的精确结构，并且可以在不脱离其范围进行各种修改和改变。本发明的范围仅由所附的权利要求来限制。