Recently,visual target tracking was widely used in security surveillance,navigation,human-computer interaction,and other applications^{[1, 2]}. In a video sequence,targets for tracking often change dynamically and uncertainly because of disturbance phenomena such as occlusion,noisy and varying illumination,and object appearance. Many tracking algorithms were proposed in the last twenty years that can be divided into two categories: generative tracking and discriminant tracking algorithms^{[1, 2]}. Generative algorithms (e.g.,eigen tracker,mean-shift tracker,incremental tracker,covariance tracker^[2]) adopt appearance models to express the target observations,whereas discriminant algorithms (e.g.,TLD^[3],ensemble tracking ^[4],and MILTrack^[5]) view tracking as a classification problem,thus attempting to distinguish the target from the backgrounds. Here,we present a new generative algorithm.

Based on sparse coding (SC; also referred to as sparse sensing or compressive sensing)^{[6, 7]},Mei proposed an l₁-tracker for generative tracking ^{[8, 9]},addressing occlusion,corruption,and some other challenging issues. However,this tracker incurs a very high computational cost to achieve efficient tracking (see section 2.1 and Fig. 1 for details),and the local structures of similar regions are ignored,which may cause the instability and even failure of the l₁ -tracker. Indeed,the sparse coefficients,for representing six similar regions (CR₁-CR₆) under ten template regions (T₁-T₁₀) with original l₁-tracker,are diversified (Fig. 3). Considering CR₁ and CR₄,for example,we can see that although the latter is almost the partial occlusion version of the former,their sparse representations are very different. Tracking CR₄ (the woman's face) may fail,because the tracker is likely to incorrectly consider the region T₈ (the book) as its target.

Contrary to expectations,Xu proved that a sparse algorithm cannot be stable and that similar signals may not exhibit similar sparse coefficients^[10]. Thus,a trade-off occurs between sparsity and stability when designing a learning algorithm. In addition,instability in the l₁-optimization problem affects the performance of the l₁-tracker.

Lu developed a NLSSS-tracker (NLSSST) based on SC applying a non-local self-similarity constraint by introducing the geometrical information of the set of candidates as a smoothing term to alleviate the instability of the l₁-tracker^[11]. However,its low efficiency (even slower than the original l₁-tracker,Table 4) restricts its applicability in real-time tracking. In this study,motivated by the robustness of the l₁-tracker and stability of NLSSST,we propose a novel tracker,called ELSS-tracker (ELSST),that is both robust and efficient. The main contributions of this study are as follows:

1)An efficient tracker,i.e.,ELSST,is developed by considering the local structure of the set of target candidates. In contrast to the Lu5s^[11] and Mei5s-tracker^{[8, 9]},our tracker is more stable and sparse.

2)The proposed tracker shows excellent performance in tracking different video sequences with regard to scale,occlusion,pose variations,background clutter,and illumination changes.

The rest of this study is organized as follows: l₁- and NLSSS-tracker are introduced in section 2; in section 3,we analyze the disadvantages of these two trackers and propose our tracker; experimental results with our tracker and four comparison algorithms are reported in section 4; the conclusion and future work are summarized in section 5.

1 Related works 1.1 Sparse coding and the l₁-tracker

Sparse coding is an attractive signal reconstruction method proposed by Candes^{[6, 7]} that reconstructs a signal y∈R^m×1 with an over-complete dictionary D∈R^m×(n+2m) with a sparse coefficient vectorc∈R^n×1. The SC formulation can be written as the l₀-norm-constrained optimization problem as follows:

which is NP-hard,where‖·‖_Fdenotes the vector’s Frobenius norm(i.e.,l₂-norm),and ‖·‖₀counts the number of non-zero elements of the vector. Candes proved that the l₁-norm ‖·‖₁ is the tightest upper bound of the l₀-norm ‖·‖₀,and thus,Eq.(1) can be rewritten as the following l₁-optimization problem^{[6, 7]}:

Based on SC,Mei presented a nice l₁-tracker for robust tracking^{[8, 9]} (Fig. 1). Considering that the target is located in the latest frame,the l₁-tracker is initialized in the new arrival frame and N candidate regions are generated with Bayesian inference (Fig. 1a,b). With n templates learned from previous tracking and 2m trivial templates (m positive ones and m negative ones,where m is the dimension of 1D stretched image,Fig. 1c),Eq.(2) can be solved (Fig. 1d,e,f). With positive and negative trivial templates,Mei added a non-negative constraint c≥0 in Eq.(2),with which the reconstruction errors of all candidate regions with SC coefficients can be used to determine the weights for each candidate,and the object in the new arrival frame can be located with the sum of the weighted candidates. The dictionaries updating strategies can be seen in^{[8, 9]}.

1.2 Non-local self-similarity based sparse coding for tracking (NLSSST)

Recently,Xu indicated the trade-off between sparsity and stability in sparse regularized algorithms^[10]. Moreover,Yang pointed out the same A-optimization issue in pattern classification^[12]. Based on the fact that lots of similar regions exist in all N candidates generated by Bayesian inference,Lu proposed his tracker with the non-local self-similarity constraint as

where c_i and c_j are the sparse coefficients corresponding to the candidate regions y_i and y_j,respectively,and w_ji is the weight assigned to c_j. Given N m-dimensional candidates Y =y₁ … y_N∈R^m×N,the first K-closest candidate point around y_j is denoted by N_K(y_j),and the weight w_ji=,where h is a parameter enforcing similarity,and s_j is the normalization factor. The weight w_ji measures the similarity between the K-neighborhood of y_j and y_i. Lu’s algorithm actually attempts to solve the following:

Taking the solution of the l₁-tracker from Eq.(2) as the initial coefficients c₀,Eq.(4) can be solved through iterative computations^[11]. However,the high computational cost of the original l₁-tracker and iterative procedure for maintaining the neighborhood constraints of sparse coefficients make NLSSST inefficient in achieving real-timing tracking. In contrast to Fig. 1,the schematic diagram of NLSSST presented in Fig. 2,includes an additional neighborhood constraint between y_i and N_K (y_i).

2 Euclidean local structure-based sparse coding for tracking (ELSST)

To circumvent the heavy computation burden of the l₁-tracker and NLSSST (Table 4),we propose an efficient tracker,called ELSST,that considers the local Euclidean structures of the candidates.

2.1 Original euclidean local structure constraint sparse coding (Original ELSSC)

It is evident from Eq. (4) that NLSSST attempts to solve a double l₁-norm problem. However,it is well known that the l₂-norm is much more commonly used for measuring the distance between two vectors and is much easier to optimize than the l₁-norm. Thus,we take the former to measure the relationships between the sparse coefficient vectors,which are close to each other,i.e.,the Euclidean local-structure constraint,and the latter l₁-norm of C to maintain the sparsity of the optimization as follows:

Equation (5) is the objective function of our Euclidean local structure constraint-based SC and can be solved through iterative computation. In particular,at the t-th iteration,for a single candidate y_i in Y,Eq. (5) can be written as follows:

where . At the t-th iteration for the optimization of c_i,c_j,i≠j is fixed. Therefore,we can regard θ_i^(t－1) as a constant. To solve Eq. (6),we introduce the following surrogate function as presented in ^[11]: where λ is convex. According to Daubechies ^[13],when λI-D^T>D is a strictly positive definite matrix,ψ(c_i,c₀) is strictly convex for any c₀ with respect to c_i. Hence,in our experiments,the constant λ is set accordingly ( λ = γ- 2β; Table 1). Once the over-complete dictionary D is fixed,we can derive the following convex objective function from Eq. (7): where and are fixed at the t-th iteration. Thus,we can simplify Eq. (8) as follows: To solve Eq. (9) using SVD,we decompose the over-complete dictionary D∈R m×(n+2m) as D=UΣV^T, where U∈R^m×m,Σ∈R ^m×(n+2m) and V∈R^{(n+2m)×(n+2m)}. Since V is an orthogonal matrix,Eq. (9) can be rewritten as where x_i^(t)=V v_i^(t). Consequently,we can transform the optimization problem with the Euclidean local structure constraint in Eq. (6) to a pure l₁-optimization problem in Eq. (10),i.e.,to represent the given signalx_i^(t)with sparse coefficientsc_i^(t)under the new dictionary V∈R^{(n+2m)×(n+2m)}. The procedure of Euclidean local-structure constraint based sparse coding (ELSSC) is summarized in Table 1 and is very different from the optimization procedure followed for NLSSSC ^[11],even though the difference between their objective functions seems very small (Eqs. (4) and (5),respectively).

2.2 Improved euclidean local structure constraint sparse coding (Improved ELSSC)

If m in Eq. (10) is large,it is time-consuming to obtain the optimization result c_i, as that in l₁-optimization and NLSSSC. Fortunately,in terms of SVD and the structure of D (Figs. 1 and 2),we have

where I denotes the m-ordered identity matrix. Σ′ is the first n rows of Σ,V′ consists of the first n rows and the first n columns of V ,and m$ gg $n. As a result,when constructing the dictionary V in Eq. (10),only the first n rows and first n columns of V must be prepared,whereas the remaining parts of V are not considered to make any contribution to the target templates T. Thus,the large scale optimization in Eq. (10) can be reduced to a much smaller one as follows: where V″=[ V′ I′ － I″]∈R^n×3n ,I′denotes the n-ordered identity matrix,and x_i′is the first n rows of x_i in Eq.(10).

2.3 Original and improved ELSSC-tracker

Based on the above algorithm,our tracker can be obtained with the framework of the original l₁-tracker^{[8, 9]} (Table 2). We need to iteratively solve the large-scale l₁-optimization problem in Eq. (10) twice,up to three times for each candidate in the algorithm,and more than five times in NLSSST. The initial sparse coefficients c₀ are considered as all-zero vectors and iteratively solve the problem without any l₁-optimization issues,as in Table 1 in ^[11]. Nevertheless,we find that,in NLSSST,it is more effective and accurate to initialize c₀ as the solution of the l₁-optimization problem. Therefore,the computation complexity of our tracker is of the same order of magnitude as that of the l₁-tracker and NLSSST. When we resize all n= 10 targets and n = 200 candidate regions to 40 × 40,i.e.,m= 1 600 (Figs. 1 and 2),then the over-complete dictionary D is 1 600 × 3 210 and the orthogonal matrix V is 3 210 × 3 210 in Eq. (10). It is very difficult to solve the corresponding l₁-optimization problem with such a D (in l₁-tracker and NLSSST) or V (in our ELSST).

With the improved ELSSC,Σ′ is the first ten rows of Σ ,and V′ consists of the first ten rows and first ten columns of V. Thus,each iteration of each candidate region in ELSST can be reduced from the large-scale l₁-optimization problem to a much smaller one because of the much smaller scale V′∈R^10×10. To overcome the problem of occlusions in tracking,the analogous trivial templates are used to construct the new dictionaryV″∈ R^10×30,i.e.,a ten-ordered identity matrix and ten-ordered negative identity matrix.

3 Experiments 3.1 Experimental setting

In order to evaluate the proposed tracker,experiments on 12 video sequences were conducted,including Surfer,Dudek,Faceocc2,Animal,Girl,Stone,Car,Cup,Face,Juice,Singer,Sunshade,Bike,Car Dark,and Jumping^{[17, 18, 19]}. These sequences covered almost all challenges in tracking,including occlusion (even heavy occlusion),motion blur,rotation,scale variation,illumination variation,and complex background. For comparison,we used four state-of-the-art algorithms with the same initial positions and the same representations of the targets. They were the incremental learning-based tracker (IVT,a common discriminant tracker) ^[14],the covariance-based tracker (CovTrack,a generative tracker on Lie-group)^[15],the l₁-tracker (a generative tracking method)^{[8, 9]},and the NLSSST^[11].All the experiments were run on a computer with a 2.67 GHz CPU and a 2 GB memory.

The main parameters used in our experiments are set as follows: the number of candidate regions n=200,the number of template regions is n= 10,and the candidates and targets are resized to 40×40.

3.2 Experimental results for sparsity and stability

The stability and sparsity of the original sparse coding,the NLSSSC,and the original and improved ELSSC were verified. The experiments were designed with the Face sequence in the VOT 2013 benchmark dataset^[18] as follows: six similar regions were represented (CR₁,…,CR₆,their means and standard derivations illustrate the similarity) sparsely with template T=[T₁,…,T₁₀]∈R^{1 600×10} from two regions apart from each other (the red region and the green one). Evidently,T is over-completed,and the entire dictionary D∈R^{1 600×3 210}is constructed likewise in Figs. 1 and 2.

The sparse coefficients of CR₁,…,CR₆ generated with the l₁-,the NLSSSC-,the original ELSSC-,and the improved ELSSC-optimization are plotted in Fig. 3. In particular,six similar regions have very different representation coefficients,when using the original l₁-optimization problem,which ignores the structure information between regions. The results of the other three algorithms are much more stable,because of preservation of the structural information. If two regions are similar to each other,they also have similar sparse coefficients. This improves the robustness of tracking; otherwise,the tracker may degenerate or even fail to track. CR₄ for example,with l₁-optimization,can be represented by T₂, T₈, T₆, T₇,and T₁,and the tracker may fail to track the top of the book. Meanwhile,experimental results show that,NLSSSC and our two ELSSC are sparser than the original l₁-optimization problem.

3.3 Experimental results for visual target tracking

We evaluate the investigated algorithms comparatively,using the center location errors,the average success rates,and the average frames per second. The results are shown in Figs. 4&5 and in Tables 3&4. The templates of NLSSST,the original ELSST,and the improved ELSST are shown in Fig. 4(g-o). Overall,our original and improved trackers outperform the other state-of-the-art algorithms.

For occlusion,five algorithms,except IVT,function satisfactorily,especially at #206,#366 of the Dudek sequence in Fig. 4(b) (the head in tracking is covered by the hand and glasses),#143,#265,#496 of the Faceocc2 sequence in Fig. 4(c) (the head in tracking is covered by the book),#85,#108,#433 of the Girl sequence in Fig .4 (e) (the head in tracking turns right,turns back,and blocks someone else),and #56,#104,#301 of the Face sequence in Fig. 4(i) (the head in tracking is also covered by the book). After the target recovers from occlusion,these five trackers can seek it quickly. IVT works poorly,even loses the target in #10 of the Girl sequence (Fig. 5(e)),because the number of positive and negative samples is limited (considering the learning efficiency),and the incremental updating of the classifier in IVT is less effective. CovTracking has a large size of candidates (based on the definition of integral image,the feature extraction of these candidates is so fast,that its cost can be ignored),which makes it robust for occlusion,scale variation,and blur. NLSSST and our original and improved trackers all work well,when the targets are occluded; our two trackers work even better.

For motion blur,our two trackers work better than IVT and the original l₁-tracker. Moreover,CovTracking also reveals its ability to handle blur (e.g.,#4,#9,and #38 in Fig. 4(d,o). In the former sequence,the animal runs and jumps fast (motion blur) with a lot of water splashing (occlusion),while in the latter,the man ropes skipping and the camera cannot take the clear face of the man. IVT and l₁-tracker fail both from #4 in Fig. 4(d),and never recover after that. Our original and improved ELSS lost the target in #31 and #41,then recovered in #33 and #44 (Fig. 4(d)). In #12 to #21 and #44 to #71,the improved ELSST works better than original ELSST,CovTracking,l₁-tracker,and NLSSST.

For rotation and scale variation,our trackers also perform robustly (Figs. 4(a,c,e,g,j) and 5(a,c,e,g,j). When the surfer falls forward and backward,the girl turns left and right,moves towards and away from the camera,the man turns left and right,the car turns over,and the juice bottle becomes bigger and smaller in Surfer,Girl,Faceocc2,Car,and Juice sequence,respectively,five trackers except IVT perform well,especially the NLSSS-tracker and our two ELSSC-trackers.

In a complex background and with high illumination variance (Fig. 4(f)),there are many similar stones to track. The l₁-tracker and our two trackers work better than other three trackers. Cov-tracker fails,because it extracts edge information of targets as one dimension of features,and in this sequences,edge of targets are ambiguous and hard to be distinct. Similar results are obtained from Fig. 4(h,l,m).

Table 3 summarizes the average success rates. Given the tracking results R_T and the ground-truth R_G,we use the detection criterion in the PASCAL VOC challenge^[16],i.e.,

to evaluate the success rate. In general,from the above analysis,we find that our original and improved ELSSC-trackers perform almost the same,and the former is slightly better,especially in the Dudek,Faceocc2,Surfer,Stone,CarDark,and Jumping sequences (Fig. 5(a,b,c,f,n,o). However,we also find from Table 4,which summarizes the average frames per second,that the improved ELSST works much faster than the original ELSST and almost all the other trackers; IVT is faster than the improved ELSST when dealing with Surfer and Dudek sequences,but its success rate is much worse than that of the improved ELSST. It is sensitive under the phenomena of occlusion,rotation,and target motion blur. The original l₁-tracker performs well in most frames,but it is also time-consuming and fails to track sometimes; Cov-Tracking is suitable for occlusion and rotation,but fails when facing a complex background.

4 Conclusions

In this study,to deal with sparsity and instability in the l₁-optimization problem^{[10, 11, 12]} and the high time complexity of the NLSSSC-tracker ^[11],we propose a novel efficient tracker,i.e.,the Euclidean local-structure constraint based sparse coding (ELSSC). Our new algorithm is a l₁-tracker with a reconstructed over-complete dictionary,which is different from that in the original l₁-tracker and NLSSSC-tracker. Moreover,we simplify the large-scale l₁-optimization problem in our tracker to a much smaller one in our improved ELSSC-tracker.

Compared with the original l₁-tracker,our ELSSC-tracker introduces the structure information among the candidate regions generated by the Bayesian inference to the l₁-tracker,similar to that in the NLSSSC-tracker. With our derivation,the optimization procedure of our tracker (Eq.(10)) can be solved as that in the l₁-optimization but very differently from that in the NLSSSC. Furthermore,our improved tracker is much more efficient than the l₁-tracker and NLSSSC-tracker. Our experiments demonstrate the sparsity,stability,and efficiency of our tracker.