c++ - 在二维数组的矩形区域内快速找到最大值的方法

Question

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

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

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

我已经给出了一个通过使用线性时间预处理来寻找平均值而不是常数时间最大值的方法示例 here .

有人知道找到最大值的类似技术吗？

Answer 1

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

供大家引用，这里很好解释通过积分图像计算矩形的均值Viola/Jones CVPR 2001 ，请参阅第 2.1 节。

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

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

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