探寻填充重叠像素矩形的高效成熟算法

现有初始像素全为0的二值图像（像素值仅为0或1），给定一组以「左下角像素坐标、宽度、高度」描述的重叠矩形，需对每个矩形内的所有像素执行翻转操作。当前需处理数千万张此类图像，每张图像含数万个像素，关联的重叠矩形数量庞大，暴力遍历所有矩形的方法因重叠区域多存在大量计算浪费。拟开发先逐列求并集的算法，想确认计算机视觉/图像处理领域是否存在解决该问题的成熟算法。
补充背景：该问题源于大规模模拟飓风事件的最近邻搜索，通过为飓风图像的每个像素构建矩形邻域特征，将图像平展为比特数组作为特征向量，最终使用Jaccard距离进行搜索，目前特征工程环节为性能瓶颈。

经典成熟算法 #

1. 二维差分（扫描线）算法 #

这是处理矩形区域批量更新问题的标准高效方案，核心是通过记录边界变化避免遍历每个像素：

• 先将每个矩形的描述转换为对角坐标：左下角(x1,y1)，右上角(x2 = x1 + 宽度 - 1, y2 = y1 + 高度 - 1)
• 创建与图像同尺寸的差分矩阵diff，初始全为0
• 对每个矩形执行4次边界标记操作：
  • diff[y1][x1] += 1
  • 若x2+1 < 图像宽度，diff[y1][x2+1] -= 1
  • 若y2+1 < 图像高度，diff[y2+1][x1] -= 1
  • 若x2+1 < 图像宽度且y2+1 < 图像高度，diff[y2+1][x2+1] += 1
• 对差分矩阵先逐行做前缀和，再逐列做前缀和，得到每个像素的翻转次数
• 根据翻转次数奇偶性确定最终像素值：奇数次为1，偶数次为0

该方法时间复杂度为O(N + W*H)，N是矩形数量，W、H为图像宽高，完全消除了重叠区域的重复计算，适配矩形数量庞大的场景。

2. 行列区间合并优化 #

如果你的逐列求并集思路是为了减少重复操作，可以结合区间合并进一步优化：

• 对每一列，收集所有覆盖该列的矩形的y轴区间（y1到y2）
• 将重叠或相邻的区间合并为不重叠的连续区间，每个合并后的区间只需记录一次翻转（等价于区间内像素翻转次数+1）
• 最后对每列的合并区间统计奇偶性，直接得到该列所有像素的最终值

这种方法在矩形列向重叠度高的场景下，能大幅减少计算量，时间复杂度取决于区间合并的效率。

适配飓风模拟场景的额外优化 #

• 由于最终要生成比特数组特征向量，可将多个像素打包为整数（如64位整数），利用位运算批量计算翻转后的像素值，提升处理速度
• 若所有图像尺寸固定，可预先分配差分矩阵内存池，避免重复内存申请的开销
• 采用并行计算：将图像按行/列分块，每个块独立处理对应矩形和差分计算，借助多线程或GPU加速大规模图像的处理

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