The basic idea for this lab was to use the genetic
algorithm provided us, to solve a problem. I tried to breed an edge
finding matrix. The general idea is that one can convolve a matrix with
an image to achieve various effects. One of these is edge detection.
Representation
I chose to represent my transformation as a 5x5 matrix of values in the range [-7,7]. Each number could then be represented by 4 bits in my chromosome. For example
|
-> |
|
Fitness functions
For my fitness functions, I applied the matrix for
each individual to a sample image. I then did a square sum difference
on the result and my target image. I had two normalize the results of
the SSD, to keep everything in a reasonable range. I then divided by
the total number of pixels to get a per pixel error. Since an SSD will
return smaller values for a better match, I then took the reciprocal to
be the actual match value.
I tried doing this with a couple of different edge map function;
however, none of my results were inspiring or useful.
Parameters
I ran the GA with a population size of 50, a
chromosome length of 100, and a generation limit of 200. Sufficed to
say that it takes a long time to run.
Results
There are two distinct categories of results. Those produced with xv's edge map and those produced with XnView's edge map. While neither set of results is particularly good, the two edge maps do look substantially different. You will probably notice that the result images are slightly smaller than the start image. Rather than try and deal with the cases where the matrix is not fully on the image, I decided to ignore them. This resulted in a loss of 2 pixels from each side.
Start Image |
Target Image |
Results of XV edge matching | ||
Found in generation 126  |
Found in generation 179  |
Found in generation 44  |
Found in generation 197  |
Found in generation 171  |
Found in generation 68  |
Found in generation 194  |
Found in generation 174  |
Found in generation 199  |
Start Image |
Target Image |
Results of XnView edge matching | ||
Found in generation 175  |
Found in generation 16  |
Found in generation 79  |
Found in generation 184  |
Found in generation 114  |
Found in generation 13  |
Found in generation 178  |
Found in generation 197  |
Found in generation 191  |
Analysis
My first attempt at this project used the entire image for the data GA, rather than just the small section you see above. The problem with this is that much of the image is not edge, and as such not enough focus was placed on the actual edge detection, and more emphasis was placed on getting the background to be the correct color.After focusing the image slightly, I still have been unable to achieve good results. I think that this is because successful edge maps depend on most of the matrix. I was hoping that each cell in the matrix would be able to act independantly allowing the problem to have clean building blocks; however, I am no longer convinced that this is the case. It seems likely that the entire filter has to be somewhat carefully designed to achieve any specific effects. Except for a general blur, which seems to happen quite freely.
It looks like (despite my efforts to the contrary) the GA is still focusing in on the background and mapping to that rather than the edges, which are the true area's of focus. This phenomenon probably stems from the fact that general intensity control is easier to mix and match then edge detection. I do not think that a GA would necessarily fail to learn develop an edge detection; however, an extreme amount of care would have to be taken to select the training set.
Worth note, is that the XnView data set did not blur the image so much as reduce the contrast, whereas the XV set heavily blurred the image. All in all, I would say the the GA was not successful. While I do not think that it would be impossible to make a GA which produces an edge detection system. I think that a drastically different approach then the one I have chosen would be necessary.
I did a little bit of work trying to seed the initial population with good matrices, unfortunately these were quickly destroyed via crossover, and never really show up in later generations. The resultant best fit was always one of the seeded matrices.
Last modified 2003-10-07 22:15 EST