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

1、一种二值图像连通区域标记的简单快速算法_葛春平价值工程0引言二值图像连通区域标记是从仅由表示背景的“0”像素和表示前景的“1”像素组成的图像中将相互邻接的(4邻域邻接和8邻域邻接)的连通区域用唯一的标记编号进行标记。这种操作是图像处理中的一个基本操作，可以用模式识别、OCR 、图像标注、图像检索等方面。1传统标记算法传统标记的算法主要有以下几种：第一种方法是边缘检测和内部填充法。这种算法先对二值图像进行边缘检测然后对封闭的边缘内部进行标号填充，这种方法需要对图像进行两次处理，时间效率不高。而且在4邻域的情况下会把非常靠近的两个连通区域标记为相同的标号。第二种方法是跟综算法。对每个目标点标记一个

2、与其坐标相关的标号，反复对图像进行扫描，将每个像素的标号更改为其基金项目：本文得到渭南师范学院科研项目、陕西省教育学会科研项目的资助。项目名称：大规模虚拟试验中网络互联问题研究、运用信息技术手段构建网络教研新模式。项目编号:11YKZ017、SJHYBKT2021004-03。作者简介：葛春平（1981-），男，甘肃庆阳人，渭南师范学院物理与电气工程学院，讲师，硕士，研究方向为软件工程。一种二值图像连通区域标记的简单快速算法A Simple and Rapid Algorithm of Connected Component Labeling for Binary Image葛春平GE Chu

3、n-ping（渭南师范学院，渭南714000）（Weinan Normal University ，Weinan 714000，China ）摘要：针对传统二值图像连通区域标记需要对图像进行两次扫描的缺点，提出了一钟新的二值图像连通区域标记算法。算法借助创建一与图像等大的标记矩阵，通过深度优先搜索算法对图像进行一次扫描后，将标记编号记录在标记矩阵中。此算法不受连通区域的形状和面积影响，表现出了良好的鲁棒性。最后通过OpenCV 对该算法进行了实现并与传统标记算法进行了时间性能比较。Abstract:A new connected component labeling algorithm was

4、 proposed for improving of traditional algorithm for it need twice scanning of image.Algorithm need a matrix with the same size of image,the label recorded in the matrix by a depth-first search on the image.This algorithm is not affected by the shape and area of the connected component.Finally,imple

5、ment the Algorithm by OpenCV and compare it with the traditional algorithm in the aspect of time efficiency.关键词：二值图像连通区域标记；标记算法；矩阵Key words:connected component labeling for binary image ；labeling algorithm ；matrix 中图分类号：TP31文献标识码：A 文章编号：1006-4311（2021）28-0232-02y=fft(x);%对原始波形数据进行快速FOURIER 变换subplot

6、(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 编程环境，在“工程”菜单中单击“引用”选项，在列表中选中“fft 1.0Type Library ”，单击“确定”按钮。在VB 工程引用后需按照以下

7、步骤来调用Matlab 文件：Dim ft as fft.fft 声明一个COM 组件Set ft=New fft.fft Call ft.ff_t 调用一个COM 组件软件运行界面如图3所示，从图3中可分析出地震信号的优势频率分布和特性；需要注意的是在使用软件进行地震信号分析时要先将地震事件格式转换成.txt 格式。4结语主要介绍了通过COM 组件技术实现Matlab 与VB 的混合编程，并通过数字地震波谱分析的实例说明了这种方法的可行性。对于数字地震波分析含有复杂算法的界面设计有举一反三的作用，VB 的可视化界面与Matlab 强大函数库有效结合，可以很容易的编写出数字地震波形分析应用软件

8、，对地震分析人员在地震研究方面具有实用价值。参考文献：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.232DOI:10.14018/ValueEngineering表2算法效率分析图序连通区域个数时间(单位：毫秒)边缘检测填充法跟踪算法顺序标记法递归法本文算法12

9、3442484100.582.393.790.583.470.391.272.350.570.270.390.860.565.290.395.844.727.739.243.7表1标记矩阵0000000000100000000111100300111103330000000300222021000222021000022021055000004055000000055000 0000 领域内的最我号。第三种是顺序标记法。对图像进行两次扫描，对未作标记的像素的标记从其领域获得。这种算法可能会在第一次扫描完时，同一领域中出现不同的标记编号，需要构造标记冲突表进行解决。第四种是递归法。逐个遍历像素点

10、，碰到未被标记的前景像素点时对其进行标记，并递归处理其未被标记的邻接像素点。只到递归调用结束时即表示一个连通区域被标记结束。该方法实现简单，但是当图像上存在大面积的连通区域时算法将会是一个深度递归，即容易导致内存栈溢出。2本文算法2.1算法描述本文提出一种基于区域生长的广度优先标记算法。算法中我们需要定义一个和二值图像具有想同行列数的标记矩阵来存放我们的标记结果。首先将这个标记矩阵初始化为0。等算法结束时，标记矩阵中将存放由0到连通区域个数的整数。其中0表示对应行列处为图像的背景像素，其它值表示被标记的图像中的连通区域的编号。如表1所示的标记矩阵表示的标记矩阵表示对应的图像中有五个连通区域。根

11、据该标记矩阵可以很容易的求出原图像中各个连通区域的面积，边界，重心等一些重要的图像特征参数。算法首先对图像进行逐像素扫描，扫描到某个像素时，首先判断是不是背景像素。如果是背景像素，只接跳过该像素处理下一个像素。如果是前景像素，先判断该像素是否已被标记过，判断标准就是对应位置的标记矩阵值。如果值为0则表示该位置未被标记。对于未被标记的像素则对其进行标记，标记完了需要判断该像素的邻接像素是否未被标记。如果未被标记，对其标记上相同的标记编号。然后判断邻接像素的邻接像素，只到没有邻接像素为止。从以上算法描述来看是一个递归的思想，通过编写一个处理像素的递归函数来实现以上算法是比较容易的。但是如果图像中的

12、连通区域面积比较大时，算法处理将是一个深度递归。极其容易造成栈溢出。所以本文设计的算法借助一个队列将这种递归的思想转换为叠代的思想。每次扫描到一个未标记像素时将该像素入队列，然后对队头像素进行标记，再将其未标记的邻接像素也入队列并标记，最后删除队头像素，如此叠代循环只到队列为空时即表示一个连通区域已被标记完成。最后将标记标号加1再顺序扫描下一像素进行相同的操作只到扫描完所有的像素。2.2算法流程对上面提到的算法描述，可以按照下面的步骤加以实现：步骤1：设图像矩阵为I ，创建一个与图像I 相同行列数的标记矩阵M ，将标记矩阵初始化为0。创建一标记变量count ，表示将要进行标记的区域编号，将其

13、初始化为1。步骤2：对图像按照从上到下，从左到右进行逐像素扫描。扫描到第m 行n 列像素点时，对该像素的点值Im,n,(0或1)和标记矩阵中的第m 行n 列的值Mm,n(1到连通区域个数)进行步骤3中的几种情况处理。步骤3：对步骤2中取出的值分以下两种情况处理。如果Im,n已被标记过(判断依据为Mm,n0)，或者Im,n为背景像素(判断依据为Im,n=0)，跳过后面步骤，返回步骤2取出下一像素处理。否则创建一存储行列坐标(m,n)的队列L ，并将(m,n)插入队列L 队尾。步骤4：循环取出L 队头元素(x,y)，如果Ix,y未被标记(即Mx,y0)，将Ix,y标记为count(置Mx,y=co

14、unt)，判断x,y的所有邻域点x1,y1，如果Ix1,y1未被标记(即M x1,y10)，将Ix1,y1插入队列L 队尾，并将Ix1,y1标记为count(置Mx1,y1=count)。最后将队列L 队头素出列。循环该步骤真到队列为空后将标记变量count 加1。步骤5：返回步骤2处理下一像素点。2.3实验及结果分析将以上算法在OpenCV 中实现后对以下四种不同复杂程度的256256像素的二值图像进行处理，其处理结果如图1到图4所示。本文算法与传通算法的运行效率比较如表2所示。通过以上分析可以看出本文中的算法对任意复杂的连通区域都表现出一定的鲁棒性。同时也具有可观的时间效率。3总结本文提出

15、了一种二值图像连通区域标记的新算法，能够通过对图像进行一次扫描将将其连通特征标记到标记矩阵中。通过等不同数目和复杂度的二值图像进行测试以及与传统算法进行比较，可以发现算法复杂度低，不受连通区域的特征和数量影响，相比比传统二值图像连通区域标记算法具有容易实现，时间效率和空间效率较高。参考文献：1Rosenfeld A,Pfaltz J L.Sequential operations in digitalpicture processing.Journal of th ACM,1966，13(4):480-385.2高红波，王卫星.一种二值图像连通区域标记的新算法.计算机应用.2021，27(11):2776-2777.3SAMETH.Connected compone