圆心提取算法综述

圆心提取算法综述摘要：阐述当前主要的圆心提取算法，分析其优缺点和使用范围，为圆心提取算法的运用以及运用中选取合适的圆心提取算法提供参考。关键字：圆心提取，算法引言：随着现代社会信息技术的飞速发展，特别是20世纪40年代计算机的出现以及50年代人工智能的兴起，人们希望能用计算机来代替或扩展人类的部分脑力劳动，模式识别技术作为人工智能的基础，为满足社会需求获得了快速的发展。提取圆心是大多数模式识别图像处理与分析的必要环节。因此，快速而准确的圆心提取算法显得尤为重要。目前提取圆心的算法主要有以下几种:基于Hough变换的圆心坐标快速提取方法和一些改进算法,平面圆圆心及半径的最小二乘拟合,细化法,正交扫描法、阈值分割提取法、神经网络法等。本文总结阐述当前主要的圆心提取算法，分析其优缺点和使用范围，为圆心提取算法的运用以及运用中选取合适的圆心提取算法提供参考。1.基于Hough变换的几种圆心提取算法1.1Hough变换的基本原理Hough变换的原理[1]就是利用图像全局特征将边缘像素连接起来组成区域封闭边界，它将图像空间转换到参数空间，在参数空间对点进行描述，达到检测图像边缘的目的。该方法把所有可能落在边缘上的点进行统计计算，根据对数据的统计结果确定属于边缘的程度。Hough变换的实质就是对图像进行坐标变换，把平面坐标变换为参数坐标，使变换的结果更易识别和检测。典型的例子就是直线的检测，通过变换图像平面上的点对应到参数平面上的线，而图像平面中的一条直线对应于参数平面中的一簇有公共交点的曲线。从而检测直线就转换为检测有特殊特征的点，检测到的点，就是图像平面上线的参数。因此直线就被检测出来了，圆的检测原理类似。1.2基本Hough变换[2,3]已知圆的一般方程为：222)(rbyax）（………………(1)式中：（a,b）为圆心，r为圆的半径。把-平面上的圆转换到——参数空间，则图像空间中过任意一点的圆对应于参数空间中的一个三维锥面，图像空间中同一圆上的点对应于参数空间中的所有三维锥面必然交于一点。这样通过检测这一点可以得到圆的参数，相应的圆也可求得了。图像平面的方程转化为参数平面上的示意图如图1所示。该方法的优点，算法十分简单，抗干扰能力强；其缺点[4,5]是计算量大、对存储空间需求大，不能检测特殊曲线，精度低，难于找到累加数组的局部最大值,一般不用于工程实践。1.3随机Hough变换所谓随机Hough变换就是指随机的在图像上采样几个点来确定一个圆。由于噪声和复杂背景的干扰应用随机Hough变换检测圆时会产生随机采样的大量无效累积。因此，研究人员提出了多种改进方法，即首先规定一个条件，当随机采样到的点组满足此条件时，相应的累加器进行增值，否则进行下一个随机点组的选取。然而关键问题是条件的确定和选择。文献[6]的算法中，变换了圆的方程式为：)2.........(....................02222cbyaxyx使方程组的幂为1次，便于计算，同时也提高了计算速度。在圆周上任意选取3个点，代入方程式，计算出a,b,c这3个参数，用两个累加器A(a,b)和))((2122cbaB来进行统计可能的圆心和半径。此方法3个点的选择方法是在边缘图像上按扫描方式逐个选择第一个像素1p，然后依据该点的方向,向对面搜索对应弧线上的一点作为第2点2p，(2p点在1p点的对面位置，且方向满足对面圆弧所规定的方向)；而在同一方向上的另一个区域寻找第3点3p。该方法相比于经典的HT，降低了内存需要，使其参数空间无限大、参数精度任意高；缺点是对噪声敏感，处理复杂图像时引入了大量的无效累计，需利用一定的条件加以约束点组的选择。1.4广义Hough变换广义的Hough变换是Ballard提出的可以检测不必知道曲线或区域边界的参数方程的任意形状的物体的算法。一般算法[7]为：在图像上取出一个参考点；对图像上每一个为1的点，计算梯度角；对每一个梯度角，存储对应于参考点的距离和角度。文献[7]中的算法，基于统计聚类思想，从圆的基本定义及特点出发，对潜在的可能成为圆心的像素点，从其边界点集中剔除不符合要求的边界点，构造出具最大概率的边界点子集，再根据设定的阈值判断构造出的边界点子集是否构成一个圆。对得到的有限数量的圆进行简单的聚类拟合可确定图像中存在的真实圆的圆心和半径。判定的方法就是边界点的梯度与边界点到可能圆心的方向是否相同，还有可能成为圆心的点是否是与边界点集中所有边界点距离相等的惟一参考点。该方法的优点是对噪声有很好的抗干扰性。能在含有孤立点、半连续噪声点以及曲线和直线段噪声的图像空间中检测圆，也能检测残缺圆；缺点是需要大量的存储空间和巨大的计算量，效率不高。圆Hough检测是目前应用最为广泛的方法之一，其可靠性高，对噪声、变形、部分区域残缺、边缘不连续等有较好的适应性，但其缺点是计算量大，占据内存多。并且，实际图像还受光照、背景不均匀等条件的影响，从而影响了其计算精度和计算速度。霍夫变换适用于边界点数很多的情况下，在边界点数较少的情况下则不适用。2.平面圆圆心及半径的最小二乘拟合该算法直接依赖于测量数据,因此适用于求取任何平面圆的圆心和半径。是一种在圆度评估中求任意位置的平面圆圆心及半径的最小二乘算法,该算法也同祥适用于空间球心及半径的求解。具体算法参考文献[8]。3.细化法依据是否使用迭代运算可以分为两类：第一类是非迭代算法，一次即产生骨架，如基于距离变换的方法。游程长度编码细化等。第二类是迭代算法，即重复删除图像边缘满足一定条件的像素，最终得到单像素宽带骨架。迭代方法依据其检查像素的方法又可以再分成串行算法和并行算法，在串行算法中，是否删除像素在每次迭代的执行中是固定顺序的，它不仅取决于前次迭代的结果，也取决于本次迭代中已处理过像素点分布情况，而在并行算法中，像素点删除与否与像素值图像中的顺序无关，仅取决于前次迭代的结果。在经典细化算法发展的同时，起源于图像集合运算的形态学细化算法也得到了快速的发展。该方法的缺点是以线段来逼近,抗噪声性能差,误差较大。4.正交扫描法正交扫描法是先获得条,再用中垂线跟踪,分割圆弧以线段逼近圆心。具体算法过程请参见文献[9]。该方法的缺点与细化法一样抗噪声性能差,误差较大。5.阈值分割提取法是一种基于区域的图像分割技术，其基本原理是：通过设定不同的特征阈值，把图像象素点分为若干类。常用的特征包括：直接来自原始图像的灰度或彩色特征；由原始灰度或彩色值变换得到的特征。设原始图像为f(x，y)，按照一定的准则f(x，y)中找到特征值T，将图像分割为两个部分，分割后的图像为：若取：0b=0(黑)，1b=1(白)，即为我们通常所说的图像二值化。利用阈值分割提取特征点时，由于图像各处的目标灰度值与背景灰度值对比不同，常常不能取得很好的效果，并且图像经过二值化后，会丢失一些有用的信息，所以在精度要求高的场合下，该方法并不适用。6.神经网络法[10]该方法首先对图像进行边界滤波，在此基础上用Kohonen神经网络提取圆的边界点与中心点。由于该方法避免了采用阈值分割法提取特征点所带来的信息丢失的缺点，从而减小了人为误差；同时对图像进行边界滤波，可以滤除图像边界处存在的高频噪声，为下一步精确提取特征点做好了准备。该方法成功避免了传统算法中的一些缺陷，提高了精度，但是由于该方法需要利用神经网络提取边界点与圆心点，而神经网络是建立在大量数据基础上的，所以该方法不适用于边界点较少的圆的圆心提取。结束语综上所述，传统的提取圆心算法中由于人为设定阈值，容易引进人为误差，从而降低了精度，而利用霍夫变换以及Kohonen神经网络虽然精度较高，提取的圆心更精确，但是这两种方法都是基于大量边界点的基础上的，因此针对不同的条件，需采用不同的方法。参考文献【1】崔继文,谭久彬.基于约束抽样Hough变换的圆轮廓快速检测技术[J].哈尔滨工业大学学报,2005,37(10):1394-1396。【2】WildesRP.Irisrecognition:anemergingbiometrictechnology[J].IEEE,1997,85(9):1348-1363.【3】章毓晋.图像处理和分析[M].北京:清华大学出版社,2001:190-191.【4】刘勋，林娟等.一种改进的Hough变换提取圆的方法[J].信号处理,2004,20(6):623-624.【5】杨莉，隋金雪，杜艳红，郭玉刚.改进Hough变换在形状检测中的应用[J].传感器与微系统，2007(5):86-88.【6】IoannouD,HudaW,LaineAF.Circlerecognitionthrougha2DHoughtransformandradiushistogramming[C].ImageandVisionCompute,1999(17):15-26.【7】贾云得.机器视觉[M].北京:科学出版社,2003:122-126.【8】田社平,张守愚,李定学,等.平面圆圆心及半径的最小二乘拟合[J].实用测试技术,1995(9).【9】DovDori.Vector2basedarcsegmentationinthemachinedrawingunderstandingsystemenvironment[J].IEEETransactionsonPatternandMachineIntelligence,1995,17(11):105721068.【10】YoungJunRoh,WomShikPark,HyunsuckCho.CorrectingImageDistortionintheX-rayDigitalTomosynthesisSystemforPCBSolderJointInspectionImageandVision.Computing21,2003:1063~1075