elegant/faster 一种在图像上查找直线端点的方法？

Question

我一直在努力通过将数组操作的 for 循环替换为适当的 NumPy 函数来提高我的代码速度。

该函数的目的是获取一条直线的端点，这是255个中仅有的两个恰好有一个相邻像素的点。

有什么方法可以让我从 np.where 中获得两点，有条件或一些我不熟悉的 NumPy 函数可以完成这项工作？

def get_end_points(图片):

x1=-1
y1=-1
x2=-1
y2=-1
    for i in range(image.shape[0]):
        for j in range(image.shape[1]):
            if image[i][j]==255 and neighbours_sum(i,j,image) == 255:
                if x1==-1:
                    x1 = j
                    y1 = i
                else:
                    x2=j
                    y2=i
return x1,y1,x2,y2

Answer 1

编辑：我没有注意到你有灰度图像，但就想法而言，没有任何改变

我不能给你确切的解决方案，但我可以给你更快的方法来找到你想要的

1) a) 找到白色的索引（像素） [255,255,255]

indice =np.where(np.all(image==255, axis=2))

1) b) 围绕这一点做循环这更快，因为你没有做无用的循环

2)这个解决方案应该非常非常快，但是会很难编程

a) 找到 1)

中的索引

indice =np.where(np.all(image==255, axis=2))

b) 将索引数组在 X 轴上移动 +1 并添加到图像中

indices = =np.where(np.all(image==255, axis=2))
indices_up = # somehow add to all indexes in x dimension +1 (simply move it up)
add_up = image[indices]+image[indices_up]
# if in add_up matrix is array with(rgb channel) [510,510,510] # 255+255, then it has neightbour in x+1
# Note that you cant do it with image of dtype uint8, because 255 is max, adding up you will end up back at 255

你必须对所有邻居都这样做 -> x+1,x-1,y+1,y-1,x+1,y+1.... 这将是非常快速的艰难

EDIT2: 我能够制作一个脚本应该这样做，但你应该先测试它

import numpy as np
image =  np.array([[0, 0, 0,   0,    0, 0,   0,0,0],
                   [0, 0, 255, 0,    0, 0,   0,0,0],
                   [0, 0, 255, 0,  255, 0,   0,0,0],
                   [0, 0, 0,   255,0,   255, 0,0,0],
                   [0, 0, 0,   0,  0,   255, 0,0,0],
                   [0, 0, 0,   0,  0,   0,   0,0,0],
                   [0, 0, 0,   0,  0,   0,   0,0,0]])

image_f = image[1:-1,1:-1] # cut image

i = np.where(image_f==255) # find 255 in the cut image
x = i[0]+1 # calibrate x indexes for original image 
y = i[1]+1 # calibrate y indexes for original image
# this is done so you dont search in get_indexes() out of image 

def get_indexes(xx,yy,image):
    for i in np.where(image[xx,yy]==255):
        for a in i:
            yield xx[a],yy[a]


# Search for horizontal and vertical duplicates(neighbours)

for neighbours_index in get_indexes(x+1,y,image):
    print(neighbours_index )

for neighbours_index in get_indexes(x-1,y,image):
    print(neighbours_index )

for neighbours_index in get_indexes(x,y+1,image):
    print(neighbours_index )

for neighbours_index in get_indexes(x,y-1,image):
    print(neighbours_index )

Answer 2

我想我至少可以提供一个使用卷积的优雅解决方案。

我们可以通过将原始图像与 3x3 环进行卷积来寻找相邻像素的数量。然后如果中心像素也有一个白色像素，我们就可以确定线的末端是否在那里。

>>> import numpy as np
>>> from scipy.signal import convolve2d
>>> a = np.array([[0, 0, 0, 0, 0, 0, 0], [0, 1, 0, 0, 0, 0, 0], [0, 1, 0, 0, 0, 0, 0], [0, 0, 1, 0, 0, 0, 0], [0, 0, 0, 1, 0, 0, 0], [0, 0, 0, 0, 1, 0, 0], [0, 0, 0, 0, 1, 1, 0]])
>>> a
array([[0, 0, 0, 0, 0, 0, 0],
       [0, 1, 0, 0, 0, 0, 0],
       [0, 1, 0, 0, 0, 0, 0],
       [0, 0, 1, 0, 0, 0, 0],
       [0, 0, 0, 1, 0, 0, 0],
       [0, 0, 0, 0, 1, 0, 0],
       [0, 0, 0, 0, 1, 1, 0]])

>>> c = np.full((3, 3), 1)
>>> c[1, 1] = 0
>>> c
array([[1, 1, 1],
       [1, 0, 1],
       [1, 1, 1]])

>>> np.logical_and(convolve2d(a, c, mode='same') == 1, a == 1).astype(int)
array([[0, 0, 0, 0, 0, 0, 0],
       [0, 1, 0, 0, 0, 0, 0],
       [0, 0, 0, 0, 0, 0, 0],
       [0, 0, 0, 0, 0, 0, 0],
       [0, 0, 0, 0, 0, 0, 0],
       [0, 0, 0, 0, 0, 0, 0],
       [0, 0, 0, 0, 0, 0, 0]])

请随意查看各个组件产生的结果，但为了简洁起见，我没有在此处包括它们。正如您可能已经注意到的那样，它确实正确地拒绝了线条以两个相邻像素结尾的情况。

这当然可以转换为任意数量的行尾索引 np.where:

np.array(np.where(result))

Answer 3

这是一个卷积的解决方案：

import numpy as np
import scipy.signal

def find_endpoints(img):
    # Kernel to sum the neighbours
    kernel = [[1, 1, 1],
              [1, 0, 1],
              [1, 1, 1]]
    # 2D convolution (cast image to int32 to avoid overflow)
    img_conv = scipy.signal.convolve2d(img.astype(np.int32), kernel, mode='same')
    # Pick points where pixel is 255 and neighbours sum 255
    endpoints = np.stack(np.where((img == 255) & (img_conv == 255)), axis=1)
    return endpoints

# Test
img = np.zeros((1000, 1000), dtype=np.uint8)
# Draw a line from (200, 130) to (800, 370)
for i in range(200, 801):
    j = round(i * 0.4 + 50)
    img[i, j] = 255
print(find_endpoints(img))
# [[200 130]
#  [800 370]]

编辑：

您也可以考虑为此使用 Numba。该代码几乎就是您已有的代码，所以可能不是特别 "elegant"，但速度要快得多。例如，像这样：

import numpy as np
import numba as nb

@nb.njit
def find_endpoints_nb(img):
    endpoints = []
    # Iterate through every row and column
    for i in range(img.shape[0]):
        for j in range(img.shape[1]):
            # Check current pixel is white
            if img[i, j] != 255:
                continue
            # Sum neighbours
            s = 0
            for ii in range(max(i - 1, 0), min(i + 2, img.shape[0])):
                for jj in range(max(j - 1, 0), min(j + 2, img.shape[1])):
                    s += img[ii, jj]
            # Sum including self pixel for simplicity, check for two white pixels
            if s == 255 * 2:
                endpoints.append((i, j))
                if len(endpoints) >= 2:
                    break
        if len(endpoints) >= 2:
            break
    return np.array(endpoints)

print(find_endpoints_nb(img))
# [[200 130]
#  [800 370]]

这在我的电脑上运行得比较快：

%timeit find_endpoints(img)
# 34.4 ms ± 64.4 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
%timeit find_endpoints_nb(img)
# 552 µs ± 4 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

此外，它应该使用更少的内存。上面的代码假定只有两个端点。如果添加并行化，您可能会使其变得更快（尽管您必须进行一些更改，因为您将无法从并行线程修改列表 endpoints）。

elegant/faster 一种在图像上查找直线端点的方法？

An elegant/faster way to find the end points of a line on a image?

python

performance

for-loop

numpy

numpy-ndarray