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

对数字图像快速有效的圆检测方法摘要：本文提出了两种新的和有效的源于灰度图像的圆检测方法。作为一种工具，我们已经使用了在一个方案中的蚁群算法。在其它方案中，我们使用蚁群再生和重组系统〔ARRS〕，自主研发的一种全新的方法。在这里提出的方案，有三个常见的步骤。首先，MATLAB边缘检测算子将灰度图像转换成一个二进制的1；然后我们应用此二进制图像检测闭合回路；最后，这些闭合回路用来测试圆。方案的主要特点之一是，他们可以检测相交和不想交的圆圈组成的不同形状的图像。第一个方案是传统的蚁群算法修改之后的应用程序，在计算结果方面有很准确的结果。因此，我们构建一个新的蚁群系统〔ARRS〕，可以在令人难以置信的时间和内存效率检测出圆，使其适用于实时应用。关键词：循环检测，圆检测，蚂蚁系统算法，蚁群再生和重组系统。1.引言从拍摄的图像的检测规那么几何形状的各种方法已经被研究。其中Hough变换〔HT〕是最流行的一种，已被用于提取分析功能，如直线，圆，椭圆，因为它抗噪声好。这种技术的一个严重的缺点是它巨大的时间和空间复杂度，时间复杂度与用于表征该形状的参数的数目呈指数增长。本文中，我们提出了全新的方案来有效地进行圆检测，从现实生活中的图像，同时使用蚁群算法和蚂蚁再生和重组系统〔ARRS〕，这是一种全新的算法。据我们所知，我们无法从有效的灰度图像准确、快速地提取有关相交或者是非相交的圆的任何工作，这一点是我们论文所主要研究的。本文已被细分为8个局部。第二节将介绍我们的第一个基于蚁群算法的圆检测方案，我们将其叫做方案I。在第三节，我们介绍了我们的方案II蚂蚁再生和重组系统。在第四节提出了一种基于探索方案II图形根底上改良的闭环检测方法。第五节中提供了根本算法，用于从闭环中检测圆。第六节为方案I和方案II提供了仿真结果，文章最后的结论和今后的工作范围在第七局部。由于空间的稀缺性，我们无法提供预览的蚁群算法。详细讨论这算法可在[3],[4]。2.方案I：闭环检测中的蚁群算法基于蚁群算法的方案I由三个步骤组成：1.根据蚂蚁像素强度和信息素浓度产生解决2.在他们的路径封闭循环检测和测试这些循环的圆形和椭圆形；3.信息素信息的更新。这三个执行步骤在下面描述。首先，使用MATLAB的边缘检测算子〔如sobel和canny〕将现实生活中的灰度级图像转换成一个二进制1.它们将高强度梯度地区转换到边缘。因此，在二进制图像中，每一个像素相关联的强度值是0或1。这些强度值被储存在一个二维结构P中。Pij中P的每一个元素有四个信息字段。它们是四〔代表强度值〕，ant_token(将在后面解释)，Phr〔存储信息素的各像素的浓度〕和圆〔将在后面解释〕。在成立之初，大量的蚂蚁被随机放置在边缘像素，每一只蚂蚁具有一定的记忆。它们存储被访问的像素，而像素是闭合回路的一局部。它们行进通过了边缘像素同时也记下了经历过的数目。每当一只蚂蚁试图移动到一个新的像素，首先搜索在其附近的边缘像素。附近居住的蚂蚁〔I,J〕个像素Nij={(m,n):i-1≤m≤i+1,j-1≤n≤j+1,(m,n)变成一个边缘像素}。搜索的方法是如果蚂蚁已检测到一个闭环是不同的，当它没有发现任何的闭环时。每个像素具有ant_token的字段。蚂蚁，通过一个像素移动的同时，离开它在该像素ant_token字段上的识别号。当蚂蚁遇到一个像素进行识别号码，它便会得到一个二进制的循环检测器。这意味着，蚂蚁已经检测到一个封闭环。循环检测域设定在0处。循环检测域已经设好，蚂蚁就会向仍未访问过的边缘像素移动。这样做是为了防止通过相同的穿越路径，否那么，蚂蚁可以移动到它们的邻居，那些它们访问过的或者未访问的至少三步骤前的边缘像素。以防有多重选择，对于上述的任何情况下，它会根据伪随机分布选择下一个像素。其中，P(M.N)是第〔M,N〕像素下一个选择一和τmn的〔m,n〕个像素的信息素浓度的概率。一旦蚂蚁检测到一个闭合回路，它储存在其储存器中的像素使其闭环。这些封闭的环会根据第5节中所描述的算法检测圆。在蚂蚁算法中，蚂蚁对于较重的信息素浓度路径选择的概率较大。在这种情况下信息素作为一个正反应。但是，为以更好的方法探索整体图像，在方案I中，蚂蚁是基于信息素的水平较大的概率选择路径。因此，蚂蚁被启发探索以前任何其他蚂蚁没有访问过的边缘。随着新方法，信息素的沉积规那么也改变了。当蚂蚁从多个分支的起源到达一个点，它选择的路径仅依赖于路径的信息素的水平。每只蚂蚁也在计算它在旅行中作出决定的数量。现在，一只蚂蚁信息素的沉积量与必须进行决策的数量成反比。因此，如果蚂蚁在其路径中遇到许多分支，不能探索，然后就存储信息素，是蚂蚁启发通过这条道路，去探索那些没有访问过的分支。此域Pij的信息被存储在信息素。“圆〞域只有当对应像素是一个圆的一局部时是一个特殊的标识符。因此，用统一的圆的像素的现场检测符合我们的目的。方案I的伪代码：主程序：initializepheromoneconcentrationoneachpixelinitializeants’memorywhile(alliterationsarenotover)placeantsrandomlyonedgepixelsallowantstoconstructtheirsolutionpathevaporatepheromonefromtheentiregraphallowantstodepositpheromonetrailontheirsolutionpathaccordingtotherulesalreadydescribeddeleteants’currentmemoryendidentifythepixelswithunity‘circle’fieldConstructionofSolutionPath:fori=1toMAXANTwhile(anthassomeedgepixelsinitsneighbortomoveinto&ithasnotreturnedtothestartingpixel)if(anthasalreadydetectedaloop)if(q>q0)searchforunvisitededgepixelwithminimumpheromoneconcentrationelsechooseanunvisitededgepixelprobabilisticallyendelseif(q<q0)searchforedgepixelwithminimumpheromoneconcentrationelsechooseanedgepixelprobabilisticallyendif(antdetectsaloop)antsetsitsloopdetectorfieldantuploadsallthepixelsinitsmemorythatconstructthelooptheloopistestedforcircleif(theloopisacircle)set‘circle’fieldsofthepixelsendendendend3．方案II蚂蚁再生和重组系统〔ARRS〕方案I的主要缺点是，它是不确定性的方法。图像增加的复杂性使得该算法需要更长的时间和更大数量的蚂蚁。因此，我们不得不寻找一个新的基于人工蚂蚁的方法，该方法将是确定性的探索边缘像素，无论是多么复杂的图像。本节介绍我们下面的方案II，以及它如何躲避方案I的缺点。一个字符串的边缘像素，其中每个像素只能连接到两个相邻的像素，被称为一个分支。两个以上的分支集合的地方，我们称之为像素的节点。一个分支采取以坐标完全描述像素的一个分支。因此，每个分支，可以表示为一个结构，其中有两个字段：双向〕index：存储识别的分支数；branch_arr[]：包含的像素的坐标的分支；每个分支被建模为一个单一的块的链表当发现一个新的分支，一块块被添加到列表。每个节点还表示为一个结构，以下字段：n.i)index：该指数为n，我们把它的第N个节点或节点nn.ii的〕〔X,Y〕坐标的节点。n.iii)连接[]：每个节点又是另一个链表的方框图。一旦发现一个新的节点，一个新的块便被添加到列表中。正如方案A所描述的，每只蚂蚁都有一定的内存，记录旅行和探索的图形。一个单一的蚂蚁被表示为以下域结构a.i)(X,Y):当前的坐标，是蚂蚁移动不断更新的。a.ii)(Xn,Yn),其原节点的坐标索引)路径[]:这个数组存储着它沿着分支的像素坐标。在行动前一只蚂蚁发现边缘像素的像素在周围的数量，不包括它刚过来的像素〔即蚂蚁不能搬回〕。对于一个分支，这个数量是1.对于一个节点，它至少有两个〔其中跟随定义〕，当一只蚂蚁发现这样一个像素，我们说它发现了一个节点。如果一只蚂蚁移动到分支上的像素，然后更新自己的坐标和存储的坐标上的像素的阵列，对蚂蚁相邻像素的集合是，ijth像素被定义为Nij={(p,q):i-1≤p≤i+1,j-1≤q≤j+1,(p,q)作为一个边缘像素，类似的定义给了第三局部。如果一只蚂蚁发现了一个节点，它意识到自己已经过的节点和新发现的节点是由它所走过通过分支相互连接的节点。在这一点上，蚂蚁的路径[][]branch_arr阵列成为新发现的分支，这只蚂蚁变为非活动状态〔即停止旅行〕，再现新的蚂蚁放置他们在每一个新的分支的开始，起源于特定节点的像素。我们称这个过程为蚂蚁的再生。每只蚂蚁也是一个链表的一块，当一个蚂蚁变得不活泼，块对应于蚂蚁从列表中删除。当蚂蚁重生，块被附加到链表。因此这个过程无论图像是如何复杂都能进行完整的探索。事实上，放置蚂蚁开始搜索的进程〔我们称之为“妈妈〞的蚂蚁〕在一个随机选择的边缘像素上的。图像的强度信息和平常一样保存在二维数组中。妈妈蚂蚁移动到一个节点〔这是第一个发现的节点〕和新产生的蚂蚁从该节点沿着分支移动。到目前为止，我们观察到蚂蚁的三个特性：特性I：所有蚂蚁都以相同的速度移动，即一个像素一步。特性II：蚂蚁在节点产生的。特性III：蚂蚁记得它来源于并穿过像素的节点。蚂蚁这些属性有一个有趣的结果，假设两个节点A和B之间，有一条较短的路径S和较长的路径L。蚂蚁是在A生成然后向B移动，沿着S更快地到达B，然后将一个新的蚂蚁的像素连接L到B。因此这个新的蚂蚁会沿L走向A，两只蚂蚁相向一段时间后，相遇重组。重组的蚂蚁可以如下利用：i)由于每个发现有局部相同的分支，其路径[]阵列可以参加后得到一个包含数组分支的像素坐标。ii)关联矩阵，用来存储连接图中的节点之间的信息，可更新。这样的重组和交换信息保障，每一个边缘像素只被一只蚂蚁访问一次，因此，我们得到另一个特性。特性IV：一只蚂蚁最终到达了死胡同，或者是节点或者是与另一只蚂蚁相遇，而变得不活泼。每当ith节点和jth节点之间的联系是通过分支K发现，就会进行以下操作：节点i.connectivity[K]=+1和节点j.connectivity[K]=-1否那么，这些阵列的条目被设置为零。变量B跟踪分支的数量检测。从分指标的阵列位置连接[]连接阵列，这些阵列探索完成后，将有长度对应于最大的分支指数，即B。节点总数为N，现在我们堆栈与阵列下方的一个节点连接，从顶部的节点1开始，然后是节点2，之后节点3等等。因此，N*B矩阵形成根本而的图的关联矩阵。如果I=J，即来自同一节点的蚂蚁的一个分支存在，检测到它本来就是一个闭环。在这种情况下我们参加蚂蚁的路径[]阵列到像素坐标的这个分支环，然后测试它的圆形或椭圆形。ARRS的伪代码：假设，在任何时刻的活泼的蚂蚁的数量是M，检测分支数是B，搜索结束时M=0.whileM>0i=1;whilei<=Mfindd,thenumberofedgepixelsaroundthepixeloccupiedbytheithant;if(d>1)addablocktothelistofnodes;B=B+1;addablocktothelistofbranchesandmakethepath[]arrayofthisantthebranch_arr[]ofthenewbranch;theindexofthisbranchisB;if(theantwascomingfromnodepandhasreachednodeq)nodep.connectivity[B]=+1;nodeq.connectivit[B]=-1;enddeletetheblockofthisithantfromthelistofants;placed-1newantsatthestartingpixelsofthed-1newbranchesoriginatingfromthisnodebyaddingd-1newblockstothelistofants;M=M+d-2;elseif(d=1)if(theonlypixelavailabletomoveintoisoccupiedbysomeotherant//i.e.twoantsmeet//letoneantbefromnodepandtheotherfromnodeq)deletetheblockofthetwoantsfromtheantlist;M=M-2;ifp≠qthenB=B+1;addanewblocktothelistofbranches;jointhepath[]arraysoftheantsbacktobackandmakethisthebranch_arr[]ofthenewbranch;nodep.connectivity[B]=+1;nodeq.connectivity[B]=-1;elsejointhepath[]arraysofthetwoantsandtestforcircleendelseupdatetheco-ordinatesoftheithantaccordingtotheadjacentpixelitmoves;recordtheco-ordinatesofthispixelinthepath[]array;endendi=i+1endend4发现闭合回路的改良算法假设一组分支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项组成的关联矩阵。从一个分支可以连接两个节点，一列中有两个非零元素。Ik的每一行对应一个节点和非零的数，在一行中的条目给出连接到的节点的分支数目。如果在Bk的分支形成一个循环，然后在C中的行对应于属于Nk的节点必须具有两个非零项的每一个和所有其他行〔即不属于集合Nk的行〕应具有为零的条目，即如果一个行有一个非零的条目，那么它应该正好有两个这样的条目，否那么其所有条目都为零。我们在一个Ik的一个细胞〔r,c〕开始，包含一个非零的条目。现在行r中一个非零的条目意味着另一个r中非零项的存在。我们更新行数r进入到c中的其他非零细胞。这是相当于从分支的一段移动到另一端。这个新的行也有一个非零的条目〔这个细胞〕，那么我们检查其他非零项〔如果不存在，那么我们拒绝〕，并更新相应的列号移动到该单元格。修改c意味着我们在其它分支，是连接到同一个节点和我们要去的这个分支的另一端〔修改r〕再到其他分支连接到端〔修改c〕等，每次检测每个节点用条件II。我们保持一个变量P，最初设置为零。我们每一次修改，覆盖一个分支和增量P。当P为K，即所有的分支被覆盖，我们检查是否已经回到起始节点；如果是，那么条件被满足〔条件II已经满足，因为我们来到这点对每个节点用条件II检测〕，因此，形成一个封闭的循环，反之那么不行。如果我们回到起始节点P=K，那么在Bk闭环分支，否那么那么不每一次我们修改C，也会记录在一个数组的列数。因此，该阵列将有顺序，分支再形成回路。由于非零项意味着只有+1和-1，如果在一行中有两个非零项，在该行中的所有条目的模数的总和必须是两个。一个分支可以是一个独特的圆圈的一局部。所以，如果我们发现一组分支确实形成了一个圆，假设是我们删除所有这些分支那么不影响发现其他界的可能性。一旦它被发现，一些K个分支形成一个封闭的循环，这是一个圆圈，我们删除的块，分别对应到这些分支的分支列表，兵降低总分值数B为k。我们从K=2开始，检查所有的分支与当前的K值后，我们增加K值。每一次我们找了一组新的分支，我们检查是否B>=K,因为B在这个过程中变化，当B小于K是，我们从图中搜索所有可能的完整的界。5.圆检测算法用于圆检测的算法，从闭环的几何属性，通过3个非共线点可以得出一个独特的圆圈。步骤描述如下：1.选择三个等距点上的闭环随机找到独特的通过这三个点的圆的方程。2.比拟每一个回路中的其他店的圆与圆的半径和中心之间的距离。3.如果偏差δ>ε〔阈值，这是一个函数的半径〕，环是不被考虑为一个圆。4即使条件III满足，如果超过四分之一上的点的环路δ>ε/2，那么放弃该环路。5.一个闭环已经通过上述所有的四个测试被认为是一个圆。被取为可能的圆的半径的函数的阈值ε为更大范围的圆中，我们可以得到更大的偏差。我们选择了ε正比于半径，偏差常数λ，在这样一个从或多或少的所有可见的实验范围从或多或少的所有可见的来确定圆圈方式。6.模拟结果方案二的结果：我们测试我们的两套不同的图像上的算法，在逐渐增加的复杂性，以表格的形式提供的图像的系统性能的比拟研究。定时信息的结果是平均超过10运行。图5：不同的封闭循环检测到的原始图像在最后一组，考虑图像具有不同的形状。图像大小为300*300像素的边缘像素的总数是1160.探索时间为0.532秒，回路测试时间是0.703秒。方案二的时间效率从上面的结果是显而易见的。但是，该方案是内存使用效率。存储器被用来存储i)二维矩阵，对应于图像的像素的强度信息〔ii〕该坐标像素相对应于每个发现的分支〔iii〕关联矩阵通过分支结构存储不同节点间的连接信息。因此，内存的使用率最高只有在勘探结束时。7.结论和未来的工作这里介绍的两种方法是完全新颖的。I方案的缺点促使我们寻找更好的方法，我们找到了方案II。因为我们已经能够探测到闭合回路，我们可以从图像中检测到任何类型的封闭轮廓。我们的下一个尝试将是从不同形状图像中找出椭圆形和平行四边形。此外，我们的方案的时间复杂度和内存的要求没有，，与其他现有的方法比拟，如Hough变换和基于遗传算法的方法。工程上的进步，我们试图比拟我们的算法与计算时间参数的根底上，提出了内存的使用