在二维数组的矩形区域内快速查找最大值的方法

Question

我有一个深度值的二维数组，需要一种快速的方法在给定的矩形区域内找到最大值。许多矩形将针对给定的深度缓冲区进行测试，因此合理的预处理步骤是可以接受的。

天真的方法是扫描矩形中的每个像素，跟踪最大值，需要宽度*高度迭代。

通过首先创建深度缓冲区的四叉树，其中每个父节点包含其子节点的最大值，可以将复杂度降低到大约宽度+高度迭代。这种方法很好，但我想知道它是否可以更快地完成。

我给出了一个使用线性时间预处理here来求平均值而不是恒定时间中的最大值的方法的示例。

有没有人知道类似的求最大值的技术？

Answer 1

是的，您可以概括平均值的技巧，但仅限于较小的颜色深度，例如8位深度(0-255)。假设你有k种颜色(或不同的深度值)。

作为参考，这里有一个很好的解释，通过积分图像Viola/Jones CVPR 2001计算矩形的平均值，请参见第2.1节。

我的通用算法是预先计算k维向量的积分颜色/深度值出现的频率是多少。从这个向量中，您可以采用与技巧中相同的差值来计算平均值。这不仅为您提供了矩形区域内的最大值，而且还提供了该矩形内的直方图在恒定时间内的向量。当然，直方图允许您提取最大值(或最小值或其他分位数)。

时间和内存需求当然会随着颜色数量的增加而增加，我认为复杂度类对于查找是O(k)，对于预计算是O(k * width * height)。

(如果我的想法以前被使用过，我会很感兴趣。)

Answer 2

通过添加零，将数组向外填充到2的平方幂。然后将其金字塔化为堆栈，每次在每个维度上收缩2倍。在每个级别，每个元素的值等于金字塔中下一个最大数组中4个相应元素的最大值。这将在填充的数组大小之上占用额外1/3的存储空间，就像mip-mip所做的那样。

编写一个递归函数，该函数接受给定数组级别的单个元素，并检查查询区域是否覆盖它所覆盖的边界。如果不是，则检查下一个最大数组中与查询区域重叠的每个区域，返回每个区域的递归计算的最大值。

伪代码：

 int getMax(Rect query_rect, int level, int level_x, int level_y)
 {
      int level_factor = 1 << level;
      // compute the area covered by this array element:
      Rect level_rect(level_x * level_factor, level_y * level_factor,
          (level_x + 1) * level_factor, (level_y + 1) * level_factor);

      // if the regions don't overlap then ignore:
      if(!query_rect.intersects(level_rect))
          return -1;

      // query rect entirely contains this region, return precomputed max:
      if(query_rect.contains(level_rect))
          return pyramid[level][level_x][level_y];

      if(level == 0)
          return -1;  // ran out of levels

      int max = getMax(query_rect, level - 1, level_x * 2, level_y * 2);
      max = maxValue(max, getMax(query_rect, level - 1, (level_x * 2) + 1, level_y * 2);
      max = maxValue(max, getMax(query_rect, level - 1, level_x * 2, (level_y * 2) + 1);
      max = maxValue(max, getMax(query_rect, level - 1, (level_x * 2) + 1, (level_y * 2) + 1);

      return max;
 }

最初在顶层调用它(金字塔中的capstone 1x1数组)：

 int max = getMax(query_rect, 10, 0, 0);

有一个查询矩形的最小大小，低于这个最小大小，迭代所有元素的成本会更低。你可以调整它来处理非方形数组，它只需要在递归时针对每个级别的数组大小进行一些额外的测试。