# Low-Rank Representation-Based Object Tracking Using Multitask Feature Learning with Joint Sparsity

Authors: Hyuncheol Kim; Joonki Paik
Journal: Abstract and Applied Analysis
 (2014)

---

## Abstract

We address object tracking problem as a multitask feature learning process based on low-rank representation of features with joint sparsity. We first select features with low-rank representation within a number of initial frames to obtain subspace basis. Next, the features represented by the low-rank and sparse property are learned using a modified joint sparsity-based multitask feature learning framework. Both the features and sparse errors are then optimally updated using a novel incremental alternating direction method. The low-rank minimization problem for learning multitask features can be achieved by a few sequences of efficient closed form update process. Since the proposed method attempts to perform the feature learning problem in both multitask and low-rank manner, it can not only reduce the dimension but also improve the tracking performance without drift. Experimental results demonstrate that the proposed method outperforms existing state-of-the-art tracking methods for tracking objects in challenging image sequences.


---

## Body

## 1. Introduction

Object tracking is one of the well-known problems in computer vision with many applications including intelligent surveillance, human-computer interface, and motion analysis. In spite of significant success, designing a robust object tracking algorithm remains still challenging issue due to factors from real-world scenarios such as severe occlusion, scale and illumination variations, background clutter, rotations, and fast motions.An appearance model-based tracking method, which evaluates the likelihood of an observed image patch belonging to object class, considers some critical factors such as object representation and representation scheme. The object representation can be categorized by adopted features [1, 2] and description models [3, 4]. The representation scheme can be either generative or discriminative. The generative methods regard the appearance modeling as finding the image observation with minimal reconstruction error [5, 6]. On the other hand, the discriminative methods focus on determining a decision region that distinguishes the object from the background [7, 8].Various object tracking methods based on object appearance models can handle only moderate changes and usually fail to track when the object appearance significantly changes. As a result, an appearance model learning process is required for robust object tracking under challenging issues such as object deformation.Recently, sparse representation-basedl1 norm minimization methods have been successfully employed for object tracking [9–13], where an object is represented as one of multiple candidates in the form of sparse linear combination of a dictionary that can be updated to maintain the optimal object appearance model. Although the sparse representation-based method can robustly track an object with partial occlusion, the computational cost for the l1 norm minimization in each frame is still expensive.Bao et al. applied the accelerated proximal gradient (APG) [14] approach to efficiently solve the l1 minimization problems for object tracking. Structured multitask tracking (MTT) was proposed by mining object discriminative structure between different particles rather than individually learning each particle [15]. Zhang et al. address their tracking performance as a fast solution of the MTT problem using Bao’s learning method of joint particle representation. By decomposing the sparse coefficients into two matrices for maintaining inliers and outliers, the robust MTT- (RMTT-) based object tracking was proposed in [16].The low-rank sparse tracking (LRST) was proposed by representing all samples using only a few templates [17]. The LRST is improved with incremental learning method of low-rank features [18] and adaptive pruning with exploiting temporal consistency [19].In spite of these improvements in MTT and LRST in the particle filter framework, the computational cost increases with the number of particles. Furthermore, MTT regards the sparse representations of sampled particles as independent state data without considering relationships between particles. For this reason, MTT may not work if the particles are drawn from specific probability distribution. The LRST-based methods are difficult to apply directly for object tracking in online video processing due to its structural computation complexity such as nuclear norm minimization.To solve the above mentioned problems, we propose a novel object tracking algorithm based on multitask feature learning using joint sparsity and low-rank representation. We assume that the object representation can be incrementally optimized in the robust principal component analysis (RPCA) framework. The RPCA can be performed by decomposing the observations as the sum of a low-rank matrix and a sparse matrix; thus it can successfully recover the intrinsic subspace structure from corrupted observations. We extract features with low-rank representation within a few frames. After obtaining the subspace basis of object features, the features represented by all possible low-rank and the sparse property are learned using a variant of multitask feature learning framework. Finally, a novel incremental alternating direction method- (ADM-) based low-rank optimization strategy is efficiently applied for update of sparse error and features. The low-rank optimization problem for learning multitask features can be achieved by a few sequences of efficient closed form updating operation for the optimal state variables of object tracking.


## 2. Low-Rank Representation of Object with Joint Sparsity

### 2.1. Low-Rank Representation of Object

RPCA [20] was recently introduced to recover low-rank features in learning for the reduced subspace. Given a sparse matrix Y with corrupted observation, RPCA attempts to exactly recover the low-rank matrix Z and minimize sparse error E. Let Z*=∑i‍σi(Z) denote the nuclear norm of the low-rank matrix Z such as the sum of singular values of Z. Under this assumption, the principal component pursuit (PCP) is defined as in the following minimization:
(1)min⁡Z,EZ*+λE1,1,s.t.Y=Z+E,5555
where ∥·∥1,1 represents the l1,1 norm and λ is a regularization parameter.The assumption under RPCA framework [20], for disentangling the low-rank and sparse component, is that Z has singular vectors and is not sparse. The singular value decomposition of Z can be expressed as
(2)Z=UΣV⊤=∑i=1N‍σiuivi⊤,
where N is the rank of Z, σ1,…,σN are positive singular values, and U=[u1,…,uN] and V=[v1,…,vN] are the matrices of left- and right-singular projection vectors.The object tracking problem can be solved under the RPCA framework. Suppose we haven sampled particles and the correspondingly observed candidate of an object Y=[y1,…,yn] at time t. Each observation can be represented as a linear combination of m basis vectors {u1,…,um}, which spans the data space such as Y=UtWt, where Ut=[u1,…,um], and each column of Wt=[w1,…,wn] indicates the discriminative feature representation of each particle observation. In this paper, we utilize the strength of both subspace learning and sparse representation for object appearance model in the principal component analysis (PCA) as [21]
(3)Y=UW+E.In feature learning literature, the multitask feature learning [22, 23] employs the l2,1 norm minimization to involve features selection across tasks under a strict assumption that all tasks share a common underlying representation.The goal of the proposed object tracking framework is to search particles that have the most similar feature to previous tracking result. Since particles are densely sampled around the current object state, in order to estimate the optimal low-rank features in iterative steps, we focus on all possible nonsmooth sparse errors, joint sparsity of features based on low-rank, andl1,1 and l1,2 constraints that produce solution for the within- and between-feature-tasks sparsity. With this consideration, we formulate the following object tracking problem by adopting three equality constraints as
(4)min⁡W,Eλ1W*+λ2W1,2+λ3W1,1+λ4E1,1s.t.Y=UW+E,5555555555555555555555555
where Cp,q=(∑j‍(∑i‍|cij|p)q/p)1/q is called p, q norm of matrix C and λ1, λ2, λ3, and λ4 are regularization parameters.In the proposed object tracking formulation in (4), we should minimize the rank of the matrix for features of all object candidates. Since there is no closed form solution for the rank minimization problem, we replace the rank minimizing of matrix with its convex envelope by the nuclear norm as W*. Moreover, mining similarities between all particle structures can improve the tracking results. However, in the object tracking process, some candidates are completely different from others when particles are sampled from an abnormally large region. In order to address this problem, we place the matrix W in shared feature W1,2 and nonshared sparse feature W1,1. The shared inlier feature exploits the similarities of particles while the nonshared sparse feature considers possible appearance variations of object and background between candidates, and only a small number of candidates are required to reliably represent the observation of each candidate. In order to reduce sparse errors, we minimize the l1,1 norm of error matrix E. This error assumption has been originally introduced in [9] in the presence of object occlusion.In order to solve this objective function in (4), we introduce three equality constraints and slack variables such as W1, W2, and W3 as
(5)min⁡W1,W2,W3,Eλ1W1*+λ2W21,255+λ3W31,1+λ4E1,1s.t.Y=UW+E,W=W1,W=W2,W=W3.555The above mentioned problem can be minimized using the conventional inexact augmented Lagrange multiplier (IALM) method [24] that has well-defined convergence properties for nonsmooth optimization which has been used in matrix rank minimization problems. This method is an iterative process that employs the Lagrangian function by adding quadratic penalty terms that assign high cost to the infeasible data and admit closed form updates for each unknown variable. Since the alternating direction method (ADM) [25] is introduced for the low-rank matrix completion and is based on the alternating direction augmented Lagrangian method, we employ ADM for solving minimization of ALM functions.


### 2.2.  Optimization

To solve the objective function given in (5), we formulate the ALM-based ADM model [24, 26] as
(6)LW,E,M1-4=λ1W1*+λ2W21,2+λ3W31,1+λ4E1,1+M1,W1-W+M2,W2-W+M3,W3-W+α2W1-WF2+α2W2-WF2+α2W3-WF2+M4,Y-UW-E+α2Y-UW-EF2,
where M1, M2, M3, and M4 are Lagrangian multipliers, CF=∑i‍∑j‍|cij|2 is called Frobenius norm of matrix C, and α>0 is a penalty parameter.The proposed strategy for given variable update is performed by computing sparse coefficients based on the low-rank representation with updated error and jointly sparse features. Thus, we first update the sparse errorE of the observation matrix Y by referring to the proof [24] as
(7)Ek+1=argmin⁡Eλ4αkE1,1+12E-UWk-Y+1αkM4kF2=sign⁡Pmax⁡0,1-λ4αkP,
where P=UWk-Y+(1/αk)M4k.For updating low-rank variableW1, we employ the proof in [27] such that low-rank matrix approximation problem with F-norm data fidelity can be solved by a soft-thresholding operation on the singular values of observation matrix as
(8)W1k+1=argmin⁡W1λ1αkW1*+12W1-Wk+1αkM1kF2=URSλ4/αk(ΣR),
where Sλ1/αk(ΣR)ii=max⁡(0,(ΣR)ii-(λ1/αk)) and R=Wk+(1/αk)M1k.We update theW2 and W3 referring to the proof [24] as
(9)W2k+1=argmin⁡W2λ2αkW21,2+12W2-Wk+1αkM2kF2=max⁡0,1-λ2αkWk+1/αkM2kWk+1αkM2k,W3k+1=argmin⁡W3λ3αkW31,1+12W3-Wk+1αkM3kF2=sign⁡Wk+1αkM3k×max⁡0,1-λ3αkWk+1αkM3k.The ADM can perform minimization with its alternative property; thus we formulate the objective function for updating sparse coefficientW based on (6) as
(10)〈M1,W-W1〉+〈M2,W-W2〉+〈M3,W-W3〉+α2W-W1F2+α2W-W2F2+α2W-W3F2+M4,W-UY-E+α2W-UY-EF2.W is updated with the already updated sparse error Ek+1, low-rank representation W1k+1, l1,2 norm W2k+1, and l1,1 norm W3k+1 using the following model:
(11)Wk+1=argmin⁡WF(W),s.t.FW=12W-W1k+1-1αkM1kF2+12W-W2k+1-1αkM2kF2+12W-W3k+1-1αkM3kF2+12W-U⊤Y-Ek+1+1αkM4kF2.
We obtain the closed form update framework as
(12)Wk+1=Jτ/δWk-12δ∇FWk,
where ∇F(Wk) is the partial derivative of F(W) with respect to Wk and Jτ/δ(x) is a component-wise soft-thresholding operator defined by [28] such that if |x|≤τ/δ,Jτ/δ(x)=0; otherwise, Jτ/δ(x)=x-sign⁡(x)τ/δ. We set τ=0.25 and δ=1.Then, we update Lagrange multipliers as(13)M1k+1=M1k+αkW1k+1-MW1k+1+M1kαk,M2k+1=M2k+αkW2k+1-MW2k+1+M2kαk,M3k+1=M3k+αkW3k+1-MW3k+1+M3kαk,M4k+1=M4k+αkEk+1-MEk+1+M4kαk,
where M(A)ij=max⁡(aij,0).


### 2.3. Convergence

The convergence of the proposed object tracking algorithm can be guaranteed using the Karush-Kuhn-Tucker (KKT) point approach by referring to linearized ADM with adaptive penalty (LADMAP) approach [26]. The LADMAP [26] aims to solve the following type of convex problems:
(14)min⁡x,yf(x)+g(y),s.t.A(x)+B(y)=c,
where x, y, and c could be either vectors or matrices, f and g are convex functions, and A and B are linear mappings.In many problems,f and g are vector or matrix norms, and when A and B are identity mappings, the augmented Lagrangian functions of (14) for minimizing x and y have closed form solutions. However, when A and B are not identity mappings, they may not be easy to solve. Therefore, Lin et al. [26] proposed linearizing the quadratic penalty term in the augmented Lagrangian function and adding a proximal term for updating x and y, resulting in the following updating scheme:
(15)xk+1=argmin⁡xfx+μkηA2×x-xk+A*γk+μkAxk+Byk-cμkηA2,yk+1=argmin⁡yg(y)+μkηB2×y-yk+B*γk+μkAxk+1+Byk-cμkηB2,γk+1=γk+μk[A(xk+1)+B(yk+1)-c],
where γ is the Lagrange multiplier, μ is the penalty parameter, and ηA>0 and ηB>0 are some parameters for each norm. Lin et al. [26] proposed a strategy to adaptively update the penalty parameter μ and proved that when μ is nondecreasing and is upper bound and ηA>A2 and ηB>B2, then (xk,yk) converges to an optimal solution to (14), where A and B are the operator norm of A and B, respectively.For updating the penalty parameterα in (6) for the proposed problem, we apply the concept of LADMAP, where x, y, c, and γ are W, E, Y, and M1-4, respectively, in (6), with some algebra:
(16)αk+1=min⁡(αmax⁡,ραk),
where αmax⁡ is an upper bound of {αk}. The value ρ is decided as
(17)ρ=ρ0,ifαk·max⁡Ek+1-EkF,Wk+1-WkFYF<ε11,otherwise,
where ρ0≥1 is a constant, and we used ρ0=1.9 in this work.The iterations equations (7)–(13) and (16)-(17) stop when the following two conditions are satisfied:
(18)Wk+1+Ek+1-YFYF<ε2,(19)αk·max⁡⁡Ek+1-EkF,Wk+1-WkFYF<ε1,
where ε1>0 and ε2>0 are small thresholds.The above two stopping criteria are based on the KKT conditions of problem (6). Algorithm 1 summarizes the overall algorithm for the proposed low-rank representation-based multitask feature learning with joint sparsity.Algorithm 1:The algorithm for low-rank representation-based multitask feature learning.
(1) Input: A data set ofn data points Y=[y1,y2,…,yn], and parameters λ1, λ2, λ3, λ4.
(2) Output: Optimal coefficientWopt, and errors Eopt
(3) Initialization: SetW0=0, E0=0,  M10=0, M20=0, M30=0, M40=0,  W10=0, W20=0, W30=0,
ε
1
<
ε
2, and 0<α0≪αmax⁡
(4)Iterate until (18) and (19) is not satisfied:
Fix other variables and updateE using (7)
Fix other variables and updateW1 using (8)
Fix other variables and updateW2 and W3 using (9) and (10)
Fix other variables and updateW using (12)
UpdateM1, M2, M3, M4 and parameters using (13)
Updateα using (16) and (17)
(5)End


### 2.4. Object Tracking

Given a set of observed images at thetth frame Yt={Y1,Y2,…,Yt}, the goal of object tracking is to recursively estimate the state xt, maximizing the following state distribution:
(20)pxt∣Yt∝pYt∣xt∫pxt∣xt-1px∣Yt-1dxt-1,
where p(xt∣xt-1) denotes the motion model between two temporally consecutive states and p(Yt∣xt) indicates the likelihood function.In the motion model, we regard the state variablext as six affine parameters [4] such as horizontal and vertical translations, rotation, scale, aspect ratio, and skew such as xt=[xt,yt,θt,st,βt,ϕt]. The motion model is assumed to a have random Gaussian distribution such as p(xt∣xt-1)=N(xt;xt-1,Φ), where Φ is a diagonal covariance matrix.The solution of the proposed algorithm in Algorithm1 can be obtained by minimizing the following functional as
(21)min⁡W(i),E(i)12Yi-UWi-EiF2+βEi1,1,
where i indicates the ith sample data of the state x and a reconstruction error for the nonoccluded region of the object is given as Y(i)-UW(i)-E(i).The likelihood function can be formulated by the reconstruction error given in [29]
(22)pYi∣xi=exp⁡-Yi-UWiF2.This likelihood function, however, cannot deal with severe appearance deformations. For this reason, the likelihood function is modified by an additionally labeled penalty constraint about the similarity in neighboring error matrices for the deformed region of the object such as|(1-A(i+1))-(1-A(i))|, where A(i) and A(i+1), respectively, represent matrices with nonzero elements of E(i) and E(i+1). Thus, the proposed likelihood function is given as
(23)pY(i)∣x(i)=exp⁡-Ai⊙Yi-UWiF2Ai⊙Yi-UWiF2+β∑‍(1-A(i+1))-(1-A(i)),
where ⊙ is the element-wise multiplication of matrices.


## 2.1. Low-Rank Representation of Object

RPCA [20] was recently introduced to recover low-rank features in learning for the reduced subspace. Given a sparse matrix Y with corrupted observation, RPCA attempts to exactly recover the low-rank matrix Z and minimize sparse error E. Let Z*=∑i‍σi(Z) denote the nuclear norm of the low-rank matrix Z such as the sum of singular values of Z. Under this assumption, the principal component pursuit (PCP) is defined as in the following minimization:
(1)min⁡Z,EZ*+λE1,1,s.t.Y=Z+E,5555
where ∥·∥1,1 represents the l1,1 norm and λ is a regularization parameter.The assumption under RPCA framework [20], for disentangling the low-rank and sparse component, is that Z has singular vectors and is not sparse. The singular value decomposition of Z can be expressed as
(2)Z=UΣV⊤=∑i=1N‍σiuivi⊤,
where N is the rank of Z, σ1,…,σN are positive singular values, and U=[u1,…,uN] and V=[v1,…,vN] are the matrices of left- and right-singular projection vectors.The object tracking problem can be solved under the RPCA framework. Suppose we haven sampled particles and the correspondingly observed candidate of an object Y=[y1,…,yn] at time t. Each observation can be represented as a linear combination of m basis vectors {u1,…,um}, which spans the data space such as Y=UtWt, where Ut=[u1,…,um], and each column of Wt=[w1,…,wn] indicates the discriminative feature representation of each particle observation. In this paper, we utilize the strength of both subspace learning and sparse representation for object appearance model in the principal component analysis (PCA) as [21]
(3)Y=UW+E.In feature learning literature, the multitask feature learning [22, 23] employs the l2,1 norm minimization to involve features selection across tasks under a strict assumption that all tasks share a common underlying representation.The goal of the proposed object tracking framework is to search particles that have the most similar feature to previous tracking result. Since particles are densely sampled around the current object state, in order to estimate the optimal low-rank features in iterative steps, we focus on all possible nonsmooth sparse errors, joint sparsity of features based on low-rank, andl1,1 and l1,2 constraints that produce solution for the within- and between-feature-tasks sparsity. With this consideration, we formulate the following object tracking problem by adopting three equality constraints as
(4)min⁡W,Eλ1W*+λ2W1,2+λ3W1,1+λ4E1,1s.t.Y=UW+E,5555555555555555555555555
where Cp,q=(∑j‍(∑i‍|cij|p)q/p)1/q is called p, q norm of matrix C and λ1, λ2, λ3, and λ4 are regularization parameters.In the proposed object tracking formulation in (4), we should minimize the rank of the matrix for features of all object candidates. Since there is no closed form solution for the rank minimization problem, we replace the rank minimizing of matrix with its convex envelope by the nuclear norm as W*. Moreover, mining similarities between all particle structures can improve the tracking results. However, in the object tracking process, some candidates are completely different from others when particles are sampled from an abnormally large region. In order to address this problem, we place the matrix W in shared feature W1,2 and nonshared sparse feature W1,1. The shared inlier feature exploits the similarities of particles while the nonshared sparse feature considers possible appearance variations of object and background between candidates, and only a small number of candidates are required to reliably represent the observation of each candidate. In order to reduce sparse errors, we minimize the l1,1 norm of error matrix E. This error assumption has been originally introduced in [9] in the presence of object occlusion.In order to solve this objective function in (4), we introduce three equality constraints and slack variables such as W1, W2, and W3 as
(5)min⁡W1,W2,W3,Eλ1W1*+λ2W21,255+λ3W31,1+λ4E1,1s.t.Y=UW+E,W=W1,W=W2,W=W3.555The above mentioned problem can be minimized using the conventional inexact augmented Lagrange multiplier (IALM) method [24] that has well-defined convergence properties for nonsmooth optimization which has been used in matrix rank minimization problems. This method is an iterative process that employs the Lagrangian function by adding quadratic penalty terms that assign high cost to the infeasible data and admit closed form updates for each unknown variable. Since the alternating direction method (ADM) [25] is introduced for the low-rank matrix completion and is based on the alternating direction augmented Lagrangian method, we employ ADM for solving minimization of ALM functions.


## 2.2.  Optimization

To solve the objective function given in (5), we formulate the ALM-based ADM model [24, 26] as
(6)LW,E,M1-4=λ1W1*+λ2W21,2+λ3W31,1+λ4E1,1+M1,W1-W+M2,W2-W+M3,W3-W+α2W1-WF2+α2W2-WF2+α2W3-WF2+M4,Y-UW-E+α2Y-UW-EF2,
where M1, M2, M3, and M4 are Lagrangian multipliers, CF=∑i‍∑j‍|cij|2 is called Frobenius norm of matrix C, and α>0 is a penalty parameter.The proposed strategy for given variable update is performed by computing sparse coefficients based on the low-rank representation with updated error and jointly sparse features. Thus, we first update the sparse errorE of the observation matrix Y by referring to the proof [24] as
(7)Ek+1=argmin⁡Eλ4αkE1,1+12E-UWk-Y+1αkM4kF2=sign⁡Pmax⁡0,1-λ4αkP,
where P=UWk-Y+(1/αk)M4k.For updating low-rank variableW1, we employ the proof in [27] such that low-rank matrix approximation problem with F-norm data fidelity can be solved by a soft-thresholding operation on the singular values of observation matrix as
(8)W1k+1=argmin⁡W1λ1αkW1*+12W1-Wk+1αkM1kF2=URSλ4/αk(ΣR),
where Sλ1/αk(ΣR)ii=max⁡(0,(ΣR)ii-(λ1/αk)) and R=Wk+(1/αk)M1k.We update theW2 and W3 referring to the proof [24] as
(9)W2k+1=argmin⁡W2λ2αkW21,2+12W2-Wk+1αkM2kF2=max⁡0,1-λ2αkWk+1/αkM2kWk+1αkM2k,W3k+1=argmin⁡W3λ3αkW31,1+12W3-Wk+1αkM3kF2=sign⁡Wk+1αkM3k×max⁡0,1-λ3αkWk+1αkM3k.The ADM can perform minimization with its alternative property; thus we formulate the objective function for updating sparse coefficientW based on (6) as
(10)〈M1,W-W1〉+〈M2,W-W2〉+〈M3,W-W3〉+α2W-W1F2+α2W-W2F2+α2W-W3F2+M4,W-UY-E+α2W-UY-EF2.W is updated with the already updated sparse error Ek+1, low-rank representation W1k+1, l1,2 norm W2k+1, and l1,1 norm W3k+1 using the following model:
(11)Wk+1=argmin⁡WF(W),s.t.FW=12W-W1k+1-1αkM1kF2+12W-W2k+1-1αkM2kF2+12W-W3k+1-1αkM3kF2+12W-U⊤Y-Ek+1+1αkM4kF2.
We obtain the closed form update framework as
(12)Wk+1=Jτ/δWk-12δ∇FWk,
where ∇F(Wk) is the partial derivative of F(W) with respect to Wk and Jτ/δ(x) is a component-wise soft-thresholding operator defined by [28] such that if |x|≤τ/δ,Jτ/δ(x)=0; otherwise, Jτ/δ(x)=x-sign⁡(x)τ/δ. We set τ=0.25 and δ=1.Then, we update Lagrange multipliers as(13)M1k+1=M1k+αkW1k+1-MW1k+1+M1kαk,M2k+1=M2k+αkW2k+1-MW2k+1+M2kαk,M3k+1=M3k+αkW3k+1-MW3k+1+M3kαk,M4k+1=M4k+αkEk+1-MEk+1+M4kαk,
where M(A)ij=max⁡(aij,0).


## 2.3. Convergence

The convergence of the proposed object tracking algorithm can be guaranteed using the Karush-Kuhn-Tucker (KKT) point approach by referring to linearized ADM with adaptive penalty (LADMAP) approach [26]. The LADMAP [26] aims to solve the following type of convex problems:
(14)min⁡x,yf(x)+g(y),s.t.A(x)+B(y)=c,
where x, y, and c could be either vectors or matrices, f and g are convex functions, and A and B are linear mappings.In many problems,f and g are vector or matrix norms, and when A and B are identity mappings, the augmented Lagrangian functions of (14) for minimizing x and y have closed form solutions. However, when A and B are not identity mappings, they may not be easy to solve. Therefore, Lin et al. [26] proposed linearizing the quadratic penalty term in the augmented Lagrangian function and adding a proximal term for updating x and y, resulting in the following updating scheme:
(15)xk+1=argmin⁡xfx+μkηA2×x-xk+A*γk+μkAxk+Byk-cμkηA2,yk+1=argmin⁡yg(y)+μkηB2×y-yk+B*γk+μkAxk+1+Byk-cμkηB2,γk+1=γk+μk[A(xk+1)+B(yk+1)-c],
where γ is the Lagrange multiplier, μ is the penalty parameter, and ηA>0 and ηB>0 are some parameters for each norm. Lin et al. [26] proposed a strategy to adaptively update the penalty parameter μ and proved that when μ is nondecreasing and is upper bound and ηA>A2 and ηB>B2, then (xk,yk) converges to an optimal solution to (14), where A and B are the operator norm of A and B, respectively.For updating the penalty parameterα in (6) for the proposed problem, we apply the concept of LADMAP, where x, y, c, and γ are W, E, Y, and M1-4, respectively, in (6), with some algebra:
(16)αk+1=min⁡(αmax⁡,ραk),
where αmax⁡ is an upper bound of {αk}. The value ρ is decided as
(17)ρ=ρ0,ifαk·max⁡Ek+1-EkF,Wk+1-WkFYF<ε11,otherwise,
where ρ0≥1 is a constant, and we used ρ0=1.9 in this work.The iterations equations (7)–(13) and (16)-(17) stop when the following two conditions are satisfied:
(18)Wk+1+Ek+1-YFYF<ε2,(19)αk·max⁡⁡Ek+1-EkF,Wk+1-WkFYF<ε1,
where ε1>0 and ε2>0 are small thresholds.The above two stopping criteria are based on the KKT conditions of problem (6). Algorithm 1 summarizes the overall algorithm for the proposed low-rank representation-based multitask feature learning with joint sparsity.Algorithm 1:The algorithm for low-rank representation-based multitask feature learning.
(1) Input: A data set ofn data points Y=[y1,y2,…,yn], and parameters λ1, λ2, λ3, λ4.
(2) Output: Optimal coefficientWopt, and errors Eopt
(3) Initialization: SetW0=0, E0=0,  M10=0, M20=0, M30=0, M40=0,  W10=0, W20=0, W30=0,
ε
1
<
ε
2, and 0<α0≪αmax⁡
(4)Iterate until (18) and (19) is not satisfied:
Fix other variables and updateE using (7)
Fix other variables and updateW1 using (8)
Fix other variables and updateW2 and W3 using (9) and (10)
Fix other variables and updateW using (12)
UpdateM1, M2, M3, M4 and parameters using (13)
Updateα using (16) and (17)
(5)End


## 2.4. Object Tracking

Given a set of observed images at thetth frame Yt={Y1,Y2,…,Yt}, the goal of object tracking is to recursively estimate the state xt, maximizing the following state distribution:
(20)pxt∣Yt∝pYt∣xt∫pxt∣xt-1px∣Yt-1dxt-1,
where p(xt∣xt-1) denotes the motion model between two temporally consecutive states and p(Yt∣xt) indicates the likelihood function.In the motion model, we regard the state variablext as six affine parameters [4] such as horizontal and vertical translations, rotation, scale, aspect ratio, and skew such as xt=[xt,yt,θt,st,βt,ϕt]. The motion model is assumed to a have random Gaussian distribution such as p(xt∣xt-1)=N(xt;xt-1,Φ), where Φ is a diagonal covariance matrix.The solution of the proposed algorithm in Algorithm1 can be obtained by minimizing the following functional as
(21)min⁡W(i),E(i)12Yi-UWi-EiF2+βEi1,1,
where i indicates the ith sample data of the state x and a reconstruction error for the nonoccluded region of the object is given as Y(i)-UW(i)-E(i).The likelihood function can be formulated by the reconstruction error given in [29]
(22)pYi∣xi=exp⁡-Yi-UWiF2.This likelihood function, however, cannot deal with severe appearance deformations. For this reason, the likelihood function is modified by an additionally labeled penalty constraint about the similarity in neighboring error matrices for the deformed region of the object such as|(1-A(i+1))-(1-A(i))|, where A(i) and A(i+1), respectively, represent matrices with nonzero elements of E(i) and E(i+1). Thus, the proposed likelihood function is given as
(23)pY(i)∣x(i)=exp⁡-Ai⊙Yi-UWiF2Ai⊙Yi-UWiF2+β∑‍(1-A(i+1))-(1-A(i)),
where ⊙ is the element-wise multiplication of matrices.


## 3. Experimental Results

The proposed object tracking algorithm is implemented and tested using ten challenging sequences. Major challenging issues in the test sequences include scale variation, shape deformation, fast motion, out-of-plane rotation, background clutter, object rotation, occlusion, illumination variation, out of view, motion blur, and low resolution. The proposed method is compared with a number of state-of-the-art tracking algorithms such as SMTT [15], APGL1 [14], SPCA [21], ASL [2], ILRF [18], and RMTT [16].The proposed object tracking algorithm is implemented in MATLAB and processes 1.5 frames per second on a Pentium 2.7 GHz dual core PC without any hardware accelerator such as GPU. For each test sequence, the initial location of the object is manually selected in the first frame. Each image sample from the target and background is normalized to a32×32 patch.


### 3.1. Regularization Parametersλ1,λ2,λ3, and λ4

Regularization parameters in (4) are empirically chosen using the center pixel error criterion in [30].We fixλ4=1.0 and swap others since λ4 represents the sparse error matrix E while λ1,λ2, and λ3 are related to weight variables W1, W2, and W3, respectively. Parameters λ1, λ2, and λ3 are parameterized by a discrete set with 10 elements as {1e-4,1e-3,0.01,0.1,0.5,1.0,3.0,5.0,10.0,15.0}.We test different combinations ofλ1, λ2, and λ3 about three different images sequences having challenging issues such as occlusion, deformation, and scale variation with 1500 frames and compute the central pixel errors from all frames. For each λ1 in the discrete set with different λ2 and λ3, we produce 10×10 average center pixel errors. When tracking performance is acceptable for giving the fixed λ1, we average all the 10×10 center pixel errors. With this attempt, we set the regularization parameters as λ1=5, λ2=0.5, λ3=0.1, and λ4=1.0.


### 3.2. Quantitative Evaluation

For quantitative performance comparison, center pixel error evaluation method is used and overlap ratio criterion is computed. The center pixel error represents the distance between the predicted and the ground truth center pixels. Figure1 shows the result of center pixel errors of seven different object tracking algorithms for ten test sequences.Center pixel error. This figure shows center pixel error for ten test sequences. The proposed method is compared with six state-of-the-art methods.
(a)
Jogging 1
(b)
Jogging 2
(c)
Football 1
(d)
Freeman 3
(e)
Couple
(f)
Crossing
(g)
Liquor
(h)
Car Scale
(i)
Subway
(j)
SkiingThe overlap ratio criterion represents the ratio between the number of frames for a specific object to be completely tracked and the total number of frames in the image sequence. In order to decide whether the object is successfully tracked, we employ the overlapped score defined in [30]. Figure 2 shows overlap ratios between the ground truth region and the tracking region.Overlap ratio evaluation. This figure shows overlap ratios for ten test sequences. The proposed method is compared with six state-of-the-art methods.
(a)
Jogging 1
(b)
Jogging 2
(c)
Football 1
(d)
Freeman 3
(e)
Couple
(f)
Crossing
(g)
Liquor
(h)
Car Scale
(i)
Subway
(j)
Skiing


### 3.3. Qualitative Evaluation

Jogging 1 and Jogging 2 sequences include a variety of critical conditions, such as disappearing object, out-of-plane rotation, and deformation. Object deformation and out-of-plane rotation make all the existing methods except ASL [2] drift away object. On the other hand, the proposed tracking method can successfully track the object since it can represent the object appearance more completely using a large scale training data with efficient multitask feature learning for object representation.The moving object in the Football 1 sequence undergoes in- and out-of-plane rotation and background clutter. Experimental results demonstrate that the proposed method achieves the best tracking performance in this sequence. Other methods cannot avoid drift at some instances in the neighborhood of the60th frame.There is a blurry scale variation in Freeman 3 and Car Scale sequences. For this reason, it is difficult to predict the location of the moving object. Furthermore, it includes drastic appearance change caused by motion blur. The proposed method performs well since it can adapt to the scale and appearance change of the object and overcome the influence of motion blur by using joint sparsity-based object appearance representation.In addition to scale variation and in- and out-of-plane object rotations, Couple and Crossing sequences include a critical factor such as fast motion. The fast motion can be involved by both camera and object. For tracking an object in Crossing sequence, the proposed method and SPCA [21] methods perform very well whereas other methods lost their object in neighborhood of the 30th and 80th frames.The Liquor sequence contains severe motion blur, scale and illumination variation, and fast motion. Although full occlusion occurs by a bottle with the similar color, the proposed tracking method successfully tracks the object without drifting.In the Subway sequence, object's information is lost by discriminant factor such as background clutter and the total occlusion. The proposed method can successfully track the moving object since it preserves the sparsity of object appearance with optimal sparse coding using low-rank feature representation with considering the joint sparsity. Other trackers except ILRFT [18] and RMTT [16] drift in the neighborhood of the 20th and 40th frames.The Skiing sequence contains severely deformed object. The proposed method successfully performs tracking due to its novel object likelihood function defined in (21). It employs more refined likelihood function formulated by the weighted reconstruction error for rigid object regions and by the labeling penalty constraint about the similarity in residual matrices for deformed object regions as well. Figure 3 shows the overall tracking results in each test sequence. The overlapped ratio between the ground truth and predicted tracking region using proposed method turns to 0 at around frame 40, while the center pixel error between the ground truth and predicted tracking region using proposed method still increases. From this fact, we conclude that the proposed method loses tracking in around frame 40, while other state-of-the-art tracking methods totally lose their tracking in around frame 10.Object tracking results using seven different algorithms on ten test sequences. They are Jogging 1, Jogging 2, Football 1, Freeman 3, Couple, Crossing, Liquor, Car Scale, Subway, and Skiing, respectively, from the top row to the bottom row.
(a)
(b)
(c)
(d)
(e)
(f)
(g)
(h)
(i)
(j)


## 3.1. Regularization Parametersλ1,λ2,λ3, and λ4

Regularization parameters in (4) are empirically chosen using the center pixel error criterion in [30].We fixλ4=1.0 and swap others since λ4 represents the sparse error matrix E while λ1,λ2, and λ3 are related to weight variables W1, W2, and W3, respectively. Parameters λ1, λ2, and λ3 are parameterized by a discrete set with 10 elements as {1e-4,1e-3,0.01,0.1,0.5,1.0,3.0,5.0,10.0,15.0}.We test different combinations ofλ1, λ2, and λ3 about three different images sequences having challenging issues such as occlusion, deformation, and scale variation with 1500 frames and compute the central pixel errors from all frames. For each λ1 in the discrete set with different λ2 and λ3, we produce 10×10 average center pixel errors. When tracking performance is acceptable for giving the fixed λ1, we average all the 10×10 center pixel errors. With this attempt, we set the regularization parameters as λ1=5, λ2=0.5, λ3=0.1, and λ4=1.0.


## 3.2. Quantitative Evaluation

For quantitative performance comparison, center pixel error evaluation method is used and overlap ratio criterion is computed. The center pixel error represents the distance between the predicted and the ground truth center pixels. Figure1 shows the result of center pixel errors of seven different object tracking algorithms for ten test sequences.Center pixel error. This figure shows center pixel error for ten test sequences. The proposed method is compared with six state-of-the-art methods.
(a)
Jogging 1
(b)
Jogging 2
(c)
Football 1
(d)
Freeman 3
(e)
Couple
(f)
Crossing
(g)
Liquor
(h)
Car Scale
(i)
Subway
(j)
SkiingThe overlap ratio criterion represents the ratio between the number of frames for a specific object to be completely tracked and the total number of frames in the image sequence. In order to decide whether the object is successfully tracked, we employ the overlapped score defined in [30]. Figure 2 shows overlap ratios between the ground truth region and the tracking region.Overlap ratio evaluation. This figure shows overlap ratios for ten test sequences. The proposed method is compared with six state-of-the-art methods.
(a)
Jogging 1
(b)
Jogging 2
(c)
Football 1
(d)
Freeman 3
(e)
Couple
(f)
Crossing
(g)
Liquor
(h)
Car Scale
(i)
Subway
(j)
Skiing


## 3.3. Qualitative Evaluation

Jogging 1 and Jogging 2 sequences include a variety of critical conditions, such as disappearing object, out-of-plane rotation, and deformation. Object deformation and out-of-plane rotation make all the existing methods except ASL [2] drift away object. On the other hand, the proposed tracking method can successfully track the object since it can represent the object appearance more completely using a large scale training data with efficient multitask feature learning for object representation.The moving object in the Football 1 sequence undergoes in- and out-of-plane rotation and background clutter. Experimental results demonstrate that the proposed method achieves the best tracking performance in this sequence. Other methods cannot avoid drift at some instances in the neighborhood of the60th frame.There is a blurry scale variation in Freeman 3 and Car Scale sequences. For this reason, it is difficult to predict the location of the moving object. Furthermore, it includes drastic appearance change caused by motion blur. The proposed method performs well since it can adapt to the scale and appearance change of the object and overcome the influence of motion blur by using joint sparsity-based object appearance representation.In addition to scale variation and in- and out-of-plane object rotations, Couple and Crossing sequences include a critical factor such as fast motion. The fast motion can be involved by both camera and object. For tracking an object in Crossing sequence, the proposed method and SPCA [21] methods perform very well whereas other methods lost their object in neighborhood of the 30th and 80th frames.The Liquor sequence contains severe motion blur, scale and illumination variation, and fast motion. Although full occlusion occurs by a bottle with the similar color, the proposed tracking method successfully tracks the object without drifting.In the Subway sequence, object's information is lost by discriminant factor such as background clutter and the total occlusion. The proposed method can successfully track the moving object since it preserves the sparsity of object appearance with optimal sparse coding using low-rank feature representation with considering the joint sparsity. Other trackers except ILRFT [18] and RMTT [16] drift in the neighborhood of the 20th and 40th frames.The Skiing sequence contains severely deformed object. The proposed method successfully performs tracking due to its novel object likelihood function defined in (21). It employs more refined likelihood function formulated by the weighted reconstruction error for rigid object regions and by the labeling penalty constraint about the similarity in residual matrices for deformed object regions as well. Figure 3 shows the overall tracking results in each test sequence. The overlapped ratio between the ground truth and predicted tracking region using proposed method turns to 0 at around frame 40, while the center pixel error between the ground truth and predicted tracking region using proposed method still increases. From this fact, we conclude that the proposed method loses tracking in around frame 40, while other state-of-the-art tracking methods totally lose their tracking in around frame 10.Object tracking results using seven different algorithms on ten test sequences. They are Jogging 1, Jogging 2, Football 1, Freeman 3, Couple, Crossing, Liquor, Car Scale, Subway, and Skiing, respectively, from the top row to the bottom row.
(a)
(b)
(c)
(d)
(e)
(f)
(g)
(h)
(i)
(j)


## 4. Conclusion

In this paper, we present an effective, robust object tracking method using a multitask feature learning-based low-rank representation with joint sparsity. In order to overcome the limitation of existing sparse representation-based object tracking methods, we employ the novel optimization process of low-rank representation of objects by using a recently proposed model minimization method. The efficient subspace learning-based sparse coding and simultaneous update method of both optimal sparse codes and error matrix can be appropriately updated in the process of tracking in case of severe appearance variation. Experimental results demonstrate that the proposed method can successfully track objects in various video sequences with critical issues such as occlusion, deformation, plane rotations, background clutter, motion blur, scale and illumination variations, and fast motion.



---

*Source: 147353-2014-11-23.xml*