基于多尺度的改进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]	周遵富,张乾,石计亮,岳诗琴. 基于纹理和结构交互的人脸图像修复[J]. 山东大学学报 (工学版), 2025, 55(4): 18-28.
[2]	刘全金,嵇文,胡浪涛,黄汇磊,杨瑞,李翔,高泽文,魏本征. 基于双解码器的医学图像分割模型[J]. 山东大学学报 (工学版), 2024, 54(6): 8-18.
[3]	马翔悦,徐金东,倪梦莹. 基于多尺度特征模糊卷积神经网络的遥感图像分割[J]. 山东大学学报 (工学版), 2024, 54(3): 44-54.
[4]	高泽文,王建,魏本征. 基于混合偏移轴向自注意力机制的脑胶质瘤分割算法[J]. 山东大学学报 (工学版), 2024, 54(2): 80-89.
[5]	张鑫,费可可. 基于log鲁棒核岭回归的子空间聚类算法[J]. 山东大学学报 (工学版), 2023, 53(6): 26-34.
[6]	侯月武,刘兆英,张婷,李玉鑑,孙长明. 基于改进的DUNet遥感图像道路提取[J]. 山东大学学报 (工学版), 2022, 52(4): 29-37.
[7]	董璐璐,宋金涛,魏伟波,潘振宽. 多相图像分割变分模型的标签函数提升方法[J]. 山东大学学报 (工学版), 2022, 52(4): 54-68.
[8]	郝晋一,李鹏程,黄艺美,李金屏. 基于穿线法的轮胎X光图像畸变检测[J]. 山东大学学报 (工学版), 2022, 52(3): 9-17.
[9]	程业超,刘惊雷. 自适应图正则的单步子空间聚类[J]. 山东大学学报 (工学版), 2022, 52(2): 57-66.
[10]	董新宇,陈瀚阅,李家国,孟庆岩,邢世和,张黎明. 基于多方法融合的非监督彩色图像分割[J]. 山东大学学报 (工学版), 2019, 49(2): 96-101.
[11]	刘振丙, 方旭升, 杨辉华, 蓝如师. 基于多尺度残差神经网络的阿尔茨海默病诊断分类[J]. 山东大学学报 (工学版), 2018, 48(6): 1-7.
[12]	胡建平, 李鑫, 谢琪, 李玲, 张道畅. 基于Delaunay三角化的二维无约束优化EMD方法[J]. 山东大学学报 (工学版), 2018, 48(5): 9-15.
[13]	黄劲潮. 基于快速区域建议网络的图像多目标分割算法[J]. 山东大学学报(工学版), 2018, 48(4): 20-26.
[14]	叶子云,杨金锋. 一种基于加权图模型的手指静脉识别方法[J]. 山东大学学报(工学版), 2018, 48(3): 103-109.
[15]	庞人铭,王波,叶昊,张海峰,李明亮. 基于PCA相似度和谱聚类相结合的高炉历史数据聚类[J]. 山东大学学报(工学版), 2017, 47(5): 143-149.