一种改进的基于图论的图像分割方法

doi:10.3969/j.issn.1006-2475.2016.09.014

计算机与现代化

一种改进的基于图论的图像分割方法

(1.怀化学院计算机科学与工程学院,湖南怀化418008；2.武陵山片区生态农业智能控制技术湖南省重点实验室,湖南怀化418008)

收稿日期:2016-02-24 出版日期:2016-09-12 发布日期:2016-09-13
作者简介:叶青(1965-)，女(瑶族)，湖南怀化人，怀化学院计算机科学与工程学院和武陵山片区生态农业智能控制技术湖南重点实验室副教授，硕士，研究方向：数字图像处理，模式识别；胡昌标(1957-)，男（侗族），湖南怀化人，高级实验师，本科，研究方向：计算机软件与理论，算法设计与分析。
基金资助:
湖南省教育厅科学研究基金资助项目(13C714)；怀化学院重点学科建设资助项目

An Improved Image Segmentation Method Based on Graph Theory

(1. College of Computer Science and Engineering, Huaihua University, Huaihua 418008, China; 2. Key Laboratory of Intelligent Control Technology for WulingMountain Ecological Agriculture in Hunan Province, Huaihua 418008, China)

Received:2016-02-24 Online:2016-09-12 Published:2016-09-13

摘要/Abstract

摘要： 由于传统基于图论的图像分割方法是基于像素级别的，随着像素的增多，其应用也受到了限制，因此，提出一种改进的图像分割方法。该图像分割方法利用Dijkstra算法，将图像的像素点聚集形成超像素；应用Kruskal算法，得到最小生成树，确定并删除最小生成树的不一致边，完成图像分割。实验结果表明,改进方法分割的区域内部特征具有较好的均匀性和一致性。

关键词: 图论, 图像分割, 最小生成树, 最短路径, 不一致边

Abstract: The traditional image segmentation method based on graph theory is based on pixel level, whose application is limited when pixel number gets larger. So an improved image segmentation algorithm is proposed, in which image pixels are aggregated to form a super pixel using the Dijkstra algorithm and the Kruskal algorithm is used to get minimum spanning tree, determine and delete the inconsistent minimum spanning tree, and complete image segmentation. The experimental results show that the improved algorithm has the characteristics of regional segmentation uniformity and good consistency.

Key words: graph theory, image segmentation, minimum spanning tree, shortest path, inconsistent side

中图分类号:

TP391.41

叶青1,2，胡昌标1,2. 一种改进的基于图论的图像分割方法[J]. 计算机与现代化, doi: 10.3969/j.issn.1006-2475.2016.09.014.

YE Qing1,2, HU Chang-biao1,2. An Improved Image Segmentation Method Based on Graph Theory[J]. Computer and Modernization, doi: 10.3969/j.issn.1006-2475.2016.09.014.

参考文献

［1］ Urquhart R. Graph theoretical clustering based on limited neighborhood sets［J］. Pattern Recognition, 1982,15(3):173-187.
［2］ 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.
［3］ Felzenszwalb P F, Huttenlocher D P. Image segmentation using local variation［C］// IEEE Computer Society Conference on Computer Vision and Pattern recognition. 1998:98-104．
［4］ Felzenszwalb P F, Huttenlocher D P. Efficient graph-based image segmentation［J］. International Journal of Computer Vision, 2004,59(2):167-181.
［5］ Boykov Y, Veksler O, Zabih R. Fast approximate energy minimization via graph cuts［J］. IEEE Transactions on Pattern Analysis & Machine Intelligence, 2001,23(11):1222-1239.
［6］刘锁兰,王江涛,王建国,等. 一种新的基于图论聚类的分割算法［J］. 计算机科学, 2008,35(9):245-247.
［7］叶青,唐鹏举. 一种改进的基于MST的聚类算法［J］. 计算机与现代化, 2011(8):17-19.
［8］叶青,彭小宁. 图像分割算法的改进研究［J］. 哈尔滨师范大学自然科学学报, 2012,28(1):41-45.
［9］ Boykov Y， Jolly M P． Interactive organ segmentation using graph cuts［M］// Medical Image Computing and ComputerAssisted Intervention. 2000,1935:276-286.
［10］Boykov Y， Kolmogorov V． An experimental comparison of min-cut/maxflow algorithms for energy minimization in vision［J］. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2004,26(9):1124-1137.
［11］Zeng Yun， Samaras D， Chen Wei， et al． Topology cuts: A novel min-cut/max-flow algorithm for topology preserving segmentation in N-D images［J］. Computer Vision and Image Understanding, 2008,112(1):81-90.
［12］Bai Xue, Sapiro G. Distance cut: Interactive segmentation and matting of images and videos［C］// 2007 IEEE International Conference on Image Processing. 2007:Ⅱ-249-Ⅱ-252.
［13］Falcao A X， Udupa J K， Samarasekara S， et al． User-steered image segmentation paradigms: Live wire and live lane［J］． Graphical Models and Image Processing， 1998,60(4):233260
［14］Shi Jianbo， Malik J． Normalized cuts and image segmentation［J］． IEEE Transactions on Pattern Analysis and Machine Intelligence, 2000,22(8):888-905.
［15］Li Xiaobin, Zheng Tian. Optimum cut-based clustering［J］． Signal Processing， 2007，87(11):2491-2502.
［16］Wang Song， Siskind J M. Image segmentation with ratio cut［J］. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2003,25(6):675-690.
［17］Xu Ying， Uberbacher E C. 2D image segmentation using minimum spanning trees［J］. Image and Vision Computing, 1997,15(1):47-57.
［18］殷剑宏,吴开亚. 图论及其算法［M］. 合肥:中国科学技术大学出版社, 2003.
［19］Sergios Theodoridis， Konstantinos Koutroumbas．模式识别［M］. 3版. 李晶皎,王爱侠，张广渊译. 北京:电子工业出版社, 2006.

[1]	张伯泉, 麦海鹏, 陈嘉敏, 逄锦聚. 基于高灰度值注意力机制的脑白质高信号分割[J]. 计算机与现代化, 2023, 0(12): 67-75.
[2]	韩雪. 基于约束聚类和粒子群算法的多路径规划[J]. 计算机与现代化, 2023, 0(08): 7-11.
[3]	王娟, 李传庚, 张卿源, 夏承遗. 基于Multiscale-Net的膝关节半月板分割方法[J]. 计算机与现代化, 2023, 0(05): 111-116.
[4]	刘辉, 邹锋, 陈得宝, 籍旭颖, 张妍. 基于改进MOJAYA/D算法的图像分割[J]. 计算机与现代化, 2023, 0(04): 62-72.
[5]	黄翼虎, 于亚楠. 基于改进Dijkstra算法的防冲突最短路径规划研究[J]. 计算机与现代化, 2022, 0(08): 20-24.
[6]	王淑平, 李敏, 杜敏, 罗建伟. 基于改进探路者算法的多阈值图像分割[J]. 计算机与现代化, 2022, 0(01): 61-69.
[7]	雍玉洁, 顾华. 基于空间聚类和边缘梯度的图像分割算法[J]. 计算机与现代化, 2021, 0(02): 13-17.
[8]	姚传文, 黄道斌, 叶明全, . 基于粗糙集自适应粒度的MR脑肿瘤图像分割[J]. 计算机与现代化, 2021, 0(01): 34-37.
[9]	席孝倩, 刘威. 基于目标检测算法的肺结节辅助诊断系统[J]. 计算机与现代化, 2020, 0(11): 1-7.
[10]	刘晓康, 万曦, 涂文超, 周清楷, 田正稳. 基于红外可见光图像配准的电力设备分割算法[J]. 计算机与现代化, 2020, 0(08): 26-30.
[11]	曹帅帅，陈雪鑫，苗圃，卜庆凯. 基于PSO与K-均值聚类算法优化结合的图像分割方法[J]. 计算机与现代化, 2020, 0(01): 22-.
[12]	李熙莹1,2,3，朱肯钢1,2,3. 结合天空分割和局部透射率优化交通图像去雾算法[J]. 计算机与现代化, 2019, 0(05): 51-.
[13]	陈焦,康桂华,徐凯悦,曹迪. 协作多点传输系统中基于图论的动态分簇算法[J]. 计算机与现代化, 2018, 0(12): 16-.
[14]	孙源,刘汉强. 基于萤火虫算法的无监督最小视觉差彩色图像分割[J]. 计算机与现代化, 2018, 0(12): 85-.
[15]	曹靖康1，段江永2，孟娟2. 基于深度特征融合的空间植物图像分割算法[J]. 计算机与现代化, 2018, 0(10): 58-.

一种改进的基于图论的图像分割方法

An Improved Image Segmentation Method Based on Graph Theory

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价