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

摘要： 二值图像的连通区域标记算法是图像处理的一个基本问题。为了提高算法的效率，以Suzuki等人提出的多遍扫描算法为基础，提出了一种快速的一遍扫描连通域标记算法。算法通过对图像做一次正向扫描，先计算出每个当前像素所在邻域内的最小标号，再利用一个递推过程，查找该连通域中具有较小标号的结点，将被更新结点所在连通分支连接到该结点，以保证等价信息不损失。同时，用最小标号更新递推查找路径上结点的临时标号，以减小分支的深度。通过对连接表的更新使每个结点获得最终标号。算法不需要动态数据结构和递归过程的支持，需要的存储空间较小，算法比原算法速度提高了近2倍，也快于近期提出的一些基于游程的算法。

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