IEEE TRANSACTIONS ON IMAGE PROCESSING, VOL. 22, NO. 12, DECEMBER 2013

4809

Feature Adaptive Co-Segmentation by Complexity
Awareness
Fanman Meng, Hongliang Li, Senior Member, IEEE, King Ngi Ngan, Fellow, IEEE,
Liaoyuan Zeng, and Qingbo Wu

Abstract— In this paper, we propose a novel feature adaptive
co-segmentation method that can learn adaptive features of different image groups for accurate common objects segmentation.
We also propose image complexity awareness for adaptive featurelearning. In the proposed method, the original images are firstranked according to the image complexities that are measured
by superpixel changing cue and object detection cue. Then, theunsupervised segments of the simple images are used to learn
the adaptive features, which are achieved using an expectationminimization algorithm combining l1-regularized least squares
optimization with the consideration of the confidence of thesimple image segmentation accuracies and the fitness of thelearned model. The error rate of the final co-segmentation istested by the experiments on different image groups and verified
to be lower than the existing state-of-the-art co-segmentation
methods.
Index Terms— Cosegmentation, distance metric learning,
image complexity analysis.

I. I NTRODUCTIONI

N COMPUTER vision area, image segmentation [1]–[8]is a process of segmenting objects from images. The goalof image segmentation is bottom up and unsupervised segmentation of general images. As a key branch of image
segmentation, co-segmentation [9]–[24] is to segment common
objects from an image group. By assuming a group of images
contain common objects, co-segmentation only requires additional images containing the same or similar target objects for
accurate segmentation.
The co-segmentation methods are generally developed byadding foreground similarity into single image segmentation
Manuscript received January 4, 2013; revised May 30, 2013 and July 23,
2013; accepted July 31, 2013. Date of publication August 15, 2013; date ofcurrent version September 27, 2013. This work was supported in part by the
NSFC under Grant 61271289, in part by the Ph.D. Programs Foundation of
the Ministry of Education of China under Grant 20110185110002, in partby the National High Technology Research and Development Program ofChina (863 Program) under Grant 2012AA011503, and in part by the Fundamental Research Funds for the Central Universities under Grant E022050205.
The associate editor coordinating the review of this manuscript and approving
it for publication was Prof. Carlo S. Regazzoni.
F. Meng, H. Li, L. Zeng, and Q. Wu are with the School of Electronic
Engineering, University of Electronic Science and Technology of China,
Chengdu 611731, China (e-mail: fm-meng@qq.com; hlli@uestc.edu.cn;
lyzeng@uestc.edu.cn; wqb.uestc@gmail.com).
K. N. Ngan is with the Department of Electronic Engineering, The Chinese
University of Hong Kong, Hong Kong, and also with the School of Electronic
Engineering, University of Electronic Science and Technology of China,
Chengdu 611731, China (e-mail: knngan@ee.cuhk.edu.hk).
Color versions of one or more of the figures in this paper are available
online at http://ieeexplore.ieee.org.
Digital Object Identifier 10.1109/TIP.2013.2278461

TABLE IT HE F EATURES U SED IN THE E XISTING C O -S EGMENTATION M ETHODS

models, such as Markov Random Filed (MRF) segmentation [9]–[12], [17], [22], heat diffusion segmentation [19],clustering based segmentation [14], [20], and random walker
segmentation [21]. Using the additional foreground similarity
constraints guarantees the segmentation of the common objects
only, which results in more accurate segmentation than single
image segmentation.
The accuracy of co-segmentation is significantly dependent
on the efficiency of the foreground similarities measurement.
Many region features, such as color histogram [9]–[13],SIFT [14], [20], contour descriptor [18] and local binary pattern descriptor [22], have been used to evaluate the foregroundsimilarity. Furthermore, 1-norm, 2-norm, reward strategy
and χ 2 distance, were usually used for the feature distancecalculation.
However, the existing co-segmentation methods cosegment
different image classes using a fixed foreground similarity
measurement without change. In general, the fixed features aremanually selected or learned from the training data set [18]before co-segmentation. We display the fixed features usedin the existing co-segmentation methods in Table I. Using
fixed similarity measurement in co-segmentation may leadto some problems in realistic applications. Firstly, since thesimilar features of the common objects vary in different
image groups, the fixed feature can not accurately measure
the foreground similarities of different classes, which resultsin the unsuccessful co-segmentation. Secondly, for the images
whose common object varies significantly, a combination of
the general features will be required to accurately measure theforeground similarity. However, designing the combinationalfeature model creates high complexity for the manual selection
manner. Thirdly, the training features from the fixed training
data may lead to low feature accuracy because the fixed
training data cannot accurately represent the similar features

1057-7149 © 2013 IEEE

4810

IEEE TRANSACTIONS ON IMAGE PROCESSING, VOL. 22, NO. 12, DECEMBER 2013

for a specific class. Hence, to obtain the features that are
adaptive to different image classes is necessary to improve
the accuracy of the co-segmentation.
To obtain the adaptive features, we note that the common
objects in a simple image can be easily extracted by the figureground segmentation methods, such as object detection based
segmentation and saliency detection based segmentation. It isseen that these simple image segments can be used to learn
the features adaptable to each image group and thus increase
the accuracy of the co-segmentation. Furthermore, when theoriginal images are collected from various sources, certain
images will contain simple background images. Thus, thesimple image segments can provide adaptive training data for
accurate feature learning.
In this paper, we propose a feature adaptive image
co-segmentation method to improve the accuracy of the
co-segmentation when the similar features are unknown (firstreported in [27]). The simple image segments are used to learn
the adaptive features. The proposed method consists of four
steps. In the first step, we evaluate the image complexities
by the superpixel changing cue and the object detection cue.
We then select simple images and segment the initial segmentsby figure-ground segmentation method. In the third step, we
represent the features as a linear combination of the common
features, and we learn the linear combination parameters by
the EM based algorithm. In the last step, the common objects
are segmented according to the learned feature model. We test
the performance of the proposed co-segmentation method interms of error rate in different image groups. The results
demonstrate that the lower error rates can be obtained by the
proposed method.
The structure of this paper is organized as follows.
The related work is discussed in Section II. In Section III
and IV, we present the proposed co-segmentation method bydemonstrating the image complexity analysis, the adaptive
feature learning model and the final co-segmentation achievedby using the learned features. Section V and VI show theexperiment of the proposed method and the discussion of theresults. Finally, in Section VII, the conclusion is given.
II. R ELATED W ORK
Co-segmentation is usually modeled as an optimization
process with the consideration of the foregrounds similarity
constraints added into the single image segmentation models.
The MRF based co-segmentation method was first presented
by C. Rother et al. [9], which segmented common objects
through adding foreground similarity constraint into traditional
MRF based segmentation methods. 1-norm was used to represent the foreground similarity, and the co-segmentation energy
was minimized by trust region graph cuts (TRGC) method.
Based on Rother’s work, several MRF co-segmentation methods deal with the optimization problem using other constraints.
In the work of L. Mukherjee et al. [10], 1-norm was replacedby 2-norm and the Pseudo-Boolean optimization was used
for the minimization. Instead of penalizing foreground difference, D. S. Hochbaum and V. Singh [11] rewarded
the foreground similarity, which can result in the tractableenergy function optimization by graph-cuts algorithm. In [12],S. Vicente et al. modified Boykov-Jolly model as the foreground similarity measurement, and employed Dual Decomposition to minimize the energy function. Note that in these
co-segmentation methods, the common objects are assumed tocontain similar colors.
A. Joulin et al. [14] segmented common objects using
the clustering strategy, in which a classifier produced byspectral clustering technique and positive definite kernel wasused as a co-segmentation. The most discriminative classifier was then found as the final co-segmentation by solving
a continuous convex searching optimization problem. Bothcolor and SIFT features were used in this work. An interactive co-segmentation method was proposed in the work of
D. Batra et al. [15], which can segment common objects
through user interaction guided by an automatic recommendation system to correct the inconsistent segmentation. In [16],by observing that the rank of the matrix corresponding to theforeground regions still equals to one even if the common
objects contain the scale variants, L. Mukherjee et al. proposeda scale invariant co-segmentation method which intended tofind a matrix comprised of common objects with rank of one.
K. Chang et al. [17] designed a novel global energy term
to represent the foreground similarity and background consistency. Combined with the foreground potentials measured
by co-saliency model, the final energy function is submodular which can be minimized by the graph-cut algorithm.
S. Vicente et al. [18] presented an object co-segmentation
method to segment objects of interest. An off-line learning
method was used to select the discriminative features fromthe common features through random forest regressor, whichleads to the segmentation of only the interesting common
objects. G. Kim et al. in [19] used anisotropic heat diffusion
segmentation method to segment common objects of multiple
classes from a large scale of images group. In Kim’s work,
the common objects were assumed to contain similar colors,
which will result in unsuccessful co-segmentation when thecommon objects contain other similar features. Y. Chai et al.
in [25] proposed a Bi-level co-segmentation method (BiCoS)
for image classification. Chai’s method performs the Grabcuts
based segmentation with the initializations of the linear SVM
based class models and alternately updates the class models
and segmentation until convergence to achieve the image
segmentation and classification. Instead of sharing descriptor
at the level of individual pixels, Chai’s method shares a richer
descriptor at the level of superpixels stacked from multiple
general sub-descriptors which represent the superpixels’ color
distribution, SIFT distribution, size, location within the image,and shape. The use of the richer descriptor can improve theco-segmentation accuracy. However, the feature model in themethod in [25] reminds a combination of several existing
features and the features adaptive to each specific class groupis not discussed.
Recently, A. Joulin et al. [20] presented a multi-classco-segmentation method which extends the discriminative
clustering based co-segmentation [14] to segment the common objects of multiple image classes. Joulin designed a
new energy function which consists of spectral-clusteringMENG et al.: FEATURE ADAPTIVE CO-SEGMENTATION BY COMPLEXITY AWARENESS

term and discriminative term. The spectral-clustering term
can divide each image into visually and spatially consistentlabeled regions, and the discriminative term can maximize theclass separability in the image group. The energy function
can be finally optimized by using EM algorithm. In Joulin’s
work, the EM algorithm is to perform image segmentation,
where E-step estimates the label of each pixel, and the
M-step estimates the parameters of the discriminative classifier. Instead, in our method the EM algorithm is used for thefeature learning, where E-step estimates the confidence of theinitial segmentation, and the M-step estimates the parametersof the feature model. It is seen that the fixed features areused in the model in [14], while we use adaptive features formore accurate co-segmentation. The co-segmentation method
proposed by M. Collins et al. [21] adds foreground consistency into the random walker based segmentation method
which leads to a tractable energy minimization and speeds
up the co-segmentation algorithm compared with the MRF
based co-segmentation. J. Rubio et al. [22] segmented thecommon objects by proposing a new graph matching based
foreground similarity measurement and alternatively updating the saliency detection and the segmentation, which canenhance the co-segmentation accuracy. In [26], Meng et al.
used the graph theory to segment the common objects froma large scale image group. A digraph was constructed basedon the local region similarity and the co-saliency values.
The co-segmentation was then formulated as a shortest path
problem, which can be solved by using dynamic programming. In the methods discussed in this paragraph, the fixedfeatures are used to measure the foreground similarity forsuccessful co-segmentation, which will cause unsuccessful
co-segmentation when different common objects contain different types of similar features. Hence, in that situation,
features that can adapt to different image classes are needed
to improve the co-segmentation accuracy.
Another related work is the metric learning [28]–[32], whichaims to improve the performance of many applications bylearning more accurate distance metric. In general, an objectivefunction representing the consistency between the metric andthe training data is first defined. Then, the metric learning isformulated as maximizing the fitness between the metric andthe data to obtain the best distance metric according to evaluating the distance parameters. In general, Mahalanobis distance(d(x, y) = (x y)T A(x y)) with parameter A was usually usedas the basic distance. Other basic distance representation, suchas randomized binary trees, is also employed. The metriclearning has been widely used in many computer vision tasks,
such as image alignment [29], image classification [31], dataclustering, and face recognition. Nguyen et al. [29] introduced
metric learning in parameterized appearance model based
image alignment to overcome the local minima optimization
problem. The convex quadratic programming was used forthe metric learning. Eric Nowak et al. considered the domain
specific knowledge in the metric learning for accurate image
comparing [30]. This method rewarded the distinct knowledgeof the object in the metric learning in terms of a set of
randomized binary trees, which resulted in more accurate
object comparing. In the work of Nakul Verma et al. [31],4811

a hierarchy metric learning model rather than single metricleaning was proposed for the image classification. A set of
Mahalanobis distance metrics related to the class taxonomy
were trained in a probabilistic nearest-neighbor classification
framework. By representing metric in a hierarchal way, accurate distinct distance can be learned. Mensink et al. [32] usedmetric learning to enhance the Large-scale image annotation.
The Mahalanobis distance based metric was learned for bothk-NN classification and nearest class mean classifier used in
the image annotation. To consider the real-time learning in thelarge-scale datasets, a small fraction of the training data wereconsidered in each iteration by combing stochastic gradientdescend (SGD) algorithms and product quantization.
III. T HE P ROPOSED C O -S EGMENTATION M ETHOD
In the proposed method, we learn the adaptive features fromthe initial segments of simple images. We first select simple
images from the image group by image complexity analysis.
Then, we use the figure-ground segmentation to extract theinitial segments from the simple images, and learn the adaptive
feature model based on these segments. The learned featuremodel is finally used to achieve image co-segmentation.
The flowchart of the proposed co-segmentation method isshown in Figure 1, which consists of four steps, i.e., image
complexity analysis, simple image segmentation, adaptive feature learning, and co-segmentation.
A. Image Complexity Analysis
In our method, the simple image selection is to simplify the
initial object extraction. We can observe that the objects canbe easily segmented from the images with simple background,while it is usually difficult to extract the objects from thecomplex backgrounds. Hence, we define a simple image as
the image with homogenous background. On the contrary,
an image with complicated background is treated as complex
image. In this paper, the image complexity is measured by
two cues, i.e., the over-segmentation based image complexity
analysis and the object detection based image complexity
analysis.
1) Over-Segmentation Based Image Complexity Analysis:
It can be observed from the realistic images that the homogenous background contained in a simple image will keepa single local region in the edge based hierarchical oversegmentation, while a complicated background containing
many different appearances will be separated into many local
regions. We can see that the number of local regions of asimple image is small and stable in the hierarchical oversegmentation results. But a complex image will be assigned alarge number of local regions. Motivated by such observation,
we use the local regions number in the edge based hierarchicalover-segmentation to measure the image complexity. In themeasurement, the original image Ii , i = 1, · · · , Ni is firstover-segmented into local regions by the edge based oversegmentation method with different scales. Then, the sum of
local region numbers over all scales is counted as the score of
the measurement. For Ii , the score of the over-segmentation

4812

IEEE TRANSACTIONS ON IMAGE PROCESSING, VOL. 22, NO. 12, DECEMBER 2013

Fig. 1.

The flowchart of the proposed method.

based image complexity analysis Ci1 is calculated by
Ci1 =

K


n ik

(1)

k=1

where n ik is the number of the local regions in the k-th scale
over-segmentation, K is the number of scales. It is seen that
simple image will have small Ci1 . Otherwise, large values will
be assigned to the complex images. Based on Ci1 , we sort theimage complexity in ascending order and obtain the sorted
order ρ1 . Meanwhile, we record Ii by the position (η1i ) of Ii
in ρ1 and obtain η1 = {η11 , η12 , · · · , η1Ni }.
We use the method in [33]1 to obtain the hierarchicalimage over-segmentation. In the method [33], the oriented
watershed transform (OWT) is used to form the initial regions.
Then, the greedy graph-based region merging algorithm isused to construct the hierarchy of the regions. The hierarchyof the regions is finally treated as an Ultrametric Contour
Map (UCM). By setting different thresholds (the scale K ) on
the UCM, we can obtain a series of over segmentation results.
In this paper, we set K = 40, 50, 75, 100, 150 and 200 for
the hierarchical over-segmentation.
Fig. 2 shows the hierarchical over-segmentation results ofthree images, where the simple image (the top image) andthe complex images (the middle and bottom images) aredisplayed for comparison. The original images are shown in
the first column. The rest columns show the over-segmentation
results at different scales. The corresponding scales for thecolumns are represented above each column. The number ofthe local region for each over-segmentation result is shown
1 http://www.eecs.berkeley.edu/Research/Projects/CS/vision/grouping/resources.html

Fig. 2. The over segmentation results by the method in [33]. The firstcolumn: Original images. The rest columns: the segmentation results under
different K . The C 1 for three images are 50, 107 and 124 from first row tolast row, respectively.

below the over-segmentation result. It is seen that the sum
number of the local regions over all scales are 50, 107 and
124 from the top row to the bottom row, respectively. We cansee that the number of the simple image is obviously smaller
than the number of the complex image, which verifies thevalidity of the over-segmentation based image complexity
analysis. The sorted images by C 1 are shown in the top row ofFig. 4, where the top 12 simple images of Bottles are shown.
We can see that simple images can be selected by the oversegmentation based image complexity analysis.
2) Object Detection Based Image Complexity Analysis: It isobserved that the simple images usually contain single object,while the complex images include many objects, especially theobjects in the backgrounds. By performing the object detection
method on the simple images, the detected windows will focus
on the object, and result in the compact detection. But forcomplex images, the detections will locate on different objects,
and result in dispersive detection. To clearly illustrate this

MENG et al.: FEATURE ADAPTIVE CO-SEGMENTATION BY COMPLEXITY AWARENESS

Fig. 3. The detection results of the simple images and the complex imagesin [34]. (a)-(c): the detection results of simple images. (d)-(f): the detection
results of complex images.

observation, we show some detection results in Fig. 3, where
the results of the simple images and the complex images areshown in Fig. 3 (a)-(c) and Fig. 3 (d)-(f), respectively. It canbe seen that compact windows are obtained from the simple
images, such as the apple logo with a simple blue background.
Meanwhile, the scatter windows are detected in the complex
images, such as ducks under the tree.
We use the scatter degree to evaluate the image complexities. We first perform a sliding window based object detection
method in each image Ii . The best Nw windows are selected
for the complexity measurement. Then, we represent eachwindow as a binary matrix Mi , i = 1, · · · , Nw , where the sizeof the matrix is same to the size of the image, and the pixels
within the window have value one and zero for the pixels
outside the window. Next, we
compute M by summing up
Nw
all binary matrixes, i.e., M = k=1
Mk , 0 ≤ M( j, l) ≤ Nw .
The complexity of the image Ii is then measured by( j,l) π(M( j, l), Tw )( j,l) π(M( j, l), 1)2−(2)
Ci = 
( j,l) π(M( j, l), 1)( j,l) π(M( j, l), 0)

whereπ(a, b) =1
0

if a ≥ belse(3)

It can be seen that there are two terms included in (2). The firstterm is to evaluate the scatter of the detection by measuring
the ratio of the overlapped regions to the whole detected
region. It prefers a large value when most overlapped regions
focus on an object. In order to avoid the influence of theunsuccessful detections in the complex images, where mostof the backgrounds are detected and included in the windows,
we introduce the second term by measuring the ratio of thearea of the detection region to the whole image region. It isseen that the unsuccessful detections will have low scores by
the second term. We sort Ci2 in descending order and obtain thesorted order ρ2 . We also record each image Ii by the positionNof the image η2i in ρ2 and obtain η2 = {η21 , η22 , · · · , η2 i }.
2
The method in [34] is used as the object detection. We set
Nw = 10 and Tw = 8 for all image groups. In Fig. 3, we also
display Ci2 for each image. The values Ci2 are shown below
each image. It is seen that the simple images have larger C 2
2 http://groups.inf.ed.ac.uk/calvin/objectness/

4813

than the values of the complex images, which demonstrates
that the object detection based image complexity analysis candescribe the complexities of these images. The sorted images
based on the object detection based analysis method are shownin the middle row of Fig. 4, which shows the successful
selection of the simple images by the object detection based
image complexity analysis.
3) Combination of Image Analysis Methods: We combine
the above two cues to obtain more accurate image ranking.
We believe that the image Ii tends to be a simple image whenthe values of η1i and η2i are both small. Thus, we first represent
each image Ii by
ηi = η1i + η2i(4)where ηi is the sum of the rankings measured by the twocomplexity analysis cues. Then, the final sorted order isobtained by sorting ηi in ascending order. The final sorted
images of Bottles are shown in the bottom row of Fig. 4.
Compared with the results in the top row and the middle row,
we can see the more accurate sorting by the combined method.
B. Object Extraction from Simple Image
Based on the image complexity analysis, we select the
top m simple images, and segment the initial segments
Q = {Q 1 , Q 2 , · · · , Q m } from these simple images using
figure-ground segmentation method. In this paper, we use thesaliency extraction based object segmentation method [35]3 toobtain the initial segments.
IV. F EATURE L EARNING
After initial segment generation, we next learn the adaptive
features of the class. Here, we consider two requirements in thelearning. Firstly, some unsuccessful segments may be obtainedin the above initial object extraction step, which can interfere
the feature learning and result in the inaccurate feature model.
We need to avoid these interferences in the learning. Secondly,
the learned feature model must fit the initial segment data verywell.
A. Feature ModelIn our method, the similarity between two initial segments
Q i and Q j is measured by a linear feature model, i.e., a linear
combination of the general region features. Assuming there
are n general features, such as the features of color, shape andtexture, we evaluate the similarity si j between two segments
Q i and Q j by
ij

ij

ij

si j = ω1 (1 − x 1 ) + ω2 (1 − x 2 ) + · · · + ωn (1 − x n )

(5)

ij
xk

j
= d( f ki , fk ) is the distance between the k-thwherejfeatures ( f ki and f k ) of the segments Q i and Q j , fki denotes
the k-th general feature of Q i , ω1 , · · · , ωn are the weighting

coefficients of the features. In our method, we use five features
such as color histogram, inner shape descriptor [36], SIFT
descriptor [37], [38], self-similarity descriptor [39] and pHOG
descriptor [40] as the general features. Chi-square distance is
3 http://cg.cs.tsinghua.edu.cn/people/∼cmm/Saliency/Index.html

4814

IEEE TRANSACTIONS ON IMAGE PROCESSING, VOL. 22, NO. 12, DECEMBER 2013

Fig. 4. The ranking of images using the proposed method. The top row: the ranking by the over-segmentation based image complexity analysis. The middle
row: the ranking by the object detection based image complexity analysis. The bottom row: the final ranking by the proposed method.

used as the feature similarity evaluation. From (5), we can see
ijjthat x k is calculated only by the k-th features, i.e., f ki and f k .
The measurement of the feature distance is only performed by
the same feature types. Hence, the model is available although
the dimensions of different type of features are not equal toeach other.
Setting parameters θ = (ω1 , ω2 , · · · , ωn )T and⎛ i1 i1⎞x 1 x 2 · · · x ni1⎜ i2 i2⎟⎜ x x · · · x im ⎟
n
1
2
⎜
⎟
Xi = E − ⎜ .
(6).. .. .. ⎟⎝ ..
. . . ⎠
x 1im x 2im · · · x nim
i = 1, · · ·, m, we obtain

Our goal is to find the parameter θ of the feature modelthat best fits the training data X and also discover theconfidences of the initial segments to discard the bad segments. We achieve our goal in the probability framework.
We set X i as the observed data corresponding to the initial
segment Q i . The unknown segmentation confidences for the
initial segments are denoted by the unobserved latent variables
Z = {z 1 , z 2 , · · · , z m } where z i is the segmentation confidenceof the segment Q i . The complete data set is denoted by {X, Z }.
The goal is to find the maximum posteriori estimation of θ and
Z given X, which can be represented byθ̂ M A P = arg max p(θ |X) = arg max p(X|θ ) · p(θ )
θ∈

θ∈

m

S(X 1 , · · · , X m , θ )= (s11 , · · · , s1m , s21 , · · · , s2m , · · · sm1 , · · · , smm )T⎞⎛X1⎜ X2 ⎟⎟⎜= ⎜ . ⎟ θ = Xθ⎝ .. ⎠Xmp(X i , z i |θ )dz i · p(θ )= arg maxθ∈

(7)

where E is a matrix with all elements 1.
Assuming initial segments are accurately segmented fromthe simple images, the distance between any pair of theinitial segments approximately equals to 0. Hence, the target
matrix S  of S is a m 2 × 1 vector with all elements one.
However, the feature self-similarities cannot provide usefuldiscriminative information to distinguish the useful featuresfrom the other features. Furthermore, the feature learning
is based on the feature similarities. The self-similarities of
unsuccessful segmentation will interfere the feature learningand result in inaccurate feature model. Hence, we do notconsider the self-similarities, and set the values corresponding
to the self-similarities to 0 in X and S  such as the i -th row
in X i and the ((i − 1)m + i )-th element in S  , i = 1, · · ·, m.
Then, the parameters θ of the feature model that best fits X
can be calculated byarg min S−S  22 +α·θ 1 = arg min Xθ −S  22 +α·θ 1 (8)θ

B. Parameters Learningθ

where α is the scale factor. However, there may have unsuccessful initial segments. Next, we learn the feature parameters
by considering these bad segments.

(9)

i=1

We solve the problem in (9) by the EM algorithm whichseeks to find the MAP iteratively applying the following
two steps: E-step and M-step. In E-step, we generate theexpectation Q(θ, θ old ) of the complete-data evaluated using
the observed data X and the current parameter θ old , which isrepresented as
Q(θ, θ old )m=p(z i |X i , θ old ) ln p(X i , z i |θ )dz i + ln p(θ ) (10)i=1

In M-step, the parameter θ new is updated by maximizing
the expectation Q(θ, θ old ), which can be represented byθ new = arg max Q(θ, θ old )θ

(11)The E-step and M-step are iterated alternately until the convergence of θ and Z . In what follows, we detail the calculationof p(θ ), p(z i |X i , θ old ), p(X i , z i |θ ), respectively.
1) The Distribution of p(θ ): From (8), we can see thatthe model is designed to be a sparse representation sinceθ 1 is minimized. A value of θ with small θ 1 refers tolarge probability. Otherwise, a small probability will be given.
Hence, we set p(θ ) asp(θ ) =

1
exp−αθ1Nθ

where Nθ is the normalized constant.

(12)

MENG et al.: FEATURE ADAPTIVE CO-SEGMENTATION BY COMPLEXITY AWARENESS

2) The Posterior Distribution of p(z i |X i , θ old ): Given theobserved data X i of the segment Q i and feature model parameters θ old , the similarities between Q i and other segments
τi = (τi (1), · · · , τi (m))T can be obtained by
τi = X i θoldX i θ old 1
, 1)
N1

(14)

where N1 are the normalized constants. We set
N1 = maxi X i θ old 1 , i = 1, · · · , m.
3) The Posterior Distribution of p(X i , z i |θ ): In our model,
we assume that θ independents to Z . Given a feature model
parameter θ , we can measure p(X i , z i |θ ) = p(z i ) p(X i |θ, z i )by two terms, i.e., p(z i ) and p(X i |θ, z i ).
a) p(X i |z i , θ ): In our model, we measure p(X i |z i , θ ) by
the fitness between the observed data corresponding to X i andz i and the target matrix related to z i and θ . A large p(X i |z i , θ )prefers a good fitness. Otherwise, a small p(X i |z i , θ ) will beassigned.
Given z i , we train our model by only considering the goodsegment Q i with large z i . Two data adjustments are used to
select the good segment. The first is to adjust the data X i
according to Z . The j -th data row of X i with large z j need
to be selected. Otherwise, the data row should be abandoned.
We achieve the adjustment by multiplying the values of k-th
row of X i by z i , i.e.,
X inew =and⎛zi X i0···min(z 1 , z i )
⎜
0
min(z
,
z
)
···
2
i
⎜
..
..
..
zi = ⎜
⎝
.
.
.
0

0

to be retained and approximately equal to 1. For unsuccessful
segment pairs, the corresponding target value should be close
to 0. In our method, we adjust S  bySi =(13)

Since the initial segments are obtained from the simple
images, most of the initial segments can be considered as
successful segments. It is seen that a successful segmentation
will be similar to most of the segments and have large
sum of the similarities, i.e., a large value of X i θ old 1 .
Otherwise, unsuccessful segmentation refers to a small valueof X i θ old 1 . We can see that p(z i |X i , θ old ) is related toX i θ old 1 , and we set p(z i |X i , θ old ) asp(z i |X i , θ old ) = N (

4815

(15)

0
0
..
.

⎞
⎟
⎟
⎟
⎠

· · · min(z m , z i )where X inew is the adjusted observed data for Q i . The value
min(z k , z i ) represents the confidence of a pair of segments(Q k , Q i ). Here, these z k , k = i are considered as fixed values
for X i . It is seen that the confidence of a pair of segments Q k
and Q i is represented by the smaller confidence of z k and z i ,since we believe that the value referring to any bad segment
should be abandoned. Hence, by multiplying min(z k , z i ), thedata in X i corresponding to the successful segment pairs will
be retained, while the date of the unsuccessful segmentation
pairs tends to be zeros and to be abandoned.
We next adjust the target Si with respect to Z . The original
target vector is m × 1 vector Si = (1, 1, · · · , 0, · · · , 1)T with
only one zero element Si (i ) = 0. Similar to observed data X i ,the target value corresponding to a pair of good segments need(17)

where Si is the adjusted target vector. We can see that theobserved data of the successful segment pairs has the valueSi (k) that is close to one. For the unsuccessful segment, Si (k)tends to be zero.
Based on X inew and S  , the fitness between X i , θ and latentvariable z i is evaluated by
i (X inew , θ, z i ) = X inew θ − Si 22 = zi X i θ − 2
z i Si 2(18)

where i (X inew , θ, z i ) (use i for short) is the loss function measuring the difference between the similarity matrix
z i X i θ and the target similarity matrix Si . A good fitness
newprefers small i . Based on i (X i , θ, z i ), we formulatep(X i |θ, z i ) asp(X i |θ, z i ) =1
exp(−i (X inew , θ, z i ))
Nx

(19)

and Nx is the normalized constant.
b) The distribution of p(z i ): Since the initial segments
are obtained from the simple images, we believe that most of
the initial segments are successfully segmented. Hence, z i ≈ 1
for most of segments. In our method, we set p(z i ) asp(z i ) =1exp(−β|1 − z i |)
Nz

(20)

with the normalized constant Nz .
c) The distribution of p(X i , z i |θ ): Based on the distribution of p(X i |θ, z i ) and p(z i ) above, p(X i , z i |θ ) can be
represented byp(X i , z i |θ ) =(16)

z i Si1exp(−(X inew , θ, z i ) − β|1 − z i |) (21)
N x Nz4) The Minimization of the Expectation Q: By (14) and(21), Q in(10) can be represented as
Q(θ, θ old )m=p(z i |X i , θ old ) ln p(X i , z i |θ )dz i + ln p(θ )
i=1

=

m


[− ln(Nx Nz ) −p(z i |X i , θ old )i dz i

(22)

i=1

−

p(z i |X i , θ old )β(|1 − z i |)dz i ] − γ θ 1where γ = Nαθ . The derivation of (22) can be found in the
appendix. It is seen from (22) that only p(z i |X i , θ old )i dz iand γ θ 1 are related to θ . Hence, maximizing Q in
M-step (11) with respect to θ changes to solve the following

4816

IEEE TRANSACTIONS ON IMAGE PROCESSING, VOL. 22, NO. 12, DECEMBER 2013minimization problem, i.e.,θ

Algorithm 1 The Algorithm for EM Based Feature Learning
Methodnew= arg maxθ= arg maxθm

− p(z i |X i , θ old )i dz i − γ θ 1

i=1
m


zi X i θ −− p(z i |X i , θ old )

 2
z i (X i θ − Si )2 dz ii=1−γ θ 1m
= arg maxθ

i=1−γ θ 1m
= arg max

− p(z i |X i , θ old )(X i θ − Si )Tθ

i=1(X i θ − Si )dz i − γ θ 1m= arg max−(X i θ − Si )Tθ
i=1(X i θ − Si ) − γ θ 1m= arg max−(X i θ − Si )T
θ
i=1
m


= arg max −θ= arg min Xθ 2
z i Si 2 dz i

− p(z i |X i , θ old )



i=1
new

ui X i θ −

p(z i |X i , θ old )

T
ui

T
zi

zi

T
zi

z i dz iu i (X i θ − Si ) − γ θ 1

 2
u i Si )2 − γ θ 1

θ − S )22 + γ θ 1

(23)

T
where
=
p(z i |X i , θ old ) Tzi zi dz i , X new =
ui ui
new
T
new
T
 )T , · · · , (S  )T )T((X u1 ) , · · · , (X um ) )T , and S  = ((Su1um
are the adjusted data of X and S based on u i . It is seen thatthe problem in (23) is a l1-Regularized Least Squares problem.
We use the method in [41]4 for the minimization.
5) Implementation: The E-step and M-step are iteratively
executed until the convergence. We can see from (23) that zi
consists of m different matrixes over all z i . Hence, u i can becalculated by the sum of these piecewise matrixes combinedwith cumulative distribution function of Gaussian distribution (byp(z i |X i , θ old )dz i ). For simplicity, we directlyolduse zi , z i = X i Nθ 1 1 to approximate u i , i.e., X new =new )T )T , and S  = ((S  )T , · · · , (S  )T )T((X 1new )T , · · · , (X mm1
to reduce the computational cost. We set the iteration number(the stop number is 50) as the EM stop condition. We set
m = 10 for the simple image selection. In (23), γ = 0.01.
Note that these parameters are fixed among different image
datasets. The algorithm of the proposed learning method isshown in Algorithm 1.

C. Co-Segmentation
Based on the learned feature model, we use our previous
work in [26] to achieve the co-segmentation task. In themethod, the original images are segmented into over-lapping
local regions using object detection method, saliency detection
method and hierarchy over-segmentation method. Then, thesimilarities between the local regions are represented by a
4 http://www.stanford.edu/∼boyd/l1_ls/

directed graph structure. The co-segmentation is formulated asa shortest path searching problem and is solved by dynamic
programming.
Several improvements are used to achieve adaptive feature learning based co-segmentation. Firstly, in edge weightcalculation, we calculate the region term by the learned
feature model rather than the original features. Secondly, theinitial segments referring to large confidences are used as the
co-segmentation results. The co-segmentation result is thentreated as the only local region of the related image in theprocess of the digraph construction.
V. E XPERIMENTAL R ESULTS
In this section, we verify the proposed co-segmentation
method on many images groups. The subjective and objective
assessments of the segmentation results are given.
A. Co-Segmentation Results
1) Test Images Dataset: In the experiments, we collectimage groups from well-known image databases such as
MSRC database [42],5 ETHZ shape database [43],6 andICoseg database [15]7. We select 16 classes among the total
20 classes in MSRC dataset and the classes that have morethan 20 images in ICoseg dataset for the verification. The total
five classes in ETHZ shape database are all used. To completely verify our method, we use all images in each class.
We use the ground truth given by [15] and [42] for the ICoseg
5 http://research.microsoft.com/en-us/um/people/antcrim/data_objrec/
msrc_objcategimagedatabase_v2.zip
6 http://www.vision.ee.ethz.ch/∼calvin/ethz_shape_classes_v12.tgz
7 http://chenlab.ece.cornell.edu/projects/touch-coseg/CMU_Cornell_iCoseg_dataset.zip

MENG et al.: FEATURE ADAPTIVE CO-SEGMENTATION BY COMPLEXITY AWARENESS

4817

Fig. 5. The segmentation results of the proposed method. From top to bottom: the rows 1, 3, 5, 7 and 9 show the original images. The rows 2, 4, 6, 8 and
10 display the segmentation results.

and the MSRC database, respectively. For ETHZ shape dataset,
we obtain the ground truth by the contour based ground truthin [43].
2) The Co-Segmentation Results: The co-segmentation
results of ten classes are shown in Fig. 5. For each image
class, six original images and the co-segmentation results arepresented. From Fig. 5, we can see that the original images
have many variations, such as color, shape and texture. It isalso seen that the proposed co-segmentation method successfully segments the common objects from these images. For
example, the ‘cats’ in Cats vary significantly. The proposedco-segmentation method successfully segments these ‘cats’,
which benefits from the adaptive feature learning.
We also show the results of the feature learning method.
The confidences of the initial segments are shown in Fig. 6(a),where the results of six classes are shown. For each class, theoriginal images are shown in the first row. These images are
selected by the proposed image complexity analysis method.
We can see that simple images can be selected by the proposed
method. The initial segments obtained by the unsupervised
segmentation method are shown in the second row. It is seenthat most of the objects can be successfully segmented fromthe simple images. Meanwhile, there are a few unsuccessful
segments, such as the second image in Cheetah and the fifth
image in Mugs. The learned confidence of each initial segment
is shown below the image. It can be seen that the learned
confidences fit the human judgments. For example, in Mugs,
the fifth initial segment is the unsuccessful segmentation.
The learned confidence is small (0.0869). Meanwhile, for the
first segment which is a successful segmentation, the learned
confidence is close to one (0.9634).

Furthermore, the learned feature model corresponding to theclasses in Fig. 6(a) are shown in Fig. 6(b). Each feature modelis represented by a color-bar, where each color describes a general feature. These colors represent the features of color, shape,
SIFT, Self-similarity and pHog from left to right, respectively.
The amplitude of each color represents the learned weight
coefficient of the corresponding feature. We can see that thelearned feature model can represent the similarities between
the objects. For example, the class Mugs contains similar
shape. The weight coefficient of the shape feature is large inthe learned model, which indicates that the shape feature plays
an important role in the foreground similarity measurement.
For the class Bear, the weight coefficient of color is large,
which fulfills the fact that the ‘bears’ contain similar colors.
B. Objective Evaluation
We evaluate the proposed co-segmentation method by theerror rate which is defined as the ratio of the number ofwrongly segmented pixels to the total number of pixels.
A small error rate refers to a successful segmentation.
The mean error rate over all images is used to evaluate
the performance of a class. The error rates of the proposedco-segmentation method are shown in Table II. We can seethat the proposed co-segmentation method achieves low error
rates in most of the classes. It is also seen that there areunsuccessful segments, such as Panda and Stonehenge. The
unsuccessful segments are caused by the fact that there are no
simple images in these classes. The complex images lead tounsuccessful initial segments and further result in inaccurate
learning of the feature model.

4818

IEEE TRANSACTIONS ON IMAGE PROCESSING, VOL. 22, NO. 12, DECEMBER 2013

Fig. 6. (a): The confidences of initial segments. For each block, the first row shows the simple images obtained by complexity analysis. The second row shows
the initial segments obtained by method in [35]. The confidences obtained by the proposed learning method are shown under the images. (b): The learned
feature models corresponding to the classes in (a). The color in the model represents the features. They are color, shape, SIFT, Self-similarity and pHog fromleft to right respectively.

In Table II, we also compare our method with theexisting co-segmentation methods such as the methods in[14], [19] and [26]. Joulin et al. in [14] proposed aco-segmentation model using the discriminative clustering
method and the spectral clustering method. In the experiment,
the source code given by the authors8 is used. To improve theco-segmentation results, we adjust the parameter μ for eachclass. Color feature (for ICoseg dataset and ETHZ dataset)and SIFT feature (for MSRC dataset) suggested by the author
are employed. The superpixels are generated by the oversegmentation method in [33] (by setting k = 100). The results
referring to the method in [14] are shown in the second
row of Table II. It is seen that the common objects are
successfully segmented from several classes, such as Liberty
and Airshows2. Meanwhile, there are unsuccessful segments,
such as Cheetah and Pandas. The unsuccessful segments arecaused by the fact that the classes contain different similarfeatures.
Kim et al. in [19] propose multiple class co-segmentation
method, which is achieved by the linear anisotropic diffusion
based segmentation method. Color feature is used. In the
8 www.di.ens.fr/∼joulin

experiment, the code released by the author is used9 . The intraimage Gaussian weights and the number of segments (K )are adjusted for accurate co-segmentation. The results by
the method in [19] are shown in the third row of Table II.
We can see that Kim’s method can successfully segmentcommon objects in several classes, such as Liverpool and
Goose. Meanwhile, unsuccessful segments are also achieved,
such as Dogs and Chairs. The unsuccessful segmentations arecaused by the fact that many classes contain other similarfeatures rather than color.
Meng et al. in [26] achieves common objects segmentation by graph theory. The co-segmentation is formulated as
the shortest path searching, and the shortest path is foundby dynamic programming. In the experiment, we adjust thescaling parameter α for each classes to achieve accurate
co-segmentation. We use color feature for ICoseg dataset and
MSRC dataset and shape feature for ETHZ dataset. The resultsby the method in [26] are shown in the fourth row of Table II.
We can see that the method in [26] can successfully extractcommon objects from several images, such as Soccer andKite1. Meanwhile, there are unsuccessful segments, such as
9 http://www.cs.cmu.edu/∼gunhee

MENG et al.: FEATURE ADAPTIVE CO-SEGMENTATION BY COMPLEXITY AWARENESS

4819

TABLE IIR ESULTS C OMPARISON B ETWEEN THE P ROPOSED C O -S EGMENTATION M ETHOD AND THE E XISTING M ETHODS IN T ERMS OF E RROR R ATE .
C LASSES IN ICoseg, MSRC AND ETHZ D ATASETS A RE U SED

Cats and Cheetah. These unsuccessful segments are mainly
caused by the fact that the given features cannot fully represent
the similarities between the common objects.
The comparison results show that the proposedco-segmentation method achieves the lowest error rates
for most of the image pairs. For ICoseg dataset, the meanerror rates over all classes are 0.2484, 0.2065, 0.1397 and0.1245 for the methods in [14], [19], [26] and the proposed
method, respectively. We can see that the proposed method
achieves the smallest error rate. It is also seen that the othercomparison methods achieve good performance in the ICoseg
dataset, since the common objects contain similar colors in
the ICoseg dataset. For MSRC dataset, the mean error rates
over all classes are 0.3560, 0.3145, 0.2720 and 0.2200 for
the methods in [14], [19], [26] and the proposed method,respectively. It is seen that the error rates are obviously
decreased by the proposed method which is caused by theadaptive learning of the feature model. For ETHZ dataset,the mean error rates are 0.2093, 0.4470, 0.1216 and 0.1263
for the method in [14], [19], [26] and the proposed method,respectively. We can see that the method in [26] achieves
the smallest error rate in this dataset. The reason is thatthe shape feature can accurately represent common objects
similarity for the classes. By using the shape feature, themethod in [26] can achieve accurate co-segmentation. Notethat the differences between the method in [26] and the

proposed method are small (the difference is 0.0047). Hence,the performance of the proposed method is comparable tothe method in [26] in ETHZ dataset. The error rates over allclasses are 0.2920, 0.2902, 0.1976 and 0.1684 for the methodsin [14], [19], [26] and the proposed method, respectively. It isseen that the proposed method achieves the smallest errorrate, which demonstrates the effectiveness of the proposed
method.
To further verify our proposed method, we display the
results of the initial segment method [35] in Table II.
The method in [35] is to first detect the saliency regions
by global contrast and then perform grab-cuts to obtain thesalient regions. It focuses on the salient regions in each single
image instead of the common objects in multiple images.
From Table II, we can see that the method in [35] can obtain
successful object segmentation in some classes, such as Air1
and Planes. The reason is that the salient objects in theseclasses are also the common objects. When the images containother multiple salient regions, these salient regions may be also
obtained by the method in [35], such as “Logos” and “Dogs”,
which results in unsuccessful segmentation. It is also seen from
Table II that the mean error rate (0.1684) of the proposed
method is smaller than the one (0.1918) in the method [35].
We also show the results of the proposed method byselecting different number of simple images m on the threedatasets. We show the results in Fig. 7, where the results of the4820

IEEE TRANSACTIONS ON IMAGE PROCESSING, VOL. 22, NO. 12, DECEMBER 2013

Fig. 7. The results of the proposed with different m. The three datasets(ICoseg, MSRC and ETHZ) and seven m values (m = 4, 8, 12, 16, 20,
24 and 28) are shown.

three datasets (ICoseg, MSRC and ETHZ) and seven m values(m = 4, 8, 12, 16, 20, 24 and 28) are displayed. We can see that
small error rates can be obtained when m ∈ [10, 22] for the
ICoseg and MSRC datasets. Meanwhile, the small and large
m can result in the increase of the error rates. The reason isthat a small m may not provide enough initial segments for theaccurate feature learning, while a large m can introduce moresegment noises to interfere the feature learning. Note that theerror rates of ETHZ dataset decrease along the considered m.
The reason is that the number of the images in the ETHZ
classes is large (about average 50 image per class), whichleads to a larger m to obtain the small error rates. In our
experiments, we set m = 10 by considering the small error
rate and the low computational cost of the learning.
VI. D ISCUSSION
We first discuss the motivation of using simple images tolearn the feature model. It is known that the success of a learning scheme is directly associated with an appropriate input data
selection [44]. Inaccurate learning will be obtained when the
training samples contain many wrong samples. The proposed
method adaptively learns the useful features for accurate
co-segmentation. In the feature learning, the accurate learning
depends on the accuracy of the initial segments. Successful
segments can provide useful information to accurately learn
the feature model. On the contrary, unsuccessful segments
will interfere the feature learning and lead to inaccuratefeature model. Hence, it is required to accurately extract theinitial objects as much as possible. As we known, extracting
the objects from the simple image is much easier than thecomplex image, which guarantees the requirement of our
feature learning. This property motivates us to use the image
analysis to select the simple images to achieve the initial
segmentation. For the complex images, we believe that thefeature learning will be difficult from the complex images
because many unsuccessful segments will be generated andused in the feature learning. These incorrect training samples
will result in inaccurate learning of the feature model and leadto unsuccessful co-segmentation.
We next discuss the generalization of the proposed model.
In order to guarantee the fairness of the comparison, allparameters and the general features used in the feature learning
are fixed for different datasets in our experiments. Meanwhile,

the original feature pool contains much type of features, suchas the color, texture and shape. These features are usuallyshared by most of the common objects in the realistic images.
Hence, the feature learning method can be generalized toother datasets. We verify the generalization of the proposed
method on other different image datasets, such as CaltechUCSD Birds 200-2011 dataset, Stanford Dogs, and Oxford
Flowers 102. The segmentation results and the error rates
are shown in Fig. 8 and Table III, respectively. It is seenthat the proposed method can be successfully generalized tothese image classes. Furthermore, we verify the generalizationof the learned feature model in Caltech 101 datasets. In theexperiments, we use the feature model learned from MSRC orETHZ to implement the co-segmentation on the same class in
the Caltech 101 dataset. The segmentation results and error
rates are shown in Fig. 9 and Table III, respectively. The
results of Mugs and Aeroplanes are displayed. We can seethat the learned feature model also achieves successfully cosegmentation on a new dataset. The reason is that the imagesof a class tend to contain the same similar features in different
datasets. The feature model learned from a image group canalso be used to achieve co-segmentation in the other imagegroups. The results of the methods in [14], [19] and [26]are also proposed in Table III for comparison. It is seen thatthe proposed method can also achieve the lowest error rates
on most of the classes shown in Table III, which demonstrates that the proposed method can be generalized to otherdatasets.
In our method, we use the method in [34] to detect thewindows, where the initial windows are generated by sliding
windows at many scales. Different sizes of windows are
generated and are uniformly distributed over the entire image.
In the detection, each initial window is first scored basedon four cues, such as saliency, color contrast, edge density
and superpixels straddling. The best top Nw windows arethen selected for the image complexity analysis based on thescores. After windows selection, the overlap regions among theselected windows are extracted using threshold Tw . We can seethat the choices of Nw and Tw mainly depend on the scoresof the windows instead of the window size.
In our method, we impose the sparsity constrain on the θas shown in (8). The existing sparsity constrains usually usedin the sparse representation, such as 1-norm [45], 2-normand elastic net formulation [46] can be used as the constrain.
In our model, 1-norm is selected based on its natural toobtain both the shrinkage and the variable selection in the
regression [46]. Also, the 1-norm has been successfully usedin many computer vision tasks compared with l2-norm, suchas face recognition [47]. Moreover, compared with elastic net
formulation, 1-norm can sufficiently represent the sparsity
here, since we intend to select one or small number of features
to represent the foreground similarities.
It is seen from (5) that we use a linear model to learn theadaptive feature. The reason is that linear model is simple
and can lead to the easy parameters estimation of the model.
The other and also the most important reason is that thelinear model is able to capture the foreground similarity
consistency. As our method is based on the assumption of

MENG et al.: FEATURE ADAPTIVE CO-SEGMENTATION BY COMPLEXITY AWARENESS

4821

Fig. 8. The results of the proposed method on the other datasets. (a): Caltech-UCSD Birds 200-2011 dataset. (b): Stanford Dogs dataset. (c): Oxford Flowers
102 dataset.

Fig. 9. The segmentation results by generalizing the learned model to the other image datasets. The classes Aeroplanes and Mugs in Caltech 101 dataset areused. The feature models learned in MSRC datasets (Aeroplanes) and ETHZ shape datasets (Mugs) are used for the co-segmentation in the Caltech classes.
TABLE IIIT HE E RROR R ATE ON THE O THER D ATASETS W ITH THE S AME PARAMETERS , S UCH A S C ALTECH -UCSD B IRDS 200-2011 D ATASET (Black AND
Laysan), S TANFORD D OGS (Maltese AND coonhound), O XFORD F LOWERS 102 (Petunia AND Barbeton) AND C ALTECH 101 (Mugs AND Aeroplanes).
T HE R ESULTS OF THE M ETHODS IN [14], [19] AND [26] A RE ALSO P ROPOSED FOR C OMPARISON

the sparsity of the features, it is seen that selecting single
feature or linearly combing a few of features as used in
our linear model is enough to represent the sparsity of thefeatures. Note that non-linear feature selection methods, suchas kernel based support vector regression [48] and kernel
based logistic LASSO regression [49], can also be used in
our feature learning. Since the linear model is a specific caseof the no-linear model, the no-linear model may result inbetter co-segmentation results. Meanwhile, it also leads tomore complex analytical and computational properties thanthe linear model [50]. Hence, linear model is selected in
our method.
In our method, the successful feature learning depends
on the accuracy of the initial segmentation, as discussion
in Section VI. Successful initial segmentation will result in
accurate feature learning, while incorrect feature model can belearned from the wrong initial segments. To achieve accuratefeature learning, we combine the image complexity evaluationand the saliency based foreground extraction ( [35]). It is notedthat although it is still difficult to extract the saliency regions

from complex scenes, the object foregrounds can fortunately
be well extracted from the simple backgrounds by the saliency
detection method (such as [35]), which can help the initial
segmentation of the common objects.
In the feature learning, we introduce the segmentation
confidence to select the success of a segment for the featurelearning. The segments with large confidences are used tolearn the feature model. Furthermore, we directly use thesesegments as the co-segmentation results of the corresponding
image for simplicity. Hence, some of these results in Fig. 6 areshown as the final results in Fig. 5. Note that these segments
will not be cosegmented in the following co-segmentation.
For the selected images with small confidences in Fig. 6, they
are the bad initial segments and are not used in the featurelearning. Hence, we return these images to the rest imagegroup and perform the co-segmentation to obtain the accurate
object extraction.
The proposed method and the method in [26] all require
the similar features to generate the edge weights in the graphconstruction. The indeed different is that we automatically4822

IEEE TRANSACTIONS ON IMAGE PROCESSING, VOL. 22, NO. 12, DECEMBER 2013

learn the similar features, while the method in [26] manually
selects the feature for each class [26]. Compared with manual
selecting manner in [26], our model can easily handle morefeatures (5 features) and learn the best feature combinations(by linear model), which results in the improvement of the
co-segmentation as shown in Table II. But the improvement is
not significant, since the manual selection can also select thesimilar feature of each class. However, compares with [26],our method is more reasonable due to the automatic featurelearning by the computer and the wide applications in realistic
computer vision tasks.
VII. C ONCLUSION
In this paper, we proposed a new feature adaptive cosegmentation model to segment common objects from multiple
images. We proposed a new image complexity analysis method
to rank the images and extract the objects from the simple
images by using unsupervised segmentation method. An accurate feature model is learned from the objects by using an EM
algorithm combining l1-regularized least squares optimization.
The feature model is combined with the initial segmentation to
extract the common objects. The experiments demonstrate thatthe error rate of the proposed method is lower than the existing
methods when the feature is unknown. In the future, we will
extend the proposed feature learning method for images withhigh complexity and nonlinear model.
A PPENDIX A
T HE D ERIVATIONS OF THE E QUATION (22)Q=m
p(z i |X i , θ old ) ln p(X i , z i |θ )dz i + ln p(θ )

i=1

=

m


[

p(z i |X i , θ old )(− ln(Nx Nz ) − i − β|1 − z i |)dz i ]

i=1

α
θ 1
Nθ
m

=
[− ln(Nx Nz ) −−p(z i |X i , θ old )i dz i

i=1−p(z i |X i , θ old )β(|1 − z i |)dz i ] −

α
θ 1
Nθ

(24)

R EFERENCES[1] H. Li and K. N. Ngan, “Unsupervised video segmentation with low depthof field,” IEEE Trans. Circuits Syst. Video Technol., vol. 17, no. 12,
pp. 1742–1751, Dec. 2007.
[2] N. Jacobson, Y.-L. Lee, V. Mahadevan, N. Vasconcelos, and T. Nguyen,“A novel approach to FRUC using discriminant saliency andframe segmentation,” IEEE Trans. Image Process., vol. 19, no. 11,
pp. 2924–2934, Nov. 2010.
[3] T. Patz and T. Preusser, “Segmentation of stochastic images with astochastic random walker method,” IEEE Trans. Image Process., vol. 21,
no. 5, pp. 2424–2433, May 2012.
[4] X. Chen, J. Udupa, U. Bagci, Y. Zhuge, and J. Yao, “Medical image
segmentation by combining graph cuts and oriented active appearance
models,” IEEE Trans. Image Process., vol. 21, no. 4, pp. 2035–2046,
Apr. 2012.
[5] T. F. Chan and L. A. Vese, “Active contours without edges,” IEEE Trans.
Image Process., vol. 10, no. 2, pp. 266–277, Feb. 2001.

[6] Y. Y. Boykov and M. P. Jolly, “Interactive graph cuts for optimal
boundary & region segmentation of objects in N-D images,” in Proc.
Int. Conf. Comput. Vis., 2001, pp. 105–112.
[7] L. Grady, “Random walks for image segmentation,” IEEE Trans. PatternAnal. Mach. Intell., vol. 28, no. 11, pp. 1768–1783, Nov. 2006.
[8] J. Zhang, J. Zheng, and J. Cai, “A diffusion approach to seeded image
segmentation,” in Proc. IEEE Conf. Comput. Vis. Pattern Recognit.,
Jun. 2010, pp. 2125–2132.
[9] C. Rother, V. Kolmogorov, T. Minka, and A. Blake, “Cosegmentation ofimage pairs by histogram matching-incorporating a global constraint into
MRFs,” in Proc. IEEE Conf. Comput. Vis. Pattern Recognit., Jun. 2006,
pp. 993–1000.
[10] L. Mukherjee, V. Singh, and C. R. Dyer, “Half-integrality based algorithms for cosegmentation of images,” in Proc. IEEE Conf. Comput. Vis.
Pattern Recognit., Jun. 2009, pp. 2028–2035.
[11] D. S. Hochbaum and V. Singh, “An efficient algorithm for cosegmentation,” in Proc. Int. Conf. Comput. Vis., Oct. 2009, pp. 269–276.
[12] S. Vicente, V. Kolmogorov, and C. Rother, “Cosegmentation revisited:
Models and optimization,” in Proc. Eur. Conf. Comput. Vis., 2010,
pp. 465–479.
[13] D. Batra, D. Parikh, A. Kowdle, T. Chen, and J. Luo, “Seed image
selection in interactive cosegmentation,” in Proc. IEEE Int. Conf. Image
Process., Nov. 2009, pp. 2393–2396.
[14] A. Joulin, F. Bach, and J. Ponce, “Discriminative clustering for image
co-segmentation,” in Proc. IEEE Conf. Comput. Vis. Pattern Recognit.,
Jun. 2010, pp. 1943–1950.
[15] D. Batra, A. Kowdle, and D. Parikh, “ICoseg: Interactive cosegmentation with intelligent scribble guidance,” in Proc. IEEE Conf.
Comput. Vis. Pattern Recognit., Jun. 2010, pp. 3169–3176.
[16] L. Mukherjee, V. Singh, and J. Peng, “Scale invariant cosegmentation
for image groups,” in Proc. IEEE Conf. Comput. Vis. Pattern Recognit.,
Feb. 2011, pp. 1881–1888.
[17] K. Chang, T. Liu, and S. Lai, “From co-saliency to co-segmentation:
An efficient and fully unsupervised energy minimization model,”in Proc. IEEE Conf. Comput. Vis. Pattern Recognit., Jun. 2011,
pp. 2129–2136.
[18] S. Vicente, C. Rother, and V. Kolmogorov, “Object cosegmentation,”in Proc. IEEE Conf. Comput. Vis. Pattern Recognit., Jun. 2011,
pp. 2217–2224.
[19] G. Kim, E. P. Xing, L. Fei-Fei, and T. Kanade, “Distributed cosegmentation via submodular optimization on anisotropic diffusion,” in Proc.
Int. Conf. Comput. Vis., Nov. 2011, pp. 169–176.
[20] A. Joulin, F. Bach, and J. Ponce, “Multi-class cosegmentation,” in Proc.
IEEE Conf. Comput. Vis. Pattern Recognit., Jun. 2012, pp. 542–549.
[21] M. Collins, J. Xu, L. Grady, and V. Singh, “Random walks based
multi-image segmentation: Quasiconvexity results and GPU-based solutions,” in Proc. IEEE Conf. Comput. Vis. Pattern Recognit., Jun. 2012,
pp. 1656–1663.
[22] J. Rubio, J. Serrat, A. López, and N. Paragios, “Unsupervised cosegmentation through region matching,” in Proc. IEEE Conf. Comput.
Vis. Pattern Recognit., Jun. 2012, pp. 749–756.
[23] H. Li and K. N. Ngan, “A co-saliency model of image pairs,” IEEE
Trans. Image Process., vol. 20, no. 12, pp. 3365–3375, May 2011.
[24] F. Meng, H. Li, G. Liu, and K. N. Ngan, “Image cosegmentation byincorporating color reward strategy and active contour model,” IEEE
Trans. Cybern., vol. 43, no. 2, pp. 725–737, Apr. 2013.
[25] Y. Chai, V. Lempitsky, and A. Zisserman, “Bicos: A bi-level cosegmentation method for image classification,” in Proc. Int. Conf.
Comput. Vis., Nov. 2011, pp. 2579–2586.
[26] F. Meng, H. Li, G. Liu, and K. N. Ngan, “Object co-segmentation basedon shortest path algorithm and saliency model,” IEEE Trans. Multimedia,
vol. 14, no. 5, pp. 1429–1441, Oct. 2012.
[27] F. Meng and H. Li, “Complexity awareness based feature adaptive cosegmentation,” in Proc. IEEE Int. Conf. Image Process., Sep. 2013,
pp. 1–3.
[28] X. Chen, Z. Tong, H. Liu, and D. Cai, “Metric learning with twodimensional smoothness for visual analysis,” in Proc. IEEE Conf.
Comput. Vis. Pattern Recognit., Jun. 2012, pp. 2533–2538.
[29] M. H. Nguyen and F. de la Torre, “Metric learning for image alignment,”
Int. J. Comput. Vis., vol. 88, no. 1, pp. 69–84, 2010.
[30] E. Nowak and F. Jurie, “Learning visual similarity measures for comparing never seen objects,” in Proc. IEEE Conf. Comput. Vis. Pattern
Recognit., Jun. 2007, pp. 1–8.

MENG et al.: FEATURE ADAPTIVE CO-SEGMENTATION BY COMPLEXITY AWARENESS[31] N. Verma, D. Mahajan, S. Sellamanickam, and V. Nair, “Learninghierarchical similarity metrics,” in Proc. IEEE Conf. Comput. Vis.
Pattern Recognit., Jun. 2012, pp. 2280–2287.
[32] T. Mensink, J. Verbeek, F. Perronnin, and G. Csurka, “Metric learningfor large scale image classification: Generalizing to new classes at nearzero cost,” in Proc. Eur. Conf. Comput. Vis., 2012, pp. 488–501.
[33] P. Arbeláez, M. Maire, C. Fowlkes, and J. Malik, “From contours toregions: An empirical evaluation,” in Proc. IEEE Conf. Comput. Vis.
Pattern Recognit., Jun. 2009, pp. 2294–2301.
[34] B. Alexe, T. Deselaers, and V. Ferrari, “What is an object?” in Proc.
IEEE Conf. Comput. Vis. Pattern Recognit., Jan. 2010, pp. 73–80.
[35] M.-M. Cheng, G.-X. Zhang, N. J. Mitra, X. Huang, and S.-M. Hu,“Global contrast based salient region detection,” in Proc. IEEE Conf.
Comput. Vis. Pattern Recognit., Jun. 2011, pp. 409–416.
[36] H. Ling and D. Jacobs, “Shape classification using the inner-distance,”
IEEE Trans. Pattern Anal. Mach. Intell., vol. 29, no. 2, pp. 286–299,
Feb. 2007.
[37] D. G. Lowe, “Distinctive image features from scale-invariant keypoints,”
Int. J. Comput. Vis., vol. 60, no. 2, pp. 91–110, 2004.
[38] S. Lazebnik, C. Schmid, and J. Ponce, “Beyond bags of features: Spatial
pyramid matching for recognizing natural scene categories,” in Proc.
IEEE Conf. Comput. Vis. Pattern Recognit., Jan. 2006, pp. 2169–2178.
[39] T. Deselaers and V. Ferrari, “Global and efficient self-similarity forobject classification and detection,” in Proc. IEEE Conf. Comput. Vis.
Pattern Recognit., Jun. 2010, pp. 1633–1640.
[40] A. Bosch, A. Zisserman, and X. Munoz, “Representing shape with aspatial pyramid kernel,” in Proc. ACM Int. Conf. Image Video Retr.,
2007, pp. 401–408.
[41] S.-J. Kim, K. Koh, M. Lustig, S. Boyd, and D. Gorinevsky, “An interiorpoint method for large-scale 1-regularized least squares,” IEEE J. Sel.
Topics Signal Process., vol. 1, no. 4, pp. 606–617, Dec. 2007.
[42] J. Winn, A. Criminisi, and T. Minka, “Object categorization by learned
universal visual dictionary,” in Proc. IEEE Int. Conf. Comput. Vis., vol. 2.
Oct. 2005, pp. 1800–1807.
[43] V. Ferrari, T. Tuytelaars, and L. V. Gool, “Object detection by contour segment networks,” in Proc. Eur. Conf. Comput. Vis., Jun. 2006,
pp. 14–28.
[44] C. Pedreira, “Learning vector quantization with training data selection,”
IEEE Trans. Pattern Anal. Mach. Intell., vol. 28, no. 1, pp. 157–162,Jan. 2006.
[45] R. Tibshirani, “Regression shrinkage and selection via the lasso,” J. R.
Stat. Soc. B, vol. 58, no. 1, pp. 267–288, 1996.
[46] H. Zou and T. Hastie, “Regularization and variable selection via theelastic net,” J. R. Stat. Soc. B, vol. 67, no. 2, pp. 301–320, 2005.
[47] J. Wright, A. Yang, A. Ganesh, S. Sastry, and Y. Ma, “Robust facerecognition via sparse representation,” IEEE Trans. Pattern Anal. Mach.
Intell., vol. 31, no. 2, pp. 210–227, Feb. 2009.
[48] A. J. Smola and B. Scholkopf, “A tutorial on support vector regression,”
Stat. Comput., vol. 14, no. 3, pp. 199–222, 2004.
[49] K. Koh, S.-J. Kim, and S. Boyd, “An interior-point method for largescale 1-regularized logistic regression,” J. Mach. Learn. Res., vol. 8,
pp. 1519–1555, Jul. 2007.
[50] C. M. Bishop, Pattern Recognition and Machine Learning. New York,NY, USA: Springer-Verlag, 2006.

Fanman Meng received the B.Sc. degree in computer science and technology from Shandong Agricultural University, Taian, China, in 2006, and the
M.Sc. degree in computer software and theory
from Xihua University, Chengdu, China, in 2009.
Since September 2009, he has been pursuing the
Ph.D. degree with the Intelligent Visual Information
Processing and Communication Laboratory, University of Electronic Science and Technology ofChina, Chengdu. He has been a Visiting Student with
the Division of Visual and Interactive Computing,Nanyang Technological University, Singapore, since July 2013. He works inthe areas of computer vision and pattern recognition. His work focuses on
specific object segmentation and detection. He is currently focusing primarilyon co-segmentation and saliency detection.

4823

Hongliang Li (SM’12) received the Ph.D. degree
in electronics and information engineering fromXi’an Jiaotong University, Xi’an, China, in 2005.
From 2005 to 2006, he joined the Visual Signal
Processing and Communication Laboratory, Chinese
University of Hong Kong (CUHK), Hong Kong, asa Research Associate. From 2006 to 2008, he wasa Post-Doctoral Fellow with the same laboratory in
CUHK. He is currently a Professor with the Schoolof Electronic Engineering, University of Electronic
Science and Technology of China, Chengdu, China.
His current research interests include image segmentation, object detection,
image and video coding, visual attention, and multimedia communication
system. He has authored or co-authored numerous technical articles in wellknown international journals and conferences. He is a co-editor of a Springer
book titled Video Segmentation and its Applications. He was involved in many
professional activities. He is a member of the Editorial Board of the Journal
on Visual Communications and Image Representation. He served as a TPC
member in a number of international conferences, including ICME in 2013,
ICME in 2012, ISCAS in 2013, PCM in 2007, PCM in 2009, and VCIP
in 2010, and served as a Technical Program Co-Chair in ISPACS in 2009,
and a General Co-Chair of the 2010 International Symposium on Intelligent
Signal Processing and Communication Systems. He serves as a Local Chairof the 2014 IEEE International Conference on Multimedia and Expo. He wasselected for the New Century Excellent Talents in University, Chinese Ministryof Education, China, in 2008.

King Ngi Ngan (F’00) received the Ph.D. degree
in electrical engineering from Loughborough University, Loughborough, U.K. He is currently a Chair
Professor with the Department of Electronic Engineering, Chinese University of Hong Kong, HongKong. He was a Full Professor with Nanyang Technological University, Singapore, and the Universityof Western Australia, Crawley, Australia. He holds
honorary and visiting professorships with numerous
universities in China, Australia, and South East Asia.
He served as an Associate Editor of the IEEET RANSACTIONS ON C IRCUITS AND S YSTEMS FOR V IDEO T ECHNOLOGY,
the Journal on Visual Communications and Image Representation, EURASIP
Journal of Signal Processing: Image Communication, and the Journal ofApplied Signal Processing. He chaired and co-chaired a number of prestigious
international conferences on image and video processing, including the 2010
IEEE International Conference on Image Processing, and served on theadvisory and technical committees of numerous professional organizations.
He has published three authored books, six edited volumes, and over 300
refereed technical papers, and edited nine special issues in journals. He holds
ten patents in the areas of image/video coding and communications. He is afellow of IET, U.K., and IEAust, Australia, and was an IEEE Distinguished
Lecturer from 2006 to 2007.

4824

IEEE TRANSACTIONS ON IMAGE PROCESSING, VOL. 22, NO. 12, DECEMBER 2013

Liaoyuan Zeng received the B.Eng. degree intelecommunication engineering from Southwest
Jiaotong University, Chengdu, China, in 2005, theM.Eng. degree in computer and communicationengineering from the University of Limerick, Limerick, Ireland, in 2006, and the Ph.D. degree in electrical engineering from the University of Limerick
in 2011. He is currently a Lecturer and Researcher
with the School of Electronic Engineering, University of Electronic Science and Technology ofChina, Chengdu. He was supported by a numberof postgraduate scholarships and projects, including those provided by theGovernment of Ireland Postdoctoral Fellowships in Science, Engineering andTechnology and European Cooperation in Science and Technology Action
IC0902. He was with the Worcester Polytechnic Institute, Worcester, MA,
USA, the Limerick, Ireland, Project Center as a Teaching Assistant in 2009
and 2010, a Teaching Assistant with the Polytechnic University of Catalonia,
Catalonia, Spain, and the Limerick Project Center in 2010, and was a Leading
Researcher and Representative of the Wireless Access Research Center,
University of Limerick in the WUN Cognitive Communications Consortiumfrom 2009 to 2011. He is currently a Researcher/Lecturer with the Intelligent
Visual Information Processing and Communications Laboratory, University ofElectronic Science and Technology of China. He is an active member of theresearch community, participating in activities that help facilitate the exchangeof ideas between members within the community. He served as a Track CoChair of BWCCA in 2012, and he was a member of the Technical Program
Committee of VTC in 2012, AICT in 2012, 2011, and 2010, and COCORA
in 2012 and 2011.

Qingbo Wu received the B.E. degree in applied
electronic technology education from Hebei Normal University, Hebei, China, in 2009. He is currently pursuing the Ph.D. degree from the Schoolof Electronic Engineering, University of Electronic
Science and Technology of China, Chengdu, China.
His current research interests include image/videocoding, quality evaluation, and perceptual modelingand processing.