Running the Optimal Flood Fill on a Grid While Limited to just Non-Intersecting Squares

Question

I need to optimize a grid by taking the number of "elements" in it and minimizing it as much as possible. When I say element, I'm referring to a section within that grid. Here's essentially what "input" could look like in a visual sense:

The first solution that comes to mind would be a flood fill algorithm, however, I have one restriction: All of the elements must have 4 sides, thus, all elements must be rectangular.

My first, limited, approach simple involved looping through the input grid element by element and checking to see if the last newly created element was the same color and had the same alpha as the element that was supposed to be created then — if so, instead of creating the new element, it would just resize the last one to extend down 1 block further.

Here is a pseudo-code example of what I'm doing:

element output_array();
element last_element = null;

for (int x = 0; x < grid_width; x++) {
    for (int y = 0; y < grid_height; y++) {
        color current_input_color = input_grid(x, y);

        if (last_element && last_element.x === x && last_element.color === current_input_color) {
            last_element.span_y++;
        } else {
            last_element = create_element(
                x,                   // element.x      (the x coordinate of the elements top left most grid space)
                y,                   // element.y      (the y coordinate of the elements top left most grid space)
                1,                   // element.span_x (the number of elements to span on the x axis)
                1,                   // element.span_y (the number of elements to span on the y axis)
                curent_input_color   // element.color
            );

            output_array.append(last_element);
        }
    }
}

As a result, I get this (assuming I input the previous grid into it):

So in this particular instance I've decreased the number of elements from 64 to 20.

This is good, but my "input grids" aren't normally 8x8. An example of a more realistic grid as input results in 10201 elements prior to optimization (with my current method) and 957 after.

As this method obviously relies heavily on the structure of the grid itself, these numbers can vary a great deal. My hopes are to at least minimize the elements as best I can for any given input grid.

Right now I'm approaching it from one direction (optimizing it vertically), but I would also like to optimize it horizontally. A result of such an operation doesn't have to be perfect, but here is what I envision the most optimal end grid for the first input grid:

In this case, the number of elements is reduced from 20 to just 14 - which on my larger grids could be very helpful.

I just can't seem to think of a way to utilize a flood algorithm in a way that allows me to account for every elements space in the input grid and keep all resulting elements rectangular / 4 sided.

I figured I could probably brute force it, and while CPU utilization / speed isn't the biggest of concerns, I have to run this on very large grids with thousands upon thousands of elements so wasting resources trying to brute force something on such a grand scale just isn't realistic - I don't think.

Answer 1

Gareth Rees posted a very nice answer to this question that expands on David Eppstein's answer at Math Overflow citing multiple authors. In a sentence, the algorithm, which yields optimal solutions, is first to cut a maximum noncrossing set of lines between concave vertices (found in polynomial time by maximum independent set in a bipartite graph) and then to extend these cuts greedily so that the remaining faces are rectangles.

Finding a MIS in a bipartite graph requires a maximum matching algorithm. If this is too much work, then just the greedy step, where a vertical cut is made from each concave vertex, is a 2-approximation.

Answer 2

Depending on the application, you might be able to solve this with wavelets. Think of your 2D array as a grayscale image, the goal is to compress it by decomposing into rectangular functions (ie Haar wavelets) and then discarding the functions used to represent fine details. Given the data you've shown us so far (ie no noise or texture), you won't actually have to discard anything out after you've taken the wavelet transform.

In python you can use http://www.pybytes.com/pywavelets/ ,

import pywt
import numpy as np
import matplotlib.pyplot as plt
import Image

img = Image.open('Desktop/b12nI.png')

plt.imshow(img, cmap='gray')

Take a single level discrete wavelet transform :

coeffs = pywt.dwt2(img, 'haar')
cA, (cH, cV, cD) = coeffs

The cA contain the Haar wavelet coefficients used for the approximation. The approximation is exact on your data, we can check by inverse transforming on the approximate coefficients:

recon = pywt.idwt2(coeffs,'haar')
np.max(np.abs(recon - img))

produces 1.4210854715202004e-14

To compare, if we tried to approximate Gaussian noise with Haar wavelets:

noise = np.random.randn(512,512)
cA, (cH, cV, cD) = pywt.dwt2(noise, 'haar')
recon = pywt.idwt2(coeffs,'haar')
np.max(np.abs(noise-recon))

yields: 213.31090340487393

Computationally, wavelet transforms are O(n).

Java code for wavelet transformations is here: https://en.wikipedia.org/wiki/Discrete_wavelet_transform

More info: http://gtwavelet.bme.gatech.edu/wp/kidsA.pdf