面向工业复杂场景的合作靶标椭圆特征快速鲁棒检测

李 洋，程 智，周维虎，高 超，董登峰*

（1.中国科学院 微电子研究所，北京 100094；2.中国科学院大学，北京 100049）

1 引 言

在工业测量领域，激光跟踪仪、工业全站仪、视觉测量仪等精密光学仪器越来越多地应用于高精度复杂结构的加工装配质量控制过程［1-4］，并且正在从传统的离线人工测量朝在线自动测量方向发展。为满足工业自动测量需求，上述仪器需要具备合作靶标自动检测功能。在实际工业测量场景中，常用的全反射靶球、平面反射片、立体靶标等合作靶标均包含圆形特征［5］，经透视变换后成为椭圆特征。而在背景环境中出现椭圆特征的几率较低，所以快速准确检测场景中的椭圆特征是自动检测合作靶标的关键。

椭圆特征检测是目标检测领域中的一项经典问题，国内外学者针对该问题开展了大量研究工作，目前椭圆检测方法主要分为两类：基于霍夫变换（HT）的椭圆检测方法和基于边缘段连接的椭圆检测方法。

霍夫变换是用于检测图像中各类函数曲线特征的一种通用方法。在椭圆特征检测中应用霍夫变换的主要问题是椭圆方程包含五个参数，需要构建相应的5维参数空间进行运算，导致算法效率较低，该类算法的主要研究方向是通过减少参与计算的样本数量、降低参数空间维度等方式优化计算效率［6］。McLaughlin在文献［7］中提出利用椭圆几何性质求取中心点坐标，将5维参数空间转化为3维，然后基于Xu等［8］提出的随机霍夫变换（RHT）方法求取其余参数；Guil和Zapata等［9］提出的快速椭圆霍夫变换（FEHT）进一步约束了参与霍夫变换的图像像素范围，并在霍夫变换阶段将3维参数空间分解为2维参数空间进行求取，从而提高了算法效率；Chia等［10］提出的算法采用一维参数空间求取椭圆特征，在提升算法效率同时便于通过并行运算缩短运算时间；邹荣等［11］利用梯度图像求取椭圆切线，并利用切线参数在5维霍夫空间中通过少量图像点获取椭圆参数。这些算法对霍夫变换进行了一定程度的优化，但仍然无法从根本上解决检测低效问题，这制约了该类检测算法在检测应用领域的推广。

近年来，基于边缘连接的椭圆特征检测技术发展较快，该领域研究重点是对边缘弧段进行有效约束和聚类，找到属于同一椭圆特征的弧段集合，同时排除非椭圆边缘干扰。Prasad等［12］提出了一种基于边缘弧段曲率与相关凸性约束的椭圆检测方法，该方法基于几何特征给出弧段搜索范围，性能优于传统的边缘连续性约束方法；Fornaciari等［13］提出的YAED方法通过凸性和梯度方向，将边缘弧段分为四个象限组，然后通过几何特征约束和中心参数约束确定合适的三弧段组进行椭圆拟合；Wang等［14］提出的方法和Liu等［15］提出的方法综合采用凸性特征、弧段曲率、坐标区域等约束条件对全部边缘弧段进行分组，但弧段分组约束条件不够严格，在处理包含复杂场景的真实图像时会产生大量误匹配弧段组合，导致误检率偏高；Meng等［16］提出的AAMED方法在几何约束基础上构建邻接矩阵，通过边缘弧段搜索与组合验证来获得属于同一椭圆的边缘弧段组合，该方法有效提高了弧段聚类效率，但仍存在约束条件不严格的问题；Jia等［17］提出的CNED方法利用特征数对图像边缘弧段进行匹配约束，然后通过遍历进行弧段组合，该方法提出了相对严格的约束条件，但特征数计算和弧段搜索组合效率偏低，难以满足实时性应用要求。

本文椭圆检测方法基于边缘连接技术，能够避免霍夫变换高维参数空间带来的处理效率偏低问题，并且提出了基于帕斯卡定理的边缘弧段椭圆特征匹配方法和基于关系矩阵的弧段聚类方法，通过严格的参数约束排除伪椭圆特征，通过矩阵运算提高弧段聚类效率，从而改善系统在复杂环境干扰下的鲁棒性，有效克服边缘连接类椭圆检测方法实时性不足、易受环境干扰等问题，可以满足工业复杂场景合作靶标椭圆特征检测所需。

2 椭圆检测总体方案

图1所示为本文椭圆检测方法流程框图，主要包括以下步骤：（1）基于几何特征的边缘弧段分组；（2）基于帕斯卡定理的邻接象限弧段匹配；（3）基于弧段关系矩阵的弧段聚类；（4）椭圆特征参数非迭代拟合与椭圆特征筛选。

图1 椭圆检测方案流程框图Fig.1 Block diagram of ellipse detecting process

在步骤（1）中，首先对图像边缘弧段进行分割筛选，然后采用文献［13］方法根据边缘弧段凸性将其分四个象限弧段组；步骤（2）、（3）为本文提出的弧段匹配和聚类方法，其中步骤（2）基于帕斯卡定理提出了一种更加有效的参数约束条件，可对四个相邻象限弧段组（I、II象限，II、III象限，III、IV象限，IV、I象限）进行严格的椭圆特征匹配，筛除大量非椭圆弧段组，得到满足椭圆参数约束条件的弧段对组合，步骤（3）把弧段参数约束结果转化为关系矩阵［18］，通过关系矩阵性质和布尔乘法运算进一步建立匹配于同一椭圆的三弧段组合和四弧段组合，作为椭圆参数拟合数据集；步骤（4）采用文献［19］ElliFit方法拟合椭圆参数特征，然后根据椭圆参数筛选排除伪特征和重复特征，得到最终检测结果。

2.1 基于几何特征的边缘弧段分组

对数字图像进行高斯滤波后，采用自适应Canny算子提取图像单像素二值化边缘图，然后采用8-邻域边缘跟踪方法［20］把具有邻接关系的边缘点连通形成具有几何意义的边缘弧段，建立图像边缘弧段集合Arcs。本部分目的是基于弧段集合Arcs构造分属于图2所示四个象限的边缘弧段集合Arcs1~Arcs4。

图2 弧段象限划分示意Fig.2 Schematic of classifying arcs by quadrant

如图3所示，由于集合Arcs中的弧段元素arc可能包含来自多个象限的组成部分，无法直接被归入某个象限集合，所以需要对各弧段元素在x、y方向梯度值∇x=0和∇y=0处进行分割，用分割所得子弧段替代原弧段元素，使Arcs全部弧段元素均能被归入某一象限组。其中方向梯度值由图像Canny处理过程给出。

图3 根据方向梯度分割边缘弧段Fig.3 Segment edge arc by gradient orientation

接下来在各弧段元素中搜索拐点，并将其在拐点处断开，以获得无转折的平滑弧段组。如图4所示，对弧段以5点一组进行分组，所得端点序列集合为{p1，p2，...，pn}，可求得端点坐标二阶差分序列：。若存在某个端点pe，其坐标二阶差分（xe，ye）绝对值之和满足|xe|+|ye|>Threaddiff，则表示弧段在点pe+1前后走向发生了较大变化，点pe+1即为拐点。图4（b）中拐点p4对应的坐标二阶差分为=(-3，-2)，绝对值之和为5，其它点对应的坐标二阶差分绝对值之和均小于2。经实验验证，取二阶差分阈值Threaddiff=4，可获得较好的拐点筛除效果。

图4 基于点组坐标差分信息的弧段拐点判断Fig.4 Turning point recognition based on coordinate dif‐ference information of point groups

对于无拐点的弧段集合Arcs，需要筛除其中的直线段元素，减少非椭圆特征的干扰。如图5所示，计算弧段中点Pmid1与弧段两端点连线中点Pmid2距离dm12，若dm12小于给定阈值，则认为该元素为直线段并予以排除。

图5 直线段元素判断Fig.5 Recognition of line segment

经上述筛除后，可根据弧段元素端点连线斜率符号，把弧段集合Arcs划分为属于I/III象限的集合Arcs13和属于II/IV象限的集合Arcs24，如图6所示；同时，还可以根据弧段凸性特征把弧段集合Arcs划分为属于I/II象限的凸弧段集合Arcs12和属于III/IV凹弧段集合Arcs34。然后根据弧段集合关系式（1），即可得到所需的四个象限弧段集合：Arcs1，Arcs2，Arcs3，Arcs4。

图6 原始图像与弧段集合Arcs13，Arcs24Fig.6 Original image and groups of arcs Arcs13，Arcs24

2.2 基于帕斯卡定理的邻接象限弧段匹配

本部分提出了一种基于帕斯卡定理的邻接象限弧段椭圆特征匹配方法，它的作用是判断相邻两象限弧段集合元素是否匹配于同一椭圆特征，作为下一步构建弧段集合之间关系矩阵的依据。与同类检测算法常用的弧段邻近性约束、凸性约束、中心坐标约束等方法相比，本方法采用二次圆锥曲线性质作为约束条件，对椭圆特征的约束性更加严格，能够对非椭圆特征起到更好的筛除效果。

图7 相邻象限弧段几何位置关系Fig.7 Geometric relationship of arcs from adjacent quad‐rants

式（2）中，括号中x，y分别代表弧段端点x，y坐标。显然，只有满足以上坐标位置关系，弧段对才有可能匹配于同一椭圆特征。

对于满足弧段端点坐标位置关系C1的弧段对，基于帕斯卡定理进行椭圆特征匹配性判断。由帕斯卡定理可知，若一个六边形的三对对边交点共线，则该六边形内接于一条二次圆锥曲线。由于椭圆属于二次圆锥曲线，所以椭圆以及椭圆弧段上的点均符合帕斯卡定理。

如图8所示，以I、II象限弧段对为例，首先在两弧段上任取六点Pp1，Pp2，Pp3，Pp4，Pp5，Pp6，确保以它们为顶点的六边形H对边不平行且相邻点间距尽量大，H的三组对边延长线分别交于点Pj1，Pj2，Pj3，根据帕斯卡定理，若Pj1，Pj2，Pj3三点共线，则两弧段属于同一椭圆特征，如图8（a）所示；否则若Pj1，Pj2，Pj3三点不共线，则两弧段不属于同一椭圆特征，如图8（b）所示。

图8 基于帕斯卡定理的相邻象限弧段对椭圆匹配Fig.8 Adjacent quadrants'arc pair elliptical matching method based on Pascal's theorem

在真实图像中由于各类干扰因素的存在，上述共线条件无法绝对满足。设直线Pj1Pj2与直线Pj2Pj3夹角为θp（若夹角为钝角，则取其补角作为θp），基于帕斯卡定理的椭圆匹配约束关系C2表示为：

式（3）中，参数θt为用来判定Pj1，Pj2，Pj3三点共线程度的角度阈值。对于满足基本坐标位置关系C1的 弧 段 对，基于本文提出的椭圆匹配约束关系C2进行判断，能够排除大量不具备椭圆匹配关系的弧段对，使得本文算法对于真实场景图像复杂干扰信息具有较强的鲁棒性，同时也有助于减小弧段聚类、椭圆拟合过程的数据量，提高处理效率。对于同时满足C1和C2约束的弧段对，称其匹配关系为“椭圆匹配”，否则称其为“椭圆不匹配”。

2.3 基于弧段关系矩阵的弧段聚类

真实检测图像存在大量噪声和非目标对象干扰，为提高检测结果可靠性，需要对同时匹配于3个或4个不同象限弧段的椭圆特征进行拟合。在这一部分，本文基于关系矩阵概念及其符合运算法则，提出了一种基于弧段关系矩阵（Arcs Relation Matrix，ARM）的聚类方法，该方法可以通过2.2节弧段对匹配结果构建具有椭圆匹配关系的三象限弧段集合和四象限弧段集合，作为下一步椭圆参数拟合数据集。

弧段关系矩阵是专门用于描述两弧段集合间椭圆匹配二元关系的矩阵。对于两个相邻象限弧段集合，首先构建其二邻接关系矩阵ARM-2。通过2.2节约束条件遍历各判断弧段对的椭圆匹配关系，可建立起弧段集A͂到弧段集B͂的二元关系RA͂，B͂：

其关系矩阵MA，B表示为：

其中，矩阵各元素值rij由下式给出：

由二邻接关系矩阵ARM-2构建过程可知，弧段关系矩阵MA，B的元素rij表示两个弧段对的匹配关系：若rij=1，则表示弧段对椭圆匹配，若rij=0，则表示弧段对椭圆不匹配。

对于四个象限弧段集合，可以构建四个二邻接关系矩阵ARM-2：MI，II，MII，III，MIII，IV，MIV，I，根据二元关系的复合运算法则，可以进一步求出用以描述三个相邻象限弧段集合椭圆匹配二元关系的三邻接关系矩阵ARM-3：MI，II，III，MII，III，IV，MIII，IV，I，MIV，I，II：

以及一个用以描述四个象限弧段集合椭圆匹配二元关系的四邻接关系矩阵ARM-4：MI，II，III，IV：

式（6）、式（7）中的符号“∘”代表布尔乘法运算符。由关系矩阵概念可知，ARM-3关系矩阵中每个“1”值元素表示在相应的三个象限中存在一个具有椭圆匹配关系的三弧段组，例如MI，II，III（i，j）=1表示存在一个三弧段组具有椭圆匹配关系，i，x，j分别代表该组合中的三个弧段在各自所属象限弧段集合中的序号，其中i，j与矩阵脚标值相同，x可以在求取ARM-3关系矩阵的布尔运算过程中获得。ARM-4关系矩阵中每个“1”值元素表示存在一个具有椭圆匹配关系的四弧段组，其 中 四 个 弧 段 分 别 属于四个不同象限，i，x1，x2，j的意义和求取过程与ARM-3关系矩阵类似。

通过求取ARM-3关系矩阵和ARM-4关系矩阵，可以得到以下五个弧段组集合：

在四弧段组集合RI，II，III，IV中，每个元素表示一个来自四个不同象限的四弧段组存在椭圆匹配关系；类似地，在 三弧段组集合RA，B，C中，每个元素表示一组来自三个不同象限的三弧段组存在椭圆匹配关系。上述五个集合中的每个元素都对应于图像中的一个椭圆特征，通过对各元素对应的弧段组进行拟合就能得到相应的椭圆参数。

在进行椭圆参数拟合之前，注意到存在部分三弧段组集合元素参与构成了四弧段组集合，为避免对同一椭圆特征进行重复拟合，需要从三弧段组集合中排除上述参与构成四弧段组集合的元素。设排除重复元素后的三弧段组集合为，则它们与四弧段组集合RI，II，III，IV的并集ΦD即为椭圆参数拟合数据集。

2.4 椭圆特征参数非迭代拟合与椭圆特征筛选

对椭圆参数拟合数据集ΦE中包含的各弧段组进行最小二乘拟合，即可得到若干组椭圆特征参数，对这些椭圆特征参数进行进一步筛选，排除重复特征和伪特征，最终得出所求的椭圆特征。

在参数拟合阶段，采用ElliFit算法对各弧段组数据进行椭圆特征参数非迭代最小二乘拟合，求出各椭圆特征参数向量V(i)=，其中和为椭圆中心坐标，a(i)，b(i)分别为椭圆长、短半轴长度为椭圆长轴与x轴夹角，e(i)为椭圆拟合误差。所有参数向量共同组成椭圆特征集合ΦE。通过以下规则对集合中椭圆元素进行筛选，最终得到椭圆特征检测结果：

（1）给定阈值emax，判定椭圆特征V（i）的拟合误差ei是否超限，如果ei>emax，则表示拟合点与椭圆特征距离较大，从ΦE中剔除该椭圆特征［21］；

（2）给定阈值rmax，判定椭圆特征V（i）的长、短轴长度比ri=a（i）/b（i）是否超限，如果ri>rmax，则表示椭圆形状过于扁平，存在较大的误匹配可能，从ΦE中剔除该椭圆特征。

（3）给定阈值dmin，tmin，对于每个椭圆特征V（i），求取该特征与其它每个椭圆特征的中心点欧氏距离dij，若存在椭圆特征V（j）使得dij

3 实验结果与分析

为验证本文算法效果，对典型工业测量合作目标进行了一系列实验验证，实验时将被测对象置于复杂环境场景中，模拟现场检测环境。硬件环境为计算机（CPU主频3.0 GHz），软件环境为VC++。

本文算法检测过程与结果如图9所示，图9（a）为平面反射片在实验室模拟场景中拍摄的原始图像，（b）为边缘跟踪所得的图像边缘片段，（c）为筛选分组后的四象限边缘弧段集合，图中四种颜色代表四个象限弧段集合，（d）为弧段聚类结果，颜色相同的弧段表示属于同一椭圆特征，（g）为椭圆拟合结果，（h）为筛选后的最终椭圆检测结果。

图9 椭圆检测过程与检测结果（椭圆数量n=3）（椭圆数量n=2）Fig.9 Ellipse detection process and result（with 3 ellipses fitted）（with 2 ellipses detected）

经实验验证，对于分辨率为640×480 pixels的实验图像，本文算法图像预处理过程用时159.2 ms，弧段预处理过程用时7.2 ms，弧段匹配聚类用时5.9 ms，椭圆拟合用时8.3 ms，拟合结果筛选用时2.6 ms，总用时183.2 ms。应用同一图像对RHT、YAED、AAMED、CNED算法进行比对实验，检测结果如图10所示，检测用时如表1所示。由实验结果可得出结论：与参照算法相比，本文算法对实验图片的总体检测用时最短，能够从实验图像的复杂环境背景中准确提取出平面反射靶的椭圆特征。

表1 不同检测方法用时比对Tab.1 Time comparison of different detection methods （ms）

图10 不同检测方法检测比对实验Fig.10 Comparison experiment of different detection methods

通过对各算法用时进一步分析可知，本文算法和CNED算法由于通过相对严格的约束条件排除非椭圆弧段组合，在椭圆拟合与筛选步骤均取得了更高的效率；本文算法和AAMED算法通过不同方法优化弧段聚类过程，使得该环节效率与传统遍历方法相比提升了一个数量级以上；与RHT算法相比，参与实验对比的边缘连接类算法效率普遍占优，更加符合实时应用要求。

为进一步考察本文算法的可靠性，通过改变被测目标类型、检测距离、环境光照、外界遮挡、检测方位、噪声干扰等测量条件，进行了进一步实验，结果如图11~16所示。其中图11为全反射靶球目标检测结果，图12为距离目标500 mm和1 000 mm时的检测结果，图13~14分别为由于反光不均匀、外界遮挡而导致目标椭圆特征不连续情况下的检测结果，图15为目标测量方位发生倾斜变化时的检测结果，图16为图像包含均值为0、方差为0.1的高斯噪声时的检测结果。检测结果表明，本文算法能够适应复杂场景下合作目标椭圆特征的检测需求，对常见干扰因素不敏感，鲁棒性较强。

图11 全反射靶球目标原始图像与椭圆特征检测结果Fig.11 Original image of SMR and detection result of its elliptical character

图12 不同距离靶标原始图像与椭圆特征检测结果Fig.12 Original images and the elliptical character detec‐tion results of target at different distance

图13 不均匀反射干扰下靶标原始图像及椭圆特征检测结果Fig.13 Original image of target under non-uniform re‐flection interference and its elliptical character de‐tection result

图14 外界遮挡干扰下靶标原始图像及其椭圆特征检测结果Fig.14 Original image of occluded target and its elliptical character detection result

图15 测量方位倾斜时靶标原始图像及其椭圆特征检测结果Fig.15 Original image of tilted target and its elliptical character detection result

图16 包含高斯噪声的靶标图像与椭圆特征检测结果Fig.16 Target’s image with Gaussian noise and its ellip‐tical character detection result

4 结 论

本文提出了一种在工业复杂场景中准确检测合作靶标椭圆特征的方法，该方法首先对预处理边缘图像进行边缘跟踪和弧段分割筛选分组，通过基于帕斯卡定理的邻接象限弧段匹配方法和基于关系矩阵的弧段聚类方法，对图像弧段根据椭圆匹配性实现有效聚类，优化了椭圆拟合环节效率，可获得更加准确可靠的检测结果。实验结果表明，本文方法对检测距离、光照条件、目标方位、噪声干扰等因素具有显著的抑制作用，在各种典型复杂场景条件下均能得到可靠的检测结果；该方法对分辨率为640×480 pixels的实验图像检测时间为183.2 ms，与YAED，CNED，AAMED等同类椭圆检测方法相比，用时分别缩短了72.9%，22.5%和16.9%，能够满足工业测量仪器现场搜索合作靶标性能需求。

本文算法图像预处理Canny运算边缘跟踪处理时间数倍于其它环节，未来将针对上述问题进行优化，进一步提高检测速度，同时面向激光跟踪仪、工业全站仪等典型工业精密测量仪器的合作靶标检测需求，进一步开展应用研究。