Элегантный / быстрый способ найти конечные точки линии на изображении?

Question

Я работал над повышением скорости моего кода, заменив циклы операций с массивами на соответствующие функции 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

Я думаю, что я могу, по крайней мере, предоставить элегантное решение с использованием сверток.

Мы можем искать количество соседних пикселей, свернув исходное изображение с кольцом 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 2

Вот решение со сверткой:

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 для этого.Код будет в значительной степени тем, что у вас уже есть, так что, возможно, не особенно «элегантным», но намного быстрее.Например, что-то вроде этого:

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 из параллельных потоков).

Answer 3

Редактировать: я не заметил, что у вас есть изображение в градациях серого, но что касается идеи, ничего не изменилось

Я не могу дать вам точное решение, но я могу дать вам более быстрый способ найти то, что вы хотите

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) переместить массив индексов +1 по оси X и добавить его к изображению

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 )