Multi-Modality Tracker Aggregation: From Generative to Discriminative

1 Introduction

Visual tracking is a key component in numerous video analysis applications, such as visual surveillance, vision-based control, human-computer interfaces, intelligent transportation, and augmented reality. It strives to infer the motion states of a target, e.g., location, scale, and velocity, from the observations in the each frame with the assumption that the appearance of the target is temporally consistent. This assumption may be occasionally violated due to the large appearance variations of a target induced by changing illumination, viewpoint, pose, occlusion, and cluttered background, which leaves visual tracking a quite challenging task after decades of intensive study.

In terms of how to construct the appearance models, the tracking algorithms can be roughly categorized into generative model or discriminative model based methods. The generative model based methods usually build a model to describe the visual appearance of a target, e.g., by a distribution or subspace of intensities or features. Then the tracking problem may reduce to search for the optimal motion state of a target that yields the most similar object appearance in a maximum likelihood formulation. An image patch model [Hager and Belhumeur, 1998], which takes the set of pixels in the target region as the model representation, is a direct way to model the target, but it loses the discriminative information that is contained in the pixel values. The color histogram [Comaniciu et al., 2003] provides global statistical information about the target region which is robust to noise, but it is sensitive to illumination changes and distracters with similar colors. [Stauffer and Grimson, 1999] first employ a Gaussian mixture model (GMM) to represent and recover the appearance changes in consecutive frames. Later, a number of more elaborate Gaussian mixture models are proposed for visual tracking [Jepson et al., 2003; Zhou et al., 2004; Wang et al., 2007]. In [Porikli et al., 2006], the object to be tracked is represented by a covariance descriptor which enables efficient fusion of different types of features and modalities. Another category of appearance models is based on subspace learning. In [Black and Jepson, 1998], a view-based eigenbasis representation of the object is learned off-line, and applied for matching successive views of the object. However, it is very difficult to collect training samples that cover all possible viewing conditions. To deal this problem, subspace learning based tracking algorithms [Lim et al., 2004; Zhang et al., 2010; 2014] are proposed to effectively learn the variations of both appearance and illumination in an incremental way. Generative models generally seek a compact object description and do not take advantage of the background information. Therefore, the generative model based trackers are apt to be distracted by background regions with similar appearances during tracking.

To address the background distraction problem, discriminative models are adopted and trained online during tracking, which concentrate on maximizing the difference between a target and the background. Hence, visual tracking is viewed as a binary classification problem that finds the optimal decision boundary to distinguish a target from the background. [Collins et al., 2005] firstly note the importance of background information for object tracking, and formulate tracking as a binary classification problem between the tracked object and its surrounding background. In [Lin et al., 2004], a two-class FDA (Fisher Discriminant Analysis) based model is proposed to learn a discriminative subspace to separate the object from the background. In [Avidan, 2007], an ensemble of online weak classifiers are combined into a strong classifier. [Grabner et al., 2006] adopt online boosting to select discriminative local tracking features. [Saffari et al., 2009] introduce a novel on-line random forest algorithm for feature selection that allows for on-line building of decision trees. [Babenko et al., 2011] use multiple instance learning instead of traditional supervised learning to learn the weak classifiers. This strategy is more robust to the drifting problem. Apparently the classification performance of discriminative models largely depends on the correctly labeled training samples. The common choice is to regard the current tracked object as the positive sample and sample its neighborhood locations to select negative samples. The self-training nature , that is, the classification results are directly utilized to update the classifier, will lead to overfitting.

Although there are numerous tracking algorithms in the literature, no mater generative based or discriminative based, no one algorithm performs better than the others under all circumstances, and the best algorithm for a particular dataset may not be known a priori. This motivates a fundamental problem-the necessity of an ensemble learning of different tracking algorithm to overcome their drawbacks and to increase the generalization ability. Besides, a natural step forward to cope with the self-training problem suffered by the discriminative appearance models is to introduce generative appearance models to supervise the sample selection and training of the discriminative model in a co-training manner [Yu et al., 2008], since the generative and discriminative models have the complimentary advantages in modeling the appearance of the object. However, the major challenge of combining different tracking algorithms is how to measure the performance of different trackers in the absence of groundtruth? When trackers employ different features from multiple modalities, it is hard to directly evaluate their performance [Wu et al., 2013].

To address the above issues, we propose a multi-modality ranking aggregation framework for fusion of multiple tracking algorithms. In our work, each tracker is viewed as a 'ranker' which outputs a rank list of the candidate image patches based on its own appearance model in a particular modality. Then, the proposed algorithm aggregates the rankings of different rankers to produce a joint ranking. Moreover, the level of expertise for each 'ranker' based on the historical ranking results (tracking results before current video frame) is also effectively used in our model. The main features of our work are two-fold: (1) Our work provides a general framework for fusing multiple tracking algorithms employing different features from multiple modalities. It does not need to directly compare the output results obtained by different trackers, and such a comparison is usually heuristic and is only feasible in some specific conditions. (2) Our work provides a natural way to combine the advantages of the generative model based trackers and the the discriminative model based trackers. To our best knowledge, such a framework for fusion of multiple tracking algorithms has not been addressed in the literature.

The rest of the paper is organized as follows. In section 2, the multi-modality ranking aggregation framework is introduced. In section 3, the proposed tracking algorithm is detailed. The experimental results to validate our method are presented in section 4. Some concluding remarks are made in section 5.

2 Multi-Modality Ranking Aggregation Framework

2.1 Ranking AggregationModel

In this part, we will briefly introduce the theory of ranking aggregation. Let O = {o1, o2, .., oN} be a set of object candidates to be ranked by different rankers, and let ri ∈ SN be the ranking list of ranker i for these candidates where SN is a pool of all the possible rankings. Assuming that a set of ranking R = {r1, r2, ..., rK} from K individual rankers is available, the probability of assigning a true ranking ξ to the candidates O can be defined using the extended Mallows model [Lebanon and Lafferty, 2002]:

where p(ξ) is a prior of ξ, and Z(ξ, α) = Σξ∈SN p(ξ) exp(∑Ki=1 αid(ξ, ri)) is a normalizing constant. d(., .) is the distance measure between two ranking lists, and α = {α1, α2, ..., αK} is the expertise of all the rankers which fulfils that αi < 0. The closer of αi to zero, the less influence of the i-th ranker on the assignment of the probability. When αi trends to negative infinity, the corresponding ranker trends to be the true rank. So the Eq.(1) calculates the probability that the true ranking is ξ, given the rankings from different rankers R and the degrees of their expertise α. In the learning process, only the rankings from different rankers R are available, based on which we need to infer ξ and α.

In the above model, the distance d(., .) between two rankings need to be right-invariant, which means the value of d(., .) does not depend on how the objects are indexed. More specially, if we re-index the object using τ, the distance between two rankings over the objects does not changes: d(ξ, r) = d(ξτ, rτ), where ξτ is defined by ξτ(i) = ξ(τ(i)). That means, the value of d(., .) does not change if we reindex the objects such that one ranking becomes ξξ-1 = e = (1, 2, ..., n) and the other rξ-1 . Kendall's tau distance [Lebanon and Lafferty, 2002] is an example of common rightinvariant distance function. The distance between ranking ξ and r is defined as the minimum number of pairwise adjacent transpositions needed to turn one ranking into the other:

[Klementiev et al., 2008] proved that if the distance is right-invariant, the following generative process can be derived based on Eq. (2):

This generative process can be described in Fig.1. From the generative model, we can find the observation is ranking ri, ξ and α are the hidden parameters of the model. Based on the generative model, a set of samples can be sampled. These samples are used to approximate the distribution of the rankings.

The parameters α and ξ can be estimated using the EM algorithm [Klementiev et al., 2008] given a set of rankings R = {r1, r2, ..., rK}. In the E-step, the true ranking ξ is taken as the missing data. The expected value of the complete data log-likelihood with respect to missing data ξ, observed data R, and current expertise estimate α′ is defined as follows:

The calculation of the expected value in above equation results in:

where L(α) is

where rj i is the ranking generated by the i-th ranker for the object candidate j, and U(α′ ) is

where rj is the ranking generated by all rankers for the object candidate j.

In the M-step, Eq.(5) is maximized by αi with the following derivation:

For the Kendall's tau distance, Eαi (d(ξ, ri)) is the expectation of Eq.(2) and can be expressed in the following form

[Fligner and Verducci, 1986]:

At each iteration, a sampling method is introduced to obtain the approximate value of the RHS (right-hand side) of Eq. (8). Since Eαi (d(ξ, ri)) is monotone decreasing, αi can be easily obtained by a binary search approach.

2.2 Top-k Ranking AggregationModel

As we can see, direct application of the above learning procedure is expensive, when the number of the candidates N is large. In tracking applications, it is reasonable that the groundtruth will be contained in the top-k candidates. To reduce to computational complexity, we do not need to do the rank aggregation on the whole list of the candidates.

Top-k lists are partial rankings indicating preferences over different (possibly, overlapping) subsets of k objects, where the elements not in the list are implicitly ranked below all of the list elements. Top-k ranking aggregation model means that the ranking aggregation is conducted on the top-k lists of all rankers. We find the above model can be easily extended to the top-k rank aggregation, the only difference is the Eαi (.), which can be calculated as follows.

Definition 1: Let Fξ and Fri be the top-k elements of ξ and ri respectively, with |Fξ| = |Fri | = k. Z = Fξ ∩ Fri with |Z| = z. P = Fξ \ Z, and S = Fri \ Z, with |P| = |S| = k - z = l. Therefore,

3 Multi-Modality Ranking Aggregation based Tracking Algorithm

Inspired by the above discussion, we propose a multimodality ranking aggregation based tracking algorithm. In our work, we use three generative model based trackers and a discriminative model based tracker. The three generative model based trackers are: (1) the covariance matrix based tracker [Porikli et al., 2006]; (2) the incremental subspace learning based tracker [Lim et al., 2004]; (3) the spatial-color mixture of Gaussians based tracker [Wang et al., 2007]. The discriminative model based tracker is the MIL (multiple instance learning) based tracker [Babenko et al., 2011].

3.1 AlgorithmDescription

A flowchart of our algorithm is presented in Fig.2. The particle filtering tracking framework is adopted for all the trackers. In the prediction process, we first use the state transition to generate a set of candidate image patches corresponding to the object states {si}Ni=1 . In the tracking process, all the four trackers evaluate these candidate image patches according to their own appearance model, and output a set of ranking lists based on their evaluation value. Then the top-k rankings are aggregated using the above model, and obtain the final ranking of the candidate image patches. The top-1 candidate image patch in the aggregated ranking is considered as the tracking result. All the four trackers are updated according to the aggregated ranking results respectively. In this way, the MIL tracker is supervised by the generative model based trackers and does not trained the classifiers using its own tracking result, therefore the self -training problem is avoided. Also in the instance selection process, even if the MIL tracker itself fails to locate the true object location during some frames, the other generative model based trackers may still help it select the correct positive bag.

3.2 Learning of the Ranker Expertise

The above ranking aggregation model obtains the expertise αi of each ranker ri using the EM algorithm in an iterative way. Then the true ranking ξ is deduced. It is an unsupervised ranking aggregation, and the expertise of each ranker is independent for different frames. However, it is not reasonable in tracking applications. In fact, the expertise of each ranker should meet the following two requirements: (1) the expertise of each ranker will vary little between two consecutive frames, and this consistency constraint should be considered; (2) the expertise of each ranker should reflect whether a ranker is a good tracker which needs to be adaptively evaluated in the tracking process.

After obtaining the aggregated ranking ξ, we can evaluate whether the ranker ri is a good tracker by calculating the distance value d(ri, ξ). However, direct using this distance value for evaluation is not appropriate, for example, if ri changes the top-2 candidates of ξ or the bottom-2 candidates of ξ, the distance value between them is the same. The former case means ri do not give the same tracking results as ξ, while for the latter case, we think ri give a very good tracking performance. To simplify this problem, we only focus on the top-1 candidate of the rankings. If the top-1 candidate of ri and ξ is the same, we multiply the expertise αi by a factor m (m > 1) which means ri is reliable. While if the top-1 candidate of ri and ξ is not the same, we multiply the expertise αi by a factor m (m < 1). To take the historical ranking results and consistency constraint into consideration, the expertise parameter can be adaptively initialized in each frame as follow.

where w = 1 - e-1/σ acts as a forgotten factor and σ is a predefined constant. This warm start learning of the expertise αi can accelerate the EM convergence process and make the results more accurate.

3.3 Implementation Detail

In this paper, the object is localized using a rectangular window and its state is st = (tx, ty, w, h) where (tx, ty) denotes the center location of the bounding box and (w, h) are respective the width and height of the bounding box. Some important parameters are set as follows: N = 600, k = 90, α0 i = -1, m = 1.1 or 0.9, σ = 2.

4 Experiment

In this section, we test the proposed multi-modality ranking aggregation based tracking algorithm (MRAT) on several challenging sequences. The difficulties of these sequences lie in that the background is noisy, the object undergoes large appearance changes, occlusion and the object is similar to the background. We compare our algorithm with five state-of-art algorithms. The first four algorithms are respectively multiple instance learning based tracker (MIL) [Babenko et al., 2011], the L1-regularized sparse template based tracker (LRST) [Mei and Ling, 2011], the visual decomposition tracker (VDT) [Kwon and Lee, 2010], and the online adaboost tracker (OBT) [Grabner et al., 2006]. We also choose co-training multiple instance learning tracker (CMIL) [Lu et al., 2011] as comparison 1 . In CMIL, it improves the MIL through combining HOG-classifier and RGB-classifier in a co-training way. While we improve the MIL tracker

1 The source codes of these trackers are available from:

http://vision.ucsd.edu/ bbabenko/project-miltrack.shtml

http://www.ist.temple.edu/ hbling/code/

http://cv.snu.ac.kr/research/ vtd/

http://www.vision.ee.ethz.ch/boostingTrackers/

http://ice.dlut.edu.cn/lu/Paper/FG2011/code/COMILcode.rar

(h) Girl through ranking aggregation instance selection, so it is interesting to compare these two algorithms. In the tracking results, MRAT is located using a white bounding box, MIL is located using a red bounding box, LRST is located using a green bounding box , VDT is located using a yellow bounding box, OBT is located using a green bounding box and CMIL is located using a light blue bounding box.

Figure 3: The tracking results of §4.1.(Please refer to the PDF version and enlarge the figure for a clear view of the results)

4.1 Qualitative Analysis

Car, Boat and SmallTarget

The Car, Boat and Smalltarget sequences are selected to test the performance of our algorithm against noisy and cluttered backgrounds. In the Car sequence, a car moves in a very noisy environment. The nearby background is so noisy that the car can not easily be located even by eyes. Some representative frames of the tracking results are shown in Fig.3(a). MRAT outperforms other trackers and successfully tracks all the frames. The other trackers fail to locate the object as the background becomes noisy.

In the Boat sequence, the surround background of the boat shares similar colors with it. Some representative frames of the tracking results are shown in Fig.3(b). MRAT and MIL are able to track the object. The VDT drifts away in some frames and can relocates the object. The other three trackers do not performs well in this sequence.

In the Smalltarget sequence, the object has a similar appearance to the background and there exists background distraction when the pedestrian passes by the car. Some representative frames of the tracking results are shown in Fig.3(c). MRAT and the VDT tracker can successfully track all the frames. The other trackers can not accurately locate the object when the background distraction exists.

Surf and Shake

The Surf and Shake are chosen to test the robustness of our algorithm against large appearance, illumination changes and cluttered backgrounds. In the Surf sequence, the surfer has a similar appearance with the wave and endures large appearance changes when he is covered by the wave. Some representative frames of the tracking results for this sequence are shown in Fig.3(d). MRAT achieves the best performance. It only fails to accurately locate the object as the scale of the object becomes so large that the bounding box cannot include the object. The other trackers cannot provide accurate results.

In the Shake sequence, the man changes his appearance by shaking his head. The background is cluttered and also undergoes large illumination changes. Some representative frames of the tracking results are shown in Fig.3(e). The MIL tracker successfully tracks all the frames. MRAT only fails to track the object around frame frame 60 and then quickly recovers to track the object. The other trackers do not perform well in this challenging sequence.

Football, Woman and Girl

The last three sequences are Football, Woman and Girl. We apply MRAT on these three sequences to test the robustness against occlusion and background distractions. In the Football sequence, severe occlusion happens and the target object shares a similar color with the other players. Some representative frames of the tracking results for this sequence are shown in Fig.3(f). The MIL and VDT tracker both begin to lose the object when severe occlusion and background distraction happen. MRAT successfully tracks the object in this challenging situation.

In the Woman sequence, the woman undergoes occlusion by the car. In the Girl sequence, the girl undergoes large appearance changes by turning around her head and is severely occluded by the man. Some representative frames of the tracking results for these two sequences are shown in Fig.3(g) and Fig.3(h). Both MRAT and VDT can successfully track the object through all the frames. The MIL tracker, it can track the object for most of frames but without accuracy. While the other trackers do not performwell in these two sequences.

4.2 Quantitative Analysis

In this part, we present quantitative evaluations to show the performance of trackers in different video sequences. We calculate the RMSE (root mean square error) of the four points in the bounding box between the tracking results and the groundtruth. The groundtruth is marked by hand. The mean of RMSE of the seven sequences we test on are given in Table 1. From the quantitative evaluations, MRAT provide the lowest RMSE in most of the sequences.

4.3 Discussion

The qualitative and quantitative results show that MRAT outperforms the other five competing trackers in most of the sequences. MRAT is robust in the presence of the background clutter and distraction, large appearance and illumination changes, and occlusion. It improves on the MIL through training the tracker under the supervision of the generative model based trackers in a ranking aggregation manner. In the sequences where the MIL successfully tracks the object, the proposed aggregation strategy does not worse the performance of MIL tracker. However, in the sequences that the MIL fails to track the object, MRAT improves the performance of the MIL tracker and can successfully track the object. As a result, we conclude that MRAT provides an effective solution to the problem of self -training.

5 Conclusion

In this paper, we propose a novel multi-modality ranking aggregation tracking algorithm to improve performance of the MIL under the supervision of the generative model. In our ranking aggregation framework, the discriminative classifier based MIL tracker is boosted with the help of the generative models in ranking aggregation manner. The discriminative model and generative models are fused together seamlessly without the need to compare the performance of each other. The experimental results validate the effectiveness of our algorithm.

Acknowledgments

This work is supported by NSFC (Grant Nos. 61472285, 6141101224, 61473212, 61100147, 61203241 and 61305035), Zhejiang Provincial Natural Science Foundation (Grants Nos. LY12F03016, LY15F030011 and LQ13F030009), Project of science and technology plans of Zhejiang Province (Grants No. 2014C31062).