基于角点和三角形内间距的多工件检测方法

1 引 言

随着工业生产自动化水平的提高，对工件自动化检测的需求也在不断增长。机器视觉测量技术因具有非接触、精度高、速度快的优点，被广泛地运用于生产线上的工件测量中。由于工件物体本身具有的刚性和规则性，工件图像的轮廓能有效地体现目标物体的特征。但工业现场的工件堆叠遮挡会导致提取的工件轮廓缺失和断裂。因此，对局部工件轮廓进行检测，已成为研究热点。

Ianni 等在 1996 年时将部分轮廓在模板轮廓上的匹配问题描述为一个组合优化问题，并使用基于模拟退火算法和遗传算法的改进搜索算法对其进行求解。之后，van Kaick 等在此基础上提出了基于蚁群算法的局部形状匹配方法，对局部轮廓匹配的组合优化问题求解得到概率最优路径，同时获得最佳的匹配结果。此后，各种利用形状特征描述子的局部轮廓匹配方法也被相继提出。主要包括基于轮廓点区域分布直方图的形状上下文描述子 (Shape Context)、基于轮廓内距离的形状上下文描述子 (Inner-Distance Shape Contex) 和融合了全局与局部轮廓信息的精确型高度函数描述子 (Exact Height Function 1)。王燕妮等在针对建筑轮廓的识别中，提出了基于各种矢量描述和轮廓局部特征的局部轮廓识别算法。该算法根据不同建筑的矢量信息，制定了任意形状轮廓匹配相似度准则及映射函数，能有效解决局部轮廓的匹配问题。黄浩等提出了利用形状描述子将各轮廓转换为信号数据，训练反向传播神经网络，对复杂的管道网络图像完成了识别。文献利用物体的局部轮廓大多为开轮廓的特性，提出一种基于轮廓点内间距的特征描述子。该描述子有旋转、尺度和平移不变性，而且具有很好的仿射不变性。Yang 等在 2018 年提出三角形内间距 (Triangular Centroid Distances，TCDs) 算子。TCDs 算子对于平移、旋转、缩放，以及相当大的形状变形都有可靠的不变性。孙国栋等对TCDs 描述子和 EHF1(Exact Height Function 1) 描述子进行融合，利用 EHF1 算子对轮廓全局信息与局部信息融合的优点， 提出新的 TCDs 描述子。但为了有效地描述轮廓，TCDs 描述子需要在轮廓处密集地取采样点，在和模板轮廓匹配时，局部轮廓按采样点次序依次在模板轮廓上滑动，并进行相似度计算。这存在算法匹配时计算时间过长，且要处理采样点起点不变的问题。针对以上问题，本文根据工件轮廓的角点特性，使用角点数量对模板轮廓进行初步划分，获取模板图像中的疑似轮廓段，再根据角点位置重新选取采样点，解决采样点的起点不变性。最后再将局部轮廓和模板的疑似轮廓进行匹配，完成局部轮廓的识别。结果表明，在相同取样点的情况下，本文算法的识别率高于传统 TCDs 算法，并且算法耗时减少了 86%。

2 轮廓角点提取

对于轮廓的角点提取，传统方法是提取轮廓上每一点的曲率，而轮廓的角点一般是轮廓上曲率值极大的点，所以可以通过提取轮廓上的曲率极值点来提取轮廓图像的角点。本文采用构建轮廓点前后三角形的方式计算轮廓曲线上每一点的曲率值。具体方法是，将轮廓上每一点和其前后一定距离的两点组成一个三角形，计算每个前后三角形中轮廓点所在角的角度， 作为该点的曲率值。这种计算曲率值的方法用时短，对于轮廓的细小突起也能起到明显的平滑作用。该算法的原理如图 1 所示。

如图 1 所示，对于一段轮廓序列，序列上的每一个点 P 都能组成图 1 中所示的 ΔP-PP+ 。如果记 P-P 距离为 b、PP+ 距离为 a、 P-P+ 距离为 c，那么∠ P-PP+ 的大小 α 便可以表示点 P 的曲率。由于角度的余弦值在[0, 180] 的范围内单调递减，故可用值来表示∠ P-PP+ 的大小。

获取每个轮廓点所组成三角形的后，便可获得如图2 所示局部轮廓的曲率值序列。其中，曲率值序列的局部极大值点便是该轮廓的角点。

图 1 轮廓点曲率原理图

3 三角形内间距描述子

TCDs 描述子于 2018 年提出，能很好地描述二维形状。该作者在文中还提出了局部轮廓和模板轮廓的匹配方法，其原理如图 3 所示。

首先，假设图 3 中红色段为总轮廓的局部轮廓段，记为轮廓 P，随后计算轮廓 P 的质心 G， 在 P 上均匀地取 N 个采样点，对于每个采样点Pi 来说，都可以与其他采样点P(j j ∈ [1,N] j ≠ i)和质心 G 组成 N - 1 个三角形，记为 ΔPiPPj 。接着计算出每个 ΔPiPPj 的质心，记为 gij。其次，对于采样点 Pi，计算 Pi 与 gij 之间的欧氏距离，获得一组长度为 N - 1 的特征向量，该特征向量就是采样点 Pi 的 TCDs 特征向量，记为 li。最后，按照轮廓点的次序提取轮廓 P 上所有采样点的 TCDs 特征向量，记为 L=(l1,…，ln)。至此，轮廓 P 的 TCDs 描述子提取完成。而对于局部轮廓和模板轮廓的匹配问题，首先根据轮廓 P 的长度，在模板轮廓上取相同长度的轮廓段;然后，在模板轮廓上滑动轮廓段，计算每次滑动后轮廓段的 TCDs 特征矩阵，并计算特征矩阵与 L 的相似度;最后，选取模板轮廓中相似度最大的轮廓段作为匹配结果。

图 2 轮廓点曲率值序列

4 融合角点信息的三角形内间距描述子

一般 TCDs 描述子提取的采样点是在轮廓段上均匀地采样，同时为了准确地描述轮廓，采样点的间距不能过大。而这样的采样方式将导致在模板轮廓匹配的过程中模板轮廓段滑动次数过多，计算量较大。此外，在计算 TCDs 描述子时，局部轮廓采样点起始点的改变会造成特征矩阵的变化，故一般会对提取的特征矩阵的每一行进行离散傅里叶变换，然后忽略傅里叶变换后的相位信息，只使用系数的大小，保证了描述子的起点不变性。但这样会导致提取 TCDs 描述子的时间变长，而且起点不变性主要运用在两个完整封闭形状的匹配，在局部轮廓的匹配中实用性不强。

(1)

图 3 TCDs 算法原理图

图 4 采样点分布

图 5 工件的局部轮廓

本文提出使用角点特征对模板轮廓段进行筛选，然后使用角点坐标对采样点进行锁定，再对局部轮廓提取 TCDs 特征矩阵，减少了计算量和计算步骤，具体方法如下。

首先对于一段长度为 n 的局部轮廓，记为 P={pi=(xi， yi)，i=1，2， …，n}， 其中(xi，yi)为轮廓点在二维图像中的坐标。再根据公式 (1)，对 P 提取角点，假设轮廓 P 共有 N 个角点，将每一个角点在轮廓序列 P 的序列位置记为 kj, j ∈ [1,N] ，那么角点 Pkj 可以将轮廓分为 N + 1 段，记轮廓 P={p1…pk1…pkj…pkn…pn}。

使用角点对轮廓进行分段，轮廓段在结构上体现出平滑、稳定的特性，因此对角点间的轮廓段均匀取采样点，可有效地反映整体的轮廓特征。如公式 (2) 所示，对 N + 1 段轮廓段的每一段均匀分成 S 份，便可得到整个轮廓的采样点，记为 L。采样点的分布如图 4 所示。

(2)

之后根据采样点集 L 获得轮廓 P 的 TCDs 特征矩阵。首先提取轮廓 P 的质心 G(xG，yG) ，为了简化计算量，使用采样点的坐标来计算质心。计算公式如下：

(3)

对每一个采样点 li 来说，可以与质心 G 及剩下的 n-1 个采样点组成 n-1 个三角形。记这 n-1 个三角形的质心为 gij 。

图 6 模板轮廓疑似轮廓段

而采样点 l i 与 g i j 在图像中的距离，便是 l i 点此处的轮廓点特征，记为，其中 的计算公式如下：

(4)

而对于整段轮廓 P，则可提取出 (n - 1)×n 大小的特征矩阵，记为 TCDsP。

(5)

为了获得轮廓描述子的比例不变性，对 TCDsP 矩阵的每一行除以该行的最大值，如公式 (6) 所示：

图 7 特殊的轮廓段

(6)

至此，TCDs 特征矩阵的提取基本完成。随后根据局部轮廓的角点信息在模板轮廓上提取疑似的轮廓段。由于本文的描述子算法简化了方向不变性，所以从一开始就要对局部轮廓进行方向上的判定。

如图 5 所示，对于图像的局部轮廓来说，若以 A 为起点， 则轮廓序列的遍历方向为逆时针;若以 B 为起点，则轮廓序列的遍历方向为顺时针。可见，不同的轮廓起点导致轮廓遍历方向的不同。为了判定局部轮廓的序列方向，首先可以将局部轮廓视作一个封闭的图像，以 A → B → A 或 B → A → B 方向对轮廓点的二维坐标求曲线积分。若求得的值为正，则轮廓方向为逆时针;求得的值为负，则轮廓方向为顺时针。为了节省计算时间，本文算法不对所有的轮廓点进行计算，而只计算轮廓的角点。设序列 J=[ ji=(xi，yi)，i=1，2，…，n]，其中 j1 与 jn 分别表示局部轮廓的起点和末点，其他点为局部轮廓的角点，(x i , y i ) 为对应角点 j i 在图像中的二维坐标。设参数 F 为：

(7)

若 F > 0，则局部轮廓的遍历方向为逆时针;若 F < 0， 则局部轮廓的遍历方向为顺时针;若 F = 0，则表示局部轮廓为一条直线。

获得局部轮廓的遍历方向后，便可以按照局部轮廓的方向在模板轮廓上生成疑似轮廓段。记模板轮廓为 D、角点个数为M、局部轮廓 P、角点个数为 N，那么显然 N ≤ M。这样模板轮廓就能分成 M 组，每组包含 N 个角点的疑似轮廓段。图5 所示的局部轮廓上有 4 个角点，记轮廓起点 A 与第 1 个角点的距离为 L1，轮廓末点 B 与最后 1 个角点的距离为 L2。在模板轮廓上选取任意角点为起点，并按照公式 (6) 确定的遍离方向，在模板轮廓上依次选取包含 4 个角点的轮廓段，并在轮廓段的第 1 个角点和最后 1 个角点处，分别在模板轮廓上顺延 L1 与 L2 的距离，获得模板轮廓的一个疑似轮廓段。然后依次按确定的遍历方向移动起始的角点，获得剩下的疑似轮廓段，组成该模板的疑似轮廓段集合，具体如图 6 所示。

图 8 相似零件的匹配结果

疑似轮廓段集合按照上文方法提取 TCDs 特征矩阵，并与局部轮廓 P 的 TCDs 特征矩阵计算差异度，其中差异度最小的轮廓段便是局部轮廓 P 与该模板轮廓的匹配结果。

提取模板的疑似轮廓后，需要考虑一种特殊情况：当局部轮廓的 L1、L2 过长时，某些模板的疑似轮廓段的长度会超出整个模板轮廓的长度。如图 7 所示，显然这些疑似轮廓段不是最相似的。为了节省计算时间，本文直接计算疑似轮廓段的长度，若疑似轮廓段长度超出整个模板轮廓的长度，则可直接剔除。

图 9 算法流程图

由于已经对轮廓 P 和模板轮廓进行采样方向的统一，采样点的位置也经过角点进行锁定，所以轮廓 P 的 TCDs 特征矩阵和每个模板的疑似轮廓段的大小、方向都一致。因此， 直接按顺序计算每个轮廓段 TCDs 特征矩阵中每个采样点的特征向量的余弦相似度，再将这些向量的余弦相似度取均值，就可以得到两个轮廓段的 TCDs 特征矩阵相似度。设轮廓 P 的采样点个数为 n，那么轮廓 P 的 TCDs 特征矩阵为： TCDsP=[TCDsp1…TCDspn]。设轮廓 C 为轮廓 P 的疑似轮廓段， 轮廓 C 的 TCDs 特征矩阵为：TCDsC=[TCDsc1…TCDscn]。其中， TCDspi 和 TCDsci 是长度为 n-1 的一维特征向量。两者的相似度 Dist(P,C)为：

(8)

由公式 (8) 可得，Dist(P,C)取值范围为 [0, 1]，其中取值越接近 0 表示越匹配，越接近 1 表示越不匹配。虽然 TCDs 描述子具有较好的尺度不变性，但实际工件检测过程中存在许多相似形状，因此不同尺寸的工件，使用 TCDs 描述子将难以区分，如图 8 所示。

图 8(a) 中标红轮廓段为待检测的目标轮廓段，图 8(b、a) 为两个形状类似但尺寸不同的模板轮廓匹配结果。其中，图8(b) 为正确的匹配结果，但目标轮廓段与图 8(c) 的匹配结果也非常相似。为了正确区分不同尺寸的工件，本文根据轮廓的长度特征对两轮廓的计算公式加以修正。设轮廓 P 的长度为lP、轮廓 C 的长度为 lC，那么修正后的轮廓相似度为Dis(t P,C)：

(9)

其中，δ 为长度差异的控制系数，主要是为了控制长度差异对轮廓相似度的影响，一般 δ 的取值范围在 [0, 1]，主要体现形状轮廓相似的优先性。经过多次实验验证，δ 取 0.1 时实验效果最为理想。本文的算法流程如图 9 所示。

5 实验结果

本文从检测速度和检测精度两方面来验证检测算法的性能。首先，选取 6 种形状和大小不同的工件，每种工件取不同角度、不同视角下的轮廓图各 11 张。每张工件图中随机选取6 段工件的局部轮廓，共提取出 600 张工件的局部轮廓样本，并给每一个工件使用不同视角的 3 张图片作为模板，取 3 张模板中相似度值最接近的轮廓段作为模板的匹配结果，具体流程如图 10 所示。

图 10 匹配流程图

图 11 局部工件轮廓的匹配结果

图 11 为实验匹配结果。其中，图 11 第 1 列标红的轮廓为待配结果，绿色框表示和待检测轮廓最相似的工件轮廓。对于待检测的部分轮廓，即便不是对应的正确工件，也能在相应的工件轮廓中找到最相似的疑似轮廓段，很好地体现了 TCDs 描述子对形状的敏感性。可见，对于形状相似但大小不同的工件局部轮廓，本文算法也能正确完成识别。

图 12 为本文算法在堆叠工件图像的匹配结果。其中，不同颜色分别表示不同的识别结果。例如，工件轮廓标注为紫色， 那就说明该工件被识别为下方为紫色的模板工件，并在模板工件上给出匹配的轮廓段和相似度。

在堆叠情况比较复杂时，如图 13 所示被标红的轮廓段为工件堆叠较为严重的区域，堆叠物体的轮廓线互相覆盖，局部轮廓段的角点位置和个数被改变，造成该轮廓段不能识别或者识别错误的情况。在轮廓线影响不严重的区域，一般忽略重叠轮廓线的影响，将重叠轮廓段作为独立的目标轮廓段进行匹配， 匹配结果如图 14 所示。而对于堆叠物体的轮廓线影响较严重的图片，本文算法很难识别提取出来的局部轮廓段，这是本文算法的不足之处。

从公式 (2) 可知，对于一段待检测的局部轮廓，本文算法的采样点选取是通过对轮廓段进行角点分割，然后在角点分割段中均匀取样。这样的采样方法能充分利用角点间轮廓段平滑的特性，少量取点也能很好地描述轮廓。角点轮廓段内不同采样点个数对识别正确率的影响如图 15 所示。

从图 15 可知，当每个角点间的采样点数为 6 个时，识别率达到了较高值，且采样点个数最少。因此本文算法对轮廓的采样点个数为 (n + 1)×6(n 为局部轮廓上的角点个数 )。

表 1 为不同局本轮廓匹配算法在单一模板的匹配时间，

图 12 局部工件轮廓的匹配结果

图 13 复杂的堆叠工件图像

图 14 复杂的堆叠工件匹配结果

图 15 采样点个数对准确率的影响

由于本文算法的采样点数量和轮廓内角点数量相关，而传统TCDs 算法都为固定数目的采样点，为了保证算法比较的公平性，TCDs 算法的采样点数目限定为 (n + 1)×6 个。从表 1 可以看出，与传统的 TCDs 轮廓匹配方法相比，本文算法的计算效率有明显的提升。

为了体现本文算法的识别精度，将传统 TCDs 匹配算法、形状上下文 (Shape Context) 匹配算法、基于 Shape Context 描述子的 BP(Back Propagation) 神经网络算法和本文算法，在不同遮挡比例下的识别率进行计算。根据上文所提到的，由于本文算法是根据目标局部轮廓的角点个数来形成采样点个数，所以 TCDs 匹配算法和 SC( 形状上下文 ) 匹配算法的采样点个数均为 (n + 1)×6 个，而 SC + BP 神经网络算法则使用固定的采样点个数进行网络的训练和识别，大小和本文算法的数量级相同。实验对比结果如表 2 所示。从表 2 可知，

本文算法在不同的局部轮廓比例的识别率均优于以上 3 种算法。在采样点数量较少的情况下，本文算法根据轮廓角点位置的采样方法对轮廓的描述精度有明显的提升。

6 结论

本文针对工件被遮挡只能提取局部轮廓的问题，提出一种基于 TCDs 描述子的改进局部轮廓匹配算法。首先，利用局部轮廓的角点信息在模板轮廓上寻找到相对应的疑似轮廓，这大大缩短了传统 TCDs 算法在模板匹配上滑动匹配的计算时间。其次，在描述子的采样点上，根据轮廓的角点分布，在轮廓段的角点间均匀取样，充分利用了角点间轮廓段平滑的特性，大大减少了采样点的数量。而且，本文简化了传统 TCDs 算法解决起点不变性的步骤。最后，通过统一局部轮廓和模板轮廓的遍历方向，保证了局部轮廓和模板轮廓中疑似轮廓方向的一致性。通过对工件局部轮廓和模板轮廓疑似轮廓段的相似度比较， 获得局部轮廓在不同模板轮廓的匹配结果，实现局部工件轮廓的目标匹配。实验结果表明，与传统的 TCDs 算法相比，本文算法时间效率有明显的提升。在不同的局部轮廓比例和少量采样子的情况下，本文算法对局部轮廓的识别率均优于传统算法。其中，当局部轮廓的比例为 60% 时，本文算法的识别率依然高于 90%。但本文算法也存在不足之处：当堆叠物体的轮廓线影响较严重时，由于局部轮廓段的角点信息被破坏，算法难以识别该局部轮廓。

表 1 算法计算时间

表 2 不同遮挡比例的识别率

作者：慎正 1 胡超 2

1 江西理工大学电气工程与自动化学院

2 浙大宁波理工学院信息科学与工程学院转载自《集成技术》