基于FPGA 的快速連通域標(biāo)記算法*

黃名政，李彬華，2*，王錦良

(1.昆明理工大學(xué)信息工程與自動(dòng)化學(xué)院，云南 昆明650500；2.昆明理工大學(xué)云南省計(jì)算機(jī)技術(shù)應(yīng)用重點(diǎn)實(shí)驗(yàn)室，云南 昆明650500)

連通域標(biāo)記是機(jī)器人視覺、目標(biāo)跟蹤與識(shí)別、交通檢測(cè)和字符識(shí)別等領(lǐng)域的基礎(chǔ)與前提[1-2]，在圖像分析、模式識(shí)別和計(jì)算機(jī)視覺中也扮演著重要角色[3]。 對(duì)于實(shí)時(shí)性要求較高的圖像處理系統(tǒng)，通?？墒褂脠D形處理單元(GPU)、FPGA 等以附加硬件的方式進(jìn)行加速處理，特別是小型設(shè)備中，F(xiàn)PGA 具有較大的優(yōu)勢(shì)。 目前在FPGA 上，只需通過流水線方式就可實(shí)現(xiàn)圖像濾波、閾值分割和邊緣檢測(cè)這類流程相對(duì)簡(jiǎn)單的圖像處理算法[4]。 但通常的連通域標(biāo)記算法由于需要更多的存儲(chǔ)資源，在使用資源較為有限的FPGA 進(jìn)行處理時(shí)，資源消耗問題顯得尤為重要。 因此，基于FPGA 的高效連通域標(biāo)記算法成為當(dāng)前的研究熱點(diǎn)之一。

連通域標(biāo)記算法可分為連通域標(biāo)號(hào)標(biāo)記和連通域特征分析，連通域標(biāo)號(hào)標(biāo)記是將同一連通域的所有像素分配唯一的標(biāo)號(hào)；連通域特征分析是提取每個(gè)連通域的特征信息，如面積、周長(zhǎng)、包圍盒和重心等[3]。 針對(duì)連通域標(biāo)號(hào)標(biāo)記，Chang 等[5]提出的輪廓標(biāo)記法，僅對(duì)圖像進(jìn)行一次掃描，檢測(cè)每個(gè)連通域輪廓，并標(biāo)記其內(nèi)部區(qū)域，但輪廓點(diǎn)掃描次數(shù)可能不止一次。 Bataineh[1]提出快速的雙掃描連通域標(biāo)記算法，優(yōu)化了等價(jià)標(biāo)號(hào)與臨時(shí)標(biāo)號(hào)替換規(guī)則，使連通域算法具有更高的效率。 Stefania 等[6]提出的雙掃描方法，可在像素及幀間進(jìn)行并行處理，通過緩沖器存儲(chǔ)等價(jià)標(biāo)號(hào)，實(shí)時(shí)處理等價(jià)標(biāo)號(hào)與臨時(shí)標(biāo)號(hào)，在一定程度上降低了系統(tǒng)耗時(shí)。 張國(guó)和等人[4]提出的快速連通域標(biāo)記算法，利用片上RAM 讀寫特性，減少了資源的消耗。 Zhao 等人[7]提出的高效連通域標(biāo)記算法，在掃描時(shí)對(duì)輸入的二進(jìn)制圖像用游程編碼進(jìn)行壓縮，同時(shí)掃描相鄰行，實(shí)時(shí)輸出已結(jié)束區(qū)域并釋放其存儲(chǔ)空間。

通常為了清晰地區(qū)分各連通域，還需對(duì)連通域進(jìn)行特征分析。 針對(duì)連通域特征分析，再結(jié)合包圍盒特點(diǎn)，Tang 等[8]提出的單通循環(huán)編碼算法對(duì)目標(biāo)進(jìn)行了包圍盒標(biāo)記，結(jié)合鏈表和游程特征優(yōu)化了等價(jià)標(biāo)號(hào)處理過程，但處理過程中需要對(duì)圖像進(jìn)行單行緩存，加大了系統(tǒng)內(nèi)存資源的消耗。 閆石等人提出的基于地址-事件的高速連通域標(biāo)記方式，處理極低冗余的事件信息，降低了算法運(yùn)行時(shí)間[9]，但僅在前景目標(biāo)較少的二值圖像的前提下才具有較高的執(zhí)行效率。 王凡等人提出的快速連通域標(biāo)記方法，對(duì)圖像一次掃描，不產(chǎn)生臨時(shí)標(biāo)號(hào)[10]，但僅適合于艦船或其他形狀較規(guī)則的目標(biāo)。 戴華東等人提出了一種適用于單目標(biāo)圖像實(shí)時(shí)檢測(cè)與跟蹤算法，簡(jiǎn)化了等價(jià)標(biāo)號(hào)處理過程，緩存單行圖像即可完成標(biāo)記[11]，但僅支持單目標(biāo)標(biāo)記或者已知個(gè)數(shù)的多目標(biāo)標(biāo)記，并不適用于一般性的多目標(biāo)檢測(cè)。

綜上，在連通域標(biāo)記的算法中，大多需要處理等價(jià)標(biāo)號(hào)與臨時(shí)標(biāo)號(hào)[1，4，6-8]，必然導(dǎo)致額外的運(yùn)行時(shí)間與片上RAM 資源消耗；此外，當(dāng)標(biāo)記特殊圖案時(shí)，等價(jià)標(biāo)號(hào)與臨時(shí)標(biāo)號(hào)過大，使算法時(shí)間與資源的消耗成倍增加。 同時(shí)大多數(shù)算法僅對(duì)圖像進(jìn)行標(biāo)號(hào)標(biāo)記，并未對(duì)特征進(jìn)行分析[1，6-7]。 針對(duì)以上問題，再結(jié)合包圍盒特點(diǎn)，本文提出了一種基于FPGA 的快速連通域標(biāo)記算法。 該算法利用片上RAM 讀寫特性，處理游程時(shí)就判斷游程間連通與否，同時(shí)合并優(yōu)化連通游程信息，不產(chǎn)生等價(jià)標(biāo)號(hào)；利用片上RAM 地址信息判斷不同連通域，不產(chǎn)生臨時(shí)標(biāo)號(hào)。整個(gè)過程僅對(duì)圖像掃描一次，即可得到所有連通域排序后的行特征信息(包圍盒起始特征信息/結(jié)束行特征信息)，最后將行特征信息疊加在待標(biāo)記圖像上就能完成連通域標(biāo)記。

1 快速連通域標(biāo)記算法設(shè)計(jì)

1.1 新的連通域標(biāo)記算法流程

連通域標(biāo)記算法是對(duì)圖像中前景像素進(jìn)行標(biāo)記，目的是區(qū)分圖像中不同連通域。 其連通性一般分為4 連通和8 連通，因8 連通在處理過程中判斷更多的像素點(diǎn)，標(biāo)記更為準(zhǔn)確，常用8 連通作為連通域標(biāo)記檢測(cè)算子。 結(jié)合包圍盒特點(diǎn)，本算法最終采用不同顏色包圍盒交叉標(biāo)記各連通域，算法流程圖如圖1 所示。

圖1 快速連通域標(biāo)記算法流程圖

與傳統(tǒng)標(biāo)記算法類似，新的標(biāo)記算法仍以像素為基本單位按光柵掃描順序(即由左至右、由上至下)逐行掃描，但在幾個(gè)關(guān)鍵步驟(如等價(jià)游程優(yōu)化置換、行特征信息提取和包圍盒快速顯示)與傳統(tǒng)算法不同。 掃描過程中以游程為單位記錄行列信息。 等價(jià)游程優(yōu)化置換過程:將游程視為運(yùn)算單元，進(jìn)行8 鄰域判斷，若連通則將游程信息合并優(yōu)化后置換原數(shù)據(jù)，否則直接將游程信息按地址累加方式存儲(chǔ)于片上RAM。 行特征信息提取過程:實(shí)時(shí)提取已結(jié)束連通域的結(jié)束行特征信息，當(dāng)所有區(qū)域檢測(cè)完成(幀結(jié)束信號(hào))后提取起始行特征信息。 包圍盒快速顯示過程:將排序后的行特征信息疊加在待標(biāo)記圖像上顯示。

1.2 FPGA 系統(tǒng)總體設(shè)計(jì)

按圖1 所示算法流程，結(jié)合FPGA 對(duì)信息處理的特點(diǎn)，采用Verilog 硬件描述語言(HDL)對(duì)新的快速連通域標(biāo)記算法進(jìn)行了邏輯設(shè)計(jì)，并在基于Xilinx Spartan-6 系列XC6SLX150 芯片為核心的開發(fā)板上進(jìn)行了系統(tǒng)實(shí)現(xiàn)。

這一新的FPGA 系統(tǒng)總體分為圖像輸入、圖像存儲(chǔ)、連通域檢測(cè)和包圍盒快速顯示4 個(gè)模塊。 圖像輸入模塊:將輸入圖像進(jìn)行二值化處理后轉(zhuǎn)為以像素為單位的連續(xù)數(shù)據(jù)流。 得到的數(shù)據(jù)流分兩路輸入不同模塊:一路輸入到連通域檢測(cè)模塊，經(jīng)過該模塊將得到圖像中各連通域包圍盒行特征信息；一路直接輸入到第三代雙倍數(shù)據(jù)率同步動(dòng)態(tài)隨機(jī)存取存儲(chǔ)器(DDR3)中緩存，即DDR3 緩存模塊。 圖像顯示模塊:將排序后的行特征信息疊加在緩存于DDR3 中的圖像上，并通過視頻圖形陣列(VGA)顯示模塊顯示標(biāo)記后圖像。 系統(tǒng)總體結(jié)構(gòu)框圖如圖2 所示。

圖2 系統(tǒng)總體結(jié)構(gòu)框圖

本文主要介紹快速標(biāo)記算法，而算法僅對(duì)圖像進(jìn)行連通域特征分析，所以下面僅對(duì)連通域檢測(cè)模塊和包圍盒快速顯示模塊進(jìn)行詳細(xì)介紹。 另外兩個(gè)模塊(即圖像輸入和DDR3 圖像緩存模塊)可以參看我們以前發(fā)表的相關(guān)論文[12]。

1.3 連通域檢測(cè)模塊設(shè)計(jì)

連通域檢測(cè)模塊主要完成圖像掃描、等價(jià)游程優(yōu)化置換和行特征信息提取等任務(wù)。 其中圖像掃描模塊由像素掃描模塊和游程信息緩存組成，等價(jià)游程優(yōu)化置換模塊由鄰域判斷模塊和RAM 存儲(chǔ)模塊組成，行特征信息提取模塊則主要由行特征信息緩存模塊構(gòu)成。 各模塊詳細(xì)情況介紹如下。

1.3.1 圖像掃描

光柵掃描過程中記錄游程信息，游程信息中行地址、列起始地址和列結(jié)束地址，分別用row、left 和right 表示。 檢測(cè)到“01”時(shí)，說明游程開始，記錄行列信息并存儲(chǔ)到寄存器R0{row，left}；檢測(cè)到“10”時(shí)，說明游程結(jié)束，將記錄的列信息與寄存器R0 值合并后存儲(chǔ)到寄存器D0{row，left，right}中。 單行游程可能出現(xiàn)的情況如圖3 所示。

圖3 單行可能出現(xiàn)游程示意圖

針對(duì)圖3，本算法游程信息存儲(chǔ)詳細(xì)過程:掃描到第一個(gè)前景像素(第0 行第1 列)時(shí)，R0 賦值為{0，1}，當(dāng)掃描到游程結(jié)束(第0 行第4 列)時(shí)，D0賦值為{0，1，4}。 為了避免兩游程相近時(shí)(即上一游程未處理完，下一游程已被檢測(cè))，丟失下一游程信息的情況發(fā)生，將游程信息D0 數(shù)據(jù)緩存于先進(jìn)先出存儲(chǔ)器(FIFO)FIFO_RUN 中。 類似地處理后續(xù)每個(gè)游程。 同時(shí)還需注意邊界情況，當(dāng)檢測(cè)到前景像素且位于第一列時(shí)視為游程開始，當(dāng)檢測(cè)到前景像素且位于最后一列時(shí)視為游程結(jié)束，其賦值方式不變。

1.3.2 等價(jià)游程優(yōu)化置換

經(jīng)圖像掃描后得到的第一個(gè)游程視為新游程，直接將其信息存儲(chǔ)于RAM0 第1 個(gè)地址中。 RAM0數(shù)據(jù)為一個(gè)臨時(shí)包圍盒特征信息，數(shù)據(jù)格式為起始行/結(jié)束行地址和起始列/結(jié)束列地址，分別up、down、left 和right 表示，其中新游程對(duì)應(yīng)的up 與down 數(shù)值均賦值為row；同時(shí)將列信息(列起始與結(jié)束地址)存儲(chǔ)于RAM1 中，數(shù)據(jù)格式{left，right}。 當(dāng)?shù)? 個(gè)及其之后游程到來時(shí)，需要將RAM1 中非零數(shù)據(jù)讀出并與該游程(即當(dāng)前游程)進(jìn)行8 連通判斷，若連通則將該游程信息與對(duì)應(yīng)地址RAM0 中數(shù)據(jù)合并優(yōu)化后置換原數(shù)據(jù)；否則，將其視為新游程，相關(guān)信息按地址累加方式存儲(chǔ)于RAM0 中。 RAM1始終存儲(chǔ)該游程(實(shí)時(shí)處理游程)對(duì)應(yīng)臨時(shí)包圍盒中上一行前景像素列信息。 判斷連通關(guān)系用式(1)，合并優(yōu)化過程用式(2)至式(5)。

式中:M1_left 和M1_right 為RAM1 中數(shù)據(jù)，M0_up、M0_down、M0_left 和M0_right 為RAM0 中數(shù)據(jù)，Mr_row、Mr_left 和Mr_right 為當(dāng)前游程數(shù)據(jù)，Mn_up、Mn_down、Mn_left 和Mn_right 為合并優(yōu)化后數(shù)據(jù)。

當(dāng)出現(xiàn)一個(gè)游程與上一行多個(gè)游程滿足連通，即“U”或“W”型圖案時(shí)，處理過程中需要將最終合并優(yōu)化后數(shù)據(jù)置換RAM0 中最小地址數(shù)據(jù)，RAM1中數(shù)據(jù)也隨之置換；同時(shí)在該游程處理完成后將其余地址RAM(RAM0 和RAM1)數(shù)據(jù)寫0。 相鄰兩行游程可能存在的關(guān)系，如圖4 所示。

圖4 相鄰兩行可能出現(xiàn)游程示意圖

針對(duì)圖4，本算法處理的詳細(xì)過程:當(dāng)?shù)? 行掃描結(jié)束后RAM 中數(shù)據(jù)如表1；處理第1 行游程(第5游程)時(shí)，RAM 中數(shù)據(jù)置換過程如表2。

表1 第1 行處理完存儲(chǔ)器數(shù)值

表2 處理游程比較置換過程

因?yàn)镽AM1 存儲(chǔ)數(shù)據(jù)的特殊性，導(dǎo)致RAM1 中數(shù)據(jù)除處理過程中寫入數(shù)據(jù)外，還需在同行游程確定不同連通域后或下一行游程到來時(shí)寫入上一游程列信息。 處理完成游程5 后，類似地處理下一游程，若該游程(游程6)與上一游程(游程5)屬于同行游程且與上一游程(游程5)區(qū)域不連通，則將上一游程列信息{7，13}寫入RAM1；否則，重復(fù)以上步驟，直至游程為下一行的游程，再將上一游程列信息寫入RAM1。 引入RAM1 可提高了特殊情況判斷連通性的準(zhǔn)確率。 針對(duì)圖4，在判斷游程連通關(guān)系時(shí)，若采用RAM0(臨時(shí)包圍盒特征信息)中列信息{5，15}，則將錯(cuò)誤的判斷游程6 與游程5 連通；引入RAM1(上一行前景像素列信息){7，13}，則準(zhǔn)確地將游程6 視為新的游程。

1.3.3 行特征信息提取

確定連通域結(jié)束后需要提取該連通域結(jié)束行特征信息。 當(dāng)滿足式(6)或式(7)表示連通域結(jié)束。

連通區(qū)域結(jié)束后實(shí)時(shí)提取特征信息就完成了圖像連通域檢測(cè)。 為了后續(xù)快速顯示包圍盒，需要將包圍盒特征信息分為起始行特征信息和結(jié)束行特征信息。

結(jié)束行特征信息提取:將結(jié)束區(qū)域地址信息存儲(chǔ)于FIFO(FIFO_DOWN)，后續(xù)提取包圍盒結(jié)束行特征信息時(shí)，提取該FIFO 中數(shù)據(jù)作為RAM0 地址對(duì)應(yīng)的數(shù)據(jù)即可，數(shù)據(jù)格式為{down，left，right}，同時(shí)后續(xù)處理游程間關(guān)系讀RAM1 數(shù)據(jù)時(shí)無需讀該地址數(shù)據(jù)。

當(dāng)處理某一游程時(shí)出現(xiàn)多個(gè)連通域結(jié)束，此時(shí)需要考慮各連通域結(jié)束的先后順序。 式(6)判斷結(jié)束區(qū)域優(yōu)先于式(7)，所以在提取地址信息時(shí)優(yōu)先提取式(6)判斷區(qū)域；當(dāng)式(6)、式(7)各自判斷出多個(gè)連通域結(jié)束時(shí)，在式(6)優(yōu)先于式(7)前提下，還需按列數(shù)據(jù)小的地址信息優(yōu)先提取。

起始行特征信息提取:根據(jù)片上RAM 地址從小到大順序可得到排序后的起始行特征信息，但由于各區(qū)域結(jié)束的不確定性，無法實(shí)時(shí)按該順序提取已結(jié)束的起始行特征信息，需等所有區(qū)域檢測(cè)完成后提取，將RAM0 非零數(shù)據(jù)按格式{up，left，right}提取，還需同步記錄color 數(shù)值。 其中color 數(shù)值根據(jù)地址確定，但color 僅在2～3 間循環(huán)，實(shí)現(xiàn)兩種顏色包圍盒交叉標(biāo)記各連通域。 其中顏色數(shù)值0 代表背景像素，1 代表前景像素，2、3 代表兩種不同顏色。

1.4 包圍盒快速顯示模塊設(shè)計(jì)

由于算法用于目標(biāo)檢測(cè)系統(tǒng)的前端模塊，需要考慮能否快速顯示包圍盒標(biāo)記。 本算法提出一種快速顯示包圍盒標(biāo)記方法，分為行特征信息排序、VGA顯示兩個(gè)過程。

行特征信息排序:經(jīng)過連通域檢測(cè)模塊后得到兩組數(shù)據(jù)(起始行特征信息和結(jié)束行特征信息)，通過對(duì)兩組數(shù)據(jù)按光柵掃描出現(xiàn)的先后順序讀取，將得到所有排序后的行特征信息；同時(shí)結(jié)合顏色數(shù)值color 存儲(chǔ)在FIFO(FIFO_ROW)中，數(shù)據(jù)格式為{color，up/down，left，right}，其中取結(jié)束行特征信息時(shí)，color 數(shù)值賦0。 處理過程中連通域可能出現(xiàn)的特殊情況，如圖5 所示。

針對(duì)圖5，本算法處理行特征信息排序過程，如表3 所示。

表3 包圍盒快速標(biāo)記過程

VGA 顯示:將排序后的行特征信息疊加在待標(biāo)記圖像上顯示，實(shí)現(xiàn)對(duì)圖像各連通域的包圍盒標(biāo)記。

行標(biāo)記:當(dāng)FIFO_ROW 出現(xiàn){2，0，12，15}時(shí)，表示起始行特征信息，有顏色數(shù)值，待標(biāo)記圖像第0 行12 列至15 列將顯示顏色2；當(dāng)FIFO_ROW 出現(xiàn){0，3，5，8}，表示結(jié)束行特征信息，無顏色數(shù)值，待標(biāo)記圖像第3 行5 列至8 列將顯示對(duì)應(yīng)列標(biāo)記顏色。

列標(biāo)記:僅用0 和1(非0)緩存上一行標(biāo)記結(jié)果，當(dāng)檢測(cè)“01”或“10”時(shí)則表示各包圍盒對(duì)應(yīng)列出現(xiàn)，此時(shí)顯示上一行顏色數(shù)值；當(dāng)結(jié)束行特征信息到來時(shí)，結(jié)束對(duì)應(yīng)列標(biāo)記。 同時(shí)需要注意包圍盒交叉情況，將交叉標(biāo)記點(diǎn)取列標(biāo)記值，同時(shí)產(chǎn)生使能信號(hào)，這樣在下一行標(biāo)記時(shí)能準(zhǔn)確按列標(biāo)記，使包圍盒交叉情況也能準(zhǔn)確標(biāo)記。

2 算法運(yùn)行時(shí)間及硬件資源分析

2.1 算法運(yùn)行時(shí)間

基于上述理論分析可知，對(duì)于分辨率為N×M的圖像，本算法運(yùn)行時(shí)間T0滿足式(8)。

式中:t為機(jī)器周期，td為提取剩余結(jié)束行特征信息時(shí)間，tr為提取所有起始行特征信息時(shí)間。td＝(l+2)×t，tr＝(n+n0+1)×t。l為處理最后一游程時(shí)未結(jié)束區(qū)域個(gè)數(shù)，n為總的連通域個(gè)數(shù)，n0為零數(shù)據(jù)個(gè)數(shù)。

根據(jù)多次實(shí)驗(yàn)表明l與n0值偏小對(duì)算法總體時(shí)間影響較小，連通域個(gè)數(shù)n值可能出現(xiàn)較大情況，但一般不會(huì)超過列最大值N，故算法最大運(yùn)行時(shí)間Tmax滿足式(9)。

考慮到一般圖像中最后一行無前景像素，若將所有區(qū)域檢測(cè)完成信號(hào)由幀結(jié)束信號(hào)提前至最后一行開始，此時(shí)算法運(yùn)行時(shí)間T′0滿足式(10)。

結(jié)合實(shí)際情況，算法運(yùn)行時(shí)間應(yīng)大于等于圖像掃描時(shí)間，故算法最小運(yùn)行時(shí)間Tmin滿足式(11)。

基于上述理論分析可知，不同分辨率圖像在工作頻率100 MHz 的條件下本算法運(yùn)行時(shí)間如表4所示。

表4 工作頻率100 MHz 不同分辨率本算法運(yùn)行時(shí)間

2.2 硬件資源消耗

基于上述理論分析可知，本算法需要消耗2 組片上RAM 和3 組FIFO 資源。 對(duì)一副N×M(N列M行)圖像，各存儲(chǔ)器消耗位寬及深度分析如下。

對(duì)于N×M圖像，通過8 鄰域判斷連通的情況，理論上連通域個(gè)數(shù)至多可達(dá)N/2×M/2，但實(shí)際上幾乎不會(huì)出現(xiàn)這種情況，而且當(dāng)出現(xiàn)這種情況時(shí)，也沒有對(duì)其做連通域標(biāo)記意義。 同時(shí)若二值圖像已經(jīng)過濾波或形態(tài)學(xué)處理，那么連通域個(gè)數(shù)至多為N/6×M/6。 若采用單個(gè)有效區(qū)域大小至少為N/100×M/100 個(gè)像素點(diǎn)，則連通域個(gè)數(shù)至多為100/6×100/6≈278。

下面以分辨率為1 920×1 080 pixel 的全高清(FHD)圖像為例，對(duì)算法進(jìn)行資源需求分析。 因存儲(chǔ)器均通過二進(jìn)制方式對(duì)其進(jìn)行存儲(chǔ)，通過式(12)可求出十進(jìn)制數(shù)X所需位寬B。

連通域檢測(cè)模塊資源消耗:片上RAM0 數(shù)據(jù)位寬44(4×11)bit；片上RAM1 數(shù)據(jù)位寬22(2×11)bit。 其深度均需根據(jù)最大連通域個(gè)數(shù)確定。 經(jīng)過MATLAB 實(shí)驗(yàn)分析及多次實(shí)驗(yàn)，得出通常情況下連通域個(gè)數(shù)小于278，F(xiàn)IFO_RUN 僅為防止兩游程太近丟失數(shù)據(jù)，深度Rf設(shè)為N/20≈96 即可。 為防止連通域過多，結(jié)合二進(jìn)制位寬特性，本文將最大連通域個(gè)數(shù)設(shè)為512，Rf設(shè)為128。 FIFO_DOWN 存儲(chǔ)結(jié)束連通域地址信息，數(shù)據(jù)位寬9bit，深度512bit。

包圍盒快速顯示模塊資源消耗:color 數(shù)值和FIFO_ROW 存儲(chǔ)行特征信息，需數(shù)據(jù)位寬35(3×11+2)bit，深度1 024(2×512)bit。 本算法連通域檢測(cè)過程存儲(chǔ)器資源需求如表5 所示。

表5 本算法存儲(chǔ)器資源需求

從表5 可知，本算法在檢測(cè)模塊消耗片上資源約41.63 kbit，在包圍盒快速顯示模塊消耗片上資源35 kbit，總共消耗片上資源約76.63 kbit。 本算法運(yùn)算過程僅利用FIFO_RUN 和RAM1 中數(shù)據(jù)，而RAM0 存儲(chǔ)包圍盒特征信息。 若特征信息需要連通域面積時(shí)，僅需將RAM0 中{up，left}數(shù)據(jù)更改為連通域中心坐標(biāo)，{down，right}數(shù)據(jù)更改為連通域面積信息即可求出各連通域面積。

3 實(shí)驗(yàn)結(jié)果及分析

為驗(yàn)證本算法準(zhǔn)確性，選取了含多種特殊形狀的圖像進(jìn)行實(shí)驗(yàn)。 并通過ChipScope pro 14.7 和Modelsim 10.1 對(duì)算法運(yùn)行時(shí)間進(jìn)行驗(yàn)證；通過VGA顯示對(duì)包圍盒標(biāo)記進(jìn)行驗(yàn)證。

3.1 時(shí)間消耗及標(biāo)記結(jié)果

為了驗(yàn)證本算法運(yùn)行時(shí)間準(zhǔn)確性，首先通過Modelsim 進(jìn)行驗(yàn)證算法運(yùn)行時(shí)間。 模擬輸入64×64 pixel 圖像(最后一行無前景像素)，共3 個(gè)連通域(一個(gè)普通型、一個(gè)“W”型和一個(gè)“U”型)，進(jìn)行了仿真實(shí)驗(yàn)，得到連通域檢測(cè)模塊運(yùn)行時(shí)序圖，如圖6 所示。

圖6 連通域檢測(cè)模塊運(yùn)行時(shí)序圖

由圖6 可知，l＝1，n＝3，n0＝3，t＝10 ns。 (N×M-N)×t＝40 320 ns，td＝(l+2)×t＝30 ns，tr＝(n+n0+1)×t＝70 ns，滿足式(10)。 但算法實(shí)際運(yùn)行時(shí)間應(yīng)為Tmin＝40.96 μs。

為了進(jìn)一步驗(yàn)證本算法運(yùn)行時(shí)間準(zhǔn)確性，接下來通過ChipScope pro 抓取信號(hào)來驗(yàn)證上板后的準(zhǔn)確性，采用分辨率為480×320 pixel 圖像(最后一行無前景像素)進(jìn)行實(shí)驗(yàn)，其圖像包含52 個(gè)字母(含大小寫)，得到連通域檢測(cè)模塊運(yùn)行時(shí)序圖如圖7 所示。

圖7 算法運(yùn)行時(shí)序圖

由圖7 可知，所有區(qū)域檢測(cè)完成信號(hào)產(chǎn)生后需77 個(gè)周期產(chǎn)生結(jié)束信號(hào)。l＝1，n＝52，n0＝21，td＝(l+2)×t＝3t，tr＝(n+n0+1)×t＝74t；可以得出算法運(yùn)行時(shí)間滿足式(10)，但實(shí)際算法運(yùn)行時(shí)間應(yīng)為Tmin≈2.621 ms。

在確定算法運(yùn)行時(shí)間準(zhǔn)確后，還需對(duì)標(biāo)記結(jié)果進(jìn)行驗(yàn)證，對(duì)含52 個(gè)字母圖像進(jìn)行實(shí)驗(yàn)，F(xiàn)PGA 開發(fā)板上標(biāo)記結(jié)果，如圖8(a)所示，在MATLAB 上進(jìn)行相同處理，結(jié)果如圖8(b)所示。 為了針對(duì)圖片環(huán)境和連通域更為復(fù)雜的情況，對(duì)含15 個(gè)不規(guī)則圖案的圖像進(jìn)行實(shí)驗(yàn)，F(xiàn)PGA 開發(fā)板上標(biāo)記結(jié)果，如圖8(c)所示，在MATLAB 上進(jìn)行相同處理，結(jié)果如圖8(d)所示。

對(duì)比圖8(a)和圖8(b)、圖8(c)和圖8(d)可知，在FPGA 上對(duì)圖像標(biāo)記的結(jié)果與在MATLAB 上標(biāo)記的結(jié)果完全一致，說明在本算法能準(zhǔn)確地對(duì)各連通域進(jìn)行標(biāo)記。

圖8 實(shí)驗(yàn)結(jié)果圖

為驗(yàn)證包圍盒交叉時(shí)標(biāo)記的準(zhǔn)確性，將對(duì)含包圍盒交叉情況的圖像進(jìn)行實(shí)驗(yàn)，其中行特征信息及排序情況，通過ChipScope pro 抓取相關(guān)信號(hào)，結(jié)果如圖9 所示，在MATLAB 上進(jìn)行相同處理，結(jié)果如圖10 所示，原圖如圖11(a)所示，二值化結(jié)果圖如圖11(b)所示，F(xiàn)PGA 開發(fā)板上標(biāo)記結(jié)果，如圖11(c)所示，在MATLAB 上進(jìn)行相同處理，結(jié)果如圖11(d)所示。

圖9 FPGA 行特征信息排序結(jié)果

圖10 MATLAB 行特征信息排序結(jié)果

圖11 包圍盒交叉實(shí)驗(yàn)結(jié)果圖

對(duì)比圖9 和圖10 可知，在FPGA 上對(duì)行特征信息提取及排序的結(jié)果與在MATLAB 上實(shí)現(xiàn)的結(jié)果完全一致，說明行特征信息提取及排序模塊設(shè)計(jì)正確；對(duì)比圖11(c)和圖11(d)可知，在FPGA 上對(duì)圖像標(biāo)記的結(jié)果與在MATLAB 上標(biāo)記的結(jié)果完全一致，驗(yàn)證了在包圍盒交叉情況下包圍盒快速顯示模塊設(shè)計(jì)的準(zhǔn)確性。

3.2 實(shí)驗(yàn)對(duì)比分析

在算法運(yùn)行時(shí)間上，為了與文獻(xiàn)[4]相比，本文選擇了與文獻(xiàn)[4]相同的工作頻率(100 MHz)，并選取了相同分辨率(512×512 pixel)的圖像進(jìn)行實(shí)驗(yàn)。兩種不同算法運(yùn)行時(shí)間如表6 所示。

表6 不同算法運(yùn)行時(shí)間對(duì)比

從表6 可以看出，文獻(xiàn)[4]運(yùn)行最小時(shí)間大于本算法運(yùn)行最大時(shí)間，且運(yùn)算時(shí)間的最小值與最大值相差較大。 這是因?yàn)槲墨I(xiàn)[4]在運(yùn)算過程中需要處理等價(jià)標(biāo)號(hào)與臨時(shí)標(biāo)號(hào)，帶來了額外時(shí)間消耗，同時(shí)多游程情況下等價(jià)標(biāo)號(hào)與臨時(shí)標(biāo)號(hào)過大，導(dǎo)致算法運(yùn)行時(shí)間成倍增加。

在資源消耗上，為了公平比較各算法資源消耗，假設(shè)所有算法均對(duì)N×M圖像進(jìn)行連通域標(biāo)記。 其中Rr表示單行游程上限(Rowruns)，Ar表示游程總數(shù)(Allruns)，A′r表示優(yōu)化后游程總數(shù)(A′r≤Ar)，Rw表示游程數(shù)據(jù)位寬(Runswidth)，Dw表示特征數(shù)據(jù)位寬(Datawidth)。Rr＝N/2，LR＝「log2Rr」，Ar＝Rr×M，LA＝「log2Ar」，Rw＝Dm+2×Dn，(Dn＝「log2N」，Dm＝「log2M」)，Rf＝「N/20」，其中Dw由算法自身確定。幾種不同算法對(duì)連通域標(biāo)記所需片上資源如表7所示。

從表7 可知，相比文獻(xiàn)[8，10-11，13]，雖然本算法在提取特征信息時(shí)需要緩存片上RAM 地址信息，但在其他存儲(chǔ)器方面具有更低的資源消耗。 相比文獻(xiàn)[10，13]，本算法沒有等價(jià)標(biāo)號(hào)與臨時(shí)標(biāo)號(hào)，降低了算法運(yùn)行的復(fù)雜性。 相比文獻(xiàn)[11]僅支持單個(gè)目標(biāo)或已知個(gè)數(shù)的多個(gè)目標(biāo)檢測(cè)，本算法在功能上具有更大的優(yōu)勢(shì)。 此外，本算法引入RAM1(上一行前景像素列信息)使得在標(biāo)記特殊圖案時(shí)有更高的準(zhǔn)確率。 當(dāng)最后一行無前景像素時(shí)，各算法時(shí)間均為T0＝M×N×t。

表7 不同算法資源消耗對(duì)比

為了方便比較不同算法具體的資源消耗，參照文獻(xiàn)[8，10-11，13]以三種不同分辨率的圖像為例對(duì)幾種算法進(jìn)行資源分析比較。 其中在資源消耗分析時(shí)，由于部分參數(shù)過大，結(jié)合實(shí)際情況，最終將文獻(xiàn)[10]的A′r設(shè)為4 096，LA設(shè)為14；而將文獻(xiàn)[11]的LA設(shè)為10，進(jìn)行分析。 不同算法資源消耗如表8 所示。

表8 不同算法資源消耗對(duì)比

由表8 可知，與文獻(xiàn)[8，10-11，13]的算法相比，本算法在相同分辨率圖像上進(jìn)行連通域檢測(cè)標(biāo)記所需資源最少。 同時(shí)算法增加了快速顯示包圍盒標(biāo)記，使圖像在顯示同時(shí)完成包圍盒標(biāo)記。

4 結(jié)論

本文在傳統(tǒng)連通域標(biāo)號(hào)標(biāo)記算法的基礎(chǔ)上，結(jié)合包圍盒特點(diǎn)，提出了一種連通域特征分析算法——基于FPGA 的快速連通域標(biāo)記算法。 在檢測(cè)過程中，以游程為處理單元實(shí)時(shí)合并連通游程并以包圍盒特征信息格式存儲(chǔ)到片上RAM，不產(chǎn)生等價(jià)標(biāo)號(hào)與臨時(shí)標(biāo)號(hào)；在標(biāo)記過程中，將排序后的行特征信息疊加在圖像上，可實(shí)現(xiàn)包圍盒標(biāo)記隨圖像顯示而顯示。 同時(shí)，在保證資源不變的情況下，可根據(jù)需求更換連通域特征信息(包圍盒或面積)。 實(shí)驗(yàn)結(jié)果表明在連通域檢測(cè)過程中，相比其他算法，本算法在時(shí)間和資源方面均有一定優(yōu)勢(shì)；同時(shí)提出的包圍盒快速顯示方法，在包圍盒交叉情況下亦能成功顯示。 本算法僅存儲(chǔ)連通域特征信息，并未對(duì)前景像素進(jìn)行標(biāo)號(hào)存儲(chǔ)，在一定程度上降低了算法運(yùn)行時(shí)間及資源消耗，雖然不支持提取連通域周長(zhǎng)，但可根據(jù)需求對(duì)連通域包圍盒或面積進(jìn)行提取，所以在目標(biāo)實(shí)時(shí)檢測(cè)系統(tǒng)中具有一定的實(shí)用價(jià)值。