---
abstract: '> As an important and challenging problem in computer vision and graphics, keypoint-based object tracking is typically formulated in a spatio-temporal statistical learning framework. However, most existing keypoint trackers are incapable of effectively modeling and balancing the following three aspects in a simultaneous manner: temporal model coherence across frames, spatial model consistency within frames, and discriminative feature construction. To address this issue, we propose a robust keypoint tracker based on spatio-temporal multi-task structured output optimization driven by discriminative metric learning. Consequently, temporal model coherence is characterized by multi-task structured keypoint model learning over several adjacent frames, while spatial model consistency is modeled by solving a geometric verification based structured learning problem. Discriminative feature construction is enabled by metric learning to ensure the intra-class compactness and inter-class separability. Finally, the above three modules are simultaneously optimized in a joint learning scheme. Experimental results have demonstrated the effectiveness of our tracker.'
author:
- |
    Liming Zhao, Xi Li[^1], Jun Xiao, Fei Wu, Yueting Zhuang\
    College of Computer Science\
    Zhejiang University, Hangzhou 310027, China\
    {zhaoliming, xilizju, junx, wufei, yzhuang}@zju.edu.cn\
bibliography:
- 'zhao.bib'
title: |
    Metric Learning Driven Multi-Task Structured Output Optimization\
    for Robust Keypoint Tracking
---

Introduction
============

Due to the effectiveness and efficiency in object motion analysis, keypoint-based object tracking [@KLT1981; @Optical2010; @keypoint2013; @ConKey] is a popular and powerful tool of video processing, and thus has a wide range of applications such as augmented reality (AR), object retrieval, and video compression. By encoding the local structural information on object appearance [@Li2013], it is generally robust to various appearance changes caused by several complicated factors such as shape deformation, illumination variation, and partial occlusion [@EvaDes; @StrKey]. Motivated by this observation, we focus on constructing effective and robust keypoint models to well model the intrinsic spatio-temporal structural properties of object appearance in this paper.

![[]{data-label="fig:firstShow"}](res/flow/firstshow.pdf){width="100.00000%"}

Typically, keypoint model construction consists of keypoint representation and statistical modeling. For keypoint representation, a variety of keypoint descriptors are proposed to encode the local invariance information on object appearance, for example, SIFT [@SIFT] and SURF [@SURF]. To further speed up the feature extraction process, a number of binary local descriptors emerge, including BRIEF [@Brief], ORB [@ORB], BRISK [@BRISK], FREAK [@FREAK], etc. Since the way of feature extraction is handcrafted and fixed all the time, these keypoint descriptors are usually incapable of effectively and flexibly adapting to complex time-varying appearance variations as tracking proceeds.

In general, statistical modeling is cast as a tracking-by-detection problem, which seeks to build an object locator based on discriminative learning such as randomized decision trees [@RandTrees; @RandFerns] and boosting [@Boost2007; @Boost2013]. However, these approaches usually generate the binary classification output for object tracking, and thus ignore the intrinsic structural or geometrical information (e.g., geometric transform across frames) on object localization and matching during model learning. To address this issue, Hare [*et al.*]{} [@Hare2012] propose a structured SVM-based keypoint tracking approach that incorporates the RANSAC-based geometric matching information into the optimization process of learning keypoint-specific SVM models. As a result, the proposed tracking approach is able to simultaneously find correct keypoint correspondences and estimate underlying object geometric transforms across frames. In addition, the model learning process is independently carried out frame by frame, and hence ignores the intrinsic cross-frame interaction information on temporal model coherence, leading to instable tracking results in complicated scenarios.

In this work, we propose a joint learning approach that is capable of well balancing the following three important parts: temporal model coherence across frames, spatial model consistency within frames, and discriminative feature construction. As illustrated in Figure \[fig:firstShow\], the joint learning approach ensures the temporal model coherence by building a multi-task structured model learning scheme, which encodes the cross-frame interaction information by simultaneously optimizing a set of mutually correlated learning subtasks (i.e., a common model plus different biases) over several successive frames. As a result, the interaction information induced by multi-task learning can guide the tracker to produce stable tracking results. Moreover, the proposed approach explores the keypoint-specific structural information on spatial model consistency by performing geometric verification based structured output learning, which aims to estimate a geometric transformation while associating cross-frame keypoints. In order to make the keypoint descriptors well adapt to time-varying tracking situations, the proposed approach naturally embeds metric learning to the structured SVM learning process, which enhances the discriminative power of inter-class separability.

In summary, we propose a keypoint tracking approach that learns an effective and robust keypoint model through metric learning-driven multi-task structured output optimization. The main contributions of this work are as follows:

1.  We propose a multi-task joint learning scheme to learn structured keypoint models by simultaneously considering spatial model consistency, temporal model coherence, and discriminative feature learning. An online optimization algorithm is further presented to efficiently and effectively solve the proposed scheme. To our knowledge, it is the first time that such a joint learning scheme is proposed for learning-based keypoint tracking.

2.  We create and release a new benchmark video dataset containing four challenging video sequences (covering several complicated scenarios) for experimental evaluations. In these video sequences, the keypoint tracking results are manually annotated as ground truth. Besides, the quantitative results on them are also provided in the experimental section.

Approach
========

Our tracking approach is mainly composed of two parts: learning part and prediction part. Namely, an object model is first learned by a multi-task structured learning scheme in a discriminative feature space (induced by metric learning). Based on the learned object model, our approach subsequently produces the tracking results through structured prediction. Using the tracking results, a set of training samples are further collected for structured learning. The above process is repeated as tracking proceeds.

Preliminary {#sec:model}
-----------

Let the template image $O$ be represented as a set of keypoints $O=\{(u_i, \q_i)\}_{i=1}^{N^O}$, where each keypoint is defined by a location $u_i$ and associated descriptor $\q_i$. Similarly, let $I=\{(v_j,\d_j)\}_{j=1}^{N^I}$ denote the input frame with keypoints. Typically, the traditional approaches construct the correspondences between the template keypoints and the input frame keypoints. The correspondences are scored by calculating the distances between $\{\q_i\}_{i=1}^{N^O}$ and $\{\d_j\}_{j=1}^{N^I}$. Following the model learning approaches [@Hare2012; @track2012], we learn a model parameterized by a weight vector $\w_i$ for the template keypoint $u_i$ to score each correspondence. The set of the hypothetical correspondences is defined as $\C=\{(u_i,v_j,s_{ij})| (u_i,\q_i)\in O,(v_j,\d_j)\in I,s_{ij}=\left<\w_i,\d_j\right>\}$, where $s_{ij}$ is a correspondence score and $\left<\cdot,\cdot\right>$ is the inner product.

Similar to [@Hare2012; @track2013], we estimate the homography transformation for planar object tracking as the tracking result based on the hypothetical correspondences.

Multi-task Structured Learning {#sec:structure}
------------------------------

During the tracking process, the keypoints in the successive frames $\{I_1,I_2,\dots\}$ corresponding to the $i$-th keypoint $u_i$ in the template image form a tracklet $\{v^1,v^2,\dots\}$. Based on the observation that the adjacent keypoints in a tracklet are similar to each other, the models learned for the frames $\{\w_i^1,\w_i^2,\dots\}$ should be mutually correlated. So we construct $K$ learning tasks over several adjacent frames. For example, task $k$ learns a model $\w^k$ over the training samples collected from the frames $I_{1}$ to $I_{t+k}$, where $\w^k=[\w_1^k,\dots,\w_{N^O}^k]^\T$ is the column concatenation of the model parameter vectors. We model each $\w^k$ as a linear combination of a common model $\w^0$ and an unique part $\v^k$ [@multi2013]: $$\w^k=\w^0+\v^k,\quad k=1,\dots,K$$ where all the vectors $\{\v^k\}_{k=1}^K$ are “small” when the tasks are similar to each other.

To consider the spatial model consistency in the model learning process, the transformation which maps the template to the location of the input frame is regarded as a structure, which can be learned in a geometric verification based structured learning framework. In our approach, the expected transformation $\hat{\y}$ is expressed as $\hat{\y}=\argmax_{\y\in\Y}F(\C,\y)$, where $F$ is a compatibility function, scoring all possible transformations generated by using the RANSAC [@Ransac] method. Before introducing the compatibility function, we give the definition of the inlier set with a specific transformation $\y$: $$\label{eq:inlier}
\H(\C,\y)=\{(u_i,v_j)| (u_i,v_j)\in\C, \lVert\y(u_i)-v_j\rVert<\tau\}$$ where $\y(u_i)$ is the transformed location in the input frame of the template keypoint location $u_i$, $\tau\in\R$ is a spatial distance threshold, and $\lVert\cdot\rVert$ denotes the Euclidean norm.

The compatibility function with respect to task $k$ is then defined as the total score of the inliers: $$\label{eq:F}
\begin{aligned}
F^k(\C,\y)=\hspace{-1em}\sum_{(u_i,v_j)\in\H(\C,\y)}\hspace{-2em}\left<\w_i^k,\d_j\right>
        =\left<\w^k,\Fai(\C,\y)\right>
\end{aligned}$$ where $\Fai(\C,\y)$ is a joint feature mapping vector concatenated by $\fai_i(\C,\y)$ which is defined as: $$\label{eq:Phi}
\fai_i(\C,\y)=
\begin{cases}
\d_j & \exists(u_i,v_j)\in \C: \lVert\y(u_i)-v_j\rVert<\tau\\
\0   &\textrm{otherwise}
\end{cases}$$

Given training samples $\{(\C_t,\y_t)\}_{t=1}^{T}$ (each $\C_t$ is the hypothetical correspondences of the frame $I_t$, and $\y_t$ is the predicted transformation), a structured output maximum margin framework [@markov; @SSVM2005] is used to learn all the multi-task models, which can be expressed by the following optimization problem: $$\label{eq:multi}
\begin{aligned}
\min_{\w^0,\v^k,\boldsymbol\xi}
&\frac{1}{2}\lVert\w^0\rVert^2
+\frac{\lambda_1}{2K}\sum_{k=1}^K\lVert\v^k\rVert^2
+\nu_1\sum_{k=1}^K\sum_{t=k}^T\xi_{kt}
\\
\text{s.t.}
&\forall k,t, \xi_{kt} \geq 0\\
&\forall k,t, \forall \y\neq\y_t: \delta F_t^k(\y)\geq\Delta(\y_t,\y)-\xi_{kt}
\end{aligned}$$ where $\delta F^k_t(\y)=\left<\w^k,\Fai(\C_t,\y_t)\right>-\left<\w^k,\Fai(\C_t,\y)\right>$ and $\Delta(\y_t,\y)$ is a loss function which measures the difference of two transformations (in our case, the loss function $\Delta(\y_t,\y)=|\#\H(\C,\y_t)-\#\H(\C,\y)|$ is the difference in number of two inlier sets). The nonnegative ${\lambda_1}$ is the weight parameter for multiple tasks, and the weighting parameter $\nu_1$ determines the trade-off between accuracy and regularization.

![[]{data-label="fig:multi"}](res/multi/paper.pdf "fig:"){width="100.00000%"}\
(a) tracking result

![[]{data-label="fig:multi"}](res/multi/origin420.jpg "fig:"){width="82.00000%"}\
(b) without multi-task ![[]{data-label="fig:multi"}](res/multi/multi420.jpg "fig:"){width="82.00000%"}\
(c) with multi-task

To better describe the contribution of the multi-task learning, example tracking results of the trackers with and without multi-task learning are shown in Figure \[fig:multi\]. From Figure \[fig:multi\](b), we observe that the independent model fails to match the keypoints in the case of drastic rotations, while the multi-task model enables the temporal model coherence to capture the information of rotational changes, thus produces a stable tracking result.

Discriminative Feature Space {#sec:metric}
----------------------------

In order to make the keypoint descriptors well adapt to time-varying tracking situations, we wish to learn a mapping function $f(\d)$ that maps the original feature space to another discriminative feature space, in which the semantically similar keypoints are close to each other while the dissimilar keypoints are far away from each other, that can be formulated as a metric learning process [@Metric2009; @Metric2011]. We then use the mapped feature $f(\d)$ to replace the original feature $\d$ in the structured learning process, to enhance its discriminative power of inter-class separability.

Figure \[fig:metric\] shows an example of such feature space transformation. Before the mapping procedure, the object keypoints and the background keypoints can not be discriminated in the original feature space. After the transformation, the keypoints in different frames corresponding to the same keypoint in the template, which are semantically similar, get close to each other in the mapped feature space, while the features of the other keypoints have a distribution in another side with a large margin.

![[]{data-label="fig:metric"}](res/metric/book50origin.pdf "fig:"){width="100.00000%"} (a) before mapping

![[]{data-label="fig:metric"}](res/metric/book50metric.pdf "fig:"){width="100.00000%"} (b) after mapping

The following describes how to learn the mapping function. For a particular task $k$, given the learned model $\w_i^k$, the distance between a doublet $(\d_j,\d_k)$ is defined as follows: $$\label{eq:distance}
D_i^k(\d_j,\d_{j'})=\left<\w_i^k,f(\d_j)-f(\d_{j'})\right>$$

We assume that the binary matrix $p_{j{j'}}\in\{0,1\}$ indicates whether or not the features $\d_j$ and $\d_{j'}$ are semantically similar (if they are similar, $p_{j{j'}}=1$). Therefore, the hinge loss function on a doublet is defined as: $$\ell_i^k(\d_{j},\d_{j'})=[(-1)^{p_{j{j'}}}(1-D_i^k(\d_{j},\d_{j'}))]_+$$ where $[z]_+=\max(z,0)$.

To learn the effective feature consistently in our mapping process, we wish to find the group-sparsity of the features. So we utilize $\l21$-norm [@L21norm1; @L21norm2] to learn the discriminative information and feature correlation consistently. Since we use a linear transformation $f(\d)=\M^{\T}\d$ as our mapping function, the $\l21$-norm for the mapping matrix $\M$ is defined as: $\lVert\M\rVert_{2,1}=\sum_{i}\sqrt{\sum_{j}\M_{ij}^2}$.

Given all the keypoint features from the video frames $\{I_t\}_{t=1}^T$, we collect all possible combinations of the features as the training set, which is denoted as $\A=\{(\d_j,\d_{j'})|\d_j\in\{I_t\}_{t=1}^T, {j'}\neq{j}, \d_{j'}\in\{I_t\}_{t=1}^T\}$. We obtain the binary matrix $p_{j{j'}}$ by using the tracking results (if $\d_j$ and $\d_{j'}$ from different frames correspond to the same keypoint in the template, $p_{j{j'}}$ is set to 1; otherwise, $p_{j{j'}}$ is set to 0). We wish to minimize the following cost function consisting of the empirical loss term and the $\l21$-norm regularization term: $$\label{eq:metricLoss}
\sum_{i,k,(\d_{j},\d_{j'})\in\A}\hspace{-1.2em}\ell_i^k(\d_{j},\d_{j'})
 + \lambda\lVert\M\rVert_{2,1}$$

The cost function is incorporated into our multi-task structured learning framework, and then a unified joint learning scheme for object tracking is obtained. The final optimization problem of our approach is expressed in the following form: $$\label{eq:final}
\begin{aligned}
\min_{\w^0,\v^k,\M,\boldsymbol\xi,\boldsymbol\gamma}
&\frac{1}{2}\lVert\w^0\rVert^2
+\frac{\lambda_1}{2K}\sum_{k=1}^K\lVert\v^k\rVert^2
+{\lambda_2}\lVert\M\rVert_{2,1}&\\
+\sum_{k=1}^K&
\Big(
\nu_1\sum_{t=k}^T\xi_{kt}
+\nu_2\sum_{t=k}^T\sum_{(u_i,v_j) \in \H(\C_t,\y_t)}\hspace{-1.5em}\gamma_{kti}
\hspace{0.3em}\Big)\\
\text{s.t.}\forall k,t,& \xi_{kt} \geq 0&\\
\forall k,t,& \forall \y\neq\y_t: \delta F_t^k(\y)\geq\Delta(\y_t,\y)-\xi_{kt}&\\
\forall k,t,&i: \gamma_{kti}\geq 0&\\
\forall k,t,&(u_i,v_j), \forall j'\neq j: D_i^k(\d_j,\d_{j'})\geq 1-\gamma_{kti}&
\end{aligned}$$

After all the models $\w^1,\w^2,\dots,\w^K$ are learned, we use the last model $\w=\w^K$ to predict the result of new frame $I_t$. We use the RANSAC method to generate hypothetical transformations. Based on the model $\w$, we predict the expected transformation $\y_t$ from all hypothetical transformations by maximizing Eq. . The hypothetical correspondence set $\C_t$ of the frame $I_t$ and the predicted transformation $\y_t$ are then added to our training set. We use all the training samples collected from the results of previous $K$ frames ($I_{t-K+1}$ to $I_{t}$) to update our model. Then the above process is repeated as tracking proceeds.

Online Optimization {#sec:optimization}
-------------------

The optimization problem presented in Eq.  can be solved online effectively. We adopt an alternating optimization algorithm to solve the optimization problem.

#### Unconstrained form

Let $\a_{kt}=[\max_{\y\neq\y_t}\{\Delta(\y_t,\y)-\delta F_t^k(\y)\}]_+$ and $\b_{kti}=[\max_{j'\neq j}\{1-D_i^k(\d_j,\d_{j'})\}]_+$. Therefore, Eq.  can be rewritten to an unconstrained form: $$\label{eq:relaxed}
\begin{aligned}
\min_{\w^0,\v^k,\M}
\frac{1}{2}\lVert\w^0\rVert^2
+\frac{\lambda_1}{2K}\sum_{k=1}^K\lVert\v^k\rVert^2
+{\lambda_2}\lVert\M\rVert_{2,1}\\
+\sum_{k=1}^K
\Big(
\nu_1\sum_{t=k}^T\a_{kt}
+\nu_2\sum_{t=k}^T\sum_{(u_i,v_j) \in \H(\C_t,{\y_t})}\hspace{-1.5em}\b_{kti}
\hspace{0.2em}\Big)
\end{aligned}$$

For descriptive convenience, let $\J$ denote the term of $\nu_1\sum_{t=k}^T\a_{kt}+\nu_2\sum_{t=k}^T\sum_{(u_i,v_j) \in \H(\C_t,{\y_t})}\b_{kti}$.

#### Fix $\{\v^k\}_{k=1}^K$ and $\w^0$, solve $\M$

Firstly, we fix all $\{\v^k\}_{k=1}^K$ and $\w^0$, and learn the transformation matrix $\M$ by solving the following problem: $$\label{eq:M}
\min_{\M}
\hspace{0.2em}
\lVert\M\rVert_{2,1}
+\frac{1}{\lambda_2}\sum_{k=1}^K{\J}$$

Let $\M^i$ denote the $i$-th row of $\M$, and $Tr(\cdot)$ denote the trace operator. In mathematics, the Eq.  can be converted to the following form: $$\label{eq:M2}
\begin{aligned}
\min_{\M}
\hspace{0.2em}
Tr(\M^{\T}\D\M)
+\frac{1}{\lambda_2}\sum_{k=1}^K{\J}
\end{aligned}$$ where $\D$ is the diagonal matrix of $\M$, and each diagonal element is $\D_{ii}=\frac{1}{2\lVert\M^i\rVert_2}$. We use an alternating algorithm to calculate $\D$ and $\M$ respectively. We calculate $\M$ with the current $\D$ by using gradient descent method, and then update $\D$ according to the current $\M$. The details of solving Eq.  are shown in the supplementary file.

#### Fix $\M$ and $\{\v^k\}_{k=1}^K$, solve $\w^0$

Secondly, after $\M$ is learned, let $\{\v^k\}_{k=1}^K$ have been the optimal solution of Eq. . Then $\w^0$ can be obtained by the combination of $\v^k$ according to [@Multitask]: $$\w^0=\hspace{0.2em}\frac{\lambda_1}{K}\sum_{k=1}^{K}\v^k$$ The proof can be found in our supplementary material.

#### Fix $\M$ and $\w^0$, solve $\{\v^k\}_{k=1}^K$

Finally, $\{\v^k\}_{k=1}^K$ can be learned one by one using gradient descent method. In fact, we learn $\w^k=\w^0+\v^k$ instead of $\v^k$ for convenience. Let $\bar{\w}=\frac{1}{K}\sum_{k=1}^{K}\w^k$ be the average vector of all $\w^k$. Then the optimization problem for each $\w^k$ can be rewritten as: $$\label{eq:v}
\begin{aligned}
\min_{\w^k}
\hspace{0.2em}
\rho_1\lVert\w^k\rVert^2
+\rho_2\lVert\w^k-\bar{\w}\rVert^2+{\J}
\end{aligned}$$ where $\rho_1={\lambda_1}/({\lambda_1+1})$ and $\rho_2={\lambda_1^2}/({\lambda_1+1})$ (the derivation proof is given in the supplementary material).

Given training samples $\{(\C_{t-k},\y_{t-k})\}_{k=0}^{K-1}$ at time $t$, the subgradient of Eq.  with respect to $\w^k$ is calculated, and we perform a gradient descent step according to: $$\label{eq:updateV}
\begin{aligned}
\w^k\leftarrow
\hspace{0.2em}
(1-\frac{1}{t})\w^k
+\eta\rho_2\bar{\w}
-\eta\frac{\partial\J}{\partial\w^k}
\end{aligned}$$ where $\eta={1}/{(\rho_1t+\rho_2t)}$ is the step size (the details of the term $J$ is described in the supplementary material). We repeat the procedure to obtain an optimal solution until the algorithm converges (on average converges after $5$ iterations).

All the above is summarized in Algorithm \[alg:opt\], and the details are described in the supplementary material.

Calculate the correspondences $\C_t$ based on the model $\w^K$ Estimate hypothetical transformations $\y$ using RANSAC; Calculate the inlier set of each $\y$ using Eq.  Predict the expected $\y_t$ by maximizing Eq.  Collect the training samples $\{(\C_{t-k},\y_{t-k})\}_{k=0}^{K-1}$ $\y_t$, $\{\w^1,\dots,\w^K\}$ and $\M$

Experiments and Results
=======================

Experimental Settings
---------------------

#### Dataset

The video dataset used in our experiments consists of nine video sequences. Specifically, the first five sequences are from [@Hare2012], and the last four sequences (i.e., “chart”, “keyboard”, “food”, “book”) are recorded by ourselves. All these sequences cover several complicated scenarios such as background clutter, object zooming, object rotation, illumination variation, motion blurring and partial occlusion (example frames can be found in the supplementary material).

#### Implementation Details

For keypoint feature extraction, we use FAST keypoint detector [@Fast] with 256-bit BRIEF descriptor [@Brief]. For metric learning, the linear transformation matrix $\M$ is initialized to be an identity matrix. For multi-task learning, the number of tasks $K$ is chosen as $5$ and we update all the multi-task models frame by frame. All weighting parameters $\lambda_1,\lambda_2,\nu_1,\nu_2$ are set to $1$, and remain fixed throughout all the experiments. Similar to [@Hare2012], we consider the tracking process of estimating homography transformation on the planar object as a tracking-by-detection task.

#### Evaluation Criteria

We use the same criteria as [@Hare2012] with a scoring function between the predicted homography $\y$ and the ground-truth homography $\y^*$: $$S(\y,\y^*)=\frac{1}{4}\sum_{i=1}^{4}\lVert\y(c_i)-\y^*(c_i)\rVert_2$$ where $\{c_i\}_{i=1}^4=\{(-1,-1)^\T,(1,-1)^\T,(-1,1)^\T,(1,1)^\T\}$ is a normalized square. For each frame, it is regarded as a successfully detected frame if $S(\y,\y^*)<10$, and a falsely detected frame otherwise. The average success rate is defined as the number of successfully detected frames divided by the length of the sequence, which is used to evaluate the performance of the tracker. To provide the tracking result frame by frame, we present a criterion of the accumulated false detection number, which is defined as the accumulated number of falsely detected frames as tracking proceeds.

Experimental Results
--------------------

#### Comparison with State-of-the-art Methods

We compare our approach with some state-of-the-art approaches, including boosting based approach [@Boost2007], structured SVM (SSVM) approach [@Hare2012] and a baseline static tracking approach (without model updating). All these approaches are implemented by making use of their publicly available code. We also implement our approach in C++ and OPENCV. On average, our algorithm takes 0.0746 second to process one frame with a quad-core 2.4GHz Intel Xeon E5-2609 CPU and 16GB memory. Table \[tab:others\] shows the experimental results of all four approaches in the average success rate. As shown in this table, our approach performs best on all sequences.

  ----------- --------- ---------- ------ ------
                                          
               Static    Boosting   SSVM   Ours
   barbapapa   19.7138   89.0302          
     comic     42.5000   57.6042          
      map      81.1295   82.0937          
     paper     05.0267   03.8502          
     phone     88.1491   84.9534          
     chart     13.1461   01.9101          
   keyboard    27.8607   57.7114          
     food      32.8173   67.4923          
     book      08.5616   08.9041          
  ----------- --------- ---------- ------ ------

  : []{data-label="tab:others"}

![[]{data-label="fig:chart"}](res/chart/chart.pdf){width="100.00000%"}

![[]{data-label="fig:chart"}](res/chart/keyboard.pdf){width="100.00000%"}

\

![[]{data-label="fig:chart"}](res/chart/food.pdf){width="100.00000%"}

![[]{data-label="fig:chart"}](res/chart/book.pdf){width="100.00000%"}

To provide an intuitive illustration, we report the detection result on each frame in Figure \[fig:chart\]. We observe that both the “Boosting” and “SSVM” approaches obtain a number of incorrect detection results on some frames of the test sequences, while our approach achieves stable tracking results in most situations (the curve corresponding to our approach grows slowly and is almost horizontal).

Figure \[fig:exp\] shows the tracking results on some sample frames (more experimental results can be found in our supplementary materials). These sequences containing background clutter are challenging for keypoint based tracking. In terms of metric learning and multi-task learning, our approach still performs well in some complicated scenarios with drastic object appearance changes.

SSVMOurs\
![[]{data-label="fig:exp"}](res/exp/chart/origin388.jpg "fig:"){width="49.00000%"} ![[]{data-label="fig:exp"}](res/exp/chart/ours388.jpg "fig:"){width="49.00000%"}\
(a) chart frame 388 (camera motion blurring)\

\

![[]{data-label="fig:exp"}](res/exp/keyboard/origin300.jpg "fig:"){width="49.00000%"} ![[]{data-label="fig:exp"}](res/exp/keyboard/ours300.jpg "fig:"){width="49.00000%"}\
(b) keyboard frame 300 (illumination variation)\

\

![[]{data-label="fig:exp"}](res/exp/food/origin350.jpg "fig:"){width="49.00000%"} ![[]{data-label="fig:exp"}](res/exp/food/ours350.jpg "fig:"){width="49.00000%"}\
(c) food frame 350 (object rotation)\

\

![[]{data-label="fig:exp"}](res/exp/book/origin357.jpg "fig:"){width="49.00000%"} ![[]{data-label="fig:exp"}](res/exp/book/ours357.jpg "fig:"){width="49.00000%"}\
(d) book frame 357 (confusing keypoints)\

#### Evaluation of Our Individual Components

To explore the contribution of each component in our approach, we compare the performances of the approaches with individual parts, including SSVM(structured SVM), SML(SSVM $+$ metric learning), SMT(SSVM $+$ multi-task learning), and SMM (SSVM $+$ ML $+$ MT, which is exactly our approach). The experimental results of all these approaches in the average success rate are reported in Table \[tab:ours\].

  ------------------------- --------- --------- --------- -----
   \[4\][\*]{}[Sequence]{}                                
                              SSVM       SML       SMT     SMM
          barbapapa          94.1176             94.2766  
            comic            98.1250   98.5417            
             map                       98.6226            
            paper            82.7807   86.2032            
            phone            96.6711   97.2037            
            chart            53.0337             61.1236  
          keyboard           62.3549   73.6318            
            food             85.7585   88.0805            
            book             55.8219   71.5753            
  ------------------------- --------- --------- --------- -----

  : []{data-label="tab:ours"}

![[]{data-label="fig:indiv"}](res/indiv/comic.pdf){width="100.00000%"}

![[]{data-label="fig:indiv"}](res/indiv/keyboard.pdf){width="100.00000%"}

\

![[]{data-label="fig:indiv"}](res/indiv/food.pdf){width="100.00000%"}

![[]{data-label="fig:indiv"}](res/indiv/book.pdf){width="100.00000%"}

From Table \[tab:ours\], we find that the geometric verification based structured learning approach achieves good tracking results in most situations. Furthermore, we observe from Figure \[fig:indiv\] that multi-task structured learning guides the tracker to produce a stable tracking result in the complicated scenarios, and metric learning enhances the capability of the tracker to separate keypoints from background clutter. Our approach consisting of all these components then generates a robust tracker.

Conclusion
==========

In this paper, we have presented a novel and robust keypoint tracker by solving a multi-task structured output optimization problem driven by metric learning. Our joint learning approach have simultaneously considered spatial model consistency, temporal model coherence, and discriminative feature construction during the tracking process.

We have shown in extensive experiments that geometric verification based structured learning has modeled the spatial model consistency to generate a robust tracker in most scenarios, multi-task structured learning has characterized the temporal model coherence to produce stable tracking results even in complicated scenarios with drastic changes, and metric learning has enabled the discriminative feature construction to enhance the discriminative power of the tracker. We have created a new benchmark video dataset consisting of challenging video sequences, and experimental results performed on the dataset have shown that our tracker outperforms the other state-of-the-art trackers.

Acknowledgments
===============

All correspondence should be addressed to Prof. Xi Li. This work is in part supported by the National Natural Science Foundation of China (Grant No. 61472353), National Basic Research Program of China (2012CB316400), NSFC (61472353), 863 program (2012AA012505), China Knowledge Centre for Engineering Sciences and Technology and the Fundamental Research Funds for the Central Universities.

[^1]: Corresponding Author
