使用numpy优化水平和垂直邻接计算 [英] Optimize the calculation of horizontal and vertical adjacency using numpy

问题描述

我有以下单元格：

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值

因为我需要在所有数组元素上循环两次，所以对于较大的数组(例如图像)，这会很慢。

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

摘要：

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

我使用示例图像和带有比较的python文件创建了一个small Repo。结果令人震惊：

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

推荐答案

我用Numba快速尝试了一下，但没有检查得太彻底，尽管结果似乎大致正确：

#!/usr/bin/env python3

# https://stackoverflow.com/q/69854335/2836621
# magick -size 1920x1080 xc:black -fill white -draw "circle 960,540 960,1040" -fill black -draw "circle 960,540 960,800" a.png

import cv2
import numpy as np
import numba as nb

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

@nb.jit('void(uint8[:,::1], int32[:,::1])',parallel=True)
def nb_get_horizontal_adjacency(cells, result):
    for y in nb.prange(cells.shape[0]):
        span = 0
        for x in range(cells.shape[1]-1,-1,-1):
            if cells[y, x] > 0:
                span += 1
            else:
                span = 0
            result[y, x] = span
    return 

# Load image
im = cv2.imread('a.png', cv2.IMREAD_GRAYSCALE)

%timeit get_horizontal_adjacency(im)

result = np.zeros((im.shape[0],im.shape[1]),dtype=np.int32)
%timeit nb_get_horizontal_adjacency(im, result)

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

In [15]: %timeit nb_get_horizontal_adjacency(im, result)
695 µs ± 9.12 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

In [17]: %timeit get_horizontal_adjacency(im)
2.78 s ± 44.2 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

输入

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

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

输出(对比度调整)

这篇关于使用numpy优化水平和垂直邻接计算的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！