\chapter{Generic Feature Detection using GP}
\label{ch:low-level}

%Chapter \ref{ch:gp-classification} discussed at length how Genetic Programming might best be put to the task of classification, that is finding patterns in amongst data. 

Having established a classification strategy by Genetic Programming (GP) which is competitive with other techniques and considered how it might be converted into a ``black-box'' learning procedure, we can now turn our attention to using it for the automated development of vision systems. This chapter will describe some of the imaging techniques used and will discuss the construction of training datasets for image problems.

Here we begin to focus on some key problems in computer vision, and examine how GP classifiers may be employed to produce vision applications. That is, alas, too high level just now -- we must first explore exactly how one might create a suitable datasets for a given vision task. Among the datasets used for validation in Chapter \ref{ch:gpcomparison} was the Iris dataset \cite{fisher36}, in which the task is to distinguish three species of iris given four measurements of the length and width of the flower's petal and sepals\footnote{A sepal is part of a flower, usually green, lying under the more colourful petals.}, and the Wisconsin Diagnostic Breast Cancer set \cite{wdbc}, which consists of a number of measurements relating to cell nuclei which may be predictors of the presence of cancer.  The nature of the Iris and WDBC measurements seem rather obvious, given their specific domains, but exactly which measurements should we take from images in order to develop a generic vision solver? This chapter starts by discussing the kind of image measurements that may be useful. Later it shall be demonstrated how they can be used by GP to approach a selection of low-level vision tasks.

Exactly what makes a \emph{useful} image feature is a significant point of discussion in itself. Some algorithms, such as SIFT \cite{sift} and SURF \cite{surf}, were developed to find generic points of interest within an image, which seems quite promising. A range of other detector families are concerned with the detection of many kinds of features, such as corners, edges, blobs, lines and geometric shapes. Although the kind of features detected by SIFT are quite robust, making them suitable for image matching and 3D reconstruction work, one has to consider the extent to which different \emph{objects} can be described using such features. It may be these points of interest are in fact \emph{too} generic to work well in our experiments; indeed a substantial database is needed when SURF features are used for classification\footnote{According to David Lowe, the inventor of SIFT, a ``typical'' $500\times500$ image will give rise to approximately 2000 stable SIFT features.}. 

While the goal of this thesis is to discover a generic \emph{methodology} for solving problems, this does not necessarily mean that it should be reliant on generic features. Instead the intention is that our GP-powered learning algorithm should find highly \emph{specific} solutions to particular problems by tailoring or tuning features. Although such solutions may have limited scope for re-use, the automatic means by which they are developed makes this concern somewhat irrelevant. The idea of this work is to develop a system capable of producing ``disposable'' vision systems!

\section{The Approach}
As we'll see in the next chapter, the author's vision framework may develop solutions with up to four separate, evolved stages of processing. Each stage may be defined broadly as either feature detection or object classification. The first, feature detection, is the topic of this chapter. The author's approach is introduced following a brief discussion of two different image processing techniques.

%We start by considering the kind of program we would like our GP system to produce. Following any pre-processing operations, the starting point for many vision algorithms is some process in which areas or objects of interest within the image are identified.

\subsection{Segmentation}
Images are usually represented as arrays of pixel data. Such arrays are typically large, yet each individual pixel bears little information about the overall content of the scene. To understand the image it is helpful to look at groups of pixels rather than in isolation. Segmentation  (discussed on page \pageref{segmentation}) is a method for grouping the pixels into larger ``segments'', each of which may represent information about the image content more succinctly.  Although there are various means for going about segmentation, the author's approach is to have GP develop some measure of similarity which categorises a given pixel into a particular class. A decision is made for every pixel in the image. Segments are then constructed from homogenous regions of similarly classified pixels.

The nature of the similarity is problem-specific, as is the number of different classes, but the concept of ``apparent material'' is a useful rule-of-thumb. Given that objects are often composed of components made from a single material, identifying those pixels which have similar characteristics to known pixels of a given class will go some way toward identifying the position and contours of  objects and sub-objects within a scene. The computer vision developer may then choose to discard, investigate or compare different regions.

%Following the evolution of a suitable classifier, each pixel is labelled by the classifier individually, then those regions of adjacent, similarly-labelled pixels are identified.

 %This process, therefore, is a useful method for combining many pixels (which individually carry very little contextual information) into fewer groups which may represent image content more concisely.

%Although the classifier is not trained to actively seek contours or edges between different segments, the end result may often be used to do exactly that. The means by which the user can produce training data to evolve the classifier will be demonstrated in later chapters.

Segmentation has a large range of applications. It may be used to identify bands of mineralogical or geological features based on multi-spectral image data, to identify human skin, for background subtraction, are part of optical character recognition, or in medical image processing, to name a few examples.

Although segmentation can be quite flexible, it does have certain drawbacks. For instance it works best when objects have clearly defined boundaries, so segmenting more amorphous objects with soft edges may not yield robust results. It will typically distinguish objects based on material, so each object must have reasonably consistent appearance. Finally, it isn't always invariant to changes in scale.

\subsection{Window Detection}

One common method which addresses some of these issues is window detection, which is usually employed to detect particular patterns or shapes within a given rectangular area or window, which ``slides'' over the image.  At each position, a number of features are calculated for different areas and shapes within the window, and a decision is made whether an object exists at the location or not.

Rather than basing all features on or around a central pixel, the window detector may take its decision based on relationships between different groups of pixels within the window. If the size and location of features within the window are defined by percentage measurements of the window's own dimensions, then the window can be increased or decreased in size in order to achieve a degree of scale invariance. 

Window detection has two particular issues. The first is that for an $x\times x$ window, there will be an $x/2$ thickness border around the image that cannot be identified. Second is that the appropriate window features for a given task often have to be discovered themselves.

\subsection{Feature Detection Approach}
The author's approach is to combine the two techniques into a single generic feature detection system. Since the segmentation process outlined above (by which each pixel is classified in turn) is essentially an image filter, it is broadly similar to the window detection method. If all the features are made to exist within and relative to a variable scale window, then the approach should be able to detect objects in a scene of variable size. 

Although the detector is capable of higher-level detection when demanded, the technique will typically be used to label the whole image, for the purpose of region extraction, yielding an output similar to that of a segmenter. 

The author's approach thus works as a general feature detector, intended to identify certain regions by surrounding context, or texture, or colour (or a combination of each). To render it capable of doing so, it is necessary to choose image functions that can robustly quantify these characteristics. In the next section we will discuss the kind of features that may be useful, before going on to describe how they can be used to generate a suitable dataset for training the evolved detector.

\section{Evaluating Image Features}

Having discussed some of the ways in which Genetic Programming may be used to classify an object, given an $n$ dimensional feature vector, we now turn to the construction of the vector itself, specifically: what image metrics might be useful, and how can we ensure they are as robust as possible?

Since there is a potentially endless supply of metrics that can be harvested from an image, it is worthwhile considering criteria by which each may be judged. The author has decided upon four different considerations that should be taken into account.

\paragraph{1. Robustness}
Robustness may be defined as a feature's invariance to image transformations and other external factors prone to change, such as illumination or noise. The general idea is that the feature should return a consistent value if referring to the same object. Common geometric transformations include rotations and scaling. Certain problems, such as the recognition of vehicles from satellite images, will require rotation invariance around one axis, and many problems will encounter objects at different scales (face detection, for instance).  Processes such as noise reduction (covered on page \pageref{noise}) may help make the output of certain features more consistent.

\paragraph{2. Localisation}
A second important consideration is the ability of the feature to localise particular objects accurately. It is no use being able to determine the presence of an object in a scene without being able to accurately pinpoint its location! In general single-pixel features will be able to do this, although they consider less of the overall context. Features that make use of several pixels, such as convolution masks or other summed areas, may be more useful than individual pixel features, but may localise less well, unless they are highly specific. It is important to have a balance of features using various different area sizes. 

%TODO: What scale invariant features are there?

\paragraph{3. Efficiency}
\label{integral-image}
As the feature detector may be run on every pixel of the image, and by an interpreted GP system at that, it is essential that all features be as computationally efficient as possible. There are various means of increasing the efficiency of features. Convolution masks can be optimised or approximated, and in recent years the usage of an \emph{integral image}, or summed-lookup table \cite{Crow:1984:STT} was popularised by the work of Viola and Jones \cite{EvoVision:Viola-Jones:2004}. An integral image, as its name suggests, is a summed table produced from an original image in which a point at $(x,y)$ consists of the sum of pixels' intensities in the rectangular region from the origin $(0,0)$ to that point. Using such a table, it is possible to calculate sums or arbitrarily-sized image regions using just four array accesses, two addition and two subtraction operations. Certain statistics, such as standard deviation, may also be calculated more efficiently\footnote{The efficient calculation of population variance is an interesting topic in its own right. Since the standard deviation is calculated as the sum of differences for a series of values ${x_1, ..., x_n}$ from their mean $\mu$, it can be calculated in two passes, one to calculate $\mu$, and one to calculate the standard deviation. However, this requires storing all values of $x$ which is inefficient. A naive one-pass solution calculates the population variances as $\sigma = ({sum of the squares})/n - ({square of the sums})/n^2$, but this is numerically unstable in the cases where $n$ is large and the difference between the numerator values is small. The author uses a one-pass algorithm by Knuth \cite{knuth2}, which iteratively calculates the mean and is numerically stable.}.

\paragraph{4. Usefulness}
In a general sense, each feature should aid the decision making process by providing ``useful'' information. To contrive an example to illustrate the point, the number of credit cards that a person has may help predict how much debt they are in, but the last three digits on the back of each card is unlikely to be a successful predictor: both features come from a similar source, but one is significantly more helpful than the other. In imaging the same may also be the case.

Naturally enough, these requirements tend to conflict with each other: the more localised a feature is, the more sensitive it is to small fluctuations, which may impact its reliability. The need for efficiency limits the complexity of features that can be used. Needless to say, it is difficult to find a feature that can meet all the requirements, but the idea is to provide a library of features that is sufficiently diverse as to allow each requirement to be met in different ways. The task of the GP system is to choose the appropriate features required to develop a suitable feature detector.

The final requirement, concerning the assessment of usefulness, will be discussed later in this chapter. However, before we can discuss the \emph{selection} of features, we must first give some consideration the features themselves.

\section{Image Features}
In order to render the system capable of solving a variety of different problem types, image features from three different families were explored:

\begin{itemize}
 \item Colour Information, about the intensity and colour of a particular pixel.
 \item Texture Information, regarding the pattern surrounding the pixel in question.
 \item Spatial Information, regarding the location of the pixel within the image.
 %\item Temporal Information regarding the changes to a pixel across several frames
\end{itemize}

\noindent These are discussed below.

\subsection{Colour Features}
In this section, the author shall discuss the kind of \emph{colour} features that can be made available to the feature detector. However, since ``colour'' is more of a perception than a physical property, it is worthwhile to consider the pre-processing operations that may make colour information more robust in general.

\subsubsection{Robustness to Illumination}
While light sensors (including our eyes) only perceive a beam of light in terms of its wavelength -- a scalar property -- the light is actually the product of at least two sources: the irradiance of the light(s), and the reflectance of the surface being viewed. The human vision system seems able to recover the surface's reflectance, what we describe as ``colour'', with relative accuracy, regardless of the light source, a phenomenon known as colour constancy. While it is sometimes difficult simply to calibrate camera white-balance in order to reproduce colours faithfully, the development of software that can \emph{perceive} colours accurately is even more tricky. 

Developing colour constancy algorithms is just one part of the huge task of developing a sensor that can compete with the masterpiece of engineering buried within the human vision system. The discipline of colour science is rather beyond the scope of this thesis, but a couple of ideas will be discussed briefly here. We shall make use of one of them later in this chapter.

One algorithm, white-patch retinex \cite{white-patch}, assumes that the true colour of the light can be identified by looking at white patches in the scene (which are assumed not to affect the irradiance). White patches are relatively easily identified, as they are the usually the brightest. When the light's colour is known, then the colour of the rest of the image can be divided by that value to recover the ``true'' colour of the scene's materials. The white-patch algorithm is used by many digital cameras for calibration, although it is dependent the presence of something white, and that the illumination is reasonably consistent throughout the scene.

Another approach, grey-world assumption \cite{greyworld}, is based on the expectation that the \emph{average} colour of images tends to be grey. Therefore if one finds the actual average colour of an image, each pixel can be adjusted such that the average colour becomes mid grey. Although slightly more computationally expensive than the white patch algorithm (the image needs to be read twice, once to calculate the average colour, second to adjust the values) the technique can produce reasonably good results.

Figure \ref{fig:greyworld} shows the author's implementation of a basic grey-world retinex algorithm on two images that have been ``lit'' with different lights. While it is difficult to know what the ``true'' appearance of the image, minus the lights is, the algorithm appears to work reasonably well, here at least producing the kind of consistent perception necessary to make decisions more robust, although the saturation and contrast in the lower images is reduced because of division operation. While the author does not claim to have implemented an ideal solution to the problem, its inclusion here is recognition of a useful processing step for a system designed for creating generic vision systems which may have to work in non illumination-controlled environments.

\begin{figure}
\begin{centering}
\includegraphics[width=0.75\textwidth]{images/greyworldcolourconstancy}
\par\end{centering}
\caption[Algorithms for Colour Constancy]{The two images at the top have different tints, to indicate different lighting conditions. The images on the bottom show each images following adjustment by the author's grey-world-assumption implementation. The lower pair of images are more comparable than the top two.}
\label{fig:greyworld}
\end{figure}

\paragraph{Exposure Compensation}
Machine vision systems may also produce inconsistent results in environments where the range of intensities is too large for the camera's exposure system to accommodate. Although humans are able to perceive both very bright and relatively dark objects within the same scene with relative ease, cameras tend to correctly expose one area while underexposing or overexposing others, manifested in some images by either completely white-out skies (``blown out highlights''), or dark silhouettes in the foreground (``blocked up shadows''). The human retina is composed of both extremely sensitive intensity sensors (rods), and much less sensitive colour sensors (cones). This allows our vision system to support a much higher dynamic range than current camera sensors, which typically only apply one level of sensitivity to the whole CCD at once\footnote{The Sigma SD14 Digital Camera is intended to be better in this regard since it uses an unconventional sensor using a separate element for each of the three colour components instead of a single one; however, camera manufacturers generally do not publish the dynamic range of their sensors.}; exposure in cameras is typically governed by a single light meter. Furthermore, camera light meters assess exposure by subject brightness rather than incident illumination.

%TODO: Look at Cornsweet

Until camera sensor technology improves in this regard, computer vision software in environments with uncontrolled lighting conditions will remain a limitation affecting the robustness of machine vision applications. But again, there are algorithms which can improve the camera's exposure in software, one of which is described here. As it is generally the case that illumination affects large areas while a surface's texture is finer, an estimate of the average exposure of a pixel can be gleaned from looking at a weighted average of the pixels around it. If the weighted average is treated as the level of illumination, then the pixel's intensity can be updated accordingly such that all pixels in the scene have more equal illumination. This forms part the ideas proposed by Land in his Retinex Theory \cite{land83}\footnote{Edwin Land, founder of Polaroid and prolific researcher, developed his retinex theory after conducting experiments which showed people can perceive colours in an image even when that colour isn't used at all by the illuminant. He stated the perceived colour is not absolute, but depends on the surroundings.}. The author has implemented a simple example of this algorithm, the results of which are shown in Figure \ref{fig:exposure}. While the image cannot be perfectly restored, the algorithm is capable of reducing some of the blocked up shadows; the contrast boost may be enough to permit image processing algorithms such as edge detectors to find features where they would otherwise fail.

\begin{figure}
\begin{centering}
\includegraphics[width=0.75\textwidth]{images/exposure-adjustment}
\par\end{centering}
\caption[Exposure Correction Algorithms]{The two images at the top are both poorly exposed. However, it is possible to recover the image to an exposure more akin to the perception of a human, using a software exposure compensation algorithm (see text). Some colour information is lost, however, due to the 8-bit nature of this image.}
\label{fig:exposure}
\end{figure} 

This completes this author's brief foray into the world of colour constancy and exposure control. Although there are many other more complex approaches, these techniques can, at least, aid the perception of an image by making some parts visible, and providing a degree of the consistency which is vital for the robustness of learned vision approaches. Later in this chapter we shall consider some vision tasks which may benefit from colour constancy pre-processing, and investigate whether these algorithms produce more robust solutions.

\subsubsection{Appropriate Colour Spaces}
Having discussed how images might be rendered more consistent before processing, we turn to the numeric description of colour itself. The traditional way to express a colour in computing environments is dictated by the construction of display hardware which present a colour in terms of its red, green, and blue components. The intensity, or brightness, of a given colour can be calculated by performing a weighted sum of each component. The weights are chosen that match most closely our own perception\footnote{The cones (colour sensors) in the human retina have different sensitivities to different wavelengths. The most sensitive cones are those that respond to green light, while the least sensitive are those that respond to blue light. This ratio is taken into account in the formula above. Since yellow is regarded as the combination of red and green, the two most sensitive wavelengths, this makes it the most suitable colour for high-visibility clothing.}, accepted values are generally in the region of:

%TODO: Adrian things blue is less sensitive still.

\[
I = 0.3R + 0.59G + 0.11B
\]

\noindent The benefit of using RGB values is that intensity can be computed rapidly using the above formula; however, the additive nature of RGB space means that none of the three components is independent of the illuminant's intensity, which leads to issues of robustness with regard to illumination and object geometry. Illumination originating from a point light source will shine with different intensities on most 2D or 3D surfaces since all points are not the same distance from the light source (see Figure \ref{fig:illumination}). Directed lighting in general will illuminate a three dimensional shape in different ways according to its geometry. Thus while an object may be composed entirely from the same material, the RGB components are neither illumination or geometry invariant; algorithms using them may be prone to over-segmentation. Consequently, raw RGB components are not used by the author's system.

\begin{figure}
\begin{centering}
\includegraphics[width=0.9\textwidth]{images/illumination-geometry-invariance}
\caption[Variances in Illumination]{Planar surfaces will generally receive variable illumination from point lighting, the geometry of non planar objects will cause different parts of the object to be illuminated differently.}
\label{fig:illumination}
\end{centering}
\end{figure}

However, RGB may be used as the basis for producing different colour spaces.
Many computer vision researchers choose to use colour spaces which separate the illumination component of a colour wholly or partly into its own independent channel. Hue/Saturation/Intensity (HSI) is one space which partly fulfils this criterion, defining a colour according to its shade, its saturation (``strength of colour'') and overall illumination intensity. HSI colour components make potentially more succinct information about the pixel's colour available to the learning system making each feature inherently more useful. Although the conversion from RGB to HSI is reasonably straightforward there are other RGB transformations that also benefit from more illumination invariance.

% TODO: how to detect if an image is greyscale or not?

Since Hue and Saturation are less affected by changes in illumination intensity or shadow, the features are generally considered more robust, although the Hue value is unstable along the entire achromatic axis, and unsurprisingly is best avoided in grey-scale images. The author's system can automatically detect the use of grey-scale images; in these cases colour-based features such as Hue are disabled.

Although RGB components in their raw forms pose disadvantages, they can be readily used to generate different colour features. For example, they are often normalised as follows:

\[
R = \frac{R}{R+G+B}
\]

\[
G = \frac{G}{R+G+B}
\]

\[
B = \frac{B}{R+G+B}
\]

\noindent Since the RGB space is additive, the total intensity can be estimated by summing each component. Dividing each component by the intensity estimate gives a value that should be less affected by the intensity of the illumination. Although the colour of the light itself will still have an effect, this may be mitigated by colour constancy pre-processing.

Other easily computable models include the $c1c2c3$ model by Gevers and Smeulders \cite{gevers99}:

\[
c1(R,G,B) = tan^{-1}\left(\frac{R}{max(G,B)}\right)
\]

\[
c2(R,G,B) = tan^{-1}\left(\frac{G}{max(R,B)}\right)
\]

\[
c3(R,G,B) = tan^{-1}\left(\frac{B}{max(R,G)}\right)
\]


%The $o1o2$ model is also used, as it is invariant to highlights:

%\[
%o1(R,G,B) = \left(\frac{R-G}{2}\right)
%\]

%\[
%o2(R,G,B) = \left(\frac{R+G}{4}-\frac{B}{2}\right)
%\]

%TODO: What are the disadvantages, and why is it invariant?
\noindent This model is sometimes used for shadow identification owing to its illumination invariance due to the geometry of the object, although this only applies to illumination by white light. The $l1l2l3$ model \cite{gevers99} is also used, as it is invariant to specular highlights:

\[
M = (R - G)^2 + (R - B)^2 + (G-B)^2
\]

\[
l1 = \frac{(R-G)^2}{M}
\]

\[
l2 = \frac{(R-B)^2}{M}
\]

\[
l3 = \frac{(G-B)^2}{M}
\]

\noindent In common with any feature derived using a division, the normalised RGB operators are unstable near the black vertex of the RGB cube. The best that can be done is to ensure that no divide-by-zero errors occur. HSI values, normalised RGB values, $c1c2c3$, and $l1l2l3$ are made available to the GP segmenter as \emph{channels}, using which any image statistic may be computed. Of course, statistics typically require the input from a number of different points; features which combine data from many pixels are discussed in the following section.

% Read: Motion Detection using an Improved Colour Model for an improvement to HSI that doesn't have an unstable hue.

% TODO: What about the YUV Colour Space? What about CMYK?
% TODO: Discuss Color Quantization

% Running sobel operator on different channels - can find shadow edges if run on the intensity channel only.
% Paper on Shadow segmentation: "Cast Shadow Segmentation using invariant colour features"

\subsection{Texture Features}
So far we have discussed single-pixel features, which can only be meaningfully described by their intensity or colour, and are limited to a few reasonably straightforward design choices. This section will deal with features that combine the inputs from an \emph{area} of pixels near to a central point of interest. 

A benefit of multiple-pixel features is their potential to describe the spatial context around a point of interest, otherwise known as pattern or texture. Although colour or intensity information is often useful in segmentation, in low contrast or grey-scale images the texture of different objects may be the only suitable discriminant. One example is the distinction between human skin and wood, which are quite often to be found in close proximity and yet may appear very similar in terms of colour alone -- especially through low quality cameras.

One approach is to provide the feature detector with the intensity and other colour information regarding every pixel in a region surrounding the central point of interest, and leave the GP system to invent texture discriminants of its own. Given arithmetic, statistical and logical operators, it is perfectly possible that the GP system could evolve a form of convolution mask or indeed a more complex descriptor. Since no data are lost, it may be possible to develop a measure that accurately represents the texture. We saw in Chapter 2 that Song and Ciesielski \cite{EvoVision:Song-Ciesielski:2004} compared this approach to evolution using Haralick statistics (covered shortly) as image features. The problem is that a relatively large number of pixels is required in order to produce a discernible pattern, and typically each pixel is represented by one terminal in the GP tree, so the evolved programs would have to be relatively large in turn. Given sufficient time, a learning system may discover useful ways of combining pixel data to develop texture features, but it may longer than the genetic programmer is prepared to wait! This kind of approach, attractive in some senses, is thus unlikely to be a practical solution. Indeed, Song and Ciesielski found that the individuals using Haralick features yielded more accurate results.

Therefore, the requirement of texture features is that they should reduce the dimensionality of the data by processing a number of pixels together in order to arrive at a single statistic that concisely represents a notion of texture. Since several features may be used for each pixel, their processing should be as fast as possible to ensure that the learning process can proceed and that the eventual program can operate in practical circumstances.

One family of texture features are those which produce averages of colours by using a $n \times n$ mask to convolve pixels in some way. Common examples include Gaussian, Laplacian and Sobel Masks. Gaussian masks may yield an intensity estimate that is more robust to noise, while Laplacian and Sobel masks are useful in detecting edges and their direction. Different masks with different weight matrices can easily be applied, permitting the segmenter to discover edges, or identify certain basic patterns. Although convolution masks are typically used to emphasise certain parts of an image, they don't give much indication of texture, as their primary effect is to blur or discard spatial data, or match specific patterns.

%This kind of feature might give GP the capabilities for a rudimentary shadow detector, where shadows can be detected when the average illumination changes, but the hue remains relatively constant. The main advantage is the smoothing operation which may reduce the suceptibility of the solution to noise.



Other descriptors of texture may be imagined quite readily. Indeed we saw in Chapter 2 that GP researchers have made use of a number of \foreign{ad hoc} features. Possible descriptors include the difference between neighbours' intensity values, which may give an indication of the contrast of the texture, the arrangement of neighbours may that reveal the directionality of patterns within the texture. The rate of intensity change across a series of points could reveal the roughness or smoothness of the texture. Given a set of pixels, one obvious approach is to calculate the variance in value of a particular channel, which gives an indication of the smoothness. Other straightforward statistics such as the range may be used to get an impression of the contrast in that area of the image.  The number of edge pixels in a particular area may provide some indication of the ``busy-ness'' of the image, and the directions of each may provide useful, relatively scale invariant information about the nature of the texture itself.
Although simple, these calculations may be computed more easily than other techniques and may still provide useful discriminants.

One of the most well-known texture analysis methods computes texture descriptors from Grey Level Co-Occurence Matrices (GLCM). A GLCM records probabilities between different intensity levels given a particular spatial relationship between two pixels, for instance the relationship between one pixel and the pixel directly below or above it. Each GLCM can be used to calculate a variety of different texture metrics, known as Haralick Statistics, some of which are summarised in Table \ref{tab:haralick}.

\begin{table}
\centering
\begin {tabular}{ l p{10cm} }
\toprule
Contrast 	& Contrast is measured by the sum of GLCM probabilities, weighted according to their distance from the diagonal point of the GLCM (the further the distance from the diagonal, the higher the contrast).\\ \midrule
Angular Second Moment &	Calculated from the sum of squared probabilities, high values provides a measure of the ``orderliness'' of the texture since high probabilities (definite patterns) will be emphasised, and low probabilities will be emphasised less.\\ \midrule
Entropy 	& Gives an indication of the ``disorderliness'' of the image by summing the natural log of each probability, which gives highest weight to low probabilities.\\ \midrule
GLCM Mean & Measures the average probability of whatever relationship the GLCM is measuring. Horizontal and vertical GLCMs may produce different means.\\ \midrule
GLCM Variance & Measures the Standard Deviation of GLCM probabilities and is similar to the entropy measure. A completely uniform image will have a GLCM variance of zero.\\ \bottomrule
\end {tabular}
\caption{A Description of Several Haralick Statistics}
\label{tab:haralick}		
\end{table}
 
While the GLCM is relatively easy to understand and calculate, its usefulness is somewhat dependent upon the quantisation level of the image. For 8 bit images, producing 256 separate grey levels, the matrix will require a $256\times256$ array, which is resource hungry, especially if the process must be repeated for every point in the image. With an array of this size the matrix will inevitably be extremely sparse, unless the area surrounding the pixel is expanded significantly, although this in turn will produce a ``border'' effect around the edges of the image and reduce the feature's ability to localise. The practical reaction is to quantise the image intensity values into larger ranges, although this has the drawback of de-sensitising the matrix to more subtle changes.

\subsubsection{Haar-like Features}
Haar-like features are used for object detection/recognition rather than analysis of texture \foreign{per se}.  Although some objects are deformable and may be better identified by texture, shape is often a useful descriptor. A differential operator, Haar-like features \emph{compare} two or more adjacent rectangular areas within a portion of an image. For each area the sum of pixel intensities is calculated; the feature returns the difference between different areas. The feature can be in any location or scale relative to a central decision point. Haar-like features were popularised by the work of Viola and Jones \cite{EvoVision:Viola-Jones:2004}, who used them for face detection. Viola and Jones invented additional features, composed of three and four sub-rectangles (see Figure \ref{fig:haar-regions} for some examples). The principal advantage of Haar-like features is that they can be computed readily using an integral image (see page \pageref{integral-image}). The integral image can be manipulated to return sums for rectangles tilted at 45$^\circ$, which may be useful in some applications. 

The disadvantage of Haar-like features is that they cannot be used "out-of-the-box", as it were. The parameters that identify useful Haar features in terms of their position and scale need to be determined first, and this process may also be processor intensive. Typically a parameter optimiser such as a Genetic Algorithm is used to identify the parameters that define useful Haar features for a given task.

In order to render Haar features more consistent, the author's implementation divides the differential result by the area of the feature, such that the result of any feature will occupy the same numeric range (0-255).

%This was stupid idea...
%\footnote{The author also tried expressing the differential using a percentage rather than absolute difference, based on the assumption that this would make the feature more robust to changes in illumination. The percentage difference variation reduced the discriminative ability of the haar feature on the AT\&T face dataset by a substantial margin: even apparently sensible ideas should be tested on real data before being adopted!}.


\begin{figure}
\begin{centering}
\includegraphics[width=0.9\textwidth]{images/haar-features}
\caption[Haar Feature Examples]{Some examples of 2/3/4 rectangle Haar-like features. The darker rectangles correspond to those regions that are subtracted.}
\label{fig:haar-regions}
\end{centering}
\end{figure}

\subsubsection{Dissociated Dipoles}
``Dissociated dipoles'' are similar in nature to Haar-like features, except where the comparison made between adjacent rectangles is inherently local in nature, dissociated dipoles make comparisons between different areas of the image, which may be far apart. In some ways this is a more flexible structure than Haar-like features. The original dissociated dipole was an operator that measured the differential between two gaussian convolution masks of variable scales and locations. 

Again, dissociated dipoles require their parameters to be chosen according to the vision task, in a process of feature extraction. The author spent some considerable time looking into this, including using Genetic Algorithms and other search procedures. The solution eventually devised by the author was to develop a new type of GP terminal node which includes its own parameters. The node can initially choose random parameters for itself (within sensible limits), and subsequently generates different features using a similar procedure to produce a population of features. Given a score, the node can go about a hill-climbing technique to improve its discriminative abilities. This technique is integrated into the author's feature selection and extraction interface which is covered in the following chapter.

\subsection{Location-Based Features}
A more straightforward family of features gives an indication of the pixel's location within the image. These features include the distance of the pixel from the centre of the image, and the angle thereof. Certain problems in vision may pay more attention to those objects closer to the center of the image than on the outer edges. Many problems, however, will not require such features; the feature selection technique employed by the author's toolkit (see Section \ref{feature-selection}) will remove these features if not needed.

%\subsection{Motion Based Features}
%The final feature type gives clues as to the motion within a sequence by comparing any feature in one frame to the equivalent position in the other frame. Although the author was enthused enough to implement these features, they are not used by any of the chosen vision problems and so are not discussed further.

%TODO: Explain what Euclidean feature is

\subsection{Other Features}
By now we have covered a variety of different image operators, each of which are made available to the author's GP system for the purposes of evolving a feature detector. Other features include the author's \emph{DistanceFeature} which computes the Euclidean distance between the entire current input feature vector and a known feature vector from the training set. This allows GP to create solutions slightly similar to k-nearest-neighbour, which is often surprisingly effective at finding solutions. Unlike k-NN, however, the distance of only one vector may be checked at a time, so the feature instead provides another means of non-linear transformation.

% TODO: Discuss scale and rotation invariant texture features
\subsection{Invariance}
Integral images make it possible to compute Haar-like features efficiently. Indeed it is this kind of feature that makes it possible for modern digital cameras to recognise faces in real time, despite their limited processing capabilities. Although they can be used to approximate circular regions, rectangles are generally not rotation invariant, which limits their applicability for certain problems. 

If we confine ourselves to the recognition of 2D objects from a top-down perspective, then rotation invariance can be achieved by using circular features. The disadvantage is that they cannot be computed so quickly, although they can be approximated. One may use either completely circular features, rings, or circular perimeters. The latter were used by Roberts \& Howard  \cite{roberts:1999:evdIRLI} for recognising vehicles and ships from satellite images, with some success. The author prefers perimeter based-features, because they involve fewer pixels and are therefore more efficient to compute. Various calculations can be made from each perimeter, including the mean and standard deviation of pixel intensity. Perimeter features can also calculate the number of edges they encounter: an ``edge'' is detected if the difference between two adjacent pixels' intensity is larger than half the image's standard deviation.

For some problems it is not necessary for the feature detector to be rotation invariant. In the following chapter we shall see examples of features which lend themselves to rotation invariance more elegantly.

The scale invariance of certain features may be measured by scaling them (and the image) up and down to see whether they return a consistent result. An experiment was run for this purpose, using a number of image points and a selection of 6 straightforward features, which calculate the means and standard deviations from horizontal and vertical lines, and from circular perimeters. The average deviation of each feature from its value at 100\% image size is plotted in Figure \ref{fig:feature-scale-invariance}. As one can see, many of the \foreign{ad hoc} features do not produce invariant results at different scales. As one might expect, the mean is largely unaffected by changes in scale, so mean-derived descriptors, such as the Haar-like features should produce similar robustness to changes in scale.

% From scale-invariance.xls
\begin{figure}
\begin{centering}
\includegraphics[width=0.9\textwidth]{images/scale-invariance}
\caption[Feature Scale Invariance]{Measuring the invariance of certain features to changes in the image scale. As the image approaches half its original size, some features' output deviates by over 30\%. The perimeter, which increases in size while maintaining a single pixel thickness is naturally most prone to deviations of scale. Other features such as the mean, unsuprisingly, are very robust to changes in scale.}
\label{fig:feature-scale-invariance}
\end{centering}
\end{figure}

A common approach to scale invariance is through the use of a framework referred to as ``scale space'', which considers an image at various different scales, following convolution by a gaussian mask of different sizes. This method can reveal those points which are apparent at all scales in the image, so it is commonly used in feature point detection techniques, such as SIFT \cite{sift}. Once these features have been detected, they can be used for a variety of tasks, including object detection. 

%TODO: Mention finding points of interest then using them for recognition is opposite to the author's approach, since it is not easy to control how the points are found.

However, it is less straightforward to adapt existing features into scale invariant ones, since most are inherently local in nature. One reaction to this is to define the scale of features themselves according to some window. The window can then be applied to images at different scales in order to find objects or features of different sizes. The author's segmentation features may be defined in terms of position and location within an arbitrary window, expressed in percentages.

To summarise, the author's feature detector has access to approximately 60 different image features, including image intensity, normalised colour operators, Haralick statistics, Haar-like features, dissociated dipoles, rectangular, convolution operators and linear and circular area statistics.

\section{Feature Selection}
\label{feature-selection}
Given the large number of potential features with which one could describe an image, a few of which have been described above, it is worthwhile to identify  those features that may be redundant or irrelevant.  Motivations for eliminating ``useless'' features include avoiding the so-called ``curse of dimensionality'', the effect in which the search space grows exponentially as extra features are included. Learning only using relevant features may also improve the learned system's ability to generalise, as its outcome is dependent only on true discriminants. Finally, in the spirit of \emph{Ockham's Razor}, feature selection can help make the classifier more efficient, both in terms of final execution speed (fewer features need to be calculated for the classifier to make its decision), and the rate at which the classifier can be learned in the first place.

Two schools of thought dominate feature selection philosophy filtering and subset selection, discussed in the following paragraphs.

\paragraph{Filtering}
%Minimum Redundancy Maximum Relevance
The first approach is concerned with evaluating features individually. Features are usually scored against certain criteria, with the top $n$ being selected for inclusion within the feature vector. The criterion may involve measuring the variable's linear correlation with the ground truth, or indeed their individual predictive power when used by a classifier such as Linear Discriminant Analysis.

\label{ig}
Other metrics aim to assess ``usefulness'' in more concrete terms, for instance by calculating the \emph{information gain} of a feature, which is defined as the difference between the entropy of the training data $H(Y)$, and the average conditional entropy $H(Y|X)$ given a particular feature $X$ . The larger the information gain, the more useful is the feature $X$.

A criticism is that these techniques do not generally consider the correlation \emph{between} different variables, which may lead to a feature set characterised by a high level of redundancy. Some techniques, such as \cite{peng05}, aim to maximise relevance while minimising redundancy by developing a more complex scoring system that takes both into account.

\paragraph{Subset Selection}
A distinct approach is to consider the set of features as a whole, without trying to assess the usefulness of each variable individually. The rationale is that simply because a feature doesn't perform well against some metric individually doesn't mean that it doesn't have any merit. 

A straightforward technique in this regard was reviewed in a popular paper by Kohavi and John \cite{kohavi97}, concerning the ``wrapping'' of learning machines as black boxes. The black boxes were used as evaluators for different variable subsets. Since our perception of what should make a useful variable will not necessarily translate into a positive outcome for the solution, this method dispenses with any arbitrary scoring and focuses instead on a more direct predictor of success. 

This kind of approach attracts its own criticisms for being rather brute force in nature. Putting to one side the idea that an exhaustive search could lead to over-fitting on the training data, for all but the simplest problems the computational expenditure required makes exhaustive search impractical.

It appears that the rough search strategies implemented by greedy hill-climbing algorithms seem to do well instead, both in terms of alleviating over-fitting and preventing the computation from becoming intractable. \emph{Forward selection}, by which features are added to the dataset one at a time, or \emph{backward elimination}, by which features are eliminated one at a time, appear to be effective greedy algorithms. Nonetheless, Genetic Programming is already slow enough, so the author chose not to use wrapper methods for feature selection, favouring the individual filtering algorithms which can be executed in a matter of seconds.

% Sometimes it is useful to have different subsets for different classifiers in an ensemble (See David Opitz, 1999)

%TODO: Mention Branch and Bound Techniques

In any case, one of the advantages of Genetic Programming is that it permits a reasonably large library of features to be used; feature selection is a natrual consequence of the selective process. The nature of genetic learning systems is to breed the useful solutions more often than the use\emph{less} useful ones, so a viable form of feature selection is already included. In any case, genetic programs are under no obligation to use all the features available, and the usual fitness criterion favouring smaller individuals may help to ensure solutions are as general as possible\footnote{In fact, without proper checks, GP programs will sometimes use none at all, and simply return the most popular class.}.

%Todo: Experiment comparing different subsets on the same classifier: does it make a difference?

\subsection{Experiments}
Nonetheless, with an expanding set of image features, it is worthwhile investigating which are most useful for a particular task. Conversely, one can consider feature selection as a means for removing irrelevent features that may affect the ability of a classifier to generalise or operate efficiently. At this point it is necessary to move away from the public datasets and their fixed feature sets, and start using images directly to generate feature vectors. Over the course of his research, the author has developed a number of image datasets for different purposes; four of which are described below.

\label{flags-dataset}
\textbf{Flag Colours Dataset. Colour. 8 Classes}
The first dataset is concerned with the recognition of different colours, taken from images of 16 different European flags. Images of each flag were printed and then cut out to produce different cards. Images of each card were then captured through a webcam\footnote{A Logitech Quickcam Pro 5000, a reasonably good quality camera, costing about \pounds50 in 2007.}. The goal is to reliably identify the colours apparent in each flag design.

Given the relatively poor reputation of webcams in terms of photographic excellence this set provides a useful experiment to identify the robustness of vision algorithms created by the author's system, using everyday equipment in habitual environments. The samples in the dataset are categorised into 7 classes, corresponding to 7 colours\footnote{`Red', `Yellow', `Green', `Light' `Blue', `Dark Blue', `White' and `Black'.} and a background class.

\begin{center}
\includegraphics[width=5cm]{images/flags}
\end{center}

\textbf{Pipeline Dataset. Texture. 4 Classes }
The author's pipeline dataset is derived from top-down images collected from an unmanned aerial vehicle (UAV) at a height of several hundred feet. The task is to identify automatically different regions within each image: ground, vegetation, water and buildings/roads/pipeline.

The pipeline dataset is a more useful assessor of segmentation by texture, as each class cannot readily be distinguished by colour (the saturation of the images is quite low).

\begin{center}
\includegraphics[width=5cm]{images/pipeline}
\end{center}

\textbf{Leaves Dataset. Background Subtraction. 2 Classes}
The third dataset is concerned with locating different types of leaf, photographed against a variety of cluttered backgrounds. Images come from the Caltech leaves dataset \cite{leaves}. This is a binary dataset with two classes: leaf and not-leaf.

\begin{center}
\includegraphics[width=5cm]{images/leaf} 
\end{center}

\textbf{Pasta Dataset. Background Subtraction. 2 Classes}
This dataset is representative of some kind of industrial inspection task. Like the leaves dataset, the primary task here is background subtraction, permitting the localisation of objects.

\begin{center}
\includegraphics[width=5cm]{images/pasta} 
\end{center}

Three different feature selection techniques were applied to select features for each dataset. Each was an attribute filtering technique, as opposed to a subset-selection method. These were:

\begin{description}
\item[Linear Discriminant Analysis]
The feature's capability as an independent discriminant was measured using Linear Discriminant Analysis (see page \pageref{lda}). The score was measured according to the number of samples the LDA classifier could correctly classify using the feature, using the fitness function $error_1$ (see page \pageref{error1}).

\item[Program Classification Map (PCM)]
The author's implementation of a DRS2 Program Classification Map (see page \pageref{pcm}) was used to convert the feature into a classifier. The score was measured according to the number of samples the PCM classifier could correctly classify using the feature

\item[Information Gain (IG)]
The score of each attribute was measured by its Information Gain (see page \pageref{ig}) with respect to the known classes, which measures the difference in entropy between the training set and the output of the classifier on the training set.
\end{description}

Each feature selection technique was used to reduce the size of the feature set from 60 down to 20 features.  Each attribute was individually scored, with the top 20 chosen to form a new feature set, from which a dataset was produced. Both the reduced and original datasets (using all the features) was then used as training data for the author's ICS classifier, which developed solutions in the usual manner for each. Each experiment was repeated 50 times; the results are shown in Table \ref{table:feature-selection}. In the Flags dataset there were no statistically significant differences in performance on test data. In the Pipelines task, the reduced datasets did produce, on average, individuals that were significantly better, although the absolute difference was not huge. 

The numerical basis for an interesting observation is shown in Table \ref{table:feature-selection-generalisation} which shows the percentage difference between the training error and test error for each dataset. For both tasks, the difference is significantly higher when using the entire set than when using filtered subsets. This indicates that classifiers developed using the reduced feature sets are able to generalise better, perhaps because those irrelevant features that may affect generalisation have been removed successfully. 

In conclusion, the results on these tasks appear to show that the feature sets for feature detection problems can be quite sharply reduced without causing any significant decline in performance; indeed the performance of pipeline classifiers improved for all filtering algorithms. With the desire to add more and more image operators to render a system capable of solving a wide variety of problems comes the need to ensure that the feature sets are maintained at a manageable size, and it would appear that this kind of feature selection technique is a suitable means for doing so. The observant reader will note that subset selection techniques are not covered here: the author's preference is to use filtering techniques that can assess the relevent features in seconds. A lengthy process of genetic learning, preceded by an even lengthier feature selection operation would be likely to test the patience of the end user!

Having covered three different feature filters, a reasonable question is which is the most useful? Based on the limited results provided here, a definite choice would be premature. Nonetheless, the author has a preference for the \emph{PCM} technique on the basis that it is fast, and naturally shares much in common with the GP classifier itself, so would appear to be a good model. As we'll see later in this chapter, there are further uses for this type of feature selection.

% From feature-selection.xls
\begin {table}[ht]
\centering 
\begin {tabular*}{0.9\textwidth}{ lrrrr }
\toprule
Task		& Entire Set 		& Filtered (LDA) 	& Filtered (PCM)	& Filtered (IG) \\ \toprule		
Flags		& 93.5 $\pm$ 3.5	& 93.9 $\pm$ 2.6	& 92.7 $\pm$ 2.6	& 93.9 $\pm$ 2.9 \\ \midrule
Pipelines	& 95.4 $\pm$ 0.5	& \textbf{95.9} $\pm$ 0.5 		& \textbf{95.6}	$\pm$ 0.5	& \textbf{96.3} $\pm$ 0.3 \\ \bottomrule
Leaves	& 97.6 $\pm$ 1.0	& \textbf{98.0} $\pm$ 0.6 		& \textbf{97.7}	$\pm$ 0.9	& 97.7 $\pm$ 0.8 \\ \bottomrule

\end {tabular*}
\caption [Feature Selection: Performance]{Comparing the average performance of classifiers, evolved using different feature sets, on test data. Significant differences in \textbf{bold}, $\pm$ denotes standard deviation.}
\label {table:feature-selection} 
\end {table}

\begin {table}[ht]
\centering 
\begin {tabular*}{0.9\textwidth}{ lrrrr }
\toprule
Task		& Entire Set 		& Filtered (LDA) 	& Filtered (PCM)	& Filtered (IG) \\ \toprule		
Flags		& 7.39			& 2.17			& 2.32			& 3.16 \\ \midrule
Pipelines	& 14.16			& 0.61	 		& 0.37			& 5.34 \\ \bottomrule
Leaves	& 17.4			& 10.26			& 1.59			& 7.05 \\ \bottomrule
\end {tabular*}
\caption [Feature Selection: Generalisation]{Comparing the average percentage difference between classifiers' training and testing performance (an indication of their ability to generalise), evolved using different feature sets}
\label {table:feature-selection-generalisation} 
\end {table}

\section{Performance Considerations}
Like GP learning, machine vision is often computationally expensive. If the former is used to develop the latter, then it is doubly important to ensure that evolution can proceed as efficiently as possible! We have already touched on various means by which the GP process can be made more efficient, by decreasing population redundancy or employing integral images and faster means of calculating statistics. Here we shall look at some further means by which the performance of GP vision learning can be improved.

\subsection{Image-Level Caching}
Efficiency can be achieved both by ensuring the algorithms themselves are not computationally wasteful, and by minimising the number of re-calculations made, typically by caching results.

Certain sub-trees become common in genetic populations because of the selective pressure imposed on good individuals, leading the crossover operator to repeatedly copy certain sub-trees of popular parents. An approach taken by Roberts \cite{Roberts03caching} to improve the speed of GP on image processing problems was to cache the results of common sub-trees on the training data, saving the need to re-evaluate them continuously. While this technique was shown to be quite successful, it was memory hungry: one value for every pixel on every image for every sub-tree is stored, probably at least one byte in size. Accordingly, a cost-based decision was made to determine which sub-trees should be included in the cache by estimating the time taken to retrieve the cache from disk versus the time taken to make the calculation in the first instance. Roberts reported decreases in evolutionary time were measured between 1.5\% and 52.2\%, which is quite promising. Experiments were conducted on a variety of different population sizes; the largest improvement was attained when using a population size of 2000, rather larger than is generally used, and thus more prone to benefit from any kind of caching.

The author's own caching approach takes place at the image level, rather than the sub-tree level. Since image processing is the most significant bottleneck in learning vision systems, it makes sense to cache the imaging functions themselves, rather than the sub-trees, which often amount to little more than performing arithmetic operations upon underlying image calculations. SXGP makes use of the author's own imaging library which caches the results of imaging operations so that subsequent processes can proceed more quickly. Basic pixel metrics, such as the mean grey-value of an image may be called several times \emph{per pixel}, for instance by convolution masks. These are cached. The caches are implemented using one-dimensional arrays which can be accessed efficiently. The results of other, more complex, operations may also be cached.

Figure \ref{fig:caching-performance} shows the advantage and disadvantage of this type of caching, here implemented in two ways: ``half'' caching, in which only the most essential operations are cached\footnote{Grey-scale, Red, Green, Blue, Hue, Saturation, Lightness.}, and ``full'' caching, where a variety of other results from more computationally expensive operations are cached. The figure shows that the time taken to process $n$ images is significantly lower for the cached methods, with ``full'' caching requiring the least amount of time overall. Caching permits the operations can be run on the images nearly three times faster than otherwise.

While caching permits evolved programs to work efficiently during deployment, it is dependent on large amounts of memory. In Java, the language in which SXGP is coded, every integer or float requires 4 bytes of memory, so storing the result of any image operation on a $640\times480$ image will require approximately a third of a megabyte, assuming Java is  memory efficient\footnote{It isn't.}. While this is not too much of a concern for vision applications which typically look at one image at a time, it may be overwhelming for the Genetic Programming training process, in which all the images (and associated caches) are typically held in memory at the same time.

Accordingly, the lower graph in Figure \ref{fig:caching-performance} shows the memory requirements of each caching technique -- the ``full'' caching technique requires up to 9Mb per image, which could charitably be described as a limitation on the number of images that could be used in training\footnote{The images in this case were $320\times211$ in size. Uncharitable descriptions of this level of memory usage are left to the reader's imagination.}. 
 
\begin{figure}
\begin{centering}
\includegraphics[width=0.8\textwidth]{images/caching-performance}
\caption[Image Level Caching]{Comparison between different levels of image caching in terms of performance and memory usage.}
\label{fig:caching-performance}
\end{centering}
\end{figure}

The problem is exacerbated by the bluntness of the caching mechanism, which is intended for operations on the whole image. The training data, by contrast, may only comprise a small number of chosen pixels from each image. Nonetheless, the cache is calculated for the whole image, which is wasteful. 

The author's solution is: another level of caching! The idea is to pre-compute the outputs of the feature set for every pixel in the segmentation training set, and store them in a separate dataset structure, the same used to represent the public datasets used throughout Chapter \ref{ch:gpcomparison}. Not only does this permit solutions to both public datasets and imaging problems to be evolved by exactly the same system, the dataset structure requires significantly less memory per image, as only the pixels part of the training set are included.

To implement this approach the terminal nodes in SXGP trees are able to execute in either of two modes: the first using the pre-computed values from the dataset, the second calculating the feature directly from the image as before. This permits the GP system to produce ``live previews'' of the segmenter on test images, while training on a precomputed dataset that doesn't use images at all. 

It must be acknowledged, however, that this strategy is not limitlessly scalable. In the author's current implementation, the dataset resides entirely within memory; some huge datasets would still be too large to accommodate. Experiments involving the selective culling of training data, to ensure speedy and feasible evolution, await the reader in the following chapter.

\subsection{Fitness Caching}
\label{fitness-caching}
The author, whose enthusiasm for caching continued unabated, went on to invent a different form of caching, similar in spirit to that of Roberts \cite{Roberts03caching} but with a lower memory overhead. The approach, termed ``fitness caching'' ensures that some needless evaluations do not take place.

As was discussed in Chapter \ref{ch:gpcomparison}, a feature of the ramped-half-and-half tree builder (see page \pageref{ramped-half-and-half}) is that it generates a number of duplicates. This is because the builder generates a fixed number of trees at every tree depth; since there are fewer small trees than large trees, a number of them will not be unique. A plot of the proportion of duplicates in a randomly generated population of different sizes is shown in Figure \ref{fig:duplication}. We have also seen that any selection technique will bring about a reduction in variability. Despite the vastness of the search space, the paradox is that there is always some degree level of duplication within a GP population.

The author's image caching mechanism ensures individuals can be processed quickly, but there is a further saving to be made. Given that it isn't computationally practical for the tree builder to ensure that every tree is unique, it makes sense to attempt caching on a per-individual level, rather than a per-sub-tree level. This requires much less memory, and means the duplicated individuals do not have to be evaluated at all. Instead of caching the output of the tree on each data point, which is memory intensive and still requires the entire training to be iterated through, the author's technique simply caches the final \emph{fitness value} of the individual, on the basis that two identical individuals must be allocated identical fitness. 

% From duplication.xls, using data from MathsProblem.java, Population size from 1-100, tree depth 8, each value is average from 20 populations of that size.
\begin{figure}
\begin{centering}
\includegraphics[width=0.9\textwidth]{images/duplication}
\caption[Duplication in Random Populations]{The level of duplication in random populations approaches over 20\% when generated by the standard ramped half-and-half population builder in the author's GP system.}
\label{fig:duplication}
\end{centering}
\end{figure}

Each individual's structure is given a unique code, by taking the hash code of its LISP expression\footnote{The bracketed syntax of LISP is well-suited for expressing tree structures. It is acknowledged that hashing functions are not guaranteed to produce unique codes. The author conducted an experiment in which 10,000,000 individuals were hashed. Individuals with identical hash codes were checked to see if their trees were the same. No instances were found in which the hash code was not unique.}. When an individual is evaluated, a record of the fitness for its code is recorded. Subsequent evaluations start by checking the record first; a ``full'' evaluation only proceeds if fitness hasn't already been calculated for that individual.

%\begin{verbatim}
%function evaluate(individual) {
%	hash = hashcode(toLisp(individual))
%	if cache.contains(hash) {
%		return cache.get(hash)
%	} else {
%		fitness = calculateFitness(individual)
%		cache.put(fitness)
%		return fitness
%	}
%}
%\end{verbatim}

% This is the Avoid Evaluations Experiment (#12)
\begin {table}[ht]
\centering 
\begin {tabular*}{0.6\textwidth}{ lrrr }
\toprule
Data Set	& Normal 	& Fitness Caching 	& Improvement\\
		& \emph{seconds}& \emph{seconds}	& \emph{\%} \\ \toprule
BUPA		& 35.35 	& 32.52 			& 8.7 \\ \midrule
Heart		& 28.63 	& 26.66 		& 7.4 \\ \midrule
Glass		& 62.46 	& 61.85 		& 1.0 \\ \bottomrule
Iris		& 22.74 	& 21.83 		& 4.2 \\ \midrule
Pima		& 51.82 	& 49.31 		& 5.1 \\ \midrule
Thyroid	& 102.47	& 94.27 		& 8.7 \\ \midrule
WDBC		& 25.07 	& 21.92 		& 14.4 \\ \midrule
\end {tabular*}
\caption [Fitness Caching]{Comparison of average runtimes of a 250 member popupation over 25 generations with and without fitness caching. Fitness caching can produce a performance increase of up to 14\% on classification datasets.}
\label {table:avoid-evaluations} 
\end {table}

The results of an experiment comparing performances with and without fitness caching are summarised in Table \ref{table:avoid-evaluations}. The results show that fitness caching is able to achieve up to an additional 14.4\% reduction in processing time (6.2\% on average). Although this improvement is modest, it requires significantly less memory than other caching techniques and can therefore be implemented \emph{in addition} to any other caching mechanisms.

%It is straightforward to collect statistics about how many individuals were able to avoid an unnecessary evaluation on any given generation. Interestingly the graph reveals a sharp spike immediately after the first generation in which 40-50\% of individuals are not unique. Since the random search that generates the first population only generates a few individuals that are any good, the subsequent generation is likely to be constructed from a relatively small number of parents, which would explain the number of duplicates. As the learning process continues, the number of non-unique individuals drops to around 20\%. 

\subsection{Deployment Procedure}
\label{deployment}
A further performance enhancement is initiated following the evolutionary process. In common with most Genetic Programming systems, the author's toolkit represents programs as trees. Since Java is a compiled programming language, the Java process cannot execute programs written during runtime, so the tree must be executed by an interpreter which traverses the tree according to the logic of the nodes. Once the Genetic Programming process is completed and a suitable program discovered, it is desirable to dispense with the interpreter, both to remove its computational overhead and to disentangle the program completely from dependence on any Genetic Programming libraries. 

Following any tree optimisation operations enacted upon the tree, the author's toolkit begins the process of deployment by converting the optimised tree to Java source code. Each node implements a \emph{toJava()} function, which translates its functionality into Java source code, and in general each node will produce a single programming statement. A source interpreter runs on the tree and combines the statements together, before adding the headers and footers to make a complete Java program. Any functions that are used more than once within the function are cached inline. The Java compiler is then instantiated to compile the source into Java byte code, which may then be executed by the Java runtime. Finally the compiled class file is loaded back into the Java virtual machine as an instantiated class that can be run on any vision problem. 

\begin{figure}[h!]
\begin{centering}
\includegraphics[width=0.4\textwidth]{images/deployment}
\caption[Deployment Procedure]{The deployment procedure for converting a GP tree into a compiled Java class, which typically runs about 20\% faster.}
\label{fig:deployment}
\end{centering}
\end{figure}

%See byte-code-performance.xls
Although this process is too involved to be run during the GP run, it yields ``pure'' Java programs which run faster than interpreted ones and are reliant only upon the author's imaging libraries. The Java process doesn't need to be restarted, so the program can be used immediately. Experiments (summarised in Table \ref{table:byte-code-performance}) show that, on average, the compiled programs execute between 20--30\% faster than the equivalent interpreted versions.

\begin {table}[ht]
\centering 
\begin {tabular*}{0.6\textwidth}{ lrrr }
\toprule
Data Set	 	& GP Tree 	& Byte Code 	& Improvement\\
				& \emph{ms}& \emph{ms}	& \emph{\%} \\ \toprule
Flags			& 273		& 218 		& 20.0 \\ \midrule
Pipelines	& 175 	& 127 		& 27.2 \\ \midrule
Leaves		& 320 	& 218 		& 31.8 \\ \bottomrule
\end {tabular*}
\caption [Byte Code Performance Boost]{Comparison between the average performance of interpreted GP trees and compiled Java programs, when running on vision datasets. The compiled version yields a performance boost of between 20--31.8\%}
\label {table:byte-code-performance} 
\end {table}

\section{Experimenting with Preprocessing}
Earlier in this chapter several straightforward algorithms intended to achieve consistent colour constancy and better exposure control were described. There were a couple of subjective demonstrations of these algorithms in Figures \ref{fig:greyworld} and \ref{fig:exposure}, but it seems worthwhile to devise a general, objective means of assessing the usefulness of preprocessing algorithms. In this section, we shall present the results from a limited set of experiments that demonstrate some of the effects of the colour constancy algorithms.

We have already seen several of the author's own image datasets, including the straightforward Pasta dataset and the Flags dataset (see page \pageref{flags-dataset}). The Pasta dataset equates to an industrial inspection task, and has relatively consistent illumination. The Flags dataset, by contrast, is primarily a colour recognition task, so each image was captured at different exposures and white balances to ensure robustness. 

In this section, we shall investigate whether the colour constancy algorithms can affect the quality of classifiers evolved by Genetic Programming. Two datasets were generated for each task,  each using the same set of training data points. In the first experiment the images in their original form were used; in the second experiment the images were pre-processed first using the grey-world colour constancy algorithm\footnote{The white patch colour constancy algorithm was not used -- requiring the continual presence of white objects is something of a restriction for a generic vision system builder!}. All other parameters were identical. GP runs were then performed on each dataset. The results are shown in Table \ref{tab:ccresults} and graphically in Figure \ref{fig:ccresults}, which shows typical GP runs by generation.

\begin {table}[ht]
\centering 
\begin {tabular*}{0.5\textwidth}{ lrrr }
\toprule
Data Set		& Unprocessed 	& Preprocessed \\ \toprule
Pasta			& 0.001 			& 0.001 		  \\ \midrule
Flags			& 0.173			& 0.015 		  \\ \midrule
Pipelines	& 0.094 			& 0.145 		  \\ \midrule
Leaves		& 0.030 			& 0.060 		  \\ \bottomrule
\end {tabular*}
\caption [Preprocessing Results]{Measuring the effect of the author's colour constancy implementations on four segmentation datasets. Shown here is the average error for each dataset after 25 runs apiece.}
\label {tab:ccresults} 
\end {table}

Perhaps unsurprisingly, the colour constancy technique has little effect on the Pasta dataset, which features very little variance in illumination, and in any case already achieves a respectably low average error. On the Flags dataset, however, the difference is marked: the error is reduced from a rather high level down to a much lower level (the accuracy was 98.5\%), which is a substantial improvement. Inspection of the images before and after preprocessing reveals why -- much of the inconsistency in the training data has been removed by the grey-world algorithm. Although the pre-processed images do not really represent our own perception of the images, they may render a series of differently exposed images to a much more consistent intermediate.

However, for the Leaves and Pipelines dataset, the preprocessing operation makes the classifier significantly worse. This is perhaps because the types of images in these datasets do not fit the assumptions underlying the grey-world assumption.

\begin{figure}[h!]
\begin{centering}
\includegraphics[width=0.85\textwidth]{images/preprocessing}
\caption[Pre-processing Results]{The outcomes of the evolutionary process, with and without grey-world colour constancy pre-processing. For the Flag dataset the reduction in error is significant. In other datasets the pre-processing either has a neutral or damaging effect.}
\label{fig:ccresults}
\end{centering}
\end{figure}

We have seen that colour constancy algorithms can make a substantial difference to some datasets, sometimes beneficial and sometimes detrimental. Given the significant improvement on the Flags dataset, it is preferable to involve the colour constancy algorithm where suitable, but a decision must be taken whether to run it or not. Running a colour constancy algorithm that doesn't yield any improvement only adds to the computational burden of the vision system, and may even decrease the accuracy. Since this is a generic system, it would be nice to decide whether certain preprocessing operations are useful \emph{prior} to running the GP process and preferably in an automatic manner. Fortunately, it appears the colour constancy algorithms also have an effect on the author's feature selection techniques -- the average feature ``score'' was improved by between 8--20\% for the pre-processed Flags dataset, but it remained unchanged for the Pasta dataset. Similarly it was worsened on each occasion for the Leaf and Pipeline datasets. There would, therefore, appear to be a mechanism for quickly identifying the usefulness of certain preprocessing techniques automatically, using any of the feature selection techniques discussed. All feature filters gave similar results, but Information Gain provided the clearest distinctions in value, shown in Table \ref{table:ccprediction}.

\begin {table}[ht]
\centering 
\begin {tabular*}{0.5\textwidth}{ lrrr }
\toprule
Data Set		& Unprocessed 	& Preprocessed \\ \toprule
Pasta			& 0.471 			& 0.472 		  \\ \midrule
Flags			& 0.249			& 1.525 		  \\ \midrule
Pipelines	& 0.865 			& 0.721 		  \\ \midrule
Leaves		& 0.374 			& 0.340 		  \\ \bottomrule
\end {tabular*}
\caption [Information Gain from Preprocessing]{The average Information Gain by the top 20 features for a given task, with and without colour constancy preprocessing. The difference in error correlates with the observed results, so Information Gain can be used to assess whether preprocessing should be used or not.}
\label {table:ccprediction} 
\end {table}

\section{Applications of Segmentation}
In this chapter we have covered the design of a generic feature detection system, the means by which image datasets may be produced from suitable image features and techniques for ensuring the evolution and execution of the detector can proceed rapidly.

This chapter is concluded with some images showing examples of the applicability of the feature detector. Although numerical results are provided, it is difficult to make empirical comparisons to other work since it is not often possible to access the same datasets. Nonetheless, the idea here is to present how the author's software may be applied to those problems for which a result of publishable quality has already been presented by GP researchers in the past. The objective is to explore the \emph{applicability} of the feature detector to a range of domains; it is left to the reader to assess the quality of the results on a subjective basis. All images below are unseen by the feature detector.

\subsection{Skin Segmentation}
\label{skin-segmentation-results}
Computer vision has a large number of applications within the domain of medical imaging. The overwhelming majority of these images must be examined by an expert radiologist, oncologist or other specialist. The consensus is that it would be of great use if computers could be used to automate the process in some way. Accordingly this field has received a lot of research, including by researchers using GP. Roberts and Claridge \cite{roberts:2003:skin} used GP to develop a segmenter for the purposes of skin segmentation, specifically to segment those areas of skin described by medics as lesions. 

Given a set of 100 images carefully hand-segmented by an expert as training data, they evolved a program that could perform similar segmentations using just eight images as training data. The detector achieved a sensitivity of 88\% and a specificity of 96\%, and was able to run on images approximately $600 \times 400$ in size within 4 seconds. Although the author was unable to acquire the same dataset, it was possible to obtain a similar set of images from a series of online dermatology databases, from which 8 were chosen as representative training samples. The author's generic system evolved a segmenter within 10 minutes that achieved an accuracy of 94.3\% and was able to run in under a second on each image. 

The results of the feature detector are shown below, in each case identifying the boundary of the lesion. The bottom set of images are benign in nature, while the top images are cancerous legions referred to as malignant melanoma.

\begin{center}
\includegraphics[width=0.8\textwidth]{images/skin-lesions}
\end{center}

%\paragraph{Near/Far Segmentation}
%\paragraph{Text Detection}
%Segmentation of near/far objects: stationary: stapler, scissors, mobile hone, hand, card

%\paragraph{Terrain Segmentation}
%Segmentation of different textures - pipeline

\subsection{Terrain Segmentation}
The author's pipeline dataset has already been described in this chapter. It is composed of several hundred time-lapse frames captured from a camera in an unmanned aerial vehicle. The purpose is to identify gas pipelines in the image which require human inspection on a fortnightly basis in order to meet US safety and environmental standards. The author's feature detector was trained to identify several other features in the scene, including vegetation, roads and water. This information may be helpful in identifying the nature of potential problems with pipelines. The author's system evolved a segmenter over the course of 100 generations, which took 18 minutes per run, on average, achieving an average accuracy of 89.9\% on labelled areas of unseen test images. The results on two frames are presented below:

\begin{center}
\includegraphics[width=0.8\textwidth]{images/pipeline-segmented}
\end{center}

Without a means of assessing this result in a comparative manner, we shall instead consider its \emph{utility} for further stages of processing. The detection of pipelines themselves can be performed by taking the output of the segmenter on one class channel. Following skeletonisation, the output is shown below. Since the detection of pipelines in these images is very much related to edge detection, it is worthwhile comparing the effort of a generic benchmark edge detector -- such as that of Canny \cite{Canny:1986}. A comparison between the two is shown below. 

\begin{center}
\includegraphics[width=1.0\textwidth]{images/pipeline-edges}
\end{center}

The first observation is that the evolved detector is more specific with regard to the pipelines than is Canny's detector. Furthermore, the detector can be trained to detect the edge along the \emph{centre} of each pipeline, rather than at its edge, which yields only one response per pipeline, which is more helpful. A Hough transform may be used to identify the straight pipelines.

Of course, Canny's detector is generic and the author's feature detector is evolved with specific training data in mind, so the comparison is mean spirited in some ways. Nonetheless, the point is that domain-specific approaches can be more valuable for certain applications than the equivalent generic algorithm -- provided that domain-specific approaches are straightforward to develop. The detector in this instance was developed in approximately 5 minutes by GP, following approximately one hour producing training data.

\subsection{Object Detection}
Roberts and Howard \cite{EvoVision:Roberts-Howard:1999, roberts:1999:evdIRLI} developed a rotation invariant object detector using GP for the purpose of recognising various vehicles from infra-red satellite images. So far we've seen examples of segmentation, so it is worth investigating whether the author's approach is applicable to more specific objects which themselves may consist of hundreds of pixels. In a brief experiment, a number of images of San Francisco were downloaded, in which over 600 cars were identified. Each car was labelled using the author's software, and a segmenter evolved. Half the images were reserved for testing. Although the detector yielded multiple responses per vehicle, producing a set of blobs, the author's shape processing software (covered in the following chapter) was used to identify the centre of each, the results on a test image are shown below; the sensitivity was 97.6\% and the specificity was 91.8\%.

\begin{center}
\includegraphics[width=0.95\textwidth]{images/vehicle-detection}
\end{center}

\subsection{OCR Segmentation}
One area in which computer vision has already excelled is Optical Character Recognition (OCR), in which letters and words in images are identified automatically to be converted into ASCII text. The segmentation of black text against white paper is reasonably straightforward -- techniques such as adaptive thresholding generally are often sufficiently accurate. In Chapter~\ref{ch:gp-classification} we also saw two other common approaches to automatic thresholding used in mainstream computer vision. Although the author's software is able to segment letters, it is an instance of wheel-reinvention, so is not covered here. We will, however, see an example of handwritten character recognition on the MNIST dataset in the following chapter.

Other OCR tasks, however, are more challenging from a feature detection perspective. Quintana \emph{et al.} \cite{quintana:2002:KBCS} tackled a more interesting problem of extracting musical notation from an image, a problem made more difficult by the overlapping nature of musical notes, staff lines and other notations. Quintana used GP to evolve mathematical morphology operations to extract each. The authors were able to develop a detector for the purpose of classifying note heads to an excellent degree of accuracy, but detecting beams and stave lines was more difficult. It was particularly difficult to evolve a stave line detector with the required level of specificity. 

This author has also tried out this experiment on a series of images. To make the problem more challenging, the images were captured from photographs of printed sheet music using a webcam instead of purely electronic versions. The author's detector was applied to the classification of the same three features, and was able to discover solutions to each all using a single multi-class detector, shown below.

\begin{center}
\includegraphics[width=0.8\textwidth]{images/music-segmentation}
\end{center}

%\paragraph{Colour Segmentation}
%Colour segmentation - flags, pasta

%\paragraph{Object Detection}
%Object detection - vehicles from above would be nice

%\paragraph{}
%Motion detection and tracking
%\paragraph{Shadow Segmentation}
%Shadow segmentation - needs to be quite a strong shadow, from a light.

\subsection{Conclusion}
In the last chapter we saw how the author's feature-detection approach can be employed for the extraction of different features from images. Some are based on colour, others on texture, and others by their context. The author's generic learning system has been applied to develop specific solutions for several tasks where previously GP researchers had developed custom features specific to each problem. Although the image datasets are not available for direct comparison, the author claims that the solutions developed using the generic system are equivalent.

In this thesis, the detection of features is the beginning rather than the end -- in the next chapter we shall look at what to do with the output of the segmenter, and how to construct multi-stage vision \emph{systems}, rather than just vision \emph{components}. 

It has already been stated that numeric results on a particular dataset are not always enough to give a good impression of a segmenter's performance. The author would state that a better measure of the performance is its \emph{utility} -- are the features that it detects sufficiently reliable as to permit further stages of processing? In attempting to use one set of evolved solutions as inputs to another, one soon appreciates whether the former is helping or hindering the overall process! In the next chapter we shall see just what kind of tasks can be attempted by multiple stage evolved vision architectures on a series of more complex datasets.
