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 (GeneticEdgeDetection directory). To use this project, JRE needs to be installed and assumed that you have JRE installed and java.exe should be added to the PATH enviroment.

Usage: open project directory in command line, go to the dist directory and type:

java -cp EdgeDetector.jar edgedector.Main ../sample.jpg

You can verify and observe the program with different input images, just change the last argument.

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.

26 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
  2. Can i get the source code of above mentioned topic to make further modifications?

    ReplyDelete
    Replies
    1. Sure, it's on GitHub:
      https://github.com/RobertGawron/snippets/tree/master/edge_detection
      You can also download all source code files as a single zip file (when you will open it, the project is in edge_detection directory):
      https://github.com/RobertGawron/snippets/archive/master.zip

      Delete
  3. Respected, the source code of above topic is not working that provided by you.

    ReplyDelete
    Replies
    1. Could you tell me what was the problem? It doesn't compile, doesn't run, or produce incorrect results? Is the java part doesn't work or the R script?

      I checked today the project by myself, because I made it about two years ago and I don't remember it fully, there were some errors with missing classpath, but after I've fixed them it worked as expected and produced exactly the same output as is presented in the article (I mean the black and white image).

      Anyway I have made some minor changes and committed them, so you can download the code again, I have also enriched in the post the info, how to run the code.

      I hope, that it will work for you now,if not, please let me tell in details, what doesn't work correctly from your point of view.

      Delete
  4. I have run the provided code using NetBeans IDE 8.0.1 . It gets compiled but not generating the output( black and white image).

    ReplyDelete
    Replies
    1. Yes, because to run this program, you have to pass (as an argument in command line) the path + filename of the input image. I could hardcode this in the build configuration use the sample image), but I'm not sure if this would be good.

      To run the compiled project you have to:
      >Usage: open project directory in command line, go to the dist directory and type:
      >java -cp EdgeDetector.jar edgedector.Main ../sample.jpg

      I have already added this information to the post, did you try it this way?

      Delete
  5. Kindly, provide the full path to compile and run the program.

    ReplyDelete
  6. What happened? Kindly, give details to run your code using NetBeans 8.0.2 IDE.

    ReplyDelete
    Replies
    1. Please copy & paste here console output from your NetBenas when you try to compile the program.It's hard to say anything for me without it.

      Delete
    2. After compiling the code in NetBeans IDE the output is -
      usage: java -cp EdgeDetector.jar edgedector.Main [path and filename of the input image]

      Kindly, give me details to run your code using NetBeans 8.0.2 IDE.

      Delete
    3. OK, thanks. What is in the "dist" directory in the project? Is there EdgeDetector.jar file?

      Delete
    4. That's good, please open this directory in cmd (command line) and type:
      java -cp EdgeDetector.jar edgedector.Main ../sample.jpg
      It should do the work.

      Delete
    5. If it doesn't work, please tell me what was printed on the cmd.

      Delete
    6. The output is-
      run:
      usage: java -cp EdgeDetector.jar edgedector.Main [path and filename of the input image]
      BUILD SUCCESSFUL (total time: 3 seconds)

      But, not getting the output image.

      Delete
    7. >BUILD SUCCESSFUL (total time: 3 seconds)
      You pressed "build" button on Netbeans, in above comment I was referring to run the program outside of the Netbeans, from command line, like other console applications.

      That's how to open command line on Windows:
      http://windows.microsoft.com/en-us/windows-vista/open-a-command-prompt-window
      That's how to change the directory (you want to be in the "dist" directory of the project):
      Then:
      java -cp EdgeDetector.jar edgedector.Main ../sample.jpg

      Delete
    8. >That's how to change the directory (you want to be in the "dist" directory of the project):
      Missing link:
      http://coweb.cc.gatech.edu/ice-gt/339

      Delete
    9. I have added a plugin to my NetBean IDE to pass arguments to a file.
      I followed your path..........succeed.

      Thanks a lot.

      Delete
    10. Can you help me one more time?
      Kindly, send me the complete theory of the above implemented concept in doc or pdf format on- dhanraj.yerate@gmail.com
      I shall try the same concept with different method.

      Delete
    11. I don't have any theoretical materials of this concept (nothing more that presented on the blog), I made this project based on my combined knowledge of genetic algorithms and image processing, so unfortunately I can't send you any materials.

      Not used here but methods for the same purpose are Sobel operator and Kirsch operator, maybe you will find this useful in your research.

      Delete