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

张 恒 倪永婧

（1中国电子科技集团公司第五十四研究所，河北 石家庄 050081)（2河北科技大学，河北 石家庄 050011）

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

张 恒1倪永婧2

（1中国电子科技集团公司第五十四研究所，河北 石家庄 050081)（2河北科技大学，河北 石家庄 050011）

目标特征是目标分类识别的基础，在二值图像中常基于像素连通关系进行提取并通过连通域标记使所含像素能便捷访问。文章简要分析了常见连通域标记算法的性能，针对三种特殊而常见的连通域与目标间的对应关系指出其在目标特征提取中的不适用性，为提高目标特征完整性和准确性在目标语义层次重新定义了像素连通，利用区域边界扫描以及对边界像素的有效标记，将取决于二维信息的连通关系识别转化到一维中，使每行（列）的处理过程相互独立，从而实现一遍逐行（列）的图像扫描即可完成特征提取（包括目标轮廓）及连通域标记，且标号连续。最后通过仿真从效率、适用性及内存耗费等方面对算法进行了验证与分析。

连通域标记轮廓跟踪特征提取

1 引言

目标特征是目标分类识别的基础，后者在图像分析及计算机视觉等多个领域都有着广泛应用。由图像分割或运动检测得到的像素连通区域与实际目标存在对应关系，连通域标记也因此成为提取目标特征的有效手段。本文结合实际，从目标语义理解角度定义像素连通，提高特征的完整性和准确性；进而基于轮廓标记判定像素连通关系及所属目标，同时提取特征。算法经一遍扫描完成原图目标标记处理且标号连续，并将目标特征存储在一维数组的相应位置，便于通过标号直接访问和应用。

2 实现方法

按像素连通关系对图像中同值区域进行分类是连通域分析的主要内容，为便于同类像素访问类属性（如标号、特征等），还需将类属性的存储位置信息反馈给所含的每个像素，该过程可由连通域标记算法实现。这样连通域分析包括连通信息收集和下发2个过程，按处理方式的不同可分为逐行式[1-[4]2种。前者逐行收集、下发连通信息，存在固有的标号冲突问题，通过改善连通信息记录、更新的方式并斟酌下发的时机可在不同程度上提高算法效率；后者逐邻域收集、下发连通信息，对邻域大量的重复处理成为影响算法性能的主要因素。提高信息处理单位的层次，如行程而非像素，能在一定程度上改善算法性能[5-9]。

3 应用局限性

受扫描顺序影响，上述算法不能方便地提取目标轮廓，而轮廓正是目标形状特征的集中反映，从而丢失了后续目标分类识别的有效依据。

基于连通域分析提取目标特征，其成立的前提是同一目标的像素在图像中完备连通，而不同目标的像素不具有连通关系，即目标与连通域一一对应。但由于种种原因，同一个目标的像素可能分布于不同的前景连通域，甚至背景连通域，此时单纯依靠上述算法提取目标特征是失效的。

4 连通域分析

4.1 目标连通定义

二值图像中，连通域与实际目标可能存在多种对应关系，比较特殊而常见的有3种：①目标和前景连通域一一对应；②目标与前景连通域及为其所包围的前景连通域对应；③目标与前景连通域及为其所包围的背景连通域和前景连通域对应。连通域与目标间不同对应关系及连通域标记结果如图1所示。

图1 连通域与目标的不同对应关系及标记结果示意图

同属一个目标的像素，不论其分布于前景连通域还是背景连通域，都会对目标特征有贡献。为提高目标特征的完整性和准确性，在目标语义层次定义这些像素是连通的，进而基于连通域分析提取目标特征。

4.2 目标轮廓及标记

轮廓是目标形状特征的集中反映，在平面图像中体现为连通域边界像素的有序集，可分外轮廓和内轮廓，其中外轮廓是对不同目标的分隔，内轮廓是对目标不同组成部分的分隔，轮廓像素邻域中的背景像素称为目标的包围像素。

连通定义不同，轮廓特点也不尽相同，如图2所示。在对应关系①下，目标的所有轮廓都是外轮廓，没有内轮廓；对应关系②下，目标有且只有一条外轮廓，可以有多条内轮廓；对应关系③下，目标有且只有一条外轮廓，没有内轮廓。但不论哪种对应关系，任一目标都有且只有这样一条外轮廓，即若顺（逆）时针遍历该轮廓则目标像素均位于其右（左）侧，使得在逐行扫描过程中最先遇到的像素必处在该轮廓上。利用这个特点对连通域作标记处理，就可以实现不经任何处理而使目标标号连续。

利用目标轮廓的封闭特性，可以完成轮廓像素的有序遍历[11]和目标轮廓特征的提取。在该过程中，对轮廓像素及相应的包围像素进行标记（轮廓像素标记为目标标号，外轮廓包围像素标记位-1，内轮廓包围像素标记为目标标号的相反数），从而将基于多维信息的连通关系判定转化到一维（行或列）中，减少连通域关系判定中像素的重复扫描[4][9,10]或可能的等价关系存储、处理[5-8]等。

图2 对应关系与目标轮廓示意图

图2中字母表示所属目标，下标o代表外轮廓，i代表内轮廓，数字代表在其所属目标中的轮廓序号，箭头表示本文轮廓跟踪顺序。

4.3 目标连通关系判定

根据轮廓的封闭特性，若像素属于某目标，则必被该目标的轮廓所包围，在其所属行（列）中亦然；而轮廓跟踪可以完成对轮廓点及包围点的正负标记，使任一目标被正负对包围。这样在每行（列）中，像素被正负对分割成目标区和非目标区2种状态区间（后者在对应关系②下又可进一步分为内非目标区和外非目标区），同一区间内的像素具有连通性，且连通性的改变只可能发生在正负对处。这样就将基于多维信息的连通关系判定转化到一维（行或列）中，且各行(列)的判定过程相互独立，通过对图像逐行（列）扫描，即可完成连通关系判定和目标特征提取。

5 算法实现

5.1 数据结构

其中，FType为针对不同对应关系所采用的相应分析规则，该值至晚在外轮廓跟踪后确定。flag为目标序号，也为目标像素的标号，与在一维数组中的存储位置直接相关。pFeature指向为目标特征分配的存储空间。

定义一维object型数组array_objects，数组大小视可能的最大目标数而定。

5.2 算法描述

不妨设原二值图像中前景像素为1，背景像素为0，并初始化目标序号为2。首先将图像上下左右边界像素统一标记为-1[11]，同时初始化区间状态为非目标区，然后进行逐行扫描。为叙述方便，用P表示当前像素，V表示像素值，F记录目标标号，Tag记录区间状态。根据区间状态对连通域分析算法作如下描述：

ⅠTag=-1，即非目标区：

A若V=1，则更新F为F+1，并以P为起始点启动轮廓遍历，同时分别标记轮廓点和包围点为F和-1，最后更新Tag为F；

B若V跃1，则更新Tag为V。

ⅡTag跃1，即目标区：

A若V约0，则更新Tag为V；

B若V=0，针对不同对应关系相应处理如下：

①对应关系I：启动外轮廓遍历，标记轮廓点为Tag，包围点为-1，并将轮廓特征计入目标Tag；

更新Tag为-1；

②对应关系II:启动内轮廓遍历，标记轮廓点为Tag，包围点为-Tag，并将轮廓特征计入目标Tag；更新Tag为-Tag；

③对应关系III:标记P为Tag；并将特征计入目标Tag；

C若V=1，则标记P为Tag，并将特征计入目标Tag。

ⅢTag约-1，即内非目标区（仅限于对应关系②）：

A若V=1，则更新Tag为-Tag；启动内轮廓遍历，标记轮廓点为Tag，包围点为-Tag，并将轮廓特征计入目标Tag；

B若V跃1，则更新Tag为V。

6 实验与分析

本节在Windows XP操作系统、奔4处理器、3G主频、1G内存的测试平台下，对算法性能及实际应用给出验证。

6.1 算法效率及鲁棒性

本节采用多种测试图像检验算法效率及其鲁棒性，包括汉字、指纹、指纹骨架等，并对这些图像作旋转、翻转等变换，以探求图像扫描顺序、连通域形状及相对分布对算法效率的影响。将本文算法与经典的回溯处理式[1]、种子增长式[4]及基于行程的优化算法[5]按对应关系①作效率对比，测试中只关心前景连通域并采用8-连通邻域定义，且要求连通域标号连续（回溯法未作此要求）。同时定义时间耗费的平均相对偏差衡量算法鲁棒性。

表1 连通域标记算法效率及鲁棒性

注：像素回溯和行程等价算法中最大标号标注于所耗时间后的括号内。

可以看出，相对于文献算法，本文算法在效率、鲁棒性等方面都获得了极大改善。基于逐行收集连通关系的像素回溯式、行程等价式等算法的鲁棒性不及逐邻域式，这是因为连通信息不完备导致的标号冲突受图像扫描顺序、连通域形状的影响更为严重。种子增长类算法的效率普遍较低，尤其在连通域轮廓所占比例较小的情况下，邻域的重复处理很严重。本文算法所涉及的重复操作只发生在连通域轮廓处，而轮廓像素占连通域的比例通常是比较小的，且不随图像的变换而改变，故具有较高的效率和较好的鲁棒性。实际上，在轮廓象素所占比例很小的图像中，算法所耗时间与图像大小成正比[10]。

6.2 目标连通标记

针对同一二值图像，分别按对应关系①、对应关系②和对应关系③进行连通域标记。为便于显示，令标号均匀分布在[0,255]之间，标记结果如图3所示。

图3 二值图像按不同对应关系的目标标记结果

6.3 内存耗费

7 结束语

为提高基于连通域提取的目标特征的完整性和准确性，本文针对二值图像中3种特殊而常见连通域与目标的对应关系，在目标语义层次重新定义像素连通，进而利用轮廓标记将取决于多行信息的连通关系判定转化到每一行中，经一遍图像扫描即完成连通域标记和目标特征提取。算法运行效率高、占用内存少且鲁棒性好。

[1]刘贤喜,李邦明,苏庆堂,等.一种新的二值图像连通区域准确标记算法[J].计算机工程与应用,2007(22):76-78,98.

[2]罗志灶,周赢武,郑忠楷.二值图像连通域标记优化算法[J].安庆师范学:学报(自然科学版),2010,16(4):34-39.

[3]宋斌.一种新的图像连通域快速标号算法[J].电子测量技术,2009,32(9):67-68,73.

[4]刘奇琦,龚晓峰.一种二值图像连通区域标记的新方法[J].计算机工程与应用,2012,48(11):178-180,200.

[5]张恒,胡文龙,丁赤飙.基于快速连通域分析的目标特征提取算法[J].计算机工程与应用,2009,45(29):230-232,244.

[6]周跃,闫丰,章明朝,等.基于标号回传的二值图像连通体标记算法[J].计算机工程与应用,2009,45(33):153-155.

[7]CHAO YU-YAN,KENJI SUZUKI.A run-based two-scan labeling algorithm[A].In:4th International Conference on Image Analysis and Recognition[C].Montreal,Canada, 2007,3-42.

[8]孔斌.快速连通域分析算法及实现[J].模式识别与人工智能,2003,6(1)：110-115．

[9]罗志灶,周赢武,郑忠楷.基于区域增长的连通域标记算法的优化[J].闽江学:学报,2011,32(2):41-44.

[10]CHANG fu,CHEN Chunjen,LU Chijen.A linear-time component-labeling algorithm using contour tracing technique[J].Computer Vision and Image Understanding, 2003,93(2):206-220.

[11]曹长虎,李亚非.一种二值图像连通区域标记快速算法[J].科学技术与工程,2010,10(33):8168-8171,8180.

Connected Component Labeling Algorithm Oriented to Target Feature Extraction

ZHANG Heng1,NI Yong-jing2
(1 The 54th Research Institute of CETC,Shijiazhuang Hebei 050081,China) (2 Hebei University of Science and Technology,Shijiazhuang Hebei 050011,China)

The target feature is the foundation of target classification and recognition,which can be extracted based on pixel connected relation and accessed easily by pixel through connected component labeling in binary image.This paper briefly analyzes the function of common connected component labeling algorithm,points out the inapplicability of connected component labeling algorithm in target feature extraction aiming at three kinds of special and common corresponding relations between connected components and targets,and redefines the pixel connectivity in the target semantic level to improve the completeness and accuracy of target feature.Using the regional boundary scanning and the efficient labeling,the connected relation depending on two-dimensional signal is recognized and transformed into one-dimensional to make the processing procedures in each row(column)mutually independent,so that the feature extraction(including target contour)and the connected component labeling are realized through picture scanning row by row(line by line),the labeling number is continuous.Finally,through simulation,this paper verifies and analyzes the algorithm from such aspects as efficiency,applicability and memory consumption.

connected component labeling;contour tracking;feature extraction

TP391

A

1008-1739（2015）07-58-4

定稿日期：2015-03-12