Frequently Asked Questions

What problem does mergeSmallRegionsInPlace solve?

This function removes tiny connected regions in an RGBA image by merging them into neighboring, sufficiently large regions in-place.

It is intended for post-processing steps after:

• k-means color quantization
• segmentation

Or as a pre-processing step before:

• image-to-vector (SVG) pipelines

Small regions often appear as visual noise and make downstream geometry extraction harder.

What exactly is a “region” in this context?

A region is a 4-connected component of pixels where:

• Each pixel is connected via up, down, left, or right
• All pixels have exactly the same RGBA values

Diagonal adjacency does not count.

Why use 4-connectivity instead of 8-connectivity?

4-connectivity:

• Matches most raster algorithms (flood-fill, contour tracing)
• Avoids diagonal “corner-touch” artifacts
• Produces cleaner, grid-aligned regions

Using 8-connectivity would merge diagonally touching pixels that visually are not part of the same region.

Why is the image indexed as idx(x, y, width) * 4?

Each pixel consists of 4 bytes: R, G, B, A

So the linear index into the pixel buffer is:

$$(\text{y} \cdot \text{width} + \text{x}) \times 4$$

Visual Example: 5×5 RGBA Image Indexing

Assumptions this layout has

• Row-major order
• No padding between rows

What does sameColor(...) check?

It compares all four RGBA channels for equality:

• Red
• Green
• Blue
• Alpha

Two pixels are considered connected only if all channels match exactly.

This is important for correctness when alpha is meaningful (e.g. transparency).

Why does the algorithm do two passes?

The function is split into two distinct phases:

1. Labeling pass

   • Flood-fills each region
   • Assigns a label to every pixel
   • Computes region metadata (area + bounding box)

2. Merge pass

   • Iterates pixels again
   • Replaces pixels belonging to “small” regions
   • Copies color from a neighboring “big enough” region

This separation keeps the logic simpler and avoids modifying regions while still discovering them.

What makes a region “big enough”?

A region must satisfy all three conditions:

• size >= minArea
• width() >= minWidth
• height() >= minHeight

Where:

• size = number of pixels
• width() = bounding box width
• height() = bounding box height

This prevents:

• Thin lines
• Long but narrow artifacts
• Small blobs

Why use a bounding box instead of checking shape quality?

Bounding boxes are:

• Fast to compute
• Memory cheap
• Conservative

They don’t capture holes or concavities, but they are a good heuristic for filtering obvious noise.

There is a TODO noting that internal gaps could reduce effective width/height even if the bounding box looks valid.

Can a region pass the bounding box test but still be “bad”?

Yes.

Example:

• A hollow ring
• A U-shaped region
• A region with internal gaps

The bounding box may be large, but the actual filled area might be sparse.

This implementation prioritizes speed and simplicity over perfect geometric validity.

Why are regions merged pixel-by-pixel instead of as a whole?

Because:

• The function operates in-place
• It avoids reallocating buffers
• It keeps memory usage predictable

Each pixel independently:

• Checks its neighbors
• Copies the color of a valid region

This makes the merge phase linear and simple.

Why only check immediate neighbors during merging?

Only 4 immediate neighbors are checked because:

• The merge should respect spatial adjacency
• Copying from distant pixels could create visual artifacts

This ensures merges look natural and locally consistent.

What happens if a small region has no big neighbors?

Nothing.

Pixels in that region remain unchanged.

This avoids:

• Arbitrary color assignment
• Unexpected long-range merges

If this is undesirable, a second pass or fallback strategy can be added.

Does this update region metadata after merging?

No.

Once the merge phase starts:

• regions is treated as read-only
• Labels may change per pixel
• Region sizes are not recomputed

This is intentional to keep runtime linear and avoid cascading changes.

What is the time complexity?

Overall complexity is linear:

• Flood-fill labeling: $O(n)$
• Merge pass: $O(n)$

Where $n = \text{width} \times \text{height}$

Each pixel is:

• Visited once in flood-fill
• Checked against at most 4 neighbors

What is the memory overhead?

Additional memory used:

• labels: one int per pixel
• regions: one entry per connected component
• BFS queue (temporary)

No additional image buffers are allocated.

Why use BFS (std::queue) instead of DFS?

BFS:

• Avoids deep recursion
• Prevents stack overflow on large regions
• Has predictable memory usage

DFS would require either recursion (unsafe) or an explicit stack (no advantage here).

Can this function be parallelized?

Not easily in its current form.

Reasons:

• Flood-fill has data dependencies
• Label assignment is sequential
• Merge step mutates shared data

Parallel versions would require:

• Tiled processing
• Boundary reconciliation
• More complex region merging logic

Is this suitable for SVG generation pipelines?

Yes — especially as a cleanup step before:

• Boundary tracing
• Polygon extraction
• Path simplification

Removing small regions early greatly simplifies vector geometry later.

What are common improvements or extensions?

Possible enhancements include:

• Detecting holes inside regions

• Merging based on color similarity instead of equality

• Multi-pass merging

• Choosing the largest neighboring region instead of the first valid one

• Detecting localised width/height - regions often have large tentacle-like protrusions.

The current design favors clarity and predictability over heuristics.

Is this function deterministic?

Yes.

Given the same input image and parameters, the output is always identical.

No randomness is involved.

When should I not use this?

Avoid this function if:

• You need exact topology preservation
• You rely on diagonal connectivity
• You require sub-pixel or fuzzy color matching

It is designed for grid-aligned, exact-color regions.

Summary

mergeSmallRegionsInPlace is a fast, predictable cleanup step for raster segmentation pipelines.
It trades geometric perfection for simplicity, performance, and ease of reasoning — which is often exactly what you want before vectorization.