\chapter{Motivation and related work}
\label{sec:learnmatch_backgound}

Keypoint-based methods for geometric object detection generally follow a two stage approach:
\begin{enumerate}
  \item Finding a set of 2D correspondences between an object model and an input image.
  \item Estimating the transformation of the object in the image using a robust geometric verification method based on hypotheses generated
    from the correspondences (\eg~RANSAC and its variants).
\end{enumerate}
Generally these two stages are considered as separate problems, and many algorithms focus on improving the object detection quality by employing robust methods for each of these steps individually.
%Continious application of such an object
%detector to a video sequence in known as \emph{tracking-by-detection} and can be used for 2D or 3D object tracking.

To find the appearance-based 2D correspondences, there are two approaches: matching and classification. Matching-based
approaches~\cite{Lowe2004,Bay2008,Calonder2010,Leutenegger2011} use descriptors to store a signature for each model
keypoint in a database. These descriptors are designed to be invariant to various geometric and photometric
transformations and can then be matched given a suitable distance metric to keypoints in an image in a nearest-neighbour
fashion.

Classification-based approaches~\cite{Taylor2009,Lepetit2006,Ozuysal2010} treat matching as multi-class classification, in which the task is to classify each image keypoint as either background or a particular keypoint from the model. These classifiers are learned offline from training examples of the object observed under various geometric and photometric transformations (usually generated synthetically) and are therefore tuned to the specific object and how individual keypoints might appear in an image. The training algorithm and the number of training examples determine the computational complexity of the learning stage.

Since classification-based approaches rely on an expensive training stage as well as the availability of a 2D/3D object model at training time, these approaches cannot easily be used for on-the-fly detection and tracking of arbitrary objects. This particular problem of the classification-based approaches limit their applicability in practice.

\"{O}zuysal \etal \cite{Ozuysal2006} propose an approach for learning a classification-based model at runtime, by using online random forests to reduce training time. However, this approach is still too computationally expensive to be useful on low-powered devices and also does not continue to adapt the model after the initial training phase. The method most related to our own work is that proposed by Grabner \etal \cite{Grabner2007}, in which keypoint classifiers are learned online by using Haar features and an online boosting algorithm. This approach relies on the fact that the geometric verification step can be used in order to provide labels for updating the classifiers in an online manner, allowing for adaptive tracking-by-detection.

To the best of our knowledge, all previous methods involving learning treat the generation of correspondences and estimation of object transformation separately. In this chapter, we propose a novel approach which combines these two steps into a coherent structured learning framework. In this formulation, correspondence generation, learning, and transformation estimation all work together in a unified optimisation formulation with the goal of performing object detection robustly. Our approach proposes an alternative view on keypoint-based object detection where the transformation estimation algorithm operates as the maximisation step of a structured prediction framework. Unlike the online boosting approach of Grabner \etal \cite{Grabner2007}, our formulation is also capable of incorporating any kind of keypoint descriptor into its learning process and is specifically targeted towards low-powered devices.

Structured output prediction was introduced to the computer vision community by Blaschko and Lampert \cite{Blaschko2008} for the task of 2D sliding-window object localisation. In Chapter \ref{chp:struck} we have seen how a similar approach can be taken which uses online learning to perform adaptive 2D tracking-by-detection. The work in this chapter is different from these approaches because we are now interested in object detection and tracking under a much larger class of transformations such as 3D pose or homography, and as a result we propose using RANSAC in order to perform structured prediction.

There has recently been significant research interest focusing on object detection for low-powered portable platforms such as smartphones. In particular, highly efficient methods such as BRIEF \cite{Calonder2010} and BRISK \cite{Leutenegger2011} have been developed for descriptor matching. Both of these methods
perform simple binary pixel-based tests on keypoints in order to build binary descriptors. By representing these
descriptors as bitsets and measuring similarity using the Hamming distance, matching can be performed extremely
efficiently using bitwise operations which are well-supported by modern CPUs. We show how the internal representation of our algorithm can be approximated to take advantage of these binary descriptors, making our approach also suitable for low-powered devices.

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: "../learnmatch"
%%% End:
