Semantic Single Video Segmentation with Robust Graph Representation

1 Introduction

Video resource has grown tremendously with the development of digital technology. YouTube has over 100 hours of video uploaded per minute, so it is challenging to handle such big video data. Video object segmentation is one of the attracting applications for recent years, as it automatically generates a pixel-level boundary of foreground objects which benefits a lot for other higher-level applications, such as scene classification or understanding.

Generally the existing video segmentation methods can be categorized into the following groups: (1) graph-based model [Grundmann et al., 2010, Lee et al., 2011, Galasso et al., 2014,Zhang et al., 2013], (2) trajectory-based model [Li et al., 2013,Ochs and Brox, 2011,Palou and Salembier, 2013], (3) generative layered model [Galasso et al., 2012,Ma et al., 2013, Xu et al., 2013], and so on. It has been verified that the effectiveness of graph-based models enjoys the following advantages: (a) good generalizability to videos of arbitrary sizes, (b) rich mathematical supports for graph-model optimization, (c) encouraging segmentation result, and (d) less computational load [Galasso et al., 2012]. Thus in this work, we keep investigating the graph-based model.

∗This research is supported in part by the NSF CNS award 1314484, ONR award N00014-12-1-1028, ONR Young Investigator Award N00014-14-1-0484, and U.S. Army Research Office Young Investigator Award W911NF-14-1-0218.

Nevertheless, it is known that graph-based models are vulnerable to outliers. When the input data are heavily corrupted, graph-based models might fail [Cand`es et al., 2011, Liu et al., 2010]. For video segmentation, outliers and noises happen a lot, especially when the graph is built upon superpixels/supervoxels. It is because the current superpixel/supervoxel generation methods have difficulties in producing the exactly pixel-wise segmentation for objects. After over-segmenting video frames, those segments that cover both foreground object and background, but not stable across the frames, are considered as "outliers", e.g., the scroll caption in "tiger" case as shown in the bottom row of Figure 1. To alleviate the influence of outliers, several attempts have been made and encouraging results have been reported [Zhang et al., 2012,Zhang et al., 2013]. Zhang et al. [Zhang et al., 2012] represented each frame by a bunch of superpixels. Considering each superpixel as a vertex, the video sequence can be represented as a directed acyclic graph. The shortest path algorithm is used to select the graph vertices for all frames. However, this method cannot deal with the occlusion case. Most recently, Zhang et al. [Zhang et al., 2013] solved this problem by designing a dynamic programming algorithm which makes the graph model more robust. Although these attempts have demonstrated the effectiveness in handling outliers, they can only deal with one single foreground object case as shown in Figure 1(c).

To achieve the semantic segmentation, segment different objects based on their class information is challenging, especially for single video case. Grundmann et al. [Grundmann et al., 2010] proposed a hierarchical graphbased segmentation method, which over-segments a volumetric video graph into spatial-temporal regions (similar to superpixel/supervoxel) firstly. Then a region-graph is created. By finding the minimum spanning tree (MST) iteratively, the segmentation is achieved. It is deserving to notice that although different labels are assigned to different regions, the aim is to find regions with the same spatial-temporal information. While on opposite, we aim to produce the semantically meaningful segmentation for foreground objects. Similarly, another graph-based recent work [Galasso et al., 2014] by Galasso et al. focused on computation and memory costs but not semantic segmentation. For the majority of semantic segmentation works, multiple videos are needed. Chiu et al. [Chiu and Fritz, 2013] formulated this as a non-parametric bayesian model. Videos segmentation prior is introduced to leverage the segments of coherent motion and global appearance classes. Then objects with the same class property are linked across frames. Fu et al. [Fu et al., 2014] proposed a multi-stage selection graph method by leveraging the potential between two input videos and the potential within each video. Zhang et al. [Zhang et al., 2014] designed a regulated maximum weight clique extraction scheme. It balances well the spatially saliency and temporal consistency in object proposal (superpixels) tracklet selection step. The similar shape and appearance could be iteratively extracted by weighted groupings of objects. Unfortunately, these semantic segmentation methods require more than one video as input, which limits the scope of real-world applications.

In this work, to overcome the limitations of multiple videos as input and sensitivity to outliers, we fully exploit the spatial and temporal information in a single input video. As a tradeoff, we assume that (1) the location of foreground objects in the successive frame has a relatively small shift and (2) multiple objects lie in separated latent subspaces. By considering the spatial consistency of foreground objects, object-like regions can be aligned across frames. With the usage of object appearance and motion, different objects can be clustered into different groups. In general, our method can be divided into four major steps as shown in Figure 2(b-e). First, a pool of scored "object-like regions" (proposals) for each frame are generated based on appearance and motion features. Second, to perform a robust graph representation, we conduct outlier detection with the help of low-rank representation. Third, spectral clustering is performed based on the clean representation. Finally, objects in the missing frame are recovered using spatial consistency. In general, we summarize our contributions as:

• To the best of our knowledge, this is the pioneer work to achieve semantic video segmentation using one single video, opposed to using multiple videos, required by other graph-based video segmentation methods.
• Low-rank representation based outlier analysis is conducted to uncover the intrinsic multiple structure of proposals. By characterizing the outliers via l2,1-norm regularizer, this outlier detection technique can be applied in any graph-based segmentation methods.
• By fully exploiting the motion directions of foreground objects, we theoretically demonstrate the effectiveness of our proposed proposal objectness prediction method, which can well handle the inconsistent moving situation.

2 RelatedWork

In this section, we are talking about the related works of two major techniques used in the proposed method, i.e. graphbased video segmentation method and low-rank graph representation.

Graph-based object segmentation is a relatively new topic. Different from traditional video segmentation method [Shi and Malik, 1998], which works on individual pixel, the recent graph-based methods [Lee et al., 2011, Jain and Latecki, 2012,Zhang et al., 2013,Grundmann et al., 2010,Galasso et al., 2014] work on superpixel or supervoxel generated using object-like region extraction methods [Endres and Hoiem, 2010,Alexe et al., 2010]. This has an advantage in terms of processing speed. For instance, a 100×100 video clip has 100 superpixels per frame. The data to be processed with a pixelbased method are 1000 times more than with a superpixelbased method. Besides time saving, these object-like region extraction methods can provide a pool of semantic region candidates as a preprocessing step. Lee et al. [Lee et al., 2011] utilized a single cluster graph partitioning method [Olson et al., 2005] to discover the foreground object, then the authors refined the result by proposed pixel-level object labeling methods. Ma and Latecki [Jain and Latecki, 2012] treated the object region selection process as finding the maximum weight clique in a weight graph. Zhang et al. [Zhang et al., 2013] first constructed a directed acyclic graph based on object-like regions, then turned the region selection problem to find the maximal/minimal weight path problem. These methods that work well in segmenting one foreground object, however, will fail in multiple objects segmentation task.

Low-rank based graph representation attracts more and more attention because of its robustness to the data corruption [Cand`es et al., 2011, Liu et al., 2010]. Cand`es et al.

formulated the given observation matrix X by the sum of two terms, i.e. low-rank clean matrix X0 and errors E, X = X0 +E. This formulation implicitly assumes the underlying structure is single low-rank subspace. However, in real-world application, it is more likely that data are drawn from multiple subspaces. Thus, Liu et al. [Liu et al., 2010] proposed a low-rank representation (LRR) method to uncover the multiple subspace structure of data, which can represent the samples as linear combinations of the basis in a given dictionary, as X = DZ+E, where D is the "Dictionary", which can be set as data samples X itself in many applications [Liu et al., 2010]. Under the low-rank representation framework, l2,1-norm regularization has demonstrated the effectiveness of handling outliers in many applications, for instance, face recognition [Shao et al., 2014], kinship verification [Xia et al., 2012], etc. This motivates us to characterize the video region outliers using l2,1-norm regularizer.

3 Our Method

In this section, we illustrate our method in detail. Specifically, according to the order of video processing, object-like regions generation will be discussed firstly, then followed by the core part, proposal clustering with outlier detection. To complete the segmentation task, the post-processing step is followed at last.

3.1 Object-like Regions Generation

To achieve the multi-class foreground object segmentation task, the first thing is to segment all possible object-like regions (proposals). There exist several works focusing on finding proposals [Endres and Hoiem, 2010, Alexe et al., 2010]. However, these works are all single image based, which means the relationship between frames is not considered by simply applying these methods. We consider optical flow between successive frames to make a better prediction of objectness. Thus, the objectness of proposal can be calculated as:

where r denotes a proposal, A(·) and M(·) stand for objectness scores measured by appearance feature and motion feature, respectively.

Specifically, we compute A(r) using [Endres and Hoiem, 2010], which represents the objectness in the sense of appearance, such as color, texton, etc. Although it gives a reasonable likelihood measurement on proposal that is an object, it does not take motion into account since it is single-image based. With the help of consecutive frames at the input, objectness in the sense of motion M(r) is measured using optical flow [Liu, 2009] as follows:

where u and v denote the optical flow calculated from current-to-previous (backward) direction, and current-to-next (forward) direction, respectively. ur means the optical flow map in proposal r. Term vr is defined in the same way. Since there are two directions x and y to quantify the optical flow, we define ξ(u, v) as:

where ‖ · ‖1 is the sum of absolute value of all elements in the matrix [Lu et al., 2012]. It is worthy mentioning that the way we measure motion features within the proposal has a few benefits as follows: (1) It encourages the proposals with large motions by multiplication of forward and backward optical flows. Proposals with larger movements can be assigned to a high motion score; (2) Proposals with inconsistent moving direction will be depressed by this separate-direction motion scoring method. Without loss of generosity, let's assume (ux, uy) and (vx, vy) are the forward and backward optical flows on a single pixel. Only proposals with the similar direction (θ is small) are encouraged. For the extreme case, when θ = π/2, and lengths (or norms) of two optical flows are the same, the motion score is zero. The effectiveness of this definition is based on the assumption that the foreground objects are moving consistently. Even object of interest moves erratically, the movement trajectory between frames are slight; (3) The noises induced by optical flow calculation or tiny background movement can be eliminated. Here an assumption that background objects' movements are trivial is made.

By normalizing two kinds of scores into the same scale, the quantitative measure on proposals is done by simply adding two scores up. For the first and last frame, we only use appearance score due to the incapability of optical flow computation. To reduce the computational cost, 100 proposals with the highest scores in each frame are selected for the next step.

3.2 Proposal Clustering

Given the pool of scored object-like regions, our goal in this step is to group different regions into different categories based on class information. Dataset-oriented feature selection method can always achieve good results, however, it will narrow the application scope as well. To alleviate this dilemma, we only use two features in our method, color histogram for appearance and optical flow histogram for motion.

Firstly, we define color and optical flow similarity (distance) between two proposals rm and rn as follows:

where Xc ∈ Rdc and Xf ∈ Rdf denote the χ2 -distance between color and optical flow histograms of rm and rn, respectively. µc and µf are the means of the all distances for color and optical flow histograms. Instead of combining them directly to form an affinity matrix, we make a simple but effective feature selection to determine whether or not to use the optical flow feature. The intuition is that the estimated optical flow map is not as robust as the color feature. Furthermore, the slight movement in the background could have a significant impact on finding foreground objects, especially when the foreground object has a relatively small movement or even no movement. Instead of giving the same weight on optical flow and color, we set a binary threshold λ to turn optical flow feature on/off.

Proposal Outlier Removal

The proposal generation method [Endres and Hoiem, 2010] used in the first step not only focuses on accurate object-like region prediction, but also focuses on region diversity, which means for each frame it gives a pool of objectlike region candidates. So overlap between region candidates happens. In this case, the similarity between the overlapped proposals will have relatively high scores using our proposed measurement Eq. (4). It is the fact that the overlapped proposal covering both foreground object and background happens a lot, but not stable across the frames. We consider these proposals as "outliers". Obviously, removing these outliers will benefit the clustering result. Here, we concatenate two features Xc and Xf to get the X = [Xc; Xf ] ∈ Rd×N , where d = dc+df denotes the new feature dimension for the outlier detection step, and N is the total number of proposals.

The intuition of low-rank representation is to find the new representation Z of original data X with intrinsic rank. Inspired by the fact that intrinsic rank of "clean" data is always small, we enforce the rank of Z in the objective following the previous works [Liu et al., 2010] as

Recently, l2,1-norm has been testified its efficiency on feature selection and outlier detection [Nie et al., 2010,Liu et al., 2010], with its definition as follows:

Compared with lp-norm (p = 1, 2,∞), l2,1-norm can well characterize the sample-specified outliers, since it is performed to select features across all points with joint sparsity. Then Eq. 5 can be rewritten as:

where β is the trade-off parameter balancing the two terms. Because of the discrete nature of the rank function, the Eq.(8) is difficult to solve. As a good surrogate of rank function, trace norm ‖ · ‖∗ is often used due to its convexity. Then the objective can be rewritten as:

The above convex optimization problem can be solved by several off-the-shelf methods. In this paper, exacted Augmented Lagrange Multiplier (ALM) method is applied [Bertsekas, 1982] to iteratively optimize Z and E.

After removing the outliers, we then define the similarity matrix W using the clean color feature ˜Xc and optical flow feature ˜Xf by

where ˜Xc = Xc -Ec and ˜Xf = Xf -Ef . λ is the binary threshold defined above. The similarity matrix W has a property of block-diagonal by putting the proposals within the same cluster together, as shown in Figure 3. Proposals within the cluster have higher similarity (white); the correlation between two clusters has a lower similarity (black). The sizes of two blocks are not the same. In fact, the perfect clustering result should have the same size in this case, as the video sequence shown in Figure 3 is "chicken" from dataset MOViCS, and both chicken and turtle exist in all frames. Thus, by selecting one best proposal for each frame, both of the block sizes should be equal to the frame number. However, this ideal case rarely happens due to the following reasons: (1) there always exist some similar proposals (for most cases, they are parts of the foreground objects) considered as inliers. In this "chicken" case, the lower right block represents chicken, the upper left block represents turtle. As we can see clearly from Figure 3(c), the two block sizes are not the same, representing the different number of proposal "chicken" and "turtle".

As we obtain the similarity matrix W, to speed up the clustering step, k-nearest neighbour algorithm is used before performing spectral clustering. By applying the basic graph knowledge, the normalized Laplacian matrix L is defined as L = IN -D-1/2WD-1/2 , where IN is the identity matrix with N-dimension and degree matrix D is the diagonal degree matrix with its elements determined by the corresponding row sums of W.

With L, we can achieve the semantic segmentation with multiple classes. For simplicity, we illustrate our idea on the case class number k equals 2. For a given proposal y, we consider it as foreground when y is set to 1 and as background when set to -1. Thus, our problem can be formulated as,

where 1N denotes the N-dimensional vector of all ones. Following the classical spectral clustering methods [Ng et al., 2001]. This objective function can be solved by using singular value decomposition (SVD).

4 Experimental Result

In this section, we make a quantitative evaluation on the proposed method and other baselines. Since we focus on graph-based model, the state-of-the-arts of graph-based image cosegmentation (ICS) [Joulin et al., 2012] and graphbased video segmentation (VS) [Zhang et al., 2013] are selected as baselines. The evaluation is performed on two public video databases containing multiple foreground objects. To demonstrate the effectiveness of the outlier detection part, we consider two versions of our method, i.e. Ours-1 denotes our model without outlier detection, and Ours-2 denotes our model with outlier detection.

4.1 Dataset

In order to evaluate the performance of multi-class foreground object segmentation, many traditional video segmentation databases are not suitable, because they mainly focus on one moving object segmentation task, such as database SegTrack [Tsai et al., 2010], GaTech [Grundmann et al., 2010] or Persons and Cars Segmentation Database [Zhang et al., 2013]. However recently, video cosegmentation works provide the source databases for evaluating the semantic segmentation, since these works focus on foreground segmentation with different object labels.

In this work, we select two open public datasets, MOViCS [Chiu and Fritz, 2013] and ObMiC [Fu et al., 2014], where MOViCS is the first benchmark for multi-class video cosegmentation task. It has 4 different video cases with a total of 11 video clips, including "chicken", "lion", "giraffe", and "tiger". All the foreground objects with the same class are assigned by the same label.

MOViCS

ObMiC

Dataset ObMiC also contains 4 sets of videos. Each has two video clips. Different from MOViCS only containing animals, ObMiC extends the object to people and cartoon figures. Compared with MOViCS, ObMiC is more challenging due to the following reasons: (1) scale, most foreground objects in MOViCS are relatively large (except "chicken" case), which is less sensitive to the bad proposal generation; (2) Slight motion, objects in ObMiC have less movements, which might result in the failure of optical flow feature.

4.2 Comparison

As the graph-based video segmentation method, one of our baselines is the state-of-the-art video segmentation from Zhang et al. [Zhang et al., 2013]. In addition, ICS can be tailored to the video segmentation work without taking the spacial-temporal information into account. Thus, we also make a comparison with the state-of-the-art ICS [Joulin et al., 2012]. Specifically, an important parameter of ICS which needs tuning is the class number. In the experiments, this number is set in the range of [4, 8]. In VS, two key parameters of GMM model and MRF model are tuned in the range of [0.1, 2]. For all methods, we run the publicly available code and report the best performance.

To make a quantitative evaluation, we use "intersectionover-union" metric used in PASCAL challenge and previous works [Chiu and Fritz, 2013]. It is well defined to measure the segment region on both precision and recall rate as,

where S stands for a set of segments and G is the groundtruth annotation. Following the common clustering performance MOViCS

ObMiC

measurement criteria, we assign the class label to the segments with the best matching to groundtruth.

We present the comparison result of intersection-overunion metric on both datasets in Figure 4. The corresponding visualizations of all methods are shown in Figure 1 and Figure 6, respectively. By observation, several conclusions can be drawn: (1) Our-2 performs the best. (2) Compared with Our-1, Our-2 with outlier detection has a modest improvement, indicating the effectiveness of the low-rank based robust graph construction part. (3) For most multi-class objects cases, i.e. "lion and zebra" and "giraffe and elephant" in MOViCS and all the cases in ObMiC, ICS performs better than VS. This is because VS fails to consider the multi-class objects scenario, which is a common scene in real-world. Take "giraffe and elephant" as example in Figure 1, VS cuts both the giraffe and elephant out with same label. Moreover, similar to many other previous video segmentation methods which only segment one foreground object, VS only gives the results of "zebra" in "zebra and lion" case. (4) All the methods perform bad for the case "skating" in ObMiC. Two possible reasons may explain this: (a) the foreground objects (skaters) are relatively small, which easily results in a large false positive; (b) The female skater has different appearances for her upper body and lower body, which is difficult to segment. The statistics of performance measured by intersection-over-union metric are tabulated in Table 1. We highlight the highest score using bold font. It is deserved to note that for MOViCS, our method improves the performance of each case by 26.25%, 8.39%, 5.25% and 4.33%, respectively. For ObMiC, we boost the performance by 25.41%, 12.42%, 11.98% and 52.9%, respectively. On average, the performance bar is raised by 24.17%.

Note that although intersection-over-union metric is a good measurement on segmentation results, it is weighted more by recall than precision. To make a wholesome evaluation, F-measure is used as a complementary measurement. Compared with the groundtruth, the F-measure with different parameters γ is calculated as:

We set γ 2 = 0.3 following Achanta et al. [Achanta et al., 2009] to weigh precision more than recall. Figure 5 shows the comparison results between our method and other methods. We can observe the same trend showing that our method performs the best. The exact F-measure result numbers are shown in Table 2. On average, our method outperforms ICS by 13.93% and VS by 39.84%, respectively.

5 Conclusions

We have proposed a semantic graph-based video segmentation method by clustering the objects of different classes into separate groups. To make a robust graph representation, we have analyzed the cause of outliers and modeled them with l2,1-norm regularizer under low-rank constraint. With the "clean" representation, spectral clustering is used to get the different foreground object groups. The experimental results demonstrate that our method outperforms state-of-theart image cosegmentation and graph-based video segmentation baselines on the existing datasets MOViCS and ObMiC.