Hi everyone, I'm currently working on a Genetic algorithm that needs to take a black and white image as input. Then the GA covers the image with a n-sided polygon. The problem is that it is not really covering the input image very well. Can someone please check my steps and tell me if I'm thinking like a retard. 1)Convert input image to a 2D array, 0 where white, 1 where black. img[width][height] 2)Initialize the population, with its chromosomes and genes. 3)calculate each chromosome's fitness by converting chromosome to 2D array and comparing it to the real image. 3)Selecting crossover candidates with tournament selection and crossing-over. 4)Mutate - I'm a bit stuck with the mutation part - how do I find a good mutation step-size? 5)back to step 3. Any help would be appreciated. Thanks.

That whole scheme makes no sense to me. Why would you use a GA to do something like that? You're trying to do a gradient descent in a space that has the dimensionality of your input image.

Concur. That seems odd.

Quote:

Original post by Steadtler That whole scheme makes no sense to me. Why would you use a GA to do something like that? You're trying to do a gradient descent in a space that has the dimensionality of your input image.

Really you only have 2n decision variables, no?

Questions:
1 - What is your cost function? Number of misclassified pixels?
2 - Is there additional structure; e.g, do all the white/black pixels of your image occur in a single connected component?
3 - Is it terribly important that your polygon have exactly N sides?

It seems to me that viewing this as a contour- (or outline-) tracing problem would be productive...

Quote:

Original post by Emergent Quote: Original post by Steadtler That whole scheme makes no sense to me. Why would you use a GA to do something like that? You're trying to do a gradient descent in a space that has the dimensionality of your input image. Really you only have 2n decision variables, no? Questions: 1 - What is your cost function? Number of misclassified pixels? 2 - Is there additional structure; e.g, do all the white/black pixels of your image occur in a single connected component? 3 - Is it terribly important that your polygon have exactly N sides? It seems to me that viewing this as a contour- (or outline-) tracing problem would be productive...

Even if he was doing it properly, it'll still be dumb to use a gradient descent for that. Finding the convex contour is an easy and well-solved problem in imaging with straightforward solutions.

Quote:

Original post by Steadtler Even if he was doing it properly, it'll still be dumb to use a gradient descent for that. Finding the convex contour is an easy and well-solved problem in imaging with straightforward solutions.

That's why I was asking him what exactly his problem was.

I'm assuming that he actually wants non-convex contours (but this is something which it would be good for him to clarify).

If he's willing to give up #3 (using the numbering of my previous post), then standard contour-tracing algorithms (e.g. Moore-Neighbor) should do the trick (hence the last sentence of my previous post), so I think we're in agreement there. The answer to #2 determines how much searching we have to do.

This kind of solution, however, will result in zero misclassified pixels but a very complicated polygon. If he wants a simpler polygon, the obvious thing to do then would be to throw Ramer-Douglas-Peucker at it -- and this might be a reasonable idea -- but this would not trade off between error and the number of polygon vertices in any principled way. It's possible that literature exists on this problem; if it does, the references cited here may be a good starting point, but I haven't dug into this. Hence, without knowing a better alternative, I think it actually may be reasonable to perform a local optimization to remove vertices (starting from the output of a standard outline tracing algorithm as above), and perhaps simultaneously adjust the locations of the remaining ones; I don't think I'd try using a global optimizer like a GA for this, but would instead use a local hill-climber. If one were to use such an approach, a cost function with a relatively nice theoretical justification here might be

log(2N) + log(2 [# misclassified pixels])

as this is the amount of data needed to transmit the locations of the polygon vertices, plus the locations of all the misclassified pixels (which is enough to reconstruct the original image).