Fast Connected-Component Labeling through Sequential Local Operations in the Course of Forward Raster Scan Followed by Backward Raster Scan

摘要

This paper presents a fast algorithm for labeling connected components in binary images based on sequential local operations in the course of forward raster scan followed by backward raster scan. A one-dimensional table, which memorizes label equivalences, is used successively during the operations for uniting equivalent labels. The proposed algorithm has a desirable characteristic: the execution time is directly proportional to the number of pixels in connected components in an image. By comparative evaluations, it has been shown that the proposed algorithm outperforms the conventional algorithms in terms of the computational cost.