获取矩阵相邻元素之和

Question

我有一个矩阵，例如：

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

针对矩阵中的每个元素，我试图获取其相邻对角线元素的总和以及其相邻水平和垂直元素的总和。

以矩阵中间的3为例，我试图计算对角线相邻元素（1）和水平和垂直相邻元素（2）的总和。 对于角落和边缘情况，我希望忽略没有元素的区域，例如（对于左上角的4，我想要获取对角线相邻的1和水平和垂直相邻的5的总和）。

在Python中，最有效的方法是什么？

到目前为止，我想到了：

diagonals = lambda x,y:[(x-1, y-1), (x-1,y+1), (x+1,y-1), (x+1,y+1)]
horiz_vert= lambda x,y:[(x,y+1), (x,y-1), (x+1,y), (x-1,y)]

要获取索引，但这些不考虑边缘和角落的情况。

- Zito Relova

---

如果您没有使用错误的算法，性能应该不会太差。您尝试过基准测试吗？ - user202729

Answer 1

这个任务的正确工具似乎是卷积。您只需要定义将在每个位置应用的滤波器（“对角邻居之和”或“垂直/水平邻居之和”），然后就完成了。

import numpy as np
import scipy.signal

D = np.array([[4,5,0,0,0],
              [5,1,2,1,0],
              [0,2,3,2,0],
              [0,1,2,1,0],
              [0,0,0,0,0]])

h_diag = np.array([[1,0,1], [0,0,0], [1,0,1]])
h_hv   = np.array([[0,1,0], [1,0,1], [0,1,0]])

这就是过滤器的外观：

>>> h_diag
array([[1, 0, 1],
       [0, 0, 0],
       [1, 0, 1]])
>>> h_hv
array([[0, 1, 0],
       [1, 0, 1],
       [0, 1, 0]])

你可以将2D卷积视为在矩阵上移动滤波器，并在每个位置计算元素逐个相乘的总和。严格来说，滤波器需要镜像，但在您的情况下它们已经对称了。以下是从网络上找到的该原理的随机示意图：

唯一与您的情况不同之处在于，我们希望将过滤器放置在所有位置，包括“边界”或“角落”位置。这可以通过用零填充原始矩阵D来实现，使得过滤器的中心可以放置在例如位置(0,0)。

好消息！它已经在Numpy/Scipy中实现，并且是非常高效的实现！现在，您只需通过使用过滤器h对D进行卷积来构造矩阵即可。

>>> scipy.signal.convolve2d(D, h_diag, mode='same')
array([[1, 7, 2, 2, 1],
       [7, 7, 9, 3, 2],
       [2, 9, 4, 4, 2],
       [2, 3, 4, 3, 2],
       [1, 2, 2, 2, 1]])

>>> scipy.signal.convolve2d(D, h_hv, mode='same')
array([[10,  5,  7,  1,  0],
       [ 5, 14,  5,  4,  1],
       [ 7,  5,  8,  5,  2],
       [ 1,  4,  5,  4,  1],
       [ 0,  1,  2,  1,  0]])

从这些矩阵中，您可以在每个位置上读取所需的总和。例如，在原始矩阵 D 中，即 D [2,2] 的中心元素被对角线上的 4 个一和水平/垂直邻接的 4 个二所包围。因此，卷积输出在位置 (2,2) 的条目为 4 和 8。位置 D[0,0] 只有一个对角线邻居 (1) 和两个水平/垂直邻居 (5 和 5)。卷积输出矩阵中的条目如预期的那样是 1 和 10。

- Pavel

Answer 2

def is_inbounds(x, y, length):
    return (0 <= x < length and 0 <= y < length)


def total_of_diags(m, x, y):
    size = len(m)
    return sum([(m[x - 1][y - 1]) * is_inbounds(x, y, size),
                (m[x - 1][y + 1] ) * is_inbounds(x, y, size),
                (m[x + 1][y - 1] ) * is_inbounds(x, y, size),
                (m[x + 1][y + 1] ) * is_inbounds(x, y, size)])

现在将同样的原理应用于相邻数字的总和。

- Tynan J

Answer 3

暂时忽略边角情况，一种方法是将移位后的矩阵叠加在一起。

例如，给定一个矩阵m，我们对行求和：

def collapse_rows(m):
    # Select odd/even rows and then
    # pad top and bottom with row of zeroes
    e = np.pad(m[::2],  [(1,1), (0,0)], 'constant')
    o = np.pad(m[1::2], [(1,1), (0,0)], 'constant')

    # Sum together adjacent odd/even rows
    E = (e[:-1] + e[1:])[1:-1]
    O = (o[:-1] + o[1:])[1:-1]

    # Interweave rows
    m2 = np.empty((E.shape[0] + O.shape[0], m.shape[1]), dtype=m.dtype)
    m2[0::2] = E
    m2[1::2] = O

    return m2

在您的矩阵上运行此代码，我们得到：

[[4, 7, 3, 2, 0],
 [5, 2, 4, 2, 0],
 [0, 2, 3, 2, 0]]

我们可以类似地处理 列。为了速度，我建议您专门针对行编写的代码进行优化，但我会懒一点，在转置上进行操作：

def collapse_columns(m):
    return collapse_rows(m.T).T

在您的矩阵上运行此代码，我们得到：

[[4, 5, 0],
 [7, 2, 2],
 [3, 4, 3],
 [2, 2, 2],
 [0, 0, 0]]

现在我们需要将这些矩阵组合在一起。让我们删掉多余的行/列，生成3x3的矩阵，然后将它们相加：

result = collapse_rows(m)[:, 1:-1] + collapse_columns(m)[1:-1, :]

[[14,  5,  4],
 [ 5,  8,  5],
 [ 4,  5,  4]])

正如所期望的那样！

...但是我们如何考虑边界呢？只需用零填充矩阵即可！

m_pad = np.pad(m, 1, 'constant')
result = collapse_rows(m_pad)[:, 1:-1] + collapse_columns(m_pad)[1:-1, :]

这将会给出：

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

---

要计算对角线之和，简单来说：

m_pad = np.pad(m, 1, 'constant')
result = collapse_columns(collapse_rows(m_pad))

这会产生：

[[1, 7, 2, 2, 1],
 [7, 7, 9, 3, 2],
 [2, 9, 4, 4, 2],
 [2, 3, 4, 3, 2],
 [1, 2, 2, 2, 1]]

- Mateen Ulhaq

Answer 4

事实证明，我意识到有一种比我之前的回答描述的方法更简单的方式来完成这个任务。

def get_adj(m):
    m_pad = np.pad(m, 1, 'constant')

    x = m_pad[:, :-2] + m_pad[:, 2:]
    y = m_pad[:-2] + m_pad[2:]

    hv = x[1:-1] + y[1:-1]
    diag = y[:, :-2] + y[:, 2:]

    return hv, diag

print(*get_adj(
    [[4,5,0,0,0],
     [5,1,2,1,0],
     [0,2,3,2,0],
     [0,1,2,1,0],
     [0,0,0,0,0]]))

结果为：

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

[[1, 7, 2, 2, 1],
 [7, 7, 9, 3, 2],
 [2, 9, 4, 4, 2],
 [2, 3, 4, 3, 2],
 [1, 2, 2, 2, 1]]

- Mateen Ulhaq

Answer 5

def is_inside(x, y):
    return 0 <= x < len(m[0]) and 0 <= y < len(m) 

def diagonal_sum(x, y):
    return sum([m[x - 1][y - 1] if is_inside(x - 1, y - 1) else 0,
                m[x - 1][y + 1] if is_inside(x - 1, y + 1) else 0,
                m[x + 1][y - 1] if is_inside(x + 1, y - 1) else 0,
                m[x + 1][y + 1] if is_inside(x + 1, y + 1) else 0])

def vertical_sum(x, y):
    return sum([m[x][y - 1] if is_inside(x, y - 1) else 0,
                m[x][y + 1] if is_inside(x, y + 1) else 0,
                m[x - 1][y] if is_inside(x - 1, y) else 0,
                m[x + 1][y] if is_inside(x + 1, y) else 0])

m = [[4,5,0,0,0],
     [5,1,2,1,0],
     [0,2,3,2,0],
     [0,1,2,1,0],
     [0,0,0,0,0]]

diagonal = []
vertical = []
for i in range(len(m)):
    diagonal.append([])
    vertical.append([])
    for j in range(len(m[0])):
        diagonal[i].append(diagonal_sum(i, j))
        vertical[i].append(vertical_sum(i, j))

print(diagonal)
# prints:
#
# [[1, 7, 2, 2, 1],
#  [7, 7, 9, 3, 2],
#  [2, 9, 4, 4, 2],
#  [2, 3, 4, 3, 2],
#  [1, 2, 2, 2, 1]]

print(vertical)
# prints:
#
# [[10, 5,  7, 1, 0],
#  [5, 14,  5, 4, 1],
#  [7,  5,  8, 5, 2],
#  [1,  4,  5, 4, 1],
#  [0,  1,  2, 1, 0]]

如果您需要对角线和垂直线的总和：

def is_inside(x, y):
    return 0 <= x < len(m[0]) and 0 <= y < len(m) 

def neighbour_sum(x, y):
    r = 0
    for i in range(y - 1, y + 2):
        for j in range(x - 1, x + 2):
            if is_inside(i, j):
                r += m[i][j]
    return r

m = [[4,5,0,0,0],
     [5,1,2,1,0],
     [0,2,3,2,0],
     [0,1,2,1,0],
     [0,0,0,0,0]]

result = []
for i in range(len(m)):
    result.append([])
    for j in range(len(m[0])):
        result[i].append(neighbour_sum(i, j))

print(result)
# prints:
#
# [[15, 17,  9,  3,  1],
#  [17, 22, 16,  8,  3],
#  [9,  16, 15, 11,  4],
#  [3,   8, 11,  8,  3],
#  [1,   3,  4,  3,  1]]

- kiyah