基于FPGA的二值圖像連通域標(biāo)記快速算法實(shí)現(xiàn)

1 引言

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

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

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

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

2 算法描述

　　首先，在進(jìn)行標(biāo)記算法以前，利用硬件開(kāi)辟獨(dú)立的圖像標(biāo)記緩存和連通關(guān)系數(shù)組，接著在視頻流的采集傳輸過(guò)程中，以流水線(xiàn)的方式按照視頻傳輸順序?qū)D像進(jìn)行逐行像素掃描，然后對(duì)每個(gè)像素的鄰域分別按照逆時(shí)針?lè)较蚝退椒较蜻M(jìn)行連通性檢測(cè)和等價(jià)標(biāo)記關(guān)系合并，檢測(cè)出的結(jié)果對(duì)標(biāo)記等價(jià)數(shù)組和標(biāo)記緩存進(jìn)行更新，在一幀圖像采集傳輸結(jié)束后，得到圖像的初步標(biāo)記結(jié)果以及初步標(biāo)記之間的連通關(guān)系，最后，根據(jù)標(biāo)號(hào)對(duì)連通關(guān)系數(shù)組從小到大的傳遞過(guò)程進(jìn)行標(biāo)號(hào)的歸并，利用歸并后的連通關(guān)系數(shù)組對(duì)圖像標(biāo)記緩存中的標(biāo)號(hà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）對(duì)連通區(qū)域以自然數(shù)順序重新編號(hào)，得到臨時(shí)標(biāo)記與最終標(biāo)記之間的等價(jià)關(guān)系。

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

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

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

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

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

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

　　步驟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)系數(shù)組。

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

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

　　步驟1判斷經(jīng)過(guò)逆時(shí)針?lè)较驑?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），否則對(duì)標(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），否則對(duì)標(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）），對(duì)lab（k0（1））同樣執(zhí)行上述追蹤過(guò)程。

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

2.2 等價(jià)表整理與圖像代換

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

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

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

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

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

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

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

　　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)記取較小值并且不會(huì)遺漏等價(jià)標(biāo)記。其三，結(jié)合視頻數(shù)據(jù)流傳輸方式，采用乒乓存儲(chǔ)結(jié)構(gòu)進(jìn)行流水線(xià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í)實(shí)現(xiàn)過(guò)程中，采用Altera公司的性?xún)r(jià)比高的Cyclone II EP2C8 FPGA[4]，該器件內(nèi)部有8256個(gè)LE，，18個(gè)DSP模塊，165888bits存儲(chǔ)單元。這些存儲(chǔ)單元可以配置為大小、位數(shù)不同的存儲(chǔ)器，它可以減少外部存儲(chǔ)器的使用，縮小硬件的體積，便于電路的小型化。

圖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ù)分割閾值對(duì)采集來(lái)的灰度數(shù)據(jù)進(jìn)行二值化，輸出二值視頻流；通過(guò)延遲FIFO的串并轉(zhuǎn)換，將串行的二值視頻數(shù)據(jù)流轉(zhuǎn)換成兩行并行的數(shù)據(jù)；逆時(shí)針?lè)较驑?biāo)記單元利用移位寄存器對(duì)接受來(lái)的并行數(shù)據(jù)流組成圖2所示窗口，在窗口內(nèi)對(duì)數(shù)據(jù)進(jìn)行逆時(shí)針的連通性檢測(cè)，生成初始的等價(jià)關(guān)系表并且對(duì)像素?cái)?shù)據(jù)進(jìn)行臨時(shí)標(biāo)記；水平方向標(biāo)記歸并單元緊接在逆時(shí)針?lè)较驑?biāo)記后，對(duì)初始標(biāo)記后的像素?cái)?shù)據(jù)通過(guò)移位寄存器組成如圖3所示的數(shù)據(jù)窗，對(duì)數(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組成的存儲(chǔ)器組中；外部雙端口RAM在下一行視頻數(shù)據(jù)流處理時(shí)把標(biāo)記好的上一行像素?cái)?shù)據(jù)存入到外部雙端口RAM中。

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

　　標(biāo)記緩存采用乒乓結(jié)構(gòu)通過(guò)FPGA中的雙端口RAM構(gòu)成，標(biāo)記兩行圖像數(shù)據(jù)的同時(shí)外部雙端口RAM接口對(duì)已標(biāo)記的一行圖像數(shù)據(jù)進(jìn)行存儲(chǔ)。圖5所示標(biāo)記緩存結(jié)構(gòu)，乒乓結(jié)構(gòu)標(biāo)記緩存模塊一共用了3個(gè)384*10bit的雙端口RAM，每個(gè)雙端口RAM對(duì)應(yīng)一行圖像標(biāo)記數(shù)據(jù)，依靠水平方向歸并單元和外部DPRAM接口交互進(jìn)行數(shù)據(jù)存儲(chǔ)，當(dāng)水平方向歸并單元同時(shí)存儲(chǔ)其中兩個(gè)雙端口RAM時(shí)，外部DPRAM接口對(duì)剩余的第三個(gè)雙端口RAM進(jìn)行存數(shù)操作，構(gòu)成標(biāo)記緩存乒乓結(jié)構(gòu)存儲(chǔ)操作。外部存儲(chǔ)接口用像素時(shí)鐘的4倍頻對(duì)緩存中的數(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)

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

內(nèi)部構(gòu)造如圖6所示，把外圍雙端口RAM設(shè)成圖像幀A、B兩個(gè)區(qū)，利用兩個(gè)數(shù)據(jù)地址端口同時(shí)對(duì)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給出對(duì)4幅384×288二值紅外圖像的標(biāo)記結(jié)果，由于本文設(shè)計(jì)針對(duì)天空中飛行目標(biāo)，因此剔除圖像邊緣（對(duì)于圖像邊緣的背景目標(biāo)不標(biāo)記，致為0值）；統(tǒng)一了標(biāo)記算法規(guī)則，減小了邊緣背景對(duì)目標(biāo)識(shí)別的影響。

　　圖7、8、9、10所示均為在多云背景的天空中含有飛機(jī)編隊(duì)，對(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為T(mén)I公司的6416DSP通過(guò)傳統(tǒng)的收斂標(biāo)記算法執(zhí)行時(shí)間；T2為T(mén)I公司的6416DSP通過(guò)本文設(shè)計(jì)的快速標(biāo)記算法執(zhí)行時(shí)間；T3為FPGA通過(guò)本文設(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é)果對(duì)比

　
圖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]張樹(shù)生.一種基于線(xiàn)的標(biāo)號(hào)傳播二值圖像連通體快速檢測(cè)方法[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