
\part{Introduction}
\label{chp:intro}

\noindent This thesis addresses a number of real-time computer vision problems, all of which are motivated by their potential application to computer games. The work we present has been carried out as part of a collaboration between academia and industry and has therefore been influenced by factors from both of these fields. Throughout this thesis, the desire has been to produce results which are both academically interesting and rigorous, and which also lay the groundwork for useful real-world applications of computer vision.

%The work presented here has been carried out as part of a collaboration between academia and industry, and can therefore be seen as straddling the two. Throughout this thesis, the desire has been to produce results which are both academically interesting and rigorous, and which also lay the groundwork for useful real-world applications of computer vision. % improve
% how well has this been achieved? worth discussing in conclusion

%\TODO{change}
% yuli:
% The work presented here has been carried out as part of a collaboration between academia and industry, and the aim has therefore been to develop ideas which straddle the two.

\chapter{Motivation}

In recent years, computer vision has played an increasingly important role in the development of computer games, and it now features as part of the core technology for many gaming platforms. Aside from the obvious factors contributing to this such as the availability of cheaper camera hardware and more powerful processors, there have been two major factors affecting the development of computer games which have placed increasing emphasis on computer vision.

The first of these is the shift towards casual gaming, which aims to make more accessible and social games which can be played by non-expert users. Many of these are `physical' games, meaning a user interacts with them using their body, rather than having to learn less intuitive button presses on a traditional controller. Besides being accessible to non-expert users, physical games have proved popular for computer game publishers wishing to change the image of gaming as an anti-social, unhealthy pastime.
% picture

The second factor is the rise in mobile gaming, caused by an explosion in the number of portable devices such as smartphones and tablets, which means that mobile gaming is no longer restricted to users who choose to carry around a dedicated gaming device. The fact that most current smartphones, tablets and portable games consoles also include a camera provides opportunities for computer vision to be used in games for these devices.
% and there has been a great deal of interest in using augmented reality for this purpose, with users looking `through' the device to see a modified scene.
% picture


The work in this thesis is motivated by both of these factors, and our contributions fall into two broad categories:
\newpage
\begin{itemize}
\item
\textbf{Human-computer interaction}. The work in Chapter \ref{chp:struck} deals with tracking, which is motivated by the need to track the face of a player interacting with a camera-based game. By tracking the player, games can be developed which take their input directly from the player's physical movements, providing a more intuitive form of human-computer interaction than would be available using a traditional controller.

\item
\textbf{Augmented reality (AR)}. Mobile devices provide an excellent platform for augmented reality, as it feels both natural and magical to hold them up as a `window' to the world through which a user can see a modified version of reality. The work in Chapter \ref{chp:learnmatch} deals with the task of providing robust detection and tracking of an object in 3D, which is an essential core component of an AR system. Chapter \ref{chp:reconstructor} deals with the higher-level task of trying to infer the real-world structure of a scene, which can be used to enhance the AR experience and provide a platform for more compelling games.

\end{itemize}


\chapter{Challenges}

% real-time/performance
% real-world -> learning
% modern learning -> large data -> can be retargeted for our purpose

Being driven by applications for computer games means that certain important challenges had to be taken into account when developing the approaches in this thesis.

\section{Diverse environments}

A key factor when developing vision algorithms for use in computer games is that they are expected to be deployed to a large audience in a wide variety of environments. This principle has guided much of the work in this thesis, and a common theme is that algorithms should incorporate an element of \emph{adaptability} to a given environment.

The approaches we develop all incorporate machine learning at their core, in common with much of the recent research across the entire field of computer vision. Importantly, building on these well-studied and principled techniques from the machine learning community provides us with a natural mechanism for incorporating adaptability into our algorithms: \emph{online learning}. Significant progress has been made by the machine learning community in recent years in order to handle the vast, distributed datasets which arise from an increasingly digital and connected world. Traditional learning approaches which require access to all training data at once are being superseded by those which are able to learn incrementally using only portions of the dataset and, in the extreme case, using only individual training examples. In this thesis we take advantage of this progress in order to provide adaptability to diverse environments.

% discuss structure


\section{Computational constraints}

The other significant factor which must be considered in our setting is computational cost and, in particular, the desire for algorithms to be \emph{real-time}. This is of course an imprecise term, but in general the algorithms developed in this thesis are designed to be run interactively as frames are received from a camera. This requirement places fundamental constraints on the types of approaches which can be developed and affects the way that success is measured. Such real-time requirements have even more significant consequences when targeting portable devices. While the portable computing revolution has been made possible in large part by the development of more powerful and efficient processors, these devices still possess only a fraction of the computational power of a typical desktop computer. The computational constraints placed on the vision algorithms are compounded by the fact that in practice not all of the available processing power is available, since it is also necessary to run a game on the same device. The goal is therefore to produce algorithms which achieve acceptable accuracy, whilst using as little processing resources as possible.

We again find that we are able to benefit from progress in online machine learning in order to work within these constraints. Because these learning algorithms are intended to work with extremely large datasets, they too must be designed to be as computationally efficient as possible. Often, this is achieved using the philosophy of the `unreasonable effectiveness of data' \cite{Halevy2009}, which states that simple learning algorithms trained with large quantities of data often outperform more sophisticated and expensive learning algorithms trained with smaller quantities of data. Using these simple learning algorithms, we are able to produce algorithms which achieve our goal of providing adaptability in a principled way, whilst still remaining computationally efficient, even for low-powered devices.


%A common theme when developing computer vision algorithms for use in computer games is performance, and typically real-time performance is essential. 

% for mobile gaming, another key requirement is suitability of algorithms for low-powered devices

% the real-time/low-power requirement feature throughout this thesis, and fundamentally affect design decisions for algorithms. while traditional research in computer vision may focus entirely on results, with performance being no object, in our case the performance cannot be neglected. this is not unique to the work in this thesis, however, as it is becoming increasingly important in both computer vision and machine learning. 

% real-world applications: needs to work in a variety of environments. this can motivate the online learning aspect. want algorithms that can adapt and use data in sensible ways. increasingly in vision this is achieved using machine learning, rather than hand-designing. our work also makes use of this.

% performance also plays a major factor in modern machine learning research, though usually for slightly different reasons. in these cases, the desire is to develop algorithms which can cope with the vast quantities of data which are available because of the internet and all of the data produced be people (so-called 'big data'). in order to work with web-scale data, researchers have produced new algorithms which focus on efficiency. often, these approaches take simple approaches to learning, but couple this with large quantities of data, yet still find that overall performance improves. this has been attributed to the 'unreasonable effectiveness of data' [cite]. the work in this thesis benefits from much of this research, in particular online learning. while this has been developed mostly for large datasets, we take advantage of it for real-time and low-power applications.

% another area from machine learning from which we benefit is structured learning, which goes beyond traditional machine learning tasks such as classification to problems with more structure. when dealing with computer vision problems, structure is often an important factor...



\chapter{Contributions}

In this thesis we address three problems in real-time computer vision. These problems have been chosen because they have been identified as being useful from an industrial perspective, in that they can provide the building blocks for vision-based computer games. The approaches which we develop make use of recent progress in online machine learning, and in particular structured learning, in order to tackle these problems in a principled academic manner.

%In order to tackle these problems, we make use of recent developments in online machine learning, and in particular structured learning, in order to provide principled academic solutions.


% They are also linked from an academic perspective in terms of the approaches which have been chosen to tackle them.

%yuli:
%\TODO{change}
% from an academic perspective, we make use of recent developments in online structured learning in order to tackle each of these problems.

% In order to tackle these problems, we make use of recent developments in online structured learning in order to provide principled academic solutions.

%We have sought to provide principled academic solutions by making using of recent developments in online structured learning to tackle these problems.


\section{2D object tracking}

Chapter \ref{chp:struck} presents a novel approach for 2D tracking of arbitrary objects. In common with recent research in visual object tracking we incorporate online learning to provide an appearance model which is able to adapt to the target object and its surrounding background during tracking. However, our approach moves beyond the standard framework of treating tracking as a binary classification problem and instead integrates tracking and learning in a more principled way through the use of structured learning. We use a structured output support vector machine (SVM) to perform learning, and in order to allow for real-time application we also introduce a budgeting mechanism which constrains the computational cost of our approach. As well as providing a more powerful framework for adaptive visual object tracking, our approach also outperforms state-of-the-art tracking algorithms on standard datasets.

\section{Keypoint-based object tracking}

Chapter \ref{chp:learnmatch} deals with the task of keypoint-based object tracking, which is a core component required for AR applications. We take the traditional pipeline for this task of matching keypoints using image descriptors followed by geometric verification using random sampling and show how this can be embedded into a structured learning framework in order to provide adaptivity to a given environment. Similarly to the work of Chapter \ref{chp:struck}, the use of structured learning allows tracking and learning to be tightly integrated in a principled way. We also propose an approximation method allowing us to take advantage of recently developed binary image descriptors, meaning our approach is suitable for real-time application even on low-powered portable devices. Experimentally, we clearly see the benefit that online adaptation using learning can bring to this problem.

\section{Scene reconstruction}

Chapter \ref{chp:reconstructor} continues the theme of AR on low-powered devices from Chapter \ref{chp:learnmatch} and presents an approach for approximately recovering the dense 3D structure of a scene which has been mapped by a simultaneous localisation and mapping (SLAM) system. Our approach is guided by the constraints of the hardware we are targeting, and we develop a system which coarsely models the scene using a small number of planes. In common with the work in other chapters, we frame the task as a structured prediction problem and introduce online learning into our approach. This allows us to use relatively simple multi-view information coupled with online learning of appearance to efficiently produce reconstructions of a scene which are useful from a gaming perspective.

\newpage


% for each section, include some illustrative graphics?

\chapter{Publications}

The work presented in Chapter \ref{chp:struck} first appeared in:

\begin{itemize}
\item
S.~Hare, A.~Saffari, and P.~H.~S.~Torr.
\newblock Struck: Structured Output Tracking with Kernels.
\newblock In \emph{IEEE International Conference on Computer Vision},~2011.
\end{itemize}

\noindent The work presented in Chapter \ref{chp:learnmatch} first appeared in:

\begin{itemize}
\item
S.~Hare, A.~Saffari, P.~H.~S.~Torr.
\newblock Efficient Online Structured Output Learning for Keypoint-Based Object Tracking.
\newblock In \emph{IEEE Conference on Computer Vision and Pattern Recognition},~2012.
\end{itemize}



