基于数组型并查集的连通域标记算法

罗志灶，周赢武，郑忠楷

（闽江学院物理与电子信息工程系，福建 福州350108）

基于数组型并查集的连通域标记算法

罗志灶，周赢武，郑忠楷

（闽江学院物理与电子信息工程系，福建 福州350108）

常用的二次扫描算法存在某些缺陷，即共同连通域的合并主要是通过重复遍历共同连通域标号数组，修改相应的共同连通域标号完成的．重复遍历严重影响算法的性能．数组型并查集算法利用树型数据结构特点实现连通域合并，以取代重复遍历．实验表明数组型并查集算法更具优势．

二值图像；连通域；像素扫描；标记

0 引 言

连通域标记是是介于图像预处理和目标识别之间的重要步骤．连通域标记是指将图像中符合某种连通规则［1］（4－邻域连通、8－邻域连通或m－邻域）的像素标识为同一目标［2］，并用唯一的标号标记连通域内的像素点［3］．通常图像的目标是由一个或多个连通域组成，因此，可根据连通域的属性，例如面积、二阶矩等，计算目标的特征值，以达到识别目标的目的．连通域标记是对扫描图像标记目标的过程，其运算量相当大．优化连通域标记算法可极大提高数字图像处理系统的性能．

影响连通域标记算法性能［3－4］的因素主要有：1）图像扫描的次数及连通域标号冲突处理的方法；2）内存访问的方法等．通常提高连通域标记算法性能的方法也是基于这两方面：减少图像的扫描次数，尽可能减少回溯扫描；合理设计内存访问方式，尽量减少连通域信息访问……