\part{Background and Related Work}
\label{chp:background}

%\input{chapters/background/sections/tracking.tex}

%\input{chapters/background/sections/keypoints.tex}

%\input{chapters/background/sections/reconstruction.tex}

%\input{chapters/background/sections/svm.tex}

%\TODO{Add images to this chapter}

In this chapter we provide an overview of the background material relevant to the work in this thesis. The first three sections focus on the computer vision application areas tackled in Chapters \ref{chp:struck}-\ref{chp:reconstructor}, while the fourth section focuses on structured learning, which features at the core of all the approaches developed in this thesis.

%\pawanchapter{Application areas}

%This section provides a review of relevant existing approaches which have been developed for the application areas tackled in this thesis. 

\chapter{Object tracking}

Object tracking aims to estimate the motion of a target object between successive frames of a video sequence. This is a fundamental problem in computer vision, and a great deal of prior research exists in the area. The interested reader is directed to \cite{Cannons2008} for a thorough survey of the field, while this section summarises those approaches which are most relevant to the work in this thesis.

\begin{figure}[b]
\centering
\includegraphics[width=0.2\textwidth]{images/tracking/sylva.png}\includegraphics[width=0.2\textwidth]{images/tracking/sylvb.png}\includegraphics[width=0.2\textwidth]{images/tracking/sylvc.png}\includegraphics[width=0.2\textwidth]{images/tracking/sylve.png}\includegraphics[width=0.2\textwidth]{images/tracking/sylvf.png}
\caption[An example object tracking task]{An example object tracking task using a bounding box representation. Notice the target object undergoes significant appearance changes, which must be handled by the tracking approach.}
\label{fig:tracking_overview}
\end{figure}

All tracking algorithms require some kind of \emph{representation} of the target object. Possible choices for this include points \cite{Lucas1981,Shi1994}, bounding box, contour \cite{Isard1998,Bibby2008} and articulated structures \cite{Ramanan2007,Buehler2008}. 
% should these be expanded upon here?
The choice of representation in turn determines the \emph{state} of the tracker, which is what must be estimated in each video frame. For the work presented in Chapter~\ref{chp:struck} of this thesis, we consider only a bounding box representation (Figure \ref{fig:tracking_overview}). The advantage of such a representation is that the state is simple, consisting only of 2D translation and possibly rotation and scale. However, in the physical world we expect the target object to undergo deformations, out-of-plane motion and be affected by partial occlusions and lighting changes, none of which are handled explicitly by this representation. Consequently, these factors must be handled by an \emph{appearance model}, which should encode the variability in the object as it appears within the bounding box.



The appearance model is the primary differentiator between approaches which make use of a bounding box representation and can broadly be divided into two categories: generative and discriminative.
%%%
%%%In order to perform object tracking, an object representation must be decided upon. Many possible representations: points, contours, bounding boxes.
%%%
%%%
%%%
%%%
%%%
%%%In the case of a bounding box representation this state includes 2D translation, and possibly rotation and scale. To perform the estimation of this state, a variety of approaches are available.
%%%
%%%
%%%For the work in this thesis, we use bounding boxes. Given this choice, the core differentiator between different approaches is the way in which they model the appearance of the object. This choice particularly important given the constrained nature of bounding boxes. In the physical world we expect the object to undergo complex out-of-plane motion, suffer occlusion, changing lighting conditions etc. Since the representation does not explicitly handle any of these factors, it becomes the job of the appearance model to be able to deal with them.
%%%
%%%% brute force. pros: simple. can handle multi-modal cost functions, cons: slow
%%%% gradient based: pros: efficient, cons: not good when cost function isn't smooth (so need e.g. coarse-to-fine strategy)
%%%% mean shift: 
%%%% particle filtering: elements of both: uses multiple samples to effectively avoid problems of failure
%%%
%%%We now focus on some of the different approaches which are taken for modelling the appearance of the target object given a bounding box representation. These can be divided into generative and discriminative approaches.


\section{Generative appearance models}

Generative approaches involve some kind of model which is able to capture the way the target object appears inside the bounding box during tracking.

The simplest approach for modelling the appearance of target object is with a single template image, for example the image inside the bounding box at the start of tracking. Tracking can then be performed by registering this template image with each subsequent video frame by maximising a similarity function, based on \eg\ sum of squared differences (SSD) or normalised cross-correlation (NCC). To perform this maximisation, one approach is to use exhaustive local search around the previous tracker state. Although this is very straightforward, it is also computationally expensive. A more efficient approach is to assume that the similarity function is locally smooth and perform gradient-based optimisation \cite{Lucas1981,Benhimane2004,Baker2004}. This smoothness assumption may only be valid in a very local area, so in order to handle greater motion between frames, coarse-to-fine optimisation on an image pyramid can be used \cite{Bouguet1999}.

Tracking with a single template image suffers from robustness issues in practice, since it is does not provide sufficient tolerance to the changes in appearance which are expected during tracking. Various extensions to this approach have been proposed in order to improve robustness by incorporating illumination invariance \cite{Hager1998}, robustness to partial occlusion \cite{Jepson2003}, and multiple appearance modalities \cite{Black1998}.

\begin{figure}[tbh]
\centering
\includegraphics[width=\textwidth]{images/tracking/esm.pdf}
\caption[Template-based tracking]{Template-based tracking using the ESM method \cite{Benhimane2004}. This approach is able to track under a large class of transformations, in this case perspective homography. Image courtesy of S. Benhimane \cite{Benhimane2004}.}
\label{fig:tracking_esm}
\end{figure}

A strength of template based approaches is that they are able to provide very accurate estimates of object state (Figure \ref{fig:tracking_esm}), and the mathematics they are based on makes it straightforward to extend the classes of transformations which are supported. But because of the way in which they model an object in terms of individual pixels which must be aligned exactly with pixels in a new frame, they have little tolerance to spatial misalignment and as a result can be rather fragile.

An alternative approach for modelling object appearance is to treat it as a probability distribution in some feature space, most commonly colour \cite{Comaniciu2003}. Tracking is then performed using the mean-shift \cite{Fukunaga1975} mode seeking algorithm to iteratively maximise the similarity between the model distribution and the current tracker distribution. The strength of this approach is that it is far more tolerant to slight changes in object appearance, since it is essentially tracking a blob of colour (Figure \ref{fig:tracking_mean_shift}). The associated weakness, however, is that discarding all spatial information reduces the discriminative power of the appearance model, meaning the tracker provides less accurate estimates of object state and may become confused by background regions with a similar colour distribution. Another issue with this approach is that it is less straightforward to extend tracking to include parameters such as scale and rotation, which are simple to include in a template tracking framework.

\begin{figure}[tbh]
\centering
\includegraphics[width=0.9\textwidth]{images/tracking/meanshift.pdf}
\caption[Mean-shift tracking]{Mean-shift tracking using a colour distribution \cite{Comaniciu2003}. This approach is able to track under significant appearance change, since the colour distribution remains roughly the same. Image courtesy of D. Comaniciu \cite{Comaniciu2003}.}
\label{fig:tracking_mean_shift}
\end{figure}


These issues have been addressed by various authors, and in particular the approach of Elgammal \etal \cite{Elgammal2003} along with the related approach of Yang \etal \cite{Yang2005} reintroduce spatial information into the mean-shift framework and perform tracking in so-called joint feature-spatial spaces. Another related approach for introducing spatial information into a histogram-based object model is that of Adam \etal \cite{Adam2006}, which divides the target object into multiple sub-regions, with tracking performed by robustly combining the results of tracking individual sub-regions.

\subsection{Incorporating adaptability}

The approaches described so far do not incorporate any notion of adaptability of the appearance model, as the template image or histogram remains fixed during tracking. Such adaptability is often essential in practice to handle changes in object appearance caused by object deformation and changing environmental conditions. One simple strategy for adapting the appearance model is to replace it each frame, discarding the previous model. This approach is very aggressive, however, as it does not maintain any history about the appearance of the object in previous frames. As a result, it is prone to \emph{drift}, since small tracking errors will accumulate over time and ultimately result in tracking failure. One approach for dealing with this was proposed by Mattews \etal \cite{Matthews2004}, which updates the template only when it is considered safe to do so and retains the original template to prevent drift (Figure \ref{fig:tracking_matthews}). Other approaches maintain more sophisticated appearance models which summarise the appearance of the object over time and adapt gradually to changes, such as the incremental PCA approach of Ross \etal \cite{Ross2007} and the WSL tracker of Jepson \etal. \cite{Jepson2003}.

\begin{figure}[tbh]
\centering
\includegraphics[width=\textwidth]{images/tracking/matthews.pdf}
\caption[The template update problem]{The template update problem. In the first row a fixed template is used, and tracking is lost as the target object changes appearance due to lighting. In the second row the template is updated every frame, which also results in tracking failure because the template drifts. The final row uses an approach which combines both fixed and updating templates to result in successful tracking. Image courtesy of I. Matthews \cite{Matthews2004}.}
\label{fig:tracking_matthews}
\end{figure}

% [Mattews], WSL [Jepson], incremental PCA [Ross]



% pros and cons of template tracking, 

% to handle lighting changes and appearance changes we have hager and pca

% histograms and mean shift, discard spatial information. jfsk to combine elements of both

% fragtrack

% not adaptive. describe some methods for making adaptive e.g. replacing template, 


%Simplest approach is template matching, whereby an image is used as the appearance model, and image registration used between frames. To estimate the state of the tracker we can use brute force SSD matching, or gradient-based approaches such as Lucas Kanade. Problem is that the object model is very rigid, and is not able to handle appearance changes caused by e.g. lighting changes, out of plane rotation or occlusion. Extensions have been proposed to deal with these such as Hager and PCA.

%Alternative approach goes to other extreme and discards all spatial information about the object, choosing only to model as a histogram. Exhaustive search avoided by using mean-shift on a back-projection image. The advantage is that the appearance model is more tolerant to changes in object appearance since it has discarded spatial information. However this can also mean it is not sufficiently discriminative. Approaches such as JFSK tracker attempt to find a middle ground between mean-shift and template tracking.

% providing adaptivity: replace template each frame, but this is highly adaptive and suffers from drift.


% naive: brute force
% gradient-based: lukas kanade
% mean-shift: comaniciu

\section{Discriminative appearance models}

More recent tracking research has focused around appearance models which are discriminative, meaning that rather than capturing the appearance of the target object alone, they model the differences between the appearance of the target object and its surrounding background. Such approaches have benefited greatly from the significant progress which has been made in the related task of category-level object detection \cite{Viola2004,Dalal2005,Felzenszwalb2010,Vedaldi2009}.

An early approach for discriminative object tracking was proposed by Avidan \cite{Avidan2004}, which used the classification function of an SVM as the similarity function which should be optimised by a gradient-based tracker. The classifier itself was learned offline, meaning a training set of representative examples of object and background was required in advance of tracking, but this approach established the now-common technique of incorporating discriminative classifiers into a tracking framework.

\subsection{Incorporating adaptability}

Since discriminative approaches incorporate information about the target object and its background, providing a mechanism for adaptability becomes particularly important. While object detection research has shown that it is possible to use large training sets containing `typical' background examples to train object detectors, during tracking we will only be discriminating between the object and a particular background. It is therefore desirable to use an appearance model which is specific to this background. Since most discriminative appearance models are based around classifiers, online learning provides a natural mechanism for achieving this, providing the tracker with the ability to adapt both to changes in the object appearance, as well as changes in the surrounding background. After initialising the classifier at the start of tracking (\eg\ with a user-specified bounding box, or the output from an object detector), approaches designed in this way operate in two stages. First the existing classifier is used to update the state of the tracker, and then the new state of the tracker is used in order to update the classifier (Figure \ref{fig:tracking_grabner}). 

\begin{figure}[tbh]
\centering
\includegraphics[width=\textwidth]{images/tracking/grabner.png}
\caption[Online learning for tracking]{Online learning for tracking. The classifier confidence function is used to update the state of the tracker, after which the classifier is updated by generating training samples from the new tracker state. Image courtesy of H. Grabner \cite{Grabner2006}.}
\label{fig:tracking_grabner}
\end{figure}

An influential approach based on these ideas was the Online Boosting method proposed by Grabner \etal \cite{Grabner2006}. In this method, a boosting-based \cite{Schapire1990} classifier similar to that proposed for object detection by Viola and Jones \cite{Viola2004} is learned online \cite{Oza2005}. To update the classifier each frame, a set of labelled training examples is generated using the current tracker state. The image patch inside the current tracker bounding box is treated as a positive training example, while image patches inside a number of randomly-selected bounding boxes from the local area (some of which overlap with the tracker bounding box) are treated as negative examples. The boosting-based classifier is able to select from a large pool of image features to best discriminate between the positive and negative examples.

This approach results in a powerful tracking framework, which under the right conditions is able to track arbitrary objects in complex backgrounds, whilst handling the various changes in appearance which cause problems for most tracking approaches. It still suffers from a number of drawbacks, however, which subsequent research has attempted to address.

The first problem is that of label noise. Because the tracker state will inevitably contain some errors, the training examples given to the classifier may not be labelled correctly. If the classifier cannot handle this noise, its ability to discriminate between the target object and its background will suffer, causing tracking quality to decline. Boosting is known to suffer from label noise \cite{Dietterich2000}, since it can overfit to samples which are not well predicted by the current classifier, so one approach is to make use of robust loss functions for boosting to provide more tolerance to label noise \cite{Leistner2009,Masnadi-shirazi2010}. Alternatively, different classifiers such as random forests \cite{Breiman2001,Saffari2009} which have better robustness to label noise may be employed. A particularly successful approach for handling labelling noise was proposed by Babenko \etal \cite{Babenko2011}, who make use of Multiple Instance Learning (MIL) \cite{Dietterich1997} to allow the classifier to select from a number of potential positive examples, according to its current state (Figure \ref{fig:tracking_miltrack}). This method was shown to provide significant improvements over the original Online Boosting tracker.

\begin{figure}[tbh]
\centering
\includegraphics[width=0.7\textwidth]{images/tracking/miltrack.png}
\caption[Multiple instance learning for handling label noise]{Multiple instance learning for handling label noise. The first column updates the classifier using a single positive and multiple negative examples, which may result in drift as the positive example is mis-aligned. The second column updates the classifier using multiple positive and negative examples, which may also result in drift as it is harder for the classifier to discriminate between the two classes. The final column uses multiple instance learning to allow the classifier to select for itself which example should be treated as positive based on its current state. Image courtesy of B. Babenko \cite{Babenko2011}.}
\label{fig:tracking_miltrack}
\end{figure}

The second problem is the reliance of classification-based approaches on self-training, whereby the result of the tracker is always assumed to be correct and then used to update the classifier. Fundamentally, this is a problem with all adaptive tracking methods, since the only true supervision comes from the first frame of tracking (\ie\ when the tracker is initialised). Given the framework of adaptive tracking using a discriminative classifier, however, a number of approaches have been proposed to try and mitigate the danger of self-training. One such approach was proposed by Grabner \etal \cite{Grabner2008}, which makes use of semi-supervised learning and treats all examples after the initial frame as unlabelled. This approach retains a classifier learned from the initial frame, which is used to anchor future updates during tracking so that significant drift cannot take place. In practice, however, this approach can suffer from a lack of adaptability to appearance change, which can also lead to poor tracking performance.

%todo: move this to conclusion?
Fundamentally, there is a dilemma which must be faced when performing adaptive object tracking. On one hand, allowing too much adaptation of the appearance model can lead to drift and ultimately tracking failure. On the other hand, if the adaptation is constrained in order to prevent drift, the appearance model may not be able to handle the changes in object appearance, which will also lead to tracking failure. Recently, attempts have been made to resolve this dilemma by incorporating higher-level reasoning about the scene into the tracking framework \cite{Saffari2010a,Kalal2011}, which appears to be a promising research direction.


\chapter{Keypoint-based object detection}

Keypoint-based object detection is a widely-used approach for detecting instances of a specific textured target object in an image. Its robustness and efficiency mean that it forms the cornerstone of many computer vision applications such as augmented reality (AR) and simultaneous localisation and mapping (SLAM).

\begin{figure}[b!]
\centering
\includegraphics[width=0.8\textwidth]{images/keypoints/keypoint_detect.png}
\caption[Keypoint-based object detection]{Keypoint-based object detection. A planar target object is shown on the left, and potential matches are found between object and image keypoints (brighter lines indicate higher matching scores). Geometric verification is then used to determine the homography transformation between object and image.}
\label{fig:keypoints_overview}
\end{figure}

The target object is modelled as a collection of distinctive \emph{keypoints}, each consisting of location and local appearance information. These keypoints are designed to be easy to identify when the object is observed in a given image. Detecting the object in an input image then follows a standard pipeline consisting of three stages: detecting keypoints in an input image; finding potential matches between image keypoints and model keypoints; and geometric verification of matches to determine overall object presence and geometric transformation (Figure \ref{fig:keypoints_overview}).



% todo: this needs to be improved
The strengths of these approaches are twofold: firstly, they are able to detect an object under a large class of geometric and photometric transformations. This is possible because individual keypoints describe only local information about an object, allowing methods to be designed which are locally tolerant to such transformations. Secondly, they incorporate a great deal of redundancy, since geometric verification provides a very strong cue for object detection. This means that detection requires only a subset of keypoints to be successfully matched, making these methods robust against partial occlusions and matching failures.

There exists a great deal of prior research related to each of the stages of the detection pipeline. In this section we provide a brief overview of some of the key literature.


%The technique of extracting and matching keypoints was first introduced in [Shmidt] for the related task of matching an unknown image to a database of images, and has since been the focus of a great deal of research in the computer vision community.


\section{Keypoint detection}

In order to identify keypoints in an image, a detector is required. The aim is for a detector to have high \emph{repeatability}, meaning it can reliably detect the same keypoint even as an image undergoes various geometric and photometric transformations. To achieve this repeatability, the detector is designed with invariances to certain transformations. In theory, if the local image data around the keypoint is transformed in a way which is handled by the detector, it will still be detected. In practice there are inevitably artefacts introduced by the imaging process such as aliasing and noise which can violate the assumptions made by the detector, but this is compensated by the redundancy which comes from modelling the object as a collection of such keypoints.

An early example of a keypoint detector was proposed by Harris \cite{Harris1988}, which uses the eigenvalues of a $2 \times 2$ matrix built from local image gradient information around each pixel in an image to identify stable \emph{corners}. A related extension was proposed by Shi and Tomasi \cite{Shi1994}, which under certain assumptions results in more stable corners. These detectors are able to provide invariance to translation and rotation of the image.
% figures
% mention the reason why corners are good? i.e. not ambiguous like textureless regions or edges

% further extensions to handle scale: harris-laplace, DoG, SURF

To provide additional invariance to scaling of the image, a number of subsequent approaches have been proposed which make use of image \emph{scale-space} \cite{Lindeberg1994}. This image representation adds a third dimension corresponding to the scale of a Gaussian kernel with which the image is convolved. \emph{Blobs} can then be identified in scale-space by searching for extrema of the Laplacian of Gaussian (LoG) \cite{Lindeberg1998} or Difference of Gaussian (DoG) \cite{Lowe2004} operators. In particular, the DoG detector was introduced to accompany the well-known Scale-Invariant Feature Transform (SIFT) \cite{Lowe2004} descriptor and so is widely used in practice. A similar approach for blob detection uses the Determinant of Hessian (DoH) \cite{Lindeberg1998} operator, and a fast approximation of this method is used as the detector for the widely-used Speeded Up Robust Feature (SURF) \cite{Bay2008} descriptor.

% further extensions to handle affine: ... {tuytelaars2000,mikolajczyk2004,matas2002}.

Detectors have also been proposed to handle general affine (translation, rotation, scaling and shearing) transformations of the image. Some of these are based on affine extensions to scale-space approaches \cite{Tuytelaars2000,Mikolajczyk2004}, while others identify different image features which are stable under affine transformations, such as Maximally Stable Extremal Regions (MSERs) \cite{Matas2002}.

% while providing as much invariance as possible is important, an equally important consideration in practice is speed. consequently, one of the most commonly-used detectors in practice is FAST. this only provides the same degree of invariance as Harris, but is very fast to compute. further extensions have been proposed to extend FAST to multi-scale [BRISK]

\begin{figure}[tb]
\centering
\begin{subfigure}[b]{0.32\textwidth}
\centering
\includegraphics[width=\textwidth]{images/keypoints/bryce.jpg}
\caption{Input image}
\end{subfigure}
\begin{subfigure}[b]{0.32\textwidth}
\centering
\includegraphics[width=\textwidth]{images/keypoints/bryce_sift.png}
\caption{DoG keypoints}
\end{subfigure}
\begin{subfigure}[b]{0.32\textwidth}
\centering
\includegraphics[width=\textwidth]{images/keypoints/bryce_fast.png}
\caption{FAST keypoints}
\end{subfigure}
\caption[Examples of DoG and FAST keypoints]{Examples of DoG \cite{Lowe2004} and FAST \cite{Rosten2006} keypoints. The DoG detector identifies multi-scale blobs, while the FAST detector identifies single-scale corners.}
\label{fig:keypoints_examples}
\end{figure}

Whilst the development of keypoint detectors with invariance to a large class of transformations is important, in practice an equally important consideration is computational cost, especially where we are interested in real-time applications. Consequently, one of the most commonly-used keypoint detectors in practice is the Features from Accelerated Segment Test (FAST) detector \cite{Rosten2006}. This approach aims to detect only single-scale corners, but focuses on doing so very efficiently. Corners are identified by scanning a ring of 16 pixels around a central pixel and checking whether a run of $n$ consecutive pixels (with $n=9$ most commonly used) which are brighter or darker than the central pixel exists. Furthermore, the ordering of tests is learned from training data to reject non-corner pixels as quickly as possible. Although this approach only offers invariance to rotation and translation, the fact that it is extremely fast, even on low-powered devices, means it is frequently used. Leutenegger \etal\ \cite{Leutenegger2011} propose an extension to FAST which also provides invariance to image scaling.

%provides invariance to translation and rotation of the image. Subsequent research has developed detectors which also provide invariance to image scaling \cite{lowe2004}, and to all affine transformations (translation, rotation, scaling and shearing) \cite{tuytelaars2000,mikolajczyk2004,matas2002}.

%This low-level process of keypoint detection provides an alternative representation for an image, so that rather than being a 2D grid of pixels, it is instead a collection of sparse keypoints, each of which corresponds to an `interesting' image feature. The motivation is that this procedure highlights the important information in an image, ready to be interpreted for higher-level tasks such as object detection.

% detectors: Harris, SIFT, SURF, MSER
% low-power: FAST, agast, BRISK

\section{Keypoint matching}

Once keypoints have been identified, the next stage in the object detection pipeline is to use local appearance information in order to match keypoints in an image against keypoints on the target object. Methods for achieving this can be divided into two categories: those based on descriptors and those based on classification.

\subsection{Matching with descriptors}

The traditional approach to matching has been to produce a \emph{descriptor} for each keypoint, a signature based on local image information. Ideally these descriptors should be invariant to the same class of transformations as the detector, and the usual approach is to use statistics based on the image data around a keypoint to define a local coordinate frame in which to compute the descriptor. Given a descriptor type, matching then becomes a nearest-neighbour problem. For each keypoint in an image, the nearest-neighbour object keypoint is found using some distance metric (usually Euclidean). If this distance is sufficiently small, it is considered a candidate match. Additional heuristics are also employed in practice, such as rejecting matches which are not sufficiently unique, as defined by the ratio of distances between the nearest and second-nearest match \cite{Lowe2004}.

Schmid and Mohr \cite{Schmid1997} introduced the concept of image descriptors by building Local Jets, vectors of local image derivative information, around image keypoints. Since then, many other descriptors have been proposed, by far the most well-known of which is the SIFT descriptor \cite{Lowe2004}. This descriptor is constructed from histograms of oriented gradient information collected from a 4x4 grid around each keypoint, along with normalisation to increase robustness to illumination changes (Figure \ref{fig:keypoints_sift}). This carefully-designed descriptor and its associated DoG detector have become the gold standard in terms of performance for keypoint matching against which all other approaches are compared.


\begin{figure}[tbh]
\centering
\includegraphics[width=0.7\textwidth]{images/keypoints/sift.pdf}
\caption[The SIFT descriptor]{The SIFT descriptor. Local image gradients weighted by a Gaussian kernel around DoG keypoints are collected into a spatial histogram to produce the descriptor. This example shows 2x2 histograms, while the actual descriptor uses 4x4 histograms. Image courtesy of D. Lowe \cite{Lowe2004}}
\label{fig:keypoints_sift}
\end{figure}

An issue with the SIFT descriptor is its computational cost. Construction of the descriptor involves relatively expensive image operations such as convolutions with Gaussian kernels and the resulting descriptor is a 128-dimensional real vector, making nearest-neighbour search expensive. Various approaches have been proposed for addressing these issues. The SURF descriptor \cite{Bay2008} was designed to match the performance of SIFT, whilst replacing various stages in the pipeline with more efficient alternatives making use of integral images \cite{Viola2004} and the resulting descriptor is only 64-dimensional. This approach has been shown to be suitable for real-time application on desktop computers, although it is still too expensive for low-powered devices. Approaches for accelerating the nearest-neighbour search include reducing the dimensionality of the descriptor through the use of principal component analysis (PCA) \cite{Ke2004} or vector quantisation \cite{Sivic2003,Tuytelaars2007} and approximate search methods based on efficient tree structures \cite{Nister2006,Philbin2007,Muja2009}. However, these approaches all require the original descriptor to be computed first, which may itself be prohibitively expensive, particularly on low-powered devices.


\subsection{Matching as classification}

% motivation: object-specific and fast.

An alternative view of keypoint matching is to treat it as a classification problem. In this setting, each object keypoint defines a class, and a classifier is trained to identify which (if any) of these classes a given image keypoint corresponds to. This approach was first introduced by Lepetit and Fua \cite{Lepetit2006}, who trained a random forest \cite{Breiman2001} classifier based on simple tests between pairs of pixels around a keypoint. Subsequently, a related approach by \"{O}zuyal \etal \cite{Ozuysal2010} replaced the random forest classifier with a more discriminative and memory efficient random fern classifier (Figure \ref{fig:keypoints_rfs}). The key factor in both of these approaches is the training stage of the classifier. This proceeds by generating a large number of synthetic views of the target object and then relying on the learning algorithm to choose tests which together discriminate between the object keypoints. There are two main strengths to such an approach. The first is that the classifier is tuned specifically for the object of interest and can focus its tests appropriately. This is in contrast to descriptor-based approaches, which require a universal descriptor which is suitable for all objects. The second strength is that because the tests are chosen to be very simple, the resulting classifier is efficient to evaluate at run-time, allowing for real-time object detection.

\begin{figure}[b!]
\centering
\begin{subfigure}[m]{0.49\textwidth}
\centering
\includegraphics[width=0.9\textwidth]{images/keypoints/rf.pdf}
\end{subfigure}
\begin{subfigure}[m]{0.49\textwidth}
\centering
\includegraphics[width=\textwidth]{images/keypoints/ferns.pdf}
\end{subfigure}
\begin{subfigure}[b]{0.49\textwidth}
\centering
\caption{Random forests}
\end{subfigure}
\begin{subfigure}[b]{0.49\textwidth}
\centering
\caption{Random ferns}
\end{subfigure}
\caption[Random forests and ferns]{Random forests and ferns. Decision trees are constructed consisting of pairwise pixel tests around a keypoint. While random forests select different tests at each node, random ferns restrict all nodes at a given level to use the same test, resulting in a simpler linear structure and lower memory requirements. Images courtesy of V. Lepetit \cite{Lepetit2006} and M. \"{O}zuysal \cite{Ozuysal2010}}
\label{fig:keypoints_rfs}
\end{figure}

The weakness of classification-based approaches is that the training stage is typically time-consuming and computationally expensive, as a large number of examples of the object keypoints under various transformations must be generated to produce an accurate classifier. This is acceptable for certain applications, such as detecting a fixed image for an AR application, as the classifier can be fully trained offline and then will only ever be evaluated at runtime. There are other situations, however, where the classifier needs to be updated at runtime to include new keypoints. One such example is SLAM, where keypoint-based object detection can be used to perform relocalisation when tracking fails. Williams \etal \cite{Williams2007} propose a modification of the random forest approach to allow learning of new keypoints for SLAM, but even with simplification of the classifier and the use of the GPU, training is still computationally expensive and can only handle a relatively small number of keypoints. \"{O}zuysal \etal \cite{Ozuysal2006} propose an alternative approach which uses an online version of random forest training, allowing the classifier to be updated incrementally as new training data arrives. Their approach is therefore suitable for situations in which keypoints are added or removed at runtime, but still requires examples of the keypoints under many different transformations, which must somehow be supplied.

%machine learning is used in order to train a classifier which can take an image keypoint and classify it either as being part of the background, or as one of the model keypoints. Matching with descriptors can itself be viewed as a form of classification, in which the classifier is a simple nearest-neighbour classifier. In \cite{babenko2007}, boosting \cite{schapire2003} is used to learn a classifier which, given the image regions around two keypoints, decides whether they are a match or not, even if they have been transformed with respect to each other. In \cite{lepetit2005}, a multi-class random forest \cite{breiman2001} classifier is learned which treats each keypoint on the object model as a class, and given an unknown keypoint can predict which (if any) of the model keypoints it matches. Both of these approaches are trained using the raw image around keypoints, and learn features of these images which can be used for matching, without the need for hand-designing a descriptor. This approach is very powerful, as it allows \emph{task-specific} matching, meaning that low-level matching is tuned to the specific high-level problem one is trying to solve, rather than universal settings for all problems. Furthermore, \cite{lepetit2005} along with subsequent improvements such as \cite{ozuysal2010} provide matching which is far more efficient than SIFT, allowing for real-time object detection.


% using learning: good because we make task-specific, rather than a descriptor which is general-purpose. 

% however, the learning usually performed offline in advance. as in the case of tracking we are interested in methods which are able to perform online adaptation. some examples of this e.g. feature harvesting, but mostly the learning is still expensive. good example is grabner...



%, machine learning is being applied to the problem of keypoint matching. Although the SIFT descriptor provides excellent matching performance, it is relatively expensive to compute, and has a large number of parameters which have been empirically tuned by hand to give good performance. In \cite{winder2009}, the authors use machine learning to tune the parameters of their keypoint descriptor to maximise matching accuracy based on a training set of true matches. Machine learning can also be used to avoid the need for computing a descriptor altogether, by learning a classifier able to match keypoints directly. In \cite{babenko2007}, boosting \cite{schapire2003} is used to learn a classifier which, given the image regions around two keypoints, decides whether they are a match or not, even if they have been transformed with respect to each other. In \cite{lepetit2005}, a multi-class random forest \cite{breiman2001} classifier is learned which treats each keypoint on the object model as a class, and given an unknown keypoint can predict which (if any) of the model keypoints it matches. Both of these approaches are trained using the raw image around keypoints, and learn features of these images which can be used for matching, without the need for hand-designing a descriptor. This approach is very powerful, as it allows \emph{task-specific} matching, meaning that low-level matching is tuned to the specific high-level problem one is trying to solve, rather than universal settings for all problems. Furthermore, \cite{lepetit2005} along with subsequent improvements such as \cite{ozuysal2010} provide matching which is far more efficient than SIFT, allowing for real-time object detection.

% descriptors: Jets, SIFT, SURF
% learning: random forests, ferns, HIPs
% low-power descriptors: BRIEF, BRISK, ORB, FREAK

\subsection{Methods for low-powered devices}

There has recently been significant interest in developing approaches for keypoint matching which are suitable for portable devices such as smartphones and tablets. These devices provide an excellent platform for AR and SLAM applications, but they also have far less computational power than a typical desktop computer.

As has already been discussed, descriptor-based approaches typically involve expensive image operations, followed by high-dimensional nearest-neighbour search. While classification-based approaches were designed to provide more efficient matching, the classifiers involved often have high memory usage, which also makes them unsuitable for low-powered devices. Wagner \etal \cite{Wagner2008} present a number of carefully-engineered modifications to both of these categories of approaches which allow them to run on low-powered devices. They propose an approximation of the SIFT descriptor and matching procedure which results in significantly lower computational cost compared with the original approach. They also present an approximation of the ferns approach which results in much lower memory usage compared with the original.

Rather than improving the efficiency of existing approaches, there have also been a number of recent methods proposed which are designed from the ground up to be suitable for low-powered devices. 

Taylor \etal \cite{Taylor2009} propose Histogrammed Intensity Patches (HIPs), a classification based approach which builds independent histograms of pixel intensities for 64 sample locations around a model keypoint from training data. These histograms are each approximated very coarsely in binary form using 5 bits, resulting in a 320-bit representation of a model keypoint. Using a similar representation for an image keypoint, a dissimilarity measure between model and image keypoints can be computed using a bitwise XOR followed by a bit-count, both of which can be achieved very efficiently using bitwise operations on a CPU.


\begin{figure}[tb]
\centering
\includegraphics[width=0.5\textwidth]{images/keypoints/brief.pdf}
\caption[The BRIEF descriptor]{The BRIEF descriptor. Randomly-generated pairwise pixel tests are concatenated to give a binary descriptor. This figure shows different sampling strategies for selecting the tests. Image courtesy of M. Calonder \cite{Calonder2010}}
\label{fig:keypoints_brief}
\end{figure}

Calonder \etal \cite{Calonder2010} propose a descriptor-based approach called BRIEF, which uses simple binary tests on randomly-generated pairs of pixels around a keypoint, inspired by the random forest and fern classification-based approaches. The results of a number of independent tests are concatenated together to produce a binary descriptor (Figure \ref{fig:keypoints_brief}). The distance between two such descriptors can then be computed using the Hamming distance, which can be computed very efficiently on a CPU using bitwise operations. Although this approach is extremely simple, it has experimentally been shown to produce results comparable to SIFT and SURF matching, whilst being around two orders of magnitude faster \cite{Calonder2010a}. A number of variations on this approach have subsequently been proposed, which retain the core idea, but improve matching further by tuning the binary tests which are chosen for the descriptor \cite{Leutenegger2011,Rublee2011,Alahi2012}.

% drawback of descriptor-based approaches: both computing descriptors and performing matching are expensive. attempts have been made to address both of these: e.g. SURF is designed to make computing descriptors much cheaper than SIFT, and resulting descriptor is lower-dimensional, which improves matching speed. also PCA-SIFT performs dimensionality reduction to improve matching time. Note though that reducing the dimensionality after the descriptor has been computed, so still expensive to compute.

% drawback of classification-based approaches: hard to add new features at runtime. this is because the classifiers involved typically require an expensive training phase. this precludes the use of such approaches for e.g. SLAM. attempts have been made to address this (williams, ozuyal), but still require an explicit training step which is costly. also too expensive to use on a low-powered device

% recently, approaches using aspects from each of these methods. simple tests like RFs/Ferns, but descriptor-based so no training stage. distances fast to compute because Hamming distance used.


% recently focus on low-powered devices. 

\section{Geometric verification}

% ransac, mlesac, mapsac, prosac, desac

The final stage of the detection pipeline is geometric verification, which uses the set of independently-found keypoint matches to infer the overall presence and transformation of the target object. If the set of matches was known to be largely correct then this would be a simple task, and we could use \eg\ least-squares estimation to find the best-fitting transformation between model and image given the set of matches. However, because matches are generated independently by considering only local image information, the expectation is that there will be a significant number of outlier (incorrect) matches. For this reason, a \emph{robust} estimation procedure must be used which is able to tolerate these outliers.

The majority of approaches for geometric verification are based on RANSAC \cite{Fischler1981}. Such approaches proceed by randomly sampling minimal subsets from the full set of matches to generate transformation hypotheses and then use the remaining matches to test these hypotheses. The number of matches which define a minimal subset depends on the class of transformation which is being considered \cite{Hartley2004}. To estimate a homography, for example, 4 matches are required, while to estimate 3D rotation and translation given known intrinsic camera parameters (the P3P problem), 3 matches are required. Depending on the ratio of inlier to outlier matches, with a sufficiently large number of random samples the probability of selecting a minimal set which is free from outliers is very high, allowing the procedure to robustly estimate an overall object transformation. Alternatively, if no transformation can be found with sufficient support from the set of matches, no detection is reported.

Subsequent research has further extended the underlying RANSAC approach to use a more principled maximum-likelihood estimation procedure \cite{Torr2000}, which is now more commonly used in practice. Another important improvement is the PROSAC algorithm \cite{Chum2005}, which does not sample matches uniformly at random, but rather assumes the matches can be ranked according to their quality (\eg\ using their matching score) and biases the sampling to focus initially on the best matches. In practice this approach is able to estimate transformations with substantially fewer iterations than RANSAC, which brings great benefit for real-time applications.


\chapter{Scene reconstruction}

%\TODO{Note form at the moment.}

The task of reconstructing the underlying 3D scene which has been observed by a camera is a fundamental problem in computer vision, as it essentially aims to invert the imaging process performed by a camera. Obtaining a 3D reconstruction of a scene is particularly useful for AR applications, as it allows virtual content to be introduced which interacts with its environment in a realistic way, resulting in a more compelling experience for the user. Inverting a 2D image is of course not possible in general, although approaches have been proposed which attempt to achieve this by incorporating additional prior assumptions about the scene \cite{Zhang1999,Hoiem2007}. Given multiple views of the scene, however, the problem of scene reconstruction becomes well-posed, and there now exist a variety of sophisticated approaches able to produce high-quality dense 3D scene reconstructions.

Such multi-view reconstruction approaches take as their input multiple calibrated images of a scene, meaning the intrinsic camera parameters are known (focal length, principal point, distortion coefficients, etc), as well as the extrinsic camera parameters for each view (the 3D  camera pose). This calibration information may either come from a carefully controlled capture environment in which the 3D pose of the camera is known in advance, or by using structure-from-motion techniques \cite{Hartley2004} to estimate the calibration information from the images themselves.

% need to introduce photoconsistency here as its used a lot in chapter 5

In order to estimate 3D information from multiple views, approaches typically make use of \emph{photo-consistency} to establish dense correspondences between pixels in each view, which subsequently allows a 3D position for each pixel to be estimated by triangulation. This technique is referred to as multi-view stereo, since it generalises the principles used by stereo algorithms to more than two images. While the core principle for these methods remains the same, there are still a great variety of multi-view stero approaches \cite{Seitz2006} which differ in various factors such as how they measure photo-consistency, how they represent the scene, how they handle occlusion between views, and the optimisation strategy they use.

% i think i need more here, maybe go into some specific approaches?

While photo-consistency provides a strong cue for multi-view reconstruction, there are situations in which it may not be able to provide useful information. Problems can occur with textureless regions, for example, where it becomes impossible to reliably establish correspondences between multiple views. Similar problems can also occur at occlusion boundaries. To tackle these problems, Campbell \etal \cite{Campbell2008} propose an approach to incorporate higher-level structural constraints based around local continuity to help resolve such ambiguities.

\section{Real-time approaches}

Traditional multi-view reconstruction methods are designed to operate offline and are often computationally very expensive, taking minutes or hours on powerful desktop computers to produce reconstructions. Recently, however, there has been increased interest in developing approaches which are able to produce real-time reconstructions, and it is these approaches which have the most potential for AR applications.

\begin{figure}[b]
\centering
\includegraphics[width=\textwidth]{images/reconstruction/proforma.png}
\caption[The ProFORMA reconstruction method]{The ProFORMA reconstruction method. Points are tracked on the surface of an object to produce a 3D point cloud. Delaunay tetrahedralisation is applied and space-carving is used to remove empty tetrahedra. Image courtesy of Q. Pan \cite{Pan2009}}
\label{fig:reconstruction_proforma}
\end{figure}

One class of real-time method are those based around space-carving, which perform volumetric reconstruction using reasoning based on the visibility of features in the scene observed from multiple views. These approaches lend themselves well to the coarse reconstruction of individual closed objects, for example allowing a user to `scan' an object to produce a 3D model. The ProFORMA method \cite{Pan2009} achieves this by tracking points on the surface of an object as it is moved in front of a fixed camera and subsequently uses tetrahedral space-carving to produce a textured object model (Figure \ref{fig:reconstruction_proforma}). A related approach proposed by Basitan \etal \cite{Bastian2010} tracks the silhouette of an object by performing colour-based segmentation in multiple viewpoints and uses space-carving on a voxel grid to generate a 3D reconstruction of the object.

Space-carving methods are typically not able to produce very accurate reconstructions and suffer from problems based on the topology of the scene. For example, space-carving based on silhouettes is not able to reconstruct concavities in an object, as these do not affect the silhouette. Another class of real-time method are those which use multi-view stereo, but have been engineered to be highly efficient so that they are capable of real-time reconstruction. One such example is the method of Vogiatzis and Hern\'{a}ndez \cite{Vogiatzis2011}, which is able to estimate the 3D position of a large number of points in real-time to produce a dense point cloud for a scene. Methods proposed by Newcombe and Davison \cite{Newcombe2010} and Stuehmer \etal \cite{Stuehmer2010} both use sophisticated optimisation algorithms which can be implemented on the GPU in order to produce real-time depth-maps for multiple views, which are then fused to give 3D scene reconstructions (Figure \ref{fig:reconstruction_newcombe}).

\begin{figure}[tbh]
\centering
\includegraphics[width=\textwidth]{images/reconstruction/newcombe.png}
\caption[Real-time multi-view stereo]{Real-time multi-view stereo using the method of Newcombe and Davison \cite{Newcombe2010}. Here depth-maps have been computed and fused from 4 reference views to produce a 3D reconstruction. Image courtesy of R. Newcombe \cite{Newcombe2010}}
\label{fig:reconstruction_newcombe}
\end{figure}
%For reconstructing objects [Dick] - only for a single object [Pang, Vogiatzis] - only for textured objects.

%For reconstructing scenes, [Newcombe, Cremers]. High-quality and real-time, but computationally expensive. PC-only, requires powerful GPU hardware.



\chapter{Structured learning}

% computer vision now dominated by machine learning methods which build powerful statistical models to perform tasks

Computer vision as a field has benefited greatly from progress in machine learning, and powerful statistical models which can be learned efficiently from large quantities of data now form the core of most modern vision techniques. 

The types of problems dealt with in computer vision often involve rich models with a large amount of \emph{structure}. Such structure exists at various levels in the vision pipeline. At the low level, there is structure in terms of the local spatial relationships between pixels in an image. For higher-level scene understanding tasks, models are introduced which are structured, such as pictorial structures, hidden markov models, etc.

Recent developments in machine learning have provided tools for learning with such structured models, and this section provides a summary. For further reading, the interested reader is directed to the survey by Nowozin and Lampert \cite{Nowozin2010}.


%Motivate structured learning. What is it? What can it do? How is it different from other types of learning

% structured models, structured prediction. what's the difference. we summarise both 



\section{Structured prediction}
\label{sec:struct_prediction}


%Structured prediction refers to the general task of finding a structured solution to a problem using an optimisation procedure.

Structured prediction provides a general framework for the task of finding solutions to structured problems. In this setting we have a prediction function $f : \mathcal{X} \rightarrow \mathcal{Y}$ from an input domain $\mathcal{X}$ to a structured output domain $\mathcal{Y}$. This prediction function is defined such that it makes use of an auxiliary function $g : \mathcal{X} \times \mathcal{Y} \rightarrow \mathbb{R}$, which can be seen as measuring the \emph{compatibility} of an input-output pair. Predictions are then made according to
\begin{equation}
\label{eqn:struct_pred_fn}
\hat{\vt{y}} = f(\vt{x}) \coloneqq \argmax_{\vt{y}\in\mathcal{Y}} g(\vt{x},\vt{y}),
\end{equation}
meaning that $\hat{\vt{y}}$ is the output which has the highest compatibility with the input $\vt{x}$. 

%Such a framework encompasses many approaches commonly used in computer vision. For example, making predictions with probabilistic models using maximum a-posteriori (MAP) estimation can be achieved if we use $g(x,y) = p(y|x)$. Similarly, sliding-window object detection can be seen as a special case, in which $g(x,y)$ defines the classification score of a bounding box $y$ in an image $x$.

Such a framework encompasses many approaches commonly used in computer vision, and performing prediction amounts to solving an optimisation problem, with an objective function determined by $g(\vt{x},\vt{y})$. Defining this objective function and finding efficient ways of solving it thus form the core of structured prediction problems. 

\subsection{Sliding-window object localisation}
\label{sec:background_sliding_window}

%\TODO{Sliding-window detection is an instance structured prediction. Can use exhaustive sliding window, or more efficient techniques such as branch-and-bound... (2 paras)}

One example of a structured prediction approach used in computer vision is sliding-window object localisation, which is the most common method used for performing category-level object localisation. Here the task is to localise instances of a given category (\eg\ face, person, car, etc.) in an image, typically by drawing a bounding box around them (Figure \ref{fig:learning_sliding_window}). Sliding-window approaches \cite{Viola2004,Dalal2005,Felzenszwalb2010,Vedaldi2009} achieve this by training a classifier to predict whether a given bounding box in an image contains the category of interest or not. Localisation then proceeds by searching  over all possible bounding boxes in an image, with detections reported at local maxima of the classification confidence function. As such, this process can be viewed as an instance of structured prediction, in which the input is an image $\vt{x}$ and the output is a bounding box $\vt{y}$. The sliding-window search procedure is performing the maximisation \eqref{eqn:struct_pred_fn}, with $g(\vt{x},\vt{y})$ being the classification confidence function for a given bounding box in the image.

\begin{figure}[tb]
\centering
\includegraphics[width=0.32\textwidth]{images/learning/sliding_window1.jpg}
\includegraphics[width=0.32\textwidth]{images/learning/sliding_window2.jpg}
\includegraphics[width=0.32\textwidth]{images/learning/sliding_window3.jpg}
\caption[Sliding-window object localisation]{Sliding-window object localisation. The goal is to draw bounding boxes around instances of known object classes in an image.}
\label{fig:learning_sliding_window}
\end{figure}

Sliding-window methods must search and test a very large number of bounding boxes in an image, which is potentially too expensive for practical purposes. Consequently, researches have developed efficient ways of performing this prediction. One approach is to introduce a cascaded classifier \cite{Viola2004,Vedaldi2009}, which uses a simple and fast classifier in its early stages to reject windows which obviously do not contain the object, saving the full classifier for a smaller number of more promising windows. For certain types of classifier another method is to use branch-and-bound optimisation \cite{Lampert2009}, which can make use of an upper bound on the classification score of a collection of windows in order to reject portions of an image which cannot possibly result in a detection.


\subsection{Conditional random fields}

Discrete labelling problems occur frequently in computer vision and are often modelled as conditional random fields (CRFs). A CRF consists of a set of random variables $\vt{Y} = \{Y_1, \dots, Y_N\}$, each of which can be assigned a label from a set $\mathcal{L} = \{l_1, \dots, l_K\}$. Often, the task is to label each pixel in an image, meaning there will be one random variable per image pixel. Examples of the types of labels include categories (\eg\ road, building, tree, sky, etc.) in the case of semantic segmentation (Figure \ref{fig:learning_crf}), greyscale intensity values in the case of image denoising, or disparity values in the case of stereo matching.

\begin{figure}[tbh]
\centering
\includegraphics[width=\textwidth]{images/learning/crf.pdf}
\caption[Semantic segmentation]{Semantic segmentation. The goal is to label each pixel in an image with one of a number of known categories. Image courtesy of J. Shotton \cite{Shotton2007}}
\label{fig:learning_crf}
\end{figure}

The random variables $\vt{Y}$ are not independent, but rather affect one another based on a neighbourhood $\mathcal{N}$, which most commonly consists of pairwise connections between random variables. Given some data $\vt{x}$ (\eg\ the image data for semantic segmentation or denoising, or a pair of images for stereo matching), the posterior probability distribution of a particular labelling $\vt{y}$ of a pairwise CRF is defined by a \emph{Gibbs} distribution \cite{Hammersley1971}:
\begin{equation}
\label{eqn:crf_gibbs_distribution}
P(\vt{y}|\vt{x}) = \frac{1}{Z}\prod_{i=1}^N \exp ( -\psi_i(y_i) ) \prod_{(i,j) \in \mathcal{N}} \exp(-\psi_{ij}(y_i, y_j))
\end{equation}
where $Z$ is a constant normalisation factor, and the terms $\psi_i(y_i)$ and $\psi_{ij}(y_i, y_j)$ are referred to as unary and pairwise potentials, respectively. The way these potentials are defined is problem-specific. In the case of semantic segmentation, for example, the unary potential is generally determined by some type of classifier giving a per-pixel confidence of category membership, while the pairwise potential encourages neighbouring pixels with similar appearance to be assigned to the same category. Finding the maximum a-posteriori labelling of a CRF given some data $\vt{x}$ is thus an instance of structured prediction, since we wish to find:
\begin{equation}
\hat{\vt{y}} = \argmax_{\vt{y} \in \mathcal{L}^N} P(\vt{y}|\vt{x}).
\end{equation}
The distribution \eqref{eqn:crf_gibbs_distribution} is log-linear, which means performing this maximisation is equivalent to minimising the Gibbs energy, defined as:
%\begin{equation}
%\hat{\vt{y}} = \argmin_{\vt{y} \in \mathcal{L}^N} E(\vt{y}),
%\end{equation}
%where
\begin{equation}
\label{eqn:crf_gibbs_energy}
E(\vt{y}) = \sum_{i=1}^N \psi_i(y_i) + \sum_{(i,j) \in \mathcal{N}} \psi_{ij}(y_i, y_j)
\end{equation}

Minimising this energy is NP-hard in general, but in certain cases it can be performed exactly and in polynomial time. In the case of tree-structured CRFs, belief propagation \cite{Pearl1988} can be used. In the case of \emph{submodular} energy functions \cite{Kolmogorov2004}, the energy minimisation is equivalent to a graph cut problem, for which several efficient algorithms exist \cite{Kolmogorov2004,Boykov2004}.

In other cases, minimising \eqref{eqn:crf_gibbs_energy} exactly is not feasible, but there are still efficient approximate approaches. In particular, for the case of non-submodular multi-label problems the $\alpha$-expansion and $\alpha\beta$-swap move-making algorithms \cite{Boykov2001} are widely used.


%Solving labelling problems: can use graph cuts, belief propagation, message passing, etc.



% * may have to make compromises for efficiency: approximate solutions, random sampling, worst-case complexity, etc.


\section{Learning the prediction function}

The prediction function \eqref{eqn:struct_pred_fn} may be designed by hand to capture the properties of the problem of interest, but in many cases it is desirable to \emph{learn} the function based on training data. While structured prediction is often used in computer vision, typically the way learning has been introduced does not take into account the structure of the problem. For example, most approaches for sliding-window object detection (as discussed in Section \ref{sec:background_sliding_window}) involve training a binary classifier from a training set of positive and negative examples. Therefore the learning is for making this binary decision. However, in practice this classifier will be used inside a sliding-window framework to perform structured prediction, which is not taken into account at all by the learning. Blaschko and Lampert \cite{Blaschko2008} tackled this problem in their influential work and showed how this pipeline can be better embedded in a learning framework using a recently-proposed extension of the support vector machine (SVM) \cite{Cortes1995} to structured output spaces \cite{Tsochantaridis2005}. We now provide an overview of the classification SVM, and show how the principles behind it can be extended to structured learning problems.


% structured prediction often used in vision, but learning for these models is typically not structured. for example training a classifier for object detection. here the learning is actually to discriminate between windows with and without the object of interest. however, in practice the task is the structured prediction task of localisation, where the prediction step (eqref) is performed using a sliding-window. 

% recent developments in machine learning have provided tools for incorporating learning which takes into account the structure in the problem. in particular, the structured output svm has extended the principles of classification svms to structured space.

\subsection{Classification SVM}

% svm is one of the most widely used machine learning methods for classification it attempts to learn a linear classifier using the following function:

\begin{figure}[b]
\hspace{2.4cm}
\includegraphics[width=0.5\textwidth]{images/learning/svm.pdf}
\caption[The classification SVM]{The classification SVM. Given linearly separable training data, the SVM finds the decision boundary with the largest margin between the two classes. }
\label{fig:learning_svm}
\end{figure}

The classification SVM \cite{Cortes1995} is one of the most widely-used tools in machine learning and computer vision. The task is to take a set of training examples $\{(\vt{x}_i, y_i)\}_{i=1}^N$, where $y_i \in \{-1,1\}$, and learn a classification function $h : \mathcal{X} \rightarrow \mathbb{R}$ which can be used to make predictions according to
\begin{equation}
\hat{y} \coloneqq \text{sign}(h(\vt{x})).
\end{equation}
The SVM defines $h(\vt{x})$ as a linear function of the input
\begin{equation}
h(\vt{x}) = \langle \vt{w}, \vt{x} \rangle + b,
\end{equation}
where $b$ is a constant bias, and $\vt{w}$ represents a hyperplane defining the \emph{decision boundary} $\langle \vt{w}, \vt{x} \rangle + b = 0$. Assuming the training data are separable, that is, it is possible to find a decision boundary which correctly classifies all the positive and negative training examples, the SVM finds $\vt{w}$ which results in the largest possible separation between the positive and negative examples. To achieve this, two additional hyperplanes $\langle \vt{w}, \vt{x} \rangle + b = 1$ and $\langle \vt{w}, \vt{x} \rangle + b = -1$ are taken on either side of the decision boundary such that no training examples lie in the region in between. The region between these two hyperplanes is referred to as the \emph{margin}, and the SVM finds the decision boundary which maximises the size of this margin for the training data (Figure \ref{fig:learning_svm}). The size of the margin can be shown geometrically to be inversely proportional to $\|\vt{w}\|$, meaning the maximum-margin decision boundary can be found by solving the following convex quadratic optimisation problem:
\begin{equation}
\label{eqn:svm_hard_margin_primal}
\begin{aligned}
& \underset{\vt{w}}{\min}
& & \frac{1}{2}\|\vt{w}\|^2\\
& \; \text{s.t.}
& & \forall i: y_i (\langle \vt{w}, \vt{x}_i \rangle + b)  \geq 1.
\end{aligned}
\end{equation}
To handle the situation where the training examples are not linearly separable, it is possible to introduce \emph{slack variables} which allow some of the training examples to violate the constraint that they must lie outside of the margin. The optimisation problem then becomes
\begin{equation}
\label{eqn:svm_soft_margin_primal}
\begin{aligned}
& \underset{\vt{w}, \vg{\xi}}{\min}
& & \frac{1}{2}\|w\|^2 + C\sum_{i=1}^N\xi_i\\
& \; \text{s.t.}
& & \forall i: \xi_i \geq 0 \\
& & & \forall i: y_i (\langle \vt{w}, \vt{x}_i \rangle + b) \geq 1 - \xi_i,
\end{aligned}
\end{equation}
where $C$ is a parameter which controls how strongly margin violations are penalised. When $C=\infty$, this optimisation problem is equivalent to \eqref{eqn:svm_hard_margin_primal}, since it forces all $\xi_i=0$.


The typical way in which \eqref{eqn:svm_soft_margin_primal} is solved is first by introducing Lagrange multipliers:
\begin{equation}
\label{eqn:svm_soft_margin_lagrangian}
\underset{\vt{w}, \vg{\xi}}{\min} \; \underset{\vg{\alpha}, \vg{\beta}}{\max} \left\{ 
\frac{1}{2}\|\vt{w}\|^2 + C\sum_{i=1}^N\xi_i - \sum_{i=1}^N \alpha_i (y_i(\langle \vt{w}, \vt{x}_i \rangle + b) -1 + \xi_i) - \sum_{i=1}^N \beta_i \xi_i \right\},
\end{equation}
with $\alpha_i, \beta_i \geq 0$. Applying the stationary Karush-Kuhn-Tucker (KKT) \cite{Kuhn1951} condition and making the relevant substitutions into \eqref{eqn:svm_soft_margin_lagrangian} results in the Lagrangian dual form
\begin{equation}
\label{eqn:svm_dual}
\begin{aligned}
& \underset{\vg{\alpha}}{\max}
& & \sum_{i=1}^N \alpha_i - \frac{1}{2} \sum_{i=1}^N \sum_{j=1}^N \alpha_i \alpha_j y_i y_j \langle \vt{x}_i, \vt{x}_j \rangle\\
& \; \text{s.t.}
& & \forall i: 0 \leq \alpha_i \leq C. \\
& & & \sum_{i=1}^N \alpha_i y_i = 0
\end{aligned}
\end{equation}
Another implication of the stationary KKT condition is an instance of the representer theorem \cite{Scholkopf2001}, which states that the solution to this optimisation can always be expressed as a linear combination of the training examples:
\begin{equation}
\vt{w} = \sum_{i=1}^N \alpha_i y_i \vt{x}_i.
\end{equation}
Those training examples for which $\alpha_i > 0$ are referred to as \emph{support vectors}, and in general this solution will be sparse, meaning only a small proportion of the training examples will have $\alpha_i > 0$.

It is also possible to extend the SVM to support non-linear classification. Since all input vectors $\vt{x}_i$ only ever appear inside scalar products (both during training and classification), it is possible to use the \emph{kernel trick} and first apply a non-linear feature mapping $\vg{\phi}(\vt{x})$ to an input vector $\vt{x}$, before taking scalar products in this new feature space. A linear classifier learned in this mapped feature space will then correspond to a non-linear classifier in the original input space. This approach can be taken further by replacing scalar products with a \emph{kernel function} $k(\vt{x},\vt{x}')$. In this case, it is not necessary to perform an explicit feature-mapping of the input vectors. Provided that the kernel function satisfies certain properties \cite{Aizerman1964}, it can be shown that its evaluation is equivalent to a scalar product in a corresponding Hilbert space, which may even have infinite dimensionality. Since this mapping is never explicitly computed, evaluation of the kernel can remain efficient. 

There are a number of mature, publicly-available SVM solvers which have been designed to efficiently solve the SVM optimisation problem \eqref{eqn:svm_soft_margin_primal} \cite{Chang2011,Joachims1999a}. Most of these in practice solve the dual problem \eqref{eqn:svm_dual}, using the efficient sequential minimal optimisation (SMO) procedure proposed by Platt \cite{Platt1999}.

%\TODO{more on SMO}

%\vspace{0.5cm}
%
%\noindent An alternative view of the SVM can be obtained by considering the classification task from a risk minimisation point of view. In this case, we assume there is an underlying joint probability distribution $P(x,y)$ from which our training examples are drawn i.i.d. We further define a \emph{loss function} $L(h(x), y) \in \mathbb{R}^+$ which measures the correctness of a prediction $h(x)$ made by the classifier compared to the true output $y$. The \emph{risk} for a particular classifier $h$ is then defined as:
%\begin{equation}
%R(h) = E[L(h(x), y)] = \int L(h(x), y) dP(x,y),
%\end{equation}
%and the optimal classifier among a fixed class of classifiers $\mathcal{H}$ is the one for which this risk is minimal:
%\begin{equation}
%h^* = \argmin_{h \in \mathcal{H}} R(h).
%\end{equation}
%In general, this cannot be performed because the underlying probability distribution $P(x,y)$ is unknown. However, given a set of training examples $\{(x_i, y_i)\}_{i=1}^N$ it is possible to approximate the risk with the \emph{empirical risk}:
%\begin{equation}
%R_{emp}(h) = \frac{1}{N} \sum_{i=1}^N L(h(x_i), y_i),
%\end{equation}
%and subsequently find a classifier which minimises the empirical risk. Such an approach is referred to as empirical risk minimisation, but suffers from the fact that if $\mathcal{H}$ is large, or if the amount of training data is small, the resulting solution may have high variance, and as a result will \emph{overfit} to the training data and not generalise well. To avoid this problem, structural risk minimisation [Vapnik and Chervo- nenkis, 1974] incorporates \emph{regularisation} into the solution, to encourage simpler solutions to be chosen. The general form of structural risk minimisation is thus:
%\begin{equation}
%\label{eqn:structured_risk_minimisation}
%\underset{h}{\min} \ \lambda \, \Omega(h) + \frac{1}{N}\sum_{i=1}^N L(h(x_i), y_i),
%\end{equation}
%where $\Omega(h)$ is the regularisation function, and $\lambda$ is a parameter controlling the amount of regularisation which should be used.
%
%A natural choice for loss function is the 0/1-loss:
%\begin{equation}
%l(y_i, h(x_i)) = \left\{
%\begin{aligned}
%& 1 && \text{if $y_i h(x_i) < 0$} \\
%& 0 && \text{if $y_i h(x_i) \geq 0$},
%\end{aligned}
%\right.
%\end{equation}
%however, this function is both non-convex and non-differentiable, meaning the resulting minimisation problem \eqref{eqn:structured_risk_minimisation} is extremely challenging to solve. Consequently, machine learning algorithms must make certain approximations to result in practical solutions.
%
%If we now return to the SVM objective function \eqref{eqn:svm_soft_margin_primal}, we see that by performing some manipulation to eliminate the slack variables $\xi$, and a constant scaling which does not affect the solution, we have:\begin{equation}
%\begin{aligned}
%& \underset{w}{\min}
%& & \lambda \|w\|^2 + \frac{1}{N}\sum_{i=1}^N (1-y_i \langle w, x_i \rangle)_+,
%\end{aligned}
%\end{equation}
%where $\lambda = \frac{1}{2NC}$, and $(z)_+ = \max\{0, z\}$. In this form we can see that the SVM is in fact performing structural risk minimisation with $L_2$-regularisation and the \emph{hinge-loss}:
%\begin{equation}
%L_{hinge}(h(x_i), y_i) = (1-y_i h(x_i))_+.
%\end{equation}
%As can be seen in Figure ??, the hinge-loss provides a convex upper bound to the 0/1-loss, which importantly results in a practical optimisation problem.
%


\subsection{Structured SVM}

Recently, the SVM has been extended beyond classification so that it can also be used for structured prediction problems \cite{Tsochantaridis2005,Taskar2003}. The task in this setting is to learn the prediction function \eqref{eqn:struct_pred_fn} given a set of training examples $\{(\vt{x}_i, \vt{y}_i)\}_{i=1}^N$, where now $\vt{y}_i \in \mathcal{Y}$ is a structured label. The way this problem is approached with the structured SVM is to define the auxiliary function $g(\vt{x},\vt{y})$ as a linear function
\begin{equation}
g(\vt{x},\vt{y}) = \langle \vt{w}, \vg{\phi}(\vt{x},\vt{y}) \rangle,
\end{equation}
where $\vg{\phi}(\vt{x},\vt{y})$ is a \emph{joint feature mapping} of the input-output pair. Learning $g(\vt{x},\vt{y})$ can thus be achieved by learning $\vt{w}$. Given the prediction function \eqref{eqn:struct_pred_fn}, the goal of learning is to satisfy the constraints:
\begin{equation}
\label{eqn:struct_constraints}
\forall i: \langle \vt{w}, \vg{\phi}(\vt{x}_i,\vt{y}_i) \rangle \geq \underset{\vt{y} \in \mathcal{Y} \setminus y_i}{\max} \langle \vt{w}, \vg{\phi}(\vt{x}_i,\vt{y}) \rangle.
\end{equation}
These constraints are non-linear, however they can equivalently be replaced by a larger set of linear constraints:
\begin{equation}
\forall i, \forall \vt{y} \in \mathcal{Y} \setminus y_i: \langle \vt{w}, \vg{\phi}(\vt{x}_i,\vt{y}_i) \rangle \geq \langle \vt{w}, \vg{\phi}(\vt{x}_i,\vt{y}) \rangle.
\end{equation}
As in the case of the classification SVM, there may be many $\vt{w}$ which satisfy all of these constraints, so it is necessary to define additional criteria for selecting the `best' $\vt{w}$. This is achieved by generalising the concept of the margin, such that it now refers to the minimal difference between the score of a correct label and the closest runner-up over the entire training set:
\begin{equation}
\gamma = \underset{i}{\min} \; \underset{\vt{y} \in \mathcal{Y} \setminus y_i}{\max} \langle \vt{w}, \vg{\phi}(\vt{x}_i,\vt{y}_i) \rangle - \langle \vt{w}, \vg{\phi}(\vt{x}_i,\vt{y}) \rangle.
\end{equation}
Analogously to the classification SVM, the structured SVM finds the $\vt{w}$ which maximises $\gamma$ for the training data, which can be shown to be achieved with the following convex quadratic optimisation problem:
\begin{equation}
\label{eqn:struct_hard_margin_primal}
\begin{aligned}
& \underset{\vt{w}}{\min}
& & \frac{1}{2}\|\vt{w}\|^2\\
& \; \text{s.t.}
& & \forall i, \forall \vt{y} \in \mathcal{Y} \setminus y_i:\langle \vt{w}, \vg{\phi}(\vt{x}_i,\vt{y}_i) \rangle - \langle \vt{w}, \vg{\phi}(\vt{x}_i,\vt{y}) \rangle \geq 1.
\end{aligned}
\end{equation}
To handle the situation where it is not possible to satisfy the constraints \eqref{eqn:struct_constraints}, slack variables are introduced which allow some of the training examples to violate them. The optimisation problem then becomes:
\begin{equation}
\label{eqn:struct_soft_margin_primal}
\begin{aligned}
& \underset{\vt{w}, \vg{\xi}}{\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} \in \mathcal{Y} \setminus y_i:\langle \vt{w}, \vg{\phi}(\vt{x}_i,\vt{y}_i) \rangle - \langle \vt{w}, \vg{\phi}(\vt{x}_i,\vt{y}) \rangle \geq 1 - \xi_i,
\end{aligned}
\end{equation}
where $C$ is a parameter controlling how strongly margin violations are penalised. An issue with this formulation is that all margin violations are treated equally. In the case of the classification SVM this is appropriate, since the problem is binary. For structured prediction, however, it is desirable for prediction errors which are close to the correct label to be penalised less than those which are significantly different. This can be achieved by defining a problem-specific \emph{loss function} $\Delta : \mathcal{Y} \times \mathcal{Y} \rightarrow \mathbb{R}^+$. This loss function should satisfy $\Delta(\vt{y}, \hat{\vt{y}}) = 0$ iff $\hat{\vt{y}} = \vt{y}$ and increase as $\hat{\vt{y}}$ and $\vt{y}$ become more dissimilar. This loss function can be incorporated into \eqref{eqn:struct_soft_margin_primal} by \emph{margin rescaling}, which defines the size of the required margin between outputs according to the loss function\footnote{An alternative approach is \emph{slack rescaling} \cite{Tsochantaridis2005}, in which the loss function is incorporated by replacing the slack variables in \eqref{eqn:struct_soft_margin_primal} with $\xi_i \leftarrow \xi_i/\Delta(\vt{y}_i, \vt{y})$; however, this has seen less use in the computer vision literature.}\cite{Tsochantaridis2005,Taskar2003}:
\begin{equation}
\label{eqn:struct_margin_rescaling_primal}
\begin{aligned}
& \underset{\vt{w}, \vg{\xi}}{\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} \in \mathcal{Y} \setminus y_i:\langle \vt{w}, \vg{\phi}(\vt{x}_i,\vt{y}_i) \rangle - \langle \vt{w}, \vg{\phi}(\vt{x}_i,\vt{y}) \rangle \geq \Delta(\vt{y}_i, \vt{y}) - \xi_i,
\end{aligned}
\end{equation}
% todo: show dual form
As can be seen, the structured SVM optimisation problem is very similar in form to that of the classification SVM \eqref{eqn:svm_hard_margin_primal}. The major difference is that now instead of $N$ constraints, there are $N(|\mathcal{Y}|-1)$. Depending on the size of the output space, this is potentially a very large or even infinite (if the output space is continuous) number. Nevertheless, practical approaches exist for performing this optimisation. Tsochantaridis \etal \cite{Tsochantaridis2005}, who first introduced the structured SVM as presented here, also proposed a \emph{cutting plane} \cite{Kelley1960} scheme for solving \eqref{eqn:struct_margin_rescaling_primal}. The key observation is that although there are a very large number of constraints, only a small fraction of them will ever be active, with the remaining ones satisfied automatically. The optimisation procedure maintains an active set of constraints, which define a reduced optimisation problem which can be solved to find $\vt{w}$. Given this solution, any constraints which are violated from the full set are identified and added into the active set, and the procedure is iterated until no further violated constraints exist. This method provably converges to the solution of \eqref{eqn:struct_margin_rescaling_primal} and has the additional benefit that the core optimisation procedure is able to use the same efficient methods \cite{Platt1999} as standard classification SVM solvers. Subsequent improvements have also been made to this approach which result in faster convergence guarantees \cite{Joachims2009}.


As in the case of classification SVMs, it is also possible to extend structured SVMs to non-linear prediction functions by kernelisation. In the case of classification SVMs, such kernels $k(\vt{x},\vt{x}')$ operate on two elements from the input domain only. Structured SVMs extend this concept and make use of \emph{joint kernels}, which operate on two input-output pairs:
\begin{equation}
k(\vt{x},\vt{y},\vt{x}',\vt{y}') = \langle \vg{\phi}(\vt{x},\vt{y}) , \vg{\phi}(\vt{x}',\vt{y}') \rangle.
\end{equation}
An example of such a joint kernel is the \emph{restriction kernel} \cite{Blaschko2008}, used for object localisation. Here the inputs $\mathcal{X}$ are images, and the outputs $\mathcal{Y}$ are bounding boxes. The restriction kernel $k_r(\vt{x}|_\vt{y}, \vt{x}'|_{\vt{y}'})$ applies any standard image-based kernel to the regions in $\vt{x}$ and $\vt{x}'$ defined by the bounding boxes $\vt{y}$ and $\vt{y}'$. %figure



%As has been discussed previously, the SVM performs structural risk minimisation using the hinge loss to provide a convex upper bound on the 0/1-loss. The 0/1-loss is appropriate for classification problems, since the problem is binary. For structured prediction, however, in which the size of the output space is large or potentially infinite, the 0/1-loss is usually not appropriate, since it considers all incorrect predictions as being equally bad. Instead, structured SVM problems also require a problem-specific loss function $\Delta : \mathcal{Y} \times \mathcal{Y} \rightarrow \mathbb{R}^+$, which measures the loss for predicting the output $\hat{y}$ instead of the true output $y$. This loss function should satisfy $\Delta(\hat{y}, y) = 0$ iff $\hat{y} = y$, and increase as $\hat{y}$ and $y$ become more dissimilar. As before, it is generally not possible to perform structural risk minimisation directly using this loss function, but again the hinge-loss can be employed as a convex upper bound. The structured hinge-loss is then defined as:
%\begin{equation}
%L(x, y, w) = ( \underset{y' \neq y}{\max} \{\Delta(y',y) - \langle w, \phi(x,y) \rangle + \langle w, \phi(x,y') \rangle \})_+
%\end{equation}



% natural extension to structured prediction. replace classification function with structured prediction function, and assume g(x,y) = <w, phi(x,y)>. can now learn w given training pairs of (x,y). note that the classification SVM is a special case of this, where y = {-1,1} and phi(x,y) = y*x

% important addition: loss function, measures how similar to outputs are.

% as before, can write this as an optimisation...

% now we have similar problem, but with much larger set of constraints. however, can still solve using delayed constraint generation. mention 1-slack formulation.

% can still benefit from kernelisation as before, but now using joint kernels between x and y.

\subsection{Online learning}
\label{sec:background_online_learning}

Both the classification and structured SVM as presented so far assume that all the training data are available at the time of learning. This scenario is referred to as \emph{batch} learning. A different scenario is \emph{online} learning, in which the training data arrive sequentially. In this setting, the learner must be incrementally updated each time a new training example arrives. The current state of the learner is used in order to predict the label for this new example, which is then compared to the true label, and adjustments are made to the learner as appropriate. Besides handling the situation where training data truly does arrive sequentially, online learning is a useful tool when there is a great deal of training data which cannot practically be processed by a batch learning algorithm.

Recent research has resulted in a variety of methods for training SVMs in an online fashion. These methods can be separated into two classes: those which operate in the primal, and those which operate in the dual.

\vspace{0.5cm}

\noindent \textbf{Primal approaches.} Methods for training SVMs online in the primal are generally based on \emph{stochastic sub-gradient descent}. As an illustrative example, we present an overview of the Pegasos \cite{Shalev-Shwartz2010} algorithm for online training of a classification SVM. This approach maintains a hyperplane $\vt{w}_t$ which summarises the result of learning from all examples $\{(\vt{x}_i,y_i)\}_{i=1}^{t-1}$. The objective function of the primal SVM optimisation problem \eqref{eqn:svm_soft_margin_primal} can be rewritten in unconstrained form (with a constant scaling that does not affect the solution) by eliminating the slack variables $\vg{\xi}$:
\begin{equation}\label{eqn:background_svm_primal_unconstrained}
f(\vt{w}) = \frac{\lambda}{2} \|\vt{w}\|^2 + \frac{1}{N}\sum_{i=1}^N (1-y_i \langle \vt{w}, \vt{x}_i \rangle)_+,
\end{equation}
where $\lambda = \frac{1}{NC}$, and $(z)_+ = \max\{0, z\}$ is the \emph{hinge} function. In order to optimise this given a single training example $(\vt{x}_t, y_t)$, Pegasos considers an approximate objective function based on just this example:
\begin{equation}\label{eqn:background_pegasos_approx_objective}
f(\vt{w}; t) = \frac{\lambda}{2} \|\vt{w}\|^2 + (1-y_t \langle \vt{w}, \vt{x}_t \rangle)_+.
\end{equation}
This approximation is justified probabilistically because, considering the training examples as random variables, the expectation of its gradient is equivalent to the actual gradient of \eqref{eqn:background_svm_primal_unconstrained}. The function \eqref{eqn:background_pegasos_approx_objective} is convex in $\vt{w}$, but non-differentiable due to the discontinuity in the gradient of the hinge function $(z)_+$ at $z=0$. Nevertheless, a \emph{sub-gradient} \cite{Shor1985} is given by
\begin{equation}
\vg{\nabla}_t = \lambda \vt{w}_t - \mathbb{I}(y_t \langle \vt{w}_t, \vt{x}_t \rangle < 1) y_t \vt{x}_t,
\end{equation}
where $\mathbb{I}(\cdot)$ is an indicator function which takes a value of 1 if its argument is true and 0 otherwise. This sub-gradient is then used to perform a single gradient descent step according to
\begin{equation}
\vt{w}_{t+1} = \vt{w}_t - \eta_t \vg{\nabla}_t,
\end{equation}
%todo: algorithm box?
where $\eta_t = \frac{1}{\lambda t}$ is the step size at time $t$. This approach provably converges to the batch SVM solution \cite{Shalev-Shwartz2010}, whilst being extremely simple to implement. Further improvements have also been proposed which can accelerate convergence, such as performing updates to $\vt{w}$ which are averaged over time \cite{Xu2010,Polyak1992}.

A very similar approach for online learning can also be taken for the case of structured SVMs, where now the approximate objective function based on the structured training example $(\vt{x}_t,\vt{y}_t)$ is derived from \eqref{eqn:struct_margin_rescaling_primal} and given by:
\begin{equation}
f(\vt{w}; t) = \frac{\lambda}{2} \|\vt{w}\|^2 + (\underset{\vt{y} \in \mathcal{Y} \setminus y_t}{\max} \{ \Delta(\vt{y}_t, \vt{y}) + \langle \vt{w}, \vg{\phi}(\vt{x}_t, \vt{y}) \rangle - \langle \vt{w}, \vg{\phi}(\vt{x}_t, \vt{y}_t) \rangle \})_+.
\end{equation}
Let
\begin{equation}
\label{eqn:sgd_structured_secondbest}
\hat{\vt{y}}_t = \underset{\vt{y} \in \mathcal{Y} \setminus y_t}{\arg\max} \{ \Delta(\vt{y}_t, \vt{y}) + \langle \vt{w}, \vg{\phi}(\vt{x}_t, \vt{y}) \rangle \},
\end{equation}
then a sub-gradient is given by:
\begin{equation}
\vg{\nabla}_t = \lambda \vt{w}_t - \mathbb{I}(\Delta(\vt{y}_t, \hat{\vt{y}}_t) + \langle \vt{w}, \vg{\phi}(\vt{x}_t, \hat{\vt{y}}_t) \rangle - \langle \vt{w}, \vg{\phi}(\vt{x}_t, \vt{y}_t) \rangle > 0) (\vg{\phi}(\vt{x}_t,\vt{y}_t) - \vg{\phi}(\vt{x}_t,\hat{\vt{y}}_t)),
\end{equation}
and $\vt{w}_t$ is updated in the same way as before. Notice that finding $\hat{\vt{y}}_t$ in\eqref{eqn:sgd_structured_secondbest} is closely related to the prediction function \eqref{eqn:struct_pred_fn}, except it now also includes the loss function $\Delta$. This step is referred to as \emph{loss-augmented prediction} and is a core consideration when learning with the structured SVM. Ideally, the loss function should be chosen in such a way that it decomposes over the output space, meaning the efficient prediction algorithms discussed in Section \ref{sec:struct_prediction} can still be applied\cite{Szummer2008,Blaschko2008}.



\vspace{0.5cm}

\noindent \textbf{Dual approaches.} While primal approaches for online learning are efficient and simple to implement, they also rely on an explicit representation of the SVM weight vector $\vt{w}$. As has been discussed, one of key strengths of SVMs is that non-linearity can be introduced through the use of kernels. However, once kernels are employed the weight vector is only represented implicitly based on the set of support vectors. In order to make use of kernels in an online setting, alternative algorithms have been proposed which perform online optimisation of the dual SVM optimisation problems. In the case of the classification SVM, the LASVM algorithm \cite{Bordes2005} performs online optimisation of \eqref{eqn:svm_dual}, and the approach has subsequently been extended to the structured SVM to perform online optimisation of the dual form of \eqref{eqn:struct_margin_rescaling_primal} with the LaRank algorithm \cite{Bordes2007,Bordes2008}. All of these methods are based on the fact that the standard approach for optimising the dual form of SVMs is to use sequential minimal optimisation (SMO) \cite{Platt1999}. SMO involves repeatedly solving minimal sub-problems of the dual optimisation involving only pairs of Lagrange multipliers $\alpha_i$ and $\alpha_j$, along with a strategy for choosing these pairs to encourage fast convergence. LASVM and LaRank both adapt SMO to an online setting, by alternating between optimising the Lagrange multipliers associated with new training examples as well as of existing support vectors.

When optimising in the dual, the solution is entirely defined by the set of support vectors. It is known that in general the number of support vectors increases with the size of the training set, meaning that in an online setting the number of support vectors grows without bound over time. This has the consequence that both prediction and learning become more expensive in terms of computation and memory usage over time, which is an undesirable property for an online learning algorithm. To tackle this issue, approaches have been proposed for incorporating a \emph{budget} on the number of support vectors \cite{Crammer2003,Wang2010}. These approaches set an upper limit on the number of support vectors which can be retained to describe the solution of the optimisation problem. Various strategies can then be employed for enforcing this budget. The simplest strategy is to remove support vectors, either based on their influence on the solution (\ie\ remove the support vector with the smallest Lagrange multiplier) or based on their age. Other strategies \cite{Wang2010} include projecting the support vector which will be removed onto the remaining support vectors, or merging pairs of support vectors.



% key feature: example received, model predicts, label revealed, adjustments made.

% besides handling the situation where training data really does arrive sequentially, online learning is also useful in situations where there is a great deal of training data.

% reasons for online learning: can handle large datasets which don't fit in memory, scale better with the training set size.

% first set of approaches consider the primal SVM problem, and solve for w using stochastic sub-gradient descent. good property is that w is represented explicitly, so very efficient even for large training sets. 

% tacking in the primal doesn't allow for the use of kernels, so alternatively can produce online algorithms operating in the dual. now w is represented implicitly by the support vectors, so we can suffer from problems as the number of support vectors grows. to tackle this unbounded growth, approaches have been proposed for budgeting, which limit the number of support vectors. different strategies for maintaining the budget.


% formulations presented so far assume we have a set of training data available when performing learning. such approaches are referred to as batch methods, and have traditionally been the focus of machine learning algorithms

% different scenario is when we don't have access to all training data, and instead wish to learn from data sequentially. reasons for this include inability to hold all data in memory because there is so much of it 




% both classification and structured output svms can make use of online training. 

% first set of approaches take advantage of the fact that the optimisation is convex, and uses stochastic sub gradient descent. bottom, pegasos, 

% next set of approaches operate in dual, and develop online versions of SMO. [bordes]




% rich models

% majority of these methods focus on classification, the task of predicting a binary output based on an input vector. 

% machine learning has traditionally dealt with problems such as classification and regression, where output is a binary or real-valued number. but recently approaches have been developed for outputs which are more complicated and contain structure.

% structured SVM -- introduce mathematically

%%%\subsection{Online learning}

% much progress in adapting machine learning techniques to be able to be trained online.

% here we focus on online learning for SVMs.

% the SVM involves solving a convex optimisation problem. while many sophisticated solvers for this objective function have been proposed, can also be solved using very simple approaches such as gradient descent. research from neural networks has often made use of stochastic gradient descent, and porting these ideas to SVMs have resulted in very successful online algorithms. [bottou, pegasos]

% 



%%%\section{Conditional random fields}

% another example of a technique exploiting structure is CRFs. here the goal is to label a random field, with structure imposed structure through the use of a neighbourhood.

% models contain various parameters, and learning involves learning these parameters given labelled examples. different levels of complexity for learning: simplest is learning just unary, then more complex approaches also learn pairwise etc.