My goal is to remove dark horizontal and vertical lines from an image after it has been converted into a numpy array. I didn't want to use a predefined image module for this since I wanted fine control over parameters such as threshold values.

My logic was as follows:

1. Convert a color image to a 3D numpy array image (BGR) using cv2.imread.
2. Iterate over row indices and extract each row using row = image[row_index,:,:].
3. In each row, calculate how many pixels are "black pixels" based on whether all 3 channel values are below the defined threshold.
4. If enough number (or ratio) of pixels in a row meet the above criteria, store this row index into the list remove_rows.
5. After all iterations, determine the rows to be preserved, stored into preserve_rows, based on the list remove_rows.
6. The new image after the rows deletion can be estimated by image = image[preserve_rows,:,:].
7. Repeat the process for columns as well.

The program worked, but it takes a very long time. I think the time complexity is O(rows * columns * 3) because every value has to be visited and compared with the threshold. The program takes around 9 seconds for a single image, which is unacceptable since I eventually plan to use this function for preprocessing in Keras in the ImageDataGenerator function and I'm not sure whether this function uses the GPU during neural network training. The full code is below:

def edge_removal(image, threshold=50, max_black_ratio=0.7):
    num_rows, _, _ = image.shape

    remove_rows = []
    threshold_times = []
    start_time = time.time()
    for row_index in range(num_rows):
        row = image[row_index,:,:]
        pixel_count = 0
        black_pixel_count = 0
        for pixel in row:
            pixel_count  = 1
            b,g,r = pixel
            pre_threshold_time = time.time()
            if all([x<=threshold for x in [b,g,r]]):
                black_pixel_count  = 1
            threshold_times.append(time.time()-pre_threshold_time)
            
            
        if pixel_count > 0 and (black_pixel_count/pixel_count)>max_black_ratio:
            remove_rows.append(row_index)
    
    
    time_taken = time.time() - start_time

    print(f"Time taken for thresholding = {sum(threshold_times)}")
    print(f"Time taken till row for loop = {time_taken}")
    preserve_rows = [x for x in range(num_rows) if x not in remove_rows]
    
    image = image[preserve_rows,:,:]
    
       
    _, num_cols, _ = image.shape

    remove_cols = []

    for col_index in range(num_cols):
        col = image[:,col_index,:]
        pixel_count = 0
        black_pixel_count = 0
        for pixel in col:
            pixel_count  = 1
            b,g,r = pixel
            if all([x<=threshold for x in [b,g,r]]):
                black_pixel_count  = 1
            
        if pixel_count > 0 and (black_pixel_count/pixel_count)>max_black_ratio:
            remove_cols.append(col_index)
    
    preserve_cols = [x for x in range(num_cols) if x not in remove_cols]
    
    image = image[:,preserve_cols,:]
    
    time_taken = time.time() - start_time
    print(f"Total time taken = {time_taken}")
    return image

And the output of the code is:

Time taken for thresholding = 3.586946487426758
Time taken till row for loop = 4.530229091644287
Total time taken = 8.74315094947815

I've tried the following:

1. Using mutlithreading to replace the outer for loop, where the argument to the threaded function is the threadnumber (no of threads = no of rows in the image). However, this did not speed up the program. This is probably because the for loop is a CPU-bound process, which cannot be sped up due to the Global Interpreter Lock, as described by this SO answer.
2. Looking for other suggestions how to reduce the time complexity of the program. This answer did not help me much since its not the deletion that's the bottleneck as can be seen in the output. The number of comparisons to perform thresholding is what's slowing this program down.

Any suggestions or heuristics to reduce the amount of computation and thereby the processing time of the program?

CodePudding user response：

Since your code is comprised of two parts that do the same job, simply on a different dimension of the image, I moved all that logic in a single function that tells you whether the "series of pixels" (row or column, does not matter) provided is above or below the threshold.

I replaced all the manual counts with len calls.

The various generators (r, g, b = pixel; x <= threshold for x in (r, g, b)) are replaced with direct numpy array comparison like pixel <= threshold and python's all is replaced by numpy's .all().

The old and new codes process my test image in 5.9 s and 37 ms respectively, with the added benefit of readability.

def edge_removal(image, threshold=50, max_black_ratio=0.7):

    def pixels_should_be_conserved(pixels) -> bool:
        black_pixel_count = (pixels <= threshold).all(axis=1).sum()
        pixel_count = len(pixels)
        return pixel_count > 0 and black_pixel_count/pixel_count <= max_black_ratio

    num_rows, num_columns, _ = image.shape
    preserved_rows    = [r for r in range(num_rows)    if pixels_should_be_conserved(image[r, :, :])]
    preserved_columns = [c for c in range(num_columns) if pixels_should_be_conserved(image[:, c, :])]
    image = image[preserved_rows,:,:]
    image = image[:,preserved_columns,:]
    return image

To explain further the change that saved us the most time (counting black pixels), let's take a look at a simplified example.

red = np.array([255, 0, 0])
black = np.array([0, 0, 0])
pixels = np.array([red, red, red, black, red]) # Simple line of 5 pixels.
threshold = 50

pixels <= threshold
# >>> array([[False,  True,  True],
#            [False,  True,  True],
#            [False,  True,  True],
#            [True,   True,  True],
#            [False,  True,  True]])

(pixels <= threshold).all(axis=1)
# >>> array([False,
#            False,
#            False,
#            True,
#            False])
# We successfully detect that the fourth pixel has all its rgb values below the threshold.

(pixels <= threshold).all(axis=1).sum()
# >>> 1
# Summing a boolean area is a handy way of counting how many element in the
# array are true, i.e. dark enough in our case.