PgSql: how could I achive a group by that checks any match on any of two columns?

Question

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

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)

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

3. 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.

4. 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))?

Answer 1

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.