基于区域增长的连通域标记算法的优化

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

1、第32卷第2期闽江学院学报Vol．32No．22011年3月JOURNALOFMINJIANGUNIVERSITYMar．2011基于区域增长的连通域标记算法的优化罗志灶，周赢武，郑忠楷(1、闽江学院物理学与电子信息工程系福建福州350108)摘要:与以往基于区域增长的连通域标记算法用目标点作为种子不同，优化算法将游程作为种子，结合游程和种子算法的优点，减少种子的数量和目标点邻域的搜索次数．实验表明，本算法能有效地减少算法冗余操作，明显提高效率，且性能优于其它算法．关键词:二值图像;连通域;区域增长;标记算法中图分类号:TP391文献标识码:A文章编号:1

2、009－7821(2011)02－0041－04Optimizingthealgorithmoflabelingconnectedcomponentsbasedonregion-growthLUOZhi-zao，ZHOUYing-wu，ZHENGZhong-kai(DepartmentofPhysicsandElectronicInformationEngineering，MinjiangUniversity，Fuzhou，Fujian350108，China)Abstract:Theoptimizedalgorithmoflabelingconnecte

3、dcomponentsbasedonregion-growthregardsrun-lengthasseeds，otherthanobjectpixelsthatwasconsideredasseedsbytraditionalalgorithm，itmakesuseofbothadvantagesofrun-lengthseedsalgorithmandalgorithm，anditcoulddecreasequantityofseedsandtimesforsearchingneighborsofobjectpoints．Theexperimental

4、resultsshowthealgorithmcoulddecreaseredundantoperationsefficientlyandimproveit’sefficiencyobviously，anditismoreexcel-lentthanothers．Keywords:binaryimages;connectedcomponents;regiongrowth;labellingalgorithm［1］图像的连通域标记是将图像中符合某种连通规则(4邻域或8邻域)的像素点用相同的、唯一的标号标记．连通域标记的速度和准确性直接影响图像的后续处理，故历

5、来是数字图像处理的重要研究方向．CostantinoG在文献［2］分析了连通域标记算法的发展进程及类别，并将现有的连通域标记算法大致归［3－5］纳为如下3种:一次扫描连通域标记算法，该类算法完成连通域标记仅需扫描图像一次．其中主要类别有［5］［4］［3］［6，7］基于轮廓扫描技术、区域增长法及递归搜索算法等;二次扫描连通域标记算法，分两阶段对图像进［8］行扫描，用一维共同连通域标号数组标记不同的连通域所属的共同连通域;多次扫描连通域标记算法，该类算法主要是反复自顶向下和自底向上扫描图像，并传递临时连通域标号，直到不再出现连通域标号冲突．［5］［4］一次扫描

6、算法不论是轮廓跟踪标记算法、还是区域增长法，通常需大量访问堆栈和邻域搜索．究其原因，主要是目标连通域形状的不规则且不可预测，图像扫描未完成前，无法获取全部的信息，需堆栈保存扫描获取的信息和反复搜索目标点的邻域以获取所有可能的连通路径．减少邻域搜索和堆栈访问的次数是提［4，9－10］高该类算法效率的有效方法．常用的区域增长标记算法是以目标点作为种子单位，目标点之间的冗余连通路径被重复搜索，因而从堆栈中存取种子占用了大量运行时间，且还造成大量冗余的连通路径搜索．［11］游程编码是用一个符号值代替具有相同值的连续符号．以游程为种子单位，能有效地减少算法存取种子的

7、次数;同时线标记游程内的连续目标点，可减少目标点的邻域搜索次数．图像的游程编码原先主要用于图像压缩和减少内存消耗．由于在连通域标记算法中，若用游程表示行时，需判断该游程的上行和下行的每个目收稿日期:2011－03－01项目资助:福建省教育厅科技项目(JB10137)作者简介:罗志灶(1971－)，男，福建三明人，闽江学院物理学与电子信息工程系讲师．周赢武(1967－)，男，福建屏南人，闽江学院物理学与电子信息工程系副教授．郑忠楷(1978－)，男，福建福州人，闽江学院物理学与电子信息工程系讲师．42闽江学院学报第32卷标点是否在游程范围之内，并需提取与该游

8、程连通的游程，算法逻辑复杂，影响算法的速度．本算法以游程为种子单位