A new Direct Connected Component Labeling and Analysis Algorithms for GPUs

Until recent years, labeling algorithms for GPUs have been iterative. This was a major problem because the computation time depended on the content of the image. The number of iterations to reach the stability of labels propagation could be very high. In the last years, new direct labeling algorithms have been proposed. They add some extra tests to avoid memory accesses and serialization due to atomic instructions. This article presents two new algorithms, one for labeling (CCL) and one for analysis (CCA). These algorithms use a new data structure combined with low-level intrinsics to leverage the architecture. The connected component analysis algorithm can efficiently compute features like bounding rectangles or statistical moments. A benchmark on a Jetson TX2 shows that the labeling algorithm is from 1.8 up to 2.7 times faster than the State-of-the-Art and can reach a processing rate of 200 FPS for a resolution of 2048 × 2048.