How do we find a biggest white rectangle in a n x n bitmap ?

Any idea on how to solve su开发者_高级运维ch problems (in C++)- like which is the best Algorithm to use.

Say you have a n x n rectangular area black and white (O and 1) pixels and you're looking for the biggest white rectangle in this area.

I would write something simple like below:

• first pass: create a set of 1 line segments for each pixel row.
• second pass aggregate rectangles:
  • for each segment iterate on rows to find the largest rectangle containing it.
  • if you use another segment in the process mark it as used, not need to try it again
  • at any point keep only the largest rectangle found

That's only a first draft of a possible solution. It should be rewritten using a more formal algorithmic syntax and many details should be provided. Each step hides pitfalls to avoid if you want to be efficient. But it should not be too hard to code.

If I did not missed something, what I described above should basically be O(n4) in the worst case, with the first pass O(n2) used to find horizontal segments (could be quite fast with a very small loop) and the second pass probably much less thant O(n4) in practice (depends on segment size, really is nb_total_segment x nb_segment_per_line x nb_overlapping_segment).

That looks not bad to me. Can't see any obvious way to do it with better O complexity, (but of course there may be some way, O(n4) is not that good).

If you provide some details on input structure and expected result it may even be some fun to code.

What you ask for is known as blob filtering on the computer vision world.

• http://en.wikipedia.org/wiki/Blob_extraction
• http://en.wikipedia.org/wiki/Connected_component_labeling
• http://www.aforgenet.com/framework/features/blobs_processing.html