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架飛機目標的二值紅外圖像和標記后的圖像 |