戴華東+胡謀法+盧煥章+王陽

摘 要： 在圖像目標(biāo)識別和跟蹤任務(wù)中，連通域標(biāo)記算法的設(shè)計優(yōu)化主要體現(xiàn)在執(zhí)行速度、存儲空間和邏輯判斷次數(shù)三個方面，因此提出并實現(xiàn)了一種基于一次逐像素掃描連通域標(biāo)記的單目標(biāo)檢測算法。算法結(jié)合包圍盒和單目標(biāo)圖像檢測的特點，只需單行的圖像緩存空間，同時簡化復(fù)雜的等價標(biāo)號替換操作，目標(biāo)的判斷準(zhǔn)則為目標(biāo)圖像連通區(qū)域面積最大化，最終以包圍盒形式給出目標(biāo)位置。FPGA仿真結(jié)果表明：該方法資源占用率小，檢測一幅圖像的總時鐘周期數(shù)為M×N×4

（M，N分別為圖像行列數(shù)），適用于單目標(biāo)圖像的實時識別與跟蹤。

關(guān)鍵詞： 連通域標(biāo)記； FPGA； 目標(biāo)檢測； 包圍盒

中圖分類號： TN911?34； TP391 文獻標(biāo)識碼： A 文章編號： 1004?373X（2015）20?0071?04

Design and implementation of target detection algorithm based on

connected?domain labeling

DAI Huadong， HU Moufa， LU Huanzhang， WANG Yang

（Key Laboratory on Automatic Target Recognition， National University of Defense Technology， Changsha 410073， China）

Abstract： In the task of image target recognition and tracking， the design optimization of connected?domain labeling algorithm is only reflected in three aspects： executing speed， storage space and numbers of logical judgment. Thats why a single?target detection algorithm based on single per?pixel scanning connected?domain labeling is proposed and realized. The algorithm combines the characteristics of bounding box and single?target image detection， which only requires a single?line image caching space， while simplifying the complex equivalent label replacement operation. The target judging criteria is the maximized area of target image connected region， and the target location is given in the form of bounding box finally. The FPGA simulation results show that the method has less resource consumption rate and total clock cycle number of detecting an image is M×N×4 （M and N express the number of image rows and columns respectively）， which is suitable for real?time recognition and tracking for single target image.

Keywords： connected?domain labeling； FPGA； object detection； bounding box

在精確制導(dǎo)圖像目標(biāo)識別和跟蹤任務(wù)中，連通域標(biāo)記算法用于從圖像中提取目標(biāo)區(qū)域，計算目標(biāo)區(qū)域的特征參數(shù)，是圖像處理系統(tǒng)中必不可少的環(huán)節(jié)。因此對于高幀頻圖像序列，研究如何優(yōu)化底層二值圖像連通域標(biāo)記算法的時間性能、存儲空間占用和可靠性，實現(xiàn)目標(biāo)的檢測識別，具有較大的應(yīng)用價值。

目前常用的快速連通域標(biāo)記算法大致可以歸納為以下3類：第1類是基于像素的1次或2次連通域標(biāo)記算法[1]，其中2次掃描算法的第1次掃描獲得所有像素點的臨時標(biāo)號（中間會有標(biāo)號的等價處理操作），第2次掃描是替換已標(biāo)記圖像中等價的臨時標(biāo)號。1次與2次掃描算法的主要區(qū)別在于：1次掃描算法在等價標(biāo)號替換過程中直接計算連通區(qū)域的特征（如面積、矩、包圍盒、平均灰度值等）[1]。第2類是基于游程的1次或2次連通域標(biāo)記算法[2]，和基于像素方法的差異在于：以游程代替像素作為基本處理單元，可以簡化鄰域標(biāo)號關(guān)系的判斷邏輯，減少標(biāo)記結(jié)果所需的存儲空間。第3類基于區(qū)域生長的連通域標(biāo)記算法[3]采用種子點填充原理，可分為遞歸法和深度優(yōu)先法等，此類方法均會消耗大量的內(nèi)存空間，僅適用于小面積區(qū)域的標(biāo)記。

在以上基本的連通域標(biāo)記算法基礎(chǔ)上，文獻[4]結(jié)合基于像素和游程掃描算法的優(yōu)點，利用樹形拓撲結(jié)構(gòu)完成等價標(biāo)號替換，并輸出線段作為結(jié)果，適于硬件實現(xiàn)，有較高的性能和執(zhí)行效率。但對于大目標(biāo)圖像，圖像處理所需時間和存儲空間與直線段條數(shù)成正比關(guān)系，消耗資源較多。文獻[5]用分段的思想替代游程，以段為標(biāo)記單位，等價關(guān)系的計算量最小，時間性能遠遠優(yōu)于其他算法。但其數(shù)據(jù)存儲有像素點、直線段和線段塊三級結(jié)構(gòu)，對于多分叉情況會造成存儲資源的浪費。文獻[6]是結(jié)合游程和區(qū)域增長的改進算法，該算法不對二值圖像進行逐行逐列掃描，簡化了等價標(biāo)號處理，一次性標(biāo)記整個連通區(qū)域，但其受限于深度優(yōu)先搜索思想，需要反復(fù)搜索每個連通體的鄰域，降低了運行效率?？梢钥闯觯墨I[4?6]中的連通域標(biāo)記算法都是基于兩條思路：存儲空間的優(yōu)化[4?5，7?9]，節(jié)省了FPGA上有限的存儲資源；簡化了等價標(biāo)號的邏輯判斷[4，6，10]，同時避免了連通信息的損失[11]。本文算法采用基于游程的連通判斷方法[4]，結(jié)合包圍盒和單目標(biāo)圖像的特點，只需單行的圖像緩存空間，簡化了復(fù)雜的等價標(biāo)號替換操作。對于目標(biāo)像素比較集中且連通的二值圖像，進行一次逐像素掃描，以目標(biāo)連通區(qū)域包圍盒面積最大為判斷準(zhǔn)則，最終通過包圍盒的形式給出圖像中最大面積目標(biāo)區(qū)域坐標(biāo)位置，適用于單目標(biāo)圖像的實時識別與跟蹤處理。

1 算法原理

本文算法按光柵掃描順序（從上到下，從左到右），使用包圍盒表示目標(biāo)位置信息。算法的主要思路是：

（1） 在圖像第1行，當(dāng)遇到未標(biāo)記的第1個目標(biāo)點時，將該目標(biāo)點作為新直線段的起點，向右掃描直到目標(biāo)點構(gòu)成直線段結(jié)束，并標(biāo)上相應(yīng)的標(biāo)號，標(biāo)號存儲格式為info（x）={pix_value，line_start， col_min，col_max，row_min，label}（其中x是對應(yīng)的列號），并計算標(biāo)號區(qū)域包圍盒的面積aera。

（2） 緩存上一行的標(biāo)記結(jié)果，遇到未標(biāo)記的直線段時，判斷該直線與上一行已標(biāo)記直線有無構(gòu)成鄰域關(guān)系。如果有則使用上一行的標(biāo)號，并更新相應(yīng)的包圍盒信息；否則使用新的標(biāo)號。

（3） 重復(fù)以上操作。當(dāng)遇到U字形結(jié)構(gòu)（即當(dāng)行的1條直線段分別與上行的2條直線段構(gòu)成鄰域關(guān)系），使用上行中左側(cè)直線段的標(biāo)號作為該直線段的標(biāo)號。

（4） 每條直線段處理完成時，計算該直線對應(yīng)標(biāo)號的包圍盒面積aera_temp，并與之前緩存的最大面積aera_Max（初始值為0）比較，如果前者大則輸出aera_Max_out，其中包含當(dāng)條直線段對應(yīng)標(biāo)號的包圍盒、標(biāo)號和面積信息，否則不做任何處理。

（5） 繼續(xù)掃描圖像，直到掃描到最后1行的最后1列。最終處理結(jié)果以目標(biāo)所在連通域的包圍盒[col_max，col_min，row_max，row_min]形式給出。

1.1 基于游程的圖像標(biāo)記

基于游程的圖像標(biāo)記算法是用直線段替代像素點作為基本標(biāo)記處理單元，標(biāo)記過程中會有兩種情況：

（1） 當(dāng)前行目標(biāo)像素構(gòu)成的直線段與上行目標(biāo)像素沒有構(gòu)成鄰域關(guān)系（圖像第1行由于沒有上行也當(dāng)作這種情況），則在掃描到該線段最后1個像素點時給該直線段分配1個新的標(biāo)號，如圖1標(biāo)號3的直線段；

（2） 當(dāng)前行目標(biāo)像素構(gòu)成的直線段與上行目標(biāo)像素構(gòu)成鄰域關(guān)系，則該直線段使用上1行的標(biāo)號，如圖1中標(biāo)號1的直線段。

圖1 直線段位置關(guān)系圖

如上描述，該方法的好處在于：1條直線段對應(yīng)1個標(biāo)記信息，存儲量小，而且充分利用區(qū)域連通性的結(jié)構(gòu)信息，減少了鄰域邏輯判斷。

1.2 等價關(guān)系處理

在圖像標(biāo)記過程中，當(dāng)遇到U型結(jié)構(gòu)時，由于之前的目標(biāo)像素已標(biāo)記完成，且標(biāo)號更新只能通過下一次逐像素掃描更改，因此會出現(xiàn)等價的臨時標(biāo)號，如圖1中U型結(jié)構(gòu)所示，可以看出標(biāo)號1和標(biāo)號2是屬于同一連通區(qū)域，即構(gòu)成等價關(guān)系（本文圖1，圖2，圖3都是未做等價標(biāo)號替換前的標(biāo)號結(jié)果）。當(dāng)圖像比較復(fù)雜時，多個連通嵌套的U型結(jié)構(gòu)會導(dǎo)致復(fù)雜的等價標(biāo)號替換邏輯。本文算法采用包圍盒形式表示連通結(jié)構(gòu)信息，簡化了等價關(guān)系替換過程，思路如下：如圖2所示，在檢測到U型結(jié)構(gòu)時，比較上行標(biāo)號4和標(biāo)號5對應(yīng)的[col_max，col_min，row_max，row_min]大小，將其合并同時使用左側(cè)標(biāo)號（即標(biāo)號4），在當(dāng)行直線段結(jié)束時，上行鄰接的直線段信息即為合并后的標(biāo)號信息，因此完成了等價標(biāo)號包圍盒信息的合并。對于連接的多個U型結(jié)構(gòu)，均采用以上原則，最終上行合并后包圍盒信息標(biāo)號為4（即為最左側(cè)標(biāo)號）。

圖2 U型結(jié)構(gòu)標(biāo)記中間結(jié)果圖

1.3 同標(biāo)號信息合并處理

算法的標(biāo)號傳遞都是基于上一行目標(biāo)直線段，對于同一行同標(biāo)號的直線段，倒U型結(jié)構(gòu)會導(dǎo)致整個連通區(qū)域出現(xiàn)分叉現(xiàn)象，如圖3標(biāo)號8的連通區(qū)域，分叉會導(dǎo)致在圖像的同一行中多條直線段使用同一個標(biāo)號，所以在標(biāo)記過程中需要實時合并該標(biāo)號的包圍盒信息。由于同一行同標(biāo)號直線段的條數(shù)、對應(yīng)標(biāo)號、中間間隔線段數(shù)等都不確定，所以需要對每一個標(biāo)號對應(yīng)的[col_max，col_min，row_max，row_min]參數(shù)建立1個更新表，在每1條直線段結(jié)尾處進行更新。對于256×256的圖像，1行可能出現(xiàn)的最多線段條數(shù)是86條（只做行緩存），需要的存儲空間是86×32 b，需要占用新的BRAM塊。

圖3 同標(biāo)號直線段分叉關(guān)系圖

算法針對特定的單一目標(biāo)，目標(biāo)像素相對集中且連通，并且以包圍盒形式輸出目標(biāo)位置是一種近似的結(jié)果。所以當(dāng)只合并相鄰的同標(biāo)號直線段時，即對于圖3情況，標(biāo)號為9的直線段左右兩邊直線段（不相鄰）不做合并，而其上行或下行的直線段同標(biāo)號且相鄰，則做合并操作，經(jīng)測試該方法最終結(jié)果與建立更新表方法的結(jié)果一致。合并思路是先將2條直線段所屬的包圍盒信息合并，然后在第2條直線段結(jié)束時，將合并后的信息寫入第1條直線段的行緩沖位置（即覆蓋上一條直線段信息），節(jié)省了建立更新表所需的行緩存空間。

2 連通域標(biāo)記的硬件實現(xiàn)

本文算法對圖像進行單次從左到右，從上到下的掃描，掃描的同時進行圖像標(biāo)記。標(biāo)記電路的輸入是圖像數(shù)據(jù)流（包括圖像時鐘、像素值、行列號、幀同步信號等），圖像數(shù)據(jù)經(jīng)行緩存后進行連通關(guān)系判斷（本文采用四鄰域），當(dāng)1條直線段標(biāo)記完成時，進行標(biāo)號選擇、行列坐標(biāo)極值比較、標(biāo)號合并等操作，最后將該直線段標(biāo)記結(jié)果寫入行緩存，輸出目標(biāo)包圍盒結(jié)果，標(biāo)記檢測電路結(jié)構(gòu)圖如圖4所示。

圖4 標(biāo)記電路結(jié)構(gòu)圖

2.1 連通關(guān)系判斷模塊

連通關(guān)系判斷是整個電路最基本的模塊，對于圖像中任意一個像素點，連通關(guān)系判斷過程中存在4種位置關(guān)系：直線段起點、中點、結(jié)束點和直線段外。算法基于這4個位置關(guān)系和像素點左側(cè)、上方的鄰域關(guān)系完成連通關(guān)系判斷，流程圖如圖5所示。

圖5 連通關(guān)系判斷流程圖

2.2 等價關(guān)系合并模塊

如圖2所示，本文算法的所有等價關(guān)系都來自于圖中所示U型結(jié)構(gòu)，對于第2行目標(biāo)像素，當(dāng)光柵掃描到第2個標(biāo)號為4的像素時，從行緩存中讀出的上行直線段的信息是{1，line_start，col_min，col_max，row_min，4}；光柵掃描到第3個標(biāo)號為4的像素時，上行該像素值為0，直線段信息也為0；光柵掃描到第4個標(biāo)號為4的像素時，從行緩存中讀出的上行直線段的信息是{1，line_start， col_min，col_max，row_min，5}，在下一個時鐘比較標(biāo)號4和標(biāo)號5的col_min，col_max，row_min值，并將合并后的包圍盒參數(shù)寫入當(dāng)前上行直線段信息的臨時變量中。即在光柵掃描到第5個標(biāo)號為4的像素時，上行直線段信息已是合并后的包圍盒信息，且標(biāo)號修改為4。

3 實驗結(jié)果

3.1 資源消耗

本文設(shè)計在Xilinx公司的XC2V3000?4CG717硬件平臺上實現(xiàn)，對于大小為256×256的二值圖像，行緩存采用256×36的BRAM，存儲格式為：像素值（1位）、線段起始標(biāo)志（1位）、標(biāo)號（10位）、最大列號（8位）、最小列號（8位）、最小行號（8位）。經(jīng)測試，此電路對大小為256×256的二值圖像，圖像傳輸頻率為25 MHz時，由于在1個像素的處理中，需要對當(dāng)前像素的上一行對應(yīng)像素信息進行讀取和對當(dāng)前像素信息的寫入2次操作，為節(jié)省FPGA內(nèi)部存儲資源和避免存儲器乒乓操作，本算法采用4倍圖像傳輸時鐘頻率f （不高于30 MHz）對行緩存雙口BlockRAM進行讀寫，所以標(biāo)記一幅圖像所需時間t=M×N×[4f]，即能夠在圖像傳輸完成的同時輸出標(biāo)記結(jié)果。算法實現(xiàn)FPGA的內(nèi)部資源占用如表1所示，從表中可以看出，算法的硬件實現(xiàn)所占用FPGA各項內(nèi)部資源均不超過1%。

表1 FPGA資源消耗列表

3.2 仿真結(jié)果與分析

本文算法對目標(biāo)圖像有一定的針對性，要求目標(biāo)單一且像素相對集中，所以選取如圖6所示的6幅二值圖像進行測試，標(biāo)記檢測電路對二值圖像的處理結(jié)果如圖6所示，并根據(jù)最終輸出的包圍盒結(jié)果以方框的形式在已標(biāo)記目標(biāo)區(qū)域顯示出來。

圖6 二值化圖像實驗結(jié)果

測試結(jié)果表明，標(biāo)記電路能夠準(zhǔn)確定位目標(biāo)（如圖6目標(biāo)連通區(qū)域均在方框內(nèi)），并且在圖像傳輸完成的同時輸出標(biāo)記結(jié)果。對于100 Hz的幀頻（10 ms/幀），25 MHz時鐘速率下圖像傳輸時間（也是圖像處理時間）為[1（2.5×10]7）×256×256≈1.85 ms，完全滿足實時處理要求。

該算法在圖像目標(biāo)由粗到精的檢測識別硬件加速中應(yīng)用前景廣闊。例如，在粗識別過程通過包圍盒鎖定目標(biāo)圖像區(qū)域，為后期目標(biāo)精確識別減少所需處理的數(shù)據(jù)量，為滿足彈載平臺目標(biāo)識別算法的實時性奠定了基礎(chǔ)。同時，雖然算法的設(shè)計針對單一目標(biāo)，但對于已知的多個目標(biāo)，存儲多個連通區(qū)域面積較大的目標(biāo)信息，可實現(xiàn)多目標(biāo)的標(biāo)記檢測。另外在目標(biāo)標(biāo)記的同時可以計算目標(biāo)面積、平均灰度值等目標(biāo)特性參數(shù)，以獲得更高的處理效率，具有較大的實用價值。

4 結(jié) 論

本文針對單目標(biāo)光學(xué)成像敏感器圖像處理的實時性要求，提出了一種基于連通域標(biāo)記的單目標(biāo)檢測算法。算法結(jié)合包圍盒和單目標(biāo)圖像的特點，在圖像傳輸過程中完成整幅圖像的標(biāo)記檢測，并以包圍盒形式給出圖像中目標(biāo)的坐標(biāo)位置。算法以目標(biāo)連通區(qū)域包圍盒面積最大為判斷準(zhǔn)則，有一定的局限性。但其占用較少的存儲空間，簡化了復(fù)雜的等價標(biāo)號替換操作，在彈載平臺單一目標(biāo)圖像的實時識別與跟蹤處理方面具有實用價值。

參考文獻

[1] BAILEY D G， JOHNSTON C T. Single pass connected components analysis [J]. Proceedings of Image and Vision Computing， 2007， 23（19）： 282?287.

[2] 徐利華，陳早生.二值圖像中的游程編碼區(qū)域標(biāo)記[J].光電工程，2004，31（6）：63?65.

[3] 夏晶，孫繼銀.基于區(qū)域生長的前視紅外圖像分割方法[J].激光與紅外，2011，41（1）：107?111.

[4] 趙菲，張路，張志勇，等.基于硬件加速的實時二值圖像連通域標(biāo)記算法[J].電子與信息學(xué)報，2011，33（5）：1069?1075.

[5] 王靜.二值圖像連通域的分段標(biāo)記算法及實現(xiàn)[J].紅外與激光工程，2010（4）：761?765.

[6] 高紅波，王衛(wèi)星.一種二值圖像連通區(qū)域標(biāo)記的新算法[J].計算機應(yīng)用，2008，27（11）：2776?2777.

[7] JOHNSTON C T， BAILEY D G. FPGA implementation of a single pass connected components algorithm [C] // Proceedings of the 4th IEEE International Symposium on Electronic Design， Test and Applications. [S.l.]： IEEE， 2008： 228?231.

[8] KLAIBER M， ROCKSTROH L， WANG Z， et al. A memory?efficient parallel single pass architecture for connected component labeling of streamed images [J]. Field?Programmable Technology， 2012， 10（12）： 159?165.

[9] SANTIAGO D J C， REN T I， CAVALCANTI G D C， et al. Fast block?based algorithms for connected components labeling [C]// Proceedings of 2013 IEEE International Conference on Acoustics， Speech and Signal. [S.l.]： IEEE， 2013： 2084?2088.

[10] WU K， OTOO E， SHOSHANI A. Optimizing two?pass connected?component labeling algorithms [J]. Pattern Analysis and Applications， 2005， 12（2）： 117?135.

[11] 馮海文，牛連強，劉曉明.高效的一遍掃描式連通區(qū)域標(biāo)記算法[J].計算機工程與應(yīng)用，2014，50（23）：31?35.