Блог

Я ищу координаты соединенных больших двоичных объектов в двоичном изображении (2d массив чисел 0 или 1).

Библиотека skimage предоставляет очень быстрый способ маркировки больших двоичных объектов в массиве (который я нашел в аналогичных сообщениях SO). Однако мне нужен список координат большого двоичного объекта, а не помеченный массив. У меня есть решение, которое извлекает координаты из помеченного изображения. Но это происходит очень медленно. Гораздо медленнее, чем первоначальная маркировка.

Минимальный воспроизводимый пример:

 import timeit
from skimage import measure
import numpy as np

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

print(f"nn2d array of type: {type(binary_image)}:")
print(binary_image)

labels = measure.label(binary_image)

print(f"nn2d array with connected blobs labelled of type {type(labels)}:")
print(labels)

def extract_blobs_from_labelled_array(labelled_array):
    # The goal is to obtain lists of the coordinates
    # Of each distinct blob.

    blobs = []

    label = 1
    while True:
        indices_of_label = np.where(labelled_array==label)
        if not indices_of_label[0].size > 0:
            break
        else:
            blob =list(zip(*indices_of_label))
            label =1
            blobs.append(blob)


if __name__ == "__main__":
    print("nnBeginning extract_blobs_from_labelled_array timingn")
    print("Time taken:")
    print(
        timeit.timeit(
            'extract_blobs_from_labelled_array(labels)', 
            globals=globals(),
            number=1
            )
        )
    print("nn")
 

Выход:

 2d array of type: <class 'numpy.ndarray'>:
[[0 1 0 0 1 1 0 1 1 0 0 1]
 [0 1 0 1 1 1 0 1 1 1 0 1]
 [0 0 0 0 0 0 0 1 1 1 0 0]
 [0 1 1 1 1 0 0 0 0 1 0 0]
 [0 0 0 0 0 0 0 1 1 1 0 0]
 [0 0 1 0 0 0 0 0 0 0 0 0]
 [0 1 0 0 1 1 0 1 1 0 0 1]
 [0 0 0 0 0 0 0 1 1 1 0 0]
 [0 1 1 1 1 0 0 0 0 1 0 0]]


2d array with connected blobs labelled of type <class 'numpy.ndarray'>:
[[ 0  1  0  0  2  2  0  3  3  0  0  4]
 [ 0  1  0  2  2  2  0  3  3  3  0  4]
 [ 0  0  0  0  0  0  0  3  3  3  0  0]
 [ 0  5  5  5  5  0  0  0  0  3  0  0]
 [ 0  0  0  0  0  0  0  3  3  3  0  0]
 [ 0  0  6  0  0  0  0  0  0  0  0  0]
 [ 0  6  0  0  7  7  0  8  8  0  0  9]
 [ 0  0  0  0  0  0  0  8  8  8  0  0]
 [ 0 10 10 10 10  0  0  0  0  8  0  0]]


Beginning extract_blobs_from_labelled_array timing

Time taken:
9.346099977847189e-05
 

9e-05 невелика, но таково и это изображение для примера. На самом деле я работаю с изображениями очень высокого разрешения, для которых эта функция занимает около 10 минут.

Есть ли более быстрый способ сделать это?

Примечание: Я использую только list(zip()) для того, чтобы попытаться преобразовать координаты numpy в то, к чему я привык (я не часто использую numpy только на Python). Должен ли я пропустить это и просто использовать координаты для индексирования «как есть»? Это ускорит процесс?

Та часть кода, которая медленная, находится здесь:

     while True:
        indices_of_label = np.where(labelled_array==label)
        if not indices_of_label[0].size > 0:
            break
        else:
            blob =list(zip(*indices_of_label))
            label =1
            blobs.append(blob)
 

Во-первых, полная сторона: вы должны избегать использования while True , когда знаете количество элементов, которые вы будете перебирать. Это рецепт для труднодоступных ошибок с бесконечным циклом.

Вместо этого вы должны использовать:

     for label in range(np.max(labels)):
 

и тогда вы можете игнорировать if ...: break это .

Вторая проблема заключается в том , что вы действительно используете list(zip(*)) , что медленно по сравнению с функциями NumPy. Здесь вы могли бы получить примерно такой же результат , с np.transpose(indices_of_label) которым получите двумерный массив формы (n_coords, n_dim) , (n_coords, 2) т. е.

Но большая проблема заключается в выражении labelled_array == label . Это позволит изучить каждый пиксель изображения один раз для каждой метки. (На самом деле дважды, потому что затем вы бежите np.where() , что требует еще одного прохода.) Это много ненужной работы, так как координаты можно найти за один проход.

Функция scikit-image skimage.measure.regionprops может сделать это за вас. regionprops просматривает изображение один раз и возвращает список, содержащий по одному RegionProps объекту на метку. Объект имеет .coords атрибут, содержащий координаты каждого пикселя в большом двоичном объекте. Итак, вот ваш код, измененный для использования этой функции:

 import timeit
from skimage import measure
import numpy as np

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

print(f"nn2d array of type: {type(binary_image)}:")
print(binary_image)

labels = measure.label(binary_image)

print(f"nn2d array with connected blobs labelled of type {type(labels)}:")
print(labels)

def extract_blobs_from_labelled_array(labelled_array):
    """Return a list containing coordinates of pixels in each blob."""
    props = measure.regionprops(labelled_array)
    blobs = [p.coords for p in props]
    return blobs


if __name__ == "__main__":
    print("nnBeginning extract_blobs_from_labelled_array timingn")
    print("Time taken:")
    print(
        timeit.timeit(
            'extract_blobs_from_labelled_array(labels)', 
            globals=globals(),
            number=1
            )
        )
    print("nn")