基于地址-事件表示的高速二值连通域标记方法*

闫　石，徐江涛，高志远，王含宇（天津大学电子信息工程学院，天津300072）



基于地址-事件表示的高速二值连通域标记方法*

闫石，徐江涛*，高志远，王含宇
（天津大学电子信息工程学院，天津300072）

摘要：为提高二值连通域标记的速度，将地址-事件表示AER（Address Event Representation）思想引入到二值图像处理，提出了一种基于事件对等价标号的二值连通域标记方法。该算法无需多次遍历图像中的背景点和冗余目标点，首先将待标记的连通域以AER“事件对”的方式编码保存，通过“事件对”的遍历生成临时标号和等价标记表；然后根据等价表修改临时标号；完成标号映射后最终实现连通域标记。整个算法只处理极低冗余的事件信息，避免了对全图像素的重复扫描与处理。实验结果表明，图像以AER“事件对”方式存储，数据量仅为全帧图像的10%～35%，有较高的压缩比；且该算法速度快，可达到了传统基于等价标号算法的1.5～8倍。

关键词：二值图像；连通域标记；地址-事件表达；事件对；等价标号

项目来源：国家自然科学基金（61274021，61234003）

连通域标记是二值图像处理领域中最常见的运算之一，它可以将二值图像中不同的目标区域标记区分开来，从而方便分别对各个目标的特征进行分析和提取［1］。二值连通域标记已被广泛应用于图像分割、图像分析以及目标识别等领域［2-3］，因此其运行速度的提升对机器视觉应用的发展具有重要意义。

基于等价标号思想的连通域标记算法是一种最普遍的二值图像连通域标记算法［4］，根据实施细节的不同，其又可分为线标记法［5］、基于像素扫描的方法［6］和基于块扫描［4，7］的方法，这些算法本质上都是通过遍历图像，初步标记并确定等价标号，再根据等价标号对初步标记进行整合，从而获得最终的标记。这些算法大都需要对图像进行多次扫描，文献［8］算法结合基于像素扫描的标记法和线标记法，提出了一种基于硬件加速的高速二值图像连通域标记方法，尽管大大提高了标记速度，但依然需要两次扫描。文献［9］提出的方法并不直接标记图像中的连通区域，而是提取出每个连通区域的特定信息，这避免了多次扫描。每次扫描过程都需要对大量的背景点以及冗余目标点进行遍历、判定和赋值。这些无效的操作很大程度地增加了算法运行时间，特别是对于高分别率、大尺度的二值图像，算法程序运行的冗余现象更为明显。

为提高二值图像连通域标记的效率，本文提出了一种基于地址-事件表达（AER）的二值连通域标记方法。AER是一种仿生的图像采集、处理模式［10］，最早出现于图像传感器领域［11］。AER图像传感器模仿生物视觉系统的工作机理，各个像素之间独立工作，仅对光强发生显著变化的像素点触发事件响应，输出对应像素的地址和事件属性，从而具有低冗余、低延时、高实时性等优点［12-14］。本文提出的算法将目标区域前后边缘响应产生的“事件对”作为待处理的原始数据，仅对有限个“事件对”进行遍历；通过判断“事件对”间的相交性确定连通性和标号的等价关系，最后将每个“事件对”的标记值映射回其地址间所夹的像素点，即可获得二值图像连通域的精确划分。本算法只处理事件信息，而无需对原图中背景点和冗余目标点进行遍历，对于高分辨率、背景点数量庞大的二值图像，该算法具有较高的处理效率。

1　 AER感知方式

AER感知方式以仿生神经学为原型。AER图像传感器的工作机理为：传感器像素阵列中各个像素单元相互独立工作，当某个单元检测到光强变化超过设定阈值后，触发特定事件响应，其中ON事件代表光强增大，而OFF事件则代表光强减弱。若同时有多个单元触发响应，就需要经过行、列仲裁控制依次输出事件脉冲，并触发外围电路编码事件地址与属性。AER图像传感器只输出发生事件的地址（x，y）和属性（ON/OFF），而光强变化不明显的背景和目标内部点则不会触发事件响应，没有信息输出。这从源头上消除了冗余信息的产生。

将AER感知模式应用于二值图像的处理中，对于一帧图像而言，基于AER的处理方式不关心其背景信息以及冗余的目标点，而将每个目标的前后边缘点触发响应产生的OFF/ON事件作为原始数据，并记录事件坐标和属性，称之为AER编码。AER数据可以由AER图像传感器直接获取，也可以通过对原始图像的二值矩阵平移求差获得：通过平移模拟前景目标的移动，响应获得对应的OFF/ON事件，按照由上向下、由左向右的顺序将同一行地址上的相邻异性事件作为一个“事件对”予以保存记录。由于只保存事件点的地址属性，因此AER码可在一定程度上压缩数据量，二值图像AER编码的数据压缩比为：

式中，n为响应事件点的个数。w和h分别为图像的宽度和高度。对于目标物数量较少的二值图像而言，由于n值较小，AER编码有较高的数据压缩比。另外，现有的二值图像编码都需要解码译成二值矩阵之后才能进行诸如连通域标记等图像处理。而AER编码无需解码，即可直接应用本文算法进行图像处理，这进一步提高了算法的速度。

2　连通域标记算法

2.1基于点扫描的等价标号连通域标记算法

传统的基于等价标号的二值连通域标记主要分为以下步骤：

初步标记先对二值图像按从上到下、从左到右的顺序进行一次完整扫描，判断所有像素点是否为前景点并对前景点进行初步标记，得到临时标记矩阵。对于每一个前景像素点，只根据已标记像素点来确定自身的连通性，即扫描上、左2个像素的标记值即可。在初步标记过程中，往往会存在重复标记的情况，即在前面扫描过程中产生的不同标号的区域最终连通在一起，这时需要将这些等价标号对记录下来。等价标记对存储在一维数组Equl中，其中，数组的下标为临时标记值，例如：Equl（i1）=i2，表示临时标记i1、i2等价，即i1、i2标记的区域连通。为了便于连通域合并，等价表按照i2

等价表整理对等价表进行扫描整理，将所有等价的标号统一为其中的最小值，得到共同连通域标记。例如TEMP（i1）=i2，TEMP（i2）=i3，且有i3

修正初步标记。对临时标记矩阵进行扫描，根据等价表将临时连通域标记合并替换，得到最终的连通域标记。

2.2基于AER的连通域标记算法

对于二值图像，AER的感知方式可以进行精确、低冗余的数据处理。假设原始图像经过一个单位的横向平移，此时AER像素阵列所探测到目标物的前后边缘必然响应生成相应的ON/OFF事件集。图1（a）为一幅普通的二值图像；图1（b）为由AER像素阵列模型响应输出的ON/OFF事件，其中灰色大圆点为OFF事件，黑色小圆点为ON事件；图1（c）为理想的连通域标记结果。由于目标物与背景相对光强关系的统一性，因此待标记目标物应处于由前后边缘产生的OFF-ON或ON-OFF事件集之间，通过这些事件集就可以精确地定位相应的各个目标。为此我们提出基于AER信息的快速二值连通域标记算法，该算法仅标记ON/OFF事件点，并通过判定事件对之间的相交性，创建等价标号数组，确保同一连通域被相同标号值的事件对所夹，最终根据事件对的映射域填充所有前景点的标号值，完成二值图像的连通域标记。本文算法可以提高系统的实时性且实现简单，适用于大分辨率，大尺度二值图像的连通域标记处理。

图1　理论分析

3　算法实现与分析

基于上述的理论分析，算法的具体流程设计如下：

（1）将二值图像转化为OFF/ON事件信息，按从左至右，从上至下的顺序分别压制成事件数组OFFSet/ ONSet。各个OFF/ON事件依次包含3个元素：①行地址x、②列地址y以及③连通域标号值value。OFFSet （n）和ONSet（n）为一组OFF/ON事件对。

（2）对OFFSet/ONSet数组进行首次遍历，为所有的事件对赋予临时标记并记录等价标记。

①一个事件对（OFFSet（1）/ONSet（1）），直接赋予临时标号值i=1；

②对于第n（n≥2）个事件对（OFFSet（n）/ONSet （n）），首先判断当前事件对的上一行是否存在已标记的事件对，若不存在则说明上方无连通性，直接赋予新临时标号值i=i+1；若存在则说明上方可能存在连通性，顺序选取上一地址行所有事件的列地址组成判定向量，分别与OFF/ON事件的列地址（OFFSet（n，y）/ONSet（n，y））相比较，若无相交情况则说明不属于同一连通域，对（OFFSet（n）/ONSet （n））赋予新临时标号值i=i+1；

③若存在相交情况，则判定该事件对与上方事件对相连通，属于同一连通域，对OFFSet（n，value）赋予上一行中列地址≥OFFSet（n，y）且最接近的ON事件的标号值；对ONSet（n，value）赋予上一行中列地址≤ONSet（n，y）且最接近的OFF事件的标号值。若这两个标号值不同，则说明该事件对连接了不同的连通域，首先将这两个标号之中较小的值赋予该事件对，然后将上一行在此事件对列地址间所有事件的标号值设为等价标记，记入等价标号数组Equl，例如确定临时标号n，p，q等价，则Equl（n）= Equl（p）=Equl（q）=min（n，p，q）。根据每个事件对的具体情况更新等价标号数组Equl，直至所有OFF⁃Set/ONSet遍历完毕。

（3）合并等价标号。根据Equl数组的等价性修订中的临时标号，例如：a、b为自然数，若Equl（a）= b，则将OFFSet/ONSet中所有临时标号为a的值替换为b。

（4）原始图像标记。根据事件对的标号值确定原始图像中对应区域的所有前景像素点的连通域标记，以此完成原始二值图像的连通域标记处理。

图2（a）显示了本文提出的二值连通域标记的算法流程，图2（b）显示了本文算法一个实例的具体分析。在行地址x=2下首次出现了3个事件对，依次赋予连通域标号1，2，3；第3行的3个事件对都只与上一行的一个事件对相交，根据连通性赋予与之相同临时标记值；第4行的第二个事件对同时与上一行的两个事件对相交，因此推出这两个事件对具有连通性，即临时标号2，3等价，二次遍历时将标号3的事件全部替换为标号2；最终根据事件对的标号值和地址映射域完成对该图所有像素点的连通域标记。

图2　算法框图和流程分析

4　实验结果与分析

本文建立了AER视觉传感器行为级模型用于生成事件信息，并选取了近百幅不同分辨率的二值图像用以测试本文提出连通域标记算法的性能，图3中显示了其中部分的测试图样。本文算法基于MATLAB语言实现并在Core 2 Duo E4500的处理器，2 GB内存的实验平台上进行仿真测试。通过100次执行的平均运行时间估测算法的执行效率，以此来与传统基于像素扫描等价标号［6］、基于块扫描［7］的二值连通域标记算法进行比较。仿真结果及对比如表1和图4所示，可以看到，本文提出基于AER事件对的二值连通域标记方法无需多次遍历原始图像中的所有像素点，只处理极低冗余的事件信息，所以当图像中所含目标区域较少时，即使是原图分辨率很大，实际需要处理的事件信息依旧很少，算法的运行效率也就更高，可以达到传统算法的4倍～8倍；然而随着图像中连通域数目的增加，事件的响应率提高，AER感知方式抗冗余的特性也会随之减弱，本文算法的运行速度也会有所下降。综合实验数据表明，基于AER编码事件对信息数据量仅为全帧图像的10%～35%，且运行速度较快，是传统算法的1.5倍～8倍。

图3　部分测试二值化图样

表1　与传统算法的速度对比

图4　各算法运行速度对比

表2为AER编码与几种现有二值图像压缩编码的对比，本文算法将二值图像转化为AER事件的方式编码，编码压缩比可以达到5～15，与传统的跳白块（Write Block Skipping，WBS）［15］、自适应跳块（Adaptive Block Skipping，ABS）［16］，方块编码［17］等编码方式相同数量级。而且，AER编码可以直接进行连通域标记的流程判定而无需解码，这是其相对于现有编码方式的最大优势。

表2　AER事件编码与几种现有编码的数据压缩比对比

5　总结与展望

本文在传统基于等价标号的二值连通域标记算法基础上，引入地址-事件表达的思想，提出了一种新的基于AER事件对标记的二值连通域标记算法。待标记二值图像中的所有前景目标以AER事件对的形式保存。标记过程中只对事件对进行处理，从而避免了对大量无效背景点和冗余目标点的遍历。实验结果表明，通过与传统算法的比较，对于高分辨率、前景目标物较少的二值图像，本文提出算法具有较高的执行效率。而且，AER事件编码拥有较好的图像压缩能力、低冗余以及无需解码等优势特征，可以移植于二值图像处理的其他领域，具有广阔的应用前景。

参考文献：

［1］He Lifeng，Chao Yuyan. A Very Fast Algorithm for Simultaneous⁃ly Performing Connected-Component Labeling and Euler Number Computing［J］. IEEE Transactions on Image Processing，2015，24 （9）：2725-2735.

［2］汪飞跃，姚志明，许胜强，等.基于柔性力敏传感器的左右脚动态识别方法［J］.传感技术学报，2015，28（7）：964-971.

［3］袁泽，丁建丽，王娇，等.基于国产GF_1遥感影像的面向对象桥梁提取方法研究［J］.传感技术学报，2015，28（5）：690-696.

［4］He Lifeng，Zhao Xiao，Chao Yuyan，et al. Configuration-transitionbased Connected-Component Labeling［J］. IEEE Transactions on Image Processing，2014，23（2）：943-951.

［5］王洪涛，罗长洲，王渝，等. New Algorithm for Binary Connectedcomponent Labeling Based on Run-length Encoding And Unionfind Sets［J］.北京理工大学学报：英文版，2010，19（1）：71-75.

［6］He Lifeng，Chao Yuyan，Susuki Kenji. An Efficient First- scan Method for Label-equivalence-Based Labeling Algorithms［J］. Pat⁃tern Recognition，2010，31（1）：28-35.

［7］Santiago D J C，Ren T I，Cavalcanti，et al. Fast Block-based Algo⁃rithms for Connected Components Labeling. IEEE International Conference on Acoustics，Speech，and Signal Processing［C］//Van⁃couver，2013：2084-2088.

［8］赵菲，张路，张志勇，等.基于硬件加速的实时二值图像连通域标记算法［J］.电子与信息学报，2011，33（5）：1069-1075.

［9］Bailey D G，Johnston C T. Single Pass Connected Components Analysis［C］//Proceedings of Image and Vision Computing，Hamil⁃ton，New Zealand，2007：282-287.

［10］Zamarreno R C，Linares B A，Serrano G T，et al. Multicasting Mesh AER：A Scalable Assembly Approach for Reconfigurable Neuromorphic Structured AER Systems［J］. IEEE Transactions on application to Conv Nets. Biomedical Circuits and Systems，2013，7（1）：82-102.

［11］Zamarreno R C，Kulkarni R，Silva M J，et al. A 1.5 ns OFF/ON Switching- time Voltage- mode LVDS Driver/Receiver Pair for Asynchronous AER Bit- serial Chip Grid Links with Up to 40 Times Event-rate Dependent Power Wavings［J］. IEEE Transac⁃tions on Biomedical Circuits and Systems，2013，7（5）：722-731.

［12］Boahen K A. Point-to-point Connectivity Between Neuromorphic Chips Using Address-events［J］. IEEE Transactions on Circuits System II，2000，47（5）：416-434.

［13］Serrano G T，Linares B B. A 128×128 1.5% Contrast Sensitivity 0.9% FPN 3 μs Latency 4 mW Asynchronous Frame-free Dynam⁃ icVision Sensor Using Transimpedance Preamplifiers［J］. IEEE Journal of Solid-state Circuits，2013，48（3）：827-838.

［14］于璐，姚素英，徐江涛.一种基于地址-事件表达的实时视觉传感器实现方法［J］.光学学报，2013（1）：251-257.

［15］Horlander F J. Incremental Scanning for Facsimile［J］. IBM Tech. Disclosure Bull，1972，14（11）：3311-3313.

［16］Liu Yong，Yin Lixin，Zhao Yang. New Adaptive Block Skipping Codingof Binary Image［J］. Computer Engineering，2009，35（13）：219-221.

［17］Gonzalez R C. Digital Image Processing［M］. Third Edition，USA NJ：Prentice Hall，2007：334-345.

闫石（1991-），硕士研究生，研究方向为AER视觉系统，数字图像处理与分析，机器视觉等，yanshi_tju@126.com；

徐江涛（1979-），副教授，博士生导师，研究方向为CMOS图像传感器芯片与相机系统、数字图像处理电路等，xuji⁃angtao@tju.edu.cn。

A Fast Address-Event Representation Based Algorithm for Binary Image Connected-Component Labeling*

YAN Shi，XU Jiangtao*，GAO Zhiyuan，WANG Hanyu
（School of Electronic and Information Engineering，Tianjin University，Tianjin 300072，China）

Abstract：To achieve high processing speed，address-event representation（AER）is introduced to binary image pro⁃cessing. A label-equivalence connected-component labeling algorithm based on AER encoding and“event-pair”matching is proposed in this paper. The binary images are coded in“event-pair”represented by address and event. The“event-pair”array is scanned and label-equivalences are recorded. Then the labels are modified according to the label-equivalences. This algorithm only requires the low-redundant events information rather than the whole pix⁃els in the image. The experimental results show that AER coding could help to compress images into 10%～35% da⁃ta volume from original ones，and the proposed algorithm has a 1.5～8 times higher speed than traditional labelequivalence labelingalgorithms.

Key words：binary image；connected components labeling；address event representation（AER）；event-pair；labelequivalence

doi：EEACC：723010.3969/j.issn.1004-1699.2016.03.010

收稿日期：2015-11-03修改日期：2015-12-02

中图分类号：TN911.73

文献标识码：A

文章编号：1004-1699（2016）03-0362-06