How can I sort contours from left to right and top to bottom? [duplicate]

Question

I am trying to build an character recognition program using Python. I am stuck on sorting the contours. I am using this page as a reference.

I managed to find the contours using the following piece of code:

mo_image = di_image.copy()
contour0 = cv2.findContours(mo_image.copy(),cv2.RETR_EXTERNAL,cv2.CHAIN_APPROX_SIMPLE)
contours = [cv2.approxPolyDP(cnt,3,True) for cnt in contour0[0]]

And added the bounding rectangles and segmented the image using this part of the code:

maxArea = 0
rect=[]
for ctr in contours:
    maxArea = max(maxArea,cv2.contourArea(ctr))

if img == "Food.jpg":
    areaRatio = 0.05
elif img == "Plate.jpg":
    areaRatio = 0.5

for ctr in contours:    
    if cv2.contourArea(ctr) > maxArea * areaRatio: 
        rect.append(cv2.boundingRect(cv2.approxPolyDP(ctr,1,True)))

symbols=[]
for i in rect:
    x = i[0]
    y = i[1]
    w = i[2]
    h = i[3]
    p1 = (x,y)
    p2 = (x+w,y+h)
    cv2.rectangle(mo_image,p1,p2,255,2)
    image = cv2.resize(mo_image[y:y+h,x:x+w],(32,32))
    symbols.append(image.reshape(1024,).astype("uint8"))

testset_data = np.array(symbols)

cv2.imshow("segmented",mo_image)
plt.subplot(2,3,6)
plt.title("Segmented")
plt.imshow(mo_image,'gray')
plt.xticks([]),plt.yticks([]);

However the resulting segments appear in to be in random order. Here is the original image followed by the processed image with detected segments.

The program then outputs each segment separately, however it is in the order: 4 1 9 8 7 5 3 2 0 6 and not 0 1 2 3 4 5 6 7 8 9. Simply adding a sort operation in "rect" fixes this, but the same solution wont work for a document with multiple lines.

So my question is: How do I sort the contours from left to right and top to bottom?

Farmhouse

Could you add an example of the contents for rect ? – Anticatalyst

rect contains (x,y,w,h) for each detected contours [(287, 117, 13, 46), (102, 117, 34, 47), (513, 116, 36, 49), (454, 116, 32, 49), (395, 116, 28, 48), (334, 116, 31, 49), (168, 116, 26, 49), (43, 116, 30, 48), (224, 115, 33, 50), (211, 33, 34, 47), ( 45, 33, 13, 46), (514, 32, 32, 49), (455, 32, 31, 49), (396, 32, 29, 48), (275, 32, 28, 48), (156, 3 2, 26, 49), (91, 32, 30, 48), (333, 31, 33, 50)] This is for the above example. (0-9) – Farmhouse

@ZdaR I asked it first. The other one is a duplicate. – Farmhouse

Ok I understand, But you can take some pointers from that question to solve your problem. – Darcidarcia

Answer 1

I don't think you are going to be able to generate the contours directly in the correct order, but a simple sort as follows should do what you need:

First approach
Use a sort to first group by similar y values into row values, and then sorting by the x offset of the rectangle. The key is a list holding the estimated row and then the x offset.

The maximum height of a single rectangle is calculated to determine a suitable grouping value for nearest. The 1.4 value is a line spacing value. So for both of your examples nearest is about 70.

import numpy as np

c = np.load(r"rect.npy")
contours = list(c)

# Example - contours = [(287, 117, 13, 46), (102, 117, 34, 47), (513, 116, 36, 49), (454, 116, 32, 49), (395, 116, 28, 48), (334, 116, 31, 49), (168, 116, 26, 49), (43, 116, 30, 48), (224, 115, 33, 50), (211, 33, 34, 47), ( 45, 33, 13, 46), (514, 32, 32, 49), (455, 32, 31, 49), (396, 32, 29, 48), (275, 32, 28, 48), (156, 32, 26, 49), (91, 32, 30, 48), (333, 31, 33, 50)] 

max_height = np.max(c[::, 3])
nearest = max_height * 1.4

contours.sort(key=lambda r: [int(nearest * round(float(r[1]) / nearest)), r[0]])

for x, y, w, h in contours:
    print(f"{x:4} {y:4} {w:4} {h:4}") 
    

Second approach
This removes the need to estimate a possible line height and also allows for possible processing by line number:

1. Sort all the contours by their y-value.
2. Iterate over each contour and assign a line number for each.
3. Increment the line number when the new y-value is greater than max_height.
4. Sort the resulting by_line list which will be in (line, x, y, w, h) order.
5. A final list comprehension can be used to remove the line number if it is not required (but could be useful?)

# Calculate maximum rectangle height
c = np.array(contours)
max_height = np.max(c[::, 3])

# Sort the contours by y-value
by_y = sorted(contours, key=lambda x: x[1])  # y values

line_y = by_y[0][1]       # first y
line = 1
by_line = []

# Assign a line number to each contour
for x, y, w, h in by_y:
    if y > line_y + max_height:
        line_y = y
        line += 1
        
    by_line.append((line, x, y, w, h))

# This will now sort automatically by line then by x
contours_sorted = [(x, y, w, h) for line, x, y, w, h in sorted(by_line)]

for x, y, w, h in contours:
    print(f"{x:4} {y:4} {w:4} {h:4}")

Both would display the following output:

  36   45   33   40
  76   44   29   43
 109   43   29   45
 145   44   32   43
 184   44   21   43
 215   44   21   41
 241   43   34   45
 284   46   31   39
 324   46    7   39
 337   46   14   41
 360   46   26   39
 393   46   20   41
 421   45   45   41
 475   45   32   41
 514   43   38   45
  39  122   26   41
  70  121   40   48
 115  123   27   40
 148  121   25   45
 176  122   28   41
 212  124   30   41
 247  124   91   40
 342  124   28   39
 375  124   27   39
 405  122   27   43
  37  210   25   33
  69  199   28   44
 102  210   21   33
 129  199   28   44
 163  210   26   33
 195  197   16   44
 214  210   27   44
 247  199   25   42
 281  212    7   29
 292  212   11   42
 310  199   23   43
 340  199    7   42
 355  211   43   30
 406  213   24   28
 437  209   31   35
 473  210   28   43
 506  210   28   43
 541  210   17   31
  37  288   21   33
  62  282   15   39
  86  290   24   28
 116  290   72   30
 192  290   23   30
 218  290   26   41
 249  288   20   33
 

Anticatalyst

That did work for the digits above, however they seem to fail for sorting text contours. Here's the contours detected for the sample text: i.imgur.com/b3fnDFP.jpg The contours (after sorting) aren't in the order of the text but in the order "Dkhdf?oyou...." Anyway I can fix this? – Farmhouse

Are you able to give me the updated rect list? It should just be a matter of adjusting the nearest value which should be roughly the expected height of a word. i.e. try 20. – Anticatalyst

Here is another Image I used. i.imgur.com/VUHrGDQ.jpg And here is the rect list drive.google.com/open?id=0BwuAHXrh5YRTSlV0UG5XSEsxVlU – Farmhouse

For the examples you have given, a value of around 70 appears to work. I have updated the script to estimate this based on the tallest rectangle and an estimated line spacing value. – Anticatalyst

For OpenCV3 I am getting the error TypeError: only length-1 arrays can be converted to Python scalars for the contours.sort... line. Is there anything I need to change? – Lifeboat

I have updated it to use the npy file you provided which it seems work ok with. Is the data you have different to that? – Anticatalyst

This works for me as well, but can someone explain the logic behind this formula to me? I cannot figure out what the 1.4 * max_height is doing, or what the sort-key represents. – Allegedly

max_height is the highest height of any rectangle. There is spacing between lines, this is estimated as 1.4 times the maximum height of a rectangle. The formula in the key is in effect giving each rectangle a row and column. Try using the same formula manually on a few rectangles to see the values it gives. – Anticatalyst

I've modified the key to make it use a list, so the first element is a row, and the second value is the x offset of the rectangle. – Anticatalyst

@MartinEvans Thank you for your great approach. How could we find the line spacing value automatically? It could be better if it is dynamic for every image. – Parrot

@quents, I've added an alternative approach which assigns line numbers to each contour, this avoids the need for line spacing and should work better for lines with uneven spacing or blank lines – Anticatalyst

Answer 2

While I solved my task I made such an approach (this one is not optimized and can be improved, I guess):

import pandas as pd
import cv2
import cv2
import matplotlib.pyplot as plt
import numpy as np
%matplotlib inline
import matplotlib
matplotlib.rcParams['figure.figsize'] = (20.0, 10.0)
matplotlib.rcParams['image.cmap'] = 'gray'

imageCopy = cv2.imread("./test.png")
imageGray = cv2.imread("./test.png", 0)
image = imageCopy.copy()

contours, hierarchy = cv2.findContours(imageGray, cv2.RETR_EXTERNAL, 
                                           cv2.CHAIN_APPROX_SIMPLE)
bboxes = [cv2.boundingRect(i) for i in contours]
bboxes=sorted(bboxes, key=lambda x: x[0])

df=pd.DataFrame(bboxes, columns=['x','y','w', 'h'], dtype=int)
df["x2"] = df["x"]+df["w"] # adding column for x on the right side
df = df.sort_values(["x","y", "x2"]) # sorting

for i in range(2): # change rows between each other by their coordinates several times 
# to sort them completely 
    for ind in range(len(df)-1):
    #     print(ind, df.iloc[ind][4] > df.iloc[ind+1][0])
        if df.iloc[ind][4] > df.iloc[ind+1][0] and df.iloc[ind][1]> df.iloc[ind+1][1]:
            df.iloc[ind], df.iloc[ind+1] = df.iloc[ind+1].copy(), df.iloc[ind].copy()
num=0
for box in df.values.tolist():

    x,y,w,h, hy = box
    cv2.rectangle(image, (x,y), (x+w,y+h), (255,0,255), 2)
    # Mark the contour number
    cv2.putText(image, "{}".format(num + 1), (x+40, y-10), cv2.FONT_HERSHEY_SIMPLEX, 1, 
                (0, 0, 255), 2);
    num+=1
plt.imshow(image[:,:,::-1])

Original sorting: Up-to-bottom left-to-right: The original image, if you want to test it:

Broz

Answer 3

Given a binary image - thresh, I think the shortest way is -

import numpy as np
import cv2 

contours,hierarchy = cv2.findContours(thresh,cv2.RETR_EXTERNAL,cv2.CHAIN_APPROX_NON) #thresh is a bia
cntr_index_LtoR = np.argsort([cv2.boundingRect(i)[0] for i in contours])

Here, cv2.boundingRect(i)[0] returns just x from x,y,w,h = cv2.boundingRect(i) for the ith contour.

Similarly, you can use the top to bottom.

Delagarza

Answer 4

contours.sort(key=lambda r: round( float(r[1] / nearest))) will cause similar effect like (int(nearest * round(float(r[1])/nearest)) * max_width + r[0])

Cytherea

Answer 5

after finding the contours using contours=cv2.findContours(),use -

boundary=[]
for c,cnt in enumerate(contours):
    x,y,w,h = cv2.boundingRect(cnt)
    boundary.append((x,y,w,h))
count=np.asarray(boundary)
max_width = np.sum(count[::, (0, 2)], axis=1).max()
max_height = np.max(count[::, 3])
nearest = max_height * 1.4
ind_list=np.lexsort((count[:,0],count[:,1]))

c=count[ind_list]

now c will be sorted in left to right and top to bottom.

Nobel

Answer 6

A simple way to sort contours with the bounding box (x, y, w, h) of the contours left to right, top to bottom is as follows.

You can get the bounding boxes using the boundingBoxes = cv2.boundingRect() method

def sort_bbox(boundingBoxes):
'''
function to sort bounding boxes from left to right, top to bottom
'''
    # combine x and y as a single list and sort based on that 
    boundingBoxes = sorted(boundingBoxes, key=lambda b:b[0]+b[1], reverse=False))
    return boundingboxes

The method is not extensively tested with all the cases but found really effective for the project I was doing.

Link to sorted function documentation for reference https://docs.python.org/3/howto/sorting.html

Hui

Answer 7

def sort_contours(contours, x_axis_sort='LEFT_TO_RIGHT', y_axis_sort='TOP_TO_BOTTOM'):
    # initialize the reverse flag
    x_reverse = False
    y_reverse = False
    if x_axis_sort == 'RIGHT_TO_LEFT':
        x_reverse = True
    if y_axis_sort == 'BOTTOM_TO_TOP':
        y_reverse = True
    
    boundingBoxes = [cv2.boundingRect(c) for c in contours]
    
    # sorting on x-axis 
    sortedByX = zip(*sorted(zip(contours, boundingBoxes),
    key=lambda b:b[1][0], reverse=x_reverse))
    
    # sorting on y-axis 
    (contours, boundingBoxes) = zip(*sorted(zip(*sortedByX),
    key=lambda b:b[1][1], reverse=y_reverse))
    # return the list of sorted contours and bounding boxes
    return (contours, boundingBoxes)
    

contours, hierarchy = cv2.findContours(img_vh, cv2.RETR_TREE, cv2.CHAIN_APPROX_SIMPLE)
contours, boundingBoxes = sort_contours(contours, x_axis_sort='LEFT_TO_RIGHT', y_axis_sort='TOP_TO_BOTTOM')

Melodize