-
树木图像采集是“数字林业”领域中相关研究数据来源的一个主要途径。利用树木数字图像可以获得树种分类、树木生长态势、树木健康状况、树木形态特征等一系列信息。因此，近年来，树木图像提取研究引起了林业科研工作者的广泛关注。
目前，学者们提出的树木图像提取算法可以归纳为以下几种：(1)对颜色过绿特征进行转换，利用过绿因子构建颜色向量，然后采用分形维数、MRF-MAP、形态小波等算法实现分割[1-5]；(2)把树木图像从RGB颜色空间转换到HIS和Lab等颜色空间，获取颜色向量，再利用形态学方法和高斯马尔科夫模型等进行分割[6-7]；(3)利用数字抠图技术进行树木图像提取[8]。无论是基于过绿因子，还是颜色空间转换的图像分割方法，进行树木图像分割时，都仅考虑了图像中的颜色特征信息，而忽略了图像的空间信息，所以导致分割结果中树冠和树干的纹理信息难以保留。基于数字抠图技术提取树木图像的方法，结果虽优于分割方法，但是算法复杂，实时性、实用性较差，而且需要人监督完成抠图。
-
树木图像具有明显的颜色特征，树冠多以绿色为主，树干以棕色、白色居多。模糊聚类分割方法是目前常用的图像分割方法，基本思想是计算像素点间的欧氏距离或曼哈顿距离来测量像素点间的相似性，然后进行类别划分，注重像素集内部和像素集彼此间的关系。聚类方法可以较好的在颜色空间进行树木图像的分割。但是，当背景中包含其他绿色植物时，如灌木、杂草等，颜色特征聚类效果并不理想。
树木图像同时具有明显的纹理特征，树冠中叶片构成的纹理、树皮的纹理等。另一种常用的图像分割方法，就是分类算法，基本思想是根据样本像素集的特征信息，构造分类判决目标函数，从而实现对未知样本像素点进行标号分类，注重每个像素个体的划分。分类方法可以较好的在纹理空间进行树木图像的分割。但是，当光线较弱，纹理特征不明显的条件下，分类效果也不理想。
基于以上分析，本文提出了一种基于多目标优化融合聚类和分类算法的树木图像分割方法，采用两个目标函数，同时考虑树木图像的颜色特征和纹理特征，使聚类和分类方法的优势同时发挥，然后用多目标进化算法进行优化，获取最优解集。
-
一些学者尝试结合聚类和分类两种方法，例如，CCAS[9]、RBFNN[10]、VQ+LVQ[11]、ECCAS[12]和Fuzzy Relational Classifier(FRC)[13]等，但这些算法基本上都是对通过聚类算法得出的结果再进行分类学习，并没有使两种方法各自优势同时得到发挥。
Cai等[14-15]在2010年提出了一个MSCC(Multi-objective simultaneous learning framework for both clustering and classification learning)框架，同时进行聚类和分类学习，并采用多目标粒子群优化算法(MOPSO)来同时优化嵌入这些功能的聚类中心。
实现MSCC框架中的同时聚类和分类的关键，是如何让聚类和分类结果依赖于相同的参数。在聚类分析中，通常使用模糊C-均值聚类作为参考，μik表示训练样本Xi与聚类k的模糊隶属度，可以用如下公式[16]计算：
$$ {\mu _{ik}} = \frac{{{D^2}{{\left( {{X_i},{V_k}} \right)}^{ - 1}}}}{{\sum\limits_{k = 1}^K {{D^2}{{\left( {{X_i},{V_k}} \right)}^{ - 1}}} }} $$ (1) 式中：D2(Xi，Vk)代表样本与聚类中心之间的欧式距离，Vk为第k个聚类中心，K为聚类中心总数。
在确定了聚类中心后，聚类目标函数就可以建立了。
接下来，基于贝叶斯理论设计一个分类机制仅依赖于{Vk}，在分类学习中，后验概率p(ωl|Xi)被建立时，输出类标签f(Xi)可以表示为
$$ f\left( {{X_i}} \right) = \arg \mathop {\max }\limits_{1 \le l \le L} p\left( {{\omega _l}\left| {{X_i}} \right.} \right) $$ (2) 式中：L为类总数，ωl表示第l个类。
为了引入聚类信息到p(ωl|Xi)，利用已经生成的聚类{Vk}，通过全概率定理，重新构建p(ωl|Xi)为：
$$ \begin{array}{*{20}{c}} {p\left( {{\omega _l}\left| {{X_i}} \right.} \right) = \sum\limits_{k = 1}^K {p\left( {{\omega _l},{c_k}\left| {{X_i}} \right.} \right)} = }\\ {\sum\limits_{k = 1}^K {p\left( {{c_k}\left| {{X_i}} \right.} \right)p\left( {{\omega _l},{c_k}\left| {{X_i}} \right.} \right)} = }\\ {\sum\limits_{k = 1}^K {p\left( {{c_k}\left| {{X_i}} \right.} \right)p\left( {{\omega _l}\left| {{c_k}} \right.} \right)} } \end{array} $$ (3) 式中：ωl表示第l个类，ck表示第k个聚类，p(ck|Xi)表示相应样本的后验概率，p(ωl|ck)表示类成员的聚类后验概率。p(ωl|ck, Xi)与Xi没有关系，因此可以被简化为p(ωl|ck)。
根据p(ck|Xi)的直接含义，可以由公式(1)来进行计算。根据贝叶斯定理，p(ωl|ck)可以用如下公式计算：
$$ p\left( {{\omega _l}\left| {{c_k}} \right.} \right) = p\left( {{\omega _l},{c_k}} \right)/p\left( {{c_k}} \right) $$ (4) 式中：p(ck)是先验概率，可以通过计算第k个聚类中的样本比例来得到，例如$\frac{{{\mathop{\rm Num}\nolimits} \left( {x \in {c_k}} \right)}}{N}$; p(ωl, ck)是联合分布，同样地，也可以通过计算属于第k个聚类，且属于第l个分类的样本比例来得到，例如，$\frac{{{\mathop{\rm Num}\nolimits} \left( {x \in {\omega _l}{\rm{ and }}x \in {c_k}} \right)}}{N}$。
因此，p(ωl|ck)可以被重新定义为：
$$ p\left( {{\omega _l}\left| {{c_k}} \right.} \right) = \frac{{{\rm{Num}}\left( {x \in {\omega _l}\;{\rm{and}}\;x \in {c_k}} \right)}}{{{\rm{Num}}\left( {x \in {c_k}} \right)}} $$ (5) 对于每个聚类ck，当L为类的个数时，应该满足约束条件$\sum\limits_{l = 1}^L p \left( {{\omega _l}|{c_k}} \right) = 1$。公式(5)表明当p(ωl|ck)取大值(小值)，聚类ck中所含类l样本比例也同比变换为大值(小值)。现在所有的p(ωl|ck)可以用一个矩阵K×L表示为：
$$ \mathit{\boldsymbol{P}} = \left[ {\begin{array}{*{20}{c}} {p\left( {{\omega _1}\left| {{c_1}} \right.} \right)}& \cdots &{p\left( {{\omega _l}\left| {{c_1}} \right.} \right)}\\ \vdots &{}& \vdots \\ {p\left( {{\omega _1}\left| {{c_k}} \right.} \right)}& \cdots &{p\left( {{\omega _l}\left| {{c_k}} \right.} \right)} \end{array}} \right] $$ (6) 很显然，这个关系矩阵P可以揭示给定聚类和分类之间的统计关系。
对于具有分类标签的训练数据集，聚类结果描述为μik或者是只与聚类中心相关的p(ck|Xi)。另一方面，分类结果p(ωl|ck)同样依赖于聚类中心。因此，通过应用贝叶斯理论，使得聚类和分类机制全部由聚类中心决定。
-
多目标优化在图像领域得到广泛应用，其定义[17]如下：
定义1(Pareto占优)：对于给定的多目标优化问题minJ(X)=[J1(X), J2(X), …, JM(X)]，解X1支配解X2，或者解X2劣于解X1，即以下两个条件成立：(1)${\forall _i}$∈[1, 2, …, M]，Ji(X1)≤Ji(X2)；(2)${\exists _i}$∈ [1, 2, …, M]，Ji(X1)≤Ji(X2)，则可以记作${X^1} \prec {X^2}$。
定义2(Pareto最优解)：如果不存在解X1使得${X^1} \prec {X^0}$，则称解X0为Pareto最优解。
定义3(Pareto最优解集)：Pareto最优解的集合，可以记作${P_s} = \left\{ {{X^0}|\bar \exists {X^1} \prec {X^0}} \right\}$。
定义4(Pareto前沿)：对于一个给定的Pareto最优解集PS，Pareto前沿可以表示为PF={J(X)=(J1(X), J2(X), …, JM(X))|X∈PS}。
两个目标函数的多目标优化问题如图 1所示，空心圆点表示一个支配解，实心圆点表示一个Pareto最优解，也被称为非支配解。由定义1可知，解X0支配解X1和解X2；由定义2可知，实心圆点为Pareto最优解；由定义3可知，所有的实心圆点构成了Pareto最优解集；由定义4可知，Pareto前沿由全部实心圆点的目标函数值构成。
图 1 两个目标函数的帕累托前端最优解集
Figure 1. Pareto front of a set of solutions in a two objective space
基于MSCC框架对聚类和分类机制的描述，多目标聚类和分类可以表述如下：
$$ \begin{array}{*{20}{c}} {\min J\left( {\left\{ {{V_k}} \right\}} \right) = \left[ {{J_1}\left( {\left\{ {{V_k}} \right\}} \right),{J_2}\left( {\left\{ {{V_k}} \right\}} \right), \cdots ,} \right.}\\ {\left. {{J_m}\left( {\left\{ {{V_k}} \right\}} \right), \cdots ,{J_M}\left( {\left\{ {{V_k}} \right\}} \right)} \right]} \end{array} $$ (7) 式中：M表示目标函数的个数，Jm({Vk})代表与聚类相关的第m个目标函数。选择一个聚类目标函数和一个分类目标函数，两个目标函数来解决聚类和分类问题。
$$ \min J\left( {\left\{ {{V_k}} \right\}} \right) = \left[ {{J_1}\left( {\left\{ {{V_k}} \right\}} \right),{J_2}\left( {\left\{ {{V_k}} \right\}} \right)} \right] $$ (8) 式中：J1({Vk})是聚类性能评价目标函数，J2({Vk})是分类性能评价目标函数。无论选择哪些聚类和分类评价函数，J({Vk})的值都仅取决于一系列聚类中心。通过优化聚类中心J({Vk})，可以同时优化聚类和分类结果。
-
Cai等[14]采用多目标粒子群优化算法(MOPSO)对其研究所选择的目标函数进行优化，实验表明MOPSO作为MSCC框架的多目标优化算法不利于保持种群的多样性，只能得到少数非支配解。本文选择NSGA-II算法[18]进行多目标优化，与其他具有精英策略的多目标进化算法相比，该方法具有较低的计算复杂度、较少的共享参数，且利用拥挤度距离计算得到更好的最优解集分布，快速非支配排序使得收敛性更接近实际的Pareto最优层级。
-
输入一幅树木图像后，采用FCM算法进行初始分割，然后运用NSGA-II进行多目标优化，基本工作流程如下。
第1步：随机产生规模为N的父代种群Pt；
第2步：迭代计算一次FCM，计算模糊隶属度；
第3步：计算适应度函数(即两个目标函数)，进行非支配排序，并计算拥挤度距离；
第4步：遗传操作，锦标赛选择、交叉、变异产生子代种群Qt，规模同样为N；
第5步：计算模糊隶属度，计算适应度函数(即两个目标函数)；
第6步：合并父代种群和子代种群Rt=Pt∪Qt；
第7步：对种群Rt进行非支配排序，并对处于每个非支配排序ranki上的所有个体进行拥挤度距离id计算；
第8步：根据ranki值和id值，选择N个最优个体组成新的父代种群Pt+1；
第9步：判断是否满足优化问题结束条件，如果不满足，重复第四步到第九步操作；
第10步：若满足优化问题结束条件，获取非支配排序结果，标识聚类中心，选择最优解。
NSGA-II算法优化的基本流程可用图 2表示。
图 2 NSGA-II优化基本流程图
Figure 2. Flowchart of NSGA-II optimization
-
把n维空间的聚类中心用固定长度的串进行编码，从而把解空间的问题转化为染色体编码的问题。在MSCC框架中，两个目标函数的值取决于一系列聚类中心。因此，染色体由确定两个目标函数值的二维聚类中心的一串实数值表示。图 3显示了包含4个聚类中心的{V1, V2, V3, V4}的染色体的二维示例。例如，一个串可以表示为{(5.02, 3.66), (4.23, 2.68), (6.78, 3.24), (6.12, 2.06)}，串的长度代表了聚类中心的个数。
图 3 染色体编码
Figure 3. Chromosome coding
-
FCM算法的主要工作是成员隶属度的计算和聚类中心的更新。成员隶属度用来表示每个像素点隶属于每个聚类的程度，并且这个信息也用于更新聚类中心的值。设X={x1，x2，…，xM}是M个样本像素点，其中每个像素点xk是Rn(n维空间)的特征向量。C是聚类的个数。使用欧氏距离计算像素点xk到聚类中心vi的距离公式[16]如下：
$$ d_{ik}^2 = \sum\limits_{j = 1}^n {{{\left( {{x_{kj}} - {v_{ij}}} \right)}^2}} ,1 \le k \le M,1 \le i \le C $$ (9) 式中：dik2用来表示n维空间欧氏距离。
计算模糊隶属度公式如下：
$$ \begin{array}{*{20}{c}} {{\mu _{ik}} = \frac{1}{{\sum\limits_{j = 1}^C {{{\left( {\frac{{{d_{ik}}}}{{{d_{jk}}}}} \right)}^{2/\left( {m - 1} \right)}}} }},}\\ {1 \le k \le M,1 \le i \le C} \end{array} $$ (10) 式中：μik表示xk属于第i个聚类中心的隶属度值；模糊系数m>1，是控制模糊程度的参数。这意味着每个像素点对于每个聚类中心都具有相应的成员隶属度值。
根据公式(11)，聚类中心的值可以进行更新。最后，在获得新的聚类中心值后，根据公式(10)重新计算每个像素点的成员隶属度。
$$ {v_i} = \frac{{\sum\limits_{k = 1}^M {{{\left( {{\mu _{ik}}} \right)}^m}{x_k}} }}{{\sum\limits_{k = 1}^M {{{\left( {{\mu _{ik}}} \right)}^m}} }},1 \le i \le C $$ (11) -
基于聚类内紧凑性和聚类间分离性，可以设计多个不同的聚类目标函数。本文选择Fatma根据Wu-and-Li (WL)指数[19]和Tang (T)指数[20]提出的HF指数[21]：
$$ {N_{{\rm{HF}}}} = \sum\limits_{k = 1}^K {\sum\limits_{i = 1}^N {\mu _{ij}^m{{\left\| {{X_i} - {V_k}} \right\|}^2}} } + {\rm{ADP}} $$ (12) $$ {\rm{ADP}} = \frac{1}{{K\left( {K - 1} \right)}}\sum\limits_{k = 1}^K {\sum\limits_{k = 1,k \ne i}^K {{{\left\| {{V_i} - {V_k}} \right\|}^2}} } $$ (13) $$ {D_{{\rm{HF}}}} = \frac{N}{{2K}}\left( {\mathop {\min }\limits_{i \ne k} {{\left\| {{V_i} - {V_k}} \right\|}^2} + \mathop {{\rm{median}}}\limits_{i \ne k} {{\left\| {{V_i} - {V_k}} \right\|}^2}} \right) $$ (14) $$ {J_1}\left( {\left\{ {{V_k}} \right\}} \right) = {\rm{HF}} = \frac{{{N_{{\rm{HF}}}}}}{{{D_{{\rm{HF}}}}}} $$ (15) 式中：${\min\limits _{i \ne k}}{\left\| {{V_i} - {V_k}} \right\|^2}$表示各聚类中心欧氏距离的最小值，$\mathop {{\mathop{\rm median}\nolimits} }\limits_{i \ne k} {\left\| {{V_i} - {V_k}} \right\|^2}$表示各聚类中心欧氏距离的均值。最小化聚类准则J1({Vk})，评价聚类特征空间的类内紧凑性和类间分离性。HF指数避免了单调递减问题，所以可以更可靠、更高效的评估聚类结果。
-
基于分类机制，评测分类目标的最小误分类率公式如下[14]：
$$ {J_2}\left\{ {{V_k}} \right\} = \frac{{\sum\limits_{i = 1}^N {\delta \left( {f\left( {{X_i}} \right),{y_i}} \right)} }}{N} $$ (16) 式中：f(Xi)的含义如公式(2)所述，yi是样本Xi分类标识。对于树木图像，本研究中将其划分为3类，即背景区域、树冠、树干。因此，yi∈{1, 2, 3}。δ是损失函数，当f(Xi)=yi时，值为0，否则为1。最小化分类准则J2({Vk})，用来评价最小误分类率。
-
在聚类方法中，解决方案必须根据聚类中心的实际编码串，在连续搜索空间中进行优化。通过二进制比赛选择[22]，模拟二进制交叉(SBX)算子[22]和多项式变异算子[23]，实现对实数编码串的随机搜索。
NSGA-II执行过程中，采用二进制锦标赛选择新一代父代种群。两个随机选择的个体进行锦标赛，通过拥挤度比较算子($\prec $)选出获胜者。这个算子同时考虑非支配排序层级ranki值和拥挤度距离id值。假设两个个体分别为i和j，则拥挤度比较算子可以定义如下：当irank < jrank时i$\prec $j，或者当irank=jrank且id>jd时i$\prec $j。当两个个体处于不同层级，层级低的被选出；如果两个个体层级相同，拥挤度距离大的被选出。
-
在本文的实验中，基于MSCC框架理论，选择公式(15)和公式(16)作为两个目标函数，采用NSGA-II算法进行多目标优化，优化流程如图 2所示。实验中，选择了具有代表性的法国梧桐(Platanus orientalis)(样本1)、侧柏(Platycladus orientalis)(样本2)、松树(Pinus sp.)(样本3)和杏树(Armeniaca sp.)(样本4)等自然背景下拍摄的图像进行分割。多目标进化优化得到的多个解决方案的聚类中心可以进化和比较，因此，运行一次NSGA-II得到的非支配排序最优解集已经足够。然后，利用聚类有效性指数I的最大值从最优解集中选出一个最优解，其定义[24]如下：
$$ I\left( K \right) = {\left( {\frac{1}{K}\frac{{{E_1}}}{{{E_K}}} \times {D_K}} \right)^P} $$ (17) 式中：K表示聚类中心的个数，${E_K} = \sum\limits_{k = 1}^K {\sum\limits_{j = 1}^n {{\mu _{kj}}\left\| {{x_j} - {V_k}} \right\|} } $，同时${D_K} = \max\limits _{i, j = 1}^K\left\| {{V_i} - {V_j}} \right\|$。由公式(17)可知，指数I由$\frac{1}{K}$、$\frac{{{E_1}}}{{{E_K}}}$和DK这3个要素构成。第1个要素中，随着K值增加，指数I的值减小。第2个要素中，E1是一个给定数据集，E1对于EK的比率随着K值的增加而减小，因此，指数I随着EK的减小而增加。第3个要素DK用来计算各个聚类中心两两比较的最大距离，会随着K值的增加而增加。以上3个要素相互平衡、相互制约。参数P用来控制不同聚类之间的对比度，实验中选定P值为2。Pareto解集中某个解决方案的指数I的值越大意味着该方案越好，所以要寻找指数I取最大值时，对应的解决方案。
实验过程中，NSGA-II相关参数取值如表 1所示。
表 1 NSGA-II实验参数设置
Table 1. Parameter settings for the experiment
参数名称Parameter 参数值Setting 种群大小Population size 20 遗传代数Number of generations 40 选择算子Selection operator 二进制锦标赛Binary tournament 交叉算子Crossover operator SBX算子SBX operator 变异算子Mutation operator 多项式变异算子Polynomial mutation operator 交叉概率Probability of crossover 0.8 变异概率Probability of mutation 1/染色体长度1/length of chromosome 交叉索引值Crossover index value 2.0 变异索引值Mutation index value 5.0 使用聚类硬分割方法K-means、模糊聚类分割方法Fuzzy C-means、单目标优化和基于MSCC的多目标优化分割方法对上述4类样本图像进行分割，分割结果如图 4所示。
图 4 不同分割方法分割结果图
Figure 4. Comparison of segmentation results by different segmentation methods
对于样本图像，采用K-means和FCM的算法分割结果中远处绿色的山峰、近处绿色的草地都不能与目标树木分离，而采用融合聚类和分类的多目标优化分割方法分割后，我们可以看到绿色的远山基本被分离；样本1和样本3中的绿色草地也基本被分离；样本2和样本4中绿色植物与目标树木颜色基本一致(图 4)。由此可知，分割时有部分残留，但分割结果已经明显优于其他两种单一运用聚类分割方法的结果。
不同分割方法指数I值计算结果如表 2所示。从指数I的值可以验证，本文提出的分割方法优势显著。对4类不同样本图像分割的指数I值对比可知，以HF指数为单目标函数进行遗传优化的结果优于单一使用K-means和FCM算法，MOPSO多目标优化方法分割结果优于单目标优化结果，但基于NSGA-II优化的多目标函数分割结果又优于MOPSO多目标优化结果。
表 2 不同分割方法指数I值比较
Table 2. Comparison of I index value by different segmentation methods
样本Sample K-means (K=3) FCM (m=2, K=3) HF指数单目标GA优化HF index single objective optimization MSCC多目标粒子群优化Two objective MOPSO optimization MSCC多目标NSGA-II优化Two objective NSGA-II optimization 法国梧桐Platanus orientalis 67.56 74.87 85.32 91.36 96.28 侧柏Platycladus orientalis 50.56 67.45 74.65 85.43 90.32 松树Pinus sp. 40.56 41.45 50.32 72.39 83.87 杏树Armeniaca sp. 59.67 65.34 69.56 78.82 87.98 -
本文通过分析树木图像的特征，基于MSCC框架融合聚类和分类算法，构建聚类性能评价指标函数和分类评价性能指标函数，并采用非支配排序遗传算法对多目标函数进行优化。选择4类不同树种的树木图像作为样本进行实验分析，结果表明，多目标优化后的最优解分割正确率明显优于其他聚类分割方法的分割结果, 且很好地保留了树木的纹理特征，更适用于自然背景下拍摄的树木图像的分割。当背景中绿色植物与目标树木基本一致时，如何更为精确地分割目标树木，是下一步研究需要解决的问题。
A multi-objective optimization segmentation method for tree image based on fusion clustering and classification algorithm
-
摘要:
目的结合树木图像颜色和纹理特征，融合聚类和分类算法对树木图像进行多目标优化分割，从而提高自然背景下树木图像分割的准确性。 方法首先，利用MSCC框架理论，解决聚类和分类目标函数同时依赖于聚类中心的问题。然后，分别选定聚类性能评价指标函数和分类性能评价指标函数。最后，采用多目标进化优化方法——NSGA-II算法进行优化，得到Pareto前端最优解集，并通过计算聚类有效性指数I的最大值，寻找最优解决方案。选择具有代表性的法国梧桐、侧柏、松树和杏树等自然背景下拍摄的4幅图像作为样本。分别采用K-means、Fuzzy C-means、对聚类目标函数进行单目标优化，采用MOPSO方法进行多目标优化，以及NSGA-II方法进行多目标优化等5种方法对样本图像进行分割比较。 结果在聚类中心数量相同、种群大小相同、遗传代数相同的条件下，指数I的值表明本文提出的分割方法优势显著。对于4类不同样本图像分割的指数I值进行对比可知，以HF指数为单目标函数进行遗传优化的结果优于单一使用K-means和FCM算法；MOPSO多目标优化方法分割结果优于单目标优化结果；基于NSGA-II优化的多目标函数分割结果又优于MOPSO多目标优化结果。 结论融合聚类和分类算法构建聚类性能评价指标函数和分类评价性能指标函数，并采用非支配排序遗传算法对多目标函数进行优化，能更好地保留树木图像的颜色和纹理特征，分割准确率显著提高。 Abstract:ObjectiveIn order to improve the accuracy of tree image segmentation under natural background, this paper studies how to combine the color and texture features of tree image, and combine clustering and classification algorithm to optimize multi-objective segmentation of tree image. MethodBased on the tree image feature analysis, this paper proposes a multi-objective tree image segmentation method based on clustering and classification algorithm. Firstly, using the MSCC framework theory, the clustering and classification objective function depends on clustering center simultaneously. Then, the cluster performance evaluation index function and the classification performance evaluation index function were selected. Finally, the multi-objective evolutionary optimization method, NSGA-II algorithm was used to optimize, and the Pareto front-end optimal solution set was obtained. The I index was used to select the optimal solution from the optimal solution set. In this paper, we selected four images taken under the natural background, such as Oriental plane, Platycladus orientalis, pine and apricot, as samples. K-means, Fuzzy C-means, single-objective optimization of clustering objective function, multi-objective optimization using MOPSO method and multi-objective optimization using NSGA-II method were used to segment the sample images. ResultWhen the number of cluster centers, the size of population and the number of genetic iterations were the same, the value of index I can verify that the proposed segmentation method had significant advantages. Comparing the index I values of four different sample image segmentation, we can see that the result of genetic optimization using HF index as single objective function was better than that using K-means and FCM algorithm alone. The result of MOPSO multi-objective optimization method was better than that of single objective optimization method, but the result of multi-objective function segmentation based on NSGA-II optimization was better than that of MOPSO objective optimization results. ConclusionThe experimental results show that the segmentation accuracy of the method proposed in this paper is obviously better than that of single-objective optimization segmentation and K-means, Fuzzy c-means and other segmentation methods, the color and texture features of the tree image are better preserved. So the accuracy of segmentation is significantly improved. -
Key words:
- multiple-objective optimization /
- tree image /
- NSGA-II
-
图 1 两个目标函数的帕累托前端最优解集
Figure 1. Pareto front of a set of solutions in a two objective space
图 4 不同分割方法分割结果图
Figure 4. Comparison of segmentation results by different segmentation methods
表 1 NSGA-II实验参数设置
Table 1. Parameter settings for the experiment
参数名称Parameter 参数值Setting 种群大小Population size 20 遗传代数Number of generations 40 选择算子Selection operator 二进制锦标赛Binary tournament 交叉算子Crossover operator SBX算子SBX operator 变异算子Mutation operator 多项式变异算子Polynomial mutation operator 交叉概率Probability of crossover 0.8 变异概率Probability of mutation 1/染色体长度1/length of chromosome 交叉索引值Crossover index value 2.0 变异索引值Mutation index value 5.0 
下载: 导出CSV
表 2 不同分割方法指数I值比较
Table 2. Comparison of I index value by different segmentation methods
样本Sample K-means (K=3) FCM (m=2, K=3) HF指数单目标GA优化HF index single objective optimization MSCC多目标粒子群优化Two objective MOPSO optimization MSCC多目标NSGA-II优化Two objective NSGA-II optimization 法国梧桐Platanus orientalis 67.56 74.87 85.32 91.36 96.28 侧柏Platycladus orientalis 50.56 67.45 74.65 85.43 90.32 松树Pinus sp. 40.56 41.45 50.32 72.39 83.87 杏树Armeniaca sp. 59.67 65.34 69.56 78.82 87.98
下载: 导出CSV
-
[1] 葛玉峰, 周宏平, 郑加强, 等.基于相对色彩因子的树木图像分割算法[J].南京林业大学学报(自然科学版), 2004, 28(4):19-22. doi: 10.3969/j.issn.1000-2006.2004.04.004 Ge Y F, Zhou H P, Zheng J Q, et al. Tree image segmentation algorithm based on relative color factor[J].Journal of Nanjing Forestry University(Natural Science Edition), 2004, 28(4):19-22. doi: 10.3969/j.issn.1000-2006.2004.04.004 [2] 赵茂程, 郑加强, 林小静, 等.基于分形理论的树木图像分割方法[J].农业机械学报, 2004, 35(2):72-75. doi: 10.3969/j.issn.1000-1298.2004.02.021 Zhao M C, Zheng J Q, Lin X J, et al. Tree image segmentation based on fractal theory[J].Transactions of the Chinese Society of Agricultural Machinery, 2004, 35(2):72-75. doi: 10.3969/j.issn.1000-1298.2004.02.021 [3] 蔡世捷.基于Matlab的树木图像分割方法研究[D].南京: 南京林业大学, 2005. http://cdmd.cnki.com.cn/Article/CDMD-10298-2005103040.htm Cai S J. Research on tree image segmentation based on matlab[D]. Nanjing: Nanjing Forestry University, 2005. http://cdmd.cnki.com.cn/Article/CDMD-10298-2005103040.htm [4] 李云峰, 曹渝昆, 朱庆生, 等.基于小波域隐马模型的树木类图像分割算法[J].计算机应用研究, 2007, 24(8): 233-235. doi: 10.3969/j.issn.1001-3695.2007.08.076 Li Y F, Cao Y K, Zhu Q S, et al. Tree image segmentation algorithm based on wavelet-domain hidden-maze model[J]. Research of Computer Applications, 2007, 24(8):233-235. doi: 10.3969/j.issn.1001-3695.2007.08.076 [5] 张娜.树木图像分割方法的研究[D].哈尔滨: 东北林业大学, 2013. http://cdmd.cnki.com.cn/Article/CDMD-10225-1013371465.htm Zhang N.Research on tree image segmentation method[D]. Harbin: Northeast Forestry University, 2013. http://cdmd.cnki.com.cn/Article/CDMD-10225-1013371465.htm [6] 程磊.树木图象的分割方法初探[D].北京: 北京林业大学, 2004. http://cdmd.cnki.com.cn/article/cdmd-10022-2004116979.htm Cheng L. The method of tree image segmentation[D]. Beijing: Beijing Forestry University, 2004. http://cdmd.cnki.com.cn/article/cdmd-10022-2004116979.htm [7] 郭晶晶, 李庆武, 程海粟, 等.基于Lab颜色距离和GMM的树木图像分割算法[J].信息技术, 2016(2):1-4, 9. http://d.old.wanfangdata.com.cn/Periodical/xxjs201602001 Guo J J, Li Q W, Cheng H S, et al. Tree image segmentation algorithm based on lab color distance and GMM[J]. Information Technology, 2016(2):1-4, 9. http://d.old.wanfangdata.com.cn/Periodical/xxjs201602001 [8] 王晓松, 黄心渊.一种改进的基于MRF的树木图像提取方法[J].北京林业大学学报, 2012, 34(5):128-133. http://j.bjfu.edu.cn/article/id/9811 Wang X S, Huang X Y. An improved MRF based tree image extraction method[J].Journal of Beijing Forestry University, 2012, 34(5):128-133. http://j.bjfu.edu.cn/article/id/9811 [9] Ye N, Li X Y. A scalable, incremental learning algorithm for classification problems[J]. Computers & Industrial Engineering, 2002, 43(4): 677-692. http://cn.bing.com/academic/profile?id=42c70044a0b7abac36225de930766425&encoded=0&v=paper_preview&mkt=zh-cn [10] Musavi M T, Ahmed W, Chan K H, et al. On the training of radial basis function classifiers[J]. Neural Networks, 1992, 5(4): 595-603. doi: 10.1016/S0893-6080(05)80038-3 [11] Kim S W, Oommen B J. Enhancing prototype reduction schemes with LVQ3-type algorithms[J]. Pattern Recognition, 2003, 36(5): 1083-1093. doi: 10.1016/S0031-3203(02)00115-2 [12] Li X, Ye N. A supervised clustering and classification algorithm for mining data with mixed variables[J]. IEEE Transactions on Systems, Man, and Cybernetics, Part A: Systems and Humans, 2006, 36(2): 396-406. doi: 10.1109/TSMCA.2005.853501 [13] Setnes M, Babuska R. Fuzzy relational classifier trained by fuzzy clustering[J]. IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetic, 1999, 29(5): 619-625. doi: 10.1109/3477.790444 [14] Cai W L, Chen S C, Zhang D Q. A simultaneous learning framework for clustering and classification[J]. Pattern Recognition, 2009, 42(7): 1248-1259. doi: 10.1016/j.patcog.2008.11.029 [15] Cai W L, Chen S C, Zhang D Q. A multiobjective simultaneous learning framework for clustering and classification[J]. IEEE Transactions on Neural Networks, 2010, 21(2): 185-200. doi: 10.1109/TNN.2009.2034741 [16] Bezdek J C, Ehrlich R, Full W. FCM: the fuzzy c-means clustering algorithm[J]. Computers & Geosciences, 1984, 10(2/3): 191-203. http://d.old.wanfangdata.com.cn/Periodical/gpxygpfx201012036 [17] Coello C A C, Pulido G T, Lechuga M S. Handling multiple objectives with particle swarm optimization[J]. IEEE Transactions on Evolutionary Computation, 2004, 8(3): 256-279. doi: 10.1109/TEVC.2004.826067 [18] Deb K, Pratap A, Agarwal S, et al. A fast and elitist multiobjective genetic algorithm: NSGA-II[J]. IEEE Transactions on Evolutionary Computation, 2002, 6(2): 182-197. doi: 10.1109/4235.996017 [19] Wu C H, Ouyang C S, Chen L W, et al. A new fuzzy clustering validity index with a median factor for centroid-based clustering[J]. IEEE Transactions on Fuzzy Systems, 2015, 23(3): 701-718. doi: 10.1109/TFUZZ.2014.2322495 [20] Tang Y G, Sun F C, Sun Z Q. Improved validation index for fuzzy clustering[C]//Proceedings of the 2005, American Control Conference, 2005. Portland: IEEE, 2005, 2: 1120-1125. [21] Haouas F, Dhiaf Z B, Hammouda A, et al. A new efficient fuzzy cluster validity index: application to images clustering[C]//2017 IEEE International Conference on Fuzzy Systems (FUZZ-IEEE). Naples: IEEE, 2017. [22] Deb K, Agrawal R B. Simulated binary crossover for continuous search space[J]. Complex Systems, 1994, 9(3): 115-148. http://cn.bing.com/academic/profile?id=fc75f2c786e997992685ce3da77fbd15&encoded=0&v=paper_preview&mkt=zh-cn [23] Deb K, Goyal M. A combined genetic adaptive search (GeneAS) for engineering design[J]. Computer Science Informatics, 1996, 26(4): 30-45. http://cn.bing.com/academic/profile?id=ca0c97135300a100909d6ad8af227e7b&encoded=0&v=paper_preview&mkt=zh-cn [24] Maulik U, Bandyopadhyay S. Performance evaluation of some clustering algorithms and validity indices[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2002, 24(12): 1650-1654. doi: 10.1109/TPAMI.2002.1114856 -
点击查看大图
图(4) / 表 (2)
计量
- 文章访问数: 470
- HTML全文浏览量: 182
- PDF下载量: 9
- 被引次数: 0
