面向目标特征提取的连通域标记算法

计算机与网络　面向目标特征提取的连通域标记算法　张恒　倪永婧　（１中国电子科技集团公司第五十四研究所，河北石家庄０５００８１）　（２河北科技大学，河北石家庄０５００１１）　【摘要】目标特征是目标分类识别的基础，在二值图像中常基于像素连通关系进行提取并通过连通域标记使所含像素能　便捷访问。文章简要分析了常见连通域标记算法的性能，针对三种特殊而常见的连通域与目标间的对应关系指出其在目标特征　提取中的不适用性，为提高目标特征完整性和准确性在目标语义层次重新定义了像素连通，利用区域边界扫描以及对边界像素　的有效标记，将取决于二维信息的连通关系识别转化到一维中，使每行（列）的处理过程相互独立，从而实现一遍逐行（列）的图　像扫描即可完成特征提取（包括目标轮廓）及连通域标记，且标号连续。最后通过仿真从效率、适用性及内存耗费等方面对算法　进行了验证与分析。　［关键词】连通域标记轮廓跟踪特征提取　中图分类号：ＴＰ３９１　文献标识码：Ａ文章编号：１００８—１７３９（２０１５）０７—５８—４　Ｃｏｎｎｅｃｔｅｄ　Ｃｏｍｐｏｎｅｎｔ　Ｌａｂｅｌｉｎｇ　Ａｌｇｏｒｉｔｈｍ　Ｏｒｉｅｎｔｅｄ　ｔｏ　Ｔａｒｇｅｔ　Ｆｅａｔｕｒｅ　Ｅｘｔｒａｃｔｉｏｎ　ＺＨＡＮＧ　Ｈｅｎｇ　，ＮＩ　Ｙｏｎｇ－ｊｉｎｇ２　（１　Ｔｈｅ　５４ｔｈ　Ｒｅｓｅａｒｃｈ　Ｉｎｓｔｉｔｕｔｅ　ｏｆ　ＣＥＴＣ，Ｓｈｉｊｉａｚｈｕａｎｇ　Ｈｅｂｅｉ　０５００８１，Ｃｈｉｎａ）　（２　Ｈｅｂｅｉ　Ｕｎｉｖｅｒｓｉｔｙ　ｏｆ　Ｓｃｉｅｎｃｅ　ａｎｄ　Ｔｅｃｈｎｏｌｏｇｙ，Ｓｈｉｊｉａｚｈｕａｎｇ　Ｈｅｂｅｉ　０５００１　１，Ｃｈｉｎａ）　Ａｂｓｔｒａｃｔ：Ｔｈｅ　ｔａｒｇｅｔ￣ａｍｒｅ　ｉｓ　ｔｈｅ　ｆｏｕｎｄａｔｉｏｎ　ｏｆ　ｔａｒｇｅｔ　ｃｌａｓｓｉｉｆｃａｔｉｏｎ　ａｎｄ　ｒｅｃｏｇｎｉｉｔｏｎ，ｗｈｉｃｈ　ｃａｒｌ　ｂｅ　ｅｘｔｒａｃｔｅｄ　ｂａｓｅｄ　ｏｎ　ｐｉｘｅｌ　ｃｏｎｎｅｃｔｅｄ　ｒｅｌａｔｉｏｎ　ａｎｄ　ａｃｃｅｓｓｅｄ　ｅａｓｉｌｙ　ｂｙ　ｐｉｘｅｌ　ｔｈｒｏｕｇｈ　ｃｏｎｎｅｃｔｅｄ　ｃｏｍｐｏｎｅｎｔ　ｌａｂｄｉｎｇ　ｉｎ　ｂｉｎａｒｙ　ｉｍａｇｅ．Ｔｈｉｓ　ｐａｐｅｒ　ｂｒｉｅｆｌｙ　ａｎａｌｙｚｅｓ　ｔｈｅ　ｆｕｎｃｔｉｏｎ　ｏｆ　ｃｏｍｍｏｎ　ｃｏｎｎｅｃｔｅｄ　ｃｏｍｐｏｎｅｎｔ　ｌａｂｅ￣ｎｇ　ａｌｇｏｒｉｔｈｍ，ｐｏｉｎｔｓ　ｏｕｔ　ｔｈｅ　ｉｎａｐｐｌｉｃａｂｉｌｉｔｙ　ｏｆ　ｃｏｎｎｅｃｔｅｄ　ｃｏｍｐｏｎｅｎｔ　ｌａｂｅｌｉｎｇ　ａｌｇｏｒｉｔｈｍ　ｉｎ　ｔａｒｇｅｔ￣ａｍｒｅ　ｅｘｔｒａｃｔｉｏｎ　ａｉｍｉｎｇ　ａｔ　ｔｈｒｅｅ　ｋｉｎｄｓ　ｏｆ　ｓｐｅｃｉａｌ　ａｎｄ　ｃｏｍｍｏｎ　ｃｏｒｒｅｓｐｏｎｄｉｎｇ　ｒｅｌａｔｉｏｎｓ　ｂｅｔｗｅｅｎ　ｃｏｎｎｅｃｔｅｄ　ｃｏｍｐｏｎｅｎｔｓ　ａｎｄ　ｔａｒｇｅｔｓ，ａｎｄ　ｒｅｄｅｆｉｎｅｓ　ｔｈｅ　ｐｉｘｄ　ｃｏｎｎｅｃｔｉｖｉｙ　ｔｉｎ　ｔｈｅ　ｔａｒｇｅｔ　ｓｅｍａｎｔｉｃ　ｌｅｖｅｌ　ｔｏ　ｉｍｐｒｏｖｅ　ｔｈｅ　ｃｏｍｐｌｅｔｅｎｅｓｓ　ａｎｄ　ａｃｃｕｒａｃｙ　ｏｆ　ｔａｒｇｅｔ￣ａｍｒｅ．Ｕｓｉｎｇ　ｔｈｅ　ｒｅｇｉｏｎａｌ　ｂｏｕｎｄａｒｙ　ｓｃａｎｎｉｎｇ　ａｎｄ　ｔｈｅ　ｅｆｉｃｉｅｎｔｆ　ｌａｂｅｌｉｎｇ，ｔｈｅ　ｃｏｎｎｅｃｔｅｄ　ｒｅｌａｔｉｏｎ　ｄｅｐｅｎｄｉｎｇ　ｏｎ　ｔｗｏ—ｄｉｍｅｎｓｉｏｎａｌ　ｓｉｇｎａｌ　ｉｓ　ｒｅｃｏｇｎｉｚｅｄ　ａｎｄ　ｔｒａｎｓｆｏｒｍｅｄ　ｉｎｔｏ　ｏｎｅ—ｄｉｍｅｎｓｉｏｎａｌ　ｔｏ　ｍａｋｅ　ｔｈｅ　ｐｒｏｃｅｓｓｉｎｇ　ｐｒｏｃｅｄｕｒｅｓ　ｉｎ　ｅａｃｈ　ｒｏｗ（ｃｏｌｕｍｎ）ｍｕｔｕａｌｌｙ　ｉｎｄｅｐｅｎｄｅｎｔ，ＳＯ　ｔｈａｔ　ｔｈｅ　ｆｅａｔｕｒｅ　ｅｘｔｒａｃｔｉｏｎ（ｉｎｃｌｕｄｉｎｇ　ａｔｒｇｅｔ　ｃｏｎｔｏｕｒ）ａｎｄ　ｈｅｔ　ｃｏｎｎｅｃｔｅｄ　ｃｏｍｐｏｎｅｎｔ　ｌａｂｅｌｎｇ　ｉａｒｅ　ｒｅｌａｉｚｅｄ　ｔｈｒｏｕｇｈ　ｐｉｃｔｕｒｅ　ｓｃａｎｎｉｎｇ　ｒＯＷ　ｂｙ　ｒｏｗ（１ｉｎｅ　ｂｙ　ｉｆｎｅ），ｔｈｅ　ｌａｂｄｉｎｇ　ｎｕｍｂｅｒ　ｉｓ　ｃｏｎｔｉｎｕｏｕｓ．Ｆｉｎａｌｌｙ，ｔｈｒｏｕｇｈ　ｓｉｍｕｌａｔｉｏｎ，ｔｈｉｓ　ｐａｐｅｒ　ｖｅｒｉｉｆｅｓ　ａｎｄ　ａｎａｌｙｚｅｓ　ｈｅ　ｔｌａｇｏｒｉｔｈｍ　ｆｒｏｍ　ｓｕｃｈ　ａｓｐｅｃｓｔ　ａｓ　ｅｆｆｉｃｉｅｎｃｙ，ａｐｐｌｉｃａｂｉｌｉｙ　ｔａｎｄ　ｍｅｍｏｒｙ　ｃｏｎｓｕｍｐｔｉｏｎ．　Ｋｅｙ　ｗｏｒｄｓ：ｃｏｎｎｅｃｔｅｄ　ｃｏｍｐｏｎｅｎｔ　ｌａｂｅｌｉｎｇ；ｃｏｎｔｏｕｒ　ｔｒａｃｋｉｎｇ；￣ａｍｒｅ　ｅｘｔｒａｃｔｉｏｎ　１引言　目标特征是目标分类识别的基础，后者在图像分析及计　算机视觉等多个领域都有着广泛应用。由图像分割或运动检　测得到的像素连通区域与实际目标存在对应关系，连通域标　记也因此成为提取目标特征的有效手段。本文结合实际，从目　标语义理解角度定义像素连通，提高特征的完整陛和准确性；　定稿日期：２０１５－０３—１２　进而基于轮廓标记判定像素连通关系及所属目标，同时提取　５８　计算机与网络　特征。算法经一遍扫描完成原图目标标记处理且标号连续。并　将目标特征存储在一维数组的相应位置，便于通过标号直接　访问和应用。　同属一个目标的像素，不论其分布于前景连通域还是背　景连通域，都会对目标特征有贡献。为提高目标特征的完整陛　和准确性，在目标语义层次定义这些像素是连通的，进而基于　连通域分析提取目标特征。　２实现方法　按像素连通关系对图像中同值区域进行分类是连通域分　４．２目标轮廓及标记　轮廓是目标形状特征的集中反映，在平面图像中体现为　连通域边界像素的有序集，可分外轮廓和内轮廓，其中外轮廓　　析的主要内容，为便于同类像素访问类屙陛（如标号、特征　是对不同目标的分隔，内轮廓是对目标不同组成部分的分隔。　等），还需将类属性的存储位置信息反馈给所含的每个像素，　轮廓像素邻域中的背景像素称为目标的包围像素。该过程可由连通域标记算法实现。这样连通域分析包括连通　信息收集和下发２个过程，按处理方式的不同可分为逐行式　连通定义不同，轮廓特点也不尽相同，如图２所示。在对　应关系①下，目标的所有轮廓都是外轮廓，没有内轮廓；对应　可以有多条内轮廓；对　骄口逐邻域式Ｈ２种。前者逐行收集、下发连通信息，存在固有的　关系②下，目标有且只有一条外轮廓，标号冲突问题，通过改善连通信息记录、更新的方式并斟酌下　应关系③下，目标有且只有一条外轮廓，没有内轮廓。但不论　任一目标都有且只有这样一条外轮廓，即若顺　发的时机可在不同程度上提高算法效率；后者逐邻域收集、下　哪种对应关系，发连通信息。对邻域大量的重复处理成为影响算法性能的主　（逆）时针遍历该轮廓则目标像素均位于其右（左）侧，使得在　要因素。提高信息处理单位的层次。如行程而非像素，能在一　逐行扫描过程中最先遇到的像素必处在该轮廓上。利用这个　特点对连通域作标记处理，就可以实现不经任何处理而使目　定程度上改善算法眭能　。　标标号连续。　３应用局限性　受扫描顺序影响，上述算法不能方便地提取目标轮廓，而　轮廓正是目标形状特征的集中反映，从而丢失了后续目标分　类识别的有效依据。　利用目标轮廓的封闭特性，可以完成轮廓像素的有序遍　历＿ｌ１】和目标轮廓特征的提取。在该过程中。对轮廓像素及相应　的包围像素进行标记（轮廓像素标记为目标标号，外轮廓包围　像素标记位一１，内轮廓包围像素标记为目标标号的相反数），　从而将基于多维信息的连通关系判定转化到一维（行或列）　中，减少连通域关系判定中像素的重复扫描ｍ　ｑ或可能的等价　关系存储、处理　＿司等。　基于连通域分析提取目标特征，其成立的前提是同一目　标的像素在图像中完备连通。而不同目标的像素不具有连通　关系，即目标与连通域一一对应。但由于种种原因，同一个目　标的像素可能分布于不同的前景连通域，甚至背景连通域，此　时单纯依靠上述算法提取目标特征是失效的。　图２对应关系与目标轮廓示意图　４连通域分析　４．１目标连通定义　二值图像中，连通域与实际目标可能存在多种对应关系，　图２中字母表示所属目标，下标０代表外轮廓，ｉ代表内　轮廓，数字代表在其所属目标中的轮廓序号，箭头表示本文轮　廓跟踌；Ｊ顷序。　４．３目标连通关系判定　根据轮廓的封闭特陛，若像素属于某目标，则必被该目标　的轮廓所包围，在其所属行（列）中亦然；而轮廓跟踪可以完成　比较特殊而常见的有３种：①目标和前景连通域一一对应：②　目标与前景连通域及为其所包围的前景连通域对应：③目标　与前景连通域及为其所包围的背景连通域和前景连通域对　对轮廓点及包围点的正负标记，使任一目标被正负对包围。这　应。连通域与目标间不同对应关系及连通域标记结果如图１　所示。　样在每行（列）中，像素被正负对分割成目标区和非目标区２　种状态区间（后者在对应关系②下又可进一步分为内非目标　—　腑蝴嘲　矧应关系①　对应美承⑦　（由赠应关系④　区和外非目标区），同一区间内的像素具有连通性，且连通性　的改变只可能发生在正负对处。这样就将基于多维信息的连　通关系判定转化到一维（行或列）中，且各行（列）的判定过程相　图１连通域与目标的不同对应关系及标记结果示意图　５９　计算机与网络　６．２目标连通标记　针对同一二值图像，分别按对应关系①、对应关系②和对　应关系③进行连通域标记。为便于显示，令标号均匀分布在　［Ｏ，２５５］之间，标记结果如图３所示。　参考文献　【１］刘贤喜，李邦明，苏庆堂，等．一种新的二值图像连通区域准　确标记算法Ⅱ］．计算机工程与应用，２００７（２２）：７６－７８，９８．　【２］罗志灶＇周赢武，郑忠楷．二值图像连通域标记优化算法卟　圜６．３内存耗费　■圈田　安庆师范学院学报（自然科学版），２０１０，１６（４）：３４—３９．　［３］宋斌．一种新的图像连通域快速标号算法卟ｅ￣－Ｉ－－￣，Ｉ量技　术，２００９，３２（９）：６７—６８，７３．　（　源＝岫孽　）列应；毫系①　）列应关系②臼）列匝关系④　图３二值图像按不同对应关系的目标标记结果　［４】刘奇琦，龚晓峰．一种二值图像连通区域标记的新方法卟计　算机工程与应用，２０１２，４８（１１）：１７８—１８０，２００．　［５】张恒，胡文龙，丁赤飙．基于快速连通域分析的目标特征提　算法所需内存包括像素标号矩阵及目标特征数组，设图　像高日，宽　，目标特征用ｍ个字节表示，则算法可能占用的　最大内存约为（单位Ｂｙｔｅ）：　Ｈｘ　×取算ａｌＪ］．计算机工程与应用，２００９，４５（２９）：２３０－２３２，２４４．　［６】周跃，闫丰，章明朝，等．基于标号回传的二值图像连通体标记　算法Ｕ１．计算机工程与应用，２００９，４５（３３）：１５３—１５５．　［７】ＣＨＡＯ　Ｙｕ—ＹＡＮ，ＫｅＮＪＩ　ＳＵＺＵＫＩ．Ａ　ｍｎ—ｂａｓｅｄ　ｔＷＯ—ｓｃａｎ　ｌａｂｅｌｉｎｇ　ａｌｇｏｒｉｔｈｍ『Ａ］．Ｉｎ：４ｔｈ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｉ　－。ｇ　Ⅳｌ＋Ⅳ×ｍ　ｓ　ｘ（　Ｈ　式中，Ⅳ为可能的最大目标数，不大于Ｈ×　／４。由于算　法不需要处理标号冲突，故无需开辟额外空间存储连通关系　信息。　Ｉｍａｇｅ　Ａｎａｌｙｓｉｓ　ａｎｄ　Ｒｅｃｏｇｎｉｔｉｏｎ［Ｃ］．Ｍｏｎｔｒｅａｌ，Ｃａｎａｄａ，　２００７，３－４２．　【８】孔斌．快速连通域分析算法及实现Ⅲ．模式识别与人工智　７结束语　为提高基于连通域提取的目标特征的完整性和准确性，　本文针对二值图像中３种特殊而常见连通域与目标的对应关　能，２００３，６（１）：１１０—１１５．　［９］罗志灶，周赢武，郑忠楷．基于区域增长的连通域标记算法的　优化　闽江学院学报，２０１１，３２（２）：４１－４４．　【１０］ＣＨＡＮＧ　ｆｕ，ＣＨＥＮ　Ｃｈｕｎｊｅｎ，ＬＵ　Ｃｈｉｊｅｎ．Ａ　ｌｉｎｅａｒ—ｔｉｍｅ　ｃｏｍｐｏｎｅｎｔ——ｌａｂｅｌｉｎｇ　ｌｇｏｒａｉｔｈｍ　ｕｓｉｎｇ　ｃｏｎｔｏｕｒ　ｔｒａｃｉｎｇ　系，在目标语义层次重新定义像素连通，进而利用轮廓标记将　取决于多行信息的连通关系判定转化到每一行中，经一遍图　ｔｅｃｈｎｉｑｕｅ［Ｊ］．Ｃｏｍｐｕｔｅｒ　Ｖｉｓｉｏｎ　ａｎｄ　Ｉｍａｇｅ　Ｕｎｄｅｒｓｔａｎｄｉｎｇ，　２００３，９３（２）：２Ｏ６—２２０．　像扫描即完成连通域标记和目标特征提取。算法运行效率高、　占用内存少且鲁棒性好。　［１１］曹长虎，李亚非．一种二值图像连通区域标记快速算法Ｕ】．　科学技术与工程，２０１０，１０（３３）：８１６８—８１７１，８１８０．　商梭子鱼网络近日宣布梭子鱼下一代防火墙，邮件归档　网关，垃圾邮件防火墙和梭子鱼Ｗｅｂ应用防火墙现巳在　ＶＭｗａｒｅ　Ｒｅａｄｙ—ｖＣｌｏｕｄ　Ａｉｒ上获得认证，意味着以上梭子鱼　本地还是在云端往数据中心迁移业务数据将变得更加复杂且　具有安全挑战。但是我们很高兴看到梭子鱼的安全和存储解　决方案如今已获得ＶＭｗａｒｅ　Ｒｅａｄｙ的认证，在ｖＣｌｏｕｄ　Ａｉｒ上我　产品现已在ｖＣｌｏｕｄ　Ａｉｒ环境中通过技术验证，并被ＶＭｗａｒｅ　们将帮助我们共同的客户促进业务增长，并实现梭子鱼对客　ｖＣｌｏｕｄ　Ａｉｒ支持。　户一直以来的承诺，那即是为客户提供完善的安全防护阻止　网络威胁。”　ＶＭｗａｒｅ公司联盟计划的高级总监Ｈｏｗａｒｄ　Ｈａｕ表示：　“我们很高兴梭子鱼加入了ｖＣｌｏｕｄ　Ａｉｒ　ＩＳＶ计划并获得　ＶＭｗａｒｅ　Ｒｅａｄｙ—ｖＣｌｏｕｄ　Ａｉｒ的认证许可。梭子鱼下一代防火　墙，邮件归档网关，垃圾邮件防火墙和梭子鱼Ｗｅｂ应用防火　ＶＭｗａｒｅ　Ｒｅａｄｙ是技术联盟合作伙伴（ＴＡＰ）项目的联合　品牌推广计划，旨在帮助用户便捷识别已通过ＶＭｗａｒｅ云端　基础架构认证的产品。与定制产品相比，这些产品或解决方案　墙能够印上ＶＭｗａｒｅ　Ｒｅａｄｙ—ｖＣｌｏｕｄ　ｉｒ标记，Ａ代表着以上梭　可降低风险与项目成本。ＶＭｗａｒｅ　ＴＡＰ计划在全球拥有数千　子鱼产品有信心帮助客户在ＶＭｗａｒｅ　ｖＣｌｏｕｄ　ｒ上做到无缝　运行并可以部署到生产运营环境中。”　梭子鱼技术联盟副总裁Ｎｉｃｏｌｅ　Ｎａｐｉｌｔｏｎｉａ表示：“无论在　名会员，这些会员均为一流的技术合作伙伴并为满足每个不　同客户需求提供专业技术和业务解决方案ｊ　（何钰洁）　６１