# Feature Selection Tracking Algorithm Based on Sparse Representation

Authors: Hui-dong Lou; Wei-guang Li; Yue-en Hou; Qing-he Yao; Guo-qiang Ye; Hao Wan
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

In order to enhance the robustness of visual tracking algorithm in complex environment, a novel visual tracking algorithm based on multifeature selection and sparse representation is proposed. In the framework of particles filter, particles with low target similarity are first filtered out by a fast algorithm; then, based on the principle of sparsely reconstructing the sample label, the features with high differentiation against the background are involved in the computation so as to reduce the disturbance of occlusions and noises. Finally, candidate targets are linearly reconstructed via sparse representation and the sparse equation is solved by using APG method to obtain the state of the target. Four comparative experiments demonstrate that the proposed algorithm in this paper has effectively improved the robustness of the target tracking algorithm.


---

## Body

## 1. Introduction

Visual target tracking algorithm, due to its wide application in fields such as robotics visual control, human-machine interaction, intelligent assistance driving, and video surveillance, has attracted increasing attention from the researchers. However, in complex environment, due to changes in illumination and expression of the target object, object occlusion, and noises disturbance, design of an accurate and real-time visual tracker remains a challenging problem [1].In recent years, a kind of appearance modeling technology called sparse representation has been widely used for information compression and pattern recognition. Agarwal and Roth [2] have achieved good results in object recognition via sparse representation. Researches [3–5] demonstrate that high recognition rate has been obtained in face recognition via sparse representation. Mei and Ling [6, 7] first introduced sparse representation theory into visual tracking and developed a sparse representation tracking algorithm based on particles filter. The algorithm uses the template dictionary to linearly reconstruct the candidate targets and imposes sparsity constraints on the reconstruction coefficients. Apart from the target template, the algorithm uses the trivial template to construct the template dictionary, showing good robustness to occlusion; however, it requires a large amount of calculation because the algorithm adopts the LESSO method to solve the sparse equation. Bai and Li [8] developed a structural sparse representation model, which divides the sample into blocks and uses the Block Orthogonal Matching Pursuit (BOMP) algorithm to solve the sparse equation. It effectively improves the calculation speed, but the algorithm is not robust to illumination change. Hou et al. [9] provided a tracking algorithm of block sparse representation, in which each block is given the corresponding weights to improve the robustness to occlusion, but there may be drift due to large noises. A target tracking algorithm based on the structural sparse representation is proposed in [10], which constructs a vector pool of sparse representation coefficients by blocking the target sample and identifies the target state through the similarity information in the vector pool. But this algorithm fails to effectively use the residual error information; its robustness needs to be further improved. Based on this, Hou et al. [11] developed a target tracking algorithm with sparse representation based on ranking. The algorithm gives full consideration to the sparse representation coefficients and residual error information while locating the target, which improves the robustness of the tracking algorithm. In the framework of structural sparse representation, the sparse coefficients of the candidate targets is classified in [12] by training the Naive Bayes Classifier, strengthening the algorithm’s ability to differentiate between the target and its background. But the algorithm fails to extract the features with differentiation; its robustness needs to be further improved. Wang et al. [13] propose a least soft-threshold squares tracking algorithm based on sparse representation, which models the reconstructed residual error terms with the Gaussian-Laplacian distribution and finds the optimal solution of the objective equation by using iterative and soft-threshold methods. Bao et al. [14] impose constraints on the target template coefficients and the trivial template with L1-norm and L2-norm, respectively. Additionally, it adopts the Accelerated Proximal Gradient (APG) method to solve the objective equation with sparsity constraints. As a result, the accuracy of the tracker and the speed of calculation are significantly improved. Zhuang et al. [15] propose a multitask concept that is similar to [14]; the algorithm also uses the Accelerated Proximal Gradient (APG) method to solve the objective equation by iteration, but it requires a fair amount of calculation. In the framework of sparse representation, Lan et al. [16] propose an objective equation based on adaptive multifeature selection and solve the equation by using the Accelerated Proximal Gradient (APG) method. The multifeature selection method has effectively improved the robustness of the tracking algorithm, but it requires a large amount of calculation.In order to improve the robustness of visual tracking algorithm, this paper proposes a novel tracking algorithm based on multifeature fusion and sparse representation. According to the image intensity, the proposed algorithm uses the simple algorithm to filter out the candidate targets largely dissimilar to the target. Then, the discriminative features, which come from multifeature, are selected by using a method of sparsely reconstructing sample label. Finally, it usesL2-norm to linearly reconstruct the candidate targets and obtains the state of the target.


## 2. Overview of the Tracking Algorithm

The theorem of proposed tracking algorithm based on multifeature fusion and sparse representation in this paper is shown in Figure1. Compared with other tracking algorithms, it has the following contributions:(1)
This paper proposes a fast algorithm that can quickly filter out the particles with low similarity to the target template, improving the calculation speed of the algorithm.(2)
Based on the sample feature constructed from multifeature, the proposed algorithm uses the method of sparsely reconstructing positive and negative sample label to extract sample features, which can help these extracted features more discriminatively.(3)
The conventional tracking algorithms based on sparse representation always useL1-norm to impose the constraints on the linear reconstruction function, but they require a large amount of calculation, whereas the proposed algorithm in this paper uses APG method to solve the sparse function with nonnegative constraints, greatly improving the calculation speed of the algorithm.Figure 1
Proposed tracking algorithm.


## 3. Fast Particle Filter Algorithm

In the framework of particle filtering, most particles bear little resemblance to the target. So they can be filtered out through simple algorithm. Based on this idea, a fast algorithm is proposed to filter out the particles with low similarity to the target.LetZ=[Z1,Z2,…,Zn] denote the sample set of the candidate targets, and Z-∈Rm denote the target template, where Zi∈Rm is one of the candidate target samples, m is the dimension of the sample, and n represents the number of particles. In order to reduce the amount of calculation, only the gray image information of the sample is involved in the calculation. By normalizing the candidate target Zi and target template Z-, we can get zi′=zi/(∑j=1mzi,j) and z¯′=z¯/(∑j=1mz¯j), where zi,j is the jth feature of zi, z¯j is the jth feature of z¯, and ui is the similarity measure of zi and z¯. If zi bears much resemblance to z¯, then there will be no remarkable difference between the values of ui. So we can filter out the particles according to the fluctuation of values of ui:(1)ui¯=ui,j-meanui,where ui,j is the jth element of ui and mean(ui) is the mean of all elements of ui. The value of ui¯ reflects the fluctuation of values of ui. If the target is disturbed by occlusions or noises, the real target can possibly be filtered out when the value of ui¯ is too small. In order to solve this problem, only the elements with 50% variance value in ui¯ will be involved in the calculation. Sort the elements in ui¯ in descent order according to their values and eliminate the elements with values in the top half; then we can get the vector ui~. Suppose yi=∑j=1m/2ui,j~, where ui,j~ is the jth element of ui~; then we can filter out the particles according to the value of yi. Through experiment, we select the yi with smaller value (n0=n/3) from all the particles to participate in the later operation. Through the algorithm, we can quickly eliminate two-thirds of particles with low similarity to the object, which effectively improves the calculation speed of the tracking algorithm.


## 4. Feature Selection

In order to improve the robustness of the tracking algorithm, we use the image intensity and LBP featuresL∈Rm2 to construct the sample features. Denote the gray features of the sample by sG∈Rm1 and the LBP feature of the sample by sL∈Rm2. When sG and sL are combined, we can get s=[sG,sL]T, where s∈Rk represents the sample feature, k=m1+m2. Because the dimension of s is high, it contains a fair amount of redundant information. In order that the algorithm can differentiate between target and background better, we need to select the discriminative features from s.During the tracking process, according to the target sample in the first frame and the tracking result, we can get the positive and negative sample set of the targetT=[tp,tn], where the positive sample of the target is Tp∈Rk×p and the negative sample is Tn∈Rk×q, where p represents the number of the positive samples and q indicates the number of negative samples. Use the sparse reconstruction theory to select the sample features; then we can get(2)minA⁡12TTA-l22+λA2,where · is the norm operator and l represents the label vectors of the positive and negative samples. The positive and negative samples are set to 1 and -1, respectively. λ is the sparse adjustment coefficient and A∈Rk represents the reconstruction vectors, A=[A1,A2,…,Ak]. It should be noted that, in (2), we use the 2-norm to impose constraints on the sparsity of A. The benefit is that it can effectively reduce the amount of calculation in solving the sparse function. Set threshold as τ, and when Ai>τ, the corresponding feature has a strong ability to differentiate between the target and its background.Construct the mapped vector of feature selectionM=[M1,M2,…,Mk]T, M∈Rk. Consider (3)Mi=0,Ai≤τ,Mi=1,Ai>τ.Here,s is the feature vector before the feature selection. After the feature selection, the feature vector s¯ is defined as(4)s¯=s⊗M,where ⊗ denotes the multiplication of the corresponding elements within the vector.


## 5. Solution to the Sparse Equation with APG Approach

After feature selection, we get the feature vector set of the candidate targetsS=[s1¯,s2¯,…,sn0¯], s-∈Rk0, and k0 denotes the dimension of each sample after feature selection. Let D=[D0,I,-I] denote the template dictionary, where D0 is the target sample set, D0∈Rk0×f, and I∈Rk0×k0 represents the unit diagonal matrix used to reduce the disturbance of occlusions and noises.Using template dictionaryD to make sparse linear reconstruction for the candidate targets, we can get(5)arg minC12s¯-DC22+λC1s.t.CT≥0,where C=[CT,CI]T represents the sparse coefficients, CT is the sparse coefficients corresponding to the target template, and CI is the sparse coefficients corresponding to I and -I. Impose the nonnegative constraints on the elements in CT to improve the robustness of the tracker [7].After adding a penalty term, (5) with nonnegative constraints can be updated by(6)arg minC⁡12s¯-DC22+λC1+JCT,where J(·) is the penalty term defined by(7)Ja=1,a≥0;Ja=+∞,a<0.The solution to (6) is equivalent to optimizing the convex function. This paper uses the Accelerated Proximal Gradient (APG) approach to find the optimal solution to (6). Set(8)FC=12s¯-DC22+λC1,GC=JCT,where F(C) is a differentiable convex function and G(C) is a discontinuous convex function. The specific algorithm is shown in Algorithm 1.Algorithm 1.
Minimization algorithm for (6) by using APG method is as follows:(1)
Initialize,α0=α-1=0, t0=t-1=1(2)
Fori = 1 : 4(3)
βi+1=αi+((ti-1-1)/ti)(αi-αi-1);(4)
αi+1=argminC⁡(γ/2)C-βi+1+∇F(βi+1)/γ22+G(C);(5)
ti+1=(1+1+4ti2)/2;(6)
end forIn Algorithm1, step (4) needs to find the minimum value of the function, so it can be updated by(9)arg minC⁡γ2C-hi+122+JCT,where hi+1=βi+1-∇F(βi+1)/γ. Equation (9) can be seen as to solve the minimum values of the two functions as follow:(10)arg minCT⁡γ2CT-hi+1T22+JCT,(11)arg minCI⁡γ2CI-hi+1I22,where hi+1T and hi+1I are the elements corresponding to T and [I,-I] in hi+1. It can be seen that the optimal solution to (10) is CT=max⁡(0,hi+1T) and the optimal solution to (11) is CI=hi+1I.


## 6. Object Tracking

The proposed algorithm in this paper is implemented in the framework of particles filter. In the first frame of the video, the initial state of the target is picked by mouse or captured through target recognition. Let{o1,o2,…,ot} denote the observation values from the first frame to the tth frame of the video. xti is the state of the ith particle in the tth frame. The target state in tth frame is(12)xt=arg maxxti⁡pxti∣o1:t.Here, p(xti∣o1:t) can be obtained by solving the following equations:(13)pxt∣o1:t-1=∫pxt∣xt-1pxt-1∣o1:t-1dxt-1,(14)pxt∣o1:t=pot∣xtpxt∣o1:t-1pot∣o1:t-1.In (13), pxt∣xt-1 is the state transfer function. The state of the sample is defined by six-dimensional affine vector [τ1,τ2,τ3,τ4,τ5,τ6], which represents the x coordinate, y coordinate, length-width ratio, rotation angle, torsion angle, and scale, respectively. Suppose that the six parameters are mutually independent; then the state transfer function pxt∣xt-1 can be represented as(15)pxt∣xt-1=Nxt∣xt-1,Σ,where Σ is the diagonal matrix constituted by [τ1,τ2,τ3,τ4,τ5,τ6].The relation between the similarity measurepot∣xt in (14) and the residual error e based on sparse representation can be represented as(16)pot∣xt∝1e.The proposed algorithm is shown in Algorithm2.Algorithm 2.
The proposed algorithm in this paper is as follows.
Input. Video, the target state in the first frame(1)
Obtain the target dictionary of the initial target and positive and negative samples(2)
fori = 1 : f (f is the number of the frames of the video)(3)
Update particles with normal distribution(4)
Extract the intensity of the particlessG and filter out particles(5)
Extract LBP feature of the samplesL and get s(6)
Use sparse reconstruction theory to select the sample features, and then get the feature vectors¯(7)
Construct a sparse equation and solve it with APG method(8)
iff can be divided by 5(9)
Update the feature vectors¯, update template dictionary, and update the positive and negative samples(10)
end if(11)
end forOuput. The state of target in each frame.


## 7. Experiments and Discussion

The proposed algorithm in this paper is implemented in Matlab 2009b. In order to make the tracking results of the proposed algorithm more convincing, the experiment selects other three representative tracking algorithms for comparison, includingL1 tracking algorithm [7], IVT tracking algorithm [17], and ASLSAM tracking algorithm. The four algorithms will be tested by four internationally used tracking test videos including “Panda,” “Woman Square,” “Trellis,” and “ThreePassShop2cor”. It is a challenging task to track these targets because all the videos pose challenging factors such as partial occlusion and variations in illumination, pose, and scale.The first test video is Panda with a cartoon panda as the tracked target. For this video, the difficulty in tracking the target lies in the partial occlusion and the target rotation. Figure2 shows the test results of the four algorithms in the 4th, 55th, 108th, 176th, 201th, and 241th frame. The test results of the proposed algorithm, ASLSAM algorithm, L1 algorithm, and IVT algorithm are marked by the blue, red, gray, and purple boxes, respectively. As shown in Figure 2, our proposed algorithm can handle the target very well before the 201th frame but drift from the target in the 201th and 241th frame due to the occlusion. However, it has never missed the target throughout the tracking process. While the other three algorithms miss the target when there are occlusion and target rotation.Figure 2
Tracking results on sequence “Panda.”The second test video is Trellis with the face as the target. There is a great difficulty in tracking the target because of the drastic illumination and variation in pose in the video. As shown in Figure3, our proposed algorithm can track the target faithfully throughout the tracking process without being affected by the pose and illumination change. But L1 algorithm and IVT algorithm miss the target in the 276th frame and ASLSAM algorithm misses the target in the 532th frame.Figure 3
Tracking results on sequence “Trellis.”The third test video is Woman Square with a pedestrian as the target. The main challenge of tracking the target comes from the partial occlusion. As shown in Figure4, only our proposed algorithm has successfully tracked the target without being affected by the partial occlusion while all the other three algorithms miss the target in the 143th frame as a result of the partial occlusion.Figure 4
Tracking results on sequence“Woman Square.”The fourth test video is ThreePassShop2Cor. The difficulty of tracking the target lies in the occlusion, the disturbance of the similar object, and scale variation. The tracking results of the four algorithms are shown in Figure5. Because of the disturbance of occlusion and similar objects, our proposed tracker drifts from the target in the 125th frame but relocates the target later. While the ASLSAM and IVT algorithms locate the similar object instead of the tracked target in the 125th frame and the L1 algorithm misses the target in the 303th frame.Figure 5
Tracking results on sequence“ThreePassShop2Cor.”In order to compare the tracking results better, Table1 lists the maximum, mean, and standard variance values of the tracking error of the four algorithms in four image sequences. The tracking error refers to the Euclidean distance between the center point of the target derived from the tracking algorithm and the center point of the actual target. It can be seen that the tracking results on all the four videos demonstrate that our proposed algorithm achieves more favorable performance than the other three.Table 1
Maximum, mean, and standard variance values of the tracking error.
Video
Proposed algorithm
ASL algorithm
L
1 algorithm
IVT algorithm
Max
Mean
STD
Max
Mean
STD
Max
Mean
STD
Max
Mean
STD
TPS
24.2
3.9
4.6
115.3
65.6
38.0
40.9
18.2
14.1
114.9
65.8
38.4
WS
12.6
3.4
2.2
259.8
15.2
90.3
225.3
129.4
75.2
343.8
156.8
98.8
Panda
23.4
8.6
5.1
385.8
136.3
158.9
410.1
129.9
112.2
190.4
68.3
68.8
Trellis
13.6
3.6
2.9
191.2
21.6
45.4
222.1
59.2
54.4
151.6
72.3
51.0
Average
18.5
4.9
3.7
238.0
59.7
83.2
224.6
84.2
64.0
200.2
90.8
64.25Apart from handling the tracking error, in order to reflect the relation between the tracking results and the actual appearance of the target, Table2 lists the success rate of the four tracking algorithms based on the PASCAL VOC standard [18]. It can be seen that the success rate of our proposed algorithm is remarkably higher than that of the other three.Table 2
Success rate of tracking algorithms.
Video
Proposed algorithm
ASLSAM algorithm
L
1 algorithm
IVT algorithm
TPS
0.99
0.21
0.49
0.24
WS
0.76
0.21
0.21
0.20
Panda
0.85
0.52
0.15
0.42
Trellis
0.94
0.74
0.24
0.26
Average
0.86
0.42
0.27
0.28


## 8. Conclusion

A new sparse representation-based tracking algorithm in the framework of particles filter is proposed in this paper. The new method first uses a fast algorithm to filter out the particles largely dissimilar to the tracked target, which reduces the amount of calculation. Then, with the intensity feature and LBP feature combined, the algorithm extracts the features with discriminative ability viaL2 sparse representation, improving its robustness to the occlusion and disturbance. Furthermore, it adopts the APG method to solve the sparse equation with nonnegative coefficient constraints, improving the computational speed and robustness of the proposed algorithm. Finally, the experiments demonstrate that the proposed tracker achieves more favorable tracking results.



---

*Source: 684370-2015-10-20.xml*