基于連通域標記的目標檢測算法設計與實現

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

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

（M，N分別為圖像行列數），適用于單目標圖像的實時識別與跟蹤。

關鍵詞： 連通域標記； FPGA； 目標檢測； 包圍盒

中圖分類號： TN911?34； TP391 文獻標識碼： 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

在精確制導圖像目標識別和跟蹤任務中，連通域標記算法用于從圖像中提取目標區域，計算目標區域的特征參數，是圖像處理系統中必不可少的環節。因此對于高幀頻圖像序列，研究如何優化底層二值圖像連通域標記算法的時間性能、存儲空間占用和可靠性，實現目標的檢測識別，具有較大的應用價值。

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

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

1 算法原理

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

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

（2） 緩存上一行的標記結果，遇到未標記的直線段時，判斷該直線與上一行已標記直線有無構成鄰域關系。如果有則使用上一行的標號，并更新相應的包圍盒信息；否則使用新的標號。

（3） 重復以上操作。當遇到U字形結構（即當行的1條直線段分別與上行的2條直線段構成鄰域關系），使用上行中左側直線段的標號作為該直線段的標號。

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

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

1.1 基于游程的圖像標記

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

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

（2） 當前行目標像素構成的直線段與上行目標像素構成鄰域關系，則該直線段使用上1行的標號，如圖1中標號1的直線段。

圖1 直線段位置關系圖

如上描述，該方法的好處在于：1條直線段對應1個標記信息，存儲量小，而且充分利用區域連通性的結構信息，減少了鄰域邏輯判斷。

1.2 等價關系處理

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

圖2 U型結構標記中間結果圖

1.3 同標號信息合并處理

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

圖3 同標號直線段分叉關系圖

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

2 連通域標記的硬件實現

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

圖4 標記電路結構圖

2.1 連通關系判斷模塊

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

圖5 連通關系判斷流程圖

2.2 等價關系合并模塊

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

3 實驗結果

3.1 資源消耗

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

表1 FPGA資源消耗列表

3.2 仿真結果與分析

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

圖6 二值化圖像實驗結果

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

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

4 結 論

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

參考文獻

[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] 徐利華，陳早生.二值圖像中的游程編碼區域標記[J].光電工程，2004，31（6）：63?65.

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

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

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

[6] 高紅波，王衛星.一種二值圖像連通區域標記的新算法[J].計算機應用，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] 馮海文，牛連強，劉曉明.高效的一遍掃描式連通區域標記算法[J].計算機工程與應用，2014，50（23）：31?35.