Object Tracking with the Multi-Templates Regression Model Based MS Algorithm

1. Introduction

Object tracking plays an important role in computer vision, such as surveillance, robotics, human computer interaction, etc. In the past decade, many successful algorithms have been proposed for robust object tracking in the complex environment [1-4]. However, the object tracking is still a challenging task due to appearance variations caused by occlusion, pose variations, abrupt motion, and illumination variations.

In general, object tracking algorithms can be classified into two groups: the generative methods and the discriminative methods. The generative methods model an object in the first frame and search for the area with the most similar appearance as the result [5]. The generative methods include MS tracker [6], fragments based tracker [7], incremental tracker (IVT) [8], and visual tracking decomposition (VTD) [9]. The mean-shift (MS) tracker often represents an object with color histograms and determines the tracking result with the highest matching score by using the iterative method [6]. The fragments based tracker models an object by using multiple image fragments or patches and determines the tracking result by combining patches instead of the whole object [7,10]. The IVT tracker learns and updates a low dimensional eigenspace representation to reflect an object’s appearance changes [8]. It has demonstrated that these methods perform well when there are appearance changes caused by lighting and pose variations. However, they are less effective in dealing with the problems of heavy occlusion, serious lighting and pose variations [11]. VTD tracker addresses the problems of occlusion and appearance changes by decomposing the observation model into multiple basic observation models. In the VTD tracker, each basic observation model covers a specific appearance of an object. However, it suffers from expensive computation because it is realized through an interactive Markov Chain Monte Carlo (IMCMC) framework.

The discriminative methods formulate object tracking as a binary classification problem to distinguish an object from background. The online-boosting algorithm selects discriminative features for object tracking [12]. However, it often suffers from tracking drift because only one positive sample (the tracking result) is used for classifier updating [5]. Then, Grabner et al. [13] proposed a semisupervised object tracking algorithm which labels the positive samples in the first frame. However, it suffers from ambiguity as tracking evolves. The multiple instance learning (MIL) algorithm was proposed to learn a strong classifier from multiple instances in the positive and negative bags [14]. Although the algorithm overcomes the problem of ambiguity in object tracking, it does not handle the problem of large non-rigid shape deformation [15,16].

Recently, sparse representation based object tracking algorithms have been studied [17-20]. The tracker represents [17] an object as a sparse linear combination of the object templates and trivial templates. The templates are useful for handling the problems of occlusion and appearance changes. The tracking results show that the algorithm can achieve good performance but with expensive computation.

In this paper, a regression model based MS algorithm is proposed for object tracking. In the algorithm, multiple templates are captured to deal with the problems of occlusion, lighting changes, and pose variations. These templates are divided into two classes. The first candidate templates are captured from the object, the object’s transformational versions, and the occlusion templates. The second candidate templates are generated when tracking fails. The color-texture descriptor is used to represent these templates. Furthermore, to implement real-time and robust object tracking, a regression model is trained by using these templates. Then, the regression model estimates the values of the Bhattacharyya coefficients of the candidate areas for determining the object’s location. At last, the proposed algorithm is evaluated on several videos. The experimental results show that the algorithm is robust to occlusion, illumination variations, and poses changes.

2. Overview of the System

The overview of the object tracking algorithm is shown in Fig. 1. To handle the problems of illumination changes, pose variations, and occlusion, the algorithm employs multiple templates including the object, the object’s transformational versions, the illumination ones, and the occlusion templates. In the beginning of the tracking process, the MS algorithm is applied to these templates. Consequently, several candidate areas are obtained. The tracking result is determined by the geometric center of the candidate areas with larger similar scores (Bhattacharyya coefficient is used to measure the similarity). As tracking evolves, the templates are inserted into a training pool. As the number of the templates in the pool achieves a given value, a regression model is trained with these templates. Then, the regression model estimates the values of the Bhattacharyya coefficients between these templates and the candidate areas. At last, the object’s location is determined by weighting the candidate areas which have larger similar scores. The contributions of this paper are as follows.

 Multiple templates are proposed to handle the problems of occlusion, illumination changes, and pose variations. The multi-templates are captured from the object, the object’s transformational versions, the illumination models and occlusion templates.

 A regression model is presented to estimate the similarity of the object and candidate area. The more the number of the templates is, the better the algorithm performs. However, as the number of the templates increases, the algorithm will suffer from heavy computing time. The presented regression model trains the multi-templates to control the number of the templates.

 Regression model based MS algorithm is applied on the templates. The MS algorithm is applied to the obtained templates for detecting the candidate areas. Then, the regression model estimates the similar values of the candidate areas. The tracking result is determined by weighting the areas’ similar scores with the estimated values.

3. Multiple Templates

In many videos, objects are often occluded or corrupted by noise [21]. To address the problem, the context-aware exclusive sparse tracker (CEST) [11] employed a dictionary combining by three types of templates D_F, D_O and D_C. These templates incorporate information about the object, noise/occlusion, and context. It is shown that the algorithm performs well in challenging videos. Inspired by the CEST, a multiple templates based MS algorithm is proposed. In the algorithm, a final multi-templates set, which includes the first candidate templates and the second candidate templates, are defined. Then, the MS algorithm is applied on the final templates set for tracking the areas with larger similar scores.

The first candidate templates contain information about the object, noise, and occlusion. They are defined as [TeX:] $$T _ { 1 i } \{ i = 1,2,3 \}$$. The first group includes the target templates which are cropped from the tracking result and the transformed versions of the result. The transformational versions of the result are robust to the pose variations. The second group constituted by occlusion templates is shown in Fig. 1. The non-zero entries in the templates indicate that the pixels are occluded [11]. The last group includes the lighting templates.

The second candidate templates are obtained when tracking fails. They are indicated as [TeX:] $$T _ { 2 i } \{ i = 1,2 , \cdots , n \}$$. Then, the final templates [TeX:] $$T _ { i } \{ i = 1,2 , \cdots , M \} M = m + n$$ are composed by the first and second candidate templates. The process for obtaining the second candidate templates and the final templates are detailed as follows.

In the beginning of the tracking process, the MS algorithm is applied to the first candidate templates. As a result, the candidate areas are obtained. The Bhattacharyya coefficient is used to measure the similarity of the candidate areas. If there are the areas with the similar scores larger than a given threshold [TeX:] $$$$, the tracking results are determined by these areas’ geometric center [TeX:] $$L _ { c o n } = \frac { 1 } { N _ { \mathrm { c } } } \sum _ { i = 1 } ^ { N _ { c } } L _ { i }$$ where N_c is the number of the selected areas and L_i is an area’s center location. Furthermore, we re-extract samples for the first candidate templates based on the tracking result. Once all the candidate areas’ similar scores are less than the given threshold, the MS based tracking algorithm fails. In such a case, the EKF [10] predicts the object’s location. Meanwhile, the areas with larger similar scores are selected as the second candidate templates. At last, the final templates are obtained by the first candidate templates and the second candidate templates.

After obtaining the final templates, the MS algorithm is employed in the successive frames. Then, m+n candidate areas are obtained. If there are the areas with the similar scores larger than the given threshold, the object location will be determined by these areas. Meanwhile, the first candidate templates are cropped around the tracking result, while the second candidate templates are obtained as the step mentioned above. If tracking fails, the first candidate templates remain unchanged and the second candidate templates are updated with the n areas which have larger similar scores. In such a case, the EKF [10] predicts the object’s location.

4. Regression Model

Multi-templates based object tracking algorithm is useful to deal with the problems of illumination changes and pose variations. The more the number of the templates is, the better the tracking algorithm performs. However, the computing time will increase as the number of the templates grows. To deal with the problem, multi-templates based regression model is proposed. The goal of the regression model is to estimate a candidate area’s similar score.

4.1 Color-Texture Descriptor

Color feature is often used in computer vision because it is insensitive to rotation, translation, and scale. However, it ignores the spatial information [22]. The texture feature reflects the spatial distribution of the pixel’s pray and makes up the shortcoming of the color feature [23]. Therefore, color-texture descriptor is used to all-sided represent an object. We use the HUE component in the HSV space as the color feature, while the uniform LBP feature is employed due to its lower computational complexity, scale invariability, and rotation invariability [24,25]. The color-texture descriptor is obtained as follows:

where [TeX:] $$f = C o , T e$$ indicates the color and texture information, respectively. [TeX:] $$\hat { q } _ { f , u }$$ is the corresponding histogram. C is the normalization constant which guarantees [TeX:] $$\sum _ { u = 1 } ^ { M } \hat { q } _ { f , u } = 1 . \delta ( \cdot )$$ is Delta function, which determines whether the value of x_i belongs to the u^th bin. [TeX:] $$k ( \cdot )$$ is the Epanechnikov kernel function. h is the bandwidth of the kernel function. x₀ is the center of the object area.

In the tracking process, the candidate area centered in y is expressed with its pixels [TeX:] $$\left\{ x _ { i } ^ { * } \right\} , i = 1,2 , \ldots , n$$. Then, a candidate area’s color-texture descriptor [TeX:] $$\hat { p } _ { f , u }$$ is obtained as follows:

To measure the similarity between the candidate area and the template, the Bhattacharyya coefficient is used:

where [TeX:] $$\hat { p } _ { C o , u } \text { and } \hat { p } _ { { Te , u } }$$ are the color histogram and texture histogram of the template, respectively. [TeX:] $$\hat { q } _ { C o , u } \text { and } \hat { q } _ { { Te , u } }$$ are the color histogram and texture histogram of the candidate area, respectively. [TeX:] $$\hat { \rho } _ { C o } \text { and } \hat { \rho } _ { T e }$$ are the color similarity and texture similarity, respectively. [TeX:] $$\hat { \rho } _ { f }$$ is the obtained similarity.

4.2 Regression Model

In the multi-templates based MS algorithm, the number of the templates affects the algorithm’s performance. The algorithm is more robust to the problem of occlusion, illumination variations and pose changes as the number of the templates increases. However, it means that the MS algorithm will be applied on more templates for generating the accurate result. As a result, the computing time of dealing with one frame will increase. To address the problem, a regression model is presented:

where R(·) is the estimated value of the Bhattacharyya coefficient [TeX:] $$$$ for a candidate area. [TeX:] $$\hat { p } ( y ) = \left( \hat { p } _ { f 0 } ( y ) , \hat { p } _ { f 1 } ( y ) , \cdots , \hat { p } _ { f m } ( y ) \right) ^ { T }$$ is a vector with the color-texture descriptor as the elements and [TeX:] $$\hat { p } _ { f 0 } ( y ) = 1 , \beta = \left( \beta _ { f 0 } , \beta _ { f 1 } , \cdots , \beta _ { f m } \right) ^ { T }$$ is a template’s parameter.

The regression model is trained online by using the final templates and the candidate areas. The goal of training is to estimate the parameter β which guarantees the loss function L(β) be the minimum value:

where [TeX:] $$\hat { \rho } \left( y _ { i } \right)$$ is the similar score between the i^th candidate area and the corresponding template.

The closed solution of the Eq. (5) can be obtained by using the algebra method:

where [TeX:] $$\hat { \beta }$$ is the estimated value of the parameter. P^T is a matrix with dimension [TeX:] $$( m + 1 ) \times n \cdot P ^ { T }$$ is composed by n samples’ color-texture descriptors: [TeX:] $$P ^ { T } = \left( \hat { p } \left( y _ { 1 } \right) , \hat { p } \left( y _ { 2 } \right) , \cdots , \hat { p } \left( y _ { n } \right) \right) . \hat { \rho }$$ is a vector composed by the Bhattacharyya coefficients of n candidate areas:

4.3 Regression Model based MS Algorithm

To implement robust and real-time object tracking, the regression model based MS algorithm is used. In the beginning, the MS algorithm is applied on the final templates for detecting an object. In such a case, the Bhattacharyya coefficients are employed to measure the similarity between the tracked candidate areas and the templates. The MS algorithm is implemented as follows:

Step 1: Initialize the searching area and center manually in the first frame;

Step 2: Compute the color-texture descriptor according to the Eq. (1);

Step 3: Take the searching area and center in the previous frame as the initialization values in the current frame;

Step 4: Apply the MS algorithm and compute the searching area as follows:

where [TeX:] $$g ( x ) = - k _ { E } ^ { \prime } ( x )$$ is the Epanechnikov function. w_i is the weight for the pixels in the object area and it is calculated as follows:

Step 5: If [TeX:] $$\left\| y _ { 1 } < y \right\| < \varepsilon$$, then stop searching and obtain the final tracking position. Else, let [TeX:] $$y = y _ { 1 }$$ and return to the step 4.

After detecting the object by using the MS algorithm, the final templates are inserted into a training pool. Once the number of the training samples reaches a value, the regression model is trained. Then, the estimated value generated by the regression model is used to measure the candidate areas’ similar score instead of the Bhattacharyya coefficients. The areas with the estimated values larger than a given threshold are weighted by their values to determine the object’s location:

where L_cen is the final position of an object. L_i is the position of the detected area with the estimated value larger than the given threshold. N_c is the number of the detected areas with the estimated value larger than the given threshold.

5. Results

Experimental results are detailed in the section to validate the performance of our algorithm.

5.1 Data-Sets

To evaluate the regression model based MS algorithm, a set of challenging videos which are publicly available online are used [9]. The videos are “David indoor”, “Occluded face”, “Coke can”, “Cliffer bar”, “Tiger”, and “Can”. There are serious occlusion, illumination changes, and pose variations in these videos. Furthermore, our regression model based MS algorithm is compared to other state-of-the-art trackers: MIL [15], VTD [9], compressive tracker (CT) [5]. These algorithms are realized by using the source codes available online. The default parameters of the MIL [15], VTD [9], CT [5] algorithms are used. For our algorithm, the number of the final templates is 3, while that of the candidate templates is 2. In the regression model, the dimension of the color feature is 48, while dimension of the texture feature is 36.

5.2 Tracking Results

The tracking position is used to evaluate the performance of the proposed algorithm. The tracking results are shown in Fig. 2. The tracked object is indicated by a rectangle. The red rectangles are for the proposed algorithm. The purple ones are for the MIL algorithm. The results of the VTD algorithm are indicated by the green rectangles. The results of the CT algorithm are indicated by the blue rectangles.

The results of the “David indoor” sequences are shown in the first line. There are serious illumination change and pose variation in the frame “128” and “202”. These tracking algorithms can detect the object in the frame “128”. However, as tracking evolves, the MIL, CT, VTD trackers drift. The tracking results show that the proposed algorithm is robust to the illumination variations and pose changes. The results in the second line are for the “Occluded face” sequence. The “face” is occluded by a book or a hat from the frame “495”. The proposed regression model based MS algorithm tracks the “face” by using multiple templates and updates these templates in different cases. Therefore, the algorithm can deal with the serious occlusion. The “Cliffer bar” moves fast and rotates in the tracking process. The proposed algorithm performs well over other algorithms. Especially, in the frame “412”, only the proposed algorithm detects the object. The objects, in the “Coke can” and “Tiger” sequences, move fast and are often occluded by other objects. The tracking results show that the proposed algorithm tracks the object successfully. In the last line, the “dollar” is interfered by the similar background. All the trackers can detect the “dollar”, but the MIL, CT, VTD trackers often drift away.

The experimental results show that the proposed algorithm is robust to the illumination (e.g., the “face” in the “David indoor” video), serious occlusion (e.g., the “face” in the “Occluded face” video), pose variation (e.g., the “Can” in the “Coke can” video), and scale changes (e.g., the object in the “Cliffer bar” video).

5.3 Computational Cost

The proposed tracker has been demonstrated to perform well in visual tracking. Then, the algorithm is evaluated in term of computational cost. Table 1 shows the average per-frame computational cost of these algorithms.

The MIL tracker suffers from a heavy computational cost, because it computes the bag probability and instance probability M times when a powerful classifier is selected. The CT algorithm is a fast tracker which processes a frame with the least time. However, the CT tracker often fails in the case of serious illumination changes and poses variations. The VTD realizes the tracking algorithm in the framework of IMCMC. As a result, it suffers from a long computational time. Applying the MS algorithm to multiple templates will result in heavy computational cost. To decrease the average perframe computational cost, the regression model is proposed in our algorithm. The experimental results show that the computing time of our method is lower than that of the VTD and MIL algorithms. Meanwhile, our method runs slower than the CT algorithm, but performs better especially when there are serious scale changes (e.g., in the “Cliffer bar” video). Overall, the presented algorithm can successfully track the object in real time.

6. Conclusion

In this paper, a regression model based MS algorithm is proposed for object tracking. First, multiple templates are extracted to deal with the problems of occlusion, illumination changes and pose variations. Second, a regression model is presented to estimate the similar score between the candidate area and template. The method decreases the number of templates and guarantees good performance. Third, the MS algorithm is applied to the templates, and several candidate areas with larger estimated similar scores are obtained. Then, the obtained candidate areas are weighted by the estimated similar scores for detecting the object. The experimental results have shown that the algorithm performs well in terms of illumination changes, pose variations and occlusion.

Acknowledgement

The authors would like to thank the key research and development program of the Hebei Province science (No. 18210329D) and the Natural Science Foundation of Hebei Province (No. F2018205178).