Reproducing images with primitive shapes. (Graphics optimization problem)

Question

Based on this original idea, that many of you have probably seen before: http://rogeralsing.com/2008/12/07/genetic-programming-evolution-of-mona-lisa/

I wanted to try taking a different approach:

You have a target image. Let's say you can add one triangle at a time. There exists some triangle (or triangles in case of a tie) that maximizes the image similarity (fitness function). If you could brute force through all possible shapes and colors, you would find it. But that is prohibitively expensive. Searching all triangles is a 10-dimensional space: x1, y1, x2, y2, x3, y3, r, g, b, a.

I used simulated annealing with pretty good results. But I'm wondering if I can further improve on this. One thought was to actually analyze the image difference between the target image and current image and look for "hot spots" that might be good places to put a new triangle.

What algorithm would you use to find the optimal triangle (or other shape) that maximizes image similarity?

Should the algorithm vary to handle coarse details and fine details differently? I haven't let it run long enough to start refining the finer image details. It seems to get "shy" about adding new shapes the longer it runs... it uses low alpha values (very transparent shapes).

Target Image and Reproduced Image (28 Triangles):

Edit! I had a new idea. If shape coordinates and alpha value are given, the optimal RGB color for the shape can be computed by analyzing the pixels in the current image and the target image. So that eliminates 3 dimensions from the search space, and you know the color you're using is always optimal! I've implemented this, and tried another run using circles instead of triangles.

300 Circles and 300 Triangles:

Answer 1

An idea using multiple runs:

• Use your original algorithm as the first run, and stop it after a predetermined number of steps.
  • Analyze the first run's result. If the result is pretty good on most part of the image but was doing badly in a small part of the image, increase the emphasis of this part.
• When running the second run, double the error contribution from the emphasized part (see note). This will cause the second run to do a better match in that area. On the other hand, it will do worse in the rest of the image, relative to the first run.
• Repeatedly perform many runs.

Finally, use a genetic algorithm to merge the results - it is allowed to choose from triangles generated from all of the previous runs, but is not allowed to generate any new triangles.

Note: There was in fact some algorithms for calculating how much the error contribution should be increased. It's called http://en.wikipedia.org/wiki/Boosting. However, I think the idea will still work without using a mathematically precise method.

Answer 2

I would start experimenting with vertex-colours (have a different RGBA value for each vertex), this will slightly increase the complexity but massively increase the ability to quickly match the target image (assuming photographic images which tend to have natural gradients in them).

Your question seems to suggest moving away from a genetic approach (i.e. trying to find a good triangle to fit rather than evolving it). However, it could be interpreted both ways, so I'll answer from a genetic approach.

A way to focus your mutations would be to apply a grid over the image, calculate which grid-square is the least-best match of the corresponding grid-square in the target image and determine which triangles intersect with that grid square, then flag them for a greater chance of mutation.

You could also (at the same time) improve fine-detail by doing a smaller grid-based check on the best matching grid-square.

For example if you're using an 8x8 grid over the image:

• Determine which of the 64 grid squares is the worst match and flag intersecting (or nearby/surrounding) triangles for higher chance of mutation.
• Determine which of the 64 grid-squares is the best match and repeat with another smaller 8x8 grid within that square only (i.e. 8x8 grid within that best grid-square). These can be flagged for likely spots for adding new triangles, or just to fine-tune the detail.

Answer 3

Very interesting problem indeed ! My way of analyzing such problem was usage of evolutionary strategy optimization algorithm. It's not fast and is suitable if number of triangles is small. I've not achieved good approximations of original image - but that is partly because my original image was too complex - so I didn't tried a lot of algorithm restarts to see what other sub-optimal results EVO could produce... In any case - this is not bad as abstract art generation method :-)

Answer 4

i think that algorithm is at real very simple.

P = 200 # size of population 
max_steps = 100

def iteration
  create P totally random triangles (random points and colors)
  select one triangle that has best fittness
  #fitness computing is described here: http://rogeralsing.com/2008/12/09/genetic-programming-mona-lisa-faq/
  put selected triangle on the picture (or add it to array of triangles to manipulate them in future)
end

for i in 1..max_steps {iteration}