1 引言

　　在圖像自動目標(biāo)識別和跟蹤過程中，首先對圖像目標(biāo)進(jìn)行閾值分割提取,，得到的二值圖像通常包含多個(gè)連通區(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)行逐行(列)掃描,，每遇到一個(gè)未標(biāo)記的“1”像素點(diǎn),，就分配其一個(gè)未使用過的標(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)行與以上相同的處理,。整個(gè)圖像掃描結(jié)束,，算法也就終止。這種方法可準(zhǔn)確地檢測出各種類型的連通體．但處理時(shí)間也較長．因?yàn)橐鹨粰z測每一“1”像素的鄰域,，且出現(xiàn)“1”像素的重復(fù)掃描,。跟蹤算法：二值圖像中每個(gè)取值為“1”的像素 被標(biāo)記一個(gè)與其坐標(biāo)相關(guān)的標(biāo)號，如由n,，m串構(gòu)成的數(shù),。熱后，

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

　　本文以適合FPGA實(shí)現(xiàn)為目的，提出一種具有計(jì)算規(guī)則性的快速二值圖像連通域標(biāo)記算法,。與傳統(tǒng)的二值圖像標(biāo)記算法相比,，該算法具有運(yùn)算簡單性、規(guī)則性和可擴(kuò)展性的特點(diǎn),，適合以FPGA實(shí)現(xiàn),。選用在100MHz工作時(shí)鐘下，處理384×288像素的紅外圖像能夠達(dá)到400幀／秒以上的標(biāo)記速度,，足夠滿足實(shí)時(shí)目標(biāo)識別系統(tǒng)的要求,。處理速度可以滿足大部分實(shí)時(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)行逐行像素掃描，然后對每個(gè)像素的鄰域分別按照逆時(shí)針方向和水平方向進(jìn)行連通性檢測和等價(jià)標(biāo)記關(guān)系合并,，檢測出的結(jié)果對標(biāo)記等價(jià)數(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)記算法分為三個(gè)環(huán)節(jié)：

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

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

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

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

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

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

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

　　二值圖像連通域標(biāo)記算法采用8連通判斷準(zhǔn)則,，通過縮小標(biāo)記范圍剔除了圖像的邊界效應(yīng)。為了簡化標(biāo)記處理過程,，使標(biāo)記處理在硬件對一幀圖像傳輸操作時(shí)間內(nèi)結(jié)束,，標(biāo)記處理利用中間數(shù)據(jù)緩存分為連續(xù)的兩種類型，其中類型1用于直接圖像序列傳輸,，硬件發(fā)起圖像序列傳輸時(shí),，類型1采用逆時(shí)鐘順序連通域檢測，對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）,，按照逆時(shí)針方向依次與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寫入等價(jià)關(guān)系表,，以Z為地址將Z寫入等價(jià)關(guān)系數(shù)組。

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

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

　　步驟1判斷經(jīng)過逆時(shí)針方向標(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 等價(jià)表整理與圖像代換

　　首先，從等價(jià)表地址1開始掃描等

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

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

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

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

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

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

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

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

　　FPGA(Field Programmable Gate Array)是一種大規(guī)模的可編程邏輯器件,，可以用于各種數(shù)字邏輯系統(tǒng)，特別是實(shí)時(shí)處理方面,，具有獨(dú)特的優(yōu)勢,。在本算法的實(shí)時(shí)實(shí)現(xiàn)過程中，采用Altera公司的性價(jià)比高的Cyclone II EP2C8 FPGA[4],，該器件內(nèi)部有8256個(gè)LE,，,，18個(gè)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)換,、逆時(shí)針標(biāo)記單元、歸并數(shù)據(jù)傳輸接口,、水平方向標(biāo)記歸并單元,、標(biāo)記等價(jià)關(guān)系表、標(biāo)記等價(jià)關(guān)系整理單元,、圖像標(biāo)記代換等單元構(gòu)成,。

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

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

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

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

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

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

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

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

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

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

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