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

(1.昆明理工大學信息工程與自動化學院，云南 昆明650500；2.昆明理工大學云南省計算機技術應用重點實驗室，云南 昆明650500)

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

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

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

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

1 快速連通域標記算法設計

1.1 新的連通域標記算法流程

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

圖1 快速連通域標記算法流程圖

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

1.2 FPGA 系統(tǒng)總體設計

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

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

圖2 系統(tǒng)總體結構框圖

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

1.3 連通域檢測模塊設計

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

1.3.1 圖像掃描

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

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

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

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

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

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

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

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

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

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

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

1.3.3 行特征信息提取

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

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

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

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

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

1.4 包圍盒快速顯示模塊設計

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

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

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

表3 包圍盒快速標記過程

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

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

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

2 算法運行時間及硬件資源分析

2.1 算法運行時間

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

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

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

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

結合實際情況，算法運行時間應大于等于圖像掃描時間，故算法最小運行時間Tmin滿足式(11)。

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

表4 工作頻率100 MHz 不同分辨率本算法運行時間

2.2 硬件資源消耗

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

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

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

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

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

表5 本算法存儲器資源需求

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

3 實驗結果及分析

為驗證本算法準確性，選取了含多種特殊形狀的圖像進行實驗。 并通過ChipScope pro 14.7 和Modelsim 10.1 對算法運行時間進行驗證；通過VGA顯示對包圍盒標記進行驗證。

3.1 時間消耗及標記結果

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

圖6 連通域檢測模塊運行時序圖

由圖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)。 但算法實際運行時間應為Tmin＝40.96 μs。

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

圖7 算法運行時序圖

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

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

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

圖8 實驗結果圖

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

圖9 FPGA 行特征信息排序結果

圖10 MATLAB 行特征信息排序結果

圖11 包圍盒交叉實驗結果圖

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

3.2 實驗對比分析

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

表6 不同算法運行時間對比

從表6 可以看出，文獻[4]運行最小時間大于本算法運行最大時間，且運算時間的最小值與最大值相差較大。 這是因為文獻[4]在運算過程中需要處理等價標號與臨時標號，帶來了額外時間消耗，同時多游程情況下等價標號與臨時標號過大，導致算法運行時間成倍增加。

在資源消耗上，為了公平比較各算法資源消耗，假設所有算法均對N×M圖像進行連通域標記。 其中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由算法自身確定。幾種不同算法對連通域標記所需片上資源如表7所示。

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

表7 不同算法資源消耗對比

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

表8 不同算法資源消耗對比

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

4 結論

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