% !TEX root = ../../../thesis.tex
\chapter{Introduction}\label{sec:struck_intro}

% what is tracking, why do we want to do it? specifically mention video as opposed to still images

%Visual object tracking is one of the core problems of computer vision, and, with ever-increasing quantities of video data being generated, has wide-ranging applications including human-computer interaction, surveillance and augmented reality, to name just a few. For other areas of computer vision which aim to perform higher-level tasks such as scene understanding and action recognition, object tracking provides an essential component.

Visual object tracking is one of the core problems of computer vision, with wide-ranging applications including human-computer interaction, surveillance and augmented reality, to name just a few. For other areas of computer vision which aim to perform higher-level tasks such as scene understanding and action recognition, object tracking provides an essential component.

% tracking may be tuned for specific objects, or may be for generic objects. generic objects can be useful in their own right, but also can be important as components in other systems, e.g. scene understanding. furthermore, components required to allow tracking of generic objects are useful as they can be combined with non adaptive components. this has parallels with object detection, where it has been shown that it's useful to adapt to specific environment (face detection paper from cvpr11)

\begin{figure}[b!]
\centering
\begin{subfigure}[b]{0.32\textwidth}
\centering
\includegraphics[width=\textwidth]{images/sylva.png}
\includegraphics[width=\textwidth]{images/sylvb.png}
\caption{Object motion}
\end{subfigure}
\begin{subfigure}[b]{0.32\textwidth}
\centering
\includegraphics[width=\textwidth]{images/davida.png}
\includegraphics[width=\textwidth]{images/davidb.png}
\caption{Lighting}
\end{subfigure}
\begin{subfigure}[b]{0.32\textwidth}
\centering
\includegraphics[width=\textwidth]{images/tiger1a.png}
\includegraphics[width=\textwidth]{images/tiger1b.png}
\caption{Partial occlusion}
\end{subfigure}
\caption[Causes of target object appearance change]{Examples of different causes of appearance change of the target object. An adaptive tracking framework is needed in order to handle these appearance changes during tracking.}
\label{fig:struck_challenges}
\end{figure}

For some applications, the object to be tracked is known in advance and it is possible to incorporate prior knowledge when designing the tracker. There are other cases, however, where it is desirable to be able to track arbitrary objects, which may only be specified at runtime. In these scenarios, the tracker must be able to model the appearance of the object on-the-fly and adapt this model during tracking to take into account changes caused by object motion, lighting conditions, and occlusion (as illustrated in Figure \ref{fig:struck_challenges}). Even when prior information about the object is known, having a framework with the flexibility to adapt to appearance changes and incorporate new information during tracking is attractive, and in real-world scenarios is often essential for successful tracking.



\begin{figure}[tb]
  \begin{center}
	\includegraphics[width=0.85\linewidth]{images/tracking.pdf}
  \end{center}
  \caption[Different adaptive tracking-by-detection paradigms]{Different adaptive tracking-by-detection paradigms: given the current estimated object location, traditional approaches (shown on the right-hand side) generate a set of samples and, depending on the type of learner, produce training labels. Our approach (left-hand side) avoids these steps and operates directly on the tracking output.}
  \label{fig:struck_tracking_paradigms}
\end{figure}

%\begin{figure}[tbhp]
%\centering
%\begin{subfigure}{0.49\textwidth}
%\centering
%\includegraphics[width=\textwidth]{images/binary_tracking.pdf}
%\caption{Traditional}
%\end{subfigure}
%\begin{subfigure}{0.49\textwidth}
%\centering
%\includegraphics[width=\textwidth]{images/structured_tracking.pdf}
%\caption{Structured}
%\end{subfigure}
%  \caption{Different adaptive tracking-by-detection paradigms: given the current estimated object location, traditional approaches (shown on the right-hand side) generate a set of samples and, depending on the type of learner, produce training labels. Our approach (left-hand side) avoids these steps, and operates directly on the tracking output.}
%  \label{fig:struck_tracking_paradigms2}
%\end{figure}
%\begin{figure}[t]
%  \begin{center}
%	\includegraphics[width=0.95\linewidth]{images/tracking.png}
%  \end{center}
%  \caption{Different adaptive tracking-by-detection paradigms.}
%  \label{fig:tracking-paradigms}
%\end{figure}
 
%Recent work in object detection [cvpr11] has also demonstrated that adapting an object detector to the specific image in which it is being applied can help improve detection performance.

% online ML provides great framework for building adaptive classifiers -- can treat tracking like detection, which has come on in leaps and bounds recently

%Many approaches have been proposed for performing visual object tracking, and we do not attempt to summarise them all
%here \TODO{Some key references...}. 

An approach to tracking which has become particularly popular recently is tracking-by-detection~\cite{Avidan2004}, which treats the tracking problem as a detection task applied over time. This popularity is due in part to the great deal of progress made recently in object detection, with many of the ideas being directly transferable to tracking. Another key factor is the development of methods which allow the classifiers used by these approaches to be trained online, providing a natural mechanism for adaptive tracking\cite{Grabner2006,Babenko2011,Saffari2010a}.

Adaptive tracking-by-detection approaches maintain a classifier trained online to distinguish the target object from its surrounding background. During tracking, this classifier is used to estimate object location by searching for the maximum classification score in a local region around the estimate from the previous frame, typically using a sliding-window approach. Given the estimated object location, traditional algorithms generate a set of binary labelled training samples with which to update the classifier online. As such, these algorithms separate the adaptation phase of the tracker into two distinct parts:\ (i) the generation and labelling of samples; and (ii) the updating of the classifier. 

While widely used, this separation raises a number of issues. Firstly, it is necessary to design a strategy for generating and labelling samples, and it is not clear how this should be done in a principled manner. The usual approaches rely on predefined rules such as the distance of a sample from the estimated object location to decide whether a sample should be labelled positive or negative. Secondly, the objective for the classifier is to predict the binary label of a sample correctly, while the objective for the tracker is to estimate object location accurately. Because these two objectives are not explicitly coupled during learning, the assumption that the maximum classifier confidence corresponds to the best estimate of object location may not hold (a similar point was raised by Williams \etal\ \cite{Williams2003}). State-of-the-art adaptive tracking-by-detection methods mainly focus on improving tracking performance by increasing the robustness of the classifier to poorly labelled samples resulting from this approach. Examples of this include using robust loss functions~\cite{Leistner2009,Masnadi-shirazi2010}, semi-supervised learning~\cite{Grabner2008,Saffari2010}, or multiple-instance learning~\cite{Babenko2011,Zeisl2010}.

%These shortcomings result in degraded tracking performance caused by disconnected objectives of sample generation/labelling, tracking, and learning processes. Indeed, the current adaptive tracking-by-detection systems are composed of many individual components by sometimes conflicting or unrelated goals. The state-of-the-art tracking-by-detection methods mainly focus on increasing the robustness of the classifiers to the remedy these problems, either by using robust loss functions~\TODO{Citations}, semi-supervised learning~\TODO{Citations}, or multiple-instance learning~\TODO{Citations} algorithms.

%% Tracking-by-detection approaches maintain a classifier trained to distinguish the target object from its surrounding
%% background. During tracking, this classifier is used to estimate object location by searching for the maximum
%% classification score in a local region around the estimate from the previous frame. For an adaptive tracker, this new
%% location is then used to generate training examples with which the classifier is updated. While widely used, this
%% approach suffers from at least two drawbacks. Firstly, the objective when training the classifier is not directly linked
%% to the tracking objective, and the assumption that the maximum classifier confidence corresponds to the best estimate of
%% object location is not explicitly incorporated into the learning algorithm. Secondly, in order to update the classifier
%% it is necessary to decide how samples should be generated and labelled, and it is not clear how this should be done in a
%% principled manner.


In this chapter we take a different approach and frame the overall tracking problem as one of structured output
prediction, in which the task is to directly predict the change in object location between frames. We present a novel
and principled adaptive tracking-by-detection framework which integrates the learning and tracking, avoiding the need
for ad-hoc update strategies (see Figure~\ref{fig:struck_tracking_paradigms}).

%does not treat the learning part separate from the tracking and sample generation parts. Our approach can handle 


%Such an approach is more appropriate for tracking, since we are ultimately interested in optimising tracking, rather than classification, performance. In other words, our target is to define a novel and principled tracking-by-detection framework which does not treat the learning part separate from the tracking and sample generation parts. A similar argument was made in [Williams], in which the authors apply a relevance vector machine to learn a regression between image patches and tracker motion. The tracker developed in [Williams] is forced to treat each dimension of the output space independently, and is non-adaptive, being trained only from the first frame of a tracking sequence. 

%he approach we present here can handle dependencies in the output space, and is also able to learn online, allowing for adaptive tracking. As well as explicitly optimising tracking performance, our approach avoids the need for ad-hoc updating strategies, since it does not introduce an intermediate classification step.

%In order to achieve our goal, we need an online learner which is able to operate in structured output spaces. 

Most recent tracking by detection approaches have used variants of online boosting-based classifiers~\cite{Grabner2006,Babenko2011,Saffari2010a}. In object detection, boosting has proved to be very successful for particular tasks, most notably face detection using the approach of Viola and Jones \cite{Viola2004}. Elements of this approach, in particular the Haar-like feature representation, have become almost standard in tracking-by-detection research. The most successful research in object detection, however, has tended to make use of SVMs rather than boosting, due to their good generalisation ability, robustness to label noise, and flexibility in object representation through the use of kernels~\cite{Blaschko2008,Vedaldi2009,Felzenszwalb2010}. Because of this flexibility of SVMs and their natural generalisation to structured output spaces, we make use of the structured output SVM framework of Tsochantaridis \etal \cite{Tsochantaridis2005}. In particular, we extend the online structured output SVM learning method proposed by Bordes \etal \cite{Bordes2007,Bordes2008} and adapt it to the task of adaptive object tracking. 
%As an added bonus, this approach enables us to bring the benefits of an SVM framework to tracking domain. 
We find experimentally that the use of our framework results in large performance gains over state-of-the-art tracking by detection approaches. 

%Our use of structured output learning has simil

A structured output SVM framework has previously been applied to the task of object detection by Blaschko and Lampert \cite{Blaschko2008}. In contrast to their work, in our setting there is no offline labelled data available for training (except the first frame which is assumed to be annotated) and instead online learning is used. However, online learning with kernels suffers from the \emph{curse of kernelisation}, whereby the number of support vectors increases with the amount of training data. Therefore, in order to allow for real-time operation, there is a need to control the number of support vectors. Recently, approaches have been proposed for online learning of classification SVMs on a fixed budget \cite{Crammer2003,Wang2010}, meaning that the number of support vectors is constrained to remain within a specified limit. We apply similar ideas in this chapter and introduce a novel approach for budgeting which is suitable for use in an online structured output SVM framework. We find empirically that the introduction of a budget brings large gains in terms of computational efficiency, without impacting significantly on the tracking performance of our system.

%When applying kernels, the discriminant function of a structured output SVM, like a binary SVM, is expressed as a linear combination of kernel evaluations between an input sample and a set of support vectors. The cost of evaluating the discriminant function in terms of both computation and storage is therefore determined by the number of support vectors. While the support vectors are designed to be a sparse subset of the training examples, in general their number will grow without bound as the size of the training set increases. In an online setting, where training samples arrive in a continuous stream over time, this means that the cost of prediction will increase over time, which is an undesirable property. Recently, approaches have been proposed for learning binary SVMs on a budget, meaning that the number of support vectors is constrained to remain within a specified limit [Refs]. We apply a similar approach in this work, and introduce a budgeting strategy for online structured output SVMs which does not impact significantly on the performance of the tracking algorithm.



% While classification to separate an object from its local background is one way of treating the problem, it not necessarily the most appropriate, and regression is what we really want to do. This point has been made before [Williams], when tracking by detection was first gaining popularity before online adaptation.

% Another artifact of transferring object detection to tracking is that we've ended up using boosting+haars predominantly. In detection, most successful approaches are built around SVMs, as they have good generalisation ability, are robust to noise, and are extremely flexible because of the use of kernels

% we propose an approach which makes use of a recent ML developement to allow the problem to be posed as discriminative regression, and is based around SVMs, so enjoys all their advantages. Suffers from growth of SVs, so we introduce a budgeting mechanism


%---

% most people use classification for tracking, and furthermore most have gone down one particular route -- boosting, based on viola-jones. we use a framework which is more appropriate for tracking, and do it in an svm framework, which has become very popular for detection due to its power and flexibility. we bring this power/flexibility to tracking.

% we come up against issue of performance with svms. this has been tackled one way in detection to make use of kernel approximation, but an alternative way of tacking is using budgeting. we show that this fits naturally into our framework, and we propose a budgeting mechanism which allows us more freedom with kernel choice.


% ---- OLD

%A popular approach to visual tracking is tracking by detection, in which a classifier is used for estimating the motion of a target object. This classifier can be pre-trained for a given object and used only for evaluation during tracking [Avidan], but recent research has centred around the idea of also updating the classifier during tracking, to enable adaptive tracking of generic objects under varying environmental conditions [Grabner, Babenko, Saffari, etc]. This has become possible because of a great deal of recent research into online machine learning algorithms, which are designed to incrementally update a learner given a stream of training data.

%Most tracking by detection algorithms frame the problem as one of binary classification, in which the task is to distinguish the object of interest from its surrounding background. To perform tracking, the classifier is applied in a local region around the previously estimated object location in order to build a confidence map. The highest peak of this confidence map is then taken to be the new object location. Although this approach is widely used and has been shown to produce good results, it suffers from at least two drawbacks. Firstly, in order to update the classifier it is necessary to decide how samples should be labelled. This could be based on a bounding box overlap criterion, for example, by labelling samples which have high overlap with the true bounding box as positive, and those which have low overlap as negative, but in any case it requires a somewhat arbitrary scheme to be introduced. Secondly, the objective when learning the binary classifier is not directly linked to the tracking objective, and the assumption that the highest peak in the confidence map corresponds to the best estimate of object location is not explicitly incorporated into the learning algorithm.

%In this paper we take a different approach and frame the problem as one of structured output regression, in which the task is to directly predict the relative change in object location between frames. To learn such a predictor we make use of the structured output Support Vector Machine (SVM) framework proposed in [Tsochantaridis], and in particular the extensions to online learning proposed in [Bordes]. As well as addressing the problems which have already been mentioned, this approach brings the additional benefit of allowing us to use non-linear kernels in order to learn powerful prediction functions.

% decision or discriminant function??

%When applying kernels, the discriminant function of a structured output SVM, like a binary SVM, is expressed as a linear combination of kernel evaluations between an input sample and a set of support vectors. The cost of evaluating the discriminant function in terms of both computation and storage is therefore determined by the number of support vectors. While the support vectors are designed to be a sparse subset of the training examples, in general their number will grow without bound as the size of the training set increases. In an online setting, where training samples arrive in a continuous stream over time, this means that the cost of prediction will increase over time, which is an undesirable property. Recently, approaches have been proposed for learning binary SVMs on a budget, meaning that the number of support vectors is constrained to remain within a specified limit [Refs]. We apply a similar approach in this work, and introduce a budgeting strategy for online structured output SVMs which does not impact significantly on the performance of the tracking algorithm.




%\begin{itemize}
%\item \TODO{Generic overview of the state-of-the-art tracking by detection}
%\item \TODO{Most of these methods are based on online boosting or random forests and the power of kernel SVMs has not been used}
%\item \TODO{State why it is not trivial to use vanilla SVMs for tracking: memory issues, efficiency and real-time issues}
%\item \TODO{An overview of previous SVM based trackers: they are mostly linear and not efficient etc}
%\item \TODO{An overview of our method and what are the contributions etc.}
%\end{itemize}



% NOTES

% should cite ollie williams and avidan, who both use svms, and indeed williams uses regression rather then classification. however, a) this is a generative model (i think) and b) is trained only once at the start of tracking, not online c) estimates each output coord independently

