Hong Li()Wen Wuand Enhua Wu

Robust interactive image segmentation via graph-based manifold ranking

Hong Li1(),Wen Wu1,and Enhua Wu1,2

Interactive image segmentation aims at classifying the image pixels into foreground and background classes given some foreground and background markers.In this paper,we propose a novel framework for interactive image segmentation that builds upon graph-based manifold ranking model,a graph-based semi-supervised learning technique which can learn very smooth functions with respect to the intrinsic structure revealed by the input data. The final segmentation results are improved by overcoming two core problems of graph construction in traditional models:graph structure and graph edge weights.The user provided scribbles are treated as the must-link and must-not-link constraints. Then we model the graph as an approximatively k-regular sparse graph by integrating these constraints and our extended neighboring spatial relationships into graph structure modeling. The content and labels driven locally adaptive kernel parameter is proposed to tackle the insufficiency of previous models which usually employ a uni fied kernel parameter.After the graph construction, a novel three-stage strategy is proposed to get the final segmentation results.Due to the sparsity and extended neighboring relationships of our constructed graph and usage of superpixels,our model can provide nearly real-time,user scribble insensitive segmentations which are two core demands in interactive image segmentation.Last but not least,our framework is very easy to be extended to multi-label segmentation, and forsome lesscomplicated scenarios,itcaneven get the segmented object through single line interaction. Experimental results and comparisons with other state-of-the-art methods demonstrate that our framework can efficiently and accurately extract foreground objects from background.

interactive image segmentation;graph structure;graph edge weights;manifold ranking;relevance inference

1 Introduction

Image segmentation,which is described as extracting meaningful partitions from an image,is one of the most fundamental,well-studied but challenging problems in image processing and computer vision. In general,image segmentation models can be divided into two groups:automatic and interactive segmentations.There are many models in each group and Hu et al.[1]presented a very comprehensive review.For automatic image segmentation approaches,which areknown as unsupervised models,they automatically classify the image pixels into coherent regions without any prior knowledge,such as mean shift[2,3],level sets[4-6],and graph based methods[7,8]. Although automatic image segmentation models have gained much success and been applied to many other algorithms,such as scene parsing[9],they are still far away from satisfaction;especially they have the problem of separating the whole object into di ff erent parts.On the other hand,interactive segmentation methods can accurately extract the whole object from the input image based on the user provided prior knowledge about the object and background. So in this paper,we only focus on interactive imagesegmentation models,in the sense that the users provide a partial labeling of the image.

Recently,interactive image segmentation methods havegained an extensivepopularity sincethe methods give users the ability to a ff ect the segmentation results as necessary for given applications. However, image segmentation is not easy because of many difficulties, such asnoise pollution,illumination variation,and background clutter,and so on.In the meanwhile, the segmentation results should also not be sensitive to the seed location and quantity in order to reduce the user e ff ort. To confront all these difficulties,many approaches have been proposed in the literature with impressive results.Popular approaches include graph-cut based methods[10-14],edge based methods[15-17],random walk based methods[18-20],and region based methods[21-23].

Almost all of these existing interactive segmentation systems provide users with an iterative procedure to add or remove scribbles to temporary results until they get the final satisfactory segmentation result.However,they can only get high-precision segmentation results at the cost of high computational complexity or many carefully placed seeds.Obviously,these two disadvantages make their models impractical because the users usually requirethesystem to respond quickly and update the corresponding result immediately for further re fi nement. In another word,the system should have an acceptable computational complexity, even real-time performance, of interactive segmentation algorithms.

In order to overcome these shortcomings,we propose a robust interactive image segmentation system that builds upon graph-based semisupervised learning theory and superpixels.Figure 1 illustrates the framework of our proposed model. The input image is firstly over-segmented into small homogeneous regions and the user provided scribbles are integrated with superpixels.Then we model the approximately k-regular sparse graph and form the affinity graph matrix using proposed labels driven and locally adaptive kernel parameter. The final segmentation is generated by a three-stage strategy.

Contributions. The key contributions of this work are:

Fig.1 The framework of our proposed interactive image segmentation.

1.A novel framework that combines the graphbased semi-supervised learning theory with region based models to efficiently segment out the desired object(s)accurately. It can be easily extended to multi-label segmentation and single-line cutout problems.

2. A novel graph construction strategy which models the graph as an approximately k-regular sparse graph by integrating spatial relationships and user provided scribbles.

3.A new graph edge weights computing strategy which forms the weights using a locally adaptive kernel width parameter.

The rest of the paper is organized as follows. First,related works are summarized in Section 2. In Section 3,we first introduce the basic concept of graph-based manifold ranking in Section 3.1 and then give the details of our three-stage interactive imagesegmentation framework in Section 3.2. Experimental results and analysis are given in Section 4.Finally,conclusions and future work are given in Section 5.

2 Related work

Related works fall into two categories:segmentationbased on graph theory and region operations.We address each of them in turn.

Graph based segmentation models can be roughly divided into two subgroups: graph-cutbased models and random walk based models.Boykov and Jolly[10]propose the first interactive graphcut model. The user provided foreground and background seeds are treated as source and sink nodes in graph respectively and the segmentation is performed by the min-cut/max- fl ow algorithm. It has been very popular because of its strong mathematical foundation provided by the maximum a posterior-Markov random field (MAP-MRF) framework[24].Rother et al.[11]propose an iterated graph-cut algorithm named GrabCut.It uses a Gaussian mixture model(GMM)to model the pixel colors’distribution and alternates between object estimation and GMM parameter estimation iteratively.GrabCut needs less user interaction by only requiring a rectangle or lasso around an object (not detailed foreground and background seeds).Li et al.[12]also propose an improved (both in speed and accuracy)interactive graph-cut algorithm named Lazy Snapping.They adopt superpixels to construct the graph to reduce the computational cost.It also supports boundary editing to achieve pixel-level accuracy. All these graph-cut based methods sometimes have the problem of shortcutting and itisusually caused by a lower cost along a shorter cut than that of a real boundary.To overcome this problem,Price et al.[13] propose a geodesic graph-cut method which takes geodesic distance(instead of Euclidean distance)into account.It outperforms previous graph-cut based methods when user provided information separates the background and foreground feature distributions e ff ectively.

Random walk based methods classify an unlabeled pixel via resolving a question:if a random walker starts from one location,what is the most probable seed destination? Grady[18]regards the image segmentation as random walk on a graph and demonstrates that the method is more robust to noise,weak boundary detection,and ambiguous region segmentation.However,it is very sensitive to the seeded points.Kim et al.[19]propose a generative image segmentation algorithm by utilizing random walk with restart(RWR)which gives the walker two choices:randomly move to one of its neighbors with probabilitycor jump back to its initial seed point and restart with probability 1?c.RWR algorithm can segment images with weak boundaries and textures more e ff ectively,but its computational cost is very high because it demands large matrix inversion.

Region based methods can be categorized into two subgroups:region growing,region splitting and merging.Adams and Bischof[21]propose a fast and easily implemented method based on region growing. It iteratively adds pixels in subregions neartheforeground orbackground subregions to the active set and updates the seeds until all pixels in the image are assigned to a label. It generates unsatisfactory results when foreground and background have close color distribution. Both maximalsimilarity-based region merging (MSRM)[22]and matingattributed relational graph(MARG)[23]begin with superpixels(the input image is divided into small homogenous regions).MSRM iteratively merges a region into a neighboring region which has the most similar color histogram and updates the histogram of newly merged region until there is no region to be merged. It has high overall computational complexity because it needs computing the histogram similarity in each iteration.MARG constructs two graphs:the input graph,which represents the input superpixels image;and the model graph,which is constructed by the labeled superpixels.Then the region merging is performed by matching these two graphs.This method needs many labeled pixels which is not impractical.

3 Robust interactive image segmentation via graph-based manifold ranking

In this section,we first brie fl y introduce the graphbased manifold ranking in Section 3.1,then present the details of our proposed three-stage interactive image segmentation framework in Section 3.2.

3.1 Graph-based manifold ranking

Graph-based semi-supervised models usually consist of two main parts:graph modeling and information inference.Given a set ofndata pointsX={x1,x2,···,xq,···,xn},with each dataxi∈Rm, the firstqpoints{x1,x2,···,xq}are labeled as the queries and the rest points{xq+1,···,xn}are unlabeled.The ranking algorithm aims to rank the remaining points according to their relevances to the labeled queries.Letf:X→Rndenotes a ranking function which assigns to each data pointxia ranking valuefi.We can treatfas a vectorf= [f1,f2,···,fn]T.We can also de fi ne an indication vectory=[y1,y2,···,yn]T,in whichyi=1 ifxiis a query,andyi=0 otherwise.

Next,we de fi ne a graphG=(V,E)on these data points,where the nodesVare datasetXand the edgesEare weighted by an affinity matrixW=[wij]n×n.Wis often obtained by applying the Gaussian kernel to a distance matrix:

According to Zhou et al.[25,26],cost function associated with the ranking functionfis de fi ned to be

where the regularization parameterμ＞0 controls the balance of the first term(smoothness constraint) and the second term( fi tting constraint,containing labeled as well as unlabeled data.).The first term means that nearby points should have similar scores. Then the optimal rankingf?of queries is computed by solving the following optimization problem:

The solution of Eq.(3)can be denoted as

3.2 Segmentation via graph-based manifold ranking

Above mentioned graph-based semi-supervised learning algorithm indicates that our interactive image segmentation framework should consist of two main parts:graph construction and information inference.In Section 3.2.1,we present our labels driven and locally adaptive graph construction. And in Section 3.2.2,we present our three-stage interactive image segmentation procedure.

3.2.1Labels driven andlocallyadaptive graph construction

To better exploit the intrinsic relationship between data points,there are two aspects should be carefully treated in graph construction:graph structure and edge weights.We over-segment input image into small homogeneous regions using work[27]instead of popular simple linear iterative clustering(SLIC) model[28]because superpixels generated by work [27]have better boundary fi tness than that of work [28].Then we regard each superpixel as a node in the graphG.

For graph structure,we take the local smoothness cue(i.e.,local neighboring superpixels are more likely to belong to the same object)into account and follow three rules.Firstly,each node is not only connected with its direct adjacent neighboring nodes,but also is connected with those nodes sharing common boundaries with its neighboring nodes. Secondly,the nodes labeled as foreground should be connected and the nodes labeled as background should also be connected.Thirdly,the labeled foreground and background nodes should not be connected.First rule models the graph as a k-regular structure by extended neighboring relationships and makes sure the graph structure being sparse.The rest two rules integrate the user provided information into graph construction and destroy the k-regularity by treating the user provided scribbles as mustlink and must-not-link constraints. However,the user provided constraints are much less than total amount of nodes and this makes the graph structure approximately k-regular.

After modeling the graph structure,the very core problem is to get the edge weight between any pairwise nodes given input data. Most models utilizetheL2 distancebased Gaussian kernel (See Eq.(1)for example)to de fi ne edge weights. However,choosing the optimal Gaussian kernel width parameter is very challenging. Figure 2 illustrates the segmentation sensitivity with respect to the uni fied kernel width. It can be seen that the kernel width will dramatically in fl uence the finalsegmentation result and fi nding the optimalσis usually very hard and time consuming.So in this work,we propose a locally adaptive kernel parameter based edge weight formation strategy,which can be de fi ned as follows:

Fig.2 Sensitivity of kernel width.(a)Input image with labels. (b)Segmentation result withσ=0.1.(c)Segmentation result withσ=5.(d)Segmentation result withσ=10.

whered(i,j)denotes theL2 distance between superpixel regioniandjand is de fi ned as

ciandcjdenote the mean of regioniandjrespectively inLabcolor space.

Itcan alsobeseen from Eq.(5)thatwe adopt a content adaptive kernel width instead of a uni fied one. The reason for this adaption is straightforward:a good choice ofσshould pull intraclass objects together and push extra-class objects apart simultaneously.Di ff erent images have di ff erent feature representations and using a globally uni fiedσwill not achieve this goal in most time.So we de fi ne our local content adaptive kernel width as

here?denotes the median operation.N(i)denotes neighboring nodes of superpixeli(all the nodes that have connections with nodei).

Our constructed graph takes spatial relationship, user provided information,and image content into account.It can exploit the intrinsic structure of input data more properly.Algorithm 1 shows our labels driven and locally adaptive graph construction.

Algorithm 1: Labels driven and locally adaptive graph construction

Input:Input image and corresponding superpixles

1: Construct the k-regular graph by extended neighboring relationships.

2:Modify the graph edge connections with mustlink and must-not-link constraints.

3:Compute the distance matrix usingL2 distance (Eq.(6)).

4:Form the affinity matrix by Eq.(5)using locally adaptive kernel width.

Output:Affinity matrix.

3.2.2Three-stage interactive segmentation

In this section,we present the details of our threestage strategy for interactive image segmentation with foreground labels and background labels.

Learning with foreground labels. We use the user labeled foreground seeds as queries and other nodes as unlabeled data.By this setting,we get the indicator vectory.The ranking scores are learned using Eq.(4).These ranking scores form anNdimensional vector,in whichNstands for the number of superpixels(also is the total number of nodes of the graph).Every element in this vector gives the similarity of corresponding node to the foreground queries.Final foreground labels based ranking scores are de fi ned as

whereiis the superpixel index andis the normalizedf?(in the range of[0,1]).

Learning with background labels. In this stage,we form the indicator vectoryby treating the user labeled background seeds as background queries. Then the ranking scores are computed according to Eq.(4)and are normalized into[0,1].Final background labels based ranking scores are de fi ned as

whereiandare de fi ned in the same way as in Eq. (8).Note thatare the ranking scores according to background queries,so we subtract them from one to get the corresponding foreground based scores.

Integration.When we get the foreground and background ranking scores,the next stage is to integrate them.In this work,we adopt a very simple strategy de fi ned as

where.?stands for pixel-wise product,RSfandRSbare de fi ned in Eq.(8)and Eq.(9)respectively,Mdenotes mean based thresholding operation de fi ned by

hereμis the mean value of{f1,f2,···,fN}.

Figure 3 shows an example of our three-stage interactiveimage segmentation algorithm.The detailed procedure can be found in Algorithm 2.

Algorithm 2: Efficient interactive image segmentation

Input:Input image and user scribbles

1:Construct the graph as stated in Section 3.2.1.

2:Form the foreground and background indicator vectors respectively according to user scribbles.

3:Get the ranking scores by Eq.(8)and Eq.(9) using corredponding indicatory.

4:Integrate the ranking scores and get the final segments using Eq.(10).

Output:Final segments.

4 Experiments and analysis

In order to show the advantages over previous algorithms,we conduct qualitative and quantitative evaluation on the GrabCut dataset[11]and some real natural images. Firstly,we will analyze the segmentation results with di ff erent user scribbles, i.e.,sensitivity of user scribbles.Then,we show the fl exibility of our framework by extending it to multilabel segmentation and single-line cutout problems. Thirdly,we show the segmentation comparisons of applying our method and other four methods: RWR[19],GCPP[29],NHL[30],and CAC[17]on some representative images.Finally,we report the running time of these models.

Fig.3 Three-stage interactive segmentation. (a)Input image with labels.(b)Segmentation result.(c)Learning with background labels.(d)Learning with foreground labels.

The experimental results of RWR[19],NHL [30],and CAC[17]are all generated by directly using the implementation from the authors.The segmentations of GCPP[29]are generated using ourimplementation and itisa morerecent graph-cut based segmentation framework with post processing output of BJ[10]to remove disconnected foreground islands.To make the comparison more fair and reliable,we keep all the default parameters unchanged and use the same user scribbles.The number of superpixels is set to beN=500 in all the experiments. There is one parameter left in our model:the balance weightαin Eq.(4).It balances the smooth and fi tting constraints in theregularization.Wesetα= 0.99 forall the experiments to put more emphasis on the label consistency like previous graph-based semisupervised learning models usually did. We use green scribbles and blue scribbles to indicate the foreground and background regions respectively in all our experiments except in multi-label segmentation where we use di ff erent labels.

4.1 Comparison of scribble sensitivity

Through extensive experiments we fi nd that the user scribbles play a very important role in the interactive image segmentation models,i.e.,thelocations and quantity of seeds will drastically a ff ect the segmentation results. So a good interactive segmentation model should be insensitive to the locations and quantity of user scribbles. We demonstrate the user scribble insensitivity of our method in Fig.4.We use less scribbles in bottom row and the scribbles are also placed in di ff erent locations in Fig.4(a).The corresponding segmentation results of RWR[19],GCPP[29],NHL[30],and CAC[17]are shown in Figs.4(b)-4(e)respectively.Segmentation results of our method are shown in Fig.4(f).It can be seen that our method can get almost unchanged best segmentation results given user scribbles of di ff erent locations and quantities.Thus our method can generate more stable and satisfying segmentation results that are not sensitive to the locations and quantity of user scribbles.

4.2 Multi-label segmentation and single-line cutout

Because we integrate the user scribbles into graph construction and also take spatial relationships into account,our proposed model can be easily extended to the multi-label and single-label segmentation problems in a straightforward manner as illustrated in Fig.5 and Fig.6 respectively.

For multi-label segmentation, we use corresponding colorsto mask di ff erent regions according to the user provided di ff erent labels.Take top row in Fig.5 for example,the left dog and right dog are segmented as red and green regions respectively according to the labels while the rest is treated as background and is labeled as blue just as the label indicated.It can be seen that our method can generate highly accurate segmentations,even in the presence of multiple objects with similar color.

Fig.4 User scribble sensitivity comparison.(a)Input images with di ff erent user scribbles. (b)Results by RWR[19]. (c) Results by GCPP[29].(d)Results by NHL[30].(e)Results by CAC[17].(f)Our results.

Fig.5 Multi-label segmentation.(a)Input images with multilabels.(b)Corresponding segmentation results.

Fig.6 Single-line cutout.Top row:Input images with singleline label(only foreground labels).Bottom row:Corresponding segmentation results.

For single-label segmentation problem,which we refer as single-line cutout,it just uses the foreground label to segment out the desired object.As shown in Fig.6,it can get satisfying segmentation results using only single-line interaction.This will de fi nitely make the segmentation problem more convenient and interesting.

4.3 Qualitative and quantitative comparison

In Fig.7,the segmentations are produced by fi ve algorithms including RWR[19],GCPP[29],NHL [30],CAC[17],and ours.It shows the qualitative and quantitative comparison of these fi ve di ff erent algorithms.

For qualitative comparison,we use the same user scribbles and corresponding optimal parameters to generate the segmentation results.Then for each segmention,we form its boundary map and integrateit into input image to visualize the performance of segmentation. Figures 8 and 9 give the fair comparisons of more complicated images from the GrubCut dataset[11].

Fig.7 Comparison of our model with other models.(a)Input images with labels.(b)Results by RWR[19].(c)Results by GCPP [29].(d)Results by NHL[30].(e)Results by CAC[17].(f)Our results.

For quantitative comparison, we use the normalized overlapβo[31]to measure the similarity between the segmentation result and the preset ground truth quantitatively.It is de fi ned as

Fig.8 Comparison of our model with other models.(a)Input images with labels.(b)Results by RWR[19].(c)Results by GCPP [29].(d)Results by NHL[30].(e)Results by CAC[17].(f)Our results.

whereSfis the assigned foreground pixels of the segmentation result andGfis that of ground truth. This value is presented below each segmentation result.

As can be seen,RWR[19]and GCPP[29]can generally generate satisfactory segmentation results. However,RWR[19]can only get good segmentation results when there are enough user scribbles to surround the desired object.This requirement makes their method inapplicable because it needs more user scribbles.For GCPP[29],it will produce isolated regions(even dots)in bigger foreground regions as shown in the fourth and last rows of the third column. CAC[17]will segment out background regions when the background and foreground have similar colors. NHL [30]has the problem of producingisolated regionsand segmenting out background regions when the corresponding regions have no scribbles.On the other hand,our model consistently outperforms all other models.It has the highestβovalue which indicates that the segmentation resultsaremoreconsistentwith ground truth.Meanwhile,the segmentation results of our model have high boundary fi tness.

Fig.9 Comparison of our model with other models.(a)Input images with labels.(b)Results by RWR[19].(c)Results by GCPP [29].(d)Results by NHL[30].(e)Results by CAC[17].(f)Our results.

4.4 Running time

Another very important factor which will in fl uence the level of segmentation satisfaction dramatically is the computational cost.The processing should be very fast in order to let the users modify the segmentation results in a real-time fashion.We conduct experiments on some representative images and report the mean running time of each model.Allthe experiments are carried out on a PC with an Intel Core i7 3.2 GHz processor and 16 GB of RAM.Table 1 illustrates the running time of di ff erent models for segmentations on images with size of 640×480.

We can see from Table 1 that NHL[30]needs the most time;it takes about fi fty seconds to process an image.The rest four models including ours need almost the same time to proceed.It’s worth mentioning that our unoptimized MATLAB code only needs less than 2 seconds including oversegmentation computation time to segment the input image.The running time of our model can be sharply reduced by standard multi-core methods due to the sparsity of our model in C++implementation and it can provide real-time performance.This will be one of our next works.We will make all the resources including source code,dataset,and evaluation code publicly available after this paper been published.

5 Conclusions and further work

In this paper,we have proposed a novel framework for interactive image segmentation,which generates accurate segmentation results with very fast respond to users’interactions.The core of this technique is a graph-based semi-supervised learning framework to rank similarities of unlabeled data points with respect to the labeled ones by exploiting the global and local consistency of all the data.

To better exploit the intrinsic structure of data, we firstly model the graph as a k-regular graph to take spatial relationships into account. Then we further enhance the graph structure by integrating user provided scribbles and finally model the graph as an approximately k-regular sparse graph. To overcome the instability brought by the sensitivity of hyper-parameter,we propose a content based locally adaptive kernel width parameter to form the graph edge weights. A three-stage strategy is employed to generate the final segmentationresults.Our framework can also be easily extended to multi-label segmentation and single-line cutout problems. Extensive experiments show that our model consistently outperforms other models both qualitatively and quantitatively.Last but not least, our framework has the least computational cost compared with other four models due to the sparsity of our constructed graph and usage of superpixels.

Table 1 Running time of di ff erent models

As future work, we consider two possible directions: multi-features, multi-scale and optimization.We only use color feature for now. There are other features that can be integrated into this framework to better di ff erentiate di ff erent regions,such as texture and edge.We employ superpixelsasourbasicprocessing unit.The incorrect over-segmentation will a ff ect the final segmentation result. This disadvantage can be overcome e ff ectively by utilizing the multiscale technique.Wewillfurtheroptimizethe framework and consider parallelism to speed up the segmentation procedure.

Acknowledgements

The authors would like to thank the anonymous reviewers for their valued suggestions which helped a lot to improve the manuscript.This work has been supported by NSFC(National Natural Science Foundation of China,No.61272326),the research grant of University of Macau(No.MYRG202(Y1-L4)-FST11-WEH),and the research grantof University of Macau(No.MYRG2014-00139-FST).

Open Access This article is distributed under the terms of the Creative Commons Attribution License which permits any use,distribution,and reproduction in any medium,provided the original author(s)and the source are credited.

[1]Hu,S.-M.;Chen,T.;Xu,K.;Cheng,M.-M.;Martin, R.R.Internet visual media processing:A survey with graphics and vision applications.The Visual ComputerVol.29,No.5,393-405,2013.

[2]Comaniciu,D.;Meer,P.Mean shift: A robust approach toward feature space analysis.IEEE TransactionsonPatternAnalysisandMachine IntelligenceVol.24,No.5,603-619,2002.

[3]Xiao,C.;Liu,M.Efficient mean-shift clustering usingGaussian KD-tree.Computer Graphics ForumVol.29, No.7,2065-2073,2010.

[4]Vese,L.A.;Chan,T.F.A multiphase level set framework for image segmentation using the Mumford and Shah model.International Journal of Computer VisionVol.50,No.3,271-293,2002.

[5]Li,C.;Xu,C.;Gui,C.;Fox,M.D.Distance regularized level set evolution and its application to image segmentation.IEEE Transactions on Image ProcessingVol.19,No.12,3243-3254,2010.

[6]Liu,Y.;Yu,Y.Interactive image segmentation based on level sets of probabilities.IEEE Transactions on Visualization and Computer GraphicsVol.18,No.2, 202-213,2012.

[7]Shi,J.; Malik,J.Normalized cutsand image segmentation.IEEE Transactions on Pattern Analysis and Machine IntelligenceVol.22,No.8,888-905, 2000.

[8]Huang,H.;Zhang,L.;Zhang,H.-C.RepSnapping: Efficient image cutout for repeated scene elements.Computer Graphics ForumVol.30,No.7,2059-2066, 2011.

[9]Eigen,D.;Fergus,R.Nonparametric image parsing using adaptive neighbor sets.In:Proceedings of 2012 IEEE Conference on Computer Vision and Pattern Recognition,2799-2806,2012.

[10]Boykov,Y.Y.;Jolly,M.-P.Interactive graph cuts for optimal boundary®ion segmentation of objects in N-D images.In:Proceedings of the Eighth IEEE International Conference on Computer Vision,Vol.1, 105-112,2001.

[11]Rother,C.;Kolmogorov,V.;Blake,A.“GrabCut”: Interactive foreground extraction using iterated graph cuts.ACM Transactions on GraphicsVol.23,No.3, 309-314,2004.

[12]Li,Y.;Sun,J.;Tang,C.-K.;Shum,H.-Y.Lazy snapping.ACM Transactions on GraphicsVol.23,No. 3,303-308,2004.

[13]Price,B.L.;Morse,B.;Cohen,S.Geodesic graph cut for interactive image segmentation.In:Proceedings of the 2010 IEEE Conference on Computer Vision and Pattern Recognition,3161-3168,2010.

[14]Gulshan,V.;Rother,C.;Criminisi,A.;Blake,A.; Zisserman,A.Geodesic star convexity for interactive image segmentation.In: Proceedings of the 2010 IEEE Conference on Computer Vision and Pattern Recognition,3129-3136,2010.

[15]Mortensen,E.N.;Barrett,W.A.Intelligent scissors forimagecomposition.In: Proceedingsofthe 22nd Annual Conference on Computer Graphics and Interactive Techniques,191-198,1995.

[16]Sundaramoorthi,G.; Yezzi,A.; Mennucci,A. C.Coarse-to- fi ne segmentation and tracking using Sobolev active contours.IEEETransactionson Pattern Analysis and Machine IntelligenceVol.30,No. 5,851-864,2008.

[17]Nguyen,T.N.A.N.;Cai,J.;Zhang,J.;Zheng, J.Robustinteractiveimage segmentation using convex active contours.IEEE Transactions on Image ProcessingVol.21,No.8,3734-3743,2012.

[18]Grady,L.Random walks for image segmentation.IEEE Transactions on Pattern Analysis and Machine IntelligenceVol.28,No.11,1768-1783,2006.

[19]Kim,T.H.;Lee,K.M.;Lee,S.U.Generative image segmentation using random walks with restart.In:Lecture Notes in Computer Science,Vol.5304.Berlin Heidelberg:Springer,264-275,2008.

[20]Yang,W.;Cai,J.;Zheng,J.;Luo,J.Userfriendly interactive image segmentation through uni fied combinatorial user inputs.IEEE Transactions on Image ProcessingVol.19,No.9,2470-2479,2010.

[21]Adams,R.;Bischof,L.Seeded region growing.IEEE Transactions on Pattern Analysis and Machine IntelligenceVol.16,No.6,641-647,1994.

[22]Ning,J.;Zhang,L.;Zhang,D.;Wu,C.Interactive image segmentation by maximal similarity based region merging.Pattern RecognitionVol.43,No.2, 445-456,2010.

[23]Noma, A.; Graciano, A.B.V.; Cesar Jr., R.M.;Consularo,L.A.;Bloch,I.Interactive image segmentation by matching attributed relational graphs.Pattern RecognitionVol.45,No.3,1159-1179, 2012.

[24]Greig,D.M.;Porteous,B.T.;Seheult,A.H.Exact maximum a posteriori estimation for binary images.Journal of the Royal Statistical Society.Series B (Methodological)Vol.51,No.2,271-279,1989.

[25]Zhou,D.;Bousquet,O.;Lal,T.N.;Weston, J.;Sch¨olkopf,B.Learning with local and global consistency.In:Proceedings of Advances in Neural Information Processing Systems,321-328,2003.

[26]Zhou,D.;Weston,J.;Gretton,A.;Bousquest, O.; Sch¨olkopf,B.Ranking on data manifolds. In: Proceedings of Advances in Neural Information Processing Systems,2004.Available at http://papers.nips.cc/paper/2447-ranking-ondata-manifolds.pdf.

[27]Shen,J.;Du,Y.;Wang,W.;Li,X.Lazy random walks for superpixel segmentation.IEEE Transactions on Image ProcessingVol.23,No.4,1451-1462,2014.

[28]Achanta,R.;Shaji,A.;Smith,K.;Lucchi,A.;Fua, P.;Susstrunk,S.SLIC superpixels compared to stateof-the-art superpixel methods.IEEE Transactions on Pattern Analysis and Machine IntelligenceVol.34, No.11,2274-2282,2012.

[29]Liu,J.Y.;Sun,J.;Shum,H.Y.Paint selection.In: Proceedings of ACM SIGGRAPH 2009 papers,Article No.69,2009.

[30]Kim,T.H.;Lee,K.M.;Lee,S.U.Nonparametric higher-order learning for interactive segmentation.In: Proceedings of 2010 IEEE Conference on Computer Vision and Pattern Recognition,3201-3208,2010.[31]Sinop,A.K.;Grady,L.A seeded image segmentation framework unifying graph cuts and randomwalker which yields a new algorithm.In:Proceedings of IEEE 11th International Conference on Computer Vision,1-8,2007.

Hong Li is currently a third-year Ph.D.candidate at Macau University (Macao,China),Computer Graphics Laboratory. His researches focus on image processing, semi-supervised learning, computer vision, and so on.

Wen Wu received her Ph.D.degree in computer science and engineering from The Chinese University of Hong Kong. She is currently an assistant professor in Department of Computer and Information Science at University of Macau.Her research interests include medical simulation,virtual reality,and physically-based animation.

Enhua Wu is a professor of the State Key Laboratory of Computer Science at the Chinese Academy of Sciences Institute of Software and the University of Macau. His interests include VR, realistic-image synthesis, and data visualization. He received his Ph.D. in computer science from University of Manchester.

Other papers from this open access journal are available free of charge from http://www.springer.com/journal/41095. To submit a manuscript,please go to https://www. editorialmanager.com/cvmj.

1Department of Computer and Information Science, UniversityofMacau,Macau999078,China. E-mail: H.Li,valhongli@gmail.com;W.Wu, wenwu@umac.mo.

2Chinese Academy of Sciences,Beijing 100000,China.E-mail:ehwu@umac.mo.

Manuscript received:2015-08-11;accepted:2015-09-15