{'fraction_non_alphanumeric': 0.035137202409408166, 'fraction_numerical': 0.013337795200305957, 'mean_word_length': 4.684510869565218, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 5, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Robust Visual Tracking Using Dynamic Classifier Selection with Sparse Representation of Label Noise

Recently a category of tracking methods based on"tracking-by-detection"is widely used in visual tracking problem. Most of these methods update the classifier online using the samples generated by the tracker to handle the appearance changes. However, the self-updating scheme makes these methods suffer from drifting problem because of the incorrect labels of weak classifiers in training samples. In this paper, we split the class labels into true labels and noise labels and model them by sparse representation. A novel dynamic classifier selection method, robust to noisy training data, is proposed. Moreover, we apply the proposed classifier selection algorithm to visual tracking by integrating a part based online boosting framework. We have evaluated our proposed method on 12 challenging sequences involving severe occlusions, significant illumination changes and large pose variations. Both the qualitative and quantitative evaluations demonstrate that our approach tracks objects accurately and robustly and outperforms state-of-the-art trackers.


Introduction
Visual object tracking has been one of the most attractive topics in computer vision and there are numerous practical applications so far, such as motion analysis, video surveillance, traffic controlling and so on. In recent years, although many tracking methods [4,21,22,3,28,15,10,16] have been proposed and made a certain breakthrough, it is still a challenging issue to design a tracking algorithm which is robust to severe occlusions, significant illumination changes, pose variations, fast motion, scale changes and background clutter.
Generally, a typical tracking system contains three basic components: object representation, appearance model and motion model. The appearance model is used to represent the object and provide prediction accordingly. The motion model (such as Kalman filter [6], Particle filter [21,22,27]) is applied to predict the motion distribution of the object between two adjacent frames. In this paper, we focus on the appearance model which is the most important and challenging part of the tracker.
In literatures [4,21,2,26], most of tracking approaches can be categorized as either generative or discriminative ones based on different appearance models.
The generative methods formulate the tracking problem as locating the object region with maximum probability generated from the modeled appearance model [22,6]. Adam et al. [1] proposed a robust fragments-based tracking approach where the object is represented by multiple image fragments. This tracker can handle partial occlusions and pose changes well. Since the template was fixed and not updated during tracking, the tracker is sensitive to appearance changes of the object. To acclimate to appearance changes, the template or appearance model of the tracker should be updated dynamically. Ross et al. [22] developed a tracking algorithm based on incrementally learning a low-dimensional subspace representation. Kwon et al. [15] decomposed the observation model into multiple basic observation models and the proposed method was robust to significant motion and appearance changes.
For discriminative methods, the tracking problem is formulated as training a discriminative classifier to separate the object from surrounding background. These methods are also noted as tracking-by-detection methods since training a classifier is similar to detection problem. Recently, numerous tracking approaches based on detection are proposed [4,8,9,23,11,17,13]. In order to handle appearance changes, online ensemble learning was popularly applied to the tracking problem. In [2], Avidan proposed an online ensemble tracking algorithm by online learning. Grabner et al. [8] proposed an online Adaboost feature selection method. Babenko et al. [4] used online MIL (Multiple Instance Learning) instead of traditional supervised learning to handle the drifting problem. In their work, the training samples are constructed as bags and labels are corresponded to bags rather than samples. Classifier selection scheme plays an important role in online ensemble learning based tracking methods. In [8], classifiers are selected by measuring the accumulated error. In [4], by maximizing the log likelihood of bags, classifiers are selected from the classifier pool. However, these classifier selection algorithms almost assume the training dataset is clean, which do not meet practical applications of visual tracking. Noisy training dataset will reduce the performance of the classifier and cause drifting during tracking.
Recently, sparse representation [26] has been widely applied in object tracking [21,28,20,19,18,12]. Mei et al. [21] treated tracking as a sparse approximation problem in a particle filter framework. Each target candidate is sparsely represented in the space of object templates and trivial templates, and the candidate with the smallest projection error is taken as the target. This representation is robust to partial occlusions and other changes. However it is computationally expensive to obtain sparse coefficients by 1 minimization. This restriction makes it unsuitable for real-time applications. Bao et al. [5] developed a very fast numerical solver to tackle the 1 minimization problem based on the accelerated proximal gradient (APG) algorithm such that the tracker can work in real time. Zhang et al. [28] expanded the 1 tracker by employing popular sparsity-inducing p,q mixed norms and formulated object tracking in a particle filter framework as a multi-task sparse learning problem. Most of these methods use sparse coding to represent the appearance model of the object. However, little work has been done on sparse representation for the class labels of classifiers.
In this paper, we present a novel dynamic classifier selection with sparse representation of label noise. We use sparse representation to model the class labels and obtain classifiers by 1 minimization. In order to verify the robustness of the selection scheme, the algorithm is integrated into a boosting framework to solve visual tracking problem. In order to handle severe occlusion issue, we expand the traditional boosting algorithm to a part based one which is more robust to occlusion. Figure 1 depicts an overview of the proposed tracking approach. The key contributions of our work can be concluded as follows.
• We split the class labels into true labels and noisy labels and model them using sparse representation. Moreover, we propose a novel dynamic classifier selection algorithm based on 1 minimization, which is more robust than traditional selection schemes in [4,8]. • We expand online boosting framework and employ the proposed dynamic classifier selection to this framework. And then a more robust tracking approach is proposed and achieves better performance comparing with other methods.
The rest of the paper is organized as follows. Dynamic classifier selection is proposed in section 2. In section 3, we integrate dynamic classifier selection and an expanded online boosting framework to object tracking. Experimental results are shown and analyzed in section 4 with qualitative and quantitative evaluations. The concluding remarks are drawn in section 5.

Dynamic classifier selection with label noise
In this section, we describe the proposed dynamic classifier selection algorithm with class label noise in details. First we discuss the motivation of our work. Then, the model of classifier with class label noise is presented. At last, we solve this problem using 1 minimization.

Motivation
In the field of machine learning, ensemble learning methods has been popular in recent years and achieved better performance than traditional learning methods. One of the most critical tasks is to select a group of classifier dynamically in the weak classifier pool [14]. Many dynamic classifier selection methods [8,4] have been proposed in recent years, however, most of them do not pay attention to the class label noise which is inherent in the real world dataset. The performance of ensemble learning methods can be rapidly degraded when there are some noises in the training dataset. Therefore, developing a noise-tolerant dynamic classifier selection algorithm is a significant task. In this work, we model the class labels using sparse representation based on the assumption that noise class labels are sparsely distributed over the training dataset. Finally, the weak classifier with the maximum value in the sparse vector will be selected. In (c), the sample with purple box is a noisy one since it is actually positive but labeled as negative.

Sparse representation of class labels
Given the training dataset X = [x 1 , x 2 , . . . , x L ] and label y = [y 1 , y 2 , . . . , y L ] ∈ R L×1 , y i ∈ {−1, +1}. The class label vector predicted by the weak classifier h in this feature set X is denoteds as, where h (X) ∈ R L×1 and h (x i ) is the predicted class label of sample x i by the weak classifier h. Then the joint class labels corresponding to different weak classifiers are denoted by, where Φ ∈ R L×M , L M , L is the number of training samples, and M is the number of weak classifiers in a pool which are used for selection. Assuming that the true label vectorŷ without noise is a linear combination of h i (X), thusŷ can be represented as, is a coefficient vector corresponding to those M weak classifiers, and the weak classifier with the maximum coefficient in β β β will be selected.
However,ŷ can not be obtained ideally in practical applications since the data is not always clean. For example, on visual tracking problem, training data is generated automatically and class labels are obtained by the trained classifier. Since the classifier is not perfectly correct, there will be several misclassified training samples in the training set. In order to solve this problem, we split the class labels y into true labelsŷ and noise labels e such thatŷ is described aŝ y = y − e. Thus Equation (3) is changed to, In addition, as the predicted labels must be positively related to y, we add a non-negativity constraint to these coefficients. The final formulation is shown in Equation (5). where

Classifier selection using 1 minimization
Based on the above formulation, we herein want to have a sparse solution to (5).
When we obtain a solution, the β β β * should be a sparse vector corresponding to weak classifiers and e + and e − correspond to the class label noises respectively. In our approach, the weak classifier which has the maximum value in the sparse vector β β β * is selected, i.e., The optimal coefficients c * can be obtained by solving the following 0 optimization objective function. However, the 0 minimization is NP-hard problem, thus 1 minimization is instead.
And Equation (7) can be changed into Lagrangian optimization problem and solved in polynomial time [26]. Figure 2 gives some experiments and intermediate results of our method on tiger sequence. Figure 2(d) shows a sample of patches corresponding to those weak classifiers selected by the proposed algorithm. In order to get the spatial distribution of these patches, we map them to the object rectangle, as shown in Figure 2

Visual tracking using dynamic classifier selection
In this section we employ the above mentioned dynamic classifier selection algorithm to an expanded online boosting framework. And then a novel tracking approach which is robust to severe occlusion, fast motion, illumination changes and pose variations is proposed. The basic framework of track-by-detection algorithm is depicted in Figure 3. First we will give a brief introduction of motion model. Then the proposed method will be described in detail. Generally, almost all the motion models in tracking-by-detection algorithms [4,8,9,23,11,17,13] are based on sampling. The goal of tracking is to choose the sample with the maximal confidence p s (y = 1|p t ) by an online trained classifier, where p t represents the location of estimated 2D patch in the search region at frame f t ∈ F, t = 1, . . . , T . As shown in Figure 3, the tracker maintains the object location p * t−1 (marked with red fork) at time t − 1. In order to estimate the object location at time t, a number of patches P t = p t | p t − p * t−1 2 2 ≤ r will be generated to predict the location with a radius r. The patch p * t with the maximum confidence becomes the object location at time t.
This motion model is called translational motion model. Although there exist some more sophisticated motion models, such as particle filter [21,22,27], com-bined motion model [15], we mainly concentrate on the appearance model during tracking, especially in the scheme of online learning.  Given a patch located at p ∈ P t , let x p denote the feature vector extracted from the image patch in the frame f t . The training samples are formulated as x p , y , y ∈ {−1, +1}, where +1 and −1 represent the sample belonging to the object or background. The strong classifier, H (x p ), has the following form, where h n,sel (x p ) is the n th selected weak classifier and weighted by α n,sel . As the standard online boosting [8] mentioned, α n,sel can be expressed as . λ c n,sel is the number of samples correctly classified and λ w n,sel is the number of samples misclassified.
In order to deal with severe occlusion, we expand online boosting framework by employing part based scheme and propose a part based boosting algorithm in this paper, with the assumption that there will always be a part of the object which is not occluded. The K strong classifiers are combined by adopting the Noisy-OR [25] model. Let p t • l k indicate the patch location in the k th part of the object, the model can be written as, The algorithm of part based boosting framework and online updating based on dynamic classifier selection are shown in Algorithm 1 and Algorithm 2 respectively.

Experiments
In this section, we verify the proposed tracker on 12 challenging tracking sequences (e.g. animal, coke11, david, dollar, faceocc, faceocc2, girl, shaking, surf, sylv, tiger1, tiger2). The 1 st and 8 th sequence can be obtained from [15], and the others are available at [4]. The proposed method is compared to the latest state-of-the-art tracking algorithms, including fragment-based tracker (FRAG) [1], 1 tracker ( 1 ) [21], multiple instance learning (MIL) tracker [4], visual tracking decomposition (VTD) approach [15] and the method of part based online boosting without 1 minimization called ours (w/o 1 ) using the same initial position. The source codes of FRAG 1 , 1 -tracker 2 , MIL 3 , VTD 4 can be found at URLs.
Our proposed algorithm is implemented in MATLAB, and can process about 15 frames per second. The features we used in this paper are the standard Haarlike features [24]. Each weak classifier h (x) corresponds to a Haar-like feature. We use the following weak classifier model, where p w (y = 1|x p ) and p w (y = −1|x p ) are two Gaussian distributions, i.e., N (µ + , σ + ) for positive samples and N (µ − , σ − ) for negative samples respectively. In addition, we adopt Kalman filter [6] to update weak classifiers. Almost all the parameters in the experiments are fixed. We set the number of strong classifiers K = 5, corresponding to the raw position, half top, half bottom, half left and half right respectively. The number of weak classifier N is 10 for sequence (coke11, dollar, faceocc, sylv) and 20 for others, and the number of weak classifiers M in the pool for selection is 200. The parameter λ in 1 minimization is fixed to 0.01.
In order to eliminate the effects which are brought by randomness, we run each video sequence 5 times and average the results.

Qualitative Evaluation
In the sequence animal, several deers are running in water very fast. Figure 4(a) shows the tracking results on animal sequence. FRAG, MIL tracker, 1 tracker, ours (w/o 1 ) tracker failed at frame 39 because of fast motion. Only ours (w/ 1 ) and VTD tracker can successfully track the object throughout this sequence. The result shows the robustness of ours (w/ 1 ) algorithm in handling fast motion.
In the sequence coke11, a moving coke can is suffering illumination changes, occlusion and pose variations. The tracking results are shown in Figure 4(b). The FRAG, 1 tracker and VTD tracker failed at frame 50 after illumination variation. The other algorithms provide robust tracking result for this sequence.
In the third sequence david, light and pose changes significantly throughout the whole sequence. As shown in Figure 4(c), the pose of David changes heavily between frame 117 and 161. And all the other algorithms drift when the pose varies wildly. This result clearly demonstrates that ours (w/ 1 ) can handle pose change robustly.
In the sequence dollar, some dollars are folded and then divided into two parts. The appearance is changed when dollars are folded. From Figure 4(d), we can conclude that the FRAG, 1 tracker, and VTD tracker failed to track the dollars when the appearance changed. Ours (w/ 1 ) and (w/o 1 ) and MIL can track the dollars through the whole sequence. The reason for the better performance is that these algorithms are online learning based algorithms.
In the sequence faceocc, the woman's face is partly occluded by a book. Figure 4(e) shows the tracking results. MIL tracker drifts at frame 250 after the occlusion. VTD tracker fails to track the face between frame 577 and frame 600. The other algorithms can track the occluded face throughout the sequence.
The next the sequence is faceocc2, which is more challenging than faceocc. Except the occlusion, the man's appearance is changed (wearing a hat) among the sequence. In Figure 4(f), FRAG and VTD trackers failed when the head is rotated. 1 tracker loses the face when the man wears a hat. Ours (w/o 1 ) algorithm tracks the face poorly after frame 707. However, ours (w/ 1 ) method is able to track the face throughout the whole sequence.
The results of sequence girl are shown in Figure 4(g). In this sequence, occlusion and pose variations are taken place during the sequence. Ours (w/ 1 ), 1 tracker and VTD tracker can successfully track the girl. The other algorithms failed as the pose change and occlusion.
In the sequence shaking (Figure 4(h)), the variations of illumination and pose are very severe. The results show that all the other algorithms except ours (w/ 1 ) and VTD tracker drift at frame 61 when light is changed significantly. We show the robustness of our algorithm to severe illumination and pose changes.
The challenges of sequence surfer are fast motion, pose change and scale change. As shown in Figure 4(i), only FRAG and 1 tracker lost the object during tracking. The other algorithms can faithfully track the object through the sequence.
In the sequence sylv, a moving animal doll is suffering from lighting variations, scale and pose changes. The results are shown in Figure 4(j). 1 tracker failed after the frame 624 and VTD tracker, FRAG also failed after frame 1179. Only MIL tracker, ours (w/ 1 ) and ours (w/o 1 ) can track the object through the long sequence.
The results of sequence tiger1 are shown in Figure 4(k). Many trackers drift at frame 76 because of occlusion and fast motion, pose changes. Only ours (w/ 1 ) can deal with these issues well.
In the last sequence tiger2, trackers except MIL tracker lost the tiger at frame 113 ( Figure 4(l)). Our algorithm can not perform well on this sequence when fast motion and occlusion occurred simultaneously.

Quantitative Evaluation
For the quantitative comparison, position error and overlap criterion in PASCAL VOC [7] are employed. They are computed as,  Table 1 summarizes the average position error and Table 2 shows the success rate of tracking methods. Figure 5 depicts the average position error of trackers on each tested sequence. Overall, our proposed algorithm achieves best performance on the sequence david, dollar, feaceocc2, surfer, sylv, tiger1 against state-of-the-art methods, and on the other sequences its performance is comparable to the best method.

Conclusion
In this paper, we propose a dynamic classifier selection algorithm and integrate it to an expanded online boosting framework. In the proposed dynamic classifier selection algorithm, we divided the class labels into two parts which are true and noise class labels. Based on the formulation, the classifier selection is solved by 1 minimization. In the proposed online boosting framework, we employ the part-based idea in which object is represented by several patches. Compared to some state-of-the-art trackers on 12 challenging sequences, the experimental results demonstrate that the proposed method is more accurate and more robust to appearance variations, pose changes, occlusions, fast motion and so on.