一种基于蚁群聚类的多模板图像分割方法

摘要

一种基于蚁群聚类(Ant Colony Clustering)的多模板图像分割方法，实施步骤为：步骤一：图像预处理；步骤二：确定各像素的属性，可选择的模板有：Laplacian模板，Canny模板，Sobel模板，Roberts模板等；步骤三：计算初始聚类中心和初始优化度函数值F

说明书

(一)技术领域

本发明一种基于蚁群聚类(Ant Colony Clustering)的多模板图像分割方法，属于计算机视觉信息处理处理领域。

(二)背景技术

图像分割是图像处理领域的一个重要问题，它是许多图像处理问题的基础。已经广泛应用在很多领域，包括图像融合、模式识别、计算机视觉、飞机导航、虚拟现实、工业检测、交通管理、数字摄影测量、医学图像分析等。但是由于图片背景的复杂性，目标特征的多样性以及噪声等影响，使图像分割成为图像处理技术的难点。

作为计算机视觉信息处理领域中最为基本的一个问题，图像分割吸引了许多不同领域的研究工作者，包括人工智能、航空、航天、航海、机器人等领域，它是目前图像处理领域的一个研究热点。传统的图像分割技术主要有两种，一种是区域生成的方法(也就是聚类)，一是基于图像边缘检测的方法。这两种方法分别针对不同的图像都取得了很好的效果，因而都是目前使用的比较广泛的方法。但是针对不同条件、要求以及使用目的，传统方法又表现出了很大的局限性。目前传统的聚类方法在目标与背景不明显的情况下效果不佳，而且计算量大；边缘检测算子也都只能在各自特定的条件下才能达到很好的效果，在复杂与多变的环境下则显得无能为力，而且存在边界不连续或边界不准确的问题，同时，要受到阈值选择造成的对噪声的敏感。

蚁群优化(Ant Colony Optimization)算法是一种最新发展的模拟昆虫王国中蚂蚁群体觅食行为的仿生优化算法，该算法采用了正反馈并行自催化机制，具有较强的鲁棒性、优良的分布式计算机制、易于与其他方法结合等优点，在解决许多复杂优化问题方面已经展现出其优异的性能和巨大的发展潜力。

蚁群优化算法是由蚂蚁觅食行为演化来的优化算法，蚂蚁个体之间是通过一种称之为信息素(Pheromone)的物质进行信息传递，从而能相互协作，完成复杂的任务。蚂蚁在运动过程中，在它所经过的路径上会留下一定量的信息素，信息素的强度与路径长度有关。并且蚂蚁在运动过程中能够感知路径上信息素的存在及其强度，并以此指导自己的对路径的选择，蚂蚁倾向于朝着信息素强度较高的方向移动。因此，由大量蚂蚁组成的蚁群的集体行为便表现出一种信息正反馈现象：某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大。蚂蚁个体之间就是通过这种信息的交流达到搜索食物的目的。蚁群算法采用了正反馈并行自催化机制，该算法具有较强的鲁棒性、优良的分布式计算机制、易于与其他方法结合等优点，在解决其他许多复杂优化问题方面也已经展现出了优异的性能和巨大的发展潜力。

自然界中，像蚂蚁这类社会性动物，单只蚂蚁的能力和智力非常简单，但它们通过相互协调、分工、合作完成不论工蚁还是蚁后都不可能有足够能力来指挥完成的筑巢、觅食、迁徙、清扫蚁穴等复杂行为。蚂蚁的食物源总是随机散布于蚁巢周围，我们只要仔细观察就可以发现，经过一段时间后，蚂蚁总能找到一条从蚁巢到食物源的最短路径。科学家曾经通过“双桥实验”对蚁群的觅食行为进行了研究。发现除了能找到巢穴和食物源之间的最短路径之外，蚁群对环境有着极强的适应能力。例如当原有的最短路径由于一个新的障碍物的出现而变得不可行时，蚁群能迅速找到一条新的最短路径。因此，在现实生活中，我们总可以观察到大量蚂蚁在巢穴与食物源之间形成近乎直线的路径，而不是曲线或者圆等其它形状，如图1(a)所示。蚂蚁群体不仅能完成复杂的任务，而且还能适应环境的变化，如在蚁群运动路线上突然出现障碍物时，一开始各只蚂蚁分布是均匀的，不管路径是否长短，蚂蚁总是先按同等概率选择各条路径，如图1(b)所示。蚂蚁在运动过程中，能够在其经过的路径上留下信息素，而且能感知这种物质的存在及其强度，并以此指导自己运动的方向，蚂蚁倾向于信息素浓度高的方向移动。相等时间内较短路径上的信息量就遗留得比较多，则选择较短路径的蚂蚁也随之增多，如图1(c)所示。不难看出，由于大量蚂蚁组成的蚁群集体行为表现出了一种信息正反馈现象，即某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大，蚂蚁个体之间就是通过这种信息交流机制来搜索食物，并最终沿着最短路径行进，如图1(d)所示。

蚁群是如何完成这些复杂任务的呢？仿生学家经过大量的观察、研究发现，蚂蚁在寻找食物时，能在其经过的路径上释放一种蚂蚁特有的信息素，使得一定范围内的其他蚂蚁能够感觉到这种物质，且倾向于朝该物质强度高的方向移动。因此，蚁群的集体行为表现为一种信息正反馈现象：某条路径上经过的蚂蚁数越多，其上留下的信息素也就越多(当然，随时间的推移会逐渐蒸发)，后来蚂蚁选择该路径的概率也越高，从而更增加了该路径上信息素的强度。随着时间的推移，整个蚁群最终会收敛到最短的遍历路径上。

蚁群算法最初是用于解决旅行商问题，旅行商问题的简单形象描述是：给定n个城市，有一个旅行商从某一城市出发，访问各城市一次且仅有一次后再回到原出发城市，要求找出一条最短的巡回路径。

作为一种新兴的启发式仿生智能优化算法，目前人们对蚁群优化算法的研究已经由当初单一的旅行商问题领域渗透到了多个应用领域，由解决一维静态优化问题发展到解决多维动态组合优化问题，由离散域范围内的研究逐渐拓展到了连续域范围内的研究，而且在蚁群优化算法的硬件实现上也取得了很多突破性进展，从而使这种新兴的仿生优化算法展现出勃勃生机和广阔的发展前景。

(三)发明内容

本发明提出了一种基于蚁群聚类的多模板图像分割方法，其目的是提供一种解决图像分割问题的有效途径，也可应用于其它复杂的智能优化问题。

该方法将图像看作是具有不同梯度特征的像素点的集合，运用蚁群优化对其进行边缘的聚类，从而实现图像的分割，再根据不同模版的边缘提取结果设定初始聚类中心，对算法进行改进，并用改进后的算法对图像进行聚类分析，提取出图像的边缘。

蚁群算法最初是用于解决旅行商问题(Traveling Salesman Problem，TSP)，旅行商问题的简单形象描述是：给定n个城市，有一个旅行商从某一城市出发，访问各城市一次且仅有一次后再回到原出发城市，要求找出一条最短的巡回路径。

基本蚁群算法的数学模型如下：

设b_i(t)表示t时刻位于元素i的蚂蚁数目，τ_ij(t)为t时刻路径(i，j)上的信息量，n表示TSP规模，即城市总数目，m为蚁群中蚂蚁的总数目，则$m=\underset{i=1}{\overset{n}{\Sigma }}{b}_i\left(t\right);$$\Gamma =\left\{{\tau }_{\mathrm{ij}}\left(t\right)\right|c_i,c_j⋐C\}$是t时刻集合C中元素(城市)两两连接l_ij上残留信息量的集合。在初始时刻各条路径上信息量相等，并设初始信息量为τ_ij(0)＝const。

蚂蚁k(k＝1，2，.....，m)在运动过程中，根据各条路径上的信息量决定其转移方向。这里用禁忌表tabu_k(k＝1，2，....，m)来记录蚂蚁k当前所走过的城市，集合tabu_k随着进化过程作动态调整。

搜索过程中，蚂蚁根据各条路径上的信息量及路径的启发信息来计算状态转移概率。

表示在t时刻蚂蚁k由元素(城市)i转移到元素(城市)j的状态转移概率

式中，allowed_k＝{C-tabu_k}表示蚂蚁k下一步允许选择的城市。

α为信息启发式因子，表示轨迹的相对重要性，反映了蚂蚁在运动过程中所积累的信息在蚂蚁运动时所起的作用，其值越大，则该蚂蚁越倾向于选择其它蚂蚁经过的路径，蚂蚁之间协作性越强；

β为期望启发式因子，表示能见度的相对重要性，反映了蚂蚁在运动过程中启发信息在蚂蚁选择路径中的受重视程度，其值越大，则该状态转移概率越接近于贪心规则。

η_ij(t)为启发函数，其表达式如下

${\eta }_{\mathrm{ij}}\left(t\right)=\frac{1}{d_{\mathrm{ij}}}---\left(2\right)$

式中，d_ij表示相邻两个城市之间的距离。对蚂蚁k而言，d_ij越小，则η_ij(t)越大，也就越大。显然，该启发函数表示蚂蚁从元素(城市)i转移到元素(城市)j的期望程度。

为了避免残留信息素过多引起残留信息淹没启发信息，在每只蚂蚁走完一步或者完成对所有n个城市的遍历(也即一个循环结束)后，要对残留信息进行更新处理。这种更新策略模仿了人类大脑记忆的特点，在新信息不断存入大脑的同时，存贮在大脑中的旧信息随着时间的推移逐渐淡化，甚至忘记。

由此，t+n时刻在路径(i，j)上的信息量可按如下规则进行调整

τ_ij(t+n)＝(1-ρ)·τ_ij(t)+Δτ_ij(t)        (3)

$\Delta {\tau }_{\mathrm{ij}}\left(t\right)=\underset{k=1}{\overset{m}{\Sigma }}\Delta {\tau }_{\mathrm{ij}}^k\left(t\right)---\left(4\right)$

式中，ρ表示信息素挥发系数，则1-ρ表示信息素残留因子，为了防止信息的无限积累，ρ的取值范围为：$\rho ⋐\left[\mathrm{0,1}\right);$

Δτ_ij(t)表示本次循环中路径(i，j)上的信息素增量，初始时刻$\Delta {\tau }_{\mathrm{ij}}^k\left(0\right)=0,$表示第k只蚂蚁在本次循环中留在路径(i，j)上的信息量。

在Ant-Cycle模型中：

(5)

式中，Q表示信息素强度，它在一定程度上影响算法的收敛速度；

      L_k表示第k只蚂蚁在本次循环中所走过路径的总长度。

本发明一种基于蚁群聚类的多模板图像分割方法，其具体实现步骤如下(可参见图2)：

步骤一：图像预处理

由于进行图像分割的图片格式、大小及特征存在着各种差异，很多时候都不适合对图像直接进行分割。因此，在图像分割之前对图像进行锐化等预处理，可以使其特征更加突出，使得最终提取效果更好。

这些预处理步骤主要包括：

(1)图像的读取并转换为灰度图像

对于不同格式的图像先都转换为灰度图像再进行边缘分割。这样使得处理方法统一，便于进行编程设计。

(2)图像大小的调整

对于不同情况下采集到的图像，其大小规格各不相同，现将其调整到一个合适的大小再进行后续处理，节省时间且提高效果。

(3)中值滤波去噪声和图像的锐化

图像去噪声，可减轻图像分割时噪声的影响，从而可大大提高分割精度和准确性；图像锐化，可使图像的边缘特征更加突出，从而使得最终效果更佳。

经过预处理后，图片大小适宜，噪声较少，边缘特征鲜明，适合于后续的图像分割工作。

步骤二：确定各像素的属性

由于是提取图像的边缘，故用多种模版(如Laplacian模版、Canny模版等)的计算所得的梯度值作为个像素点的属性。模板选择依据不同的图像，和不同模板适用范围，选择最适用于该图像的两种模板。

选择好两种模板(模板A，模板B)后，计算图像各像素点的模板A梯度与模板B梯度，作为各点的两个属性、蚁群搜索的依据。

根据两种梯度，分别计算各自的边缘点集合。由其中一种模版提取图像的边缘点集为a，由另一种模版提取图像的边缘点集为b。

可选择的模板有：Laplacian模版，Canny模版，Sobel模版，Roberts模版等。

步骤三：计算初始聚类中心和初始优化度函数值F₀

将a与b的交集a∩b作为初始边缘点集，所有属于a∩b的像素的两个属性各自的平均值作为初始聚类中心(Cen_a，Cen_b)。所有属于a∩b的像素点的两个属性值构成两个数组，记为ab₁₁，ab₁₂。

F₀＝var(ab₁)+var(ab₂)           (6—1)

其中，var是计算方差的函数。

在以后的每一次迭代中，都会得到一个边缘点集，将这个边缘点集中像素点的两个属性构成两个数组，记为ab_i1，ab_i2。(i是迭代次数)

F＝var(ab_i1)+var(ab_i2)             (6—2)

优化度函数F是表征边缘提取优化程度的函数，F越小，表明边缘点集的属性方差和越小，边缘提取结果越好。

步骤四：根据初始聚类中心确定搜索点集并初始化信息素浓度和相关参数

将属于Laplacian或者Canny边界的各点直接保留，求剩下各点到初始聚类中心的距离。假设某点属性为(x，y)，那么其到聚类中心的距离为

$d=\sqrt{({|x-{\mathrm{Cen}}_a|}^2+{|y-{\mathrm{Cen}}_b|}^2)}---\left(7\right)$

一般而言，保留当中离聚类中心最近的12％左右比较合适，其它点是边界点的可能性很小(几乎为零)，就可以直接舍去，在以后的搜索中不再考虑它们，这样可以减少很多计算量，从而大大提高了聚类搜索效率。

将属于a∩b的点(A_and_B)赋予初始信息素浓度0.95，属于a或者b但不属于a∩b的点(A_or_B)赋予初始信息素浓度0.5，保留的12％的点中，离聚类中心最近的前半部分(Center-front)赋予初始信息素浓度0.3，后半部分(Center-back)赋予初始信息素浓度0.2，从而得到信息素浓度矩阵τ。

相关参数初始化：设置N_Cmax，M，ρ，ζ，其中：Nc_max为本算法最大循环次数；M为蚂蚁总数目；ρ是信息素残留系数，即每一代过后信息素的残留；ζ为系数，根据分割图像的实际情况确定其值大小。

步骤五：将M只蚂蚁放置在随机的位置，每只蚂蚁分别对搜索点集进行聚类并更新全局最优

根据信息素浓度，依据概率选择公式

其中，rand( )为随机数；确定是否把某点归到边界点集内，这样M只蚂蚁可以得到M种结果。蚂蚁的数量M通过实际需要和图像的大小由经验设定。

分别计算每一次迭代中M种结果的边缘优化度F。取F最小的那个结果作为本代最优的F_dbest。比较F_dbest与全局最优F_gbest，如果F_dbest小于F_gbest，那么将本代最优结果更新为全局最优，本代F_dbest赋予F_gbest。

每一次迭代中都会产生一个本代最优边缘像素点集L_Best，完成N_Cmax次迭代后，产生一个全局最优L_gbest。

步骤六：更新信息素浓度

每一次迭代结束后，要进行信息素更新，其更新规则如下

τ(t+1)＝ρ·τ(t)+Δτ(t)              (9)

其中，ρ是信息素残留系数，即每一代过后信息素的残留。Δτ是信息素浓度增量矩阵，其值用下式进行计算。

$\mathrm{\Delta \tau }=\frac{\zeta ·F_0}{F_{\mathrm{dbest}}}\times L_{\mathrm{Best}}---\left(10\right)$

其中，F_dbest为本代最优的边缘优化度；

      L_Best为本代最优边缘像素点集；

      ζ为系数，根据分割图像的实际情况确定其值大小。

步骤七：重复返回的步骤五和步骤六，直到完成预定的算法循环次数N_Cmax

步骤八：算法结束，并输出最优结果。全局最优边缘像素点集L_gbest。

其中，用于图像边缘提取的两种模板A和B选择Laplacian模版，Canny模版，Sobel模版，Roberts模版中任意两种的组合。

其中，用于图像边缘提取的两种模板A和B选择Laplacian模版和Canny模版。

本发明一种基于蚁群聚类的多模板图像分割方法，其优点及功效在于：该方法为解决视觉信息处理领域中图像分割问题的有效途径，应用领域广泛，如航空、航天、机器人、工业生产等涉及图像信息处理的领域。

(四)附图说明

图1现实中蚁群寻找食物的过程

图2基于蚁群聚类的多模板图像分割流程

图3蚁群聚类进化曲线

图中标号及符号说明如下：

F₀——初始优化度函数值

m——正在计算的蚂蚁数

M——蚂蚁总数目

F_dbest——本代最优解

F_gbest——全局最优解

Nc——算法循环次数

Nc_max——算法最大循环次数

Y——满足条件(是)

N——不满足条件(否)

(五)具体实施方式

下面通过一个具体实施例来验证本发明所提基于蚁群聚类的多模板图像分割方法的性能，所采用的是一幅570*447的jpg格式的图像作为验证对象。实验环境为P43.06Ghz，1G内存，MATLAB7.1版本，其具体实现步骤如下：

步骤一：图像预处理

(1)图像的读取并转换为灰度图像

将验证对象转换为灰度图像再进行边缘分割，使得处理方法统一，便于进行编程设计。

(2)图像大小的调整

将其调整到一个合适的大小再进行后续处理，节省时间且提高效果。

(3)中值滤波去噪声和图像的锐化

图像去噪声，减轻图像分割时噪声的影响，；图像锐化，使图像的边缘特征更加突出。

经过预处理后，图片大小适宜，噪声较少，边缘特征鲜明，适合于后续的图像分割工作。

步骤一：参数初始化：N_Cmax＝100，M＝8，ρ＝0.9，ζ＝0.15，A_and_B初始信息素浓度取0.95，A和B初始信息素浓度均取0.5，Center-front初始信息素浓度取0.3，Center-back初始信息素浓度取0.2，模版的选择为Canny和Laplacian。

步骤二：确定各像素的属性

由于是提取图像的边缘，故用各种模版的计算所得的梯度值作为个像素点的属性。计算图像各像素点的Laplacian梯度与Canny梯度，作为各点的两个属性、蚁群搜索的依据。根据两种梯度，分别计算各自的边缘点集合。由Laplacian模版提取图像的边缘点集为a，由Canny模版提取图像的边缘点集为b。

步骤三：计算初始聚类中心和初始优化度函数值F₀

将a与b的交集a∩b作为初始边缘点集，所有属于a∩b的像素的两个属性各自的平均值作为初始聚类中心(0.3，0.2)。

F＝var(ab₁)+var(ab₂)

步骤四：根据初始聚类中心确定搜索点集并初始化信息素浓度和相关参数

将属于Laplacian或者Canny边界的各点直接保留，求剩下各点到初始聚类中心的距离。假设某点属性为(x，y)，那么其到聚类中心的距离为

$d=\sqrt{({|x-0.3|}^2+{|y-0.2|}^2)}$

保留当中离聚类中心最近的12％，将属于a∩b的点(A_and_B)赋予初始信息素浓度0.95，属于a或者b但不属于a∩b的点(A_or_B)赋予初始信息素浓度0.5。

相关参数初始化：N_Cmax＝100，M＝8，ρ＝0.9，ζ＝0.15，A_and_B初始信息素浓度取0.95，A和B初始信息素浓度均取0.5，Center-front初始信息素浓度取0.3，Center-back初始信息素浓度取0.2，模版的选择为Canny和Laplacian。

步骤五：每只蚂蚁分别对搜索点集进行聚类并更新全局最优

根据信息素浓度，依据概率选择公式

        (3)

确定是否把某点归到边界点集内，这样8只蚂蚁可以得到8种结果。

分别计算每一次迭代中8种结果的边缘优化度F。取F最小的那个结果作为本代最优的F_dbest。比较F_dbest与全局最优F_gbest，如果F_dbest小于F_gbest，那么将本代最优结果更新为全局最优，本代F_dbest赋予F_gbest。

每一次迭代中都会产生一个本代最优边缘像素点集L_Best，完成100次迭代后，产生一个全局最优L_gbest。

步骤六：更新信息素浓度

每一次迭代结束后，要进行信息素更新，其更新规则如下

τ(t+1)＝0.9·τ(t)+Δτ(t)

$\mathrm{\Delta \tau }=\frac{0.15·F_0}{F_{\mathrm{dbest}}}\times L_{\mathrm{Best}}$

步骤七：重复返回的步骤五和步骤六，直到完成预定的算法循环次数N_Cmax＝100。

步骤八：算法结束，并输出最优结果。全局最优边缘像素点集L_gbest。

由实验运行的结果可见，Canny模版提取的边界的效果很好，但是图像的细节过多，有很多线条，却没有很好的反映各个相对独立的部分仅仅是边界的线条堆砌。Laplacian模版提取的图像具有同样问题，而且对于一些较暗的区域并没有很好的把边缘检测出来；而使用本文的基于蚁群优化的方法对图像分割，由实验结果可见，较暗地方可以很好检测出来，而且不会显得细节过多，整个分割图像层次感比较强，线条彼此之间是构成图像中的各个部分，而不仅仅是线条堆砌，分割结果比较准确。实验表明本发明所提出的分割方法有效地提高了分割速度和区域完整性，表明这种方法能够取得好的分割效果。图3所给出的进化过程较为平稳地趋于一个最优值，最后达到稳态收敛。