基于自适应粒子群优化的三维OTSU图像分割算法

曾业战，王润民

（1.湖南理工学院 物理与电子学院，湖南 岳阳 414000；2.湖南科技大学 信息与电气工程学院，湖南 湘潭 411201）

图像分割是图像处理和计算机视觉的关键环节，是进行图像识别、分析和理解的基础。近几年来随着电子技术和计算机的飞速发展，应用计算机技术进行图像分割广泛应用于军事、遥感、气象等方面。在常用的图像分割算法中，基于灰度直方图的阈值分割方法以其简单实用的特点引起了研究者普遍重视。1979年日本学者大津展之提出了一维OTSU算法[1],该方法依据一维直方图,以目标和背景的类间方差最大为阈值选取准则，在一般情况下能够取得好的效果，但一维OTSU算法在分割含有噪声的图像时，分割效果并不理想。在一维OTSU的基础上，二维OTSU分割算法利用了图像象素与其邻域空间的相关信息因而具有更强的抗噪性能[2]，并且由于该算法直观、简便、运行速度快等特点而受到广大学者的关注，但二维OTSU算法假设对象区域和背景区域上的概率和近似为1普遍性不够。文献[3]引入邻域中值作为第三个特征构造了三维灰度直方图，提出了一种三维OTSU的图像分割算法，该算法对低对比度、低信噪比的图像获得了更好的分割效果，特别对高斯噪声或椒盐噪声和叠加了混合噪声（高斯噪声加椒盐噪声）的图像有很好的抗噪性能，但三维OTSU运算时间长，占用内存空间大。文献[4]对三维OTSU分割算法的递推公式进行了改进，使得算法的运算时间得到减少。为进一步减少运算时间，本文结合分割图像的具体信息，综合利用图像的分割阈值与目标区域的关系，提出了一种基于自适应粒子群优化的三维OTSU图像分割算法，并进行了仿真和分析。

1 基本理论

1.1 粒子群算法

粒子群算法的基本思想是通过群体中个体之间的协作和信息共享来寻找最优解，是一种基于群集智能方法的演化计算技术。由于算法设置参数少、实现容易、精度高、收敛快等优点引起了学术界的高度重视，目前已广泛应用于函数优化、神经网络训练、模糊系统控制以及其他遗传算法的应用领域。类似于其他进化算法，粒子群算法对每个优化问题的解设为搜索空间中的一个粒子，每个粒子根据求解问题参数用一个相应的适应度进行匹配，粒子飞行的速度决定飞行的距离和方向，通过迭代追寻当前的最优粒子。

设D为搜索空间的维数，粒子i的位置和速度分别用Xi=（xi1，xi2，…,xiD）、Vi=（vi1，vi2，…，viD）表示，pid=（pi1，pi2，…，piD）为粒子i曾经到达的最好位置，pg表示种群的最好位置。在每一次迭代中，粒子根据本身的最优解pi和整个种群的最优解pg修正自己的速度和位置最后找到最优解[5]。速度和位置根据如下方程进行更新

1.2 三维OTSU分割算法

在二维OTSU算法的基础上，三维OTSU分割算法引入邻域中值作为第3个特征构造了三维灰度直方图。对于尺寸为 M×N、灰度范围为{0，1，…L－1}的数字图像，设像素点（x，y）的灰度值为 f（x，y），定义 h（x，y）和 g（x，y）分别为像素点（x，y）处 r×r的邻域均值和邻域中值，g（x，y）、h（x，y）灰度变化范围均为{0，1，…L－1}。 采用（f（x，y），g（x，y），h（x，y））表示三向量（i，j，k）组成的三维直方图，3个坐标分别代表像素的灰度值、邻域均值和邻域中值，三维直方图构成大小为L×L×L的正方体区域，如图 1（a）所示。 向量（i，j，k）发生的频率为:

图1 图像的三维直方图Fig.1 Three-Dimension histogram image

采用 sB的迹作 trsB（i，j，k）为类间的离散度测度[3－4]，即：

2 三维OTSU图像分割算法

由式（4）可知，在计算三维 OTSU的离散度测度时 ui、uj、uk和Ps（0）只与背景区域相关，如果能确定背景区域的大概范围，则可进一步减少 ui、uj、uk、Ps（0）和 trsB（i，j，k）运算量。 由于三维OTSU算法的最佳分割阈值（i*，j*，k*）小于目标区域灰度均值（gm，gm，gm），本文提出一种基于自适应粒子群优化的三维OTSU图像分割算法。首先采用最佳熵分割算法初步提取目标区域，选取该目标区域的平均灰度值gm作为背景区域，即三维 OTSU 背景区域范围为（gm×gm×gm，gm＜L），在此基础上再采用三维OTSU算法进行分割。因为背景区域的搜索空间从（L×L×L）降到了（gm×gm×gm），相应的 ui、uj、uk、Ps（0）和 trsB（i，j，k）的计算量也由 O（L3）降为 O（gm3），所以运算量进一步减少。

在求解 trsB（i，j，k）时需 7 次乘法和一次除法，运算复杂、计算量大、占用的时间长，而粒子群算法具有搜索速度快、效率高，算法简单等优点，本文通过粒子群算法优化trsB最大时三维OTSU的最佳分割阈值i*，j*，k*。由于三维OTSU求解分割阈值含有3个参数，因此粒子群初始化为3维向量（i*，j*，k*），每个向量分别代表像素的灰度值、邻域均值和邻域中值。初始化种群大小为80，最大迭代次数为500次，加速系数c1=1.49、c2=1.49，其适应度函数fit设为:

该算法的实现步骤包括:

1）采用基于最佳熵的分割算法初步提取目标区域并计算该目标区域的平均灰度值gm。

2）根据gm自适应地设置三维OTSU背景区域范围为（gm×gm×gm，gm＜L），并计算参数 ui、uj、uk、Ps（0）。

3）初始化粒子群算法的种群大小，迭代次数、加速系数c1与c2、惯性权重w及粒子的初始速度和位置。

4）根据式（6）计算粒子的适应度值，更新粒子的速度和位置。

5）如果达到最大迭代次数，则输出最佳分割阈值i*，j*，k*，否则转步骤 4）。

3 结果与分析

实验是在Intel Dual 1.6 GHz、1 G内存、编程环境为Matlab 7.0的笔记本电脑上进行。选取加有均值为零、方差为20的高斯白噪声的图像Peppers、Barbara、Lena3幅图像进行测试，图像大小为512×512像素，表1给出了二维OTSU算法、文献[4]分割算法和本文分割算法的运算时间，从仿真结果可以看出，在运算时间方面，本文分割算法的运算时间比二维OTSU算法要长，主要是由于搜索空间从二维扩大到三维，再加上三维OTSU算法本身的复杂性，导致运算量增加、计算时间长，但明显优于文献[4]所采用的分割算法，主要是由于背景区域的搜索空间从（L×L×L）降到了（gm×gm×gm），相应参数计算量也由O（L3）降为O（gm3），另外采用粒子群算法优化最佳分割阈值，进一步减少了运算时间；在分割效果方面，从图2可以看出，对零均值的高斯白噪声图像，本文算法分割效果与文献[4]分割算法相似，但优于二维OTSU算法分割，如在Barbara的脸部和桌子的阴影部分，能够有效的抑制目标和背景处的大部分噪声。

表1 不同算法的运算时间（s）Tab.1 Different algorithms for computing time（second）

图2 噪声方差为20时不同方法对图像的分割结果Fig.2 Noise variance for 20 different algorithms for segmentation result

4 结 论

本文从分割图像自身特点出发，提出了一种基于自适应粒子群优化的三维OTSU图像分割算法。首先根据目标区域的平均灰度值自适应地设定三维OTSU图像分割算法的背景区域搜索范围，然后采用基于三维OTSU图像分割算法和粒子群算法对图像进行分割。该方法综合利用了图像目标区域平均灰度值与OTSU算法背景区域范围的关系，减小了计算的运算量。另外，引入粒子群算法优化最佳分割阈值，进一步提高了算法的运行效率。

[1]Otsu N.A threshold selection method from gray-level histograms[J].IEEE Transactions on System Man and Cybernetic，1979，9（1）：62－66.

[2]邱丽君，侯德文，王依才.改进的二维Otsu图像分割方法的研究[J].计算机工程与应用，2010，46（33）：195－197.

QIU Li-jun，HOU De-wen，WANG Yi-cai.Research on modified two-dimensional Otsu of image segmentation algorithm[J].ComputerEngineeringandApplications，2010，46（33）：195－197.

[3]景晓军，李剑峰，刘郁林.一种基于三维最大类间方差的图像分割算法[J].电子学报，2003，31（9）：1281－1285.

JING Xiao jun，LI Jian feng，LIU Yu lin.Image segmentation based on 3-D maximum between-Cluster variance[J]，Acta Electronica Sinica，2003，31（9）：1281－1285.

[4]范九伦，赵凤，张雪峰.三维OTSU阈值分割方法的递推算法[J].电子学报，2007，35（7）：1398－1402.

FAN Jiu-lun，ZHAO Feng，ZHANG Xue-feng.Recursive algorithm for Three-Dimensional Otsu's thresholding segmentaion method[J].Acta Electronica Sinica，2007，35（7）：1398－1402.

[5]李娟，饶妮妮，廖瑞华，等.基于改进粒子群算法的AdHoc网络移动模型研究[J].电子学报，2010，38（1）：222-227.

LI Juan，RAO Ni-ni，LIAO Rui-hua，et al.Mobility model based on the improved-PSO algorithm for ad hoc network[J].Acta Electronica Sinica，2010，38（1）：222-227.

[6]迟玉红，孙富春，王维军，等.基于空间缩放和吸引子的粒子群优化算法[J].计算机学报，2011，34（1）：115-130.

CHI Yu-hong,SUN Fu-chun，WANG Wei-jun，et al.An improved particle swarm optimization algorithm with search space zoomed factor and attractor[J].Chinese Journal of Computers，2011，34（1）：115-130.

[7]LV Yan，GONG Qu.Application of weighting 3D-Otsu method in image segmentation[J].Application research of computers，2011，28（4）：1576-1579.