Static labels in watershed

Note: I incorrectly identified my problem; cf Static labels in watershed - #4 by Arcanis

I’m trying to apply the watershed algorithm, but I have a slight hiccup. From my understanding, I need to give the background a non-zero value in order to prevent the algorithm to try to fill it. That makes sense, however it means that the background slightly bleeds inside the objects themselves (trying to fill the unknown part).

Assuming I know for a fact that the background is exactly where it is and nowhere else, is there a way I could define the background label as “static” (ie it would prevent any other label from traversing, but wouldn’t spread its own)? I considered just using 0 and applying a mask as postprocess, but that would cause other labels to cross the background, potentially affecting the results in other parts of the image.

Perhaps related, perhaps not, but I notice that the watershed algorithm is injecting -1 values into my image - is it something expected, perhaps because of rounding? Is there something I can do to avoid that?

For instance here, on the left is the image before watershed, then right after. As you can see, white pixels representing -1 appeared from nowhere:


you’re using watershed. do you have a distance field? seeing some data would help.

No, I don’t have the distance field. Basically I generate the markers using an opening operation of the original map, then apply connectedComponents to identify each relevant section, then finally apply the watershed to cover unknown areas.

After digging a bit I saw that the documentation mentions that the object boundaries are stored as -1:

In the function output, each pixel in markers is set to a value of the “seed” components or to -1 at boundaries between the regions.

However this behavior is a bit annoying since it introduces artifacts. I’d like to clean them from the output.

(It also means I incorrectly identified my initial problem, since what I thought was the background bleeding was actually the region boundary artifacts; however I don’t understand why the background is not bleeding - what prevents the light gray section from filling the black one? why does the algorithm prefer the dark gray one?)

if you don’t have a distance field, you can’t use watershed. that’s just a cold hard prerequisite.

I think you’re using the wrong approach. don’t get stuck on your chosen solution.

what is the goal of the goal of the goal of what you’re trying to achieve? present your situation/problem on multiple levels. that includes and needs to go above abstraction levels such as “boss told me to do it” (what’s his task?), “it’s a class assignment” (what class?), “I want to learn” (what do you want to learn?).

you should prefer to use pictures rather than words for your explanation/exposition. little cropped corners of a larger picture don’t help much either.

Fair enough. To give you context, I’m experimenting with OpenCV, and my goal is, given a building map (Among us game) under the form shape, figure out the location of the rooms inside. Take the following pictures:

1 - The map itself, as a mask
2 - Opening on the map; extracts seeds for it (connectedComponents)
2b - Separate processing[1] to get the corridor seeds (unique seed for all corridors)
2c - (not pictured) I set the background to a unique seed as well
3 - Debug render; with the original map overlayed. As you can see, some spots are still black

At this point, I’m looking for something to turn the black spots into the nearest seed color (to finalize both the corridors and the rooms). Using watershed almost works (image 5), but:

  • I don’t understand why some of the black spots don’t take the background color (since it’s a seed as well). It’s the effect I want, but I don’t understand why it works (for instance, in image 4, what makes the watershed prefer corridors over background in the lower-left black spot?).

  • The watershed algorithm seems to set boundaries between regions to -1, causing artifacts to appear (you don’t see them very well in image 5 due to scaling, it’s easier to see in the full scale image). I’d like to remove them.

If there’s a better solution I’m very open to try something different, it’s possible/likely I’m using the wrong tools for the job :sweat_smile:

[1] This “separate processing” is a two-passes (horizontal+vertical) processing where I run the HitAndMiss algorithm with a marker that’s basically a large line that forces two background pixels to be on the side, and a band of active pixels to be on the middle.

1 Like

I agree with the morphology operations. I disagree with the watershed stuff. it’ll probably work but I wanted to try a different path. edit: watershed does require a distance field but I guess it can somehow function without one? nobody ever uses watershed without a distance/height field. that guides how fast the areas grow and where they’ll meet.

I’m separating the space into room and corridor type of pixels. rooms are hopefully labeled sufficiently by the morphology operation. everything else is corridor.

there are narrow pieces of room that weren’t characterized as room but as corridor. they’re “dead-end corridors” because they only connect to the one room. I simply relabel them, after figuring out the connectivity of this graph.

building graph
  1 -> {16, 15}
  2 -> {17, 18, 15}
  3 -> {19}
  4 -> {16, 27, 20, 21}
  5 -> {17, 26, 19, 22}
  6 -> {22}
  7 -> {20}
  8 -> {18}
  9 -> {25, 23, 15}
  10 -> {24}
  11 -> {21}
  12 -> {19}
  13 -> {24, 25, 26}
  14 -> {25, 27, 28}
  15 -> {1, 2, 9}
  16 -> {1, 4}
  17 -> {2, 5}
  18 -> {8, 2}
  19 -> {3, 12, 5}
  20 -> {4, 7}
  21 -> {11, 4}
  22 -> {5, 6}
  23 -> {9}
  24 -> {10, 13}
  25 -> {9, 13, 14}
  26 -> {5, 13}
  27 -> {4, 14}
  28 -> {14}
relabeling dead-end corridors
  corridor 3 := room 19
  corridor 6 := room 22
  corridor 7 := room 20
  corridor 8 := room 18
  corridor 10 := room 24
  corridor 11 := room 21
  corridor 12 := room 19

some code:

edit: scratch that. watershed does need a distance field for its operation, but also seeds.

it runs “fronts” of assignment from each seed, according to “water level” that rises and floods areas according to the distance transform. wherever the flooded areas meet, you get the -1 because it can’t say which side would win. it’s unavoidable.

which side to assign them to? you could enumerate them all and assign each to the smallest adjacent label.

Wow, that’s very clever :open_mouth:

I never would have thought about this approach, but it definitely makes sense. The code was helpful as well - using OpenCV.js the binary operation counterparts weren’t immediately obvious, but after some research I’ve managed to reproduce exactly your results.

Thanks, it’s exactly the effect I was looking for!