閆　石，徐江濤，高志遠，王含宇（天津大學電子信息工程學院，天津300072）

?

基于地址-事件表示的高速二值連通域標記方法*

閆石，徐江濤*，高志遠，王含宇
（天津大學電子信息工程學院，天津300072）

摘要：為提高二值連通域標記的速度，將地址-事件表示AER（Address Event Representation）思想引入到二值圖像處理，提出了一種基于事件對等價標號的二值連通域標記方法。該算法無需多次遍歷圖像中的背景點和冗余目標點，首先將待標記的連通域以AER“事件對”的方式編碼保存，通過“事件對”的遍歷生成臨時標號和等價標記表；然后根據(jù)等價表修改臨時標號；完成標號映射后最終實現(xiàn)連通域標記。整個算法只處理極低冗余的事件信息，避免了對全圖像素的重復掃描與處理。實驗結(jié)果表明，圖像以AER“事件對”方式存儲，數(shù)據(jù)量僅為全幀圖像的10%～35%，有較高的壓縮比；且該算法速度快，可達到了傳統(tǒng)基于等價標號算法的1.5～8倍。

關(guān)鍵詞：二值圖像；連通域標記；地址-事件表達；事件對；等價標號

項目來源：國家自然科學基金（61274021，61234003）

連通域標記是二值圖像處理領域中最常見的運算之一，它可以將二值圖像中不同的目標區(qū)域標記區(qū)分開來，從而方便分別對各個目標的特征進行分析和提?。?］。二值連通域標記已被廣泛應用于圖像分割、圖像分析以及目標識別等領域［2-3］，因此其運行速度的提升對機器視覺應用的發(fā)展具有重要意義。

基于等價標號思想的連通域標記算法是一種最普遍的二值圖像連通域標記算法［4］，根據(jù)實施細節(jié)的不同，其又可分為線標記法［5］、基于像素掃描的方法［6］和基于塊掃描［4，7］的方法，這些算法本質(zhì)上都是通過遍歷圖像，初步標記并確定等價標號，再根據(jù)等價標號對初步標記進行整合，從而獲得最終的標記。這些算法大都需要對圖像進行多次掃描，文獻［8］算法結(jié)合基于像素掃描的標記法和線標記法，提出了一種基于硬件加速的高速二值圖像連通域標記方法，盡管大大提高了標記速度，但依然需要兩次掃描。文獻［9］提出的方法并不直接標記圖像中的連通區(qū)域，而是提取出每個連通區(qū)域的特定信息，這避免了多次掃描。每次掃描過程都需要對大量的背景點以及冗余目標點進行遍歷、判定和賦值。這些無效的操作很大程度地增加了算法運行時間，特別是對于高分別率、大尺度的二值圖像，算法程序運行的冗余現(xiàn)象更為明顯。

為提高二值圖像連通域標記的效率，本文提出了一種基于地址-事件表達（AER）的二值連通域標記方法。AER是一種仿生的圖像采集、處理模式［10］，最早出現(xiàn)于圖像傳感器領域［11］。AER圖像傳感器模仿生物視覺系統(tǒng)的工作機理，各個像素之間獨立工作，僅對光強發(fā)生顯著變化的像素點觸發(fā)事件響應，輸出對應像素的地址和事件屬性，從而具有低冗余、低延時、高實時性等優(yōu)點［12-14］。本文提出的算法將目標區(qū)域前后邊緣響應產(chǎn)生的“事件對”作為待處理的原始數(shù)據(jù)，僅對有限個“事件對”進行遍歷；通過判斷“事件對”間的相交性確定連通性和標號的等價關(guān)系，最后將每個“事件對”的標記值映射回其地址間所夾的像素點，即可獲得二值圖像連通域的精確劃分。本算法只處理事件信息，而無需對原圖中背景點和冗余目標點進行遍歷，對于高分辨率、背景點數(shù)量龐大的二值圖像，該算法具有較高的處理效率。

1　 AER感知方式

AER感知方式以仿生神經(jīng)學為原型。AER圖像傳感器的工作機理為：傳感器像素陣列中各個像素單元相互獨立工作，當某個單元檢測到光強變化超過設定閾值后，觸發(fā)特定事件響應，其中ON事件代表光強增大，而OFF事件則代表光強減弱。若同時有多個單元觸發(fā)響應，就需要經(jīng)過行、列仲裁控制依次輸出事件脈沖，并觸發(fā)外圍電路編碼事件地址與屬性。AER圖像傳感器只輸出發(fā)生事件的地址（x，y）和屬性（ON/OFF），而光強變化不明顯的背景和目標內(nèi)部點則不會觸發(fā)事件響應，沒有信息輸出。這從源頭上消除了冗余信息的產(chǎn)生。

將AER感知模式應用于二值圖像的處理中，對于一幀圖像而言，基于AER的處理方式不關(guān)心其背景信息以及冗余的目標點，而將每個目標的前后邊緣點觸發(fā)響應產(chǎn)生的OFF/ON事件作為原始數(shù)據(jù)，并記錄事件坐標和屬性，稱之為AER編碼。AER數(shù)據(jù)可以由AER圖像傳感器直接獲取，也可以通過對原始圖像的二值矩陣平移求差獲得：通過平移模擬前景目標的移動，響應獲得對應的OFF/ON事件，按照由上向下、由左向右的順序?qū)⑼恍械刂飞系南噜彯愋允录鳛橐粋€“事件對”予以保存記錄。由于只保存事件點的地址屬性，因此AER碼可在一定程度上壓縮數(shù)據(jù)量，二值圖像AER編碼的數(shù)據(jù)壓縮比為：

式中，n為響應事件點的個數(shù)。w和h分別為圖像的寬度和高度。對于目標物數(shù)量較少的二值圖像而言，由于n值較小，AER編碼有較高的數(shù)據(jù)壓縮比。另外，現(xiàn)有的二值圖像編碼都需要解碼譯成二值矩陣之后才能進行諸如連通域標記等圖像處理。而AER編碼無需解碼，即可直接應用本文算法進行圖像處理，這進一步提高了算法的速度。

2　連通域標記算法

2.1基于點掃描的等價標號連通域標記算法

傳統(tǒng)的基于等價標號的二值連通域標記主要分為以下步驟：

初步標記先對二值圖像按從上到下、從左到右的順序進行一次完整掃描，判斷所有像素點是否為前景點并對前景點進行初步標記，得到臨時標記矩陣。對于每一個前景像素點，只根據(jù)已標記像素點來確定自身的連通性，即掃描上、左2個像素的標記值即可。在初步標記過程中，往往會存在重復標記的情況，即在前面掃描過程中產(chǎn)生的不同標號的區(qū)域最終連通在一起，這時需要將這些等價標號對記錄下來。等價標記對存儲在一維數(shù)組Equl中，其中，數(shù)組的下標為臨時標記值，例如：Equl（i1）=i2，表示臨時標記i1、i2等價，即i1、i2標記的區(qū)域連通。為了便于連通域合并，等價表按照i2

等價表整理對等價表進行掃描整理，將所有等價的標號統(tǒng)一為其中的最小值，得到共同連通域標記。例如TEMP（i1）=i2，TEMP（i2）=i3，且有i3

修正初步標記。對臨時標記矩陣進行掃描，根據(jù)等價表將臨時連通域標記合并替換，得到最終的連通域標記。

2.2基于AER的連通域標記算法

對于二值圖像，AER的感知方式可以進行精確、低冗余的數(shù)據(jù)處理。假設原始圖像經(jīng)過一個單位的橫向平移，此時AER像素陣列所探測到目標物的前后邊緣必然響應生成相應的ON/OFF事件集。圖1（a）為一幅普通的二值圖像；圖1（b）為由AER像素陣列模型響應輸出的ON/OFF事件，其中灰色大圓點為OFF事件，黑色小圓點為ON事件；圖1（c）為理想的連通域標記結(jié)果。由于目標物與背景相對光強關(guān)系的統(tǒng)一性，因此待標記目標物應處于由前后邊緣產(chǎn)生的OFF-ON或ON-OFF事件集之間，通過這些事件集就可以精確地定位相應的各個目標。為此我們提出基于AER信息的快速二值連通域標記算法，該算法僅標記ON/OFF事件點，并通過判定事件對之間的相交性，創(chuàng)建等價標號數(shù)組，確保同一連通域被相同標號值的事件對所夾，最終根據(jù)事件對的映射域填充所有前景點的標號值，完成二值圖像的連通域標記。本文算法可以提高系統(tǒng)的實時性且實現(xiàn)簡單，適用于大分辨率，大尺度二值圖像的連通域標記處理。

圖1　理論分析

3　算法實現(xiàn)與分析

基于上述的理論分析，算法的具體流程設計如下：

（1）將二值圖像轉(zhuǎn)化為OFF/ON事件信息，按從左至右，從上至下的順序分別壓制成事件數(shù)組OFFSet/ ONSet。各個OFF/ON事件依次包含3個元素：①行地址x、②列地址y以及③連通域標號值value。OFFSet （n）和ONSet（n）為一組OFF/ON事件對。

（2）對OFFSet/ONSet數(shù)組進行首次遍歷，為所有的事件對賦予臨時標記并記錄等價標記。

①一個事件對（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事件的標號值。若這兩個標號值不同，則說明該事件對連接了不同的連通域，首先將這兩個標號之中較小的值賦予該事件對，然后將上一行在此事件對列地址間所有事件的標號值設為等價標記，記入等價標號數(shù)組Equl，例如確定臨時標號n，p，q等價，則Equl（n）= Equl（p）=Equl（q）=min（n，p，q）。根據(jù)每個事件對的具體情況更新等價標號數(shù)組Equl，直至所有OFF?Set/ONSet遍歷完畢。

（3）合并等價標號。根據(jù)Equl數(shù)組的等價性修訂中的臨時標號，例如：a、b為自然數(shù)，若Equl（a）= b，則將OFFSet/ONSet中所有臨時標號為a的值替換為b。

（4）原始圖像標記。根據(jù)事件對的標號值確定原始圖像中對應區(qū)域的所有前景像素點的連通域標記，以此完成原始二值圖像的連通域標記處理。

圖2（a）顯示了本文提出的二值連通域標記的算法流程，圖2（b）顯示了本文算法一個實例的具體分析。在行地址x=2下首次出現(xiàn)了3個事件對，依次賦予連通域標號1，2，3；第3行的3個事件對都只與上一行的一個事件對相交，根據(jù)連通性賦予與之相同臨時標記值；第4行的第二個事件對同時與上一行的兩個事件對相交，因此推出這兩個事件對具有連通性，即臨時標號2，3等價，二次遍歷時將標號3的事件全部替換為標號2；最終根據(jù)事件對的標號值和地址映射域完成對該圖所有像素點的連通域標記。

圖2　算法框圖和流程分析

4　實驗結(jié)果與分析

本文建立了AER視覺傳感器行為級模型用于生成事件信息，并選取了近百幅不同分辨率的二值圖像用以測試本文提出連通域標記算法的性能，圖3中顯示了其中部分的測試圖樣。本文算法基于MATLAB語言實現(xiàn)并在Core 2 Duo E4500的處理器，2 GB內(nèi)存的實驗平臺上進行仿真測試。通過100次執(zhí)行的平均運行時間估測算法的執(zhí)行效率，以此來與傳統(tǒng)基于像素掃描等價標號［6］、基于塊掃描［7］的二值連通域標記算法進行比較。仿真結(jié)果及對比如表1和圖4所示，可以看到，本文提出基于AER事件對的二值連通域標記方法無需多次遍歷原始圖像中的所有像素點，只處理極低冗余的事件信息，所以當圖像中所含目標區(qū)域較少時，即使是原圖分辨率很大，實際需要處理的事件信息依舊很少，算法的運行效率也就更高，可以達到傳統(tǒng)算法的4倍～8倍；然而隨著圖像中連通域數(shù)目的增加，事件的響應率提高，AER感知方式抗冗余的特性也會隨之減弱，本文算法的運行速度也會有所下降。綜合實驗數(shù)據(jù)表明，基于AER編碼事件對信息數(shù)據(jù)量僅為全幀圖像的10%～35%，且運行速度較快，是傳統(tǒng)算法的1.5倍～8倍。

圖3　部分測試二值化圖樣

表1　與傳統(tǒng)算法的速度對比

圖4　各算法運行速度對比

表2為AER編碼與幾種現(xiàn)有二值圖像壓縮編碼的對比，本文算法將二值圖像轉(zhuǎn)化為AER事件的方式編碼，編碼壓縮比可以達到5～15，與傳統(tǒng)的跳白塊（Write Block Skipping，WBS）［15］、自適應跳塊（Adaptive Block Skipping，ABS）［16］，方塊編碼［17］等編碼方式相同數(shù)量級。而且，AER編碼可以直接進行連通域標記的流程判定而無需解碼，這是其相對于現(xiàn)有編碼方式的最大優(yōu)勢。

表2　AER事件編碼與幾種現(xiàn)有編碼的數(shù)據(jù)壓縮比對比

5　總結(jié)與展望

本文在傳統(tǒng)基于等價標號的二值連通域標記算法基礎上，引入地址-事件表達的思想，提出了一種新的基于AER事件對標記的二值連通域標記算法。待標記二值圖像中的所有前景目標以AER事件對的形式保存。標記過程中只對事件對進行處理，從而避免了對大量無效背景點和冗余目標點的遍歷。實驗結(jié)果表明，通過與傳統(tǒng)算法的比較，對于高分辨率、前景目標物較少的二值圖像，本文提出算法具有較高的執(zhí)行效率。而且，AER事件編碼擁有較好的圖像壓縮能力、低冗余以及無需解碼等優(yōu)勢特征，可以移植于二值圖像處理的其他領域，具有廣闊的應用前景。

參考文獻：

［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］汪飛躍，姚志明，許勝強，等.基于柔性力敏傳感器的左右腳動態(tài)識別方法［J］.傳感技術(shù)學報，2015，28（7）：964-971.

［3］袁澤，丁建麗，王嬌，等.基于國產(chǎn)GF_1遙感影像的面向?qū)ο髽蛄禾崛》椒ㄑ芯浚跩］.傳感技術(shù)學報，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］于璐，姚素英，徐江濤.一種基于地址-事件表達的實時視覺傳感器實現(xiàn)方法［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視覺系統(tǒng)，數(shù)字圖像處理與分析，機器視覺等，yanshi_tju@126.com；

徐江濤（1979-），副教授，博士生導師，研究方向為CMOS圖像傳感器芯片與相機系統(tǒng)、數(shù)字圖像處理電路等，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