面向FPGA的連通域快速標記方法

王 凡，周國清，張榮庭，劉德全

1.天津大學(xué) 精密儀器與光電子工程學(xué)院，天津300072

2.天津大學(xué) 遙感研究中心，天津300072

3.桂林理工大學(xué) 廣西空間信息與測繪重點實驗室，廣西 桂林541004

4.天津大學(xué) 微電子學(xué)院，天津300072

1 引言

我國海域遼闊，利用衛(wèi)星對海面艦船目標進行檢測在軍用和民用領(lǐng)域均受到越來越多的重視，在衛(wèi)星上完成艦船目標實時檢測，可以避免星地傳輸和地面處理的巨大壓力。在圖像處理、目標檢測、模式識別等領(lǐng)域，連通區(qū)域標記算法常作為目標候選區(qū)域特征提取環(huán)節(jié)的必要步驟而有著廣泛應(yīng)用。在基于光學(xué)遙感圖像的艦船檢測的工程應(yīng)用中，使用現(xiàn)場可編程門陣列（Field Programmable Gate Array，F(xiàn)PGA）實現(xiàn)圖像處理與目標檢測等功能。與可以流水線實現(xiàn)的圖像濾波、閾值分割等算法相比，連通域標記算法往往需要消耗更多的硬件資源與處理時間。因此，如何高效地實現(xiàn)連通域標記算法是滿足實時性要求的關(guān)鍵。

Rosenfeld 等人[1]提出的兩遍掃描算法是經(jīng)典的連通域標記算法。趙菲等人[2]提出基于等價標號的二次掃描連通域標記算法，結(jié)合基于像素掃描方法和基于游程編碼方法的優(yōu)點，按像素逐行掃描，以線段形式進行標記。王堯等人[3]采用單次掃描的連通域標記算法，在掃描過程中記錄當(dāng)前元素鄰域內(nèi)的標號。凌璐祥[4]提出游程-連通域數(shù)據(jù)映射結(jié)構(gòu)，采用三個雙端口RAM作為保存媒介，分別保存當(dāng)前行游程、上一行游程和連通域，無需建立等價表。黃金寶等人[5]提出基于輪廓跟蹤的一次掃描連通域標記優(yōu)化算法。王凱等人[6]設(shè)計了基于圖像分塊的連通域標記算法，將連通域標記與去噪處理相結(jié)合。馮海文等人[7]通過最小標號傳播處理，將多次掃描算法改進為一次掃描算法。張國和等人[8]提出了一種適于硬件的快速連通域標記算法，該算法以游程為基本單位，采用一次掃描和等價游程對合并的方式完成連通域標記。譚許彬等人[9]設(shè)計一種基于FPGA的連通域標記電路，通過對圖像進行一次像素掃描，標記連通域并統(tǒng)計參數(shù)信息。王凱等人[10]利用游程編碼優(yōu)化標號生成算法，減小臨時標號數(shù)量和等價表長度，并基于FPGA實現(xiàn)。文獻[11]提出游程和鏈表結(jié)合的連通域標記方法，以游程技術(shù)分配臨時標簽，再利用鏈表結(jié)構(gòu)構(gòu)造等價標簽之間的關(guān)系。文獻[12]設(shè)計了一個圖像組件標記和特征提取模塊并在FPGA上實現(xiàn)。文獻[13]設(shè)計了基于FPGA的單次掃描連通域標記架構(gòu)。文獻[14]提出了一種通過將圖像分割成切片來實現(xiàn)加速的單通道連通分量分析架構(gòu)。文獻[15-16]也提出了基于FPGA 的連通域標記方法設(shè)計。以上方法中一部分方法[1，2，6]需要對圖像進行兩次或多次掃描來完成連通域標記，導(dǎo)致了處理時間的增加，不利于滿足實時性要求；一部分方法[3，5，7-12，14-16]則對圖像進行一次掃描，但需要借助臨時標記表來進行連通域標記，使得硬件資源的消耗量增加。

本文在對近些年的二值圖像連通域標記算法進行總結(jié)與分析的基礎(chǔ)上，設(shè)計一種基于游程的連通域快速標記算法，基于FPGA 實現(xiàn)，并作為遙感圖像艦船檢測硬件系統(tǒng)的一個模塊。結(jié)合遙感圖像艦船目標的特點，針對現(xiàn)有方法在重復(fù)掃描和臨時標記表上花費較多的處理時間與硬件資源的問題，該方法以游程為單位對像素進行批量處理，不產(chǎn)生臨時標記表，對圖像進行一次掃描完成連通域標記。結(jié)合星上檢測應(yīng)用中對實時性的要求，設(shè)計基于FPGA的硬件架構(gòu)，描述關(guān)鍵模塊，對所設(shè)計的硬件模塊從資源占用與時間消耗兩方面進行優(yōu)化設(shè)計，并進行仿真分析和實驗驗證。結(jié)果表明，該模塊能高效實現(xiàn)連通域標記，與文獻[9]相比運行速度提高了約1 倍，與文獻[8]相比資源消耗顯著降低，滿足工程應(yīng)用的要求。

2 二值圖像連通域快速標記算法

2.1 算法基礎(chǔ)

文獻[17]將連通域標記算法分為一次掃描算法、二次掃描算法和多次掃描算法。目前常用的一次掃描算法通常是以游程為基本單位的處理方法，二次掃描算法和多次掃描算法通常是以像素為基本單位的處理方法。以像素為單位的描述方法需要逐像素處理，以游程為單位的描述方法則需要對像素進行批量處理，因此以游程為基本單位的處理方法往往比以像素為基本單位的處理方法更高效。

基于游程的算法將二值圖像每一行中連續(xù)的前景像素視為一個游程，并記錄游程的起點、終點、所在行以及賦予的標記；然后判斷相鄰行的游程是否存在連通，如果是則標記為等價對；之后遍歷游程的標記，將等價對中的游程進行標記合并。對于二值圖像，游程開始和結(jié)束的判定依據(jù)是：當(dāng)目標像素與前一個像素的值構(gòu)成“01”時，表示游程的開始；當(dāng)目標像素與前一個像素的值構(gòu)成“10”時，表示游程的結(jié)束。對于8 鄰域連通情況，判斷當(dāng)前行的游程與上一行的游程是否連通的關(guān)系式如下：

其中，Y0、Y1表示當(dāng)前行游程的起點和終點列坐標，y0、y1表示上一行游程的起點和終點列坐標。

當(dāng)判定兩個游程存在連通情況時，算法通常將這兩個游程標記為等價對，并將等價關(guān)系存儲到臨時標記表中，再通過遍歷臨時標記表來完成等價對的標記統(tǒng)一。臨時標記表的存在增加了方法的時間和資源消耗。

本文對多幅遙感圖像中艦船目標的特點進行分析，如圖1所示艦船目標的形狀通常比較規(guī)則，不存在類似圖2中的復(fù)雜的連通域情況，連通域中的游程通過相鄰行之間的標記傳遞即可完成標記統(tǒng)一，因此不需要借助臨時標記表。本文借鑒已有研究中一次掃描的算法，對連通域標記方法進行設(shè)計，以游程為單位對像素進行批量處理，不記錄等價對，不產(chǎn)生標記表，在像素掃描過程中逐行地記錄游程信息，同時并行地對已記錄的游程進行標記合并處理。

圖1 遙感圖像中的艦船目標

圖2 復(fù)雜的連通域

2.2 連通域快速標記算法設(shè)計

在圖像連通域的描述中，常用4 鄰域連通和8 鄰域連通兩種方法，因為8 鄰域連通更為全面，通用性好[18]，所以本文以8鄰域連通進行連通域快速標記的設(shè)計，采用光柵掃描的方式，以游程為基本單位對像素進行批量統(tǒng)計。如圖3所示，本文設(shè)計的連通域快速標記算法包括游程記錄、連通游程標記合并和連通域的特征提取幾個主要環(huán)節(jié)。

圖3 連通域標記算法流程圖

（1）游程記錄。對二值圖像進行光柵掃描，即逐行地從左到右讀入圖像像素，判定行內(nèi)的所有游程，并依次賦予游程不同的標記編號，將各個游程的標記編號、左右端點坐標和行坐標記錄到數(shù)組mem_a 中。對于每行的開始處和結(jié)束處，若每行的第一個像素的值為1，則記錄為一個游程的開始；若每行的最后一個像素的值為1，則記錄為一個游程的結(jié)束。

（2）連通游程標記合并。從掃描到第三行像素起，將之前兩行中的游程依次進行端點坐標的比較。若滿足關(guān)系式（1），則判定游程連通，將上一行的游程標記賦予當(dāng)前游程。若多個游程之間存在連通的情況，則將這些游程中的最小的標記賦予其他游程，如圖4 和圖5 所示。將所有的連通游程合并完成后，具有同一標記的游程便同屬一個連通區(qū)域。

圖4 相鄰行游程之間可能存在的連通關(guān)系

圖5 連通游程標記合并

（3）特征提取。對已完成標記合并的游程進行統(tǒng)計以提取連通域的特征，并且判斷已經(jīng)掃描過的圖像中的連通域是否都完成了標記。如果沒有完成，則繼續(xù)第二步的等價游程標記合并；如果已完成，則將提取到的連通域特征輸出。

3 基于FPGA的硬件架構(gòu)設(shè)計

3.1 FPGA硬件結(jié)構(gòu)

如圖6所示為艦船目標檢測環(huán)節(jié)的硬件架構(gòu)，其中連通域標記是重要步驟，是進行特征提取的前提和基礎(chǔ)。如圖7所示為本文設(shè)計的基于FPGA的連通域快速標記模塊的硬件架構(gòu)，包括游程信息記錄和連通游程標記合并兩部分。本文采用1 000×500大小的光學(xué)遙感圖像，對其中的艦船目標的連通區(qū)域進行快速標記。經(jīng)過預(yù)處理和分割處理后的二值圖像通過RAM讀寫模塊以光柵掃描的方式逐個像素地輸入到硬件電路中，以連續(xù)的兩個像素數(shù)據(jù)為一組輸入到游程信息記錄模塊。游程信息記錄模塊判斷游程的開始和結(jié)束，生成游程標記，并將游程的標記、左右端點坐標與行坐標記錄到存儲器mem_a 中，將各行的游程數(shù)目累加起來記錄到存儲器k 中。從記錄完第二行的游程開始，連通游程標記合并模塊判斷前兩行的游程之間是否連通，將連通的游程進行標記合并，不連通的游程跳過。之后，連通域特征提取模塊讀取游程信息與游程連通判斷結(jié)果，如果有連通域被記錄完，則輸出提取到的該連通域的特征。

圖6 艦船目標檢測環(huán)節(jié)的硬件架構(gòu)

圖7 連通域快速標記模塊硬件架構(gòu)

在連通域標記的電路中，游程信息記錄模塊和連通游程標記合并模塊是關(guān)鍵模塊，下文將分別進行詳細的設(shè)計說明，并且對后續(xù)模塊的設(shè)計思路進行簡要說明。

3.2 游程信息記錄模塊

該模塊的設(shè)計思路為：對輸入的兩個連續(xù)像素，依據(jù)它們的值判斷游程的開始點和結(jié)束點；并根據(jù)RAM讀寫模塊的讀地址判斷行坐標；數(shù)組mem_a 的一個元素對應(yīng)一個游程的信息。

定義一個存儲位寬為40位，存儲深度為1 536的存儲器mem_a，其每個存儲單元存儲一個游程的全部信息，高11 位存儲游程的標記，之后9 位存儲游程的行坐標，之后10位存儲左端點坐標，最后10位存儲右端點坐標。定義一個存儲器地址信號j，其值在每存入一個游程信息后加1。定義一個行計數(shù)器信號i，其值在每讀入一行像素數(shù)據(jù)后加1。定義一個存儲位寬為11位，存儲深度為500的存儲器k，記錄各行及其以前行的游程數(shù)目之和，即k[i]與k[i-1]之差為第i 行的游程數(shù)目。所定義的相關(guān)信號的信息如表1所示。

表1 游程信息記錄模塊的信號

該模塊的工作過程為：通過讀寫控制模塊依次讀取圖像像素，兩個reg 型變量將相鄰的兩個像素進行存儲，在同時傳遞給游程判斷模塊。當(dāng)輸入的相鄰兩個像素的值滿足“01”的組合時，產(chǎn)生寫使能信號，將當(dāng)前的值為1的像素點的行坐標和列坐標，以及生成的標記值寫入mem_a 存儲器中；當(dāng)輸入的相鄰兩個像素的值滿足“10”的組合時，產(chǎn)生寫使能信號，將當(dāng)前的值為1 的像素點的列坐標寫入mem_a 存儲器中，并使j 的值增加1。通過RAM的讀地址對行坐標進行計數(shù)，并計算當(dāng)前的列坐標；像素的行坐標、列坐標與存儲地址的關(guān)系為：

其中，x 表示行坐標，y 表示列坐標，raddr 表示存儲地址，實驗用圖像每行像素數(shù)量為1 000。mem_a 存儲器在接受到寫使能的信號后，記錄當(dāng)前游程的信息，當(dāng)接收了游程開始點和結(jié)束點兩次的寫使能信號后，當(dāng)前游程的全部信息才記錄完畢。

3.3 連通游程標記合并模塊

該模塊的設(shè)計思路為：讀取行計數(shù)信號，從行計數(shù)大于等于3起，從mem_a 存儲器中讀取前兩行的游程信息，從左到右依次比較相鄰行的游程的端點坐標，以判定游程是否連通，如果游程連通，則對標記進行合并。

定義兩個integer型變量m 和n 作為從存儲器mem_a中讀取數(shù)據(jù)的地址，用于遍歷各相鄰行的游程，m 和n的取值范圍如下所示；

定義兩個計數(shù)器信號count_1 和count_2，用于判斷游程連通情況時的時序控制；定義一個計數(shù)器信號num，用于記錄游程之間存在連通情況的數(shù)目。信號的相關(guān)信息如表2所示。

表2 連通域標記合并模塊的相關(guān)信號

該模塊的工作過程為：根據(jù)行計數(shù)信號i 的值將存儲器k 的值讀取出來，經(jīng)過計算得到m 與n 的值。連通判斷模塊讀取mem_a[m]和mem_a[n]的信息并進行比較，若存在連通情況則將合并標記按對應(yīng)的地址寫入存儲器mem_a 中，并使num 加1；若不存在連通情況則信號num 不變。

3.4 后續(xù)模塊的處理

游程連通判別模塊的行計數(shù)信號i 和連通計數(shù)信號num 輸入到特征提取模塊。隨著信號i 每變化一次，特征提取模塊從存儲器mem_a 中依次讀取各個游程的信息進行統(tǒng)計，以提取連通域的特征。同時對信號num進行一次比較，若其值不為0 且不變，則表明已有連通域被完整記錄，將所提取的連通域的特征輸出；若信號num 的值有變化，則表明當(dāng)前涉及的連通域還沒有被記錄完整，繼續(xù)進行特征提取。

目標判別模塊對已提取的特征進行判斷，將不滿足條件的連通域排除，將滿足條件的連通域框選出來。

4 實驗分析

本文采用Xilinx 公司的Virtex-7 系列FPGA 作為硬件平臺，采用Vivado設(shè)計套件作為開發(fā)環(huán)境。采用Verilog硬件描述語言進行連通域快速標記模塊設(shè)計和仿真。圖8 所示為連通域快速標記模塊的仿真時序圖。圖9所示為存儲器mem_a 的部分值的時序變化情況。如mem_a[259] 的初值為0，之后記錄的游程信息為208349fa9c，經(jīng)過連通游程標記合并后其值變?yōu)?5e349fa9c，所記錄的游程其標記由260變?yōu)?7。

下文將從時間消耗、資源占用和處理結(jié)果等方面進行分析。

4.1 時間消耗

假設(shè)所處理的圖像高為H ，寬為W ，每行所包含的游程數(shù)目不超過n，電路工作的時鐘周期為clk，則兩行游程連通情況的處理時間最大為(2n-1)×clk。每行像素數(shù)目為W ，讀入一行像素的時間為W 個時鐘周期。本文的連通域標記電路模塊從掃描到第三行像素數(shù)據(jù)起，比較前兩行游程的連通情況。在讀完當(dāng)前一行像素前，已經(jīng)處理完前兩行的游程連通情況。當(dāng)一幅圖像的全部像素被讀入后，最多還需要(2n-1)×clk 的時間來處理最后兩行的游程連通情況。因此，該連通域標記電路處理一幅圖像的時間不超過(W×H+2n-1)×clk。

因為對二值圖像的連通域標記必須要將圖像至少掃描一遍，所以該處理環(huán)節(jié)的處理時間最少為掃描整幅圖像的時間Tmin=W×H×clk 。本文的設(shè)計在處理時間上已無限接近Tmin，若圖像最后一行的像素值均為0，則連通域標記的處理時間等于Tmin。文獻[9]設(shè)計所需處理時間為t=(W×H×2+L×4)×clk，其中L 為連通域的最大上限。與文獻[9]相比，本文的設(shè)計的處理時間提高了約1倍。

4.2 資源耗費

本文設(shè)計的連通域標記模塊對資源的耗費主要在于對信息的存儲，如表3所示，為對1 000×500大小的二值圖像進行連通域標記所需的存儲資源。其中，對于游程記錄存儲器mem_a 的定義，由于圖像實際中的游程數(shù)遠小于理論值W×H/4，根據(jù)對多幅艦船遙感圖像中的游程數(shù)量統(tǒng)計定義一個合理存儲深度的存儲器，本文對1 000×500大小的圖像定義的存儲器深度為1 536位。

表3 存儲資源耗費

對于游程信息的統(tǒng)計和整理，文獻[8]的方法需要5個存儲器記錄臨時標記集合中所有標記的排列順序，1個存儲器記錄臨時標記集合的結(jié)束點，1個存儲器記錄臨時標記集合中所有標記的排列順序。而本文方法只需要1個游程信息存儲器和1個游程數(shù)目存儲器即可完成游程的記錄和整理，對存儲資源的消耗更小。在圖像大小為2 048×1 536 的情況下，兩種方法的存儲資源消耗如表4 所示，相比之下，本文的設(shè)計對資源的消耗大幅降低。

圖8 連通域快速標記模塊仿真時序圖

圖9 mem_a 中的部分值

表4 存儲資源消耗對比

4.3 連通域標記處理結(jié)果

選取多幅艦船目標的遙感圖像進行實驗，其中部分結(jié)果如圖10 所示，每行為一幅圖像的二值圖（左）和最終的艦船檢測結(jié)果圖（右）。圖像大小均為1 000×500，工作頻率為f=100 MHz，由于這兩幅圖像的最后一行像素中不存在游程，故在對整幅圖像進行一次掃描的時間內(nèi)，連通域標記操作也順利完成，時間消耗為5 ms，滿足工程應(yīng)用中的實時性要求。

圖10 二值圖像及檢測結(jié)果

5 總結(jié)

本文提出了一種面向遙感領(lǐng)域艦船目標檢測的連通域標記方法及其硬件設(shè)計。本文采取的連通域標記策略，只需要掃描整幅圖像一次，記錄各行的游程信息并合并連通游程的標記，后續(xù)對連通域進行特征提取時依次統(tǒng)計相同標記下的游程信息即可。本文的方法不產(chǎn)生臨時標記表，在像素掃描過程中對已記錄的游程完成標記合并。在運行時間方面，本文的設(shè)計對于最后一行都是背景像素的圖像可以在一次掃描像素的過程中完成連通域標記，對于最后一行包含游程的圖像可以在一次掃描像素后的有限個時鐘周期內(nèi)完成連通域標記。在資源占用方面，本文的設(shè)計只需要一個游程信息存儲器和一個游程數(shù)目存儲器即可完成對全部游程的信息統(tǒng)計，不產(chǎn)生臨時標記表，對存儲資源的消耗很小。因此，本文提出的對于遙感圖像艦船檢測中的連通域標記方法和硬件設(shè)計是簡潔高效的。