高级检索

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

一种融合聚类和分类算法的树木图像多目标优化分割方法

王晓松 杨刚

王晓松, 杨刚. 一种融合聚类和分类算法的树木图像多目标优化分割方法[J]. 北京林业大学学报, 2018, 40(12): 124-131. doi: 10.13332/j.1000-1522.20180160
引用本文: 王晓松, 杨刚. 一种融合聚类和分类算法的树木图像多目标优化分割方法[J]. 北京林业大学学报, 2018, 40(12): 124-131. doi: 10.13332/j.1000-1522.20180160
Wang Xiaosong, Yang Gang. A multi-objective optimization segmentation method for tree image based on fusion clustering and classification algorithm[J]. Journal of Beijing Forestry University, 2018, 40(12): 124-131. doi: 10.13332/j.1000-1522.20180160
Citation: Wang Xiaosong, Yang Gang. A multi-objective optimization segmentation method for tree image based on fusion clustering and classification algorithm[J]. Journal of Beijing Forestry University, 2018, 40(12): 124-131. doi: 10.13332/j.1000-1522.20180160

一种融合聚类和分类算法的树木图像多目标优化分割方法

doi: 10.13332/j.1000-1522.20180160
基金项目: 

国家自然科学基金项目 61602277

国家自然科学基金项目 61773244

山东省自然科学基金项目 ZR2016GB06

国家自然科学基金项目 61772319

详细信息
    作者简介:

    王晓松,博士,副教授。主要研究方向:图像处理、数字林业。Email:morningpine@163.com  地址:264005山东省烟台市滨海中路191号山东工商学院管理科学与工程学院

    通讯作者:

    杨刚,副教授。主要研究方向:计算机图形学、数字林业。Email:yanggang@bjfu.edu.cn  地址:100083北京市海淀区清华东路35号北京林业大学信息学院

  • 中图分类号: S757.2;TP391

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多目标优化结果。结论融合聚类和分类算法构建聚类性能评价指标函数和分类评价性能指标函数,并采用非支配排序遗传算法对多目标函数进行优化,能更好地保留树木图像的颜色和纹理特征,分割准确率显著提高。
  • 图  1  两个目标函数的帕累托前端最优解集

    Figure  1.  Pareto front of a set of solutions in a two objective space

    图  2  NSGA-II优化基本流程图

    Figure  2.  Flowchart of NSGA-II optimization

    图  3  染色体编码

    Figure  3.  Chromosome coding

    图  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
  • [1] 任才, 贾昕, 吴雅娟, 马景永, 田赟, 查天山.  油蒿光系统II光化学参数在生长季早期对降雪事件的响应 . 北京林业大学学报, 2019, 41(12): 119-127. doi: 10.12171/j.1000-1522.20190058
    [2] 任文子, 王新杰, AlexAppiah Mensah.  瑞典南部Ostad区私有林多目标森林经营中期规划 . 北京林业大学学报, 2019, 41(2): 97-105. doi: 10.13332/j.1000-1522.20180220
    [3] 张帆, 付慧, 杨刚.  低空林地航拍图像拼接的改进缝合线算法 . 北京林业大学学报, 2018, 40(5): 90-102. doi: 10.13332/j.1000-1522.20170372
    [4] 孙林豪, 方陆明, 唐丽华, 刘江俊.  便携式树木胸径测量系统的研制 . 北京林业大学学报, 2018, 40(9): 82-89. doi: 10.13332/j.1000-1522.20180102
    [5] 贾道祥, 刘鹏举, 张英凯, 刘长春, 孙永明.  基于地形匹配的图像烟火定位方法研究 . 北京林业大学学报, 2018, 40(6): 19-29. doi: 10.13332/j.1000-1522.20170439
    [6] 冯静静, 张晓丽, 刘会玲.  基于灰度梯度图像分割的单木树冠提取研究 . 北京林业大学学报, 2017, 39(3): 16-23. doi: 10.13332/j.1000-1522.20160373
    [7] 张一茗, 付慧.  基于间隙度的无人机林地航拍图像序列拼接方法 . 北京林业大学学报, 2017, 39(6): 107-115. doi: 10.13332/j.1000-1522.20170020
    [8] 白雪冰, 许景涛, 郭景秋, 陈凯.  基于改进C-V模型的木材表面缺陷图像分割 . 北京林业大学学报, 2015, 37(12): 108-115. doi: 10.13332/j.1000-1522.20150198
    [9] 王丽君, 淮永建, 彭月橙.  基于叶片图像多特征融合的观叶植物种类识别 . 北京林业大学学报, 2015, 37(1): 55-69. doi: 10.13332/j.cnki.jbfu.2015.01.006
    [10] 王斌, 杨秀珍, 戴思兰.  4种园林树木抗旱性的综合分析 . 北京林业大学学报, 2013, 35(1): 95-102.
    [11] 陶嗣巍, 赵东.  树木几何结构快速建模的研究 . 北京林业大学学报, 2013, 35(2): 97-101.
    [12] 程希平, 水崎大二郎, 王四海, 吴利华, 马月伟, 巩合德.  基于空间自相关构建树木生长模型 . 北京林业大学学报, 2012, 34(5): 113-119.
    [13] 张娟, 黄心渊.  基于图像分析的梅花品种识别研究 . 北京林业大学学报, 2012, 34(1): 96-104.
    [14] 张娟, 韩殿元, 黄心渊.  自然背景下的梅花图像分割算法研究 . 北京林业大学学报, 2012, 34(3): 64-70.
    [15] 王晓松, 黄心渊.  一种改进的基于MRF的树木图像提取方法 . 北京林业大学学报, 2012, 34(5): 128-133.
    [16] 李春干, 邵国凡.  Landsat7 ETM+图像用作SPOT5图像森林分类的辅助数据研究 . 北京林业大学学报, 2010, 32(4): 1-5.
    [17] 王晓松, 黄心渊, 付慧.  复杂背景下的树木图像提取 . 北京林业大学学报, 2010, 32(3): 197-203.
    [18] 赵博光, 张厚江, 胡建忠, 张建军, 莫秋云, 张丽丽, 石娟, 武三安, 贾黎明, 陈玮, 郭惠红, 刁一伟, 韩烈保, 杜晓, 李成茂, 刘晓丽, 李镇宇, 王安志, 王昌俊, 清水晃, 梁波, 邢长山, 申世杰, 李文彬, 徐文铎, 姜笑梅, 宋菲, 骆有庆, 张峻萍, 马履一, 曾凡勇, 李景锐, 殷亚方, 苏德荣, 壁谷直记, 金昌杰, 石碧, 崔英颖, 沉昕, 王小平, 李海林, 赵林果, 蒋艳灵, 延廣竜彦, 胡青, 苗毅, 韩瑞东, 韦艳葵, 徐梅, 陈卫平2, 关德新, 严晓素, 王瀛坤, 徐君, 赵永利, 高述民, 裴铁璠, 周军, 李凤兰, 蒋平, 蒋平.  人工林尾巨案树木表面轴向生长应变 . 北京林业大学学报, 2005, 27(6): 95-98.
    [19] 宗世祥, 韩轶, 吴延熊, 杨期和, LIYong-ning, 李春干, 李悦, 王登芝, 杨华, 李崇贵, 瞿超, 耿宏生, MENGXian-yu, 聂立水, 贾峰勇, 李吉跃, 叶万辉, 孟宪宇, 张云, HUANGXuan-rui, 景海涛, 李吉跃, 刘燕, 骆有庆, , 续九如, 高润宏, 廖富林, 胡磊, , 胡涌, WANGJin-mao, 程俊, 许志春, 张连生, 孙丹峰, , , , 梁树军, 贾黎明, 刘云慧, , , 赵世华, .  单株立木图像信息的提取与解算 . 北京林业大学学报, 2005, 27(1): 51-54.
    [20] 武三安, 胡建忠, 杜晓, 莫秋云, 陈玮, 贾黎明, 刁一伟, 李成茂, 刘晓丽, 张丽丽, 韩烈保, 张建军, 张厚江, 郭惠红, 石娟, 赵博光, 王昌俊, 申世杰, 梁波, 马履一, 李文彬, 姜笑梅, 徐文铎, 邢长山, 骆有庆, 李镇宇, 王安志, 清水晃, 宋菲, 张峻萍, 金昌杰, 苏德荣, 崔英颖, 壁谷直记, 王小平, 曾凡勇, 李海林, 李景锐, 赵林果, 石碧, 殷亚方, 沉昕, 延廣竜彦, 徐梅, 蒋艳灵, 韩瑞东, 苗毅, 陈卫平2, 韦艳葵, 胡青, 关德新, 王瀛坤, 裴铁璠, 赵永利, 严晓素, 高述民, 徐君, 李凤兰, 周军, 蒋平, 蒋平.  确定监测区域建立森林郁闭度估测方程最优样地的研究 . 北京林业大学学报, 2005, 27(6): 24-28.
  • 加载中
图(4) / 表 (2)
计量
  • 文章访问数:  331
  • HTML全文浏览量:  110
  • PDF下载量:  7
  • 被引次数: 0
出版历程
  • 收稿日期:  2018-05-15
  • 修回日期:  2018-09-17
  • 刊出日期:  2018-12-01

一种融合聚类和分类算法的树木图像多目标优化分割方法

doi: 10.13332/j.1000-1522.20180160
    基金项目:

    国家自然科学基金项目 61602277

    国家自然科学基金项目 61773244

    山东省自然科学基金项目 ZR2016GB06

    国家自然科学基金项目 61772319

    作者简介:

    王晓松,博士,副教授。主要研究方向:图像处理、数字林业。Email:morningpine@163.com  地址:264005山东省烟台市滨海中路191号山东工商学院管理科学与工程学院

    通讯作者: 杨刚,副教授。主要研究方向:计算机图形学、数字林业。Email:yanggang@bjfu.edu.cn  地址:100083北京市海淀区清华东路35号北京林业大学信息学院
  • 中图分类号: S757.2;TP391

摘要: 目的结合树木图像颜色和纹理特征,融合聚类和分类算法对树木图像进行多目标优化分割,从而提高自然背景下树木图像分割的准确性。方法首先,利用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多目标优化结果。结论融合聚类和分类算法构建聚类性能评价指标函数和分类评价性能指标函数,并采用非支配排序遗传算法对多目标函数进行优化,能更好地保留树木图像的颜色和纹理特征,分割准确率显著提高。

English Abstract

王晓松, 杨刚. 一种融合聚类和分类算法的树木图像多目标优化分割方法[J]. 北京林业大学学报, 2018, 40(12): 124-131. doi: 10.13332/j.1000-1522.20180160
引用本文: 王晓松, 杨刚. 一种融合聚类和分类算法的树木图像多目标优化分割方法[J]. 北京林业大学学报, 2018, 40(12): 124-131. doi: 10.13332/j.1000-1522.20180160
Wang Xiaosong, Yang Gang. A multi-objective optimization segmentation method for tree image based on fusion clustering and classification algorithm[J]. Journal of Beijing Forestry University, 2018, 40(12): 124-131. doi: 10.13332/j.1000-1522.20180160
Citation: Wang Xiaosong, Yang Gang. A multi-objective optimization segmentation method for tree image based on fusion clustering and classification algorithm[J]. Journal of Beijing Forestry University, 2018, 40(12): 124-131. doi: 10.13332/j.1000-1522.20180160
  • 树木图像采集是“数字林业”领域中相关研究数据来源的一个主要途径。利用树木数字图像可以获得树种分类、树木生长态势、树木健康状况、树木形态特征等一系列信息。因此,近年来,树木图像提取研究引起了林业科研工作者的广泛关注。

    目前,学者们提出的树木图像提取算法可以归纳为以下几种:(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(XiVk)代表样本与聚类中心之间的欧式距离,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))|XPS}。

      两个目标函数的多目标优化问题如图 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=PtQt

      第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={x1x2,…,xM}是M个样本像素点,其中每个像素点xkRn(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值。假设两个个体分别为ij,则拥挤度比较算子可以定义如下:当irank < jranki$\prec $j,或者当irank=jrankid>jdi$\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类不同树种的树木图像作为样本进行实验分析,结果表明,多目标优化后的最优解分割正确率明显优于其他聚类分割方法的分割结果, 且很好地保留了树木的纹理特征,更适用于自然背景下拍摄的树木图像的分割。当背景中绿色植物与目标树木基本一致时,如何更为精确地分割目标树木,是下一步研究需要解决的问题。

参考文献 (24)

目录

    /

    返回文章
    返回