第23卷第l 期 计算机应用与软件
Vol.23，No.l
2006年l 月 Computer Applications and Software Jan.2006
收稿日期：2004-04-0l 。左文明，博士生，主研领域：模式识别，图像处理，知识产权保护。
连通区域提取算法研究
左文明
（华南理工大学电子商务学院 广东广州5l0640）
摘 要 常见的连通区域提取算法是针对四连通区域的。本文分析了几个相关的算法，并指出其优劣点，提出了一个八连通区域提取算法。首先按照一定的标号规则扫描图像，得到一定数量的连通区域；然后针对同一区域内标号不一致的情况进行处理即得到最终处理结果。实验结果表明此方法能有效地提取八连通区域，故可用于连通区域复杂的图像如签名的分块处理中。关键词 八连通 连通区域 连通区域提取 签名
STUDY ON CONNECTED REGIONS EXTRACTION
Zuo Wenming
（School of Electronic Business ，South China Uniuersity of Technology ，fuangzhou fuangdong 510640，China ）
Abstr t Common algorithms for extracting connected regions are aimed at 4-connected regions.In this paper ，several related algorithms are analyzed and a new algorithm for 8-connected regions is proposed.First the image is scanned and connected regions are obtained in several labeling strategies.Then some processes are utilized to eliminate labels inconsistency within the same region.Experiment result shows that this algorithm is simple and effective when 8-connected regions are extracted.So it can be used in processing complex images such as signature ima-ges.
Keywords 8-connected Connected region Connected regions labeling Signature image
1 引 言
连通区域的提取是各种图像处理工作中重要的一个预处理过程。但常见算法是关于四连通区域的研究，其中文献［l ，2］中描述或采用的是区域标号法，但文献［l ］中描述的算法在实现时并不能达到预定的结果。
图l 连通区域示例一
文献［3］中提出了一个基于边缘点匹配的搜索算法，但在其算法原理描述中，明显出现一个漏洞，尽管在具体实现中被掩盖。由于其采用的仅是上下
边缘点的匹配，故在如图l 所示情况下就将出现错误。按照其算法描述，当搜
索至第二行第六个目标像素时，由于上下两行各六个像素形成区域的上下边缘点数相等，故此区域搜索完毕。实际上，右边五个像素与此区域为四连通，仍属于一个区域。如果对此算法改进，即可再考虑区域的左右边缘点匹配。当上下边缘点数及左右边缘点数匹配时即为提取了一个完整的四连通区域。
2 本文算法描述
本文研究的是八连通区域的提取，采用了标号处理法。设原始二值图像为f ，区域提取即标号处理后为g 。f （x ）=l 表示当前点为二值图像中黑色像素即为目标点，f （x ）=0表示当前为背景点。分以下步骤来进行：
步骤1 令起始标号值K 为l ；
步骤2 对图像从左到右、从上到下进行扫描，若为背景点
即f （x ）=0时则继续扫描；若遇到黑色像素即f （x ）=l 时按照以下规则来进行标号。
x ul x u x ur
x l
x
图2 像素关系示意图
（l ）若左上角像素为目标像素，则当前像素标号同左上角像素，即f （x ul ）=l 时，g （x ）=g （x ul ）=K ；
（2）若正上方像素为目标像素，则当前像素标号也同正上方像素，即f （x u ）=l ，
则g （x ）=g （x u ）=K ；（3）若上方为背景点左方为目标点时，当前像素标号值同左方像素，即f （x u ）=0且f （x l ）=l 时，g （x ）=g （x l ）=K ；
（4）如果正上方与左方像素都为目标像素时，则当前像素标号值同左方像素，即f （x u ）=l 且f （x l ）=l 时，g （x ）=g （x l ）=K ；
（5）如果左上方及左方像素为背景点，则分两种情况：（a ）右上角像素为背景点，当前像素标号值增加l ，即K =K +l ；（b ）否则当前像素标号值同右上角像素标号值，g （x ）
=g （x ur ）=K 。
步骤3 扫描完整幅图像后，仍会出现同一区域各部分标号不一致的情况。在同一区域标号变化的地方即相邻像素点不同处会有以下三种情况：
（l ）当前像素标号与左边像素标号不同；
98计算机应用与软件2OO6年
（2）当前像素标号与左下角像素标号不同；
（3）当前像素与正下方像素标号不同。
针对以上情况可采取再度扫描图像来对不一致的标号进行处理，从而将同一区域中不一致的标号进行更正。例如，假设当前像素与左下角像素标号不同，则可用左下角像素值来更正所有与当前标号值相同的像素。
3 实验结果及算法复杂度分析
3.1 实验
本文算法针对八连通区域进行处理，故适合含复杂区域的图像如签名的分块处理。图3为四个用作实验的图像，说明中列出了其尺寸及内含连通区域数目。
图3 实验图像（a）68X67（四）（b）68X67（十）
（c）l36X86（四）（d）l36X86（二十）
3.2 算法性能分析
设图像大小为!X!，本算法在步骤二的处理运算时间为"（!2），缓存需要量也为"（!2）。步骤三处理的时间与图像的复杂度有关，但缓存也是需要"（!2）。
本文算法用VisuaI C++6.O编程实现，在赛扬2.4GHz、256M内存，操作系统为Windows XP的Acer TraveIMate24O上运行，图3所示四个图像实验运算的时间如表l所示。
表1 实验图像处理时间
图像编号图像大小连通区域数处理时间（ms）
a68＊674 5.443
b68＊67lO 3.97
c l36＊86425.Ol7
d l36＊862O3O.323
分析以上实验结果表明，本算法不易受连通区域数目的影响，而连通区域面积的大小及规则程度将影响其处理时间。
4 总结
对于八连通区域的研究可见文献不多，文献［5］中主要描述了一个四连通区域提取算法，同时也将此算法扩充至八连通区域。算法简单，但由于其处理的目的是为设计一个连通区域提取的电路板，对内存的限制较多。故其在处理外围边缘点以及具体标号时很繁琐，如在判断当前点是否标号时，需要考虑56种情况。相比而言，本文算法实现简单，是一个提取八连通区域的有效算法。
参考文献
［l］李庆华、周琴芳，“工程图纸中文字符号的识别与提取”，《华中理工大学学报》，l997，VoI.25（l2），2O~22.
［2］权炜、郑南宁、贾新春，“复杂背景下的车辆牌照字符提取方法研究，”《信息与控制》，2OO2，VoI.3l（l），25~29.
［3］谢贵、彭嘉雄，“基于上下边缘点匹配的连通域搜索算法”，《华中科技大学学报》，2OO2，VoI.3O（4），66~68.
［4］田学东、李新福、郭宝兰，“印刷文档中表格字符的自动提取算法”，《河北大学学报》，2OOl，VoI.2l（l），9O~93.［5］Yutaka Ishiyama，Chihiro Funaoka，Fumio https://www.doczj.com/doc/312536366.html,beIing board based on boundary tracking.Pattern Recognition，l992.VoI.IV.Conference D：Architectures for Vision and Pattern Recognition，Proceedings，llth IA-
PR InternationaI Conference on.l992，～～～～～～～～～～～～～～～～～～～～～～～
34~38.
（上接第78页）
方式的优点是使用了硬件部件设计重用者所关注的重要基本信息（重要基本信息起到精确作用），便于理解，使用方便，正确率大大提高，而且通过粗略的分类能缩小搜索的空间，能满足硬件部件设计重用者的搜索要求。
5 专业搜索引擎总结
搜索引擎的发展趋势之一是建立垂直化专业化领域搜索引擎，调查表明：一半互联网用户认为目前搜索引擎死链接太多，四成以上的互联网用户认为目前的搜索引擎搜索不相关信息太多，而专业垂直搜索引擎可解决以上问题［6］。由于国外的GoogIe、AItaVista、Yahoo等，国内的Baidu、Sohu、Sina、Tom等都不能满足专业需要，因此专业引擎得到发展。如由美国医学信息学会主办的MedicaI Matrix搜索引擎是目前最重要的医学专业搜索引擎，还有国内金融类专业搜索引擎homeway和全球最大的环境问题搜索引擎webdirectory等等都属于此类。与计算机有关的软件组件搜索引擎有卡耐基梅隆大学的软件工程研究所开发的Agora以及IBM开发的aIphaBean［2，3］。特别是专业搜索引擎的精选集合Easy Searcher2收罗了超过3OO个专业搜索引擎［7］。只可惜上面的搜索引擎都不能满足硬件设计专业的搜索需求。所以有必要开发与研究针对硬件部件设计的搜索引擎。
6 结束语
由于硬件设计的重用还没有规模兴起，远比不上软件组件的重用规模。现在研究的搜索引擎还能满足需求，一旦向软件组件大规模重用时，该引擎将有可能负荷过重。为了应对这种情况，正在开发一个硬件资源库管理平台，并可以构建基于HCD-S信息描述体的硬件部件设计资源库，同时建立资源库注册中心。这样搜索引擎可以重点搜索资源库和注册中心，提高效率。
参考文献
［l］Shang-Hua Lin，Meng Chang Chen，Jan-Ming Ho and Yueh-Ming Huang，“ACIRD：InteIIigent Internet Document Organiztion and Re-
trievaI，”IEEE Transaction on KnowIedge and Data Engineering，VoI.
l4，No.3，pp.559~6l4，May/June2OO2.
［2］R.C.Seacord，S.A.Hissam，and K.C.waIInau，“Agora：A search En-gine for Software Component”，TechnicaI Report，CMU/SEL-98-
Oll，l998.
［3］AIphaBeans Homepage，http：）https://www.doczj.com/doc/312536366.html,/aIphabeans.［4］沈美娥、应时，“一种专用的软件组件搜索引擎”，《计算机工程与应用》，2OO5（2l）.
［5］俞君立、陈树年，文献分类学，武汉大学出版社，2OOl年lO月.
［6］薛宏熙、刘素洁，编译，MACH可编程逻辑器件及其开发工具，清华大学出版社，l998.
［7］焦玉英，信息检索进展，科学出版社，2OO3.
［8］Easy Searcher2.http：）www.easysearcher.
com.
连通区域提取算法研究
作者：左文明， Zuo Wenming
作者单位：华南理工大学电子商务学院,广东,广州,510640
刊名：
计算机应用与软件
英文刊名：COMPUTER APPLICATIONS AND SOFTWARE
年，卷(期)：2006,23(1)
被引用次数：14次
参考文献(5条)
1.李庆华;周琴芳工程图纸中文字符号的识别与提取 1997(12)
2.权炜;郑南宁;贾新春复杂背景下的车辆牌照字符提取方法研究[期刊论文]-信息与控制 2002(01)
3.谢贵;彭嘉雄基于上下边缘点匹配的连通域搜索算法[期刊论文]-华中科技大学学报(自然科学版) 2002(04)
4.田学东;李新福;郭宝兰印刷文档中表格字符的自动提取算法[期刊论文]-河北大学学报(自然科学版) 2001(01)
5.Yutaka Ishiyama;Chihiro Funaoka;Fumio Kubo Labeling board based on boundary tracking[外文会议] 1992
本文读者也读过(9条)
1.高红波.王卫星.GAO Hong-bo.WANG Wei-xing一种二值图像连通区域标记的新算法[期刊论文]-计算机应用
2007,27(11)
2.郭尚.苏鸿根.GUO Shang.SU Hong-gen基于像素的计算大量连通区域面积的快速算法[期刊论文]-计算机工程与设计2008,29(7)
3.陈柏生.CHEN Bai-sheng一种二值图像连通区域标记的新方法[期刊论文]-计算机工程与应用2006,42(25)
4.刘贤喜.李邦明.苏庆堂.刘中合.王玉亮.杨峰.LIU Xian-xi.LI Bang-ming.SU Qing-tang.LIU Zhong-he.WANG Yu-liang.YANG Feng一种新的二值图像连通区域准确标记算法[期刊论文]-计算机工程与应用2007,43(22)
5.沈乔楠.安雪晖.SHEN Qiao-nan.AN Xue-hui基于游程递归的连通区域标记算法[期刊论文]-计算机应用2010,30(6)
6.张云哲.赵海.宋纯贺.景巍.ZHANG Yun-zhe.ZHAO Hai.SONG Chun-he.JING Wei一种新的连通区域标记算法[期刊论文]-计算机应用研究2010,27(11)
7.章德伟.蒲晓蓉.章毅.ZHANG De-wei.PU Xiao-rong.ZHANG Yi基于Max-tree的连通区域标记新算法[期刊论文]-计算机应用研究2006,23(8)
8.蔡世界.于强.CAI Shi-jie.YU Qiang基于游程编码的连通区域标记算法优化及应用[期刊论文]-计算机应用
2008,28(12)
9.曹长虎.李亚非.CAO Chang-hu.LI Ya-fei一种二值图像连通区域标记快速算法[期刊论文]-科学技术与工程
2010,10(33)
引证文献(14条)
1.李仪芳.刘景琳基于连通域算法的区域测量[期刊论文]-科学技术与工程 2008(9)
2.黄战华.杨基春.朱猛.张尹馨嵌入式汽车轮胎规格号快速识别系统[期刊论文]-计算机工程 2010(2)
3.郭全民.张海先基于图像处理技术的混凝土路面裂缝检测方法[期刊论文]-传感器与微系统 2013(4)
4.谢祥徐基于链表的图像连通区域提取算法[期刊论文]-数字通信 2012(3)
5.汤一平.叶永杰.朱艺华.顾校凯智能全方位视觉传感器及其应用研究[期刊论文]-传感技术学报 2007(6)
6.汤一平.李雯基于动态图像理解的空调节能研究[期刊论文]-工业控制计算机 2007(1)
7.汤一平.陆海峰基于计算机视觉的电梯内防暴力智能视频监控[期刊论文]-浙江工业大学学报 2009(6)
8.汤一平.李雯基于全方位视觉的快速实时人体检测[期刊论文]-浙江工业大学学报 2008(4)
9.汤一平.李雯.俞立基于动态图像理解的节能空调控制器设计[期刊论文]-计算机测量与控制 2008(4)
10.汤一平.周宗思.贺武杰.楼勇攀基于全方位视觉传感器的智能安防装置的设计[期刊论文]-安防科技 2007(9)
11.马宝秋基于八邻域算法的多区域面积测量方法的应用[期刊论文]-石家庄职业技术学院学报 2013(2)
12.罗斌.戴玉名.翟素兰自适应CCV及等价关系聚类的视频摘要的生成[期刊论文]-重庆大学学报(自然科学版) 2010(2)
13.陈亚军.张二虎.牟永强基于空间模型及连通域分析的异纤维在线检测[期刊论文]-计算机工程与应用 2013(19)
14.岳书良磁致变温效应空调节能系统的探讨[期刊论文]-科学技术与工程 2010(13)
引用本文格式：左文明.Zuo Wenming连通区域提取算法研究[期刊论文]-计算机应用与软件 2006(1)