How to efficently set all values above a line in an binary image to 1?

Question

I currently have a binary image, stored as a 2D array of [col][row]. The image is split in 2 by a line and I want to set all array values above the line to 1.

Currently, I loop through the columns of the array, looping through the rows of the column (bottom to top) to find the first row where the value of the array [col][row] is 1. I then break from looping through the rows and set all values above the row that I broke from to 1 for that column.

Unfortunately for a 1920x1080 image, this takes about 3 seconds. How could this be achieved more efficiently?

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

Before and After pictures below...

user_5218354 · Answer

Here a couple of methods requiring a 2D input. May need to be adjusted to ensure they are working on the correct side and on the correct dimension, but the core idea holds.

using np.where() and looping over one dim with slicing:

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

using full explicit looping (similar to yours, but somehow cleaner), but accelerated with 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

To test that we are getting the correct result, we generate some input using:

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

and the test reads:

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]]

Now for the timings for approx. your input size:

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

As you can see, with the NumPy approach (which is as much vectorized as I could think of) you get approx. 2 orders of magnitude speed-up, with the Numba accelerated code you get approx. 3 orders of magnitude speed-up.

user_4734439 · Answer

You can use cv2.floodFill to fill all connected pixels within a range of values. You have to specify a seed_point from which the filling starts until blocked by a pixel with a value outside the specified range.

To solve the issue of the duplicate lines we need first to connect them. To do so, we can apply the closing morphological operation.

Code (~10 ms for the question image including the closing operation):

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)

How to efficently set all values above a line in an binary image to 1?

2 Answers