对数字图像快速有效的圆检测方法

1、对数字图像快速有效的圆检测方法摘要：本文提出了两种新的和有效的源于灰度图像的圆检测方法。作为一种工具，我们已经使用了在一个方案中的蚁群算法。在其它计划中，我们使用蚁群再生和重组系统（ARRS），自主研发的一种全新的方法。在这里提出的方案，有三个常见的步骤。首先，MATLAB边缘检测算子将灰度图像转换成一个二进制的1；然后我们应用此二进制图像检测闭合回路；最后，这些闭合回路用来测试圆。方案的主要特点之一是，他们可以检测相交和不想交的圆圈组成的不同形状的图像。第一个方案是传统的蚁群算法修改之后的应用程序，在计算结果方面有很准确的结果。因此，我们构建一个新的蚁群系统（ARRS），可以在令人难以置信的

2、时间和内存效率检测出圆，使其适用于实时应用。关键词：循环检测，圆检测，蚂蚁系统算法，蚁群再生和重组系统。1.引言从拍摄的图像的检测规则几何形状的各种方法已经被研究。其中Hough变换（HT）是最流行的一种，已被用于提取分析功能，如直线，圆，椭圆，因为它抗噪声好。这种技术的一个严重的缺点是它巨大的时间和空间复杂度，时间复杂度与用于表征该形状的参数的数目呈指数增长。本文中，我们提出了全新的方案来有效地进行圆检测，从现实生活中的图像，同时使用蚁群算法和蚂蚁再生和重组系统（ARRS），这是一种全新的算法。据我们所知，我们无法从有效的灰度图像准确、快速地提取有关相交或者是非相交的圆的任何工作，这一点是我

3、们论文所主要研究的。本文已被细分为8个部分。第二节将介绍我们的第一个基于蚁群算法的圆检测方案，我们将其叫做方案I。在第三节，我们介绍了我们的方案II蚂蚁再生和重组系统。在第四节提出了一种基于探索方案II图形基础上改进的闭环检测方法。第五节中提供了基本算法，用于从闭环中检测圆。第六节为方案I和方案II提供了仿真结果，文章最后的结论和今后的工作范围在第七部分。由于空间的稀缺性，我们无法提供预览的蚁群算法。详细讨论这算法可在3,4。2. 方案I：闭环检测中的蚁群算法基于蚁群算法的方案I 由三个步骤组成：1.根据蚂蚁像素强度和信息素浓度产生解决2.在他们的路径封闭循环检测和测试这些循环的圆形和椭圆形；

4、3.信息素信息的更新。这三个执行步骤在下面描述。 首先，使用MATLAB的边缘检测算子（如sobel和canny）将现实生活中的灰度级图像转换成一个二进制1.它们将高强度梯度地区转换到边缘。因此，在二进制图像中，每一个像素相关联的强度值是0或1。这些强度值被储存在一个二维结构P中。Pij中P的每一个元素有四个信息字段。它们是四（代表强度值），ant_token(将在后面解释)，Phr（存储信息素的各像素的浓度）和圆（将在后面解释）。在成立之初，大量的蚂蚁被随机放置在边缘像素，每一只蚂蚁具有一定的记忆。它们存储被访问的像素，而像素是闭合回路的一部分。它们行进通过了边缘像素同时也记下了经历过的数目

5、。每当一只蚂蚁试图移动到一个新的像素，首先搜索在其附近的边缘像素。附近居住的蚂蚁（I,J）个像素 Nij=(m,n):i-1mi+1, j-1nj+1,(m,n)变成一个边缘像素。搜索的方法是如果蚂蚁已检测到一个闭环是不同的，当它没有发现任何的闭环时。每个像素具有ant_token的字段。蚂蚁，通过一个像素移动的同时，离开它在该像素ant_token字段上的识别号。当蚂蚁遇到一个像素进行识别号码，它便会得到一个二进制的循环检测器。这意味着，蚂蚁已经检测到一个封闭环。循环检测域设定在0处。循环检测域已经设好，蚂蚁就会向仍未访问过的边缘像素移动。这样做是为了防止通过相同的穿越路径，否则，蚂蚁可以移

6、动到它们的邻居，那些它们访问过的或者未访问的至少三步骤前的边缘像素。以防有多重选择，对于上述的任何情况下，它会根据伪随机分布选择下一个像素。其中，P(M.N)是第（M,N）像素下一个选择一和mn的（m,n）个像素的信息素浓度的概率。一旦蚂蚁检测到一个闭合回路，它储存在其储存器中的像素使其闭环。这些封闭的环会根据第5节中所描述的算法检测圆。在蚂蚁算法中，蚂蚁对于较重的信息素浓度路径选择的概率较大。在这种情况下信息素作为一个正反馈。但是，为以更好的方法探索整体图像，在方案I中，蚂蚁是基于信息素的水平较大的概率选择路径。因此，蚂蚁被启发探索以前任何其他蚂蚁没有访问过的边缘。随着新方法，信息素的沉积规

7、则也改变了。当蚂蚁从多个分支的起源到达一个点，它选择的路径仅依赖于路径的信息素的水平。每只蚂蚁也在计算它在旅行中作出决定的数量。现在，一只蚂蚁信息素的沉积量与必须进行决策的数量成反比。因此，如果蚂蚁在其路径中遇到许多分支，不能探索，然后就存储信息素，是蚂蚁启发通过这条道路，去探索那些没有访问过的分支。此域Pij的信息被存储在信息素。“圆”域只有当对应像素是一个圆的一部分时是一个特殊的标识符。因此，用统一的圆的像素的现场检测符合我们的目的。 方案I的伪代码： 主程序： initialize pheromone concentration on each pixel initialize ants

8、 memorywhile ( all iterations are not over) place ants randomly on edge pixels allow ants to construct their solution path evaporate pheromone from the entire graph allow ants to deposit pheromone trail on their solution path according to the rulesalready described delete ants current memory end ide

9、ntify the pixels with unity circle field Construction of Solution Path: for i=1 to MAXANT while (ant has some edge pixels in its neighbor tomove into & it has not returned to the starting pixel)if ( ant has already detected a loop)if(q q0)search for unvisited edge pixel with minimumpheromone concent

10、rationelsechoose an unvisited edge pixel probabilisticallyendelseif(q0i=1;while i1)add a block to the list of nodes;B=B+1;add a block to the list of branches and makethepath array of this ant the branch_arr ofthe new branch; the index of this branch is B;if (the ant was coming from node p and hasrea

11、ched node q)node p.connectivityB=+1;node q. connectivit B=-1;enddelete the block of this ith ant from the list ofants;place d-1 new ants at the starting pixels ofthe d-1 new branches originating from this node byadding d-1 new blocks to the list of ants;M=M+d-2;else if (d=1)if ( the only pixel avail

12、able to move into isoccupied by some other ant /i.e. two ants meet/letone ant be from node p and the other from node q)delete the block of the two ants from theant list;M=M-2;if pqthen B=B+1;add a new block to the list of branches;join the path arrays of the ants backto back and make this the branch

13、_arr of the newbranch ;node p.connectivity B=+1;node q.connectivity B=-1;elsejoin the path arrays of the two ants and test for circleendelseupdate the co-ordinates of the ith antaccording to the adjacent pixel it moves;record theco-ordinates of this pixel in the path array;endendi=i+1endend4 发现闭合回路的

14、改进算法假设一组分支K是Bk=b1，b2，bk，选择所有B分支数集，这里有两点要注意，I.各分支与它连接的两个节点是相关联的。分支Bi终端节点ni1和ni2，如果Bi是一个闭环回路，则闭环必须通过ni1和ni2。那么很明显，如果选定的分支构成一个闭合回路，回路必须通过那个属于它集节点的所有节点。在一个封闭的循环，分支的数量形成回路，在回路的节点数目必须相等，即Nk的基数必须等于K。集合Nk中的每个节点都必须恰好连接到Bk两个分支中。条件I和II是必要的和足够的任何选定的组构成闭合回路。现在，我们的关联矩阵，对应于选定的分支，是增强形成一个新的N*K的矩阵，我们称之为IK。IK是只有1，-1,0

15、项组成的关联矩阵。从一个分支可以连接两个节点，一列中有两个非零元素。Ik的每一行对应一个节点和非零的数，在一行中的条目给出连接到的节点的分支数目。如果在Bk的分支形成一个循环，然后在C中的行对应于属于Nk的节点必须具有两个非零项的每一个和所有其他行（即不属于集合Nk的行）应具有为零的条目，即如果一个行有一个非零的条目，那么它应该正好有两个这样的条目，否则其所有条目都为零。我们在一个Ik的一个细胞（r,c）开始，包含一个非零的条目。现在行r中一个非零的条目意味着另一个r中非零项的存在。我们更新行数r进入到c中的其他非零细胞。这是相当于从分支的一段移动到另一端。这个新的行也有一个非零的条目（这个细

16、胞），那么我们检查其他非零项（如果不存在，那么我们拒绝），并更新相应的列号移动到该单元格。修改c意味着我们在其它分支，是连接到同一个节点和我们要去的这个分支的另一端（修改r）再到其他分支连接到端（修改c）等，每次检测每个节点用条件II。我们保持一个变量P，最初设置为零。我们每一次修改，覆盖一个分支和增量P。当P为K，即所有的分支被覆盖，我们检查是否已经回到起始节点；如果是，则条件被满足（条件II已经满足，因为我们来到这点对每个节点用条件II检测），因此，形成一个封闭的循环，反之则不行。如果我们回到起始节点P=K，则在Bk闭环分支，否则则不每一次我们修改C，也会记录在一个数组的列数。因此，该阵列

17、将有顺序，分支再形成回路。由于非零项意味着只有+1和-1，如果在一行中有两个非零项，在该行中的所有条目的模数的总和必须是两个。一个分支可以是一个独特的圆圈的一部分。所以，如果我们发现一组分支确实形成了一个圆，若是我们删除所有这些分支则不影响发现其他界的可能性。一旦它被发现，一些K个分支形成一个封闭的循环，这是一个圆圈，我们删除的块，分别对应到这些分支的分支列表，兵降低总分值数B为k。我们从K=2开始，检查所有的分支与当前的K值后，我们增加K值。每一次我们找了一组新的分支，我们检查是否B=K,因为B在这个过程中变化，当B小于K是，我们从图中搜索所有可能的完整的界。5.圆检测算法用于圆检测的算法，

18、从闭环的几何属性，通过3个非共线点可以得出一个独特的圆圈。步骤描述如下：1.选择三个等距点上的闭环随机找到独特的通过这三个点的圆的方程。2.比较每一个回路中的其他店的圆与圆的半径和中心之间的距离。3.如果偏差（阈值，这是一个函数的半径），环是不被考虑为一个圆。4即使条件III满足，如果超过四分之一上的点的环路/2，则放弃该环路。5.一个闭环已经通过上述所有的四个测试被认为是一个圆。被取为可能的圆的半径的函数的阈值为更大范围的圆中，我们可以得到更大的偏差。我们选择了正比于半径，偏差常数，在这样一个从或多或少的所有可见的实验范围从或多或少的所有可见的来确定圆圈方式。6.模拟结果 方案二的结果：我们

19、测试我们的两套不同的图像上的算法，在逐渐增加的复杂性，以表格的形式提供的图像的系统性能的比较研究。定时信息的结果是平均超过10运行。 图5：不同的封闭循环检测到的原始图像在最后一组，考虑图像具有不同的形状。图像大小为300*300像素的边缘像素的总数是1160.探索 时间为0.532秒，回路测试时间是0.703秒。方案二的时间效率从上面的结果是显而易见的。但是，该方案是内存使用效率。存储器被用来存储i)二维矩阵，对应于图像的像素的强度信息（ii）该坐标像素相对应于每个发现的分支（iii）关联矩阵通过分支结构存储不同节点间的连接信息。因此，内存的使用率最高只有在勘探结束时。7.结论和未来的工作这

20、里介绍的两种方法是完全新颖的。I计划的缺点促使我们寻找更好的方法，我们找到了方案II。因为我们已经能够探测到闭合回路，我们可以从图像中检测到任何类型的封闭轮廓。我们的下一个尝试将是从不同形状图像中找出椭圆形和平行四边形。此外，我们的方案的时间复杂度和内存的要求没有，与其他现有的方法比较，如Hough变换和基于遗传算法的方法。工程上的进步，我们试图比较我们的算法与计算时间参数的基础上，提出了内存的使用，执行复杂性和噪声下，在系统输出的精度。参考文献1Jie Yao, Nawwaf Kharma and Peter Grogono, A multipopulation genetic algorithm for robust and fast ellipse detection, Electrical and Computer Engineering Dept. and Computer Science Dept., Concordia University.2R. O. Duda,