Find the largest rectangular bounding box containing only ones in a 2d mask NumPy array

Question

I have a 2d mask where I'd like to find the largest rectangular bounding box containing only ones.

Is there a more efficient way than determining all possibilities for bounding boxes and then comparing their size?

Example code:

import matplotlib.patches as patches
import matplotlib.pyplot as plt
import numpy as np

mask = np.array([[0, 1, 0, 0, 0, 1, 0, 1],  # example mask
                 [0, 0, 0, 1, 1, 0, 0, 1],
                 [1, 1, 0, 1, 1, 1, 0, 0],
                 [1, 1, 1, 1, 1, 1, 1, 0],
                 [0, 1, 0, 1, 1, 0, 0, 0],
                 [0, 0, 0, 1, 0, 0, 1, 1],
                 [0, 0, 0, 1, 1, 0, 0, 0],
                 [0, 0, 0, 0, 1, 0, 0, 0],
                 [0, 1, 1, 1, 0, 0, 1, 1]])

def find_largest_bbox(mask):
    # TODO
    return 3, 1, 4, 4

bbox = find_largest_bbox(mask)

plt.close()
plt.imshow(mask)
x, y = bbox[0] - 0.5, bbox[1] - 0.5
w, h = bbox[2] - bbox[0] + 1, bbox[3] - bbox[1] + 1
rect = patches.Rectangle((x, y), w, h, linewidth=2, edgecolor="red", facecolor="none")
plt.gca().add_patch(rect)
plt.show()

Answer 1

One option would be to use lir (that uses Numba) :

# takes some time for compilation
# required only after installation
import largestinteriorrectangle as lir

def find_largest_bbox(mask):
    return lir.lir(mask.astype("bool"))

x, y, w, h = find_largest_bbox(mask)

im = plt.imshow(mask)

xp, *_, yp = im.get_extent()

plt.gca().add_patch(
    patches.Rectangle(
        (x + xp, y + yp), w, h,
        lw=2, fc="none", ec="r",
    )
)

Answer 2

I think you can do it by dynamic programming (ends up as O(N^3) time complexity).

Let B[i,j,w] be the biggest area that ends (bottom-right corner) at [i,j] and has width w. Then, pseudocode:

if mask[i,j]>0 and ones>=w then
    B[i,j,w] = B[i-1,j,w] + w
else
    B[i,j,w] = 0

where ones is the current tally of consecutive ones for that row.

If you are careful then you only need store B[j,w] and update it at successive rows.

Note that the routine returns -1,-1,-1,-1 for a mask of all zeros, so you'd need to deal outside with that edge case.

import matplotlib.patches as patches
import matplotlib.pyplot as plt
import numpy as np

mask = np.array([[0, 1, 0, 0, 0, 1, 0, 1],  # example mask
                 [0, 0, 0, 1, 1, 0, 0, 1],
                 [1, 1, 0, 1, 1, 1, 0, 0],
                 [1, 1, 1, 1, 1, 1, 1, 0],
                 [0, 1, 0, 1, 1, 0, 0, 0],
                 [0, 0, 0, 1, 0, 0, 1, 1],
                 [0, 0, 0, 1, 1, 0, 0, 0],
                 [0, 0, 0, 0, 1, 0, 0, 0],
                 [0, 1, 1, 1, 0, 0, 1, 1]])

def find_largest_bbox( mask ):
    ni, nj = mask.shape
    bestArea = 0
    x1, y1, x2, y2 = -1, -1, -1, -1
    B = np.zeros( ( nj, nj + 1 ) )
    for i in range( ni ):
        ones = 0
        for j in range( nj ):
            if mask[i,j] > 0: 
                ones += 1
                for w in range( 1, j + 2 ):
                    if ones >= w: 
                        B[j,w] += w
                        if B[j,w] > bestArea:
                            bestArea = B[j,w]
                            x1, y1, x2, y2 = j - w + 1, i - bestArea // w + 1, j, i
                    else:
                        B[j,w] = 0
            else:
                ones = 0
                B[j,:] = 0
    return [ x1, y1, x2, y2 ]


bbox = find_largest_bbox(mask)

plt.close()
plt.imshow(mask)
x, y = bbox[0] - 0.5, bbox[1] - 0.5
w, h = bbox[2] - bbox[0] + 1, bbox[3] - bbox[1] + 1
rect = patches.Rectangle((x, y), w, h, linewidth=2, edgecolor="red", facecolor="none")
plt.gca().add_patch(rect)
plt.show()

Your plot: