How To Sort Contours Left To Right, While Going Top To Bottom, Using Python And Opencv

I'm finding the contours for an image with digits and characters, for OCR. So, I need the contours to be sorted left to right, while going line to line, i.e. top to bottom. Right n

Solution 1:

I used this method and it worked for me. In my case, there was 5 contours in each row

defx_cord_contour(contours):
    #Returns the X cordinate for the contour centroid
    M = cv2.moments(contours)
    return (int(M['m10']/M['m00']))
    
defy_cord_contour(contours):
    #Returns the Y cordinate for the contour centroid
    M = cv2.moments(contours)
    return (int(M['m01']/M['m00']))
    

# Sort by top to bottom using our y_cord_contour function
contours_top_to_bottom = sorted(questionCnts, key = y_cord_contour, reverse = False)





for (q, i) inenumerate(np.arange(0, len(contours_top_to_bottom), 5)):
    # sort the contours for the current question from left to right# As in my example every row contain 5 coutours so now i sorted them in row wise
    cnts = sorted(contours_top_to_bottom[i:i + 5], key = x_cord_contour, reverse = False)
    
    # loop over the sorted contoursfor (j, c) inenumerate(cnts):
        # construct a mask that reveals only the current contour#and do what ever you want to do#....#

please correct me if i m wrong

Solution 2:

I like your trying to solve the problem with a single sorting. But as you said, the variation of y in each line might break your algorithm, plus, the max_line_height is something you probably have to tweak based on different inputs.

So instead, I would propose a slightly different algorithm, but with decent computational complexity. The idea is that, if you only look at all the boxes horizontally, all the boxes from line N+1 will never intersect with the boxes from line 1 to N, but they intersects with each other inside one line. So you can sort all the boxes by their y first, walk through them one by one and try to find 'breaking point' (grouping them into one line), then within each line, sort them by their x.

Here is a less Pythonic solution:

# sort all rect by their y
rect.sort(key=lambda b: b[1])
# initially the line bottom is set to be the bottom of the first rect
line_bottom = rect[0][1]+rect[0][3]-1
line_begin_idx = 0for i in xrange(len(rect)):
    # when a new box's top is below current line's bottom# it's a new lineif rect[i][1] > line_bottom:
        # sort the previous line by their x
        rect[line_begin_idx:i] = sorted(rect[line_begin_idx:i], key=lambda b: b[0])
        line_begin_idx = i
    # regardless if it's a new line or not# always update the line bottom
    line_bottom = max(rect[i][1]+rect[i][3]-1, line_bottom)
# sort the last line
rect[line_begin_idx:] = sorted(rect[line_begin_idx:], key=lambda b: b[0])

Now rect should be sorted in the way you want.