Course Home
Administration
Syllabus
References
Lecture Notes
Readings
Assignments
Projects
Resources


Comments? Idea?























































































































































































































































































































































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

  1. The Berkley Segmentation Dataset and Benchmark: http://www.cs.berkeley.edu/projects/vision/grouping/segbench/
  2. Koza, J. R.: Genetic Programming: On the programming of computers by natural selection. MIT press, Cambridge, Mass. (1992)
  3. Tomassini M.: Evolutionary Algorithms. Swiss Scientific Computing Center, Manno.
  4. Darwin, Charles: On the origin of species by means of natural selection. London, John Murray, 1859
  5. Montana, D.J.: Strongly typed genetic programming. Evolutionary Computation 3 (1995) 199-230
  6. Langdon, W.B.: Size fair and homologous tree genetic programming crossovers. Genetic Programming and Evolvable Machines 1 (2000) 95-119.
  7. Luke S.: ECJ 13 - a Java based Evolutionary Computation and Genetic Programming research system: http://cs.gmu.edu/~eclab/projects/ecj/
  8. Koza, J. R.: Genetic Programming II: Automatic Discovery of Reusable Programs. MIT press, Cambridge, Mass. (1994)