二值图像连通域标记优化算法

《二值图像连通域标记优化算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、精品文档二值图像连通域标记优化算法罗志灶1周赢武1罗志仕2(1．闽江学院电子系福州市350108；2．三明电业局三明市365000)摘要：在分析现有二值图像像素扫描连通域标记算法的基础上，提出像素扫描连通域标记优化算法。本算法具有速度快，算法简单，易于实现的特点，仅需两次扫描，即可实现像素的多目标标记。本算法将背景也作为目标加以标记，分两步扫描图像和待合并连通域标号完成连通域的标记和合并，采用顺序存储结构存储和处理等价标号,算法速度快，内存节约。关键字：二值图像；连通域；像素扫描；标记中图分类号:TP391Opt

2、imizationonalgorithmoflabelingconnectedcomponentsinbinaryimagesAbstract:Theimprovedalgorithmisintroducedbasedonanalysisofexistingalgorithmsoflabelingconnectedcomponentsthroughscanningpixelsinbinaryimages.Thealgorithmhasmanyadvantagessuchasfaster,simpler,easie

3、rtorealizethantheothers,onlyneedtwo-scanstolabelconnectedcomponentswhichpixelbelongto.Thealgorithmcouldlabelbackgroundasobjects,labelandmergeconnectedcomponentsviathetwoprocedureofscanningbinaryimageandscanningtheprovisionallabels.Itadoptssequentialstoragestr

4、ucturetostoreandresolvetheequivalentlabels,runsmorerapidly,occupiesmuchlessmemorythantheunimprovedalgorithm.Keywords:binaryimages;connectedcomponents;scanningbypixels;labelling二值后的图像，是由白像素点(通常二值图像用“1”，灰度图像用“255”来表示)和黑像素点(通常用“0”来表示)组成的点阵图像[1]。连通区域标记是指将图像中符合某种连

5、通规则(4邻域连通、8邻域连通或m邻域)的像素标识为同一目标[2]，设计合适的数据结构记录每个像素点归属的目标，和保存相关的目标的属性[3]，例如目标的面积即目标的像素点的数量、重心、二阶矩等参数。连通域标记法是计算机视觉和目标识别的预处理步骤，对目标识别的准确性和速度直接影响系统的性能[4]。影响连通域标记算法性能的主要有两个方面：a)图像扫描方式及连通域标号冲突处理的方法;b)存储连通域信息的数据结构。改善连通域标记算法性能也着眼于这两方面：减少图像的扫描次数，尽可能减少回溯扫描，一次扫描尽可能多地提取连通域

6、的信息；设计合适的数据结构，尽可能减少连通域信息访问的时间，提高算法效率。1现有算法分析图像的连通域标记算法有多种，根据扫描方法不同可分为像素扫描即点标记法[5]和线段扫描即线标记法[6]。像素点扫描方式有如下1、顺序扫描法[7]、2、递归标记法[8]、3、区域增长法[9]等。线段扫描算法主要有有基于跑长码的标记算法[10]、基于游程的标记算法[11]等。各算法均能准确标记目标连通域，其主要区别在于等价标号的处理。最终的标记要把等价标号标记为同一标号。优化算法的目的是在正确解决等价标记和冲突标记基础上，降低算法的

7、复杂度和提高算法的性能。像素点扫描法是比较常用的算法，其直观，数据结构简单，易于实现[5]。二值图像扫描后，会有大量的冲突标号；通常的做法是对二值图像迭代扫描，以完全消除等价标号[8]，算法运行时间不稳定；算法常用链表结构、树型结构或堆栈结构存储标号[8]，大量的运行时间消耗在递归调用和指针传递上。本文针对像素点扫描法的缺陷，提出了改进像素点扫描法的算法。首先针对常用的存储等价标号的链表结构的缺点，改用顺序存储结构以减少指针传递次数；其二、用与二值图像大小相同的二维数组存储标号，标记像素点的连通域标号，方便后续图

8、像处理；其三、用一维数组存储等价标号的共同连通域标号及目标属性，用于解决冲突标号的处理；最后、改进等价标号合并算法，重新排序标号，获得合理的目标标号。2算法描述2.1术语定义精品文档连通域标号：图像像素点所在的连通域的序号。用与图像大小相同的二维数组保存每个像素点的连通域标号。连通域标号有二个阶段：第一阶段，对二值图像扫描所得的临时连通域标号，此阶段，会有不同的连通域标号