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

Я работал над повышением скорости своего кода, заменив циклы операций с массивами на соответствующие функции NumPy.

Функция нацелена на получение конечных точек линии, которые являются единственными двумя точками, имеющими ровно один соседний пиксель из 255.

Есть ли способ получить две точки от np.where с условиями или некоторыми функциями NumPy, с которыми я не знаком, выполнят эту работу?

защита 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

葉品廷 21.01.2019 источник

comment

Есть несколько деталей, которые мне не ясны. Когда вы говорите «соседи», это 4 или 8 окружающих пикселей? (то есть включаете ли вы диагональных соседей?) И условие для нахождения конечной точки состоит в том, что пиксель должен иметь значение 255 (image[i][j]==255), а сумма соседей должна быть... 255 или ноль? Что делает neighbours_sum? Может быть, вы могли бы привести пример того, как будет выглядеть конечная точка со значениями? - jdehesa 21.01.2019

comment

Соседями @jdehesa являются 8 окружающих пикселей, потому что сама линия может быть не горизонтальной или вертикальной. Neghbours_sum возвращает сумму всех значений пикселей соседей. В моем случае значение пикселей строки равно 255, а пикселей фона — 0. Например, для линии ((1,1),(2,2),(2,3),(3,4)) конечными точками являются (1,1),(3,4) которые имеют только один сосед точно - 葉品廷 21.01.2019

Ответы (3)

arrow_upward
1
arrow_downward

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

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

jdehesa 21.01.2019

comment

Коротко, просто и эффективно. Любить это! - 葉品廷; 21.01.2019

comment

@葉品廷 Рад, что это помогло. Я также добавил еще один вариант с помощью Numba, который может быть быстрее. - jdehesa; 21.01.2019

comment

Версия Numba работает намного быстрее. Я пытался применить numba.jit к другим функциям, но это не работает. Работает ли он только с функциями с чистыми базовыми операциями и операциями numpy? - 葉品廷; 21.01.2019

comment

@葉品廷 Я на самом деле не эксперт по Numba, но обратите внимание, что jit и njit (или jit(nopython=True)) сильно отличаются, поскольку первый может оптимизироваться только на уровне Python, а второй всегда является родным (собственная оптимизация более ограничена, но довольно быстрее) . Если вы используете njit и получаете сообщение об ошибке, обычно это связано с тем, что вы используете какую-то неподдерживаемую функцию для нативного кода. Вы можете прочитать больше обо всем этом в документах Numba и других местах, но да, повысить производительность функции с помощью Numba не всегда тривиально. - jdehesa; 21.01.2019

comment

@葉品廷 Кроме того, если вы используете функцию, которая работает векторизованным способом (например, первая find_endpoints в моем ответе), использование Numba, вероятно, мало поможет, поскольку тяжелая работа уже выполняется изначально в Python. Это хорошо работает, когда у вас есть узкие циклы, которые выполняют некоторые математические операции (например, старайтесь избегать if ветвей, динамически растущих структур и т. д.). А с помощью parallel=True и prange вы можете делать параллельные вещи практически автоматически, если вы внимательны к условиям гонки. - jdehesa; 21.01.2019

arrow_upward
0
arrow_downward

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

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

1) а) Найти индексы (пиксели), где белый [255,255,255]

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

1) б) делайте циклы вокруг этих точек, это быстрее, потому что вы не делаете бесполезные циклы

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 )

Martin 21.01.2019

arrow_upward
0
arrow_downward

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

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

Felix 21.01.2019

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

Ответы (3)

Похожие вопросы