关键词: 连通域, 标记算法, 一遍扫描, 标号, 二值图像, 标记连接表

Abstract: How to label connected components of a binary image is a basic problem in image processing field. To improve efficiency, a fast one-scan algorithm to label connected components is presented in this paper on the base of the multiple-scans algorithm proposed by Suzuki et al. The algorithm runs a forward scan to the object image only once. The node with the minimum label in the mask of the object pixel is calculated. The node with smaller label is searched in the connected component by an iterative process, and the connected branch including the note to be updated is linked to it. This technique can guarantee no loss to the equivalent information. At the same time, the provisional labels in iterative search path are updated by the minimum label in order to decrease the depth of the branch. The final labels of all nodes are obtained by scanning the connected table. Dynamic data structure and recursive procedure are not needed in this algorithm, and only less memory is required. Experiments and analysis show that the algorithm is about 2 times faster than the original one, and is also faster than some run algorithms proposed recently.

Key words: connected component, labeling algorithm, one-scan, label, binary image, label connected table