EDCircles: A real-time circle detector with a false detection control 翻译

论文名：EDCircles:一个带有错误检测控制的实时圆检测器

摘要

我们提出了一种实时的，无参数的圆检测算法，具有高的检测率，产生准确的结果，并控制错误的圆检测的数量。该算法利用了无参数边缘段检测器产生的连续(连通)边缘段集，即无参数边缘绘制(EDPF)算法;因此得名EDCircles。该算法首先利用EDPF算法对给定图像进行边缘分割，然后将边缘分割成线段。将检测到的线段转换为圆弧，使用两种启发式算法将圆弧拼接在一起，检测出候选圆和近圆椭圆。最后通过亥姆霍兹原理的反向验证步骤对候选对象进行验证，该方法消除了错误检测，只留下有效的圆和近圆椭圆。我们通过实验表明，edcircle工作实时(640 x 480图像的10-20毫秒)，具有高的检测率，产生准确的结果，非常适合下一代实时视觉应用，包括工业品的自动检测，瞳孔检测，环形交通标志检测等。

简介

数字图像中圆形物体的检测是图像处理[1]和计算机视觉[2]中一个重要且反复出现的问题，尤其在工业品自动检测[3]、线描图像辅助矢量化[4,5]、瞳孔和虹膜检测[6-8]、圆形交通标志检测[9-11]等自动化问题中有很多应用别人。
理想的圆检测算法对所有图像的内部参数都是固定的，即不需要对不同的图像进行参数调优，速度非常快(如果可能的话是实时的)，可以检测多个大大小小的圆，可以处理合成的、自然的和有噪声的图像，检测率高，准确率高，很少或没有错误检测。本文提出的圆检测算法满足所有这些性质。
传统上最流行的圆检测技术是基于著名的圆霍夫变换(CHT)[12-16]。这些技术首先使用传统的边缘检测器(如Canny[17])计算图像的边缘映射，将边缘像素映射到三维霍夫圆空间(x, y, r)，并提取包含一定数量边缘像素的圆。基于cht的技术不仅非常慢且需要内存，而且还会产生许多错误的检测，尤其是在存在噪声的情况下。 此外，这些方法有许多参数必须由用户预置，这大大限制了它们的使用。
为了克服基于cht的经典方法的局限性，人们提出了许多变种，包括概率HT[18,19]，随机HT[20,21]，模糊HT[22]等。也有基于HT和假设滤波的方法[23-25]。Alk这些方法试图纠正CHT的不同缺点，但仍然需要内存，在实时应用程序中使用很慢。
除了基于cht的方法外，还有几种随机化的圆检测算法。Chen等人[26]提出了一种随机圆检测(RCD)算法，该算法从图像的边缘映射中随机选择4个像素，使用距离准则来判断图像中是否存在可能的圆。然后，他们使用一个收集证据的步骤来测试候选圆是否是一个实数圆。RCD产生良好的结果，但速度较慢。最近，Chung等人[27,28]提出了高效的采样和细化策略，以加快RCD的速度，提高RCD结果的准确性。虽然新的RCD变种GRCD-R、GLRCD-R[28]具有良好的检出率和准确的结果，但距离实时性仍有很大差距。此外，所有rsd -变体都是在由传统边缘检测器(如Sobel滤波器或Canny边缘检测器)计算的图像边缘地图上工作的，这些边缘检测器有许多参数必须由用户设置。
近年来，遗传算法和进化计算技术在圆检测中的应用成为研究热点[29-36]。Ayala-Ramirez等人[30]提出了一种圆检测的遗传算法(GA)，该算法能够检测多个圆，但经常无法检测出小的或不完美的圆。Dasgupta等[31-33]开发了一种用于圆圈检测的群体智能技术——自适应细菌觅食优化(ABFO)。该算法具有良好的效果，但对噪声敏感。Cuevas等人使用离散差分进化(DDE)优化[34]、和谐搜索优化(HSA)[35]和克隆选择算法(CSA)[36]人工免疫系统优化技术进行循环检测。虽然这些进化计算技术具有良好的检测率和准确的结果，但通常需要多次运行来检测多个圆，速度较慢，不适合实时应用。与RCD算法一样，这些算法也适用于由传统的边缘检测算法预先计算的边缘地图。
Frosio等人[37]提出了一种基于最大似然的实时圆检测算法。该方法速度快，能够检测出部分被遮挡的圆形物体，但需要预先定义被检测圆的半径，这极大地限制了其应用。Wu等人提出了一种循环检测算法，该算法在640 x 480图像上运行7帧/s。作者声称获得了很高的成功率，但没有太多的实验验证来支持他们的说法。Zhang等人[38]提出了一种可以用于实时人脸检测的椭圆检测算法。Liu等人[39]提出了一种用于噪声图像的椭圆探测器，Prasad等人[40]提出了一种利用边缘曲率和凹凸信息的椭圆探测器。虽然这两种算法都产生了良好的结果，但它们速度较慢，不适合实时应用。
Vizireanu等[42-44]利用数学形态学对图像进行形状分解，利用图像的形态形状分解表示对图像中的不同形状和模式进行识别。虽然他们的算法很好地检测图像中的一般形状，但他们不适合实时应用。
有关反向圆弧检测的问题，请参见下文。最近，Patraucean等人[45,46]提出了一种无参数椭圆检测算法，该算法基于荒芜neux等人[58]的反向框架。作者扩展了Grompone von Gioi等人[63]的线段检测器(LSD)，在不需要任何参数的情况下检测给定图像中的圆弧和椭圆弧，同时利用Helmholtz原理[58]控制错误检测的数量。然后，他们使用提出的算法(命名为ELSD[46])来检测和识别Bubble Tags[47]。
在本文中，我们提出了一种实时(640 x 480图像上10-20毫秒)，无参数圆检测算法，具有高检测率，产生准确的结果，并有一个反向验证步骤，由于亥姆霍兹原理，让它控制错误检测的数量。该算法利用了我们的无参数边缘段检测器产生的连续(连通)边缘段集，即无参数边缘绘制(EDPF) [48-53];因此得名EDCircles[54,55]。给定一个输入图像，EDCircles首先使用EDPF计算图像的边缘段。接下来，使用线段检测器EDLines[56,57]将得到的边缘段转化为线段。然后将计算得到的线转换为圆弧，并使用两种启发式算法组合在一起，生成许多候选环和近圆椭圆。最后，通过Helmholtz原理验证候选结果[58-63]，该原理消除了错误检测，只留下有效的圆和近圆椭圆。

2. 提出的算法:EDCircles

EDCircles遵循几个步骤来计算给定图像中的圆。其基本思路是提取图像中的线段，将其转换为圆弧，然后结合这些圆弧来检测圆和近圆椭圆。EDCircles算法的大致轮廓在算法1中给出，我们将在以下部分详细描述EDCircles的每个步骤。
算法1 EDCircles算法的步骤。

1. 利用EDPF检测边缘段，提取完整的圆和椭圆。
2. 将剩余的边段转换为线段。
3. 通过合并线段来检测弧段。
4. 加入弧来检测圆候选。
5. 加入剩余的弧，以检测接近圆形的椭圆候选者。
6. 使用亥姆霍兹原理验证候选圆/椭圆。
7. 输出剩余的有效圆/椭圆。

2.1. 基于边缘绘制参数自由的边缘分割算法

给定一幅图像，EDCircles的第一步是检测图像中的边缘段。为了实现这一点，我们使用了我们最近提出的实时边缘/边缘分割检测器，边缘绘制(ED)[48-51]。与传统的边缘检测器不同，例如Canny[17]，它通过识别图像中一组潜在的边缘像素，并通过非最大抑制、滞后阈值、侵蚀等操作消除非边缘像素，ED遵循一种主动的方法，首先识别图像中的一组点，称为锚点，然后使用智能路由程序连接这些锚点;也就是说，ED实际上是在图像中绘制边缘。ED不仅输出与传统边缘检测器相似的二进制边缘图，而且输出结果为一组边缘段，每个边缘段是一个连续(连接)的像素链[49]。
ED有许多用户必须设置的参数，这需要针对不同类型的图像调优ED的参数。理想情况下，人们希望有一个实时的边缘/边缘分割检测器，它运行在一个固定的内部参数集的所有类型的图像，不需要参数调优。为了实现这一目标，我们最近将ED与一种基于亥姆霍兹原理的反向边缘验证机制结合起来[58-60]，并获得了一种实时无参数边缘分割检测器，我们将其命名为无参数边缘绘制(EDPF)[52,53]。EDPF的工作原理是在ED的所有参数的极值处运行ED，它检测给定图像中所有可能的边缘段，其中有许多假阳性。然后，我们通过亥姆霍兹原理验证提取的边缘段，它消除了错误检测，只留下感知意义的边缘段相对于一个反向方法。
图1(a)显示了一个424 x 436灰度合成图像，其中包含一个被4个矩形块遮挡的大圆、一个被3个矩形块遮挡的小椭圆、一个小圆、一个椭圆和一个任意多边形样物体。当将该图像输入EDPF时，产生了如图1(b)所示的边缘段。边缘图中的每一种颜色都代表一个不同的边缘段，每个边缘段都是一个连续的像素链。对于这幅图像，EDPF在2.2 GHz Intel 2670QM CPU的PC上仅在3.7 ms内输出15个边缘段。注意边缘地图的高质量，所有细节都清晰可见。
每个边缘段跟踪图中一个或多个对象的边界。虽然一个物体的边界可以被单个边缘段跟踪，但小圆、椭圆和多边形物体如图1(b)所示，也有可能一个物体的边界被多个不同的边缘段跟踪。这是大圆的情况，因为圆的边界是由四个不同的边缘段跟踪的，而小的受阻椭圆是由三个不同的边缘段跟踪的。结果完全取决于物体的结构，图像中阻碍和噪声的数量。也就是说，没有办法预先告诉边缘段如何跟踪给定图像中物体的边界。

从图1中可以看到，在某些情况下，比如小圆、椭圆和多边形，图像中物体的整个边界会以闭合曲线的形式返回;也就是说，边缘段从物体边界上的一个像素开始，跟踪它的整个边界，并在它开始的地方结束。也就是说，边缘段的第一个像素和最后一个像素是相邻的。如图1所示，这样的闭合边缘段很有可能沿着圆、椭圆或多边形的边界运动。因此，在检测边缘线段后的第一步，我们检查所有的边缘线段，选取闭合的边缘线段，看看闭合的边缘线段是否跟踪了一个圆或一个椭圆的整个边界。
闭合边缘段的处理遵循一个非常简单的思路:我们首先使用最小二乘圆拟合算法[64]将一个圆拟合到边缘段的整个像素列表中，并计算均方根误差。如果圆拟合误差，即均方根误差小于某个阈值(固定在1.5像素)，然后将该圆添加到候选圆列表中。圆拟合误差小并不意味着这条边就是一个圆;它还只是一个候选，需要通过亥姆霍兹原理的圆验证才能返回为一个真正的圆。第2.6节描述了圆验证的细节。
如果圆拟合失败，那么我们尝试拟合一个椭圆到边缘段的像素。我们使用[65]中描述的椭圆拟合算法，它返回一个形式为Ax2 + Bxy +Cy+Dx+ Ey +F= 0的椭圆方程。如果椭圆拟合误差，即均方根误差小于某一阈值(本文算法将其固定为1.5像素)，则将该椭圆添加到椭圆候选列表中，该椭圆也需要通过亥姆霍兹原理的验证，然后作为真实椭圆返回。
如果边缘段被接受为一个圆或一个椭圆候选，它将从边缘段列表中删除，不再进一步处理。否则，该边缘段将与其他非闭合边缘段一起用于进一步加工。

2.2. 将边缘段转换为线段

在去除闭合边段后，将其作为候选圆或椭圆，将剩下的边段转换为线段(本文其余部分简称线段)。这个步骤的动机来自于观察到任何圆形形状都是由一组连续的线逼近的(如图1所示)，这些线可以很容易地通过一个简单的后处理步骤变成圆弧，在下一节中描述。
将边缘段转换为一组直线遵循我们的直线检测器EDLines[56,57]中给出的算法。其思路是，从一条满足一定直线度标准的短线开始，只要均方根误差小于一定阈值，即1像素误差，就延长这条线。线段提取的细节参考EDLines[56,57]，我们使用Helmholtz原理对检测后的线段进行验证，以消除无效检测。但是，在EDCircles中，我们在检测后不验证行。这一决定的原因是我们观察到，由于Helmholtz原理的线段验证算法通常会消除许多短线段，这可能对图像中小圆的检测有价值。因此，与EDLines不同的是，我们不排除任何检测到的线段，而是使用所有检测到的线段进行进一步的处理和检测弧。
图1所示为从图1(a)所示图像中提取的直线。显然，圆形物体可以用一组连续的线来近似。在下一节中，我们将描述如何通过处理连续的直线将这些直线转换成圆弧。

2.3. 圆弧检测

我们把一个圆弧定义为至少有三条连续的、向同一方向转弯的直线的集合。根据这个定义，我们可以检测出如下的圆弧:给定一组构成边缘段的线，简单地遍历这些线，计算连续线之间的角度和从一条线到另一条线的转弯方向。如果至少有三条线转向相同的方向，并且线与线之间的夹角处于某些阈值之间，那么这些线可以形成一个圆弧。
图2说明了一个假设的边缘段被18个连续的线段近似，标记为I，到l18。为了计算两条连续直线之间的夹角，我们只需将每条直线作为一个向量，并计算向量的点积。类似地，要计算从一条线到另一条线的方向转弯，我们只需计算矢量叉乘，并使用结果的符号作为转弯方向。

图3(a)给出了图1(b)中右侧蓝色垂边段被11个连续的标号为v1到v11的线段逼近的结果。图3(b)显示了11条线的细节:它们的长度、连续线之间的夹角以及从一条线到另一条线的转向方向，其中“+”表示左转，“-”表示右转。

我们的圆弧检测算法是基于以下思想的:一组线要成为潜在的圆弧候选线，它们必须具有相同的转弯方向(向左或向右)，并且连续线之间的夹角必须在一定的阈值之间。如果角度太小，我们假设这两条线共线，所以它们不可能是弧的一部分;如果角度太大，我们假定这些线是严格旋转物体的一部分，如正方形、矩形等。对于我们当前的实现，我们将低角度阈值固定为6°，高角度阈值固定为60°。这些数值是通过对含有各种圆形物体的各种图像进行实验得到的。
图2的底部描绘了图2顶部所示的边缘线段的连续线之间的夹角，以及从一条线到另一条线的方向转向。小于低角度阈值或大于高角度阈值的角，如01、θ2、θg和916，被标记为红色;所有其他角度都根据方向的变化被涂成蓝色或绿色。具体来说，如果下一行向左转弯，这个角度就被涂上蓝色，如果下一行向右转弯，那么这个角度就被涂上绿色。
这些数值是通过对含有各种圆形物体的各种图像进行实验得到的。在计算了角度和方向转弯信息之后，我们简单地遍历一个边缘段的线，寻找一组至少由3条连续的线组成的集合，这些线都在同一个方向转弯，并且从一条线到下一条线的转弯角度在的低角度和高角度阈值之间。在图2中，线v3到v7满足我们的准则，是一个潜在的候选弧。类似地，v10到v16行构成了另一个候选弧线。
给定一组至少有三条满足弧候选约束条件的直线，我们首先尝试使用[64]中的圆拟合算法将一个圆拟合到构成这些直线的所有像素。如果圆拟合成功，即均方根误差小于1.5像素，则只需将提取的圆弧添加到圆弧列表中，就完成了。否则，我们从仅由三行组成的短弧线开始，通过拟合一个新的圆[64]逐行扩展它，直到均方根误差超过1.5像素。此时，检测到的圆弧被添加到圆弧列表中，我们继续处理其余的线来检测更多的圆弧。利用该算法，我们在图2中检测出两条弧:$v_3$到$v_7$的直线形成的圆弧A1，圆心为($X_{CA1},Y_{CA1}$)，半径为$r_{A1}$。同样，$v_{10}$到$v_{16}$的直线形成了圆弧A2，圆心为($X_{CA2},Y_{CA2}$)，半径为$r_{A2}$。在一个由许多边缘段组成的复杂图像中，我们将有数百条弧。


图4显示了从图1的线计算出的弧，表1给出了这些弧的详细信息。圆弧横跨大圆(圆心X，圆心Y，半径)之间的部分(起始角，结束角)。假设圆弧在大圆上从起始角逆时针移动到终点角。以Az为例，圆心坐标(210.6,211.3)，半径= 182.6的大圆从91°到152°共覆盖61°。

2.4. 利用弧连接检测候选圆

计算完弧后，下一步是将弧加入候选圆中。要做到这一点，我们首先将所有的弧按照长度降序排序，并首先开始延长最长的弧。这个决定的动机来自于观察到最长的弧是最接近一个完整的圆，所以它必须在其他弧之前延伸和完成一个完整的圆。在弧线的延伸过程中，我们的想法是寻找具有相似半径和近中心的弧线，并收集可能与当前弧线结合的候选弧线列表。
给定一个弧线Ai延伸成一个完整的圆，我们检查所有检测到的弧线，并生成一组可能与a连接的候选弧线。我们有两个判定弧连接的标准:(1)半径差约束:Ay与候选弧A的半径差必须在某个阈值内。其中，如果Az的半径小于A1半径的25%，则取Az作为加入的候选;否则A2不能与Aj连接。例如，如果Ay的半径为100，那么所有半径在75到125之间的弧都可以作为弧连接的候选弧。(2)中心距离约束:A1的中心与候选弧A2的中心之间的距离必须在某个阈值内。具体来说，我们要求Aj和A2的中心之间的距离不能超过Al半径的25%。例如，如果Ay的半径为100，那么所有圆心距离Ay圆心25像素以内的圆弧都可以作为圆弧连接的候选点并且它们也满足半径差构造。
图5为圆弧连接检测圆时可能出现的场景。在图5(a)中，我们说明了一个情况，所有潜在的候选弧都满足中心距离约束，但有一个不满足半径差约束。这里，A1是将A2、A3和A4作为弧连接的潜在候选者来扩展的弧。如图所示，所有弧的中心都非常接近;即A2、A3和A4的中心到A1中心的距离都在中心距离阈值rt以内，对于半径差约束，只有A3和A4满足，而A2的半径不在半径差范围内。因此在图5(a)中，只选取了弧段A3和A4作为与A1连接的候选。
在图5(b)中，我们展示了一个情况，所有潜在的候选弧都满足半径差约束，但有一个不满足中心距离约束。这里A1是要扩展的弧，A2、A3、A4是弧连接的潜在对象。如图所示，所有圆弧的半径都非常接近，因此都满足半径差约束。对于中心距离约束，只有A2和A4满足，而A3的中心没有达到中心距离阈值rt。所以在图5(b)中，只选择A2和A4作为与A1连接的候选弧。
在计算完候选弧之后，下一步是将它们逐个与扩展的弧A1结合起来，通过将一个新圆拟合到组成两个弧的像素上。我们不再以随机的顺序尝试连接，而是从任意一个端点都离A1的任意一个端点最近的弧开始。这个决定的动机来自于观察到，如果同一大圆有不止一条弧，最好从最接近延伸弧A的弧开始连接。以图5(a)为例，我们先将A1与A4连接，再将A3连接。类似地，在图5(b)中，我们将首先连接A1，然后连接A2，然后连接A4。

当圆弧A1与其他圆弧在同一大圆上展开后，我们在最后一步决定是否使扩展的圆弧成为候选圆弧。在这里，我们认为，如果一个弧的跨度至少是其大圆周长的50%，那么我们就认为这个弧是一个圆。否则，弧是留下近圆椭圆检测。以图5(a)为例，当A1与A4和a连接时，延伸的弧将会跨越其大圆周长的50%以上。所以延伸的弧线应该是圆的候选。然而，在图5中，当A1、A2和A3连接在一起时，我们观察到延伸的弧没有跨越其大圆周长的至少50%，即θ1 +θ2 +θ3 <π;因此，延伸的弧线不能作为圆的候选。计算总弧跨度是通过简单地查看组成连接弧的像素总数与新拟合圆周长的比率来完成的。如果该比例大于50%，则将延伸的弧作为候选圆。
为了举例说明上述观点，下面是如何处理图4(a)和表1中详细描述的七条弧:我们首先以A1，最长的弧，作为要延长的弧，A2, A3, A4, A5, A6和A7作为剩余的弧。由于A2、A3、A4的半径都在A1半径的25%以内，且它们的中心距离都在中心距离阈值以内，所以只选取这三条弧作为加入的候选弧。由于A2的端点最接近A1，我们接下来将A1和A2连接起来(参见图4(A))。在A1和A2连接后，延长的弧现在将与A3连接，因为A3的端点现在最接近延长的弧。最后将A4连接起来。由于最终延伸的弧线覆盖了其大圆的50%以上，因此被视为候选圆。同样地，剩下的下一个最长的弧是A5，所以我们尝试用A6和A7作为弧列表中唯一剩下的弧来扩展A5。唯一可以与A5连接的候选弧是A7，因为A6的半径不在A5半径的25%以内。

2.5. 基于弧连接的候选近圆椭圆检测

上一节介绍的算法处理的是完美圆候选的检测。但这种算法无法检测出接近圆形的椭圆。众所周知，根据相机的视点不同，圆看起来会有轻微的椭圆。因此，圆检测算法对图像中不完美圆形物体的检测就显得尤为重要。
用于椭圆检测的圆弧连接与2.4节中介绍的用于完美圆检测的圆弧连接非常相似。给定要延伸成椭圆的弧线Aj，我们检查剩余的弧线并生成一组可能与A1连接成椭圆的候选弧线。对于圆弧连接，我们采用与2.4节相同的两个准则，但约束条件有所放宽:(1)半径差约束:如果Az的半径与A1的半径相差50%，则取Az作为连接的候选;否则Az不能和A连在一起。例如，如果Ay的半径为100，那么所有半径在50到150之间的弧都可以作为弧连接的候选弧。(2)中心距离约束:我们要求A1和A2的中心的距离不能超过A1半径的50%。举个例子，如果A1的半径是100，那么所有圆心在内的弧。以A1中心的50个像素点作为圆弧连接的候选点，假设它们也满足半径差约束。

图6为圆弧连接椭圆检测的可能场景。在图6(a)中，我们展示了一个情况，所有潜在的候选弧都满足中心距离约束，但有两个不满足半径差约束。这里，A1是将A2、A3、A4、A5作为弧连接的潜在对象来扩展的弧。如图所示，所有弧的中心都非常接近;即A2、A3、A4、A5的中心到A中心的距离均在中心距离阈值rr内。对于半径差约束，只有A3和A4满足，而A2和A5的半径不在半径差范围内。所以在图6(a)中，只选取了弧段A3和A4作为与A1连接的候选。
在图6(b)中，我们展示了一个情况，所有潜在的候选弧都满足半径差约束，但有两个不满足中心距离约束。这里A1是要扩展的弧线，A2、A3、A4、A5是弧线连接的潜在对象。如图所示，所有圆弧的半径都非常接近，因此都满足半径差约束。对于中心距离约束，只有A2和A4满足，而A3的中心和A5的中心都不在中心距离阈值rt以内，因此在图6(b)中，只选择A2和A4作为与A1连接的候选弧。
计算完候选圆弧后，下一步是使用[65]中的椭圆拟合算法，在组成两个圆弧的像素上拟合一个新的椭圆，将它们逐个与扩展的圆弧A1合并。如果均方根误差小于1.5像素，连接成功;否则,它就会失败。我们不再以随机顺序尝试连接，而是从任意端点都离A1的任意端点最近的弧开始。这个决定的动机来自于观察，如果有多个弧是同一大椭圆的一部分，最好从最接近扩展弧A1的弧开始连接。以图6(a)为例，我们先将A1与a连接，再将A4连接。同样，在图6(b)中，我们会先将A1与Az连接，再将A4连接。
当圆弧A1与其他圆弧在同一大椭圆上展开后，我们在最后一步决定是否使扩展的圆弧成为椭圆候选。在这里，我们认为，如果延伸的弧跨越了它的大椭圆的周长的至少50%，那么我们就使这个弧成为一个椭圆候选。否则，电弧将被排除在进一步加工。以图6(a)为例，当A1与As和A4连接时，延伸的弧跨度超过其大椭圆周长的50%。所以延伸的弧线是一个椭圆候选。然而，在图6中，当A1、A2和a连接在一起时，我们观察到延伸的弧没有跨越其大椭圆的至少50%的周长，即θ1 +θ2+θ3 < π。因此，延伸的弧不被认为是一个椭圆候选。计算总弧跨度是通过简单地查看组成连接弧的像素总数与新拟合椭圆周长的比率来完成的。如果该比例大于50%，则将扩展的弧作为椭圆候选。
为了举例说明上述观点，下面是如何处理图4(a)和表1中详细描述的其余三个弧，A5, A6和A7:由于A5是最长的弧，我们尝试以A6和A7作为候选扩展A5。由于A5和A6的半径都在A5半径的50%以内，且中心距离都在中心距离阈值以内，因此将两段弧都作为候选弧。然后我们尝试连接A5和A6，因为A6的端点最接近A5(参见图4(a))。最后，将A7连接起来。由于最终延伸的弧线覆盖了其大椭圆的50%以上，因此被认为是一个候选椭圆。
图4(b)显示了图1(a)图像的所有圆和椭圆候选点在图像顶部以红色叠加。我们有3个圆和2个椭圆的候选对象，其中小圆、小椭圆和小多边形物体在算法的第一步成为候选对象，因为它们的边缘段将它们的整个边界勾画成闭合曲线;在第四步，大圆将A1、A2、A3和A4弧合并成一个完美的圆，成为候选弧;第五步，将圆弧A5、A6和A7合并成一个椭圆，遮挡椭圆成为候选椭圆。现在，所有5个候选者都必须通过Helmholtz原理(下一节将对此进行描述)的验证，然后才被返回为真阳性检测。

2.6. 用亥姆霍兹原理对圆和椭圆进行验证

在前两节中，我们描述了EDCircles如何将弧线连接成圆或椭圆候选。仅仅因为一些弧可以连接成圆和椭圆并不意味着所有的候选都是有效的检测。因此，作为最后一步，EDCircles使用圆和椭圆验证算法来消除无效检测，只返回有效的圆和椭圆。
在讨论EDCircles使用的圆和椭圆验证算法之前，我们首先需要定义亥姆霍兹原理，为其反向验证框架奠定基础，并描述如何使用它来检测给定图像中有意义的对齐，即线段。然后将直线验证技术应用于圆和椭圆验证。
亥姆霍兹原理简单地说，一个几何结构要在感知上有意义，这个结构(分组或格式塔)在随机情况下的期望必须很低[59,60]。这是一种相反的方法，其中对象被检测为背景模型的异常值。如凄凉等[60]所示，一个合适的背景模型是所有像素都是独立的。他们表明这种模型最简单的是高斯白噪声。换句话说，在高斯白噪声图像[60]中看不到有意义的结构。

solneux等人使用Helmholtz原理在给定图像中寻找意义对齐，即线段，而不需要任何参数[61]。他们的想法是计算给定图像的水平线方向场(与梯度方向场正交)，并寻找一组具有相似水平线方向的连续像素。图7(a)显示了图像的水平线方向场，其中构成线段的对齐像素标记在矩形内。作者对对齐的定义如下:点(或线段)Pand Q方向相同，即当角度( p)和角度(Q)在p/π= π/n度内时，对齐精度为p= 1/n。solneux等人指出，“根据心理物理学[68]和数值实验，n的实际值从32到4不等，一般来说，考虑更大的n值是无用的。”[60]。在EDCircles中，我们将n的值固定为8，因此，p，两个像素之间的精度或方向精度，等于p= 1/8 = 0.125，两个点对齐(或p对齐)，如果它们的角度是pπ= π/8= 22.5°。
使用2 × 2掩模计算一个像素(x, y)的梯度大小和水平线角度，如下[61]:


其中，I(x.y)为输入图像在像素(x, y)处的强度，g(x, y)为梯度幅值，角(x, y)为水平线角。作者在[61]中指出，使用这样一个简单的梯度算子的原因是为了减少计算梯度的依赖性，从而尽可能地保持像素独立性。
为了具体验证Helmholtz原理的正确性，solneux等人定义了线段的虚警数(NFA)[61]:设L为长度为n的线段，在大小为n × n像素的图像中，至少有k个点的方向与L方向对齐。定义L的NFA为[62,63]

其中$N^4$为Nx N幅图像中潜在线段的数量。这是由于线段有两个端点，每个端点可以位于图像的$N^2$像素的任何一个点;因此，共$N^2$ x $N^2$= $N^4$条线段。二项尾计算中使用的概率p是像素的水平线角度与线段对齐的精度。
如果NFA(n,k) <ϵ，事件(在本例中是线段)被称为有e意义的。solneux等人[59-61]建议将ϵ设置为1，这对应于每个图像一次错误检测。给定这些定义，对线段进行验证:对于长度为n的线段，计算线段上每个像素的水平线角度，计算对齐像素的个数k，然后计算NFA(n,k)，当NFA(n,k) ≤1时接受该线段有效。否则，拒绝线段。
Desoulneux等人的上述线段验证框架已成功应用于最近的两个线段detectors;请等等，你知道他的名字由Akinlar等[56,57]设计的EDLines，以验证检测到的线段，消除错误检测。
在本文中，我们采用了上述solneux等人的线段验证框架来进行圆和椭圆检测。这个想法非常简单:就像一组具有水平线角与线段对齐的连续像素组成一个线段，一组具有水平线角与圆对齐的连续像素组成一个圆。图7(b)所示为图像的水平线方向场，其中构成圆的对齐像素标记在两个圆内。为了定义像素与圆的对齐方式，我们只需修改像素与线段对齐方式的定义:如果P与P处圆的切线对齐，则圆边界上的像素P与圆对齐。回想一下，如果角度( P)和角度(L)之间的距离在P * n度内，则点P和线段L与精度P对齐。假设圆在给定点P处的切线为T，我们可以简单地使用这个定义来对齐点和圆;也就是说，如果P和圆对齐，角§和角(T)之间的距离必须在P * m度以内。
图7是圆边界上几个点的梯度方向(垂直于水平线角)，有些点与圆p对齐，有些点与圆p对齐。灰色三角形表示理想梯度方向与观测梯度方向之间的公差锥。如果观测到的梯度方向在圆锥内部，则假设该点与圆对齐，否则假设该点与圆不对齐。
我们没有将圆和椭圆作为两个不同的格式塔进行验证，而是将问题简单地表述为椭圆验证问题，因为圆本质上是长轴和短轴长度相等的椭圆。考虑到这一点，我们将线段的虚警数(NFA)的定义适用于一个椭圆:设E是一个圆周上有n个点的椭圆，在大小为Nx n个像素的图像中，至少k个点的方向与E对齐。定义E的NFA为

其中$N^5$表示nxn图像中潜在椭圆的总数。这是因为一个椭圆有5个自由度，即它的中心坐标、长轴、短轴和方向;因此，共有$N^5$省略号。
给定这个NFA定义，我们验证一个圆/椭圆(简称圆)如下:对于一个长度为n的圆，计算每个像素沿圆的水平线角度，并计算对齐像素的数量k。计算NFA(n,k)，如果NFA(n,k) ≤ϵ，则认为该圆有效;否则将被拒绝。需要指出的是，我们在验证步骤中按照反向框架的要求对原始的未滤波图像执行梯度计算。
上述比较中的ε (ϵ)表示背景模型下的期望检测次数。也就是说，如果将高斯白噪声图像输入到算法中，我们最多可以得到ϵ次检测。我们按照荒芜neux等人[59,60]的建议将ϵ设为1，这对应于每幅图像一次错误检测。
虽然观测到的水平线角是由上面给出的2x2掩模计算的，但计算圆/椭圆周长上一点的理想像素角需要计算该点的切线。如果水平线角与切线角在p *π = 0.125 *180 = 22.5°范围内，则对齐;否则就不是。

2.7. EDCircles的复杂性

给定一幅Nx N的图像，EDCircles的第一步是EDPF的边缘检测，这是一个O($N^2$)运算。然后将检测到的边缘段转换为线段，这是对边缘像素个数的线性时间操作。假设我们有L段线段，将线段转换成弧段同样是对线段数量的线性时间操作;也就是说,O (L)。如果我们现在有A条弧，算法的其余部分首先涉及到对弧的长度排序，这可以在O(A log A)中完成，然后从排序列表中取出剩余最长的弧，在O(A)中找到候选弧，并使用贪婪启发式将候选弧与目标弧连接起来。这是一个关于弧数的二次运算;也就是说,O ($A^2$)。

3.实验

为了测量EDCircles的性能[54,55]，我们采集了包含圆形物体的合成图像和自然图像，并将它们输入我们的算法。然后，我们显示检测到的圆圈和EDCircles的运行时间。我们强调EDCircles是参数无关的，因为它只有一组内部参数，用于本文和EDCircles演示网站http://ceng.anadolu.edu.tr/CV/EDCircles/Demo.aspx上的所有图片。

图8显示了EDCircles和cvHoughcircles在五幅含有circular对象的合成和自然图像上的性能。运行时间是在带有2.2 GHz Intel 2670QM CPU的PC上测量的。第一列为原始图像，第二列为EDPF检测到的边缘片段。在第三列中，候选的圆圈和椭圆(本文其余部分中的圆圈简称)用红色覆盖在图像的顶部。请注意，有许多虚假的候选圆圈，特别是在眼睛和交通标志图像上可见。第四列显示EDCircles的最终结果输出。注意，由于Helmholtz原理，圆验证算法消除了所有无效的圆候选，只留下有效的圆检测。例如，在Image4中有29个候选圆圈，其中17个是错误检测;因此，EDCircles只输出12个有效的圆。请注意，检测到的圆圈大小不一，从很小到很大。
图8中的第五列是OpenCV基于CHT的圆检测算法cvHoughCircles检测到的圆。之所以选择OpenCV[66]进行比较，是因为OpenCV实现的eneric图像处理和计算机视觉算法在文献中是最快的，并且被广泛使用，而且OpenCV是开源的，任何人都可以重复相同的结果。我们注意到cvHoughCircles有许多参数(类似于文献中许多其他的圆检测算法)，必须由用户为每个图像预先提供。为了获得cvHoughCircles的结果，我们首先用s¼1:0的5 x 5高斯核平滑图像。然后我们尝试了许多不同的参数，并在图8中呈现了最佳结果。表3列出了用于获取cvHoughCircles结果的参数，如图8所示。从表3中可以注意到，cvHoughCircles需要一组不同的参数来为每个图像获得最佳结果。由于只有一组默认参数，cvHoughCircles要么无法检测到许多有效的圆，要么产生更多的错误检测，这在本文中没有展示。


从图8中可以看出，EDCircles实时检测到大部分有效圆，而cvHoughCircles不仅检测不到很多有效圆，还会产生很多错误检测。这在Imagel中更加明显，cvHoughcircles执行时间接近1秒，输出71个圆圈，其中许多是错误的检测。我们再次强调，EDCircles是无参数的，也就是说，它对所有图像使用相同的内部参数;然而，要用cvHoughcircles获得最好的结果，用户必须通过试错为每个图像提供一组不同的参数。
图8中最后一行Image5需要特别注意，这是一个来自Sweedish traffic sign数据库的环形交通标志[67]。由于相机的视角，这个圆形标志显示为一个椭圆而不是一个圆。从图8中可以看到，EDCircles正确地检测到了这个椭圆圆;然而，传统的环形检测器，如cvHoughcircles，可以检测到三个不同的环形，但没有一个能正确地代表交通标志。
表2对图8中每个图像的EDCircles运行时间进行了剖析，并与cvHoughcircles的运行时间进行了比较。显然，对于典型的640 x 480摄像机输入尺寸，EDCircles是实时运行的，EDPF的大部分时间花在边缘分割检测上，而不是圆圈检测和验证上。还要注意，EDCircles比cvHoughcircles快14倍，这可能是经典CHT算法最快的实现。
接下来，我们将EDCircles与[26]中首次提出、最近在[27,28]中改进的随机圆检测(RCD)算法进行比较，在该算法中，作者讨论了不同的RCD变体，并给出了名为GRCD-R的变体的结果。不幸的是，这个算法没有公开的实现。因此，我们从作者的原始论文中提取测试图像及其结果[28]，将测试图像输入EDCircles并比较结果。
图9和图10分别为[28]获取的10张测试图像和GRCD-R生成的结果，以及EDCircles生成的结果。Chung等人指出，GRCD-R结果的运行时间是在3 GHz Intel E8400 CPU[28]上获得的。为了公平地比较GRCD-R和EDCircles的运行时间，我们在2.2 GHz的Intel E4500 CPU上运行EDCircles，这也是一个类似于E8400的Core 2双核CPU，但根据CPU基准测试，它的时钟速度较慢，CPU评级较低。
从图9和图10的结果可以清楚地看出，EDCircles在“五子棋”和“五子棋”中除了一些光线反射外，检测到大多数有效的圆圈“稳定球”图像和“五子棋”图像的中心球，运行速度平均比GRCD-R快5倍。图9和图10的10张图片，GRCD-R和EDCircles的执行时间对比见表4。需要注意的是，GRCD-R的执行时间只包括边缘检测后的圆检测，而EDCircles的执行时间既包括EDPF的边缘检测，也包括接下来的圆检测和验证。考虑到EDCircles至少有一半的运行时间花在边缘段检测上，并且EDCircles运行在较慢的CPU上，因此EDCircles实际性能比GRCD-R要好于表4所反映的性能。
还需要注意的是，EDCircles可以检测到图像中各种大小的圆，而GRCD-R无法检测到许多有效的圆。这在图10的“logo”和“speaker”图像中表现得更加明显，GRCD-R只检测到较大的圆，而EDCircles则检测到许多半径或大或小的圆。
EDCircles的一个缺点是在边界模糊的圆圈周围进行多个圆圈检测。这在图9的“硬币”和“蛋糕”图像中表现得更为明显，EDCircles检测到两个圆围绕着两个不同的硬币，两个圆围绕着三个不同的圆形物体。请注意，这些物体的边界周围有阴影，这些阴影被EDPF检测到，并被edcircle变成圆圈。GRCD-R没有检测到相同物体周围的多个圆圈的原因可能是GRCD-R使用的边缘图比较干净，没有把这些阴影作为边缘。由于我们不知道GRCD-R计算圆所使用的边缘图，所以我们无法在这个意义上对GRCD-R和EDCircles进行公平的比较。
为了评价EDCircles的精度，我们对图9和图10所示的10幅测试图像进行传统的圆形霍夫变换(CHT)[12]运算，得到地面真值结果。为了使CHT结果尽可能准确，我们将横坐标、纵坐标和半径的粒度设置为一个像素的精度。表5显示了每个测试图像中，CHT检测到的每个圆参数与GRCD-R和EDCircles检测到的每个圆参数的平均差值。从结果可以看出，EDCircles虽然没有GRCD-R那么精确，但精度是亚像素的。
在接下来的实验中，我们测量了edcircle在探测近圆形椭圆物体时的性能。正如我们之前指出的，根据相机的视角，圆形物体可能会在图像中呈现出略微椭圆形。一个好的圆检测器应该能够处理这种情况。

图11展示了EDCircles在四幅图像中检测近圆形椭圆物体的性能。其中两幅图像来自瞳孔检测应用程序;另外两个来自瑞典交通标志数据库[67]，包含几个环形交通标志。请注意，所有圆形物体，由于相机的视角，在图像中显得略微椭圆，已检测到没有错误检测。我们想强调的是，EDCircles不是一般的椭圆检测算法，也不打算成为一个。相反，EDCircles试图检测由于相机的视角而看起来略显椭圆的圆形物体。
非正式地，我们可以说EDCircles尝试检测长轴不超过短轴两倍的椭圆。这是由于第2.5节中所述的圆弧连接启发式算法，该算法只在圆弧半径相差不超过50%的情况下将两个圆弧连接在一起。如果一个圆形物体由于相机的视角而显得过于椭圆，EDCircles将无法检测到它。EDCircles网站[55]上显示的任意椭圆检测大多是由于椭圆的整个边界被检测为单个闭合边缘段。
图12分析了edcircle的几个失败案例。第一列显示了一组紧密同心圆，分成八个部分，这引发了EDCircles的弧连接启发式。从结果可以看出，在某些情况下，EDCircles错误地将外圆和内圆的弧线连接在一起，造成了外圆的一半和内圆的一半。这与edcircles使用的贪心join启发式有关。回想一下2.4节，当EDCircles试图扩展一条弧线时，它会生成一组候选弧线，并将当前扩展的弧线与端点最近的候选弧线连接起来。如果连接成功，则立即连接弧，并且以后不会分离连接的弧。这是一种贪心启发式，选择它是出于性能考虑。虽然这种启发式方法在很多情况下都能很好地检测出圆，但当同心圆被划分为两个或多个区域时，它就会失效，如图12所示。在“下水道盖”的自然图像中也可以观察到类似的问题，EDCircles再次将来自外圆的弧与来自内圆的弧连接起来。 图12第一列和第二列的图像说明了EDCircles的另一个弱点;检测小的分割圆的失败。请注意，在这两幅图像中，EDCirdes都没有检测到图像中心的小圆圈。这与EDCircle的弧生成策略有关。回想2.3节，生成的弧线至少有三条线在同一方向转弯，且满足角度约束，在小圆内一般不满足，检测失败。图12的第三列显示了三个边界模糊的血细胞，检测要么失败，要么产生不完美的结果。在物体边界模糊的情况下，edcircle使用的边缘分割检测器EDPF会产生粗糙的边缘分割，无法转化为圆弧，检测失败。图12的最后一列显示了一个螺旋和EDPF检测到的圆圈。当螺旋旋转时，EDCircles会产生许多弧线，这些弧线组合在一起形成图中所示的圆圈。我们再次看到内圆的弧线和外圆的弧线连接在一起。由于亥姆霍兹原理的验证也不能消除这些错误的检测。
我们的最后一个实验是测量EDCircles在噪声图像中的性能。为此，我们获取一幅包含若干小圆和大圆的图像，向图像中添加不同程度的高斯白噪声，并将图像提供给EDCircles。
图13展示了在包含一个大圆和几个小圆的样本图像上，随着高斯白噪声量的增加，EDCircles的性能。注意，随着噪声的增加，对小圆的检测开始失效;


直到 σ = 60高斯噪声时，只检测到大圆。增大噪声会导致检测完全失败，如图所示。检测失败的原因是，随着噪声的增加，圆的边界被许多短边缘段逼近，而不是在噪声较小的图像中少数长的边缘段。这意味着近似圆形边界的弧线将是短的，不能连接在一起，以弥补圆。请注意，在所有图像中都没有错误检测，这也是非常重要的。我们还观察到，在有噪声的图像中，edcircle的运行时间会增加。原因是增加了边缘分割检测

由EDPF时间。随着图像中噪声量的增加，EDPF需要更多的时间来计算边缘段，因为许多像素开始成为潜在的边缘元素。在边缘检测之后的圆检测在所有图像中保持相当稳定。
图14显示了在不同尺度下分析噪声很大的图像(包含σ = 100的高斯噪声)的结果。在全尺度下，没有任何结构被检测到，尽管它们对人类观察者是可见的。这是因为人类视觉系统进行了多尺度分析，能够检测到强噪声中的结构。以一半和四分之一的分辨率运行edcircle，我们看到现在检测到了几个圆圈。我们得出这样的结论:当存在强噪声时，去噪或放大步骤有助于EDCircles检测到许多有效的圆。

4. 结论

EDCircles是一种实时的、无参数的圆检测算法，它是通过对我们的无参数边缘分割检测器(EDPF)检测到的边缘进行后处理来实现的。EDCircles首先将每个边缘段(一个连续的像素链)转换成一组线段。然后将线段转换为圆弧，并使用两种启发式算法将其连接成候选圆和近圆椭圆。在最后一步，使用亥姆霍兹原理对所有候选圆进行验证，从而消除错误检测，只留下有效的圆检测。在这篇论文中展示的实验(以及读者可能希望在http://ceng.anadolu.edu在线执行的其他实验)。tr/CV/EDCircles/Demo.aspx)的测试结果表明，EDCircles具有较高的检测率，良好的准确性，运行速度快，只产生少量错误检测或不产生错误检测。我们希望edcircle能广泛应用于自动化等实时自动化任务中产品检验，瞳孔检测，环形交通标志检测，以及类似的应用。

致谢

我们非常感谢匿名审稿人的深刻评论，这极大地帮助了本文的发展。我们也感谢土耳其科学技术研究委员会(TUBITAK)对这项工作的支持。111 e053。

参考文献

[1]…