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

Question

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.

Answer 1

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.