%TODO: Read:http://vision.ai.uiuc.edu/mhyang/object-recognition.html 
\chapter{A Framework for Evolving Solutions to Vision Problems}
\label{ch:vision-system}

% Summary, and stating that the authors software is competitive with other published GP vision research
Following a reasonably lengthy description of the author's Genetic Programming toolkit, and the means by which GP may be put to work in evolving classifiers, the preceding chapter introduced a generic approach to feature detection in images which is able to produce similar results to those published by other GP vision researchers; indeed in some cases the author's generic system was able to evolve solutions to problems that other researchers' task-specific approaches had difficulty with. In this chapter the approach is extended to render it more functional and capable of higher-level understanding. The concept is to integrate one or more stages of feature detection into a larger vision system, providing a basis for extracting more complex content from the image by secondary detectors and classifiers which have an altogether different nature. This secondary stage of processing will be described shortly. The key point is that all domain-specific components of the vision system are evolved by GP: the development of vision systems of this type appears to be novel.  

% Indicating how this will be achieved
The manner in which the different evolved components interact is determined by a straight-forward machine vision architecture, of a type commonly used in conventional computer vision. In this chapter we shall describe the author's approach \cite{oechsle:vision-system}, and demonstrate how it can be used to tackle vision tasks. The framework itself is then extended to render it more applicable to different problems. Toward the end of this chapter, some vision systems generated using this framework shall be presented and assessed.

% Introducing Jasmine
The final key component of the author's software is a graphical interface that automates and simplifies the process of evolving vision systems. It will be shown how training data may be created to supervise the learning of the vision system components, and how a non-expert user can generate working vision systems in a straightforward manner. In this chapter, the idea is to bring together all the concepts discussed throughout the course of this thesis and show how they can be integrated into one software system, capable of the automatic construction of vision systems.

\section{More Complex Vision}
% Feature detector is good...
In the last chapter, the evolution of a generic feature detector was described and evaluated. The results showed that the evolved programs were capable of finding a variety of different features in images, based on colour, texture, and surrounding context. The examples presented give an indication of the kind of domains in which such a detector can be put to work. Feature detection alone, however, is not always enough to yield the kind of high-level information that an end user would appreciate -- in many cases it merely highlights those items within the image that may warrant further inspection. In order for the vision system to be useful, it should make some attempt to identify those detected features, at which point further automated processing by machine could be initiated. Here we shall move on from the detection of features in general to the recognition and classification of particular \emph{objects}.

\subsection{Creating Objects}
% Creating objects from segmenter output.
As we have seen, the feature detector makes an individual decision about every pixel in the image, classifying it into two or more user-defined classes. When plotted into an image this gives the \emph{appearance} of segments, but first the pixels must be joined together into sets for the computer to process them further. Homogenous areas of similarly classified pixels are grouped together into rudimentary ``objects''. Since the feature detection proceeds in a supervised manner, each object can base its initial identifier on the feature classes invented by the user. As well as providing a unique identifier for each, the user can also set whether a class is useful or not. Those objects assigned to a ``background'' class are immediately discarded, leaving only the objects of interest in the scene; see Figure \ref{fig:grouping}.

\begin{figure}
  \begin{center}
    \includegraphics[width=\textwidth]{images/grouping}
  \end{center}
  \caption[Object Grouping]{Object Grouping -- Taking the output from the segmenter and turning it into groups, which in turn can be classified.}
  \label{fig:grouping}
\end{figure}

% Reasons for subsequent processing
This set of objects is the primary output of the feature detector. It  identifies all objects, permitting them to be located and counted. The output can also be used in subsequent processing for two purposes. The first is to analyse each object more carefully to see whether the segmenter was correct in classifying it as such, the second is to identify the object as a member of a more specific sub-class. An example presented throughout this chapter is pasta recognition -- the feature detector cuts out the pasta shapes from the background; the secondary processor identifies the type of each piece.

\section{Classifying Objects}
% The nature of the second classifier
The secondary processor, which processes objects rather than pixels, is, therefore, another classifier. Given a vector of features that describe a given object robustly, the same classification system can be used on each occasion. Once again we first must turn our attention to the means by which a particular object may be described.

\subsection{Shape Descriptors}
\label{shape-features}
The first family of features comprises a series of descriptors that may be used to describe each segment according to its shape or outline. Although an inherently 2D processing operation, the ``silhouettes'' of segmented shapes in an image can yield useful information. Although the author developed these descriptors independently\footnote{One of the perils of an incomplete literature review!}, they are similar to shape descriptors described in the computer vision literature. They include the following:

% Todo: Better descriptions of each of these. Perhaps show invariances in the table
\paragraph{Roundness}
The roundness is calculated by inspecting the edge points of the shape and seeing how closely it approximates a circle, whose edges will all be the same distance from the centre. The function calculates the standard deviation of edge points' distance from the center of the shape.

\paragraph{Rectangularity}
A measure of how rectangular the object is, which is measured by comparing its area to the total area of its bounding box. As a percentage measure, this function is scale invariant. Since the bounding box is perpendicular to the axes, it is not rotation invariant.

\paragraph{Symmetry}
The symmetry may be calculated by looking at how well the shape is mirrored along a particular axis, in this case both the horizontal and vertical axes.

\paragraph{Roughness}
The roughness is calculated by looking at the \emph{variance} in radius between different edges along the perimeter of the shape relative to the centre of gravity. The function works by comparing opposite pixels with respect to a given line of symmetry and awarding points if they have the same value. The points are divided into the size of the shape to acquire a scale invariant measure.

\paragraph{Density}
The outer and inner perimeters of the shape are identified, and the volume of any ``holes'' in the shape are computed. If there are $H$ holes, each with a size of $h_x$, in a shape whose mass is $s$, then the total hole size $hT$  is $\sum_{i=1}^H h_i$. The density is $hT / (s + hT)$. The density measure returns a percentage which is scale invariant.

\paragraph{Number of Corners}
Although it is rather difficult to measure the number of corners in an image, corners are defined as those points where the differential of the tangental angle of an edge is above a certain threshold. This is similar in concept to the Wang and Brady corner detector.

\paragraph{Number of Edges}
Following a process of skeletonisation on the image, the number of skeleton edges can be counted. This is a useful descriptor of the structure of the shape and is scale and rotation invariant.

\paragraph{Number of Joints}
Following the same process, the number of joints, or points at which edges converge can also be counted. This is also scale and rotation invariant.

\paragraph{Maximum and Average Depth}
During the process of skeletonisation, the depth of each pixel from the nearest edge is measured, permitting additional statistics to be calculated regarding the maximum and average depth of pixels in the shape. This can give a rotation invariant indication of the overall thin-ness of the shape.

\paragraph{Balance}
The ``balance'' of the shape is measured as where its centre of gravity falls, compared to its centre point. This can be used as another measure of the shape's symmetry.

\paragraph{Size}
The size descriptor, or number of pixels in the shape, is the most straightforward measure. It is generally useful in discarding smaller segments arising from an inaccurate segmenter or a noisy image.

The observant reader will note that some of these features are invariant to certain geometric transformations\footnote{It is assumed that illumination invariance will have been accounted for by the feature detector.}. Density, for instance, is both scale and rotation invariant. Others, such as \emph{rectangularity} which requires a threshold, is scale invariant but not rotation invariant. 

Some problems do not necessarily require full invariance to all transformations -- OCR for instance is generally expected to work with the letters facing upside-up, as it were\footnote{Humans too are trained this way -- our own recognition of upside down text usually leaves something to be desired! Of course, you can train yourself to read upside down.}. Other tasks, such as pasta detection, are very much dependent on rotation invariant features since each shape may be observed at different angles. The author's feature selection techniques, described in Chapter \ref{ch:low-level}, can be used in a similar manner to discard those features that are not sufficiently robust for a particular problem. Since all data is placed into a common dataset interface, exactly the same procedure can take place, even though the task is quite different. Of course, a secondary process of feature selection will occur during evolution, as those features that do not yield sufficiently fit individuals will become less prevalent within the population.

% Extra features about material - not actually implemented in Jasmine yet
\subsection{Material Features} 
While shape statistics permit classifiers to distinguish basic objects based on their outline shape, they cannot be used in all situations, and indeed discard a substantial amount of information regarding the appearance of the shape itself. Although the feature detector will have selected the shapes on the basis of their sharing a similar material, that material may be as simple as ``not the background''. Therefore there may still be considerable variation in the appearance of segments. It is useful, therefore, to provide features relating to the colour and texture of the segments. 

These features are quite similar to those used by the segmenter (covered in Chapter \ref{ch:low-level}), but are calculated as averages for the whole object. The features include:

\begin{itemize}
\item Average Colour/Intensity Values
\item Colour/Intensity Values Standard Deviation
\item  ``Within Shape'' Haar-like features
\item Intensity Averages for the border of the shape
\item Intensity Averages for the centre of the shape
\end{itemize}
 
The material and shape descriptor features may be used in conjunction -- again the feature selector and the GP system will decide their applicability to  particular problems. Following the process of feature selection, each shape is represented by a tuple of shape or material descriptors, and is sent to the classifier. 

\section{A Framework for Evolving Vision Systems}
It should be reasonably clear to the reader how these components may integrate readily into a two stage architecture, generating vision systems that can cut out arbitrary parts from the image, and then make higher-level decisions about them. The first phase is required for the detection of objects in the scene, and the second aims to classify each object into a particular class. This system is illustrated in \figref{fig:vision-system} with reference to the pasta recognition example. Such an architecture is sufficiently abstract as to cover a variety of different problem domains, and is commonly used in conventional computer vision.

\begin{figure}[!ht]
  \begin{center}
    \includegraphics[width=\textwidth]{images/vision-system-diagram}
  \end{center}
  \caption[Vision System 1]{The First Vision System Used for Experimental Work}
  \label{fig:vision-system}
\end{figure}

\subsection{An Extended Architecture}
Towards the end of this chapter we shall see some examples of vision systems created using this framework, including a gesture recognition system and pasta recognition system, which are certainly quite different domains. Both of which were created using the framework described above \cite{oechsle:vision-system}. However, the initial framework implies certain restraints that limit its applicability. Chief among these is the requirement that the object be cut out in its entirety by the segmenter. In most situations this demands that the shape must be relatively homogenous. This is sufficient for objects like pasta, which (should!) be composed of a single material. However, some objects do not suit this approach -- such as the flags in the author's Flag data set (introduced on page \pageref{flags-dataset}). The segmenter can either cut out flags from the background in their entirety, or segment individual colour regions of the flags. In the first case, the  object classifier would make the startling discovery that all flags are rectangles; even with average colour information the overall shape descriptor features may not be concise or robust enough to make accurate distinctions between them. In the latter situation it would be be unable to understand how the different components related to each other.

The author's solution is to divide the process of segmentation/feature detection into two stages: a background subtraction phase, followed by a process of finer segmentation. In the case of the flags dataset, the first detector would cut out the flags in their entirety from the background to identify the objects. A second phase of feature detection could then proceed \emph{within} each flag, this time segmenting based on colour, attaching a number of ``sub-objects'' to each object. Each object is thus described as a basic hierarchy -- another technique employed to make sense of scenes in conventional computer vision.

% Todo - examples as bullet points here.
The sub-objects are processed into shapes in the same manner as the main object. Descriptors relating to the sub-objects can then be used to help with the classification of the main object. Examples may include the number of ``red shapes'' within a given flag. Thus, as well as being able to represent content as a basic hierarchy of objects and sub-objects, additional information becomes available to help with the process of classifying the object. Furthermore, by dividing the feature detection stage into two parts -- background subtraction and segmentation -- the task is made more straightforward; the segmentation stage in particular can be evolved more easily, because it need only operate within the confines of specific objects defined by the background segmenter. This is a process in some ways analogous to binary decomposition, which was shown in Chapter \ref{ch:gp-classification} to learn solutions more rapidly than multi-class classification performed during a single run.

% Again - examples as bullet points
The approach can actually be extended further, such that the sub-objects can themselves be classified. In the case of the Flags dataset, the sub-objects can be classified as ``stripes'', ``crosses'' etc. The types of sub-objects can thus be of assistance when classifying the main object -- it can make use of features such as the number of ``white crosses'' within the flag. Later in this chapter, we shall also see an example where sub-object classification can yield useful information directly. A diagram of this second vision framework, which comprises up to four different evolved vision components, is shown in Figure \ref{fig:vision-system2}.

\begin{figure}[!ht]
  \begin{center}
   \includegraphics[width=\textwidth]{images/vision-system-diagram-2}
  \end{center}
  \caption[Vision System 2]{The author's updated vision system framework. It is composed of up to four evolved components (shown here in green). Following a process of background subtraction, which locates the objects in the scene, a secondary process of segmentation may be initiated to detect sub-objects within each object, distinguished by different material. The sub-objects may themselves be classified, and that information can either be outputted directly or added to the object classification feature set. The objects themselves may also be classified to produce useful high-level output.}
  \label{fig:vision-system2}
\end{figure}

\subsection{Discussion}
One could argue that any framework for designing systems will usually introduce limitations in flexibility, which could be at odds with any claims of genericity. Nonetheless, there are two good reasons to make use of such a architecture. Genetic Programming is a powerful tool for automated feature selection and learning\dots provided the task itself is not unduly ambitious. While it is tempting to provide the GP toolkit with a generous set of components, sufficient for Turing-complete programming, and to leave it to evolve a complete vision system in a single run, the reality is that the learning process would probably not yield anything particularly useful, at least in the limited time available for artificial evolution. As we saw in Chapter \ref{ch:gpcomparison}, the search space can grow to enormous proportions quite easily. Since time and processing are always limited, a practical reaction is to divide the task into separate components. The author believes that this partitioning into a pipeline of separately-evolved stages is critical as it allows a range of domain-specific operators to be used in each stage without causing an explosion in the dimensionality of the search space. 

The second advantage of using a framework is that users do not need to start from scratch each time they attack a new problem. Given a fixed set of objectives or processes, it becomes easier to automate the production of systems in general, and to ensure the useful ideas and concepts discussed earlier in this thesis are made use of. Indeed, the author's software encapsulates the vision system architecture into a single user interface, permitting the advanced user to generate vision systems within a couple of hours. 

\section{Jasmine}
\label{jasmine}
Having developed a reasonably generic vision system architecture, which is dependent upon one or more evolved vision components, a significant challenge is the creation of a unified interface by which the user can provide training data to the system and thus produce  vision systems with minimal effort. The author was inspired in this regard by work by Brumby \emph{et al.} \cite{Brumby:2001:remote} on a project called GENIE (``Genetic Imagery Exploration''), which included a basic user interface named \emph{Aladdin} for marking up images for binary segmentation. The author's own interface, named Jasmine\footnote{Jasmine was a character featured in the Disney adaptation of Aladdin, and has the advantage of starting with `J', a crucial requirement for all applications written in Java. In line with the best traditions of computer science, the name is a recursive acronym which the author fancies as standing for ``Jasmine: A Segmented IMage Notation Environment'', or (a suggestion by Riccardo Poli) ``Just Another Simple iMage Interpretation Environment''.}, which was initially similar in functionality to Aladdin, later extended into a reasonably substantial platform for producing evolved vision systems. Besides its support for object recognition as well as segmentation, Jasmine is distinguished from Brumby's interface by its support for arbitrary numbers of feature classes; users may create and use as many classes as they wish. It has already been mentioned in passing that classes can be embellished with meta-data, for instance stating that it is a ``background'' class: that information is used later by the vision system.

The software is project-based, meaning that users can import a series of images, create training data and evolve solutions, with all the information being saved together in one file. This permits a problem to be shared easily, and for a user to resume their work quickly. Training images may be added to the project either from pictures on disk or directly from a compatible video camera. 

In this section, the author will describe how a user may go about using Jasmine to produce a vision application concerning the recognition of different shapes of pasta. The process starts by choosing appropriate classes, in this case ``pasta'' and ``background'' and labelling the training images appropriately.

\subsection{Training Procedure}
By this point the reader should no doubt be familiar with the concept underlying the author's feature detection procedure, which works by making a decision about each individual pixel. The detector is evolved using a supervised learning paradigm in which programs are selected according to their performance against a training dataset: a series of examples for which the ``correct'' class has been established. Since most images are composed of tens if not hundreds of thousands of pixels, generating meaningful training sets can be time intensive. One way to create the training set is to create a binary mask to fit over a given image, which defines which pixels in the image belong to a given class and which do not. This can be performed using off-the-shelf graphics software such as Adobe Photoshop\textregistered. However, in the author's experience, marking up \emph{every} pixel in an image is not always a good idea, as some parts of the image cannot be assigned to one class with absolute certainty. If the user does fully mark an entire image, the training data may contain contradictions that are broadly invisible to the human editor (seeing only the bigger picture) but nonetheless confuse the learning system.

The author started his experiments using this approach and can attest that such masks are tiresome to create! Furthermore, they do not readily permit the marking of more than two classes. For this reason the author commenced development of Jasmine, which permits the user to mark up parts of a scene by roughly ``painting'' overlays, one per class, onto one or more training images (see \figref{fig:jasmine1}). The whole image need not be marked up, the user can select those pixels most representative of a particular material -- the Genetic Programming process will discover the boundaries itself. In Chapter \ref{ch:low-level} it was shown how samples from multiple images could be taken without using excessive amounts of memory. All the feature detectors demonstrated at the end of Chapter \ref{ch:low-level} were evolved using datasets produced in Jasmine.

\begin{figure}
  \begin{center}
    \includegraphics[width=\textwidth]{images/jasmine1}
  \end{center}
  \caption[Creating Training Data]{Creating training data via a graphical
    user interface in which the user simply ``paints'' the different
    classes onto a training image. We shall use the detection of pasta as an example throughout this chapter.}
  \label{fig:jasmine1}
\end{figure}

\subsection{Training Data Selection}
Painting classes directly onto images is a reasonably painless means by which to produce training data, but each stroke of the mouse can add hundreds of new pixels to the training set. It does not take long before the training set is filled with hundreds of thousands, it not millions, of pixels. As was mentioned in Chapter \ref{ch:low-level}, each pixel individually does not convey a huge amount of information; indeed two adjacent pixels will often exhibit similar characteristics. Therefore, there is good cause to reduce the training set size such that evolution can proceed more briskly. Preliminary experiments by the author reveal that segmentation training data can typically be pruned by about 80\% with no significant loss in accuracy on test data.

Having decided to prune the training data in some way, we now turn to reasonable methods for doing so. The author's approach is to discard a certain proportion of training data while maintaining the approximate class distributions, similar to the technique employed in stratified k-fold cross validation. This first method shall hereafter be referred to as ``by Class'' selection. Another sensible suggestion in this regard was made by Roberts and Claridge \cite{EvoVision:Roberts-Claridge:2005}, who proposed using k-means clustering to group the training data into ten classes, after which an equal number of points are taken from each class. This, they said, would ensure that each type of pixel would receive an equal representation in the training data, and would permit the training data to be smaller. Their approach is referred to hereafter as ``by Cluster'' selection.  However, no results were published to prove their claim one way or the other. Table \ref{table:training-data-selection} shows the results of an experiment conducted by this author in order to determine the difference between the two techniques on imaging datasets. The training dataset was culled to approximately 20\% of its former size on three different vision datasets, using both techniques. The results, averaged over 50 runs, are the error for the classifiers on test data, which was left full-size. The result of an independent samples T-Test is also shown.

%Training-data-selection.xls
\begin {table}[ht]
\centering 
\begin {tabular*}{0.8\textwidth}{ lrrl }
\toprule
Data Set	& By Class & By Cluster & Result	\\ \toprule
Flags		& 0.048	& 0.057 		& By Class is better, p = 0.0369 \\ \midrule
Pipelines	& 0.039 	& 0.042 		& By Class is better, p = 0.0008\\ \midrule
Leaves		& 0.158 	& 0.191 		& By Class is better, p = 0.0121 \\ \midrule
\end {tabular*}
\caption [Training Data Selection]{Comparison between different training data selection techniques}
\label {table:training-data-selection} 
\end {table}

The results show that the ``by Class'' method produced better results on each of the datasets, which in some ways is not surprising because the test set is more likely to be similarly stratified to the culled training set, so the experiment is somewhat biased. However, if we are interested purely in the results, it would appear that the clustering method does not, in fact, offer any advantage.

%TODO: Can Adrian advise on a better way to conduct this experiment?

%The training data is saved in a simple way - a record is made of every labelled pixel, based on its image, its location and its chosen class. For the shape training data, each segment is recorded as a collection of pixels, again with a classID. The training data can be exported in various different formats, including to CSV files for export to arbitrary data sets, and as binary images so that the data can be used in other environments.

\subsection{Feature Selection}
Once the user is satisfied with his/her artistic endeavours, he/she may employ either of the above techniques in order to select a fixed number of samples; the relevant pixels are extracted and formed into a set of training data for the feature detector's evolution. However, before the process of evolution is started, it is worthwhile selecting the most useful features. The feature selection techniques described in Chapter \ref{ch:low-level} are implemented within Jasmine, and can be invoked to automatically cut the feature set down to a suitable size, shown in Figure \ref{fig:jasmine2}. 

\begin{figure}
  \begin{center}
    \includegraphics[width=0.66\textwidth]{images/jasmine2}
  \end{center}
  \caption[Jasmine Feature Selection]{Feature selection is performed directly within Jasmine.}
  \label{fig:jasmine2}
\end{figure}

Returning to our pasta example, the figure shows that the most useful feature was identified as the saturation level of a particular pixel, which appears to be a wise choice -- the pasta shapes are a reasonably saturated shade of yellow, but the background in this simple example is textured but mainly grey. The second highest feature is a texture feature. The user may still choose to disable the colour features -- forcing the software to develop a system that works on grey-scale images, or disable features that are computationally expensive in order to evolve a more efficient detector.

\subsection{Feature Detector Evolution}
Following the process of feature selection, a final dataset is produced and fed to the author's GP classification system (see Chapter \ref{ch:gp-classification}). Jasmine can automatically choose the appropriate classifier representation by running short mini-evolution runs; it may choose either DRS2 or ICS. As we saw, ICS tries many of the tricks a human would in finding a suitable classifier, including performing binary decomposition, experimenting with different parameters and trying out classifier ensemble techniques. In Chapter \ref{ch:gp-classification} a number of classification representations were described; it was shown that classifier ensemble techniques can improve the accuracy of the classifier, but they have the disadvantage of slowing down the process of classification (several decisions must be made per pixel instead of one). In the case of the feature detector, which must make decisions for tens of thousands of pixels, this is not ideal but may depend on circumstances -- the user is given the option whether to use classifier ensembles or not, although by default the option is switched off for feature detection.

While the feature detector is being evolved, a live preview of its performance on the training images is shown (see Figure \ref{fig:jasmine3}). This can give a good indication of how the detector performs on entire images, especially when the training data is taken from just a few representative samples on each. Sometimes it becomes clear that certain characteristics in the image are under-represented. Based on visual observation, the user may choose to update the training overlays; often discrepancies become clear quite soon into the evolutionary process. Thus the user can iteratively improve and fine-tune the training data to produce the desired result.

Once the classifier has gobbled up the data and completed its business, the evolved feature detector is saved and automatically compiled to Java byte-code. This means the code can be executed without the need for interpretation of the GP tree, and runs at the same speed as hand-written code.

\begin{figure}
  \begin{center}
    \includegraphics[width=\textwidth]{images/jasmine3}
  \end{center}
  \caption[Live GP Evaluation]{As the GP evolves a solution, the best of run individual can be run immediately on training data to visualise how well the program is performing}
  \label{fig:jasmine3}
\end{figure}

We have seen so far the process necessary for feature detection (in this case background-subtraction) on the simple pasta dataset. The process of segmentation (which yields the sub-objects) can proceed in a similar manner. However, the pasta experiment does not demand the extra step, so we can skip forward to the object classification stage. 

\subsection{Object Classification in Jasmine}
Once the feature detector has been evolved satisfactorily, the user may deploy it on the training images such that individual pieces of pasta are cut out as objects. The user may then define another set of classes that define the higher-level characteristics of the objects. In this case this may be the \emph{type} of pasta\footnote{`penne', `conchigle', `fusilli', `farfalle', etc}. As will be shown shortly, the number of classes required in some circumstances can be quite large -- over 30 in some cases. The author does not recall having seen classification by GP beyond 16 classes, which itself is unusual: usually the number is around 4--5. In Jasmine each object can simply be clicked on to assign it a particular class.

% TODO: Image of clicking each object to select it and assign it a class.

When the user's mouse finger is tired, the shapes may be used to assemble another set of training data, this time using the features described in Section \ref{shape-features}. These features are passed through a second process of feature selection, this time with respect to the object classes, and the classification system is invoked once more. Due to the relatively small number of shapes within the image relative to the number of pixels, the system can be indulged in using classifier ensembles, which generally improve accuracy (in the author's experience). 

Again, if pasta were more complex, we may have run a classifier for sub-objects first. In the case of the vision system, the sub-object classifier must be run before the object classifier, such as to provide the object dataset with more information. Such practicalities are taken care of by the author's software -- the end user need only concentrate on evolving the components, which can then be added to a visual representation of the vision system in Jasmine.

After the evolution of each stage, the evolved component can be evaluated against a series of test set images, not used in training, to assess how well the evolved solution copes with unseen data. The software can calculate accuracy metrics for each component in the vision system.

%\subsection{Validation}
%  This gives the system developer insight into how difficult each of the stages are; they may choose to tailor the training set to incorporate novel characteristics. At this stage the process becomes iterative: the user may decide that they need to include more training data in order to make the system more robust.

\subsection{Vision System Object}
A separate vision-system program stores all the evolved components and performs the necessary in-between processing. Following the evolution of all necessary components, this vision system program may be exported into outside applications  of the user's choice. The vision system raises events at appropriate times during processing, permitting other software to interact with it. In the next section we shall see how the vision system performs.

%This completes the description of the author's software and activities undertaken during the course of three years' research. What follows are some results using the software, again for a variety of different domains.

\section{Results}
\label{vision-system-results}
This final results section presents examples of the vision systems that can be generated using the author's framework. We shall start with those systems using the author's initial two-stage architecture, then move onto problems that demand the extra steps of the author's second, more complex architecture. Numeric results will be shown wherever possible; the quality and applicability of the solution will be assessed in each case.

%TODO: How many Pasta shapes were there?
\subsection{Pasta Shape Recognition}
Approaching the end of this thesis, the reader may be rather tired of pasta, or indeed vaguely hungry. Nonetheless, having discussed it during this chapter, it seems fair to present the results of the vision system. The feature detector, which cuts out pasta shapes, was evolved using the author's DRS2 technique in approximately 90 seconds on a modest 3Ghz single core machine. It achieved a high accuracy of 99.9\% on training data. It was then put to work on a series of previously unseen images for the purposes of detecting objects, in this case individual pieces of pasta, of five different types. The detector yielded a sensitivity of 100\% and a specificity of 97.4\% with respect to detecting the pasta shapes on test images. These are high levels of accuracy; we shall shortly see whether they yield in accurate classifiers -- a better test of their utility.

Each object was labelled into one of 5 different classes corresponding to different pasta types; producing an object training set of approximately 500 samples and a test set of 1250 samples\footnote{The author's mouse finger was quite tired at the end; fortunately each training image only contains instances of one type of pasta -- Jasmine includes an option to classify every object in an image into a particular class which reduces the number of mouse miles to be travelled!}. This is a straightforward process of clicking on each shape in each image to assign it an appropriate class. A shape classifier was then evolved using ICS in approximately 2 minutes and was able to achieve 96.8\% accuracy on the object dataset. Thus the total accuracy of the system on test data is 96.8\%, which corresponds to the likelihood that any piece of pasta in the images can be detected, located and correctly identified. An example of the system working this is shown in Figure \ref{fig:pastavs} below. The system was developed in a morning, which included generating the training data.

\begin{figure}
  \begin{center}
    \includegraphics[width=0.66\textwidth]{images/pasta-vs}
  \end{center}
  \caption[Pasta Recognition]{The Pasta Recognition Vision System, working on an unseen image.}
  \label{fig:pastavs}
\end{figure}

\subsection{Hand Gesture Recognition}
The second experiment concerns the recognition of hand gestures.  Although this kind of problem has been tackled effectively by researchers using other learning techniques, notably by Starner \cite{starner98realtime}, it has not previously been investigated using Genetic Programming\footnote{Although it has been used for hand detection in shape silhouettes by \cite{EvoVision:Johnson-Maes-Darrell:1994}, see page \pageref{johnson}.}. The author devised a set of ten different hand gestures, some of which are shown in {Figure \ref{fig:postures}}. 
%Some 300 sample images were taken, and then rotated and scaled in different ways to produce a data set of 3000 instances. Half were used for training with the other half reserved for testing.

\begin{figure}
  \begin{center}
    \includegraphics[width=0.85\textwidth]{images/posture-types}
  \end{center}
  \caption{Examples of some of the hand gesture types.}
  \label{fig:postures}
\end{figure}

A training set of images was developed using images captured using a webcam, which can be loaded directly into Jasmine. Two classes were created: ``skin'' and ``non-skin'', and a series of training samples were marked up in the usual fashion.

A background subtracter was evolved to distinguish the two, and achieved an accuracy of 96.4\% on a reduced training set comprising approximately 15,000 pixels, and accordingly could be evolved rapidly. The feature selection process was run as normal, but some of the computationally expensive features were disabled manually to ensure the detector could run quickly. The detector was able to cut out hands from test images with a sensitivity of 99.6\% and specificity of 94.3\%.

The ten different classes were then added to the project, and each hand ``object'' was then labelled with the appropriate class. An object dataset was produced, consisting of some 600 hand images, with 200 used for training. Unsurprisingly, the feature selector revealed that shape descriptors were the best available means of classifying these objects. 

ICS was put to work learn to classify the gestures and achieved an accuracy of 96.2\%, yielding a final accuracy per gesture of 95.8\%. The vision system was developed in approximately 2 hours. Since the primary application of gesture recognition is human-computer interaction, it is essential that the vision system work in real-time. The system was able to recognise hand gestures at a rate of 6 frames per second, shown in Figure \ref{fig:postures2}.

\begin{figure}
  \begin{center}
    \includegraphics[width=0.85\textwidth]{images/postures-test}
  \end{center}
  \caption[Posture Vision System]{The posture vision system working on a webcam in real time.}
  \label{fig:postures2}
\end{figure}

%A video is available here...

%\subsection{OCR}
%The third experiment concerns a different domain -- that of character recognition, an area that is usually dominated by the neural networks. In this case the author chose to try musical OCR -- the reading of sheet music by computer. This is, in some ways more difficult than normal OCR because the objects are not clearly defined but overlap stave lines. 

\subsection{Lesion Classification}
In the last chapter, the author's generic feature detector was applied to the task of skin lesion segmentation (see page \pageref{skin-segmentation-results}). Without a ground truth from an expert, it is difficult to assess how accurate the author's segmenter was, although from a layman's point-of-view, the system seemed to identify the lesion boundaries accurately, was not affected by hairs or other skin features, and could work on a variety of different skin colours. It has already been stated several times that the performance of a vision technique can also be assessed by its \emph{utility} -- is its output meaningful enough for higher-level decisions to be taken? Fortunately it is somewhat easier to find images from medical databases which state the type of lesion -- either a benign nevus (mole), or malignant melanoma (a particularly unpleasant form of skin cancer). Although it is sometimes difficult to tell the two apart (malignant melanomas will often grow out from moles), medics have devised an ``A-B-C-D'' test to distinguish malignant melanomas, which are typically A-symmetric, have irregular B-orders, uneven C-olor, and have a D-iameter over 6mm. Although the last criterion is difficult to measure from images when there is no idea of scale, the author's vision framework should be quite well placed to assess the first three and classify the regions previously extracted using the lesion feature detector.

A set of 68 images were acquired by the author, which had been identified by dermatologists\footnote{The images came from the Dermnet Skin Disease Image Atlas, www.dermnet.com.}. The images were loaded into Jasmine and processed in the same manner as was previously described. A segmenter was evolved to cut out the lesions, with an object classifier later employed in order to classify them as being malignant or not. Since it was difficult to acquire a large number of appropriate images, 10-fold cross validation was used to assess the result of the classifier, which achieved an average accuracy of 85.8\% on test data following 50 runs.

This result shows that the author's system can extend the functionality of vision components evolved by other GP researchers, and also goes some way to demonstrating that the output of the segmenter is meaningful. 

Despite attempts to acquire the original datasets cited by other researchers in their results, it was unfortunately not possible to acquire the same sets. In order to develop some means of comparison, or an assessment of the difficulty of the images themselves, the author developed a web-based training system by which humans could learn to discriminate between different lesions by following examples after an introduction to the ``A-B-C-D'' rule. They then had their new ability tested. The system used the same procedure as the GP system, with 90\% of the images used for training and 10\% reserved for testing. The results from 50 respondents were interesting: the average error on test images was 81.3\%, indicating that the author's GP system is competitive with amateur humans. 

\subsection{The MNIST Dataset}
Optical Character Recognition (OCR), has been mentioned at several points during this thesis, as it is a good example for a variety of different processes, including thresholding,  template matching or shape analysis. Indeed, the author's software has already been put to work on the detection process for musical notes. The cogitant reader have considered whether the author's system is suitable for other character recognition tasks. A background subtractor can be evolved to cut out shapes, and some of the shape descriptors may do a good job of characterising letters. 

To compare its performance relative to other techniques for this task, the author's system was applied to the MNIST dataset \cite{mnist}, a large set of hand-written digits (0--9), collected from hundreds of writers. The dataset consists of 60,000 training samples and 10,000 test samples (see Figure \ref{fig:mnist} for a few examples). Although the recognition of printed Latin characters is regarded by some as a solved problem,  the recognition of \emph{hand-written} characters remains a more difficult task, due to the high variation in written forms.  

\begin{figure}
  \begin{center}
    \includegraphics[width=0.5\textwidth]{images/MNIST}
  \end{center}
  \caption{Random examples selected from the MNIST database.}
  \label{fig:mnist}
\end{figure}

Unfortunately Jasmine could not be used for this purpose, because the author did not feel up to hand-labelling all the digits manually! The author instead wrote a programmatic interface to produce the training set. A background detector was evolved by GP, which was trivial in nature. A process of feature selection took place in order to select the most useful features. The system was then left to its own devices to develop classifiers.

The system took, on average, 50 minutes to produce a multi-class classifier using ICS. The average accuracy following 10 runs was 92.7\% on training data, and 90.6\% on test data. The results, compared to other approaches, are shown in Table \ref{tab:mnist}. Although some techniques in this case, notably the Support Vector Machine, achieved significantly better results than the author's system, the result by ICS is nonetheless reasonably competitive with other approaches, and quite reasonable for a generic system! The addition of further features may help improve the result further.

\begin {table}[ht]
\centering 
\begin {tabular}{ lcccccc }
Dataset & 	Result	\\ \toprule
ICS		& 90.6 $\pm 1.3$ \\ \midrule
Neural Network		& 88.0 \\ \midrule
K-NN		& 95.0 \\ \midrule
SVM		& 98.4 \\ \midrule
\end {tabular}
\caption { Results on the MNIST database test data.}
\label {tab:mnist} 
\end {table}

We saw in Chapter \ref{ch:cvsurvey} Teredesai used Genetic Programming to recognise characters on the NIST dataset (of which MNIST is a subset). Teredesai used a set of image features specifically designed for the purposes of OCR. Teredesai reported results of binary classifiers \emph{per class} of between 95.9\% and 97.6\% each. Assuming the best case, and equal class distributions, this yields an overall accuracy of $0.976^9$ or 80.3\%. This is the closest comparison available from other Genetic Programmers; again it indicates that the author's generic approach is competitive with the more specific attempts by other GP researchers.

\subsection{Flag Recognition}
Moving onto the author's more complex vision system architecture, we encounter once more the author's Flag dataset, which comprises a number of flag images captured using a webcam. The dataset consists of images of flags from 16 EU member states. Since flags are primarily defined by their colour, the dataset is a test of the vision system's ability to recognise colours accurately. The first stage is to detect the flag images from the background (the author's desk), which is relatively straightforward  given its reasonably plain nature. Accordingly the flags could be extracted on all occasions from the test set following the evolution of an appropriate background detector by GP. The second stage is then to identify the colour of objects within each flag -- 7 classes were identified: Red, Yellow, Green, Dark Blue, Light Blue, White, Black; these were inputted into Jasmine and a further set of training data pixels was produced. Following the evolution of the colour segmenter, on the test set the colour segmenter achieved an accuracy of 91.5\%. This accuracy was boosted to 97.1\% by the author's classifier ensemble technique. 

The segmenter permitted the system to identify the sub-objects within each flags; the individual coloured shapes that make up the flags' designs. Four further sub-object classes (`long stripe', `short stripe', `cross' and `other') were added to the project, and instances of each were labelled to generate a sub-object dataset. A sub-object classifier was then learned by ICS, which achieved an accuracy of 98.2\%. 

Given this information, including the other colour and shape information, the flags themselves were finally classified, again using ICS, which achieved an accuracy of 95.9\%. The accuracy per flag therefore was 95.9\%. The vision system was developed in approximately 2 hours.

\begin{figure}
  \begin{center}
    \includegraphics[width=1.0\textwidth]{images/flag-recognition}
  \end{center}
  \caption[The Flag Vision System in Action]{The Flag vision system in action. The Flags are cut out from the background and then segmented in order to yield sub-objects within each. This information is then used to decide the class of each flag, displayed on the right side.}
  \label{fig:flagvs}
\end{figure}

\subsection{Automatic Number Plate Recognition (ANPR)}
We shall complete the results in this section with a task relating to images in a much less constrained environment, which again makes use of the author's more complex architecture. The problem concerns the detection, location and reading of car number plates. Over the last decade or so, ANPR systems have become quite ubiquitous, and are used extensively by the police, in traffic cameras, and in petrol station forecourts.  Although many ANPR machine vision systems use infra-red filters to identify number-plates optically, the author developed a similar system using pure vision software. The system was trained on a series of images taken from cars in a local car park, and tested on images of cars in motion, travelling past the author at 50--60mph. 

The first stage is to detect the number plates using a background subtractor. As before, examples of numberplates and non-numberplates were marked up on Jasmine, with a suitable discriminator learned by GP. The evolved solution achieved an accuracy of 99.0\%, following just 40 seconds of evolution. Since UK rear number-plates are a relatively specific shade of yellow, the background-subtractor was reasonably straightforward to construct. However, there are often other similarly coloured objects within a scene. Two object classes were created to distinguish true numberplates from other yellow regions, and another object dataset was created. A classifier was developed in order to identify the true number plates, this time based on their shape; it was essentially a rectangle-finder. Although the author's system seeks to classify sub-objects before objects (to aid the object recognition process), if the object is found not to be rectangular, then any identified digits are ignored.

The third stage of evolution was to develop a segmenter that can accurately distinguish characters on the number plate as sub-objects. A separate set of training data for this purpose was painted in Jasmine and another segmenter evolved. The segmenter was then deployed into the ANPR vision system. The sensitivity of the system, or the probability of any letter being correctly detected, was 99.4\%. Fortunately the detector doesn't have to detect \emph{every} pixel in the letter, but sufficient ones to identify its shape.

Each character was then labelled appropriately, yielding a dataset whose members represented 34 different alphanumeric classes (all numbers and all letters apart from Q and I). This is a significantly larger number of classes than has previously been tackled by GP vision researchers, or indeed in GP OCR tasks. The final process, of sub-object classification, was then initiated. Each letter in each training numberplate was labelled with the appropriate sub-object class, and a classifier was evolved using ICS. Each letter was classified with an accuracy of 98.4\%. This means that the probability of correctly segmenting \emph{and} classifying a given letter by the system is 97.8\%. If a number plate is generally composed of 7 letters, then the probability of getting the whole plate right is 85.6\%. The vision system was constructed in the course of a day, which included taking pictures of the vehicles. Figure \ref{fig:labelled-anpr} shows the process in action. 
% Probability of letters being correctly segmented: 1 / (2 / 339) = 99.39%
% Probability of letters being correctly classified: 99.38
% Probability of letters being correctly classified overall: 98.77
% Probability of getting the whole number plate right (7 chars):98.77^7 = 91.7%

%FMI: I said earlier that the sub-object detector happens first, so the letters will be attempted to be classified. If the object detector then decides that the numberplate is not rectangular, then the results are discarded.
\begin{figure}
  \begin{center}
    \includegraphics[width=1.0\textwidth]{images/anpr-new}
  \end{center}
  \caption[An Evolved Vision System Recognising and Reading Car Licence Plates]{An Evolved Vision System Recognising and Reading Car Licence Plates. The background segmenter (top right) identifies the areas of number plate. The segmenter (bottom left) then cuts out the letters, which are individually classified and labelled in order to read the plate (bottom right).}
  \label{fig:labelled-anpr}
\end{figure}

\section{Applicability}
In this chapter the author has presented a framework based on learning by GP for producing vision systems. Throughout, the features and learning systems have been assessed according to their genericity, or applicability to a wide range of problems. Indeed the examples just presented are representative of a reasonably diverse set of tasks -- more diverse, at least, than has been reported by GP researchers to date. Still, there are a number of limitations to the applicability in this approach, which merit a brief discussion of their own. 

One limitation is manifested in results on COIL-100 dataset \cite{coil100}. The dataset consists of images of 100 different objects. Each object is rotated 360$^\circ$ about an axis roughly perpendicular to the camera view in 5$^\circ$ increments. The author's system, however, uses features that are not invariant to this type of rotation. An experiment was run to assess whether the author's software could develop a vision system could distinguish among all the objects, and to analyse the extent to which the software is invariant to this kind of rotation. The author's system was put to work on the dataset in much the same way as before, first segmenting the objects from the background, then performing a finer process of colour segmentation, then evolving an object classifier.

\begin{figure}
  \begin{center}
    \includegraphics[width=0.75\textwidth]{images/coil-accuracy}
  \end{center}
  \caption[Results on the COIL-100 Image Dataset]{Results on the COIL-100 Dataset, (attained using cross validation). Results are shown for a number of angle ranges. As the range of angles increases, so the performance of the classifier decreases.}
  \label{fig:coil-results}
\end{figure}

The results of the evolved solution for different amounts of rotation are shown in Figure \ref{fig:coil-results}. For small changes in angle, the author's system is reasonably accurate (achieving an accuracy of 92.7\% for rotations within $\pm$ 10$^\circ$), certainly given the number of classes, which is far beyond the number usually tackled by GP researchers investigating multi-class classification. Nonetheless, it is clear that the author's vision systems are inherently limited to two dimensional problems -- the figure shows that the performance of the system degrades markedly as the extent of rotation is increased. A new set of features is necessary to render the author's software more capable of a wider range of tasks in three dimensions. Of course any function that returns 3D invariant information could be plugged into the author's framework. 

In the author's opinion, the other key limitation of the existing framework is its inability to cope with occluded or overlapping objects, which would otherwise be treated as a single large object that would probably be mis-classified. Although the feature detector can be trained to divide objects using a number of metrics, including edges, it is difficult to \emph{insist} that it does so. One solution is to implement an idea (proposed by Campbell \cite{campbell97}, see page \pageref{campbell-segmentation}) in which the image is first pre-segmented using a watershed or other unsupervised learning technique. Given suitable parameters, such approaches tend to over-segment but this process also tends to preserve edges. Segments could then be combined together using Genetic Programming to assess their similarity, taking account of edges between. A further discussion of applicability and extensions to this work awaits the reader in Chapter \ref{ch:conclusions}.

The addition of extra features may also help improve the accuracy of the vision systems developed by the author's framework. Although it was shown that a given letter in the ANPR task could be classified at a rate of 97.8\%, this would lead to a probability of recognising only 85.6\% of entire plates entirely correctly, which police or security organisations might prefer to be a little higher before placing orders for the first GP-evolved ANPR system! The author's system works on images in quite a ``raw'' way -- additional pre-processing operations such as normalisation or shape de-skewing may yield more robust results that bring the author's software into the range of genuine commercial applicability.

\section{Conclusion}
This brings us to the end of the experimental work in this thesis. In this chapter we have covered extensions to the author's feature detection software which permits more complete vision systems to be constructed using GP. Some are able to run in real time. In this thesis the author has explored the means by which a reasonably large range of problems can be tackled by a generic GP approach. In the next, final chapter, the applicability and limitations of the author's approach will be discussed in more detail.

