Finding complete rectangles enclosing 0

Question

There are diverse rectangles in given 1000 x 1000 arrays. in <Figure 1>, the serial “1” displayed as yellow cell is the pattern of rectangle. The minimum size of rectangle in <Figure 1> is 3 x 3 displayed as green cell.

There should be at least one of ‘0’ inside the rectangle.

But, in this array, there exists unclosed shape or straight line pattern also.

(The initial value of array is ‘0’, and the patterns are represented a series of ‘1’. They are not overlapped or included each other.)

What could be an efficient algorithm to find the complete regtangles in the array except unclosed shape or straight line? For example in the figure above the number of complete rectangles is 3

Answer 1

This is quite simple. If you have n squares, you can count the rectangles in O(n).

Assumptions:

• The borders of each valid rectangle don't share any cells with a non-valid path.
• If one rectangle is inside another, you would be happy finding them

You would need extra memory as big as the input. Let's call this visited and initialize with 0.

Let's first construct a helper function:

is_rectangle(square s)
    from s, go right while you see 1s and visited is 0
        mark them as 1 in visited
    if less than 3 steps
        return 0
    then, go down while you see 1s and visited is 0
        mark them as 1 in visited
    if less than 3 steps
        return 0
    then, go left while you see 1s and visited is 0
        mark them as 1 in visited
    if less than 3 steps
        return 0
    then, go up while you see 1s and visited is 0
        mark them as 1 in visited
    if then one above is not s
        return 0
    return 1

This function basically traces the 1s in the directions of right-down-left-up and checks if the conditions are met (length at least 3 and reaching the starting position). It also marks the visited squares.

The important thing to notice about this function, is that it works correctly only if the initial square is the top-left corner.

Now, the solution to the problem is easy:

num_rectangles = 0
initialize visited to 0 (rows x columns)
for r in rows
    for c in columns
        if visitied[r][c] or image[r][c] == 0
            continue
        num_rectangles += is_rectangle(<r,c>)
return num_rectangles

Here is how the algorithm executes:

1. Failed (and marked) part of a bad rectangle

2. Found (and marked) a rectangle.

3. Failed on a single square (of a vertical line)

4. Failed on a single square (of a vertical line)

5. Failed on a single square (of a vertical line)

6. After many similar steps, found the next rectangle.

7. And the next rectangle

8. Algorithm end

Answer 2

The following O(n) algorithm will work on any 2D matrix of 0/1 values (that is, intersecting/overlapping rectangles are allowed, as are arbitrary non-rectangular open/closed shapes). The definition of a rectangle I'm using here is "the interior is entirely made up of 0-cells" (so e.g. if one rectangle entirely contains another, only the inner rectangle will be found; if containing rectangles should also be considered, then each found rectangle can be deleted and the algorithm restarted). It's based on the observation that each 0-cell can be in the interior of at most one 1-rectangle.

I use the convention that x = 0 is the leftmost position and y = 0 is the topmost position.

1. Find the top-left corner. Starting at the top-left cell and proceeding left-to-right and top-to-bottom, find the next unvisited cell that could be the top-left corner of a solid-0 rectangle: specifically it must be a 0-cell that has 1-cell neighbours in the SW, W, NW, N and NE positions, and 0-cells in the remaining 3 neighbouring positions.
2. Find the top-right corner. Scan through neighbours to its right while these cells are 0 and have a 1-cell N neighbour.
3. Could this be the top row of a solid 0-rectangle? If the the last cell found by the above loop before it ends is a cell that could be the top-right cell in a solid-0 rectangle (specifically a 0-cell having 1-cell neighbours in the NW, N, NE, E and SE cells, and 0-cells in the remaining 3 positions), then we have established both the top y co-ordinate and the exact width of the only possible solid 0-rectangle that uses any of these cells. If the last cell doesn't meet these top-right-corner conditions, then none of these cells can be part of a solid 0-rectangle: mark them visited and goto 1.
4. Call the start and end x co-ordinates of the strip of 0-cells x1 and x2; call the vertical position y1.
5. Scan down, a row at at time. Set y2 = y1, and while the line between x1 and x2 at vertical position y2 could be part of the solid 0-rectangle, increment y2. Specifically, the test at each vertical position y2 is: the cells at (x1 - 1, y2) and (x2 + 1, y2) must both be 1, and all cells in between must be 0.
6. Could this be the bottom row of a solid 0-rectangle? If the last row found by the previous loop before it ends is a row that could be the bottom row of a solid 0-rectangle (specifically there are 1-cells all the way from (x1 - 1, y2 + 1) to (x2 + 1, y2 + 1)), then we have found a complete solid 0-rectangle surrounded by 1-cells: if its size is greater than the biggest discovered so far, then record it as the new biggest rectangle. Otherwise (if there is not a solid row of 1-cells in the next line down), none of the 0-cells examined can be part of any solid 0-rectangle: mark them all as visited and goto 1.

Answer 3

If you can have only rectangular shapes in your array, it is equivalent to a classic problem of computation on binary images: just apply a standard algorithm for connected components. You label only connected components of 0's, and count them.

See http://en.wikipedia.org/wiki/Connected-component_labeling for example. This type of algorithm is quite simple on images but take some amount of memory (same size as your input array, of type short or int). Be careful of connectivity: if you choose 4-connectivity, you will count enclosed rectangles even if some corners are missing. But the algorithm is simpler than with 8-connectivity.

If you can have more complex enclosed shapes, just add a post-processing: for each connected component, count the number of pixels inside the bounding box of the component (if the two numbers are equal, you have a rectangle)