使用numpy优化水平和垂直邻接的计算

Question

我有以下细胞：

cells = np.array([[1, 1, 1],
                  [1, 1, 0],
                  [1, 0, 0],
                  [1, 0, 1],
                  [1, 0, 0],
                  [1, 1, 1]])

我想计算水平和垂直邻接以获得这个结果：

# horizontal adjacency 
array([[3, 2, 1],
       [2, 1, 0],
       [1, 0, 0],
       [1, 0, 1],
       [1, 0, 0],
       [3, 2, 1]])

# vertical adjacency 
array([[6, 2, 1],
       [5, 1, 0],
       [4, 0, 0],
       [3, 0, 1],
       [2, 0, 0],
       [1, 1, 1]])

实际的解决方案如下所示：

def get_horizontal_adjacency(cells):
    adjacency_horizontal = np.zeros(cells.shape, dtype=int)
    for y in range(cells.shape[0]):
        span = 0
        for x in reversed(range(cells.shape[1])):
            if cells[y, x] > 0:
                span += 1
            else:
                span = 0
            adjacency_horizontal[y, x] = span
    return adjacency_horizontal

def get_vertical_adjacency(cells):
    adjacency_vertical = np.zeros(cells.shape, dtype=int)
    for x in range(cells.shape[1]):
        span = 0
        for y in reversed(range(cells.shape[0])):
            if cells[y, x] > 0:
                span += 1
            else:
                span = 0
            adjacency_vertical[y, x] = span
    return adjacency_vertical

该算法基本上是（对于水平邻接）：

1. 循环遍历行
2. 向后循环列
3. 如果像元的x、y值不为零，则实际跨度加1
4. 如果像元的 x、y 值为零，则将实际跨度重置为零
5. 将跨度设置为结果数组的新 x, y 值

由于我需要对所有数组元素循环两次，这对于较大的数组（例如图像）来说很慢。

有没有办法使用矢量化或其他一些 numpy 魔法来改进算法？

概括：

Joni 和 Mark Setchell 提出了很好的建议！

我创建了一个小型 Repo，其中包含示例图像和带有比较的 python 文件。结果令人惊讶：

• 原始方法：3.675 s
• 使用 Numba：0.002 秒
• 使用 Cython：0.005 秒

Answer 1

我用 Numba 进行了一次非常快速的尝试，但还没有彻底检查过，尽管结果似乎是正确的：

\n

#!/usr/bin/env python3\n\n# /sf/ask/4889803481/\n# magick -size 1920x1080 xc:black -fill white -draw "circle 960,540 960,1040" -fill black -draw "circle 960,540 960,800" a.png\n\nimport cv2\nimport numpy as np\nimport numba as nb\n\ndef get_horizontal_adjacency(cells):\n    adjacency_horizontal = np.zeros(cells.shape, dtype=int)\n    for y in range(cells.shape[0]):\n        span = 0\n        for x in reversed(range(cells.shape[1])):\n            if cells[y, x] > 0:\n                span += 1\n            else:\n                span = 0\n            adjacency_horizontal[y, x] = span\n    return adjacency_horizontal\n\n@nb.jit(\'void(uint8[:,::1], int32[:,::1])\',parallel=True)\ndef nb_get_horizontal_adjacency(cells, result):\n    for y in nb.prange(cells.shape[0]):\n        span = 0\n        for x in range(cells.shape[1]-1,-1,-1):\n            if cells[y, x] > 0:\n                span += 1\n            else:\n                span = 0\n            result[y, x] = span\n    return \n\n# Load image\nim = cv2.imread(\'a.png\', cv2.IMREAD_GRAYSCALE)\n\n%timeit get_horizontal_adjacency(im)\n\nresult = np.zeros((im.shape[0],im.shape[1]),dtype=np.int32)\n%timeit nb_get_horizontal_adjacency(im, result)\n

\n

如果工作正常的话，计时效果很好，显示出 4000 倍的加速：

\n

In [15]: %timeit nb_get_horizontal_adjacency(im, result)\n695 \xc2\xb5s \xc2\xb1 9.12 \xc2\xb5s per loop (mean \xc2\xb1 std. dev. of 7 runs, 1000 loops each)\n\nIn [17]: %timeit get_horizontal_adjacency(im)\n2.78 s \xc2\xb1 44.2 ms per loop (mean \xc2\xb1 std. dev. of 7 runs, 1 loop each)\n

\n

输入

\n

输入图像以 1080p 尺寸创建，即 1920x1080，使用ImageMagick使用：

\n

magick -size 1920x1080 xc:black -fill white -draw "circle 960,540 960,1040" -fill black -draw "circle 960,540 960,800" a.png\n

\n

\n

输出（对比度调整）

\n

\n