[LabelAnnotator, RichLabelAnnotator, VertexLabelAnnotator] - add smart label positioning

[SkalskiP]

Description

Overlapping labels are a common issue, especially in crowded scenes. Let's add an optional smart label positioning feature to the LabelAnnotator, RichLabelAnnotator, and VertexLabelAnnotator that:

• Ensures that the label box does not extend beyond the image.
• Automatically adjust the position of overlapping labels to prevent them from overlapping.

The algorithm boils down to locating overlapping label boxes and then calculating the direction of vectors to push the labels apart. This process may require an iterative approach, as moving label boxes can lead to new overlaps with other label boxes.

Importantly, the bounding box remains in the same place, only the label boxes are moved. It would be great if, after the shift, the label and its original position were connected by a line.

Examples of incorrect behavior

Examples of expected behavior

vertex-label-annotator-v1-optimized.mp4

Here's the Google Colab I used to experiment with this feature.

Additional

• Note: Please share a Google Colab with minimal code to test the new feature. We know it's additional work, but it will speed up the review process. The reviewer must test each change. Setting up a local environment to do this is time-consuming. Please ensure that Google Colab can be accessed without any issues (make it public). Thank you! 🙏🏻

[jeslinpjames]

Hey, @SkalskiP

I'd like to try working on this. Could you provide any specific guidelines or tips for implementing this feature?

[LinasKo]

We're opening this up to the community! @jeslinpjames, it's been a long time - are you still interested? I'll leave this open for a few days on the off-chance you're still around.

Edit: Assigning to you temporarily until I hear back or a few days pass.

[LinasKo]

With respect to the implementation details, I'm glad to see Piotr's plan as I had the exact same idea, down to the connector line.

1. The mentioned annotators would have a new argument use_smart_positioning, activating this feature if set to True.
2. Let's treat the annotators as independent. If two different LabelAnnotators are used at once, let's allow their labels to overlap, even if this feature is on.
3. Unmentioned annotators that use labels can be ignored (LineZoneAnnotator, PolygonZoneAnnotator).
4. There are alternate approaches to this.

Let's start with the simplest one:

• If two boxes intersect with another box, move it either along x or y, based on where the overlap is SMALLEST (this minimizes the distance we need to move).
• Move proportionally to overlap size size, but with a cap. When everything moves at once, large movements may cause even greater overlaps. (similar to gradient descent!)
• region boundaries should not allow labels to escape. They should reset the labels to the nearest possible position, at least along one axis. Even if the label moved or started out-of-bounds.

An upgraded version of this would take into account both x and y axes of the overlap and allow arbitrary motion direction. Implement this if you wish, but take care to minimize motion - overemphasize the motion along the SMALLER overlap direction.

An even more robust system uses some random noise to avoid stable states. We don't need this much detail 😉

find_smart_rectangle_positions(
    xyxy: npt.NDarray[float], shape (H, W, 4).
    region_boundary_wh: (float, float)  # This is a hard boundary on the edges.
    max_iterations=10:  # return if there are no overlaps or this many iterations have passed.
    force_multiplier=1.0  # Make the movements larger.
)

5. You may find the function cv2.getTextSize helpful.
6. Before drawing the label boxes, each annotator should draw a line between the center of the old and new label locations.

Whoever ends up working on this, I hope it gives you some ideas of how this could work!

[LinasKo]

Contribution guidelines

If you would like to make a contribution, please check that no one else is assigned already. Then leave a comment such as "Hi, I would like to work on this issue". We're happy to answer any questions about the task even if you choose not to contribute.

Please share a Google Colab with minimal code to test the new feature. We know it's additional work, but it will speed up the review process. You may use the Starter Template. The reviewer must test each change. Setting up a local environment to do this is time-consuming. Please ensure that Google Colab can be accessed without any issues (make it public). Thank you! 🙏

[kshitijaucharmal]

I know this issue is already assigned to @jeslinpjames, but reading this:

Edit: Assigning to you temporarily until I hear back or a few days pass.

I would like to work on this issue as well.

[LinasKo]

Hi @kshitijaucharmal 👋

Indeed, I'm opening this up to the community.
It's yours - best of luck!

[LinasKo]

Hi @kshitijaucharmal,

How's the task going? Do you have any updates for us? 😉

[kshitijaucharmal]

Yeah I have made some progress, specifically:

1. In the VertexLabelAnnotator, used the test code given by @SkalskiP in his collab to label vertex points without ovelapping.
2. Tried out on the Basketball example and seems to work fine.

I still haven't gotten around to implementing it as an optional feature (using argument use_smart_positioning) and also after it works for VertexLabel, to implement it for the other annotators.

PS: Sorry its taking some time, my college exams are going on and I'm getting enough time for this :(

[LinasKo]

All of that sounds like great progress. Very glad to hear that.

Take your time! Our timeline is to have a PR for this next Friday. This way, I can pitch in the week after, in case the PR still needs some help 😉

[kshitijaucharmal]

Glad to hear that! I'll definitely raise a PR before Friday

[kshitijaucharmal]

Sorry it took a while, had completed it earlier but couldn't raise a PR. I have raised the #1625 PR with the latest changes.

PS: I know this was for hacktoberfest, but I will continue working on it after that too

[kshitijaucharmal]

I have done all the changes required in #1625, please let me know any changes required
Also I cannot assign anyone to review this PR, I don't have permission for it i guess @LinasKo

[LinasKo]

Hey @kshitijaucharmal,

Sorry it took a while, had completed it earlier but couldn't raise a PR.

It's quite alright. I'm sure I can find the time to help it past the finish line before the new supervision release.

Do you have a Colab where I could see the changes?

[kshitijaucharmal]

Thanks! Don't have a Collab cause I tested it locally in a venv, but can make one if you want.

I also have put the result videos in the PR comment, but tell me if the Collab is required

[LinasKo]

Colab is amazing for us, as we can:

• Quickly evaluate how well the code works
• Tweak the testing code to make sure the contributor didn't miss anything (most issues discovered here)
• Have a bit of history we can look back at when implementing new features / checking for regressions

Because of that, it's really important for us 😉

Feel free to use the starter template if you find it helpful, but it's also fine if you make your own.

[kshitijaucharmal]

Okay, I'll be glad to provide you with a Collab as soon as I can

[kshitijaucharmal]

Hey @LinasKo, I'm really not understanding the problem here cause this command:
!pip install "supervision[assets] @ git+https://github.com/kshitijaucharmal/supervision.git@develop"
works, even resolves to the latest commit hash on my fork, but somehow after importing supervision just goes back to the base version on collab. Doesn't happen locally from the same command, so I don't understand the issue, please help me on this :)

Latest Commit Hash (which is detected by pip): ecf5b13

Here is the link: https://colab.research.google.com/drive/1GPHr7PpZ_eNs8Gkxx_A4w6PL5p4pJAn1?usp=sharing

[LinasKo]

Small chance, but if you haven't tried entirely recreating the environment with Runtime -> Disconnect and delete Runtime, it might help.

[kshitijaucharmal]

Nope, doesn't work, even tried all the other runtime types.

ERROR: pip's dependency resolver does not currently take into account all the packages that are installed. This behaviour is the source of the following dependency conflicts.
inference 0.24.0 requires supervision<=0.22.0,>=0.21.0, but you have supervision 0.24.0 which is incompatible.

Gonna try using ultralytics now

[kshitijaucharmal]

UPDATE: Works now, changed supervision[assets] to supervision only.

• Found an error, passing an empty image breaks the pad method in utils, will fix in in the next commit