An Improved Image Segmentation Method Based on Graph Theory

doi:10.3969/j.issn.1006-2475.2016.09.014

Abstract

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

CLC Number:

TP391.41

YE Qing1,2, HU Chang-biao1,2. An Improved Image Segmentation Method Based on Graph Theory[J]. Computer and Modernization, 2016, 0(9): 64-67.

References

［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]	WAN Hongwei, CHEN Pinghua. Polyp Segmentation Based on Involution and Coordinate Reverse Attention [J]. Computer and Modernization, 2024, 0(11): 84-90.
[2]	ZHAO Wenbo1, XIANG Dong1, WANG Jiubin2, DENG Yuehui3, ZHANG Wei1, KANG Qian1, LI Yujie1. Infrared Image Segmentation of Electrical Equipment Based on Improved Slime Mould Algorithm and Tsallis Entropy [J]. Computer and Modernization, 2024, 0(06): 70-75.
[3]	ZHU Fen, HE Lifeng, SUN Shuang, ZHANG Mengying, YU Jiajia. Pancreas Segmentation Model Based on Deformable Residual and Cascading Encoding [J]. Computer and Modernization, 2024, 0(06): 83-88.
[4]	ZHANG Zixu, LI Jiaying, LUAN Pengpeng, PENG Yuanyuan. An Attention Mechanism-based U-Net Fundus Image Segmentation Algorithm [J]. Computer and Modernization, 2024, 0(05): 110-114.
[5]	ZHANG Bo-quan, MAI Hai-peng, CHEN Jia-min, Pang Jin-ju. White Matter Hyperintensities Segmentation Based on High Gray Value#br# Attention Mechanism [J]. Computer and Modernization, 2023, 0(12): 67-75.
[6]	HAN Xue. Multi Path Planning Based on Constrained Clustering and Particle Swarm Optimization [J]. Computer and Modernization, 2023, 0(08): 7-11.
[7]	WANG Juan, LI Chuan-geng, ZHANG Qing-yuan, XIA Cheng-yi. Segmentation Method of Knee Meniscus Based on Multiscale-net [J]. Computer and Modernization, 2023, 0(05): 111-116.
[8]	LIU Hui, ZOU Feng, CHEN De-bao, JI Xu-ying, ZHANG Yan. An Improved MOJAYA/D Algorithm for Image Segmentation [J]. Computer and Modernization, 2023, 0(04): 62-72.
[9]	HUANG Yi-hu, YU Ya-nan. Anti-collision Shortest Path Planning Based on Improved Dijkstra Algorithm [J]. Computer and Modernization, 2022, 0(08): 20-24.
[10]	WANG Shu-ping, LI Min, DU Min, LUO Jian-wei. Multilevel Thresholding Image Segmentation Using Improved Pathfinder Algorithm [J]. Computer and Modernization, 2022, 0(01): 61-69.
[11]	YONG Yu-jie, GU Hua. Image Segmentation Algorithm Based on Spatial Clustering and Edge Gradient [J]. Computer and Modernization, 2021, 0(02): 13-17.
[12]	YAO Chuan-wen, HUANG Dao-bin, YE Ming-quan, . MR Brain Tumor Image Segmentation Based on Rough Set Adaptive Granularity [J]. Computer and Modernization, 2021, 0(01): 34-37.
[13]	XI Xiao-qian, LIU Wei. Pulmonary Nodule Aided Diagnosis System Based on Target Detection Algorithm [J]. Computer and Modernization, 2020, 0(11): 1-7.
[14]	LIU Xiao-kang, WAN Xi, TU Wen-chao, ZHOU Qing-kai, TIAN Zheng-wen. Power Equipment Segmentation Algorithm Based on Infrared and Visible Images Registration [J]. Computer and Modernization, 2020, 0(08): 26-30.
[15]	CAO Shuai-shuai， CHEN Xue-xin， MIAO Pu， BU Qing-kai. Image Segmentation Method Based on Optimization of PSO Algorithm #br# and K-means Clustering Algorithm [J]. Computer and Modernization, 2020, 0(01): 22-.