A fast connected components labeling algorithm for binary images

A fast label-equivalence-based connected components labeling algorithm is proposed in this paper. It is a combination of two existing efficient methods, which are pivotal operations in two-pass connected components labeling algorithms. One is a fast pixel scan method, and the other is an array-based Union-Find data structure. The scan procedure assigns each foreground pixel a provisional label according to the location of the pixel. That is to say, it labels the foreground pixels following background pixels and foreground pixels in different ways, which greatly reduces the number of neighbor pixel checks. The array-based Union-Find data structure resolves the label equivalences between provisional labels by using only a single array with path compression, and it improves the efficiency of the resolving procedure which is very time-consuming in general label-equivalence-based algorithms. The experiments on various types of images with different sizes show that the proposed algorithm is superior to other labeling approaches for huge images containing many big connected components.