Find the largest possible submatrix with non-zero elements

Hi. I have a large, binary image and I want to find the largest possible rectangle area of non zero elements, as it is showed in the attached image. Can you please help finding a computationally feasible solution? Thank you.

Answer 1

[John D'Errico]

Come on. What have you tried? If nothing, then why not? Your definition of computationally feasible is relative to you, as someone else would surely define it differently. And only you know what a "large" image means. How large is large?

A simple greedy algorithm would seem adequate. Consider each pixel as a potential upper left corner of the region. Then look to see how far that region can be grown, moving purely to the right. Store in a separate matrix, the number of contiguous white pixels in each row to the right of the corresponding pixel. This would be simple to compute in advance.

Having done that, now use that information to grow a rectangle down from the upper left corner. You will need to do this operation for every pixel of the image, considering each pixel in turn. But it would surely be doable, and computationally feasible. Of course, feasible for me might not be so for you.

[Bill Kavvas]

It is not so trivial as it might seem with the first look. The images are large, 50MP each and the rectangle must not contain any zero values. I also tried the approach that you suggested, but it doesn't solve the problem.

[Rik]

@Brady Hasse: In response to your flag ("Useless"): this answer isn't useless. It provides a strategy to solve this question.

If you have a similar problem: you can greatly increase the efficiency of this algorithm by only considering white pixels with a black pixel to the left as possible upper left corner (you can use the diff function, and you shouldn't forget white pixels along the left edge). You can even use run length encoding (see the FEX for efficient code).

[John D'Errico]

Seriously, something based on the approach I suggested should be entirely feasible. Yes, it will take some effort to make it work on big problems. The real trick that I see is one I outlined - to do some work in advance, thus to store how many contiguous non-zero pixels there are directly to the right of any pixel. This is trivial to compute. But then it also allows you to grow the regions as I suggested.

A nice thing is, if a region is contained in an existing rectangular region, then you can avoid even considering that sub-region.