[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