Using Evolutionary Algorithm to
find image segmentation
Final project by
Yossef
Kitrossky
Yoad
Lewenberg
yossefki@bgu.ac.il
yoad@bgu.ac.il
Introduction
At this project we tried to find image segmentation using Evolutionary Algorithm. We focused on 128*128 gray scale images and used our algorithm to separate the image in to two segments. Potential solution represented as matrix such that the value of every index at the matrix can be either 1 or 0.
Approach and Method
In order to find segmentation using Evolutionary Algorithm, we must define the follow:
Individual
First generation population
Fitness function
Selection
Recombination
Mutation
Evolution steps
Individual
As mentioned, every individual in the population represented as a binary matrix, so the two segments can easily be distinguished.
First Generation Population
In order to start with population that could evolve to satisfying segmentation
maps, every individual in the first generation contain 
random
circles (with random radius and random center) and 
random
rectangles (with random width, length and center), when
.
Fitness Function
The score of segmentation map determinates according to two criteria:
The variance of the pixels value at every segment.
The values of partial derivative at the boundary points (by the 
and
axes).
Selection
So we can apply the principle of the Natural Selection in our algorithm,
at each generation the top 
individuals join
the next generation as they are. For the last 
the following is
processed:
Until the population is complete:
4 random individual picked and
the best one (by the fitness function) chosen as parent A.
In the same way parent B is
chosen. After both parents are chosen we recombine them to a new individual
that take part in the new generation.
Recombination
After both parents are chosen, we randomly chose a pivot 
(between 0 and
, where 
and 
are 
binary matrixes)
and axis (either 
or
). Their offspring 
compound from the first columns of and the other from
, if the chosen axis is
. If the chosen axis is
, compound from the first rows from and the other from . After the offspring is compound, with
some probability mutation will occur.
Mutation
We mutate individuals in 4 ways:
Add a random circle (random
center and radius) of a random segment (0, 1).
Add a random rectangle (random
center, width and length) of a random segment (0, 1).
Smooth the segmentation map with
Gaussian kernel.
At a random point 
of segment
, find – in a
random orientation (right-left, up-down) – boundary point and extend the 
segment at the
boundary point.
Evolution steps
Instead of creating the first generation and evolving according to the
original image, we let the individuals evolve as follow:
We lower the resolution of the original image (128*128), to 8*8 image,
16*16 image, 32*32 image and 64*64 image.
The first generation population created as 8*8 binary matrix
and evolve 
generations to fit
the 
resized image.
After generations every
individual in the population transform to 16*16 binary matrix.
The updated individuals evolve for 
generations to fit
the 16*16 resized image.
In the same way the individuals evolve for 
generations to fit
32*32 resized image, 
generations to fit
the 64*64 resized image and finally 
generations to fit
the original image.
Running Time
For 
image, population
size
, generation total amount
of
.
Creating the
initial population
.
For every generation;
Ranking
all the population
for every individual;
Pick
parents 
Merge
Mutate
Total running time
- 
. Theoretically the running time
seems effective. But in order to achieve a satisfying result 
should be at least
, so the real running time
.
Results
Demonstration of the evolution steps:
|
|
|
|
|
The original image. We used
population size 400. Total amount of 400 generations. mutation probability
0.3 |
20 generation of evolution
according to 8*8 resized image. |
40 generation of evolution according
to 16*16 resized image. |
|
|
|
|
|
80 generation of evolution
according to 32*32 resized image. |
100 generation of evolution
according to 64*64 resized image. |
160 generation of evolution
according to original image. |
Result on an image with
noise:
|
|
|
|
Original 128*128 image with noise. |
The best solution after 400
generations, with population size 400 .mutation probability 0.3. |
Conclusions
As in real life evolution is a long time
process with respect to the input. (E.g. human evolution is very slow) hence
our algorithm requires an impractical amount of generation and population size
to achieve a satisfying result when dealing with large images.
Although finding image segmentation
is hard problem and we show a polynomial solution, in
order to deal with more complex images a lot of work is still ahead.
Additional Information
References
Flight of the FINCH through the Java
Wilderness;
Michael Orlov and Moshe Sipper.
Perceptual
Organization I - Edge aggregation case study; Ohad Ben-Shahar (Course lecture
notes).
Perceptual Organization IV -
Segmentation; Ohad Ben-Shahar (Course lecture
notes).