Run-Based Connected Components Labeling Using Double-Row Scan

This paper presents a novel run-based connected components labeling algorithm which uses double-row scan. In this algorithm, the run is defined in double rows and the binary image is scanned twice. In the first scan, provisional labels are assigned to runs according to the connectivity between the current run and runs in the last two rows. Simultaneously, equivalent provisional labels are recorded. Then the adjacent matrix of the provisional labels is generated and decomposed with the Dulmage-Mendelsohn decomposition, to search for the equivalent-label sets in linear time. In the second scan, each equivalent-label set is labeled with a number from 1, which can be efficiently accomplished in parallel. The proposed algorithm is compared with the state-of-the-art algorithms both on synthetic images and real image datasets. Results show that the proposed algorithm outperforms the other algorithms on images with low density of foreground pixels and small amount of connected components.