摘  要：針對高速圖像目標實時識別和跟蹤任務，需要利用系統(tǒng)中有限的硬件資源實現(xiàn)高速、準確的二值圖像連通域標記，提出了一種適合FPGA實現(xiàn)的二值圖像連通域標記快速算法。算法以快捷、有效的方式識別、并記錄區(qū)域間復雜的連通關系。與傳統(tǒng)的二值圖像標記算法相比，該算法具有運算簡單性、規(guī)則性和可擴展性的特點。利用FPGA實現(xiàn)該算法時，能夠準確有效的識別出圖像中復雜的連通關系，產生正確的標記結果。在100MHz工作時鐘下，處理384×288像素的紅外圖像能夠達到400幀／s以上的標記速度，足夠滿足實時目標識別系統(tǒng)的要求。
關鍵詞：二值圖像；連通域標記；并行處理；FPGA

Realization of a fast connected components labeling algorithm for binary image based on FPGA
He Ming   Wang Xinsai 
(Infrared & radio-frequency technology Center,
Air Defense Forces Command Academy, Zhengzhou, 450052, P.R. China)
Abstract: Based on high-speed image target recognition and tracking tasks, need to make use of limited hardware resources required to achieve high-speed system, accurate binary image component labeling. Proposed a suitable hardware algorithm to achieve rapid binary image component labeling. Algorithm for fast, effective way to identify and record the complex inter-regional connectivity. With the traditional binary image marker algorithm, the algorithm is a simple, rules and scalability characteristics.The simulation results show that the algorithm can accurately identify effective connectivity complex images, produced the correct labeling. The algorithm in hardware form, in the 100MHz clock work, 384 × 288-pixel infrared image processing to achieve more than 400 pictures of the markings s speed enough to meet the demands of real-time object recognition system.
Key words: binary image ,connected components labeling, parallel process,FPGA;

1 引言

　　在圖像自動目標識別和跟蹤過程中，首先對圖像目標進行閾值分割提取，得到的二值圖像通常包含多個連通區(qū)域，系統(tǒng)利用圖像目標的形狀特性對可疑高威脅的飛行目標進行自動識別。因此，需要對各連通區(qū)域塊進行分別檢測判斷，本文采用改進的適合FPGA實現(xiàn)的快速標記算法對各連通域進行檢測提取。

　　實現(xiàn)二值圖像連通體檢測通常采用的方法有下幾種[1] [2] [3]：區(qū)域生長法：首先對圖像進行逐行(列)掃描，每遇到一個未標記的“1”像素點，就分配其一個未使用過的標號，然后對其領域進行檢測，如有未標記過的“1”像素，則賦予相同的標號。反復進行這一操作．直到不存在應該傳播標號的“1”像素。然后繼續(xù)圖像行(列)掃描，如檢測判未標記的“1”像素則賦予其新的標號，并進行與以上相同的處理。整個圖像掃描結束，算法也就終止。這種方法可準確地檢測出各種類型的連通體．但處理時間也較長．因為要逐一檢測每一“1”像素的鄰域，且出現(xiàn)“1”像素的重復掃描。跟蹤算法：二值圖像中每個取值為“1”的像素 被標記一個與其坐標相關的標號，如由n，m串構成的數。熱后，掃描標記后的圖像，并將每十像素的標號改為其鄰域內的最小標號。反復執(zhí)行這個過程，直到不需要作標記更改為止。用這種方法處理小而凸的目標時，收斂速度較慢。

　　本文以適合FPGA實現(xiàn)為目的，提出一種具有計算規(guī)則性的快速二值圖像連通域標記算法。與傳統(tǒng)的二值圖像標記算法相比，該算法具有運算簡單性、規(guī)則性和可擴展性的特點，適合以FPGA實現(xiàn)。選用在100MHz工作時鐘下，處理384×288像素的紅外圖像能夠達到400幀／秒以上的標記速度，足夠滿足實時目標識別系統(tǒng)的要求。處理速度可以滿足大部分實時目標識別系統(tǒng)的要求。該算法同樣可以軟件編程方式應用于嵌入式DSP系統(tǒng)中。

2 算法描述

　　首先，在進行標記算法以前，利用硬件開辟獨立的圖像標記緩存和連通關系數組，接著在視頻流的采集傳輸過程中，以流水線的方式按照視頻傳輸順序對圖像進行逐行像素掃描，然后對每個像素的鄰域分別按照逆時針方向和水平方向進行連通性檢測和等價標記關系合并，檢測出的結果對標記等價數組和標記緩存進行更新，在一幀圖像采集傳輸結束后，得到圖像的初步標記結果以及初步標記之間的連通關系，最后，根據標號對連通關系數組從小到大的傳遞過程進行標號的歸并，利用歸并后的連通關系數組對圖像標記緩存中的標號進行替換，替換后的圖像為最終標記結果，并且連通域按照掃描順序被賦予唯一的連續(xù)自然數。

　
圖 1 標記算法流程

　　本文快速二值圖像連通域標記算法分為三個環(huán)節(jié)：

　　1.圖像初步標記：為每個像素賦予臨時標記，并且將臨時標記的等價關系記錄在等價表中

　　2.整理等價表：這一環(huán)節(jié)分為兩個步驟：

　　　?。?）將具有等價關系的臨時標記全部等價為其中的最小值；
　　　?。?）對連通區(qū)域以自然數順序重新編號，得到臨時標記與最終標記之間的等價關系。

　　3.圖像代換：對圖像進行逐像素代換，將臨時標記代換為最終標記．經過3個環(huán)節(jié)處理后，算法輸出標記后的圖像，圖像中連通域按照由上到下，由左至右出現(xiàn)的順序被標以連續(xù)的自然數。

2.1 圖像初始標記

　　標記算法符號約定：算法在逆時鐘方向檢測連通域時用w1，w2表示連續(xù)兩行的圖像數據，在緊接著的順時鐘方向連通域檢測時用k0，k表示連續(xù)兩行經過逆時鐘方向標記后的圖像數據。 其在工作窗口的位置在圖2、3中分別說明；對初始逆時針方向臨時標記用Z表示。Z初始標記值為1。

　　二值圖像連通域標記算法采用8連通判斷準則，通過縮小標記范圍剔除了圖像的邊界效應。為了簡化標記處理過程，使標記處理在硬件對一幀圖像傳輸操作時間內結束，標記處理利用中間數據緩存分為連續(xù)的兩種類型，其中類型1用于直接圖像序列傳輸，硬件發(fā)起圖像序列傳輸時，類型1采用逆時鐘順序連通域檢測，對2×3工作窗口中的二值像素進行初始標記。類型2對經過類型1初始標記過的圖像數據再進行水平方向的連通域檢測和歸并，然后把標記結果存入圖像存儲區(qū)。

圖像初始標記類型1：

　　步驟1讀取像素w1（2）、w1（1）、w1（0）、w0（2）、w0（1），以及相應的二值像素值。

　　步驟2讀取像素w0（1），按照逆時針方向依次與w1（0）、w1（1）、w1（2）、w0（2）比較，若w0（1）= w1（0），則k0（1）=k（2）；若w0（1）= w1（1），則k0（1）=k（1）；若w0（1）= w1（2），則k0（1）=k（0）；若w0（1）= w0（2），則k0（1）=k0（0）；否則（即w0（1）≠（w1（2）、w1（1）、w1（0）、w0（2）），k0（1）= Z；Z ++。

　　步驟3寫入等價關系表，以Z為地址將Z寫入等價關系數組。

　
圖 2 逆時鐘方向初始標記的工作窗

圖像初始標記類型2：

　　步驟1判斷經過逆時針方向標記后，如果w0（1）=  w0（2）=  1，而標記灰度k0（1）≠ k0（0），則進行下一步驟。

　　步驟2 假設k0（1）> k0（0），判斷l(xiāng)ab（k0（1））=k0（1）或者lab（k0（1））=k0（0），則lab（k0（1））=k0（0），否則對標記數組進行追蹤置換。跳轉至步驟3。

　　步驟3 假設k0（1）< k0（0），判斷l(xiāng)ab（k0（0））=k0（0）或者lab（k0（0））=k0（1），則lab（k0（0））=k0（1），否則對標記數組進行追蹤置換。

　　追蹤置換方法：步驟2的追蹤置換令t= lab（k0（0））；若lab（t）≠ t，則令t= lab（t），重復執(zhí)行，直lab（t）=t；步驟3的追蹤置換令t1= lab（k0（1）），對lab（k0（1））同樣執(zhí)行上述追蹤過程。

　
圖 3 水平方向初始標記的工作窗

2.2 等價表整理與圖像代換

　　首先，從等價表地址1開始掃描等價表，依次檢查其中各個臨時標記是否存在等價關系，若存在，則以標記值作為等價表地址的數據更新等價表。由于整理過程從等價表地址1開始，因此對整個等價表的掃描可以一遍結束。

　　圖像代換環(huán)節(jié)對臨時標記圖像中的每個像素進行代換，生成最終的標記后圖像。具體做法是：設圖像中坐標為（n，m）的像素的臨時標記值為S，則將lab（S）寫入圖像中（n，m）位置。代換后得到的圖像，其中的
　　連通區(qū)域按照由上到下，由左至右出現(xiàn)的順序被標以惟一的自然數。

2.3 算法特點分析

算法設計具有以下特點：

　　a．本文算法針對空中目標的識別和跟蹤進行標記，可以剔除對空中目標識別沒有影響的圖像的邊界，圖像中其他像素的標記工作均利用2.1中所述算法完成，因此運算具有規(guī)則性和同地址性，利用硬件實現(xiàn)時只需要定義兩個算法框架函數循環(huán)使用，節(jié)約了算法存儲器資源。

　　b．圖像初步標記過程中，在記錄標記等價信息的同時對等價表進行初步整理，這樣安排，一方面可以保證區(qū)域之間存在復雜連通關系時，等價表能夠保存已經檢測到的全部等價關系；另一方面，在以硬件電路實現(xiàn)標記算法時，圖像初步標記和等價表初步整理的過程可以并行執(zhí)行，等價表的初步整理，能夠簡化隨后的等價表整理操作，相當于壓縮了標記執(zhí)行的全過程。

　　c．在本算法中，采取兩方面措施減少臨時標記數量：其一，反復利用8鄰域范圍內生成的所有標記信息，在逆時針順序8鄰域范圍標記后借助圖像傳輸的順序進行水平方向的等價標記歸并，降低了需要賦予新標記值的概率；其二，在等價表整理時，歸并等價標記時按照等價表地址從小到大的的順序進行比較替換，使等價標記取較小值并且不會遺漏等價標記。其三，結合視頻數據流傳輸方式，采用乒乓存儲結構進行流水線處理，同時進行圖像標記和圖像標記替換。使圖像標記達到實時處理的效果。

3 算法的FPGA實現(xiàn)

　　FPGA(Field Programmable Gate Array)是一種大規(guī)模的可編程邏輯器件，可以用于各種數字邏輯系統(tǒng)，特別是實時處理方面，具有獨特的優(yōu)勢。在本算法的實時實現(xiàn)過程中，采用Altera公司的性價比高的Cyclone II EP2C8 FPGA[4]，該器件內部有8256個LE，，18個DSP模塊，165888bits存儲單元。這些存儲單元可以配置為大小、位數不同的存儲器，它可以減少外部存儲器的使用，縮小硬件的體積，便于電路的小型化。

　
圖4 快速標記算法FPGA實現(xiàn)的硬件結構

　　圖4所示快速標記算法FPGA實現(xiàn)的硬件結構，主要由二值視頻流延遲FIFO串并轉換、逆時針標記單元、歸并數據傳輸接口、水平方向標記歸并單元、標記等價關系表、標記等價關系整理單元、圖像標記代換等單元構成。

　　FPGA內部視頻流采集單元，根據分割閾值對采集來的灰度數據進行二值化，輸出二值視頻流；通過延遲FIFO的串并轉換，將串行的二值視頻數據流轉換成兩行并行的數據；逆時針方向標記單元利用移位寄存器對接受來的并行數據流組成圖2所示窗口，在窗口內對數據進行逆時針的連通性檢測，生成初始的等價關系表并且對像素數據進行臨時標記；水平方向標記歸并單元緊接在逆時針方向標記后，對初始標記后的像素數據通過移位寄存器組成如圖3所示的數據窗，對數據窗中的數據在水平方向進行標記等價性判斷，歸并屬于同一區(qū)域的標記值，并且追蹤置換標記等價關系表，把在此以前的等價標記值全部統(tǒng)一成最小的標記值，最后把歸并后的并行標記視頻流存入后續(xù)雙端口RAM組成的存儲器組中；外部雙端口RAM在下一行視頻數據流處理時把標記好的上一行像素數據存入到外部雙端口RAM中。

　　一幀圖像數據標記完畢后，在視頻數據的間隙對等價關系表數組進行整理歸并，等到下一幀視頻數據傳輸時，從外部雙端口RAM中取出上一幀數據進行標記圖像代換完成最終的圖像標記。

　　標記緩存采用乒乓結構通過FPGA中的雙端口RAM構成，標記兩行圖像數據的同時外部雙端口RAM接口對已標記的一行圖像數據進行存儲。圖5所示標記緩存結構，乒乓結構標記緩存模塊一共用了3個384*10bit的雙端口RAM，每個雙端口RAM對應一行圖像標記數據，依靠水平方向歸并單元和外部DPRAM接口交互進行數據存儲，當水平方向歸并單元同時存儲其中兩個雙端口RAM時，外部DPRAM接口對剩余的第三個雙端口RAM進行存數操作，構成標記緩存乒乓結構存儲操作。外部存儲接口用像素時鐘的4倍頻對緩存中的數據進行搬移，確保在其余兩個雙端口RAM標記完畢后外部數據也搬移完畢。實驗證明在一行標記數據傳輸時間里可以完成3行標記數據搬移。

　
圖5 標記緩存結構

　　為了滿足標記的實時流水線處理，外圍雙端口RAM也采用乒乓結構。在對一幀圖像標記數據存儲的同時取出數據進行標記圖像代換，并且在取數的過程中完成對標記結果圖像的形狀的識別，外圍雙端口RAM的內部構造如圖6所示，把外圍雙端口RAM設成圖像幀A、B兩個區(qū)，利用兩個數據地址端口同時對A、B兩個區(qū)進行操作。因此標記算法整體延時一幀視頻數據傳輸時間，具有很強的實時性。

　
圖6 外圍雙端口RAM的內部分區(qū)

4 實驗結果與分析

　　圖7、8、9、10給出對4幅384×288二值紅外圖像的標記結果，由于本文設計針對天空中飛行目標，因此剔除圖像邊緣（對于圖像邊緣的背景目標不標記，致為0值）；統(tǒng)一了標記算法規(guī)則，減小了邊緣背景對目標識別的影響。

　　圖7、8、9、10所示均為在多云背景的天空中含有飛機編隊，對于形狀各異的云層具有復雜的復連通關系，產生復雜的等價表操作，最終被正確地賦予相同的標記。仿真結果相關數據示于表1。其中，F(xiàn)PGA工作時鐘為100 MHz；n為連通區(qū)域個數；N（MAX）為最大臨時標記；T1為TI公司的6416DSP通過傳統(tǒng)的收斂標記算法執(zhí)行時間；T2為TI公司的6416DSP通過本文設計的快速標記算法執(zhí)行時間；T3為FPGA通過本文設計的快速標記算法執(zhí)行時間。

　　仿真結果證明，傳統(tǒng)的收斂標記算法以軟件方式運行于TI公司DSP6416系統(tǒng)中時，算法處理速度不確定，取決于圖像中連通域的形狀和數量；本文中描述的二值分割圖像標記快速算法以軟件方式運行于TI公司DSP6416系統(tǒng)中時，算法處理384×288像素圖像可以達到50幀的處理速度；但是，以FPGA實現(xiàn)該算法時，在100MHz工作時鐘下，能夠達到400幀／秒的處理速度。
表1 圖像標記仿真結果對比
　

　
圖7 含有4架飛機目標的二值紅外圖像和標記后的圖像

　
圖8 含有2架飛機目標的二值紅外圖像和標記后的圖像

　
圖9 含有4架飛機目標的二值紅外圖像和標記后的圖像

　
圖10 含有2架飛機目標的二值紅外圖像和標記后的圖像

參考文獻
[1]張樹生.一種基于線的標號傳播二值圖像連通體快速檢測方法[J].計算機研究與發(fā)展,1994,31(10):51-54
[2]Ranganathan N,Mehrotra R.Subramanmian S.A high speed systolic architecture for labeling connected components in an image[J].IEEE Transaction on Systems.Man.and Cybernetics，1995，25(3):415-423
[3]Nicol C J,A systolic approach for reahime connected component labeling[J].CVGIP,Image Understanding，1995，61(1):17-31
[4]Altera.cycloneII_handbook[R].published by Altera,2005

作者：
賀明：男，1981，江蘇丹陽，防空兵指揮學院在讀研究生，研究的方向為圖像處理、紅外成像技術、FPGA和DSP圖象處理系統(tǒng)設計等。
王新賽：男，1963，博士，碩士生導師，防空兵指揮學院紅外與射頻技術研究中心主任、教授，研究的方向為圖像處理、人工智能。 
李堅：男，1982，湖北荊門，防空兵指揮學院在讀研究生，研究的方向為圖像處理、紅外成像技術等。
聯(lián)系地址：鄭州市建設東路防空兵指揮學院紅外與射頻技術研究中心          郵編：450052  
聯(lián)系電話：0371-63534669    13838119647（M）