如何在矩阵中查找邻居？
这里有一个7x7的矩阵：
11 21 31 41 51 61 71
12 22 32 42 52 62 72
13 23 33 43 53 63 73
14 24 34 44 54 64 74
15 25 35 45 55 65 75
16 26 36 46 56 66 76
17 27 37 47 57 67 77
数字 11, 21, 33 等等是这些位置的值。如果给定一个半径、行号和列号，怎么找到邻居呢？
比如，函数 neighbors(radius = 1, rowNumber = 3, columnNumber = 3) 应该返回一个矩阵：
22 32 42
23 33 43
24 34 44
function neighbors(radius = 2, rowNumber = 3, columnNumber = 3) 应该返回一个矩阵：
11 21 31 41 51
12 22 32 42 52
13 23 33 43 53
14 24 34 44 54
15 25 35 45 55
当邻居超出边界时，它的值应该是0。比如，function neighbors(radius = 2, rowNumber = 1, columnNumber = 1) 应该返回一个矩阵：
0 0 0 0 0
0 0 0 0 0
0 0 11 21 31
0 0 12 22 32
0 0 13 23 33
我考虑了这个问题三天，但还是没能找到解决方案。
7 个回答
1
这个问题其实和在特定位置创建一个正方形（或者说是n维的长方体）遮罩是一样的。
Raster Geometry这个包提供了创建n维长方体的方法，可以通过raster_geometry.nd_cuboid()来实现。
下面是一个简化的版本：
def neighbors_sq(
position,
shape,
size):
"""Generate mask of given size at given position in an array of given shape."""
assert len(position) == len(shape)
n = len(shape)
semisizes = (size,) * n
mask = np.zeros(shape, dtype=np.bool_)
# generate all slicing around the position
slicing = tuple(
slice(max(int(x - s), 0), min(int(x + s + 1), d))
for x, s, d in zip(position, semisizes, shape))
mask[slicing] = True
return mask
我们可以想出几种不同的方法：
import scipy.ndimage
def neighbors_sq_dilate(
position,
shape,
size):
assert len(position) == len(shape)
n = len(shape)
semisizes = (size,) * n
mask = np.zeros(shape, dtype=np.bool_)
mask[position] = True
mask = scipy.ndimage.binary_dilation(
mask,
iterations=size,
structure=scipy.ndimage.generate_binary_structure(n, n))
return mask
- 使用逐步应用遮罩的方法（这种方法更容易推广到非长方体的邻域，比如超椭球体，包括球体，具体可以参考这里）。
def neighbors_sq_mask(
position,
shape,
size):
assert len(position) == len(shape)
n = len(shape)
semisizes = (size,) * n
# genereate the grid for the support points
# centered at the position indicated by position
grid = [slice(-x0, dim - x0) for x0, dim in zip(position, shape)]
position = np.ogrid[grid]
mask = np.ones(shape, dtype=np.bool_)
# apply consecutive rectangular masks
for x_i, semisize in zip(position, semisizes):
mask *= (np.abs(x_i) <= semisize)
return mask
- 使用手动循环（为了简单起见，这个方法仅限于二维，且不容易写成N维的形式，以便Numba在非Python模式下加速——这可能需要步幅设置）。
def neighbors_sq_loop(
position,
shape,
size):
assert len(position) == len(shape)
n = len(shape)
mask = np.zeros(shape, dtype=np.bool_)
for i in range(
max(int(position[0] - size), 0),
min(int(position[0] + size + 1), shape[0])):
for j in range(
max(int(position[1] - size), 0),
min(int(position[1] + size + 1), shape[1])):
mask[i, j] = True
return mask
- 使用Numba加速的手动循环（和上面的方法一样，但进行了加速）：
import numba as nb
neighbors_sq_loop_nb = nb.njit(neighbors_sq_loop)
neighbors_sq_loop_nb.__name__ = "neighbors_sq_loop_nb"
这些方法都能得到相同的结果：
import matplotlib.pyplot as plt
funcs = neighbors_sq, neighbors_sq_mask, neighbors_sq_dilate, neighbors_sq_loop, neighbors_sq_loop_nb
fig, axs = plt.subplots(1, len(funcs), squeeze=False, figsize=(4 * len(funcs), 4))
d = 2365
n = 2
shape = (d,) * n
position = (d // 2,) * n
size = (d // 10)
base = neighbors_sq(position, shape, size)
for i, func in enumerate(funcs):
arr = func(position, shape, size)
axs[0, i].imshow(arr)
但是它们的执行时间不同，下面的例子说明了这一点（总之，时间数据要谨慎看待）：
base = neighbors_sq(position, shape, size)
for func in funcs:
print(f"{func.__name__:20s}", np.allclose(base, arr), end=" ")
%timeit -o func(position, shape, size)
# neighbors_sq True 1000 loops, best of 5: 489 µs per loop
# neighbors_sq_mask True 1000 loops, best of 5: 1.63 ms per loop
# neighbors_sq_dilate True 10 loops, best of 5: 99.1 ms per loop
# neighbors_sq_loop True 10 loops, best of 5: 32.9 ms per loop
# neighbors_sq_loop_nb True 1000 loops, best of 5: 635 µs per loop
结果显示，切片的方法在速度上明显更快（至少在这些输入大小下，可能对大多数输入也适用）。 而循环的方法灵活性不如其他方法（需要为多维情况进行调整），而且速度也不特别快，除非用Numba加速，但即使加速后也可能不是最快的。
想了解如何在球形邻域中寻找邻居，而不是正方形邻域，可以查看这里。
1
我喜欢在对二维数组进行操作时使用边界检查函数。这个代码虽然不完全符合你的需求（它是从左上角开始的），但应该能帮助你更进一步。
matrix = [
[11, 21, 31, 41, 51, 61, 71],
[12, 22, 32, 42, 52, 62, 72],
[13, 23, 33, 43, 53, 63, 73],
[14, 24, 34, 44, 54, 64, 74],
[15, 25, 35, 45, 55, 65, 75],
[16, 26, 36, 46, 56, 66, 76],
[17, 27, 37, 47, 57, 67, 77] ]
def in_bounds(matrix, row, col):
if row < 0 or col < 0:
return False
if row > len(matrix)-1 or col > len(matrix)-1:
return False
return True
def neighbors(matrix, radius, rowNumber, colNumber):
for row in range(radius):
for col in range(radius):
if in_bounds(matrix, rowNumber+row, colNumber+col):
print str(matrix[rowNumber+row][colNumber+col]) + " ",
print ""
neighbors(matrix, 2, 1, 1)
3
我最开始的解决方案是不对的，@Gnijuohz的方案是正确的。下面的内容就是@Gnijuohz的解决方案，只不过这个函数的第一个参数是一个矩阵（也就是一个包含多个列表的列表），而且原本用来生成列表的那种写法被换成了嵌套的for循环。
def neighbors(mat, row, col, radius=1):
rows, cols = len(mat), len(mat[0])
out = []
for i in xrange(row - radius - 1, row + radius):
row = []
for j in xrange(col - radius - 1, col + radius):
if 0 <= i < rows and 0 <= j < cols:
row.append(mat[i][j])
else:
row.append(0)
out.append(row)
return out
6
这段代码接受一个二维数组（也就是矩阵）作为输入，然后返回一个包含所有邻居元素的列表。
输入：
arr = [['a', 'b', 'c'],
['d', 'e', 'f'],
['g', 'h', 'k']]
输出：
[{'value': 'a', 'neighbors': ['b', 'd']}
{'value': 'b', 'neighbors': ['c', 'e', 'a']}
{'value': 'c', 'neighbors': ['f', 'b']}
{'value': 'd', 'neighbors': ['a', 'e', 'g']}
{'value': 'e', 'neighbors': ['b', 'f', 'h', 'd']}
{'value': 'f', 'neighbors': ['c', 'k', 'e']}
{'value': 'g', 'neighbors': ['d', 'h']}
{'value': 'h', 'neighbors': ['e', 'k', 'g']}
{'value': 'k', 'neighbors': ['f', 'h']}]
更多详细信息请查看这里 -> GitHub
def find_neighbours(arr):
neighbors = []
for i in range(len(arr)):
for j, value in enumerate(arr[i]):
if i == 0 or i == len(arr) - 1 or j == 0 or j == len(arr[i]) - 1:
# corners
new_neighbors = []
if i != 0:
new_neighbors.append(arr[i - 1][j]) # top neighbor
if j != len(arr[i]) - 1:
new_neighbors.append(arr[i][j + 1]) # right neighbor
if i != len(arr) - 1:
new_neighbors.append(arr[i + 1][j]) # bottom neighbor
if j != 0:
new_neighbors.append(arr[i][j - 1]) # left neighbor
else:
# add neighbors
new_neighbors = [
arr[i - 1][j], # top neighbor
arr[i][j + 1], # right neighbor
arr[i + 1][j], # bottom neighbor
arr[i][j - 1] # left neighbor
]
neighbors.append({
"value": value,
"neighbors": new_neighbors})
return neighbors
8
在其他编程语言中可能会比较难，但在Python里这非常简单。这里有一个可以满足你需求的函数：
def neighbors(radius, row_number, column_number):
return [[a[i][j] if i >= 0 and i < len(a) and j >= 0 and j < len(a[0]) else 0
for j in range(column_number-1-radius, column_number+radius)]
for i in range(row_number-1-radius, row_number+radius)]
这里有一个二维列表：
a = [[ 11, 21, 31, 41, 51, 61, 71],
[ 12, 22, 32, 42, 52, 62, 72],
[ 13, 23, 33, 43, 53, 63, 73],
[ 14, 24, 34, 44, 54, 64, 74],
[ 15, 25, 35, 45, 55, 65, 75],
[ 16, 26, 36, 46, 56, 66, 76],
[ 17, 27, 37, 47, 57, 67, 77]]
可以查看一下列表推导式的相关内容。
更新了解决方案中缺失的“和” - 请查看一下。