Как эффективно установить все значения над линией в двоичном изображении на 1?

Question

В настоящее время у меня есть двоичное изображение, хранящееся в виде двумерного массива [col] [row]. Изображение разделено на 2 строкой, и я хочу установить все значения массива над строкой равными 1.

В настоящее время я l oop перебираю столбцы массива, циклически перебирая строки столбца. (снизу вверх), чтобы найти первую строку, в которой значение массива [col] [row] равно 1. Затем я перерываю цикл по строкам и устанавливаю все значения выше строки, которую я разбил, до 1 для этого столбца.

К сожалению, для изображения 1920x1080 это занимает около 3 секунд. Как это может быть достигнуто более эффективно?

for x in range(len(image)):
    col = image[x]
    minY= -1

    for y in range(len(col)):
        if image[x][-y] != 0:
            minY = y
            break

    if minY != -1:
        under = [0] * minY 
        over = [1] * (len(col) - minY)
        newCol = over + under
        image[x] = newCol

Фотографии до и после ниже ...

Answer 1

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

Чтобы решить проблему с дублирующимися линиями, нам нужно сначала соединить их. Для этого мы можем применить морфологическую операцию закрытия.

Код (~ 10 мс для изображения вопроса, включая операцию закрытия):

max_distance_between_lines = 15
closing_kernel = cv2.getStructuringElement(cv2.MORPH_RECT (max_distance_between_lines, max_distance_between_lines))
img = cv2.morphologyEx(img, cv2.MORPH_CLOSE, closing_kernel)
point_in_top_half = (5, 5)
#floodFill works inplace, `img` is now filled
cv2.floodFill(img, None, point_in_top_half, 255)

Answer 2

Здесь пара методов, требующих ввода 2D. Может потребоваться корректировка, чтобы гарантировать, что они работают с правильной стороны и в правильном размере, но основная идея верна.

• с использованием np.where() и циклическим перемещением по одной яркости с нарезкой:

import numpy as np


def side_fill_np(arr, value, flag):
    rows, cols = arr.shape
    idx = np.where(arr == flag)
    for i in range(cols):
        arr[idx[0][i]:, idx[1][i]] = value
    return arr

• с использованием полного явного зацикливания (аналогично вашему, но как-то чище), но ускорено с numba

import numba as nb


@nb.jit
def side_fill_nb(arr, value, flag):
    rows, cols = arr.shape
    for j in range(cols):
        found = False
        for i in range(rows):
            if found:
                arr[i, j] = value
            elif arr[i, j] == flag:
                found = True

---

Чтобы проверить это мы получаем правильный результат, мы генерируем некоторый ввод, используя:

def gen_data(shape):
    rows, cols = shape
    arr = np.zeros(shape, dtype=bool)
    indexes = (np.random.randint(0, rows - 1, cols), np.arange(cols))
    arr[indexes] = True
    return arr

и тест гласит:

np.random.seed(0)  # for reproducible results
arr = gen_data((10, 20))
print(arr.astype(int))
# [[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 1 0 0 0 0 1 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 0 1 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]
#  [1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1]
#  [0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0]
#  [0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 1 0 0 0]
#  [0 0 0 0 0 0 0 0 0 0 0 1 1 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]]

side_fill_np(arr, True, True)
print(arr.astype(int))
# [[0 1 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 1 0 0 0 0 1 0]
#  [0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 0]
#  [0 1 1 1 0 1 0 1 0 0 0 0 0 1 0 0 0 0 1 0]
#  [0 1 1 1 0 1 0 1 1 0 0 0 0 1 0 0 0 0 1 0]
#  [1 1 1 1 0 1 1 1 1 0 0 0 0 1 0 0 0 0 1 1]
#  [1 1 1 1 0 1 1 1 1 0 1 0 0 1 1 0 0 0 1 1]
#  [1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 0 1 1]
#  [1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1]
#  [1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1]]

---

Теперь для времени прибл. ваш входной размер:

arr = gen_data((2000, 2000))
%timeit side_fill(arr, True, True)
# 1 loop, best of 3: 2.48 s per loop
%timeit side_fill_np(arr, True, True)
# 10 loops, best of 3: 52.6 ms per loop
%timeit side_fill_nb(arr, True, True)
# 100 loops, best of 3: 6.14 ms per loop

Как вы можете видеть, с подходом NumPy (который настолько векторизован, насколько я мог подумать) вы получите прибл. Ускорение на 2 порядка, с ускоренным кодом Numba вы получаете прибл. Ускорение на 3 порядка.