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

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.