Python: Sorting items from top left to bottom right with OpenCV

Question

How can I go about trying to order the items of a picture from top left to bottom right, such as in the image below? Currently receiving this error with the following code .

Error:

a = sorted(keypoints, key=lambda p: (p[0]) + (p1))[0] # find upper left point ValueError: The truth value of an array with more than one element is ambiguous. Use a.any() or a.all()

This question is modelled from this: Ordering coordinates from top left to bottom right

def preprocess(img):
    img_gray = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY)
    img_blur = cv2.GaussianBlur(img_gray, (5, 5), 1)
    img_canny = cv2.Canny(img_blur, 50, 50)
    kernel = np.ones((3, 3))
    img_dilate = cv2.dilate(img_canny, kernel, iterations=2)
    img_erode = cv2.erode(img_dilate, kernel, iterations=1)
    return img_erode

image_final = preprocess(picture_example.png)
keypoints, hierarchy = cv2.findContours(image_final, cv2.RETR_EXTERNAL, cv2.CHAIN_APPROX_NONE)
points = []

while len(keypoints) > 0:
    a = sorted(keypoints, key=lambda p: (p[0]) + (p[1]))[0]  # find upper left point
    b = sorted(keypoints, key=lambda p: (p[0]) - (p[1]))[-1]  # find upper right point

    cv2.line(image_final, (int(a.pt[0]), int(a.pt[1])), (int(b.pt[0]), int(b.pt[1])), (255, 0, 0), 1)

    # convert opencv keypoint to numpy 3d point
    a = np.array([a.pt[0], a.pt[1], 0])
    b = np.array([b.pt[0], b.pt[1], 0])

    row_points = []
    remaining_points = []
    for k in keypoints:
        p = np.array([k.pt[0], k.pt[1], 0])
        d = k.size  # diameter of the keypoint (might be a theshold)
        dist = np.linalg.norm(np.cross(np.subtract(p, a), np.subtract(b, a))) / np.linalg.norm(b)   # distance between keypoint and line a->b
        if d/2 > dist:
            row_points.append(k)
        else:
            remaining_points.append(k)

    points.extend(sorted(row_points, key=lambda h: h.pt[0]))
    keypoints= remaining_points

New Picture:

Reference Ordering Picture:

Will use center of mass to determine center point ordering.

Answer 1

The resulting numbering depends on how many rows you want there to be. With the program I will show you how to make, you can specify the number of rows before you run the program.

For example, here is the original image:

Here is the numbered image when you specify 4 rows:

Here is the numbered image when you specify 6 rows:

For the other image you provided (with its frame cropped so the frame won't be detected as a shape), you can see there will be 4 rows, so putting 4 into the program will give you:

---

Let's have a look at the workflow considering 4 rows. The concept I used is to divide the image into 4 segments along the y axis, forming 4 rows. For each segment of the image, find every shape that has its center in that segment. Finally, order the shapes in each segment by their x coordinate.

1. Import the necessary libraries:

import cv2
import numpy as np

2. Define a function that will take in an image input and return the image processed to something that will allow python to later retrieve their contours:

def process_img(img):
    img_gray = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY)
    img_canny = cv2.Canny(img_gray, 100, 100)
    kernel = np.ones((2, 3))
    img_dilate = cv2.dilate(img_canny, kernel, iterations=1)
    img_erode = cv2.erode(img_dilate, kernel, iterations=1)
    return img_erode

3. Define a function that will return the center of a contour:

def get_centeroid(cnt):
    length = len(cnt)
    sum_x = np.sum(cnt[..., 0])
    sum_y = np.sum(cnt[..., 1])
    return int(sum_x / length), int(sum_y / length)

4. Define a function that will take in a processed image and return the center points of the shapes found in the image:

def get_centers(img):
    contours, hierarchies = cv2.findContours(img, cv2.RETR_EXTERNAL, cv2.CHAIN_APPROX_NONE)
    for cnt in contours:
        if cv2.contourArea(cnt) > 100:
            yield get_centeroid(cnt)

5. Define a function that will take in an image array, img, an array of coordinates, centers, the number of segments for the image, row_amt, and the height of each segment, row_h, as input. It will return row_amt arrays (sorted by their x coordinates), each containing every point in centers that lies in its corresponding row of the image:

def get_rows(img, centers, row_amt, row_h):
    centers = np.array(centers)
    d = row_h / row_amt
    for i in range(row_amt):
        f = centers[:, 1] - d * i
        a = centers[(f < d) & (f > 0)]
        yield a[a.argsort(0)[:, 0]]

6. Read in the image, get its processed form using the processed function defined, and get the center of each shape in the image using the centers function defined:

img = cv2.imread("shapes.png")
img_processed = process_img(img)
centers = list(get_centers(img_processed))

7. Get the height of the image to use for the get_rows function defined, and define a count variable, count, to keep track of the numbering:

h, w, c = img.shape
count = 0

8. Loop through the centers of the shape divided into 4 rows, drawing the line that connects the rows for visualization:

for row in get_rows(img, centers, 4, h):
    cv2.polylines(img, [row], False, (255, 0, 255), 2)
    for x, y in row:

9. Add to the count variable, and draw the count onto the specific location on the image from the row array:

        count += 1
        cv2.circle(img, (x, y), 10, (0, 0, 255), -1)  
        cv2.putText(img, str(count), (x - 10, y + 5), 1, cv2.FONT_HERSHEY_PLAIN, (0, 255, 255), 2)

10. Finally, show the image:

cv2.imshow("Ordered", img)
cv2.waitKey(0)

---

Altogether:

import cv2
import numpy as np

def process_img(img):
    img_gray = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY)
    img_canny = cv2.Canny(img_gray, 100, 100)
    kernel = np.ones((2, 3))
    img_dilate = cv2.dilate(img_canny, kernel, iterations=1)
    img_erode = cv2.erode(img_dilate, kernel, iterations=1)
    return img_erode
    
def get_centeroid(cnt):
    length = len(cnt)
    sum_x = np.sum(cnt[..., 0])
    sum_y = np.sum(cnt[..., 1])
    return int(sum_x / length), int(sum_y / length)

def get_centers(img):
    contours, hierarchies = cv2.findContours(img, cv2.RETR_EXTERNAL, cv2.CHAIN_APPROX_NONE)
    for cnt in contours:
        if cv2.contourArea(cnt) > 100:
            yield get_centeroid(cnt)

def get_rows(img, centers, row_amt, row_h):
    centers = np.array(centers)
    d = row_h / row_amt
    for i in range(row_amt):
        f = centers[:, 1] - d * i
        a = centers[(f < d) & (f > 0)]
        yield a[a.argsort(0)[:, 0]]

img = cv2.imread("shapes.png")
img_processed = process_img(img)
centers = list(get_centers(img_processed))

h, w, c = img.shape
count = 0

for row in get_rows(img, centers, 4, h):
    cv2.polylines(img, [row], False, (255, 0, 255), 2)
    for x, y in row:
        count += 1
        cv2.circle(img, (x, y), 10, (0, 0, 255), -1)  
        cv2.putText(img, str(count), (x - 10, y + 5), 1, cv2.FONT_HERSHEY_PLAIN, (0, 255, 255), 2)

cv2.imshow("Ordered", img)
cv2.waitKey(0)

Answer 2

This is not completly the same task as in your linked question you took the code from:

1. You have contours, while the other question has points. You have to come up with a method to sort contours (they might overlap in one dimension and so on...). There are multiple ways to do that, depending on your use case. The easiest might be to use the center of mass of your contour. This can be done like here: Center of mass in contour (Python, OpenCV). Then you can make an array of objects out of it, that contain points and use the code that you found.
2. The code that you found assumes that the points are basically more or less on a grid. So all the points 1-5 on your reference image are roughly on a line. In the new picture you posted, this is not really the case. It might be better to go for a clustering approach here: Cluster the center points y coordinates with some aproach (maybe one from here). Then for each cluster: sort the elements by there centers x coordinate.

As I already said there are multiple ways in doing that and it depends hardly on your use case.