\documentclass[11pt,a4paper,titlepage,twoside]{report}
\usepackage{a4wide,dates}
\usepackage{graphicx}
\usepackage[T1]{fontenc}

\renewcommand{\rmdefault}{bch}  % use Charter for the body font
\renewcommand{\bfdefault}{b}    % Charter bold for bold text
\renewcommand{\sfdefault}{phv}  % Helvetica for sans serif text
\renewcommand{\ttdefault}{pcr}  % Courier for "teletype" text

\usepackage[british]{babel}

%\def\baselinestretch{1.4}

\begin{document}
%\include{front}

%\title{Towards the Automatic Construction of Computer Vision Systems}
%\author{Olly Oechsle}
%\date{October 2008}

%\maketitle

%\pagenumbering{roman}
%\tableofcontents
%\listoffigures
%\listoftables
%\chapter*{Acknowledgements}
%\begin{abstract}
%\end{abstract}

%\pagenumbering{arabic}

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

During the last decade or so, some applications of computer vision, such as the automatic recognition of car number-plates, and 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. Now that machines have been shown to be capable of performing useful vision tasks, so the list of other vision tasks we'd like them to perform for us grows ever larger, and with that comes a desire to produce such systems more easily.

Just as modern computing power makes heavy tasks such as image
processing increasingly practical, so it also makes the automatic learning of these systems more feasible. The solutions developed by some machine learning techniques have already been shown to produce excellent results on certain computer vision tasks such as the work by Viola and Jones on face detection \cite{EvoVision:Viola-Jones:2004}. 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), and whether the learned solutions are any good.

Just as there exist a wide range of techniques for extracting information from
images, there are many machine-learning learning algorithms which can be
employed. However, almost all of these are unable to operate directly on the
pixel data, requiring some preceding feature extraction stage.  One technique
that can work directly with the pixels is Genetic Programming (GP)
\cite{EvoVision:Koza:1992}, an adaption of the classic genetic
algorithm \cite{EvoVision:Goldberg:1989} to evolve programs (parse trees) instead of sets of numerical coefficients. In this thesis, we will explore how this promising and flexible learning algorithm
can be applied in order to learn vision systems automatically.

In order to be truly useful, our GP vision system should be capable of solving a
variety of problems to a reasonable standard. In this thesis, the feasibility, accuracy and
capabilities of vision systems developed using Genetic Programming will be
described, analysed and compared to other systems.

This research is concerned with the production of complete computer vision systems using
evolutionary learning techniques. Although a number of working solutions for
specific problems have been created by other researchers, they are often highly
specific to the problem domain. These solutions represent a proof of concept as
opposed to a working, generic system which can solve problems automatically without the need for a great
deal of human intervention. This thesis presents our work towards such a system.

\section{Contributions}
During the course of this research, the author has developed an architecture
which permits a variety of vision problems to be solved. The end-user need only
define the problem; and the work of designing the system is left to the
software.

Using this software, the author has produced solutions for several
multi-stage real-world problems, using a combination of GP evolved solutions and
standard image processing techniques.

The author has developed a new classification scheme using Genetic Programming,
termed GP by Partial Solutions, which has been shown to be significantly faster
to evolve than other Genetic Programming classifiers on certain
problems.

The author has investigated different means of ensuring that the data passed to
the learning system is optimal and compared them empirically.

The author has implemented a hybrid Genetic Programming approach combining the
representation and genetic operators of GP, with the proven classification
abilities of the ZCS classifier system and compared them to other classifier
representations using Genetic Programming.

\section{Thesis Structure}
In Chapter \ref{ch:background} the wider field of computer vision and pattern recognition is introduced. A number of techniques commonly employed in computer vision are described and assessed. A variety of Machine learning techniques are introduced, including Genetic Programming.

In Chapter \ref{ch:related} a critical assessment of current work in computer vision using Genetic Programming is provided with reference to the state of the art in the wider field. The use of Genetic Programming as a learning system is justified.

In Chapter \ref{ch:gp-framework} our Genetic Programming framework is introduced, together with a fuller description of the workings of each component in a GP system.

Chapter \ref{ch:gp-classification} covers how to use Genetic Programming in order to generate classifiers and other decision making software.

Chapter \ref{ch:vision-system} covers how GP can be used to produce a working vision system and Chapter \ref{ch:automation} describes how such a vision system's components can be automated as far as possible.

\chapter{Vision Research Techniques}
\label{ch:background}
Our experiments with learned vision software are occupy a small niche within the larger computer vision and pattern recognition communities. In the first half of this Chapter some of the basic algorithms, techniques and difficulties faced by computer vision researchers will be covered. In the second half a variety of machine learning techniques will be introduced. This Chapter concludes with an introduction and overview of Genetic Programming.

\section{Image Processing}

The saying that \emph{a picture is worth a thousand words} sums up the complexity inherent in imagery. The goal of most image processing or pre-processing algorithms is to discard most of this information in order to facilitate the extraction of useful pieces of information.

Any algorithm, learned or otherwise, is likely to go through some of the following steps of this classic bottom-up approach:

\begin{itemize}
\item Image Acquisition -- from a camera, which may work in the visible spectrum, infra-red, multi-spectral and so forth.
\item Preprocessing -- noise and other artifacts are removed from the image. The data may need to be transformed to make it suitable for further analysis by fulfilling certain criteria.
\item Feature Extraction -- basic features, such as lines or corners may be detected in the image, although a variety of different features also exist.
\item Detection or Segmentation -- unnecessary parts of the image are discarded allowing the recognition system to focus its efforts on a smaller area.
\item Recognition or Identification -- high level processing techniques are applied to the processed image in order to extract useful information.
\end{itemize}

\subsection{Pre Processing}
Many of the early approaches, perhaps typified by the convolution with masks of
the 1970s and early 1980s, did little more than emphasize features for
subsequent human processing. These were refined into techniques such as edge (by
Sobel and subsequently Canny \cite{Canny:1986}) and corner detectors
(such as Plessey) in the late 1980s and early 1990s. 

\subsubsection{Noise Removal}
A characteristic of any signal captured using an electronic sensor is its liability to a degree of noise. This is due to the random fluctuations in electric current caused by the discrete nature of electrons themselves. As noise is usually at a constant level, it is most apparent when the signal itself is relatively weak, for instance in taking pictures at night time.
As noise can significantly effect the accuracy of subsequent processing, it is desirable to minimise noise as much as possible, while maintaining the integrity of the original image. Various techniques exist to do this; three are introduced briefly below.

\paragraph{Linear Filters}
One of the simplest noise-reduction techniques is a linear filtering technique which uses a Gaussian convolution mask to calculate the weighted average of a pixel's value together with those of its surrounding neighbours and thus reduces large differences in intensity caused by noise. However, legitimate differences in the signal level, such as those found by edges in the image are also diminished which causes the image to lose some definition.

\paragraph{Median Filters}
A better, non-linear technique is to use Median Filtering (REF), which chooses the \emph{median} value of a pixel and its neighbours. As this technique redistributes existing intensities rather than creating new ones it doesn't produce the blurring effect of the Gaussian filter and helps to maintain definition. Although median filtering requires more computation (to calculate the median it is necessary to sort the values), it is a preferred technique in computer vision applications.

\subsubsection{Colour Constancy}
The human eye is the benchmark by which all computer vision software is ultimately judged. Each eye is such a masterpiece of engineering that some serious issues do not even become apparent until researchers try to emulate human perception using computer software. One such problem is named colour constancy and relates to the perception of the true differences between colours and shades of materials, regardless of their illumination. The problem is demonstrated by Adelson's Same Colour illusion (REF) (shown in Fig. \ref{fig:illusion}) which shows a checker board which is partly in shadow thanks to a cylinder on the upper right. Two squares are marked on the board: A is an instance of a white square, and B an instance of a darker square. To the human eye there is nothing odd about this scene, A and B a perceived clearly as distinct shades of grey. However, the two checkers actually share exactly the same colour.

\begin{figure}
\begin{centering}
\includegraphics[width=0.5\textwidth]{grey_square_illusion}
\par\end{centering}
\caption{The Grey Square Illusion: Squares A and B have the same colour}
\label{fig:illusion}
\end{figure}

Problems such as this present a major problem for computer vision software. Shadows and other lighting effects are inherent in the real world, unless the illumination in the world of the vision system is carefully constructed and calibrated. Any serious application must be able to take illumination effects such as this into account. The human eye clearly has no difficulty in differentiating the checkers, but how is a machine to solve the problem when analysis of the the two squares reveals they have exactly the same colour? Any technique involving thresholding will fail to identify all of the white tiles from the grey ones, so a better algorithm is needed. The answer, of course, is to be found in the context in which the checker is found, but the process of providing context to the computer is in itself non-trivial.

The discrepency arises in the first place from the perception of colour which is dependent on the wavelength of light. Under different lighting conditions the same object will reflect light at different wavelengths. The problem is how to discard the effects caused by the illumination. Various solutions have been proposed:

\paragraph{Land's Retinex Theory}

\paragraph{Gamut Constraint Methods}

\paragraph{White Patch}
White Patch Retinex Algorithm

\paragraph{Gray World Assumption}
(and others, see Ebner's colour constancy paper for more)

\subsubsection{Level Set Methods} 
... information to appear here.

\subsection{Feature Extraction}
The second stage in our bottom-up approach is to identify parts of the image which may relate to something interesting. A good heuristic for doing so is the search for the boundaries between objects, otherwise known as edge detection. Other operators may search for lines and other definable shapes in the image. Of course, the problem remains as what to do with edge or shape information once it has been located.

\subsubsection{Edge Detection}
A classic problem in computer vision is the detection of edges within an image. Although it is quite easy to identify the cases where a computer makes a mistake in this regard, it is less easy to identify just where those ``true'' edges are in an image. The answer will vary from image to image and from person to person. All edge detection techniques therefore need to use some kind of threshold in order to distinguish ``important'' edges from the rest.

\paragraph{The Marr-Hildreth Operator}
An early operator, invented by David Marr and Ellen Hildreth[REF] uses Laplacian or Gaussian convolution on the image to approximate a difference-of-gaussians function. The algorithm searches for zero-crossings which relate to edges. The algorithm can return false edges and was largely replaced by the detector of Canny (1986).

\paragraph{Canny's Edge Detector}
The well-known detector by Canny \ref{Canny:1986} detects edges using several stages of processing. First noise is removed from the image using a Gaussian convolution mask. The intensity gradient of the image is then measured in order to find candidate edges. Separate convolution masks (such as Sobel's (REF)) are used to identify horizonal and vertical edges; edges at angles in-between are assumed to involve a combination of the two. A search for the local intensity maxima is then performed to thin each edge down to single-pixel thickness. The identification of edges is left to a stage involving thresholding with hysteresis, consisting of two thresholds. This allows both strong and feint edges to be connected together. The result is a binary image consisting of only edge and non-edge pixels. Canny's detector remains a benchmark for the discovery of edges in an image.

\subsubsection{Corner Detection}

\paragraph{Plessey Corner Detector}

\paragraph{Wang Brady Corner Detector}

\paragraph{SUSAN Corner Detector}

\paragraph{Moravec's ``Points of Interest''}

\subsubsection{Hough Transforms}
The Hough transform is a technique used for detecting lines and other shapes among the edges in an image. it is dependent on representing a line in terms of its angle $\theta$ and distance $r$, as in the following equation:

\[
x\sin\left(\theta\right)+y\cos\left(\theta\right)=r\]

Plotting a given $(x,y)$ point with respect to theta yields a sinusoidal curve. Although the curves for different points along the line will have different frequencies, each will cross at a spot corresponding to the common values of $\theta$ and $r$. If the curves are each plotted onto a two dimensional accumulating array, the peaks in the array will represent the equations of lines in the image. Other shapes can also be parameterised in a similar way to lines, so the Hough transform is capable of detecting a variety of shapes.

\subsubsection{Basic Features}
How many lines are there in a human face? A single one around the whole face? Separate ones for each eye? Nose? Mouth? Wrinkles? Hairs? There is no correct answer, so sometimes the information yielded from line or edge detection is not that useful. Some information, however, can define a face pretty well. Its a fair guess that of two adjacent rectangles, one over the eyes and one on the forehead, the one over the forehead will often have less variance in intensities. Low level information like this can be found using simple features based on pixel intensity information. These features can give important clues about texture or other features not as strongly indicated as edges or lines. 

\paragraph {Colour Features}
... discuss colour information

\paragraph{Rectangular Pixel Features}
... Information on haar features and dissociated dipoles.

\paragraph{GLCM Features}
... Information on Grey Level Co-occurence matrices

\subsection{Feature Selection}
Before features can be used in classification, it is sometimes necessary to involve an additional stage of feature selection in which a decision is taken as to which features are suitable for solving a particular task and which are unlikely to be helpful in classification.

Additionally, in the case where the features are parameterised (the haar features are defined in terms of the size of rectangles and other factors and thus represent a large ``family'' of potential features) it may be necessary to search for good values using techniques, for instance using a Genetic Algorithm. These techniques will be discussed in depth later.

Some linear algorithms, such as Neural Nets, are susceptible to unhelpful features, and generally also require the features' outputs to be normalised so that the magnitude of values returned by a particular feature doesn't effect the output. In non linear techniques, such as Genetic Programming, it is not always necessary to perform this stage. Indeed the GP process offers several different means of discovering acceptable parameters while the evolution is in progress. However the concept of ``dimensionality reduction'' -- where irrelevant features which would otherwise add noise to the training data while adding little new information are removed -- can certainly help speed up the search process. 

In many cases it may be the computer vision researcher who decides which features should be included, based on intuition or experience. However, sometimes the scale of the data is overwhelming or the correlations difficult to distinguish. For this reason various algorithms have been developed in order to perform this task automatically, including:

\subsubsection{Linear Discriminant Analysis (LDA)}
The aim of LDA (in its simplest form) is to find the one dimension which best
separates examples from two classes. This makes LDA suitable for feature
extraction. More information to follow here. Also to mention Principal Component
Analysis.

\subsubsection{Princical Component Analysis (PCA)}
... information about PCA

\subsubsection{Kernel Discriminant Analysis}
... information about KDA

\subsubsection{Branch and Bound}
... information to follow

\subsubsection{Floating Search Method}
... information to follow

\subsection{Classification Techniques}
The task of classification is to discover the ways in which numeric information extracted from the image are somehow representative of its content. The job of the computer vision researcher is then one of an information theorist: finding the patterns and clues in the data which can be used to define parts of the image.

Most problems in computer vision involve some degree of decision making. Vision systems evolved using Genetic Programming are no exception. Decision making may take various forms, progressing through finer and finer distinctions:

\begin{itemize}
 \item Detection or Segmentation -- On the basis that colours or texture can be distinguished with reasonable accuracy and that it is possible to extract certain features from the image, it is often useful to perform a detection phase in which parts of the image are discarded. More detail is provided in Chapter \ref{ch:vision-system}
\item Classification -- Where an object is labelled as being a member of a particular group or class.
\item Recognition -- Where a unique object is distinguished from other members of the same class.
\end{itemize}

Many algorithms have been developed in order to learn how to take these decisions in an automatic manner. Some of the well known classification algorithms are introduced briefly below. Notable by their absence here are machine learned classification algorithms which will be discussed later in this Chapter.

\subsubsection{Nearest Neighbour Classifiers}
The Nearest Neighbour family of classifiers work in non-linear space. When presented with a new example, they take a decision based on the existing, known examples in a data base each of which have been pre-labelled. The algorithms work based on the assumption that data belonging to the same class will belong in clusters. 

Euclidean distance is used as a common metric for the distance between two
examples, although other distances may be employed, each with their advantages
and disadvantages.

K Nearest Neighbour works by finding the $k$ nearest neighbours to the new
sample. $k$ is usually an odd number in order for it to be possible to always have a majority decision, at least in binary cases. The majority class represented by the
neighbours is chosen. Larger values of K increase the robustness of the
algorithm to noise and outling values, although distinctions of samples located between adjacent classes become harder to make. The K Nearest Neighbour algorithm requires a large data base of correct samples, and each of these needs to be evaluated in order to classify a new sample, so it is not always the most efficient means of making classifications. Neither is it capable of learning the relationships between features that indicate a particular class. Nonetheless, it is a capable classifier and often performs very well in comparison to other, more complex algorithms \cite{king95statlog}.

Related to K Nearest Neighbour is the K means clustering technique which is a form of unsupervised learning. More information to follow here.

Linear Support Vector Machines (SVM) work in a similar fashion. In SVMs, the
items of training data act as "support vectors", through which a plane which
separates two classes most satisfactorily is chosen. In a maximum margin classifier a
margin is calculated on each plane which represents the "thickest" it can be
before hitting a point. The plane with the largest margin, and therefore the
biggest gap between classes is chosen.

\subsubsection{Bayes' Classifiers}

Bayes' Classifiers use a simple statistical model of probability to
make classifications. The model consists of a measure of prior probability
(the known size of each class) and the likelihood of a new instance
with respect to a given class $c$, that is its similarity to existing
instances belonging to $c$.

The commonly used, \emph{naive,} version of Bayes' classifiers assumes
that all parameters are independent, otherwise some factors would
have an undue influence on the decision. Complete parameter independence
is rarely the case in real world situations, however the classifier
still performs well in general.

As the classifier's raw output is a probability, rather than a \emph{hard}
classification, a measure of the classifier's confidence can also
be computed.



\subsubsection{Decision Trees}
A decision tree is a structure which represents the likely outcomes based on a series of decisions. Decision trees may also be used as a predictive model which can be used to make classifications. In such trees, each branch represents a decision, which is taken depending on the values in a given input vector, and each leaf represents an outcome, which is usually a class label. Various algorithms have been developed in order to produce such a tree (or graph) automatically, and are presented below.

\paragraph{Classification And Regression Trees (CART)}
... information to follow

\paragraph{ID3}
... information to follow

\paragraph{C4.5 and C5.0}
... information to follow

\subsubsection{Maximum Likelihood Classification}
... information to follow

\subsection{Techniques for Motion Sequences}
Videos sequences can, of course, provide much more information than a single
frame. Various problems exist in this respect, namely to track objects moving
within or between sequences of video, or to recognise in some way the behaviour
or gait inherent in such motion.

\subsubsection{Tracking}

\paragraph{Iterative Tracking}
Tracking schemes are traditionally posed as a two step process. The first is to
initialise the tracker, by first locating the object to track. The second is to
iterate on the object's local area in order to follow its process. The tracking
may consist of a local search which maximises some fitness function.

\paragraph{Lucas-Kanade Tracking}
A second approach is to detect motion between frames by subtracting one image
from the other and find the regions where the change is most pronounced. This
works well for detecting the motion itself, but runs into problems when multiple
subjects are on the move.

\paragraph{Kalman Filters}
Kalman filters represent a simple model of object dynamics which estimates the
movement of a particular object given its previous history, with an associated
degree of certainty.

\subsubsection{Gestures}
The study of motion of human hands permits the interpretation of gestures which
in simple forms permit users a different means of interacting with a machine,
and in more complex usage form a complete means of communication. 

\paragraph{Hidden Markov Models}
Thad Starner \cite{starner98realtime} used HMMs for real time ASL Recognition.

If the object in question is likely to change in shape, then a more flexible
approach is required.

\paragraph{Deformable Contours}
.. information to follow

\subsection{Probabilistic Relaxation}
.. information to follow

\subsection{Graph Matching}
.. information to follow

\section{Overview of Machine Learning Techniques}
The techniques discussed briefly at the beginning of this Chapter provide essential components
for the computer vision researcher. However, many are often mathematically complex and so require detailed analysis and understanding in order to be tuned to work effectively. Some, such as Bayes' classifiers, rely on certain assumptions which may not be suitable in all cases.

As systems are generally measured on their accuracy when put to use on real world problems, it
is perhaps wiser to concentrate on tailoring solutions to specific problems. This tailoring happens in practice, although it requires a great deal of time from the computer vision researcher. This motivates the use of machine learning algorithms which have the potential to optimise solutions more rapidly.

There exist many different techniques for representing solutions to problems using computer software. The goal of machine learning techniques is to optimise these representations in such a way as to produce a viable solution. Three classes of machine learning will be introduced below:

\subsection{Neural Networks}

Neural Networks take their inspiration from biology. A typical neural net consists of small activated processing units, or neurons, connected together via weighted connections (aka. synapses), in a structure resembling what we presume is sufficient basis for a primitive brain.

One of the most widely used neural net structures is the Multi Layer Perceptron (MLP) [REF] which consists of an input layer, an output layer, and one or more hidden layers of neurons in between. Each neuron in one layer is connected to every neuron on the next layer, with signals passing forward through the network.

The weight given to each connection determines how much influence one neuron has over another and thus encodes the logic which determines the outputted value(s). Various learning techniques ( such as back propagation ) may be employed to adjust these weights such that they become capable of processing a set of input neurons into useful output.

Well suited to the field of computer vision, due to its ability to learn without supervision, is a sub set
of Neural Nets named Kohonen Maps. The map consists of a single-layer feedforward network with each input connected to all output neurons which may be organised in a 2D or 3D lattice. The algorithm learns to associate different regions of the output lattice with similar inputs. This is motivated by a similar
structure in the cerebral cortex of the brain where neighbouring points in the primary visual cortect correspond to neighbouring points in the retina, a phenomenon known as the retinotopic map {[}reference].

In contrast with the complexity of the human brain, it has been shown that Neural Networks can discover good solutions to problems while using only a small number of neurons. Subsequent interrogation is fast and takes a fixed period of time, making them suitable for use in fields such as robotics where real-time processing is desirable.

The case against Neural Networks includes their linearity and their sensitivity to unusual or outlying data. \emph{This point to be expanded}.

\subsection{Evolution Strategies}
Almost as soon as the computer age dawned, in the middle of the 20th Century, researchers became interested in using machines to simulate natural processes. It soon became apparent that evolutionary techniques could potentially be used to solve engineering problems. Once of the first instances was the development of Evolution Strategies, an optimisation technique, by Ingo Rechenberg in the 1960s. 

In Evolution Strategies, each individual is represented as a vector of real values. The values are used to make decisions and are problem specific. The task of finding optimal values is left to the Evolution Strategies process whose search is driven by a mutation operator which changes the values in the vector by adding a normally distributed random value to each.

In its simplest form $(1+1)$-ES, the evolution strategies learning environment consists of two individuals - a parent and child who was produced from the parent using the mutation operator. If the child's is less capable than the parent it is discarded, and another child is produced. The process continues until the child is able to outperform the parent, at which point the parent is replaced by the child and the process continues. In this form of evolution, the child competes directly with its parent. As there is essentially no variance in the population, this amounts to a hill-climbing operation that may become stuck in local minima. In later versions $(1+\lambda)$-ES, the parent produces $\lambda$ children, which compete with each other. The best of the children replaces the parent, even if the child is less capable than the parent.

\subsection{Genetic Algorithms}
Largely replacing Evolution Strategies were Genetic Algorithms, developed by John Holland and his students in the early 1970s [REF]. Genetic Algorithms use operators inspired by our knowledge of genetics, namely crossover, a more realistic mutation and inversion. Instead of deterministic selection used by Evolution Strategies, Holland suggested simulated natural selection procedures which would maintain diversity in the population instead of greedily choosing the best on each occasion. In essence Holland was more interested in the study of natural adaptation, and his technique was a much closer abstraction of biological evolution than evolutionary strategies. With it came additional complexity, and work on Genetic Algorithms had to remain largely theoretical until the late 1980s when the computing power became sufficient to host the evolution of Genetic Algorithms.

... more information to follow

\subsection{Simulated Annealing}

... more information to follow

\subsection{Michigan Classifier Systems}
\label{sec:Michigan-Classifier-Systems}

Genetic Algorithms provided the learning component for a separate system, invented by Holland (1986), and later refined by Wilson (1994, 1995). A starting point for many classification algorithms is the architecture
introduced by Holland \cite{holland1992} who proposed a system consisting of a population of rules {[}P], each comprising a condition and associated action, which compete in order to correctly label a given input vector.
{}``Good'' rules, which contribute to correct classifications, accumulate credit from the environment by way of reinforcement, constributing to the {}``strength'' of the rule. A Genetic Algorithm is used to
improve the accuracy of rules in the system.

The condition, which is used to match the input vector, is represented by a fixed length bit string. In the case where the input vector may contain either 1 or 0, the bit string is created from the binary alphabet
plus a wild card: $\{0,1,\#\}$. The wild card, or {}``don't care'' symbol, $\#$ permits general conditions, which match more than one input, to be formed. For instance the bit string $``01\#"$ would
match two input vectors: $``010"$ and $``011"$. 

All rules which match a given input are added to a {}``match set'' {[}M], from which an action is chosen with probability proportional to the sum strength of the rules which advocate the action ( the rules
are placed in an action set {[}A] ). In the simplest case the action consists of a discrete label ( $\{0,1\}$ in the binary case) for classification of the input vector.

In the event that the match set {[}M] is empty, a {}``covering operation'' is invoked where a new rule is created with a matching condition bit string and a random action, replacing another rule in the classifier,
after which point the algorithm continues as normal. More detail about this kind of classifier system is presented in the next two sections which concern two implementations of Holland's Classifier System, ZCS and XCS.

\subsubsection{Zeroth Level Classifier System (ZCS)}

Holland's specification defined a number of complex interactions and
mechanisms which are difficult to understand and model. A basic system
was developed by Wilson \cite{wilson94zcs} (named ZCS) as a baseline
implementation of Holland's ideas. A few further details of ZCS are
presented below:


\paragraph{Reinforcement in ZCS}

Reinforcement in ZCS is as follows. A fraction of the strength $\beta$
$(0<\beta\leq1)$ of each member in the action set {[}A] is removed
and placed into a common, empty {}``bucket''. Any immediate reward
$r_{imm}$ from the environment as a result of taking the action,
a quantity is added to each classifier in {[}A], the quantity being
$\beta r_{imm}/[A].size()$. Classifiers in the action set $[A]_{-1}$have
their strengths incremented by:

\[
\frac{\gamma\times bucket}{\left|[A]_{-1}\right|}\]


Where $\gamma$ $(0<\gamma\leq1)$ is a discount factor. After which
point {[}A] replaces $[A]_{-1}$ and the bucket is emptied. Wilson
stated that the discount factor should be significantly less than
1 in order for the learning process to proceed.

Matchinng classifiers in {[}M] which suggest actions other than the
selected one are weakened by $\tau$, which is similar in magnitude
to the learning rate $\beta$.


\paragraph{Learning in ZCS}

Although classifiers may initially be created by the {}``covering''
operation, they are improved using a basic Genetic Algorithm. The
GA is executed at a given rate throughout the learning cycle. Each
time it is invoked, two classifiers are selected from the population,
with probability proportional to their strength. Crossover and / or
mutation is performed to generate two children, and the two children
are inserted back into the population. If the population is already
{}``full'', then two other classifiers are first removed with probability
inverse of their strengths. Therefore good classifiers are able to
reproduce more often.

\paragraph{Extensions to ZCS}

Wilson suggested the use of \emph{s-expressions }(or Genetic Program
parse trees) instead of bit strings. Ahluwalia and Bull \cite{ahluwalia:1999:agpcs}
did use Genetic Programming to implement this in their experiments
discovering feature detectors. Lanzi \cite{lanzi:1999,lanzi:1999b}
implemented these ideas in more detail, moving from the bit-string
representation to a {}``messy'' GA, to conditions encoded using
Genetic Programming parse trees {[}results?].

\subsubsection{Classifier Fitness Based on Accuracy (XCS) }

In ZCS, a classifier's strength is measured by its ability to correctly
identify inputs and recieve payoff. It can only do this once it is
a member of {[}A], however its likelihood of joining {[}A] is also
dependent on its strength. Wilson \cite{wilson95classifier}questioned
the validity of this scheme, stating that if different niches within
the environment had different payoff levels, the system would unfairly
encourage classifiers which identify particularly generous payoffs.

Wilson theorised that classifiers using a high number of wild cards
(\#) would appear in more match sets {[}M] and therefore have more
chances to receive payoff and increase their strength.

To address these problems, Wilson designed an improvement to ZCS called
XCS, which used a different approach to measuring the fitness of a
classifier which would be a measure of the \emph{accuracy} of the
prediction rather than the prediction itself.

The prediction strength would still be used to choose the action set
{[}A], but the probability of the classifier being selected by the
Genetic Algorithm for reproduction would be dependent only on the
fitness. Wilson stated that this which would pressurise the creation
of accurate generalisations.

Secondly, he proposed a \emph{niche-based} Genetic Algorithm to treat
match sets {[}M] more fairly.

\paragraph{XCS Parameters}

XCS uses a number of parameters in its algorithms. These are summarised
here for reference.

\begin{center}
%
\begin{table}
\begin{centering}
\begin{tabular}{|c|c|c|}
\hline 
Variable & Default & Description\tabularnewline
\hline
\hline 
$p_{j}$ &  & The {}``strength'' of the prediction\tabularnewline
\hline 
$\varepsilon_{j}$ & 0.0 & Prediction error\tabularnewline
\hline 
$\kappa_{j}$ &  & The accuracy of the classifier given the error\tabularnewline
\hline 
$\kappa'_{j}$ &  & Relative accuracy of the classifier to other members of {[}A]\tabularnewline
\hline 
$F_{j}$ & 0.01 & The fitness of the classifier, based on the accuracy\tabularnewline
\hline 
$\alpha$ & <1 & Falloff parameter for calculating accuracy from error $(0<\alpha\leq1)$\tabularnewline
\hline 
$\beta$ & 0.1 & The learning rate parameter $(0<\beta\leq1)$\tabularnewline
\hline 
$\chi$ & 1 & Probability of crossover on two classifiers in {[}M]\tabularnewline
\hline 
$\mu$ & 0.05 & Probability of mutation on two classifiers in {[}M]\tabularnewline
\hline 
$\gamma$ &  & Discount factor used to calculate $P$\tabularnewline
\hline 
$N$ &  & Maximum number of rules in the population\tabularnewline
\hline 
$\theta$ & 50 & The number of iterations before the GA is evoked on {[}M]\tabularnewline
\hline 
$\delta$ & 0.1 & Value of the fraction in deletion method (2)\tabularnewline
\hline 
$\varepsilon_{0}$ & 0.01 & Error threshold beneath which accuracy is set to 1\tabularnewline
\hline
\end{tabular}
\par\end{centering}

\caption{Parameters used in XCS}
\label{tab:xcsparameters}
\end{table}

\par\end{center}


\subsubsection{XCS Fitness Calculation Procecure}

In normal ZCS a condition C causes an action A, which in turn predicts
a payoff P via its prediction\emph{ strength}. This strength both
predicts payoff and functions as the classifier's fitness for the
Genetic Algorithm. In XCS, there are several fitness parameters associated
with each classifier:

\begin{itemize}
\item Fitness $F$ which tends towards the \emph{relative accuracy }which
is calculated from the...
\item Prediction error $\varepsilon$, which is calculated as the difference
between the discounted reward (P) and the...
\item Predicted payoff $p$
\end{itemize}
Reinforcement occurs by updating $p$, $\varepsilon$, and $F$, and
occurs every time a classifier belongs to the previous action set
$[A]_{-1}$ (or {[}A] in single step problems). 


\paragraph{Adjusting Fitness F}

Fitness is a metric which defines the classifier's accuracy relative
to the other classifiers in the set. For each classifier in $[A]_{-1}$,
the fitness $F_{j}$is recalculated using the current value of $\varepsilon_{j}$
in three steps:


\paragraph{Calculating the accuracy}

The accuracy $\kappa_{j}$ of the classifier is calculated, based
on the prediction error $\varepsilon_{j}$ and the error threshold
$\varepsilon_{0}$:

\[
\kappa_{j}=exp\left[(ln\alpha)(\varepsilon_{j}-\varepsilon_{0})/\varepsilon_{0}\right]\]


Alternatively:

\[
\kappa_{j}=\alpha\left(\frac{\varepsilon_{j}}{\varepsilon_{0}}\right)^{-n}\]


For $\varepsilon_{j}>\varepsilon_{0}$, otherwise $1$. This function
weights the accuracy highly for low values of $\varepsilon_{j}$ with
a sharp drop-off for higher values (depending on the value of $\alpha$).
The second function is displayed graphically in Figure \ref{fig:xcs-accuracy-graph}
below.

%
\begin{figure}
\begin{centering}
\includegraphics[width=0.5\textwidth]{accuracy-from-error}
\par\end{centering}
\caption{An accuracy function in XCS}
\label{fig:xcs-accuracy-graph}
\end{figure}



\paragraph{Adjusting Fitness}

The \emph{relative }accuracy $\kappa'_{j}$ for the classifier is
computed by dividing its accuracy by the total of accuracies in the
action set.

Relative accuracy adjusts the fitness $F_{j}$. If fitness has been
adjusted at least $\frac{1}{\beta}$ times, $F_{j}\leftarrow F_{j}+\beta\left(k'_{j}-F_{j}\right)$
otherwise $F_{j}$ is set to the average of the current and previous
values of $\kappa'_{j}$.


\paragraph{Calculating the discounted reward P}

Take the maximum prediction value $p(a_{i})$ value from the prediction
array. Discount it by multiplying by $\gamma$, and add to it any
immediate external reward from the \emph{previous time step}. The
resulting quantity is named $P$.

\[
P=max\left(p(a_{i})\right)\gamma+r_{imm_{-1}}\]



\paragraph{Adjusting the prediction error $\varepsilon_{j}$}

$\varepsilon_{j}$ is adjusted using $P$ and the current value of
$p_{j}$, this is done by adjusting $\varepsilon_{j}$ so that it
tends towards the absolute difference $\left|P-p_{j}\right|$:

\[
\varepsilon_{j}\leftarrow\varepsilon_{j}+\beta\left(\left|P-p_{j}\right|-\varepsilon_{j}\right)\]


Only if the classifier has been adjusted at least $1/\beta$ times.
Otherwise the new value is the average of the previous and current
values. Therefore, if the difference between $P$ and $P_{j}$ is
large, the error will increase and the fitness will decrease.


\paragraph{Adjusting $P_{j}$}

$P$ is then used to update the predictions of the classifiers in
$[A]_{-1}$using the following rule:

\[
p_{j}\leftarrow p_{j}+\beta\left(P-p_{j}\right)\]


Only if the classifier has been adjusted at least $1/\beta$ times.
Otherwise the new value is the average of the current and previous
values of $P$. This is called Moyenne Adaptive Modifiee (MAM), and
exists to ensure that the initial (arbitrary) value of $P_{j}$ can
move to its {}``true'' position first.


\paragraph{Niche Based Genetic Algorithm}

The GA is run in a match set if the number of time-steps since the
last GA in that match set exceeds a certain threshold. Each classifier
is time stamped at birth with the current time-step. When a match
set is performed its \emph{average} time stamp is calculated. The
GA is executed if the average time is older than the threshold$\theta$. 

This \emph{niche} based GA, (as opposed to the \emph{panmictic} GA
in ZCS which operates on the population at large), helps to remove
competition between niches that would cause high payoff actions to
dominate the population. It may also improve the learning rate as
crossover between necessarily similar classifiers in a match set is
more likely to be lress destructive than crossovers between possibly
completely unrelated individuals.

As in ZCS the genetic algorithm works on the match set {[}M] from
which two classifiers are selected using fitness proportional selection.
Crossover is performed on the copies with probability. If {[}P] contains
fewer than $N$ members, no deletion need occur to make room. For
the deletion scheme when this is not the case, see Section \ref{sub:Extended-Deletion-Scheme}.


\paragraph{Macroclassifiers}

When a new classifier is generated by the Genetic Algorithm, the population
is scanned to see if another one exists with the same condition and
action. If this is the case then the \emph{numerosity} on the existing
classifier is increased by one, rather than having two copies. This
allows the number of classifiers, $N$ to remain constant, but the
working number of classifiers actually decreases so performance improves
as better generalisations are discovered.

If a macroclassifier is selected for deletion its numerosity is decreased
by one, if numerosity is 0 then it is removed from the population
altogether.


\paragraph{Extensions to XCS}

\subparagraph{Genetic Algorithm}

Wilson later suggested an improvement \cite{wilson98generalization},
to conduct the GA on the action sets {[}A] and $[A]_{-1}$instead
of the match set {[}M]. Wilson stated that if a match set {[}M] is
to contain accurate and maximally general classifiers for all available
actions, they would often have different conditions. Therefore if
these are bred together, the crossover operator may still be destructive.
Therefore crossover should only occur on actions with similar conditions
and similar actions.

\subparagraph{Subsumption Deletion}

Wilson proposed a nice addition to his system \cite{wilson98generalization},
in which a new classifier whose condition is subsumed by an existing,
accurate, more general classifier, the new classifier is replaced
with a clone of the subsuming classifier, that is to say that the
subsuming classifier becomes a macroclassifier. This would remove
\emph{unnecessarily }specialised classifiers.

Wilson suggested that when two parents produce an offpspring, the
offspring should be checked to see if the child's condition is logically
subsumed by either of its parents' conditions. If this is the case
then the offspring is removed and the subsuming parent's numerosity
is increased by one.


\paragraph{Pitfalls using XCS}


\subparagraph{NB: Classification Accuracy}

Kovacs and Kerber \cite{kovacs-high2004} demonstrated Wilson's argument
that high classification accuracy alone does not imply effective genetic
search. The covering algorithm in ZCS and XCS allows the system to
improve without the use of the evolutionary algorithm. They showed
that XCS was able to provide good results on boolean multiplexer problems
even when the GA was complely turned off although it requires a much
larger population of rules.


\subparagraph{Extended Deletion Scheme \label{sub:Extended-Deletion-Scheme}}

Kovacs \cite{kovacs99deletion} pointed out that the deletion schems
in XCS is the same as that in standard Genetic Algorithms, despite
XCS having a different evaluation mechanism. An XCS classifier can
only be fully evaluated after many interactions (at least $1/\beta$)
with the environment. Therefore the outcome of removing classifiers
with regard only to their fitness may actually penalise \emph{new}
individuals instead of truly unfit ones. He suggested a system to
protect poorly evaluated chromosomes and demonstrated that it can
outperform both of Wilson's original techniques.

Wilson suggested two deletion techniques for XCS. The first, which
applies no deletion pressure on unfit individuals is as follows:

\begin{quotation}
{}``1. Every classifier keeps an estimate of the size of the match
sets in which it occcurs. This estimate is updated every time the
clasifier takes parts in an {[}M] using the MAM%
\footnote{Moyenne Adaptive Modifiee%
} technique with rate $\beta$. A classifier's deletion probability
is set proportional to the match set size estimate, which tends to
make all match sets have about the same size''
\end{quotation}
The second technique was a slight modification on the first so that
unfit individuals are deleted with higher probability.

\begin{quotation}
{}``2. The classifier's deletion probability is as in (1), excepts
if its fitness is less than a small fraction $\delta$ of the population
mean fitness. Then the probability from (1) is multiplied by the mean
fitness divided by the classifier's fitness''
\end{quotation}
Kovacs suggested that each of these techniques is an extreme, with
one which doesn't punish unfit classifiers at all, and the second
one which punishes all unfit classifiers, which may prevent new classifiers
from becoming established.

He proposed a third scheme:

\begin{quotation}
{}``3, A hybrid in which (1) is used until a classifier has been used on $n$ occasions, after which (2) is used''
\end{quotation}
He showed that this scheme performed better on both the 6-bit-multiplexer problem and the even parity problems (both of which are single-step problems). As the problems in computer vision covered by this project are largely single-step problems, we will also implement this modification.

\paragraph{Experiments}
The results from experiments by Wilson using XCS have generally concerned boolean multiplexer problem, or a multi-step animat problem in a {}``woods'' environment. Each of these problems is noiseless and has a small number of inputs. {[}Make mention of non-markovian environments].


\subsection{Genetic Programming (GP)}
While Genetic Algorithms presented a leap forward in the capabilities of evolutionary learning, their inherently linear nature remains a limitation which is apparent in XCS and other systems. Genetic Programming is an extension of the GA algorithm to represent individuals not as vectors of values, but as parse trees which can represent pretty much any kind of logic.

Although various researchers investigated the automatic evolution of programs during the 1980s, the modern concept of Genetic Programming is thanks to the work of John R. Koza who produced a tome of information on the subject in the early 1990s.

The primary diference between Genetic Programming and Genetic Algorithms is the differentiation between phenotype and genotype. In nature -- and genetic algorithms -- these are distinct. The genotype refers to the encoding of the solution, in nature this is the genetic material, DNA. The phenotype refers to the realisation of that solution which bears no resemblance to the phenotype. In Genetic Programming however they are the same, as candidate programs being evolved are each solutions to the problem, to a greater or lesser extent.

\subsubsection{The GP Algorithm}

... more information to follow

\paragraph{Additions to the Genetic Programming Methodology}
\subparagraph{Strong Typing}
Montana  \cite{EvoVision:Montana:1993}
\subparagraph{Automatically Defined Features}
Andre \cite{EvoVision:Andre:1994}
\subparagraph{Coevolution}
Used by Roberts, Claridge \cite{EvoVision:Roberts-Claridge:2005} for Object Detection
\subparagraph{Grammatical Evolution }
Using a grammar to abstract the learning process. Michael O'Neill, Anthony Brabazon. Grammar can be co-evolved which makes the system highly adaptive.
\subparagraph{Partial Solutions}
My own approach \cite{oechsle:vision-system}

\subsection{AdaBoost}
Adaboost is a meta learning algorithm, developed by Freund and Schapire \cite{EvoVision:Freund-Shapire:1996}  which uses statistical methods to improve the output of classifiers produced using a separate learning system. A boosting system, it improves the overall output without the need to increase the number of training examples and works by assigning weights to each sample of training data such that the learning system may be influenced to solve the most difficult training data.

The algorithm works by calculating the error on a classifier which has been learned separately. The error is consists of the sum of weights of each sample, so a classifier may not receive high credit for solving easy but is awarded a higher score when it solves harder samples. After the error is calculated the distributions are updated such that unsolved samples maintain their weight and solved samples have their weight reduced in proportion to how well the classifier solved the sample set as a whole. This process is repeated T times or until a further useful classifier cannot be found.

After training is complete, a strong classifier can be constructed from the set of weak classifiers and their associated error values which give some indication of the confidence in the classifier. Every time a weak classifier returns a label, a value associated with that label is incremented by the confidence factor, with the label with the highest overall confidence level being returned.

Adaboost depends on a number of solutions to be run, and as a result makes the search for a strong classifier much slower.

\chapter{Related Work}
\label{ch:related}

In this Chapter, a range of research in computer vision involving genetic programming is introduced and explored. Reference is made to the non-learned approaches used in the wider computer vision community and comparisons are made where appropriate.

\section{Image Processing}
Image analysis may be considered an extension of signal processing which involves the modelling, analysis and classification of signals which may captured from a variety of sources. Hampo and Marko \ref{hampo:1992} were among the first people to consider using GP for signal processing in order to develop vehicle control systems.

\paragraph{Edge Detection}
Harris and Buxton \cite{Harris:1996:edgegp} used Genetic Programming to evolve functions which could identify the discontinuities (edges) in a one dimensional signal. 

Their work was inspired by the theoretical aspects of the work of Canny \ref{Canny:1986} whose edge detector remains the state-of-the-art in edge detection in images. Canny suggested that a good edge detector would have a good signal-to-noise-ratio, would localise each edge accurately, and would respond only once per edge. Harris and Buxton used these criteria to produce a fitness function for a GP system which was subsequently trained on various hand-labelled, one-dimensional signals.

Their GP function set consisted of mathematical functions: basic arithmetic, exp, power, sine and cos. The goal was to evolve a function which produced a response wherever an edge existed on the input signal. The function they evolved was able to perform slightly better than Canny's on real captured signals. In explanation they stated that GP permitted the discovery of near optimal detectors for edges in signals which fell outside of the assumptions inherent in a purely theoretical ``optimal'' detector, a feature which remains one of GP's major selling points.

However unlike Canny's edge detector, Harris and Buxton's detector was purely mathematical and only operated in one dimension. Chao \cite{chao:edge} had already used a Hopfield Neural Network to find edges in an image, using each pixel as an input for the net, with the weight of connections between pixels being determined by their difference in intensities. Following analysis of the networks, the outputs on edges would tend towards 1; everywhere else to zero. Results were found to be comparable with a Sobel operator. Other work using Neural Nets \cite{srinivasan:edge} also produced detectors comparable with Canny's.

Another approach using an evolutionary learning technique was by Bhandarkar \cite{bhandarkar:edge} using Genetic Algorithms. The aim was to optimise individuals' two dimensional chromosones named ``edge images'' that could be used to locate edges in greyscale images: essentially the GA produced an optimised convolution mask.

Harris and Buxton later extended their paper to demonstrate it working on real images \cite{harris97lowlevel} and once again showed that it could outperform theoretical operators when trained on and used for real world images. They showed that it was better to tailor an edge detector for a particular ``class'' of images sharing similar noise characteristics, than to use a theoretically optimal, generic detector. Given the training data techniques such as GP naturally permit the construction of tailored solutions very easily and may provide an advantage in delivering robust solutions to work in particular applications.

\paragraph{Feature Extraction}
Outside of machine learning research, Shen \cite{shen:edge} used a modified Hough transform to find edges for the purpose of corner detection, another well explored path in computer vision. Given a particular point in the image, their idea was to use the Hough transform locally in order to find lines which passed through that point. The Hough transform permits lines to be recovered that may otherwise be rounded by the Gaussian smoothing which is often required to discount noise in the image. Largely anecdotal results revealed that the detector was comparable with the existing corner detection algorithms.

Genetic Programming does not appear to have been employed to evolve specific corner detectors, although it has been used as part of the wider search for ``interest points'' in images, which may amount to something similar. Trujillo \cite{trujillo:interestpoint} used Genetic Programming to evolve such an interest detector. A key part of the fitness function was the need for \emph{repeatability} where the interest point on a particular frame would also be detected on subsequent ones. The GP programs were given access to first and second order image derivatives, which are widely used in order to develop edge and corner detectors. While it is rather difficult to produce objective results for an interest operator, the author's noted that GP had (re)discovered a previously man made design: Beudet's DET Operator. While the authors made no claim regarding the superiority of their design, it is again clear that GP can produce effective solutions to problems which are in some instances competitive with human-designed approaches.

Quintana, Poli and Claridge (2003) investigated different means of processing binary images for the extraction of rather more domain-specific information. Their experiment concerned the extraction of different musical symbols from sheet music: the notes, hooks connecting quavers and clef lines. Their approach involved Mathematical Morphology (MM) \cite{serra:mm}, an established technique for various image processing tasks. MM considers sets of pixels, rather than the pixels themselves, and offers two basic operations whereby the set may be expanded or contracted through dilation or erosion respectively. A series of operations may constitute an MM filter which may have applications in fields such as noise reduction, edge detection and general object recognition. The construction of MM filters is usually dependent upon human development.

While the heads and lines could be isolated well, the GP method was able to satisfactorally segment the clef lines from the musical notation. It may be that MM is perhaps not capable of removing large objects without eroding smaller objects such as the clef lines. This highlights one of the problems in machine learning: it is difficult to identify whether poor performance is caused by the quality of the tools provided, or the inability of the learning environment to learn.

One solution to this problem, afforded by the flexible nature of Genetic Programming, is to provide more features in the hope that some of them will prove useful. Roberts and Claridge \cite{roberts:2003:skin} proposed a system for segmenting skin lesions, a problem made difficult by the natural variability in skin tone and texture. Their feature set was large, consisting of thresholds, morphological operators, logical operators, region statistics etc, although very little information about the implementation of the system was provided. The evolved operator did perform quite well, with a sensitivity of 97\% and specificity of 81\%. 

It is also possible to use a host of different generic features for the purposes of a vision task, including any image processing technique from the wider vision or pattern recognition community.  The same authors provided a list of the kinds of feature being used \cite{roberts04cooperative}, which included statistics arising from rectangular windows about a pixel, convolved responses, concentric circle statistics (which bear the advantage of being rotationally invariant), differences between 3x3 areas and various other domain specific features. Combinations of these basic features can produce higher level operators capable of solving more subtle tasks. Roberts and Claridge went on to describe how Genetic Programming may actually adapt and produce such features through a process of co-evolution. The results published appear to show that coevolution in this manner can solve problems to a very high degree of accuracy, although unfortunately no comparison with normal GP was provided.

Zhang, Andreae and Pritchard (2003) went on to explore the usefulness of positional pixel statistics. In an experiment using moving windows to detect basic shapes and different coins, they investigated the effects of just using statistics on the whole window (mean, variance and moments), in comparison to using just the mean in sub windows. They found that whole window statistics were too rotation invariant in order to give proper information about shape, and the windows where sub-window statistics were made available were able to produce better results more quickly. 

\paragraph{General Image Processing}
Poli \cite{poli96genetic} made a number of empirical and domain-independent suggestions for image processing using GP in his 1996 paper entitled ``Genetic Programming for Image Analysis''. His suggestions included the use of an integral image and small, square convolution masks. The integral image is a widely used technique in computer vision which encodes an image in an efficient way such such that the mean and standard deviation of arbitrary rectangular regions can be calculated rapidly and in constant time. Combinations of basic masks allow more complex masks to be approximated (for instance Gaussian or Laplacian), providing the building blocks for a powerful potential feature set.

He also suggested that symbolic regression, where the output must match the expected value as closely as possible made the evolution process more difficult. Poli suggested a different means should be used to determine the output (such as dynamic thresholding, see later). 

Given these insights, Poli used Genetic Programming to evolve a custom filter capable of segmenting magnetic-resonance (MR) images of the human brain and showed that his GP approach was marginally more successful than a neural net.

\paragraph{Colour Constancy}
Ebner \cite{ebner:2001:colour-constancy} used Genetic Programming to evolve an artificial retina which is capable of recognising the true colour of materials.  His retina consisted of a 2D array of elements, each of which had a red, green and blue sub-element. Each element corresponded to one pixel on the image.

\paragraph{Stereoscopic Vision}
Graae, Nordin and Nordahl (2000) investigated using GP to produce a disparity map between two stereo images, which is used to estimate the distances of objects. They marked up corresponding points in left and right images and trained linear genetic programs to find the right point, given the left one. Two experiments were conducted, the first one, where the GP program was iterated many times and was able to move freely until it returned the disparity value, failed. The second experiment where the GP program returned a similarity measure between two sub images that was then run on a sweep across the image, returned good results, giving an eventual error of 1.5 pixels, sufficiently low to calculate the range to within 10\% of its true value.

\paragraph{Object Center Localisation}
Montes and Wyatt (2003) proposed using a variant of Genetic Programming (Cartesian Genetic Programming) to solve a spatial problem – the location of the center of mass of an object. While not a particularly difficult problem to solve in practice, it was shown that GP could evolve its own, reasonably accurate solution, using only a single imaging operator (the mean intensity of a square region). Cartesian GP uses a different form of encoding which permits graphs as well as trees to be created, but is also less able to support strongly-typed GP, an important method for constraining the search space.

\paragraph{Segmentation / Detection}
The purpose of segmentation is to classify each pixel in an image such that similar pixels form into homogenous regions. This is useful to summarise the kind of information found in a particular image and may make it easier to analyse. The task is often descibed as for at least three reasons. Firstly, segmentation is usually required to be as as accurate as possible since the output of segmentation is often passed on for higher level processing in vision systems. Secondly, segmentation has an implicit requirement for some form of edge detection which as has already been discussed is a non-trivial problem. Finally it is difficult to define what how an optimal segmenter will perform on all the but the most basic images.

There exist any number of different techniques for performing segmentation. K Means Clustering is an excellent unsupervised technique for dividing an image into various partitions. Clusters may also be discovered analytically using Histogram analysis. Since region boundaries and edges often amount to the same thing, edge detection techniques are often used in image segmentation. Other techniques include the Watershed transformation, level set methods and model based segmentation.

Genetic Programming has been used on many occasions to tackle segmentation problems which are usually highly domain specific. Examples include the segmentation of skin lesions to aid the detection of melanoma (skin cancer) \cite{roberts:2003:skin} and the recognition of features from remotely sensed multi-spectral images \cite{Brumby:2001:remote}. 

Song and Ciesielski applied Genetic Programming for texture classification and segmentation in (2004), a task which often concerns conventional machine vision researchers but is not often investigated using Genetic Programming. They showed that GP was able to marginally outperform the C4.5 Decision Tree algorithm when differentiating each texture from 47 others, although the patterns used were very basic. Both methods frequently attained perfect scores which made comparisons difficult.

They demonstrated two approaches, one using Haralick statistics as a feature set, and the second using only raw pixel data. While the pixel data experiment did not perform quite as well as the one using features, it does demonstrate the flexibility of GP to produce good results without any statistical features at all, which is something that decision tree algorithms like C4.5 would struggle to achieve. Solutions using raw pixel data are also substantially faster to execute than those using compex features such as Haralick's. 

As the textures trained were perfectly regular, with no variance at all, there was effectively no difference between training and testing data, so it was not possible for the authors to measure the robustness of their algorithm.

\paragraph {Object Detection}

All of these techniques may or may not be precursors to one of the most common high level image processing tasks: object recognition (see SIFT, David Lowe). 

Tackett (1992) was the one of the first to report the use of Genetic Programming for a vision application in his paper 'Genetic Programming for Feature Discovery and Image Discrimination'. Tackett used GP to evolve an automatic target recognition system for recognising targets in military situations. Despite the processing burden imposed by images in general and GP learning in particular, Tackett trained his system on 2000 samples, a seminal feat at the time.

He used spatial features consisting of areas’ intensity means and standard deviations, although a common theme throughout GP research suggests that the evolved systems are capable of evolving their own features from very basic inputs. 

Tackett compared his detectors with an MLP Neural Network and found that GP delivered the most accurate solution. The creative freedom afforded by the fitness function paradigm in GP makes it ideal for solving difficult problems. Briefed on a clear set of objectives, Tackett knew his program needed a detection rate of only 96\%. The MLP, aspiring to solve 100\% of the training data was forced to accommodate difficult samples, at the expense of lower specificity. As Tackett observed, this caused an unacceptable level of false alarms for the Neural Net.

Roberts and Howard (1999) used Genetic Programming to recognise classes of objects in complex environments, again using the multi-stage approach where a 'rough' preliminary detector was followed by finer, second stage detectors. Roberts and Howard didn't expect each secondary detector to provide a perfect detection rate, but rather suggested that different second stage detectors may be good at detecting different kinds of vehicle, although this was not presented in evidence.  

Single-pixel-thickness circular statistics were used as features which are invariant against rotation and noise, although they did impose an additional processing constraint.  Four circles of different diameters were used, with the average intensity, standard deviation, edge count and an edge distribution measure calculated for each. Like Poli, Roberts and Howard used a bias ratio in their fitness function to subjectively determine the sensitivity / specificity ratio. The evolved detector was able to detect 89\% of the vehicles with a 14\% false alarm rate. However there was no testing on unseen training data, and only relatively few images were trained.

Zhang and Ciesielski (1999) were among the first to investigate the detection and classification of multiple kinds of object. They conducted several experiments with different image types: square/circle classification, coin classification, and haemorrhage/aneurism detection in retinal images. Implemented using a windowing approach, they used various circular and rectangular statistics (which was computationally intensive). Despite a generous selection of features, a restrictive function set consisting only of arithmetic operators was used. Post processing was used to ensure that only the centre of each object was detected, once, similar to one of Canny's criteria. Good detection rates on the (difficult) retinal images were achieved but at the expense of relatively high false alarm rates, despite the post processing.

\paragraph{OCR}
Spivak used Genetic Programming for Optical Character Recognition \cite{spivak:2002:OCR}, as did Andre \cite{EvoVision:Andre:1994}

\paragraph{Hand Detection}
Johnson, Maes and Darrell (1994) used GP to locate features on an image. For part of an interactive system, they evolved a program which could locate the positions of right and left hands on a silhouette of a person (taken against a blue screen). Instead of using pixel statistics, as would become common in computer vision, they used a basic 'Point' data type which could hold x,y coordinates. Various functions could find important points around the silhouette, such as the corners of the bounding box, the centroid and the right-most point, and other functions could perform point operations, such as adding them together or finding the point between them. Their results were quite successful – their best program could find 93\% of left hands, although their programs didn't perform so well on validation data.

\subsection{Face Recognition}

\begin{figure}
\begin{centering}
\includegraphics[width=0.5\textwidth]{faces}
\par\end{centering}
\caption{Face Detection Training Data}
\label{fig:faces}
\end{figure}

\paragraph{Detecting Faces}
Winkeler and Manjunath (1997) demonstrated the use of Genetic Programming for face detection using a multiple-scale windowed approach. Within each window, fifty two pixel-based features were made available to the GP system, as well as other image processing features such as Gabor features. In addition to a relatively standard GP setup, the authors suggested that demetic selection (where individuals are confined to “islands”) would avoid premature convergence, a problem found in many machine learning techniques.

A good individual, cited by the authors, had a tree size of over 3000 nodes which introduced a severe performance bottleneck. In a second experiment, a segmentation program was developed to roughly distinguish areas that contained faces from areas which didn’t. When combined into a multi-stage approach, the processing cost was reduced by 75\% and the false negative rate was also cut significantly (although the effect on the detection rate was not reported)

\paragraph{Pentland and Turk (1991)}
\paragraph{Sirovich and Kirby (1987)}
\paragraph{Viola and Jones}

\section{Classification}
Ciesielski and Loveard (2001) went on to make a more detailed examination of the use of GP for multi-class classification, testing five different techniques on six standard data sets from the UCI Machine Learning Repository. 

These techniques included binary decomposition, static range selection, dynamic range selection, evolved decision trees and evidence accumulation (where each leaf contributes to a vector of values, the highest index of which is chosen as the class label).

It was found (somewhat unsurprisingly) that most methods performed relatively well on binary classification tasks, but for multi-class classification dynamic range selection (where a series of thresholds are automatically optimised for the floating point output of each program) performed best, although it did take longer to evolve than either binary decomposition or (the fastest) evolved decision trees. Evidence accumulation, which relies on large (therefore slow) decision trees was found to be lacking in terms of both speed and quality.

Smart and Zhang (2003) compared two different dynamic range selection methods for image classification. The first, Centered Dynamic Range Selection attempted to find the average result of the population for a particular class, weighted to favour the results of the best performing individuals. The second, Slotted Dynamic Range Selection, assigned a much large set of slots, each of which would be marked as having a particular class. It was found that each dynamic selection method could outperform static range selection on all but the simplest tasks, but centered dynamic range selection appeared to work the fastest and the best. It should be noted that their range selections were averages for the  population as a whole, whereas the thresholding suggested by Poli was to be calculated individually for each program.


\begin{itemize}
\item {}``Robust Real-Time Face Detection'' - Viola, Jones (2003) {[}SEMINAL]
\item {}``Rapid Object Detection using a Boosted Cascade of Simple Features''
- Viola, Jones (2004)
\item {}``Evolution of Vehicle Detectors for Infrared Line Scan Imagery''
- Robers, Howard (1999)
\item {}``A Domain Independent Window Approach to Multiclass Object Detection
using Genetic Programming'' - Zhang, Ciesielski, Andreae {[}SEMINAL]
\end{itemize}

\section{Motion Problems}

\subsubsection{GP for Motion Tracking}
\cite{smart:zhang:tracking}
\cite{winkeler:active}
\cite{perkins:shaping}
\cite{EvoVision:Martin:2002b}

\subsubsection{GP for Motion Prediction (Active Tracking)}
No GP papers exist. A paper by Hoffman used a combination of Neural Nets and handwritten code.

\section{Critical Comparison of GP}

\subsection{The Case For Genetic Programming}

Computer Vision is a notoriously ambitious area of research. It is difficult that a discipline which is arguably only twenty years old can ever seek to match the combined evolution of the human eye and brain which have been worked on by nature across millions of generations. One of the most difficult parts of computer vision is its subjective nature which makes it hard to define in concrete terms the nature of a problem. Such difficulties may leave the researcher unsure as to where he or she should begin. Genetic Programming is not encumbered with the need for a problem definition, except in the broadest sense. Neither is it prone to following a particular line of enquiry. In many aspects one may argue that Genetic Programming is an ideal researcher, working tirelessly until a result meets a set of criteria. If the result turns out to be inadequate, then the criteria themselves may be made more rigourous, but it isn't necessary to deliberate \emph{why} the result was poor.

This argument may be made for any machine learning technique, so what makes genetic programming more ideal than any other algorithm? Poli suggested that Neural Nets are unable to compete with GP, because of their inherently linear nature. His experiments showed subjective results that GP could outperform a Neural Net, although the absolute difference in fitness was actually quite small.

Genetic Programming is an extremely abstract learning paradigm, indeed most genetic programming environments are constructed without any concept of the problem or solutions that GP may be required to find. This is because virtually any nodes and training information can be slotted into the Genetic Programming interface, after which the system evolves solutions based purely upon results.

Genetic Algorithms and Neural Nets are not so flexible: their representation is relatively fixed. A GA in its basic form aims to optimise a series of values and in the case of Neural Nets the weights of various connections. The simplest adaptation of Neural Nets for image processing is to assign each input of the net to a pixel on the image and allow the net to learn some kind of useful relationship between different regions of the image. One may say the problem with this approach is that it needs to agglomerate a lot of separate (possibly redundant) information before arriving at any classification, which may render the net computationally too expensive. On a broader level the problem is that the net's fixed set of topologies make it hard to adapt them for every problem.


\subsection{The Case Against Genetic Programming}
In a previous study (by Lim/Loh/Shih, 2000) 33 different classification algorithms were tested and compared on the same data. Cielsielski and Loveard added their results to the comparison. With the algorithms compared in rank order, the dynamic range selection representation in GP was found to be quite competitive with the 33 other techniques for binary problems (ranking as high as fourth), although in general the GP programs' rankings were mediocre.

Are GP Algorithms as good as those in the wider Machine Learning community? Possibly not, but there are instances of novel code discovery. Is the gap significant? 

\paragraph{General weaknesses in Genetic Programming}

Genetic Programming is widely regarded as being slow and inefficient; this is not necessarily unjustified. The nature of Genetic Programming is to produce a large population of programs and to discard the majority. By contrast, techniques such as XCS aim to evolve and improve a single system through less blunt reinforcement and thus converge upon a solution significantly more quickly.

The nature of the genetic operators is also of concern. The process of crossover, by which new combinations are found can be more destructive than constructive.

Like various learning approaches, GP is also susceptible to finding local minima.


\subsection{Difficulty of producing Unlearned Machine Vision Algorithms}

High dependence on mathematical models which may or may not reflect the real world; high level of task specific knowledge required.

\section{Problem Statement}

Justification by direct reference to Chapter 3, that this problem is pertinent and unanswered; how the other algorithms fail. Why it is necessary to have my algorithm.

\subsection{Aims}

\subsection{To Fill Gaps in GP Research}

\paragraph{Multiclass Problems}
Has been solved using GAs which create feature planes to be subsequently
classified by Fisher Linear Discriminant. (GENIE, Perkins et Al)

Neural Networks are also capable, but can be quite slow to train.

\paragraph{Colour Images}
A colour image is a special case of a multi spectral image. 

\paragraph{Task Independence}
Still applies to only a specific subset of tasks. Nobody has proven
an algorithm that works across several machine vision fields

\subsection{To demonstrate my generic methodology is competitive with current
state of the art in GP.}

My Sub Generational GP is competitive with lots of different methods...

\subsection{To show that my methodology is generic and applicable to a number
of different tasks.}

%----------------------------------------------------------------------------------------------
\chapter{The Genetic Programming Framework}
\label{ch:gp-framework}

In order to facilitate experiments investigating parts of the GP system itself,
a complete Genetic Programming toolkit (named SXGP) was developed. This was
undertaken both for reasons of convenience, and because the author wanted to
make use of good approaches mentioned in the GP literature. 

The system is implemented in the Java Programming language, the object-orientated nature of
which lends itself to produce abstract tools easily. There is already a wealth of
freely available APIs available for image processing and capture using Java, and
finally, the cross platform nature of Java makes it suitable for running on
multiple machines.

Detail will be provided in this Chapter about the construction of a Genetic Programming
system and the additional capabilities which were added. Results will be presented providing
an empirical comparison of the performance of our 'homebrew' system, and an equivalent, widely
used evolutionary computation system.

\section{Genetic Programming System Overview}

A genetic programming system is a toolkit which comprises a number of core components
necessary to simulate the process of artificial evolution. The author identifies these
components as follows:

\begin{enumerate}
\item The selection of individuals for recombination, mutation and reproduction
\item The choice of genetic operators
\item The representation and creation of individuals
\item The evaluation of an individual's fitness
\item Generation Gap Methods
\end{enumerate}

\subsection{Selection of Individuals}

One of the primary concepts of Darwin's theory of evolution by Natural
Selection is that species become better adapted to their environment
by ``survival of the fittest''.

Artificial evolutionary learning systems, therefore, are motivated
to select ``better'' individuals while discarding ``worse''
individuals. The definition of good and bad individuals will be discussed in Section \ref{fitness}.
These individuals are then used as parents for the next
generation, with the expectation that system will be able to produce
better individuals over time as the cumulative selection process tends toward substantial improvement. 

At the heart of the selection process is a dilemma, concerning the
desire to both utilise the most successful individuals, and preserve
the diversity of the population as a whole, which may come in useful
at a later stage. The ideal selection algorithm should incorporate
both a bias in favour of better individuals, and sufficient randomness
to maintain broad range of different solutions within the population.

Three main selection algorithms are in common usage in the Genetic
Programming community: Fitness Proportional Selection, Rank Based
Selection and Tournament Selection.

\subsubsection{Fitness Proportional Selection ({}``Roulette Wheel'' Selection)}

As its name suggests, this technique selects individuals from the
population with a probability proportional to its fitness. This is
commonly implemented in practice using stochastic universal sampling
\footnote{A number of markers are assigned to each individual, proportional
to its fitness. A marker is randomly chosen and the individual associated
with that marker is selected.}.

It was decided not to employ Fitness Proportional Selection for three reasons. Firstly,
and dependent on the resolution of the stochastic uniform sampling,
some individuals may have such low fitness that they are not assigned
a marker at all, so the method cannot always yield results which are
truly proportional to fitness. Secondly, this method is sensitive to outlying fitness values. An
individual with an unusually high high fitness is likely to dominate
the intermediate parent population, at the expense of diversity. Finally, fitness proportional selection does not provide a means of adjusting the selection pressure.

\subsubsection{Rank-Based Selection}

This algorithm is less prone to outlying fitness values as selection
is made proportional to the \emph{rank} of an individual (after being
sorted by fitness), rather than its raw fitness. The individuals are
first ranked in descending order, with the index, $j$ of the selected
individual chosen according to the following formula by Whitley
\cite{whitley89genitor}:

\[
j=\left\lfloor
\frac{N}{2(c-1)}\left(c-\sqrt{c^{2}-4(c-1)\chi}\right)\right\rfloor \]


The formula essentially converts the output of $\chi$, a uniform
random number into a linear distribution which is thus more likely
to select lower-indexed, fitter individuals in the population (of
size $N$). The variable $c$ determines the selective pressure, or
the slope of the linear distribution.

\subsubsection{Tournament Selection}

This is arguably the most commonly used algorithm used for selection
in evolutionary environments due to its simplicity to understand,
model and implement both on a single machine and on parallel systems.
From the population, a tournament of size $t$ individuals are chosen,
with the best individual in the tournament chosen as the winner. The
selection pressure may be increased by using higher values of $t$.

During their comprehensive analysis of a series of selection methods,
Blickle and Thiele \cite{blickle95mathematical} concluded that Tournament
Selection produced the smallest loss in diversity and the highest
selection variance in comparison to truncation and ranking selection.
For this reason, and the reasons presented above, Tournament Selection
was chosen as the defacto selection method in our Genetic Programming
environment.

Tournament selection consists of two stages: sampling and selection. The choice of the tournament size $t$ has implications for both, namely whether an individual is sampled at all, and the
probability that it will be selected (discussed by Poli \cite{poli:2005:foga})
and each has an effect on the diversity and quality of the next generation.
When $t=1$ tournament selection is akin to random search - diversity
will be maintained but there is no selection pressure at all. When
$t=N$ the best individual will be chosen every time, but the diversity
of the subsequent generation will be severely limited. It is therefore
necessary to choose a reasonable value of $t$.

Motoki \cite{motoki2002} calculated that the expected loss of diversity
in tournament selection would be:

\[
D_{T}(t,N)=\frac{1}{N}\sum_{k=1}^{N}\left(1-\frac{k^{t}-(k-1)^{t}}{N^{t}}\right)
{}^{N}\]

Interestingly, this formula predicts that the loss of diversity grows
rapidly but becomes relatively static in populations with more than
8 individuals. This means that we can select a value of $t$ which
should not require specific tuning for each individual experiment.
Where $t=20$, the formula predicts that 80\% of the diversity of
the population is lost which may significantly affect the ability
of the evolutionary algorithm to perform. At the lowest practical
value, when $t=2$ the loss is about 40\%. Low selection pressures
are generally used in GP practice and successful results have been
achieved using low values \cite{poli05backwardchaining}, so a $t$
value of 2 was used in most situations.

From the use of Tournament Selection arises a second consideration.
There is a chance, due to the random nature of tournament selection
sampling, that an individual may never be selected. This probability
was calculated by Xie, Zhang and Andreae \cite{xie:zhang:andreae}
as:

\[
p_{selected}=1-\left(\left(\frac{N-1}{N}\right)^{N}\right)^{t}\]


Assuming that the number of tournaments is equal to $N$, which is
true in standard evolutionary breeding process where one parent produces
one child via mutation and two parents produce two children via crossover.
In a population of 500 individuals with a tournament size of 2, the
probabilty of an individual not being selected is 13.5\% (which is
relatively constant for values of N). Therefore 13.5\% of individuals
are evaluated even though the result of the evaluation, their fitness,
is never used as they never compete in a tournament.

This discrepency presents the opportunity to implement one of two
different kinds of solution:

\paragraph{Solution 1: Avoid the unnecessary evaluation}

This first approach, first suggested by Poli
\cite{poli:2005:foga,poli05backwardchaining}
suggests that individuals which are not included in any tournament
should not be evaluated indeed not even created. To do this he pre-calculated
the memberships of a series of tournaments across a given number of
generations. Based upon the individuals in generation $G$ he then
calculated a graph defining each of its ancestors. The ancestors were
all then evalated in turn, starting from the oldest in order to produce
the final individual. This scheme is able to reduce the number of
evaluations significantly provided that the value of $t$ is very
low, and with greatest effect in the prior generation, $G-1$. In
older and older generations, the probability that all individuals
will have to be evaluated increases, unless a tournament size $t=0$
is used, whereupon the integrity of the whole evolutionary environment
is jeapordised. 

A simpler and arguably more flexible scheme was suggested by
Xie, Zhang and Andreae \cite{xie:zhang:andreae}, \emph{Evaluated-just-in-time
}where individuals are only evaluated once they enter a tournament. 

While certain individuals are still created but never evaluated, the
authors pointed out that the bulk of computational expense comes from
the evaluation, rather than the creation of the individual. In the
field of image processing, covered by this project, this holds particularly
true.

\paragraph{Solution 2: Ensure that $p_{selected}$ is always 1}

A better solution is to ensure that the problem of sampling effects
leading to selection bias does not arise in the first place, as this
algorithm should be better able maintain diversity. Sokolov and Whitley
\cite{sokolov:whitley2005} suggested a different form of tournament
selection where each individual was guaranteed two tournaments. Relatively
simple to implement the indices of the population $i$ were copied
and permuted such that $P_{i}\neq i$, $\forall i$. Then each individual
$i$ is compared to individual $p_{i}$in a series of $t=2$ tournaments.
This is the same idea as suggested by Goldberg \cite{goldberg:89g}.
A feature of this procedure is that the best individual is guaranteed
to be selected exactly twice and the worst individual will not be
selected once. This tournament selection method was used in the author's
GP toolkit.

\subsubsection{Different Selections for Different Genetic Operators}

Muni \emph{et al. }\cite{muni:2004} suggested the use of different
selection methods for different genetic operations. For instance if
the genetic operator selected is reproduction, then a fitness proportional
selection should be used. Regular tournament selection should be used
for crossover, and mutation, which occurs randomly, should occur on
a random individual in order to encourage diversity, the purpose of
mutation.

\subsubsection{Elitism}

Elitism is a good policy to use if searching for \emph{the} global
maximum or optimum. However, it tends to be an \emph{expolitative}
rather than \emph{explorative} search strategy. It exists to protect
against the loss of the current best solution by either selection
effects or damaging crossover.

\subsection{Choice of Genetic Operators}

\subsubsection{Crossover}

Standard crossover works by selecting two parents, from which a subtree
from each is selected randomly. Constraints to ensure that both subtrees
are compatible may be implemented. After the subtrees have been selected
sucuessfully, they are swapped between parents to create two new individuals
which are then inserted into the new population. The intention of
crossover is to take good individuals and combine them together in
such a way that even better individuals can be created. However, this
basic form of crossover is a blunt instrument, and exhibits no intelligent
strategy for selecting subtrees based on their performance. An experiment
in \cite{banzhaf:1997:book} investigated the relationship between
building blocks in GP -- useful pieces of code which contribute to
good solutions -- and crossover. As the run progresses and the solutions
become more refined the size of the building blocks increases, with
this the probability that these blocks are disrupted by destructive
crossover also increases. Experiments by Nordin \emph{et al.
\cite{nordin:1996:aigp2}
}showed that the average fitness of child programs is less than half
the fitness of the parents on about 75\% of crossover events, demonstrating
that the standard crossover can have decidedly destructive effects.

Poli and Langdon \cite{poli:1998:crossover} demonstrated through
modelling and empirical investigation that standard crossover was
also local and biased. Local search means that the offspring is not
very different from the parent which means the search itself is not
so effective. Standard crossover is biased as it it is most likely
to make adjustments near to the leaves of the tree. This is a feature
of the different tree structures used by individuals in Genetic Programming.
In Genetic Algorithms, by contrast, each individual is usually of
the same length so recombination can occur without bias, as the sub-strings
swapped will both have the same length. It may therefore be concluded
that the transliteration of crossover from Genetic Algorithms to Genetic
Programming is not an equivalent one, and requires further refinement.

For these reasons a number of different approaches have been taken
to improving the crossover operator to make it more capable of {}``intelligent''
or at least unbiased and effective genetic search. 

The first approach is, broadly, to accept the shortcomings of crossover,
but and make improvements based on multiple attempts, at the expense
of much greater computational burden. Tackett \cite{tackett:1995:brood}
stated that in nature animals produce large broods based on the probability
that many will not survive%
\footnote{Although this analogy is not strictly accurate. Broods in nature are
likely to die as a result of factors relating to their environment,
not because of their individual genetic predispositions.%
}, therefore crossover between parents should be repeated $N$ times
to produce a {}``brood'' of $2N$ individuals (instead of the usual
two), from which the best two would be chosen. Lang
\cite{lang:1995:headlesschicken}
proposed a different crossover strategy, wryly dubbed {}``headless
chicken'' crossover, where only one parent was selected from the
population and then crossed over with a randomly generated individual,
making it more analagous with point mutation than true crossover.
Crossover was repeated until the offspring was better than the parent
- a form of hill climbing. While Lang showed that his method could
outperform standard crossover on a multiplexer problem, Zhang \emph{et
al. }\cite{zhang:2007:newcrossover} showed that while it could still
get better results than standard crossover, it was significantly slower
on classification problems.

The natural, perhaps ideal, adaptation suggested by many authors is
to develop some means of protecting useful parts of the tree so that
crossover may be forced to improve only the poor subtrees. However,
it is not easy to identify which subtrees are performing well and
which are not.

\subsection{The representation and creation of individuals}

\subsection{The evaluation of an individual's fitness}
\label{fitness}

The purpose of this component is to objectively measure the usefulness of a particular individual with respect to a particular task. Provided the vision system architecture can represent a number of different problems using training data, the fitness of an individual can be expressed in terms of its ability to solve a given set of examples. 

A second problem in fitness evaluation is the definition of what value constitutes ``ideal'' fitness. In line with John Koza's original fitness functions, we define the ``ideal'' fitness of an individual as being zero, with higher numbers being progressively less ideal.

... more to come

\subsection{Generation Gap Methods}

Evolution in the natural world proceeds slowly and is only apparent between
generations. Subtle changes which occur in offspring, if successful, will remain
in the population. The cumulative effect of these changes over thousands of generations
becomes more and more substantial. In artificial evolution, we face a choice in how to handle the gap between generations. 

Dependent on the chosen selection scheme is the generation gap method,
which determines the amount of overlap between parents and offspring.
Two such schemes are widely used in Genetic Programming (and Genetic
Algorithms in general): generational $\left(\mu,\lambda\right)$ and
steady-state $\left(\mu+\lambda\right)$ reproduction. In the former,
generational, reproduction the entire population is evaluated and
replaced in one go so parents and offspring never compete with eachother.
In steady state reproduction, a few individuals are replaced at each
reproduction cycle. 

The deletion scheme used in generational reproduction is trivial,
as the entire population is selected for deletion, to be replaced
by an entirely new generation of offspring. In steady state reproduction,
a separate selection process has to take place to decide which member
of the population should be replaced. Several schemes exist, either
taking the weakest from the population at large, or replacing a weaker
parent with its offpsring in a scheme akin to hill climbing.

In some ways, the steady state scheme appears the more natural and
flexible, and is indeed used in Evolutionary Strategies (ES) extensively.
A series of studies by De Jong \cite{dejong1975} appeared to demonstrate
that

\begin{quotation}
Any apparent advantages of overlapping populations were offset by
the effects of genetic drift (allele loss)

K. A. De Jong, 1975
\end{quotation}
This problem was caused by the high variance in lifetimes that steady
state reproduction permits, a problem exacerbated by the low population
sizes (50) used owing to the limitations of computational power at
the time. Theoretically with infinite populations, there would be
no difference in variance between either population. For this reason
it was found that generational reproduction was most appropriate.
As these problems are largely less applicable in modern computing,
the two approaches are more comparable.

It should also be pointed out that De Jong used a uniform deletion
policy, which has been shown to be less effective than other deletion
strategies, such as deleting the worst member of the population (see
GENITOR \cite{whitley89genitor})

Interestingly, Holland and Reitman (1978) found the opposite was true
for classifier systems (See Chapter 4), where unlike in regular genetic
programming, each classifier is to some extent dependent on the others.
They found that replacing only a small part of the population at a
time was more beneficial than replacing the whole population in one
go.

\section{Empirical Comparison of GP Frameworks}

%----------------------------------------------------------------------------------------------
\chapter{Classification by Genetic Programming}
\label{ch:gp-classification}
Many problems in computer vision (such as detection, recognition, segmentation, robot vision) may be regarded as a subset of classification problems, for which some kind of classifier must be learned. A classifier may be described as: 

\begin{quotation}
{}``A function which takes a feature vector in \emph{$p$ }dimension
as input and assigns a class label to it\emph{''}

Muni \emph{et al. }\cite{muni:2004}
\end{quotation}
Essentially the goal is \emph{dimensionality reduction} - that of
reducing $p$ dimensions down to one. A plethora of different methods
from numerous different disciplines exist in order to generate good
classifiers.

A number of such different classification schemes are used widely
in Genetic Programming (they are introduced in Section \ref{sec:Other-Classifiers-using}).
We maintain that while each is capable of \emph{representing} classification
problems (and solutions) a genetic programs, it cannot be proven that
optimal solutions will be reached. Furthermore, none of these representations
is capable of solving problems which require more than a single step,
something which is often required in robotics.

Michigan-Style Learning Classifier Systems, a family of architectures
invented by academics at the University of Michigan, are discussed
in some detail in Sections \ref{sec:Michigan-Classifier-Systems}
and beyond. Based on the ideas of John Holland (later adapted into
the XCS classifier system by Stewart Wilson) a system can be implemented
which is often capable of finding optimally solutions to soluble problems
through an intricate reinforcement mechanism. Furthermore, the XCS
system aims to find increasingly efficient, \emph{general} classification
schemes to solve a problem, in contrast to problems of code bloat
and introns which can cause significant performance headaches in genetic
programming.

We intend to construct a hybrid classifier system, using Genetic Programming
to represent and modify classifier conditions, while outsourcing the
fitness, reinforcement and classification algorithms to an enhanced
version of Wilson's XCS classification scheme.

We will show how Wilson's XCS scheme can be further extended to permit
XCS classifiers to be improved through committee voting, a \emph{fusion}
technique used in multiple classifier systems (MCS), and will compare
the results of the system with the established classification representations
used in Genetic Programming.

\section{Classifiers using Genetic Programming (GP) \label{sec:Other-Classifiers-using}}

The aim of many Genetic Programming systems is to learn the relationship
between a set of inputs and expected output(s). Genetic programs learn
using a set of training data consisting of a number of instances for
which the output has already been decided.

A basic, {}``vanilla'' genetic program takes a number of inputs
$X=\left\{ x_{0},x_{1},\ldots,x_{n}\right\} $, processes them in
some way and returns a single, one-dimensional numeric output, often
operating as a basic mathematical function:

\[
output=f\left(X\right)\]


To produce a binary classifier (which distinguishes one class from
another) using GP, a single threshold is all that is needed to create
a program which can make decisions. A natural threshold of 0 is usually
chosen, with all negative outputs attributed to one class, and all
zero-valued or positive outputs attributed to the other. Many problems
addressed using Genetic Programming only consider single class problems
{[}references].

However, multiclass problems ( involving $n$ classes where $n>2$)
begin to pose problems: there is no longer a pair of thresholds that
neatly divides the number space equally. The problem exacerbates as
the number of classes increases. Equally, it may be that members within one
arbitrarily defined class actually belong to two distinct clusters within the search space.

Multiclass classification problems therefore present two separate
problems: the search for classifiers which distinguish members of
a particular class from the rest of the data, and the search for a
structure which can correctly interpret a classifier's output.

Many vision problems are complex. Consider shape, gesture, digit,
vehicle or face recognition - each problem requires multiple disparate
classes to be discriminated. 

Genetic Programming (GP) has shown to be a good technique for the learning of classification algorithms. One of the advantages of GP is that its flexible nature allows it to learn classifiers using a variety of different representatations.

In contrast to other learning algorithms such as Neural Nets (whose
outputs map to specific classes almost by definition), it is necessary
to adapt Genetic Programming to make it more suitable to solving multiclass
problems, these are explained briefly below.

\subsection{Range Selection}

The simplest adaptation of Genetic Programming to multiclass problems
is the translation of the floating point output of the program onto
various ranges with each representing a certain class and defined
by a series of thresholds. The ranges may either be assigned fixed
thresholds (static range selection), or optimised in some way to {}``fit''
the output of individual programs (dynamic range selection). 

In its simplest form (a Program Classification Map) thresholds are
set at an even spacing (1 unit) on the number line from some negative
number to the same positive number, so for an N class problem, there
are N thresholds.

The original version, proposed by Loveard and Ciesielski placed a few constraints on the output of the program. Firstly, they stated that the output should be rounded to the nearest integer, and constrained within the range from -250 to +250, essentially assigning 500 slots, each of which could be assigned to a class. 

The assignment worked by figuring out which classes were assigned to which slots, and then designating the class of each slot as the id of the most often occuring class from the program output. 

Loveard and Ciesielski showed this method to be the best representation on a number of different benchmarks, when compared to other representations including decision trees, evidence accumulation, static range selection and binary decomposition.

The above method has been used widely {[}references], although it
imposes an additional requirement that the GP program \emph{translate}
its output onto an arbitrary value. Zhang \emph{et al.} \cite{zhang:2003:jasp}
were able to use this strategy with some success on three different
problems, although the largest multiclass problem studied consisted
of only four classes. 

A more adaptive solution aims to map the output of a program given
a certain class onto a probability density function which can then
be used to identify the classes (see Smart \& Zhang, 2005). 

In a paper comparing five common multiclass representations, Loveard
\emph{et al. \cite{lovcie01},} selected dynamic range selection was
chosen as the most accurate.


\subsection{Binary Decomposition}

A multiclass may be split into a series of binary classification problems
(see \cite{spivak:2002:DOCRAGP}). A solution is evolved for each
class, with the solutions chained together to solve the whole problem. 

As each class requires a solution be evolved separately the total
evolution time may be longer {[}reference]. The final solution may
be less efficient since the problem of bloat in GP may be multiplied
{[}reference]. Solutions have been proposed to reduce the effect of
this disadvantage, such as running programs to discover the most commonly
occuring classifiers first, but it remains an imperfect solution.

Smart and Zhang \cite{SmartZhang05} proposed communal binary decomposition
in which a set of binary classifiers is evolved at the same time,
allaying some of the problems of binary decomposition. They tested
their system on low-order multiclass problems consisting of four classes.


\subsection{Modi Program Structure}

Zhang and Zhang \cite{YunZhang:04:ivcnz} proposed a different kind
of GP program in which they dispensed with the $f\left(X\right)$representation
in favour of a different, {}``modi'' tree type, in which any node
may affect a vector of different outputs, each corresponding to a
class. Each node in the tree is processed as usual, but if it is bound
to a particular class, it passes its value to the vector upon execution.
The class with the highest value assigned to it after the tree is
executed is determined to be the chosen class. {[}What is the theoretical
reasoning behind this idea?]

The modi method was able to make modest improvements to the overall
effectiveness of GP, increasing performance up to 11\% on a range
of tests. The trees generated are somewhat counter intuitive although
they share much in common with decision trees.


\subsection{Decision Tree Classifiers}

This intuitive method involves the creation of programs similar in
semantic structure to a decision tree, a specific structure which
consists of a number of nested conditional if-then-else statements
( example, Figure \ref{fig:decision-tree})

\begin{figure}
\includegraphics[width=0.75\textwidth]{gp-example.eps}
\caption{An example of a decision tree classifier for distinguishing three shapes.}
\label{fig:decision-tree}
\end{figure}

Bot and Langdon \cite{bot:2000:GPilct} used GP to evolve decision
trees capable of solving a variety of different problems. Strongly
typed GP was used to constrain the tree builder to produce trees with
the correct syntax. They were able to use the system to solve some
multiclass problems involving up to seven different classes, although
the GP was not always competitive with other specialist decision tree
algorithms such as ID3, CART, OC1 and C4.5.


\subsection{One Individual, multiple trees}

Muni et al. \cite{muni:2004} proposed a single individual incorporating
one tree for every class. He used various other enhancements to Genetic
Programming, such as applying genetic operators probabalistically
based on the \emph{unfitness} of certain trees, with the aim of improving
poor performers while protecting good solutions. Other post processing
methods (OR-ing) and heuristic rules for conflict resolution were
used to boost the classifiers effectiveness. His results were broadly
competitive with a number of other machine learning methods on benchmark
tests (IRIS, WBC, BUPA, Vehicle, RS-Data), which tend to be dominated
by non-gp learning techniques.

Mention POLI

\section{Optimisation of GP Parameters}
\subsection{Tree Builder}
\subsection{Tournament Size}
\subsection{ERC Optimisation}
Built into SXGP - but does it work?





\subsection{Comparison with Genetic Programming}

Genetic Programming and XCS are very different learning environments,
although they both have a strong genetic component. XCS is an example
of a system which strives to develop and incrementally improve a \emph{single}
system, a learning scheme known as \emph{ontogenetic adaptation.}
Genetic Programming on the other hand attempts to evolve many systems
together and\emph{ }improve the classifier through competition between
independent individuals each of which represents a complete solution,
so-called \emph{phylogenetic }adaptation. In the case of Genetic Programming
there is little defined structure within the classifier, in the case
of XCS, the structure of the single individual is carefully managed
and controlled through a series of algorithms as described above.

Like other classification systems (such as Adaboost \cite{freund95decisiontheoretic}),
the population in XCS consists of a series of \emph{partial} solutions.

Fitness in Genetic Programming is usually calculated by measuring
the accuracy of the classifier after testing it on all or part of
the test set, although the execution of a Genetic Program may be require
less computation than a step using the XCS algorithm. Although the
concept of fitness in XCS is similar, XCS is able to make some adjustment
to the individual on every learning step. XCS therefore requires many
fewer inputs than Genetic Programming, on average, to reach the same
solution. {[}Is XCS optimal?]


\section{Implementing XCS using Genetic Programming}

In this case \emph{implementation} means implementing the XCS classifier
system using Genetic Programming for the representation and discovery
part. This produces a few problems which need to be solved.


\subsection{Justification}

\begin{quotation}
{}``A corollary is that generalization will not be possible if the
creature's internal representational architecture or language cannot
express it''

Wilson, 1998 \cite{wilson98generalization}
\end{quotation}
Lanzi \cite{lanzi:1999} stated that with XCS able to discover both
accurate and general classifiers, the overall generalisation ability
was determined (or limited) by its representation of conditions. He
introduced an extension of XCS to replace the bit-string representation
of conditions with variable length chromosones producing a \emph{messy}
coding.

Bit string representation, stated Lanzi, has two significant limitations:

\begin{itemize}
\item That binary encoding of environmental data loses too much information.
\item That the condition's syntax must correspond to that of the input,
therefore the input cannot change.
\end{itemize}
Lanzi first suggested introducing variable length conditions with
no correspondence between positions of sensory inputs and the genes
used to match the condition. This is achieved simply by referring
to inputs by \emph{name} as opposed to by index: an idea proposed
by Goldberg \cite{goldberg:89g} in his {}``messy'' genetic algorithms.
He did discover, however, that this decoupling caused a number of
classifiers to become \emph{underspecified} or over general, which
reduced performance. {[}This was improved via...]

A significant advantage of this form of XCS (XCSm) is that messy genes
have the same meaning regardless of position. This allows the classifier
to continue to work (and be improved) in the case that additional
sensors from the environment are provided at a later stage.

Although not applicable to the artificial, binary environments used
in Wilsons' experiments, in the real world a third limitation would
be:

\begin{itemize}
\item That this encoding does not permit comparison of values \emph{between}
sensors.
\end{itemize}

\subsection{Problem 1 - Subsumption Deletion}

In normal XCS, the bit string representation including the wild cards
(\#), makes it very easy to evaluate the generality of an individual.
If a tree is used to represent the conditions, it becomes more difficult
to evaluate whether a particular condition subsumes another, as more
complex logic is required. 

It is therefore necessary to devise a condition schema which is sufficiently
flexible as to make the use of Genetic Programming worthwhile, but
still sufficiently analysable so that schemes such as subsumption
deletion may be implemented.


\section{Classifier Fusion}

An individual classifier can be sensitive to the tuning of the training
data or learning parameters or to certain defects or local minima
in the training data. Another classifier may behave differently, even
if trained on the same data. For this reason, \emph{multiple classifier
systems} (MCS) have been developed which aim to produce results which
are more robust than those of individual classifiers.

It is important that sub classifiers are \emph{independent }from eachother,
so that the fusion is meaningful. If each of the classifiers always
agree, then the fusion is adding a computational burden without any
improvement in accuracy. A simple way of ensuring sub classifiers
are independent from oneanother is to train each on different sections
of the training data.


\subsection{Majority Vote (for binary classifiers)}

If three classifiers are evolved with each run to reach a decision
regarding a particular input vector, take a majority vote to be the
overall classification. If individual classifiers only output binary
decisions, then this is the most appropriate classifier fusion technique.


\subsection{{}``Committee'' Voting}

If each individual classifier produces more information than a simple
{}``yes'' or {}``no'' response, that is, gives a confidence estimation,
they can be combined in a {}``committee'' approach, where their
outputs can be weighted to produce an average, consensus decision. 


\subsection{Fusion by Genetic Programming}

As Langdon \cite{langdon:2001:groc} points out:

\begin{quotation}
{}``There is no single, best combination scheme nor any unequivocal
relationship between the accuracy of a multiple classifier system
and the individual constituent classifiers''

W. B. Langdon
\end{quotation}
For this reason, he proposes using Genetic Programming to evolve an
ideal problem to combine the classifiers.


\section{Confidence Intervals}

The end result for any classifier is usually a {}``hard'' classification,
stating unequivocably that a particular feature vector belonds to
class x. This is acceptable in situations where the classifier is
highly accurate. However, in situations where multiple classifier
systems are combined to produce a better classifier, it is fairer
to include a confidence interval, which indicates how reliable an
estimate from each classifier is. 

\subsection{Decision Making}
Decision making consists of four main topics:
\begin{itemize}
\item{Classification}
\item{Recognition}
\item{Novelty Detection}
\item{Matching}
\end{itemize}

\subsection{Multiclass Classification using GP}


\subsubsection{Different Approaches}

\begin{itemize}
\item Decision Tree Classifiers
\item Modi Program Structure
\item Program Classifcation Maps
\item Sub Generational GP (My Approach)
\end{itemize}

\subsubsection{Justification}

\begin{itemize}
\item Supports Multiclass Problems
\item Comparison with other multiclass GP strategies - others are really
bad!
\item Is BTC GP better than BTC?
\end{itemize}

\section{Classifier Evolution by Partial Solutions (PS)}
\label{sec:partial-solutions}
Inspired by the boosting of weak classifiers in \cite{EvoVision:Freund-Shapire:1996} 
and classifier systems in general, a scheme was developed in which GP 
programs are evolved as simple expressions which solve only part of the overall solution
and are termed \emph{partial solutions}.

As useful partial solutions are identified (see below for details) they
are added to a separate, `strong' classifier which exists outside of the GP system
(see Fig. \ref{fig:partial-solutions}). The scheme continues to evolve partial solutions 
until the strong classifier is capable of a certain level of accuracy. 

\begin{figure}
  \begin{center}
    \includegraphics[width=0.75\textwidth]{partial-solutions-diagram.eps}
  \end{center}
  \caption[]{GP by Partial Solutions creates a strong classifier from a number of smaller solutions}
  \label{fig:partial-solutions}
\end{figure}

As each partial solution is not expected to solve the whole problem,
the programs are small and so may be discovered and evolved quickly. Once a partial 
solution is identified as being useful -- that is, it can solve part of the
problem that has not already been solved -- it is saved in the strong
classifier and the problem is redefined to include only the remaining 
training data. This removes the need for already-solved data to be continuously re-evaluated,
as is the case with standard GP, and also ensures that the `knowledge' of the partial solution is 
protected\footnote{The actions of genetic operators and the sampling effect inherent in tournament
selection may each cause useful subtrees to be destroyed or lost inadvertently in standard GP.}.

Each partial solution is treated as a binary classifier with respect to a class $C$. $C$ is chosen by evaluating the partial solution with respect to each class $c$ in the problem and choosing the value of $c$ for which it has best fitness. 

The fitness with regard to a particular class $c$ is calculated by dividing the total number of correct
classifications $TP_c$ by the total number of training samples $N$
added to the number of missed classifications $FP_c$, as shown below:
\begin{equation}
  \label{eq:fitness}
  \mbox{fitness}_c = \frac{\alpha TP_c}{N + \beta FP_c}
\end{equation}
The factors $\alpha$ and $\beta$ allows the fitness
measure to be adjusted to affect the individuals' sensitivity or
specificity.

Fitness is used to drive the evolution. However, in order to decide whether a partial 
solution should be added to the strong classifier --- that is to
say that it is able to solve a new part of the overall solution --- four
criteria were devised:
\begin{enumerate}
\item \emph{Does the partial solution discriminate?}  If the solution
  returns only `true' or only `false' it is not capable of making decisions.  
  GP often evolves this kind of lazy solution in
  response to training data that are weighted in favour of one
  particular class. GP by partial solutions avoids this form of code bloat. 
\item \emph{Is the partial solution unique?}  If the classifier
  returns the same results for every instance as another partial
  solution that has already been chosen, then this classifier is
  usually discarded\footnote{Unless it is smaller or less dependent than the existing one, in which case the existing solution is replaced.}.
\item \emph{Does the partial solution return `true' for data that
  have not yet been solved?}  Each item of training data has a field
  indicating whether it has already been solved.  Each candidate partial
  solution has to identify at least one instance that has not yet been
  solved in order to be used.
\item \emph{Does the partial solution return `false' for data in other
    classes?}  If a classifier returns `true' for instances of one
  class, it should return `false' for all instances of other classes.
  However, it \emph{may} return `true' mistakenly for other classes provided
  that they have already been completely solved by other partial
  solutions. We describe this solution as being \emph{dependent} on the
  other classses.
\end{enumerate}

If the partial solution matches all these criteria, it is added to the strong classifier.
Several partial solutions may be discovered during the course of a single generation --
another feature which makes GP by partial solutions faster. 

A version of island selection is used with crossover only occuring between parents with the same value
of $C$ which are more likely to share some similarity.

The strong classifier produces classifications by evaluating each of
its partial solutions in turn (starting with the first added). If the partial solution
returns `true' for a given input vector, the class $C$ associated with the
partial solution is returned, otherwise the next partial solution is executed
and so forth.

\subsection{Papers I may have published:}

\begin{itemize}
\item {}``Automatic Classifier Selection to enhance GP Productivity''
\item {}``Sub Generational GP - The fast approach to solving Multiclass
Classification Problems''
\item {}``A Generic GP System for creating a variety of imaging subsystems''
\item {}``Statistically Typed GP for Image Tasks''
\end{itemize}

\section{Results of Classification Problems}
\section{Analysis of Multiclass success}
\section{Analysis of flexibility across different problem types.}

\section{Other Ideas}





\subsubsection{Justification}

Reduces the search space


\subsubsection{Implementation}


\subsubsection{Comparison with coevolution, ADFs}


\subsubsection{Comparison to uncontrained search spaces}


\subsection{Automatic Classifier Selection using Coevolved Grammars}
See Anthony Brabazon.


\subsection{Automatic Classifier Selection using Minimum Standard Deviation}

\subsection{Automatic Classifier Selection using Range Typing}

The idea of this is that the inputs of some nodes should be matched
with the output of others.

%-------------------------------------------------------------------------------------------------
\chapter{A GP Vision System}
\label{ch:vision-system}
The majority of publications in Genetic Programming/Computer Vision community have concentrated on particular techniques or approaches to a particular domain which do not make a fully working vision application - REF. For the purposes of this thesis, a ``fully working'' vision system shall be defined as one into which you plug raw images, and out from which you receive high level information. For a pasta recognition system, this high level information might be ``this image contains three pieces of pasta; two are farfalle and one is rigatoni''.

While the majority of GP vision researchers have leaned toward evolving several programs that each perform \emph{the entire task}, this work takes a rather different approach. Here, the feature extraction and classification stages are separated and evolved independently. Although this is fairly conventional for vision system architectures, it does not appear to have been attempted previously by GP.

This Chapter explores the construction of complete vision systems using genetic programming and demonstrates an architecture which permits a variety of different problems from different domains to be solved.

Although it is not currently possible to develop a complete vision system in a single pass using any automated learning procedure, it is possible to define an architecture consisting both of hand-coded, generic and domain specific components. The domain-specific parts can then be learned automatically, given sufficient training data. This presents two challenges: the first is to define a generic architecture, and the second is to create a unified interface by which the user can provide training data to the system.

\section{Architecture}
We decided upon a standard computer vision architecture which should appear familiar to anyone working in the field of computer vision or general signal processing. A high level diagram of the architecture is presented in Fig. \ref{fig:vision-system} below:

\begin{figure}
\includegraphics[width=0.75\textwidth]{vision-system-diagram.eps}
\caption{A basic vision system architecture which can solve a number of different tasks}
\label{fig:vision-system}
\end{figure}

The architecture consists of two components learned by Genetic Programming, the first detection phase is required for the detection of objects in the scene, and the second aims to classify each object into a particular class. This simple setup is capable of solving a variety of different problems.

\subsection{Segmentation}
Segmentation may be defined as the classification of each pixel in an image into a particular class. Once every pixel has been classified, and providing the classification process is not inherently random the image should be divided into a number of contiguous regions which may relate to separate objects. The usual goal of segmentation is to make a distinction between pixels in the foreground and those in the background. Although colour information may be gleaned from inspecting only the pixel itself, information about the texture at that point in the image can only be discovered by looking at the pixels surrounding that central point. 

The decision may be made by colour, texture or a mixture of both, depending -- as always -- upon the nature of the problem. A requirement of the architecture is that the learning system can indeed produce segmenters capable of solving a variety of problems. 

-- Images of segmentation results here --

\subsection{Classification}
Once the 

\subsection{Extensions}
While the architecture in its original form has proven to be successful at solving various tasks, there remain classes of problems that cannot be solved due to its segmentation stage. Segmentation is only appropriate for problems where the objects are well defined and distinct from their background. Shape Classification is only useful if the object tends to have little variance. 

\subsection{Window Classification}
Segmentation consists of the classification of each pixel in order to create contiguous regions. However, some problems are defined in terms of the regions themselves, such as face detection, where the training data consists of the sub-images containing faces. 

\subsection{Beyond Shape}

\section{Training Data}
In order to train the feature extraction stage, the developer identifies regions of `feature' and `non-feature' using a graphical user interface. A program is then evolved to do this automatically.
The output of this program yields the regions of interest within a given image which are to be classified. The developer marks each region with the expected class to produce a second training set. After identifying these training data and choosing a set of measures that the classification stage may use, the work of tailoring the classifier is left to the software.

\begin{figure}
\begin{centering}
\includegraphics[width=0.5\textwidth]{jasmine}
\par\end{centering}
\caption{Jasmine GUI}
\label{fig:jasmine}
\end{figure}

\subsection{Representing Training Data}

\subsection{Producing Training Data}

%--------------------------------------------------------------------------------------------------
\chapter{Automating The Learning Process}
\label{ch:automation}

Having constructed a working vision system capable of solving a variety of problems, the feasibility of various automations were investigated.

\section{Automatic Feature Extraction and Selection}
\cite{Sherrah:1997:feature-extraction}

Good training data is essential to produce accurate classifiers. We include the following two characteristics in our definition of 'good' training data. Firstly, the training data should be representative of the test data and this should be consistent across each class. Secondly, the training data should not bias the learning system as to prefer certain classifications or ignore others. The first is rather difficult to control, other than by taking sufficient training data and ensuring that it is consistent. The second offers us more possibilities. 

Irrelevant features may reduce a classifier's accuracy, so it is important that such features be removed or minimised within the training set.

\subsection{Automatic Feature Selection}
The system contains a number of predefined, generic features. Depending on the problem to be solved, some of these will be more useful than others. To make the system efficient, it is necessary to choose which of these features should be used and which should not. A Linear Discriminant Analysis classifier is applied to each terminal in order to determine how useful that terminal is at classification. Ones with better scores are used more often by the GP process. The question arises how best to ensure that some terminals are used more often than others. Fortunately GP already offers a solution to this problem, to each terminal is assigned a fitness and the terminal to be chosen is selected using
tournament selection.

\subsection{Optimising Constants}
Ephemeral random constants (ERCs) play a useful role in Genetic Programming and permit the evolution of thresholds and tunable mathematical functions. However, such is the size of the number space that we tried a variety of methods for improving the quality and usefulness of ERCs in Genetic Programming.

\paragraph{Range Typing}

\paragraph{Intellient Percentages}

\paragraph{Coevolved Constants}

\paragraph{Output Normalisation}
Ensuring all terminals return values within a certain range.

\paragraph{ERC Hill Climbing Optimisation}

\subsection{Results}

... Results to appear here

\section{Automatic Training Data Analysis}

Good training data is essential to produce accurate classifiers. We include the following two characteristics in our definition of 'good' training data.
Firstly, the training data should be representative of the test data and this should be consistent across each class. Secondly, the training data should not bias the learning system as to prefer certain classifications or ignore others. The first is rather difficult to control, other than by taking sufficient training data and ensuring that it is consistent. The second offers us more possibilities. 

Let us first briefly introduce a well known data set to illustrate the problem: the Statlog SatImage benchmark \cite{Asuncion+Newman:2007}. This database was generated from Landsat Multi-Spectral Scanner image data; it consists of the values of each pixel in a $3\times3$ neighbourhood across four spectral bands, thus producing 36 features in total.  Using these data, the central pixel is classified into one of six classes pertaining to the kind of soil present.  There are 4,435 items of training data and 2,000 samples of test data.

When the frequency of each class in the SatImage training data is plotted on a chart (see Fig. \ref{fig:satimage}), it is clear that some classes are represented rather more frequently than others. A Genetic Programming (GP), or indeed any other learning system is likely to concentrate on the most popular classes first, and may ignore the others. Of course if the frequencies in the training data are an accurate representation of data in real life, then this appears reasonable. However, if the frequencies are such that the fitness landscape prohibits the discovery of classifiers which can classify all the classes, then it may be necessary to adapt the training data somewhat.

\begin{figure}
  \begin{center}
    \includegraphics[width=0.75\textwidth]{satlog.eps}
  \end{center}
  \caption[]{Frequencies of different classes in the SatImage data set}
  \label{fig:satimage}
\end{figure}

If this is the case, then a reasonable approach may be to prune some of the classes until each one has the same number of instances, so that no class has any particular bias inherent in the training data. However, in the event that two classes are very similar to eachother, this "kind" of training data may become overrepresented. A second approach to solve this problem was touched on in \cite{roberts:2003:skin}, where it was suggested that k-means-clustering be employed on all the data to divide it into a number of different classes. Once done a certain number of instances would be extracted from each cluster to produce the training data. However, no results were published as to the usefulness of this scheme, so in this report we aim to find out whether it does have any effect, and whether that effect is significantly different to simply pruning the training data to uniform frequencies.

\chapter{Conclusions and Further Work}
\label{ch:conc}

\section{Critical Analysis}
State hypothesis and demonstrate precision, thoroughness, contribution
and comparison with closest rival(s)

\section{Further Work}
An assessment of where the work needs to go from here.

\bibliographystyle{plain}
\bibliography{../../Papers/evo-vision}

\end{document}
