《对数字图像快速有效的圆检测方法》由会员分享，可在线阅读，更多相关《对数字图像快速有效的圆检测方法（10页珍藏版）》请在金锄头文库上搜索。
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(qq0)search for edge pixel with minimum pheromoneconcentrationelsechoose an edge pixel probabilisticallyendif(ant detects a loop)ant sets its loopdetector fieldant uploads all the pixels in its memorythat construct the loop the loop
11、is tested for circle if(the loop is a circle)set circle fields of the pixelsendend endend3方案II 蚂蚁再生和重组系统（ARRS）方案I的主要缺点是，它是不确定性的方法。图像增加的复杂性使得该算法需要更长的时间和更大数量的蚂蚁。因此，我们不得不寻找一个新的基于人工蚂蚁的方法，该方法将是确定性的探索边缘像素，无论是多么复杂的图像。本节介绍我们下面的方案II，以及它如何规避方案I的缺点。一个字符串的边缘像素，其中每个像素只能连接到两个相邻的像素，被称为一个分支。两个以上的分支汇合的地方，我们称之为像素的节点。
12、一个分支采取以坐标完全描述像素的一个分支。因此，每个分支，可以表示为一个结构，其中有两个字段：双向）index：存储识别的分支数；branch _arr：包含的像素的坐标的分支；每个分支被建模为一个单一的块的链表当发现一个新的分支，一块块被添加到列表。每个节点还表示为一个结构，以下字段：n.i)index：该指数为n，我们把它的第N个 节点或节点n n.ii的）（X,Y）坐标的节点。n.iii)连接：每个节点又是另一个链表的方框图。一旦发现一个新的节点，一个新的块便被添加到列表中。正如方案A所描述的，每只蚂蚁都有一定的内存，记录旅行和探索的图形。一个单一的蚂蚁被表示为下列域结构a.i)(X,Y
13、):当前的坐标，是蚂蚁移动不断更新的。a.ii)(Xn,Yn),其原节点的坐标索引 )路径:这个数组存储着它沿着分支的像素坐标。在行动前一只蚂蚁发现边缘像素的像素在周围的数量，不包括它刚过来的像素（即蚂蚁不能搬回）。对于一个分支，这个数量是1.对于一个节点，它至少有两个（其中跟随定义），当一只蚂蚁发现这样一个像素，我们说它发现了一个节点。如果一只蚂蚁移动到分支上的像素，然后更新自己的坐标和存储的坐标上的像素的阵列，对蚂蚁相邻像素的集合是，ijth像素被定义为Nij=(p,q):i-1pi+1, j-1qj+1,(p,q) 作为一个边缘像素，类似的定义给了第三部分。如果一只蚂蚁发现了一个节点，它
14、意识到自己已经过的节点和新发现的节点是由它所走过通过分支相互连接的节点。在这一点上，蚂蚁的路径 branch_arr阵列成为新发现的分支，这只蚂蚁变为非活动状态（即停止旅行），再现新的蚂蚁放置他们在每一个新的分支的开始，起源于特定节点的像素。我们称这个过程为蚂蚁的再生。每只蚂蚁也是一个链表的一块，当一个蚂蚁变得不活跃，块对应于蚂蚁从列表中删除。当蚂蚁重生，块被附加到链表。因此这个过程无论图像是如何复杂都能进行完整的探索。事实上，放置蚂蚁开始搜索的进程（我们称之为“妈妈”的蚂蚁）在一个随机选择的边缘像素上的。图像的强度信息和平常一样保存在二维数组中。妈妈蚂蚁移动到一个节点（这是第一个发现的节点）
15、和新产生的蚂蚁从该节点沿着分支移动。到目前为止，我们观察到蚂蚁的三个特性：特性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，之后节
