Segmentation via Genetic Programming
Final project by
Yonatan Shichel
Introduction
In this project, Genetic Programming (GP) will be used to create segment maps of given images.
The result will be tested and compared to existing segmentation methods.
Approach and Method
Segmentation
Segmentation is a key problem in computational vision.
Splitting an image into segments can be an extremely hard problem, as some
'real-world' properties are inevitably lost when transferred into 2D canvas.
To achieve segmenration via GP, I will try to evolve a deciding function:
given a grayscale image, the evolved function will return a booleam map, in
which each cell indicates whether the corresponding image pixel is a
segmentation boundary point or not.
Genetic Programming
Genetic Programming (GP) is a bio-inspired Artificial Intelligence (AI)
method, using Darwin's evolutionary principles; a population of individuals
is being processed by the computer. Each individual holds a candidate
segmentation function of its own. We can assign a fitness measure to each
individual, according to how good was the segmentations that the its function
produces. Individuals with high fitness measures will be chosen to reproduce,
creating offspring generation in which each individual has some attributes of
its parents.
The function held by each individual is a LISP-like program, which can be
represented as a tree. Tree nodes and tree leafs contain image and matrix
related functions, such as matrix multiplication, convolution operator and
much more. Some genetic operators, such as crossover and mutation, are
defined, so two chosen individuals can produce offspring individuals that
contain some of their attributes.
Segmentation via GP
I have used Berkley's segmentation dataset (see references
section), a public library of 300 images that have been segmented by 30 human
subjects. The purpose of this library is to provide a common basis to
segmentation related researches, as well as being a benchmark for
segmentation algorithms.
Each individual was assigned with a fitness value, reflecting how good was
the segmentation maps produced by the individual's segmentation function. I
have used a modified version of the commonly-used accuracy function
for fitness; given the output of the segmentation function and a human-made
segmentation map for the same image, the accuracy value equals to the
intersection of the two matrices, divided by the union of the two matrices.
The individuals' segmentation produces a 'soft segmentation map' in which
each pixel hold a real value instead of a boolean one. I have used a modified
version of the threshold function used in Berkley's benchmark: the threshold
space was divided into 30-40 points and accuracy was calculated according to
each threshold value. Best values were kept and assigned as the
individual's fitness value.
To run the GP process, I have used Sean Luke's ECJ 13, a Java based
evolutionary computation and genetic programming research system. This
system provides the infrastructure when applying GP on a given problem.
Results
After running several GP sessions, I have extracted the best evolved function
using some test-set images. The code of the function is:
(- (- (conv (* (conv image gradx) (conv image
gradx)) (- (- (kernel 5.381114 -8.362269 8.888325 1.1866289 -6.4069843 -8.251046 -9.389916 6.183886 -7.817788)
grady) (- (kernel -2.334486 -4.6182337 -9.115009 8.010966 -3.0507333 3.22619 2.068446 -2.932576 -6.243905)
0.0))) (conv (* (conv image gradx) (conv
image gradx)) (- (- (kernel 2.4412537 -8.362269 8.888325 1.1866289 -6.4069843 -8.251046 -9.389916 6.183886 -7.817788)
grady) (- (kernel 9.936699 -4.6182337 -9.115009 8.010966 -3.0507333 3.22619 2.068446 -2.932576 -6.243905)
0.0)))) (- (- (- (conv image grady) (* 1.0
9.336973)) (% (* 1.0 9.336973) 9.336973))
(% (% (* -3.9138038 0.0) (* 0.0 0.0)) (%
(* 1.0 9.336973) (* 1.0 9.336973)))))
Here are some results of the algorithm, along with their accuracy (fitness)
values, compared to the accuracy values produced by 'standard' Gradient
Magnitude algorithm:
Accuracy = 0.307 (GM accuracy = 0.280)
Accuracy = 0.262 (GM accuracy = 0.245)
Accuracy = 0.172 (GM accuracy = 0.193)
Accuracy = 0.126 (GM accuracy = 0.119)
Conclusions
In this work I have tried to use Genetic Programming to evolve segmentation
functions. Results show that it is possible to evolve segmentation functions
using GP, and that some good results can be achieved: in most cases, the
best evolved function 'beats' the standard gradient-magnitude algorithm. Yet,
gradient magnitude is not the best segmentation algorithm available, so we
cannot rely on it as a benchmark.
Future Work:
- Use more CPU and RAM resources, hopefully in order to include all the
train set within the fitness calculation function.
- Add some useful building blocks to the terminal set: more image-specific
kernels (like Gaussian smoothing kernel for noise reduction etc.)
- Use ADFs (Auto Defined Functions) [8], which are subroutines that
separately evolved and may be used and reused by the evolved individuals.
- Evolve the threshold function instead of using the same one for all
images. The threshold function may be integrated into the genome or evolved
by co-evolution [3], in which species are being evolved separately and
evaluated together.
- Create an evolving 'kernel library', which will be evolved separately and
may be used by all evolved individuals.
- Include more inputs, like texture maps or other edge detector outputs.
- Use color images, which contain much more information.
Additional Information
References
- The Berkley Segmentation Dataset and Benchmark:
http://www.cs.berkeley.edu/projects/vision/grouping/segbench/
- Koza, J. R.: Genetic Programming: On the programming of computers by
natural selection. MIT press, Cambridge, Mass. (1992)
- Tomassini M.: Evolutionary Algorithms. Swiss Scientific Computing Center,
Manno.
- Darwin, Charles: On the origin of species by means of natural selection.
London, John Murray, 1859
- Montana, D.J.: Strongly typed genetic programming. Evolutionary
Computation 3 (1995) 199-230
- Langdon, W.B.: Size fair and homologous tree genetic programming
crossovers. Genetic Programming and Evolvable Machines 1 (2000) 95-119.
- Luke S.: ECJ 13 - a Java based Evolutionary Computation and Genetic
Programming research system:
http://cs.gmu.edu/~eclab/projects/ecj/
- Koza, J. R.: Genetic Programming II: Automatic Discovery of Reusable
Programs. MIT press, Cambridge, Mass. (1994)
|