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.
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.
The Scan-flood Fill (SCAFF) Algorithm
SCAFF addresses the limitations of EFCI through a "Main Filling Process" that intelligently classifies regions.
- Systematic Scanning: The algorithm iterates through every pixel. When it finds an unfilled background pixel, it designates it as a new seed.
- 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.
- 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