与 Numpy 数组中的通配符进行二维模式匹配

Question

首先，我知道这个，这个和这个关于二维模式匹配的文章，但是这些帖子都不包括通配符匹配。此外，我知道有几篇像这样的论文已经解决了我面临的问题。然而，我只是刚刚熟悉二维数组中的模式匹配，目前尝试实现论文中的算法对我来说并不容易。

因此，以下问题是我面临的问题。

给定一个二维数组：

[[1 3 4 5 3 3]
[4 1 4 5 5 2]
[5 4 3 4 4 2] # pattern
[4 5 3 4 1 3] # pattern
[3 3 3 4 4 4] # pattern
[3 4 3 4 2 5] # pattern
[4 5 3 4 1 2] # pattern
[5 1 1 2 4 2]
[2 1 3 2 1 5]
[4 4 1 3 3 1]
[1 4 3 4 4 1]
[5 2 4 4 4 1]]

以及以下示例模式(其中 ？ 表示通配符匹配(：

[[? ? 3 4 ? ?]
[? ? 3 4 ? ?]
[3 3 3 4 4 4]
[? ? 3 4 ? ?]
[? ? 3 4 ? ?]]

如何编写一个接受二维数组和模式的函数，如果模式存在于数组中，则返回 True，如果不存在，则返回 False？

如果可能的话，这个问题的通用解决方案将不胜感激，因为我正在尝试匹配许多不同的模式。如果需要，我非常愿意提供其他示例。

Answer 1

这个函数需要一个input_array、一个pattern和一个让你识别通配符的函数。在这里，我使用np.nan作为通配符，但它可以是任何东西，因为您可以制作自己的wildcard_function。

它适用于任何维度(1 或更多(的数组。我已经为您的示例对其进行了测试，似乎还可以。

from itertools import product
import numpy as np

def match_pattern(input_array, pattern, wildcard_function=np.isnan):
pattern_shape = pattern.shape
input_shape = input_array.shape
is_wildcard = wildcard_function(pattern) # This gets a boolean N-dim array
if len(pattern_shape) != len(input_shape):
raise ValueError("Input array and pattern must have the same dimension")
shape_difference = [i_s - p_s for i_s, p_s in zip(input_shape, pattern_shape)]
if any((diff < -1 for diff in shape_difference)):
raise ValueError("Input array cannot be smaller than pattern in any dimension")
dimension_iterators = [range(0, s_diff + 1) for s_diff in shape_difference]
# This loop will iterate over every possible "window" given the shape of the pattern
for start_indexes in product(*dimension_iterators):
range_indexes = [slice(start_i, start_i + p_s) for start_i, p_s in zip(start_indexes, pattern_shape)]
input_match_candidate = input_array[range_indexes]
# This checks that for the current "window" - the candidate - every element is equal 
#  to the pattern OR the element in the pattern is a wildcard
if np.all(
np.logical_or(
is_wildcard, (input_match_candidate == pattern)
)
):
return True
return False

Answer 2

由于您的搜索空间非常小，因此我们不必担心内存错误，只需解开窗口视图即可。

首先，您需要一个模式中值位置的掩码

mask
array([[False, False,  True,  True, False, False],
[False, False,  True,  True, False, False],
[ True,  True,  True,  True,  True,  True],
[ True,  True,  True,  True,  True,  True],
[False, False,  True,  True, False, False],
[False, False,  True,  True, False, False]], dtype=bool)

然后，您需要一个包含这些位置的值的数组：

val = np.array([ 3.,  4.,  3.,  4.,  3.,  3.,  3.,  4.,  4.,  4.,
3.,  3.,  3.,  4.,  4.,  4.,  3.,  4.,  3.,  4.])

然后，您需要在输入上有一个滑动窗口。 最容易使用的实现是skimage.util.view_as_windows但你可以在这里使用我的纯numpy实现

windows = skimage.util.view_as_windows(input, pattern.shape)
# or
windows = window_nd(input, pattern.shape)

现在，通常在这里做windows[mask]会很危险 - 如果你卷积许多窗口，它可以创建一个巨大的数组。 但是我们在这里可以拥有的最多窗口是 12*6 = 72，我们不必担心这一点。

loc = np.where(np.all(window[mask] == val, axis = -1))

现在loc是匹配窗口左上角的坐标。

或者应该是。 也许提供一个可以复制/粘贴到解释器的测试用例？