How to sort boundary boxes from right to left and top to bottom

Question

I have a use case where I want to sort boundary boxes from the top right to the bottom left.

args: dt_boxes(array): detected text boxes with shape [4, 2] return: sorted boxes(array) with shape [4, 2]

Example 1:

[[[258.0, 52.0], [329.0, 46.0], [329.0, 72.0], [260.0, 76.0]], [[91.0, 32.0], [174.0, 43.0], [175.0, 68.0], [90.0, 64.0]], [[182.0, 45.0], [266.0, 42.0], [266.0, 69.0], [184.0, 74.0]], [[16.0, 41.0], [97.0, 39.0], [98.0, 64.0], [17.0, 69.0]], [[226.0, 4.0], [296.0, 4.0], [296.0, 32.0], [227.0, 35.0]], [[288.0, 9.0], [331.0, 2.0], [331.0, 36.0], [289.0, 39.0]]]

Example 2:

[[[224.0, 85.0], [381.0, 83.0], [381.0, 128.0], [223.0, 126.0]], [[412.0, 88.0], [544.0, 81.0], [545.0, 129.0], [413.0, 134.0]], [[291.0, 18.0], [357.0, 18.0], [357.0, 56.0], [292.0, 68.0]], [[122.0, 12.0], [295.0, 11.0], [296.0, 57.0], [125.0, 64.0]], [[350.0, 22.0], [435.0, 11.0], [435.0, 55.0], [351.0, 66.0]], [[442.0, 15.0], [538.0, 11.0], [539.0, 49.0], [442.0, 57.0]], [[9.0, 12.0], [125.0, 8.0], [127.0, 54.0], [10.0, 63.0]]]

I have used the sort function like this to sort using the 2nd element (Top Right) and 3rd Element (Bottom Right) in the array but it doesn't provide the correct sorting

Results to be achieved :

Boundaries are upper left, upper right, lower right, and lower left.

sorted_boxes = sorted(dt_boxes, key=lambda x: (x[1][1], x[1][0]),reverse=True)

Hi! Could you please clarify a little bit how your bounding boxes are defined? This `[[[[[` is kinda scary. Which coordinate is which coordinate? Also, are the bounding boxes axis-aligned (ie with horizontal and vertical sides) or not? — Stef, Feb 14 '23 at 14:44
Also please add what you are currently getting for `sorted_boxes` for your examples, and what you expect to get. — RufusVS, Feb 14 '23 at 14:46
@Stef I have modified the question please let me know if it make sense now — ahmed osama, Feb 14 '23 at 14:57
@RufusVS current sorting is just the points to the right corner without having the top to bottom sorting — ahmed osama, Feb 14 '23 at 14:58
One last info that we're missing: can you please show the axes in your figure? In math it's customary to have x point rightwards and y point upwards, but in screens it's customary to have x point rightwards and y point downwards. — Stef, Feb 14 '23 at 14:59
I think your main issue is the way you used `reverse=True`, and how that combines with wanting to sort **right-to-left, top-to-bottom** as opposed to **top-to-bottom, right-to-left**. — Stef, Feb 14 '23 at 15:10
As a simple trick to avoid these kinds of mistake, is suggest not using `reverse=True`, and instead using negative signs inside the `key`. Instead of sorting by `(y, x)`, sort by `(-y, -x)` to reverse the order. — Stef, Feb 14 '23 at 15:11
After your last edit, it turns out your y -axis is top-to-bottom already, so you probably want to sort according to `(y, -x)`. Assuming the upper-right corner is point number 3 in your lists, use `sorted(dt_boxes, key=lambda b: b[3][1], -b[3][0])`. — Stef, Feb 14 '23 at 15:52
Or sort according to the centre of gravity of the boxes instead of a particular corner: `sorted(dt_boxes, key=lambda b: (sum(y for _,y in b), -sum(x for x,_ in b)))` — Stef, Feb 14 '23 at 15:53
@Stef , Your solution is good but it doesn't work with a situation like this `[[[529.0, 10.0], [597.0, 0.0], [598.0, 40.0], [530.0, 43.0]], [[437.0, 18.0], [531.0, 12.0], [534.0, 53.0], [445.0, 60.0]], [[317.0, 35.0], [438.0, 22.0], [448.0, 68.0], [321.0, 89.0]], [[498.0, 91.0], [613.0, 71.0], [617.0, 110.0], [501.0, 134.0]], [[368.0, 105.0], [502.0, 82.0], [505.0, 126.0], [367.0, 153.0]], [[200.0, 112.0], [335.0, 110.0], [336.0, 147.0], [202.0, 157.0]], [[80.0, 134.0], [208.0, 124.0], [211.0, 167.0], [90.0, 188.0]]]` — ahmed osama, Feb 15 '23 at 12:24
Dear ahmedosama. I do not know what "doesn't work" mean in this case. Nor what is a "situation like this". A picture would help. Also, I provided two different `sorted(...)` suggestions, so I don't know which one you mean when you say "your solution". Note that for my first suggestion, I said *"Assuming the upper-right corner is point number 3 in your lists"*. I do not know whether that assumption is right or wrong on your lists. — Stef, Feb 15 '23 at 12:52
Dear @Stef . Thanks very much for your help. Number 3 on my list is in the lower-right corner. Your help let me establish a primary solution, not perfect, My solution is to get the center point from the lower-right corners then make upper line and lower line array finally sort them individually then concatenate — ahmed osama, Feb 21 '23 at 11:33

score 0 · Answer 1 · answered Feb 21 '23 at 11:40

My Primary Solution is

Get the Middle point from the lower right corners
Create Upper Line and Lower Line Array
Sort two lines using the negative value of the X coordinates of upper left corner
Combine the two lines in one array

Solution Code:

    bottom_right_corners = [r[2] for r in dt_boxes]
       
    mid_point = (np.amax(bottom_right_corners, axis=0)[1] - np.amin(bottom_right_corners, axis=0)[1]) // 2
    top_labels = []
    bottom_labels = []
    
    for dt_box in dt_boxes:
        if dt_box[1][1] <= mid_point:
            top_labels.append(dt_box)
        else:
            bottom_labels.append(dt_box)
    
    print (f"Top Line Len {len(top_labels)} , Bottom Line len {len(bottom_labels)} and Medium Point {mid_point}")
    sorted_boxes_top = sorted(top_labels, key=lambda x:  -x[0][0])
    
    sorted_boxes_bottom = sorted(bottom_labels, key=lambda x: -x[0][0])
    
    _boxes = [*sorted_boxes_top , *sorted_boxes_bottom]

My solution is not working if I have more than 2 lines. Any suggestion

Instead of creating the two lines manually, you could do clustering on the y-values. Each cluster corresponds to 1 line. See https://stackoverflow.com/questions/11513484/1d-number-array-clustering for instance. — Stef, Feb 21 '23 at 11:43

How to sort boundary boxes from right to left and top to bottom

1 Answers1