Flood fill

Overview

A flood fill starts from one or more seed pixels and repeatedly visits neighbours. A neighbour joins the region when a test on it passes. The two sources on this page use the same traversal for different jobs. SuMa++ copies known labels into empty pixels of a LiDAR label image 2105.11320 §III-D. ALINA gathers every white pixel of one line in a binary mask, starting from a seed 2406.08775 §3.8.

The shared core is a frontier of pixels, a neighbourhood, a visited record and an accept rule. The accept rule is what the variants change. ALINA's traversal visits each neighbour once 2406.08775 §3.8 2406.08775 alg. 1. The two papers work on different data (LiDAR range images and aerial video of taxiway markings), so their numbers are not comparable.

Variants

Depth-consistent label fill (SuMa++)

Before the fill, the raw label mask is eroded: a pixel is dropped when a neighbour in its kernel carries a different label 2105.11320 §III-D 2105.11320 alg. 1. Pixels left empty are then filled from a labelled neighbour whose distance is consistent with the pixel's own [arxiv:2105.11320 §III-D] 2105.11320 fig. 3. The refined labels then feed the surfel stability update and the ICP residual weights 2105.11320 §III-E 2105.11320 §III-F. The paper evaluates on KITTI only [arxiv:2105.11320 §IV]. Card: SuMa++: Efficient LiDAR-based Semantic SLAM.

The paper's text and its Algorithm 1 give different consistency tests: one uses 3-D distance, the other a pixel-distance test with a threshold. The threshold value is not stated 2105.11320 §III-D 2105.11320 alg. 1. The released code uses a relative range test instead; see the card.

Connected-pixel traversal from a seed (ALINA)

The input is a binary mask, which the paper builds by colour thresholding a bird's-eye view. The seed is the peak column of a column histogram, together with the mean row of its white pixels 2406.08775 §4.2. A depth-first traversal then expands only white pixels, and returns every white pixel it reaches 2406.08775 §3.8 2406.08775 alg. 1.

The neighbourhood has radius θ, so white pixels separated by a gap smaller than θ are joined into one set 2406.08775 alg. 1. The paper does not state a value for θ 2406.08775 §3.8. The text calls the neighbourhood circular, while the algorithm uses a square window 2406.08775 §3.8 2406.08775 alg. 1.

The authors report 3.33 ms for this step against 10.90 ms for a sliding-window search, on their own CPU 2406.08775 tab. 3. They describe the step as linear in the number of white pixels 2406.08775 §4.4. The algorithm as written checks (2θ+1)² − 1 offsets per white pixel 2406.08775 alg. 1, so the work per pixel grows with θ². Card: ALINA: Advanced Line Identification and Notation Algorithm.

When to use which

The table covers only the constraints the two sources address.

Implementation sketch

Common core of both variants, in Python-flavoured pseudocode. The accept rule is where they differ; the notes below the block give each variant's rule.

# Seeded flood fill over a 2-D grid  [arxiv:2406.08775 alg. 1]
# Shapes: grid (H, W); seeds: list of (row, col); offsets: neighbourhood

def flood_fill(grid, seeds, offsets, accept):
    # Start the frontier at the seed pixels  [arxiv:2406.08775 §4.2]
    frontier = list(seeds)
    visited = set(seeds)
    region = []
    while frontier:
        r, c = frontier.pop()  # depth-first: take the newest pixel
        region.append((r, c))
        for dr, dc in offsets:
            # Visit each neighbour at most once  [arxiv:2406.08775 §3.8]
            n = (r + dr, c + dc)
            if n in visited or not inside(grid, n):
                continue
            visited.add(n)
            # Variant-specific test on the neighbour  [arxiv:2105.11320 §III-D]
            if accept(grid, (r, c), n):
                frontier.append(n)
    return region

• ALINA. accept returns true when the neighbour is white in the mask. The output is the set of white pixels reached. The traversal does not change the mask. The seed is set to white before the call.
• SuMa++. The fill copies a label from a labelled neighbour into an empty pixel, rather than collecting pixels. accept compares the range of the two pixels with a threshold. The threshold and the erosion kernel are not stated in the paper 2105.11320 §III-D 2105.11320 alg. 1.

Contradictions

None known between the two papers on the same quantity. Within each paper, the text and the algorithm differ. SuMa++ gives a 3-D distance test in the text and a pixel-distance test in Algorithm 1 2105.11320 §III-D 2105.11320 alg. 1. ALINA calls the neighbourhood circular in the text and uses a square in Algorithm 1 2406.08775 §3.8 2406.08775 alg. 1. Neither gap is resolved here.

Papers

• SuMa++: Efficient LiDAR-based Semantic SLAM: a depth-consistent fill that refines LiDAR label images before semantic surfel mapping.
• ALINA: Advanced Line Identification and Notation Algorithm: a seeded depth-first traversal that collects the white pixels of a painted line.