# Identify the correct spot to place a label

In the image shown below, I have a 2D data set where I have identified four clusters labeled [0,1,2,3]. I'm looking for an algorithm to place the labels in a natural* way for each shape. My first guess was to place them in the "center-of-mass" of the cluster, which is shown below. For contiguous clusters this works fine. For clusters that take a shape as in cluster 0 however, the approach fails. Without using a legend, what would be a better method to place the labels on this image?

* natural here is subjective to some extent, but the point of the labels is to help the viewer associate a certain region in the x-y plane with a number.

• Welcome to DSP.SE. This is a great question! = ) – Phonon Mar 29 '12 at 20:38
• @Hooked If the clusters are modelled as 2-dimensional gaussians of a mean and a 2x2 covariance matrix, then I would think the natural placement would simply be the mean of the gaussians. Have you already determined the mean of your clusters? – Spacey Mar 30 '12 at 0:07

What about putting the label at the innermost point of the segment? Let's define innermost by the maximum of the distance transform of the segment's mask.

With software systems like Mathematica and the sort, it is straightforward to achieve.

The mask for one segment, and its distance transform:

After repeating for each segment and positioning labels where the individual distance transforms are maximum:

• Do you mind on elaborating a bit on what "innermost" means? I don't have access to Mathematica (using python), but I should be able to code any solution presented. – Hooked Mar 30 '12 at 13:08
• @Hooked See the edit. If you have access to a function computing the distance transform you are all set. – Matthias Odisio Mar 30 '12 at 13:41
• This looks great and I don't think it will be to hard to implement myself. Just to be clear, is the transform you applied is the "... the distance transform of image, in which the value of each pixel is replaced by its distance to the nearest background pixel."? – Hooked Mar 30 '12 at 13:44
• Yes, that's this. It won't be hard to implement this solution, provided you don't have to code a distance transform function yourself (fast implementations are trickier to code) – Matthias Odisio Mar 30 '12 at 13:49

I submit that the ideal place to place the label should meet two objectives:

• proximity to the center, say $d$.
• legibility, say $l$.

Ergo, we can determine the ideal point by minimizing a holistic metric such as $l \times d^\alpha$ or $l+\alpha d$, where $\alpha$ is the trade-off parameter.

Determining $d$ is straightforward. $l$ can be set to the total variation (or some other measure of the level of detail) under the area taken up by the label. You can set this to a high number in regions outside the segment to avoid the problem in your example.

The rest is numerical optimization.

• This seems like a good approach and robust enough for a picture with higher detail. Is your proximity to the center, $d$, what I'm calling the "center-of-mass" or what @MatthiasOdisio calls the "innermost point"? – Hooked Mar 30 '12 at 13:11