外文翻译译文-霍夫圆变换方法的比较研究发现

霍夫圆变换方法的比较研究发现H.K.Yuen,J.Princen,J.IllingworthandJ.KittlerDepartmentofElectronicsandElectricalEngineeringUniversityofSurrey,Guildford,GU25XH.U.K.本文的目的是研究能检测大量的圆的检测方法，这是基于霍夫变换的圆形特征提取的方法。这些方法包括标准霍夫变换、李等人提出的快速霍夫变换等，二维存储方法是基于格里克和克莱因的那些设想和两阶段方法。我们实验性的比较了这些方法的表现，还用图阐明它们的性质，例如：准确性、可靠性、计算效率和存储需求。近些年，一些基于霍夫变换的发现圆的方法和一些关于快速启用霍夫变换的一般技术被提出。那些方法总是声称能提高效率、存储和可靠性，尽管在大多数情况下与其它技术的对照是差强人意的。我们觉得现在是时候一起提出那些算法，更详细地检查它们的性质。研究是实验性的，我们会考虑真实综合的图像。我们的研究结果表明：霍夫变换法对于更复杂的变化并不胜过那些直截了当的检测方法。本文的构成如下：在接下来这部分，我们将介绍圆的发现问题及基本霍夫变换的基本思路。我们的研究对五大霍夫变换的每类的基本方法都进行简要的描述。每种方法的实验评价都将会给出，论文的最后一部分是我们工作的总结。用霍夫变换发现圆如果一个圆被表示为：（x-a)2+(y-b)2=r2，(a,b)为圆心的坐标，r为圆的半径，圆上任意一点（xi,yi)将被转换为一个圆形的圆锥体（a,b,r)界限空间。如果图形上的所有点都位于一个圆上，这些圆锥将交叉在一个点（a,b,r)上相当于这个圆的界限。Kimme等人是首先运用霍夫变换原理用真实的图像发现圆的人。在他们的研究中，他们探索了每个边缘点的倾斜方向。一个圆的中心必须位于正常的边缘点。相较于整个圆形的圆锥扩大，其实只有圆锥的几段需要扩大，被扩大的区域的大小取决于边缘方向估计的准确性。完成霍夫变换很重要的一步就是峰值检波发现。我们所找到的一个非常有效的的方法是由格里克和克莱因提出的后处理方法，它是我们简化发现的峰值问题的一项非常有用的技术。它由一个二次设备通过在蓄能器阵列定义最大值，得出每个点的所有临界值，每个边缘点的位置都被标记下来。在所有方法中，这项技术用于发现最终的顶点。我们将在7,10中详细解释。标准霍夫变换标准霍夫变换的基本思路我们在先前部分已经概述过了。使用一个3-D蓄能器阵列，用边缘方向信息限制选上圆锥体的一部分。最理想的位置是圆心必须位于一条适应正常边缘方向的线上，因此，我们只能沿着所有正常点的边缘点去寻找可能的中心位置，这个被估计的中心到每个边缘点的距离就相当于这个圆的半径。但是，在实践中，边缘方向通常被估计得不准确。总之，如果用简单的收集策略，在累加器数组中真实最大值很难被发现。如果方向错误是在范围内，我们认为圆心点（xi,yi)是在一个确定的区域里。当半径增加，这片区域会分离开来。在累加器中扩大这片区域是非常困难的，这片区域会随着这条正常线的堵塞增加而稍稍扩大，详细请看10。格里克和克莱因的霍夫变换法标准霍夫变换存在的问题是如果圆半径变动范围很大的话，需要的存储空间也很大。格里克和克莱因用三个二维的累加器数组来替换一个三维的累加器数组，我们把这种方法叫做格里克和克莱因的霍夫变换。其中两个数组用于中心位置，另一个用于大致的半径。在这种情形下，存储空间会比标准霍夫变换要小得多，发现圆的算法结构会非常简单。当参数的轨迹在霍夫空间形成一个圆之后，给半径赋一个值r=r0，(a,b)的轨迹就是半径为r0的圆所在的空间。因此，这样就有足够的空间去扩大所有的边界的点，让每个半径值都有一个圆。格里克和克莱因提出的方法没有用到边缘方向，这种程序很节省存储空间。但是，对每个中心来说，只有一个半径是有限制的，这不可能去发现集中的圆。这种方法的应用在1。格里克和克莱因的霍夫变换法和梯度方向格里克和克莱因的霍夫变换法没有用到边缘方向，一个完整的圆必须包括每个边缘点的每个半径值，这在一定程度上对计算有较高的要求。为了提高效率，我们必须修改格里克和克莱因的霍夫变换法，加上边缘方向的信息，这个修改方法叫做格里克梯度霍夫变换。只有决定边缘方向的圆的一块扇形部分需要扩大。为了高效的做这些工作，我们把扇形近似地当做方形。这个方法的构造和格里克和克莱因的霍夫变换法是完全相同的，除了在积累和后处理的完整圆的较小的区域被认为是之外。2-1霍夫变换另一种运用边缘方向来减少存储需求的方法是将圆的发现分解成两个阶段，这种方法用在2,3中，这里我们把它叫做2-1霍夫变换。因为一个圆的中心必须位于圆上每点的法线，这些法线的公共交叉点实际上就是圆心。用一个二维的数组去收集每个边缘点的法线。为了明确圆的半径，从一个备选中心到每个点的距离都被计算出来，然后做一个半径的直方图。在中心寻找阶段，错误顶点的发现会为下一阶段花费很大的计算量，尤其是用低临界值去发现小圆。这种方法对存储空间要求非常小，只需一个简单地2-D收集器和一个1-D直方图。这种方法的应用详见2。快速霍夫变换李等人建议对霍夫变换方法的收集过程用一个多维的四叉树模型，这个方法被叫做快速霍夫变换。李认为相较于标准霍夫变换，快速霍夫变换需要的存储更小，计算的效率更高。快速霍夫变换是基于一个超平面的构想，也就是说参数空间是一个超平面，圆的发现问题很有可能发展成为一个超平面的构想。但是，从我们的实验结果上看，由于超平面构想的参数非线性问题，这个方法对于发现圆并不适合。为了避免这个问题并提高快速霍夫变换的效率，我们采用一个加上了边缘方向信息的不同的构想，这个修改后的方法叫做改良的快速霍夫变换。这个方法利用了一个由两条正交的直线在点（xi,yi,0)相交后向外延伸的三维霍夫空间，在法线方向的在一个边缘点（xi,yi)的参数轨迹（a,b,r)。为了确定一个超立方体是否被两条线的其中一条分割，我们比较了超立方体中心到这条线的垂直距离与超立方体的对角线的长度，如果前者更短，这个超立方体将会获得一条。和原来的快速霍夫变换不同，这里没有更新分割测试。为了提高这种算法的效率，我们必须做个计划基于半径的变动范围去选择合适的临界值，同时缩小半径的搜寻范围10。结果的得出就是基于这种策略。实验对照任何一种算法的对照都有很多标准，但是在我们研究中的关键点是准确性、计算复杂性和存储性。精度是衡量比较的绝对误差估计半径和中心坐标在合成图像圆的真实值。我们提出一个典型的例子，一个由19个随机生成的圆组合的图像。为了测试每个算法的探测功能，一个由76个不同半径的圆组成的真实的图像，人为地被统计，被检查，每个算法中，那些缺失的错误的圆都被统计出来。为了使计算更有效率，我们花时间在我们的VAX计算机上运行每个算法。我们意识到作为一个衡量的效率不一定是普遍的意义，然而，除了FHT，所有的其他算法都很相似，因此，至少在粗糙的理念里，我们希望得到关于效率的结论。主要的时间消耗在变换收集中出现的每种算法和格里克和克莱因的后处理方法的实施中，二维方法在半径直方图这一步也花了很多时间。每一种方法的存储要求都被累加器数组控制。所有的算法都被编码在PASCAL。图1、2展示了综合的真实的边缘点的图像，在每个图上的边缘点都被鉴别出来，通过一种基于Canny边缘检测器9的方法和使二进制变薄的合成极限值的边缘地图。合成图的边缘方向被一个在-5,5范围内的均匀分布噪声干扰,这个干扰并没有影响没有使用边缘方向的格里克和克莱因霍夫变换的性能。对于其他的方法，三种不同的误差范围，00、50和100，都被假定为边缘方向的准确度。图3表明了绝对误差的大致方法的三种参数，有趣的是，格里克和克莱因霍夫变换对于没有梯度的半径参数是零误差的。2-1HT法对于误差范围值的假定是非常敏感的，在误差范围为50时，参数得出一个非常小的误差。改良的快速霍夫变换法在误差范围为00时得出的结果很好，但是由于巨大的存储需求，在误差范围为100时得出的结果并不可用。绝对误差的意义对于标准霍夫变换法是比其他方法更重大的。格里克和克莱因霍夫变换适用于大多数的例子，而且当假定的误差范围变大时，也依旧适用。基于这个单一的例子很难去选择最好的方法，然而，基于其他实验的结果，2-1霍夫变换和格里克和克莱因霍夫变换法似乎比其他方法更准确一点。结论我们的研究结果表明，无论是格里克和克莱因霍夫变换和改良的快速霍夫变换如果应用到复杂的图像都将经历严重的干扰。格里克和克莱因霍夫变换的主要问题在于处理实际问题时的不可靠性和低效率性，因为边缘方向信息不包含在方法中。改良的快速霍夫变换在于不可预测的存储和计算要求，而且与其他方法相比拥有更复杂复杂的结构。然而，这两种方法可能仍然是有用的，如果它们被应用到简单的图像，具有非常低的噪声。已经被展示的2-1霍夫变换格里克和克莱因霍夫变换和标准霍夫变换他们的结果是非常相近的，对于存在的主要缺点是由不同大小的圆的图像储存空间需求大。虽然格里克和克莱因霍夫变换限用于非同心圆，我们发现，与其他实验结果10相比，一般的格里克和克莱因霍夫变换在可靠性上比2-1HT霍夫变换方法更好。造成这一现象的原因是因为21HT是2阶段法，在中心寻找第一阶段中心定位发生的任何错误将导致发现二次寻峰阶段的峰值时产生困难。图1图2图3绝对误差的意思,和,1)GKHT,(2)21HT,(3)GHTG,(4)SHT和(5)MFHT在误差界(a)0,(b)5和(c)10图4对合成图像检测方法的ghtg在误差10结合所得的结果图5合成图像上每个算法的计算时间图6.实时图像上的每个算法的中央处理器时间图7GHTG检测圆的结果图MissingFalseMethod05100510GKHT33300021