9

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:

enter image description here

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):

enter image description here

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:

enter image description here

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.

Freesnöw
  • 30,619
  • 30
  • 89
  • 138
  • In short: you want an algorithm that recomposes an irregular 4-connected shape to minimum number of non overlapping rectangles. (Each shape in your images above forms an independent sub-problem) Now the question mainly is, if this is NP-complete or not... – Aki Suihkonen Feb 26 '14 at 20:22
  • 1
    It is only the *number* of rectangles that matters, right? I ask because in your last example, you changed the two leftmost orange columns into two different orange rectangles (one big and one small), but this does not actually improve things according to your stated criterion. – j_random_hacker Mar 02 '14 at 11:43
  • This should solve your problem: http://stackoverflow.com/a/5813015/47984. It won't be optimal necessarily, but it will be very good. – j_random_hacker Mar 02 '14 at 11:59
  • @j_random_hacker Yes, sorry, the change was last minute when I noticed that my final example broke the rules that I had stated originally. What matters over all is the final number of parts or "rectangles." – Freesnöw Mar 02 '14 at 16:32

2 Answers2

6

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.

Community
  • 1
  • 1
David Eisenstat
  • 64,237
  • 7
  • 60
  • 120
  • I may be wrong, but this seems like it solves a slightly different problem, since the example specifies a beginning grid/square shape, as well as color and alpha varied regions. Oddly, the naive approach seems like it might have interesting parallel and possibly cpu vectorization properties. – Jason Mar 02 '14 at 18:28
  • @Jason: You can just apply Eppstein's method (or rather, the method of the various people Eppstein himself cites) to each connected component within the grid separately. That method solves a more general problem, in that the corner co-ordinates can be non-integer, so it may not be the fastest available method for this problem, but it's guaranteed to be optimal. – j_random_hacker Mar 02 '14 at 18:34
  • @j_random_hacker Right, it is optimal with respect to the final number of sub-rectangles, but you still have to add constructing the sub-polygons to the final complexity. I *suspect* there's a less complex method, but at the moment I can't prove it. – Jason Mar 02 '14 at 19:02
  • @Jason: Do you mean the time needed to construct the inputs to Eppstein's method? A O(n) flood fill can do that. I doubt there'll be a much less complex method, since the inputs to Eppstein's method aren't *much* more general -- although it takes real-valued co-ords, it actually only cares about their vert and horiz order, so every Eppstein-instance is equivalent to some grid-instance. You can save some time by collapsing adjacent rows and columns that are identical, but I doubt you can do much better than that without inventing a better algo for the more general case too -- which is hard! – j_random_hacker Mar 02 '14 at 20:56
1

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')

enter image description here

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

dranxo
  • 3,348
  • 4
  • 35
  • 48