image - 位图匹配（或二维数组）的高效算法？

Question

下图显示了算法必须执行的操作。

对于一维数组，例如字符串匹配，我们可以使用字符串搜索算法。

我们如何有效地在位图或二维数组中找到这样的匹配？

PS 给出的示例仅用于说明目的。实现 Bejeweled 求解器不需要复杂的算法，只需将游戏板拆分并制作 N x N 表，然后从每个单元格中采样一个像素，并通过检查其 RGB 值来确定每个单元格中的项目，然后我们就完成了。我想知道将在例如一个宏程序中使用的通用图像区域匹配算法，该宏程序不断单击匹配的位图区域。

Answer 1

这不是一件简单的事情。大多数游戏通过使用区域（正如您对宝石示例所推测的那样）或颜色映射来解决该问题，它们保持第二次绘图，按颜色将位置映射到特定项目。

在游戏之外，例程使用矩阵变换来尝试识别边缘和顶点，这往往会减少考虑可能匹配的数据量。一个简单的例子是使用带有内核的过滤器

 kernel = [ -1 -1 -1 ]
          [ -1  8 -1 ]
          [ -1 -1 -1 ]

强调任何与其邻国不平衡的地区。从中您可以尝试检测线和顶点，从而大大减少匹配中要考虑的项目数量。如果要检测“近”匹配，则尝试使用线性变换通过测量顶点的位移来描述匹配的距离，并设置一些标准来确定匹配是否与相同的距离太远。

一个微不足道的解决方案，但仅适用于“完美”数据的解决方案是xor针对每个可能的偏移量仅针对原始位图进行位图。如果已知图像是用精确的位图构造的，那么xor应该产生一个与位图大小相同的零字段。通过在尝试更昂贵的计算和验证计算之前检查几个选定的像素是否完全匹配，可以在一定程度上提高这种技术的性能xor，但是它的性能会随着更大的空间而降低，以非常不合需要的方式考虑。