\chapter{Introduction}
\label{ch:intro}

Some 540 million years before you started reading this thesis, something interesting happened. Although living organisms have existed on Earth for over 3.5 billion years of our planet's 4.5 billion year history, the most dramatic evolution of new species occurred during a period of ``just'' 60--70 million years -- an event we now refer to as the \emph{Cambrian Explosion}. Although the fossil record isn't fully complete, the data suggest that life on Earth transformed during this short period from mainly single-celled species to a world filled with the major groups of complex, multicellular life still in evidence today. 

The Cambrian Explosion was so rapid and pronounced that even Charles Darwin expressed concern that it undermined his theory of evolution by natural selection. However, later research \cite{eldredge72alternative} suggested that evolution is not, in fact, a process of gradual improvement, rather it consists of large periods of stasis punctuated by rapid bursts of change. To this day, and in the absence of other hypotheses, evolution is human-kind's best explanation for how we all came to be here -- and how you come to be reading this thesis.

As it happens, it is from this period that the earliest fossil remains of animal eyes have been found. While basic photo receptors are sufficient for an individual to distinguish light from dark or day from night, an eye is something rather special. Our vision systems permit us to explore and navigate through the world with a remarkable degree of understanding. 

Although nobody knows for certain what triggered the Cambrian Explosion, some zoologists \cite{parker} believe it was the advent of sight that sustained it. One can only imagine the advantage of a predator with some form of sight would have in a world filled with blind prey. The survival of a species would hinge on its ability to adopt better defences or to develop such new senses in turn; an evolutionary arms race commenced. As it happens, the \emph{Burgess Shale}, a substantial deposit of fossils dating from the Cambrian Explosion, shows evidence of the adaptations evolved by predators and prey alike. Nowadays 96\% of the world's species employ some form of vision system in order to perceive the world as illuminated by visible light\footnote{Of course, visible light is only a small band in the electromagnetic spectrum. Interestingly, the wavelengths within the ``visible'' spectrum are one of only two bands of light that can travel through water. Our continuing exclusive perception of just this small band is a throwback to the environment in which vision systems first appeared -- in creatures who lived underwater.}.

Most species have what one might describe as a \emph{vision system}, including both eye sensors and a degree of processing in the brain\footnote{Although some species of jellyfish do not -- their eyes are connected directly to motor receptors.}. Indeed some species, notably birds of prey, have significantly better sensors than humans. However, humans are distinguished by the significant portion or our already generously proportioned brains dedicated to vision \emph{processing}. In addition to being able to perceive our surroundings instantly in astonishing clarity, we can recognise almost anything, including things we haven't seen before. We can understand how some tools and machines work simply by looking at them, all seemingly without effort. 

Because these ``tasks'' can be performed without much noticeable exertion, it is quite easy to be complacent about the quality and scope of our vision system. It is perhaps only when we try to implement vision systems in silicon that we come to realise just what an astonishing feat of engineering is to be found inside our heads. From our implementations of imperfect sensor technology, incomplete vision algorithms and underpowered hardware, one gains an appreciation of how much has been accomplished within and behind our eyes. Nonetheless, while the tasks that computer vision researchers have set themselves are sometimes ambitious, some great leaps forward have been made in recent years.

\section{The Rise of Machine Vision}
During the last decade or so, some applications of computer vision, such as the automatic recognition of car number-plates or in-camera face detection, have become ubiquitous. This is thanks both to the significant increases in computing power available in increasingly small devices and the quality of work undertaken by academic researchers and commercial organisations in labs around the world. Whether one likes or dislikes applications such as the congestion charge cameras in London, they only exist because machines can now do the bulk of the vision processing automatically and accurately.

Now that machines can demonstrably perform a limited subset of useful vision tasks, human ambition demands ever more applications for them to work on. Some are completely new, such as the interactive window displays now showing on the streets of Tokyo or the foyers of Harrods department store. As machine vision breaks out from military and research circles into the mainstream, new topics of research arise, along with a desire to produce these systems more easily.

How might one go about creating vision systems more easily? Certainly many of the established, excellent techniques for extracting information from images are not easy to understand, being rooted firmly within the confines of mathematics, statistics and pattern analysis. They are often built around certain assumptions about how the world appears, which may not hold true, and they generally require the effort of an expert to select, implement and tune them. In short, it is time-consuming and difficult to produce vision software. 

\section{Machine Learning}
As a concept, it would be nice to be able to develop strategies in a way that required less effort. Ideally we would have the computer do this on its own -- a process broadly defined as machine learning. After all, computers can work on certain problems much more quickly than we can and, unlike humans, computers don't have a concept of impatience nor do they demand hourly wages! Modern computing power is certainly making heavy tasks such as image processing increasingly practical and so the automatic learning of computer vision is becoming more and more feasible. Indeed, some high quality vision software has already been developed using machine learning techniques, for instance the work by Viola and Jones on face detection \cite{EvoVision:Viola-Jones:2004}. 

%Todo - mention some other learned technques - OCR for character detection seems a good one.

%Todo: define what a vision system is. Seems to be whatever people want it to be! No fixed definition.

%TODO Citation needed for the outperform part.
One family of machine learning techniques takes inspiration from Charles Darwin's theory of evolution directly. The aim is that by simulating the process of natural selection, computers may be able to replicate the explosion of progress and adaptation that occurred on Earth 540 million years previously. So-called evolutionary computation was largely confined to parameter optimisation tasks until computing power permitted the invention of Genetic Programming (GP) \cite{icga85:cramer}, an adaption of the classic genetic algorithm \cite{Holland:GA} which evolves \emph{programs} instead of sets of numerical coefficients. Over the last twenty or so years, researchers have been exploring the ways that programs themselves can be evolved to solve all manner of problems. As we'll see later, some equal or outperform human invention. 

The value of machine learning is well understood, and accordingly many learning algorithms have been proposed, most from outside the realm of evolutionary computation. Some, such as neural networks, can already claim a variety of established applications within computer vision, notably character recognition. Most learning techniques, however, are constrained either by assumptions or applicability. Support Vector Machines for instance, are an excellent classification technique but can't develop algorithms, \foreign{per se}. Neural networks are somewhat limited in their ability to develop truly non-parametric solutions to problems.  Decision trees can make decisions based on features but cannot develop the features themselves. Genetic Programming is distinct from each: as an abstract learning system with no particular underlying assumptions about input data, it is uniquely placed to develop a whole range of different software, including all the examples above. As such, it seems appropriate that GP should be used for the automatic construction of vision systems. 

\section{Evolved Vision Software}
As we'll see later, Genetic Programming has already been put to work on a wide variety of problems in computer vision. Although a number of excellent solutions have been evolved by GP researchers, they are generally developed to prove that GP can solve problems within a particular domain. However, if one is to devise and implement a separate GP learning system for every situation, then one of the main advantages of machine learning -- reducing the human effort -- is lost.

In contrast, this thesis explores the viability of the GP as a domain-independent generator of visual routines; more specifically, the development of more complete, working vision systems -- something that isn't generally tackled by GP researchers. The author would define a working vision system as one that takes images as input and returns high-level output without requiring human intervention in the intermediate stages. The idea is to develop a framework that can learn to develop vision systems applicable to a range of different situations, with the proviso that all the task-specific information can be encapsulated within training data. The key is that the framework should not require manual tuning, adaptation or modification for individual tasks.

It is the aim of this thesis to explore the extent to which certain vision tasks can be learned automatically (or with minimal human input) by this generic architecture, and to see whether the GP-learned vision software is any good from a practical point of view. The feasibility, accuracy and capabilities of vision components developed using Genetic Programming will be described and analysed. 

\section{Challenges}
Some would argue that the use of Genetic Programming is a self-imposed challenge in its own right. As we shall later see, Genetic Programming does have some significant drawbacks not least its reputation, which is not entirely undeserved, for being slow and inefficient. 

A theme that runs through the entire course of this thesis concerns means by which  Genetic Programming can be made more efficient at solving problems involving vision. We shall also see how many of the parameters usually required to define a GP run can be dispensed with, turning the GP system into a more flexible learning tool.

Despite the drawbacks, one cannot deny the power of evolution as evidenced by nature. The potential of Genetic Programming to discover novel solutions by means we hadn't previously considered motivates this author to produce vision systems whose task-specific components are all evolved by GP, something that has not been done before.

\section{Contributions}
The author has made a number of novel contributions during the course of undertaking this research. These are outlined briefly below:

\begin{itemize}
\item The author has developed a complete Genetic Programming toolkit specifically for the purpose of solving vision problems, which compares favourably to a current, widely-used toolkit, ECJ \cite{ECJ}.
\dotfill p.\pageref{sxgp}
\\

\item The author has developed a classification scheme using Genetic Programming termed ``Intelligent Classification System'', which produces demonstrably better results on public datasets than the majority of other GP classification systems. The classification system makes pseudo-intelligent decisions, can run in parallel, and can solve problems with many classes.
\dotfill p.\pageref{ics}
\\

\item The author has proposed an extension to an existing GP classification representation to include confidence estimation. This makes it more suitable to certain problems and can improve classification accuracy when used by multiple classifier systems.
\dotfill p.\pageref{confidence}
\\

\item The author has described how many of the parameters in GP systems can be optimised or discarded such as to render GP into a suitably generic learning engine for vision problems
\dotfill p.\pageref{ch:gpcomparison}
\\

\item The author has developed a generic feature-detection approach which is capable of evolving components for a variety of domains, to a similar standard to those previously published by GP researchers.
\dotfill p.\pageref{ch:low-level}
\\

\item The author has developed a multi-stage vision framework which permits the creation of vision systems applicable to a variety of different tasks. The architecture is controlled by graphical user interface which permits end-users to define tasks and create training data visually. After the training data has been created, the interface initiates an intelligent learning process to evolve complete vision systems automatically.
\dotfill p.\pageref{ch:vision-system}
\\

\item The author has demonstrated the vision systems on a number of different vision tasks of a complexity not previously attempted by GP researchers.
\dotfill p.\pageref{vision-system-results}

\item The author's work on generating vision systems using Genetic Programming has been published in \cite{oechsle:vision-system}. By the time you come to read this thesis, two further papers will have been submitted. The first is a more thorough description to the author's vision system generator. The second concerns the author's approaches to classification by GP.
\dotfill p.\pageref{ch:low-level}
\\

\end{itemize}

\section{Thesis Structure}
This thesis concerns two areas of study: computer vision and evolutionary computation. Accordingly it begins with two literature surveys. In the following chapter the author introduces evolutionary computation in general and Genetic Programming in particular, and covers a number of techniques and algorithms employed by researchers in the GP community. In Chapter \ref{ch:cvsurvey} the wider field of computer vision and pattern recognition is introduced. A number of techniques commonly employed in computer vision are described and assessed; solutions developed by human intuition and machine learning are compared and contrasted.

The learning component of the author's system is based largely around the classification or labelling of feature vectors. Before discussing what features may be appropriate to describe the content of an image, Chapter \ref{ch:gp-classification} considers how to use Genetic Programming in order to generate classifiers in a general sense.

The field of information theory and pattern recognition is well established. There has already been mention of various machine learning techniques. In Chapter \ref{ch:gpcomparison} the results of the author's GP classifiers are compared to  other GP toolkits and other machine learning systems, in order to justify more fully the decision to use GP on a generic system. The chapter also describes in more detail the implementation of the author's GP toolkit.

Later chapters are concerned with the development of vision systems by Genetic Programming. We do not believe it possible to evolve a complete vision system during the course of a single evolutionary run; early it on it was decided to create a vision system comprising several stages. The first is concerned with low-level vision tasks, or the detection of features, and is discussed in Chapter \ref{ch:low-level}. The further stages of the author's vision system framework are presented in Chapter \ref{ch:vision-system}, which covers how GP can be used to produce more complete, standalone vision systems. It also describes how the process of creating them can be automated to the extent that non-expert users can produce vision software. Finally, in Chapter \ref{ch:conclusions} both the capabilities and limitations of the author's system are explored.

The reader is left with a question as this introduction draws to a close. How might one create a vision system, that can learn to analyse medical images, read car number-plates, recognise gestures in real-time or read sheet music, without any form of parameter tuning or expert knowledge? In this thesis we'll discover whether Genetic Programming can find an answer.

% Some of the below may be useful:
%The essential components required by the computer vision researcher in order to solve problems have already been described. Many of the hand-written algorithms employed to solve computer vision problems are mathematically complex and so require detailed analysis and understanding in order to be tuned to work effectively. The theory and reasoning behind each algorithm will naturally rely on certain assumptions. While appropriate for many applications, the assumptions may not hold true in all cases, which may cause the algorithm to perform outside of expectations.

%Outside of the academic community, the performance of any system is generally measured according to its effectiveness when working on a certain real-world problems. If this is to be considered the benchmark, it is perhaps wiser to concentrate on tailoring solutions to specific problems. Of course, this tailoring happens in practice, although it requires the time, expertise and experience of the computer vision researcher. Time may be in short supply. This motivates the use of machine learning algorithms which have the potential to perform such optimisations rapidly and automatically.

%\section{Work to be done}

%A Genetic Programming ``system'' is something of a misnomer. As has been described in this Chapter, the system actually comprises a large number of components. Each of these components inspires a separate sub-topic of research and various different algorithms have been developed for each. Island Selection, Elitism, each sound like plausible ideas but how much difference will they actually make on a generic system? The two available generation gap methods, generational and steady state, each appear to have advantages and disadvantages, however there has been little work to compare which is generally the most beneficial, at least in terms of generating computer vision programs. This two will be investigated on a variety of problems. The parameters needed to develop a reasonable generic system will be discussed and evaluated in later Chapters.

%One of the aims of this thesis is to develop as ideal a genetic programming system as possible for the purposes of generic computer vision. Subsequent chapters will descrbe experiments evaluating different components of the GP system against problems and computer vision benchmarks to determine the usefulness of each one. Our system will use and enhance the best of the research described within this Chapter and will be used for later experiments in developing vision systems using Genetic Programming, which is the topic of the remainder of this thesis.
