|
1 引言 在圖像自動(dòng)目標識別和跟蹤過(guò)程中，首先對圖像目標進(jìn)行閾值分割提取，得到的二值圖像通常包含多個(gè)連通區域，系統利用圖像目標的形狀特性對可疑高威脅的飛行目標進(jìn)行自動(dòng)識別。因此，需要對各連通區域塊進(jìn)行分別檢測判斷，本文采用改進(jìn)的適合FPGA實(shí)現的快速標記算法對各連通域進(jìn)行檢測提取。 實(shí)現二值圖像連通體檢測通常采用的方法有下幾種：區域生長(cháng)法：首先對圖像進(jìn)行逐行(列)掃描，每遇到一個(gè)未標記的“1”像素點(diǎn)，就分配其一個(gè)未使用過(guò)的標號，然后對其領(lǐng)域進(jìn)行檢測，如有未標記過(guò)的“1”像素，則賦予相同的標號。反復進(jìn)行這一操作．直到不存在應該傳播標號的“1”像素。然后繼續圖像行(列)掃描，如檢測判未標記的“1”像素則賦予其新的標號，并進(jìn)行與以上相同的處理。整個(gè)圖像掃描結束，算法也就終止。這種方法可準確地檢測出各種類(lèi)型的連通體．但處理時(shí)間也較長(cháng)．因為要逐一檢測每一“1”像素的鄰域，且出現“1”像素的重復掃描。跟蹤算法：二值圖像中每個(gè)取值為“1”的像素 被標記一個(gè)與其坐標相關(guān)的標號，如由n，m串構成的數。熱后，掃描標記后的圖像，并將每十像素的標號改為其鄰域內的最小標號。反復執行這個(gè)過(guò)程，直到不需要作標記更改為止。用這種方法處理小而凸的目標時(shí)，收斂速度較慢。 本文以適合FPGA實(shí)現為目的，提出一種具有計算規則性的快速二值圖像連通域標記算法。與傳統的二值圖像標記算法相比，該算法具有運算簡(jiǎn)單性、規則性和可擴展性的特點(diǎn)，適合以FPGA實(shí)現。選用在100MHz工作時(shí)鐘下，處理384×288像素的紅外圖像能夠達到400幀／秒以上的標記速度，足夠滿(mǎn)足實(shí)時(shí)目標識別系統的要求。處理速度可以滿(mǎn)足大部分實(shí)時(shí)目標識別系統的要求。該算法同樣可以軟件編程方式應用于嵌入式DSP系統中。 2 算法描述 首先，在進(jìn)行標記算法以前，利用硬件開(kāi)辟獨立的圖像標記緩存和連通關(guān)系數組，接著(zhù)在視頻流的采集傳輸過(guò)程中，以流水線(xiàn)的方式按照視頻傳輸順序對圖像進(jìn)行逐行像素掃描，然后對每個(gè)像素的鄰域分別按照逆時(shí)針?lè )较蚝退椒较蜻M(jìn)行連通性檢測和等價(jià)標記關(guān)系合并，檢測出的結果對標記等價(jià)數組和標記緩存進(jìn)行更新，在一幀圖像采集傳輸結束后，得到圖像的初步標記結果以及初步標記之間的連通關(guān)系，最后，根據標號對連通關(guān)系數組從小到大的傳遞過(guò)程進(jìn)行標號的歸并，利用歸并后的連通關(guān)系數組對圖像標記緩存中的標號進(jìn)行替換，替換后的圖像為最終標記結果，并且連通域按照掃描順序被賦予唯一的連續自然數。 圖 1 標記算法流程 本文快速二值圖像連通域標記算法分為三個(gè)環(huán)節： 1.圖像初步標記：為每個(gè)像素賦予臨時(shí)標記，并且將臨時(shí)標記的等價(jià)關(guān)系記錄在等價(jià)表中 2.整理等價(jià)表：這一環(huán)節分為兩個(gè)步驟： （1）將具有等價(jià)關(guān)系的臨時(shí)標記全部等價(jià)為其中的最小值； （2）對連通區域以自然數順序重新編號，得到臨時(shí)標記與最終標記之間的等價(jià)關(guān)系。 3.圖像代換：對圖像進(jìn)行逐像素代換，將臨時(shí)標記代換為最終標記．經(jīng)過(guò)3個(gè)環(huán)節處理后，算法輸出標記后的圖像，圖像中連通域按照由上到下，由左至右出現的順序被標以連續的自然數。 2.1 圖像初始標記 標記算法符號約定：算法在逆時(shí)鐘方向檢測連通域時(shí)用w1，w2表示連續兩行的圖像數據，在緊接著(zhù)的順時(shí)鐘方向連通域檢測時(shí)用k0，k表示連續兩行經(jīng)過(guò)逆時(shí)鐘方向標記后的圖像數據。 其在工作窗口的位置在圖2、3中分別說(shuō)明；對初始逆時(shí)針?lè )较蚺R時(shí)標記用Z表示。Z初始標記值為1。 二值圖像連通域標記算法采用8連通判斷準則，通過(guò)縮小標記范圍剔除了圖像的邊界效應。為了簡(jiǎn)化標記處理過(guò)程，使標記處理在硬件對一幀圖像傳輸操作時(shí)間內結束，標記處理利用中間數據緩存分為連續的兩種類(lèi)型，其中類(lèi)型1用于直接圖像序列傳輸，硬件發(fā)起圖像序列傳輸時(shí)，類(lèi)型1采用逆時(shí)鐘順序連通域檢測，對2×3工作窗口中的二值像素進(jìn)行初始標記。類(lèi)型2對經(jīng)過(guò)類(lèi)型1初始標記過(guò)的圖像數據再進(jìn)行水平方向的連通域檢測和歸并，然后把標記結果存入圖像存儲區。 圖像初始標記類(lèi)型1： 步驟1讀取像素w1（2）、w1（1）、w1（0）、w0（2）、w0（1），以及相應的二值像素值。 步驟2讀取像素w0（1），按照逆時(shí)針?lè )较蛞来闻cw1（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寫(xiě)入等價(jià)關(guān)系表，以Z為地址將Z寫(xiě)入等價(jià)關(guān)系數組。 圖 2 逆時(shí)鐘方向初始標記的工作窗 圖像初始標記類(lèi)型2： 步驟1判斷經(jīng)過(guò)逆時(shí)針?lè )较驑擞浐�，如果w0（1）= w0（2）= 1，而標記灰度k0（1）≠ k0（0），則進(jìn)行下一步驟。 步驟2 假設k0（1）> k0（0），判斷lab（k0（1））=k0（1）或者lab（k0（1））=k0（0），則lab（k0（1））=k0（0），否則對標記數組進(jìn)行追蹤置換。跳轉至步驟3。 步驟3 假設k0（1） 追蹤置換方法：步驟2的追蹤置換令t= lab（k0（0））；若lab（t）≠ t，則令t= lab（t），重復執行，直lab（t）=t；步驟3的追蹤置換令t1= lab（k0（1）），對lab（k0（1））同樣執行上述追蹤過(guò)程。 圖 3 水平方向初始標記的工作窗 2.2 等價(jià)表整理與圖像代換 首先，從等價(jià)表地址1開(kāi)始掃描等價(jià)表，依次檢查其中各個(gè)臨時(shí)標記是否存在等價(jià)關(guān)系，若存在，則以標記值作為等價(jià)表地址的數據更新等價(jià)表。由于整理過(guò)程從等價(jià)表地址1開(kāi)始，因此對整個(gè)等價(jià)表的掃描可以一遍結束。 圖像代換環(huán)節對臨時(shí)標記圖像中的每個(gè)像素進(jìn)行代換，生成最終的標記后圖像。具體做法是：設圖像中坐標為（n，m）的像素的臨時(shí)標記值為S，則將lab（S）寫(xiě)入圖像中（n，m）位置。代換后得到的圖像，其中的連通區域按照由上到下，由左至右出現的順序被標以惟一的自然數。 2.3 算法特點(diǎn)分析 算法設計具有以下特點(diǎn)： a．本文算法針對空中目標的識別和跟蹤進(jìn)行標記，可以剔除對空中目標識別沒(méi)有影響的圖像的邊界，圖像中其他像素的標記工作均利用2.1中所述算法完成，因此運算具有規則性和同地址性，利用硬件實(shí)現時(shí)只需要定義兩個(gè)算法框架函數循環(huán)使用，節約了算法存儲器資源。 b．圖像初步標記過(guò)程中，在記錄標記等價(jià)信息的同時(shí)對等價(jià)表進(jìn)行初步整理，這樣安排，一方面可以保證區域之間存在復雜連通關(guān)系時(shí)，等價(jià)表能夠保存已經(jīng)檢測到的全部等價(jià)關(guān)系；另一方面，在以硬件電路實(shí)現標記算法時(shí)，圖像初步標記和等價(jià)表初步整理的過(guò)程可以并行執行，等價(jià)表的初步整理，能夠簡(jiǎn)化隨后的等價(jià)表整理操作，相當于壓縮了標記執行的全過(guò)程。 c．在本算法中，采取兩方面措施減少臨時(shí)標記數量：其一，反復利用8鄰域范圍內生成的所有標記信息，在逆時(shí)針順序8鄰域范圍標記后借助圖像傳輸的順序進(jìn)行水平方向的等價(jià)標記歸并，降低了需要賦予新標記值的概率；其二，在等價(jià)表整理時(shí)，歸并等價(jià)標記時(shí)按照等價(jià)表地址從小到大的的順序進(jìn)行比較替換，使等價(jià)標記取較小值并且不會(huì )遺漏等價(jià)標記。其三，結合視頻數據流傳輸方式，采用乒乓存儲結構進(jìn)行流水線(xiàn)處理，同時(shí)進(jìn)行圖像標記和圖像標記替換。使圖像標記達到實(shí)時(shí)處理的效果。 3 算法的FPGA實(shí)現 FPGA(Field Programmable Gate Array)是一種大規模的可編程邏輯器件，可以用于各種數字邏輯系統，特別是實(shí)時(shí)處理方面，具有獨特的優(yōu)勢。在本算法的實(shí)時(shí)實(shí)現過(guò)程中，采用Altera公司的性?xún)r(jià)比高的Cyclone II EP2C8 FPGA[4]，該器件內部有8256個(gè)LE，，18個(gè)DSP模塊，165888bits存儲單元。這些存儲單元可以配置為大小、位數不同的存儲器，它可以減少外部存儲器的使用，縮小硬件的體積，便于電路的小型化。 圖4 快速標記算法FPGA實(shí)現的硬件結構 圖4所示快速標記算法FPGA實(shí)現的硬件結構，主要由二值視頻流延遲FIFO串并轉換、逆時(shí)針標記單元、歸并數據傳輸接口、水平方向標記歸并單元、標記等價(jià)關(guān)系表、標記等價(jià)關(guān)系整理單元、圖像標記代換等單元構成。 FPGA內部視頻流采集單元，根據分割閾值對采集來(lái)的灰度數據進(jìn)行二值化，輸出二值視頻流；通過(guò)延遲FIFO的串并轉換，將串行的二值視頻數據流轉換成兩行并行的數據；逆時(shí)針?lè )较驑擞泦卧靡莆患拇嫫鲗邮軄?lái)的并行數據流組成圖2所示窗口，在窗口內對數據進(jìn)行逆時(shí)針的連通性檢測，生成初始的等價(jià)關(guān)系表并且對像素數據進(jìn)行臨時(shí)標記；水平方向標記歸并單元緊接在逆時(shí)針?lè )较驑擞浐�，對初始標記后的像素數據通過(guò)移位寄存器組成如圖3所示的數據窗，對數據窗中的數據在水平方向進(jìn)行標記等價(jià)性判斷，歸并屬于同一區域的標記值，并且追蹤置換標記等價(jià)關(guān)系表，把在此以前的等價(jià)標記值全部統一成最小的標記值，最后把歸并后的并行標記視頻流存入后續雙端口RAM組成的存儲器組中；外部雙端口RAM在下一行視頻數據流處理時(shí)把標記好的上一行像素數據存入到外部雙端口RAM中。 一幀圖像數據標記完畢后，在視頻數據的間隙對等價(jià)關(guān)系表數組進(jìn)行整理歸并，等到下一幀視頻數據傳輸時(shí)，從外部雙端口RAM中取出上一幀數據進(jìn)行標記圖像代換完成最終的圖像標記。 標記緩存采用乒乓結構通過(guò)FPGA中的雙端口RAM構成，標記兩行圖像數據的同時(shí)外部雙端口RAM接口對已標記的一行圖像數據進(jìn)行存儲。圖5所示標記緩存結構，乒乓結構標記緩存模塊一共用了3個(gè)384*10bit的雙端口RAM，每個(gè)雙端口RAM對應一行圖像標記數據，依靠水平方向歸并單元和外部DPRAM接口交互進(jìn)行數據存儲，當水平方向歸并單元同時(shí)存儲其中兩個(gè)雙端口RAM時(shí)，外部DPRAM接口對剩余的第三個(gè)雙端口RAM進(jìn)行存數操作，構成標記緩存乒乓結構存儲操作。外部存儲接口用像素時(shí)鐘的4倍頻對緩存中的數據進(jìn)行搬移，確保在其余兩個(gè)雙端口RAM標記完畢后外部數據也搬移完畢。實(shí)驗證明在一行標記數據傳輸時(shí)間里可以完成3行標記數據搬移。 圖5 標記緩存結構 為了滿(mǎn)足標記的實(shí)時(shí)流水線(xiàn)處理，外圍雙端口RAM也采用乒乓結構。在對一幀圖像標記數據存儲的同時(shí)取出數據進(jìn)行標記圖像代換，并且在取數的過(guò)程中完成對標記結果圖像的形狀的識別，外圍雙端口RAM的內部構造如圖6所示，把外圍雙端口RAM設成圖像幀A、B兩個(gè)區，利用兩個(gè)數據地址端口同時(shí)對A、B兩個(gè)區進(jìn)行操作。因此標記算法整體延時(shí)一幀視頻數據傳輸時(shí)間，具有很強的實(shí)時(shí)性。 圖6 外圍雙端口RAM的內部分區 4 實(shí)驗結果與分析 圖7、8、9、10給出對4幅384×288二值紅外圖像的標記結果，由于本文設計針對天空中飛行目標，因此剔除圖像邊緣（對于圖像邊緣的背景目標不標記，致為0值）；統一了標記算法規則，減小了邊緣背景對目標識別的影響。 圖7、8、9、10所示均為在多云背景的天空中含有飛機編隊，對于形狀各異的云層具有復雜的復連通關(guān)系，產(chǎn)生復雜的等價(jià)表操作，最終被正確地賦予相同的標記。仿真結果相關(guān)數據示于表1。其中，FPGA工作時(shí)鐘為100 MHz；n為連通區域個(gè)數；N（MAX）為最大臨時(shí)標記；T1為T(mén)I公司的6416DSP通過(guò)傳統的收斂標記算法執行時(shí)間；T2為T(mén)I公司的6416DSP通過(guò)本文設計的快速標記算法執行時(shí)間；T3為FPGA通過(guò)本文設計的快速標記算法執行時(shí)間。 仿真結果證明，傳統的收斂標記算法以軟件方式運行于TI公司DSP6416系統中時(shí)，算法處理速度不確定，取決于圖像中連通域的形狀和數量；本文中描述的二值分割圖像標記快速算法以軟件方式運行于TI公司DSP6416系統中時(shí)，算法處理384×288像素圖像可以達到50幀的處理速度；但是，以FPGA實(shí)現該算法時(shí)，在100MHz工作時(shí)鐘下，能夠達到400幀／秒的處理速度。 表1 圖像標記仿真結果對比 圖7 含有4架飛機目標的二值紅外圖像和標記后的圖像 圖8 含有2架飛機目標的二值紅外圖像和標記后的圖像 圖9 含有4架飛機目標的二值紅外圖像和標記后的圖像 圖10 含有2架飛機目標的二值紅外圖像和標記后的圖像 |
