---
kind: concept
slug: flood-fill
title: Flood fill
summary: >-
  Growing a region outward from seed pixels through neighbours that pass a test. SuMa++ fills holes in LiDAR label images from neighbours at a consistent range. ALINA collects the connected white pixels of a painted line from a seed on a thresholded bird's-eye view. Two sources, both author-reported, on different data.
tags: [image-processing, lidar, computer-vision, labelling]
papers: ["2105.11320", "2406.08775"]
related: [image-thresholding, canny-edge-detection, semantic-segmentation, surfel-mapping, simultaneous-localization-and-mapping]
status: draft
updated_at: 2026-11-08
---

## 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 [arxiv:2105.11320 §III-D].
ALINA gathers every white pixel of one line in a binary mask, starting from a
seed [arxiv: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 [arxiv:2406.08775 §3.8] [arxiv: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 [arxiv:2105.11320 §III-D]
[arxiv: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] [arxiv:2105.11320 fig. 3]. The refined labels then feed the surfel
stability update and the ICP residual weights [arxiv:2105.11320 §III-E]
[arxiv:2105.11320 §III-F]. The paper evaluates on KITTI only [arxiv:2105.11320
§IV]. Card: [SuMa++: Efficient LiDAR-based Semantic SLAM](/papers/2105.11320).

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 [arxiv:2105.11320 §III-D] [arxiv: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 [arxiv:2406.08775 §4.2]. A depth-first
traversal then expands only white pixels, and returns every white pixel it
reaches [arxiv:2406.08775 §3.8] [arxiv:2406.08775 alg. 1].

The neighbourhood has radius θ, so white pixels separated by a gap smaller than
θ are joined into one set [arxiv:2406.08775 alg. 1]. The paper does not state a
value for θ [arxiv:2406.08775 §3.8]. The text calls the neighbourhood circular,
while the algorithm uses a square window [arxiv:2406.08775 §3.8]
[arxiv: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 [arxiv:2406.08775 tab. 3]. They describe the step as
linear in the number of white pixels [arxiv:2406.08775 §4.4]. The algorithm
as written checks (2θ+1)² − 1 offsets per white pixel [arxiv:2406.08775 alg. 1],
so the work per pixel grows with θ².
Card: [ALINA: Advanced Line Identification and Notation Algorithm](/papers/2406.08775).

## When to use which

The table covers only the constraints the two sources address.

| Situation | Use | Why |
|---|---|---|
| Per-pixel labels with holes on a range or depth image, and a 3-D point for each pixel | Depth-consistent label fill (SuMa++) | The fill is gated by a geometric test, and the labels feed the mapping pipeline [arxiv:2105.11320 §III-D] [arxiv:2105.11320 §III-E] |
| Every pixel connected to a seed inside a binary mask, no training, fixed camera setup | Connected-pixel traversal (ALINA) | Classical steps only; one region of interest per video, applied to 60,249 frames from three videos [arxiv:2406.08775 §4.1] [arxiv:2406.08775 §4.5] |
| Two distinct objects may lie within θ pixels of each other | Connected-pixel traversal with a small θ, or another method | Gaps smaller than θ are bridged, so separate objects merge; the paper does not test this [arxiv:2406.08775 alg. 1] |
| Accuracy needed on a domain other than the two evaluated | Not covered | SuMa++ is evaluated on KITTI [arxiv:2105.11320 §IV]; ALINA on the AssistTaxi dataset [arxiv:2406.08775 §4.1] |

## 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.

```pseudocode
# 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 [arxiv:2105.11320 §III-D] [arxiv: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 [arxiv:2105.11320 §III-D]
[arxiv:2105.11320 alg. 1]. ALINA calls the neighbourhood circular in the text
and uses a square in Algorithm 1 [arxiv:2406.08775 §3.8]
[arxiv:2406.08775 alg. 1]. Neither gap is resolved here.

## Papers

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