# How to segment an image using a set of imperfectly drawn boundaries?

Consider the following image:

This is an image of a set of contours (the "contour image") that was drawn by a human using a mouse on another image (the "original image"). FWIW, the purpose of hand-drawing contour images like this is to create a dataset for eventually training a CNN to segment the images like the original image (the contents of the original image aren't important for this question, and it should be assumed that they cannot be segmented directly).

If one knows that the contours were drawn by a human using a mouse, then it's fairly easy for another human to see that the contour image intends to delineate 3 foreground regions and one background region. However, small imprecisions in the drawn contours make it non-trivial to segment the four regions, even if I know the number of regions in advance. If the contours follow a reasonably rigid template, then I can come up with heuristics based on that template that result in fairly good performance, but I don't have a general solution when either the particular set of contours deviates substantially from the template or when there isn't a template to base the heuristics on. Just to be clear, the desired segmentation for the above image is as follows:

Is there a good algorithm (or class of algorithms) for performing this kind of boundary-based segmentation on arbitrary imperfect boundary drawings? It seems to me like a common-enough computer vision problem, but so far I have not even been able to find a consistent name for this kind of segmentation problem.

Things I have tried:

• Variations on the watershed algorithm: unfortunately does not seem well designed for boundaries. One can filter the image with a Gaussian whose width is high enough that the output image resembles a topographic image, but I don't know a good method for picking the positions from which to start pouring water, and the blurring may cause the smaller watersheds to disappear.
• Performing random walks that cannot cross the black lines, starting from many random pixels, and keeping track of the number of times each pixel is visited by each random walker, then performing various clustering algorithms on the counts. This separates the closed regions (which can be done in other ways) but does not consistently separate the unclosed regions.
• Treating non-contour pixels as edges in a graph that are connected via edges to adjacent pixels that are also not in the contours, then performing Laplacian embedding; this also does not consistently separate the unclosed regions.
• Look up the method that computes the watershed of the distance transform of the image. It is often used to segment cells in microscopy images, but would be equally effective in your case. Commented Aug 22, 2023 at 19:24
• @CrisLuengo That is the version of the watershed I've tried—could you elaborate on how to apply it here?
– nben
Commented Aug 22, 2023 at 20:27

## 1 Answer

One approach is to compute the distance transform (of the background), and then apply the watershed to the inverse of this distance map.

We must take care that each region only has one local maximum, discretization of the distance transform often leads to local maxima along ridges, which we can eliminate with the H-Maxima operator.

Likewise, we must ensure that the entire border of the image is a single local maximum, otherwise the background will be broken up into smaller regions. One way to do so is to set the border pixels in the distance transform to the maximum distance found.

In the code below, we do things a bit differently than described above because the DIPlib watershed function has some additional options:

• We invert the operation of the watershed itself instead of inverting the distance map, which is a bit easier.
• We don't explicitly apply the H-Maxima operator, it is built into the watershed function in the form of region merging.
import diplib as dip

# Load image, convert to binary with background as objects
img = dip.ImageRead('whOES.png')
img = img(1) > 128

# Distance transform of background regions (note img is inverted)
dt = dip.EuclideanDistanceTransform(img, border="object")

# Ensure image border is a single local maximum
dip.SetBorder(dt, value=dip.Maximum(dt)[0], sizes=2)

# Watershed (inverted)
seg = dip.Watershed(dt, mask=img, connectivity=2, maxDepth=2, flags={"high first"})

# Color annotated regions and display
cols = dip.Label(~seg)
cols.Show("labels")

Disclaimer: I'm a developer of DIPlib.

• Amazing! I am now working on figuring out what (aside from setting the outer boundary) is different between my failing implementation and this one—thanks so much!
– nben
Commented Aug 22, 2023 at 22:02
• @nben Probably the H-Maxima transform (or typically the H-Minima applied to the inverted dt, which is equivalent). Removing spurious local maxima of DT is very important. Commented Aug 22, 2023 at 22:10
• @nben There are other approaches I've seen as well. For example you can take each stroke end-point, and if it's not touching another line, then extend it a bit, in the same direction, until it does -- as long as the gap is not too large. Commented Aug 22, 2023 at 22:15
• I see! Yes, the extend-each-contour approach is basically the heuristic approach I mentioned, but I've found that this approach frequently leads to issues—e.g., sometimes two contours that meet at a sharp point are, in fact, (nearly) parallel.
– nben
Commented Aug 22, 2023 at 22:23
• @nben Indeed, I can imagine that approach needing lots of tests for edge cases and odd situations. Commented Aug 22, 2023 at 22:34