冯海文 ，牛连强 ，刘晓明

1.沈阳工业大学 软件学院，沈阳 110023

2.沈阳工业大学 电气工程学院，沈阳 110023

高效的一遍扫描式连通区域标记算法

冯海文1，2，牛连强1，刘晓明2

1.沈阳工业大学 软件学院，沈阳 110023

2.沈阳工业大学 电气工程学院，沈阳 110023

1 引言

二值图像连通区域标记是指对图像中不同连通区域中的像素设置唯一的标号，是计算机视觉、模式识别和图像处理等领域中众多算法的基础[1-4]。例如，在对医学、遥感、视频等图像进行处理时，通过连通域标记来确定物体的边缘，以对感兴趣的区域（目标）进行标记和提取；在电气行业的真空断路器的开断特性研究中，其基本方法是通过对图像连通域的查找来确定电弧图像中电弧面积和直径的变化规律，进而确定电弧的运动机理[5-6]。这些算法通常需要处理大量的图像，连通域标记算法的效率是一个关键问题。

目前，存在着多种连通区域标记算法，从处理的对象上主要可分为基于像素的算法和基于游程（块）的算法；从对像素的处理次数上，可分为一遍扫描算法、两遍扫描算法和多遍扫描算法[7-10]。文献[11-14]是几种典型的基于像素的算法，其中，文献[9]利用并查集技术减少等价信息传播的时间消耗，文献[10]采用递归方法处理连通域信息，它们对算法效率的改善不大。文献[13]提出了一种基于轮廓跟踪的快速标记算法，文献[14]提出了一种实现快速等价性判别的技术，文献[8，15]采用决策树方法减少对当前像素的邻近像素的扫描个数。……