如何在二维NumPy掩码数组中高效查找仅含1的最大矩形边界框

当然有更高效的实现方法——基于单调栈的直方图法，时间复杂度可以降到O(nm)（n为行数，m为列数），远优于枚举所有边界框的O(n²m²)复杂度。

核心思路 #

1. 构建行直方图：逐行遍历掩码数组，对每个列位置计算向上连续的1的高度。例如，第i行第j列的高度height[j]，表示从第i行往上（包括当前行），第j列连续出现1的次数。如果当前位置是0，则高度重置为0。
2. 单调栈找最大矩形：对每一行生成的高度数组，使用单调栈快速找出能构成的最大矩形。单调栈可以在O(m)时间内处理一行的高度数组，同时记录矩形的左右边界和高度，进而计算出对应的边界框坐标。

完整实现代码 #

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):
    if mask.size == 0:
        return (0, 0, 0, 0)
    
    rows, cols = mask.shape
    height = np.zeros(cols, dtype=int)
    max_area = 0
    best_bbox = (0, 0, 0, 0)  # (x1, y1, x2, y2)，对应行起始、列起始、行结束、列结束
    
    for i in range(rows):
        # 更新当前行的高度数组
        for j in range(cols):
            height[j] = height[j] + 1 if mask[i][j] == 1 else 0
        
        # 用单调栈处理当前高度数组，加哨兵简化剩余元素处理
        stack = []
        extended_height = np.append(height, 0)
        
        for j in range(len(extended_height)):
            while stack and extended_height[j] < extended_height[stack[-1]]:
                h = extended_height[stack.pop()]
                w = j if not stack else j - stack[-1] - 1
                area = h * w
                
                if area > max_area:
                    max_area = area
                    # 计算边界框的行、列范围
                    x1 = i - h + 1
                    x2 = i
                    y1 = stack[-1] + 1 if stack else 0
                    y2 = j - 1
                    best_bbox = (x1, y1, x2, y2)
            stack.append(j)
    
    return best_bbox

bbox = find_largest_bbox(mask)

plt.close()
plt.imshow(mask)
# 适配matplotlib坐标：列对应x轴，行对应y轴
x, y = bbox[1] - 0.5, bbox[0] - 0.5
w, h = bbox[3] - bbox[1] + 1, bbox[2] - bbox[0] + 1
rect = patches.Rectangle((x, y), w, h, linewidth=2, edgecolor="red", facecolor="none")
plt.gca().add_patch(rect)
plt.show()

效果展示 #

代码说明 #

• 高度数组height：逐行更新，记录每列向上连续1的数量，是构建直方图的核心。
• 单调栈：维护一个递增的栈，当遇到更小的高度时，弹出栈顶元素并计算以该元素高度为高的最大矩形宽度，从而得到面积。
• 边界框计算：根据弹出元素的高度和宽度，反推出矩形的行范围（从当前行往上数h行到当前行）和列范围（从栈顶下一个位置到当前列的前一个位置）。

内容的提问来源于stack exchange，提问作者finefoot