Заполнить ограничивающие рамки в двумерном массиве

Question

У меня есть двумерный массив, который выглядит как

array([[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., 1., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.],
       [0., 0., 1., 1., 1., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.],
       [0., 0., 1., 1., 0., 0., 0., 0., 0., 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., 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., 0., 0., 0., 0., 0., 0., 0.],
       [0., 0., 0., 0., 0., 0., 0., 0., 0., 1., 0., 0., 0., 0., 0.],
       [0., 0., 0., 0., 0., 0., 0., 0., 0., 1., 0., 0., 0., 0., 0.],
       [0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 1., 1., 0., 0., 0.],
       [0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 1., 0., 0., 0., 0.]]) `

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

array([[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., 1., 1., 1., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.],
       [0., 0., 1., 1., 1., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.],
       [0., 0., 1., 1., 1., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.],
       [0., 0., 1., 1., 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.],
       [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., 0., 0., 0., 0., 0.],
       [0., 0., 0., 0., 0., 0., 0., 0., 0., 1., 1., 1., 0., 0., 0.],
       [0., 0., 0., 0., 0., 0., 0., 0., 0., 1., 1., 1., 0., 0., 0.],
       [0., 0., 0., 0., 0., 0., 0., 0., 0., 1., 1., 1., 0., 0., 0.],
       [0., 0., 0., 0., 0., 0., 0., 0., 0., 1., 1., 1., 0., 0., 0.]])

Как мне это легко сделать?Также, как мне это сделать, если существуют другие номера типа 2,3 и т.д., но я хочу их игнорировать, а группы в основном 2.

Answer 1

Хотя предыдущие ответы в порядке, вот как вы могли бы сделать это с помощью scipy.ndimage:

import numpy as np
from scipy import ndimage

def fill_bboxes(x):
    x_components, _ = ndimage.measurements.label(x, np.ones((3, 3)))
    bboxes = ndimage.measurements.find_objects(x_components)

    for bbox in bboxes:
        x[bbox] = 1

    return x

ndimage.measurements.label выполняет маркировку подключенного компонента с помощью матрицы 3x3- «единиц», определяющей окрестность,find_objects затем определяет ограничивающий прямоугольник для каждого компонента, который затем можно использовать для установки всего в 1.

Answer 2

Вот один из подходов к решению этой проблемы.Основная идея заключается в том, чтобы использовать итеративное решение, которое принимает 2D свертку матрицы и набор фильтров на каждом шаге для обнаружения и заполнения ячеек, попадающих в ограничивающую рамку.

Это будет намного понятнее с примером.Скажем, у нас есть следующие ndarray:

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

Идея этого метода заключается в обнаружении ячеек, которые имеют как минимум двух ортогональных соседей (на расстоянии 1 ячейка), которыепод углом 90 ° между собой с ненулевыми значениями в них.

Итеративно находя эти ячейки и заполняя их ячейками, мы получим ожидаемый результат.Таким образом, для этого примера выходные данные после первой итерации будут:

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

И на следующей итерации:

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

---

Как эти ячейки могут быть обнаружены?

Один из способов - взять двумерную свертку ndarray с набором предопределенных фильтров, специально предназначенных для обнаружения интересующих ячеек.Для этой цели мы можем использовать scipy's convolve2D.

2D свертка по существу берется путем сдвига 2D-фильтра через ndarray и вычисления на каждом шагесумма поэлементного умножения.Это может быть более интуитивно понятно с помощью следующей анимации ( изображение из ):

---

Так что будет необходимопридумать какой-то фильтр, чтобы обнаружить интересующие клетки.Один из подходов может быть следующим:

array([[0, 1, 0],
       [1, 0, 1],
       [0, 1, 0]])

На первый взгляд этот фильтр может выполнить задачу, учитывая, что он обнаружит соседних соседей.Однако этот фильтр также будет учитывать выборки, которые находятся на расстоянии двух ячеек, поэтому, например, он будет складывать значения в первой и последней строке фильтра, и, как упоминалось ранее, мы хотим найти соседей, которые находятся под углом90 ° друг от друга.Таким образом, мы могли бы применить последовательность фильтров, рассматривающих все возможности такого случая:

2-мерные фильтры для применения

[0, 1, 0]   [0, 1, 0]   [0, 0, 0]   [0, 0, 0]
[0, 0, 1] , [1, 0, 0] , [1, 0, 0] , [0, 0, 1]
[0, 0, 0]   [0, 0, 0]   [0, 1, 0]   [0, 1, 0]

Применяя каждый из этихПо фильтрам мы могли определить, какие ячейки имеют хотя бы двух соседей с упомянутыми требованиями, и заполнить их.

---

Общее решение

def fill_bounding_boxes(a):
    '''
    Detects contiguous non-zero values in a 2D array
    and fills with ones all missing values in the 
    minimal rectangular boundaries that enclose all 
    non-zero entries, or "Minimal Bounding Boxes"
    ----
    a: np.array
       2D array. All values > 0 are considered to define
       the bounding boxes
    ----       
    Returns:
       2D array with missing values filled 

    '''
    import numpy as np
    from scipy.signal import convolve2d
    # Copy of the original array so it remains unmodified
    x = np.copy(a).clip(0,1)
    # Indicator. Set to false when no additional
    # changes in x are found
    is_diff = True
    # Filter to be used for the 2D convolution
    # The other filters are obtained by rotating this one
    f = np.array([[0,1,0], [0,0,1], [0,0,0]])
    # Runs while indicator is True
    while is_diff:
        x_ = np.copy(x)
        # Convolution between x and the filters
        # Only values with sums > 1 are kept, as it will mean
        # that they had minimum 2 non-zero neighbours
        # All filters are applied by rotating the initial filter
        x += sum((convolve2d(x, np.rot90(f, i), mode='same') > 1) 
                 for i in range(4))
        # Clip values between 0 and 1
        x = x.clip(0,1)
        # Set indicator to false if matrix x is unmodified
        if (x == x_).all():
            is_diff = False
    return x

---

Примеры

Давайте посмотрим на результат с помощью предложенного примера:

print(a)
array([[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, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
       [0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
       [0, 0, 1, 1, 0, 0, 0, 0, 0, 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, 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, 0, 0, 0, 0, 0, 0, 0],
       [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
       [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
       [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0],
       [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0]])

fill_bounding_boxes(a)
array([[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, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
       [0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
       [0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
       [0, 0, 1, 1, 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],
       [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, 0, 0, 0, 0, 0],
       [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0],
       [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0],
       [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0],
       [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0]])

---

И для этого другого примера:

print(a)
array([[0, 0, 0, 0, 1, 0],
       [0, 0, 0, 0, 1, 1],
       [1, 0, 0, 0, 0, 0],
       [1, 1, 1, 0, 0, 0],
       [1, 0, 1, 0, 0, 0],
       [0, 0, 0, 0, 0, 0],
       [0, 0, 1, 0, 0, 0],
       [0, 1, 1, 0, 0, 1],
       [0, 0, 0, 0, 1, 0]])

fill_bounding_boxes(a)
array([[0, 0, 0, 0, 1, 1],
       [0, 0, 0, 0, 1, 1],
       [1, 1, 1, 0, 0, 0],
       [1, 1, 1, 0, 0, 0],
       [1, 1, 1, 0, 0, 0],
       [0, 0, 0, 0, 0, 0],
       [0, 1, 1, 0, 0, 0],
       [0, 1, 1, 0, 1, 1],
       [0, 0, 0, 0, 1, 1]])

Answer 3

Это интересная проблема.2D свертка является естественным подходом.Однако, если входная матрица является разреженной (как это показано в вашем примере), это может быть дорогостоящим.Для разреженной матрицы другой подход заключается в использовании алгоритма кластеризации.Это извлекает только ненулевые пиксели из поля ввода a (массив в вашем примере) и выполняет иерархическую кластеризацию.Кластеризация основана на специальной матрице расстояний (кортеж).Объединение происходит, если поля разделены максимум 1 пикселем в любом направлении.Вы также можете применить фильтр к любым числам, которые вам нужны на шаге инициализации (скажем, сделать только для [row, col] == 1 и пропустить любые другие числа или все, что вы пожелаете.

from collections import namedtuple 

Point = namedtuple("Point",["x","y"]) # a pixel on the matrix
Box = namedtuple("Box",["tl","br"]) # a box defined by top-lef/bottom-right

def initialize(a):
    """ create a separate bounding box at each non-zero pixel. """
    boxes = []
    rows, cols = a.shape
    for row in range(rows):
        for col in range(cols):
            if a[row, col] != 0:
                boxes.append(Box(Point(row, col),Point(row, col)))
    return boxes

def dist(box1, box2):
    """ dist between boxes is from top-left to bottom-right, or reverse. """
    x = min(abs(box1.br.x - box2.tl.x), abs(box1.tl.x - box2.br.x))
    y = min(abs(box1.br.y - box2.tl.y), abs(box1.tl.y - box2.br.y))
    return x, y

def merge(boxes, i, j):
    """ pop the boxes at the indices, merge and put back at the end. """
    if i == j:
        return

    if i >= len(boxes) or j >= len(boxes):
        return

    ii = min(i, j)
    jj = max(i, j)
    box_i = boxes[ii]
    box_j = boxes[jj]
    x, y = dist(box_i, box_j)

    if x < 2 or y < 2:
        tl = Point(min(box_i.tl.x, box_j.tl.x),min(box_i.tl.y, box_j.tl.y))
        br = Point(max(box_i.br.x, box_j.br.x),max(box_i.br.y, box_j.br.y))
        del boxes[ii]
        del boxes[jj-1]
        boxes.append(Box(tl, br))


def cluster(a, max_iter=100):
    """ 
        initialize the cluster. then loop through the length and merge 
        boxes. break if `max_iter` reached or no change in length.
    """
    boxes = initialize(a)
    n = len(boxes)
    k = 0

    while k < max_iter:
        for i in range(n):
            for j in range(n):
                merge(boxes, i, j)
        if n == len(boxes):
            break
        n = len(boxes)
        k = k+1

    return boxes

cluster(a)
# output: [Box(tl=Point(x=2, y=2), br=Point(x=5, y=4)),Box(tl=Point(x=11, y=9), br=Point(x=14, y=11))]

# performance 275 µs ± 887 ns per loop (mean ± std. dev. of 7 runs, 1000 loops each)
# compares to 637 µs ± 9.36 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each) for 
#the method based on 2D convolution

Это возвращаетсписок блоков, определяемых угловыми точками (верхний левый и нижний правый). Здесь x - номер строки, а y - номера столбцов. Инициализация проходит по всей матрице. Но после этого мы обрабатываем только очень маленькое подмножествоиз точек. Изменяя функцию dist, вы можете настроить определение блока (перекрытие, неперекрытие и т. д.). Производительность может быть дополнительно оптимизирована (например, для разрыва, если i или j больше длины блоков внутри циклов for, чем для простого возврата).из функции слияния и продолжения).

Answer 4

Есть одно решение , но оно немного хакерское, и я не буду его программировать.

OpenCV - Библиотека обработки изображений, имеет алгоритм для поиска прямоугольного контура ->Прямо или повернуто.Что вы можете сделать, это преобразовать ваш массив в 2D-изображение в градациях серого, найти контуры и записать в контуры ваши 1 с.

Проверьте это изображение - оно из Opencv DOC - 7.a - https://docs.opencv.org/3.4/dd/d49/tutorial_py_contour_features.html

Вас заинтересует все, что находится внутри зеленых линий.

---

Если честноЯ думаю, мне кажется, это намного проще, чем программирование какого-либо алгоритма для ограничивающих рамок

Примечание

Конечно, вам действительно не нужно делать изображения, но я думаю, что этодостаточно использовать алгоритм opencv для ограничивающих рамок (счетчиков)