Coarse-to-fine Image Co-segmentation with Intra and Inter Rank Constraints

1 Introduction

Co-segmentation, i.e., jointly segmenting the common objects from a collection of similar images, has attracted an increasing attention recently in computer vision community

∗Corresponding author: Lianli Gao, Heng Tao Shen

[Joulin et al., 2010; Yuan et al., 2017; Mukherjee et al., 2018; Maninis et al., 2017; Song et al., 2016]. Compared with single image segmentation [Gao et al., 2016], co-segmentation has the advantage of utilizing the very weak prior that the set of images contain the same objects to improve the segmentation of individual images. At the meanwhile, cosegmentation is a challenging problem, which faces several major issues: 1) The classical segmentation methods are designed for a single image while co-segmentation deals with multiple images. How to design a co-segmentation model and minimize the model is crucial for image co-segmentation. 2) The common object extraction depends on the foreground similarity measurement. But the foreground usually varies in color, shape and scale, which makes the foreground similarity measurement difficult. Moreover, the model minimization is highly related to the selection of similarity measurement. Therefore, the foreground similarities measurement is another important issue.

A straight-forward way for co-segmentation is to extend classical single image based segmentation models. In general, the extended models can be represented as

where ℓs is the single image segmentation term, which guarantees the smoothness and the distinction between foreground and background in each image, and ℓg is the co-segmentation term, which focuses on evaluating the consistency between the foregrounds among the images.

Many classical single image segmentation models can be used to form ℓs, e.g, MRF segmentation models [Lee et al., 2015] and discriminative clustering [Joulin et al., 2010]. The co-segmentation term ℓg is used to evaluate the multiple foreground consistency, which is introduced to guarantee the common object segmentation. Due to the variance of the foreground, the similarity measure using visual features is not accurate enough.

On the other hand, segmentation proposal selection based approaches [Vicente et al., 2011; Meng et al., 2012; 2013] have recently drawn more attention. These methods aim at select the real common objects from the segmentation proposals, and the assumption that the common targets should be real-world objects makes co-segmentation much more efficient. Compared with co-segmenting images using pixels, segmentation proposal selection based approaches have their advantages. First, instead of starting from scratch, they incorporate either class-specific or class-independent object proposal methods to generate a set of candidates, and then look for a pool of regions that have high probability to cover the objects by some of the proposals. The proposals are usually more robust, and they contain rich information than pixels. Therefore, they usually achieve better accuracy than methods based on pixels. Secondly, they are more efficient compared with pixel-based methods, because the number of proposals is usually much small than the number of pixels in images. However, their disadvantages are obvious as well. They usually reply heavily on the performance of object proposals. Also, due to the variety of the common objects, it usually requires manually selecting features [Meng et al., 2012] or supervised feature learning performed beforehand [Vicente et al., 2011; Meng et al., 2013].

To address the above issues, in this work, we propose a novel coarse-to-fine image co-segmentation framework, which introduces graph-based image co-segmentation using superpixels based on intra and inter rank constraints. To take advantage of proposal, we utilize the coarse foreground and background proposals to learn a robust similarity measure of the superpixels. It is worthwhile to highlight the following aspects of our method here: 1) We propose a novel coarse-tofine image co-segmentation framework. To take advantage of object proposals but avoid heavily depending on the proposal quality, we utilize multiple image proposal strategies and generate a set of coarse foreground and background. These incomplete but with few noise coarse segments are further used to learn a similarity measurement of the raw features to obtain a fine image co-segmentation. 2) We design an intuitive graph-based objective function for image co-segmentation based on its definition. Taking the feature similarity graph as input, we aim to learn a segmentation similarity graph which should be consistent with feature similarity graph and also be able to co-segment the superpixels in images into either foreground or background. We devise an efficient solution for this objective function. 3) Experiments for image co-segmentation on real-world datasets demonstrate the superiority of our method over existing methods. Notably, this performance is achieved using HSV feature only.

2 Our Approach

In this section, we introduce our method which consists of two phases (see Fig. 1). Firstly, we further introduce how to construct an original similarity graph using the coarse foreground and background proposals. Then, a graph-based image co-segmentation algorithm is proposed based on the original similarity graph of the superpixels.

We first introduce the notations which will be used in the rest of the paper. Given a set of M images I = {I1, I2, ..., IM} for an object class, we first generate a set of N oversegmenting superpixels V = {v1, v2, ..., vN} as a preprocessing, and then extract features X = {x1, x2, ..., xN} from these N superpixels. A superpixel is an image segment consisting of pixels that have similar visual characteristics.

The goal is to learn the similarity matrix S between each superpixel based on the features X, and all the superpixels are segmented to either foreground or background.

2.1 Coarse Foreground and Background Proposal for Original Similarity Graph Construction

Instead of segmenting common objects from an object class from scratch, we start by generating a set of coarse foreground and background proposals. The motivation is that if we can generate pure foreground and background with high precision but low recall, we can use these regions as coarse proposals to construct an accurate original similarity graph. Inspired by recent progress in object proposal and salient object detection, we find that those two techniques have potential to propose incomplete by with few noise objects in an image. This is because salient object detection (e.g., PCA Saliency [Margolin et al., 2013]) is originally a task of predicting the eye-fixations on images, and recently has been extended to detecting regions with salient attention-grabbing objects, while object proposal (e.g.,MCG [Arbel´aez et al., 2014] ) aims to generate a set of regions to delineate candidate objects in an image. However, current generated saliency maps are typically blurry, especially near the boundary of salient objects, while object proposal methods can provide accurate object boundaries but it is still difficult to obtain complete objects by merging together sets of regions, thus they are complementary to each other.

Therefore, in this study we take the advantages of both salient object detect [Margolin et al., 2013] and object proposal [Arbel´aez et al., 2014] to produce coarse foreground and background, which respectively contain incomplete but relatively pure foreground and background, to refine our similarity graph. Here, we introduce the construction details. Given an image Ig ∈ Rw×h , where w and h are the width and length.

Saliency map and candidate mask generation. At beginning, PCA Saliency [Margolin et al., 2013] takes Ig as input and produce a saliency map s map ∈ Rw×h , while MCG [Arbel´aez et al., 2014] takes I as input and produces a ranked list of object candidates. Here, we merge the top-5 ranked object candidates to output a candidate mask c mask ∈ Rw×h . If c maski,j = 1, it stands that the pixel Ig (i, j) is an object pixel otherwise it is a background pixel.

Refine candidate with UCMs. After we obtained the initialized c Mask, we apply ucms to refine c Mask. Firstly, we extract superpixesl with ucm ≤ 0.5 and then remove the superpiexles containing border pixels, except those superpixels meets one of the following conditions: having less than 18 (w + h) border superpixels; 2) only containing left or right boarder pixels; and 3) the number of top/bottom boarder pixels is less than 3 4 of the corresponding boarder length. Next, we project these superpixels to ucm ≤ 0.18 and then merge with c Mask to obtain a new c Mask. Note that, all the parameter values are empirically set as above. Next, we move to coarse foreground and background generation.

Coarse background generation. At first, we compute a threshold thb by averaging the values of s Map that are lower than the mean of s Map. Next, comparing each element of s map with thb to initialize the coarse background mask b mask by setting the larger elements as 1, otherwise setting as 0. Finally, we sum the initialized b mask with c mask to update b mask. If an element of b mask is less than 2, it stands for the corresponding pixel is a pure background pixel. Coarse foreground generation. First, we look for elements of s map that are larger than s Map mean and then set them as 1, otherwise set as 0, to form an initial coarse foreto obtain the coarse foreground mask f mask. If the element ground mask f mask. Next, we joint f mask and c mask of f mask is 1, the corresponding pixel is pure foreground.

2.2 Image Co-segmentation with Intra and Inter Rank Constraints

Instead of following the conventional pipeline for image co-segmentation, in our framework (see Fig. 1), we propose a novel perspective to solve the graph-based image cosegmentation problem. Based on the definition of image cosegmentation, all the images have two segments (foreground and background), and each image also has two segments. Conventional methods usually construct a similarity graph A based on the features of superpixels, and all the superpixels are connected as just one connected component. Ideally, if the superpixels of all the images (and also for each image) are connected as exactly 2 components, the superpixels are naturally divided into 2 segmentations and this segmentation is the optimal solution for different criteria, e.g., normalized cut [Shi and Malik, 2000]. Then we can get our objective function:

where S is the segmentation similarity graph to be learned, and A ∈ RN×N is the original similarity graph. Sm is a block of S and it is the segmentation similarity matrix of image Im. The object function aims to learn a S which is similar to A. To avoid the case that some rows of S are all zeros, we further constrain the S such that the sum of each row of S is one.

Under these constraints, we learn a S that best approximates the initial affinity matrix A. The last two constraints require that all the images have two segments (foreground and background), and each image also has two segments, which is the definition of image co-segmentation.

The problem in (2) is not easy to solve because of the constraints. To tackle this, we start from the following theorem. For a nonnegative similarity matrix S, there is a Laplacian matrix L associated with it. According to the definition of Laplacian matrix, suppose each superpixel xi is assigned a random value as fi ∈ R1×K , then L can be calculated as:

where F ∈ RN×K with the i-th row formed by fi, L = D - St+S 2 is called the Laplacianmatrix in graph theory, the degree matrix D ∈ RN×N is defined as a diagonal matrix where the i-th diagonal element is ∑j (sji + sij) /2. The Laplacian matrix L has the following property.

Theorem 1 The number K of the eigenvalue 0 of the Laplacian matrix L is equal to the number of connected components in the graph with the similarity matrix S if S is nonnegative.

Theorem 1 indicates that if rank(L) = N - 2, then the superpixels have 2 connected components based on S. Thus, (2) can be reformulated as:

where L is the laplacian matrix of S, and Lm is the laplacian matrix of Sm. It is still difficult to solve the problem (4). Because L = D - (ST + S) /2 and D also depends on S. The constraint rank(L) = N-2, rank(Lm) = N-2 are not easy to tackle. Suppose ei is the i-th smallest eigenvalue of L and (em)i is the i-th smallest eigenvalue of Lm, we know ei, (em)i ≥ 0 since L and Lm are positive semi-definite. It can be seen that the problem (4) is equivalent to the following problem for a large enough value of α and β 1 :

When α and β are set to a large enough value, ∑2i ei and ∑2i (em)i will be imposed to be close to 0, which results in rank (L) = N - 2 and rank (Lm) = N - 2.

According to the Ky Fan's Theorem [Fan, 1949], we have:

Therefore, (5) is further equivalent to:

Compared with the original problem 2, the problem 7 is much easier to solve.

2.3 Iterative Optimization

We propose an iterative method to minimize the above objective function in Eq.7. We first formally define the relationships between S to Sm, and F to Fm. Recall that S is the original similarity graph of all images, and Sm is the similarity graph of the m-th image. Therefore, Sm = S (idsm : idem, idsm : idem), where idsm and idem are the index for the starting and ending position of superpixels in M images set. Formally, we define a selection matrix U ∈ RN×Nm so that Sm = UTmSUm, where U is a matrix with all zeros, but the idsm to idem rows are filled by an identity matrix INm . Similarly, we can get Fm = UTmF.

By taking the original similarity matrix A as input, in each iteration, our algorithm first updates F and Fm given S, and then updates S by fixing F and Fm. These steps are described below.

Update F and Fm

By fixing S, we can obtain F and Fm by optimizing Eq.7. This is equivalent to optimize the following objective function:

which can be further reformulated as:

F can be solved by obtaining the two smallest eigenvector of UmLmUTm), and Fm = UT F.

1 In the real implementation, we initialize with 1000, and increase α, β to α×2, β ×2 if the current number of connected components is less than 2, and decrease α, β to α/2, β/2 if the current number of connected components is larger than 2

Update S

By fixing F and Fm, we can obtain S by optimizing Eq.7. It is equivalent to optimize the following objective function:

and we can rewrite the second part as:

Denote gi,j = α‖fi - fj‖2 + β M∑ m=1 (bm)ij , and (12) can

be reformulated as:

The problem in Eq.13 is simplex [Nie et al., 2016] and the critical step of the projected gradient method is to solve the following proximal problem:

This proximal problem can be solved by an efficient iterative algorithm [Nie et al., 2016]. Then each si can be efficiently solved, and we can get the updated graph S.

We update F and S iteratively until the objective function Eq.7 converges.

3 Experiments

We evaluate our algorithm on the task of image cosegmentation. Firstly, we compare our results with state-ofthe-art algorithms on two standard datasets. Then, we study the influence of different features for our algorithm.

3.1 Experimental Settings

Datasets

We evaluated the proposed algorithm on two public benchmark datasets: the iCoseg dataset [Batra et al., 2010] and the MSRC dataset [Winn et al., 2005]. iCoseg dataset contains 38 image classes of totally 643 images with manually labeled pixel-wise ground-truth masks. We follow [Lee et al., 2015] to use a subset of 16 object classes. The later includes 591 pixelwise labeled images of 23 object classes. We select the same classes as reported by [Joulin et al., 2010;

Lee et al., 2015]. The complex background of the MSRC dataset makes it more challenging, and it involves considerable changes in viewpoints and illumination.

Following [Lee et al., 2015], we evaluate accuracy, precision and recall for the segmentation. A segmentation accuracy is defined as the percentage of correctly labeled pixels, while precision and recall are defined as the percentage of correctly labeled foreground.

Features

We utilize two kinds of image features, i.e., the shallow features and the deep features, to capture different characteristics of each superpixel. Specifically, we used HSV feature in our work, and we further test another three kinds of shallow features, including LAB, texture, and dense SIFT descriptors. Software from [van de Sande et al., 2011] is used, and the dimensions for each feature is 75-D for HSV, 75-D for LAB, 240-D for texture, and 1024-D for SIFT.

For deep feature, we employ the CNN-S [Chatfield et al., 2014] model which is pre-trained on the ImageNet dataset. Firstly, we feed each image into the pre-trained CNN and get the responses from the last convolutional layer, which consists of 512 feature maps with size of 17×17. Next, we resize the feature maps to the size of the original image, and then use a max pooling operation on each superpixel to generate a 512-D CNN feature vector.

We run our algorithm using single image (IS) and cosegmentation (CS). Instead of running our method on the proposed non-background regions, we also test the performance of our algorithm using the full image (FI).

3.2 Results on iCoseg Dataset

To evaluate the performance of our method, we compare it with different image co-segmentation algorithms, e.g., MRW

[Lee et al., 2015], RM [Rubio, 2012], OC [Vicente et al., 2011], CFM [Wang et al., 2013], CFO [Li et al., 2016].

Table 1 shows the accuracy of state-of-the-art image cosegmentation algorithms on iCoseg dataset and Table 2 depicts the precision and recall for the different methods. We also show some qualitative results in Fig. 2. From these figures, we have the following observations:

Compared to state-of-the-art image co-segmentation algorithms, our method achieves better performance in terms of segmentation average accuracy. This indicates that our graphbased coarse-to-fine image co-segmentation strategy can result in a good segmentation. MRW [Lee et al., 2015] and [Li et al., 2016] are strong competitors, and they outperform our method for some object classes, e.g., 'elephant', 'skating' and 'stonehenge2'. One reason is that the proposed nonbackground regions of our method is not that accurate, and some foreground are not covered by the non-background regions, e.g., 'elephant' and 'stonehenge2'. Another reason is that HSV is a simple visual feature, and is not powerful enough to segment visually different superpixels into one part, e.g., the black skirts and white pants for 'skating'.

Compared with FI, the performance for CS is improved by 2.1%. This indicates that our proposed non-background regions can get rid of some noise, and improve our graph-based segmentation algorithm. On the other hand, the improvement of CS over IS is more significant, and it is 8.0%. IS attempts to separate an object from its background in a single image, but without consideration of multiple images, the definition of 'object' is ambiguous. For instance, given the single image of 'baseball', it is not clear whether the object should consist of the people in white only or all the people. Thus, IS may fail to delineate desired objects, especially in the cases of several objects. In contrast, CS overcomes the ambiguity, by extracting regions that occur repeatedly across images.

Comparing with MRW [Lee et al., 2015] in terms of precision and recall, our method CS achieves much better performance for precision with 7.4%, but slightly worse performance for recall with 0.7% decrease. These results show that our CS can generate relative smaller foreground than MRW, but these regions are more precise.

The qualitative results are demonstrated as the top-rows in Fig. 2 . The results show that our CS can successfully cosegment images for simple background (e.g., 'balloon'), complex background (e.g., 'alaskan bear'), single object (e.g., 'panda') and multiple objects (e.g., 'skating'). In general, better performance is achieved for single object segmentation with simple background. In cases of complex background and foreground, e.g., 'skating' and 'Stonehenge2', our segmentation performance is unsatisfactory, and the proposed foreground and background have more noise than other cases.

3.3 Results onMSRCDataset

On MSRC dataset, we compare our method to state-of-the-art image co-segmentation algorithms, e.g., MRW, DC [Joulin et al., 2010], RM [Rubio, 2012], CFM [Wang et al., 2013]. Table 3 shows the accuracy of state-of-the-art image cosegmentation algorithms on MSRC dataset and Table 4 depicts the precision and recall for the different methods. We also show some qualitative results in Fig. 2. We have the following observations:

Compared to state-of-the-art image co-segmentation algorithms, our method CS achieves comparable performance in terms of segmentation average accuracy. This indicates that our CS can result in a good segmentation for cases of complex background. [Wang et al., 2013] has better accuracy than our CS, and it outperform our method for object classes of 'car(back)' and 'face' by 7.0% and 5.7%. However, they use multiple features, and our CS achieves this performance by using HSV feature only. By using sophisticated features or multiple features, the performance can be potentially improved. On the other hand, our CS obtains the best performance for 'car(front)', 'bike', 'cat' and 'cow', and it consistently outperforms MRW,[Rubio, 2012] and [Joulin et al., 2010] except for the class of 'plane'.

Compared with FI, the performance for CS is improved by 10.2%, which is greater than iCoseg dataset. The indicates that for complex background, our proposed non-background regions can better get rid of noise. On the other hand, the improvement of CS over IS is much more significant, and it is 17.0%. The reason for the improvement of CS over IS is similar to that of iCoseg dataset. CS overcomes the ambiguity of IS by extracting regions that co-occur in all the images.

Comparing with MRW [Lee et al., 2015] in terms of precision and recall, our method CS achieves much better performance for recall, but slightly worse performance for precision. These show that our CS can segment more regions to foreground than MRW, without decreasing the precision.

The qualitative results are demonstrated as the bottom-rows in Fig. 2. The qualitative results show that our CS can successfully co-segment images for simple background (e.g., 'cow'), complex background (e.g., 'face'), single object (e.g., 'face') and multiple objects (e.g., 'bike'). In general, better performance is achieved for single object segmentation with simple background. In cases of complex background and foreground, e.g., 'car(front)' and 'airplane', the proposed foreground and background have more noise then other cases. Therefore, our segmentation performance is unsatisfactory.

4 Conclusions

In this work, we propose a novel unsupervised coarse-to-fine co-segmentation (CFC) framework, which introduces graphbased image co-segmentation based on intra and inter rank constraints, and also utilizes the coarse foreground and background proposals to construct a robust original similarity graph. Experiments on two commonly used image datasets (iCoseg and MSRC) demonstrate that our method achieves comparable or even better performance than state-of-the-art methods by using only HSV feature.

Acknowledgments

This work is supported by the Fundamental Research Funds for the Central Universities (Grant No. ZYGX2014J063, No. ZYGX2014Z007) and the National Natural Science Foundation of China (Grant No. 61772116, No. 61502080, No. 61632007, No. 61602049).