基于非几何约束的图像局部特征匹配方法、装置及终端

摘要

一种基于非几何约束的图像局部特征匹配方法、装置及终端，所述方法包括：对目标图像和待匹配图像分别进行局部特征检测，以得到各自的局部特征点；对目标图像和待匹配图像各自的局部特征点进行局部特征匹配，以得到多个第一候选匹配特征点和多个第二候选匹配特征点，其中每一第一候选匹配点与相应的第二候选匹配特征点匹配，第一候选匹配特征点位于目标图像，第二候选匹配特征点位于待匹配图像；对多个第一候选匹配特征点和多个第二候选匹配特征点进行近邻约束检测，将符合近邻约束的所述第一候选匹配特征点以及与其匹配的第二候选匹配特征点加入匹配特征点集合。本发明技术方案有效实现了各类型图像中的错配消除。

说明书

技术领域

本发明涉及图像处理领域，尤其涉及一种基于非几何约束的图像局部特征匹配方法、装置及终端。

背景技术

在计算机视觉领域，图像局部特征(local features)是指图像局部领域的特征；局部通常是指能够稳定出现并且具有良好的可区分性像素点区域。局部特征匹配方法已经广泛应用于计算机视觉领域的诸多问题，成为了图像检索、目标检测与识别等应用领域的必要手段。

现有技术中，局部特征匹配分为两个阶段：特征向量匹配和错配消除。特征向量匹配是指通过描述子计算特征点的特征向量，然后根据特征向量之间的相似性，找出相匹配的特征点的过程。局部特征的描述子一般只使用局部图像块内的像素，所包含信息有限，易受图像畸变、噪声等因素的影响。因此基于特征向量相似性的局部特征误匹配率较高，匹配结果往往不能直接被高层算法所利用。

现有技术中，为了得到稳定可靠的匹配结果，一般在描述子匹配结果上引入几何约束来消除错配。错配消除方法将不满足几何约束条件的匹配点作为错配消除，仅保留满足约束条件的匹配点。几何约束是指对匹配点坐标的变换关系的约束。在双目、多目视觉图像中，图像之间相对关系已知，一般通过极线几何约束消除特征点的错配。在目标检测、识别与跟踪等高层视频图像内容分析任务中，通常不对摄像机进行标定；两幅图像中同一目标上的对应点符合某种仿射变换关系。这种仿射变换关系可以通过随机样本一致(RANdom Sample Consensus,RANSAC)方法求取；通过检验一对匹配点是否满足所求得的仿射变换关系，可判定其是否为错配。上述几何约束方法在刚体目标的检测、跟踪与识别等领域中误匹配率较低，得到了广泛的应用。

但是，在实际应用中，图像中的目标通常是行人、人脸、动植物等非刚体。由于非刚体目标可以发生形变，此时无法确定非刚体目标在两幅图像之间的仿射变换关系，难以通过几何约束消除错配，从而导致目标检测的准确率低。此外，当两幅图像之间不是简单的仿射变换关系时，比如图像中包括重复目标以及多个刚体目标时，通过RANSAC算法也无法消除错配，降低了目标检测率。

发明内容

本发明解决的技术问题是如何有效实现各类型图像中的错配消除。

为解决上述技术问题，本发明实施例提供一种基于非几何约束的图像局部特征匹配方法，基于非几何约束的图像局部特征匹配方法包括：

对目标图像和待匹配图像分别进行局部特征检测，以得到各自的局部特征点；对所述目标图像和所述待匹配图像各自的局部特征点进行局部特征匹配，以得到多个第一候选匹配特征点和多个第二候选匹配特征点，其中每一第一候选匹配点与相应的第二候选匹配特征点匹配，所述第一候选匹配特征点位于所述目标图像，所述第二候选匹配特征点位于所述待匹配图像；对所述多个第一候选匹配特征点和所述多个第二候选匹配特征点进行近邻约束检测，将符合近邻约束的所述第一候选匹配特征点以及与其匹配的第二候选匹配特征点加入匹配特征点集合；其中，如果所述多个第一候选匹配特征点中存在至少两个特征点互为近邻点，且互为近邻点的至少两个第一候选匹配特征点各自匹配的第二候选匹配特征点也互为近邻点，则确定所述至少两个第一候选匹配特征点和各自匹配的所述第二候选匹配特征点符合近邻约束。

可选的，通过非参数密度估计的方式进行近邻约束检测。

可选的，所述非参数密度估计的方式包括：通过Parzen窗进行密度估计。

可选的，所述近邻点指的是：如果两个特征点之间的距离小于设定阈值，则所述两个特征点互为近邻点。

可选的，所述对所述多个第一候选匹配特征点和所述多个第二候选匹配特征点进行近邻约束检测，将符合近邻约束的所述第一候选匹配特征点以及与其匹配的第二候选匹配特征点加入匹配特征点集合包括：

形成四维向量集合，所述四维向量集合包括多个四维向量，每一四维向量由所述第一候选匹配特征点的二维坐标和匹配的第二候选匹配特征点的二维坐标组合形成；通过Parzen窗估计所述四维向量集合的密度；如果所述四维向量集合在Parzen窗内的密度大于设定值，表示所述四维向量集合在Parzen窗内存在至少两个第一候选匹配特征点及其匹配的第二候选匹配特征点符合近邻约束，则将所述至少两个所述第一候选匹配特征点以及与其匹配的第二候选匹配特征点加入匹配特征点集合。

可选的，所述设定值为16K/δ⁴；其中，K为在Parzen窗内所述四维向量的数量，K为大于等于2的正整数，δ/2为Parzen窗的宽度。

可选的，Parzen窗的宽度根据所述目标图像中目标大小和候选匹配特征点的数量进行确定。

为解决上述技术问题，本发明实施例还公开了一种基于非几何约束的图像局部特征匹配装置，基于非几何约束的图像局部特征匹配装置包括：

局部特征检测单元，适于对目标图像和待匹配图像分别进行局部特征检测，以得到各自的局部特征点；局部特征匹配单元，适于对所述目标图像和所述待匹配图像各自的局部特征点进行局部特征匹配，以得到多个第一候选匹配特征点和多个第二候选匹配特征点，其中每一第一候选匹配点与相应的第二候选匹配特征点匹配，所述第一候选匹配特征点位于所述目标图像，所述第二候选匹配特征点位于所述待匹配图像；近邻约束检测单元，适于对所述多个第一候选匹配特征点和所述多个第二候选匹配特征点进行近邻约束检测，将符合近邻约束的所述第一候选匹配特征点以及与其匹配的第二候选匹配特征点加入匹配特征点集合；

其中，如果所述多个第一候选匹配特征点中存在至少两个特征点互为近邻点，且互为近邻点的至少两个第一候选匹配特征点各自匹配的第二候选匹配特征点也互为近邻点，则所述近邻约束检测单元确定所述至少两个第一候选匹配特征点和各自匹配的所述第二候选匹配特征点符合近邻约束。

可选的，通过非参数密度估计的方式进行近邻约束检测。

可选的，所述非参数密度估计的方式包括：通过Parzen窗进行密度估计。

可选的，所述近邻点指的是：如果两个特征点之间的距离小于设定阈值，则所述两个特征点互为近邻点。

可选的，所述近邻约束检测单元包括：形成子单元，适于形成四维向量集合，所述四维向量集合包括多个四维向量，每一四维向量由所述第一候选匹配特征点的二维坐标和匹配的第二候选匹配特征点的二维坐标组合形成；密度估计子单元，适于通过Parzen窗估计所述四维向量集合的密度；匹配特征点确定子单元，适于在所述四维向量集合在Parzen窗内的密度大于设定值，表示所述四维向量集合在Parzen窗内存在至少两个第一候选匹配特征点及其匹配的第二候选匹配特征点符合近邻约束时，将所述至少两个所述第一候选匹配特征点以及与其匹配的第二候选匹配特征点加入匹配特征点集合。

可选的，所述设定值为16K/δ⁴；其中，K为在Parzen窗内所述四维向量的数量，K为大于等于2的正整数，δ/2为Parzen窗的宽度。

可选的，Parzen窗的宽度根据所述目标图像中目标大小和候选匹配特征点的数量进行确定。

为解决上述技术问题，本发明实施例还公开了一种终端，所述终端包括所述图像局部特征匹配装置。

与现有技术相比，本发明实施例的技术方案具有以下有益效果：

本发明实施例通过对目标图像和待匹配图像分别进行局部特征检测，以得到各自的局部特征点；对所述目标图像和所述待匹配图像各自的局部特征点进行局部特征匹配，以得到多个第一候选匹配特征点和多个第二候选匹配特征点，其中每一第一候选匹配点与相应的第二候选匹配特征点匹配，所述第一候选匹配特征点位于所述目标图像，所述第二候选匹配特征点位于所述待匹配图像；对所述多个第一候选匹配特征点和所述多个第二候选匹配特征点进行近邻约束检测，将符合近邻约束的所述第一候选匹配特征点以及与其匹配的第二候选匹配特征点加入匹配特征点集合；其中，如果所述多个第一候选匹配特征点中存在至少两个特征点互为近邻点，且互为近邻点的至少两个第一候选匹配特征点各自匹配的第二候选匹配特征点也互为近邻点，则确定所述至少两个第一候选匹配特征点和各自匹配的所述第二候选匹配特征点符合近邻约束。通过使用近邻约束在候选匹配特征点中确定匹配特征点，避免使用目标图像和待匹配图像相对关系和仿射变换关系，实现易发生形变的非刚体目标的局部特征匹配和错配消除；同时，对于刚体目标的错配消除的误配率降低；以及在复杂场景中，在目标图像和待匹配图像中包括多个目标时，实现了错配消除，提高了图像目标检测的准确性。

进一步，通过非参数密度估计的方式进行近邻约束检测，提高了错配消除的计算速度，从而提高了图像目标检测的效率。

附图说明

图1是现有技术中一种几何约束关系的示意图；

图2是本发明实施例一种基于非几何约束的图像局部特征匹配方法的流程图；

图3是本发明实施例一种近邻约束关系的示意图；

图4是本发明实施例另一种近邻约束关系的示意图；

图5是本发明实施例一种匹配关系的示意图；

图6是本发明实施例一种近邻约束检测方法的流程图；

图7是本发明实施例一种重复目标匹配效果示意图；

图8是本发明实施例一种多目标匹配效果示意图；

图9是本发明实施例一种非刚体目标匹配效果示意图；

图10是本发明实施例一种基于非几何约束的图像局部特征匹配装置的结构示意图；

图11是图10所示近邻约束检测单元的结构示意图。

具体实施方式

如背景技术中所述，在实际应用中，图像中的目标通常是行人、人脸、动植物等非刚体。由于非刚体目标可以发生形变，此时难以确定非刚体目标在两幅图像之间的仿射变换关系，不能通过几何约束消除错配，从而导致目标检测率低。此外，当两幅图像之间不是简单的仿射变换关系时，比如图像中包括重复目标以及多个刚体目标时，通过RANSAC算法也无法消除错配，降低了目标检测率。

申请人对现有技术的分析如下，现有技术在提取目标图像和待匹配图像上特征点的特征向量后，根据特征向量之间的相似性，给出匹配点集合M＝{(p_i,p′_i)}，其中p_i为目标图像上的点，p′_i是待匹配图像上的点。通过几何约束条件，消除集合M中的错配，返回一组满足几何约束条件的匹配点M*，去除剩余不满足约束条件的匹配点。

上述过程中，几何约束条件是指一种正确匹配点所应满足的条件(正确匹配的必要条件)。图1是现有技术中几何约束关系的示意图。如图1所示，目标上的点p*分别对应目标图像上点p与待匹配图像上点p′，则(p,p′)为一对正确匹配点，并满足坐标变换关系：f(p；Λ)＝p′。。其中，Λ为线性变换矩阵。

线性变换矩阵Λ反映了特征点p和特征点p′之间坐标的几何变换关系。然而，上述公式并不是(p,p′)正确匹配的充要条件，一对错配特征点也有可能满足几何约束条件。

因此，基于几何约束的错配消除算法不能完全避免错配，检测效果一般可以通过实验进行评估。

同时，现有技术中基于几何约束的错配消除方法需要预先估计线性变换矩阵Λ。通常需要根据特征向量的匹配结果集合M估计线性变换矩阵Λ，因此现有技术的错配消除方法的稳定性会受匹配结果集合M中噪声的影响。此外，当目标为非刚体，或者待匹配图像中存在多个目标时，一个线性变换矩阵难以描述目标上所有特征点坐标的几何变换关系。

因此几何约束方法不能很好地解决非刚体目标以及复杂场景中的错配消除问题。

本发明实施例则在错配消除方法中使用属于正确匹配关系必要条件的约束关系，也就是近邻约束。通过使用近邻约束在候选匹配特征点中确定匹配特征点，实现了各类型图像中的错配消除，提高了图像目标检测的准确性。

为使本发明的上述目的、特征和优点能够更为明显易懂，下面结合附图对本发明的具体实施例做详细的说明。

本发明实施例中所称目标图像和待匹配图像可以表示包括目标的图像，目标的数量可以是一个，也可以是多个。当目标的数量为多个时，目标可以相同也可以不同。其中，目标的类型可以包括刚体目标和非刚体目标。

本发明实施中，局部特征匹配可以是通过局部特征确定目标图像与待匹配图像的多对匹配特征点的过程。在确定匹配特征点后，则可以基于匹配特征点确定待匹配图像中的目标。也就是说，基于局部特征匹配的目标检测可以是指根据目标的目标图像，在待匹配图像中定位目标。

图2是本发明实施例一种基于非几何约束的图像局部特征匹配方法的流程图。

如图2所示，基于非几何约束的图像局部特征匹配方法可以包括以下步骤：

步骤S201，对目标图像和待匹配图像分别进行局部特征检测；

步骤S202，对所述目标图像和所述待匹配图像各自的局部特征点进行局部特征匹配；

步骤S203，对所述多个第一候选匹配特征点和所述多个第二候选匹配特征点进行近邻约束检测，将符合近邻约束的所述第一候选匹配特征点以及与其匹配的第二候选匹配特征点加入匹配特征点集合；

其中，如果所述多个第一候选匹配特征点中存在至少两个特征点互为近邻点，且互为近邻点的至少两个第一候选匹配特征点各自匹配的第二候选匹配特征点也互为近邻点，则确定所述至少两个第一候选匹配特征点和各自匹配的所述第二候选匹配特征点符合近邻约束。

下面结合图2和具体实施例对上述步骤S201至步骤S203对做详细的说明。

具体实施中，在步骤S201中得到目标图像和待匹配图像各自的局部特征点。具体而言，在步骤S201中得到局部特征点的位置，也就是局部特征点在目标图像或待匹配图像的像素矩阵中的坐标。

具体而言，局部特征点可以由检测子和描述子确定。具体地，检测子可以根据视觉原理的不变性，找到图像中特殊的点和区域。例如可以是利用尺度不变性或者稳定区域进行检测。其中，检测子可以包括：尺度不变特征变换(Scale-Invariant Feature Transform,SIFT)检测子，最大稳定极值区域(MSER-Maximally Stable Extremal Regions,MSER)检测子等。在找到特殊点和区域后，通过描述子利用局部特征的邻域内的梯度和纹理信息，对点进行描述，确定局部特征点的位置。其中，描述子可以包括：SIFT描述子，二值化鲁棒独立基本特征(Binary Robust Independent Elementary Features,BRIEF)描述子等。

可以理解的是，对于描述子和监测子，可以采用任意可实施的方式，本发明实施例对此不做限制。

具体实施中，在步骤S202中得到多个第一候选匹配特征点和多个第二候选匹配特征点，其中每一第一候选匹配点与相应的第二候选匹配特征点匹配，所述第一候选匹配特征点位于所述目标图像，所述第二候选匹配特征点位于所述待匹配图像。

具体而言，可以是通过描述子计算目标图像和待匹配图像中特征点的特征向量，然后根据特征向量之间的相似性，确定相匹配的多个第一候选匹配特征点和多个第二候选匹配特征点。

具体实施中，在步骤S203中，如果至少两个特征点互为近邻点，表示至少两个特征点具有近邻关系。更具体而言，近邻关系可以是图像上的两个点之间的距离小于设定阈值的关系。也就是说，如果两个特征点之间的距离小于设定阈值，则所述两个特征点互为近邻点。其中，所述距离可以是两个特征点之间的欧氏距离。

具体地，所述设定阈值可以是距离值，设定阈值的大小可以根据所述目标图像中目标大小和候选匹配特征点的数量进行确定。

需要说明的是，设定阈值的大小还可以根据实际的应用环境进行适应性的调整，本发明实施例对此不做限制。

可以理解的是，上述距离也可以是马氏距离等任意可实施的距离，本发明实施例对此不做限制。

本发明实施例所述基于非几何约束的图像局部特征匹配方法可以应用于多种应用场景。上述应用场景可以包括待匹配图像中包括多个不同目标；待匹配图像中包括多个相同目标；以及待匹配图像中包括非刚体目标。也就是说，所述基于非几何约束的图像局部特征匹配方法可以实现对多个不同目标、多个相同目标以及非刚体目标的检测。

需要说明的是，本发明实施例所称非刚体目标可以是指发生形变的目标。

本发明实施例通过使用近邻约束在候选匹配特征点中确定匹配特征点，避免使用目标图像和待匹配图像相对关系和仿射变换关系，实现易发生形变的非刚体目标的局部特征匹配和错配消除；同时，对于刚体目标的错配消除的误配率降低；以及在复杂场景中，在目标图像和待匹配图像中包括多个目标时，实现了错配消除，提高了图像目标检测的准确性。

图3是本发明实施例一种近邻约束关系的示意图。

下面结合图3对近邻约束关系做详细的阐述。

假设p₁和p₂是目标上的两个点，若满足||p₁-p₂||＜δ，其中，||p₁-p₂||表示点p₁和点p₂之间的距离；δ为设定阈值；则认为点p₁和点p₂具有近邻关系，也就是，点p₁和点p₂互为近邻点，记为<p₁,p₂>_δ。其中，对于点集合P＝{p_i},i＝1,2,…,N，集合中任意两点p_i和p_j具有近邻关系||p_i-p_j||＜δ，则称这些点两两近邻，记为<p₁,p₂,…,p_N〉_δ。

如图3所示，假设特征点p^*和特征点q^*是刚体目标上两点，分别对应目标图像中的第一候选匹配特征点p和q和待匹配图像中的第二候选匹配特征点p’和q’。则(p,p’)和(q,q’)是两对匹配特征点。若特征点p^*和特征点q^*是目标上的近邻点，那么第一候选匹配特征点p和q是目标图像上的近邻点，第二候选匹配特征点p’和q’也是待匹配图像上的近邻点。选取适当的设定阈值δ，可得到如下条件：||p-q||＜δ，||p’-q’||＜δ；||p-q||＜δ表示第一候选匹配特征点p和q的距离小于设定阈值δ，以及第二候选匹配特征点p’和q’的距离小于设定阈值δ。

也就是说，若特征点p^*和特征点q^*在目标上互为近邻点，那么它们所对应的两对匹配特征点(p,p’)和(q,q’)满足如下条件：<p’,q’>_δ。该条件即为近邻约束。该近邻约束条件是目标上一对近邻点所对应的两对匹配特征点应满足的条件(必要条件)。若不满足该条件，则候选匹配特征点(p,p’)和(q,q’)不是正确匹配点，或者特征点p^*和特征点q^*在目标并不是互为近邻点。

通过上述近邻约束约束可消除匹配结果中的错配点和目标上孤立的点所对应的候选匹配特征点。

具体地，设定阈值δ可以取决于特征点p^*和特征点q^*两点间距离、目标图像和待匹配图像之间的尺度变化和视角变化等。

图4是本发明实施例另一种近邻约束关系的示意图。

以目标某一局部区域为例，对区域内任意一特征点A，在其半径为δ的邻域内的所有特征点与特征点A互为近邻点。如图4(a)所示，特征点B和特征点C与特征点A互为近邻点。

若目标为刚体，不发生形变，则特征点与特征点之间的近邻关系始终不变。

若目标为非刚体，当非刚体目标发生形变时，如果特征点A所在区域不受形变影响，那么特征点A与其近邻点之间的近邻关系保持不变；如果特征点A所在区域受目标形变影响，那么特征点A与部分近邻点之间的近邻关系保持不变。

本实施例以特征点B和特征点C为例对目标发生形变的情况做详细说明。如图4(b)所示，当该区域被拉伸时，特征点B变为特征点B′，特征点C变为特征点C′。其中，部分特征点之间的近邻关系被改变，例如特征点A和特征点C。但仍有部分特征点保留在特征点A的邻域内，并与特征点A互为近邻点，例如特征点A和特征点B。

需要说明的是，只有在非刚体目标解体成质点后完全重新排列，才可以破坏所有与特征点A互为近邻点的特征点与特征点A之间的所有近邻关系。由此，非刚体目标形变时只破坏部分特征点与特征点A之间的近邻关系，故存在与特征点A一直互为近邻点的特征点。

由于两个点的近邻约束比较弱，不能有效地消除错配。可以采用K个特征点的近邻关系作为近邻约束条件，此处K大于2。若表示目标上的特征点集合，｛p₁,p₂,…,p_k}表示目标图像上的第一候选匹配特征点集合，{p′₁,p′₂,…,p′_k}表示待匹配图像上的第二候选匹配特征点集合。特征点集合两两互为近邻点，那么其所对应的匹配特征点P＝{(p₁,p′₁),(p₂,p′₂),…,(p_k,p′_k)}满足近邻约束：<p₁,p₂,…,p_k>_δ和<p′₁,p′₂,…,p′_k>_δ。

也就是说，如果所述多个第一候选匹配特征点中存在至少两个特征点互为近邻点，且互为近邻点的至少两个第一候选匹配特征点各自匹配的第二候选匹配特征点也互为近邻点，则确定所述至少两个第一候选匹配特征点和各自匹配的所述第二候选匹配特征点符合近邻约束。

图5是本发明实施例一种匹配关系的示意图。

如图5所示，坐标轴A和坐标轴B为一维坐标轴，分别表示目标图像和待匹配图像；在坐标轴A和坐标轴B上的空心三角形表示一维坐标轴上的特征点。例如特征点p表示第一候选匹配特征点，特征点q表示第二候选匹配特征点。虚斜线表示坐标轴A和坐标轴B的一对候选匹配特征点相匹配，例如虚线1表示第一候选匹配特征点p与第二候选匹配特征点q相匹配。也就是说，虚斜线可以表示一种匹配关系，该匹配关系可以表示为二维空间上的点。例如，图5中黑色三角形m表示第一候选匹配特征点p和第二候选匹配特征点q的匹配关系。

具体实施中，在确定第一候选匹配特征点和第二候选匹配特征点的匹配关系后，对其进行近邻约束检测。

具体地，采用K个特征点的近邻关系作为近邻约束条件时，此处K大于2；需要遍历候选匹配特征点集合中所有满足近邻约束条件的K对匹配特征点构成的集合。若候选匹配特征点集合中候选匹配特征点的数量为m，则需要检查个不等式，计算复杂度比较高。

本实施例中，可以将检测满足近邻约束的匹配点集合通过密度估计的方式实现。具体地，可以通过非参数密度估计的方式进行近邻约束检测。更具体而言，非参数密度估计的方式可以包括：通过Parzen窗进行密度估计(Parzen window density estimation)。

可以理解的是，还可以采用其他任意可实施的密度估计算法实现近邻约束检测，本发明实施例对此不做限制。

图6是本发明实施例一种近邻约束检测方法的流程图。

如图6所示，近邻约束检测方法可以包括以下步骤：

步骤S601，形成四维向量集合；

步骤S602，通过Parzen窗估计所述四维向量集合的密度；

步骤S603，如果所述四维向量集合在Parzen窗内的密度大于设定值，表示所述四维向量集合在Parzen窗内存在至少两个第一候选匹配特征点及其匹配的第二候选匹配特征点符合近邻约束，则将所述至少两个所述第一候选匹配特征点以及与其匹配的第二候选匹配特征点加入匹配特征点集合。

其中，在步骤S601中，所述四维向量集合可以包括多个四维向量，每一四维向量由所述第一候选匹配特征点的二维坐标和匹配的第二候选匹配特征点的二维坐标组合形成。具体地，第一候选匹配特征点和第二候选匹配特征点可以是目标图像和待匹配图像中的像素点，故二维坐标可以是第一候选匹配特征点或第二候选匹配特征点对应的像素点在像素矩阵中的坐标。

具体实施中，在步骤S603中，所述设定值可以为16K/δ⁴；其中，K为在Parzen窗内所述四维向量的数量，K为大于等于2的正整数，δ/2为Parzen窗的宽度。优选的，K可以为3或5。

进一步而言，Parzen窗的宽度可以根据所述目标图像中目标大小和候选匹配特征点的数量进行确定。具体地，目标图像中目标越大，Parzen窗的宽度越宽；候选匹配特征点的数量越多，Parzen窗的宽度越窄。优选的，δ可以为目标大小的三分之一。

具体实施中，对采用密度估计的进行近邻约束的过程做详细的说明。可以将在目标图像和待匹配图像上的候选匹配特征点的近邻约束检测转化为四维空间上的近邻约束检测。例如，对于一对候选匹配特征点(p_i,p′_i)，其二维坐标分别为p_i＝(x_i,y_i)与p′_i＝(x′_i,y′_i)，将候选匹配特征点(p_i,p′_i)的二维坐标表示为一个四维向量P_i＝(x_i,y_i,x′_i,y′_i)^T。那么，候选匹配特征点集合可以表示为四维向量集合。

如果另一对匹配点(p_j,p′_j)的四维向量P_j＝(x_j,y_j,x′_j,y′_j)^T满足：||P_i-P_j||＜δ。那么，

$\left(\begin{array}{c}\left|\right|P_i-P_j\left|\right|=\sqrt{{(x_i-x_j)}^2+{(y_i-y_j)}^2+{(x_i^{\prime }-x_j^{\prime })}^2+{(y_i^{\prime }-y_j^{\prime })}^2};\\ \left|\right|p_i-p_j\left|\right|=\sqrt{{(x_i-x_j)}^2+{(y_i-y_j)}^2};\\ \left|\right|p_i^{\prime }-p_j^{\prime }\left|\right|=\sqrt{{(x_i^{\prime }-x_j^{\prime })}^2+{(y_i^{\prime }-y_j^{\prime })}^2};\end{array}\right)$

也就是，在||P_i-P_j||＜δ的情况下，||p_i-p_j||＜δ且||p′_i-p′_j||＜δ。

由上，如果一组候选匹配特征点的四维向量两两之间的距离小于δ，则该四维向量对应的两个第一候选匹配特征点和两个第二候选匹配特征点分别满足近邻约束，也就是说，两个第一候选匹配特征点和两个第二候选匹配特征点分别互为近邻点。在这种情况下，两对第一候选匹配特征点和第二候选匹配特征点可以加入匹配特征点集合。

具体实施中，对通过Parzen窗进行密度估计的具体过程做详细的说明。

采用窗宽为δ/2的超立方体窗口Parzen窗估计点四维向量集合的密度。其中，在Parzen窗内的任意两个四维向量之间的最大距离为也就是说，Parzen窗内任意两个四维向量满足距离阈值为δ的近邻约束。若Parzen窗内的密度大于K/(δ/2)⁴＝16K/δ⁴，则表示窗内有至少K个四维向量，即在四维空间上找到了至少K对互为近邻点的候选匹配特征点。那么，该K对互为近邻点的候选匹配特征点为匹配特征点。在错配消除时应保留满足上述Parzen窗内的候选匹配特征点。

继续参照图5和图6，采用密度估计的进行近邻约束的过程中，由于四维空间难以可视化，故在图5中用一维坐标点的匹配关系来说明基于Parzen窗密度估计方法确定匹配特征点的过程。

当采用Parzen窗密度估计方法确定包括K对互为近邻点的候选匹配特征点的区域时，如图5中虚线矩形N所示。虚线矩形N内3对候选匹配特征点对应的一维特征点两两距离小于设定值，该3对候选匹配特征点可以加入匹配特征点集合。也即确定了满足近邻约束的匹配特征点集合。根据Parzen窗确定所有满足近邻约束的候选匹配特征点并加入匹配特征点集合，则错配消除过程也完成。

本发明实施例通过将确定特征匹配点的过程转化为密度估计，使得基于近邻约束的错配消除在算法上更容易实现。同时，由于近邻约束不反映特征点之间的坐标的几何匹配关系，因此近邻约束可以是一种非几何约束。

本发明实施例通过非参数密度估计的方式进行近邻约束检测，提高了错配消除的计算速度，从而提高了图像目标检测的效率。

本发明一实施例中，在使用Parzen窗进行密度估计确定匹配特征点时，首先确定Parzen窗的参数δ和K；输入是目标图像、待匹配图像、参数δ和K；输出则是匹配特征点集合M^*。实施方法的过程可以如下所述。

在目标图像和待匹配图像上进行局部特征检测，并计算局部特征点的描述子；进行局部特征点匹配，得到候选匹配特征点集合M＝{(p₁,p′₁),(p₂,p′₂),…,(p_N,p′_N)}，并计算该集合的四维向量集合M₄；遍历向量集合M₄内所有的四维向量P_i∈M₄：以P_i为中心，取窗宽为δ/2的Parzen窗口，若窗口内包括多于K个点(此处，每个点对应一个四维向量)，则将窗口内所有四维向量所对应的候选匹配特征点加入匹配特征点集合M^*；输出匹配特征点集合M^*。

具体地，如果四维向量集合M₄中四维向量的数量为m，以其中一点为中心对窗口内的候选匹配特征点进行计算需要检查(m-1)个不等式。遍历四维向量集合M₄中所有点需要计算m×(m-1)个不等式，远少于直接使用近邻点检测时的计算量

由此，本发明实施例的基于非几何约束的图像局部特征匹配方法提高了错配消除的计算速度，提高了图像目标检测的效率；从而使得本发明实施例的基于非几何约束的图像局部特征匹配方法可以应用于大数量级的图像匹配场景中。

对于刚体目标的局部特征匹配中的错配消除，得到匹配特征点集合。具体地，匹配特征点集合可以用特征点列表来表示。

本实施例中，通过实验得到本发明实施例的局部特征匹配方法和现有技术中RANSAC方法的匹配速度对比表，具体请参见表1。

表1

如表1所示，候选匹配特征点数量为88时，RANSAC方法匹配完成消耗时间0.43s，本发明实施例方法匹配完成消耗时间0.04s；候选匹配特征点数量为305时，RANSAC方法匹配完成消耗时间0.54s，本发明实施例方法匹配完成消耗时间0.14s；依此类推，候选匹配特征点数量为1011时，RANSAC方法匹配完成消耗时间1.41s，本发明实施例方法匹配完成消耗时间0.74s。

由表1可知，相对于现有技术，本发明实施例在刚体目标的局部特征匹配中，检测速度提高。

图7是本发明实施例一种重复目标匹配效果示意图。图8是本发明实施例一种多目标匹配效果示意图。

对于多目标/重复目标的局部特征匹配，得到匹配特征点集合。具体地，匹配特征点集合可以用特征点列表来表示。在具体实施中，还可以采用K均值(k mean)聚类算法，将匹配特征点进行聚类，每一类表示在待匹配图像上的一个目标物体。

需要理解的是，对于聚类采用的算法可以是任意可实施的算法，本发明实施例对此不做限制。

如图7所示，在重复目标检测的应用场景中，在目标图像(a)中可以包括待检测的目标字母A，待匹配图像(b)中可以包括多个字母A。通过本发明实施例的局部特征匹配方法进行匹配后的结果如图7中虚线所示，对于待匹配图像(b)中的多个字母A，其特征点分别被准确的与目标图像(a)中的目标字母A的特征点相匹配。

如图8所示，在多目标检测的应用场景中，在目标图像(a)中可以包括待检测的目标字母A和字母B，待匹配图像(b)中可以包括字母A和字母B。通过本发明实施例的局部特征匹配方法进行匹配后的结果如图8中虚线所示，对于待匹配图像(b)中的字母A和字母B，其特征点分别被准确的与目标图像(a)中的目标字母A和字母B的特征点相匹配。

如上所述，本发明实施例的局部特征匹配方法，可以实现多目标以及重复目标的检测；同时，检测的准确度高。

图9是本发明实施例一种非刚体目标匹配效果示意图

对于非刚体目标的匹配，得到匹配特征点集合。具体地，匹配特征点集合可以用特征点列表来表示。

如图9所示，在非刚体目标检测的应用场景中，在目标图像(a)中可以包括待检测的目标字母A，待匹配图像(b)中可以包括形变后的字母A，也即字母A被分割成了两部分。通过本发明实施例的局部特征匹配方法进行匹配后的结果如图9中虚线所示，对于待匹配图像(b)中的形变后的字母A，两部分的特征点分别被准确的与目标图像(a)中的目标字母A的特征点相匹配。

如上所述，本发明实施例通过使用近邻约束在候选匹配特征点中确定匹配特征点，避免使用目标图像和待匹配图像相对关系和仿射变换关系，实现易发生形变的非刚体目标的局部特征匹配和错配消除，目标检测的准确度提高。

综合图7、图8和图9以及相应的说明，本发明实施例的基于非几何约束的图像局部特征匹配方法不仅可以应用于刚体目标的检测，加快检测速度；还可以应用于非刚体目标、重复目标以及多个不同目标的检测，且检测的准确度高。

图10是本发明实施例一种基于非几何约束的图像局部特征匹配装置的结构示意图。

如图10所示，基于非几何约束的图像局部特征匹配装置可以包括：局部特征检测单元1001、局部特征匹配单元1002和近邻约束检测单元1003。

其中，局部特征检测单元1001适于对目标图像和待匹配图像分别进行局部特征检测，以得到各自的局部特征点；

局部特征匹配单元1002适于对所述目标图像和所述待匹配图像各自的局部特征点进行局部特征匹配，以得到多个第一候选匹配特征点和多个第二候选匹配特征点，其中每一第一候选匹配点与相应的第二候选匹配特征点匹配，所述第一候选匹配特征点位于所述目标图像，所述第二候选匹配特征点位于所述待匹配图像；

近邻约束检测单元1003适于对所述多个第一候选匹配特征点和所述多个第二候选匹配特征点进行近邻约束检测，将符合近邻约束的所述第一候选匹配特征点以及与其匹配的第二候选匹配特征点加入匹配特征点集合；

其中，如果所述多个第一候选匹配特征点中存在至少两个特征点互为近邻点，且互为近邻点的至少两个第一候选匹配特征点各自匹配的第二候选匹配特征点也互为近邻点，则所述近邻约束检测单元1003确定所述至少两个第一候选匹配特征点和各自匹配的所述第二候选匹配特征点符合近邻约束。

具体实施中，近邻约束检测单元1003在确定第一候选匹配特征点和第二候选匹配特征点的匹配关系后，对其进行近邻约束检测。

具体实施中，近邻点指的是：如果两个特征点之间的距离小于设定阈值，则所述两个特征点互为近邻点。

具体实施中，如果至少两个特征点互为近邻点，表示至少两个特征点具有近邻关系。更具体而言，近邻关系可以是图像上的两个点之间的距离小于设定阈值的关系。也就是说，如果两个特征点之间的距离小于设定阈值，则所述两个特征点互为近邻点。其中，所述距离可以是两个特征点之间的欧氏距离。

具体地，所述设定阈值可以是距离值，设定阈值的大小可以根据所述目标图像中目标大小和候选匹配特征点的数量进行确定。

需要说明的是，设定阈值的大小还可以根据实际的应用环境进行适应性的调整，本发明实施例对此不做限制。

可以理解的是，上述距离也可以是马氏距离等任意可实施的距离，本发明实施例对此不做限制。

本发明实施例所述基于非几何约束的图像局部特征匹配方法可以应用于多种应用场景。上述应用场景可以包括待匹配图像中包括多个不同目标；待匹配图像中包括多个相同目标；以及待匹配图像中包括非刚体目标。也就是说，所述基于非几何约束的图像局部特征匹配方法可以实现对多个不同目标、多个相同目标以及非刚体目标的检测。

需要说明的是，本发明实施例所称非刚体目标可以是指发生形变的目标。

本发明实施例通过使用近邻约束在候选匹配特征点中确定匹配特征点，避免使用目标图像和待匹配图像相对关系和仿射变换关系，实现易发生形变的非刚体目标的局部特征匹配和错配消除；同时，对于刚体目标的错配消除的误配率降低；以及在复杂场景中，在目标图像和待匹配图像中包括多个目标时，实现了错配消除，提高了图像目标检测的准确性。

具体地，采用K个特征点的近邻关系作为近邻约束条件时，此处K大于2；需要遍历候选匹配特征点集合中所有满足近邻约束条件的K对匹配特征点构成的集合。若候选匹配特征点集合中候选匹配特征点的数量为m，则需要检查个不等式，计算复杂度比较高。

图11是图10所示近邻约束检测单元的结构示意图。

本实施例中，可以将检测满足近邻约束的匹配点集合通过密度估计的方式实现。具体地，可以通过非参数密度估计的方式进行近邻约束检测。更具体而言，非参数密度估计的方式可以包括：通过Parzen窗进行密度估计(Parzen window density estimation)。

如图11所示，近邻约束检测单元1003可以包括：形成子单元1101、密度估计子单元1102和匹配特征点确定子单元1103。

其中，形成子单元1101适于形成四维向量集合，所述四维向量集合包括多个四维向量，每一四维向量由所述第一候选匹配特征点的二维坐标和匹配的第二候选匹配特征点的二维坐标组合形成；

密度估计子单元1102适于通过Parzen窗估计所述四维向量集合的密度；

匹配特征点确定子单元1103适于在所述四维向量集合在Parzen窗内的密度大于设定值，表示所述四维向量集合在Parzen窗内存在至少两个第一候选匹配特征点及其匹配的第二候选匹配特征点符合近邻约束时，将所述至少两个所述第一候选匹配特征点以及与其匹配的第二候选匹配特征点加入匹配特征点集合。

具体地，形成子单元1101可以形成四维向量集合。例如，对于一对候选匹配特征点(p_i,p′_i)，其二维坐标分别为p_i＝(x_i,y_i)与p′_i＝(x′_i,y′_i)，将候选匹配特征点(p_i,p′_i)的二维坐标表示为一个四维向量P_i＝(x_i,y_i,x′_i,y′_i)^T。那么，候选匹配特征点集合可以表示为四维向量集合。

具体实施中，所述设定值为16K/δ⁴；其中，K为在Parzen窗内所述四维向量的数量，K为大于等于2的正整数，δ/2为Parzen窗的宽度。

具体实施中，Parzen窗的宽度可以根据所述目标图像中目标大小和候选匹配特征点的数量进行确定。具体地，目标图像中目标越大，Parzen窗的宽度越宽；候选匹配特征点的数量越多，Parzen窗的宽度越窄。优选的，δ可以为目标大小的三分之一。

本发明实施例通过非参数密度估计的方式进行近邻约束检测，提高了错配消除的计算速度，从而提高了图像目标检测的效率。

具体实施中，对通过Parzen窗进行密度估计的具体过程做详细的说明。

采用窗宽为δ/2的超立方体窗口Parzen窗估计点四维向量集合的密度。其中，在Parzen窗内的任意两个四维向量之间的最大距离为也就是说，Parzen窗内任意两个四维向量满足距离阈值为δ的近邻约束。若Parzen窗内的密度大于K/(δ/2)⁴＝16K/δ⁴，则表示窗内有至少K个四维向量，即在四维空间上找到了至少K对互为近邻点的候选匹配特征点。那么，该K对互为近邻点的候选匹配特征点为匹配特征点。在错配消除时应保留满足上述Parzen窗内的候选匹配特征点。

可以理解的是，还可以采用其他任意可实施的密度估计算法实现近邻约束检测，本发明实施例对此不做限制。

具体地，如果四维向量集合M₄中四维向量的数量为m，以其中一点为中心对窗口内的候选匹配特征点进行计算需要检查(m-1)个不等式。遍历四维向量集合M₄中所有点需要计算m×(m-1)个不等式，远少于直接使用近邻点检测时的计算量

由此，本发明实施例提高了错配消除的计算速度，从而提高了图像目标检测的效率；从而使得本发明实施例的基于非几何约束的图像局部特征匹配装置可以应用于大数量级的图像匹配场景中。

本发明实施例还公开了一种终端，所述终端可以包括上述基于非几何约束的图像局部特征匹配装置100。所述终端可以包括但不限于手机、笔记本、平板电脑等。

本领域普通技术人员可以理解上述实施例的各种方法中的全部或部分步骤是可以通过程序来指令相关的硬件来完成，该程序可以存储于以计算机可读存储介质中，存储介质可以包括：ROM、RAM、磁盘或光盘等。

虽然本发明披露如上，但本发明并非限定于此。任何本领域技术人员，在不脱离本发明的精神和范围内，均可作各种更动与修改，因此本发明的保护范围应当以权利要求所限定的范围为准。