# Robust Online Object Tracking Based on Feature Grouping and 2DPCA

Authors: Ming-Xin Jiang; Jun-Xing Zhang; Min Li
Journal: Mathematical Problems in Engineering
 (2013)

---

## Abstract

We present an online object tracking algorithm based on feature grouping and two-dimensional principal component analysis (2DPCA). Firstly, we introduce regularization into the 2DPCA reconstruction and develop an iterative algorithm to represent an object by 2DPCA bases. Secondly, the object templates are grouped into a more discriminative image and a less discriminative image by computing the variance of the pixels in multiple frames. Then, the projection matrix is learned according to the more discriminative image and the less discriminative image, and the samples are projected. The object tracking results are obtained using Bayesian maximum a posteriori probability estimation. Finally, we employ a template update strategy which combines incremental subspace learning and the error matrix to reduce tracking drift. Compared with other popular methods, our method reduces the computational complexity and is very robust to abnormal changes. Both qualitative and quantitative evaluations on challenging image sequences demonstrate that the proposed tracking algorithm achieves more favorable performance than several state-of-the-art methods.


---

## Body

## 1. Introduction

Online object tracking is a fundamental problem in many computer vision applications such as surveillance, driver assistance systems, and human-computer interactions [1–4]. Although researchers have made great progresses in this area, object tracking remains a challenging problem due to the difficulty arising from the appearance variability of an object. Intrinsic and extrinsic changes inevitably cause large appearance variation. Due to the nature of the tracking problem, an effective appearance model is of prime importance for the success of a tracking algorithm [5–8].In recent years, as a popular dimensionality reduction and feature extraction technique, linear subspace learning has been successfully used in robust visual tracking. Supervised discriminative methods for classification and regression have also been exploited to solve visual tracking problems. For example, Avidan developed a tracking algorithm that employs the support vector machine (SVM) classifier within an optic flow framework [9]. Along similar lines, Williams et al. developed a method in which an SVM-based regressor was used for tracking [10]. As a result of training the regressor on in-plane image motion, this method is not effective in tracking objects with out-of-plane movements. In [11], the author combines the sparse coding and Kalman filtering together and chooses the color histogram and gradient histogram as features to track the object. The template updating strategy of the algorithm is to replace a random template of the original template library with the last tracking result. This updating strategy can easily introduce tracking errors when abnormal changes happen to the object, which would result in failure of tracking. A method by casting object tracking as a sparse approximation problem in a particle filter framework is proposed in [12]. The author solves the problem of object occlusion through the introduction of trivial template which, however, extends the number of templates greatly and increases the computational complexity. In that case, the practical value of algorithm is greatly reduced.Motivated by the abovementioned discussions, we propose an online object tracking algorithm based on feature grouping and 2DPCA. Firstly, we introduce regularization into the 2DPCA reconstruction and develop an iterative algorithm to represent an object by 2DPCA bases. Secondly, the object templates are grouped into a more discriminative image and a less discriminative image by computing the variance of the pixels in multiple frames. Then, the projection matrix is learned according to the more discriminative image and the less discriminative image, and the samples are projected using the projection matrix. The object tracking results are obtained using Bayesian maximum a posteriori probability (MAP) estimation (Figures1, 2, and 3). Finally, to further reduce tracking drift, we employ a template update strategy which combines incremental subspace learning and the error matrix. This strategy adapts the template to the appearance change of the target and reduces the influence of the occluded target template as well. The experimental results show that our proposed method has strong robustness to abnormal changes.Tracking results of test video “Lemming.”
(a)
(b)
(c)
(d)
(e)
(f)Tracking results of test video “Car4.”
(a)
(b)
(c)
(d)
(e)
(f)Tracking results of test video “Singer1.”
(a)
(b)
(c)
(d)
(e)
(f)


## 2. Robust Online Object Tracking Based on Feature Grouping and 2DPCA

### 2.1. The Theory of 2DPCA

Principal component analysis (PCA) is a well-established linear dimension-reduction technique, which has been widely used in many areas (such as face recognition [13]). It finds the projection directions along which the reconstruction error to the original data is minimum and projects the original data into a lower dimensional space spanned by those directions corresponding to the top eigenvalues. Recent studies demonstrate that two-dimensional principal component analysis (2DPCA) could achieve performance comparable to PCA with less computational cost.Given a series of image matricesY=[Y1;Y2;…;Yd], 2DPCA aims to obtain an orthogonal left-projection matrix U, an orthogonal right-projection matrix V, and the projection coefficients A=[A1;A2;…;Ad] by solving the following objective function:
(1)minU,V,Ai1d∑i=1d∥Yi-UAiV′∥F2.Then the coefficientAi can be approximated by Ai≈U′YiV. We note that the underlying assumption of (6) is that the error term is Gaussian distributed with small variances. This assumption is not able to deal with partial occlusion as the error term cannot be modeled with small variances when occlusion occurs. In this paper, we propose an object tracking algorithm by using 2DPCA basis matrices and an additional MLE error matrix Y≈UAV′+e.Let the objective function be(2)L(A,E)=12∥Y-UAV′-E∥F2+λ∥e∥1,
the problem is
(3)minA,EL(A,E)s.t.U′U=I;V′V=I,
where Y denotes an observation matrix, A indicates its corresponding projection coefficient, λ is a regularization parameter, and e describes the error matrix.


### 2.2. Feature Grouping

In object tracking problem,T=[t1,t2,…,tn]∈ℝd×n consists of n templates and forms the object template library, where ti∈ℝd,d≫n. In our experiments, we make n=10 and the object template size 32×32; that is, d=1024. The result image block in current frame is denoted as y,y∈ℝd, which has the same size as object template ti.We would like to decompose each templateti,i=1,2,…,n, into a more discriminative image tia and a less discriminative image tib. First, we rewrite ti as ti,j,j=1,2,…d, and compute the variance of each pixel in each template. if the pixel ti,j has a smaller variance, we can think that this pixel is more stable. Based on this heuristic, we can decompose those templates into a more discriminative image and a less discriminative image.Denote byt-j the mean of the templates ti,j. The variance of the jth pixel in template ti,j is
(4)σj=1d∑j=1d(ti,j-t-j).We want to put those pixels having smallerσj into a more discriminative image and the remaining into a less discriminative image tib.After decomposing, each template can be written asti=tia+tib,i=1,2,…,n, and we have T=Ta+Tb. However, if we learn the projection matrix P only based on Ta, the result cannot be very satisfying because Tb is also useful for determining the projection direction. To effectively exploit the information in both Ta and Tb, we propose to learn a subspace where the energy in Ta is well preserved and the energy in Tb is suppressed. Denote by t-, t-a, and t-b the mean vectors of T, Ta, and Tb, respectively, and let t-i=ti-t-, t-ia=tia-t-a, and t-ib=tib-t-b be the centralized image vectors. Accordingly we have the centralized datasets T-, T-a, and T-b. Clearly, we have t-=t-a+t-b, t-i=t-ia+t-ib, and Pt-i=Pt-ia+Pt-ib. After projection, the average energy of Pt-ia is
(5)Ea=1n∑i=1n∥Pt-ia∥22=1n∑i=1n(Pt-ia)T(Pt-ia)=tr{P(1nT-aT-aT)PT}=tr{PSaPT},
where Sa=(1/n)T-aT-aT is the total scatter matrix of Ta and “tr” is the matrix trace operator.Similarly, the average energy ofPt-ib is
(6)Eb=1n∑i=1n∥Pt-ib∥22=tr{PSbPT},
where Sb=(1/n)T-bT-bT is the total scatter matrix of Tb.To preserve theTa while suppressing the Tb, we seek for a projection matrix P to maximize the energy Ea while minimizing the energy Eb by solving the following optimization problem:
(7)JP=argmaxPEaEb=argmaxPtr{PSaPT}tr{PSbPT}.An equivalent form of (4) is
(8)JP=argmaxPEaEb=argmaxPtr(PSaPT)s.t.PSaPT=I.Apparently, the desiredP can be computed by using generalized eigenvalue decomposition; that is, matrix P is composed of the generalized eigenvectors of Saw=λSbw corresponding to the p largest eigenvalues.


## 2.1. The Theory of 2DPCA

Principal component analysis (PCA) is a well-established linear dimension-reduction technique, which has been widely used in many areas (such as face recognition [13]). It finds the projection directions along which the reconstruction error to the original data is minimum and projects the original data into a lower dimensional space spanned by those directions corresponding to the top eigenvalues. Recent studies demonstrate that two-dimensional principal component analysis (2DPCA) could achieve performance comparable to PCA with less computational cost.Given a series of image matricesY=[Y1;Y2;…;Yd], 2DPCA aims to obtain an orthogonal left-projection matrix U, an orthogonal right-projection matrix V, and the projection coefficients A=[A1;A2;…;Ad] by solving the following objective function:
(1)minU,V,Ai1d∑i=1d∥Yi-UAiV′∥F2.Then the coefficientAi can be approximated by Ai≈U′YiV. We note that the underlying assumption of (6) is that the error term is Gaussian distributed with small variances. This assumption is not able to deal with partial occlusion as the error term cannot be modeled with small variances when occlusion occurs. In this paper, we propose an object tracking algorithm by using 2DPCA basis matrices and an additional MLE error matrix Y≈UAV′+e.Let the objective function be(2)L(A,E)=12∥Y-UAV′-E∥F2+λ∥e∥1,
the problem is
(3)minA,EL(A,E)s.t.U′U=I;V′V=I,
where Y denotes an observation matrix, A indicates its corresponding projection coefficient, λ is a regularization parameter, and e describes the error matrix.


## 2.2. Feature Grouping

In object tracking problem,T=[t1,t2,…,tn]∈ℝd×n consists of n templates and forms the object template library, where ti∈ℝd,d≫n. In our experiments, we make n=10 and the object template size 32×32; that is, d=1024. The result image block in current frame is denoted as y,y∈ℝd, which has the same size as object template ti.We would like to decompose each templateti,i=1,2,…,n, into a more discriminative image tia and a less discriminative image tib. First, we rewrite ti as ti,j,j=1,2,…d, and compute the variance of each pixel in each template. if the pixel ti,j has a smaller variance, we can think that this pixel is more stable. Based on this heuristic, we can decompose those templates into a more discriminative image and a less discriminative image.Denote byt-j the mean of the templates ti,j. The variance of the jth pixel in template ti,j is
(4)σj=1d∑j=1d(ti,j-t-j).We want to put those pixels having smallerσj into a more discriminative image and the remaining into a less discriminative image tib.After decomposing, each template can be written asti=tia+tib,i=1,2,…,n, and we have T=Ta+Tb. However, if we learn the projection matrix P only based on Ta, the result cannot be very satisfying because Tb is also useful for determining the projection direction. To effectively exploit the information in both Ta and Tb, we propose to learn a subspace where the energy in Ta is well preserved and the energy in Tb is suppressed. Denote by t-, t-a, and t-b the mean vectors of T, Ta, and Tb, respectively, and let t-i=ti-t-, t-ia=tia-t-a, and t-ib=tib-t-b be the centralized image vectors. Accordingly we have the centralized datasets T-, T-a, and T-b. Clearly, we have t-=t-a+t-b, t-i=t-ia+t-ib, and Pt-i=Pt-ia+Pt-ib. After projection, the average energy of Pt-ia is
(5)Ea=1n∑i=1n∥Pt-ia∥22=1n∑i=1n(Pt-ia)T(Pt-ia)=tr{P(1nT-aT-aT)PT}=tr{PSaPT},
where Sa=(1/n)T-aT-aT is the total scatter matrix of Ta and “tr” is the matrix trace operator.Similarly, the average energy ofPt-ib is
(6)Eb=1n∑i=1n∥Pt-ib∥22=tr{PSbPT},
where Sb=(1/n)T-bT-bT is the total scatter matrix of Tb.To preserve theTa while suppressing the Tb, we seek for a projection matrix P to maximize the energy Ea while minimizing the energy Eb by solving the following optimization problem:
(7)JP=argmaxPEaEb=argmaxPtr{PSaPT}tr{PSbPT}.An equivalent form of (4) is
(8)JP=argmaxPEaEb=argmaxPtr(PSaPT)s.t.PSaPT=I.Apparently, the desiredP can be computed by using generalized eigenvalue decomposition; that is, matrix P is composed of the generalized eigenvectors of Saw=λSbw corresponding to the p largest eigenvalues.


## 3. Bayesian Map Estimation

We can regard object tracking as a hidden state variables’ Bayesian MAP estimation problem in the hidden Markov model; that is, with a set of observed samplesYt={y1,y2,…,yt}, we can estimate the hidden state variable xt using Bayesian MAP theory.According to the Bayesian theory,(9)p(xt∣Yt)∝p(yt∣xt)∫p(xt∣xt-1)p(xt-1∣Yt-1)dxt-1,
where p(xt∣xt-1) stands for a state transition model for two consecutive frames and p(yt∣xt) stands for an observation likelihood model. We can obtain the object’s best state in tth frame through maximum a posteriori probability estimation; that is,
(10)x^t=argmaxxtlp(xtl∣Yt),l=1,2,…,N,
where xtl stands for the lth sample of state variable xt in tth frame. In this paper, we choose N=400.


### 3.1. State Transition Model

We choose object’s motion affine transformation parameters as state variablext={xt,yt,θt,St,αt,ϕt}, where xt and yt, respectively, represent the x-direction and y-direction translation of the object in tth frame, θt stands for the rotation angle, St represents the scale change, αt stands for the aspect ratio, and ϕt stands for the direction of tilt.We assume that the state transition model follows the Gaussian distribution; that is,(11)p(xt∣xt-1)=N(xt;xt-1,Ψ),
where Ψ is a diagonal matrix whose diagonal elements are motion affine parameter’s variation σx2,σy2,σθ2,σS2,σα2, and σϕ2.


### 3.2. Observation Likelihood Model

We use object’s reconstruction error to build observation likelihood model; that is,(12)p(yt∣xt)=∏j=1,2,…,dℕ(ejt,μ,σ2),
where ℕ(·) means Gaussian distribution, μ and σ2, respectively, represent the mean and variation of Gaussian distribution, d stands for the number of pixels of an object template, and ejt stands for the reconstruction error of jth pixel of object templates in tth frame.


## 3.1. State Transition Model

We choose object’s motion affine transformation parameters as state variablext={xt,yt,θt,St,αt,ϕt}, where xt and yt, respectively, represent the x-direction and y-direction translation of the object in tth frame, θt stands for the rotation angle, St represents the scale change, αt stands for the aspect ratio, and ϕt stands for the direction of tilt.We assume that the state transition model follows the Gaussian distribution; that is,(11)p(xt∣xt-1)=N(xt;xt-1,Ψ),
where Ψ is a diagonal matrix whose diagonal elements are motion affine parameter’s variation σx2,σy2,σθ2,σS2,σα2, and σϕ2.


## 3.2. Observation Likelihood Model

We use object’s reconstruction error to build observation likelihood model; that is,(12)p(yt∣xt)=∏j=1,2,…,dℕ(ejt,μ,σ2),
where ℕ(·) means Gaussian distribution, μ and σ2, respectively, represent the mean and variation of Gaussian distribution, d stands for the number of pixels of an object template, and ejt stands for the reconstruction error of jth pixel of object templates in tth frame.


## 4. Experimental Results and Analysis

In order to show the robustness of the object tracking algorithm based on projection discussed in this paper, we choose several sets of public test videos taken under different environments to test the performance of our algorithm (Figures4, 5, and 6). Given the limited space, in this section we only list three of them to show the tracking results and error curves. Different abnormal changes have happened to the moving objects in chosen test videos such as occlusion, rotation, illumination variation, or scale variation (Table 1).Table 1
The description of test videos.
Name of test videos
Number of frames
Video description
Lemming
1336
Out-of-plane rotation, scale change, occlusion, and  background cluster
Car4
659
Illumination variation and scalevariation
Singer1
351
Illumination variation and  scale changeFigure 4
Quantitative evaluation in terms of center location error for test video “Lemming.”Figure 5
Quantitative evaluation in terms of center location error for test video “Car4.”Figure 6
Quantitative evaluation in terms of center location error for test video “Singer1.”The implementation of the algorithm is based on Windows operating system. The configuration of the computer is AMD Athlon (TM) X2 Dual Core QL-62 2.00 GHz, 1.74 GB memory. In order to evaluate the performance of the algorithm, we choose six currently most representative and classic tracking algorithms to do the comparison. The six classic algorithms are L1 Tracker [8], IVT Tracker [14], PN Tracker [15], VTD Tracker [16], MIL Tracker [17], and Frag Tracker [18].The average processing speeds of our method for different test videos are listed in Table2. The statistical data is obtained using Opencv2.2. Table 2 shows that the proposed algorithm can meet the real-time performance.Table 2
The average processing speed of our method.
Name of test videos
The average processing speed (Frame/S)
Lemming
32.57
Car4
35.13
Singer1
29.98


## 5. Conclusions

This paper presents a robust tracking algorithm via feature grouping and 2DPCA. In this work, we represent the tracked object by using 2DPCA bases and a feature grouping. With the proposed model, we can reduce the effect of abnormal pixels on tracking algorithms. We obtained the tracking result using Bayesian maximum a posteriori probability estimation framework and designed a stable and robust tracker. Then, we explicitly take partial occlusion and misalignment into account for appearance model update and object tracking. Experiments on challenging video clips show that our tracking algorithm performs better than several state-of-the-art algorithms. Our future work will be the generalization of our representation model into other related fields.



---

*Source: 352634-2013-10-10.xml*