1 引言

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

　　實(shí)現(xiàn)二值圖像連通體檢測通常采用的方法有下幾種[1] [2] [3]：區(qū)域生長法：首先對圖像進(jìn)行逐行(列)掃描，每遇到一個未標(biāo)記的“1”像素點(diǎn)，就分配其一個未使用過的標(biāo)號，然后對其領(lǐng)域進(jìn)行檢測，如有未標(biāo)記過的“1”像素，則賦予相同的標(biāo)號。反復(fù)進(jìn)行這一操作．直到不存在應(yīng)該傳播標(biāo)號的“1”像素。然后繼續(xù)圖像行(列)掃描，如檢測判未標(biāo)記的“1”像素則賦予其新的標(biāo)號，并進(jìn)行與以上相同的處理。整個圖像掃描結(jié)束，算法也就終止。這種方法可準(zhǔn)確地檢測出各種類型的連通體．但處理時間也較長．因?yàn)橐鹨粰z測每一“1”像素的鄰域，且出現(xiàn)“1”像素的重復(fù)掃描。跟蹤算法：二值圖像中每個取值為“1”的像素 被標(biāo)記一個與其坐標(biāo)相關(guān)的標(biāo)號，如由n，m串構(gòu)成的數(shù)。熱后，

掃描標(biāo)記后的圖像，并將每十像素的標(biāo)號改為其鄰域內(nèi)的最小標(biāo)號。反復(fù)執(zhí)行這個過程，直到不需要作標(biāo)記更改為止。用這種方法處理小而凸的目標(biāo)時，收斂速度較慢。

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

2 算法描述

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

圖 1 標(biāo)記算法流程

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

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

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

（1）將具有等價關(guān)系的臨時標(biāo)記全部等價為其中的最小值；

（2）對連通區(qū)域以自然數(shù)順序重新編號，得到臨時標(biāo)記與最終標(biāo)記之間的等價關(guān)系。

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

2.1 圖像初始標(biāo)記

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

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

圖像初始標(biāo)記類型1：

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

　　步驟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寫入等價關(guān)系表，以Z為地址將Z寫入等價關(guān)系數(shù)組。

圖 2 逆時鐘方向初始標(biāo)記的工作窗

圖像初始標(biāo)記類型2：

　　步驟1判斷經(jīng)過逆時針方向標(biāo)記后，如果w0（1）= w0（2）= 1，而標(biāo)記灰度k0（1）≠ k0（0），則進(jìn)行下一步驟。

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

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

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

圖 3 水平方向初始標(biāo)記的工作窗

2.2 等價表整理與圖像代換

　　首先，從等價表地址1開始掃描等

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

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

2.3 算法特點(diǎn)分析

算法設(shè)計具有以下特點(diǎn)：

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

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

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

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

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

圖4 快速標(biāo)記算法FPGA實(shí)現(xiàn)的硬件結(jié)構(gòu)

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

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

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

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

圖5 標(biāo)記緩存結(jié)構(gòu)

　　為了滿足標(biāo)記的實(shí)時流水線處理，外圍雙端口RAM也采用乒乓結(jié)構(gòu)。在對一幀圖像標(biāo)記數(shù)據(jù)存儲的同時取出數(shù)據(jù)進(jìn)行標(biāo)記圖像代換，并且在取數(shù)的過程中完成對標(biāo)記結(jié)果圖像的形狀的識別，外圍雙端口RAM的

內(nèi)部構(gòu)造如圖6所示，把外圍雙端口RAM設(shè)成圖像幀A、B兩個區(qū)，利用兩個數(shù)據(jù)地址端口同時對A、B兩個區(qū)進(jìn)行操作。因此標(biāo)記算法整體延時一幀視頻數(shù)據(jù)傳輸時間，具有很強(qiáng)的實(shí)時性。

4 實(shí)驗(yàn)結(jié)果與分析

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

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

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

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

表1 圖像標(biāo)記仿真結(jié)果對比

　
圖7 含有4架飛機(jī)目標(biāo)的二值紅外圖像和標(biāo)記后的圖像
　
圖8 含有2架飛機(jī)目標(biāo)的二值紅外圖像和標(biāo)記后的圖像
　
圖9 含有4架飛機(jī)目標(biāo)的二值紅外圖像和標(biāo)記后的圖像
　
圖10 含有2架飛機(jī)目標(biāo)的二值紅外圖像和標(biāo)記后的圖像

參考文獻(xiàn)

[1]張樹生.一種基于線的標(biāo)號傳播二值圖像連通體快速檢測方法[J].計算機(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