python - NumPy fast iteration trough image

Question

I'm trying to get the extreme points in a binary image that has a rectangular shape (more or less). Binary image in which I want to find some rectangular bound around my rectangular (black) object

I would like to get 4 points like this (image) in order to use cv2.minAreaRect(points) on them and obtain a bounding box. The issue is that my current algorithm is extremely slow in finding those bounds because I have to iterate through this binary image 4 times (2D NumPy array).

def findCornerOne(frame):
    #threshold that handles the case when you have some noise around your object (as in the photo 
    #above)
    global thresholdVal
    x = frame.shape[0]
    y = frame.shape[1]
    point = None
    firstFound = True
    count = 0
    for i in range(0, y):
        for j in range(0, x):
            if frame[j][i] != 0:
                if firstFound:
                    point = [i, j]
                    firstFound = False
                 count += 1
            else:
                if count <= thresholdVal:
                    firstFound = True
                    count = 0
                else:
                    return point

    return None

Is there any way speeding this up just with NumPy and standard python (without any libraries)? I was thinking about using numpy.where but I don't know how to specify on what axis I'm going to search first and find the bounding points.

In the end, I would like to obtain some points like the red ones in the image:image

question from:https://stackoverflow.com/questions/65837329/numpy-fast-iteration-trough-image

Answer 1

The solution I came up with can be summarized as follows:

• Convert the original image into grayscale and binarize through Otsu's method.
• Compute the connected components of the binary image.
• Select the largest region.
• Determine the extreme coordinates of that region.

import numpy as np
from skimage import io
from skimage.measure import label, regionprops
from skimage.filters import threshold_otsu
from skimage.color import rgb2gray

img = io.imread('https://i.stack.imgur.com/FIQjh.png')[:, :, :3]
gray = rgb2gray(img)

thresholded = gray > threshold_otsu(gray)
labels = label(thresholded, background=1)
props = measure.regionprops(labels)

largest = sorted(props, key=lambda x: x.area, reverse=True)[0]

top = np.where(largest.coords[:, 0] == largest.coords[:, 0].min())
bottom = np.where(largest.coords[:, 0] == largest.coords[:, 0].max())
left = np.where(largest.coords[:, 1] == largest.coords[:, 1].min())
right = np.where(largest.coords[:, 1] == largest.coords[:, 1].max())

extremes = np.concatenate([top[0], bottom[0], left[0], right[0]])
corners = largest.coords[extremes]

The code above relies not only in NumPy but also in scikit-image and is fairly efficient. Please note that this approach returns more than 4 points (you could readily cluster the coordinates to get just 4 points).

In [419]: corners
Out[419]: 
array([[ 69, 417],
       [ 69, 418],
       [ 69, 419],
       [ 69, 420],
       [ 69, 421],
       [256, 211],
       [256, 212],
       [256, 213],
       [256, 214],
       [101, 187],
       [102, 187],
       [103, 187],
       [104, 187],
       [227, 460],
       [228, 460],
       [229, 460],
       [230, 460],
       [231, 460],
       [232, 460],
       [233, 460],
       [234, 460],
       [235, 460]], dtype=int64)

If you want to obtain a bounding box, you don't need to calculate them manually since the properties returned by regionprops have a key bbox that contains the coordinates of the bounding box:

In [420]: largest.bbox
Out[420]: (69, 187, 257, 461)

Demo

import matplotlib.pyplot as plt
from matplotlib.patches import Circle

patches = [Circle((col, row), radius=25, color='green') 
           for row, col in corners]

fig, ax = plt.subplots(1)
ax.imshow(img)
for p in patches:
    ax.add_patch(p)
plt.show(fig)