Scan-flood Fill(SCAFF): an Efficient Automatic Precise Region Filling Algorithm for Complicated Regions

Yixuan He, Tianyi Hu, Delu Zeng

Abstract

Recently, instance-level labeling for supervised machine learning has created a high demand for filled masks. We propose Scan-flood Fill (SCAFF), an efficient automatic region-filling algorithm designed for complicated geometries. By distinguishing between adjacent connected regions, the Main Filling Process scans through all pixels and classifies them as either exterior or interior. This approach allows for the precise generation of output masks even when boundaries touch image borders or contain complex nested "holes." Experimental results demonstrate that SCAFF achieves high accuracy (F1 score of 0.988 on MSRA10K) and maintains linear time complexity, making it suitable for large-scale automated data pipelines.

The Challenge of Precise Mask Generation

In fields like salient object segmentation and medical imaging, supervised machine learning models require pixel-perfect masks. However, many datasets provide only boundary coordinates to minimize storage requirements. Converting these boundaries into masks is traditionally difficult due to several factors:

  • Manual Intervention: Many "flood fill" tools require a human to manually place a seed point inside the boundary.
  • Complex Geometries: Standard scan-line algorithms often struggle with non-polygonal or irregular shapes.
  • Nested Holes: Distinguishing between the interior of an object and a background "hole" (like the center of a ring) is a common failure point for automated systems.
  • Border Interactions: Objects that touch the edge of an image frame can break the logic of algorithms that assume the border is always background.
Visualizing the conversion from boundaries to filled masks for complex objects, including those with internal holes and border-touching edges.

Methodology: From EFCI to SCAFF

The researchers developed their approach in two stages, moving from a simple inversion technique to a sophisticated adjacency-based scanning process.

Exterior-Fill and Color Inversion (EFCI)

The baseline method, EFCI, operates by padding the image with a background color and performing a flood-fill from the origin (0,0) using a temporary "exterior" label. Any remaining background pixels are then inverted to become the mask. While computationally efficient, this method fails to account for internal holes, as it treats all pixels enclosed by the outermost boundary as part of the object.

Algorithm 1: The Exterior-Fill and Color Inversion (EFCI) baseline process.

The Scan-flood Fill (SCAFF) Algorithm

SCAFF addresses the limitations of EFCI through a "Main Filling Process" that intelligently classifies regions.

  1. Systematic Scanning: The algorithm iterates through every pixel. When it finds an unfilled background pixel, it designates it as a new seed.
  2. Contextual Adjacency Logic: To determine if a new region is "Exterior" (background) or "Interior" (mask), the algorithm scans backward to identify the color of the nearest previously filled region. By tracking these relationships across boundaries, SCAFF correctly identifies nested structures.
  3. Robust Padding: A 1-pixel background border ensures the true exterior is always connected to the origin, preventing misclassification of objects that touch the image edge.

Evaluation and Performance

The algorithm was tested against a "Toy Dataset" of edge cases and the MSRA10K salient object dataset.

Quantitative Results

On the MSRA10K dataset, SCAFF reconstructed masks from extracted boundaries with remarkable precision:

  • F1 Score: 0.988
  • Mean Absolute Error (MAE): 0.0041

Computational Efficiency

SCAFF maintains a linear time complexity of $O(p)$, where $p$ is the number of pixels. In practical tests on a standard consumer laptop, a $2000 \times 2000$ pixel image was processed in approximately 11.7 seconds. This performance is strictly proportional to image resolution, ensuring scalability for high-definition datasets.

Conclusion and Future Directions

SCAFF provides a robust, fully automatic solution for generating high-quality training data from boundary annotations. While its precision is currently tied to the quality of the input boundary (requiring "gap-free" edges), it significantly reduces the need for human intervention in the data labeling pipeline. Future work may focus on optimizing the processing area through dynamic cropping and extending the logic to handle vector-based geometries directly.

Summary updated

Abstract

Recently, instant level labeling for supervised machine learning requires a considerable number of filled masks. In this paper, we propose an efficient automatic region filling algorithm for complicated regions. Distinguishing between adjacent connected regions, the Main Filling Process scans through all pixels and fills all the pixels except boundary ones with either exterior or interior label color. In this way, we succeed in classifying all the pixels inside the region except boundary ones in the given image to form two groups: a background group and a mask group. We then set all exterior label pixels to background color, and interior label pixels to mask color. With this algorithm, we are able to generate output masks precisely and efficiently even for complicated regions as long as boundary pixels are given. Experimental results show that the proposed algorithm can generate precise masks that allow for various machine learning tasks such as supervised training. This algorithm can effectively handle multiple regions, complicated `holes' and regions whose boundaries touch the image border. By testing the algorithm on both toy and practical images, we show that the performance of Scan-flood Fill(SCAFF) has achieved favorable results.
BibTeX
@inproceedings{he2019scan,
  author = {Yixuan He and Tianyi Hu and Delu Zeng},
  title = {{Scan-flood Fill(SCAFF): an Efficient Automatic Precise Region Filling Algorithm for Complicated Regions}},
  booktitle = {Workshops @ CVPR},
  year = {2019},
  url = {https://openreview.net/forum?id=oV2gyMs0C5},
}
Figure