# Fast contour set comparison?

**URL:** <https://forum.opencv.org/t/fast-contour-set-comparison/13426>\
**Category:** Python\
**Tags:** contours\
**Created:** [June 6, 2023, 7:51pm UTC](https://forum.opencv.org/t/fast-contour-set-comparison/13426 "2023-06-06T19:51:55Z")\
**Posts on this page:** 5\
**Page:** 1

<div class="post-metadata">

**Author:** ![Stuart\_Reynolds](https://sea2.discourse-cdn.com/flex020/user_avatar/forum.opencv.org/stuart_reynolds/32/4079_2.png) [@Stuart\_Reynolds](https://forum.opencv.org/u/Stuart_Reynolds)\
**Post date:** [June 6, 2023, 7:51pm UTC](https://forum.opencv.org/t/fast-contour-set-comparison/13426/1 "2023-06-06T19:51:55Z")

</div>

Suppose that I have a whole bunch of masks describing contours/patches of objects in an image. Is there an efficient way to test contours for similarity between images? (I’d like to avoid N\*N, particularly on whole-image masks).

I have N masks describing object contours for each scene (the output of a segmener)  
I’d like to compare the masks for similarity between scenes (the objects are static in the scene - I don’t care about translation, or rotation invariance, but its possible the contours might be chomped into by occluding objects). Mostly I want to identify what’s the same and what’s new/gone.

I could use their mask’s IOU here - but that seems a little expensive.

It seems that run-length-encodings of the masks could do the same much cheaper. Are there alternatives I might consider?

Thanks in advance.

---

<div class="post-metadata">

**Author:** ![crackwitz](https://sea2.discourse-cdn.com/flex020/user_avatar/forum.opencv.org/crackwitz/32/14_2.png) [@crackwitz](https://forum.opencv.org/u/crackwitz)\
**Post date:** [June 7, 2023, 6:33am UTC](https://forum.opencv.org/t/fast-contour-set-comparison/13426/2 "2023-06-07T06:33:13Z")

</div>

> [@Stuart\_Reynolds](#):
>
> I could use their mask’s IOU here - but that seems a little expensive.

no. that’s dirt-cheap to calculate because it’s parallelizable in every way (SIMD, threading, GPU, …) and is already parallelized without you doing anything (SIMD, threading) or very little (GPU: `UMat`).

those neural networks emit masks, not contours, and calculating a contour from a mask is a little more complex.

moving away from masks also potentially forces you to spend that O(N^2) figuring out which goes with what, or coming up with further smart algorithms to make that lookup more efficient.

IoU is trivial in comparison.

also, “similarity” is usually the word to describe **shape** (i.e. shape matching/description) or any semantic content. since you consider IoU a valid solution, you seem to want to estimate overlap over time.

---

<div class="post-metadata">

**Author:** ![Stuart\_Reynolds](https://sea2.discourse-cdn.com/flex020/user_avatar/forum.opencv.org/stuart_reynolds/32/4079_2.png) [@Stuart\_Reynolds](https://forum.opencv.org/u/Stuart_Reynolds)\
**Post date:** [June 7, 2023, 7:22pm UTC](https://forum.opencv.org/t/fast-contour-set-comparison/13426/3 "2023-06-07T19:22:41Z")

</div>

I wouldn’t say its a trivial computation.

Naively:

```auto
def iou(mask1, mask2):
    return (mask1 & mask2).sum() / (mask1 | mask2).sum()

t = time.time()
for m1 in masks:
    for m2 in masks:
        iou(m1,m2)
print(f'{time.time()-t}:3.1f')

```

takes almost 9 seconds on my 24 core 3900x.  
(here with ~24 masks).

I can spend time optimizing this… but what I’m looking for is a algorithm that efficiently compares the outlines of masks. Even this IOU case isn’t too great for me because new object the scene take a chomp out of the masks existing segments – the IOU score penalizes the lost space even though the contour may be very similar. Something like IOU of the contour mask with `contourmask = mask & ~erode(mask,n)` masks might be better for measuring whether a blob has the same shape? Perhaps there are even better measures of shape difference.

---

<div class="post-metadata">

**Author:** ![crackwitz](https://sea2.discourse-cdn.com/flex020/user_avatar/forum.opencv.org/crackwitz/32/14_2.png) [@crackwitz](https://forum.opencv.org/u/crackwitz)\
**Post date:** [June 8, 2023, 10:56am UTC](https://forum.opencv.org/t/fast-contour-set-comparison/13426/4 "2023-06-08T10:56:37Z")

</div>

> [@Stuart\_Reynolds](#):
>
> ```auto
> for m1 in masks:
> for m2 in masks:
> 
> ```

you only do that because you cut the labels map apart into individual components. don’t do that.

just _keep_ the entire picture with labels, then `labels1 == labels2` to get overlap, then recombine with labels to count intersection pixels.

please clarify: do objects move? do you require the movement to be compensated in the calculation, i.e. the same object, translated, still gives 100% “overlap”?

---

<div class="post-metadata">

**Author:** ![Stuart\_Reynolds](https://sea2.discourse-cdn.com/flex020/user_avatar/forum.opencv.org/stuart_reynolds/32/4079_2.png) [@Stuart\_Reynolds](https://forum.opencv.org/u/Stuart_Reynolds)\
**Post date:** [June 8, 2023, 5:02pm UTC](https://forum.opencv.org/t/fast-contour-set-comparison/13426/5 "2023-06-08T17:02:01Z")

</div>

That’s how the labels come to me. (And yes, n^2 is naive - lots to save be checking bbox overlaps, etc.).  
The masks I get are in a hierarchy (they overlap). I can build some kind of representation for it.  
But again, was kinda hoping there are already tools for this (actually the cv2 contours API talk about hierarchies … 🤔 ).