英语原文共 16 页，剩余内容已隐藏，支付完成后下载完整资料

EDCircles: 错误检测数量可控的实时圆检测器

Cuneyt Akinlar n，Cihan Topal

阿纳多卢大学 计算机工程系，埃斯基谢希尔26470，土耳其

关键词：圆检测；椭圆检测；实时图像处理；Helmholtz准则；NFA

摘要：本文提出了一种实时的无参数圆检测算法，该检测算法具有较高的检测精度，能够产生准确的结果。该算法利用了由无参数边缘检测算法（EDPF）产生的连续边缘，因此得名为EDCircles。首先通过EDPF检测给定图像中的边缘，然后将其转换为直线；再将被检直线连接成圆弧，通过两种启发式算法将它们连接为候选圆和近圆椭圆；再利用Helmholtz准则，基于对立推理的方法对候选圆和椭圆进行校验。我们通过实验证明了EDCircles算法具有较高的实时检测率（10-20毫秒可检测640~480幅图像），并能产生准确的结果，非常适合下一代实时视觉检测应用，如制造产品的自动检测，瞳孔检测，圆形交通标志检测等。

1 引言

对数字图像中圆形物体的检测是图像处理[1]和计算机视觉[2]中一个重要和常见的问题，特别是在产品的自动检测[3]，辅助矢量化线绘制图像[4，5]，瞳孔和虹膜检测 [6-8]，圆形交通标志检测 [9-11]等实际问题中都有着广泛的应用。

理想的圆检测算法不需要根据不同图像进行参数调整，同时需要具备较高的检测速度，可以准确检测出合成、自然或噪声图像中各种大小的圆，并能够降低甚至消除无效检测的数量。本文提出的圆检测算法可以很好的满足上述性能要求。

目前使用较广泛的圆检测技术是基于著名的Hough变换（CHT）[12-16]实现的，其原理是利用传统的边缘检测器（如Canny [17]边缘检测器），将边缘像素映射到三维Hough圆空间（x，y，r）后提取出包含某些边缘片段的圆。这种技术不仅检测速度慢、占用内存多，而且会在噪声干扰下提取错误，此外许多参数必须人为设定，因此应用受限。为了克服标准Hough变换的固有缺陷，出现了许多Hough变换的变体：如概率Hough变换[18,19]、随机Hough变换[20,21]、模糊Hough变换[22]等，此外还有基于Hough变换和假设过滤的方法[23-25]，一定程度上弥补了Hough变换的缺点，但计算上还是相当复杂。

除此之外还有几种随机圆检测算法，T.C.Chen等人[26]提出了一种随机圆检测算法RCD（randomized circle detection），其基本原理是从边缘图像中随机选取4个像素，用一种距离判据决定是否有圆存在，再通过取证环节判定候选圆是否是一个真正的圆，检测效果较好但速度较慢。K.Chung等人[27,28]对RCD算法做了改进，有效地提高了RCD算法的快速性和准确性。虽然新的GRCD-R，GLRCD-R等算法[28]的检测效果比较理想，但在方面实时性方面仍然存在着缺陷。此外RCD算法都需要传统边缘检测器（例如Sobel滤波器或Canny边缘检测器）检测出边缘图像，仍然需要提前对参数进行设置。

近年来，遗传算法不断被引入到圆与椭圆的检测中[29-36]，Ayala-Ramirez等人[30]提出了一种用于圆检测的遗传算法（GA），能够实现大多数圆的检测，但无法检测出小尺寸圆。Dasgupta等人[31-33]提出了一种用于圆检测的菌群自适应搜索算法ABFO，可产生比较理想的检测结果，但对噪声敏感。Cuevas等人利用离散差分进化（DDE）优化 [34]、声搜索（HSA）优化[35]和人工免疫系统优化技术[36]，提出了克隆选择算法（CSA）进行圆检测。虽然这些检测算法的效果比较理想，但难以满足实时性检测的速度要求，也同样需要对传统的边缘检测算法进行参数设置来检测边缘。

Frosio等人[37]还提出了一种基于极大似然估计的圆检测算法，该算法可以检测被遮挡一部分的圆物体，但需要预先知道圆的半径，这在很大程度上限制了该算法的应用。吴等人[41]提出了一种能够以7帧/秒的速度对640x480的图像进行圆检测的算法，但缺乏实验验证。张等人[38]提出了一种可用于实时人脸检测的椭圆检测算法。刘等人[39]提出了一种用于噪声图像的椭圆检测器，Prasad等人[40]提出了一种利用边缘曲率和凸凹度的椭圆检测器，虽然这两种算法检测效果较好，但都不适合实时应用。Vizireanu等人[42-44] 利用数学形态学对图像进行形状分解，从而识别图像中的不同形状和图案，虽然可以进行一般的特征提取，但难以满足实时性的要求。

Desolneux等人[60]最先提出利用对立推理的方法检测圆弧，在他的研究基础上[58]，Patraucean[45,46]提出了一种将LSD直线提取算法[63]拓展到圆弧和椭圆弧检测的自适应算ELSD[46]，在不需要任何参数的情况下检测给定图像中的圆弧和椭圆弧，同时利用Helmholtz准则[58]控制无效检测的数量。

本文提出了一种实时的无参数圆检测算法（10-20毫秒可检测640~480幅图像），该检测算法具有较高的检测精度，能够产生准确的结果，并且基于对立推理的方法，利用Helmholtz准则校验检测结果从而减少误判。该算法利用无参数边缘检测算法（EDPF）[48-53]产生连续边缘，因此命名为EDCircles。给定一幅输入图像，首先利用EDPF检测图像中的边缘，再通过EDLines[56,57]直线检测器将边缘像素连接成直线，然后利用两种启发式算法将它们连接为候选圆和近圆椭圆；再利用Helmholtz准则对候选圆和椭圆进行有效性校验。

2 EDCircles算法

EDCircles通过几个步骤完成提取圆和近圆椭圆的过程。先将提取到的直线段组合出可能的圆弧，再将圆弧拼接后检测圆和近圆椭圆。EDCircles算法的概述在算法1中给出，我们将在以下部分中展开详细说明。

算法1. EDCircles算法的步骤

1.通过EDPF检测边缘段并提取完整的圆和椭圆。

2.将剩余的边缘转换为直线段。

3.利用直线段组合出可能的圆弧。

4.将圆弧拼接为候选圆。

5.将剩余的圆弧拼接为候选的近圆椭圆。

6.利用Helmholtz准则对候选圆和椭圆进行校验。

7.输出剩余的有效圆和椭圆。

2.1 无参数边缘检测（EDPF）

给定一幅图像，EDCircles首先利用我们最近提出的实时边缘检测器Edge Drawing（ED）[48-51]检测图像中的边缘。传统的边缘检测器如Canny检测[17]首先识别图像中可能存在的边缘像素，并通过非极大值抑制、双阈值处理等步骤消除非边缘像素，与之不同的是，ED算法首先检测出图像中的锚点，再通过智能路由方法对锚点进行连接。因此ED算法不仅能像传统边缘检测器输出二进制图像，而且能够输出连续的像素链[49]。

ED算法中的许多参数需要人为设定，并需要根据图像类型的不同对参数进行调整，为了减少这一步骤，我们基于Helmholtz准则提出了一种实时的无参数边缘检测器（EDPF）[52,53]。EDPF是将ED算法中的参数设定为极限值，可以检测出图像中所有可能的边缘，但也会产生错误输出，因此需要根据Helmholtz准则对提取到的边缘进行校验。

图1（a）是一个大小为424times;436的灰度合成图像，其中包含一个被四个矩形截断的大圆，一个被三个矩形截断的小椭圆，一个小圆，一个椭圆和一个多边形。利用EDPF算法产生图1（b）所示的边缘，图中每种颜色代表不同的边缘，每个边缘都是连续的像素链。EDPF可在2.2 GHz Intel 2670QM CPU的PC上于3.7 ms内输出15个边缘，可以得到清晰且精确的检测结果。

每个边缘都对应着图中一个或多个对象的边界，虽然可以用单个边缘表示对象的边界，但是如图1（b）所示，每个对象也可以对应着多个边缘，例如大圆的边界分成了4个边缘片段，小椭圆的边界分成了3个边缘片段。检测结果取决于对象的结构、障碍物的数量和图像噪声，因此无法预先得知该算法如何对边缘进行分割。

图1.（a）样本图像（424 times;436）；（b）由EDPF提取的边缘（连续的像素链），每种颜色代表不同的边缘部分，EDP​​F在3.7毫秒（ms）内输出15个边缘；（c）近似边缘段的线。总共提取了98行。

从图1可以看出，图像中小圆、椭圆和多边形的整个边缘作为封闭曲线输出，即边缘从对象边界上的像素起围绕整个边界并在初始位置结束，边缘的首尾像素彼此相邻。这种封闭的边缘很可能是圆形，椭圆形或多边形的边界。因此，可以在完成边缘检测之后首先从所有的边缘找出封闭曲线，进而验证是否为封闭的圆或椭圆。

首先用最小二乘圆拟合算法[64]对封闭曲线进行拟合并计算拟合误差，如果均方根误差不超过某个阈值（例如1.5个像素），就把拟合圆作为候选圆。拟合误差较小并不能说明检测到了实际的圆，还需要利用Helmholtz准则进行校验，2.6节详细介绍了校验过程。

如果没有拟合出候选圆则进行椭圆拟合，利用文献[65]中的椭圆拟合算法拟合椭圆方程。如果均方根误差不超过某个阈值（例如1.5个像素），就把拟合椭圆作为候选椭圆，同样后续利用Helmholtz准则进行校验。如果上述圆和椭圆的拟合都失败了，则将该像素链从边缘片段列表中移除，不参与后续检测，否则需让该像素链和其他非闭合边缘一起进行进一步处理。

2.2 将边缘拟合成直线

由于圆都是由连续的直线近似得到的（如图1（c）所示），在完成封闭圆和椭圆检测后，剩余边缘片段被转化成直线，如下一节内容所述，这些直线可以通过简单的后处理步骤转换成圆弧。

直线检测器EDLines[56,57]介绍了直线拟合的方法，首先找到一条最小长度的直线段，之后检测剩余像素，当拟合误差不超过某个阈值（如1个像素）时对直线段进行延长，最后利用Helmholtz准则对每条直线段进行校验。但是在EDCircles算法中不进行直线校验，这是由于直线段的Helmholtz准则校验会滤掉许多较短的直线片段，而这对于尺寸较小的圆和椭圆的提取相当重要，因此 EDCircles 算法在此步不对任何拟合线段进行 Helmholtz 准则校验。

图1（c）显示了从图1（a）中提取的直线，可以看出圆是由一组连续的直线近似拟合得到的，我们将在下一节中介绍如何将连续的直线拟合成圆弧。

2.3 圆弧搜索

一个圆弧至少由连续三段转向相同的直线段组合而成，根据这一定义，我们通过判定相邻两线段之间的夹角以及直线段的转向搜索圆弧。假设某个边缘片段由连续三段或以上的直线段组成，如果相邻线段所夹锐角都在夹角阈值之间，而且线段之间的转向保持一致，我们就认为这些边缘有可能构成一个圆弧。

图2是由标记为到的18条连续直线拟合的边缘，将每条直线记作一个向量，通过计算向量的点乘可以得出两条连续直线之间的角度，通过计算向量的叉乘可以得出一条直线到下一条直线的旋转方向。图3（a）是图1（b）中到的11条连续直线段近似拟合的蓝色边缘，图3（b）中显示了11条直线段的细节，包括长度、直线间的夹角和转角，其中方向向左表示为“ ”，向右表示为“-”。

圆检测算法规定候选直线段必须转角方向相同，且两条直线段的夹角在一定的阈值范围内。如果夹角太小则认为两直线共线，不能构成圆弧，如果夹角太大则两直线可能构成矩形，通过对大量图像进行实验，最终设定夹角的阈值范围为6°~60°。

图2下方给出了上方图像中两条连续直线段间的夹角和旋转方向。、、、等小于低阈值或大于高阈值的角度标记为红色，其他角度根据转向的不同标记为蓝色或绿色，如果转向向左则标记为蓝色，转向向右则标记为绿色。

图2.（a）标记为到的18条连续直线拟合的边缘；（b）向量之间的夹角被标记为不同的颜色，如果夹角大于高阈值如、、（标为红色）或者夹角小于低阈值则不能组合成圆弧，如果三条及以上直线之间都转向相同则可以组成圆弧（标为蓝色或绿色）。

计算出夹角和转向之后，将三条及以上转向相同且夹角在阈值范围内的直线段进行组合，图2中到的直线段满足要求，则构成备选圆弧，到的直线段也构成一段圆弧。

EDCircles算法首先对整个满足要求的像素链进行圆拟合，若均方根误差不超过1.5 个像素宽度，则将该段像素链标记为“圆弧”；如果均方根误差超过了阈值，则从连续三段直线段开始，逐一添加进行圆拟合，直到均方根误差超过阈值为止，将阈值范围内的直线段组合标记为“圆弧”。利用该算法我们在图2中拟合出两端圆弧：由到组成的圆心为，半径为的弧和由到组成的圆心为，半径为的弧，在一副复杂图像中可拟合出上百条圆弧。

图3.（a）图1（b）中到的11条连续直线段近似拟合的蓝色边缘，并且标出了直线段之间的夹角；（b）图1（b）中直线段的详细信息。

图4为图1（c）中的直线段拟合出的圆弧，表1给出了圆弧的详细参数。每段圆弧都是大圆中按逆时针方向从起始角到终止角之间的一段，如是半径182.6，圆心坐标（210.6，211.3）的大圆中从91°~152°中61°的弧段。

图4.（a）图1（c）中的直线段拟合出的圆弧；（b）候选圆和椭圆。

表1. 圆弧段的详细参数

2.4 通过圆弧拼接进行圆检测

找到图像中所有的圆弧后进行圆弧拼接，由于最长的圆弧更接近一个整圆，因此首先将这些圆弧按照长度降序排列，从长的圆弧开始，找出半径和圆心坐标相近的圆弧作为候选。对于圆弧，首先搜索所有可能与之组合的圆弧，需要满足两个约束条件：（1）半径约束：弧和的半径差需要在某个阈值范围内，通常设置为25%

全文共22400字，剩余内容已隐藏，支付完成后下载完整资料

资料编号：[2766]