\chapter{GP for Low-Level Vision Tasks (DRAFT)}
\label{ch:low-level}

This Chapter covers some of the lower-level vision tasks necessary to produce a working vision system. These tasks are primarily concerned with the detection of interesting objects within a particular image. The methods used to perform such detections will be covered; various techniques for making the process more accurate or more efficient are discussed later as these techniques are applied to standard image processing data sets.

The initial steps of image pre-processing appear quite clear. There is certainly a desire to reduce noise as much as possible, or to find the edges and corners within a picture. What to do with a processed image thereafter seems to be less obvious. An advantage of GP is that it places no requirement upon the quality of the input image to begin with, so in some regards, these procedures are unnecessary for our vision system if it is learned by GP.

\section{The Tasks}

\subsection{Segmentation}
Segmentation is a technique used to divide up regions in an image according to their apparent material. If an object consists of one material, and the other objects in the scene are made up from another, then segmentation can be used to distinguish the two.

Segmentation is usually used to classify each pixel in the image. Pixels of a certain class may form contiguous regions, or segments, which can help to make sense of the objects in a scene.

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

%TODO: Highlight A and B on the diagram with arrows to make them easy to see.
%\begin{figure}
%\begin{centering}
%\includegraphics[width=0.5\textwidth]{images/grey_square_illusion.eps}
%\par\end{centering}
%\caption{The Grey Square Illusion: Squares A and B have the same colour}
%\label{fig:illusion}
%\end{figure}

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

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

\paragraph{Land's Retinex Theory}
... information to appear here.

\paragraph{Gamut Constraint Methods}
... information to appear here.

\paragraph{White Patch}
... information to appear here.

\paragraph{Gray World Assumption}
... information to appear here.

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

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

\paragraph{Drawbacks}
As a classic bottom-up approach, segmentation is concerned with the classification of individual pixels into groups which may belong to a common object type. Segments with a particular class may be marked as being intereseting objects which demand closer inspection. Segmentation is applicable to a wide range of different problems where objects of a distinct material need to be extracted from the background. 

However, segmentation does suffer from certain drawbacks. If objects do not have clearly defined boundaries, the output of a segmentation system may be unreliable or unhelpful. It can also only relate information based on material, so the objects in a scene ought to be all of the same class. However, for certain problems this doesn't work - if one is trying to evolve a face detector, a segmenter may well be able to find the regions of skin. The segmenter won't, however, be able to distinguish a person's hands from his or her face. It is therefore necessary to consider detectors which consider relationships between groups of pixels more carefully.

\subsection{Window Detection}



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

\subsection{Colour Features}
Information on features which relate purely to the colour of a given point. Colour spaces etc.

\subsection{Pixel Features}

\subsubsection{Requirements}
A reasonable person may well suggest that all the pixel data should be sent to the learning system. After all this eliminates the need for any form of feature selection, and causes no loss of data, so in theory the GP system would be completely free to produce solutions tailored exactly to the input data. The problem with this approach is that pixel data in an image only really makes any kind of semantic sense when viewed collectively; the data is in such high dimensions that a single point offers almost no information about the content of the image. It is quite possible that given sufficient time, a learning system could discover useful ways of combining pixel data, as the processing would be interpreted and without any form of optimisation. If the processing overhead is too high, then the learning process will be seriously affected.

Implied in the statements above are two requirements for a good pixel-based feature. he first is that it should in some way reduce the dimensionality of data in the image, and the second is that processing it should be as fast and optimised as possible. There do exist a number of established techniques in the computer vision community for performing such optimisations. In recent years the usage of an \emph{integral image}\cite{Crow:1984:STT} was popularised by the work of Viola and Jones. An integral image, as its name suggests, is a summed table produced from an original image in which each point at (x,y) consists of the sum of points' intensities from the (0,0) origin. Using such a table it is possible to calculate arbitrary image sums using only addition and subtraction operations.

\subsubsection{Features for Texture}

\subsubsection{Haar Features and other Parameterised Features}

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

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

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

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

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

\subsection{Existing Approaches}

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

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

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

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

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

\subsection{Feature Construction by Genetic Programming}
Genetic Programming is a flexible learning technique. Given a set of raw data, it is capable of evolving a reasonable solution to a problem, given time and the appropriate tools (those tools will be discussed later). In order to generate a high-level solution to a particular problem, the raw, generic data requires processing in some way to make it suitably useful. 

The kind of features discussed earlier in this chapter are mostly parameter based, and therefore represent families of potential features. Some of these features will be useful for a particular task, and other will not. While Genetic Programming may be able to tune these parameters and find a suitable overall solution in a single pass, other approaches have been suggested which may be more efficient; some are introduced below.

\paragraph{Two Stage Evolution}
As the granularity of a GP system usually only extends as far as individual programs, in default GP implementations it is not easy to retain those parts of a tree which work very well. The system may evolve an excellent feature but if used incorrectly, the feature (and the rest of the program) may not be included in further generations (it should also be remembered that GP does not necessarily guarantee that even the best individual will be able to reproduce). In such a situation, the bluntness of the fitness measure causes the system to loose otherwise useful information. For this reason it may be useful to separate the evolution into smaller stages so the fitness function is more precise and less information is lost. 

A natural approach is to split the evolution into two stages. In the first stage, just the feature set is evolved. As complex objects, such as a human face, generally cannot be completely described by one feature, in the second stage the GP system learns how to combine a set of pre-evolved features in order to deliver an optimised result.

The evolution of the feature set is in essence a parameter optimisation problem, for which techniques such as Genetic Algorithms have been previously employed. As Genetic Programmins is essentially an extension of Genetic Algorithms, a GP approach may also be taken.

\paragraph{Coevolution}
A second approach also splits the evolution into two parts, but aims to learn them in parallel rather than sequentially.

\section{Making GP More Efficient}
In this section, various techniques for improving the general efficiency of Genetic Programming are explored. Desirable techniques are those which have some positive impact either on the speed of evolution or on the quality of the results produced. 

\subsection{Automatic Classifier Selection using Minimum Standard Deviation / LDA}

\subsection{Automatic Classifier Selection using Range Typing}

\subsection{ERC Optimisation}

\subsection{Training Data}
Genetic Programming, in general, works using a supervised learning paradigm. That is to say that the fitness of an individual is measured according to its performance against known training samples. The collection of such training data will be discussed later in Chapter \ref{ch:vision-system}, but here we discuss here the ways in which GP can be adapted to learn as much from the training data as possible.

It is widely recognised in pattern recognition that training data is likely to contain some level of bias. It may be that some parts of the problem are represented very well by a particular set of training data, while other parts may may be represented by fewer samples. Some training data may be significantly easier to solve than others. 

These situations present two problems. Firstly they may introduce local minima in the solution landscape, into which learning systems may easily become stuck. Secondly the bias of training data sample may not reflect the true bias of data unseen environments, which will reduce the predictive performance of the learned system.

\subsubsection{Ensemble Methods}
The general purpose of ensemble methods, which are widely used in pattern recognition, is to generate a series of different estimators through manipulation of the training data which improve the overall performance. Two exist: bagging and boosting. These two methods have been widely used to create more accurate classifiers. As meta algorithms they can be used to improve the accuracy of any set of weak classifiers. As such we'll not discuss them further here.

\subsubsection{P Learning}

\subsubsection{Training Data Weighting}
Genetic Programming may be used to generate the weak classifiers used by the ensemble methods, but we do want to ensure that the learning system is as efficient as possible in the first place. This reduces the number of weak classifiers required to reach a level of accuracy, and speeds up the learning process itself, which may be hampered by a boosting procedure.

GP is susceptible to local minima because it is a lot easier to break a working individual than to make it that much better that it can continue to make incremental improvements. If the training data can be weighted such that more difficult samples attract greater rewards, then the GP system may be able to break out of local minima more easily. The downside is that this may make the learning process less stable.

The difficulty of a particular item of data may be approximated according to how often it is wrongly classified. The benefit of this approach is that it is domain independent, and can be added into any learning system in which Genetic Programming is involved. Although it appears to be a logical approach, it may introduce instability into the learning process. A number of experiments were conducted to investigate its effect empirically.

The experiments were conducted on a widely used machine vision data set: the CBCL face database (version 1), which consists of thousands of face and non-face images, divided into training and test data sets. Training set comprises 2,429 faces and 4,548 non-faces, the test set: 472 faces and 23,573 non-faces.

``Regular'' Genetic Programming without any training data weighting, and the weighted version were both evolved over the course of 50 generations. The process was repeated 10 times each in order to gather an average measure of performance. The same random seeds were used for each. 

\paragraph{Fitness Function}
Choosing a suitable fitness function is a key problem in Genetic Programming. In a face detection task the problem poses a dilemma - whether to reward highly sensitive classifiers which detect every face, or to reward highly specific classifiers which produce very few false positives. The CBCL data set is difficult to please in some ways, as the training and test set have very different ratios of face and non-face. If each item of training data is given equal weight, then the classifier could evolve a solution with accuracy exceeding 98\% simply by returning false for everything. For the purposes of this experiment we gave both types equal weight - that is to say that sensitivity and specificity could each account for up to half of the individual's score.

\paragraph{Results}
The following results were found after investigating training data weighting and ERC optimisation. \footnote{training-data-weighting-results2.ods}.

In general it was found that ERC optimisation and training data weighting had little overall impact on the results for the training data. Interestingly, both approaches appeared to improve the score on the unseen data when measured according to the same metric.