一种基于启发式策略的连通区域标记算法
VIP免费
一种基于启发式策略的连通区域标记算法
摘要：论文首先分析了目前几种二值图像连通区域的标记方法，并在区域生长算法的基础
上提出了一种基于启发式的连通区域标记算法。该算法可以避免重复标记，一次标记完所有
的连通区域，并且不受图形形状的影响，同时算法提出的启发式策略，可以有效地减少逐
行扫描像素的次数，也能减少八领域搜索的次数。实验结果显示该算法的高效性和稳定性。
关键词：二值图像；启发式；连通区域标记；
中图分类号： 文献标识码：A 文章编号：
0 引 言
二值图像是图像经过预处理得到的图像，它是由值为“0”的像素点（背景）和值为
“1”的像素点（图形）组成的图像，二值图像的连通区域就是那些彼此连接的像素值为
“1”的集合。对二值图像的连通区域标记是图像识别的预处理中的关键一步，已经被广泛
应用到很多实际领域中，如车牌识别系统[1]，验证码识别技术[2]。这种技术有三个作用：1.
实现待识别对象的粗定位；2. 去除图片中的孤立噪声点；3.将图形分解为多个连通子图，
便于对每一个子图进行处理。总之，二值图像的连通区域标记技术是图像处理中的关键一
步，为图像的进一步处理打下基础。
目前为止，二值图像的连通区域标记已有不少算法，一种传统的连通区域的标记方法
[3] 采用了二次扫描图像的方式，在第一次扫描中采取逐行逐列的方式扫描像素，将属于同
一个连通区域的像素赋予相同的连通标号，采取这种方式，通常会产生被重复标记的现象，
也会导致同一个区域的子区域有不同的标号。因此，为了消除这种重复标记的现象，必须
执行第二次扫描，在第二次扫描中，将属于同一个连通区域而具有不同标记的子区域合并。
采取这种传统的方式，效率往往比较低，特别地，如果图像的重复性标记比较严重，如 U
型图，效果很不理想。文献[4]提出了一种基于线的标号传播的连通区域标记方法，其思想
是对图像进行逐行扫描，当扫描出当前行的一条直线，就判断是否与上一行的直线存在连
通性，如果满足就将两条直线合并，提高了连通区域标记的效率。文献[5]中提出了区域增
长法，其核心思想为依次扫描二值图像的每一个像素，当找到某一个未标记的目标像素点
时，将其压入堆栈，并从该点开始反复标记其领域，直到堆栈为空。文献[6]提出了类似于
区域增长的方法，较好得解决了重复标记的问题。
本文对文献[6]的算法进行了改进，提出了一种启发式策略，该算法继承了文献[6]算
法的优点，能够一次扫描标记出图像中的所有的连通体区域，同时在此原有算法的基础上
减少了扫描次数和搜索次数。
1 算法改进基础
文献[6]提出的算法基本思想是对输入的图像施行逐行扫描，找到一个未标记的点，标
记该点，并搜索该点的八邻域，标记满足连通性要求的且未标记过的点，这些点作为区域
增长的种子点放入数组中，之后不断从数组中取出“种子”，循环执行上述操所，直到数
组为空，表示一个连通体标记的完成。用同样的方式标记下一个连通体，直到所有的连通
体全部标记完成。我们通过对连通体的特性进行分析认为算法[6]提出的搜索和扫描策略仍
然有改进的空间。为此总结出了关于连通区域扫描和搜索的两条规律，这也是改进算法的
思想基础。本文将根据图 1 示意的二值图像来解释这两条规律。
规律 1：
假设像素 P属于某一个连通区域，并且 P为已经标记访问过的像素点，那么我们可以
确信 P1-P8 在下一次的连通体搜索是不需要访问的。
证明：假设 P1-P8 在下一次的连通体搜索是需要扫描访问的，
那么我们认为P1-P8 不在当前的连通体内（如果 P1-P8 在当前
的连通体内，就不可能是下一个连通区域的点）我们取P1来
证明，其他的可以类似得出，P1 必须为 1（如果 P1 值为 0，那
么没有必要去扫描它），那么 P1肯定在当前的连通体内，这
个与假设矛盾，证毕。
规律 2：
在八领域搜索上，我们也发现了一些规律，假设 P1-P8 以及 P
属于同一个连通区域，如果 P为已经标记访问过，那么我们认
为P 周围的八个点已经被搜索过，因此对于 P1 而言，没有必
要对所有 8个方向进行搜索，在 P1 的邻居点P2、P3、P7、P8、P
之前已经被搜索过，不需再去搜索，同理，对于 P2 而言，邻居点P1、P3、P 也不需要去
搜索。
2 启发式策略
文献[6]中提出的算法在扫描和搜索上具有一定的盲目性，本文根据前面讲述的规律，
制定了一系列策略，使算法在扫描和搜索上具有启发性，提高运行效率。为了将启发式策
略更好地描述出来，文中提出了两个概念：
定义1
摘要：
展开>>
收起<<
一种基于启发式策略的连通区域标记算法摘要：论文首先分析了目前几种二值图像连通区域的标记方法，并在区域生长算法的基础上提出了一种基于启发式的连通区域标记算法。该算法可以避免重复标记，一次标记完所有的连通区域，并且不受图形形状的影响，同时算法提出的启发式策略，可以有效地减少逐行扫描像素的次数，也能减少八领域搜索的次数。实验结果显示该算法的高效性和稳定性。关键词：二值图像；启发式；连通区域标记；中图分类号：文献标识码：A文章编号：0 引言二值图像是图像经过预处理得到的图像，它是由值为“0”的像素点（背景）和值为“1”的像素点（图形）组成的图像，二值图像的连通区域就是那些彼此连接的像素值为“1”的集...
相关推荐
-
新能源项目融资计划VIP免费
2024-12-31 12 -
新能源汽车运营服务公司商业计划书VIP免费
2024-12-31 7 -
上海xxx新能源股份有限公司商业计划书VIP免费
2024-12-31 47 -
绿特新能源商业计划书VIP免费
2024-12-31 9 -
关于新能源充电项目创业计划VIP免费
2024-12-31 13 -
太阳能充电器创业计划书模板VIP免费
2025-01-09 5 -
中国新能源及节能环保材料项目商业计划书VIP免费
2025-01-09 4 -
中国(陕西)xxxx新能源股份有限公司VIP免费
2025-01-09 4 -
阳光新能源公司创业计划书VIP免费
2025-01-09 4 -
新型纯电动安全汽车项目商业计划书VIP免费
2025-01-09 5
作者：李琳琳
分类：高等教育资料
价格：15积分
属性：4 页
大小：91.5KB
格式：DOC
时间：2024-10-12
