基于多尺度的改进Graph cut算法

doi:10.6040/j.issn.1672-3961.1.2015.030

山东大学学报(工学版) ›› 2016, Vol. 46 ›› Issue (1): 28-33.doi: 10.6040/j.issn.1672-3961.1.2015.030

基于多尺度的改进Graph cut算法

樊淑炎^1,2, 丁世飞^1,2*

1. 中国矿业大学计算机科学与技术学院, 江苏徐州 221116;
2. 中国科学院计算技术研究所智能信息处理重点实验室, 北京 100190

收稿日期:2015-05-12 出版日期:2016-02-20 发布日期:2015-05-12
通讯作者: 丁世飞(1963- ),男,山东青岛人,教授,博士生导师,主要研究方向为人工智能,机器学习与数据挖掘等. ;E-mail: dingsf@cumt.edu.cn E-mail:745254102@qq.com
作者简介:樊淑炎(1992- ),女,内蒙古兴和人,硕士研究生,主要研究方向为聚类分析与机器学习. E-mail:745254102@qq.com
基金资助:
国家自然科学基金资助项目(61379101);国家重点基础研究发展计划资助项目(2013CB329502)

An improved multi-scale Graph cut algorithm

FAN Shuyan^1,2, DING Shifei^1,2*

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

摘要/Abstract

摘要： 针对Graph cut算法存在着计算复杂度高及可能出现过分割等不足,提出了一种基于多尺度的改进算法,以更好地解决图像分割问题。该算法将多尺度的Normalized cut作为Graph cut算法的目标函数,避免了过分割的现象,同时将精细尺度的精确性和粗糙尺度的易分割性统一结合起来,对像素点进行采样,不仅保留了原来像素点间的关系,还降低了计算复杂度。然后运用基于谱图理论的求解方式,将问题转化为对相似矩阵求解特征值和特征向量的问题,相似度较高。试验结果表明,本研究算法能够对用户选取的图片进行有效地分割,无需用户交互,分割快速且结果精确。

关键词: 谱聚类, 图论, 图像分割, 多尺度, Graph cut, Normalized cut

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

中图分类号:

TP18

樊淑炎, 丁世飞. 基于多尺度的改进Graph cut算法[J]. 山东大学学报(工学版), 2016, 46(1): 28-33.

FAN Shuyan, DING Shifei. An improved multi-scale Graph cut algorithm[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2016, 46(1): 28-33.

参考文献

[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.

多维度评价

Viewed

Full text

Abstract

Cited

Shared

Discussed

基于多尺度的改进Graph cut算法

An improved multi-scale Graph cut algorithm

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

多维度评价

本文评价

推荐阅读 10

[1]	胡建平,李鑫,谢琪,李玲,张道畅. 基于Delaunay三角化的二维无约束优化EMD方法[J]. 山东大学学报 (工学版), 2018, 48(5): 9-15, 37.
[2]	黄劲潮. 基于快速区域建议网络的图像多目标分割算法[J]. 山东大学学报(工学版), 2018, 48(4): 20-26.
[3]	叶子云,杨金锋. 一种基于加权图模型的手指静脉识别方法[J]. 山东大学学报(工学版), 2018, 48(3): 103-109.
[4]	庞人铭,王波,叶昊,张海峰,李明亮. 基于PCA相似度和谱聚类相结合的高炉历史数据聚类[J]. 山东大学学报(工学版), 2017, 47(5): 143-149.
[5]	胡金戈,唐雁. 基于视觉中心转移的视觉显著性检测方法[J]. 山东大学学报(工学版), 2017, 47(3): 27-33.
[6]	李璐,范文涛,杜吉祥. 基于Markov随机场的Student's t混合模型的脑MR图像分割[J]. 山东大学学报(工学版), 2017, 47(3): 49-55.
[7]	任玉玲, 路文, 徐红强, 何立火. 一种基于Shearlet变换的图像质量客观评价方法[J]. 山东大学学报(工学版), 2015, 45(3): 15-21.
[8]	杨秀林1,黄硕2*,邓苗1,张基宏1,3. 基于显著计算与自适应PCNN的图像融合方法[J]. 山东大学学报(工学版), 2014, 44(2): 35-42.
[9]	于海晶1,2, 李桂菊1*. 基于差分盒维数的彩色烟雾图像识别[J]. 山东大学学报(工学版), 2014, 44(1): 35-40.
[10]	戚世乐,王美清. 自适应分割弱边缘的活动轮廓模型[J]. 山东大学学报(工学版), 2013, 43(6): 17-20.
[11]	王兴良,王立宏*,李海军. 谱聚类中特征向量的Bagging选取方法[J]. 山东大学学报(工学版), 2013, 43(2): 35-41.
[12]	严云洋1,2,唐岩岩2,刘以安2，张天翼3. 使用多尺度LBP特征和SVM的火焰识别算法[J]. 山东大学学报(工学版), 2012, 42(5): 47-52.
[13]	管燕,李存华*,仲兆满,孙兰兰. 化学分子结构图分割算法[J]. 山东大学学报(工学版), 2012, 42(5): 65-70.
[14]	张峰1,梁军1,高红梅2,潘猛3. 基于多频带信息融合的小电流故障选线方法[J]. 山东大学学报(工学版), 2012, 42(2): 118-123.
[15]	张新明, 毛文涛, 李振云. 二阶广义概率的二维Otsu阈值分割[J]. 山东大学学报(工学版), 2012, 42(1): 25-33.