Sorting Boxes on a Page(2D Plane) top to bottom, left to right. (Python)

user_14949373 0
Viewed 518

I am trying to sort boxes which are result of OCR engine. The bounding boxes from the engine are random and not in any particular sorting. I would like to sort the boxes from left to right, top to bottom. Which is the boxes in same row(line) should be sorted left to right, and than it should go to below row(line) and sort it left to right and so on.

I have all the 4 points of each rectangle(box)

Here are some sample Images.

Sample Image 1

Sample Image 2

Sample Image 3

opencv ocr sorting python
3 Answers

You can use sorted function, which is build-in Python function, as below (this code supposes that rects are stored as tuples of (x, y, width, height) or (x1, y1, x2, y2):

from operator import itemgetter, attrgetter
rects = [(8, 10, 10, 10), (0, 5, 10, 10), (0, 0, 10, 10), (1, 10, 10, 10)]

rects = sorted(rects, key=itemgetter(1,0))

Result:

[(0, 0, 10, 10), (0, 5, 10, 10), (1, 10, 10, 10), (8, 10, 10, 10)]
user_148436350

Here is a proposition:

  • Sort by vertical coordinate of the center of the box;
  • Two boxes that are adjacent in the sorted list are considered "on the same line" if their vertical overlap is greater than 50% of the height of the first box.

We'll use python's sorted and more_itertools.split_when to sort then group according to these criteria.

from more_itertools import split_when

def get_y_center(b):
    up, down= b[0], b[2]
    return (up + down) / 2

def not_vertically_overlapping(b1, b2):
    up1, down1 = b1[0], b1[2]
    up2, down2 = b2[0], b2[2]
    return down1 < up2 or (down1 - up2) < (up2 - up1) 

def groupbyrow(boxes):
    sorted_boxes = sorted(boxes, key=get_y_center)
    return list(split_when(sorted_boxes, not_vertically_overlapping))

Testing:

import random
import matplotlib.pyplot as plt
import matplotlib.colors as mcolors

# GENERATE RANDOM BOXES

centers = [(random.gauss(i, 5),random.gauss(j,0.25)) for i in range(0,40,10) for j in range(0,40,2)]
random.shuffle(centers)
boxes = [(y-(h:=random.gauss(1,0.25)),x-(w:=random.gauss(5,2)),y+h,x+w) for x,y in centers]

# GROUP BOXES BY ROW

rows = groupbyrow(boxes)

# DRAW BOXES WITH ONE COLOUR PER ROW

def draw_box(box, colour):
    u,l,d,r = box
    xs = [l, r, r, l, l]
    ys = [u, u, d, d, u]
    plt.plot(xs, ys, colour)

colours = list(mcolors.CSS4_COLORS.keys())

for i,row in enumerate(rows):
    for box in row:
        draw_box(box, colours[i])

plt.gca().set_aspect('equal')
plt.show()

Boxes coloured by row

user_30807230

Can you please summarize the rules you are considering to sort the boxes? Do you want to sort boxes in Zigzag order scanning? Anyway, if you want to apply a specific rule, you can pass your customized Comparator function to sorted function.

user_148436350
Related