面向文本檢測的NMS加速器設計

屠程力，陳章進，2，喬 棟

(1.上海大學 微電子研究與開發中心，上海 200444；2.上海大學 計算中心，上海 200444)

0 引 言

對自然場景中的文本圖片進行批量檢測是自動駕駛和場景分類等工業應用的基礎，鑒于自然場景中的文本有寬高比差異大和背景光照復雜等特點，使用神經網絡提取特征并輸出多個高置信度候選框的深度學習檢測方法受到廣泛歡迎。該方法根據候選框提取的方式不同分為區域建議，如SegLink[1]、RRD[2]和分割融合，如EAST[3]、SPC-Net[4]。鑒于神經網絡輸出的是多個置信度不同的候選框，因此通過非極大值抑制算法，即NMS(non-maximum suppression)作為后處理算法[5]，將交并比較高而置信度較低的候選框刪去，其偽代碼[6]如下，其中N為交并比閾值，B為檢測框集，S為檢測框對應的置信度集，D為保留的目標框集。

NMS algorithm

(1)D←{}

(2) whileB≠empty do

(3)m←argmaxS

(4)M←b[m]

(5)D←D∪M;B←B-M

(6) forb[i] in B do

(7) if then iou (M,b[i])≥N

(8)B←B-b[i];S←S-s[i]

(9) end if

(10) end for

(11) end while

隨著拍攝像素的提高，經過神經網絡產生的檢測框數由數十個上升到數百個，NMS為高復雜度的貪婪算法，其耗時與檢測框數的平方成正比，因此后處理耗時的比重不斷提高。以EAST算法為例，NMS算法的效果如圖1(a)所示，檢測算法各部分的耗時如圖1(b)所示，NMS作為后處理算法占總檢測時間的41%，嚴重阻礙了檢測算法的實時性。

圖1 NMS算法效果和耗時分析

本文優化候選框的排序方法和單次交并比的計算公式，實現低耗時和低功耗的NMS加速器，可以作為異構加速器與神經網絡檢測并行運算。

1 相關工作

針對NMS算法延遲過大的問題，文獻[7]將后處理與神經網絡中的池化層相結合，利用神經網絡專用框架進行加速，充分利用高效軟件庫的接口，但該方法缺少泛用性，需要針對特定文本數據集進行訓練。為此，在不改變神經網絡結構的前提下，文獻[8]針對語義分割后，檢測框緊密圍繞目標文本的特點，將交并比較高的檢測框以置信度為權重進行坐標合并，在精簡的檢測框集合上進行NMS后處理，但該方法的初衷是降低后處理的計算復雜度，本質仍是基于CPU的順序運算，其延遲較高無法滿足實時性的要求。

目前，對復雜算法進行加速不再局限于CPU平臺[9]，神經網絡各階段的加速平臺開始向TPU[10]和FPGA[11]轉移，受到上述研究影響，對NMS算法進行加速的通常做法是在計算結構上進行改良，以圖2(a)中的3個目標和8個檢測框為待處理示例，3種常見的加速方法如圖2所示。其中圖2(b)為文獻[12]與卷積加速一同提到的高并行NMS方法，通過36個計算單元同時計算出8個檢測框之間的交并比，并將交并比與閾值的比較結果存入8×8的布爾矩陣，最后采用邏輯“與”的運算刪去冗余檢測框。但該方法需要的計算單元與檢測框的平方成正比，同時需要額外的存儲空間存放中間數據。因此為了改進計算單元消耗過大和中間數據存放過多的問題，文獻[13]提出了基于PBBT(position-based bit table)的加速方法，如圖2(c)所示，先將檢測框以置信度從高到低排序，第一次迭代時，以首個檢測框為滑動窗口起始點，將該框與剩下的檢測框依次計算，其結果存儲在PBBT表中，用1 bit狀態位表示與起始點相比是否冗余并附加檢測框的存儲地址，以此大幅節約中間數據的存儲空間，第二次迭代時，以第二個“1”狀態所在的檢測框為起始點重復上一輪操作，直到遍歷完所有“1”狀態框。該方法采用多個滑動窗口來保證每次迭代能同時進行，但需要對檢測框提前排序，導致計算延遲較高。

圖2 3種常見的加速方法

為了避免提前排序帶來的延遲，文獻[14]提出的保留最值辦法，如圖2(d)所示，針對置信度大小排列為亂序的檢測框，加入一個最值模塊，該模塊存儲前一次迭代中置信度最高的n個檢測框，下次迭代從n個檢測框中挑選置信度次高的檢測框，并以該檢測框為起點，逐個比較次高檢測框與其它框的重合程度。鑒于該方法的起始點由前次迭代產生，因此不同迭代之間無法并行計算，另外，容易存在置信度次高框在前一次迭代中滿足交并比條件，歸類為冗余框后刪除，造成最值模塊未命中下一個起點，需要重新迭代尋找高置信度檢測框的步驟。

2 面向文本檢測的加速方法

在采用深度學習方法檢測文本的算法中，神經網絡輸出的是批量隨機位置的檢測框，而隨著檢測框數的逐步提升，以文獻[13]為代表的加速方法并行度較高但需要提前排序，其計算復雜度為O(N2)， 不適合文本檢測任務，而文獻[14]的方法能處理亂序排列的檢測框，但其并行度較低，無法充分利用嵌入式設備并行計算的優勢。

本文首先分析文本檢測檢測框特點，如圖1(a)所示，待消除的冗余框緊密包圍目標框，同時冗余框在橫坐標的位置偏離不超過目標框的長度，在縱坐標的位置偏離不超過目標框的寬度。因此考慮在比較交并比之前，先將檢測框基于位置范圍分類，而檢測框之間的交并比可以在各類之間并行計算，提高整體并行度。按位置范圍將兩個檢測框分為同類的依據如式(1)、式(2)所示，其中x1、y1、L和W分別為前一個檢測框的左下坐標和長寬，x2、y2為下一個檢測框的左下坐標，不等式左右兩邊為該類的4個位置閾值，存入閾值表

(1)

(2)

為了保證數據能夠被高效存儲，借鑒文獻[13]的PBBT(position-based bit table)方法，也采用附帶存儲框地址的位表來記錄檢測框狀態。但由于需要記錄類別信息，因此將比特位擴展到7位，其中前5位用來記錄該框所屬的類別，后2位記錄該檢測框經交并比比較后的3種狀態，其中寫入“0”表示該框交并比超過閾值被刪除且后續不進行其它操作，“1”表示作為起始框與其它框進行比較，“2”表示該框交并比低于閾值并進入下一輪比較。

以圖2(a)為待處理示例，本文方法如圖3所示，一共分為兩階段。第一階段如圖3(a)所示，根據檢測框的坐標位置將檢測框分類，將各類的位置范圍存入閾值表，將該框所屬的類別寫入PBBT，PBBT的存儲順序與檢測框的存儲地址為一對一映射，因此無需改變檢測框的存儲空間，在計算交并比時，直接通過PBBT中存放的地址索引下一個檢測框的坐標信息。

圖3 面向文本檢測的加速方法

第二階段為圖3(b)所示，分類完成后進入檢測框的交并比計算階段，該階段需要包含兩次迭代過程：

第一次迭代按類別進行并行計算，同一類別內的比較采用文獻[13]中單個起始點并行計算多個檢測框的模式，但處理狀態位的方式不同：所有檢測框的狀態初始化為“2”，第一步將首個存儲框的狀態修改為“1”，以該框為起始點與其它框比較交并比，若交并比高于閾值N則不修改檢測框狀態，若低于閾值則將檢測框刪去并將狀態位修改為“0”。第一步中同時比較置信度大小，若起始點置信度低于檢測框而交并比高于閾值，則狀態修改后交換狀態，并將該檢測框為起始點與剩余的檢測框比較交并比，保證狀態“1”所在檢測框為對應目標的置信度最高位置。第一步結束后，若存在狀態“2”的檢測框，則進行第二步，將首個狀態“2”修改為“1”框并與剩下的狀態“2”進行比較。重復上述步驟，直到不存在狀態位“2”時為止。以圖3(b)中的類別3為例，第一步中b3將b8狀態修改為“0”，第二步中的b5將b7狀態修改為“0”，此時不存在狀態“2”檢測框。

第二次迭代，比較所有狀態“1”之間的重復率，刪去超過閾值的檢測框，此時剩余檢測框數較少，無需通過修改狀態“2”的方式保留中間數據。如圖3(b)中的b2檢測框刪去b5檢測框。

基于位置范圍的分類本質是將目標周圍的檢測框視為同類，但同類檢測框可能混入屬于其它目標的檢測框，因此需要第二次迭代，在按類刪去檢測框的基礎上比較剩余檢測框之間的交并比，此時剩余的檢測框少，計算復雜度低。若從內存中取出坐標并計算所消耗的時間視為一次計算延遲，以圖1(a)中3個目標和8個檢測框為例，為了完成一次NMS算法，文獻[13]在比較前需要冒泡排序，所需的延遲為67次。文獻[14]按最值模塊全部命中計算，一共需要32次延遲。而本方法在第一階段中，基于位置范圍的分類需要8次延遲，在第二階段中，類間和類內的計算可以同時進行，因此本文一共需要12次延遲，計算復雜度大幅降低。

3 硬件結構

3.1 系統結構

面向文本檢測的NMS加速器由DDR存儲器、控制模塊、閾值表THT(threshold table)、位表PBBT和計算單元組(computation unit)組成。整體結構如圖4所示。

圖4 系統結構

DDR存儲器存放檢測框的坐標信息和置信度。控制單元根據PBBT中存儲的狀態位是否為“1”，決定迭代起始點并分配檢測框數據，計算單元組負責在各類檢測框之間并行計算交并比，同時比較交并比是否超過閾值、檢測框之間是否完全覆蓋和起始點置信度是否為較大值。

為了更好地說明閾值表和PBBT如何存儲對應數據，將實驗過程的中間數據進行展示，如圖5(a)所示，閾值表用來記錄基于位置范圍分類的閾值信息，XL、XR、YU、YD和C分別表示該類位置區域的左右橫坐標范圍、上下縱坐標范圍和類號。如圖5(b)所示，PBBT負責記錄檢測框的狀態、分類和存儲地址，Key、C、S分別表示偏移地址、類號和狀態。如圖5所示，該實驗一共分為18類檢測框，偏移地址為“01”的檢測框為“02”類的起始檢測框，偏移地址為“02”的檢測框交并比高于閾值被刪除，偏移地址為“FF”的檢測框為待比較檢測框。

圖5 閾值表和位表的存儲示例

加速器啟動時，THT和PBBT被初始化，其中PBBT上的狀態位初始化為“2”，其它位清零，控制單元迭代所有檢測框并基于位置范圍分類：

首先，第一個檢測框視作第一類，將該框的閾值范圍存入THT，將該框的偏移地址和類號寫入PBBT。其次將下一個檢測框與第一類的位置閾值進行比較，若檢測框的左下點坐標在閾值范圍內則視作同類，否則視為第二類并將該類閾值寫入THT。重復上述操作，直到整張圖片的檢測框都遍歷一遍，此時完成基于位置范圍的檢測框分類。在ICDAR2015數據集上的實驗結果表明，分類后的類別數不超過20個，檢測框數不超過900個，因此THT的長度設為32，PBBT的長度設為1024。

基于位置范圍的分類完成后，控制單元負責派發各檢測框數據，考慮到各類之間的交并比可以并行計算，因此結合數據集的實際情況將計算單元組的列數設為8，每列負責一類，最大支持8類檢測框的并行計算。同時將行數設為16，保證在確定起始點后，同類的檢測框之間，支持16個剩余檢測框與起始點同時比較交并比。控制單元根據PBBT中的偏移地址將“1”和“2”狀態的檢測框數據發送到計算單元組，最大不超過128個，同時根據返回的比較結果更新PBBT數據。

3.2 針對交并比的計算單元優化

ALU為計算單元組中的基礎模塊，負責計算兩個檢測框之間的交并比并比較置信度大小。以檢測框B1和B2為例，比較兩者交并比是否大于閾值的計算如式(3)所示

(3)

上述公式中關于面積的計算需要4個乘法器和一個除法器來完成，鑒于計算單元決定了加速器的整體功耗和資源消耗，而乘法和除法操作占用的硬件資源遠高于其它運算，因此考慮對不等式兩邊進行縮放來減少乘法和除法運算。

將檢測框B1和B2的位置分別用左下點坐標 (x1，y1)(x2，y2)， 框寬w1w2和框高h1h2表示。首先，觀察到交并比公式中兩框的并面積與最大面積之間存在式(4)所示的大小關系，因此采用式(4)對式(3)的分母進行縮放。再對不等式兩邊開方，并將新的分母移到不等式右側，此時的不等式如式(5)所示

(A(b1)+A(b2)-A(b1∩b2))≥max(A(b1)，A(b2))

(4)

(5)

若忽略開方運算，此時不等式不包含除法操作，但仍需四次乘法才能比較閾值，鑒于存在兩值平均值大于等于兩值開方的定理，即式(6)。為了滿足定理條件，通過式(7)將兩框并面積用坐標和寬高來表示，此時可以將不等式的左側按式(6)進行縮放，同時將框最大面積的也用坐標和寬高來代入，即式(8)

(6)

A(b1∩b2)=(min(x1+w1，x2+w2)-max(x1，x2))×(min(y1+h1，y2+h2)-max(y1，y2))

(7)

max(A(b1)，A(b2))=max(w1×h1，w2×h2)

(8)

(9)

ALU模塊負責比較交并比和置信度，引入額外約束會大幅增加計算單元的面積。因此考慮在實現完全覆蓋約束時，將式(9)中的部分條件判斷復用，減少硬件資源的消耗。復用后的約束條件如式(10)、式(13)所示，當4項公式全部成立時，b2是被b1完全覆蓋的小尺寸框，b2成為待刪去的冗余框。完整的判斷邏輯如圖6所示，ALU單元的輸入是待比較候選框的左下坐標、框寬和框高，輸出交并比和置信度的比較結果。將交并比的判斷條件復用后，計算是否完全覆蓋只需額外的兩個與門、一個后門和兩個比較器，進一步降低計算單元對硬件資源的消耗

圖6 三級流水線的ALU單元

x1+w1≥x2+w2&x1≥x2

(10)

x2+w2≥x1+w1&x2≥x1

(11)

y1+h1≥y2+h2&y1≥y2

(12)

y2+h2≥y1+h1&y2≥y1

(13)

在時序約束方面，鑒于乘法器的延遲較大，而硬件實現過程中有平衡各周期延遲的要求，因此將ALU單元劃分為三級流水線結構，如圖6所示，第一個周期完成加減法和初始條件判斷，延遲相近的雙與門級聯和乘法器安排在第二個周期，置信度和交并比的比較在最后一個周期，此時各個關鍵路徑的延遲最小。

鑒于計算單元同時包含置信度的比較，ALU采用雙比特輸出表示計算結果：控制模塊負責分發起始框和檢測框的數據，將兩框的左下坐標、框寬和寬高輸入ALU，經過計算后，輸出“10”表示該檢測框不滿足交并比條件，控制單元將PBBT對應的狀態位設為“2”；輸出“00”表示兩框的交并比超過閾值或兩框滿足完全覆蓋條件，該檢測框為需要刪除的冗余框，PBBT的對應狀態位設為“0”；輸出“11”表示額外滿足檢測框置信度較大的條件，此時該檢測框成為新的起始點，PBBT的狀態位設為“1”，起始點對應的狀態位設為“0”，完成一次交并比計算。

4 實驗與結果

為了評估硬件資源消耗情況，本文選擇PYNQ-Z2平臺，并以ZYNQ-XC7Z020芯片為核心部署面向文本檢測的NMS加速器，通過Verilog語言描述硬件模塊后，在vivado2019.1環境中進行布局布線，工作頻率設為100 MHz，并通過內置時序分析報告，確定加速器各條關鍵路徑滿足時序要求。加速器的資源消耗見表1，其中BRAM主要完成閾值表和PBBT的存儲，LUTRAM存放中間比較數據，與文獻[14]相比LUT占用減少12%，BRAM減少41%，說明通過多次縮放來優化計算公式，減少計算交并比所需的乘法器與除法器和重用判斷條件等優化方法能夠有效降低硬件資源的消耗。

表1 NMS加速器資源消耗情況

本文采用多次不等式縮放來簡化單次交并比的計算過程，該方法本質上放寬了交并比的約束條件，保留了部分交并比在閾值附近的冗余框，為了探討是否能通過降低交并比閾值來刪去上述冗余框，采用計算機模擬縮放算法，設置階梯閾值進行實驗，其中文本檢測前置算法采用EAST方法，文本數據集為ICDAR2013水平文本數據集，其結果見表2，縮放后的NMS與標準NMS相比，在閾值為0.4時準確率降低0.2%，而在閾值為0.8時準確率降低5.1%，驗證了降低閾值能減少不等式縮放損失的猜想，但閾值過高和過低都會帶來誤檢和漏檢的問題，因此本文NMS的閾值設為0.6。

表2 交并比閾值對準確率的影響

為了進一步評估FPGA平臺上本文加速器的文本檢測效果，我們對檢測指標、計算延遲和性能等方面進行評估，實驗現場如圖7所示。

圖7 實驗現場

首先將EAST文本檢測算法在ICDAR2013數據集上的處理結果預先存在SD存儲卡中，并將PYNQ-Z2上的PS處理器作為驗證實驗的數據控制器，通過AXI-Lite總線讀取候選框的位置信息，最后通過Jupyter Notebook添加測試任務并輸出實驗結果。

為了比較不同后處理方法后的文本檢測指標，我們在檢測框亂序存儲的基礎上，后處理方法分別選擇CPU實現的高準確率NMS、本文的加速器方法和文獻[12]的模擬方法。實驗結果見表3，相比誤差最小的NMS-CPU，本文方法的準確率降低2.4%，召回率降低0.8%，同時與比文獻[13]相比，準確率提高1.2%，召回率提高2.1%。說明雖然縮放過程會損失一定的準確率，但本文引入完全覆蓋的約束條件，能刪去部分遺漏的冗余框，提高檢測準確率。

表3 不同方法在ICDAR2013數據集上的效果

為了評估面向文本的NMS加速器性能，分別挑選文本目標數為5、10和15的待處理圖片，采用本文方法、CPU上實現的NMS算法和NMS的優化方法LANMS[3]作為后處理方法，比較三者的計算延遲，實驗結果見表4。本文加速器的性能比NMS-CPU方法提高67倍，比LANMS方法提高38倍。說明本文能通過檢測框分類的方法降低計算復雜度，通過優化計算公式的方法能減低單次交并比計算所需的周期。同時，按列并行計算異類檢測框和列內并行計算同類檢測框的計算結構有效，能通過提高NMS計算并行度的方式減低延遲，在多目標的圖片上的延遲較小。

表4 不同目標框數的計算延遲

為了衡量本文加速器與不同平臺實現NMS算法的優勢，我們選擇同類后處理加速文獻進行比較，鑒于文獻中給出的實驗候選框數最多不超過1000且最少不低于500，因此將處理725個檢測框時的數據作為本文結果，比較結果見表5，對比數據來自對應文獻。本文方法針對NMS的計算速度比CPU平臺的文獻[15]方法提高63倍，比同為FPGA平臺上的文獻[16]和文獻[14]分別提高7.1倍和1.8倍，同時硬件功耗與上述方法相比最低，僅為3.28 W。與TSMC工藝的文獻[13]相比算法延遲較大，但該方法要求檢測框的存儲按置信度從大到小排列，不支持亂序檢測框。上述對比說明，本文提出的面向文本檢測的NMS加速器延遲較低，能作為并行加速器提高文本檢測算法的實時性。

表5 NMS算法在不同平臺的性能比較

5 結束語

本文提出一種低延遲和低功耗NMS加速器設計方法，首先，該方法基于位置范圍對檢測框分類，通過各類并行和類內并行的方式提高加速器的運算效率。其次，通過多個縮放公式優化交并比的計算方法，減少計算所需的乘法器和除法器，并補充完全覆蓋的約束條件，改善縮放造成的小尺度候選框保留問題。最后，復用交并比的判斷條件，并設計三級流水線的計算單元，進一步減少硬件資源消耗較少。實驗結果表明，在100 MHZ的FPGA平臺上，本文提出的NMS加速器相比CPU平臺計算性能提高67倍。