find largest rectangle not (necessary) aligned with image boundary in binary matrix

Question

I am using this solution to find rectangles aligned with the image border in a binary matrix. Suppose now I want to find a rectangle that is not aligned with the image border, and I don't know its orientation; what would be the fastest way to find it?

For the sake of the example, let's look for a rectangle containing only 1's. For example:

1 1 1 1 0 0 0 0 0 1 0 0 1 1 1
0 1 1 1 1 1 0 0 0 1 0 0 1 1 0
0 0 0 1 1 1 1 1 0 1 0 0 1 0 0
0 0 0 0 0 1 1 1 1 1 0 0 0 0 0
0 0 0 0 0 0 0 1 1 1 1 1 0 0 0
0 0 0 0 0 0 0 0 0 1 1 1 1 1 0

Then the algorithm described in the solution I described above would only find a rectangle of size 6 (3x2). I would like to find a bigger rectangle that is tilted; we can clearly see a rectanble of at least size 10 or more...

I am working in C/C++ but an algorithm description in any language or pseudo-code would help me a lot.

Some more details:

• there can be more than one rectangle in the image: I need the biggest only
• the rectangle is not a beautiful rectangle in the image (I adapted my example above a little bit)
• I work on large images (1280x1024) so I'm looking for the fastest solution (a brute-force O(n³) algorithm will be very slow)
• (optional) if the solution can be parallellized, that is a plus (then I can boost it more using GPU, SIMD, ...)

Helles

I wonder whether knowing the orientation of the minimum bounding box containing all the 1's could provide any indication on the orientation of the largest rectangle containing only 1's. It probably doesn't work in general, but it might be a start. For instance, it might be the case for convex shapes... – Sherwoodsherwynd

If you want "just do it" - you can apply O(n^3) search for rectangles algorithm. I.e. - start to check for rectangle in each 1 point, building all possible rectangles. Then find rectangle with maximum area (it may be more that one) – Velodrome

@AlmaDo I don't know anything about the orientation; so I cannot choose all possible orientations: every 10 degrees? Every 5 degrees? ... However I agree it would be a possible solution but very sub-optimal. (I use 1280x1024 images) – Helles

Depends. You need to decide what should be treated as rectangle (here we came to such thing as line plotting on discrete space. This can be done with Bresenham algorithm). So: you need to determine if given points represent border of rectangle. To do it, you need to know, what is border - and what is correct discrete representation of it (because we're not on continuous plane, we're on some discrete space) – Velodrome

Mmh, I'd like some clarification about so I prefer an optimal solution (which I'll be able to boost myself later using GPU, SIMD or others ...) because highly parallel algorithms are not always (even) close to optimal ones. Are you looking for a highly parallel algorithm or an optimal one? I'd like more information on the discrete-ness of your problem too. Do you consider cells to be 2D-coordinates or are they really squares in the sense that a line crossing them is considered crossing the whole cell? – Sherwoodsherwynd

@Sherwoodsherwynd I am really looking for the fastest way; not for the "scientifically most optimal and beautiful". Does that answer your question? I tried to make it a little more clear in my question – Helles

You might want to post this question on cs.stackexchange.com – Jackie

Answer 1

I only have a partial answer for this question, and only a few thoughts on complexity or speed for what I propose.

Brute Force

The first idea that I see is to use the fact that your problem is discrete to implement a rotation around the center of the image and repeat the algorithm you already use in order to find the axis aligned solution.

This has the downside of checking a whole lot of candidate rotations. However, this check can be done in parallel since they are indepedant of one another. This is still probably very slow, although implementing it (shouldn't be too hard) and would provide a more definite answer to the question speed once parallelized.

Note that your work-space being a discrete matrix, there is only a finite number of rotation to browse through.

Other Approach

The second solution I see is:

1. To cut down your base matrix so as to separate the connected components [1] (corresponding to the value set you're interested in).
2. For each one of those smaller matrices -- note that they may be overlapping depending on the distribution -- find the minimum oriented bounding box for the value set you're interested in.
3. Still for each one of those, rotate your matrix so that the minimum oriented bounding box is now axis-aligned.
4. Launch the algorithm you already have to find the maximum axis-aligned rectangle containing only values from your value set.
5. The solution found by this algorithm would be the largest rectangle obtained from all the connected components.

This second solution would probably give you an approximation of the soluiton, but I believe it might prove to be worth trying.

For reference

The only solutions that I have found for the problem of the maximum/largest empty rectangle are axis-aligned. I have seen many unanswered questions corresponding to the oriented version of this problem on 2D continuous space.

EDIT:

[1] Since what we want is to separate the connected component, if there is a degree of overlap, you should do as in the following example:

0 1 0 0
0 1 0 1
0 0 0 1

should be divided into:

0 0 0 0
0 0 0 1
0 0 0 1

and

0 1 0 0
0 1 0 0
0 0 0 0

Note that I kept the original dimensions of the matrix. I did that because I'm guessing from your post it has some importance and that a rectangle expanding further away from the boundaries would not be found as a solution (i.e. that we can't just assume there are zero values beyond the border).

EDIT #2:

The choice of whether or not to keep the matrix dimensions is debatable since it will not directly influence the algorithm.

However, it is worth noting that if the matrices corresponding to connected components do not overlap on non-zero values, you may choose to store those matrices "in-place".

You also need to consider the fact that if you wish to return as output the coordinates of the rectangle, creating a matrix with different dimensions for each connected component, this will force you to store the coordinates of your newly created matrix in the original one (actually, one point, say for instance the up-left one, should be enough).

Sherwoodsherwynd

Okay, then the choice of whether or not to keep the matrix dimensions is debatable since it will not directly influence the algorithm. However, it is worth noting that if the matrices corresponding to connected components do not overlap on non zero values, you may choose to store those matrices "in-place" and share it across threads. – Sherwoodsherwynd