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

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]（形状的左上角）

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

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

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

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

Answer 1

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

执行以下步骤：

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

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;
    }
}

您可以使用积分图像数组快速计算给定地图矩形中所有条目的总和，只需 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) 遍历地图，并为每个 (x,y) 计算 (x, y, shape width, shape height) 的矩形总和。如果它小于形状总和，则地图中不可能有左上角位于 (x,y) 的形状，因此您可以跳过它。否则检查。

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

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

在 (4) 中的测试通过时检查形状：

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

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

Locate a shape in a 2D array of integers

algorithm

match