۱- Introduction

۲- Model description

۳- Computer simulations

۴- Computational time and storage complexity

۵- Benchmark

۶- Conclusions

References

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.

Introduction

Image segmentation is the process of dividing an image in parts, identifying objects or other relevant information (Shapiro & Stockman, 2001). It is one of the most difficult tasks in image processing (Gonzalez & Woods, 2008). Fully automatic segmentation is still very challenging and difficult to accomplish. Many automatic approaches are domain-dependant, usually applied in the medical field (Avendi, Kheradvar, & Jafarkhani, 2016; Bozkurt, Kse, & Sar, 2018; Christ et al., 2016; Martinez-Muoz, Ruiz-Fernandez, & Galiana-Merino, 2016; Moeskops et al., 2016; Patino-Correa, Pogrebnyak, Martinez-Castro, & Felipe-Riveron, 2014). Therefore interactive image segmentation, in which a user supplies some information regarding the objects of interest, is experiencing increasing interest in the last decades (Artan, 2011; Blake, Rother, Brown, Perez, & Torr, 2004; Boykov & Jolly, 2001; Breve, Quiles, & Zhao, 2015a,b; Ding & Yilmaz, 2010; Ding, Yilmaz, & Yan, 2012; Dong, Shen, Shao, & Gool, 2016; Ducournau & Bretto, 2014; Grady, 2006; Li, Bioucas-Dias, & Plaza, 2010; Liew, Wei, Xiong, Ong, & Feng, 2017; Lin, Dai, Jia, He, & Sun, 2016; Oh, Ham, & Sohn, 2017; Price, Morse, & Cohen, 2010; Rother, Kolmogorov, & Blake, 2004; Wang, Zuluaga et al., 2018; Wang, Ji et al., 2018; Wang, Ji, Sun, Chen, & Jing, 2016; Wang, Sun, Ji, Chen, & Fu, 2016).