JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE) ›› 2016, Vol. 46 ›› Issue (1): 28-33.doi: 10.6040/j.issn.1672-3961.1.2015.030

Previous Articles     Next Articles

An improved multi-scale Graph cut algorithm

FAN Shuyan1,2, DING Shifei1,2*   

  1. 1. School of Computer Science and Technology, China University of Mining and Technology, Xuzhou 221116, Jiangsu, China;
    2. Key Laboratory of Intelligent Information Processing, Institute of Computing Technology, Chinese Academy of Science, Beijing 100190, China
  • Received:2015-05-12 Online:2016-02-20 Published:2015-05-12

PDF (PC)

702

Abstract: Aimed at Graph cut algorithm that has the short comings of high computational and possible aver-segmentation, a developed algorithm was presented. The algorithm used multi-scale normalized cut as an objective function of Graph cut algorithm which could avoid the over-segmentation phenomenon. Meanwhile, by combining accuracy of fine scale and easy divisibility of rough scale, sampling pixels not only retained the relationship between the original pixels, but also reduced computational complexity. By using the solving approach based on spectral graph theory, the problem was transformed into similarity matrix eigenvalue and eigenvectors problems, and the similarity was high. Experimental results showed that the proposed algorithm could effectively segment images without user interaction. The segmentation process was fast and segmentation results were accurate.

Key words: spectral clustering, graph theory, image segmentation, multi-scale, graph cut, Normalized cut

CLC Number: 

  • TP18
[1] 艾海舟, 兴军亮. 计算机视觉:算法与应用[M].北京:清华大学出版社, 2012:206-235. AI Haizhou, XING Junliang. Computer Vision:Algorithms and Applications[M]. Beijing:Tsinghua University Press, 2012:206-235.
[2] 韩守东, 赵勇, 陶文兵, 等. 基于高斯超像素的快速 Graph Cuts 图像分割方法[J]. 自动化学报, 2011, 37(1):10-20. HAN Shoudong, ZHAO Yong, TAO Wenbing, et al. Gaussian super-pixel based fast image segmentation using graph Cuts[J]. Acta Automatica Sinica, 2011, 37(1):10-20.
[3] OTSUKI K, KOBAYASHI Y, MUROTA K. Improved max-flow min-cut algorithms in a circular disk failure model with application to a road network[J]. European Journal of Operational Research, 2016, 248(2):396-403.
[4] ZHOU Xiangyang, ZHANG Jiaxin, KULIS Brian. Power-Law graph cuts[J]. Computer Vision and Pattern Recognition, 2014:1411-1971.
[5] SESHADRI K, SHALINIE S M. Parallelization of a graph-cut based algorithm for hierarchical clustering of web documents[J]. Concurrency and Computation:Practice and Experience, 2015, 27(17):5156-5176.
[6] ZHANG D, JODOIN P M, LI C, et al. Novel graph cuts method for multi-frame super-resolution[J]. IEEE Signal Processing Letters, 2015, 22(12):2279-2283.
[7] BOYKOV Y, JOLLY M P. Interactive graph cuts for optimal boundary and region segmentation of objects in ND images[C] //IEEE International Conference on Computer Vision. New York,USA:IEEE, 2001:105-112.
[8] WU Z, LEAHY R. An optimal graph theoretic approach to data clustering:theory and its application to image segmentation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1993, 15(11):1101-1113.
[9] WEI Y C, CHENG C K. Toward efficient hierarchical designs by ratio cut partition[C] //IEEE International Conference on CAD. New York:IEEE, 1989:298-301.
[10] SARKAR S, SOUNDARARAJAN P. Supervised learning of large perceptual organization:graph spectral partitioning and learning automata[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2000, 22(5):504-525.
[11] SHI J B, MALIK J. Normalized cuts and image segmentation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2000, 22(8):888-905.
[12] DING C, HE X, ZHA H, et al. A min-max cut algorithm for graph partitioning and data clustering[C] //Proceedings of the 2001 IEEE International Conference on Data Mining. Washington D C, USA:IEEE Computer Society, 2001:107-114
[13] NEWMAN M E J. Finding community structure in networks using the eigenvectors of matrices[J]. Physical Review E, 2006, 74(3):36-104.
[14] NEWMAN M E J. Modularity and community structure in networks[J]. Proceedings of the National Academy of Sciences of the United States, 2006, 103(23):8577-8582.
[15] NEWMAN M E J. Analysis of weighted networks[J].Physical Review E, 2004, 70(5):56-131.
[16] LEICHT E A, NEWMAN M E J. Community structure in directed networks[J]. Physical Review Letters, 2008, 100(11):118-703.
[17] COUR T, BENEZIT F, SHI J. Spectral segmentation with multiscale graph decomposition[C] //IEEE Computer Society Conference on Computer Vision and Pattern Recognition(CVPR). New York,USA:IEEE, 2005:1124-1131.
[18] 孙吉贵, 刘杰, 赵连宇. 聚类算法研究[J]. 软件学报, 2008, 19(1):48-61. SUN Jigui, LIU Jie, ZHAO Lianyu. Clustering algorithms research[J]. Journal of Software, 2008, 19(1):48-61.
[19] 孙惠泉. 图论及其应用[M]. 北京:科学出版社, 2004.
[20] PACCANARO A, CHENNUBHOTLA C, CASBON J A. Spectral clustering of protein sequences[J]. Nucleic Acids Research, 2006, 34(5):1571-1580.
[21] JIA H, DING S, XU X, et al. The latest research progress on spectral clustering[J]. Neural Computing and Applications, 2014, 6(24):1477-1486.
[22] 李建元, 周脚根, 关佶红, 等. 谱图聚类算法研究进展[J]. 智能系统学报, 2011, 6(5):405-414. LI Jianyuan, ZHOU Jiaogen, GUAN Jihong, et al. A survey of clustering algorithms based on spectra of graphs[J]. CAAI Transactions on Intelligent Systems, 2011, 6(5):405-414.
[23] LINDEBERG T. Scale-Space theory in computer vision[M].Berlin:Springer Science & Business Media, 2013.
[24] 王鹏伟. 基于多尺度理论的图像分割方法研究[D]. 合肥: 中国科学技术大学, 2007. WANG Pengwei. Research on the application of multi-scale analysis method in image segmentation[D]. Hefei:University of Science And Technology of China, 2007.
[25] CHEN W Y, SONG Y Q, BAI H J, et al. Parallel spectral clustering in distributed systems[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2011, 33(3):568-586.
[26] 黄先楼.基于Normalized Cut的图像分割及其CUDA并行实现[D].北京:北京交通大学, 2014. HUANG Xianlou. Image segmentation based on Normalized Cut and CUDA parallel implementation[D]. Beijing:Beijing Jiaotong University, 2014.
[1] Jianping HU,Xin LI,Qi XIE,Ling LI,Daochang ZHANG. An unconstrained optimization EMD approach in 2D based on Delaunay triangulation [J]. Journal of Shandong University(Engineering Science), 2018, 48(5): 9-15, 37.
[2] HUANG Jinchao. A new method for muti-objects image segmentation based on faster region proposal networks [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2018, 48(4): 20-26.
[3] YE Ziyun, YANG Jinfeng. A finger-vein recognition method based on weighted graph model [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2018, 48(3): 103-109.
[4] PANG Renming, WANG Bo, YE Hao, ZHANG Haifeng, LI Mingliang. Clustering of blast furnace historical data based on PCA similarity factor and spectral clustering [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2017, 47(5): 143-149.
[5] HU Jinge, TANG Yan. Visual saliency detection based on visual center shift [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2017, 47(3): 27-33.
[6] LI Lu, FAN Wentao, DU Jixiang. Brain MR image segmentation based on student's t mixture model with Markov random field [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2017, 47(3): 49-55.
[7] YANG Xiulin1, HUANG Shuo2*, DENG Miao1, ZHANG Jihong1,3. Image fusion method based on saliency computation and adaptive PCNN [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2014, 44(2): 35-42.
[8] YU Hai-jing1,2, LI Gui-ju1*. Color smoke image recognition based on differential box-counting fractal dimension algorithm [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2014, 44(1): 35-40.
[9] QI Shile, WANG Meiqing. Adaptive active contour model for weak boundary extractio [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2013, 43(6): 17-20.
[10] WANG Xing-liang, WANG Li-hong*, LI Hai-jun. Eigenvector selection in spectral clustering based on Bagging [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2013, 43(2): 35-41.
[11] GUAN Yan, LI Cun-hua*, ZHONG Zhao-man, SUN Lan-lan. Segmentation algorithm of chemical molecular structure images [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2012, 42(5): 65-70.
[12] ZHANG Feng1, LIANG Jun1, GAO Hong-mei2, PAN Meng3. Adaptive fault line selection method based on  a multi-scale frequency signal in non-solid earthed network [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2012, 42(2): 118-123.
[13] ZHANG Xin-ming, MAO Wen-tao, LI Zhen-yun. Two-dimensional Otsu image thresholding based on second order generalized probability [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2012, 42(1): 25-33.
[14] WANG Liya, PAN Zhenkuan, WEI Weibo*, LIU Cunliang, ZHANG Zhimei, WANG Yu. Alternating convex relaxation minimization of the multiphase image
segmentation model and its Split Bregman algorithm [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2011, 41(2): 40-45.
[15] WANG Xin-pei1, LIU Chang-chun1*, BAI Tong2. An image segmentation method based on mean divergence [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2010, 40(4): 36-41.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] LI Ke,LIU Chang-chun,LI Tong-lei . Medical registration approach using improved maximization of mutual information[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2006, 36(2): 107 -110 .
[2] YUE Yuan-Zheng. Relaxation in glasses far from equilibrium[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2009, 39(5): 1 -20 .
[3] WANG Yong, XIE Yudong. Gas control technology of largeflow pipe[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2009, 39(2): 70 -74 .
[4] LIU Xin 1, SONG Sili 1, WANG Xinhong 2. [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2009, 39(2): 98 -100 .
[5] MENG Jian, LI Yibin, LI Bin. Bound gait controlling method of quadruped robot[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2015, 45(3): 28 -34 .
[6] HANG Guang-qing,KONG Fan-yu,LI Da-xing, . Efficient algorithm with resistance to simple power analysis on Koblitz curves[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2007, 37(3): 78 -80 .
[7] XU Yan-sheng,LIU Xing-fang . Application of the fuzzy clustering iterative model to the evalution of water resource carrying capacity[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2007, 37(3): 100 -104 .
[8] LI Shan-ping,HU Zhen,SUN Yi-ming*,ZHEN Bo-ru,ZHANG Qi-lei,CAO Han-lin . Preparation and evaluation of the electro-catalytic characteristics of novel lead Ti-based dioxide electrodes[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2007, 37(3): 109 -113 .
[9] LI Xin-Ping, DAI Yi-Fei, HU Jing. Fluid-solid coupling analysis of surrounding rock mass stability and water inflow forecast of a tunnel in a karst zone[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2009, 39(4): 1 -6 .
[10] HE Dongzhi, ZHANG Jifeng, ZHAO Pengfei. Parallel implementing probabilistic spreading algorithm using MapReduce programming mode[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 0, (): 22 -28 .
Copyright 2018 © Editorial office of Journal of Shandong University (Engineering Science)
Supported by Beijing Magtech Co.Ltd