This problem is underspecified. Because you've provided a single, simplistic example, you have missed some of the important logical possibilities and corner cases here (or, you just haven't explicitly excluded them). For instance, since you don't mention the proposed application for this, you haven't specified what is more important: Breaking up the entire map into exclusive rectangles that have as large an area as possible (the Packing Problem, which has an arbitrary number of solutions), or simply getting edge-matched rectangles in each of x and y, as you seem to imply above. I assume the latter.
Consider the case where you fill in each of the 4 tiles that sit immediately in the corners of the "plus-sign"-shaped bitmask you've drawn above ([2, 2] being the topmost).
Now what are the optimal rectangles? Considering just columns, Would you prefer narrower, longer rects with slimmer ones to the sides, or the large, broader square which could now be found in the middle of the image, with squat squares above and below?
Anyway, assuming longest-possible edge-matched rects, take this as a first-attempt solution:
- Break the bitmask down into columns. Each column starts at some value y0 and ends at some other value y1. Store each column as a (y0, y1) tuple in a list.
- Columns: Evaluate the list. Find where adjacent tuples have the same y0 AND y1 between them (eg. column A starts at y0=1 and ends at y1=4; so does column B). For as long as each consecutive column DOES have these the same, increment the width of a rectangle you have created to represent these, by one. As soon as they DO NOT, end this rectangle and store it, and create a new one for any subsequent column groups.
Repeat both of the above steps for rows, exactly as for columns (using x0 and x1 instead, and a separate list, of course).
You should now have some lists of cleanly-edged rectangles. They may however not be optimal for your application; if this is the case, you will need a system of heuristics that enables more efficient packing. See the Packing Problem for more.