Getting sum of adjacent elements of a matrix

Question

I have a matrix eg.

[[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]]

For each element in the matrix, I am trying to get the sum of its adjacent diagonal elements and the sum of its adjacent horizontal and vertical elements.

Taking the 3 in the middle of the matrix for example, I am trying to calculate the sum of the diagonally adjacent elements (the 1's) and the horizontally and vertically adjacent elements (the 2's). For corner and edge cases, I want to disregard the areas where there are no elements eg.(for the 4 in the upper left, I'd want to get the sum of the diagonally adjacent 1 and the sum of the horizontally and vertically adjacent 5's.

What would be the most efficient way to do this in python?

So far i've come up with

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)]

to get the indices but these don't take into account the edge and corner cases.

Answer 1

The right tool to solve this task appears to be convolution. You only need to define the filters that will be applied in each position ("sum of diagonal neighbors" or "sum of vertical/horizontal neighbors") and you're done.

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]])

Here's how the filters look like:

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

You can think of 2D convolution as of shifting the filter across your matrix and calculating in each position the sum of the element-wise multiplication. Strictly speaking, the filters need to be mirrored, but in your case they are symmetric anyway. Here's a random illustration of the principle as found on the web:

The only difference to your case is that we want to place the filters everywhere, including the "boundary" or "corner" positions. This can be achieved by zero-padding the original matrix D such that the center of the filter can be placed e.g. in position (0,0).

Good news! It's already implemented in Numpy/Scipy and it's a very efficient implementation! Now you just construct a matrix by convolving D with a filter h.

>>> 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]])

From these matrices you can read off the required sums in each position. E.g. the central element in your original matrix D, i.e. D[2,2] is surrounded by 4 ones on the diagonals and 4 twos on the horizontal/vertical adjacency. The entries in the convolution output at the position (2,2) are therefore 4 and 8. The position D[0,0] has only one diagonal neighbor (1) and two horizontal/vertical neighbors (5 and 5). The entries in the convolution output matrices are as expected 1 and 10.

Answer 2

As it turns out, I realized there's a much simpler way to do this than described in my previous answer.

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]]))

Results in:

[[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]]

Answer 3

Ignoring the corner cases for a moment, one way to do this is to overlay shifted versions of the matrices atop one another.

For instance, given a matrix m, we sum over the rows:

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

Running this on your matrix, we obtain:

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

We can then do something similar for the columns. For speed, I suggest you specialize the code I wrote for rows, but I'm going to be lazy and do it on the transpose:

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

Running this on your matrix, we obtain:

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

Now we need to combine these matrices together. Let's shave off the extra rows/columns to produce 3x3 matrices, then sum them together:

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

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

Just as desired!

...But how can we account for the boundaries? Simply pad your matrix with zeroes!

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

Which gives:

[[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]]

---

To sum diagonals, it's simply:

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

Which produces:

[[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]]

Answer 4

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)])

And now apply the same principle for the sum of adjacent numbers.

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]]

If you need the sum of the diagonals and verticals:

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]]