英语原文共 8 页，剩余内容已隐藏，支付完成后下载完整资料
摘要：圆检测的传统霍夫变换是强大的，但对于上一个世纪的电脑，它太慢了且需求的内存过大。随着计算机硬件的快速发展，霍夫变换现在是可以被计算机接受的。改进圆检测的霍夫变换是有价值的。本文。我们提出了一种用于圆检测算法的使用计算机辅助计算的新型霍夫变换，他通过曲率估算来确定圆。曲率预估计避免了对所有点的计算，让算法能够更快，更准确地找出圆。和传统的霍夫变换相比，这种方法更具有实际操作价值，并且消耗的时间更少。它消耗的时间大约是传统霍夫变换的1/8。在交通信号灯的图片检测中，检测出了91.25%部分的圆。这种圆检测算法能够在复杂情况下检测曲率不同的圆。
- 介绍
在计算机视觉和模式识别领域，圆检测是一个重要的问题。在自然界中，圆是最常出现的形状。望远镜下的天体和显微镜下的细胞都是圆形；甚至许多日常生活中水果也是圆形。不仅如此，更多的人造物品都被设计成圆形，比如交通信号灯，警告牌，篮球和足球。这些圆形物体包含了丰富的信息。在大量的机器视觉应用中，我们需要找出圆形物体中的信息。一个例子是交通信号灯或者相机校准。圆的检测是理解圆形物体中包含的信息的第一步。
大多数的圆检测算法都是基于霍夫变换。标准圆霍夫变换需要巨大的内存并且消耗大量的时间来计算。研究者尝试改善它。Davies将梯度方向纳入考虑范围，只计算梯度方向上像素的累加器结果。Kimme et al从一个 2-D累加器中识别出了圆，并用变换滤波器加速了霍夫变换。这些改进工作需要比如半径之类的先觉条件。否则，这些计算将消耗很多时间且需要恒大的内存。测试的效果主要取决于半径的信息是否准确。更糟糕的是，这些算法在复杂情况下的多圆检测会失效。因为半径较小的圆会被较大的圆所淹没。
另一方面，研究人员也提出了随机霍夫变换，必要的步骤有：随机为求圆选取三个点，然后检测这三个圆是不是在同一个合适的圆上。有许多可以改进的地方。江随机选取了四个点并且检查之中的所有三个点的情况。于和巍在同一个弧线上选取三个点，缩小了合适的边缘范围。黄和李直接根据有相似弧度的点求到了圆。De Marco et al 也考虑了弧度来改善随机霍夫变换。冈萨雷斯采取了哈希图的方法加速随机霍夫变换的搜索程序。这种算法是高度随机的。试想我们从有着复杂纹理的图像中随机选取三个点，这三个点在同一个圆上的概率是很小的。我们需要不断失败并尝试直到这三个点是取自同一个圆上。成功地寻找一个圆需要花费很长的时间。更糟糕的是，由于随机霍夫变换的随机性，检测的结果是不稳定的。另一种圆的检测方法是基于弧的。Kim et al 用一种最小正方形拟合一段圆的方法来检测圆。Akinlar和Topal给出了一种非常快速的基于弧的检测方法。霍兹海姆原理被用来消除错误的圆。
本文提出了曲率辅助的用于检测圆的霍夫变换，它能够自适应地检测圆心和半径。这种霍夫检测圆的方法可以在复杂情况下检测不同半径。和经典圆检测的一些方法相比，这种方法更可行且消耗的时间更少。
本文接下来的部分按下面的顺序组织：第二部分一步步描述这种用到曲率的霍夫圆检测。实验结果在第三部分中展示并讨论。最终，第四部分总结了本文。
2
在几何里，曲率检测了曲线方向改变的程度。换句话说，它检测了一条曲线和直线有多不同。和图一展示的一样，曲率的倒数是曲率半径，也就是相切圆的半径。如果点在圆上，它的曲率半径应当是圆的半径。根据这个公式，我们提出了这个算法，接下来将会一步一步描述算法剩下的部分。
2.1 边缘检测
首先，图像的边缘被提取出来。和其他的算法一样，CACD（霍夫圆检测）算法也是对图像的边缘处理。所以在进行下一步之前边缘的检测是必要的。Canny边缘检测是一个选择。Canny边缘检测的主要步骤包括：图像平滑，梯度计算，非极大值抑制，通过两个阈值来追踪边缘。详情见canny1986年的论文。在边缘检测后，我们得到了一幅二值图像。
2.2 曲线追踪
在边缘检测后，我们通过连通性分析来从边缘分割的结果中确定曲线。如果任意两段曲线的末端是靠近的，那么我们就把他们间的缝隙填充，并将它们算为一段曲线。这里归类的标准是缝隙间的大小不能超过一个像素。一般来说，由很少的点组成的曲线一般是由噪声产生的或者是一些无关紧要的细节。它们需要被剔除。这里由十个像素点组成的曲线都被抑制了。最终，确定的曲线有着如下的形式：
这个公式一个一个点地表明了点的坐标，线i是由n个点所组成的，坐标分别是（）,()hellip;()
2.3 曲率半径估计
当我们得到一段曲线的时候，我们可以计算每一个点的曲率。根据（HEamp;Yung,2004）文献，对于每段曲线，高斯模糊是必要的，模糊不仅可以抑制曲线上的毛刺，而且也计算了子像素的曲率。曲率的计算公式如下：
g(u,sigma;)是一个二维的高斯核，u是中心，sigma;是偏差。*,,,,分别是的一阶和二阶导数，是f和g的卷积
我们需要得到曲率的倒数作为半径的估计。值得一提，如果曲率为0时，我们不能找到他的倒数。如果曲率很小时，它的曲率就会非常大，这样半径就会远大于图片尺寸，这些情况就不计入考虑。所以由噪声产生有着很大曲率的像素点，对应的半径就很小。这些点也被抑制了。半径的估算公式如下：
m为图像的最大尺寸
圆弧的曲率半径估计在图2中表示。我们可以看到真实的圆的半径有21个像素点，曲率半径估计结果并不精确。这只是一个粗略的结果。但是，就和本文接下来的内容所讲的，这些粗略的结果足够用来进行圆检测了
2.4 通过分层叠加来寻找圆心
为了避免不同圆间弧线的干扰，我们将半径分类（每一类都是半径的范围），并计算每一层的积分。因为量化错误和噪声干扰，曲率不能够被准确地估计。因此，在同一个圆上的像素会有着不同的曲率半径。如图图二里表示的，它们也可能有着相同的范围，该层的大小应该慎重决定。
为了避免同一个圆上的点被分到两个不同的层，每个层都应该和它相邻的层有着重叠的部分，比如[8,20]的领域范围是[13,33]
在我们的理解里，起始的三个叠加层是根据经验来确定的。它们是[3,15][8,20]和[13,33],从第四层开始，层的产生都是自动的。第i层表示成[],下层边界比上层的增量是
,当上边界确定为,所以第四层是[20,35]，而第六层是[34,51]，等等。我们假设最大半径为图像的最小大小。比如，如果图像的360*480，最大的半径为360。搜索程序在分层的最低范围超过范围[0,360]时将会结束。
对于每一层，曲率半径超过相应范围边缘将被忽略。我们计算剩下像素点在分层的和，就像图3显示的。因为我们不知道哪里是圆的中心，每个像素都被计入沿着梯度方向的支持区域。在像素点和每一个支持区域的中心之间距离就是预计的曲率半径。我们可以想象，每个圆上的点将会支持这个圆心，所以，真正的圆心将会得到比其他区域更高的值。圆心是求和的极大值。我们通过阈值来寻找特殊点，每一组特殊点的峰值就是所求的圆心。
2.5 半径估计
对于每一个圆心的候选点，我们计算在一定范围内的半径直方图。直方图的条目是在特定圆上的边缘点的数量。处于公正的考虑，直方图应该由距离圆心的距离标准化。半径直方图的峰值就是真正的半径。
2.6 检查圆心所用的证据收集
不能确定圆是否存在，只有圆的初步估算被求得。进一步检查需要测试是否有足够的边缘点在潜在的圆上。如果在圆上有足够的边缘点我们就认为证据是足够的，并认为潜在的圆是真的。如果不是这样，我们就因为缺少证据而忽视这个未确定的圆。需要指出的是，半径更小的圆更容易出现假圆，因为半径小的圆只要很少的像素点作为证据。这里我们设定对小的圆设定更高的阈值。通过分析实验结果我们通过如下公式来设定阈值：
在0le;ble;2，0le;ale;b，的情况下，b决定了整体的阈值大小，a决定了大半径和小半径的不同阈值。
和前面提到的一样，层的附近有重叠的区域，所以同一个圆可能被检测出两次，为了消除重复，我们就不将类似的圆加入记录。
整个的检测算法在图算法一中被贴了出来。
算法1：
0.输入图像
1.图像降噪和平滑
2.canny边缘检测
3.弧线检测
4.半径估计
5.FOR 每段线段
计算梯度方向的求和和判断曲率
通过分析求和结果找出圆心
通过半径直方图找出半径
记录可能的圆的参数
ENDFOR
6.FOR 每个可能的圆
IF有足够的点在圆上且没有重复
记下这个圆为真实的圆
ENDIF
ENDFOR
输出所有真圆的参数
检测结果的中间结果在图4中被给了出来。图4（a）是原始图像有10个标记的圆，4对同心圆。所以一共有6个不同的圆心。它们被用红色的序号标示。图4（c）是边缘检测的结果，图4（d）是边缘的弧度。图4的（e）-（h）是判断不同圆的累加和数组。在图4（e）是半径范围的累加器数组。在图4（e）中最高的峰值在圆心3处。还有一些更低的峰值，但是没有足够高的值被识别为圆心。图4（f）是范围[20,35]。圆心4,5,6在数组里被检查出来。三个峰明显可见，很难会被干扰。图（4）是范围[34,51]范围内的累加器数组。圆心1被检查出来，最高峰在圆心1的位置出现。其他的峰值也可以看到，但他们的值都很小。图4（h）是范围[104,156]的累加器数组。圆心2在这个范围内被检测出来。没有发现干扰。
3．实验结果
在这一部分，实验结果表明我们的算法非常有效。方位霍夫变换被作为对比。在3.1部分，两种算法都被用交通信号灯的图片测试。我们使用roc弧线对两种算法进行测试。统计偏差（SD）被定义为计算累计圆心的显著性，SD的比较是在干净的和噪声数据间比较的。在3.3节，对两种算法运行时间进行比较。最后再3.4节算法测试了一些实际图像，除了OHT算法，测试结果好比较了OPenCV和其他的算法。
我们比较了CACD算法和OHT算法，为了公平起见，OHT也是和CACD在各层上完成的。
3.1 ROC弧线
图像数据是从网上下载的，他们是交通标志图像。 29交通标志图像从互联网上下载到组成一个数据集。圆手动标记，如果我们能找到在图像和边缘图都最像圆的一部分，它被标记为一个圆。 279个圆被标记在29幅图像。
为了评估检测算法的性能，接收器工作特性（ROC）由曲线表示，ROC的水平轴是误报率，纵轴是检出率。
但是我们发现很难说明在图像里有多少个不是圆的图形。所以我们选择了部分的ROC,直方图的横坐标是由错误个数组成的。
图6 给出了不同方法下不同错误的ROC曲线。我们可以发现，随着错误警报的增加，CACD和OHT的检出率都在增加。当错误警报小于20或者大于40的时候，CACD的检出率远远高于OHT.当假警报数量在20-40间时，两种方法的检出率是相近的。所以，我们可以认为CACD性能比OHT好得多。
AUC(ROC)被定义为曲线下面积的比值。它代表检测精度，AUC越大，检测的效果越好。这里OHT的AUC值是0.8894，这已经足够好了，但是CACD的AUC达到了0.9125，比OHT好多了。
它是合理的，这减少了中的假警报数。设计将边缘点分层，且仅计算曲率半径落在该层中的点的集合。至于OHT，尽管它将边缘点分层，但它计算所有层中所有点的集合。不同的层中的点可能形成假峰，这常被误认为是圆心。这些假圆心会导致许多假警报。这就是为什么OHT方法得到的假警报比CACD方法多的原因。
3.2圆心显著性测量
为了进一步说明CACD的优越性，定义统计偏差为圆心显著性的量度。统计偏差表示在累积数组中圆心与其他点的不同。对于任意累积数组A，累积值A（i，j）表示有多少边缘像素表明（i，j）为圆心。如2.4节所示，圆心的积累值要远远大于其他位置。（i，j）的统计偏差定义为
其中，a（i，j）为（i，j）的积累值，整个计算器A的标准方差。
图7（a）有6个不同的圆心。它们被用红色标记了出来。我们在检测过程中记录最大统计偏差，如图7（b）所示。如图，CACD的统计偏差明显高于OHT。数量上来说，CACD的统计偏差是OHT的1.5到2.2倍。很明显，CACD算法的圆心比OHT的更显著。因此用CACD算法更容易检测到圆心。
此外，在含噪图像中也可检测统计偏差。为了实施有针对性的检查，我们将“盐和胡椒”噪声加入到边缘检测结果中。以一定概率添加或删除边缘像素是等价的。图8（a）表示在含3%噪声时的检测结果。图8（c）表示两种算法的的统计偏差，CACD的统计偏差依旧明显高于OHT。数量上来说，CACD的统计偏差是OHT的1.4到2.2倍。在图8（b）中，噪声更为密集，噪声密度为10%。图8（d）表示两种算法的的统计偏差，CACD的统计偏差平均依旧明显高于OHT。数量上来说，CACD的统计偏差是OHT的0.95到2.4倍.很明显，无论噪声密集与否，CACD的统计偏差都高于OHT。用CACD算法更容易检测到圆心。
3.3算法效率
性能比较后，我们要研究算法的效率。在3.1节中，这两种算法用由29张图片组成的数量集进行了测试。两种算法都是通过MATLAB 2008实现的，为了避免不同的实现细节，这两种算法的计算部分都有相同的程序。检测所需的时间如图9所示。平均而言，CACD需要461.2s检测出图片中所有的圆，而OHT需要3758.8s，这几乎是CACD的8倍。
对曲率半径的预估计可以缩短计算时间。事实上，曲率半径的预估计从两方面避免了无谓的累积计算：首先，不同于OHT计算所有半径范围，CAC
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[29242]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
