Shifted Subspaces Tracking on Sparse Outlier for Motion Segmentation

1 Introduction

In video sequences, an object flow is composed of multiple motions or moving objects with the identical trajectory. Analyzing object flows is more frequently preferred than analyzing the motion of a single object, because the flows can provide more semantic clues for the crowd behavior [Ali and Shah, 2007]. Tracking multiple object flows and motion segmentation [Wu et al., 2011][Galasso et al., 2012] in complex scenes is a vital and challenging problem in a variety of computer vision tasks such as surveillance, robotics, augmented reality, medical imaging and human-computer interactions. The challenges mainly come from the complex background, occlusion, illumination variation, noise, overlapping, and intertwined trajectories of different flows [Fragkiadaki and Shi,

2011]. Some of these problems have been well studied in the previous research works, but some are typical features of the flow tracking or motion segmentation and thus have not been fully tackled before. In this paper, we construct a model that considers all the miscellaneous problems above, reduce the motion detection, tracking and segmentation to a simple matrix factorization, and then develop an efficient optimization algorithm to achieve the factorization result.

1.1 RelatedWork

To begin with, we can roughly categorize existing tracking approaches into two groups, i.e., generative model [Doucet et al., 2001][Comaniciu et al., 2003] and discriminative method [Hess and Fern, 2009][Hong et al., 2012]. Generative model formulates tracking as estimation of the state within a time series space state space model, and search the regions of the highest likelihood. Early works such as Kalman filter and its variants have been demonstrated to be optimal for linear Gaussian model. Another representative generative model for tracking is particle filter [Doucet et al., 2001], which approximates the posterior distribution of the state space by Monte Carlo integration. Single appearance model or multiple appearance models [Yu et al., 2008] are used in these generative models. Different from generative models, discriminative classifies cast the tracking problem into a classification task whose goal is to distinguish the target object from the background. In the training stage, each pixel is represented by a feature vector, and the pixels belonging to the same target object is assigned to the same class. Hybrid approaches [Yu et al., 2008] combining both generative models and discriminative classifiers have also been proposed for solving visual tracking under significant occlusions.

Recent advances in matrix completion [Cand`es and Recht, 2008][Ji and Ye, 2009] and robust principle component analysis (RPCA) [Chandrasekaran et al., 2009][Cand`es et al., 2009][Chen et al., 2010][F. Nie, 2011] lead us to a new perspective for analyzing large-scale video data, which is exploring the inherent low-rank structures of background and motions. As an extension of matrix completion who recovers a low-rank matrix from a small portion of its entries, RPCA exactly recovers a low-rank matrix L from collected data matrix X = L + S, where S is sparse outlier of large magnitude on random support. RPCA decomposes X by minimizing the convex surrogates of L's rank and S's cardinality, i.e., the trace norm of L and the ℓ1 norm of S,

Above convex optimization ensures exact or adequately precise recovery of L and S under mild identifiability conditions such as rank-sparsity coherence, on the premise that exact decomposition X = L + S does exist. However, this premise cannot be always fulfilled for data collected from real applications. Moreover, the rank and cardinality cannot be fixed within a small range while the error is still guaranteed to be small. This uncertainty brings unpredictable computational costs in optimization.

RPCA has been successfully applied to background modeling in video surveillance [Cand`es et al., 2009], where the backgrounds in all frames compose the rows of low-rank matrix L, whilst the moving objects or motions are captured by the sparse outlier S. However, most existing methods simply treat S as random noise and lack further study of the obtained sparse outlier, which in fact contains substantial rich information about the motions of object flows. In addition, the extra dense noise caused by camera lens or environment illumination changes make the exact decomposition assumption X = L + S cannot be satisfied in practices. Hence several recent approaches [Zhou et al., 2010][Hsu et al., 2011][Zhou and Tao, 2013] aim to obtain the approximated RPCA decomposition X = L + S + G, where G is the dense noise. Since most RPCA algorithms rely on repeating time consuming singular value thresholding, randomized method [Zhou and Tao, 2012] was introduced for acceleration.

In order to overcome the shortcomings of existing RPCA approaches, a novel method GoDec [Zhou and Tao, 2011] is proposed. GoDec imposes hard constraints to the rank of L and the cardinality of S [Xiong et al., 2010], and additionally accelerates the noisy decomposition with the help of bilateral random projections (BRP) based low-rank approximation [Zhou and Tao, 2012] and controllable rank of L.

Although linear convergence of GoDec can be proved by the framework "alternating projections on two manifolds" [Lewis and Malick, 2008], the upper bound for cardinality of S has to be carefully chosen in GoDec. Otherwise some portion of S's entries will be contaminated or lost. Moreover, the hard thresholding towards S requires sorting all its entries' magnitudes and thus is time consuming.

1.2 Overview of SST

A significant open problem left by the mentioned RPCA approaches is how to further analyze the rich structure of the sparse part. In many practical applications, the sparse part has structures that can contribute more useful information than the low-rank part. An example in point is that the sparse part of video sequence data is comprised of the motions of multiple object flows. In this paper, we consider decomposing the sparse part as the sum of several shifted low-rank matrices, each of which corresponds to objects sharing one motion trajectory. This can be viewed as a novel structured sparsity. It is also worthwhile to point out that although the main focus of this paper is object flow tracking and motion segmentation, the SST framework allows other forms of nonlinear transformation and thus can be directly applied to other problems.

We develop an efficient unsupervised framework to detect, track and segment multiple motions in complex scenes via solving a matrix factorization model. This framework invokes a sequence of matrix decompositions as subroutines, which can be summarized in two steps, i.e., background modeling and flow tracking. For the first step, we proposes "semi-soft GoDec" which replaces the cardinality constraint in GoDec with an ℓ1 penalty. This small change greatly shortens the computational time and facilitates the parameter tuning. For the second step, as the main contribution of this paper, we present a novel insight that each flow can be depicted by a low rank matrix after certain geometric transformation sequence to video frames (which are stored as rows of a matrix), and develop a matrix factorization method to recover both the low-rank matrices and the transformation sequences. If we treat the sparse outliers attained by semisoft GoDec as the new data matrix X, our flow tracking approach "shifted subspaces tracking (SST)" decomposes X as X = ∑ki=1 L(i) ◦ τ (i) +S +G, where L(i) stands for a lowrank matrix and τ(i) stands for a transformation sequence, both correspond to the motion of the ith object flow. SST reduces the matrix factorization to a sequence of alternating optimizations in a similar manner with semi-soft GoDec, and efficiently solves them by taking advantages of the betweenframe affinity and the motion sparsity of L(i). Besides, BRP [Zhou and Tao, 2012] is invoked to speed up the update of L(i). The low-rank patterns, together with their transformation sequences, reveals unexplored structure of the sparse part and rich information of segmented motion in complex scenes.

2 Problem Setup

We consider the problem of tracking object flows and segmenting their motions from the raw video data. Given a data matrix X ∈ Rn×p that stores a video sequence of n frames, each of which has w × h = p pixels and reshaped as a row vector in X, the goal of SST framework is to separate the motions of the object flows, recover both their low-rank patterns and geometric transformation sequences. This task is decomposed as two steps in SST, i.e., background modeling that separating all the moving objects from the static background, and flow tracking that recovers the information of each motion. In this paper, ·i stands for the ith entry of a vector or the ith row of a matrix, while ·i,j signifies the entry at the ith row and the j th column of a matrix.

2.1 Background modeling

Although previous RPCA approaches provides several effective matrix decomposition formulations for background modeling, some problems still arise in real applications. In SST, we consider the low-rank and sparse matrix decomposition in noisy case, which has been adopted by several recent models due to its robustness and adaptiveness to the real data,

where L describes the background and S denotes the motions. In SST, a new formulation for background modeling is adopted to overcome the shortcomings of both RPCA and GoDec,

Compared with RPCA, (4) does not require the exact decomposition X = L + S. Furthermore, the rank of L is controllable and the update of L can be randomized as in GoDec, thus the time cost can be largely decreased. Compared with GoDec, (4) replaces the "hard" cardinality constraint with a "soft" ℓ1 regularization. Tuning soft threshold λ is much easier than determining s in (3), because the resulting decomposition error is more robust to the change of λ. Later, we will develop "semi-soft GoDec" to solve the optimization (4).

2.2 Flow tracking

After obtaining the sparse outliers storing motions by background modeling, SST treats the sparse matrix S as the new data matrix X, and decomposes it as X = ∑ki=1 ˜L(i)+S+G, wherein ˜L(i) denotes the ith object flow, S stands for the sparse outliers and G stands for the Gaussian noise.

The matrix decomposition model for flow tracking in SST is based on an observation to the implicit structures of the sparse matrix ˜L(i). If the trajectory of the object flow ˜L(i) is known and each frame (row) in ˜L(i) is shifted to the position of a reference frame, due to the limited number of poses for the same object flow in different frames, it is reasonable to assume that the rows of the shifted ˜L(i) exist in a subspace. In other words, ˜L(i) after inverse geometric transformation is low-rank. Hence the sparse motion matrix ˜L(i) has the following structured representation

The invertible transformation τ(i)j : R2 → R2 denotes the 2-D geometric transformation (to the reference frame) associated with the ith object flow in the j th frame, which is represented by L(i)j . To be specific, the j th row in ˜L(i) is L(i)j after certain permutation of its entries. The permutation results from applying the nonlinear transformation τ (i)j to each nonzero pixel in L(i)j such that,

where τ(i)j could be one of the five geometric transformations [Prince, 2011], i.e., translation, Euclidean, similarity, affine and homography, which are able to be represented by 2, 3, 4, 6 and 9 free parameters, respectively. For example, affine transformation is defined as

wherein θ is the rotation angle, tx and ty are the two translations and ρ is the scaling ratio. It is worth to point out that τ(i)j can be any other transformation beyond the geometric group. So SST can be applied to sparse structure in other applications if parametric form of τ(i)j is known. We define the nonlinear operator ◦ as

Therefore, the flow tracking in SST aims at decomposing the sparse matrix X (S obtained in the background modeling) as

In SST, we iteratively invoke k times of the following matrix decomposition to greedily construct the decomposition in (9):

In each time of the matrix decomposition above, the data matrix X is S obtained by former decomposition. In order to save the computation and facilitate the parameter tuning, we cast the decomposition (10) into an optimization similar to (4),

To summarize, the optimization scheme of SST framework is given in Algorithm 1.

Algorithm 1 SST framework

3 SST framework

In this section, we develop efficient algorithms to solve the two types of minimization in Algorithm 1, both of which can be addressed by alternating minimization. In our algorithm, we speed up the update of low-rank part L in (4) and the lowrank motion patterns L(i) in (11) by bilateral random projection based low-rank approximation [Zhou and Tao, 2012]. In ST algorithm for flow tracking and motion segmentation, piece-wise linear approximation method is used to approximate the nonlinear operator ◦ when updating τ. Both the sparsity of L(i) and the between-frame affinity are leveraged to save computations. We also establish a rule to update the reference frame, which decides the uniqueness of τ(i) and avoids missing any object flow.

3.1 Semi-Soft GoDec for BackgroundModeling

We propose semi-soft GoDec for optimization (4), which can be solved by alternatively solving the following two subproblems until convergence:

The subproblems have global solutions Lt and St that can be obtained via closed-forms.

In particular, the two subproblems in (12) can be solved by updating Lt via singular value hard thresholding of X-St-1 and updating St via soft thresholding of X-Lt , respectively.

According to the bilateral random projection (BRP) based low-rank approximation [Zhou and Tao, 2012], the costly truncated SVDs in updating Lt can be approximated by

or its power scheme modification, wherein Y1 ∈ Rn×r and Y2 ∈ Rp×r are the left and right random projections and A2 is the left random projection matrix. The obtained semi-soft GoDec algorithm is given in Algorithm 2.

Algorithm 2 Semi-soft GoDec

Here q is the power parameter. When q > 0, the algorithm adopts a power-scheme modification of BRP for improving approximation accuracy [Zhou and Tao, 2011]. When q = 0, for dense X, (13) is applied. In the latter case, the QR decomposition of Y1 and Y2 in Algorithm 2 are not performed, and Lt is updated as Lt = Y1 (AT2 Y1 )-1 Y T 2 . Actually, q = 0 is sufficient to produce satisfying accuracy in most visual applications. The key difference of Semi-soft GoDec comparing to the ordinary GoDec is the soft-thresholding of S, which requires merely np subtractions, while the hard-thresholding of the largest entries in ordinary GoDec needs sorting of np values. This improvement further speedup the computation of background modeling. The linear convergence of L still holds and can be proved by following the same procedure in [Zhou and Tao, 2011].

3.2 SST algorithm for Object Flow Tracking

Flow tracking in SST solves a sequence of optimization problem of type (11). Thus we firstly apply alternating minimization to (11). This results in iterative update of the solutions to the following three subproblems,

Initialization

Unfortunately, alternating solving the 3 sub-problems might not guarantee to produce a global solution or even a stable one, unless an appropriate initialization is adopted. In particular, in the case when the solutions to L ◦ τ and S in (11) are unique, the pair (L, τ) may not be unique. This is because that we can choose arbitrary frame as the reference frame and transform the object flow in all the other frames of L ◦ τ to their positions in the reference frame, while the low-rank L◦τ keeps the same. To avoid such trivial multiple solutions of τ , we pre-define a template frame s and do not update its transformation τs during the tracking (w.l.o.g., we fix all the parameters of τs to be zeros). Then the object flow in each other frame of L ◦ τ are transformed to the position of the object flow in frame s via the inverse transform of τ, and thus the uniqueness of L and τ can be guaranteed. In this paper, we choose the template frame s as the one with the largest cardinality, which implies that almost all the objects are included in the frame,

We then set the rows of the low-rank pattern L as the duplicates of Xs, and initialize both the entries of the sparse outlier S as well as the parameters of τ to be zeros,

We now start to solve the three subproblems in (14).

Update of τ

The first subproblem aims at solving the following series of nonlinear equations of τj,

Albeit directly solving the above equation is difficult due to its strong nonlinearity, we can approximate the geometric transformation Lt-1 j ◦ τj by using piece-wise linear transformations, where each piece corresponds to a small change of τj defined by ∆τj. Thus the solution of (17) can be approximated by accumulating a series of ∆τj . This can be viewed as an inner loop included in the update of τ. Thus we have linear approximation

where Jj is the Jacobian of Lt-1 j ◦τj with respect to the transformation parameters in τj. Therefore, by substituting (18) into (17), ∆τj in each linear piece can be solved as

The update of τj starts from some initial τj, and iteratively solves the overdetermined linear equation (19) with update τj := τj + ∆τj until the difference between the left hand side and the right hand side of (17) is sufficiently small. It is critical to emphasize that a well selected initial value of τj can significantly save computational time. Based on the between-frame affinity, we initialize τj by the transformation of its adjacent frame that is closer to the template frame s,

Another important support set constraint, supp(L ◦ τ) ⊆ supp(X), needs to be considered in calculating Lt-1 j ◦ τj during the update of τ . This constraint ensures that the object flows or segmented motions obtained by SST always belong to the sparse part achieved from the background modeling, and thus rules out the noise in background. Hence, suppose the complement set of supp(Xj) to be suppc(Xj), each calculation of Lt-1 j ◦ τj follows a screening such that,

Update of L

The second subproblem has the following global solution that can be updated by BRP based low-rank approximation (13) and its power scheme modification,

wherein τ -1 denotes the inverse transformation towards τ. The SVDs can be accelerated by BRP based low-rank approximation (4). Another acceleration trick is based on the fact that most columns of (X - St-1 ) ◦ τ -1 are nearly all-zeros. This is because the object flow or motion after transformation occupies a very small area of the whole frame. Therefore, The update of Lt can be reduced to low-rank approximation of a submatrix of (X - St-1 ) ◦ τ -1 that only includes dense columns. Since the number of dense columns is far less than p, the update of Lt can become much faster.

Update of S

The third subproblem has a global solution that can be obtained via soft-thresholding Pλ(·) similar to the update of S in semi-soft GoDec,

A support set constraint supp(S) ⊆ supp(X) should be considered in the update of S as well. Hence the above update follows a postprocessing,

Note the transformation computation ◦ in the update can be accelerated by leveraging the sparsity of the motions. Specifically, the sparsity allows SST to only compute the transformed positions of the nonzero pixels. We summarize the SST algorithm in Algorithm 3.

Algorithm 3 SST Algorithm

Input: X, ri, λi(i = 1, · · · , n), k Output: Li(i = 1, · · · , n), S for i = 1 → k do Initialize: s = argmax i card (Xi), L = [Xs; · · · ;Xs], S = 0, τ = -→0 while not converge do for j = s - 1 : -1 : 1 do τj := τj+1. while not converge do ˜Lt-1 j = Lt-1 j ◦ τj, ˜Lt-1 j,suppc (Xj) = -→0 . τj := τj + (Xj -St-1 j - ˜Lt-1 j ) (Jj )† . end while end for for j = s +1 : 1 : n do τj := τj-1. while not converge do ˜Lt-1 j = Lt-1 j ◦ τj, ˜Lt-1 j,suppc (Xj) = -→0 . τj := τj + (Xj -St-1 j - ˜Lt-1 j ) (Jj )† . end while end for τ t = τ. Lt = BRP ((X - St-1 ) ◦ τ -1 ). St = Pλ (X - Lt ◦ τ t ) , St j,suppc (Xj) = -→0 . end while X := St , L(i) := Lt , τ(i) = τ t . end for

4 Experiments on Surveillance Videos

This section justifies both the effectiveness and the efficiency of the SST framework, which includes semi-soft GoDec and SST algorithm as its two steps, via tracking object flows in four surveillance video sequences 1 . We run all the experiments by MATLAB on a server with dual quad-core 3.33 GHz Intel Xeon processors and 32 GB RAM. In the experiments, the type of geometric transformation τ is simply selected as translation. The detection, tracking and segmentation results as well as associated time costs are shown in Figure 1 and Figure 2.

The results show SST can successfully separate the moving objects from the background via semi-soft GoDec, and promisingly recover both the low-rank patterns and the associated geometric transformations for motions of multiple object flows. The detection, tracking and segmentation are seamlessly unified in a matrix factorization framework and achieved with high accuracy. Moreover, it also verifies that SST performs significantly robust on complicated motions in complex scenes. This is attributed to their distinguishing shifted low-rank patterns, because different object flows can hardly share a subspace after the same geometric transformation. Since SST show stable and appealing performance in motion detection, tracking and segmentation for either crowd or individual, it provides a more semantic and intelligent analysis to the video content than existing methods.

1 http://perception.i2r.a-star.edu.sg/bk model/bk index.html

Besides the precise video content analysis, another advantage of SST is its fast speed. In Table 1, we compare semi-soft GoDec with original GoDec on the 4 video sequences used in [Zhou and Tao, 2011] for background modeling task. Semisoft GoDec can processes a 200 frame video with 144 × 176 resolution in 9 seconds, which is substantially faster than all the published results of RPCA approaches. In Table 2, we list the corresponding choices of cardinality k in GoDec and softthreshold λ in semi-soft GoDec. Their resulting relative errors for reconstruction are both within [10-3 , 10-2 ]. It shows that for GoDec we should carefully select k, otherwise the noise will leak into the sparse part or some meaningful sparse outlier will be lost. But we can easily tune λ in semi-soft GoDec (we fix it to 8 in all experiments). For flow tracking, we speed up SST algorithm by leveraging the motion sparsity, between-frame affinity, and randomized approximation. Therefore, SST is very competitive in big data problems.

Figure 2: Background modeling and object flow tracking results of a 50-frame surveillance video sequence from Shoppingmall dataset with resolution 256 × 320.

Acknowledgements

We would like to thank all the anonymous reviewers for their constructive comments on improving this paper. This work is supported by Australian Research Council Discovery Project with number ARC DP-120103730.