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)

845

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] ZHOU Zunfu, ZHANG Qian, SHI Jiliang, YUE Shiqin. Face image inpainting based on texture and structure interaction [J]. Journal of Shandong University(Engineering Science), 2025, 55(4): 18-28.
[2] Xinyu DONG,Hanyue CHEN,Jiaguo LI,Qingyan MENG,Shihe XING,Liming ZHANG. An unsupervised color image segmentation method based on fusion of multiple methods [J]. Journal of Shandong University(Engineering Science), 2019, 49(2): 96-101.
[3] 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.
[4] 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.
[5] 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.
[6] 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.
[7] HU Jinge, TANG Yan. Visual saliency detection based on visual center shift [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2017, 47(3): 27-33.
[8] 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.
[9] 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.
[10] 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.
[11] 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.
[12] 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.
[13] 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.
[14] 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.
[15] 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.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] WANG Su-yu,<\sup>,AI Xing<\sup>,ZHAO Jun<\sup>,LI Zuo-li<\sup>,LIU Zeng-wen<\sup> . Milling force prediction model for highspeed end milling 3Cr2Mo steel[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2006, 36(1): 1 -5 .
[2] LI Kan . Empolder and implement of the embedded weld control system[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2008, 38(4): 37 -41 .
[3] KONG Xiang-zhen,LIU Yan-jun,WANG Yong,ZHAO Xiu-hua . Compensation and simulation for the deadband of the pneumatic proportional valve[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2006, 36(1): 99 -102 .
[4] CHEN Rui, LI Hongwei, TIAN Jing. The relationship between the number of magnetic poles and the bearing capacity of radial magnetic bearing[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2018, 48(2): 81 -85 .
[5] 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 .
[6] JI Tao,GAO Xu/sup>,SUN Tong-jing,XUE Yong-duan/sup>,XU Bing-yin/sup> . Characteristic analysis of fault generated traveling waves in 10 Kv automatic blocking and continuous power transmission lines[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2006, 36(2): 111 -116 .
[7] . [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2009, 39(1): 27 -32 .
[8] QIN Tong, SUN Fengrong*, WANG Limei, WANG Qinghao, LI Xincai. 3D surface reconstruction using the shape based interpolation guided by maximal discs[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2010, 40(3): 1 -5 .
[9] WANG Li-ju,HUANG Qi-cheng,WANG Zhao-xu . [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2006, 36(6): 51 -56 .
[10] WANG Jing,LI Yu-jiang,ZHANG Xiao-jin,BI Yan-jun,CHEN Wei-suo . [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2006, 36(6): 100 -103 .
Copyright 2018 © Editorial office of Journal of Shandong University (Engineering Science)
Supported by Beijing Magtech Co.Ltd