Edge Detection by using Genetic Algorithms

Abstract

In this post I will present an algorithm for searching edges in images by using genetic approach.

Algorithm

The image is preprocessed before its usage, firstly Gaussian blur is used to remove small artifacts that could pollute the result. I could be also done by using image downsizing and upsizing as I presented in the post about breaking captcha. Secondly the image is converted to black and white version to simplify the implementation.

Original image:

input image used in edge detection based on genetic algorithm

Edges found by using a genetic algorithm (100 generations):

output image produced by genetic algorithm applied to search edges in the image

In presented version each children has only one parent, so gene change is provided only by mutation. Each specimen has two genes: X and Y that describes a location on the image. If a specimen has a good set of genes (they point to a location near the edge), then he's healthy and strong so he can breed, but if his genes are weak, then he's weak too and soon he dies. The edge is defined by a fitness function as a point that has neighbor points with different color.

Strong species breed so after couple of generations theirs children will cover the whole edge. The final result is a set of genes (each is a point on the image) in the last generation.

The implementation was done in Java, the source code can be cloned from GitHub (edge_detection directory).

Results

The results take a lot of time to be computed, but they are really good. After some point, adding new generations don't improve the result, maybe this could be solved by improving a part responsible for gene mutation. It's visible on below diagram:

the results of genetic algorithm used in searching for edges in each iteration (generation)

The diagram was created by using a gnuplot script that is stored in tools subdirectory. Its body contains info, how to use it.

Better results could be obtained with more sophisticated fitness function and/or by switching to a greyscale image.

5 comments:

  1. Now I'm waiting on an article about the same, but realized with AI ;) It would be great to compare those two approaches in such task.

    ReplyDelete
    Replies
    1. It's personal. There's a lot of (pointless) hype around AI and I don't like it, I don't like when people thread AI as silver bullet.

      Delete
    2. Sure thing, religion is a serious business ;)

      Delete