张　冬，刘俊焱，薛联凤，云　挺

(南京林业大学 信息科学技术学院，江苏 南京 210037)



基于NCSPSO-AFSA优化SVM的林木冠层图像分割

张冬，刘俊焱，薛联凤，云挺

(南京林业大学 信息科学技术学院，江苏 南京 210037)

[摘要]【目的】 对林木冠层图像采用NCSPSO-AFSA优化支持向量机(SVM)进行图像分割，提取树干分割图，以进一步提高分割效果。【方法】 对现有的小生境和交叉算子的粒子群算法(NCSPSO)进行优化，并与人工鱼群算(AFSA)混合，寻找最优惩罚系数C和高斯核函数中的参数γ；然后运用SVM方法对训练样本进行综合训练，以建立最佳分类模型；最后对香樟树、马褂木和杨树的冠层图像进行分割，并与AFSA算法、NCSPSO算法的分割效果进行比较。【结果】 AFSA、NCSPSO、NCSPSO-AFSA算法的平均运行时间分别为178.909，154.661和97.213 s，平均分割准确率分别为90.83%，94.08%和98.90%，表明改进的NCSPSO-AFSA混合算法在效率上较其他2种算法提高了63%以上，而且分割准确率提高了5%～8%。【结论】 运用NCSPSO-AFSA优化SVM方法对林木冠层图像进行树干图像分割，可得到最佳分割效果。

[关键词]林木图像分割；NCSPSO；人工鱼群；支持向量机

利用图像处理和计算机视觉的方法对林木冠层遥感图像进行分割，在林分调查、森林蓄积量计测和碳汇估算中具有重要意义。由于林木冠层图像背景的复杂性，从中准确地分割出目标植物成为后续图像研究的关键问题之一。迄今为止，针对林木图像还没有一种普遍使用的分割方法。在众多分割算法中，大津法(Otsu法)得到广泛使用，并发展出各种优化的算法用于特定对象的分割[1]。基于灰度共生矩阵(Gray level co-occurrence matrix,GLCM)的图像特征分析是一种经典的二阶统计法， Haralick等[2]用GLCM特征对遥感图像进行分类研究，精度达80%左右。基于马尔科夫(Markov)随机场模型的方法也在遥感图像的分割研究中占据重要的地位，白雪冰等[3]提出的Markov-SA优化方法及李云峰等[4]建立的基于小波域的隐马模型，均在树木图像的分割方面取得了很好的效果，但是该算法的复杂度较高。支持向量机(Support vector machine，SVM)是一种基于统计学习理论的机器学习方法，通过合适的训练后泛化性能好，且能较好地处理小样本和非线性等问题。本研究尝试用优化支持向量机对林木图像进行分割，首先对基于小生境和交叉选择算子的粒子群算法[5-9](Niche crossover selection particle swarm optimization，NCSPSO)进行改进，提高其稳健性；再将改进的NCSPSO算法与人工鱼群(AFSA)算法进行混合，将前者的稳健性优势与后者的快速收敛优势相结合；最后用混合后的算法及AFSA算法、NCSPSO算法分别优化SVM[10-14]，比较各种方法对林木冠层图像的分割效果，从而验证本算法在速度和精度上的优势。

1现有的NCSPSO算法

NCSPSO算法主要分为3个阶段：①利用小生境技术计算粒子之间的距离，找到每个粒子所属的小生境群体；②在每一个子群中，利用传统的PSO算法更新方式进行粒子速度和位置的更新；③对更新后的群体，根据粒子间的距离，利用共享函数更新粒子的适应度，对于适应度最低的粒子，利用惩罚系数C惩罚相应的粒子。最后保留每个粒子的群体最优个体，直到满足终止条件。

1)小生境群体的划分。对于粒子Xi=(xi1,xi2,…,xin),i=1,2,…,N，粒子间距离用下式计算：

dij=‖Xi-Xj‖,j=1,2,…,N。

(1)

式中：dij为粒子间距离，Xi和Xj分别指在D维下第i和第j个粒子的历史最好位置。给定小生境半径参数σ，如果粒子之间的距离dij<σ，则该粒子加入Xpi，pi为Xpi中的元素。

2)粒子之间的共享函数。粒子i与粒子j之间的共享函数为：

(2)

式中：k为控制共享函数形状的参数。

3)适应度值函数的更新。根据共享机制函数更新粒子的适应度：

(3)

(4)

(5)

(6)

式中：Gl为选择算子，用于保留群体最优个体；f(·)为求解问题的目标函数。

2NCSPSO算法的改进

2.1引入变异算子

2.1.1变异算子改进本研究在NCSPSO算法的交叉操作之后引入变异机制，对适应度比小生境数最小的个体的适应度还要低的个体进行变异操作。由于本研究要将改进的NCSPSO算法应用于SVM参数优化，并最终将优化过的SVM分类模型应用到图像分割，而图像分割的效果以分割精度为准，这使得优化算法中适应度值的作用显得尤为重要。很多变异算子的设置随进化代数的不断增长而逐步变小，强调了变异算子的动态性，却没有考虑到变异后个体所获得的适应度值是否逼近最优适应度值。如果个体在变异之后所获得的适应度值并没有靠近最优适应度值，但是变异算子更小了，这样会导致其子代的变异很小，反而使得算法不能快速收敛[14]。考虑到本研究的最终目的，在引入变异算子的同时，对变异算子进行相应的改进：

(7)

根据变异因子，本研究对适应度值小于孤立点适应度值的个体进行如下变异处理：

(8)

如果当代个体的适应度较差，那么其更新就希望更能靠近最优个体，因此个体变异率的取值需要变大些。如果更新后个体的适应度优于父代的适应度，则证明新的个体更加逼近最优解，这时其变异应该相应变小。如果下代中得到的新个体的适应度差于父代的适应度，这时新个体的变异率应该更大，这样产生的下代个体的变异范围也变大，会有寻找到更优个体的机率，从而不停地使个体向着最优个体进化。

2.1.2径向基核函数为避免高维空间的向量内积而造成大量运算，本研究采用径向基核函数计算高维空间向量内积，其形式如下:

K(xi,xj)=exp(-γ‖xi-xj‖2),γ>0。

(9)

式中：xi为粒子x在i处的位置；xj为核函数的中心；‖·‖2为粒子xi到核函数中心距离的平方；γ为核函数中的重要参数，直接影响着模型的分类精度，γ的取值越大则核函数的径向作用范围越大，反之则越小。

惩罚参数C是另一个影响着SVM分类的关键参数，用于控制模型复杂度和逼近误差的折中，C的取值越大，则SVM对数据的拟合度越高，在一定程度上有利于降低出错率，但是容易造成“过学习”的问题；相反，若C的取值过小，则对错分的惩罚力度降低，出错率会上升，但易造成“欠学习”问题。常见的参数选择方法有穷举法、交叉验证法、基于遗传算法的参数确定法和基于粒子群算法的SVM模型参数选择方法[15]。

2.1.3改进效果用无变异算子、固定取值的变异算子(以FG1=0.2，FG2=0.9为例)、传统的动态变异算子(FG=FG1+rand(0,1)·(FG2-FG1))和改进变异算子对香樟树、马褂木和杨树的林木冠层图像进行分割测试，图像分割时间为获得C和γ后建立的分类模型对图像进行分割所用的时间。从表1可以看出，引入经过本研究改进的变异算子，使得林木图像的分割准确率均略高于其他变异算子，而且所用的图像分割时间也远远短于其他方式。可见，本研究对于变异算子的改进使得NCSPSO算法的性能有所提高。

表 1　树木图像分割时不同变异算子的训练结果

注：TDMD代表传统的动态变异算子；IMO代表改进的变异算子。

Note:TDMD is traditional dynamic mutation operator;IMO is impreved mutation operator.

2.2引入族外竞争机制

在NCSPSO算法的选择操作中，如果新个体的适应度优于旧个体，则用新个体替代旧个体，否则保留旧个体。选择操作是在同一个种群中不同小生境之间形成的竞争，即内部竞争。为了增加个体之间的竞争压力，本研究将个体之间的竞争扩大到不同种群之间，在个体参与内部竞争之后，增加一步族外竞争，将进化种群中最优解的个体与随机组成的种群的最优解形成竞争，如果随机生成的种群的最优解优于进化种群的最优解，那么用随机种群中的最优个体替代进化种群中的适应度值较差的一组个体。族内竞争使个体尽量避免落入局部最优，而族外竞争使目标函数值向全局最优解快速收敛。

同时，为了实现族外竞争机制，需要对算法中初始种群的划分做出相应调整。调整的思想来源于隔离机制小生境的基本思想。本研究将初始种群称作主群，同时将主群任意分为若干子群，每个子群是由主群的一部分和其他子群的全局最优值构成的。而在整个算法的迭代过程中，主群的进化更新与子群的进化更新相互独立，互不干扰。

3 改进NCSPSO与AFSA 的混合算法

本研究将AFSA算法和改进的NCSPSO算法采用并行的方式进行混合。混合算法的思想是，AFSA算法通过构造人工鱼群模式鱼群觅食方法，采用聚群、追尾等行为更新当前最佳状态，从而获取最优解，该法搜索空间具有一定的自适应能力，应用于SVM参数优化具有较高的寻优效率。改进的NCSPSO算法通过引入变异算子和族外竞争机制，最大程度上避免了粒子在寻优过程中陷入局部最优。改进的NCSPSO算法能够弥补AFSA算法在后期收敛速度慢的缺点。将改进的NCSPSO算法和AFSA算法并行混合，首先将处理过的特征图像数据作为改进的NCSPSO算法和AFSA算法的初始训练样本参数，并生成初始的适应度值。2个算法分别根据这组样本参数找到各自的最优解，比较最优解并选出全局最优解，该最优解即为所求。改进的NCSPSO和AFSA混合算法流程如图1所示。

图 1改进的NCSPSO-AFSA混合算法的技术流程

Fig.1Technology roadmap of improved NCSPSO-AFSA hybrid algorithm

4结果与分析

本研究的软件平台为MATLAB R2011a，运行环境为四CPU PC机，CPU是主频为3.2 G的Intel 志强多线程处理器，内存8 G，硬盘大小1 000 G，操作系统是Windows 7 Professional SP1。所用香樟树、马褂木、杨树林木冠层图是用鱼目摄像机(Cannon EOS 60D和Sigma EX-DC 4.5 mm鱼眼镜头)获得半球图像，图像像素大小为128×128。为了使研究更有意义，特考虑地类、优势树种等因素，对不同类树种进行对比分析。

4.1图像特征的提取

将原始图像各个像素提取转变为HSV(hue,saturation,value)颜色空间下的H、S、V值，以便对原图像进行颜色处理和识别，处理结果如图2所示。

图 2　香樟树、马褂木和杨树的HSV分量图

图像特征提取也是极其重要的一部分，不同的图像特征提取方法，会在很大程度上影响分类结果的优劣。曲波变换作为纹理分析方法，对图像进行分割的效果非常理想[16-17]。灰度共生矩阵 (Gray-level Co-occurrence Matrix)法是图像纹理分析方法的一种，它反映不同像素相对位置的空间信息，在一定程度上反映了纹理图像中各灰度级在空间上的分布特性，常用于通过纹理分析来进行图像分割[18]。

参照文献[17]的方法，将曲波变换与本研究优化的SVM方法相结合，对3幅林木冠层图像进行提取，同时应用灰度共生矩阵法进行提取，结果如表2所示。从表2可以看出，曲波变换结合改进的SVM法对林木冠层图像取得了较好的分割效果，相比灰度共生矩阵法，不仅提高了分割率，平均运行速度也快于灰度共生矩阵法。

表 2　不同特征提取方法对3个树种冠层图像的提取结果

4.2图像的分割效果

为了对比，分别用改进的NCSPSO-AFSA混合算法、AFSA算法、NCSPSO算法优化SVM，建立分类模型，对3幅林木图像进行分割，结果如表3所示。同时，给出了3幅图像树干的最终分割效果图，如图3所示。结合图3和表3可以得出，AFSA优化SVM算法对3幅林木冠层图像的平均分割准确率为90.83%，NCSPSO优化SVM算法的平均分割准确率为94.08%，NCSPSO-AFSA优化SVM算法为98.90%，3种方法均取得了较好的分割效果；相比NCSPSO优化SVM和AFSA优化SVM对图像的分割效果，NCSPSO-AFSA优化SVM方法的树干分割区域的边缘轮廓更加完整、精确。

表 3　不同算法对3个树种冠层图像的分割结果

图 3　不同算法对3个树种冠层图像的分割效果

4.3训练结果比对

使用上文3种方法寻找最优C和γ，3种方法的进化代数规模相同。从训练结果可以看出，改进的NCSPSO-AFSA算法寻找到的解优于NCSPSO算法和AFSA算法，即在训练过程中，利用NCSPSO-AFSA算法找到的C和γ使得SVM对林木图像的树干分割准确率高于NCSPSO算法和AFSA算法。

从表3可以看出，本研究采用3种优化SVM的林木冠层图像分割方法，均取得了较好的分割效果NCSPSO、AFSA、NCSPSO-AFSA优化SVM的平均分割准确率分别为94.08%，90.83%和98.90%，平均运行时间分别为154.661，178.909和97.213 s，可见NCSPSO-AFSA优化SVM算法不仅分割准确率高，而且运行速度快。

5结语

本研究尝试改进NCSPSO算法，并与AFSA混合优化支持向量机，寻找最佳C和γ，获得了针对林木图像的最佳分类识别模型。将本研究方法与NCSPSO、AFSA法对香樟树、马褂木、杨树冠层图像的分割效果进行对比，发现AFSA、NCSPSO、NCSPSO-AFSA算法的平均运行时间分别为178.909，154.661和97.213 s，平均分割准确率分别为90.83%，94.08%和98.90%，可见改进的NCSPSO-AFSA混合算法在效率上较其他2种算法提高了63%以上，分割精度提高了5%～8%。

[参考文献]

[1]李晓冬,王雪峰,贺鹏,等.林木冠层图像的分割方法研究 [J].中南林业科技大学学报,2013,33(7):40-44.

Li X D,Wang X F,He P,et al.Segmentation method research for forest canopy image [J].Journal of Central South University of Forestry & Technology,2013,33(7):40-44.(in Chinese)

[2]Haralick R M.Statistical and structural approaches to texture [J].Proceedings of the IEEE,1979,67:786-804.

[3]白雪冰,祝贺,张庭亮,等.基于Markov-SA算法的树木图像分割 [J].林业科技,2013,38(5):25-27.

Bai X B,Zhu H,Zhang T L,et al.The tree image segmentation of based on Markov-SA [J].Forestry Science & Technology,2013,38(5):25-27.(in Chinese)

[4]李云峰,曹渝昆,朱庆生,等.基于小波域隐马模型的树木类图像分割算法 [J].计算机应用研究，2007,24(8):233-235.

Li Y F,Cao Y K,Zhu Q S,et al.Multiresolution segmentation approach for tree image based on hidden Markov tree model [J].Application Research of Computers,2007,24(8):233-235.(in Chinese)

[5]向长城,黄席樾,杨祖元,等.小生境粒子群优化算法 [J].计算机工程与应用,2007,43(15):41-43.

Xiang C C,Huang X Y,Yang Z Y,et al.Niche particle swarm optimization algorithm [J].Computer Engineering and Applications,2007,43(15):41-43.(in Chinese)

[6]池元成,方杰,魏鑫,等.基于小生境和交叉选择算子的改进粒子群优化算法 [J].系统仿真报,2010,22(1):111-114.

Chi Y C,Fang J,Wei X,et al.Improved particle swarm optimization algorithm based on niche, crossover and selection operators [J].Journal of System Simulation,2010,22(1):111-114.(in Chinese)

[7]巩敦卫,张勇,张建化,等.新型粒子群优化算法 [J].控制理论与应用,2008,25(1):111-114.

Gong D W,Zhang Y,Zhang J H,et al.Novel particle swarm optimization algorithm [J].Control Theory & Applications,2008,25(1):111-114.(in Chinese)

[8]罗平,姚立海,杨仕友,等.一种改进的粒子群优化算法 [J].江南大学学报自然科学版,2007,6(5):505-509.

Luo P,Yao L H,Yang S Y,et al.An improved particle swarm optimization algorithm [J].Journal of Jiangnan University:Natural Science Edition,2007,6(5):505-509.(in Chinese)

[9]白明明,孙辉,吴烈阳.基于小生境粒子群算法的图像分割方法 [J].计算机工程与应用,2010,46(3):183-185.

Bai M M,Sun H,Wu L Y.Method for image segmentation based on niching particle swarm optimization [J].Computer Engineering and Applications,2010,46(3):183-185.(in Chinese)

[10]张阳,刘永革,景旭.一种改进的线性支持向量机的特征筛选算法 [J].西北农林科技大学学报:自然科学版，2006,34(10):210-212.

Zhang Y,Liu Y G,Jing X.An improved feature selection algorithm for linear SVM classifiers [J].Journal of Northwest A&F University:Natural Science Edition,2006,34(10):210-212.(in Chinese)

[11]Lin C F,Wang S D.Fuzzy support vector machines [J].IEEE Transactions on Neural Networks,2002,13(2):464-471.

[12]丁海勇,卞正富.基于SVM算法和纹理特征提取的遥感图像分类 [J].计算机工程与设计,2008，29(8):2131-2132.

Ding H Y,Bian Z F.Remote sensing image classification based on SVM algorithm and texture feature extraction [J].Computer Engineering and Design,2008,29(8):2131-2132.(in Chinese)

[13]李艳英.基于支持向量机参数优化的群智能优化算法研究 [D].天津:天津大学,2007.

Li Y Y.Study of the swarm intelligence algorithm based on optimizing the parameters of SVM [D].Tianjin:Tianjin University,2007.(in Chinese)

[14]Cristianini N,John S T.An introduction to support vector machines and other kernel-based learning methods [M].New York:Cambridge University Press,2006.

[15]Li Y B,Zhang C B.Support vector machine forecasting method improved by chaotic particle swarm optimization and its application [J].Journal of Central South University of Technology,2009,3:478-481.

[16]戈剑武,祁荣宾,钱锋,等.一种改进的自适应差分进化算法 [J].华东理工大学学报:自然科学版,2009,35(4):600-605.

Ge J W,Qi R B,Qian F,et al.A modified adaptive differential evolution algorithm [J].Journal of East China University of Science and Technology:Natural Science Edition,2009,35(4):600-605.(in Chinese)

[17]王娴,周宇,云挺,等.基于Curvelet变换的荻草细胞图像分割 [J].计算机科学,2012,39(11):277-279.

Wang X,Zhou Y,Yun T,et al.Miscanthus sacchariflorus cells image segmentation based on curvelet transformation [J].Computer Science,2012,39(11):277-279.(in Chinese)

[18]Mohanty A K,Senapati M R,Beberta S,et al.Texture-based features for classification of mammograms using decision tree [J].Neural Computing and Applications,2013,23(3/4):1011-1017.

Segmentation of forest canopy image based on NCSPSO-AFSA optimized SVM

ZHANG Dong,LIU Jun-yan,XUE Lian-feng,YUN Ting

(CollegeofInformationScienceandTechnology,NanjingForestryUniversity,Nanjing,Jiangsu210037,China)

Abstract:【Objective】 NCSPSO-AFSA optimized support vector machine (SVM) algorithm was adopted for image segmentation and extraction of trunk segmentation diagram.【Method】 Niche and Crossover Selection Particle Swarm Optimization (NCSPSO) was optimized before being mixed with Artificial Fish Swarm Algorithm (AFSA) to seek for the best penalty coefficient C and parameter of Gauss kernel function.Then,SVM was used to establish the optimum disaggregated model of training examples.Forest canopy image segmentation test was conducted for Camphor tree,Liriodendron Chinese and Poplar and the results were compared with AFSA and NCSPSO.【Result】 The average running times of AFSA,NCSPSO and NCSPSO-AFSA were 178.909,154.661 and 97.213 s,and the average accuracy rates of segmentation were 90.83%,94.08%,and 98.90%,respectively.The efficiency and accuracy rate of the optimized NCSPSO-AFSA mixed algorithm were enhanced by 63% and 5%-8%,repsecitvely.【Conclusion】 NCSPSO-AFSA optimized SVM can get best consequence for trunk image segmentation based on forest canopy image.

Key words:forest image segmentation;NCSPSO;artificial fish swarm algorithm;support vector machine

DOI：网络出版时间:2016-02-0209:3710.13207/j.cnki.jnwafu.2016.03.017

[收稿日期]2014-08-04

[基金项目]国家自然科学基金项目(31300472)；江苏省自然科学基金项目(BK2012418)

[作者简介]张冬(1989-)，男，陕西延安人，硕士，主要从事计算机视觉、模式识别研究。E-mail:shang_jia927@163.com[通信作者]薛联凤(1972-)，女，陕西西安人，副教授，硕士，主要从事虚拟现实与机器视觉研究。E-mail:285201972@qq.com

[中图分类号]S758.5+8

[文献标志码]A

[文章编号]1671-9387(2016)03-0118-07