3

I am trying to implement a NMS filter for labels in a Database.

NMS is a filter that removes redundant squares. On the image provided we can see there is only one tree, but there are three labels surrounding it.

The filter will acknowledge those squares share a big proportion of their areas and merge them or leave only one square.

Basically I have an image with squares and I need to pass from (1) to (2). the boxes are stored on a table called "Labels" and it has

string id   //(uuid, is string for compatibility to sqlite),
int top,
int left,
int right,
int bottom

(1)what I have, (2) goal

The picture shows 2 scenarios. The first one (1) is the current state, and the second one (2) is what I aim to get.

The table describing the first image data is the following (instead of uuid I'll just write the corresponding square's color)

id top left right bottom
orange 10 15 29 60
red 12 16 30 58
grey 11 10 28 61
green 20 23 45 44
blue 22 25 44 41

and the second one (the one I aim to get) is

id top left right bottom
orange 10 15 29 60
blue 22 25 44 41

What I got so far:

  1. I can get a combinatory of each label compared with each other.

     select l1.id, l2.id, ..*
     from labels l1
     left join labels l2
     on l1.id =! l2.id
    
  2. I can obtain the IoU score between the joined labels (IoU is IntersectionArea/UnionArea, an score that goes from 0 to 1, 1 being two squares that match perfectly, 0 meaning no match at all)

enter image description here

the area of the intersection can be described as the following:

greatest(least(l1.right,l2.right)-greatest(l1.left,l2.left),0) * greatest(least(l1.bottom,l2.bottom)-greatest(l1.top,l2.top),0)

and the area of the union is just the sume of the two independent areas minus the intersection area

  1. I can remove the repeated redundant columns that the first query returns by joining the ids in an ordered way and grouping.

     select concat(least(l1.id, l2.id),greatest(l1.id, l2.id)),
            min(l1.id) as id2, max(l2.id), min(IoU)
     from Labels as l1
     left join Labels as l2 on l1.id!=l2.id
     group by concat(least(l1.id, l2.id),greatest(l1.id, l2.id))
     where IoU > 0.85
    

with this I get only once the results of pairs like orange-grey and grey-orange (on both IoU should be the same).

the result is something like this

concat id id2 IoU
grayorange orange gray 0.9
orangered orange red 0.91
grayred gray red 0.88
bluegreen green blue 0.86

Where I need help.

  1. this step should realize that squares orange, grey, and red are all related.

If I group the table 3 by id, I would be getting that the two first squares are related.

If I group the table 3 by id2, I would be getting that the two squares in the middle are related.

and by inspection, can see that the first an third register are also related (since gray appears on column id and id2)

How can I group together the three first registers on the table?

Is there a function on pgsql that can help on this problem?

Do any trick come to your mind?, like what I did to remove the duplicates using concat(least(id,id2),greatest(id,id2))?

2
  • Your update seems to indicate you've successfully self-answered your original question ("How to do it"). If so, I encourage you to revert your edit and move it to a self-answer. "How to optimize" should be another (linked) question. Oct 27, 2022 at 16:00
  • @PeterVandivier that's good, I will do what you say. Thank you for the advice and good practice.
    – J Pablo F
    Oct 29, 2022 at 16:21

1 Answer 1

2

As @ypercubeᵀᴹ suggested in comments. I looked for transitive clauses and recursive CTE. Based on this question I wrote the following query to get the matching groups.

The query that achieves that is the following

with recursive data as ( /*(a) ,(b)*/
    select  l1.id,
            array [l1.id,l2.id] as ids,
            greatest(least(l1.right,l2.right) - greatest(l1.left,l2.left),0) * greatest(least(l1.bottom,l2.bottom) - greatest(l1.top,l2.top),0) as i, 
            (l1.right-l1.left)*(l1.bottom-l1.top) + (l2.right-l2.left)*(l2.bottom-l2.top) - greatest(least(l1.right,l2.right) - greatest(l1.left,l2.left),0) * greatest(least(l1.bottom,l2.bottom) - greatest(l1.top,l2.top),0) as u,
            (greatest(least(l1.right,l2.right) - greatest(l1.left,l2.left),0) * greatest(least(l1.bottom,l2.bottom) - greatest(l1.top,l2.top),0)::float)
                    /
                ((l1.right-l1.left)*(l1.bottom-l1.top)
                + (l2.right-l2.left)*(l2.bottom-l2.top)
                - greatest(least(l1.right,l2.right) - greatest(l1.left,l2.left),0) * greatest(least(l1.bottom,l2.bottom) - greatest(l1.top,l2.top),0))
            as iou
    from "IoAi".labelstry l1
    left join "IoAi".labelstry l2
        on l1.id != l2.id 
    where (greatest(least(l1.right,l2.right) - greatest(l1.left,l2.left),0) * greatest(least(l1.bottom,l2.bottom) - greatest(l1.top,l2.top),0)::float)
                    /
                ((l1.right-l1.left)*(l1.bottom-l1.top)
                + (l2.right-l2.left)*(l2.bottom-l2.top)
                - greatest(least(l1.right,l2.right) - greatest(l1.left,l2.left),0) * greatest(least(l1.bottom,l2.bottom) - greatest(l1.top,l2.top),0))
        > 0.6
),
grouped_data(id, ids) as( /*(c)*/
    select id, ids 
    from data
    union   
    select d.id, iou_array_merge(d.ids, gd.ids)
    from grouped_data gd
    join data d
    on gd.ids && d.ids 
), selected_data as( /*(d)*/
    select array_agg(id) as ids
    from (
        select distinct on(id) *
        from grouped_data
        order by id, cardinality(ids) desc
        ) s
    group by ids
)
select sd.ids as grouped, l1.* from selected_data sd /*(e)*/
left join "IoAi".labelstry l1
on l1.id = sd.ids[1]
  • a) The only recursive table is the second one, grouped_data. Postgres syntax demands the keyword recursive to be in the first with.
  • b) "data" query obtains the "intersection over union" (IoU) score between two labels and discards those that are less than 0.6
  • c) "grouped_data" uses the result from "data" and recursiveness to join all groups that share one common element
  • d) "selected_data" filters the result from "grouped_data" to retrieve the largest groups
  • e) the last query selects the first element of each group (arbitrary criteria) and joins the label'

These are the sub-query results:

data:

id ids I U IoU
orange {orange,red} 598 746 0.8016085790884718
orange {orange,grey} 637 963 0.6614745586708204
red {red,orange} 598 746 0.8016085790884718
grey {grey,orange} 637 963 0.6614745586708204
green {green,blue} 361 528 0.6837121212121212
blue {blue,green} 361 528 0.6837121212121212

grouped_data:

id ids
orange {orange,red}
orange {orange,grey}
red {red,orange}
grey {grey,orange}
green {green,blue}
blue {blue,green}
orange {grey,orange,red}
orange {grey,orange}
red {orange,red}
red {grey,orange,red}
grey {grey,orange,red}
green {blue,green}

selected_data:

ids
{grey,orange,red}
{blue,green}

this is the final result.

grouped id top left right bottom
{grey,orange,red} grey 11 10 28 61
{blue,green} blue 22 25 44 41

Is worth to notice that I got the gray square instead of orange. Which one I get is not important yet.

I also added the grouped column, this one will be important on future to actually delete the duplicated registers.

I will point out that I don't fully understand this method, and I would love to know if there is a more efficient way of doing this since the query takes like 2 seconds to process the data and I got the feeling that there are some clumsy steps in my solution.

I've also done a follow-up posted here asking for help optimizing this method.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.