% TODO: 
% Discuss the Production of Training Data - ALADDIN, GAMERA etc.
% Read:http://www.cim.mcgill.ca/~dparks/CornerDetector/background.htm

\chapter{A Brief Overview of Computer Vision}
\label{ch:cvsurvey}

In 1932 a small group of students at Harvard Business School commenced work on an ambitious project. They were lead by a man named Wallace Flint, whose idea was to develop a system by which products in a catalogue could be identified by a unique code that was readable by machine. Given a set of punch-cards from the customer, the system could then go about producing an invoice and updating the stock count automatically. Unfortunately for Flint and his students, the world was in the midst of the worst economic depression of the 20th century and his idea failed to gain momentum. It was another twenty years before the birth of the modern barcode and a further two decades before it finally caught on in a mainstream sense in the mid-1970s. It could be argued that barcode readers are now the most ubiquitous machine vision systems in use throughout the world -- indeed it would be inconceivable for most modern stores to operate without them. The use of barcodes has extended beyond retail too -- they are used for ticket validation in sports venues, provide mobile-phone-readable hyperlinks to web pages, and have been employed in miniature form in order to identify and track the movement of individual bees. Like most machine vision systems, barcode readers automate and simplify complex or tedious aspects of modern life; such systems are both desirable and profitable. Unfortunately vision in a truer sense cannot be confined only to the highly-constrained patterns apparent within barcode patterns, but should be applicable to images in general. 

The reader will probably be familiar with the well-known saying that ``a picture is worth a thousand words'', which somewhat \emph{understates} the complexity inherent in imagery. Indeed if it were possible to summarise any image in a mere thousand-word pr{\'e}cis, the work of the computer vision developer would be easier! Still, most of us are familiar with the ability of computers to process complex data much more rapidly, accurately and patiently than can we, but software is typically dependent upon the data being well organised or carefully encoded. Images, by contrast, are usually characterised by large amounts of unstructured, redundant or irrelevant information that hamper the machine's ability to perceive that which we can see so easily. Computer vision is the area of study concerned with making sense of images in such a general sense. It incorporates a broad range of different sub-topics including signal processing, segmentation, object detection and localisation, image matching, motion detection and tracking, classification, recognition, 3D reconstruction and many others. Rather than attempting a comprehensive review of the field, the author shall instead concentrate this brief survey of the vision literature to a selection of topics, some of which  will be discussed in more detail later on in this thesis. For more substantive introductions to computer vision, the reader is recommended to read textbooks such as those by Parker  \cite{parkerbook} or Davies \cite{daviesbook}.

In this chapter the author will compare the work of conventional machine vision researchers to equivalent solutions discovered by Genetic Programming and machine learning techniques in general. Where possible, the relative quality, applicability and advantages of machine vision systems shall be discussed; towards the end of this chapter the application of Genetic Programming to vision problems shall be assessed in a more general sense, setting the scene for the author's work. 

There are various ways in which one can organise a survey of computer vision; in this chapter we shall take a ``bottom-up'' approach and start with the lowest level image operations, working upwards to higher-level algorithms.

\section{Image Acquisition}
\label{noise}
%http://techfrontiers.blogspot.com/2008/06/cause-of-sensor-noise.html
%http://www.andor.com/learn/digital_cameras/?docID=316
All vision systems require one or more images as input, which may be captured through a digital still camera, video camera, or scanner. Whatever the device, a characteristic of any electromagnetic signal captured by electronic sensors is its liability to a degree of disruption or noise. It is preferable that this be minimised before image processing can start in earnest.

Noise arises from three sources. Two of these, \emph{readout} and \emph{thermal} noise, can be minimised through better sensor circuitry, but the dominant source of noise in images collected by digital sensors -- photon or \emph{shot} noise -- can not. This is caused by the quantum nature of photons themselves and the non-regular rate at which they are emitted and subsequently detected. Although it is easy to think of photons as being so tiny that their number must be vast, the human observer can in fact detect light at a rate of as little as 10 photons/sec at certain wavelengths, and advanced sensors can detect single photons at a time. Although we would ideally like to measure the \emph{average} number of photons reflected from the scene onto a particular CCD/CMOS element, if the number of photons actually captured during a given interval is relatively small then the number may deviate significantly from the average, leading to a noisy image. Noise is usually considered to be signal independent and becomes most apparent when the signal itself is relatively weak, for instance when taking photographs at night.

%\footnote{To improve the SNR of an image by a factor of $n$, one needs the average of $n^2$ images, since $SNR=\frac{N}{\sqrt{N}}$ where $N$ is the number of photons captured.}

Perhaps the most effective way to remove noise from images, therefore, is to accumulate a single image during the course of a number of separate exposures, which generally causes the noise to average itself out while leaving the signal intact. However, one needs a reasonably large number of images to improve the signal to noise ratio, which may be computationally expensive. Furthermore the camera and scene need to remain static during the exposures to avoid smeary blurs appearing, which is not very often the case! Although some commercial vision systems use sophisticated hardware to achieve a desirable and consistent image quality, this cannot be expected for vision systems in general. Indeed, our own eyes are still able to recognise objects in poorly captured images; artificial vision systems should be capable of the same. Accordingly there is a number of software techniques designed for the purpose of active noise removal. Although these techniques cannot uncover information from the image that wasn't there to begin with, their purpose is to achieve a more consistent image quality which should make subsequent processing more robust.

% FMI: A low-pass filter is a filter that passes low-frequency signals but attenuates (reduces the amplitude of) signals with frequencies higher than the cutoff frequency. The actual amount of attenuation for each frequency varies from filter to filter

Low-pass filtering, implemented using a Gaussian convolution mask, is a simple noise reduction technique. The mask re-computes each pixel's value as a weighted average of its original intensity and those of its neighbours. This reduces differences in intensity due to noise. However, legitimate differences in the signal level, such as those found at edges in the image, are also diminished causing a loss of definition. A better, non-linear technique instead chooses the \emph{median} intensity of a pixel and its neighbours. As this technique redistributes existing intensities rather than creating new ones it is less susceptible to producing a blurring effect than the Gaussian filter and therefore maintains definition more effectively. 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, although it will fail if too many of the pixel's neighbours have also significantly deviated from their ``true'' values. The \emph{mode} is perhaps the most useful average to take, since it selects the value with highest probability. Although the mode is poorly defined when choosing among a sparse distribution of data points, Davies \cite{davies:truncatedmedian} proposed a method to approximate the mode given the position of the median. A consequence of using the mode is that the image becomes slightly sharper, which indeed can be a desirable feature. Some results by these different techniques are shown in Figure \ref{fig:noise}; there are relatively few examples of GP being used explicitly for noise reduction so the figure also includes a result evolved by the author's software.

\begin{figure}[!ht]
\begin{centering}
\includegraphics[width=0.85\textwidth]{images/noise-reduction}
\par\end{centering}
\caption[A Vision Comparison of Different Noise Reduction Techniques]{Different noise reduction techniques working on the original, noisy image. Gaussian filtering removes noise effectively but is too indiscriminate. Median filtering preserves more definition (although some is still lost). ``Paint Shop'' refers to the edge preserving smooth option in Corel Paint Shop Pro X2\textregistered. The author's implementation of a Mode noise filter causes a slight sharpening effect. Finally, the results from a noise filter evolved by the author's GP toolkit.}
\label{fig:noise}
\end{figure}

The drawback of all the above noise filtering techniques, whether linear or nonlinear, is that they apply the same procedure across the whole image, so there is always a chance that non-noisy pixels will  also be disturbed. A sensible addition, therefore, is to integrate some form of \emph{detection} which establishes whether a given pixel is noisy or not; if the pixel is noisy then it can be processed using an appropriate filtering technique, commonly the median filter; others are left untouched. This is often implemented using one or more thresholds to compare a pixel with its neighbours, such as the work by Chen \emph{et al.} \cite{chen99}. Petrovic and Crnojevic \cite{Petrovic05} used Genetic Programming to evolve a noise detector and stated that it yielded comparable or better peak-signal-to-noise ratios on test images when compared to a wide range of similar techniques.

%Analysis Of Robustness Of Robot Programs Generated By Genetic Programming (1999) \
%Roongroj Nopsuwanchai, Prabhas Chongstitvatana

Rather than evolving separate noise filters directly, other researchers have instead investigated the robustness of GP approaches on noisy data. The general consensus is that noise in training data can help the GP system to develop robust solutions, which otherwise may become over-fitted to unblemished data. Reynolds \cite{reynolds-noise} injected noise into training data to investigate the idea for a robot obstacle avoidance task. He stated that this appeared to encourage the evolution of robust solutions, although the robustness of the individuals was not quantified on test data or otherwise. In a slightly more recent comparative work by Nopsuwanchai \cite{Nopsuwanchai98improvingrobustness}, the robustness of a robot controller was measured on a test set and compared between controllers trained on data with varying levels of perturbation. In one of the less surprising discoveries of recent times, it was shown that the controllers evolved with the highest level of perturbation were most robust. The key point is that Genetic Programming has the potential to incorporate noise handling into its choice and usage of features. Since noise does not always follow expected profiles, it is worthwhile using a learning system that can implicitly take observed noise characteristics into account.

% Evolving Robust GP Solutions for Hedge Fund Stock Selection in Emerging Markets
% Yan, Clack

%Different domains may present completely different patterns of noise, which again motivates the use of a learning system that tune solutions to specific applications, rather than attempting generic perfection. An example, outside of computer vision, is the modelling and prediction of prices in financial markets, the volatility of which cannot easily be categorised into a particular probability distribution. Genetic Programming has been used on various occasions to develop artificial fund managers (for understandeable reasons!). Yan and Clack \cite{yan-clack} showed that GP could significantly outperform a common, non-genetic investment indicator (MACD\footnote{MACD -- Moving Average Convergence Divergence, developed in the 1960s, shows the difference between two moving averages for the stock price, one fast and one slow. It was a popular indicator until the stock market crash of 2000, at which point investors decided to try something new.}) on a volatile exchange.

Of course, noise is but one of many issues affecting the quality of captured images. Colour balance and exposure are examples of other image characteristics that current sensor hardware finds difficult to reproduce reliably. Exposure is limited by the dynamic range of current sensors, while colour balance is particularly troublesome owing to the subjective and relative nature of ``colour'' itself. 

Ebner \cite{ebner:2001:colour-constancy} used Genetic Programming to evolve an artificial retina capable of recognising the true colour of materials.  His retina consisted of a 2D array of elements, each of which had red, green and blue sub-elements and could access the components in immediately adjacent neighbours. Each element corresponded to one pixel on the image, a similar approach to that used by neural networks which are also used in colour constancy. The colour of each pixel was computed by iterating an update process on the image 100 times, using update equations evolved by GP. Training was conducted on a series of Mondrian-like pictures\footnote{Mondrian's famous, ``pure abstract'' paintings often consisted of black lines and coloured rectangles, one of the most famous of which hangs in the Tate Gallery, London. On a pedantic note, the collages of coloured rectangles without black borders used by computer vision researchers often bear more similarity to some by Theo Van Doesburg, a peer of Mondrian's.}. Ebner reported good results in using his program to restore differently illuminated images to their original colours. In Chapter \ref{ch:low-level} we shall consider a few basic software approaches to colour constancy and exposure control, and see whether they can render the author's vision software more robust. 

\section{Low-Level Vision}
For now, let us assume that the image has been acquired and is of adequate overall quality, and consider some of the fundamental ways by which machines may extract image content. The ``content'' of an image, however, is not easy to quantify. Any scene may contain hundreds of objects of all shapes, sizes, colours and textures. The difficulty is confounded by the sheer number of pixels within any image: thousands at the very least. A popular approach is to start  by identifying those pixels that seem to indicate certain generic points of interest. Many of the early approaches, perhaps typified by the convolution with masks of the 1970s and early 1980s, did little more than emphasise features for subsequent human processing.  They were later refined into techniques such as edge, corner and other interest point detectors which are more suited to further interrogation by machine. More recent detectors such as SIFT \cite{sift} and SURF \cite{surf}, used to discover those points within an image which are most invariant to transformations, are direct descendants. In this section we shall consider various approaches designed to assist machines in identifying patterns that may be indicative of higher level content.

\subsection{Edge Detection}
It is often the case that different objects are constructed from different materials, or that their positions relative to fixed light sources will cause them to be subjected to different levels of illumination. Therefore, breaks in pixel intensities provide a useful cue for the detection of object boundaries and an essential first step for a variety of higher-level algorithms, for instance edge-based 3D template matching or some corner detectors. Accordingly \emph{edge detection} is one of the most thoroughly researched areas in computer vision.

%Profiles - sharp edge, gradual edge, roof, trough, highlight
The purpose of edge detectors is to identify whether local changes in image intensity indicate the presence an edge -- or not. Since any point where two neighbouring pixels have different values is a potential edge, the edge detector's decision is not straightforward; the process is rather subjective. Furthermore, there are various different ``types'' of edge (sharp edge, gradual edge, roof, trough etc), each of which have different intensity gradient profiles. It is difficult for one algorithm to be able to detect them all. Nonetheless, a wide variety of different approaches have been proposed.

An intuitive method of discovering edges is to compute a number of convolution masks that correspond to edges at different orientations and then choose the maximum response among them (see Wang \cite{wang85}). However, this approach can only be rendered scale/rotation invariant by deploying a large number of masks. As a relatively ``brute force'' approach, it may be rather computationally expensive. Nevertheless, ``template matching'' is, in general, a flexible technique which has a variety of applications, such as  character recognition, face detection or crater detection.

A more general approach to edge detection is to look at the second order derivative of the image; zero crossings in the local intensity gradient are indicative of edges. The second order derivative of the image may be approximated using the Laplacian convolution operator\footnote{The Laplacian response is believed to play a role in mammalian vision systems.}:

%\[
%\nabla^2 f = \frac{\partial^2 I}{\partial x^2} + \frac{\partial^2 I}{\partial y^2}\
%\]
%
%Which can be discretised for two dimensions
%
%\[
%\frac{\partial^2 I}{\partial x^2} = f(x+1, y) + f(x-1, y) - 2f(x, y)
%\]
%\[
%\frac{\partial^2 I}{\partial y^2} = f(x, y+1) + f(x, y - 1) - 2f(x, y)
%\]

\[
\left[ \begin{array}{ccc} 0 & -1 & 0 \\ -1 & 4 & -1 \\ 0 & -1 & 0 \end{array} \right]
\]

% Gaussian needed to smooth the image to prevent too many false edges
An early edge detector, invented by Marr and Hildreth \cite{marr-hildreth}, used Laplacian of Gaussian convolution in order to search for edges, a technique also used for blob detection. The Gaussian convolution is intended to remove noise that would otherwise yield false edges. As is apparent from the mask, the Laplacian operator responds highly to fine detail, so it is often used as a sharpening operator. Consequently the Marr Hildreth detector may be more adequately described as one that finds regions of high intensity contrast. This includes both edges and other features, giving rise to false edge responses. 

A different approach aims to target edges more specifically. Differential gradient methods estimate the magnitude of edges perpendicular to the $x$ and $y$ axes using the first order derivative, which again may be approximated by convolution operators such as those of Prewitt ($m=1$) or Sobel ($m=2$):

\[
 s_x = \left[\begin{array}{ccc} -1 & -m & -1 \\ 0 & 0 & 0 \\ 1 & m & 1 \end{array} \right]
 s_y = \left[\begin{array}{ccc} 1 & 0 & -1 \\ m & 0 & -m \\ 1 & 0 & -1 \end{array} \right]
\]

These masks approximate more succinctly the nature of an edge and therefore do not respond to high-contrast non-edges as strongly as the Laplacian operator. Each mask may be used to estimate the extent of the edge in each direction; the edge's \emph{magnitude} may be calculated either using Pythagoras' theorem, or by the approximation

\[
m = |s_x| + |s_y|
\]

% Machine Vision Book (p153) ER Davies doesn't seem to be a fan of Canny.
The magnitude of each edge candidate is then thresholded to determine the presence or absence of an edge. The Sobel operators are able to work reasonably well using small masks (which motivates the author to use them as a feature when using Genetic Programming). Given two perpendicular measurements, a little trigonometry can yield a rough estimate of the edge's direction. However, in comparison with the Laplacian operator, the differential gradient yields thicker edge responses. 

The well-known algorithm by Canny \cite{Canny:1986} extends this approach with several stages of additional processing in order to ensure thin edge responses are obtained and to mitigate some of the problems associated with thresholding edge from non-edge. In Canny's algorithm, the image is first smoothed using a Gaussian convolution mask to remove noise that might otherwise cause false edge responses. The intensity gradient of the image is then measured in order to find candidate edges. A search for the local edge intensity maximum is used to thin each edge down to single-pixel thickness, so-called non-maximal suppression. The final identification of edges is performed by an algorithm called hysteresis, which makes use of two thresholds. Edges below the first threshold are flatly rejected; all edges above the second are accepted as \foreign{bona fide} edges. Those in between are only marked as edges if they connect two such genuine edges. This reduces the number of interrupted edges in the final image.

Other, more complex techniques include methods that identify edges by viewing the image at different scales. The algorithm by Bergolm \cite{bergholm} first blurs the image and locates intensity gradients in excess of a particular threshold. Progressively less blurred images are examined in order to localise the edge accurately. Rothwell \emph{et al.} \cite{rothwell} proposed a few modifications to Canny's framework, doing away with the process of hysteresis and replacing it with an adaptive threshold, stating that the contrast of an edge should not be a primary indicator of its semantic usefulness. Numerous other approaches to edge detection continue to be published, although it becomes progressively more difficult to differentiate between them!

% Canny's three values: sigma - determining the size of the gaussian mask, and min and max for hysteresis

Harris and Buxton \cite{Harris:1996:edgegp} used Genetic Programming to evolve functions which could identify the discontinuities in a one dimensional signal. Their work was inspired by the theoretical aspects of the work of Canny; they assessed the fitness of evolved individuals using Canny's suggestions that a good edge detector should have a good signal-to-noise-ratio, localise each edge accurately and respond only once per edge. Their evolved function performed better than Canny's on real world signals. They stated that GP permitted the discovery of near-optimal detectors for edges in signals which fell outside of the assumptions inherent in a theoretically ``optimal'' detector. The authors later extended their software to render it capable of working on real images \cite{harris97lowlevel} and once again showed that it could outperform theoretical operators in applied situations. They stated that it was better to tailor an edge detector for a particular ``class'' of images sharing similar noise characteristics than to use a generic edge detector. Given appropriate training data, techniques such as GP naturally permit the construction of tailored solutions easily and may provide an advantage in delivering robust solutions to work in particular applications. All the generic edge detectors are dependent to some degree on parameters (Canny's detector typically requires three) which have to be considered carefully. This raises once again an important motivation for the use of machine learning techniques in computer vision -- data in some problem domains do not necessarily fit with assumptions made by some algorithms; a solution learned for a specific application can sometimes produce better results. Incidentally, later in this thesis we will show how GP can be used to evolve a detector for finding edges specific to a particular problem.
% TODO: Read srinivasan:edge and get more info

Chao \cite{chao:edge} used a 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 learning of the networks, the outputs on edges would tend towards a value of one; everywhere else to zero. As the net was essentially learning the weights for a convolution mask, results were found to be comparable with a Sobel operator. Another approach, this time using an evolutionary learning technique, was demonstrated by Bhandarkar \cite{bhandarkar:edge} who used genetic algorithms. The individuals' chromosomes were laid out in 2D so that the GA could evolve ``edge images'' for locating edges in grey scale images: again the GA produced, in essence, an optimised convolution mask. 

However, Srinivasan \emph{et al.} \cite{srinivasan:edge} used neural networks to devise a two-stage edge detection approach that yielded a detector comparable with Canny's. Edge detection is, therefore, one instance where learned techniques may produce equivalent or better results than ``standard'' vision algorithms for certain domains of applicability. This is due to the inherent flexibility of machine learning techniques to tailor specific solutions to specific problems.

\subsection{Line Detection}

An edge detector should be able to determine whether a given pixel is an edge or not. If the detector is applied to the whole image, then the edge detector yields: another image. As we have seen, computers find it difficult to understand the context in images, so edge detection in itself is usually not enough to yield useful information. The long-established Hough transform is a useful technique for determining whether a given edge pixel is part of a larger linear edge, which itself may be more useful information. Depending on a threshold value, the Hough algorithm can be employed to detect lines of a particular minimum length. More usefully, the Hough transform can discover the coefficients that define the line, so the computer can gain access to more quantifiable information. If we choose to represent a line in terms of any $x,y$ point's distance $r$ from the origin, given an angle $\theta$:

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

\noindent then for a set of $x,y$ points all values of $r$ can be calculated by iterating through all possible values of $\theta$, or rather a discretised subset of $\theta$'s possible values. Plotting the values of $r$ against $\theta$ yields a sinusoidal curve. If all the curves are accumulated on the same graph then the curves for a number of $x,y$ points on one line will all cross at a single point. This point represents the common values of $r$ and $\theta$, which define the line. These points are identified by creating a two dimensional ``accumulation'' array. The Hough algorithm searches for peaks in the array to find all the lines in the image.

\begin{figure}
\begin{centering}
\includegraphics[width=0.9\textwidth]{images/hough-transform}
\caption[The Hough Transform]{The Hough Transform. From left to right we see the original image (usually acquired following a process of edge detection), the contents of the accumulation array, and the lines discovered by the algorithm.}
\label{fig:hough-transform}
\end{centering}
\end{figure}

% TODO: Ref for motorways and satellite tracking.
As the Hough transform is at heart a parameter discovery mechanism, other geometric primitives that can be parameterised, such as circles, ellipses and curves, can also be detected in images using a similar process. For these reasons, and because the algorithm is suitably rotation invariant, the Hough transform is used extensively in computer vision. It is a preferred technique for applications such as road detection from satellite images. When the points are taken following the tracking of particular objects, it can be used to detect (and thus predict) the direction of moving objects, for example the movement of cars on motorways or satellites passing through the night sky. The search can be made into a local one if we assume $r$ to be zero and measure coordinates relative to a point of interest. This reduces the search to one dimension and can be performed quite quickly, making it a useful feature to be used by Genetic Programming.

\subsection{Other Points of Interest}
Besides edges and lines, there are many other useful areas of interest in a scene, for which other detectors have been developed. Some interest points are particularly generic, and may be discovered mainly according to their invariance to certain transformations, making them particularly useful for image matching. In popular use is the SIFT algorithm created by David Lowe \cite{sift}. SIFT works by locating a number of points in the image (not necessarily edges) using a difference-of-Gaussians (DoG) blob-finding technique. A ``pyramid'' of scaled DoGs is used to find those blobs that are scale invariant. Each key point is then defined by a feature vector descriptor which helps allow it to be uniquely and robustly matched. A later, slightly more robust, algorithm, SURF \cite{surf}, is based loosely on SIFT, and implements sufficient performance enhancements in order to work in real time. SIFT and SURF features are detected reasonably consistently; they can be reliably identified between different frames, making them ideal features for image matching, panorama stitching, and 3D scene reconstruction. Robots using trinocular cameras can use common features in each image for distance estimation. SURF and SIFT are also suitable for object recognition if the descriptors can be matched to an item in a feature database.

%P. R. Beaudet. Rotational invariant image operators. In Proc. IAPR 1978, pages 579--583, 1978.
Trujillo \cite{trujillo2006} used Genetic Programming to evolve similar features of interest. The fitness function for the features was primarily defined by the repeatability of the feature in successive frames. GP was able to evolve an improvement over a rotationally invariant operator proposed by Beaudet\cite{beaudet}; this is regarded as one instance where Genetic Programming was able to develop a human-competitive result.

We have already mentioned in passing that the Laplacian-of-Gaussian operation is quite good at detecting blobs, or circular points in a scene. Other interest points include ridges and corners; various algorithms have been proposed for the detection of each. The intuitive Wang and Brady corner detector, for instance, tracks edges and detects the points at which the direction changes suddenly, indicating a corner. The SUSAN \cite{susan} family of algorithms is able to integrate both edge detection and corner detection into one approach which requires neither image differentiation nor noise reduction. The principle underlying SUSAN is to pass a circular window over the image, comparing the value of the central ``nucleus'' to other pixels within the window. The set of pixels with similar value to the nucleus is described as the USAN\footnote{or ``Univalue Segment Assimilating Nucleus''.}. Different USAN sizes can be used for the detection of different features. A USAN which completely fills the circular area indicates the region is largely self-similar, so no edges or corners should be present. A USAN size of approximately half the region size indicates that the area is hovering over an edge, and smaller USAN sizes are more indicative of corners.

\section{Segmentation}
\label{segmentation}
The concept of self-similarity used by the SUSAN detectors leads us towards a new topic, in which images are partitioned into regions based on their homogeneity. Given that many items are composed of a single material, the process of identifying self-similar regions or \emph{segments} within images can play a crucial first step in object detection and recognition. Segmentation generally works by grouping pixels according some common characteristic, quite often based on grey-level intensity. Since the boundaries of segments implicitly determine edges (although perhaps less accurately), segmentation has the potential to kill two birds with one stone, as it were. Like edge detection, segmentation has received a great deal of attention from vision researchers over the years; a few of the more popular schools of thought are studied here.

One of the most straightforward approaches is to threshold each individual pixel by its intensity, yielding a binary image. Since the processing here is trivial, segmentation can readily be performed in real time. Discarding either the ``dark'' or ``light'' areas will yield the regions of interest, and is suitable for applications such as Optical Character Recognition (OCR) or various industrial inspection tasks. Although there is generally a substantial contrast between printed text and paper (in the case of OCR), gradual changes in illumination across the entire image usually prevent global thresholds from being suitable. More robust are so-called variable thresholding techniques which analyse local intensity histograms and choose automatically the threshold that divides the classes most completely, such as the technique by Otsu \cite{otsu79}. Ohlander \cite{ohlander75} proposed a non-binary technique, in which thresholds are chosen at the peak of intensity and colour histograms iteratively until no significant peaks remain. 
We shall consider a couple of automatic thresholding techniques, including Otsu's, in our discussion of classification in Chapter \ref{ch:gp-classification}. 

Such thresholding techniques are to a large extent dependent on the modality of the histogram as a result of the relative occurrences of the ``object'' and ``background'' classes. If a scene is dominated by the background class, then any peak in the histogram may be too small for histogram analysis techniques to detect it. Although techniques such as gradient relaxation (see Bhanu and Parvin \cite{bhanu87}) attempt to take this into account, there are various other means too. 

One approach is region growing. A  set of  ``seed'' regions are progressively dilated until the whole image is filled. An example is the \emph{watershed algorithm} \cite{watershed}, for which there are many implementations. If one imagines the image as a height-map derived from pixels on grey-levels, ``water'' may be allowed to flood the terrain from the lowest points, or basins, until the entire image has been covered. The different regions are then defined by the boundaries between distinct water sources. The seed points in this case are selected automatically, but may also be chosen manually, or by some other \foreign{ad hoc} method.

%FMI: Recursive algorithm developed by Vincent and Soille
% Read http://www.cs.rug.nl/~roe/publications/parwshed.pdf
Figure \ref{fig:watershed} shows three stages of a recursive watershed algorithm progressively discovering boundaries on a flag image. As can be seen, the algorithm is rather prone to over-segmentation, finding too many regions, although segments can be merged together at a later stage. Another technique applies hints or ``markers'' to indicate which parts of the image are definitely contiguous and should not be over-segmented. Of course, such markers must be manually drawn or discovered automatically using other approaches.

\begin{figure}[!ht]
\begin{centering}
\includegraphics[width=0.9\textwidth]{images/watershed}
\par\end{centering}
\caption[The Watershed Transform]{A basic watershed algorithm working on the image on the left.}
\label{fig:watershed}
\end{figure}

There are several other techniques which are not mentioned here -- segmentation, like edge detection, is not well-defined so attracts numerous different approaches, each with different scope and applicability. The problem is apparent within the Berkeley Segmentation Benchmark \cite{berkeley-db}, a growing set of human-segmented images. Each image is segmented by several people -- and no two human responses are the same! Indeed, the \emph{evaluation} of segmentation algorithms is a field of study in its own right. 

%Read this: http://www.eng.iastate.edu/ee528/sonkamaterial/chapter_5.htm
\label{campbell-segmentation}
As evidenced by the above examples, the research within the mainstream computer vision community is often focused on unsupervised segmentation. However there are no automatic algorithms that are sufficiently general to work satisfactorily on all images. Once again this motivates the author towards supervised machine learning techniques. A nice semi-hybrid approach was proposed by Campbell \cite{campbell97} who used a segmentation technique that incorporated both supervised and unsupervised components. A Self-Organising Map (a type of unsupervised neural network) was used to produce the initial set of regions. The regions themselves were then classified into different categories using another neural network. This combines the advantages of unsupervised neural learning with the benefits of knowledge provided by domain-specific training data. 

Other machine learning techniques, especially optimisation techniques such as Genetic Algorithms, have been used quite extensively in image segmentation. Genetic Algorithms may also be used to optimise parameters for many of the algorithms described above. Brumby \emph{et al.} \cite{Brumby:2001:remote} introduced a different approach using Genetic Algorithms where each GA ``gene'' could invoke a different image operator primitive (included were logical, spatial, thresholding and spectral operators). The gene additionally specified certain parameters, and the input and output ``scratch panes'' which would be affected by the operation. Their approach essentially permitted the vision system to experiment with different image filters and operations as might a computer vision researcher using MatLab or other software. 

Attempts at segmentation by Genetic Programming proceed along similar lines, in which the program more closely resembles a filter which transforms each individual pixel into a particular class. In fact the process bears most in common with classification; each pixel is described by certain features with programs evolved to identify whether or not the pixel's feature vector is representative of an ``object''. The description of a pixel in terms of multiple features is a distinct advantage. As one can see from the folds in the flag in Figure \ref{fig:watershed}, a continuous region can have both dark and light areas -- so in this case the \emph{hue} of pixels would probably result in more accurate segmentation, although our perception of ``colour'' is itself rather subjective from a machine's point of view. The key is that intensity alone is not always enough information in order to make a judgement about a particular pixel. %Adelson's Grey Square Illusion, shown in Figure \ref{fig:gs-illusion} is a good example of this. 

Of course Genetic Programming is not alone in making use of pixel features beyond grey-value. Another family of algorithms cluster image pixels by their apparent similarity, a process which is less dependent upon the size of individual classes but instead the differences between different classes. Clustering may take various forms, including k-means-clustering, where clusters are formed by iteratively moving instances between cluster centroids. The major issue with k-means clustering techniques, however, is that the number of clusters must be defined \emph{a priori}.  

A different approach, hierarchical clustering, takes an initial set of clusters and progressively combines them together based on similarity. An approach by Chang and Li \cite{chang94}, named ``Fast Adaptive Segmentation'', bears much in common with this technique, in which the image is partitioned into a large number of small areas. These are progressively combined together to grow larger and larger regions. Adjacent areas are permitted to merge if they are sufficiently similar, and provided that there isn't a significant edge along their shared boundary. The accuracy of the eventual segments, however, is somewhat dependent on all previous decisions.

%TODO: Move to Chapter 7
%Segmentation, as such, does not imply that segments must be labelled, although a process of segment classification is important if one is to differentiate between object and background. The concept of classification with regard to segmentation is one that we shall consider in more detail shortly, indeed it is the basis behind the author's feature detection system which will be discussed in Chapter \ref{ch:low-level}.

%TODO: Watershed segmentation using hue

%\begin{figure}[ht]
%\begin{centering}
%\includegraphics[width=0.66\textwidth]{images/illusion.eps}
%\par\end{centering}
%\caption[The Grey Square Illusion]{The Grey Square Illusion. Due to changes in illumination within the image, some dark squares (A) and light squares (B) actually have the same intensity values. A basic thresholding approach to segmentation will fail on this image.}
%\label{fig:gs-illusion}
%\end{figure}

% TODO: Add to this paragraph. Look into the paper ``Segmentation of Medical Images using a Genetic Algorithm''

%Machine learning algorithms have a distinct advantage for finding appropriate measures of similarity, at which point the segmentation problem starts to resemble one of classification. If we turn our attention to \emph{supervised} classification, then a host of different machine learning algorithms can be employed. Indeed, genetic algorithms are commonly used in segmentation, and have been applied to a number of different tasks including multispectral image analysis and medical imaging. Sometimes the the GA is used to optimise parameters for a separate segmentation approach, such as shape based level set functions, or works on the pixel data directly.

\subsection{Applications and Image Features}
We shall now look more closely at the efforts of genetic programmers to segment or otherwise detect objects in images. Of particular interest is the kind of image features used as pixel descriptors.

Poli \cite{poli96genetic} used Genetic Programming to evolve a custom filter capable of segmenting magnetic-resonance (MR) images of the human brain. Although his terminal set was comparatively modest, consisting of different scale image intensity averages, GP was able to invent filters that were marginally more successful those that of a neural network. 

Roberts and Claridge \cite{roberts:2003:skin} proposed a system for segmenting skin lesions, some of which are indicative of certain types of skin cancer, a problem made difficult by the natural variability in skin tone and texture. Their evolved programs were given access to a large range of image features, consisting of thresholds, morphological operators, logical operators, region statistics etc. One of the nice features of Genetic Programming is that the function set can be suffused with a reasonably large number of operators: GP's selective nature will cause the appropriate ones to be chosen more readily. The evolved operator performed reasonably well, with a sensitivity of 97\% and specificity of 81\%.

Among the metrics that may be used to describe a pixel for the purposes of segmentation are descriptors of its surrounding texture. Texture is crucially important for the accurate segmentation of certain image types, including satellite, medical or multi-spectral images. Although any feature that combines the output of more than one pixel will encode some detail about the surrounding context, the computer vision literature suggests a number of specific approaches for describing texture. 

\label{glcm}
A popular tool in texture analysis is the grey level co-occurrence matrix (GLCM, also referred to as a spatial dependence matrix, see Haralick \cite{haralick73}), which encodes the distribution of co-occurring pixel intensity values at different offsets from a central point for different levels of adjacency. A variety of different statistical features can then be calculated from the matrix. Song and Ciesielski \cite{EvoVision:Song-Ciesielski:2004} evolved binary texture classifiers that could distinguish a given black-and-white texture from a set of 47 others. Song and Ciesielski tried two function sets, one using 195 Haralick texture features and another using only the raw pixel data. They stated that GP was able to outperform the C4.5 Decision Tree algorithm marginally when differentiating each texture from 47 others using the Haralick function set, although both classifiers frequently attained 100\% accuracy, on account of the training set's simplicity. More interesting was that evolved programs using the raw data set could still achieve $>90\%$ accuracy, indicating that GP can construct useful statistics itself as well as glue existing ones together.

%TODO: Have GP researchers used Law's texture metrics?

Laws \cite{Laws79} proposed a different algorithm by which textures could be described. He suggested using a series of 5-pixel, one-dimensional masks based on Gaussian, Gradient, Laplacian of Gaussian and Gabor features, intended to measure image level, edges, spots and ripples respectively. Different combinations of these were combined into $5\times5$ convolution masks that could be run on the image, with the expectation that among the different combinations would be one able to distinguish between different classes of texture. Although not particularly invariant, these can be useful descriptors of texture, and are ideal for use by Genetic Programs, although they don't appear to have been used by GP researchers before.

Quintana \emph{et al.} \cite{quintana:2002:KBCS} evolved programs to detect domain-specific areas of interest in images using Mathematical Morphology (MM) features\footnote{Mathematical Morphology \cite{serra:mm} is a long established technique used 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 outwards or contracted inwards through dilation or erosion respectively. Although Mathematical Morphology was initially conceived to work on binary images it was later extended to work on grey-scale images, permitting new applications, such as the watershed algorithm.}. One of their experiments concerned the extraction of different musical symbols from sheet music: the notes, hooks connecting quavers and clef lines. While the heads and lines could be isolated well, the GP method was unable to segment satisfactorily 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.

\section{Object Detection}
The reader may have noticed that the applications of GP described so far have drifted from image segmentation to the detection of features of an increasingly specific nature. In this chapter we have already seen some techniques concerned with the detection of particularly generic features such as circles, corners or blobs, but here we shall cover the detection of more particular patterns. We shall start with a discussion of object detection in mainstream computer vision, taking face detection as an example. 

Despite the innate ability of humans to detect faces robustly and effortlessly, face detection is difficult to implement in silicon. Nonetheless, in recent years face recognition algorithms have become relatively ubiquitous, working in real time in small devices such as digital cameras. Since faces cannot be modelled with the mathematical precision of, say, a circular blob, machine learning techniques feature prominently in mainstream face detection algorithms and object detection in general.

Various strategies have been employed in order to generate face detection algorithms, including geometric approaches where the face is fitted to a 3D model, or more knowledge-based approach where the common features of human faces (eyes, mouth, nose) are identified and faces recognised according to the known relationships between them. This latter approach, while apparently logical, is rather dependent upon the assumption that the aforementioned features are indeed the most robust means of identifying human faces. Among the most influential papers on the area is the work by Pentland and Turk \cite{pentland-turk} who developed one of the first successful face detection systems. They used principal component analysis to construct useful face templates, so-called eigenfaces (some of which bear little resemblance to our concept of a face!). Weighted sums of various eigenfaces can be used to represent a variety of actual faces. Since faces are matched based on intensity, face recognition algorithms using this technique can be quite sensitive to changes in the position of the illuminant and are not necessarily invariant to changes in rotation.

% TODO: Read rowley's paper: apparently it is rotation invariant.
% http://www.ri.cmu.edu/publication_view.html?pub_id=2857
While a common strategy for making detection scale or rotation invariant is to use different sized templates, or to rotate the image itself through various angles, Rowley \emph{et al.} \cite{Rowley98} used a neural network to develop a face detection system that implemented rotation invariance in a more  efficient manner. They first trained a detector to identify only the angle of faces within a given window. As each angle was identified, the window was then ``de-rotated''; a second, upright-only face detector then decided whether a face was present or not. The detector was trained on an initially small training set, with additional ``false'' images added during the learning process to reduce the likelihood of the net yielding excessive false positive results. One of the big advantages of neural networks is that it can be incrementally trained using this kind of  ``bootstrap'' approach. An issue in face detection, indeed all detection tasks, is that there are many more examples of non-faces than there are examples of faces: the training data is always insufficient to some degree. The problem with face-detection algorithms, therefore, is not the sensitivity but the specificity -- the ability of the algorithm to work without producing too many false positives. Rowley suggested using multiple nets and voting schemes to develop a consensus that may suppress some of these errors, however they noticed this was sometimes at the expense of sensitivity. Such schemes may also fail because there is no guarantee that separately learned algorithms will not make the same mistakes. 

One technique used to develop a solution to these competing criteria is to use a boosting framework, such as the AdaBoost algorithm by Freund and Schapire \cite{EvoVision:Freund-Shapire:1996}, which develops a more accurate classifier from several sub classifiers, each of which is trained on the same training data, whose weights are adjusted between learning runs. A weight is assigned to each item of training data, which is iteratively adjusted after the learning of each sub classifier in order to encourage high levels of accuracy and to ensure that each classifier is different. Viola and Jones \cite{EvoVision:Viola-Jones:2004} made use of AdaBoost in the development of their own face detection technique to combine various such ``weak learners''. The weak learners themselves were Haar-like features, defined by parameters discovered by a Genetic Algorithm. Haar-like features can benefit from the use of an ``integral image'' which permits the calculation of mean and standard deviations of arbitrary image areas in constant time. Viola and Jones showed that their approach was slightly more robust than that of Rowley. 

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

% TODO: What kind of features?
Winkeler and Manjunath \cite{winkeler:active} 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 Gabor features and other descriptors developed by mainstream computer vision. The authors suggested that island selection would avoid premature convergence, a problem found in many machine learning techniques. Code bloat is another common problem in Genetic Programming; it is worth mentioning it here because image processing in particular demands that algorithms are reasonably parsimonious, and it would be unfair to paint Genetic Programming in an exclusively positive light! One of Winkeler and Manjunath's evolved solutions was composed of over 3000 nodes: a severe performance bottleneck. In a second experiment, a program was evolved to distinguish roughly areas that contained faces from areas which did not. 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). The reader should be reassured, however, that it is probably possible to evolve a reasonable classifier of a much smaller size. Various means by which code bloat in GP programs can be curtailed shall be discussed throughout the course of this thesis.

% How to adjust the fitness function then? Deliver no extra reward above 96%, causing the fitness pressure to favour more specific solutions instead.
We shall now move away from face detection in order to cover some of the other ways in which Genetic Programming has been applied to object detection in general. Tackett \cite{EvoVision:Tackett:1993}, who has the distinction of publishing the first significant GP paper concerned with computer vision in 1993, evolved an automatic target recognition system for recognising targets in military situations\footnote{Despite the processing burden imposed by images in general and GP learning in particular, Tackett trained his system on 2000 samples, an impressive feat at the time!}. He used straightforward spatial features consisting of areas' intensity means and standard deviations to evolve tank detectors. Tackett compared his detectors with an MLP neural network and found that GP delivered the more accurate solution. The creative freedom afforded by the fitness function paradigm in GP makes it ideal for solving difficult problems. Given a clear set of objectives, Tackett knew his program needed a detection rate of only 96\% and adjusted his fitness function to deliver no extra reward to individuals whose accuracy exceeded that value, causing the system to favour more specific individuals instead. The MLP neural network, whose learning algorithm aspired to solve 100\% of the ``true'' training data samples, was found to accommodate difficult samples at the expense of lower specificity. As Tackett observed, this caused an unacceptable level of false alarms for the neural network.

Roberts and Howard \cite{EvoVision:Roberts-Howard:1999, howard:1999:esdsSARi}, used Genetic Programming to evolve detectors for objects in complex environments -- vehicles and ships in satellite images. The authors used single-pixel-thickness circular statistics as features which are reasonably invariant against rotation and noise.  Four circles of different diameters were used, with the average intensity, standard deviation, edge count and an edge distribution measure calculated for each. Again, the authors encountered problems with false positives, and solved the problem in a similar manner to Winkeler and Manjunath: a ``rough'' preliminary detector was followed by finer, second stage detectors.  The authors used a bias ratio in their fitness function  (see page \pageref{fitness-bias-ratio}) to subjectively determine the sensitivity/specificity ratio that would determine whether to evolve a rough or fine detector. Roberts and Howard did not expect each secondary detector to provide a perfect detection rate, but rather suggested that different second stage detectors might be good at detecting different kinds of vehicle, although this was not presented in evidence. The evolved detector was able to detect 89\% of the vehicles with a 14\% false positive rate. However there was no testing on unseen training data, and relatively few images were trained. 

Other GP researchers have also used a variety of other basic features for vision tasks. Roberts and Claridge \cite{roberts:2003:skin} used GP to develop detectors using a generous selection of different features including statistics about rectangular, circular and ring shaped windows, convolved results, differences between 3$\times$3 areas and various other features. Combinations of these basic features can produce higher level operators capable of solving more subtle tasks, with the essential goal being to find features specific to particular problem domains, including shape recognition and pasta detection (a perennial favourite). In later work \cite{roberts04cooperative}, the authors went on to describe how Genetic Programming may construct and use imaging features simultaneously using a process of co-evolution, where the operators and GP programs using them are evolved simultaneously and cooperatively. The results published appear to show that co-evolution in this manner can solve problems to a high degree of accuracy, although unfortunately no comparison with ``standard'' GP was provided. 

Although detection has its own specific issues (we've already seen the sensitivity specificity tradeoff), it may be seen as the binary case of classification or recognition in general. In computer vision classification is dominated by machine learning techniques, including support vector machines (SVMs), decision tree builders, and neural networks. We shall look at classification in depth in chapters \ref{ch:gp-classification} and \ref{ch:gpcomparison}. For now, we shall briefly look at multi-class object detection/classification by GP.

Zhang and Ciesielski \cite{EvoVision:Zhang-Ciesielski:1999} investigated 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. Detection proceeded using a windowing approach, using various circular and rectangular statistics. Post-processing was deployed to ensure that only the centre of each object was detected once and only once. Good detection rates on the (difficult) retinal images were achieved but at the expense of relatively high positive alarm rates, despite the post-processing.

Zhang, Andreae and Pritchard \cite{zhang-andreae-pritchard} 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 of the whole window (mean, variance and moments) in comparison to using just the mean in sub-windows. In another of the less surprising discoveries of recent times, they found that whole window statistics were unable to deliver sufficient information about shape, and the programs where sub-window statistics were made available were able to produce better results more rapidly. 

Any discussion of multiple-class object recognition would be remiss if it were to omit a discussion of optical character recognition (OCR) which, like barcode readers, has been around for a surprisingly long time\footnote{OCR has been used in British post sorting offices since 1965.}. Accurate recognition of characters is largely regarded as a solved problem, at least for printed Latin-based alphabets. Nonetheless, it is by no means a straightforward task; the offline recognition of handwritten alphanumeric characters or indeed character-based written languages remains challenging.

%READ: Historical Review of OCR Research and Development

Like face detection, character recognition is dominated by machine learning techniques. Commercial OCR systems commonly use neural networks for recognition, since they are able incorporate new knowledge during application. The key to most OCR systems is the choice of features, which have a substantial impact on robustness. Assuming that a single character can be detected and cut out from the image, it can be scaled to a fixed size. Each pixel within the scaled image can then be used as input for the neural network. This was the approach taken by Koza himself in GP, and later by Spivak \cite{spivak:2002:OCR}, who used binary features (``is the pixel at $i,j$ black?'') and a standard set of functions to develop classifiers for the hexadecimal characters (0--9,a--f). Classifiers were trained on one font and then tested on others. The problem with such an approach is that the binary features are not particularly robust, indeed the decision of some of the programs was based on the values of as few as four pixels -- classification may proceed based on ``coindidence'' detection rather than semantic understanding.

Andre \cite{Andre94} made use of a more robust feature set in which the character is processed to discover its boundaries. The shape is divided into four segments, with bounding boxes measured for each one, as well as for the character as a whole. Andre showed that his system could distinguish the letter `C' from all others on about 96\% of occasions. He also proposed a clunky method by which a hand-written algorithm could be converted into a GP tree by hand, and then evolved further to take into account new training samples. The author acknowledges that neural networks can adapt to new situations in an altogether more elegant manner.

A slightly more serious attempt at OCR was undertaken by Teredesai \emph{et al.} \cite{teredesai:2001} in order to recognise the characters 0--9 from the NIST handwritten digit set. Rather than deploying a so-called ``One Model Fits All'' approach, they used a hierarchical feature set starting from coarse overall features but progressing to increasingly finer distinctions within sub-regions of the character image. Nine features were extracted at each stage, four based on gradient and five based on moments. The authors found that the best individuals tended to use features at a range of different depths in order to make accurate distinctions. A binary classifier was evolved for each digit, results between 95.9\% and 97.6\% were reported. The authors did not report the overall accuracy of the multi-class classifier, so its overall capabilities could not be assessed.

\label{johnson}
There are many applications of binary shape analysis beyond character recognition. Johnson \emph{et al.}\cite{EvoVision:Johnson-Maes-Darrell:1994} used GP to locate features \emph{within} shapes. For part of an interactive system, they evolved a program which could locate the positions of the right and left hands of a silhouette of a person (taken against a blue screen background). Instead of using pixel statistics, they used a basic ``point'' data type which could hold $x,y$ coordinates. Various functions were provided to 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 as their best program could find 93\% of left hands, although their sinister programs didn't perform so well on validation data.

GP is otherwise rarely used for shape classification in images, despite a significant body of work performed in mainstream computer vision. Over the years countless descriptors for shape have been proposed. The most straightforward descriptor of a segment or shape is its size. Morphological erosion followed by dilation may be used to discard small shapes that do not convey much meaningful context. This is a somewhat computationally inefficient means of filtering shapes by size, but can also be used to smooth the outlines of the larger shapes, rendering them more suitable for further processing. 

It is useful to identify the perimeter of a shape by tracking its edges. From the perimeter, corners and other features may be identified\footnote{The author spent an enjoyable month crafting algorithms for these ideas in his first year of study, although it was mainly a process of wheel reinvention!}. Other simple features can detect the roundness or rectangularity of the shape, and its aspect ratio and  orientation. Other algorithms label the shape according to each pixel's distance from the edge providing descriptors that reveal whether a shape is rounded or mostly thin. Conversely, shapes may be ``skeletonised'', or progressively thinned to the point where the shape resembles a tree. The number of nodes, connections and leaves in the tree can then be used as descriptors of its structure.

One family of shape descriptors use statistical moments \cite{hu62} which are traditionally used to describe the shape of probability distributions. Common statistics include the mean, variance, skew and kurtosis. Another popular approach is to compute a complex hull, which wraps around the shape as would an elastic band. From the hull can be calculated so-called concavity trees (Sklansky \cite{concavity-trees}) which store information about the hierarchy of convex areas of the shape, and unlike the examples seen so far can be used to reconstruct the shape completely. Metadata regarding the tree structure itself may be used as descriptors for object recognition, or different concavity trees may be matched more directly in order to compare two shapes (see Badawyl and Kamel, \cite{matching-concavity-trees}. The advantage of many of these features is that they are rotation and scale invariant.

%Amit and Geman \cite{amit-geman} who developed a recognition system for binarised digit images. The authors used primitive local features which would return true if the image satisfied a number of questions within a $4\times4$ neighbourhoods, such as ``is the pixel at $i,j$ black''. The features were run on the image, and characteristics developed based on the relationships between parts of the image that returned true for given primitives. Genetic Programming was used to discover important relationships.
Montes and Wyatt \cite{montes03cartesian} used graph-based Genetic Programming to  locate of the centre of mass of an object. While not a particularly difficult problem to solve in practice (given that the object had already been segmented), 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). 

There are myriad other ways of extracting image features: the discussion so far only scratches the surface.  More features will be described in Chapter \ref{ch:low-level} when the author comes to apply them for the purposes of generic feature detection. 

% TODO: Move to Chapter 7
%This research 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 of the nice features of Genetic Programming is that one can add as many operators to the GP system as one likes in order to solve a variety of problems. Later in this thesis we will show how the author's generic GP vision system can segment clef lines and other important features from the image without using MM.

% TODO: Law Texture Energy
 
% TODO: Fourier Transform
 
% TODO: Markov Random Fields

% TODO: Fractal Modelling

% TODO: Binary Partition Measure - doesn't seem very good.

\section{Vision Systems}
As we approach the end of this chapter we shall turn our attention from isolated vision components to vision \emph{systems}, which perform as many levels of processing as necessary as to produce high-level output from images.  As we have seen so far, Genetic Programming has been applied to a number of fields of endeavour within the computer vision domain; solutions have been evolved with varying degrees of accuracy and robustness. Here is a brief summary of the evolved vision algorithms covered so far:

%TODO: Where Have I Discussed MultiSpectral? Brumby?
\vspace{0.5cm}
\begin{tabular}{p{5cm}p{8cm}} 
Task & Examples \\ \toprule
\multirow{2}{*}{Preprocessing} 		
							& Noise Suppression \cite{Petrovic05} \\
							& Edge Detection \cite{harris97lowlevel} \\ 
							\midrule
\multirow{3}{*}{Feature Detection}			
							& Texture \cite{EvoVision:Song-Ciesielski:2004} \\							
							& Musical Notation \cite{quintana:2002:KBCS} \\
							& Interest Points \cite{trujillo2006} \\ 
							\midrule
\multirow{2}{*}{Segmentation} 		
							& Multi-spectral Images \\
							& Medical Imaging \cite{roberts:2003:skin, poli96genetic} \\ 
							\midrule
\multirow{4}{*}{Object Detection} 	
							& Faces \cite{winkeler:active} \\
							& Vehicles \cite{EvoVision:Tackett:1993, EvoVision:Roberts-Howard:1999} \\
							& Hands  \cite{EvoVision:Johnson-Maes-Darrell:1994} \\
							& Robot Vision \cite{reynolds-noise, Nopsuwanchai98improvingrobustness} \\ 		
								   \midrule			
\multirow{2}{*}{Object Classification} 								
							& OCR \cite{spivak:2002:OCR, Andre94, teredesai:2001} \\ 
						       	& Shapes/Coins \cite{zhang-andreae-pritchard} \\
							\midrule						
\end{tabular}
\vspace{0.5cm}

% TODO: Robot Vision is more like a complete vision system....

A common feature in all of these papers is the rather specific nature of the problems being solved. There is, of course, nothing inherently wrong with this, although to concentrate on a single domain diminishes one of the key advantages machine learning techniques offer over the development of software by hand --- the potential to learn solutions to more than one kind of task and thus save time. If one spends as much time tuning and preparing the machine learning technique as it would take to solve the problem using traditional computer vision methods, then the research has little usefulness beyond satisfying a particular curiosity, especially if the problem in question is one that has already been solved to a satisfactory degree. However, if one can ``generify'' the learning system in such a way that two or more problems can be solved, then one has a system with some added value.

% Todo - Examples of Gamera Vision Systems

The GAMERA framework \cite{gamera} is a programming interface designed for the production of document analysis systems in a general sense, and has been used for a variety of applications involving the processing of historical documents and recognition of other printed characters. The framework does not imply the use of a particular learning algorithm, but facilitates the production of domain-specific vision systems such that they can be generated more quickly. 

% Todo - mention Brumby again here

Later in this thesis, the author will present a software interface designed to provide a unified interface for the production of vision system training data.

%Segmentation is tedious and time consuming and may differ by up to 20%
%S.Warfield, J. Dengler, J. Zaers, C. Guttmann,W. Gil, J. Ettinger, J. Hiller,
%and R. Kikinis, “Automatic identification of grey matter structures from
%MRI to improve the segmentation of white matter lesions,” J. Image Guid.
%Surg., vol. 1, no. 6, pp. 326–338, 1995.

The definition of ``vision system'' is rather loose, not least because the architecture of such systems is dependent on the application. Indeed, many authors describe their work as a vision system when it is perhaps more appropriate to call it an image processing component. For the purposes of this work the author defines a vision system as follows:

\begin{quotation}
\noindent ``A system which takes unprocessed images as input, then processes them in such a way as to return high-level output without requiring further user interaction.''
\end{quotation}

% Mention Starner

There are many examples of working vision systems, both within and without the confines of purely academic research. Machine vision systems are often used for the purposes of industrial inspection, for instance the inspection of products or foodstuffs on conveyor belts, for detecting or counting items, or defect detection, such as cracks in railway lines or aviation components. Security applications include the detection of aircraft, of people or unusual behaviour, or indeed face recognition. Consumer level applications include gesture recognition for human computer interaction or augmented reality applications. Applied vision is commonly used in academic research as part of robotics projects. The iCub \cite{robotcub}, currently the most advanced humanoid robot in Europe, makes use of a number of different vision algorithms, including saliency detection, object recognition and online learning.

In practice most vision systems will deploy several of the stages of processing covered in this chapter. Given an image capture device, the vision system will go about acquiring an image, pre-processing it, performing low-level vision tasks to emphasise the objects or areas of interest, followed by higher-level processing, often classification. Indeed, there may be several further stages not covered in this brief overview. 

In this chapter we have seen most of the stages necessary to go about creating a reasonably complete OCR application. Other systems, such as automatic number plate recognition, which is essentially OCR in a less constrained environment, require additional stages of detection and greater invariance to transformation. The key point in any such system is that the human should not have to perform any part of the processing manually, such as telling the system the location of the number plates or manually segmenting individual characters. 

All of the GP research described so far has considered evolved vision in terms of a single stage of processing within a larger context, implying further stages that must take place before or after the evolved component's execution. For instance, research on OCR assumes in each case that the characters have already been cut-out from the image, binarised and scaled before the GP operator performs its task. Likewise the skin lesion research performs segmentation on individual images but does not suggest what to do next. In each case these papers relate to the proof of particular concepts rather than working on producing something complete in itself. The author has not encountered any papers which use more than one evolved stage in order to develop a ``vision system''. To put multiple stages of evolved vision together would validate such components in a more complete sense -- it is, of course, worthwhile to present quantitative results regarding the quality of a given component, but its utility is best tested when its output is used as input to another stage of processing.

We have seen that some Genetic Programming researchers do occasionally employ a multi-stage approach, but this is usually restricted to two or more stages of processing by programs that each perform the same task, though they may have been evolved using different fitness functions. A common example is the evolution first of a ``rough'' detector to discard as much of the background as quickly as possible, followed by a secondary detector to make finer distinctions. 

%A final consideration is the means by which training data are collected by the authors for each problem. Often this is done in an arbitrary, time-consuming way, which again renders the advantages of machine learning somewhat moot if the training data take too much human effort to be collected! 

%Reaching the end of our survey of the literature,  the author determines the following four characteristics that should be addressed by a generic vision system:

%\paragraph{Genericity}
%The architecture should be capable of solving a variety of problems, preferably from different domains, with a variety of different requirements.

%\paragraph{Completeness}
%The software should be able to produce complete vision systems that are capable of producing useful output given only an input image. Although the results of the software can be used for further processing, the aim should be to solve some problems in their entirety using GP. For the purposes of this thesis, a ``fully working'' vision system is defined as one into which one inserts unprocessed images, and out from which one receives 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''.

%\paragraph{Ease of Producing Training Data}
%Regardless of the problem, there should be a unified approach to collect training data with ease, so the only stage that requires significant human effort be as painless as possible!

%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.

\section{Conclusions}
%One of the major goals of this thesis is to demonstrate how a generic system using Genetic Programming can be competitive with the current or recent state of the art. The work of Viola and Jones remains a state-of-the-art approach for 2D face detection. Fortunately their full results and the training data used are available online, so we shall demonstrate that GP can be a competitive learning technique using this benchmark, and go on to show its use on other problems.

This chapter has described a number of different tasks in the field of computer vision. There exist a wide range of approaches designed to tackle each, although it is not always straightforward to identify the most appropriate algorithm for a particular task. Usually the choice of appropriate techniques and operators is undertaken by computer vision experts. We've also seen various examples where machine learning techniques have been used to ``glue'' certain imaging operators together in order to generate task specific features that can't readily be modeled mathematically. Some interesting solutions have been evolved by GP researchers. A common thread running through many of the tasks is the need to take decisions: whether a pixel is noisy or not, whether it sits on an edge or corner, is within a particular region, or is part of a larger feature. The first step in the author's framework, therefore, is to investigate means by which Genetic Programming can be applied to making decisions in a general sense, which is the topic of the next chapter.

%In what follows, the author shall attempt to make improvements to the genetic system such that it can learn more efficiently, then consider in more detail ways in which image content can be represented, before presenting an architecture that can develop more complete vision systems.

%If a single learning technique can be used for each step of the vision system, then the construction of the vision system can be achieved through simply providing the right training data and putting the evolved algorithms together.

%We shall show in later Chapters how a number of the problems mentioned here, such as skin lesion detection, texture classification and object detection can all be solved by GP, to a higher standard than the published results. The general aim of this work is to develop a Genetic Programming system which is generic enough to tackle a reasonable number of problems, and to show that the GP developed solutions are at least competitive with their equivalents from the Computer Vision community. 

%While the construction of such a system is the topic of later parts of this thesis, the next Chapter will first provide the interested reader with a detailed and thorough introduction into Genetic Programming itself.

%\section{Vision Systems}
%... Is there any work on vision systems using GP?
%	- ALADDIN Project
%... what about other learning techniques
%... what about in general in the machine vision community
%	- GAMERA
