一种二值图像连通区域标记的新方法
一种二值图像连通区域标记的新方法
陈柏生
(华侨大学计算机科学系,福建泉州362011)
E—mail:samchen@hqu.edu.ca
摘要论文提出了一种基于区域生长的二值图像连通区域标记的快速算法。与传统方法相比。该方法的特点是在一次
图像扫描中完成所有连通区域的标记,而且避免了大多数改进算法都必须处理的重复标记的问题:同时,该方法不受所标记的图形形状的影响,表现出良好的算法鲁棒性。最后分析了算法的计算复杂度,并与传统算法和两组改进算法进行了比较,试验结果表明了算法的高效率和鲁棒性。关键词
二值图像连通区域标记八邻域
一次扫描
文章编号1002—8331一(2006)25—0046—02
文献标识码A中图分类号TP391
ANewAlgorithmforBinaryConnectedComponentsLabeling
CHENBai—sheng
(Department
Abstract:A
new
paper.Comparedwith
ofComputerScience,Huaqiao
on
University,Quanzhou,Fujian
connected
components
that
algorithmis
of
36201
is
1)
in
this
algorithmbasedregion—growingfor
binarylabelingproposed
thetraditionalmethod,the
scan
characteristicoftheimage
and
the
alltheconnected
componentsare
most
labeled
methods
in
a
single
to
ofthe
inputbinaryproblem
labelingredundancy,whichimproved
havedeal
with,is
thewith
avoided.Otherwise,thecomputationofthealgorithmisindependentofthe
end
of
this
paper,the
computationof
its
complexity
of
the
algorithm
is
shapesofthe
connectedcomparativeshow
the
components.Atexperiments
discussed,and
results
traditionalmethodand
two
improved
methodsare
made.Theexperimental
proposedalgorithmhighefficiencyandrobustness.
scan
Keywords:binaryimage,connectedcomponentlabeling,eightneighborhood,single
1
引言
二值图像的连通区域标记是从仅由“0”像素(通常表示背
先对二值图像逐行扫描,每扫描出当前行的一条直线.就与上一行已检测出的直线段进行连通性检测。满足连通性要求的直线段将被合并。
本文方法受区域生长思想的启发。不对二值图像作逐行或逐列的次序扫描,而是一次性地标记整个连通区域,然后再标记下一个区域,直到所有的连通区域都被标记。
景点)和“1”像素(通常表示模式图形点)组成的一幅点阵图像
中,将相互邻接(4一邻域或8一邻域)的…1’值像素集合提取出
来。这种预处理操作在图像处理和模式识别的许多应用领域中被采用,如文本识别的图,文分割、工程图识别中的图形/标注符号分割等。其主要作用有二:一是实现待识别对象的粗分割:二是可将整幅画面分解为多个连通子图再进行后续处理.以减少系统的存储开销。
传统的连通区域标记方法【1】通常要对二值图像执行二次扫描。第一次扫描通过逐行逐列扫描像素.判断像素之间的邻域关系,对属于同一连通区域的像素赋予相同的连通标号。实现连通标识。这种逐行逐列的次序扫描的结果,通常会产生同一像素点被重复标记的现象,同一连通区域的不同子区域被赋予了不同的标记号。因此,需要执行第二次扫描消除重复性的标记,合并属于同一连通区域的而具有不同标记号的子区域。传统方法的效率非常低,尤其是在重复性标记发生率高的情况
2算法描述
传统的连通区域标记方法Ⅲ和目前多数改进方法㈤都需要
处理重复标记的问题。而这些方法的实现效率也很大程度取决于重复标记的严重程度。本文方法采用一种类似区域增长的思想,避免了重复标记的问题。该方法的基本思路是一次标记整个连通区域,然后再标记下一个区域,直到所有的连通区域都被标记。算法的基本操作如图1所示。
下,效率更低。在一些工作刚中,人们引入特殊的数据结构来组
织第一次扫描产生的结果,以实现重复标记点的快速查找:文献[4】将消除重复标记的操作融入到第一次扫描过程中,以达到一次性标记的目的。在文献【5】中,作者提出了一种基于线的标号传播的二值图像连通体检测方法,极大提高了连通区域标记的效率。该方法是将直线段作为连通体检测的基本处理单元.
图l连通区域标记(O一背景;1-模式图形;L一标记)
作者简介:陈柏生(1980一),男,助教,硕士研究生,主要研究方向为图像处理与模式识别。
46
2006.25计算机工程与应用
万方数据
首先。对输入的二值图像施行逐行扫描,找到一个未标记区域的第一点(该点的选择不影响算法的实现),标记该点;检查该点的八邻域点并标记满足连通性要求的.且尚未被标记的点,同时将新增的标记点记录下来作为“区域增长”的种子点。在后续的标记的过程中,不断地从记录种子点的数组中取出一个种子,施行上述的操作,如此循环,直到记录种子点的数组为空。一个连通区域标记结束。接着再标记下一个未标记区域,直到输入二值图像的所有连通区域都被标记。给定,表示输入的二值图像;U表示未标记的连通区域点集;茗是当前点;£是赋予连通区域的标记。算法的实现过程使用伪代码描述如下:
为了评价本文算法的实现效率。我们设计了与传统算法【1]和两种改进算法口,51的对比实验。其中,文[3】的改进算法利用特殊的数据结构优化扫描数据的组织;而文【5]则是采用扫描线的方法。我们用计算机自动生成800x600、1
l
024x1024、2
048x
024三幅测试图像。其相应的连通区域数分别是:50、100和
406、544
200.标记点数分别是:350347和1390362。为了测试
各种算法对标记不同形状的连通区域的鲁棒性,我们还手工绘制一幅包含U形和E形连通区域的,大小为512×512图像,连通区域20个。对应标记点数138叭1;其中U形、E形连通区域7个.对应标记点数81515。实验结果如表1所示。
1.foreachpoint*E,do
2.ifx∈Uthen
3.
STORE_SEEDPOINTS(x,I,);
4.L*--L+1:5.V_END・-END(V);
6.forifrom0
to(V_END-1)do
7.
SEEDPOINT=V[i】;
8.LABEL(SEEDPOINT,L);
9.CHECK_NEIGHBORHOOD(SEEDPOINT,,);
10.V_END・--END(y);
11.
i_--/+l:
上述伪代码段是本文算法的核心部分。算法在实现时,引入一个一维数组Ⅵ・】保存当前要标记的连通区域的种子点。上述伪代码段显示本文算法只要对输入二值图像,进行一次扫描就可以完成所有连通区域的标记。算法首先对,进行一次逐行扫描找到未标记区域的第一个像素点(行2.),将该点记录为ViOl(行3.)。同时将标记变量工相应地增1(行4.)。之后,便进入了当前连通区域标记的循环(行5.-行11.)。在此循环中,种子点不断地从y【・】取出(行7.)并赋予当前标记L(行8.);同时搜索当前种子点的八邻域。将满足连通性要求且尚未标记的像素点加入y[.】(行9.)。直到y[・】为空,即当前连通区域被标
记完毕(行5.),则搜索下一个未标记连通区域(行1.一行2.),
直到输入图像J中的所有连通区域都被标记。在八邻域搜索中的相关操作如下伪代码段所述:
1.CHECKNEIGHBORHOOD(SEEDPOINT,,)
2.
BEGIN
3.foreachi∈NEIGHBOR(SEEDPOINT)pointdo
4.ifi∈U山en
5.STORE_SEEDPOINTS(i,y);
6.
END
3算法复杂度分析和对比实验
传统的连通区域标记方法[1】和目前多数改进方法∞都需要
处理重复标记的问题。而这些方法的实现效率也很大程度上取决于重复标记的严重程度。尤其是在标记图形呈凹凸不齐形状的时候(例如U形、E形物体),重复标记的发生率更为突出,这导致这些算法的实现效率非常低。传统的方法【11在最好的情况,即在标记图形十分规则,标记重复不发生的情况下,算法复杂度是0(n):而在重复标记十分严重的情况下,算法复杂度将达
,
到O(n。),在一些改进算法中,文[5】的算法复杂度是0(n。),文f31的算法复杂度是o(n‘logn)。本文算法的计算开销大部分集中在两个操作:一是扫描二值图像搜索未标记区域的起点;二是对连通区域逐像素地八邻域搜索。在最坏的情况下,本文算法对输入图像的所有像素点都进行一次对应八邻域的搜索,其算法复杂度为O(n)。同时,这种基于八邻域搜索的区域增长方法不受标记区域形状的影响,具有很好的算法鲁棒性。
万
方数据表1
几组二值图像连通区域标记算法运行效率的试验比较
分析表1的对比实验数据,我们得出如下几个重要的实验(1)本文算法的实现效率十分明显。在目前已有的改进算(2)本文算法的鲁棒性很好,不受所标记图形形状的影响。(3)必须指出的是,在所标记图形形状比较规则的情况下,总之,在排除一些特殊的情况下,本文算法具有相对很高本文受区域增长思想的启发,提出了一种二值图像连通区M,HlavacV,Boyle
R著.艾海舟,武勃等译.图像处理、分析与
K.HoribaI,SugieN.Fastconnected—componentlabelingbased
sequential
localoperations
inthe
course
offorwardraster
sc粕s
bybackwardrasterscan[C].In:Proceedingsof15thInterna—
Conference
on
PattemRecognition,Barcelona,2000:434-437
中国图象图形学报,2003;8(2):198~202
计算机工程与应用2006.25
47
结论:
法中.基于扫描线的连通标记方法同的实现效率是较高的,而本文算法的效率提高了约30%~50%。
而传统算法[11和改进算法p,51对标记图形形状十分敏感,尤其是在标记图形呈明显的凹凸不齐形状时,算法的实现效率将变得非常低。因为在这种情况下。重复标记十分严重。
传统算法的效率会很高,超过本文算法。这是因为在这种情况下,重复标记较少发生,甚至不发生,传统算法不需要处理标记重复的问题:而本文算法仍要对所有的连通区域做逐像素的八邻域搜索。
的实现效率.而且具有很好的鲁棒性。
4结论
域的新方法,一次扫描标记输入图像中的所有连通区域,有效地避免了重复标记的问题,从而极大地提高了连通区域标记的实现效率。实验结果还表明本文方法具有很好的鲁棒性,算法的实现效率不受标记图形形状的影响。(收稿日期:2005年12月)
参考文献
1.Sonka机器视觉[M】.北京:人民邮电出版社,2003:159—160
2.江早。刘晋军。王冬等.一种可交互删改的二值图像快速连通体标识方法叨.东北大学学报(自然科学版),1998;19(3):251-254
3.Suzukion
followedtional4.张修军,郭霞,金心宇.带标记矫正的二值图象连通域像素标记算法叨.5.张树生.一种基于线的标号传播二值图像连通体快速检测方法【J].计’
算机研究与发展,1994;31(10):51—54
一种二值图像连通区域标记的新方法
作者:作者单位:刊名:英文刊名:年,卷(期):引用次数:
陈柏生, CHEN Bai-sheng
华侨大学计算机科学系,福建,泉州,362011计算机工程与应用
COMPUTER ENGINEERING AND APPLICATIONS2006,42(25)6次
参考文献(5条)
1.Milan Sonka.Vaclav Hlavac.Roger Boyle.艾海舟.武勃 图像处理、分析与机器视觉 2003
2.江早.刘晋军.王冬.刘积仁 一种可交互删改的二值图像快速连通体标识方法[期刊论文]-东北大学学报(自然科学版) 1998(3)
3.Suzuki K.Horiba I.Sugie N Fast connected-component labeling based on sequential local operationsin the course of forward raster scans followed by backward raster scan 2000
4.张修军.郭霞.金心宇 带标记矫正的二值图象连通域像素标记算法[期刊论文]-中国图象图形学报A辑 2003(2)5.张树生 一种基于线的标号传播二值图像连通体快速检测方法[期刊论文]-计算机研究与发展 1994(10)
相似文献(10条)
1.会议论文 梁炜.朱煜 基于线段表的二值图像连通区域检测 2007
二值图像连通区域标记是图像处理过程中的基础算法,是机器视觉和模式识别中提取目标及分析目标几何特征的常用方法。本文介绍了基于线段表的二值图像连通区域的标记算法,与传统的像素标记算法相比,该算法仅需对图像进行一次扫描,通过基于线段表的连通体检测方法,避免了像素点被重复扫描的现象,减少了图像的扫描次数,提高了算法的效率,同时巧妙的利用映射表归并等价的连通标记对,避免了归并连通关系需要大量内存和大量归并运算,提高了检测效率,实际运行效果良好,有较好的使用价值。
2.期刊论文 高红波.王卫星.GAO Hong-bo.WANG Wei-xing 一种二值图像连通区域标记的新算法 -计算机应用2007,27(11)
在线标记和区域增长的基础上提出了一种二值图像连通区域标记的快速算法.该算法综合了线标记法和区域增长法的优点,对图像进行一次扫描就可以标记所有连通区域,避免了重复标记问题;同时该算法不受标记的区域形状影响,具有良好的鲁棒性.提出对此算法的进一步优化策略,有效地降低了其搜索次数.最后与传统算法进行了比较,试验结果表明该算法是快速和高效的.
3.期刊论文 章德伟.蒲晓蓉.章毅.ZHANG De-wei.PU Xiao-rong.ZHANG Yi 基于Max-tree的连通区域标记新算法 -计算机应用研究2006,23(8)
采用灰度图像创建Max-tree的基本思想,提出一种新的二值图像连通区域标记算法.该算法主要采用8-邻域搜索及排序队列方式实现,通过一次扫描二值图像即可完成连通区域标记.提出一种新的8-邻域搜索策略,可以将邻域搜索次数由八次减少到平均四次以下,从而提高了系统效率.此外,还给出一种排序队列的快速实现方法,并将其应用到标记算法中.而且,该算法的运行时间仅与待标记图像的大小有关,与连通区数目和图像内容无关.该算法已应用于海藻图像识别,实验结果表明该算法是快速、高效的.
4.期刊论文 宋培华.高敦岳 边界跟踪与序贯算法在二值连通区域标记中的应用 -计算机科学2002,29(3)
1 引言在工业检测中图像处理应用大多都是图像识别,其输入图像为灰阶图像,然后进行边缘检测、图像分割、目标识别等一系列有效的图像处理.在最终的处理结果中一般都归结为对二值图像的处理,二值图像是只具有两个灰阶的图像,它是数字图像的一种简单形式.为了简单起见,图像处理的各种方法无非是采用各种算法将目标特征以二值图像的形式表现出来,再对二值图像这种简单的图像形式进行分析、判断得出结论[1,2].
5.期刊论文 李金.雷燕.胡文广.LI Jin.LEI Yan.HU Wen-guang 多运动目标探测标记及跟踪 -应用科技2009,36(6)
针对跟踪系统对多目标跟踪以及对实时性的要求,给出了一种基于中心点和面积特征匹配的多运动目标探测标记及跟踪方法.该方法利用对多运动目标检测后的二值图像进行了连通成分标记,提出了一种新的探测搜索标记法,赋予不同连通区域不同的数字来区分,通过四连通区域法来实现.由运动目标的4个顶点来确定中心点,通过面积及中心点距离从而进一步去匹配,最后根据标记结果在原图像中准确地框定了各运动目标,从而实现对运动目标的跟踪.采用上述算法,对车辆视频进行了跟踪,取得了较好的实验结果,跟踪实验结果验证了该方法具有很好的实时性.
6.学位论文 冯美军 基于加工表面纹理图像的刀具磨损监测 2007
本文通过对不同刀具磨损状态下加工表面纹理图像的视觉特征进行研究,以期达到对刀具磨损状态监测的目的. 分析了切削加工表面纹理的形成过程,以及加工表面纹理的形态及图像特征,并对影响工件表面纹理的因素进行了对比,阐明了基于加工表面纹理的刀具磨损监测方法的合理性和可行性. 以车削加工表面图像为基础,对图像灰度变换、图像增强、图像分割、二值图像的数学形态学运算和区域标记等预处理方法进行研究,完成了相应的算法. 从灰度共生矩阵中提取了二阶矩、对比度、相关值、熵四个统计量作为刀具磨损特征,对其所反映的加工表面纹理的状态进行了分析.提出了以基于像素空间投影法的累计面积、基于图像分割的连通区域数、基于二值图像的面积、基于图像数据的列之和的累计面积作为刀具磨损特征.
在实验基础上,以加工表面纹理图像为研究对象,使用基于图像分割的连通区域标记法、灰度共生矩阵法、像素空间投影法、基于二值图像的面积统计法、基于图像数据列求和法对加工表面纹理图像进行分析和处理.研究结果表明,随着刀具磨损的增加,二阶矩、累计面积、开运算以及基于边缘检测得到的连通区域数逐渐增大,相关值、熵值、基于腐蚀运算、开运算、sobel算子处理后得到的二值图像面积和基于图像列求和法得到的累计面积逐渐减小.因此,加工表面纹理的这些图像特征可以作为刀具磨损的评定标准,以实现刀具磨损状态监测,为刀具磨损监测提供了有效途径.
7.期刊论文 李青.郑南宁.游屈波.宋永红 计算机图形分离算法研究及实现 -计算机辅助设计与图形学学报2004,16(8)
计算机图形分离就是在由计算机生成的图形和自然图像合成的混合图像中将人工区域和自然区域分开.利用自适应自组织映射对彩色图像进行量化
,针对每种颜色组成一个色平面;然后将色平面转换成二值图像,对其中的连通区域进行快速标记,并提取出边缘.将标记后的区域和边缘映射到原图像,定义并计算每个区域的粗糙度和边缘对比度,最终完成各个连通区域的识别.实验结果表明,该方法具有一定的实用性.
8.期刊论文 甘志杰.刘云.GAN Zhi-jie.LIU Yun 基于单目视觉的实时身高测量算法 -青岛科技大学学报(自然科学版)2008,29(4)
提出了一种应用在驾驶员体检系统中的新的身高测量方法.首先利用OTSU自适应阈值分割法和快速连通区域标记算法来分别获取人头顶部投影的纵坐标和标志点的坐标;然后根据它们来初步计算身高;最后根据摄像机成像模型对计算结果进行修正以得到准确的测量结果.工程测试表明该方法测量准确、可以满足体检系统的身高测量精度要求;同时和驾驶员体检系统的其他模块有效整合在一起,降低了硬件和操作的复杂性.
9.期刊论文 牟少敏.孙永香.朱红梅.刘忠德 昆虫图像的自动计数方法的研究 -仪器仪表学报2003,24(z2)
田问害虫调查工作是一项非常繁重的体力劳动,如何解决这一问题是一项非常有意义的任务.本文利用数字图像处理技术中连通区域标记的方法对昆虫图像中的小昆虫实现了自动计数,并进行了深入的研究.
10.会议论文 牟少敏.孙永香.朱红梅.刘忠德 昆虫图像的自动计数方法的研究 2003
田间害虫调查工作是一项非常繁重的体力劳动,如何解决这一问题是一项非常有意义的任务.本文利用数字图像处理技术中连通区域标记的方法对昆虫图像中的小昆虫实现了自动计数,并进行了深入的研究.
引证文献(6条)
1.申为峰.李忠海 一种复杂环境下的前视机场跑道识别方法[期刊论文]-沈阳航空工业学院学报 2009(3)2.李芳.吴斌.张红英 基于快速8-连通域标记的视频字幕提取新算法[期刊论文]-电视技术 2009(2)3.袁远松.赵小敏.杨东勇 DataMatrix条码的畸变校正[期刊论文]-计算机系统应用 2008(10)
4.赵进辉.罗锡文.周志艳 基于颜色与形状特征的甘蔗病害图像分割方法[期刊论文]-农业机械学报 2008(9)5.苏峰.凌清.高梅国 红外小目标实时检测系统实现[期刊论文]-激光与红外 2008(08)6.高红波.王卫星 一种二值图像连通区域标记的新算法[期刊论文]-计算机应用 2007(11)
本文链接:http://d.g.wanfangdata.com.cn/Periodical_jsjgcyyy200625014.aspx
下载时间:2010年3月5日