A fast connected components labeling algorithm for binary images

FU Yi-li, HAN Xian-wei, WANG Shu-guo

State Key Laboratory of Robotics and System, Harbin Institute of Technology, Harbin 150080, China



Abstract:

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.

Key words:  binary image  connected components  labeling algorithm  Union-Find  label-equivalence

DOI£º10.11916/j.issn.1005-9113.2012.03.015

Clc Number:TP751ª±1

Fund: