algorithm - 在二维整数数组中找到一个形状

Question

在一个固定大小的整数映射上

1,1,1,0,0,0,0,0,0,0,0,0,0
0,1,1,0,0,1,0,0,0,0,0,0,0
0,0,1,0,1,2,1,0,0,1,2,0,0
0,0,0,0,0,0,0,0,0,0,0,0,0

查找任意未旋转形状的位置:

0,0,0,1,0
1,0,1,1,1

输出:[2,1](形状的左上角)

解决方案是一个区域，该区域可以根据形状在 map 中的相对位置提供所需的值。找到太大的整数值不会取消区域的资格。只有一个太小了。

蛮力方法是遍历形状的每个可能的偏移量，然后循环两个矩阵以测试是否有足够的值。

另一种方法是将 map 的行和列与形状相加，然后找到可能存在的解决方案，然后测试每个解决方案以查看它们是否有效。这仅在 map 人烟稀少时才有用。

你能推荐一个更好的方法吗？希望降低 Big O 的复杂性。

Answer 1

一种可能的优化是使用 integral image .

执行以下步骤:

1) 找到形状中的最大值，然后对 map 进行预处理，将所有高于最大值的值夹紧到最大值。

2) 创建一个积分图像数组，其中条目 ii[y][x] 包含 map[j][i] 中所有条目的总和，其中 j <= y 且 i <= x，计算类似于这个:

for(int y = 0; y <= rows; y++)
{
    int rowsum = 0;
    for(int x = 0; x <= columns; x++)
    {
        rowsum += map[y][x];
        ii[y][x] = rowsum + (y > 0) ? ii[y-1][x] : 0;
    }
}

您可以使用积分图像数组快速计算给定 map 矩形中所有条目的总和，只需 4 次数组查找(省略数组索引的上限检查):

int computeRectSum(int x, int y, int width, int height)
{
    int sum = ii[y + (height - 1)][x + (width - 1)];
    if(x > 0)
        sum -= ii[y + (height - 1)][x-1];
    if(y > 0)
        sum -= ii[y-1][x + (width - 1)];
    if((x > 0) && (y > 0))
        sum += ii[y-1][x-1];
    return sum;
}

3) 对搜索形状中的所有值求和。

4) 遍历 map ，并为每个 (x,y) 计算 (x, y, shape width, shape height) 的矩形总和。如果它小于形状总和，则 map 中不可能有左上角位于 (x,y) 的形状，因此您可以跳过它。否则检查。

与行和列求和一样，此优化最适用于稀疏数组，但我认为性能应该稍微好一些，因为它是一个更局部的测试。您可以同时使用它们:如果一行的总和小于形状的顶行总和，则排除整行。

如果 map 上的人口非常稀少，您还可以通过检查比搜索形状大得多的区域，以分而治之的方法使用积分图像排除 map 上的大块区域。

当 (4) 中的测试通过时检查形状:

对于大形状，您可以(广度优先)递归地分割形状，在每一步测试子区域:首先用积分图像测试整个形状矩形(即步骤 4)，然后如果通过则分割为 4 个子区域-regions 并以相同的方式测试它们，然后测试子子区域等，直到你最终得到一个 1x1 子区域，在这种情况下你只是在做你的原始检查。您还必须计算形状的积分图像才能使用此算法。