Evolving Linear-Logical Edge Detector with Evolutionary Algorithms

 

Final project by

 

Virin Jan

 

 

 


Introduction

 

Edge detection

 

The problem is to find edges in the image, as a first step in the process of scene reconstruction. The edges can be used afterwards for segmentation of the image into objects. The most simple edge detection can be done by using thresholds: pixels with gray level above some threshold are considered to be in one group and all the other - in the second. The edges should appear when you cross the border between the groups. This technique works for very simple domains, but by no means can serve as an edge detector in the real world.

            More sophisticated approach uses linear operators to find edges. For example if you apply a gradient operator on the image and

only then apply the threshold technique, the result that you get is much better. However, not only gradient operator can be used

for edge detection. There are a lot of linear operators (for example Laplacian) which can be used for this purpose. However, most of them

have a common false-positive problem – a lot of noise is recognized as signal in the resulting image.

            Logic-Linear[3] detectors come to solve this problem. They combine the computational strength of the linear operators with the logical strength of Boolean logics. A typical LL operator consists of several linear operators which are applied on the image, each one in its turn. Afterwards a Boolean operator is applied on the images, hopefully removing all the false-positives pixels. The LL operator can be seen as a sequence of linear operators which extract different properties of pixels from the image. LL operator defines that a true edge is found only when the conjunction of these properties holds.

 

 

            Evolutionary Algorithms

 

Evolutionary computing gets its inspiration from the nature, or more accurately from Darwin[2]. The model of the “strongest survives” is adopted to the computational world, where it creates a whole stream of algorithms called “Evolutionary Algorithms”.

To represent a problem as a domain for evolutionary algorithm one has to define the Genotype and the Objective(or Fitness) function. Genotype represents the individuals (encoded gene information) of the population and Objective function tells how each individual should be evaluated. A typical evolutionary algorithm consists of Selection, Crossover and Mutation stages. Selection is the process of selecting the individuals for breeding. In the nature this process is carried out naturally, i.e. mails and females find each other by secondary sexual properties. In our case, the best (found using the objective function) individuals get to be selected. In the Crossover stage two parents (from the selected pairs) give birth to a new individual, passing it parts of their genes. Mutation is responsible for the variety of the population, changing randomly genes in some individuals. Those three stages combined all together create a Generation which during the execution of an evolutionary algorithm is repeated many times in a loop.

Evolution works very slowly in nature and it is not different in the computational world. When the domain of the problem is not trivial, only after a hundred or even a thousand generations the resulting individuals are getting closer to the optimal solution. Typically an evolutionary algorithm is stopped by the user because of a time limit and the best individual is selected as the output.

                       

 

Approach and Method

 

            LL detector

                       

                        I used a simple dual LL operator, which consists of two linear filters F1 and F2 (3x3 each). The operator is defined to be:

 

Ioutput [i,j] = (Iinput*F1)[i,j] ♠ (Iinput*F2)[i,j]

 

where ♠ is the following Boolean-algebraic operator:                   

This operator can be seen as an amplifier of the linear operators. It gives a high positive value only when both linear operators give positive values and a low negative when both results are negative. Each one of the linear operators is responsible for some linear property in the image, and their conjunction should define the ultimate edge detector.

 

            Evolving the LL detector

           

In order to evolve the desired LL operator using the evolutionary paradigm, I had, as stated above, to define the Genotype and the Objective function. I decided to use the most simple and natural representation of a chromosome( the Genotype) - a vector of integers. Its length was set to 18 numbers, 9 for each linear filter. The first 9 integers served as the first filter (3x3) and the following 9 integers – for the second. The range of the integers was set to [-7, 7]. The objective function had to reflect how good the individual is, or in optimization context – how optimal is the individual. For this purpose I created an image training set from The Berkley Segmentation Dataset and Benchmark[1] site. I took four images as originals and their edge detection results (Gradient algorithm) as benchmarks. To evaluate a specific individual, I applied the corresponding LL detector on each image and computed the difference between the result and the benchmark (averaged on four images). This number served as a negative grade of the individual – the less it was, the better the individual was considered to be.

 

            Genetic and Evolutionary Algorithm Toolbox for Matlab

                       

            I decided to use Matlab as the platform for my project. When your project involves image manipulation, Matlab is one of the best choices you can make. Matrix and Vector manipulations are simple and natural in Matlab, what lets you be devoted to the research itself and not to the implementation of basic operators (like convolution). However, genetic algorithms are not a part of Matlab standard library, so I had to find some good tool box, which will excuse me from writing the implementation of the basic evolutionary engine.

            I found the GEATbx product site on the internet and contacted them. They've sent me the source code of the tool box for evaluation. After reading a brief introduction, I could already get started.

 

Results

           

            Using the GEATbx, I conducted an experiment which lasted for ~6 hours and got the following individual as the best one:

X = [2, -3, -3, -1, -7, 4, -4, 6, 6, 7, 4, 6, -3, 7, 4, -5, 1, 0]

 

This chromosome is decoded into the following filters:

 2,-1,-4              7,-3,-5

-3,-7, 6              4, 7, 1

            -3, 4, 6              6, 4, 0

 

Using the combination of both filters as a LL operator, I've got the following edge detection results. They are from the right. The original image and some other segmentation results (by Yonatan Shichel) are presented for comparison (they are from the left). Note: Original images were not included in the training set, so those results represent generalization of the method.

 

 

   The original image                        Segmentation by GP (Yonatan Shichel)                           LL Evolutionary approach

 

 

 

 

 

 

 

Conclusions

           

            In this project I tried to see whether evolutionary methods are sophisticated enough to create a good Logic-Linear edge detector. The above results show that it can be done indeed. The resulting LL detector seems to be more elegant than the one evolved using GP by Yonatan Shichel.

                        For example in the first image we can see that the GP segmentation approach have not cought all the small details of the face, while my

            algorithm did it well. Although one can see that in that image there are rough segments which were not detected by my approach, while were
            found by Yonatan's.

 

                        The results on the second image are more or less identical in both approaches.

 

The results on the third image show the strength of my approach in finding interesting facts in the image. There is no chance that someone will understand from Yonatan's result that the building is standing on a lake, while it is more apparent in mine. You can see that the details are more accurate when you use the LL detector.

           

           

            Future Work

·         Use intelligent and adaptive threshold technique instead of simple constant threshold

·         Define objective function based on pattern matching (find the pattern in the image) instead of simple differential technique

·         Bigger population, several subpopulations, a longer running time (use some dedicated to the task computer)

·         Include more images in the training set (of the objective function)

·         Use color images which contain more information

·         Define more powerful population, which consist of chromosomes with a lot more variables (increase the dimensionality of the domain)

 

Additional Information

           

·         Full project report

·         Oral presentation slides

·         Implementation (code in Matlab)

 

 

References

  1. The Berkley Segmentation Dataset and Benchmark: http://www.cs.berkeley.edu/projects/vision/grouping/segbench/
  2. Darwin, Charles: On the origin of species by means of natural selection. London, John Murray, 1859
  3. Logical/Linear operations for image curves, by Iverson and Zucker, 1995.
  4. GEATbx.com - Genetic and Evolutionary Algorithm Toolbox for Matlab
     http://www.geatbx.com/
  5. Tomassini M.: Evolutionary Algorithms. Swiss Scientific Computing Center, Manno