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

Question

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

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

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

我在这里给出了一个使用线性时间预处理在恒定时间内查找平均值而不是最大值的方法示例。

有谁知道寻找最大值的类似技术？

Answer 1

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

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

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

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

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