% !TEX root = ../../../thesis.tex
\chapter{Online structured output tracking}\label{sec:struck_method}

\section{Tracking by detection}\label{sec:struck_traditional}
In this section we provide an overview of traditional adaptive tracking-by-detection algorithms, which attempt to learn a classifier to distinguish a target object from its local background. 

Typically, the tracker maintains an estimate of the position $\vt{p} \in \cal{P}$ of a 2D bounding box containing the target object within a frame of a video sequence $\vt{f}_t \in \cal{F}$, where $t = 1, \dots, T$ is the time. Given a bounding box position $\vt{p}$, a classifier is applied to features extracted from an image patch within the bounding box $\vt{x}_t^{\vt{p}} \in \cal{X}$. The classifier is trained with example pairs $(\vt{x}, z)$, where $z = \pm 1$ is a binary label, and makes its predictions according to $\hat{z} = \text{sign}(h(\vt{x}))$, where $h : {\cal X} \rightarrow \mathbb{R}$ is the classification confidence function.

During tracking, it is assumed that a change in position of the target can be estimated by maximising $h$ in a local region around the position in the previous frame. Let $\vt{p}_{t-1}$ be the estimated bounding box at time $t-1$. The objective for the tracker is to estimate a transformation (\eg ~translation) $\vt{y}_{t} \in {\cal Y}$ such that the new position of the object is approximated by the composition $\vt{p}_t = \vt{p}_{t-1} \circ \vt{y}_t$. ${\cal Y}$ denotes our \emph{search space} and its form depends on the type of motion to be tracked. For most tracking-by-detection approaches this is 2D translation, in which case ${\cal Y} = \{(\Delta u, \Delta v) \; | \; \Delta u^2+\Delta v^2<r^2\}$, where $r$ is a search radius. In this case the composition $\vt{p}_t = \vt{p}_{t-1} \circ \vt{y}_t$ is given by $(u_t, v_t) = (u_{t-1}, v_{t-1}) + (\Delta u, \Delta v)$.
%In other words, after receiving a new frame $\vt{f}_t$, the tracker maintains an estimate of bounding box location $\vt{p}_t$ by applying the transformation $\vt{y}_t$ to the previous estimate $\vt{p}_{t-1}$. 
Mathematically, an estimate is found for the change in position relative to the previous frame according to
\begin{equation}\label{eqn:struck_tracking_detection_prediction}
	\vt{y}_t = \argmax_{\vt{y} \in {\cal Y}} \ h(\vt{x}_{t}^{\vt{p}_{t - 1} \circ \vt{y}}),
\end{equation}
and the tracker position is updated as $\vt{p}_t = \vt{p}_{t-1} \circ \vt{y}_t$. 

After estimating the new object position, a set of training examples from the current frame is generated. We separate this process into two components: the \emph{sampler} and the \emph{labeller}. The sampler generates a set of $n$ different transformations $\{\vt{y}_t^1, \dots, \vt{y}_t^n\}$, resulting in a set of training examples $\{\vt{x}_t^{\vt{p}_t \circ \vt{y}_t^1}, \dots, \vt{x}_t^{\vt{p}_t \circ \vt{y}_t^n}\}$.
%Let $\{\vt{y}_t^1, \dots, \vt{y}_t^n\}$ to be $n$ different transformations. The \emph{sampler} generates a set of training examples $\{\vt{x}_t^{\vt{p}_t \circ \vt{y}_t^1}, \dots, \vt{x}_t^{\vt{p}_t \circ \vt{y}_t^n}\}$. 
After this process, depending on the classifier type, the labeller chooses labels $\{z_t^1, \dots, z_t^n\}$ for these training examples. Finally, the classifier is updated using these training examples and labels.

There are a number of issues which are raised by this approach to tracking. Firstly, the assumption made in \eqref{eqn:struck_tracking_detection_prediction} that the classification confidence function provides an accurate estimate of object position is not explicitly incorporated into the learning algorithm, since the classifier is trained only with binary examples and has no information about transformations. Secondly, examples used for training the classifier are all equally weighted, meaning that a negative example which overlaps significantly with the tracker bounding box is treated the same as one which overlaps very little. One implication of this is that slight inaccuracy during tracking can lead to poorly labelled examples, which are likely to reduce the accuracy of the classifier, in turn leading to further tracking inaccuracy. Thirdly, the labeller is usually chosen based on intuitions and heuristics, rather than having a tight coupling with the classifier. Mistakes made by the labeller manifest themselves as \emph{label noise}, and many current state-of-the-art approaches try to mitigate this problem by using robust loss functions~\cite{Leistner2009,Masnadi-shirazi2010}, semi-supervised learning~\cite{Grabner2008,Saffari2010}, or multiple-instance learning~\cite{Babenko2011,Zeisl2010}. We argue that all of these techniques, though justified in increasing the robustness of the classifier to label noise, are not addressing the real problem which stems from separating the labeller from the learner. The algorithm which we present does not depend on a labeller and tries to overcome all these problems within a coherent framework by directly linking the learning to tracking and avoiding an artificial binarisation step. Sample selection is fully controlled by the learner itself, and relationships between samples such as their relative similarity are taken into account during learning.

To conclude this section, we describe how a conventional labeller works, as this provides further insight into our algorithm. Traditional labellers use a \emph{transformation similarity function} to determine the label of a sample positioned at $\vt{p}_t \circ \vt{y}_t^i$. This function can be expressed as $s_{\vt{p}_t}(\vt{y}_t^i, \vt{y}_t^j) \in \mathbb{R}$ which, given a reference position $\vt{p}_t$ and two transformations $\vt{y}_t^i$ and $\vt{y}_t^j$, determines how similar the resulting samples are. For example, the overlap function defined by
\begin{equation}\label{eqn:struck_overlap_func}
	s_{\vt{p}_t}^o(\vt{y}_t^i, \vt{y}_t^j) = \frac{(\vt{p}_t \circ \vt{y}_t^i) \cap (\vt{p}_t \circ \vt{y}_t^j)}{(\vt{p}_t \circ \vt{y}_t^i) \cup (\vt{p}_t \circ \vt{y}_t^j)}
\end{equation}
measures the degree of overlap between two bounding boxes. Another example of such a function is based on the distance of two transformations $s_{\vt{p}_t}^d(\vt{y}_t^i, \vt{y}_t^j) = - d(\vt{y}_t^i, \vt{y}_t^j)$.

Let $\vt{y}^0$ denote the identity (or null) transformation, \ie ~$\vt{p} = \vt{p} \circ \vt{y}^0$. Given a transformation similarity function, the labeller determines the label $z_t^i$ of a sample generated by transformation $\vt{y}_t^i$ by applying a \emph{labelling function} $z_t^i~=~\ell(s_{\vt{p}_t}(\vt{y}^0, \vt{y}_t^i))$. Most commonly, this can be expressed as
\begin{equation}\label{eqn:struck_labelling_function}
\ell(s_{\vt{p}_t}(\vt{y}^0, \vt{y}_t^i)) = \left\{ \begin{array}{rcl}
+1 & \mbox{for} & s_{\vt{p}_t}(\vt{y}^0, \vt{y}_t^i) \geq \theta_u \\
-1 & \mbox{for} & s_{\vt{p}_t}(\vt{y}^0, \vt{y}_t^i) < \theta_l \\
0  & \mbox{for} & \mbox{otherwise}
\end{array}\right.
\end{equation}
where $\theta_u$ and $\theta_l$ are upper and lower thresholds, respectively. A binary classifier generally ignores the unlabelled examples~\cite{Grabner2006}, while those based on semi-supervised learning use them in their update phase~\cite{Grabner2008,Saffari2010}. In approaches based on multiple-instance learning~\cite{Babenko2011,Zeisl2010}, the labeller collects all the positive examples in a \emph{bag} and assigns a positive label to the bag instead. Most, if not all, variants of adaptive tracking-by-detection algorithms use a labeller which can be expressed in a similar fashion. However, it is not clear how the labelling parameters (\eg ~the thresholds $\theta_u$ and $\theta_l$ in the previous example) should be estimated in an online learning framework. Additionally, such heuristic approaches are often prone to noise and it is not clear why such a function is in fact suitable for tracking. In the subsequent section, we will derive our algorithm based on a structured output approach which fundamentally addresses these issues and can be thought of as a generalisation of these heuristic methods.



%This question was the focus of [Babenko], which found that it was possible to improve tracking performance considerably by using multiple instance learning (MIL) to allow the classifier to choose positive examples for itself from a number of candidates. Thirdly,  This is a particular problem if the classifier is not robust to label noise, as is known to be the case for boosting, which is often used in tracking by detection algorithms [Prost]. To reduce the likelihood of label noise occurring, one can adjust the sampling method used for updating the classifier, or attempt to modify the learner to make it more robust to label noise. MIL is one such approach, another is to use semi-supervised learning to avoid assigning hard labels during tracking [Grabner].

% need to motivate this approach by talking about the way classifiers are trained when performing tracking by detection. we want to track using a classifier which we are also updating online, which requires choosing samples for updates if we're using a binary classifier. if instead we use a structured output svm then the updates are automatically chosen by the learning algorithm. this section should really just start out by introducing tracking by detection and explain why it's an ok thing to do and what advantages it offers. also mention the extensions like MIL which can handle the ambiguity during self-training.

% when discussing the LaRank algorithm, connect the algorithm with what each step actually means -- i.e. finding the y of maximum gradient corresponds to finding a bounding box which simultaneously has low overlap but high score, i.e. it is automatically selecting the correct samples to use for training

\section{Structured output SVM}

Rather than learning a classifier, we propose learning a prediction function $f:{\cal X} \rightarrow {\cal Y}$ to directly estimate the object transformation between frames. Our output space is thus the space of all transformations $\cal{Y}$ instead of the binary labels $\pm 1$. In our approach, a labelled example is a pair $(\vt{x}, \vt{y})$ where $\vt{y}$ is the desired transformation of the target. We learn $f$ in a structured output SVM framework~\cite{Tsochantaridis2005,Blaschko2008}, which introduces a discriminant function $g:{\cal X} \times {\cal Y} \rightarrow \mathbb{R}$ that can be used for prediction according to

 %We therefore require a prediction function $f:{\cal X} \rightarrow {\cal Y}$, which we would like to learn from a set of example pairs $\{(\vt{x}_1, \vt{y}_1), \dots, (\vt{x}_n, \vt{y}_n)\}$. 
%In an offline setting, each $\vt{y}_i$ would be provided by ground-truth labelling of object location, whereas in an online setting the tracker will be used to provide its own labels.

%We propose learning $f$ in a structured output SVM framework [Tsochantaridis], which introduces a discriminant function $F:{\cal X}\times{\cal Y} \rightarrow \mathbb{R}$ that can be used for prediction according to

%During tracking, we observe a frame $\vt{x}_i \in {\cal X}$ and wish to estimate the target object's change in location $\vt{y}_i \in {\cal Y}$ relative to the previous frame. If, for example, we wish to track 2D translation $\vt{y}_i = (u_i, v_i)$, and the position of the object at the start of tracking is $\vt{p}_0$, then its position at time $t$ is estimated as $\vt{p}_t = \vt{p}_0 + \sum_{i=1}^t\vt{y}_i$.
%
%Our aim is therefore to learn a function $f:{\cal X} \rightarrow {\cal Y}$ which can be used for predicting the object's change in location, and to do so we formulate the problem as one of structured output regression [Tsochantaridis, Taskar?]. In this framework, a discriminant function $F:{\cal X}\times{\cal Y} \rightarrow \mathbb{R}$ is introduced which can be used for prediction by maximising over the output space ${\cal Y}$:

\begin{equation}\label{eqn:struck_structured_output_prediciton}
\vt{y}_t = f(\vt{x}_t^{\vt{p}_{t-1}})  = \argmax_{\vt{y} \in {\cal Y}} \ g(\vt{x}_t^{\vt{p}_{t-1}}, \vt{y}).
\end{equation}

% make the point that discriminant function can now include y explicitly

\noindent Note the similarity between \eqref{eqn:struck_structured_output_prediciton} and \eqref{eqn:struck_tracking_detection_prediction}: we are performing a maximisation step in order to predict the object transformation, however now the discriminant function $g$ includes the label $\vt{y}$ explicitly, meaning it can be incorporated into the learning algorithm. In our framework, rather than using the tracker position to generate binary examples for training a classifier, we instead provide the single labelled example $(\vt{x}_t^{\vt{p}_t}, \vt{y}^0)$, which is then used to update the learner.

$g$ measures the compatibility between $(\vt{x}, \vt{y})$ pairs and gives a high score to those which are well matched. By restricting this to be a linear function $g(\vt{x}, \vt{y}) = \langle\vt{w}, \vg{\Phi}(\vt{x}, \vt{y})\rangle$, where $\vg{\Phi}(\vt{x}, \vt{y})$ is a joint kernel map (to be defined later), it can be learned in a large-margin framework from a set of examples $\{(\vt{x}_1, \vt{y}_1), \dots, (\vt{x}_n, \vt{y}_n)\}$ by minimising the convex objective function

\begin{equation}\label{eqn:struck_structured_primal}
	\begin{aligned}
		& \underset{\vt{w}}{\min}
		& & \frac{1}{2}\|\vt{w}\|^2 + C\sum_{i=1}^n \xi_i \\
		& \; \text{s.t.}
		& & \forall i: \; \xi_i \geq 0 \\
		& & & \forall i, \forall \vt{y} \neq \vt{y}_i: \; \langle\vt{w}, \delta\vg{\Phi}_i(\vt{y})\rangle \geq \Delta(\vt{y}_i, \vt{y})-\xi_i
	\end{aligned}
\end{equation}

\noindent where $\delta\vg{\Phi}_i(\vt{y}) = \vg{\Phi}(\vt{x}_i, \vt{y}_i) - \vg{\Phi}(\vt{x}_i, \vt{y})$. This optimisation aims to ensure that the value of $g(\vt{x}_i, \vt{y}_i)$ for the training example $(\vt{x}_i, \vt{y}_i)$ is greater than $g(\vt{x}_i, \vt{y})$ for $\vt{y} \neq \vt{y}_i$, by a margin which depends on a loss function $\Delta$. This loss function should satisfy $\Delta(\vt{y}, \bar{\vt{y}}) = 0$ iff $\vt{y} = \bar{\vt{y}}$ and increase as $\vt{y}$ and $\bar{\vt{y}}$ become more dissimilar. The loss function plays an important role in our approach, as it allows us to address the issue raised previously of all samples being treated equally. This can be achieved by making use of the transformation similarity function introduced in Section \ref{sec:struck_traditional}. For example, as suggested by Blaschko and Lampert \cite{Blaschko2008}, we choose to base the loss function on bounding box overlap according to
\begin{equation}
	\Delta(\vt{y}, \bar{\vt{y}}) = 1 - s_{\vt{p}_t}^o(\vt{y}, \bar{\vt{y}}),
\end{equation}
where $s_{\vt{p}_t}^o(\vt{y}, \bar{\vt{y}})$ is the overlap function \eqref{eqn:struck_overlap_func}.

% what is it that encourages this to be sparse? the fact that the |Y| linear constraints were introduced in place of a single nonlinear constraint, so only max one is active

%Solving \eqref{eqn:structured-primal} is challenging because of the $n|{\cal Y}|$ constraints, which could be infinite in the case that ${\cal Y}$ is continuous. In [Tsochantaridis] the authors propose a method based on constraint generation suitable for optimisation in a batch setting. In [LaRank], the authors propose a method for online optimisation, which we use as the basis for our approach.

\section{Online optimisation}\label{sec:struck_structured_online}

To optimise \eqref{eqn:struck_structured_primal} in an online setting, we use the approach of Bordes \etal \cite{Bordes2007,Bordes2008}. Using standard Lagrangian duality techniques, \eqref{eqn:struck_structured_primal} can be converted into its equivalent dual form

\begin{equation}\label{eqn:struck_structured_dual}
	\begin{aligned}
		& \underset{\vg{\alpha}}{\max}
		& & \sum_{i,\vt{y} \neq \vt{y}_i}\!\Delta(\vt{y},\vt{y}_i)\alpha_i^\vt{y} - 
		    \frac{1}{2}\sum_{\substack{i,\vt{y}\neq\vt{y}_i \\ j,\bar{\vt{y}}\neq\vt{y}_j}}\!
		    \alpha_i^\vt{y}\alpha_j^{\bar{\vt{y}}}\langle\delta\vg{\Phi}_i(\vt{y}), \delta\vg{\Phi}_j(\bar{\vt{y}})\rangle \\
		& \; \text{s.t.}
		& & \forall i, \forall \vt{y} \neq \vt{y}_i: \; \alpha_i^\vt{y} \geq 0 \\
		& & & \forall i: \; \sum_{\vt{y} \neq \vt{y}_i}\alpha_i^\vt{y} \leq C
	\end{aligned}
\end{equation}

\noindent and the discriminant function expressed as $g(\vt{x},\vt{y}) = \sum_{i,\bar{\vt{y}} \neq \vt{y}_i} \alpha_i^{\bar{\vt{y}}} \langle \delta\vg{\Phi}_i(\bar{\vt{y}}), \vg{\Phi}(\vt{x}, \vt{y}) \rangle$. As in the case of classification SVMs, a benefit of this dual representation is that because the joint kernel map $\vg{\Phi}(\vt{x}, \vt{y})$ only ever occurs inside scalar products, it can be defined implicitly in terms of an appropriate joint kernel function $k(\vt{x},\vt{y},\bar{\vt{x}},\bar{\vt{y}}) = \langle \vg{\Phi}(\vt{x}, \vt{y}), \vg{\Phi}(\bar{\vt{x}}, \bar{\vt{y}}) \rangle$. The kernel functions we use during tracking are discussed in Section \ref{sec:struck_svm_kernels}.

%Solving \eqref{eqn:structured-dual} in a batch setting is usually achieved by using constraint generation to iteratively add violated constraints and solve the resulting constrained optimisation problem.

By reparametrising \eqref{eqn:struck_structured_dual} \cite{Bordes2007} according to

%the $(|{\cal Y}|-1)n$ dual variables $\alpha_i^\vt{y}, \vt{y} \neq \vt{y}_i$ with $|{\cal Y}|n$ variables $\beta_i^\vt{y}$ according to

\begin{equation}
	\beta_i^\vt{y} =
	\left\{
	\begin{aligned}
		& -\alpha_i^\vt{y} && \text{if $\vt{y} \neq \vt{y}_i$} \\
		& \sum_{\bar{\vt{y}}\neq\vt{y}_i}\alpha_i^{\bar{\vt{y}}} && \text{otherwise},
	\end{aligned}
	\right.
\end{equation}

\noindent the dual can be considerably simplified to

\begin{equation}\label{eqn:struck_larank_dual}
	\begin{aligned}
		& \underset{\vg{\beta}}{\max}
		& & -\sum_{i,\vt{y}}\Delta(\vt{y},\vt{y}_i)\beta_i^\vt{y} - 
		    \frac{1}{2}\sum_{i,\vt{y}, j,\bar{\vt{y}}}\beta_i^\vt{y}\beta_j^{\bar{\vt{y}}} \!
		    \langle\vg{\Phi}(\vt{x}_i,\vt{y}), \vg{\Phi}(\vt{x}_j,\bar{\vt{y}})\rangle \\
		& \; \text{s.t.}
		& & \forall i, \forall \vt{y}: \; \beta_i^\vt{y} \leq \delta(\vt{y},\vt{y}_i)C \\
		& & & \forall i: \; \sum_{\vt{y}}\beta_i^\vt{y} = 0
	\end{aligned}
\end{equation}

\noindent where $\delta(\vt{y}, \bar{\vt{y}}) = 1$ if $\vt{y} = \bar{\vt{y}}$ and 0 otherwise. This also simplifies the discriminant function to $g(\vt{x}, \vt{y}) = \sum_{i,\bar{\vt{y}}}\beta_i^{\bar{\vt{y}}} \langle\vg{\Phi}(\vt{x}_i,\bar{\vt{y}}), \vg{\Phi}(\vt{x},\vt{y})\rangle$. In this form we refer to those pairs $(\vt{x}_i, \vt{y})$ for which $\beta_i^\vt{y} \neq 0$ as \emph{support vectors} and those $\vt{x}_i$ included in at least one support vector as \emph{support patterns}. Note that for a given support pattern $\vt{x}_i$, only the support vector $(\vt{x}_i, \vt{y}_i)$ will have $\beta_i^{\vt{y}_i} > 0$, while any other support vectors $(\vt{x}_i, \vt{y})$, $\vt{y} \neq \vt{y}_i$, will have $\beta_i^\vt{y} < 0$. We refer to these as positive and negative support vectors respectively.

The core step in the optimisation algorithm of Bordes \etal\cite{Bordes2007,Bordes2008} is an SMO-style step~\cite{Platt1999} which
monotonically improves \eqref{eqn:struck_larank_dual} with respect to a pair of coefficients $\beta_i^{\vt{y}_+}$ and
$\beta_i^{\vt{y}_-}$. Because of the constraint $\sum_{\vt{y}}\beta_i^\vt{y} = 0$, the coefficients must be modified by
opposite amounts, $\beta_i^{\vt{y}_+} \leftarrow \beta_i^{\vt{y}_+}+\lambda$, $\beta_i^{\vt{y}_-} \leftarrow
\beta_i^{\vt{y}_-}-\lambda$, leading to a one-dimensional maximisation in $\lambda$ which can be solved in closed form (Algorithm~\ref{alg:struck_smo_step}).

% ------------------------------------------------------
\begin{algorithm}[tb]
\begin{algorithmic}[1]
	\REQUIRE $i$, $\vt{y}_+$, $\vt{y}_-$
	\STATE $k_{00} = \langle\vg{\Phi}(\vt{x}_i,\vt{y}_+), \vg{\Phi}(\vt{x}_i,\vt{y}_+)\rangle$
	\STATE $k_{11} = \langle\vg{\Phi}(\vt{x}_i,\vt{y}_-), \vg{\Phi}(\vt{x}_i,\vt{y}_-)\rangle$
	\STATE $k_{01} = \langle\vg{\Phi}(\vt{x}_i,\vt{y}_+), \vg{\Phi}(\vt{x}_i,\vt{y}_-)\rangle$
	\STATE $\lambda^u = \frac{g_i(\vt{y}_+) - g_i(\vt{y}_-)}{k_{00}+k_{11}-2k_{01}}$
	\STATE $\lambda = \max(0,\min(\lambda^u, C\delta(\vt{y}_+, \vt{y}_i) - \beta_i^{\vt{y}_+}))$
	\STATE \emph{Update coefficients}
	\STATE $\beta_i^{\vt{y}_+} \leftarrow \beta_i^{\vt{y}_+} + \lambda$
	\STATE $\beta_i^{\vt{y}_-} \leftarrow \beta_i^{\vt{y}_-} - \lambda$
	\STATE \emph{Update gradients}
	\FOR{$(\vt{x}_j, \vt{y}) \in {\cal S}$}
		\STATE $k_0 = \langle\vg{\Phi}(\vt{x}_j,\vt{y}), \vg{\Phi}(\vt{x}_i,\vt{y}_+)\rangle$
		\STATE $k_1 = \langle\vg{\Phi}(\vt{x}_j,\vt{y}), \vg{\Phi}(\vt{x}_i,\vt{y}_-)\rangle$
		\STATE $\nabla_j(\vt{y}) \leftarrow \nabla_j(\vt{y}) - \lambda (k_0-k_1)$
	\ENDFOR
\end{algorithmic}
\caption[\textsc{SMOStep}]{\textsc{SMOStep}}
\label{alg:struck_smo_step}
\end{algorithm}
% ------------------------------------------------------

The remainder of the online learning algorithm centres around how to choose the triplet $(i,\vt{y}_+, \vt{y}_-)$ which should be optimised by this SMO step. For a given $i$, $\vt{y}_+$ and  $\vt{y}_-$ are chosen to define the feasible search direction with the highest gradient, where the gradient of \eqref{eqn:struck_larank_dual} with respect to a single coefficient $\beta_i^\vt{y}$ is given by

\begin{equation}\label{eqn:struck_gradient}
	\begin{aligned}
		\nabla_i(\vt{y}) =& -\Delta(\vt{y},\vt{y}_i) - \sum_{j,\bar{\vt{y}}}\beta_j^{\bar{\vt{y}}}
		\langle\vg{\Phi}(\vt{x}_i,\vt{y}), \vg{\Phi}(\vt{x}_j,\bar{\vt{y}})\rangle \\
		=& -\Delta(\vt{y},\vt{y}_i) -g(\vt{x}_i, \vt{y}).
	\end{aligned}
\end{equation}

\noindent Three different update steps are considered, which map very naturally onto a tracking framework:

\begin{itemize}
\item
\textsc{ProcessNew} Processes a new example $(\vt{x}_i, \vt{y}_i)$. Because all the $\beta_i^\vt{y}$ are initially 0, and only $\beta_i^{\vt{y}_i} \geq 0$, $\vt{y}_+ = \vt{y}_i$. $\vt{y}_-$ is found according to $\vt{y}_- = \argmin_{\vt{y}\in{\cal Y}}\nabla_i(\vt{y})$.
During tracking, this corresponds to adding the true label $\vt{y}_i$ as a positive support vector and searching for the most important sample to become a negative support vector according to the current state of the learner, taking into account the loss function. Note, however, that this step does not necessarily add new support vectors, since the SMO step may not need to adjust the $\beta_i^\vt{y}$ away from 0.

\item
\textsc{ProcessOld} Processes an existing support pattern $\vt{x}_i$ chosen at random. $\vt{y}_+ = \argmax_{\vt{y}\in{\cal Y}}\nabla_i(\vt{y})$, but a feasible search direction requires $\beta_i^\vt{y} < \delta(\vt{y},\vt{y}_i)C$, meaning this maximisation will only involve existing support vectors. As for \textsc{ProcessNew}, $\vt{y}_- = \argmin_{\vt{y}\in{\cal Y}}\nabla_i(\vt{y})$.
During tracking, this corresponds to revisiting a frame for which we have retained some support vectors and potentially adding another sample as a negative support vector, as well as adjusting the associated coefficients. Again, this new sample is chosen to take into account the current learner state and loss function.

\item
\textsc{Optimize} Processes an existing support pattern $\vt{x}_i$ chosen at random, but only modifies coefficients of existing support vectors. $\vt{y}_+$ is chosen as for \textsc{ProcessOld}, and $\vt{y}_- = \argmin_{\vt{y}\in{\cal Y}_i}\nabla_i(\vt{y})$, where ${\cal Y}_i = \{\vt{y} \in {\cal Y}\;|\;\beta_i^\vt{y} \neq 0\}$.
\end{itemize}

Of these cases, \textsc{ProcessNew} and \textsc{ProcessOld} are both able to add new support vectors, which gives the learner the ability to perform sample selection during tracking and discover important background elements. This selection involves searching over ${\cal Y}$ to minimise $\nabla_i(\vt{y})$, which may be a relatively expensive operation. In practice, we found for the 2D translation case it was sufficient to sample from ${\cal Y}$ on a polar grid, rather than considering every pixel offset. The \textsc{Optimize} case only considers existing support vectors, so is a much less expensive operation.

%However, since during tracking we will only be evaluating \eqref{eqn:prediction-function} in a local region around the previous location, we restrict ${\cal Y}$ to also be a local region around $\vt{y}_i$. In the case of 2D translational tracking, we define ${\cal Y}$ to be the radial region ${\cal Y} = \{(u,v)\;|\;u^2+v^2<r^2\}$ (note that because $\vt{y}$ is the relative object location between frames, during an update we always have $\vt{y}_i = (0,0)$). Furthermore, in practice we found it unnecessary to sample every single pixel within this region, and instead sample within the region on a polar grid. The \textsc{Optimize} case only considers existing support vectors, so is a much less expensive operation.

As suggested by Bordes \etal \cite{Bordes2008}, we schedule these update steps as follows. A \textsc{Reprocess} step is defined as a single \textsc{ProcessOld} step followed by $n_O$ \textsc{Optimize} steps. Given a new training example $(\vt{x}_i, \vt{y}_i)$ we call a single \textsc{ProcessNew} step followed by $n_R$ \textsc{Reprocess} steps. In practice we typically use $n_O=n_R=10$.

During tracking, we maintain a set of support vectors ${\cal S}$. For each $(\vt{x}_i, \vt{y}) \in {\cal S}$ we store the coefficients $\beta_i^\vt{y}$ and gradients $\nabla_i(\vt{y})$, which are both incrementally updated during an SMO step. If the SMO step results in a $\beta_i^\vt{y}$ becoming 0, the corresponding support vector is removed from ${\cal S}$.

\section{Incorporating a budget}

An issue with the approach described thus far is that the number of support vectors is not bounded and in general will increase over time. Evaluating $g(\vt{x},\vt{y})$ requires evaluating scalar products (or kernel functions) between $(\vt{x},\vt{y})$ and each support vector, which means that both the computational and storage costs grow linearly with the number of support vectors. Additionally, since \eqref{eqn:struck_gradient} involves evaluating $g$, both the \textsc{ProcessNew} and \textsc{ProcessOld} update steps will become more expensive as the number of support vectors increases. This issue is particularly important in the case of tracking, as in principle we could be presented with an infinite number of training examples.

Recently a number of approaches have been proposed for online learning of classification SVMs on a fixed budget~\cite{Crammer2003,Wang2010}, meaning the number of support vectors cannot exceed a specified limit. If the budget is already full and a new support vector needs to be added, these approaches identify a suitable support vector to remove and potentially adjust the coefficients of the remaining support vectors to compensate for the removal.

We now propose an approach for incorporating a budget into the algorithm presented in Section \ref{sec:struck_structured_online}. Similar to Wang \etal \cite{Wang2010}, we choose to remove the support vector which results in the smallest change to the weight vector $\vt{w}$, as measured by $\|\Delta\vt{w}\|^2$. However, as with the SMO step used during optimisation, we must also ensure that the constraint $\sum_{\vt{y}}\beta_i^\vt{y} = 0$ remains satisfied. Because of the fact that there only exists one positive support vector for each support pattern, it is sufficient to only consider the removal of negative support vectors during budget maintenance. In the case that a support pattern has only two support vectors, then this will result in them both being removed. Removing the negative support vector $(\vt{x}_r, \vt{y})$ results in the weight vector changing according to

\begin{equation}
\bar{\vt{w}} = \vt{w} - \beta_r^\vt{y}\vg{\Phi}(\vt{x}_r, \vt{y}) + \beta_r^\vt{y}\vg{\Phi}(\vt{x}_r, \vt{y}_r),
\end{equation}

\noindent meaning

\begin{equation}
	\begin{split}
		\|\Delta\vt{w}\|^2 &= {\beta_r^\vt{y}}^2 \big\{
		\langle\vg{\Phi}(\vt{x}_r, \vt{y}), \vg{\Phi}(\vt{x}_r, \vt{y})\rangle\; + \\
		&\langle\vg{\Phi}(\vt{x}_r, \vt{y}_r), \vg{\Phi}(\vt{x}_r, \vt{y}_r)\rangle - 
		2\langle\vg{\Phi}(\vt{x}_r, \vt{y}), \vg{\Phi}(\vt{x}_r, \vt{y}_r)\rangle \big\}.
	\end{split}
\end{equation}

\noindent Each time the budget is exceeded we remove the support vector resulting in the minimum $\|\Delta\vt{w}\|^2$. We show in the experimental section that this does not impact significantly on tracking performance, even with modest budget sizes, and improves the efficiency. We name the proposed algorithm \emph{Struck} and show the overall tracking loop in Algorithm~\ref{alg:struck_tracking_loop}.  Our unoptimised C++ implementation of Struck is publicly available\footnote{\url{http://www.samhare.net/research}}.


% ------------------------------------------------------
\begin{algorithm}[H]
\begin{algorithmic}[1]
	\REQUIRE $\vt{f}_t$, $\vt{p}_{t-1}$, ${\cal S}_{t-1}$
	\STATE \emph{Estimate change in object location}
%	\STATE $\vt{x}_t = (\vt{f}_t, \vt{p}_{t-1})$
	\STATE $\vt{y}_t = \argmax_{\vt{y} \in {\cal Y}} \ g(\vt{x}_t^{\vt{p}_{t-1}}, \vt{y})$
	\STATE $\vt{p}_t = \vt{p}_{t-1} \circ \vt{y}_t$
	\STATE \emph{Update discriminant function}
%	\STATE $\vt{x}_t' = (\vt{f}_t, \vt{p}_t)$
	\STATE $(i, \vt{y}_+, \vt{y}_-) \leftarrow$ \textsc{ProcessNew}$(\vt{x}_t^{\vt{p}_{t}}, \vt{y}^0)$
	\STATE \textsc{SMOStep}$(i, \vt{y}_+, \vt{y}_-)$
	\STATE \textsc{BudgetMaintenance}$()$
	\FOR{$j=1$ to $n_R$}
		\STATE $(i, \vt{y}_+, \vt{y}_-) \leftarrow$ \textsc{ProcessOld}$()$
		\STATE \textsc{SMOStep}$(i, \vt{y}_+, \vt{y}_-)$
		\STATE \textsc{BudgetMaintenance}$()$
		\FOR{$k=1$ to $n_O$}
			\STATE $(i, \vt{y}_+, \vt{y}_-) \leftarrow$ \textsc{Optimize}$()$
			\STATE \textsc{SMOStep}$(i, \vt{y}_+, \vt{y}_-)$
		\ENDFOR
	\ENDFOR
	\RETURN $\vt{p}_t$, ${\cal S}_t$
\end{algorithmic}
\caption[Struck tracking loop]{Struck tracking loop.}
\addtocontents{loa}{\vskip -10pt} % hack to remove spacing in list of algorithms
\label{alg:struck_tracking_loop}
\end{algorithm}
% ------------------------------------------------------



\section{Kernel functions and image features}\label{sec:struck_svm_kernels}

The use of a structured output SVM framework provides great flexibility in how images are actually represented. In practice we choose to use a restriction kernel \cite{Blaschko2008} which uses the relative bounding box location $\vt{y}$ to crop a patch from a frame $\vt{x}_t^{\vt{p} \circ \vt{y}}$, allowing a standard image kernel to be applied between pairs of such patches
\begin{equation}
k_{xy}(\vt{x},\vt{y},\bar{\vt{x}},\bar{\vt{y}}) = k(\vt{x}^{\vt{p} \circ \vt{y}}, \bar{\vt{x}}^{\bar{\vt{p}} \circ \bar{\vt{y}}}).
\end{equation}
The use of kernels makes it straightforward to incorporate different image features into our approach, and in our experiments we consider a number of examples. We also investigate using multiple kernels in order to combine different image features together.

% mention that we don't want to include y in the kernel function as it's all relative to previous frame, so doesn't really make sense?

% note that gradient involves F so the opt will also be affected

%An issue with the approach described is that the number of support vectors is not bounded, meaning that the cost of storage and evaluation increases over time. Particularly bad for tracking as in principal we have an unlimited stream of examples. A similar problem is faced by binary SVMs, and recently there have been some approaches proposed for maintaining a fixed budget. We propose an approach for maintaining a budget inside the LaRank framework, resulting in a budgeted structured output SVM.

%Goal is to remove an SV in such a way that minimises change in w. Since we must ensure that sum beta_i = 0, we will have to modify pairs of svs. 

%\subsection{Kernel functions}

% During optimisation, if the SMO step results in a coefficient reaching 0 it will be removed from S. This allows the number of support vectors to shrink as well as grow. However, there is no limit to the number of support vectors.

% We propose to enforce a budget so that the number of SVs is bounded. Take similar approach to 

%Task of structured output SVM is to learn a function f:X->Y based on training samples of x,y pairs. To achieve this we introduce a discriminant function F:XxY->R which can be used for prediction by maximising over Y:
%
%f(x) = argmax_y F(x,y)
%
%We restrict F(x,y) to be of the form <w, phi(x,y)>, and learn w in a maximum margin framework by optimising the following objective function:
%
%blah
%
%Following approach of [Bordes], we convert this to its dual form by introducing a beta for each constraint. Tast is then to maximise:
%
%blah

