戴華東，胡謀法，盧煥章，王陽
（國防科學技術大學自動目標識別重點實驗室，湖南長沙410073）
摘要：在圖像目標識別和跟蹤任務中，連通域標記算法的設計優化主要體現在執行速度、存儲空間和邏輯判斷次數三個方面，因此提出並實現了一種基於一次逐像素掃描連通域標記的單目標檢測算法。算法結合包圍盒和單目標圖像檢測的特點，只需單行的圖像緩存空間，同時簡化複雜的等價標號替換操作，目標的判斷準則為目標圖像連通區域面積最大化，最終以包圍盒形式給出目標位置。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 onconnected?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 algo?rithm is only reflected in three aspects：executing speed，storage space and numbers of logical judgment. That’s why a single?target detection algorithm based on single per?pixel scanning connected?domain labeling is proposed and realized. The algorithmcombines the characteristics of bounding box and single?target image detection，which only requires a single?line image cachingspace，while simplifying the complex equivalent label replacement operation. The target judging criteria is the maximized area oftarget image connected region，and the target location is given in the form of bounding box finally. The FPGA simulation resultsshow that the method has less resource consumption rate and total clock cycle number of detecting an image is M×N×4（M andN express the number of image rows and columns respectively），which is suitable for real?time recognition and tracking for sin?gle 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.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（即為最左側標號）。
1.3 同標號信息合併處理
算法的標號傳遞都是基於上一行目標直線段，對於同一行同標號的直線段，倒U型結構會導致整個連通區域出現分叉現象，如圖3標號8的連通區域，分叉會導致在圖像的同一行中多條直線段使用同一個標號，所以在標記過程中需要實時合併該標號的包圍盒信息。由於同一行同標號直線段的條數、對應標號、中間間隔線段數等都不確定，所以需要對每一個標號對應的[col_max，col_min，row_max，row_min]參數建立1個更新表，在每1條直線段結尾處進行更新。對於256×256的圖像，1行可能出現的最多線段條數是86條（只做行緩存），需要的存儲空間是86×32 b，需要占用新的BRAM塊。
算法針對特定的單一目標，目標像素相對集中且連通，並且以包圍盒形式輸出目標位置是一種近似的結果。所以當只合併相鄰的同標號直線段時，即對於圖3情況，標號為9的直線段左右兩邊直線段（不相鄰）不做合併，而其上行或下行的直線段同標號且相鄰，則做合併操作，經測試該方法最終結果與建立更新表方法的結果一致。合併思路是先將2條直線段所屬的包圍盒信息合併，然後在第2條直線段結束時，將合併後的信息寫入第1條直線段的行緩衝位置（即覆蓋上一條直線段信息），節省了建立更新表所需的行緩存空間。
2 連通域標記的硬體實現
本文算法對圖像進行單次從左到右，從上到下的掃描，掃描的同時進行圖像標記。標記電路的輸入是圖像數據流（包括圖像時鐘、像素值、行列號、幀同步信號等），圖像數據經行緩存後進行連通關係判斷（本文採用四鄰域），當1條直線段標記完成時，進行標號選擇、行列坐標極值比較、標號合併等操作，最後將該直線段標記結果寫入行緩存，輸出目標包圍盒結果，標記檢測電路結構圖如圖4所示。
2.1 連通關係判斷模塊
連通關係判斷是整個電路最基本的模塊，對於圖像中任意一個像素點，連通關係判斷過程中存在4種位置關係：直線段起點、中點、結束點和直線段外。算法基於這4個位置關係和像素點左側、上方的鄰域關係完成連通關係判斷，流程圖如圖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× 4 f ，即能夠在圖像傳輸完成的同時輸出標記結果。算法實現FPGA的內部資源占用如表1所示，從表中可以看出，算法的硬體實現所占用FPGA 各項內部資源均不超過1%。
3.2 仿真結果與分析
本文算法對目標圖像有一定的針對性，要求目標單一且像素相對集中，所以選取如圖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 compo?nents analysis [J]. Proceedings of Image and Vision Com?puting，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 sin?gle pass connected components algorithm [C] // Proceedings ofthe 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?ef?ficient parallel single pass architecture for connected compo?nent labeling of streamed images [J]. Field?Programmable Tech?nology，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 onAcoustics，Speech and Signal. [S.l.]：IEEE，2013：2084?2088.
[10] WU K，OTOO E，SHOSHANI A. Optimizing two?pass con?nected ? component labeling algorithms [J]. Pattern Analysisand Applications，2005，12（2）：117?135.
[11] 馮海文，牛連強，劉曉明.高效的一遍掃描式連通區域標記算法[J].計算機工程與應用，2014，50（23）：31?35.
作者簡介：戴華東（1990—），男，湖南邵陽人，碩士研究生。主要研究方向為光學成像自動目標識別。
胡謀法（1979—），男，講師。主要研究方向為光學信息處理、目標識別等。
盧煥章（1963—），男，博士生導師。主要研究方向為目標識別、實時系統與專用集成電路等。
（國防科學技術大學自動目標識別重點實驗室，湖南長沙410073）
摘要：在圖像目標識別和跟蹤任務中，連通域標記算法的設計優化主要體現在執行速度、存儲空間和邏輯判斷次數三個方面，因此提出並實現了一種基於一次逐像素掃描連通域標記的單目標檢測算法。算法結合包圍盒和單目標圖像檢測的特點，只需單行的圖像緩存空間，同時簡化複雜的等價標號替換操作，目標的判斷準則為目標圖像連通區域面積最大化，最終以包圍盒形式給出目標位置。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 onconnected?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 algo?rithm is only reflected in three aspects：executing speed，storage space and numbers of logical judgment. That’s why a single?target detection algorithm based on single per?pixel scanning connected?domain labeling is proposed and realized. The algorithmcombines the characteristics of bounding box and single?target image detection，which only requires a single?line image cachingspace，while simplifying the complex equivalent label replacement operation. The target judging criteria is the maximized area oftarget image connected region，and the target location is given in the form of bounding box finally. The FPGA simulation resultsshow that the method has less resource consumption rate and total clock cycle number of detecting an image is M×N×4（M andN express the number of image rows and columns respectively），which is suitable for real?time recognition and tracking for sin?gle 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.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（即為最左側標號）。
1.3 同標號信息合併處理
算法的標號傳遞都是基於上一行目標直線段，對於同一行同標號的直線段，倒U型結構會導致整個連通區域出現分叉現象，如圖3標號8的連通區域，分叉會導致在圖像的同一行中多條直線段使用同一個標號，所以在標記過程中需要實時合併該標號的包圍盒信息。由於同一行同標號直線段的條數、對應標號、中間間隔線段數等都不確定，所以需要對每一個標號對應的[col_max，col_min，row_max，row_min]參數建立1個更新表，在每1條直線段結尾處進行更新。對於256×256的圖像，1行可能出現的最多線段條數是86條（只做行緩存），需要的存儲空間是86×32 b，需要占用新的BRAM塊。
算法針對特定的單一目標，目標像素相對集中且連通，並且以包圍盒形式輸出目標位置是一種近似的結果。所以當只合併相鄰的同標號直線段時，即對於圖3情況，標號為9的直線段左右兩邊直線段（不相鄰）不做合併，而其上行或下行的直線段同標號且相鄰，則做合併操作，經測試該方法最終結果與建立更新表方法的結果一致。合併思路是先將2條直線段所屬的包圍盒信息合併，然後在第2條直線段結束時，將合併後的信息寫入第1條直線段的行緩衝位置（即覆蓋上一條直線段信息），節省了建立更新表所需的行緩存空間。
2 連通域標記的硬體實現
本文算法對圖像進行單次從左到右，從上到下的掃描，掃描的同時進行圖像標記。標記電路的輸入是圖像數據流（包括圖像時鐘、像素值、行列號、幀同步信號等），圖像數據經行緩存後進行連通關係判斷（本文採用四鄰域），當1條直線段標記完成時，進行標號選擇、行列坐標極值比較、標號合併等操作，最後將該直線段標記結果寫入行緩存，輸出目標包圍盒結果，標記檢測電路結構圖如圖4所示。
2.1 連通關係判斷模塊
連通關係判斷是整個電路最基本的模塊，對於圖像中任意一個像素點，連通關係判斷過程中存在4種位置關係：直線段起點、中點、結束點和直線段外。算法基於這4個位置關係和像素點左側、上方的鄰域關係完成連通關係判斷，流程圖如圖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× 4 f ，即能夠在圖像傳輸完成的同時輸出標記結果。算法實現FPGA的內部資源占用如表1所示，從表中可以看出，算法的硬體實現所占用FPGA 各項內部資源均不超過1%。
3.2 仿真結果與分析
本文算法對目標圖像有一定的針對性，要求目標單一且像素相對集中，所以選取如圖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 compo?nents analysis [J]. Proceedings of Image and Vision Com?puting，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 sin?gle pass connected components algorithm [C] // Proceedings ofthe 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?ef?ficient parallel single pass architecture for connected compo?nent labeling of streamed images [J]. Field?Programmable Tech?nology，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 onAcoustics，Speech and Signal. [S.l.]：IEEE，2013：2084?2088.
[10] WU K，OTOO E，SHOSHANI A. Optimizing two?pass con?nected ? component labeling algorithms [J]. Pattern Analysisand Applications，2005，12（2）：117?135.
[11] 馮海文，牛連強，劉曉明.高效的一遍掃描式連通區域標記算法[J].計算機工程與應用，2014，50（23）：31?35.
作者簡介：戴華東（1990—），男，湖南邵陽人，碩士研究生。主要研究方向為光學成像自動目標識別。
胡謀法（1979—），男，講師。主要研究方向為光學信息處理、目標識別等。
盧煥章（1963—），男，博士生導師。主要研究方向為目標識別、實時系統與專用集成電路等。
收藏