1

我确实有以下问题要解决：我有一个简单但大的网格图（大小：mX-times-mY）。我只区分被障碍物占据或自由的瓷砖。

现在假设我使用了一个相对较小的滑动窗口，大小为 n-times-n，所以 n << mX，n << mY。对于该 n 次 n 窗口中所有可能的占用和空闲图块组合，我分配了一个标识符（我们只是说一个数字）。然后我以那个窗口的大小对我的大地图的一部分进行“快照”。

我的问题：确定从地图中提取的当前模式的识别号最简单和/或最快的方法是什么？

演示：我有一个 2x2 窗口（所以是 2x2 矩阵）。有 2^(2x2)=16 种可能的模式组合。

Pattern    #1    #2    #3    #4    #5    #6    #7    #8

           00    #0    0#    00    00    ##    #0    00
           00    00    00    #0    0#    00    #0    ##

Pattern    #9    #10   #11   #12   #13   #14   #15   #16

           0#    #0    0#    0#    #0    ##    ##    ##
           0#    0#    #0    ##    ##    0#    #0    ##

with # = obscured
     0 = free

假设我提取模式

#0
0#

从我的地图中，我怎样才能轻松快速地确定这是上面示例中的模式编号 10？

到目前为止我的想法：

1：简单循环

循环遍历所有模式，直到找到正确的模式，可能通过检查两种模式的差异是否为零矩阵。

2：使用 Row-Sum 和 Column-Sum 作为标识符

我对所有 n 行和所有 n 列求和，并将这些总和用作多维数组中的子索引。对于上面的例子： sumRow1 = 1 sumRow2 = 1 sumCol1 = 1 sumCol2 = 1 所以我的模式被保存在 patternNumbers[1][1][1][1] = 10 中。另一个例子是模式 16，它将被保存在模式编号[2][2][2][2] = 16。

更大窗口的可能优势：我只需要计算 2*n 总和并立即可以使用这些总和来解决我正在寻找的模式。很大很大的缺点：我需要一个 (2*n) 维数组，其中会留下许多空条目。所以开销比较大。

你们有没有人这样做过？任何想法如何解决这个问题？我也没有考虑任何形式的对称性（旋转或直线）。

任何帮助是极大的赞赏！

4

1 回答 1

0

好吧，看起来我找到了一个相对简单的解决方案，这是其他人向我指出的：

通过以特定顺序获取所有行或所有列（没关系，您的选择！） - 所有模式都必须相同 - 并将它们对齐为一个长向量，然后你得到一个正则二进制表达式。只需将该二进制数转换为十进制数，您就有了“唯一标识符”。

Example 1:

00
#0

can also be written as
00
10

now reorder the rows to

0010 = 2

=============================

Example 2:

##
00

can also be written as
11
00

now reorder the rows to

1100 = 12
于 2012-09-19T08:30:53.947 回答