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

《基于数组型并查集的连通域标记算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第１０卷第１期杭州师范大学学报（自然科学版）Ｖｏｌ．１０Ｎｏ．１２０１１年１月ＪｏｕｒｎａｌｏｆＨａｎｇｚｈｏｕＮｏｒｍａｌＵｎｉｖｅｒｓｉｔｙ（ＮａｔｕｒａｌＳｃｉｅｎｃｅＥｄｉｔｉｏｎ）Ｊａｎ．２０１１ＤＯＩ：１０．３９６９／ｊ．ｉｓｓｎ．１６７４－２３２Ｘ．２０１１．０１．０１７基于数组型并查集的连通域标记算法罗志灶，周赢武，郑忠楷（闽江学院物理与电子信息工程系，福建福州３５０１０８）摘要：常用的二次扫描算法存在某些缺陷，即共同连通域的合并主要是通过重复遍历共同连通域标号数组，修改相应的共同连通

2、域标号完成的．重复遍历严重影响算法的性能．数组型并查集算法利用树型数据结构特点实现连通域合并，以取代重复遍历．实验表明数组型并查集算法更具优势．关键词：二值图像；连通域；像素扫描；标记中图分类号：ＴＰ３９１文献标志码：Ａ文章编号：１６７４－２３２Ｘ（２０１１）０１－００８６－０６０引言连通域标记是是介于图像预处理和目标识别之间的重要步骤．连通域标记是指将图像中符合某种连［１］［２］通规则（４－邻域连通、８－邻域连通或ｍ－邻域）的像素标识为同一目标，并用唯一的标号标记连通域内的［３］像素点．通常图像的目

3、标是由一个或多个连通域组成，因此，可根据连通域的属性，例如面积、二阶矩等，计算目标的特征值，以达到识别目标的目的．连通域标记是对扫描图像标记目标的过程，其运算量相当大．优化连通域标记算法可极大提高数字图像处理系统的性能．［３－４］影响连通域标记算法性能的因素主要有：１）图像扫描的次数及连通域标号冲突处理的方法；２）内存访问的方法等．通常提高连通域标记算法性能的方法也是基于这两方面：减少图像的扫描次数，尽可能减少回溯扫描；合理设计内存访问方式，尽量减少连通域信息访问的时间．［５］［６］［７］连通域标记算

4、法有多种类型，根据扫描方式可分为像素扫描法、线段扫描即线标记法、基于轮［８］［６］［９］［１０］廓的标记法．像素点扫描方式有顺序扫描法、递归标记法、区域增长法等．线段扫描算法主要是［１１］基于游程的标记算法等．像素扫描法是最常用的标记算法，主要是遍历图像的像素点，并根据４－领域或［１１］８－领域规则，将相互连通的像素点用同一标号标记．基于游程的标记算法是逐行扫描图像，并记录每行连通域的起始位置和终止位置，然后与下一行的游程比较，确定是否属于同一连通域．该算法占用内存少，［８］适用于嵌入式系统．基于轮廓

5、的标记算法，是遍历图像的轮廓，并将在闭合的轮廓内的像素点标记为同一目标．该算法运算时间与图像的复杂度有关，因此应用不多．文献［５］分析了对连通域算法的进展及类别．［６］［９］顺序扫描法是最常用的算法，其直观，数据结构简单，易于实现．顺序扫描法有一次扫描法、二次收稿日期：２０１０－０９－０８基金项目：福建省重点学科项目（闽教高［２００６］４８号）．作者简介：罗志灶（１９７１—），男，福建三明人，讲师，硕士，主要从事数字图像和嵌入式系统设计与开发研究．Ｅ－ｍａｉｌ：ｌｚｚ＠ｍｊｕ．ｅｄｕ．ｃｎ第１期罗志灶

6、，等：基于数组型并查集的连通域标记算法８７［６］［１２］扫描法和多次扫描法．二次扫描法的性能及稳定性都比较好，是常用的算法．文献［６］分析了二次扫描法的原理及改进的方法．文献［３］提出等价标号快速传递法，并用决策树（ｄｅｃｉｓｉｏｎｔｒｅｅ）分析８－邻域和４－邻域内像素点的遍历秩序，以减少邻域内的像素点扫描次数；还提出用并查集（ｕｎｉｏｎ－ｆｉｎｄ）分析和处理冲突的等价连通域标号的思路，以提高等价标号冲突处理的效率．但文［３］中仅分析并查集算法原理，其算法实现不明晰，并且算法以过程调用方式植入连通域标

7、记算法，严重影响连通域算法的性能．在此首先针对二次扫描算法的缺陷提出改进的方法，分析和优化数组型并查集算法，特别对并查集的平面化算法优化，使算法易于实现，且充分利用数组直接访问存储的特点，提高算法的效率．最后，将本文的优化算法与文中提出的其它顺序扫描法相比较，分析优化算法的优缺点及适用范围．该文算法的４－邻域和８－邻域实现方法类似，将以４－邻域为例进行阐述．１二次扫描算法优化１．１常用二次扫描算法描述算法之前先解释几个变量：ＢｉｎａｒｙＩｍａｇｅ（ｘ，ｙ）是二值图像某像素点（ｘ，ｙ）的灰度级，０表示背

8、景，１表示目标．二维矩阵ｐｒｏｖｉｓｉｏｎａｌ（ｘ，ｙ）表示某像素点（ｘ，ｙ）的连通域标号，在算法的第一次扫描后，保存的是像素点（ｘ，ｙ）的临时连通域标号，二次扫描后，则保存的是目标的标号．一维矩阵ｃｏｍｍｏｎ（ｉｎｄｅｘ）表示由临时标号ｉｎｄｅｘ标记的子连通域所属的共同连通域标号．例如，ｃｏｍｍｏｎ（ｐｒｏｖｉｓｉｏｎａｌ（ｘ，ｙ））则表示由像素点（ｘ，ｙ）的临时标号ｐｒｏｖｉｓｉｏｎａｌ（ｘ，ｙ）所指定的共同连通域标号，是最终的、唯一的目标标号．二次