An Efficient Image Segmentation Approach Based on Graph Theory

Yongbo Liu

doi:10.6180/jase.201803_21(1).0014

An Efficient Image Segmentation Approach Based on Graph Theory

Mathematics / Statistics

Yongbo Liu This email address is being protected from spambots. You need JavaScript enabled to view it.¹

¹Department of Management, Hunan City University, Yiyang, Hunan 413000, P.R. China

Received: December 30, 2016
Accepted: January 5, 2018
Publication Date: March 1, 2018

Download Citation: ||https://doi.org/10.6180/jase.201803_21(1).0014

ABSTRACT

Image segmentation technology refers to a basic operation for image processing, and it can provide preparation works for high-level image analysis. The goal of this paper is to segment images with high accuracy and efficiency using the graph theory. In this paper, we propose an image segmentation algorithm based on graph cuts. We convert the image segmentation problem to a labeling problem, and we aim to allocate each pixel or block a label by deal with a graph optimization problem. The main idea of this paper lies in that we introduce some external information in the graph cut based image segmentation. Firstly, we create an augmented image which integrates the original image with texture features. Secondly, we propose a novel method to combine the region and boundary information in our proposed graph cut based image segmentation algorithm. Experimental results prove that our proposed algorithm can achieve lower average error rate than other methods, especially for images which contain salient objects and simple backgrounds.

Keywords: Image Segmentation, Graph Theory, Euclidean Distance, Foreground Region, Background Region

REFERENCES

[1] Arbelaez, P., Maire, M., Fowlkes, C. and Malik, J., “Contour Detection and Hierarchical Image Segmentation,” IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 33, No. 5, pp. 898916 (2011). doi: 10.1109/TPAMI.2010.161
[2] Vedanarayanan, V. and Nandhitha, N. M., “Advanced Image Segmentation Techniques for Accurate Isolation of Abnormality to Enhance Breast Cancer Detection in Digital Mammographs,” Biomedical ResearchIndia, Vol. 28, No. 6, pp. 27532757 (2017).
[3] Reska, D., Boldak, C. and Kretowski, M., “Towards Multi-stage Texture-based Active Contour Image Segmentation,” Signal Image and Video Processing, Vol. 11, No. 5, pp. 809816 (2017). doi: 10.1007/s11760016-1026-y
[4] Liang, Y. F., Sun, L., Ser, W., Lin, F., Tay, E. Y., Gan, E. Y., T. Thng, G. and Lin, Z. P., “Hybrid Threshold Optimization between Global Image and Local Regions in Image Segmentation for Melasma Severity Assessment,” Multidimensional Systems and Signal Processing, Vol. 28, No. 3, pp. 977994 (2017). doi: 10.1007/s11045-015-0375-y
[5] Khelifi, L. and Mignotte, M., “A Multi-objective Decision Making Approach for Solving the Image Segmentation Fusion Problem,” IEEE Transactions on Image Processing, Vol. 26, No. 8, pp. 38313845 (2017). doi: 10.1109/TIP.2017.2699481
[6] Fan, H. D., Xie, F. Y., Li, Y., Jian, Z. G. and Liu, J., “Automatic Segmentation of Dermoscopy Images Using Saliency Combined with Otsu Threshold,” Computers in Biology and Medicine, Vol. 85, pp. 7585 (2017). doi: 10.1016/j.compbiomed.2017.03.025
[7] Ben Ishak, A., “Choosing Parameters for Renyi and Tsallis Entropies within a Two-dimensional Multilevel Image Segmentation Framework,” Physica a-Statistical Mechanics and Its Applications, Vol. 466, pp. 521536 (2017). doi: 10.1016/j.physa.2016.09.053
[8] Stylianidou, S., Brennan, C., Nissen, S. B., Kuwada, N. J. and Wiggins, P. A., “SuperSegger: Robust Image Segmentation, Analysis and Lineage Tracking of BacterialCells,”Molecular Microbiology, Vol. 102, No. 4, pp. 690700 (2016). doi: 10.1111/mmi.13486
[9] Niu, S. J., Chen, Q., de Sisternes, L., Ji, Z. X., Zhou, Z. M. and Rubin, D. L., “Robust Noise Region-based Active Contour Model via Local SimilarityFactor for Image Segmentation,” Pattern Recognition, Vol. 61, pp. 104119 (2017). doi: 10.1016/j.patcog.2016.07.022
[10] Liu, C., Liu, W. B. and Xing, W. W., “An Improved Edge-based Level Set Method Combining Local Regional Fitting Information for Noisy Image Segmentation,” Signal Processing, Vol. 130, pp. 1221 (2017). doi: 10.1016/j.sigpro.2016.06.013
[11] Gupta, D. and Anand, R. S., “A Hybrid Edge-based Segmentation Approach for Ultrasound Medical Images,” Biomedical Signal Processing and Control, Vol. 31, pp. 116126 (2017). doi: 10.1016/j.bspc.2016.06. 012
[12] Xie, H., Luo, X., Wang, C., Liu, S. J., Xu, X. and Tong, X. H., “Multispectral Remote Sensing Image Segmentation Using Rival Penalized Controlled Competitive Learning and Fuzzy Entropy,” Soft Computing, Vol. 20, No. 12, pp. 47094722 (2016). doi: 10.1007/ s00500-015-1601-0
[13] von Landesberger, T., Basgier, D. and Becker, M., “Comparative Local Quality Assessment of 3D Medical Image Segmentations with Focus on Statistical Shape Model-based Algorithms,” IEEE Transactions on Visualization and Computer Graphics, Vol. 22, No. 12, pp. 25372549 (2016). doi: 10.1109/TVCG.2015. 2501813
[14] Rosado-Toro, J. A., Altbach, M.I. and Rodriguez, J. J.,
“Dynamic Programming Using Polar Variance for Image Segmentation,” IEEE Transactions on Image Processing, Vol. 25, No. 12, pp. 58575866 (2016). doi: 10.1109/TIP.2016.2615809
[15] Li,X., Song, J. D., Zhang, F., Ouyang, X. G. and Khan, S. U., “MapReduce-based Fast Fuzzy c-means Algorithm for Large-scale Underwater Image Segmentation,” FutureGenerationComputerSystems-theInternational Journal of Escience, Vol. 65, pp. 90101 (2016). doi: 10.1016/j.future.2016.03.004
[16] Li, L. L., Jia, Z. H., Yang, J. and Kasabov, N., “Noisy Remote Sensing Image Segmentation with Wavelet Shrinkage and Graph Cuts,” Journal of the Indian Society of Remote Sensing, Vol. 44, No. 6, pp. 9951002 (2016). doi: 10.1007/s12524-016-0561-x
[17] Jiang, Y. Z., Yeh, W. C., Hao, Z. F. and Yang, Z. L., “A Cooperative Honey Bee Mating Algorithm and Its Application in Multi-threshold Image Segmentation,” Information Sciences, Vol. 369, pp. 171183 (2016). doi: 10.1016/j.ins.2016.06.020
[18] Hou, J., Liu, W. X., E, X. and Cui, H. X., “Towards Parameter-independent Data Clustering and Image Segmentation,” Pattern Recognition, Vol. 60, pp. 2536 (2016). doi: 10.1016/j.patcog.2016.04.015
[19] He,K., Wang, D. and Zhang, X., “ImageSegmentation Using the Level Set and Improved-variation Smoothing”ComputerVision and ImageUnderstand, Vol. 152, pp. 2940 (2016). doi: 10.1016/j.cviu.2016.06.006
[20] Gao, H., Pun, C. M. and Kwong, S., “An Efficient Image Segmentation Method Based on a Hybrid Particle Swarm Algorithm with Learning Strategy,” Information Sciences, Vol. 369, pp. 500521 (2016). doi: 10. 1016/j.ins.2016.07.017
[21] Duan, Y. P., Liu, F. and Jiao, L. C., “Sketching Model and Higher Order Neighborhood Markov Random Field-based SAR Image Segmentation,” IEEE Geoscience and Remote Sensing Letters, Vol. 13, No. 11, pp. 16861690 (2016). doi: 10.1109/LGRS.2016.2604256
[22] Chen, H. C., Feng, H. M., Lin, T. H., Chen, C. Y. and Zha, Y. X., “Adapt DB-PSO Patterns Clustering Algorithms and Its Applications in Image Segmentation,” Multimedia Tools and Applications, Vol. 75, No. 23, pp. 1532715339 (2016). doi: 10.1007/s11042-0152518-4
[23] Chang, D. X., Zhao, Y., Liu, L. and Zheng, C. W., “A Dynamic Niching Clustering Algorithm Based on Individual-connectedness and Its Application to Color Image Segmentation,” Pattern Recognition, Vol. 60, pp. 334347 (2016). doi: 10.1016/j.patcog.2016.05. 008
[24] Zhang, Z. B., Yang, E. B., Choi, C. S. and Chang, H. Y.,“Classifying Gamma-ray Bursts with Gaussian Mixture Model,” Monthly Notices of the Royal Astronomical Society, Vol. 462, No. 3, pp. 32433254 (2016). doi: 10.1093/mnras/stw1835
[25] Kayabol, K. and Kutluk, S., “Bayesian Classification of Hyperspectral Images Using Spatially-varying Gaussian Mixture Model,” Digital Signal Processing, Vol.
59, pp. 106114 (2016). doi: 10.1016/j.dsp.2016.08.010
[26] Rother, C., Kolmogorov, V. and Blake, A., “Grabcut: Interactive Foreground Extraction Using Iterated Graph Cuts,” Proceedings of the ACM SIGGRAPH Conference, pp. 309314 (2004). doi: 10.1145/1015706. 1015720
[27] Candemir, S. and Akgül, Y., “Adaptive Regularization Parameter for Graph Cut Segmentation,” Proceedings of the Image Analysis and Recognition, pp. 117126 (2010).