research-article

Interactive image segmentation using label propagation through complex networks

Author:

Fabricio BreveAuthors Info & Claims

Volume 123, Issue C

Pages 18 - 33

https://doi.org/10.1016/j.eswa.2019.01.031

Published: 01 June 2019 Publication History

Highlights

•

This paper presents a new graph-based interactive image segmentation method.

•

It uses small-world complex networks to propagate the labels quickly.

•

“Scribbles” loosely traced over the objects of interest may be used as seeds.

•

The proposed method has low computational time and storage complexity.

•

Its accuracy and speed are comparable to those of state-of-the-art methods.

Abstract

Interactive image segmentation is a topic of many studies in image processing. In a conventional approach, a user marks some pixels of the object(s) of interest and background, and an algorithm propagates these labels to the rest of the image. This paper presents a new graph-based method for interactive segmentation with two stages. In the first stage, nodes representing pixels are connected to their k-nearest neighbors to build a complex network with the small-world property to propagate the labels quickly. In the second stage, a regular network in a grid format is used to refine the segmentation on the object borders. Despite its simplicity, the proposed method can perform the task with high accuracy. Computer simulations are performed using some real-world images to show its effectiveness in both two-classes and multi-classes problems. It is also applied to all the images from the Microsoft GrabCut dataset for comparison, and the segmentation accuracy is comparable to those achieved by some state-of-the-art methods, while it is faster than them. In particular, it outperforms some recent approaches when the user input is composed only by a few “scribbles” draw over the objects. Its computational complexity is only linear on the image size at the best-case scenario and linearithmic in the worst case.

References

[1]

F. Andrade, E.V. Carrera, Supervised evaluation of seed-based interactive image segmentation algorithms, 2015 20th symposium on signal processing, images and computer vision (STSIVA), 2015, pp. 1–7,.

[2]

Y. Artan, Interactive image segmentation using machine learning techniques, Computer and robot vision (CRV), 2011 Canadian conference on, 2011, pp. 264–269,.

[3]

M. Avendi, A. Kheradvar, H. Jafarkhani, A combined deep-learning and deformable-model approach to fully automatic segmentation of the left ventricle in cardiac MRI, Medical Image Analysis 30 (2016) 108–119,.

[4]

C.G. Bampis, P. Maragos, A.C. Bovik, Graph-driven diffusion and random walk schemes for image segmentation, IEEE Transactions on Image Processing 26 (1) (2017) 35–50,.

Digital Library

[5]

A. Blake, C. Rother, M. Brown, P. Perez, P. Torr, Interactive image segmentation using an adaptive GMMRF model, in: T. Pajdla, J. Matas (Eds.), Computer vision - ECCV 2004, in: Lecture Notes in Computer Science, 3021, Springer Berlin Heidelberg, 2004, pp. 428–441,.

[6]

Y. Boykov, G. Funka-Lea, Graph cuts and efficient n-d image segmentation, International Journal of Computer Vision 70 (2) (2006) 109–131,.

Digital Library

[7]

Y. Boykov, M.-P. Jolly, Interactive graph cuts for optimal boundary amp; region segmentation of objects in n-d images, Computer vision, 2001. ICCV 2001. Proceedings. Eighth IEEE international conference on, 1, 2001, pp. 105–112vol.1,.

[8]

F. Bozkurt, C. Kse, A. Sar, An inverse approach for automatic segmentation of carotid and vertebral arteries in cta, Expert Systems with Applications 93 (2018) 358–375,.

Digital Library

[9]

F. Breve, Building networks for image segmentation using particle competition and cooperation, in: O. Gervasi, B. Murgante, S. Misra, G. Borruso, C.M. Torre, A.M.A. Rocha, D. Taniar, B.O. Apduhan, E. Stankova, A. Cuzzocrea (Eds.), Computational science and its applications – ICCSA 2017, Springer International Publishing, Cham, 2017, pp. 217–231.

[10]

F. Breve, M. Quiles, L. Zhao, Interactive image segmentation of non-contiguous classes using particle competition and cooperation, in: O. Gervasi, B. Murgante, S. Misra, M.L. Gavrilova, A.M.A.C. Rocha, C. Torre, D. Taniar, B.O. Apduhan (Eds.), Computational science and its applications – ICCSA 2015, in: Lecture Notes in Computer Science, 9155, Springer International Publishing, 2015, pp. 203–216,.

[11]

F. Breve, M.G. Quiles, L. Zhao, Interactive image segmentation using particle competition and cooperation, 2015 international joint conference on neural networks (IJCNN), 2015, pp. 1–8,.

[12]

W. Casaca, L.G. Nonato, G. Taubin, Laplacian coordinates for seeded image segmentation, 2014 IEEE conference on computer vision and pattern recognition, 2014, pp. 384–391,.

Digital Library

[13]

C.-C. Chang, C.-J. Lin, Libsvm: A library for support vector machines, ACM Transactions on Intelligent Systems and Technology (TIST) 2 (3) (2011) 27.

[14]

P.F. Christ, M.E.A. Elshaer, F. Ettlinger, S. Tatavarty, M. Bickel, P. Bilic, et al., Automatic liver and lesion segmentation in ct using cascaded fully convolutional neural networks and 3d conditional random fields, in: S. Ourselin, L. Joskowicz, M.R. Sabuncu, G. Unal, W. Wells (Eds.), Medical image computing and computer-assisted intervention – MICCAI 2016, Springer International Publishing, Cham, 2016, pp. 415–423.

[15]

Dheeru, D., & Karra Taniskidou, E. (2017). UCI machine learning repository. http://archive.ics.uci.edu/ml.

[16]

L. Ding, A. Yilmaz, Image segmentation as learning on hypergraphs, Machine learning and applications, 2008. icmla ’08. seventh international conference on, 2008, pp. 247–252,.

Digital Library

[17]

L. Ding, A. Yilmaz, Interactive image segmentation using probabilistic hypergraphs, Pattern Recognition 43 (5) (2010) 1863–1873,.

Digital Library

[18]

L. Ding, A. Yilmaz, R. Yan, Interactive image segmentation using dirichlet process multiple-view learning, IEEE Transactions on Image Processing 21 (4) (2012) 2119–2129,.

Digital Library

[19]

X. Dong, J. Shen, L. Shao, L.V. Gool, Sub-markov random walk for image segmentation, IEEE Transactions on Image Processing 25 (2) (2016) 516–527,.

Digital Library

[20]

O. Duchenne, J.Y. Audibert, R. Keriven, J. Ponce, F. Segonne, Segmentation by transduction, 2008 IEEE conference on computer vision and pattern recognition, 2008, pp. 1–8,.

[21]

A. Ducournau, A. Bretto, Random walks in directed hypergraphs and application to semi-supervised image segmentation, Computer Vision and Image Understanding 120 (0) (2014) 91–102,.

Digital Library

[22]

J.H. Friedman, J.L. Bentley, R.A. Finkel, An algorithm for finding best matches in logarithmic expected time, ACM Transactions on Mathematical Software 3 (3) (1977) 209–226,.

Digital Library

[23]

R.C. Gonzalez, R.E. Woods, Digital image processing (3rd edition), Prentice-Hall, Inc., Upper Saddle River, NJ, USA, 2008.

[24]

L. Grady, Random walks for image segmentation, Pattern Analysis and Machine Intelligence, IEEE Transactions on 28 (11) (2006) 1768–1783,.

Digital Library

[25]

M. Guijarro, G. Pajares, I. Riomoros, P. Herrera, X. Burgos-Artizzu, A. Ribeiro, Automatic segmentation of relevant textures in agricultural images, Computers and Electronics in Agriculture 75 (1) (2011) 75–83,.

Digital Library

[26]

A. Hosni, C. Rhemann, M. Bleyer, C. Rother, M. Gelautz, Fast cost-volume filtering for visual correspondence and beyond, IEEE Transactions on Pattern Analysis and Machine Intelligence 35 (2) (2013) 504–511,.

Digital Library

[27]

M.D. Humphries, K. Gurney, Network small-world-ness: A quantitative method for determining canonical network equivalence, PLOS ONE 3 (4) (2008) 1–10,.

[28]

T.H. Kim, K.M. Lee, S.U. Lee, Generative image segmentation using random walks with restart, in: D. Forsyth, P. Torr, A. Zisserman (Eds.), Computer vision–ECCV 2008, Springer Berlin Heidelberg, Berlin, Heidelberg, 2008, pp. 264–275.

[29]

T.H. Kim, K.M. Lee, S.U. Lee, Nonparametric higher-order learning for interactive segmentation, 2010 IEEE computer society conference on computer vision and pattern recognition, 2010, pp. 3201–3208,.

[30]

P. Kohli, L. Ladický, P.H.S. Torr, Robust higher order potentials for enforcing label consistency, International Journal of Computer Vision 82 (3) (2009) 302–324,.

Digital Library

[31]

V. Lempitsky, P. Kohli, C. Rother, T. Sharp, Image segmentation with a bounding box prior, 2009 IEEE 12th international conference on computer vision, 2009, pp. 277–284,.

[32]

J. Li, J. Bioucas-Dias, A. Plaza, Semisupervised hyperspectral image segmentation using multinomial logistic regression with active learning, Geoscience and Remote Sensing, IEEE Transactions on 48 (11) (2010) 4085–4098,.

[33]

Y. Li, J. Sun, C.-K. Tang, H.-Y. Shum, Lazy snapping, ACM Transactions on Graphics 23 (3) (2004) 303–308,.

Digital Library

[34]

J. Liew, Y. Wei, W. Xiong, S. Ong, J. Feng, Regional interactive image segmentation networks, 2017 IEEE international conference on computer vision (ICCV), 2017, pp. 2746–2754,.

[35]

D. Lin, J. Dai, J. Jia, K. He, J. Sun, Scribblesup: Scribble-supervised convolutional networks for semantic segmentation, 2016 IEEE conference on computer vision and pattern recognition (CVPR), 2016, pp. 3159–3167,.

[36]

S. Martinez-Muoz, D. Ruiz-Fernandez, J.J. Galiana-Merino, Automatic abdominal aortic aneurysm segmentation in mr images, Expert Systems with Applications 54 (2016) 78–87,.

Digital Library

[37]

P. Moeskops, M.A. Viergever, A.M. Mendrik, L.S. de Vries, M.J.N.L. Benders, I. Igum, Automatic segmentation of mr brain images with a convolutional neural network, IEEE Transactions on Medical Imaging 35 (5) (2016) 1252–1261,.

[38]

M.H. Narkhede, A review on graph based segmentation, Journal of Innovative Research in Electrical, Electronics, Instrumentation and Control Engineering 1 (7) (2013) 3.

[39]

C. Oh, B. Ham, K. Sohn, Robust interactive image segmentation using structure-aware labeling, Expert Systems with Applications 79 (2017) 90–100,.

Digital Library

[40]

L.J. Patino-Correa, O. Pogrebnyak, J.A. Martinez-Castro, E.M. Felipe-Riveron, White matter hyper-intensities automatic identification and segmentation in magnetic resonance images, Expert Systems with Applications 41 (16) (2014) 7114–7123,.

Digital Library

[41]

V.Q. Pham, K. Takahashi, T. Naemura, Bounding-box based segmentation with single min-cut using distant pixel similarity, 2010 20th international conference on pattern recognition, 2010, pp. 4420–4423,.

Digital Library

[42]

B.L. Price, B. Morse, S. Cohen, Geodesic graph cut for interactive image segmentation, 2010 IEEE computer society conference on computer vision and pattern recognition, 2010, pp. 3161–3168,.

[43]

C. Rother, V. Kolmogorov, A. Blake, “Grabcut”: Interactive foreground extraction using iterated graph cuts, ACM Transactions on Graphics 23 (3) (2004) 309–314,.

Digital Library

[44]

L. Shapiro, G. Stockman, Computer vision, Prentice Hall, 2001.

Digital Library

[45]

J. Shen, Y. Du, W. Wang, X. Li, Lazy random walks for superpixel segmentation, IEEE Transactions on Image Processing 23 (4) (2014) 1451–1462,.

Digital Library

[46]

A.R. Smith, Color gamut transform pairs, ACM siggraph computer graphics, 12, ACM, 1978, pp. 12–19.

[47]

S. Vicente, V. Kolmogorov, C. Rother, Graph cut based image segmentation with connectivity priors, 2008 IEEE conference on computer vision and pattern recognition, 2008, pp. 1–8,.

[48]

F. Wang, X. Wang, T. Li, Efficient label propagation for interactive image segmentation, Sixth international conference on machine learning and applications (ICMLA 2007), 2007, pp. 136–141,.

Digital Library

[49]

G. Wang, M.A. Zuluaga, W. Li, R. Pratt, P.A. Patel, M. Aertsen, et al., Deepigeos: A deep interactive geodesic framework for medical image segmentation, IEEE Transactions on Pattern Analysis and Machine Intelligence (2018).

[50]

J. Wang, M. Agrawala, M.F. Cohen, Soft scissors: An interactive tool for realtime high quality matting, ACM Transactions on Graphics 26 (3) (2007),.

Digital Library

[51]

T. Wang, Z. Ji, Q. Sun, Q. Chen, Q. Ge, J. Yang, Diffusive likelihood for interactive image segmentation, Pattern Recognition 79 (2018) 440–451,.

[52]

T. Wang, Z. Ji, Q. Sun, Q. Chen, X. Jing, Interactive multilabel image segmentation via robust multilayer graph constraints, IEEE Transactions on Multimedia 18 (12) (2016) 2358–2371,.

Digital Library

[53]

T. Wang, Q. Sun, Q. Ge, Z. Ji, Q. Chen, G. Xia, Interactive image segmentation via pairwise likelihood learning, Proceedings of the twenty-sixth international joint conference on artificial intelligence, IJCAI-17, 2017, pp. 2957–2963,.

[54]

T. Wang, Q. Sun, Z. Ji, Q. Chen, P. Fu, Multi-layer graph constraints for interactive image segmentation via game theory, Pattern Recognition 55 (2016) 28–44,.

Digital Library

[55]

D.J. Watts, S.H. Strogatz, Collective dynamics of ‘small-world’ networks, Nature 393 (6684) (1998) 440–442,.

[56]

W. Yang, J. Cai, J. Zheng, J. Luo, User-friendly interactive image segmentation through unified combinatorial user inputs, IEEE Transactions on Image Processing 19 (9) (2010) 2470–2479,.

Digital Library

[57]

X. Yi, C. Zhang, J. Wang, Multi-view em algorithm and its application to color image segmentation, 2004 IEEE international conference on multimedia and expo (ICME) (IEEE cat. no.04th8763), 1, 2004, pp. 351–354Vol.1,.

[58]

Zanin, M. (2015). On alternative formulations of the small-world metric in complex networks. arXiv preprint. arXiv:1505.03689.

[59]

H. Zhou, J. Zheng, L. Wei, Texture aware image segmentation using graph cuts and active contours, Pattern Recognition 46 (6) (2013) 1719–1733,.

Digital Library

Cited By

Najaran M(2023)A probabilistic meta-heuristic optimisation algorithm for image multi-level thresholdingGenetic Programming and Evolvable Machines10.1007/s10710-023-09460-424:2Online publication date: 24-Oct-2023
https://dl.acm.org/doi/10.1007/s10710-023-09460-4
Wu BZhu LLi X(2023)Giza pyramids construction algorithm with gradient contour approach for multilevel thresholding color image segmentationApplied Intelligence10.1007/s10489-023-04512-953:18(21248-21267)Online publication date: 25-May-2023
https://dl.acm.org/doi/10.1007/s10489-023-04512-9
Shan YMa YLiao YHuang HWang B(2022)Interactive image segmentation based on multi-layer random forest classifiersMultimedia Tools and Applications10.1007/s11042-022-14199-882:15(22469-22495)Online publication date: 18-Nov-2022
https://dl.acm.org/doi/10.1007/s11042-022-14199-8
Show More Cited By

Index Terms

Interactive image segmentation using label propagation through complex networks
1. Computing methodologies
  1. Artificial intelligence
    1. Computer vision
      1. Computer vision problems
        Image segmentation
        Interest point and salient region detections
        Video segmentation
2. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory

Index terms have been assigned to the content through auto-classification.

Recommendations

Interactive object segmentation from multi-view images

Despite the great progress on interactive image segmentation, image co-segmentation, 2D and 3D segmentation, there is still no workable solution to the problem: given a set of calibrated or un-calibrated multi-view images (say, more than 40 images), by ...
Interactive Fuzzy Connectedness Image Segmentation for Neonatal Brain MR Image Segmentation
SMC '13: Proceedings of the 2013 IEEE International Conference on Systems, Man, and Cybernetics

Image segmentation plays a fundamental work to analyze medical images. Although many literatures studied automated image segmentation, it is still difficult to segment region-of-interest in any kind of images. Thus, manual delineation is important yet. ...
Multi-atlas Segmentation Combining Multi-task Local Label Learning and Semi-supervised Label Propagation
Image and Graphics
Abstract
Multi-atlas based segmentation methods have achieved great success in hippocampal segmentation due to their promising performance. However, the correlation between voxels in the target image is often ignored. In this study, an image segmentation ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Expert Systems with Applications: An International Journal

Expert Systems with Applications: An International Journal Volume 123, Issue C

Jun 2019

387 pages

ISSN:0957-4174

Issue’s Table of Contents

Elsevier Ltd.

Publisher

Pergamon Press, Inc.

United States

Publication History

Published: 01 June 2019

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 17 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Najaran M(2023)A probabilistic meta-heuristic optimisation algorithm for image multi-level thresholdingGenetic Programming and Evolvable Machines10.1007/s10710-023-09460-424:2Online publication date: 24-Oct-2023
https://dl.acm.org/doi/10.1007/s10710-023-09460-4
Wu BZhu LLi X(2023)Giza pyramids construction algorithm with gradient contour approach for multilevel thresholding color image segmentationApplied Intelligence10.1007/s10489-023-04512-953:18(21248-21267)Online publication date: 25-May-2023
https://dl.acm.org/doi/10.1007/s10489-023-04512-9
Shan YMa YLiao YHuang HWang B(2022)Interactive image segmentation based on multi-layer random forest classifiersMultimedia Tools and Applications10.1007/s11042-022-14199-882:15(22469-22495)Online publication date: 18-Nov-2022
https://dl.acm.org/doi/10.1007/s11042-022-14199-8
Naderi Boldaji MHosseini Semnani S(2022)Color image segmentation using multi-objective swarm optimizer and multi-level histogram thresholdingMultimedia Tools and Applications10.1007/s11042-022-12443-981:21(30647-30661)Online publication date: 1-Sep-2022
https://dl.acm.org/doi/10.1007/s11042-022-12443-9
Dalvand MFathi AKamran A(2022)Spiking Neural P System with weight model of majority voting technique for reliable interactive image segmentationNeural Computing and Applications10.1007/s00521-022-08162-935:12(9035-9051)Online publication date: 25-Dec-2022
https://dl.acm.org/doi/10.1007/s00521-022-08162-9
Zhang HZhi QYang F(2020)Minimum square distance thresholding method applying gray-gradient co-occurrence matrixInternational Journal of Knowledge-based and Intelligent Engineering Systems10.3233/KES-20004024:3(183-193)Online publication date: 1-Jan-2020
https://dl.acm.org/doi/10.3233/KES-200040
Khvostikov AKrylov AMikhailov IMalkov P(2020)CNN Assisted Hybrid Algorithm for Medical Images SegmentationProceedings of the 5th International Conference on Biomedical Signal and Image Processing10.1145/3417519.3417557(14-19)Online publication date: 21-Aug-2020
https://dl.acm.org/doi/10.1145/3417519.3417557

View Options

View options

Figures

Tables

Media

View Issue’s Table of Contents