基于hough变换的圆检测

基于hough变换的圆检测内容摘要：

文章，但就象 Inprise(原 Borland)的 OWL框架的淡出一样， MFC的淡出也是早晚的事。 如果 MFC青春永驻，微软的开发人员也不会 “ 私自 ” 开发出基于 ATL的 WTL呀。 当然，WTL 的地位不能和 MFC 比，它并不是微软官方支持的框架，封装的功能也相当有限。 但至少也反衬出了 MFC存在的不足。 小结 Visual C++是可视化的 开发工具 ,改变了传统的编程手段 ,使得用户可以直接在用户界面良好的可视化开发环境中进行工作 ,它集成了许多有用的工具和功能 ,从而大大提高了应用程序的开发效率。 中国图象图形网 第四章 基于 HOUGH变换的圆检测 研究意义 HOUGH变换于 1962年在美国作为专利被发表至今已有三十多年了。 由于具有一些明显优点和可贵性质 ,它引起了国内外许多学者和工程技术人员的普遍关注。 专家们对 HOUGH变换的理论性质和应用方法进行了深入广泛的研究 ,并取得了许多有价值的成果。 由于立体，运动分 析，三维物体和识别与定位等都依赖于图像边缘提取等前期工作，因而今年来它越发受到人们的普遍重视。 本文所述的是基于 HOUGH变换勾画出目标物体的圆弧边缘，使观察者能够一目了然；圆弧边缘还蕴含了丰富的内在信息（如方向，阶跃性质，形状等），是图像识别中提取图像特征的重要属性。 然而 ,当参数空间超过两维（比如圆检测）时 ,HOUGH变换的时间消耗和所需存储空间的急剧增大使得这种变换仅仅在理论分析上可行。 虽然目前已提出了许多方法，但这仍然是一个有待解决的公认问题。 曲线检测方法综述 利用 HOUGH变换对曲 线进行检测的方法比较繁杂。 在这我们以对椭圆的检测为例： 基于椭圆和圆的对称性 ,对传统的霍夫变换检测曲线方法进行改进 ,提出分三步快速检测椭圆和圆的方法 :(1)利用椭圆的几何对称性 ,快速确定可能的形心 ,生成相应子图 ,并滤除图像中的噪声。 (2)在各子图中由边界点梯度向量和候选形心坐标 ,获得椭圆旋转角和长短轴比率。 (3)根据椭圆参数方程确定椭圆的长短轴 ,并验证所检测到的椭圆。 实验结果表明 ,该方法有效地降低了霍夫变换参数空间的大小和运算时间 ,提高了检测精度 ,实现了椭圆特征的快速提取。 基于 HOUGH变换的圆检测 本文所要研究的圆检测是基于 HOUGH变换的圆检测，下文将具体介绍 HOUGH变换的原理，应用以及基于 HOUGH变换的圆检测的实现。 此外，本文还还假如相应的例子进行补充并详细列出相应的程序。 HOUGH 变换的原理 经典 Hough变换的实质是对图像进行坐标变换（如 将图像空间中的一点变换为参数空间中的一条直线 ） ,使变换的结果更易于识别和检测，也就 是将图像空间的具有一定关系的象元进行聚类 ,寻找能把这些象元用某一解析形式联系起来的参数空间累积对应点。 举例 将直线方程由直角坐标转换为极 坐标形式 ,转换后的结果 :直角坐标系下的一个点在极坐标下成为一条曲线 ,如图 1所示。 而直角坐标系下的一条直线在极坐标下便成为一族有公共交点的曲线 ,如图2所示 这样 ,识别直线时在变换平面上寻找具有某种特性的某些点就比在图像平面上直接识别图形更为简单。 然后 ,根据变换规则进行相应的反变换便得到其相关几何参数。 中国图象图形网 下面简述 Hough变换的过程 : 设 XY平面内一条直线 ,其方程为 : y=ax+b (1) 其中 :a为斜率 ,b为截距。 那么我们也可以 以 a!b为变换空间 ,作如下变换 : b=ax+y 方程的形式虽然改变了 ,但其参数的意义并未改变，变换的结果使直角坐标系中的一个点成为“截距 斜率”空间中的一条直线 ,而直角坐标系中的一条直线成为“截距 斜率”空间中的一族有公共交点的若干直线。 为了正确识别和检测任意方向和任意位置直线 ,就必须解决垂直线的斜率无限大这一问题 ,在Hough变换中采用了极坐标变换 :将 XY平面的图像变换到 QH平面处理。 直线方程为 : Q=xcosH+ysinH (2) 其中 :Q为原点到直线的距离 ,H表示该 直线的法线与 X轴的夹角。 变换结果如图 1,2所示 ,在图 2中所有曲线都交于一点 ,该点坐标值 (Q,H)即直线的参数 ,利用该变换的最大优点便是抗噪能力强 ,缺点是运算量大 ,内存开销也不小。 基于同样的思路 ,可以进行圆 !椭圆 !抛物线等图形的识别 ,处理方法相同 ,只是参数空间的维数增大导致内存开销增大 ,现有的众多图像处理书籍中都有相关描述 ,在此不在敖述 HOUGH变换的圆检测的算法实现 为了尽可能减少参与 HOUGH变换的点数和降低积累阵列的维数，以此提高 HOUGH变换的效率，因此在变换之前一般要进行预处理。 中国图象图形网 预处理 a利用边缘算子对原图像进行边缘抽取。 b对于图像场景中的各物体的边缘轮廓象元进行骨架化。 骨架化的方法有多种〔 2,4,5〕 ,这里不赘述。 由于我们是针对圆检测的 ,图像中圆形物体的轮廓骨架应为闭合的 (即使不闭合对该算法的实现也没影响 )。 用方向链码来表示轮廓骨架 ,并从骨架上某一点 A开始按顺时针方向延骨架移动 ,与 A相隔 n个点取 B点。 将 A点与 B点用直线相连接 ,再取与 B点相隔 n点之处为 C点 ,并将 B点与 C点用直线相连接。 再在与 A点相距 m个点之处设置 D点 ,重复上述操作得 E,F点并按上述方法连成 直线。 如此操作下去 ,直到回到最初的启始点附近。 这些连接线就成为骨架圆周上的弦的子集 ,如图 2(a)所示。 d对上述各直线求出各自的垂直平分线 ,如图 2(b)所示。 在与图像映象的累积阵列进行增值操作。 事实上 ,并不需要画出各直线和它们的垂直平分线 ,可利用图 2(a)的 A,B,C点的坐标值求出 AB和BC两线段的中点坐标值 (x1,y1),(x2,y2)即 : x1=(xb+xa)2 y1=(yb+ya)2 (7) x2=(xc+xb)2 y2=(yc+yb)2 (8) 并可求出通过这两点的法线方程 : (xx1)(xbxa)+(yy1)(ybya)=0 (xx2)(xcxb)+(yy2)(ycyb)=0 (9) 解此方程组可得出两直线的交点 ,在与图像映象的二维累加阵列中对与该交点对应的单元进行增值操作。 在对各直线均完成此类操作后 ,统计累加阵列中各存储单元的累加值。 最大者即为圆心坐标。 各点到圆心坐标距离的 均值为 r。 即 : r=(∑ [(xix0)2+(yiy0)2]12)n(10) 上述算法有以下优点 : (1)由于进行 HOUGH变换之前先进行了边缘抽取及二值化 ,选择合适的阈值能使参与变换的象元数目大大降低。 (2)由于变换前先将图像轮廓象元实行了骨架化 ,若背景噪声并非太大 ,骨架化后物体的轮廓应是闭合的 ,这非常有利于进行图像分割。 (3)在物体轮廓骨架中按一定的间隔来选择边缘点构成连接弦 ,这样可根据工程中的实际时间限制调整间隔以提高变换速度。 (4)这里积累阵列是二维的 ,可大大节省变换时所用的存储空间。 中国图象图形网 这种变换算法依然保持着传统 HOUGH变换的许多优点 ,对图像中的背景噪声不敏感。 另外 ,以上分析都是假设被检测物体的边缘骨架曲线是闭合的。 实际上 ,即使被检测物体边缘的图像残缺 ,只剩下一段弧或几段弧时 ,仍能得到很好的结果。 这种情况可参考图 3(a)与图 3(b)。 本文提出的预处理是通过 4遍历先对原图像进行边缘抽取，找到种子点（ SEED），再在此基础上进行霍夫变换。 HOUGH变换 假设希望在图像平面 (XY平面 )考察并确定一个圆周。 令 {(xi,yi)i=1,2,3,。 ,n}为图像 中欲确定圆周上的点的集合 ,而 (x,y)为集合中的一点 ,它在参数坐标系 (a,b,r)中方程为 : (ax)2+(by)2=r2(1) 显然该方程为三维锥面 ,对于图像中任意确定的一点均有参数空间的一个三维的锥面与之对应。 对于圆周上的任何点集合 {(xi,yi)},这些三维锥面构成圆锥面簇 ,如图 1所示 : 若集合中的点在同一个圆周上 ,则这些圆锥簇相交于参数空间上某一点 (a0,b0,r0),这点恰好对应于图像平面的圆心坐标及圆的半径。 HOUGH变换在计算上将参数空间 进一步分割为累加器单元 A（ i,j,k），如图（ 2）所示，并使累加器单元置零。 根据方程 (ax) (ax)+(by)( by)=r*r 对参数作相应的循环，如果一个 a(o)值得到相应的 b(p),r(q),就令 A(o,p,q)=A(o,p,q)+1. 最后我们对每个累加器进行比较，找到值最大的累加器，该累加器所对应的参数值（ a,b,r）就是我们在 XY平面上所要求的圆心及半径。 中国图象图形网 流程图 开始 对所需变量进行声明 预处理（找到种子点） 进行 HOUGH 变换 返回值 结束 b r a 中国图象图形网 对结果的分析 本次设计所达到的效果：（ 1）在一幅有多个简单图形的画面，如图（一）所示中找到其中的圆，如图（三）所示；（ 2）在一幅有较多噪声（如一些与圆弧较接近的曲线）的图如图（二）所示中找出相应的圆，如图（四）所示； 图（一 ） 图（二） 图（三） 图（四） 使用我们提出的算法仍基本保留着传统 HOUGH的优点。 对图像场景中的干扰不敏感 ,在圆周残缺不全的情况下仍能正确检测 .由于在预处理中实现了用链码表示图像中物体 ,各物体分割方便，提高了圆心坐标测量的精确度。 HOUGH变 换的应用 经典 Hough变换主要针对直线的检测 ,它将画面上所有前景点进行相同的变换 ,将变换平面上各点看作一个个累加器 (点与点的距离取决于变换所取步长的大小 ),原图像平面上各点变换后所得曲线在变换平面上每经过的某点 ,便将该点计数器值加 1,最后结果是各曲线的交点处计数器值达到最大 ,该点坐标值既直线的参数。 小结 HOUGH 变换的实质是将图像空间的具有一定关系的象元进行聚类 ,寻找能把这些象元用某一解析形式联系起来的参数空间累积对应点。 在参数空间不超过两维的情况下 ,这种变很理想的效果。 然 中国图象图形网 而 ,当参数空间超过两维时 ,这种变换的时间 消耗和所需存储空间的急剧增大使得这种变换仅仅在理论分析上可行 ,而在实际应用中几乎是不可能实现的。 这时往往要求从具体的应用情况中寻找特点 ,如利用被处理的图像象元的灰度的梯度变化值确定灰度的变化方向来降低参数空间维数。 或利用一些对于被检测图像的先验知识来设法降低参数空间的维数以降低变换过程的时间和空间开销。 HOUGH变换的优点主要在于 :它对于图像中的噪声点不敏感 ,利用它得到的结果可有效地滤除噪声的影响以提高结果的置信度。 这种变换便于并行计算 ,计算机视觉领域的一些问题相当复杂 ,需要很大的计算量 ,并行计算是提高计 算速度的有效方法。 中国图象图形网 第五章 不足和展望 目前存在的不足 （一）本次设计只是对简单几何图形（圆）进行边缘检测，并且在 HOUGH变换之前进行了图像的预处理，所以耗费的存储空间和处理时间并不是很大。 但由于此次设计涉及的知识比较的广泛，导致设计时间相对交为紧迫，致使设计中用到的图像预处理也相对的简单，从而在一定程度上降低了检测的精确度。 如果使用前文中提到的对 图像场景中的各物体的边缘轮廓象元进行骨架化预处理，得到的效果可能会相对较好， 但所用的程序会相应的变的复杂，给程序的调试也会带来较多的问题。 （二） 经典 Hough变换为我们提供了检测直线的有效手段 ,利用该算法可以实现对矩形，三角形等由直线段组成的简单几何图形的识别。 由于该变换必须逐点处理图像平面上的每一点 , 应用在圆或椭圆的检测中时 ,参数空间的维数将扩大到三维和五维 ,这将耗费大量的存储空间和处理器时间，。