一种二值图像连通区域标记的简单快速算法_葛春平

一种二值图像连通区域标记的简单快速算法_葛春平价值工程0引言二值图像连通区域标记是从仅由表示背景的“0”像素和表示前景的“1”像素组成的图像中将相互邻接的(4邻域邻接和8邻域邻接)的连通区域用唯一的标记编号进行标记。这种操作是图像处理中的一个基本操作，可以用模式识别、OCR、图像标注、图像检索等方面。1传统标记算法传统标记的算法主要有以下几种：第一种方法是边缘检测和内部填充法。这种算法先对二值图像进行边缘检测然后对封闭的边缘内部进行标号填充，这种方法需要对图像进行两次处理，时间效率不高。而且在4邻域的情况下会把非常靠近的两个连通区域标记为相同的标号。第二种方法是跟综算法。对每个目标点标记一个与其坐标相关的标号，反复对图像进行扫描，将每个像素的标号更改为其———————————————————————基金项目：本文得到渭南师范学院科研项目、陕西省教育学会科研项目的资助。项目名称：大规模虚拟试验中网络互联问题研究、运用信息技术手段构建网络教研新模式。项目编号:11YKZ017、SJHYBKT2021004-03。作者简介：葛春平（1981-），男，甘肃庆阳人，渭南师范学院物理与电气工程学院，讲师，硕士，研究方向为软件工程。一种二值图像连通区域标记的简单快速算法ASimpleandRapidAlgorithmofConnectedComponentLabelingforBinaryImage葛春平GEChun-ping（渭南师范学院，渭南714000）（WeinanNormalUniversity，Weinan714000，China）摘要：针对传统二值图像连通区域标记需要对图像进行两次扫描的缺点，提出了一钟新的二值图像连通区域标记算法。算法借助创建一与图像等大的标记矩阵，通过深度优先搜索算法对图像进行一次扫描后，将标记编号记录在标记矩阵中。此算法不受连通区域的形状和面积影响，表现出了良好的鲁棒性。最后通过OpenCV对该算法进行了实现并与传统标记算法进行了时间性能比较。Abstract:Anewconnectedcomponentlabelingalgorithmwasproposedforimprovingoftraditionalalgorithmforitneedtwicescanningofimage.Algorithmneedamatrixwiththesamesizeofimage,thelabelrecordedinthematrixbyadepth-firstsearchontheimage.Thisalgorithmisnotaffectedbytheshapeandareaoftheconnectedcomponent.Finally,implementtheAlgorithmbyOpenCVandcompareitwiththetraditionalalgorithmintheaspectoftimeefficiency.关键词：二值图像连通区域标记；标记算法；矩阵Keywords:connectedcomponentlabelingforbinaryimage；labelingalgorithm；matrix中图分类号：TP31文献标识码：A文章编号：1006-4311（2021）28-0232-02y=fft(x);%对原始波形数据进行快速FOURIER变换subplot(2,1,2)；%频域坐标方框图semilogy([0:length(x)-1]/(length(x)*dt),abs(y))；%画出频域中FFT波形图xlabel('Frequency/HZ');%频域图的X轴坐标标识xlim([01/2/dt])；%频域轴只画出采样频率具有特定功能的M函数文件创建后，根据上一节介绍的方法生成COM组件。组件名和类名，都取名为fft,如图2所示。3.2创建VB工程并调用COM组件新建“标准EXE”工程，进入VB编程环境，在“工程”菜单中单击“引用”选项，在列表中选中“fft1.0TypeLibrary”，单击“确定”按钮。在VB工程引用后需按照以下步骤来调用Matlab文件：Dimftasfft.fft‘声明一个COM组件Setft=Newfft.fftCallft.ff_t‘调用一个COM组件软件运行界面如图3所示，从图3中可分析出地震信号的优势频率分布和特性；需要注意的是在使用软件进行地震信号分析时要先将地震事件格式转换成.txt格式。4结语主要介绍了通过COM组件技术实现Matlab与VB的混合编程，并通过数字地震波谱分析的实例说明了这种方法的可行性。对于数字地震波分析含有复杂算法的界面设计有举一反三的作用，VB的可视化界面与Matlab强大函数库有效结合，可以很容易的编写出数字地震波形分析应用软件，对地震分析人员在地震研究方面具有实用价值。参考文献：[1]宋建锁.滤波在地震分析中的应用[J].防灾技术高等专科学校学报,2021,8(1):75-79.[2]李敬.数字地震记录干挠波的排除[J].防灾技术高等专科学校学报,2021,3(1):32-35.[3]潘晓霞.Matlab与VB的接口编程及在测漏仪中的应用[J].机械设计与制造,2021,(2):67-69.[4]徐金明.MATLAB实用教程[M].北京:清化大学出版社，2021:462-470.·232·DOI:10.14018/表2算法效率分析图序连通区域个数时间(单位：毫秒)边缘检测填充法跟踪算法顺序标记法递归法本文算法123442484100.582.393.790.583.470.391.272.350.570.270.390.860.565.290.395.844.727.739.243.7表1标记矩阵00000000001000000001111003001111033300000003002220210002220210000220210550000040550000000550000000领域内的最我号。第三种是顺序标记法。对图像进行两次扫描，对未作标记的像素的标记从其领域获得。这种算法可能会在第一次扫描完时，同一领域中出现不同的标记编号，需要构造标记冲突表进行解决。第四种是递归法。逐个遍历像素点，碰到未被标记的前景像素点时对其进行标记，并递归处理其未被标记的邻接像素点。只到递归调用结束时即表示一个连通区域被标记结束。该方法实现简单，但是当图像上存在大面积的连通区域时算法将会是一个深度递归，即容易导致内存栈溢出。2本文算法2.1算法描述本文提出一种基于区域生长的广度优先标记算法。算法中我们需要定义一个和二值图像具有想同行列数的标记矩阵来存放我们的标记结果。首先将这个标记矩阵初始化为0。等算法结束时，标记矩阵中将存放由0到连通区域个数的整数。其中0表示对应行列处为图像的背景像素，其它值表示被标记的图像中的连通区域的编号。如表1所示的标记矩阵表示的标记矩阵表示对应的图像中有五个连通区域。根据该标记矩阵可以很容易的求出原图像中各个连通区域的面积，边界，重心等一些重要的图像特征参数。算法首先对图像进行逐像素扫描，扫描到某个像素时，首先判断是不是背景像素。如果是背景像素，只接跳过该像素处理下一个像素。如果是前景像素，先判断该像素是否已被标记过，判断标准就是对应位置的标记矩阵值。如果值为0则表示该位置未被标记。对于未被标记的像素则对其进行标记，标记完了需要判断该像素的邻接像素是否未被标记。如果未被标记，对其标记上相同的标记编号。然后判断邻接像素的邻接像素，只到没有邻接像素为止。从以上算法描述来看是一个递归的思想，通过编写一个处理像素的递归函数来实现以上算法是比较容易的。但是如果图像中的连通区域面积比较大时，算法处理将是一个深度递归。极其容易造成栈溢出。所以本文设计的算法借助一个队列将这种递归的思想转换为叠代的思想。每次扫描到一个未标记像素时将该像素入队列，然后对队头像素进行标记，再将其未标记的邻接像素也入队列并标记，最后删除队头像素，如此叠代循环只到队列为空时即表示一个连通区域已被标记完成。最后将标记标号加1再顺序扫描下一像素进行相同的操作只到扫描完所有的像素。2.2算法流程对上面提到的算法描述，可以按照下面的步骤加以实现：步骤1：设图像矩阵为I，创建一个与图像I相同行列数的标记矩阵M，将标记矩阵初始化为0。创建一标记变量count，表示将要进行标记的区域编号，将其初始化为1。步骤2：对图像按照从上到下，从左到右进行逐像素扫描。扫描到第m行n列像素点时，对该像素的点值I[m,n],(0或1)和标记矩阵中的第m行n列的值M[m,n](1到连通区域个数)进行步骤3中的几种情况处理。步骤3：对步骤2中取出的值分以下两种情况处理。如果I[m,n]已被标记过(判断依据为M[m,n]0)，或者I[m,n]为背景像素(判断依据为I[m,n]==0)，跳过后面步骤，返回步骤2取出下一像素处理。否则创建一存储行列坐标(m,n)的队列L，并将(m,n)插入队列L队尾。步骤4：循环取出L队头元素(x,y)，如果I[x,y]未被标记(即M[[x,y]0)，将I[x,y]标记为count(置M[x,y]=count)，判断[x,y]的所有邻域点[x1,y1]，如果I[x1,y1]未被标记(即M[x1,y1]0)，将I[x1,y1]插入队列L队尾，并将I[x1,y1]标记为count(置M[x1,y1]=count)。最后将队列L队头素出列。循环该步骤真到队列为空后将标记变量count加1。步骤5：返回步骤2处理下一像素点。2.3实验及结果分析将以上算法在OpenCV中实现后对以下四种不同复杂程度的256×256像素的二值图像进行处理，其处理结果如图1到图4所示。本文算法与传通算法的运行效率比较如表2所示。通过以上分析可以看出本文中的算法对任意复杂的连通区域都表现出一定的鲁棒性。同时也具有可观的时间效率。3总结本文提出了一种二值图像连通区域标记的新算法，能够通过对图像进行一次扫描将将其连通特征标记到标记矩阵中。通过等不同数目和复杂度的二值图像进行测试以及与传统算法进行比较，可以发现算法复杂度低，不受连通区域的特征和数量影响，相比比传统二值图像连通区域标记算法具有容易实现，时间效率和空间效率较高。参考文献：[1]RosenfeldA,PfaltzJL.Sequentialoperationsindigitalpictureprocessing.JournalofthACM,1966，13(4):480-385.[2]高红波，王卫星.一种二值图像连通区域标记的新算法.计算机应用.2021，27(11):2776-2777.[3]SAMETH.Connectedcomponentlabelingusingquadtrees[J].JoumaloftheACM,1981,28(3):487-501.[4]陈柏生.一种二值图像连通区域标记的新方法[J].计算机工程与应用,2021,42(25):50-51.[5]张树生.一种基于线的标号传播二值图像连通快速检测方法[J].计算机研究与发展,1994,31(10):51-54.[6]章德伟，蒲晓蓉，章毅.基于Max-tree的连通区域标记新算法[J].计算机应用研究,2021,23(8):168-169.·233·