基于曲线拟合的随机圆检测算法

袁 坤，彭和平

（江汉大学智能制造学院，湖北武汉 430056）

0 引言

圆形是自然界中的常见形状，如硬币、篮球和交通标识等。圆检测是计算机视觉和模式识别领域的基本问题，在产品检测、生物信息提取等方面有广泛应用［1-2］。目前圆检测有许多算法，其中最常用的为Hough 变换及其改进算法。Hough 变换由Paul Hough［3］于1962 年提出，其原理是将二维图像空间的像素转化到三维参数空间，然后在累加器中对图像中的像素点进行投票累计。在Hough 变换圆检测中，二维空间中图像的每个像素点都要遍历三维空间［4］，导致计算量巨大、耗费大量内存，因此在多圆的精确检测中，经典Hough 变换有一定的应用局限性。目前，高效率、高准确度的圆检测算法是计算机视觉和模式识别领域亟需解决的问题之一。

1 相关研究

为解决传统Hough 变换圆检测算法运算量大、检测精度低的问题，国内外学者进行了相关研究提出一些改进算法。例如，文献［5］提出基于梯度的Hough 变换（Gradient Hough Transform，GHT）的同心圆检测算法，在一定程度上减小了计算量，提高了检测精度，但该算法需要提前设定被检测圆的半径范围，当图像背景复杂，如包含多个不同半径的圆时，算法的执行效率和识别准确度较低；文献［6］提出一种基于4 个点的随机圆检测算法（Randomized Circle Detection，RCD），依据迭代思想求取圆的参数。其从边缘像素点集中随机选取4 个点作为代理点，当4 个代理点均在同一圆模型边缘上时，即可得到该圆模型的参数。相较于Hough 变换及其改进算法，RCD 算法显著减少了运算量，对单一圆的检测效率及精度有很大提高。但当图像背景复杂或包含多个被检测圆时，4 个代理点来自于同一个圆的可能性很小［7］。此外，在构造圆模型后，该算法会利用全部边缘点对模型进行验证［8］，导致算法效率低且可重复性差。

为此，本文对基于4 个点的原始RCD 算法进行改进，提出一种基于曲线拟合的随机圆检测算法（Curve Fitting based RCD，CFRCD）。该算法结合概化算法与曲线拟合对检测边缘进行预筛选和分类，改进了原始RCD 算法因选取代理点不在同一个圆轮廓上而导致无效迭代次数过多的问题，提高了算法的执行效率。

2 CFRCD算法

2.1 边缘检测

边缘检测是图像预处理的重要环节，在一定程度上决定着后续检测的准确度。传统边缘检测算法，如Canny 边缘检测算法［9］通过图像平滑、梯度计算、非极大抑制及双阈值边缘标记等方法，可得到较好的二值边缘图像。然而，该算法需要设定双阈值，边缘检测结果易受阈值大小的影响。为避免实验结果的不确定性，本文采用无参数边缘绘制的EDPF（Edge Drawing Parameter Free）算法［10］，其是基于ED（Edge Drawing）算法［11］改进的一种实时、无参数的边缘分割检测算法，工作原理为将ED 算法参数设置为极值，首先检测图像中被称为锚点的像素点并对其进行连接，然后根据Helmholtz 原理对检测到的边缘段进行反向验证，从而消除无效检测边缘，仅留下有意义的图像边缘。相较于Canny 边缘检测算法，EDPF 算法可对图像边缘点进行有序标记，使检测边缘更为精确。测试图像及采用EDPF 算法处理后的边缘图像分别如图1、图2所示。

Fig.1 Test image图1 测试图像

2.2 曲线拟合

Fig.2 Picture after edge processing图2 处理后边缘图像

得到边缘检测图像后，对于互不连接的边缘，通过连通域分析以及图像形态学操作提取不同边缘。当图像边缘为类似测试图像中的遮挡圆时，则无法通过这些传统方法提取各个圆的边缘。采用CFRCD 算法，首先通过概化算法以一系列线段近似替代提取的边缘曲线，使用Visvalingam-Whyatt（V-M）概化算法［12］对提取的边缘进行曲线拟合。该算法原理为计算图像边缘点中的某一中心像素点与前后邻近像素点所构成的三角形面积，并与设定阈值进行比较，若三角形面积大于阈值，则分别对这3 个像素点构成的两像素区域各自取其中间像素点，再与之前中心像素点构成三角形并重复上述步骤，直至三角形面积不大于阈值为止。完成对边缘轮廓上的像素点标记后，通过线段连接相邻像素点完成对原有边缘的近似替代。图3（彩图扫OSID 码可见，下同）为采用概化算法处理后的图像。

Fig.3 Image after generalization algorithm processing图3 概化算法处理后的图像

2.3 圆弧提取

相邻线段之间夹角大小的变化可近似衡量圆弧的曲率变化，曲率变化大于设定阈值的点称为拐点。对于V-M概化算法处理后的边缘图像，选取任意两相邻线段ei、ei+1构造则两线段之间的夹角θi大小变化可近似表示曲线曲率大小的变化，其中θi的大小表示为：

设定一角度阈值θt，通过判断cosθi≤cosθt筛选出拐点，以拐点为分界进行边缘分割，并将分割后的边缘作为候选边缘设定构成边缘像素点数量阈值为ns，当候选边缘li构成像素点数量大于ns时，则标记为有效边缘并置于边缘集δ={li}中，从而剔除图像中的小边缘像素点和噪声点。测试图像设定角度阈值θt=25°，对图像进行拐点检测并去除拐点以分割边缘曲线。图4 圆圈处即为边缘拐点所在处。

2.4 圆检测

2.4.1 候选圆及圆弧筛选

对于提取的有效边缘集δ，以及任一有效边缘ζ=，需判断ζ是否为封闭边缘。将构成ζ的像素点集首尾元素之间距离di与设定封闭距离阈值ε进行比较，当di≤ε时，标记边缘ζ为封闭边缘，并置于封闭边缘集δ c中；否则，标记边缘ζ为非封闭边缘，并置于非封闭边缘集δs中。

对封闭边缘集δ c与非封闭边缘集δ s进行初步筛选，保留圆和圆弧边缘作为候选边缘，剔除非圆及非圆弧边缘。采取CFRCD 算法一次迭代，依次对每个边缘进行计算并筛选。为避免采样点距离过近以及取点偶然性影响算法检测结果，采用分区采样方法［14］，按照边缘将边缘点集分为等区间的S1、S2、S33个部分，具体如图5所示。

Fig.5 Picture of areal sampling图5 分区采样图

随机从3 个像素点区间中各取一点，分别表示为(x1，y1)、(x2，y2)及(x3，y3)，代入圆的方程中进行计算。采用参数a、b和r表示候选圆的相关参数，其中(a，b)表示候选圆圆心，r表示半径，计算公式分别为：

采用三点确定圆模型后，在该三点对应的边缘点集中随机选取一异于该三点的像素点(x4，y4)，并计算该像素点是否靠近模型圆的边界［15］。计算该点与模型圆圆心的距离d，并以该距离与模型圆半径作差求取绝对值，公式为：

Fig.4 Edge inflection point of the signed image图4 标记图像中的边缘拐点

对于式（5）中的距离d，设定距离阈值Td。若d≤Td，对于封闭边缘，判定为候选圆边缘并储存于圆边缘集Φc中；对于非封闭边缘，判定为候选圆弧边缘，并储存于圆弧边缘集Φa中；否则，判定该边缘为非圆边缘，并从δ c或δs中剔除。

2.4.2 圆及圆弧的验证

筛选后Φc与Φa中的圆及圆弧边缘需要进一步精确，基于CFRCD 算法通过代理点进行多次迭代。对于圆边缘，取边缘ζcc上等距的m个点，其中m≥3且m∈Ζ，m的取值应确保取点之间的最短距离不能过小，又不能因m数值过大而使运算量过大。可根据式（2）、式（3）和式（4）计算a、b与r，单个圆边缘迭代次数，则总迭代次数Ωc=nΤc。第i次迭代与第j次迭代结果的差值为：

式中，i，j=1，2，···，m且i≠j。对于Δa、Δb和Δr，设定阈值Ta、Tb和Tr。若对于全部的Δa、Δb和Δr有：

则边缘ζcc确定为圆边缘，并根据次迭代的参数结果求取均值得到圆参数a、b与r，表示为：

根据参数对圆轮廓进行标记，否则将边缘ζcc从Φc集中剔除。

对于圆弧边缘，采取基于CFRCD 算法的多个代理点进行自身迭代。选取各圆弧的两端点为既定点，在每条圆弧上随机取κ个点，对于每条圆弧，利用两端点及圆弧上的随机点进行计算。单条圆弧迭代次数为κ，总迭代次数为nκ。迭代完成后，将利用式（6）、式（7）求得的圆心半径差值小于阈值的圆弧归为同一类圆弧。

将分类后的圆弧划分为N 类，其中0 ≤N≤n且N∈Ζ+。若同一类圆弧中仅有一条圆弧，则对该圆弧进行自身代理点迭代；若同一类圆弧中包含多个圆弧，则将任一圆弧两端点与同类其他圆弧上的随机点组成代理点，直至完成所有圆弧间代理点的相互迭代。假设第i个同类圆弧所包含的圆弧段数目为ρ，则该类圆弧迭代次数为：

总迭代次数为：

同类圆弧完成迭代后，通过式（6）、式（7）、式（8）对圆弧组的圆心及半径数值进行精度优化，并根据得到的圆参数a、b与r对圆弧组确定的圆进行轮廓标记。

3 实验方法与结果分析

3.1 实验方法

为验证CFRCD 算法的可行性，利用C++程序语言搭配Opencv 4.1.0 视觉库针对多幅图像进行圆检测比较实验。程序开发环境为Visual Studio 2015，硬件环境为AMD Ryzen7处理器，主频率为1.8GHz，运行内存为16GB。

选取4 组图像进行圆检测测试，比较本文算法与GHT算法、RCD 算法对图像中圆轮廓的识别能力。

3.2 结果分析

如图6 所示，从左至右分别为原始图像，以及GHT 算法、RCD 算法和CFRCD 算法的检测结果。可以看出，GHT算法与RCD 算法对于图像中圆轮廓的检测存在误检与漏检现象，而CFRCD 算法能准确检测出图像中的圆轮廓，且多次检测结果一致。

将图6 中的4 组图像分别命名为图像1、图像2、图像3和图像4，采用GHT 算法、RCD 算法及CFRCD 算法分别对4 组图像进行10 次圆检测，并求取算法平均运行时间，结果如表1 所示。可以看出，对于同一图像，CFRCD 算法的运行时间稍大于GHT 算法，但远小于RCD 算法。虽然GHT 算法的运行速度较快，但其需要预设待测圆半径的范围，否则会大大增加运算时间，故其运行效率具有不确定性。当图像中干扰像素点或待测圆数量较多时，RCD 算法最优结果的抽样概率大大增加，计算量也随之大大增加［16］。

Fig.6 Original images，GHT，RCD and CFRCD detection results（from left to right）图6 原始图像以及GHT算法、RCD算法、CFRCD算法检测结果（从左到右）

Table 1 Execution times of three kinds of algorithm表1 3种算法的运行时间 （ms)

向真实场景中分别添加5%、15%、25%和35%的椒盐噪声，以验证CFRCD 算法的鲁棒性，结果如图7 所示。可以看出，随着噪声比例的增加，CFRCD 算法检测出的圆数量逐渐下降。为进一步考察CFRCD 算法的抗干扰性能力，分别向测试图像中添加8%、18%、27%和36%的椒盐噪声，结果如图8 所示。可以看出，随着噪声比例的增加，该算法检测出的圆数量亦逐渐减少。无论是自然场景还是测试场景，噪声均会影响CFRCD 算法的检测性能。

Fig.7 Robustness detection of CFRCD in real scenes图7 真实场景中CFRCD算法的鲁棒性检测

Fig.8 Anti-interference detection of CFRCD in test scenes图8 测试图像中CFRCD算法的抗干扰性检测

图9 为3 种算法在不同百分比噪声下对测试图像中圆的检测能力。可以看出，当噪声百分比大于10%时，RCD算法无法检测出圆；当噪声百分比大于18%时，GHT 算法无法检测出圆；当噪声百分比大于36%时，CFRCD 算法无法检测出圆。这是由于噪声比例过高时，图像边缘会变得很分散，检测难度增大。

与GHT 算法和RCD 算法相比，CFRCD 算法在一定噪声比例下仍具有较好的鲁棒性，能够较为准确地检测出圆轮廓，而其他两种算法随着噪声百分比的增加，检测结果出现较多错误圆。

4 结语

本文结合概化算法与曲线拟合算法对图像模型边缘进行分类并结合RCD 算法对圆形轮廓进行识别与标记。相较于传统圆检测算法，该改进算法能准确识别各种场景下的圆轮廓，在执行效率以及抗干扰性方面均有显著提升。然而较小的圆用概化算法经一系列线段替代后，相邻线段之间的夹角会较大而无法通过拐点筛选，故该算法可能无法检测较小的圆轮廓。后续将研究如何对较小圆轮廓进行检测，并进一步提高算法的抗干扰性能。

Fig.9 Circle detection ability of each algorithm under different percentages of noise图9 不同百分比噪声下各算法的圆检测能力