Recreate image using only overlapping squares

Question

I'm trying to take a source image, and recreate it on a transparent canvas using only overlapping mono-colored squares. The goal is to use as few squares as possible.

In other words, I'm taking a blank transparent image, and drawing squares of various colors until I recreate the source image, with the goal being to use as few squares as possible.

For example:

Here is a source image. It has two colors: red and green. I want to use only squares, that may overlap, to recreate the source image.

The ideal solution would be a large red square, and then two green squares drawn on top - that is what I want my algorithm to find, with any source image - the position, size, color and order of each square.

---

My target image that I intend to process is this:

(8x enlargement)

It has 1411 non-transparent pixels (worst case), and with a brute force solution that does not use overlapping squares, I've recreated the image using 1246 squares.

---

My current solution is a brute force method along the lines of:

1. Create a list of all colors used in the source image. Each item is a "layer". A layer has a color and a 2D array representing pixels. The order is important, but I don't know what order the layers need to be in, so its arbitrary initially.
2. For each layer in the list, initialize the 2D array. Each element corresponds to a pixel in the source image. Pixels that are the same color as the layer's chosen color is marked as '1'. Pixels that are in a layer ABOVE the current layer are marked as "don't care". All other pixels are marked as '0'.
3. Use some algorithm to process each layer, using the smallest number of squares to reach every pixel marked '1', without touching any pixels marked '0'.
4. Rearrange the order of layers and go back to Step 2. Do this for every possible combination of layers, then check to see which ordering uses the least number of squares in total.

Someone has perhaps a better explanation in a response; but brute force testing every permutation is not viable, because my target image has 31 colors (resulting in 31! permutations).

As for why I'm doing this? I'm trying to create an image in a game (Starbound), where I can only use squares. The lazy solution is to use a square for each pixel, but that's just too many squares.

Answer 1

Just a suggestion for a possible solution. I haven't tried it.

It's a greedy approach.

For every pixel, compute the largest uniform square that contains it.

Then choose the largest of all squares and mark all pixels it covers as "covered".

Then among all unmarked pixels, choose the largest covering square, and so on until no unmarked pixel remains.

Ties do no matter, just take any largest square and mark its pixels.

UPDATE: overlaps offer opportunities for reduction in the number of squares.

Consider all possible permutations of the filling order of the shapes. The shapes drawn first, on the bottom layers, can be (partly) hidden by some others. Process the shapes starting from the top layer. When you process a shape to associate every pixel with the largest uniform square that contains it, treat all covered pixels as don't care.

In the given example, fill the green squares first; then when filling the red square, the green pixels can be considered red or not, depending on convenience.

If you cannot try all permutations, then try them at random. Heuristic approaches such as genetic algorithms or simulated annealing could help. Nothing straightforward here.