Iterated shape-bias graph cut with application to ellipse segmentation

Abstract

We present a novel graph cut method for iterated segmentation of objects with specific shape bias (SBGC). In contrast with conventional graph cut models which emphasize the regional appearance only, the proposed SBGC takes the shape preference of the interested object into account to drive the segmentation. Therefore, the SBGC can ensure a more accurate convergence to the interested object even in complicated conditions where the appearance cues are inadequate for object/background discrimination. In particular, we firstly evaluate the segmentation by simultaneously considering its global shape and local edge consistencies with the object shape priors. Then these two cues are formulated into a graph cut framework to seek the optimal segmentation that maximizing both of the global and local measurements. By iteratively implementing the optimization, the proposed SBGC can achieve joint estimation of the optimal segmentation and the most likely object shape encoded by the shape priors, and eventually converge to the candidate result with maximum consistency between these two estimations. Finally, we take the ellipse shape objects with various segmentation challenges as examples for evaluation. Competitive results compared with state-of-the-art methods validate the effectiveness of the technique.

Keywords

graph cut shape elliptical pattern

1 Introduction

Segmentation of natural images is one of the most fundamental and well-studied problems in computer vision. Among the wide variety of approaches, foreground-background segmentation which refers to the task of extracting the object of interest out of the cluttered background is becoming increasingly popular. Since this kind of segmentation is a strictly ambiguous problem, most approaches rely on additional user guidance or some prior information regarding the region of interest.

Seed segmentation and graph cut. As the goal is to minimize as much as possible the user effort, many methods allow the user to loosely mark segmentation regions rather than more finely trace near object boundaries [15, 18]. Such approaches are popular because they generally require less precise input from the user. The user can seed the segmentation by arbitrarily clicking or drawing rough scribbles on parts of the desired foreground and background regions, Fig. 1(a). The most popular approach to seeded segmentation is currently the graph cut approach of [2], with numerous proposed variations [4 , 28]. This method treat the foreground-background segmentation problem as a binary labeling problem of minimizing a cost function. The cost function combines explicit edge-finding and region-modeling components. These two cues are formulated as a weighted combination and optimized by computing a weighted graph’s minimum cut that partitions foreground seeds from background seeds. Generally, the foreground/background distributions encoded in the region term are inferred from the respective seed pixels, then serve to one graph cut computation to obtain the optimal solution of the segmentation label. However, because the distributions are fixed throughout the whole segmenting procedure and the one shut segmentation has no capability to feedback the segmentation result to adjust the distribution accordingly. In situations where the given distribution is not reliable, such as the interactive segmentation interface from a user-defined bounding box [12, 19], Fig. 1(a), this one graph cut calculation cannot guarantee a good solution.

Fig. 1

Adequacy of the shape-bias graph cut in complex scene. (a) shows the initializations of each method: the 50 red and 50 blue points are the input seeds for standard graph cut [2]; the red bounding box is for grab cut [19]; the green curve obtained by inputting two seeds (the big green one for object and yellow one for background) to standard graph cut is for the proposed SBGC.

Iterative segmentation. Many researchers seek approaches to jointly optimize segmentation and object/background models in graph cut framework [19, 26]. An iterative version of the optimization is developed in [19], where the GMM model is used for appearance representation and is refined simultaneously with the segmentation iterations. In [10], the supervised learning based on the multilayer perceptron is used to identify initial seeds with high confidences to be hard exudates. Then the segmentation is finalized by unsupervised learning based on the iterative graph cut using clusters of initial seeds. However, similar as the typical graph cut, they are based on pixelwise model that evaluates each pixel individually. Because the optimization does not consider the global consistency of the segmentation data, these methods are subject to several disadvantages, such as the well-known bias towards shorter paths.

Global appearance constraint. In contrast with the pixel-wise model, introducing global measure can help to seize the global properties of the segmentation data. In [20], the authors formulated the appearance consistency by using L1 norm of the difference between histograms to find an image region consistent with a reference histogram. In [5], the authors present a graph cut based method for automated aorta segmentation. A discriminative integrated feature (DIF) and a novel adaptive smoothness constraint are designed. In [1], a global constraint based on the Bhattacharyya measure is used. The authors introduced an auxiliary labeling method to estimate the upper bound of the constraint term and performed optimization of an auxiliary function with graph cut. In [16], the authors proposed an approach for image segmentation from an inexact reference distribution in which the given reference distribution plays a guiding role to infer the latent distribution and its consistent region, relaxing the strict requirement on distribution precise in [1]. However, all of them consider the problem in appearance view and few takes the shape consistency into account, which is competent especially in class-specific object segmentation applications or in complex scene where the appearance properties are inadequate for object/background representation/discrimination, as Fig. 1.

Shape prior segmentation. There are several algorithms that employ graph cuts for shape prior segmentation. In [6], the authors use the shape’s distance transform to define the edge weight between neighboring pixels. In [24], the authors imposes a constraint on the shape of the object to be a star. The user input for this algorithm is critical as it requires the user to specify the center of the star shape exactly in the image. In [27], the authors propose a fully convolutional network architecture for shapes, denoted by Shape Fully Convolutional Networks (SFCN). 3D shapes are represented as graph structures in the SFCN architecture, based on graph convolution and pooling operations. In [23], the authors constrain the optimization within a narrow band of a predefined ellipse, where the shape prior term is defined by a binary image mask and jointly with the color cue to define the region-cost of the graph. However, none of them explores the shape priors in both the global and local view, which is critical for ensuring an optimal result that maximizes the global shape consistency and simultaneously pass through the exact target boundary.

Contribution. In this paper, we present a novel graph cut method for iterated segmentation by introducing the shape preference of the interested object. Under the guidance of the specific shape priors, the SBGC can ensure a more accurate convergence to the interested object and effectively make up for the appearance inadequacy in complicated conditions. Specifically, we evaluate the segmentation by simultaneously measuring its global shape and local edge consistencies with the object shape priors. Then these two cues are formulated into the graph cut framework to drive the optimization and seek the segmentation that maximizing both of these global and local measurements. By iteratively implementing the optimization, the proposed SBGC can achieve joint estimation of the optimal segmentation and the most likely object shape encoded by the shape priors, and eventually converge to the candidate result with maximum consistency between these two estimations. Ellipse shape objects with various segmentation challenges as well as state-of-the-art methods are invited for evaluation and comparison, which validate the effectiveness of the technique.

2 Graph cut segmentation framework

Graph cut segmentation [2] seeks a global optimum among all segmentations by minimizing a cost function that incorporates the constraints imposed on boundary and region properties of segments: $E (L) = R (L) + λ \cdot B (L)$ (1) where $L = (L_{1}, \dots, L_{i}, \dots, L_{| P |})$ is a binary vector of labels defining a segmentation, P is the set of pixels in the image, and $L_{i}$ labels $F$ (Foreground) or $B$ (Background) for pixel x_i. $R (L)$ is a region-cost term over the whole pixel set P while B (x_i, x_j) is a boundary-cost term over set N, the set of pairs of neighboring pixels. $R (L) = \sum_{x_{i} \in P} R_{L_{i}} (x_{i})$ (2) $B (L) = \sum_{(x_{i}, x_{j}) \in N} B (x_{i}, x_{j}) | L_{i} - L_{j} |$ (3) $R_{L_{i}} (x_{i})$ defines the individual penalties for assigning pixel x_i to label $L_{i}$ , i.e. $F$ / $B$ . $| L_{i} - L_{j} |$ indicates a discontinuity between x_i and x_j, and coefficient B (x_i, x_j) ≥0 is for penalty. Finally, the coefficient λ ≥ 0 in (1) specifies a relative importance of the region properties term $R (L)$ versus the boundary properties term $B (L)$ .

The terms R and B have been defined in various ways by different researchers. Generally R is based on color models of the foreground and background, and B corresponds to a measure of the similarity between the colors of adjacent pixels. Then graph cut methods minimize (1) by casting the problem as a graph-partitioning one and using the mincut/maxflow graph algorithm, where boundary costs B are assigned to graph edges between pixel nodes and region costs R are assigned to edges connecting pixel nodes to the source and sink terminals.

Graph cut methods perform well over a variety of images [3, 25]. Because both region and boundary information are explicitly captured in the algorithm, they are capable of both selecting objects consistent with region information and placing object boundaries on image edges. Many variations have sought to improve on this approach, including using watershed regions as primitives in order to reduce the size of the graph and accelerate the computation [13], jointly optimizing segmentation and appearance models [26], using patch-based representation to detects repetitive pattern and yields a parameterless hierarchical segmentation [7], and using a curvature-minimizing rather than length-minimizing regularization term to avoid short cutting [21]. However, all of them measure the consistency of the segmentation data by appearance statistics and few consider to explore the global shape information to drive the segmentation and make up for the inadequacy of the appearance cues in complicated scene.

3 Iterated shape-bias graph cut

In this section, we explored the object shape priors and present the proposed shape-bias graph cut in detail, which is competent for class-specific object segmentation problem, especially when the appearance cues show inadequate capability for representation or weak separability between the object and its local background.

3.1 Shape probability modeling

Let $I : x \to ℝ^{m}$ denote the input image that maps a pixel $x = [x y]^{T} \in ℝ^{2}$ to a value, where the value is a scalar in the case of a grayscale image (m = 1) or a three-element vector for an RGB image (m = 3). Let P denote the set of pixels in image I, L be the set of all binary segmentations on image I where each element $L$ is a binary vector with length |P| labeling each pixel in P to either object ( $F$ ) or background ( $B$ ) class. Our goal is to find an optimal segmentation $\hat{L}$ from L which best fits a given shape prior model $S$ . The shape model $S$ can be in any form to encode the shape knowledge of the object of interest, such as we here use an image database of silhouettes of the interested object. Then we model the probability of the candidate segmentation $L$ based on $S$ by considering both the global shape and the local edge cues in a Bayesian manner as $p (L | S, I) \propto \underset{global shape}{\underset{︸}{p_{s} (S | L)}} \underset{local edge}{\underset{︸}{p_{e} (S | L, I)}} \underset{prior}{\underset{︸}{p (L)}}$ (4) where $p_{s} (S | L)$ measures the global consistency between the boundary curve of segmentation $L$ and the given shape model $S$ . The second item measures the "edge" properties of $L$ . In the traditional form, this item can be presented as $p_{e} (I | L)$ , giving the likelihood that the segmentation boundary is on image edge. In the proposed method, benefiting from the shape model $S$ , the edges in image I are not treated equally and are instead valued by the shape model. Therefore, the new likelihood $p_{e} (S | L, I)$ can be interpreted as the amount of “good edges” the boundary of $L$ pass through. $p (L)$ is the prior probability of the segmentation which we regard equally for all candidates.

When we maximize the probability of (4), obviously, we expect to obtain the segmentation whose boundary has the globally consistent shape with the object shape priors encoded in the shape model $S$ and simultaneously pass through the exact object boundary. Figure 2 illustrates the properties of the expected segmentation.

Fig. 2

Properties of the optimal segmentation. Assuming the ellipse shape as the object shape priors, the boundaries of segmentation $L_{2}$ and $L_{3}$ have the global consistency with ellipse shape. The boundaries of $L_{1}$ and $L_{3}$ pass through the expected object boundary (“good edges”). Hence, $L_{3}$ is optimal among these three.

Let $\int_{i}$ denote an object silhouette in shape model $S$ , i.e. $S = {\int_{i}}_{i = 1}^{| S |}$ , the shape-based probability $p_{s} (S | L)$ of (4) can be measured by computing the minimum distance between segmentation $L$ and the silhouettes in $S$ , which is similar as the shape-based object retrieval process [11]: $p_{s} (S | L) = min_{\int \in S} D (ℓ, \int)$ (5) where ℓ is the boundary curve of $L$ and D (ℓ ₁, ℓ ₂) denotes the distance measurement between two contours.

Under the objective of driving the segmentation to target boundary, image gradient is usually used for edge detecting: $T (x, y) = | \nabla [G_{σ} (x, y) * I_{k} (x, y)] |^{2}$ (6) where ∇ denotes spatial gradient operator, * denotes convolution and G_σ is the Gaussian filter with standard deviation σ. However, this non-prior gradient can only “see” the image edge and has on capability to distinguish whether it is the exact target boundary. Here, we use the shape model $S$ to evaluate the gradient edges and drive the segmentation to the qualified edges and thereby guarantee its convergence to the real object boundary.

Specifically, we first split the image gradient edge in T into multiple smooth fragments by removing the turning point. Let $E = {e_{i}}_{i = 1}^{| E |}$ denote the edge set after splitting, each e_i denote a fragment of original image edge. For each e_i, we evaluate it using the shape model $S$ by computing its consistence degree with the closest silhouette in $S$ , then assign a corresponding confidence score v_i on it to indicate the likelihood of this fragment belonging to the object boundary. Based on the weighted edge set $E^{'} = {e_{i}, v_{i}}_{i = 1}^{| E |}$ , the edge-based probability $p_{e} (S | L, I)$ of (4) can be computed as the sum of scores assigned on the boundary ℓ of segmentation $L$ :

$\begin{matrix} log (p_{e} (S | L, I)) & \propto & \sum_{x \in ℓ} p (S | x, I) \\ \propto & \sum_{x \in ℓ} v_{i | x \in e_{i}} \end{matrix}$ (7)

3.2 Graph cut formulation

In this section, we formulate the shape probability modeled in Sec. 3.1 into the graph cut framework, where the problem of maximizing the probability of (4) over all segmentations L is converted to the form of implementing graph cut optimization. Let $L_{0}$ denote an initial input segmentation (ℓ₀ is the boundary), from where our proposed scheme begins the iterative optimizations, H_S (x) and H_T (x) are the initial t-link weights relative with $L_{0}$ . Let $\int^{ˆ}$ denote the closest object silhouette to ℓ₀ in shape model $S$ as described in (5), i.e. $\int^{ˆ} = \underset{\int | \int \in S}{arg min} D (ℓ_{0}, \int)$ . Therefore $D (ℓ_{0}, \int^{ˆ})$ is the corresponding minimum distance between ℓ₀ and $\int^{ˆ}$ . We use a signed distance function of silhouette $\int^{ˆ}$ weighted by the consistence measurement $D (ℓ_{0}, \int^{ˆ})$ , which can be regarded as a confidence degree of $\int^{ˆ}$ , to define the region term of (2) as $\begin{matrix} R_{F} (x) = max {H_{T} (x) - χ φ_{\int^{ˆ}} (x) \cdot D (ℓ_{0}, \int^{ˆ}), 0} \\ R_{B} (x) = max {H_{S} (x) + χ φ_{\int^{ˆ}} (x) \cdot D (ℓ_{0}, \int^{ˆ}), 0} \end{matrix}$ (8) where φ is defined as $φ_{\int^{ˆ}} (x) = {\begin{matrix} d (x, \int^{ˆ}), & if x inside \int^{ˆ} \\ 0, & if x at \int^{ˆ} \\ - d (x, \int^{ˆ}), & if x outside \int^{ˆ} \end{matrix}$ (9)

We can see in (8), $R_{F} (x)$ presents the region-based cost of labeling pixel x as ’Foreground’, this cost is generated by cutting the link between x and terminal T, this link weight is H_T (x) initially. As the estimated silhouette $\int^{ˆ}$ is generated based on $L_{0}$ , the pixels inside $\int^{ˆ}$ show relatively more consistence with the shape model $S$ , hence the weights on their links to terminal T decrease; and the pixels outside $\int^{ˆ}$ show relatively less consistence with shape model $S$ , hence the weights on their links to terminal T increase. Both the decrease and increase is gradually implemented by the signed distance function $φ_{\int^{ˆ}} (x)$ and weighted by the confidence degree of $\int^{ˆ}$ , i.e. $D (ℓ_{0}, \int^{ˆ})$ . χ controls the amount of these decrease and increase. This process is vice versa for $R_{B} (x)$ .

For the edge item B (x_i, x_j) in (3), traditional methods like [23] are based on the intensity/color difference of pixel x_i and x_j, making the segmentation boundary more inclined to pass the edge with strong intensity/color contrast on two sides. These methods regard the image edges with equal prior probability. Differently, in the proposed method, each edge fragment e_i is evaluated by the prior shape model $S$ and assigned a confidence score v_i, indicating its likelihood of being the target boundary. Therefore, it is more reasonable to drive the segmentation pass the "good" edges with high scores rather than the traditional "strong" edges. We assign each pixel the same score as the edge it belongs to. Pixels that are not in any gradient edge are assigned zero score. Then the edge item in the proposed SBGC model can be defined based on the score contrast between two neighboring pixels: $B (x_{i}, x_{j}) = β \cdot exp (- \frac{(v_{p | x_{i} \in e_{p}} - v_{q | x_{j} \in e_{q}})^{2}}{2 σ^{2}})$ (10)

3.3 Iterated segmentation

Under the guidance of the shape model $S$ , the proposed shape-bise graph cut scheme works iteratively, enabling the joint estimation of the optimal segmentation $\hat{L}$ and the global object shape $\int^{ˆ}$ . The main elements of the SBGC algorithm can be summarized as in Algorithm 1.

Algorithm 1 Iterative image segmentation using shape-bias graph cut.

Require: Image I, prior shape model $S$ composed of silhouettes of interested object: $S = {\int_{i}}_{i = 1}^{| S |}$ .

Ensure: Optimal segmentation $\hat{L}$ and the most likely object shape $\int^{ˆ}$ .

Initialization: A coarse initial segmentation ${\hat{L}}_{(0)}$ and the relative t-link weights of pixels H_S(0) (x), H_T(0) (x).

Iterative optimization:

1: Split the gradient edge of image I into smooth fragments $E = {e_{i}}_{i = 1}^{| E |}$ .

2: Evaluate each edge fragment using shape model $S$ and obtain its corresponding confidence score v_i, i.e. $E^{'} = {e_{i}, v_{i}}_{i = 1}^{| E |}$ .

3: Compute the edge item of SBGC based on the edge confidence score: $B (x_{i}, x_{j}) = β \cdot exp (- \frac{(v_{p | x_{i} \in e_{p}} - v_{q | x_{j} \in e_{q}})^{2}}{2 σ^{2}})$ (11)

4: Estimate the global object shape ${\int^{ˆ}}_{(τ)}$ based on the boundary ${\hat{ℓ}}_{(τ)}$ of current segmentation ${\hat{L}}_{(τ)}$ .

5: Refine the region item of SBGC based on shape ${\int^{ˆ}}_{(τ)}$ :

$\begin{matrix} R_{F} (x) = max {H_{T (τ)} (x) - χ φ_{{\int^{ˆ}}_{(τ)}} (x) \cdot D ({\hat{ℓ}}_{(τ)}, {\int^{ˆ}}_{(τ)}), 0} \\ R_{B} (x) = max {H_{S (τ)} (x) + χ φ_{{\int^{ˆ}}_{(τ)}} (x) \cdot D ({\hat{ℓ}}_{(τ)}, {\int^{ˆ}}_{(τ)}), 0} \end{matrix}$

6: Estimate segmentation using min cut and obtain:

${\hat{L}}_{(τ + 1)} = \underset{L}{arg min} E (L, R_{F / B} (x), B (x_{i}, x_{j}))$ and t-link weight of pixels H_S(τ+1)) (x), H_T(τ+1) (x).

7: Repeat from step 4, until convergence.

8: return $\hat{L}$ , $\int^{ˆ}$ ;

Initialization: Since the proposed SBGC method has the capability of automatically refining the segmentation to coincide with the global object shape encoded by the shape model, the initial segmentation ${\hat{L}}_{(0)}$ can be steered to the target from a wide variety of states, without any request of its boundary that must be inside or outside the target completely. In practice, we can do the initialization of ${\hat{L}}_{(0)}$ by a coarse division of image, such as threshold based image binarization. In this work, we use the standard interactive graph cut method with only one input seed for object and background class respectively to generate the initial segmentation ${\hat{L}}_{(0)}$ , as illustrated in Fig. 1. Once we obtain ${\hat{L}}_{(0)}$ , the initial t-link weights can be computed based on the color model of the respective foreground and background region divided by ${\hat{L}}_{(0)}$ as in standard graph cut.

Convergence: The proposed SBGC algorithm guarantees proper convergence properties. Once an unconsistency is detected between the current segmentation and the estimated object shape, the SBGC adjusts the t-link weights of the constructed graph to make the segmentation closer to the estimated object shape in next iteration. This procedure is repeated until these two curves are ideally matched, Fig. 3(a). This is a process of interactively enhancing the foreground/background discrimination, and simultaneously the foreground/background labeling becomes more and more accurate. Therefore the total energy decreases monotonically during this process until each pixel in the graph keeps one zero-weighted t-link, and this is illustrated in practice in Fig. 3(b). It is straightforward to detect when the segmentation fully matches the estimated object shape, and to terminate iteration automatically.

Fig. 3

Convergence of iterative SBGC on the photo of Fig. 1. (a) shows the consistency between the segmentation and the current estimated object shape; (b) shows the energies of the SBGC model. (The consistency measurement begins at the initialization, iteration 0, and the energy begins at the real SBGC iteration, iteration 1.) We can see the SBGC model converges at iteration 5.

4 Experimental results

In this section, we employ an ellipses segmentation application to validate the effectiveness of the proposed shape-bias graph cut method. We select the real-world oval plates as the interested object in photos since it has various challenging cases for segmentation task, such as the various inside food, real-world cluttered background, partial occlusion and so on. Due to the complicated and unstatisticable appearance properties, all these cases are challenging for traditional appearance based segmentation methods. Besides, the real-world plates detection and segmentation is useful especially in wearable camera applications such as eating event detection and food calories estimation.

Since the objects we mainly focus on in this experiment are oval plates, the shape model we use here is assumed as the set of ellipses with all various scales and orientations. In standard graph cut [2], the parameters are set as λ = 10¹² and β = 10⁸, we use the same values in the SBGC method and additionally set χ = 5 ×10⁶ according to the values of λ and β.

Firstly, we present the working process of the proposed SBGC method on the challenging photo shown in Fig. 1. This is a real-world photo taken by a wearable camera and with a little distortion. The plate is in cluttered background and with crushing food inside, both of which are in indiscriminative colors and difficult to model based on appearance features. Two pieces of white paper connected with the plate is also big interferences to segmentation, Fig. 4(a). To evaluate the boundary term of the SBGC model, we split the image gradient edge into fragments by removing the turning point where the monotonicity of the edge curve changes in either x or y directions, Fig. 4(b)(c). For each edge fragment, we evaluate it using the shape model by computing its consistency degree with the closest ellipse shape. Then each fragment is assigned a confidence score indicating its likelihood of being a part of the interested object boundary, Fig. 4(d). After that, the SBGC works iteratively to jointly estimate the segmentation and the global object shape, and eventually converges to the region with maximum consistency with the prior shape model. Figure 5 shows the SBGC iterations on this photo, where (a) is the initial input segmentation obtained by using standard seeded graph cut with one input seed on object and background region respectively, similar as the big green and yellow point in Fig. 1(a). The pleasant results shown in Figs. 1 and 5 demonstrate the effectiveness of the proposed SBGC method in complicated scene. Fig. 3(a) shows the increasing consistency between the segmentation and estimated object shape as the SBGC iterations going on this photo while Fig. 3(b) shows the decreasing energy values, illustrating the convergence properties of the proposed SBGC scheme.

Fig. 4

Boundary term construction of the proposed SBGC model. In (d), the score values are reflected by the edge’s thickness.

Fig. 5

Iterative segmentation of the proposed SBGC method. (a) is the initial input segmentation obtained by the standard graph cut with one seed for object and background respectively, similar as the big green and yellow point in Fig.1(a). (b) is the boundary of (a).

Then, we compare the SBGC method with some other graph cut based algorithms on another four challenging cases to show the advantages of our approach. The first two are regular-camera photos where the plates are in similar background while the last two are wearable-camera photos in real-world living circumstances. Both of these two kinds of photos contain a whole and a partial plate. The three algorithms we tested are: (i) the standard seeded graph cut [2] using 50 seeds on the object and background region respectively; (ii) the iterative grab cut [19] begins from a bounding box of the object; (iii) the proposed SBGC method using the segmentation of standard seeded graph cut with only one seed on object and background region respectively as the initialization. Figure 6 shows the segmentation results of these algorithms. We can see that because of the similar background pollution and the complicated scenes, it is difficult for the conventional appearance based methods to separate out the object region accurately. The proposed method, in contrast, seizing the global shape properties, can obtain pleasant result.

Fig. 6

Segmentation results of the compared methods on four challenging cases. Column (a) is the original photos; (b) shows the initialization of each method: the red and blue points are the 100 input seeds for standard graph cut, the red bounding box is for grab cut, the green curve obtained by inputting two seeds (the big pink one for object and yellow one for background) to standard graph cut is for the proposed SBGC; Columns (c)–(e) give the results of the standard graph cut, grab cut and the proposed SBGC respectively.

Furthermore, the pictures used in our experiments are taken in real daily life, with a variety of cluttered background. Therefore, it is challenging for traditional methods those focus on the segmentation of foreground object in central salient position with relatively high contrast background surround, e.g. the Grabcut method [19] and the salient key point based segmentation method [14]. In [14], the authors use a regional contrast based saliency extraction method to select rough object regions in the image, then an threshold segmentation is applied to the saliency map to get the high saliency region mask, within which the detected salient points is regarded as foreground seeds, together with star shape prior, for graph cut segmentation. The first row of Fig. 7 gives the saliency map detected on the real daily pictures, from where we can see, in the complex real life scene, the dinner plate does not have high contrast appearance and high salient score over the whole image. Therefore, it is difficult for the saliency detection based method to accurately extract the low discriminative plate region. In contrast, the proposed method, extract the elliptic edge information as shape prior to give the segmentation preference and guide the segmentation curve, can obtain pleasant results as shown in the last row of Fig. 7. The middle row of Fig. 7 shows the two seed points input into the standard graph cut model for obtaining the initial curve of the proposed method.

Fig. 7

Comparison of the proposed method with saliency detection based method [14]. The first row is saliency map, the second row shows the two seed points input into the standard graph cut model for obtaining the initial curve of the proposed method, and the last row give the segmentation results of the proposed method.

Finally, we use various cases with different challenges for segmentation to further evaluate the proposed SBGC method. Both the original photos and the segmentation results are shown in Fig. 7. In this figure, (a)–(c) are plates with complicated appearance; (c) is full of food; (e)(f) are with lots of interference edges; (m)(n) are partial occluded; (o)-(r) are from wearable cameras where (r) is from Nebojsa’s two weeks personal data (Day 1: 21st April 2009) 1 [9]. Fig. 7(g)–(l) and (s)–(x) show the corresponding segmentation results, demonstrating the robustness of the proposed method in dealing with these challenging cases.

Fig. 8

Experimental results for further evaluation. (a)–(c) are complicated plate; (c) is full of food; (e)(f) are with lots of interference edges; (m)(n) are partial occluded; (o)-(r) are from wearable cameras where (r) is from Nebojsa’s two weeks personal data (Day 1: 21st April 2009) [9]. (g)–(l) and (s)–(x) are the segmentation results of SBGC.

5 Conclusion

We have presented a novel graph cut method in this paper for iterated segmentation of objects with specific shape bias. Instead of emphasizing the regional appearance cues, the proposed SBGC takes the shape preference of the interested object into account to guide the segmentation. Both the global shape and local edge consistencies of the segmentation with the object shape priors are formulated into the graph cut framework to drive the optimization and seek segmentation that maximizing both of these global and local measurements. By jointly estimating the optimal segmentation and the most likely object shape encoded by the shape priors, the SBGC act towards the candidate result with maximum consistency between these two estimations and eventually achieve the accurate convergence to the interested object. Competitive results on ellipse shape objects with various segmentation challenges as well as the comparisons with state-of-the-art methods validate the effectiveness of the technique.

Footnotes

Acknowledgment

This work is funded by the National Natural Science Foundation of China (No. 61702138 and No. 61602128), and the Shandong Province Natural Science Foundation of China (No. ZR2016FQ13 and No. ZR2019PF007), and the China Postdoctoral Science Foundation (No. 2019M662360, No. 2017M621275 and No. 2018T110301), and the Hong Kong Scholar Project of China (No. ALGA4131016116), and Young Scholars Program of Shandong University, Weihai (No. 1050501318006), and Science and Technology Development Plan of Weihai City (No. 1050413421912), and Basic Scientific Research Operating Expenses of Shandong University (No. 2018ZQXM004), and Foundation of Key Laboratory of Urban Land Resources Monitoring and Simulation, Ministry of Land and Resources (No. KF-2019-04-034), and the Fundamental Research Funds for the Central Universities (No. HIT.NSRIF.2019082).

References

Ayed

I.B.

, Chen

, Punithakumar

, Ross

and Li

, Graph cut segmentation with a global constraint: Recovering region distribution via a bound of the bhattacharyya measure, IEEE CVPR (2010), 3288–3295.

Boykov

and Jolly

M.P.

, Interactive graph cuts for optimal boundary and region segmentation of objects in n-d images, IEEE ICCV (2001), 105–112.

Couprie

, Grady

, Najman

and Talbot

, Power watersheds: A new image segmentation framework extending graph cuts, random walker and optimal spanning forest, IEEE ICCV (2009), 731–738.

Daniel

, and M.J. Graph-cut ransac, The IEEE Conference on Computer Vision and Pattern Recognition (CVPR) (2018).

Deng

, Zheng

, Xu

, and et al, Graph cut based automatic aorta segmentation with an adaptive smoothness constraint in 3d abdominal ct images, Neurocomputing (2018), 46–58.

Freedman

and Zhang

, Interactive graph cut based segmentation with shape priors, IEEE CVPR (2005).

Gorelick

, Delong

, Veksler

and Boykov

, Recursive mdl via graph cuts: Application to segmentation, IEEE ICCV (2011), 890–897.

Hawas

A.R.

, Guo

and Du

, et al. Oce-ngc: A neutrosophic graph cut algorithm using optimized clustering estimation algorithm for dermoscopic skin lesion segmentation, Applied Soft Computing (2019).

Jojic

, Perina

and Murino

, Structural epitome:Away to summarize one’s visual experience, Advances in NIPS (2010), 1027–1035.

10.

Kusakunniran

, Wu

, Ritthipravat

and Zhang

, Hard exudates segmentation based on learned initial seeds and iterative graph cut, Computer Methods and Programs in Biomedicine (2018), 173–183.

11.

Latecki

L.J.

and Lakamper

, Shape similarity measure based on correspondence of visual parts, IEEE Trans. PAMI 22(10) (2000), 1185–1190.

12.

Lempitsky

, Kohli

, Rother

and Sharp

, Image segmentation with a bounding box prior, IEEE ICCV (2009).

13.

, Sun

, Tang

C.K.

and Shum

H.Y.

, Lazy snapping, ACM SIGGRAPH (2004), 303–308.

14.

Liao

, Xu

and Zhou

, et al. Automatic image segmentation using salient key point extraction and star shape prior, Signal Processing (2014), 122–136.

15.

Liu

, Sun

and Shum

H.Y.

, Paint selection, ACM SIGGRAPH (2009), 1–7.

16.

Pham

V.Q.

, Takahashi

and Naemura

, Foreground-background segmentation using iterated distribution matching, IEEE CVPR (2011), 2113–2120.

17.

Price

B.L.

, Morse

and Cohen

, Geodesic graph cut for interactive image segmentation, IEEE CVPR (2010).

18.

Protiere

and Sapiro

, Interactive image segmentation via adaptive weighted distances, IEEE Trans. IP 16(4) (2007), 1046–1057.

19.

Rother

, Kolmogorov

and Blake

, Grabcut – interactive foreground extraction using iterated graph cuts, ACM SIGGRAPH (2004), 309–314.

20.

Rother

, Kolmogorov

, Minka

and Blake

, Cosegmentation of image pairs by histogram matching – incorporating a global constraint into mrfs, IEEE CVPR (2006).

21.

Schoenemann

, Kahl

and Cremers

, Curvature regularity for region-based image segmentation and inpainting: A linear programming relaxation, IEEE ICCV (2009).

22.

Sinop

A.K.

and Grady

, A seeded image segmentation framework unifying graph cuts and random walker which yields a new algorithm, IEEE ICCV (2007), 1–8.

23.

Slabaugh

and Unal

, Graph cuts segmentation using an elliptical shape prior, IEEE ICIP (2005).

24.

Veksler

, Star shape prior for graph-cut image segmentation, ECCV (2008).

25.

Vela

A.H.

, Zlateva

and Marinov

, et al. Graph cuts optimization for multi-limb human segmentation in depth maps, IEEE CVPR (2012), 726–732.

26.

Vicente

, Kolmogorov

and Rother

, Joint optimization of segmentation and appearance models, IEEE ICCV (2009), 755–762.

27.

Wang

, Gan

and Shui

, et al. 3d shape segmentation via shape fully convolutional networks, Computers and Graphics (2018), 128–139.

28.

Yutian

, Gelfand

, Fowlkes

C.C.

and Welling

, Integrating local classifiers through nonlinear dynamics on label graphs with an application to image segmentation, IEEE ICCV (2011), 2635–2642.