Multiple trees contour extraction method based on Graph Cut algorithm

YANG Tingting,GUAN Fangli,XU Aijun

JOURNAL OF NANJING FORESTRY UNIVERSITY ›› 2018, Vol. 42 ›› Issue (06) : 91-98.

PDF(3656140 KB)
南京林业大学学报（自然科学版）
PDF(3656140 KB)
JOURNAL OF NANJING FORESTRY UNIVERSITY ›› 2018, Vol. 42 ›› Issue (06) : 91-98. DOI: 10.3969/j.issn.1000-2006.201804012

Multiple trees contour extraction method based on Graph Cut algorithm

  • YANG Tingting1,GUAN Fangli2,XU Aijun1*
Author information +
History +

Abstract

【Objective】 Because of the complexity of the natural environment, current tree contour extraction results are not satisfactory. This paper presents a method to extract a contour of multiple trees based on a Graph Cut algorithm to realize the boundary segmentation of multi-target trees in a single photo. 【Method】 First, this method enhances image details of each channel under RGB color space captured in the experiment by color histogram equalization. The graph of the s-t network is constructed using a Graph Cut algorithm to look for min-cut, and the image segmentation problem is transformed into the minimization of the energy function by marking the foreground and background pixels to achieve a single photo of many trees with preliminary image segmentation. Then, adaptive thresholding of gray-scale transformation is applied to the multiple-segmentation images to realize binarization of the images and morphological corrosion expansion, and the opening and closing operation processing of the binary images is used to achieve the filling, denoising, and smoothing of trees. On the basis of this morphological process, combined with the improved Canny operator edge detection technology, bilateral filtering is used instead of Gaussian filtering to enhance the boundary information to obtain a preliminary tree contour. Finally, according to the geometric position invariance of the photo’s trees, we use the geometric reconstruction method to express the features of target trees and judge their topological relationships. If there are topological relationship errors, we iterate the Graph Cut algorithm and geometry reassembly method again to obtain a better target tree extraction result. 【Result】 In order to validate the effectiveness of this method experimentally, we collected tree images in a natural environment. The results showed that this method can effectively separate the contour of every tree under different lighting conditions. The average error rate(Af)was 5.62%, the false positive rate(RFP)was 4.49%, and the false negative rate(RFN)was 4.33%, which was better than those obtained by the traditional OTSU segmentation algorithm(41.40%, 26.73% and 10.99%, respectively), the K-means clustering algorithm(49.97%, 35.02% and 11.92%), and the C-V Plane Models(28.43%, 20.53% and 13.38% ). 【Conclusion】 In a complex natural environment, a Graph Cut algorithm based on human interaction can effectively separate vertical boundaries. The results provide a reference for the visualization and reconstruction of trees and feature extraction.

Cite this article

EndNote

Ris (Procite)

Bibtex

Download Citations
YANG Tingting,GUAN Fangli,XU Aijun. Multiple trees contour extraction method based on Graph Cut algorithm[J]. JOURNAL OF NANJING FORESTRY UNIVERSITY. 2018, 42(06): 91-98 https://doi.org/10.3969/j.issn.1000-2006.201804012

References


[1] 周克瑜,汪云珍,李记,等. 基于Android平台的测树系统研究与实现[J]. 南京林业大学学报(自然科学版),2016,40(4): 95-100. DOI: 10.3969/j.issn.1000-2006.2016.04.015.
ZHOU K Y,WANG Y Z,LI J,et al. A study of tree measurement systems based on Android platform[J]. Journal of Nanjing Forestry University(Natural Sciences Edition),2016,40(4): 95-100.
[2] 王建利,李婷,王典,等. 基于光学三角形法与图像处理的立木胸径测量方法[J]. 农业机械学报,2013,44(7): 241-245.DOI: 10.6041/j.issn.1000-1298.2013.07.042.
WANG J L,LI T, WANG D,et al. Measuring algorithm for tree’s diameter at breast height based on optical triangular method and image processing[J]. Transactions of the Chinese Society for Agricultural Machinery,2013,44(7): 241-245.
[3] 沈亚峰,王歆晖,巩宇涵,等. 基于智能手机图像分析的树木胸径测量研究[J]. 江苏林业科技,2017,44(1): 28-33.DOI: 10.3969/j.issn.1001-7380.2017.01.006
SHEN Y F,WANG X H,GONG Y H,et al. Study on measurement of tree diameter size based on smartphone imageanalysis[J]. Journal of Jiangsu Forestry Science & Technology,2017,44(1): 28-33.
[4] 赵茂程,郑加强,林小静,等. 基于分形理论的树木图像分割方法[J]. 农业机械学报,2004,35(2): 72-75.
ZHAO M C,ZHENG J Q,LIN X J,et al. Tree image segmentation method based on the fractional dimension[J]. Transactions of the Chinese Society for Agricultural Machinery,2004,35(2): 72-75.
[5] 张军国,冯文钊,胡春鹤,等. 无人机航拍林业虫害图像分割复合梯度分水岭算法[J]. 农业工程学报,2017,33(14): 93-99.DOI: 10.11975/j.issn.1002-6819.2017.14.013.
ZHANG J G,FENG W Z,HU C H,et al. Image segmentation method for forestry unmanned aerialvehicle pest monitoring based on composite gradien twatershed algorithm[J]. Transactions of the Chinese Society of Agricultural Enginee-ring,2017,33(14):93-99.
[6] 王晓松,黄心渊,付慧. 复杂背景下的树木图像提取[J]. 北京林业大学学报,2010,32(3):197-203.DOI: 10.13332/j.1000-1522.2010.03.019.
WANG X S, HUANG X Y, FU H.Study surveys on tree image extraction in a complex background[J]. Journal of Beijing Forestry University,2010,32(3): 197-203.
[7] 刁智华,王欢,宋寅卯,等. 复杂背景下棉花病叶害螨图像分割方法[J]. 农业工程学报,2013,29(5): 147-152.DOI: 1002-6819(2013)-05-0147-06.
DIAO Z H,WANG H,SONG Y M, et al. Segmentation method for cotton mite disease image under complex background[J]. Transactions of the Chinese Society of Agricultural Engineering,2013,29(5): 147-152.
[8] 李冠林,马占鸿,黄冲,等. 基于K-means硬聚类算法的葡萄病害彩色图像分割方法[J]. 农业工程学报,2010,26(2): 32-37.DOI: 10.11975/j.issn.1002-6819.2010.02.005.
LI G L,MA Z H,HUANG C, et al. Segmentation of color images of grape diseases using K-means clustering algorithm[J]. Transactions of the Chinese Society of Agricultural Engineering,2010,26(2):32-37.
[9] 杨信廷,孙文娟,李明,等. 基于K均值聚类和开闭交替滤波的黄瓜叶片水滴荧光图像分割[J]. 农业工程学报,2016,32(17): 136-143.DOI: 10.11975/j.issn.1002-6819.2016.17.019.
YANG X T,SUN W J,LI M,et al. Water droplets fluorescence image segmentation of cucumber leaves based on K-means clustering with opening and closing alternately filtering[J]. Transactions of the Chinese Society of Agricultural Enginee-ring,2016,32(17): 136-143.
[10] 贺付亮,郭永彩,高潮,等. 基于视觉显著性和脉冲耦合神经网络的成熟桑葚图像分割[J]. 农业工程学报,2017,33(6): 148-155. DOI: 10.11975/j.issn.1002-6819.2017.06.019.
HE F L,GUO Y C,GAO C, et al. Image segmentation of ripe mulberries based on visual saliency and pulse coupled neural network[J]. Transactions of the Chinese Society of Agricultural Engineering,2017,33(6): 148-155.
[11] 徐黎明,吕继东. 基于同态滤波和K均值聚类算法的杨梅图像分割[J]. 农业工程学报,2015,31(14): 202-208.DOI: 10.11975/j.issn.1002-6819.2015.14.028.
XU L M,Lü J D. Bayberry image segmentation based on homomorphic filtering and K-means clustering algorithm[J]. Transactions of the Chinese Society of Agricultural Engineering,2015,31(14): 202-208.
[12] BARGOTI S, UNDERWOOD J P. Image segmentation for fruit detection and yield estimation in apple orchards[J]. Journal of Field Robotics, 2016, 34(6):14-20.
[13] WANG C, TANG Y, ZOU X, et al. A robust fruit image segmentation algorithm against varying illumination for vision system of fruit harvesting robot[J]. Optik-International Journal for Light and Electron Optics, 2017(131):626-631.DOI: 10.1016 /j.ijleo.2016.11.177.
[14] 宋怀波,张传栋,潘景朋,等. 基于凸壳的重叠苹果目标分割与重建算法[J]. 农业工程学报,2013,29(3): 163-168.DOI: 10.11975/j.issn.1002-6819.2013.03.022.
SONG H B,ZHANG C D,PAN J P,et al. Segmentation and reconstruction of overl appedapple images based on convexhull[J]. Transactions of the Chinese Society of Agricultural Engineering,2013,29(3): 163-168.
[15] 王新忠,韩旭,毛罕平. 基于吊蔓绳的温室番茄主茎秆视觉识别(英文)[J]. 农业工程学报,2012,28(21): 135-141,294. DOI: 10.3969/j.issn.1002-6819.2012.21.019.
WANG X Z,HAN X,MAO H P. Vision-based detection of tomato main stem in greenhouse with red rope[J]. Transactions of the Chinese Society of Agricultural Engineering,2012,28(21): 135-141,294.
[16] 程玉柱,陈勇,张浩. 基于MMC与CV模型的苗期玉米图像分割算法[J]. 农业机械学报,2013,44(11): 266-270. DOI: 10.6041/ j. issn.1000-1298. 2013.11.045.
CHENG Y Z,CHEN Y,ZHANG H. Color image segmentation algorithm of corn based on MMC and CV model[J]. Transactions of the Chinese Society for Agricultural Machinery,2013,44(11): 266-270.
[17] 冯静静,张晓丽,刘会玲. 基于灰度梯度图像分割的单木树冠提取研究[J]. 北京林业大学学报,2017,39(3): 16-23. DOI:10.13332/j.1000-1522.20160373.
FENG J J,ZHANG X L,LIU H L. Single tree crown extraction based on gray gradient image segmentation[J]. Journal of Beijing Forestry University,2017,39(3): 16-23.
[18] BOLLANDSAS O M,NAESSET E,SOLBERG S. Single tree segmentation using airborne laser scanner data in a structurally heterogeneous spruce forest[J]. Photogrammetric Engineering & Remote Sensing,2006,72(12):1369-1378.
[19] KWATRA V, ESSAI, TURK G, et al. Graphcut Textures: image and video synthesis using graph[J]. Acm Transactions on Graphics, 2003, 22(3): 277-286.
[20] KUO J W, MAMOU J, WANG Y, et al. Segmentation of 3-D high-frequency ultrasound images of Human lymph nodes using Graph Cut with energy functional adapted to local intensity distribution[J]. IEEE Trans Ultrason Ferroelectr Freq Control,2017,64(10): 1514-1525. DOI:10.1109/TUFFC.2017.2737948.
[21] CHEN X,UDUPA K,BAGCI U,et al. Medical image segmentation by combining graph cuts and oriented active appearance models[J]. IEEE Trans Image Process,2012,21(4): 2035-2046. DOI:10.1109/TIP.2012.2186306.
[22] ZHOU H,ZHENG J,WEI L. Texture aware image segmentation using graph cuts and active contours[J]. Pattern Recognition,2013,46(6): 1719-1733. DOI:10.1016/j.patcog.2012.12.005.
[23]CIESIELSKI K C,UDUPA J K,FALC?O A X,et al. Fuzzy connec-tedness image segmentation in Graph Cut formulation: A linear-time algorithm and a comparative analysis[J]. Journal of Mathematical Imaging and Vision,2012,44(3): 375-398. DOI:10.1007/s10851-012-0333-3.
[24] YIN S,ZHAO X,WANG W,et al. Efficient multilevel image segmentation through fuzzy entropy maximization and graph cut optimization[J]. Pattern Recognition,2014,47(9): 2894-2907. DOI:10.1016/j.patcog.2014.03.009.
[25] CIESIELSKI KC,MIRANDA PA,FALC?O AX,et al. Joint graph cut and relative fuzzy connectedness image segmentation algorithm[J]. Med Image Anal,2013,17(8): 1046-1057. DOI:10.1016/j.media.2013.06.006.
[26] 苏金玲,王朝晖. 基于Graph Cut和超像素的自然场景显著对象分割方法[J]. 苏州大学学报(自然科学版),2012,28(2): 27-33.
SU J L, WANG Z H. An image segmentation method based on graph cut and super pixed in nature scene[J]. Journal of Suzhou University(Natural Science Edition), 2012,28(2): 27-33.
[27] 韩守东,赵勇,陶文兵,等. 基于高斯超像素的快速Graph Cuts图像分割方法[J]. 自动化学报,2011,37(1): 11-20.DOI: 10.3724/SP.J.1004.2011.00011.
HAN S D,ZHAO Y,TAO W B, et al. Gaussian super-pixel based fast image segmentation using graph cuts[J]. Acta Automatica Sinica,2011,37(1): 11-20.
[28] 韦轶群,杨杰. 基于自适应Graph Cuts的自动股骨头分割[J]. 上海交通大学学报,2009,43(3): 465-469.DOI:10.16183/j.cnki.jsjtu.2009.03.027.
WEI Y Q,YANG J. Automatic segmentation of femoral heads based on adaptive Graph Cuts[J]. Journal of Shanghai Jiaotong University,2009,43(3): 465-469.
[29] 刘毅,黄兵,孙怀江,等. 利用视觉显著性与图割的图像分割算法[J]. 计算机辅助设计与图形学学报,2013,25(3): 402-409.
LIU Y,HUANG B,SUN H J, et al. Image segmentation based on visual saliency and graph cuts[J]. Journal of Computer-Aided Design & Computer Graphics,2013,25(3): 402-409.
[30] 孙龙清,李玥,邹远炳,等. 基于改进Graph Cut算法的生猪图像分割方法[J]. 农业工程学报,2017,33(16): 196-202.DOI: 10.11975/j.issn.1002-6819.2017.16.026.
SUN L Q,LI Y,ZOU Y B,et al. Pig image segmentation method based on improved Graph Cut algorithm[J]. Transactions of the CSAE,2017,33(16): 196-202.
[31] 周良芬,何建农. 基于GrabCut改进的图像分割算法[J]. 计算机应用,2013,33(1): 49-52.
ZHOU L F,HE J N. Improved image segmentation algorithm based on Grab Cut[J]. Journal of Computer Applications,2013,33(1): 49-52.
[32] 董茜,颜凯,孙婷婷,等. 基于SLIC超像素的Grab Cut算法改进[J]. 华中科技大学学报(自然科学版),2016,44(S1): 43-47,66. DOI:10.13245/j.hust.16S109.
DONG Q,YAN K,SUN T T, et al. Improvement of grab cut algorithm based on SLIC superpixel algorithm[J]. J Huazhong Univ of Sci & Tech(Natural Science Edition), 2016,44(S1): 43-47,66.
[33] 陈鑫,何中市,李英豪. 一种新的基于SLICO改进的GrabCut彩色图像分割算法[J]. 计算机应用研究,2015,32(10): 3191-3195. DOI: 10.3969/j. issn.1001-3695.2015.10.073.
CHEN X,HE Z S,LI Y H. Improved color image segmentation of GrabCut algorithm based on SLICO[J]. Application Research of Computers,2015,32(10): 3191-3195.
[34] 周志宇,刘迎春,张建新. 基于自适应Canny算子的柑橘边缘检测[J]. 农业工程学报,2008,24(3): 21-24.
ZHOU Z Y,LIU Y C,ZHANG J X. Orange edge detection based on adaptive Canny operator [J]. Transactions of the CSAE,2008,24(3): 21-24.
[35] 段红燕,邵豪,张淑珍,等. 一种基于Canny算子的图像边缘检测改进算法[J]. 上海交通大学学报,2016,50(12): 1861-1865. DOI:10.16183/j.cnki.jsjtu.2016.12.009.
DUAN H Y,SHAO H,ZHANG S Z,et al. An improved algorithm for image edge detection based on Canny operator[J]. Journal of Shanghai Jiaotong University,2016, 50(12): 1861-1865.
[36] 贺强,晏立. 基于LOG和Canny算子的边缘检测算法[J]. 计算机工程,2011,37(3): 210-212.
HE Q,YAN L. Algorithm of edge detection based on LOG and canny operator[J]. Computer Engineering,2011,37(3): 210-212.
PDF(3656140 KB)

Accesses

Citation

Detail
Sections
Recommended
The full text is translated into English by AI, aiming to facilitate reading and comprehension. The core content is subject to the explanation in Chinese.

Author

Reader

Reviewer

www.nldxb.njfu.edu.cn

Edited ＆ Published by Editorial Department of Nanjing Forestry University(Natural Sciences Edition)
Address： No.159 Longpan Road,Nanjing 210037 Jiangsu,P.R.China
E-mail ：xuebao@njfu.edu.cn , xuebao@njfu.com.cn
Telephone +86-25-85428247,85427076
Distributed by China International Book Trading Corporation P.O. Box 399, Beijing ,P.R. China

/

〈 〉