CN105261049B - 一种图像连通区域快速检测方法 - Google Patents

Abstract

本发明公开了一种图像连通区域快速检测方法，该方法首先将图像进行二值化处理，得到二值图像，将连通区标记二维数组b、连通区点数记录数组d、连通区合并标记数组t全部清0；然后从左到右、从上到下逐点扫描图像像素点p，当该点不是白色像素点则图像扫描完毕，将连通区标记相同的连通区合并，否则继续对该点所属连通区进行判断并标记。本发明方法与其他同类算法相比，针对像素点的4个邻域做出细致考虑，引入了连通区标记二维数组b、连通区点数记录数组d和连通区合并标记数组t，有效降低了图像的扫描次数，可在图像扫描完毕后，将需要合并的连通区的序号标记一次性修改，并且逻辑简单，容易实现，大大提升了图像连通检测速度，实现实时性。

Description

一种图像连通区域快速检测方法

技术领域

本发明涉及数字图像处理，具体指一种图像连通区域快速检测方法。

背景技术

数字图像处理被广泛应用于模式识别、安全监控、医疗成像等领域。图像处理的研究方向非常广泛，集中了各类先进的理论与算法，包括图像增强、噪声去除、数据压缩与复原、超分辨率重建、图像匹配与运动补偿等。在工程应用中，对很多图像的分析都会转换为二值图像进行，二值化加数学形态学方法能解决很多基于图像分析的目标提取与模式识别问题。其中，连通区域检测是二值图像分析的重要方法之一。通过对二值图像的连通性能检测，可以得到连通区域的数量、面积、分布特征等重要信息，可广泛应用于目标形状分析与模式识别中。

在图像处理过程中，为了满足实时性要求，处理速度是一个重要的评判指标。图像连通检测虽原理简单，技术难度不高，但绝大部分连通检测算法计算复杂度高，需要进行多次扫描，严重影响处理速度，难以实现实时处理。已有的连通区域检测算法可分为两类：一类是局部邻域算法，这类算法有多种不同形式，基本思想是从局部到整体，要逐个检查每个连通成分，对每个连通区都要先确定一个“种子点”，再向周围邻域扩展并填入标记；另一类是“分而治之”算法，基本思想是从整体到局部，先确定不同的连通成分，再对每一个连通区用区域填充方法填入标记。通常使用的连通区域检测算法有递归法、顺序法和游程标记法等。递归法需要大量的存储空间，对于大尺寸的图像，不仅耗费内存空间，运行速度也明显降低；顺序法至少需要扫描图像两次，处理过程中使用等价表来解决标记冲突问题，最终得到的标记图顺序杂乱，采用并行运算时，合并区域则会非常繁琐；游程标记法的特点是存储空间小、易于并行处理，但处理过程仍然需要两次扫描并且根据等价表来解决标记冲突。此外，游程标记法一般适用于横向连接点较多的情况，如果横向存在很多单像素点，则很不适用。所以，图像连通检测的关键问题是如何制定算法策略，不受任何连通形状的限制，还尽可能减少扫描次数，提高运行速度，满足实时性要求。

发明内容

针对现有技术存在的上述问题，本发明提供了一种图像连通区域快速检测方法，解决了一般连通检测算法计算复杂度高，需要进行多次扫描，严重影响处理速度，难以实现实时处理问题。

为实现上述目的，本发明采用如下技术方案：一种图像连通区域快速检测方法，包括如下步骤：

S1: 将图像进行二值化处理，得到二值图像；

初始化：将连通区标记二维数组b、连通区点数记录数组d、连通区合并标记数组t全部清0，打开二值图像，以白色像素点为检测目标；

S2：按从左到右、从上到下逐点扫描图像像素点p，判断像素点p是否为白色像素点;当像素点p不是白色像素点则转向步骤S6，否则执行下一步；

S3: 对像素点p所属连通区进行判断并标记：从连通区标记二维数组b中取图像像素点p的左、左上、上和右上四个邻近点的连通区序号值，分别记为x₁、x₂、x₃、x₄，如果x₁、x₂、x₃、x₄中某些点超出边界无法取得，则将其设为0；

另设变量x，定义其取值规则为：若x₂、x₃、x₄均为0，则x取0，否则x按顺序取第一个非0值；在获得x的值后，按以下步骤进行：

a）若x=0，且x₁=0，则图像像素点p为新的连通区，按照k=k+1的序号累加方式得到一个新的连通区序号k，根据图像像素点p的位置，将新的连通区序号k记录在连通区序号标记数组b中，并将连通区点数记录数组d中新的连通区序号k对应的元素加1,即d[k]=d[k]+1；然后，转向步骤S3；

b）若x=0，且x₁≠0，则图像像素点p不是新的连通区，p点属于x₁的连通区，故在连通区标记二维数组b中将图像像素点p的连通区序号标记为x₁，并修改连通区点数记录数组d，将连通区点数记录数组d中连通区序号标记为x₁对应的元素加1，即d[x₁]=d[x₁]+1；然后，转向步骤S6;

c）若x₃=0，x₄≠0，且x₁、x₂存在非0值时，图像像素点p承担了将两个连通区连接起来的功能，取得x₄的值以及x₁、x₂中的第一个非0值，共两个值，然后转向步骤S4；

d）若上面条件均不满足，转向步骤S5；

S4：根据连通区合并标记数组t，检查步骤c）中所取两个值代表的连通区是否已合并，若没合并，则在连通区合并标记数组t中将这两个连通区序号作合并标记，标记的方法是，若i、j两个连通区需要合并，就改写t[i]=j或者t[j]=i；

S5：在连通区标记二维数组b中将图像像素点p的连通区序号标记为x，并将x域的点数加1，即d[x]=d[x]+1;

S6：检查图像是否扫描完毕，若还没扫描完毕转向步骤S2，若已扫描完毕，则执行下面步骤S7;

S7：根据连通区合并标记数组t，对前面步骤得到的连通区标记二维数组b和连通区点数记录数组d进行修改，实现连通区的合并处理，扫描连通区标记二维数组b的非0点，设其序号的值为j，j为连通区标记二维数组b的非0点的连通区序号（也即连通区标记二维数组b的元素值），根据t[j]取值做如下处理：

a）若t[j]=0，说明以j为连通区序号的点构成了一个单独的域，不需要与任何其他域进行合并；

b）若t[j]≠0，说明以j为序号标记值的域与以t[j]为标记值的域是连通的，应进行合并，将所有连通序号标记为j的点修改为t[j]，同时修改连通区点数数组d，d[t[j]]= d[j]+ d[t[j]]，然后将d[j]清0；

S8：依据最终的连通区标记二维数组b和连通区点数记录数组d来确定连通区数量、点数和位置分布信息，并根据这些信息实现图像分割，得到连通区的外接矩形。

本发明提供的一种图像连通区域快速检测方法，不仅降低了图像的扫描次数，加快了速度，而且逻辑简单，容易实现。对图像采用从左到右，从上到下的扫描方式，因此对任意白色像素点的连通性判断依赖于其左边一个和上面三个像素点是否存在白色像素点，使用连通区序号标记二维数组b进行记录。由于对图像采用顺序扫描方式，对某些复杂的连通区域，必然会出现刚开始是若干个独立的连通区，在后续扫描中出现公共连接点，从而需要合并的情况。为此，在对二值图像的4邻域像素扫描的基础上，引入了连通区合并标记数组t，将可以进行合并的两个或两个以上连通区标记出来，在图像扫描完毕后一次性完成修改，避免了大多数算法要进行多次修改的弊端，大大提升了图像连通检测速度，也是本发明的重要价值之一。最后，根据修改后的连通区标记二维数组b的值确定连通区的数量、每个连通区包含的点数、位置分布等信息，得到每个连通区的外接矩形坐标。这种新型的图像连通检测快速算法可应用于图像分割，噪声去除、超分辨率重建、图像匹配与运动补偿、目标形状分析与模式识别等领域。

相对于现有技术，本发明具有如下优点：

本发明提供的图像连通区域快速检测方法与其他同类算法相比，针对像素点的4个邻域做出细致考虑，引入了连通区标记二维数组b、连通区点数记录数组d和连通区合并标记数组t，有效降低了图像的扫描次数，可在图像扫描完毕后，将需要合并的连通区的序号标记一次性修改，并且逻辑简单，容易实现，大大提升了图像连通检测速度，实现实时性。

附图说明

图1为本发明图像连通区域快速检测方法的实施流程图。

图2为p点左、左上、上和右上四个邻近点。

图3为经p点合并两个独立连通区的三种情况

图4为实施例用于不本发明算法测试的图例。

图5为实施例的测试结果。

具体实施方式

下面对本发明作进一步详细说明。

本发明提供的图像连通区域快速检测方法，综合运用了二值图像像素的连通特征、4邻接像素扫描模式、连通区序号标记二维数组b、连通区点数记录数组d、连通区合并标记数组t，利用较少的内存和算法处理资源，解决了一般连通检测算法计算复杂度高，需要进行多次扫描，严重影响处理速度，难以实现实时处理等问题，可应用于图像分割、噪声去除、超分辨率重建、图像匹配与运动补偿、目标形状分析与模式识别等领域。

针对二值图像，指定黑色像素为背景（也可指定白色像素为背景，流程演变为检测黑色像素点的连通情况），被测图像经过一次扫描后，可利用b数组对所有白色像素点指定所属连通区序号，并通过连通区合并标记数组t快速实现连通区域的合并，使图像中任意连通区域的所有像素点具有一个相同的连通序号值，而处在不同连通区的点对应的序号值不同。同时，数组d中保留了图像中具有相同序号值的像素点个数，反映了各连通区的面积。由此，可以得到图像中连通区的数量，各连通区的面积、形状、分布规律、外接矩形坐标等，可应用于图像降噪、超分辨率重建、图像匹配与运动补偿、目标形状分析与模式识别等领域。

本发明的基本思想是：取得一幅二值图像，以白色像素为前景，黑色像素为背景，从左至右、从上至下扫描图像，对所有前景像素点标记一个连通区序号，最后，具有相同序号的点为同一个连通区域，从而得到连通信息。针对现有图像连通检测算法的不足和应用需求，在二值图像的4邻域像素扫描的基础上，引入了连通区合并标记数组t的概念，将属于同一个连通区的两个或两个以上连通区进行合并，大大提升了图像连通检测速度，获得图像中连通区的所有信息，确定连通区的位置并绘制外接矩形。

本发明中，引入连通区序号标记二维数组b来记录白色像素点所属连通区序号，数组的行、列数分别对应二值图像的行数和列数，数组元素b[x][y]的值代表图像坐标为(x,y)的像素点对应的连通区序号；引入连通区点数记录数组d来记录属于同一个连通区的白色像素点的个数，d[i]的值代表连通区序号为i的区域的像素点数；引入连通区合并标记数组t来记录某两个具有不同序号的连通区由于公共连接点的出现，需要合并为同一个连通区。若序号分别为i和j的两个连通区需要合并，就设t[i]=j（也可设t[j]=i），表示最后处理时，需将b中所有序号值为i的点改为j。

下面结合一个非限定性实例对本发明作进一步的说明，

参见图1、图2、图3、图4、图5，一种新的图像连通检测快速算法，可广泛应用于图像分割、噪声去除、图像匹配与运动补偿、目标形状分析与模式识别等领域，其实施流程由图1所示。

首先，将图像按照应用需要进行二值化处理，得到一幅二值图像。按从左至右，从上至下顺序扫描二值图像的所有点，当扫描到一个白色像素点p时，白色像素点的灰度值为255，黑色像素点的灰度值为0。首先根据图2所示考查其四个邻域点。若邻域四点无白点，则p点引出一个新的连通区，需要生成一个新的连通序号并记录在连通区序号标记二维数组b中，同时，修改连通区点数记录数组d，使该连通区点数加1。若邻域四点有白点存在，则p点将合并到已有连通区，在b中对该点作标记并修改点数数组d。在图3所示三种情况下，p点将成为原来可能独立的两个连通区的公共连接点，采用合并标记数组t记录待合并的连通区序号，将p归入其中任意一个连通区，并将该连通区点数加1。当图像扫描完毕后，针对连通区序号标记二维数组b进行扫描，对b的非0元素对应的点进行处理。依据连通区合并标记数组t，对可以合并为同一个连通区的两个或两个以上的连通区标记相同的序号，并对连通区点数记录数组d进行修改。最后，依据修改后的连通区序号标记数组b和点数记录数组d的值确定连通区的数量、各连通区点数、位置分布等信息，得到每个连通区的外接矩形坐标，供后续应用。

实施例：首先构造了一个测试图，见图4。此测试图由若干键盘字符和手绘图组成，目的是涵盖连通区域的各种复杂形状和特殊分布。测试结果如图5，对每个连通区画出了外接矩形。实施例中以黑色为背景，检测白色区域的连通情况，若以白色为背景算法并无区别，在此不作限定。本发明的优势是扫描次数少，运行速度快，算法逻辑清楚，易于计算机编程。下面针对测试图描述连通检测的具体实施过程，对不同的测试图算法无区别：

（1）初始化。对连通区序号标记数组b、连通区点数记录数组d、连通区合并标记数组t进行清0处理，表示在开始扫描之前不存在连通区，所有连通区序号的点数为0，也不存在任何需要连接的连通区。设k为连通区序号变量，在扫描过程中发现新的连通区时，对其加1后提供连通区序号。其初值也设为0，表示连通区序号从1开始。

（2）从左到右、从上到下逐点扫描图像像素点p，判断该点是否为白色像素点。若不为白色像素点则扫描下一点直到扫描完毕。若为白色点则进行下面步骤（3）的分析处理。

（3）判断是否为新的连通区。

步骤判断是否为新的连通区。参见图2，考查p点的四个邻域点。若在它的左、左上、上、右上任一位置存在一个或多个白色像素点，则p点不构成新的连通区，而是归入某一现成连通区中，由下面第（4）步进行进一步处理。反之，若四个点均为黑点，即全为0，则p成为一个新连通区的第一点，先将k加1得到新的序号，根据p的位置将k存入b中，将d[k]加1。由于原来d[k]被初始化成0，所以现在d[k]为1，表示序号为k的连通区有一个点，然后，转向步骤（2）扫描下一点。

（4）存在非0值，表示图2中p点的邻域点存在白点。其中图3所示的三种情况，表示邻近的四个点存在两个连通区，并且由于扫描顺序的关系，这两个连通区可能具有不同的序号，即它们是分离的，但有了p点的白点后，这两个独立的连通区通过p点连通了，应当合并，由下面步骤（5）进行判断处理。

除这三种情况外，选择中任意的非0值（设为m）作为p点的连通区序号并记录到b中，同时将d[m]加1，然后，转向步骤（2）扫描下一点。

（5）连通区合并标记数组t的记录用合并标记数组t记录连通区，其具体实施方法是：若序号分别为i和j的两个连通区需要合并，就设t[i]=j（也可设t[j]=i），表示最后处理时，需将b中所有序号值为i的点改为j。引入连通区合并标记数组t，将需要合并的独立连通区记录下来，在整幅图像扫描完毕后一次性修改，大大节省了连通区标记的时间，提升了连通标记的速度。在完成合并标记记录后，p点的连通区序号可标记为i（由于已有合并标记，p的连通区序号也可标记为j）并记录到b中，同时将d[i]加1，然后，转向步骤（2）扫描下一点。

（6）在所有图像点扫描完毕后，针对连通区序号标记二维数组b进行扫描。结合发明技术方案说明中（7）的步骤，依据连通区合并标记数组t，将b中可进行合并的独立连通区序号改为相同数字，同时对连通区点数记录数组d进行修改。依据修改后的连通区序号标记数组b的值确定连通区的数量、点数、位置分布等信息，并画出每个连通区的外接矩形，结果由图5所示。

实施例还对执行速度进行了测试，在Pentium 3.2GHz计算机上，用VC++编程，对实施例的测试图进行连通检测循环测试，循环执行内容从初始化开始到获得最终的连通区标记和点数结束，不包括文件打开和界面显示，平均每次耗时为26mS，具有良好的速度性能，满足实时性要求。

最后说明的是，以上实施例仅用以说明本发明的技术方案而非限制，尽管参照较佳实施例对本发明进行了详细说明，本领域的普通技术人员应当理解，可以对本发明的技术方案进行修改或者等同替换，而不脱离本发明技术方案的宗旨和范围，其均应涵盖在本发明的权利要求范围当中。

Claims (1)

1.一种图像连通区域快速检测方法，其特征在于，包括如下步骤：

S1:将图像进行二值化处理，得到二值图像；

初始化：将连通区标记二维数组b、连通区点数记录数组d、连通区合并标记数组t全部清0，打开二值图像，以白色像素点为检测目标；

S2：按从左到右、从上到下逐点扫描图像像素点p，判断像素点p是否为白色像素点;当像素点p不是白色像素点则转向步骤S6，否则执行下一步；

S3:对像素点p所属连通区进行判断并标记：从连通区标记二维数组b中取图像像素点p的左、左上、上和右上四个邻近点的连通区序号值，分别记为x1、x2、x3、x4，如果x1、x2、x3、x4中某些点超出边界无法取得，则将其设为0；

另设变量x，定义其取值规则为：若x2、x3、x4均为0，则x取0，否则x按顺序取第一个非0值；在获得x的值后，按以下步骤进行：

a）若x=0，且x1=0，则图像像素点p为新的连通区，按照k=k+1的序号累加方式得到一个新的连通区序号k，k为连通区序号，初始时k设为0，使得检测到的第一个连通区序号为1，并在检测到新的连通区后逐渐递增，根据图像像素点p的位置，将新的连通区序号k记录在连通区标记二维数组b中，并将连通区点数记录数组d中新的连通区序号k对应的元素加1,即d[k]=d[k]+1；然后，转向步骤S3；

b）若x=0，且x1≠0，则图像像素点p不是新的连通区，p点属于x1的连通区，故在连通区标记二维数组b中将图像像素点p的连通区序号标记为x1，并修改连通区点数记录数组d，将连通区点数记录数组d中连通区序号标记为x1对应的元素加1，即d[x1]=d[x1]+1；然后，转向步骤S6;

c）若x3=0，x4≠0，且x1、x2存在非0值时，图像像素点p承担了将两个连通区连接起来的功能，取得x4的值以及x1、x2中的第一个非0值，共两个值，然后转向步骤S4；

d）若上面条件均不满足，转向步骤S5；

S4：根据连通区合并标记数组t，检查步骤c）中所取两个值代表的连通区是否已合并，若没合并，则在连通区合并标记数组t中将这两个连通区序号作合并标记,标记的方法是，若i、j两个连通区需要合并，就改写t[i]=j或者t[j]=i；

S5：在连通区标记二维数组b中将图像像素点p的连通区序号标记为m，并将m域的点数加1，即d[m]=d[m]+1;

S6：检查图像是否扫描完毕，若还没扫描完毕转向步骤S2，若已扫描完毕，则执行下面步骤S7;

S7：根据连通区合并标记数组t，对前面步骤得到的连通区标记二维数组b和连通区点数记录数组d进行修改，实现连通区的合并处理，扫描连通区标记二维数组b的非0点，设其序号的值为j，j为连通区标记二维数组b的非0点的连通区序号，根据t[j]取值做如下处理：

a）若t[j]=0，说明以j为连通区序号的点构成了一个单独的域，不需要与任何其他域进行合并；

b）若t[j]≠0，说明以j为序号标记值的域与以t[j]为标记值的域是连通的，应进行合并，将所有连通序号标记为j的点修改为t[j]，同时修改连通区点数数组d，d[t[j]]=d[j]+d[t[j]]，然后将d[j]清0；

S8：依据最终的连通区标记二维数组b和连通区点数记录数组d来确定连通区数量、点数和位置分布信息，并根据这些信息实现图像分割，得到连通区的外接矩形。