# Object Tracking via 2DPCA andl2-Regularization

Authors: Haijun Wang; Hongjuan Ge; Shengyan Zhang
Journal: Journal of Electrical and Computer Engineering
 (2016)

---

## Abstract

We present a fast and robust object tracking algorithm by using 2DPCA andl2-regularization in a Bayesian inference framework. Firstly, we model the challenging appearance of the tracked object using 2DPCA bases, which exploit the strength of subspace representation. Secondly, we adopt the l2-regularization to solve the proposed presentation model and remove the trivial templates from the sparse tracking method which can provide a more fast tracking performance. Finally, we present a novel likelihood function that considers the reconstruction error, which is concluded from the orthogonal left-projection matrix and the orthogonal right-projection matrix. Experimental results on several challenging image sequences demonstrate that the proposed method can achieve more favorable performance against state-of-the-art tracking algorithms.


---

## Body

## 1. Introduction

Visual tracking is one of the fundamental topics in computer vision and plays an important role in numerous researches and practical applications such as surveillance, human computer interaction, robotics, and traffic control. Existing object tracking algorithms can be divided into two categories, that is, discriminative or generative. Discriminative methods treat tracking as a binary classification problem with local search which estimates the decision boundary between an object image patch and the background. Babenko et al. [1] proposed an online multiple instance learning (MIL), which treats ambiguous positive and negative samples as bags to learn a discriminative classifier. Zhang et al. [2] propose a fasting compressive tracking algorithm which employs nonadaptive random projections that preserve the structure of the image feature.Generative methods typically learn a model to represent the target object and incrementally update the appearance model to search for the image region with minimal reconstruction error. Inspired by the success of sparse representation in face recognition [3], supersolution [4], and inpainting [5], recently, sparse representation based visual tracking [6–9] has also attracted increasing interests. Mei and Ling [10] first extend sparse representation to object tracking and cast the tracking problem as determining the likeliest patch with a sparse representation of templates. The method can handle partial occlusion by treating the error term as sparse noise. However, it requires solving a series of complicated l1 norm related minimization problems many times and the time complexity is quite significant. Although some modified l1 norm methods have been proposed to speed up tracker, they are still far away from being real time.Recently, many object tracking algorithms have been proposed to exploit the power of subspace representation from different points. Ross et al. [11] present a tracking method that incrementally learns a PCA low-dimensional subspace representation, efficiently adapting online to changes in the appearance of the target. However, this method is sensitive to partial occlusion. Zhong et al. [8] proposed a robust object tracking algorithm via sparse collaborative appearance model that exploits both holistic templates and local representations to account for appearance changes. Zhuang et al. [12] cast the tracking problem as finding the candidate that scores the highest in the evaluation model based upon a matrix called discriminative sparse similarity map. Qian et al. [13] exploit an appearance model based on extended incremental nonnegative matrix factorization for visual tracking. Wang and Lu [14] present a novel online object tracking algorithm by using 2DPCA and l1-regularization. This method can achieve good performance among many scenes. However, the coefficients and the sparse error matrix used in this method need an iterative algorithm to compute and the space and time complexity are too large to meet the real-time tracking.Motivated by the aforementioned work, this paper presents a robust and fastl2 norm tracking algorithm with adaptive appearance model. The contributions of this work are threefold: (1) we exploit the strength of 2DPCA subspace representation using l2-regularization; (2) we remove the trivial templates from the sparse tracking method; (3) we present a novel likelihood function that considers the reconstruction error, which is concluded from the orthogonal left-projection matrix and the orthogonal right-projection matrix. Both qualitative and quantitative evaluation on video sequences demonstrate that the proposed method can handle occlusion, illumination changes, scale changes, and no-rigid appearance changes effectively in a lower computation complexity and can run in real time.


## 2. Object Representation via 2DPCA andl2-Regularization

Principal component analysis (PCA) is a classical feature extraction and data representation technique widely used in the areas of pattern recognition and computer vision. Compared with PCA, two-dimensional principal component analysis (2DPCA) [15] is based on 2D matrices rather than 1D vectors. So the image matrix does not need to be previously transformed into vector. That is, the extraction of image features is computationally more efficient using 2DPCA than PCA. In this paper, we represent the object by using 2D basis matrices. Given a series of image matrices [B1,B2,…,BK], the projection coefficients matrices [A1,A2,…,AK] can be got by solving the following function: (1)minU,V,A1K∑i=1KB-UAVTF2,where ·F denotes the Frobenius norm; U represents the orthogonal left-projection matrix; V represents the orthogonal right-projection matrix.The cost function is set as anl2-regularization quadratic function: (2)JA=B-UAVTF2+λAF2=12tr⁡B-UAVTTB-UAVT+λAF2=12tr⁡BT-VATUTB-UAVT+λAF2=12tr⁡BTB-BTUAVT-VATUTB+VATUTUAVT+λAF2=12tr⁡BTB-tr⁡BTUAVT+12VATUTUAVT+λAF2.Here, λ is a constant. The solution of (2) is easily derived as follows: (3)∂JA∂A=-UTBV+UTUAVTV+2λA=0⇓UTUAVTV+2λA=UTBVUTUAVTV+2λI1AI2=UTBVVTV⊗UTU+I2T⊗2λI1-1vecA=vecUTBVvecA=VTV⊗UTU+I2T⊗2λI1vecUTBV.Here, I1 and I2 mean the identity matrix. ⊗ stands for Kronecker product. vec(A) means the vector-version of the matrix A. Therefore, we can get the projection coefficients matrix A. Let P=VTV⊗UTU+I2T⊗2λI2. Obviously, the projection matrix P is independent from B and we can precalculate it in each frame before circulation for all candidates. When a new candidate comes, we can simply calculate Pvec(UTBV) to obtain vec(A), which makes the proposed method very fast.Here, we abandon the trivial templates completely, which makes the target able to be represented by the 2DPCA subspace fully. The error matrix can be obtained by the following equation after we get the projection coefficients matrixA from (3): (4)E=B-UAVT.So, the error matrix can be calculated once.


## 3. Tracking Framework Based on 2DPCA andl2-Regularization

Visual tracking is treated as a Bayesian inference task in a Markov model with hidden state variables. Given a series of image matricesB=[B1,B2,…,BK], we aim to estimate the hidden state variable xt recursively: (5)pxt∣B∝pBt∣xt∫pxt∣xt-1pxt-1∣Bt-1dxt-1,where p(xt∣xt-1) is the motion model that represents the state transition between two consecutive states. p(Bt∣xt) is the observation model which indicates the likelihood function.Motion Model. We apply an affine image warp to model the target motion between consecutive states. Six parameters of the affine transform are used to model p(xt∣xt-1) of a tracked target. Let xt={xt,yt,θt,st,α,ϕt}, where xt, yt, θt, st, α, and ϕt denote x and y translations, rotation angle, scale, and aspect ration and skew, respectively. The state transition is formulated by random walk; that is, p(xt∣xt-1)=N(xt;xt-1,Σ), where Σ is a diagonal covariance matrix which indicates the variances of affine parameters.Observation Model. If no occlusion occurs, an image observation Bt can be generated by a 2DPCA subspace (spanned by U and V and centered at μ). Here, we consider the partial occlusion in the appearance model for robust tracking. Thus, we assume that the centered image matrices B¯t  (B¯t=Bt-μ) can be represented by the linear combination of the projection matrices U and V. Then, we draw N candidates in the state xt. For each of the observed image matrices, we solve a l2-regularization problem:(6)minAiB¯i-UAiVTF2+λAi22,where i denotes the ith sample of the state x. Thus, we obtain Ai and the likelihood can be measured by the reconstruction error: (7)pB¯i∣Bi=exp-B¯i-UAiVTF2.However, it is noted that, just by penalizing error level, the precise location of the tracked target can be benefited. Therefore, we present a novel likelihood function, which considers both the reconstruction error and the level of error matrix: (8)pB¯i∣Bi=exp-B¯i-UAiVT-EiF2-λEi1,where Ei can be calculated by (9): (9)Ei=B¯i-UAiVT.Here, Ai is calculated by (3).Online Update. In order to handle the appearance change of tracked target, it is necessary to update the observation model. If some imprecise samples are used to update, the tracked model may degrade. Therefore, we present an occlusion-radio-based update mechanism. After obtaining the best candidate state of each frame, we compute the corresponding error matrix and the occlusion ratio γ. Two thresholds thr1 = 0.1 and thr2 = 0.6 are introduced to define the degree of occlusion. If γ<thr1, the tracked target is not occluded or a small part of it is occluded by the noise. Therefore, the model with sample is updated directly. If thr1<γ<thr2, the tracked target is partially occluded. The occluded part is replaced by the average observation and the recovered candidate is used for update. If γ>thr2, most part of the tracked target is occluded. Therefore, the sample is discarded without update. After we cumulate enough samples, we use an incremental 2DPCA algorithm to update the tracker (left- and right-projection matrices).


## 4. Experiments

The proposed tracking algorithm is implemented in MATLAB which runs on a computer with Intel i5-3210 CPU (2.5 GHz) with 4 GB memory. The regularizationλ is set to 0.05. The image observation is resized to pixels for the proposed 2DPCA representation. For each sequence, the location of the tracked target object is manually labeled in the first frame. 600 particles are adopted for the proposed algorithm accounting for the trade-off between effectiveness and speed. Our tracker is incrementally updated every 5 frames.To demonstrate the effectiveness of the proposed tracking algorithm, we select six state-of-the-art trackers: thel1 tracker [10], the PN tracker [16], the VTD tracker [17], the MIL tracker [1], the Frag tracker [18], and the 2DPCAl1 tracker [14] for comparison on several challenging image sequences includingOcclusion 1,David Outdoor,Caviar 2,Girl, Car 4,Car 11,Singer 1,Deer,Jumping, andLemming. The challenging factors include severe occlusion, pose change, motion blur, illumination variation, and background clutter.


### 4.1. Qualitative Evaluation

Severe Occlusion. We test four sequences (Occlusion 1,DavidOutdoor,Caviar 2,andGirl) with long time partial or heavy occlusion and scale change. Figure 1(a) demonstrates that l1 algorithm, Frag algorithm, 2DPCAl1, and our algorithms perform better, since these methods take partial occlusion into account. l1 algorithm, 2DPCAl1, and our algorithms can handle occlusion by avoiding updating occluded pixels into the PCA basis and 2DPCA basis separately. Frag algorithm can work well on some simple occlusion cases (e.g., Figure 1(a),Occlusion 1) via the part-based representation. However, this method performs poorly on some more challenging videos (e.g., Figure 1(b),DavidOutdoor). MIL tracker is not able to track the occluded target inDavidOutdoor andCaviar 2, since the Harr-like features the MIL method adopted are less effective in distinguishing the similar objects. For theGirl video, the in- and out-of-plane rotation, partial occlusion, and the scale change make it difficult to track. It can be seen that the Frag and the proposed tracker work better than the other methods.Figure 1
Sampled tracking results of partial evaluated algorithms on ten challenging sequences.
(a) (b) (c) (d) (e) (f) (g) (h) (i) (j)Illumination Change. Figures 1(e) and 1(f) present tracking results using theCar 4,Car 11, andSinger 1 sequences with significant change of illumination and scale as well as background clutter. The l1 tracker, 2DPCAl1 tracker, and the proposed tracker perform well in theCar 4 sequences whereas the other trackers drift away when the target vehicle goes underneath the overpass or the trees. ForCar 11 sequences, 2DPCAl1 and the proposed tracker can achieve robust tracking results whereas the other trackers drift away when drastic illumination change occurs or when similar object appears. In theSinger 1 sequence, the drastic illumination and scale change make it difficult to track. It can be seen that the proposed tracker performs better than the other methods.Motion Blur. It is difficult for tracking algorithms to predict the location of the tracked objects when the target moves abruptly. Figures 1(h) and 1(i) demonstrate the tracking results in theDeer andJumping sequences. InDeer sequences, the animal appearance is almost indistinguishable due to the fast motion and most methods lost the target right at the beginning of the video. At frame 53, PN tracker locates the similar deer instead of the right object. From the results, we can see that the VTD tracker and our tracker perform better than the other algorithms. 2DPCAl1 tracker may be able to track the target again by chance after failure. The appearance changes of theJumping sequences are drastic such that the l1, Frag, and VTD tracker drift away from the object. Our tracker successfully keeps track of the object with small errors whereas the MIL, PN, and 2DPCAl1 can track the target in some frames.Background Clutter. Figure 1(j) illustrates the tracking results in theLemming sequences with scale and pose change, as well as severe occlusion in cluttered background. Frag tracker lost the target object at the beginning of the sequence and when the target object moves quickly or rotates, the VTD tracker fails too. In contrast, the proposed method can adapt to the heavy occlusion, in-plane rotation, and scale change.


### 4.2. Quantitative Evaluation

To conduct quantitative comparisons between the proposed tracking method and the other sate-of-the-art trackers, we compute the difference between the predicted and the ground truth center location error in pixels and overlap rates which are most widely used in quantitative evaluation. The center location error is usually defined as the Euclidean distance between the center locations of tracked objects and their corresponding labeled ground truth. Figure2 demonstrates the center error plots, where a smaller center error means a more accurate result in each frame. Overlap rate score is defined as score=area(Rt∩Rg)/areaRt∪Rg. Rt is the tracked bounding box of each frame and Rg is the corresponding ground truth bounding box. Figure 3 shows the overlap rates of each tracking algorithm for all sequences. Generally speaking, our tracker performs favorably against the other methods.Figure 2
Center location error (in pixels) evaluation.Figure 3
Overlap rate evaluation.


### 4.3. Computational Complexity

The most time consuming part of the generative tracking algorithm is to compute the coefficients using the basis vectors. For thel1 tracker, the computation of the coefficients using the LASSO algorithm is O(d2+dk). d is the dimension of subspace and k is the number of basis vectors. The load of the 2DPCAl1 tracker [10] with l1 regularization is O(mdk). m stands for the number of iterations (e.g., 10 on average). For our tracker, the trivial templates are abandoned and square templates are not used. So the load of our tracker is dk. The tracking speed of l1, 2DPCAl1, and our method is 0.25 fps, 2.2 fps, and 5.2 fps separately (fps, frame per second). Therefore, we can get that our tracker is more effective and much faster than the aforementioned trackers.


## 4.1. Qualitative Evaluation

Severe Occlusion. We test four sequences (Occlusion 1,DavidOutdoor,Caviar 2,andGirl) with long time partial or heavy occlusion and scale change. Figure 1(a) demonstrates that l1 algorithm, Frag algorithm, 2DPCAl1, and our algorithms perform better, since these methods take partial occlusion into account. l1 algorithm, 2DPCAl1, and our algorithms can handle occlusion by avoiding updating occluded pixels into the PCA basis and 2DPCA basis separately. Frag algorithm can work well on some simple occlusion cases (e.g., Figure 1(a),Occlusion 1) via the part-based representation. However, this method performs poorly on some more challenging videos (e.g., Figure 1(b),DavidOutdoor). MIL tracker is not able to track the occluded target inDavidOutdoor andCaviar 2, since the Harr-like features the MIL method adopted are less effective in distinguishing the similar objects. For theGirl video, the in- and out-of-plane rotation, partial occlusion, and the scale change make it difficult to track. It can be seen that the Frag and the proposed tracker work better than the other methods.Figure 1
Sampled tracking results of partial evaluated algorithms on ten challenging sequences.
(a) (b) (c) (d) (e) (f) (g) (h) (i) (j)Illumination Change. Figures 1(e) and 1(f) present tracking results using theCar 4,Car 11, andSinger 1 sequences with significant change of illumination and scale as well as background clutter. The l1 tracker, 2DPCAl1 tracker, and the proposed tracker perform well in theCar 4 sequences whereas the other trackers drift away when the target vehicle goes underneath the overpass or the trees. ForCar 11 sequences, 2DPCAl1 and the proposed tracker can achieve robust tracking results whereas the other trackers drift away when drastic illumination change occurs or when similar object appears. In theSinger 1 sequence, the drastic illumination and scale change make it difficult to track. It can be seen that the proposed tracker performs better than the other methods.Motion Blur. It is difficult for tracking algorithms to predict the location of the tracked objects when the target moves abruptly. Figures 1(h) and 1(i) demonstrate the tracking results in theDeer andJumping sequences. InDeer sequences, the animal appearance is almost indistinguishable due to the fast motion and most methods lost the target right at the beginning of the video. At frame 53, PN tracker locates the similar deer instead of the right object. From the results, we can see that the VTD tracker and our tracker perform better than the other algorithms. 2DPCAl1 tracker may be able to track the target again by chance after failure. The appearance changes of theJumping sequences are drastic such that the l1, Frag, and VTD tracker drift away from the object. Our tracker successfully keeps track of the object with small errors whereas the MIL, PN, and 2DPCAl1 can track the target in some frames.Background Clutter. Figure 1(j) illustrates the tracking results in theLemming sequences with scale and pose change, as well as severe occlusion in cluttered background. Frag tracker lost the target object at the beginning of the sequence and when the target object moves quickly or rotates, the VTD tracker fails too. In contrast, the proposed method can adapt to the heavy occlusion, in-plane rotation, and scale change.


## 4.2. Quantitative Evaluation

To conduct quantitative comparisons between the proposed tracking method and the other sate-of-the-art trackers, we compute the difference between the predicted and the ground truth center location error in pixels and overlap rates which are most widely used in quantitative evaluation. The center location error is usually defined as the Euclidean distance between the center locations of tracked objects and their corresponding labeled ground truth. Figure2 demonstrates the center error plots, where a smaller center error means a more accurate result in each frame. Overlap rate score is defined as score=area(Rt∩Rg)/areaRt∪Rg. Rt is the tracked bounding box of each frame and Rg is the corresponding ground truth bounding box. Figure 3 shows the overlap rates of each tracking algorithm for all sequences. Generally speaking, our tracker performs favorably against the other methods.Figure 2
Center location error (in pixels) evaluation.Figure 3
Overlap rate evaluation.


## 4.3. Computational Complexity

The most time consuming part of the generative tracking algorithm is to compute the coefficients using the basis vectors. For thel1 tracker, the computation of the coefficients using the LASSO algorithm is O(d2+dk). d is the dimension of subspace and k is the number of basis vectors. The load of the 2DPCAl1 tracker [10] with l1 regularization is O(mdk). m stands for the number of iterations (e.g., 10 on average). For our tracker, the trivial templates are abandoned and square templates are not used. So the load of our tracker is dk. The tracking speed of l1, 2DPCAl1, and our method is 0.25 fps, 2.2 fps, and 5.2 fps separately (fps, frame per second). Therefore, we can get that our tracker is more effective and much faster than the aforementioned trackers.


## 5. Conclusion

In this paper, we present a fast and effective tracking algorithm. We first clarify the benefits of the utilizing 2DPCA basis vectors. Then, we formulate the tracking process with thel2-regularization. Finally, we update the appearance model accounting for the partial occlusion. Both qualitative and quantitative evaluations on challenging image sequence demonstrate that the proposed method outperforms several state-of-the-art trackers.



---

*Source: 7975951-2016-08-10.xml*