algorithm - 方形子矩阵和的约束最大化

Question

我有一张图像的强度图，我想选择平均值较大的子区域。为此，我想找到使子区域覆盖的强度图像素总和最大化的子区域。为了防止返回过多的子区域，对每个额外返回的子区域应用惩罚。另外，两个子区域重叠也可以，但是重叠的目标值只是子区域的并集。

更正式地说，假设您有一个矩阵 A，其中包含维度为 m x n 的非负值。您想要用维度为 s x s 的方形子矩阵覆盖矩阵，这样 A 的值的总和被覆盖正方形面积的并集最大化。对于您添加到解决方案中的每个方 block ，都会从解决方案的目标值中减去常数惩罚 p。

例如，考虑以下矩阵:

0 0 0 0 0 0
0 1 2 2 1 0
0 1 2 2 2 0
0 0 0 0 0 0
0 3 0 0 0 0

参数 p = -4 和 s = 2。最优解是两个正方形 S1 = [1, 2; 1, 2] 和 S2 = [2, 1; 2, 2] 的坐标分别为 (2:3,2:3) 和 (2:3,4:5)(在 Matlab 符号中)。请注意，在此示例中，增量添加具有最大值的方 block 直到无法添加方 block (不降低目标值)的贪婪方法失败了。

解决它的一种蛮力方法是使用恰好 k 个方 block 检查所有可能的组合。从 k =1 开始，您将计算恰好有 k 个方 block 的最佳组合，增加 k 并重复直到目标值停止增加。这显然非常昂贵。

您可以使用积分图像在时间 O(mn) 内预先计算 (m-s+1)*(n-s+1) 个可能正方形的值之和。

是否有有效的解决方案？

Answer 1

问题是 NP-Hard。这可以通过减少平面最小顶点覆盖来证明。特殊情况 s=3、p=2 和 A 只有值 0 或 1 的证明与 other SO question 的证明相同.

至于蛮力解决方案，如果不是尝试增加 k 的所有组合，而是逐渐添加正方形，则可以提高效率。当部分解决方案的目标值加上尚未覆盖值的总和不大于迄今为止最佳目标值时，通过删除最近添加的方 block 并尝试其他方 block 来回滚到最后一个有效组合。避免添加将零添加到目标值的正方形。还要避免添加次优方 block :例如，如果来自 OP 的部分解包含方 block [1, 2; 1, 2], 不加方 block [2, 2; 2, 2] 因为 [2, 1; 2, 2] 至少总是一样好，甚至更好。并以快速获得足够好的解决方案的方式重新排列方 block ，这允许更快地终止所有进一步的尝试。