0

Let's assume:

  • We have a B&W image with closed loops (lines are 1px thick)
  • If we travel on the image, each time we cross a line we change area type (inside or outside)
  • The top left pixel (0,0) is defined as outside and it has no line crossing it
  • Lines are black the rest is white

I want to fill all the inside areas in the most efficient way (I am working with very large images).

For example Before:

Before

and After:

After

Christoph Rackwitz
  • 11,317
  • 4
  • 27
  • 36
Ami
  • 13
  • 3
  • 2
    Use floodfill or contour hierarchy! – fmw42 Sep 11 '22 at 22:59
  • okay it's not quite as trivial was I had hoped... there are some corner cases. I'm sure there are known algorithms for this but I CBA to look. research is _your_ responsibility. please review [ask]. -- you can use python, combine with `@numba.njit(parallel=True)` to make it fast. this probably isn't even worth copying to the GPU, unless it's a "zero-copy" to an integrated GPU. OpenCL might tickle some cycles out of it. – Christoph Rackwitz Sep 11 '22 at 23:31
  • ok, so, connected components labeling, applied to both background and foreground, should tell you each area. establish adjacency (white-black-white-...), then color that graph's nodes representing white areas, then you know what to make of each component... if the graph is as you say, it should have a tame solution but if not, this could escalate to becoming a graph coloring problem... it's late – Christoph Rackwitz Sep 11 '22 at 23:35
  • first idea: run along each pixel row, toggling a bit whenever I move from black to white (off a boundary into an area), but that fails where that _touches_ a boundary without crossing it (can't tell the situations apart). so that was a bust. – Christoph Rackwitz Sep 12 '22 at 01:00
  • second idea: connected components, adjacency graph, which ought to be a tree due to the constraints given by OP, and trees are trivially 2-colorable. -- assuming boundaries have finite width (1-2 pixels) is easier than _not_ assuming that. if the graphic does _not_ represent nested areas, but something like a map of countries, _then_ you have a real graph coloring problem. – Christoph Rackwitz Sep 12 '22 at 01:00
  • I would use [boundary fill](https://stackoverflow.com/a/37810355/2521214) (its similar to flood fill) if your contours have gaps use dilatation and or smooth filters to patch them up first... – Spektre Sep 12 '22 at 07:14

1 Answers1

2

I'll assume that it's indeed a "tree" of nested areas, delineated by thin black boundaries. A tree is trivially 2-colorable so if this isn't, the solution would be less obvious.

Approach:

  • connected components labeling
  • walk the tree from the "root" (label of top left pixel)
  • find neighboring components by dilating a mask and intersecting with other components
(nlabels, labelmap, stats, centroids) = cv.connectedComponentsWithStats(im, connectivity=4, ltype=cv.CV_32S)

root_label = labelmap[0,0]
area_coloring = { root_label: False } # label -> color
work = [ root_label ]
while work:
    area_label = work.pop(0)
    assert area_label in area_coloring
    color = area_coloring[area_label]

    # adjacent areas by dilating mask and finding unique labels
    mask = (labelmap == area_label).astype(np.uint8)
    mask_dilated = cv.dilate(mask, kernel=None, iterations=3) # 3 iterations to bridge boundaries (1-2 pixels)
    adjacent_areas = set(np.unique(labelmap[mask_dilated.astype(bool)])) - {0, area_label} # excluding background and self

    areas_to_color = adjacent_areas - set(area_coloring) # - already colored
    for adjacent_area in areas_to_color:
        area_coloring[adjacent_area] = not color
    work += areas_to_color

canvas = cv.cvtColor(im, cv.COLOR_GRAY2BGR)
for (label, color) in area_coloring.items():
    if not color: continue
    mask = (labelmap == label)
    canvas[mask] = 186 # gray

output

Christoph Rackwitz
  • 11,317
  • 4
  • 27
  • 36