寻找二维阵列中的最佳位置

Question

我正在使用行数和列数相同大小的 2D numpy 数组。我想找到最佳位置，其中每边 2n + 1 将导致最大可能的总和。 2(n) + 1 这里表示相邻元素。

所以二维数组：

[[0 0 0 0 0]
 [0 1 1 1 0]
 [0 1 1 1 0]
 [0 1 1 1 0]
 [0 0 0 0 0]]

在这个数组中， (2, 2) 处的元素似乎是 2(1) + 1 处的最佳位置。 因此，在 n = 2 时，理想位置是相同的。但是，在 n = 3 时，它将是 none，因为这将超出 2D 数组 maces。

这是我解决问题的方法，但没有给出所需的输出。

def find_target_location(arr, area):
    sum_1 = 0
    sum_2 = sum_1
    square_area = (2 * area) + 1

    if square_area > len(arr):
        return None

    for row in range(len(arr)):
        for index in range(len(arr[row])):
            area_forward = arr[row: square_area + row, index: square_area + index]
            # This is where I am doing wrong but cannot figure out.
            area_previous = arr[row - len(arr): -row -1, row - len(arr), -index -1]

            sum_area_forward = sum(sum(area_forward))
            sum_area_backward = sum(sum(area_backward))
            sum_2 = sum_area_forward + sum_area_backward
            if sum_2 > sum_1:
                sum_1 = sum_2
                optimal_location = (row, index)
    return optimal_location

Answer 1

直接邻居的总和

如果您正在查找具有最大直接相邻邻居值总和的元素的索引：

from numpy.lib.stride_tricks import sliding_window_view as windows

np.unravel_index(np.pad(windows(x, (3, 3)).sum(axis=(2, 3)), 1).argmax(), x.shape)

但请注意，此解决方案在计算其相邻值的总和时会计算元素本身的值。

2n+1 方形邻域中的邻居之和

因此，您想对 2n+1 “半径”邻域中的所有邻居求和：

n = 1
radius = 2*n + 1

# x = np.array(...)
neighbor_sums = windows(x, (radius, radius)).sum(axis=(2, 3))
padded = np.pad(neighbor_sums, radius // 2)

optimal_location = np.unravel_index(padded.argmax(), padded.shape)

我只是对此进行了测试，但是我认为应该有效。请注意，此处将选择最大值的第一个索引，因此，如果您有多个“最佳”位置，那么您将始终以出现的“第一个”位置结束（当从左上角到下角搜索时）正确的）。

我不认为填充是绝对必要的，但它确实可以让您避免进行一些繁琐的算术，并且如果您想在求和相邻值时不计算每个单元格的值，那么它也会有所帮助，例如所以：

padded -= x
adjusted_neighbor_sums = np.clip(padded, 0, padded.max())

optimal_location # = same as above

如何在没有 stride_tricks 的情况下做到这

一点 归根结底，np.lib.stride_tricks.sliding_window_view 只是聪明的索引。

令 x 为这个 (5, 5) 数组：

array([[0, 0, 0, 0, 0],
       [0, 1, 2, 3, 0],
       [0, 4, 5, 6, 0],
       [0, 7, 8, 9, 0],
       [0, 0, 0, 0, 0]])

假设 n = 1，因此您所在社区的面积为 2n+ 1 = 3。现在想象一下在 x 上放置一个 (3, 3) “窗口”，将窗口的左上角与 x< 的左上角匹配/代码>。该“窗口”围绕着这些值。

0 0 0
0 1 2
0 4 5

这些值的列索引是什么？它们是(0, 1, 2)。

现在，如果我们在 x 上滑动 (3, 3) 窗口，我们无法移动该窗口使其悬挂在 x 的任何一侧。因此，我们可以将此窗口移动到 x 顶部的最右边，使得窗口的左上角位于索引 2 处。这样，窗口的右上角就会出现与 x 的右上角对齐。该窗口现在围绕着

0 0 0
2 3 0
5 6 0

这些值的列索引是什么？它们是(2,3,4)。

让我们创建一个元组列表，它可以代表我们在 x 顶部滑动时选择的列：

n = 1
r = 2 * n + 1

# the possible index values when indexing into `x`; (0, 1, 2, 3, 4)
all_x_idxs = [*range(len(x))]

# the column indices when sliding the window across the top of `x`
idxs = list(zip(*[all_x_idxs[i:i+r] for i in range(r)]))

输出：

>>> idxs
[(0, 1, 2), (1, 2, 3), (2, 3, 4)]

Since x< /code> 是方形的，当我们想要将窗口向下滑动一行时，这些列索引也适用于行（想象一下在 x 上滑动窗口，就像阅读书页一样用英文写——从左到右，从上到下）。

如果您采用 idxs 的笛卡尔积，这将为您提供所有 9 个窗口的行索引和列索引：

>>> [(rows, cols) for rows in idxs for cols in idxs]
[((0, 1, 2), (0, 1, 2)),
 ((0, 1, 2), (1, 2, 3)),
 ((0, 1, 2), (2, 3, 4)),
 ((1, 2, 3), (0, 1, 2)),
 ((1, 2, 3), (1, 2, 3)),
 ((1, 2, 3), (2, 3, 4)),
 ((2, 3, 4), (0, 1, 2)),
 ((2, 3, 4), (1, 2, 3)),
 ((2, 3, 4), (2, 3, 4))]

现在，最后一件事：对于 (rows, cols) 的每个元组code>，我们需要再次使用笛卡尔积来获取每个 (3, 3) 窗口的所有 9 个索引对。例如，(3, 3) 窗口的 9 个索引锚定在我们开始的 x 的左上角，

[[(0, 0), (0, 1), (0, 2)],
 [(1, 0), (1, 1), (1, 2)],
 [(2, 0), (2, 1), (2, 2)]]

使用这些元组索引到 x< /code>：

>>> [[x[i, j] for i in (0, 1, 2)] for j in (0, 1, 2)]
[[0, 0, 0],
 [0, 1, 4],
 [0, 2, 5]]

现在我们可以将上面的内容包装在另外两个嵌套列表推导式中，以迭代 (rows, cols) 元组：

>>> np.array([[[[x[i, j] for j in cols] for i in rows] for cols in idxs] for rows in idxs])
array([[[[0, 0, 0],
         [0, 1, 2],
         [0, 4, 5]],

        [[0, 0, 0],
         [1, 2, 3],
         [4, 5, 6]],

        [[0, 0, 0],
         [2, 3, 0],
         [5, 6, 0]]],


       [[[0, 1, 2],
         [0, 4, 5],
         [0, 7, 8]],

        [[1, 2, 3],
         [4, 5, 6],
         [7, 8, 9]],

        [[2, 3, 0],
         [5, 6, 0],
         [8, 9, 0]]],


       [[[0, 4, 5],
         [0, 7, 8],
         [0, 0, 0]],

        [[4, 5, 6],
         [7, 8, 9],
         [0, 0, 0]],

        [[5, 6, 0],
         [8, 9, 0],
         [0, 0, 0]]]])

这会产生 (3, 3, 3, 3)< /code> 数组结束然后您可以将最后两个轴相加。

但这种理解是糟糕。幸运的是，np.ix_() 函数可以非常轻松地以适合 高级索引：

>>> np.ix_((0, 1, 2), (0, 1, 2))
(array([[0],
        [1],
        [2]]),
 array([[0, 1, 2]]))

现在获取我们的窗口要容易得多（连同设置数据）：

n = 1
r = 2 * n + 1

# the possible index values when indexing into `x`; (0, 1, 2, 3, 4)
all_x_idxs = [*range(len(x))]

# the column indices when sliding the window across the top of `x`
idxs = list(zip(*[all_x_idxs[i:i+r] for i in range(r)]))

# all (3, 3) windows of x
np.array([[x[np.ix_(rows, cols)] for cols in idxs] for rows in idxs])

这会产生与上面相同的结果。从那里，您可以将总和应用于最后两个轴（每个单独的二维数组的行和列）。

当然，这仍然是一个看起来很糟糕的理解......并且 np.lib.stride_tricks.sliding_window_view 抽象掉了所有索引废话。