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

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

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

2.天津大學 遙感研究中心，天津300072

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

4.天津大學 微電子學院，天津300072

1 引言

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

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

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

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

2.1 算法基礎

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

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

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

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

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

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

圖2 復雜的連通域

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

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

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

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

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

圖4 相鄰行游程之間可能存在的連通關系

圖5 連通游程標記合并

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

3 基于FPGA的硬件架構設計

3.1 FPGA硬件結構

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

圖6 艦船目標檢測環節的硬件架構

圖7 連通域快速標記模塊硬件架構

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

3.2 游程信息記錄模塊

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

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

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

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

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

3.3 連通游程標記合并模塊

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

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

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

表2 連通域標記合并模塊的相關信號

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

3.4 后續模塊的處理

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

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

4 實驗分析

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

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

4.1 時間消耗

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

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

4.2 資源耗費

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

表3 存儲資源耗費

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

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

圖9 mem_a 中的部分值

表4 存儲資源消耗對比

4.3 連通域標記處理結果

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

圖10 二值圖像及檢測結果

5 總結

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