一种用于图像分割的等周算法改进

doi:10.3969/j.issn.1001-2400.2012.02.015

Abstract

Abstract:

An in-depth analysis is conducted on the graph-theory-based-isoperimetric-partition-algorithm (GTBIPA), which has such drawbacks as low noise immunity and low iterative efficiency when applied to image processing, and a new approach is presented. In this new approach, the intensity of arbitrary nodes in graph are analogized as the length and width of a rectangle. On the condition of a constant perimeter of a rectangle, a new weighting function is designed by using the ratio between the present and the maximum area of the rectangle, so that the normalized problem is directly avoided; and by the participation of suboptimal isoperimetric ratio in iterative partitioning, the iteration efficiency of the algorithm is improved. Experimental results show that this new algorithm can efficiently enhance the performance of the GTBIPA by improving its noise immunity and reducing the number of iterations by 10%~30％.

Key words: graph theory, image segmentation, isoperimetric algorithm, weighting function, suboptimal isoperimetric ratio

CLC Number:

TP391

WANG Yunfei;BI Duyan;HUANG Fei. Improved isoperimetric algorithm for image segmentation[J].J4, 2012, 39(2): 87-94+212.

References

［1］黄长专, 王彪, 杨忠. 图像分割方法研究［J］. 计算机技术与发展, 2009, 19(6): 76-79.
Huang Changzhuan, Wang Biao, Yang Zhong. A Study on Image Segmentation Technique［J］. Computer Technology and Development, 2009, 19(6): 76-79.
［2］ Diestel R. Graph Theory［M］. 4th Ed.German: Springer-Verlag, 2010: 451-471.
［3］ Couprie C, Grady L. Power Watersheds: a New Image Segmentation Framework Extending Graph Cuts, Random Walker and Optimal Spanning Forest［C］//Proc of the 12th International Conference on Computer Vision(ICCV). Kyoyo: IEEE Inc, 2009: 731-738.
［4］ Shi J, Malik J. Normalized Cuts and Image Segmentation［J］. IEEE Trans on Pattern Analysis and Machine Intelligence, 2000, 22(8): 888-905.
［5］ Grady L. Random Walks for Image Segmentaion［J］. IEEE Trans on Pattern Analysis and Machine Intelligence, 2006, 28(11): 1-17.
［6］ Grady L, Schwartz E L. Isoperimetric Graph Partitioning for Image Segmentation［J］. IEEE Trans on Pattern Analysis and Machine Intelligence, 2006, 28(3): 469-475.
［7］ Chen M, Liu M, Liu J. Isoperimetric Cut on a Directed Graph［C］//Proc of 2010 Computer Vision and Pattern Recognition(CVPR). San Francisco: IEEE Inc, 2010: 2109-2116.
［8］ Merge M, Dong M. Bipartite Isoperimetric Graph Partition for Data Co-clustering［J］. Data Ming and Knowledge Discovery, 2008, 16(3): 276-312.
［9］ Grady L. Space-Variant Machine Vision-A Graph Theoretic Approach［D］. Boston: University of Vermont, 2004.
［10］ Strang G. Introduction to Applied Mathematics［M］.1th Edition. Massachusetts Institute of Technology: Wellesley Cambridge Press, 1986: 768-813.
［11］刘建磊, 冯大政. 一种全局最优的非匀质图像分割算法［J］. 西安电子科技大学学报, 2011, 38(2): 67-71.
Liu Jianlei, Feng Dazheng. Non-homogenous Image Segmentation with Global Optimization［J］. Journal of Xidian University, 2011, 38(2): 67-71.
［12］ Gracias N, Mahoor M, Negahdaripour S, et al. Fast Image Blending Using Watersheds and Graph Cuts［J］. Image and Vision Computing, 2009, 27(5): 597-607.

[1]	ZHOU Peng,YANG Jun. Semantic segmentation of remote sensing images based on neural architecture search [J]. Journal of Xidian University, 2021, 48(5): 47-57.
[2]	LIU Zhiqiang,ZHANG Mingjin,CHI Yuan,LI Yunsong. Hardware Trojan detection algorithm based on deep learning [J]. Journal of Xidian University, 2019, 46(6): 37-45.
[3]	WU Chengmao;SHANGGUAN Ruoyu. Neutrosophic fuzzy clustering segmentation algorithm based on HMRF [J]. Journal of Xidian University, 2017, 44(6): 103-108+121.
[4]	LI Jiajie;LIU Xiaoyuan;CHEN Guimin. Automatically generating kinetostatic model for planar flexure-based compliant mechanisms [J]. Journal of Xidian University, 2016, 43(6): 74-79.
[5]	WANG Yunfei;BI Duyan;LIU Huawei;LIU Ling;ZHAO Xiaolin. Locally-restricted regular clustering superpixel algorithm [J]. Journal of Xidian University, 2016, 43(3): 95-100.
[6]	MA Yong;MA Jianfeng;SUN Cong;ZHANG Shuang;CUI Xining;LI Yahui. Component-based failure mode and effect analysis for flight control systems [J]. Journal of Xidian University, 2016, 43(2): 174-179.
[7]	GAN Lu;WU Yan;WANG Fan. Unsupervised SAR image segmentation using TMF and belief propagation [J]. J4, 2015, 42(6): 49-55.
[8]	ZHANG Zejun;SHUI Penglang. SAR images segmentation algorithm using chain coding grid in G⁰ distribution [J]. J4, 2015, 42(5): 48-54.
[9]	WANG Weiwei;YANG Gongpeng;Lü Chang;YANG Yanqi. New image segmentation model based on the level set method [J]. J4, 2013, 40(6): 39-45+91.
[10]	ZHANG Wenjuan;FENG Xiangchu. Image super-pixels segmentation method based on the non-convex low-rank and sparse constraints [J]. J4, 2013, 40(5): 86-91.
[11]	MA Miao;LIANG Jianhui;GUO Min. SAR image thresholding segmentation based on the bacteria foraging algorithm [J]. J4, 2011, 38(6): 152-158+178.
[12]	CUI Yanpeng；HU Jianwei；YANG Shaoquan；ZHU Yan. SAR image automatic segmentation based on DT-GrowCut [J]. J4, 2011, 38(3): 150-154.
[13]	LIU Jianlei;FENG Dazheng. Non-homogenous image segmentation with global optimization [J]. J4, 2011, 38(2): 66-71.
[14]	XU Jianjun;GAO Shan;BI Duyan;CHEN You. A novel image segmentation algorithm [J]. J4, 2011, 38(1): 8-15.
[15]	LIU Han-qiang;JIAO Li-cheng;ZHAO Feng. SAR image multilevel segmentation based on local similarity measure [J]. J4, 2010, 37(6): 1071-1076.

Improved isoperimetric algorithm for image segmentation

PDF (PC)

Like

Knowledge

Cited

Abstract

Cite this article

share this article

References

Related Articles 15

Metrics

Comments

Recommended 10