CN113392913B - 基于边界特征点集的平面图形匹配度评价方法、装置及系统 - Google Patents

Abstract

本发明公开了一种基于边界特征点集的平面图形匹配度评价方法、装置及系统，所述方法包括采集待匹配的两个直边平面图形的边界特征点；基于所述边界特征点，以待匹配的两个直边平面图形最大程度重合为目标，计算获得平移、旋转直边平面图形后的图形变换参数，进而求得两个直边平面图形的不重合面积；根据所述不重合面积与两个直边平面图形平均面积的关系，确定图形匹配度值，完成平面图形匹配度评价。本发明基于具有平均效应的整体匹配原则，而不必考虑采集的边界特征点之间具体的对应情况，仅采用具有直线边界的平面图形的轮廓信息进行匹配，具有计算效率、健壮性和准确性高的优点，特别适合具有直边轮廓的钣金零件识别与分类、内空间平面测绘拼接等应用场合。

Description

基于边界特征点集的平面图形匹配度评价方法、装置及系统

技术领域

本发明属于计算机图象处理技术领域，具体涉及一种基于边界特征点集的平面图形匹配度评价方法、装置及系统。

背景技术

平面图形匹配及匹配度评价常用于图形拼接、比对、识别等，并可进一步用于自动测绘、机器视觉等领域的复杂应用开发。专利CN201610102703.4提供一种图像匹配方法和装置，通过图像的SIFT特征点和SIFT特征向量，计算待匹配截图和所述源图像的特征匹配点对，结合SIFT算法进行图像匹配。该方法需要对整个图像进行面域信息采集并进行特征点和特征向量运算，对例如内空间实时测量、快速轮廓识别等使用场合需要高性能数据处理硬件的支持。采用特征点进行匹配操作是避免处理大量图像数据的有效方法，但在某些非理想条件下仍然存在一些技术难点，例如：特征点采集无参考基准；用于匹配的图形并不完全相同；即使是同一个图形，特征点数据规模因采样频率的不同而不同。因此，寻找适用于计算机处理的成熟高效的方法十分有意义。

发明内容

针对上述问题，本发明提出一种基于边界特征点集的平面图形匹配度评价方法、装置及系统，基于具有平均效应的整体匹配原则，而不必考虑采集的边界特征点之间具体的对应情况，仅采用具有直线边界的平面图形的轮廓信息进行匹配，具有计算效率、健壮性和准确性高的优点，特别适合具有直边轮廓的钣金零件识别与分类、内空间平面测绘拼接等应用场合。

为了实现上述技术目的，达到上述技术效果，本发明通过以下技术方案实现：

第一方面，本发明提供了一种基于边界特征点集的平面图形匹配度评价方法，包括：

采集待匹配的两个直边平面图形的边界特征点；

基于所述边界特征点，以待匹配的两个直边平面图形最大程度重合为目标，计算获得平移、旋转直边平面图形后的图形变换参数，进而求得两个直边平面图形的不重合面积；

根据所述不重合面积与两个直边平面图形平均面积的关系，确定图形匹配度值，完成平面图形匹配度评价。

可选地，所述边界特征点的采集方法包括：

分别在待匹配的两个直边平面图形的平面内建立直角坐标系，提取待匹配的两个直边平面图形的边界特征点的位置坐标。

可选地，第一个直边平面图形的边界特征点的位置记为(x_1i,y_1i)，i从1到第一个直边平面图形的边界特征点总个数；第二个平面图形的边界特征点的位置记为(x_2i,y_2i)，i从1 到第二个直边平面图形的边界特征点总个数。

可选地，所述两个直边平面图形的不重合面积的计算方法包括：

识别出边界离散边界特征点集形成的直线边界，再分别确定相邻直线边界在直角坐标系中的交点，依次连接相邻交点形成直线边界段；将第一个平面图形的直线边界段首尾依次连接，按顺序记为l_1i，其中，i从1到第一个平面图形的直线边界段总个数；将第二个平面图形的直线边界段首尾依次连接，按顺序记为l_2i，其中，i从1到第二个平面图形的直线边界段总个数；

对所有的l_1i和l_2i进行等间距插值取点，插值取点的间距均为d，分别获得两个直边平面图形的等间距边界点(x_d1k,y_d1k)和(x_d2k,y_d2k)，k为等间距边界点的序号，分别取为1到两个平面图形的等间距边界点的总个数N_d1和N_d2；

分别计算出ΔX＝X₂-X₁，ΔY＝Y₂-Y₁；

将第二个直边平面图形整体平移(-ΔX，-ΔY)，记平移后的第二个直边平面图形的边界特征点(x’_2i,y’_2i)，直线边界段为l’_2i；

以(X₁，Y₁)为中心作0～360°等角度辐射线，相邻等角度辐射线的夹角记为θ，获得等角度辐射线与第一个平面图形的直线边界段l_1i的交点(x_θ1j，y_θ1j)，其中，j从1到第一个平面图形的直线边界段上的交点总个数N_θ1；同样，该组等角度辐射线与第二个直边平面图形的直线边界段l’_2i的交点记为(x_θ2j，y_θ2j)；其中，j从1到第二个平面图形的直线边界段上的交点总个数N_θ2；

按交点(x_θ1j，y_θ1j)在首尾依次连接的直线边界段l_1i上的顺序，按顺时针方向依次分别计算(x_θ1j，y_θ1j)与中心点(X₁，Y₁)之间的距离d_1j，按相同的方向和顺序，依次分别计算(x_θ2j，y_θ2j)与中心点(X₁，Y₁)之间的距离d_2j。对d_2j和d_1j进行互相关分析，获得互相关函数达到最高值时的时延参数Δ；按Δ×θ角度对平移后的第二个平面图形进行逆时针旋转，并记旋转后第二个平面图形的边界特征点(x”_2i,y”_2i)，直线边界段为l”_2i；

计算直线边界段l_1i和直线边界段l”_2i所围面积ΔS，即两个直边平面图形的不重合面积。

可选地，所述图形匹配度值通过下述公式计算：

其中，η为两个平面图形匹配度值，S₁为直线边界段l_1i所围面积，S₂为直线边界段l”_2i所围面积，ΔS为直线边界段l_1i和直线边界段l”_2i所围面积。

可选地，在计算出两个平面图形匹配度值η步骤之后还包括：

将第二个平面图形的边界特征点(x_2i,y_2i)替换为(x”_2i,y”_2i)，将d和θ分别取原值的一半；

重新采集待匹配的两个直边平面图形的边界特征点；

重新基于所述边界特征点，以待匹配的两个直边平面图形最大程度重合为目标，计算获得平移、旋转直边平面图形后的图形变换参数，进而求得两个直边平面图形的不重合面积；

直至两个平面图形匹配度η的变化小于期望阈值，则最后两次计算出的η值的均值即为两个平面图形的最终匹配度值。

可选地，所述η的变化期望阈值为1％。

可选地，所述直线边界是通过霍夫变换算法识别出边界离散边界特征点集后形成的。

第二方面，本发明提供了一种基于边界特征点集的平面图形匹配度评价装置，包括：

采集单元，用于采集待匹配的两个直边平面图形的边界特征点；

计算单元，用于基于所述边界特征点，以待匹配的两个直边平面图形最大程度重合为目标，计算获得平移、旋转直边平面图形后的图形变换参数，进而求得两个直边平面图形的不重合面积；

评价单元，用于根据所述不重合面积与两个直边平面图形平均面积的关系，确定图形匹配度值，完成平面图形匹配度评价。

第三方面，本发明提供了一种基于边界特征点集的平面图形匹配度评价系统，包括存储介质和处理器；

所述存储介质用于存储指令；

所述处理器用于根据所述指令进行操作以执行根据第一方面中任一项所述的方法。

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

(1)本发明仅仅采用具有直线边界的平面图形的轮廓信息进行匹配，借助图形直线边界上的有限个特征点来评价图形匹配度，相比利用整个图像信息(如像素、纹理等信息) 进行匹配可以指数级减少计算量，从而获得非常高的计算效率，尤其适合具有直边轮廓的钣金零件识别与分类、内空间平面测绘拼接等应用场合。

(2)本发明基于具有平均效应的整体匹配原则，而不用考虑两个平面图形上采集的边界特征点或关键点之间的一一对应情况，有效降低了采集的边界特征点中个别坏点数据对匹配结果的影响，提高了本发明方法的健壮性和准确性。此外，平面图形边界特征点的采集时无需参考基准，只要获得边界点集的相对坐标即可，即使两个平面图形的边界特征点数量不同也可适用本发明方法。

附图说明

为了使本发明的内容更容易被清楚地理解，下面根据具体实施例并结合附图，对本发明作进一步详细的说明，其中：

图1为本发明中基于边界特征点集的平面图形匹配度评价方法的流程图；

图2第一个平面图形边界特征点、直线边界、交点示意图；

图3第二个平面图形边界特征点、直线边界、交点示意图；

图4第一个平面图形直线边界等间距插值取点示意图；

图5第二个平面图形直线边界等间距插值取点示意图；

图6第二个平面图形平移示意图；

图7第一个平面图形等角度辐射线与直线边界段交点示意图；

图8第二个平面图形等角度辐射线与直线边界段交点示意图；

图9为d_2j和d_1j互相关分析结果；

图10第二个平面图形旋转后边界特征点、直线边界示意图；

图11 l_1i和l”_2i所围面积ΔS示意图。

具体实施方式

为了使本发明的目的、技术方案及优点更加清楚明白，以下结合实施例，对本发明进行进一步详细说明。应当理解，此处所描述的具体实施例仅仅用以解释本发明，并不用于限定本发明的保护范围。

下面结合附图对本发明的应用原理作详细的描述。

实施例1

如图1所示，本发明实施例中中提供了一种基于边界特征点集的平面图形匹配度评价方法，如图1所示，具体包括以下步骤：

(1)分别在待匹配的两个直边平面图形的平面内建立直角坐标系，提取待匹配的两个平面图形的边界特征点的位置坐标。如图2所示，第一个平面图形的边界特征点的位置记为(x_1i,y_1i)。其中，i从1到第一个平面图形的边界特征点总个数18。如图3所示，第二个平面图形的边界特征点的位置记为(x_2i,y_2i)。其中，i从1到第二个平面图形的边界特征点总个数20。

(2)利用霍夫变换算法识别出边界离散点集形成的直线边界，再分别确定相邻直线边界在直角坐标系中的交点。如图2所示，对于第一个平面图形，交点记为(x_c1i,y_c1i)。其中，i从1到第一个平面图形的相邻直线边界交点总个数3。如图3所示，对于第二个平面图形，交点记为(x_c2i,y_c2i)。其中，i从1到第二个平面图形的相邻直线边界交点总个数3。依次连接相邻交点形成直线边界段。将第一个平面图形的直线边界段首尾依次连接，按顺序记为l_1i，其中，i从1到第一个平面图形的直线边界段总个数3。将第二个平面图形的直线边界段首尾依次连接，按顺序记为l_2i，其中，i从1到第二个平面图形的直线边界段总个数3。

(3)如图4和图5所示，对所有的l_1i和l_2i进行等间距插值取点，插值取点的间距均为d＝32，分别获得两个平面图形的等间距边界点(x_d1k,y_d1k)和(x_d2k,y_d2k)。其中，k为等间距边界点的序号，分别取为1到两个平面图形的等间距边界点的总个数N_d1＝24和N_d2＝24。

(4)分别计算出 ΔX＝X₂-X₁＝-6，ΔY＝Y₂-Y₁＝-5。

(5)将第二个平面图形整体平移(-ΔX，-ΔY)，即(6，5)。如图6所示，记平移后的第二个平面图形的边界特征点(x’_2i,y’_2i)，直线边界段为l’_2i。

(6)以(X₁，Y₁)为中心作0～360度等角度辐射线，相邻等角度辐射线的夹角记为θ＝15°。如图7所示，获得等角度辐射线与第一个平面图形的直线边界段l_1i的交点(x_θ1j， y_θ1j)，其中，j从1到第一个平面图形的直线边界段上的交点总个数N_θ1＝24。同样，该组等角度辐射线与第二个平面图形的直线边界段l’_2i的交点记为(x_θ2j，y_θ2j)，如图8所示。其中， j从1到第二个平面图形的直线边界段上的交点总个数N_θ2＝24。

(7)按交点(x_θ1j，y_θ1j)在首尾依次连接的直线边界段l_1i上的顺序，依次分别计算(x_θ1j， y_θ1j)与中心点(X₁，Y₁)之间的距离d_1j，以直角坐标系X轴正方向顺时针为序，d₁₁到d₁₂₄分别为：93、103、65、49、42、39、39、42、49、63、101、104、71、57、51、49、50、 55、66、63、58、58、62、72。按相同的方向和顺序，依次分别计算(x_θ2j，y_θ2j)与中心点 (X₁，Y₁)之间的距离d_2j，d₂₁到d₂₂₄分别为：99、63、49、42、39、39、42、50、65、104、 106、73、59、53、50、52、58、69、69、64、64、69、80、105。对d_2j和d_1j进行互相关分析，结果如图9所示。由图9中，峰值横坐标位置确定时延参数Δ＝24。按Δ×θ＝360°角度(这说明两个平面图形的角度误差小于θ＝15°，要精确匹配这两个平面图形还需要进一步减小θ)，对平移后的第二个平面图形进行逆时针旋转，并按如图10所示记旋转后第二个平面图形的边界特征点(x”_2i,y”_2i)，直线边界段为l”_2i。

(8)分别计算直线边界段l_1i所围面积S₁，l”_2i所围面积S₂，l_1i和l”_2i所围面积ΔS(图 11)，并计算出两个平面图形匹配度

(9)将步骤(1)中第二个平面图形的边界特征点(x_2i,y_2i)替换为(x”_2i,y”_2i)，将d和θ分别取原值的一半，再重复步骤(1)到(8)，直至两个平面图形匹配度η的变化小于期望阈值，则最后两次计算出的η值的均值即为两个平面图形的最终匹配度值。本例中η的变化期望阈值为1％，计算获得的最终匹配度值为93％。

实施例2

基于与实施例1相同的发明构思，本发明实施例中提供了一种基于边界特征点集的平面图形匹配度评价装置，包括：

采集单元，用于采集待匹配的两个直边平面图形的边界特征点；

计算单元，用于基于所述边界特征点，以待匹配的两个直边平面图形最大程度重合为目标，计算获得平移、旋转直边平面图形后的图形变换参数，进而求得两个直边平面图形的不重合面积；

评价单元，用于根据所述不重合面积与两个直边平面图形平均面积的关系，确定图形匹配度值，完成平面图形匹配度评价。

其余部分均与实施例1相同。

实施例3

本发明实施例中提供了一种基于边界特征点集的平面图形匹配度评价系统，包括存储介质和处理器；

所述存储介质用于存储指令；

所述处理器用于根据所述指令进行操作以执行根据实施例1中任一项所述的方法。

本领域内的技术人员应明白，本申请的实施例可提供为方法、系统、或计算机程序产品。因此，本申请可采用完全硬件实施例、完全软件实施例、或结合软件和硬件方面的实施例的形式。而且，本申请可采用在一个或多个其中包含有计算机可用程序代码的计算机可用存储介质(包括但不限于磁盘存储器、CD-ROM、光学存储器等)上实施的计算机程序产品的形式。

本申请是参照根据本申请实施例的方法、设备(系统)、和计算机程序产品的流程图和/或方框图来描述的。应理解可由计算机程序指令实现流程图和/或方框图中的每一流程和/或方框、以及流程图和/或方框图中的流程和/或方框的结合。可提供这些计算机程序指令到通用计算机、专用计算机、嵌入式处理机或其他可编程数据处理设备的处理器以产生一个机器，使得通过计算机或其他可编程数据处理设备的处理器执行的指令产生用于实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能的装置。

这些计算机程序指令也可存储在能引导计算机或其他可编程数据处理设备以特定方式工作的计算机可读存储器中，使得存储在该计算机可读存储器中的指令产生包括指令装置的制造品，该指令装置实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能。

这些计算机程序指令也可装载到计算机或其他可编程数据处理设备上，使得在计算机或其他可编程设备上执行一系列操作步骤以产生计算机实现的处理，从而在计算机或其他可编程设备上执行的指令提供用于实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能的步骤。

最后应当说明的是：以上实施例仅用以说明本发明的技术方案而非对其限制，尽管参照上述实施例对本发明进行了详细的说明，所属领域的普通技术人员应当理解：依然可以对本发明的具体实施方式进行修改或者等同替换，而未脱离本发明精神和范围的任何修改或者等同替换，其均应涵盖在本发明的权利要求保护范围之内。

Claims (9)

1.一种基于边界特征点集的平面图形匹配度评价方法，其特征在于，包括：

采集待匹配的两个直边平面图形的边界特征点；

基于所述边界特征点，以待匹配的两个直边平面图形最大程度重合为目标，计算获得平移、旋转直边平面图形后的图形变换参数，进而求得两个直边平面图形的不重合面积；

根据所述不重合面积与两个直边平面图形平均面积的关系，确定图形匹配度值，完成平面图形匹配度评价；

所述两个直边平面图形的不重合面积的计算方法包括：

识别出边界离散边界特征点集形成的直线边界，再分别确定相邻直线边界在直角坐标系中的交点，依次连接相邻交点形成直线边界段；将第一个平面图形的直线边界段首尾依次连接，按顺序记为l_1i，其中，i从1到第一个平面图形的直线边界段总个数；将第二个平面图形的直线边界段首尾依次连接，按顺序记为l_2i，其中，i从1到第二个平面图形的直线边界段总个数；

对所有的l_1i和l_2i进行等间距插值取点，插值取点的间距均为d，分别获得两个直边平面图形的等间距边界点(x_d1k,y_d1k)和(x_d2k,y_d2k)，k为等间距边界点的序号，分别取为1到两个平面图形的等间距边界点的总个数N_d1和N_d2；

分别计算出ΔX＝X₂-X₁，ΔY＝Y₂-Y₁；

将第二个直边平面图形整体平移(-ΔX，-ΔY)，记平移后的第二个直边平面图形的边界特征点(x’_2i,y’_2i)，直线边界段为l’_2i；

以(X₁，Y₁)为中心作0～360°等角度辐射线，相邻等角度辐射线的夹角记为θ，获得等角度辐射线与第一个平面图形的直线边界段l_1i的交点(x_θ1j，y_θ1j)，其中，j从1到第一个平面图形的直线边界段上的交点总个数N_θ1；同样，该组等角度辐射线与第二个直边平面图形的直线边界段l’_2i的交点记为(x_θ2j，y_θ2j)；其中，j从1到第二个平面图形的直线边界段上的交点总个数N_θ2；

按交点(x_θ1j，y_θ1j)在首尾依次连接的直线边界段l_1i上的顺序，按顺时针方向依次分别计算(x_θ1j，y_θ1j)与中心点(X₁，Y₁)之间的距离d_1j，按相同的方向和顺序，依次分别计算(x_θ2j，y_θ2j)与中心点(X₁，Y₁)之间的距离d_2j；对d_2j和d_1j进行互相关分析，获得互相关函数达到最高值时的时延参数Δ；按Δ×θ角度对平移后的第二个平面图形进行逆时针旋转，并记旋转后第二个平面图形的边界特征点(x”_2i,y”_2i)，直线边界段为l”_2i；

计算直线边界段l_1i和直线边界段l”_2i所围面积ΔS，即两个直边平面图形的不重合面积。

2.根据权利要求1所述的一种基于边界特征点集的平面图形匹配度评价方法，其特征在于，所述边界特征点的采集方法包括：

分别在待匹配的两个直边平面图形的平面内建立直角坐标系，提取待匹配的两个直边平面图形的边界特征点的位置坐标。

3.根据权利要求2所述的一种基于边界特征点集的平面图形匹配度评价方法，其特征在于，第一个直边平面图形的边界特征点的位置记为(x_1i,y_1i)，i从1到第一个直边平面图形的边界特征点总个数；第二个平面图形的边界特征点的位置记为(x_2i,y_2i)，i从1到第二个直边平面图形的边界特征点总个数。

4.根据权利要求1所述的一种基于边界特征点集的平面图形匹配度评价方法，其特征在于，所述图形匹配度值通过下述公式计算：

其中，η为两个平面图形匹配度值，S₁为直线边界段l_1i所围面积，S₂为直线边界段l”_2i所围面积，ΔS为直线边界段l_1i和直线边界段l”_2i所围面积。

5.根据权利要求4所述的一种基于边界特征点集的平面图形匹配度评价方法，其特征在于，在计算出两个平面图形匹配度值η步骤之后还包括：

将第二个平面图形的边界特征点(x_2i,y_2i)替换为(x”_2i,y”_2i)，将d和θ分别取原值的一半；

重新采集待匹配的两个直边平面图形的边界特征点；

重新基于所述边界特征点，以待匹配的两个直边平面图形最大程度重合为目标，计算获得平移、旋转直边平面图形后的图形变换参数，进而求得两个直边平面图形的不重合面积；

直至两个平面图形匹配度η的变化小于期望阈值，则最后两次计算出的η值的均值即为两个平面图形的最终匹配度值。

6.根据权利要求5所述的一种基于边界特征点集的平面图形匹配度评价方法，其特征在于：所述η的变化期望阈值为1％。

7.根据权利要求1所述的一种基于边界特征点集的平面图形匹配度评价方法，其特征在于：所述直线边界是通过霍夫变换算法识别出边界离散边界特征点集后形成的。

8.一种基于边界特征点集的平面图形匹配度评价装置，其特征在于，包括：

采集单元，用于采集待匹配的两个直边平面图形的边界特征点；

计算单元，用于基于所述边界特征点，以待匹配的两个直边平面图形最大程度重合为目标，计算获得平移、旋转直边平面图形后的图形变换参数，进而求得两个直边平面图形的不重合面积；

评价单元，用于根据所述不重合面积与两个直边平面图形平均面积的关系，确定图形匹配度值，完成平面图形匹配度评价；

所述两个直边平面图形的不重合面积的计算方法包括：

识别出边界离散边界特征点集形成的直线边界，再分别确定相邻直线边界在直角坐标系中的交点，依次连接相邻交点形成直线边界段；将第一个平面图形的直线边界段首尾依次连接，按顺序记为l_1i，其中，i从1到第一个平面图形的直线边界段总个数；将第二个平面图形的直线边界段首尾依次连接，按顺序记为l_2i，其中，i从1到第二个平面图形的直线边界段总个数；

对所有的l_1i和l_2i进行等间距插值取点，插值取点的间距均为d，分别获得两个直边平面图形的等间距边界点(x_d1k,y_d1k)和(x_d2k,y_d2k)，k为等间距边界点的序号，分别取为1到两个平面图形的等间距边界点的总个数N_d1和N_d2；

分别计算出ΔX＝X₂-X₁，ΔY＝Y₂-Y₁；

将第二个直边平面图形整体平移(-ΔX，-ΔY)，记平移后的第二个直边平面图形的边界特征点(x’_2i,y’_2i)，直线边界段为l’_2i；

以(X₁，Y₁)为中心作0～360°等角度辐射线，相邻等角度辐射线的夹角记为θ，获得等角度辐射线与第一个平面图形的直线边界段l_1i的交点(x_θ1j，y_θ1j)，其中，j从1到第一个平面图形的直线边界段上的交点总个数N_θ1；同样，该组等角度辐射线与第二个直边平面图形的直线边界段l’_2i的交点记为(x_θ2j，y_θ2j)；其中，j从1到第二个平面图形的直线边界段上的交点总个数N_θ2；

按交点(x_θ1j，y_θ1j)在首尾依次连接的直线边界段l_1i上的顺序，按顺时针方向依次分别计算(x_θ1j，y_θ1j)与中心点(X₁，Y₁)之间的距离d_1j，按相同的方向和顺序，依次分别计算(x_θ2j，y_θ2j)与中心点(X₁，Y₁)之间的距离d_2j；对d_2j和d_1j进行互相关分析，获得互相关函数达到最高值时的时延参数Δ；按Δ×θ角度对平移后的第二个平面图形进行逆时针旋转，并记旋转后第二个平面图形的边界特征点(x”_2i,y”_2i)，直线边界段为l”_2i；

计算直线边界段l_1i和直线边界段l”_2i所围面积ΔS，即两个直边平面图形的不重合面积。

9.一种基于边界特征点集的平面图形匹配度评价系统，其特征在于，包括存储介质和处理器；

所述存储介质用于存储指令；

所述处理器用于根据所述指令进行操作以执行根据权利要求1-7中任一项所述的方法。