基于FPGA 的模板匹配加速器的設計與實現

李 鋒，周仕杰

（東華大學 計算機科學與技術學院，上海 201620）

0 引言

織物的瑕疵檢測是織物質量控制中的重要一環，傳統的人工驗布方式存在著檢測效率低下、漏檢率高等缺陷，還會對工人本身的視力造成傷害，是提升織物生產效率的一大瓶頸［1］。為了改變這一現狀，織物的瑕疵檢測成為計算視覺領域的一大研究熱點［2］。國內外已有不少基于計算機視覺技術的解決方案，但是這些方案在實時性、準確性、經濟性及適用性上還不足以滿足實際的生產需求，還需要進一步探索。

基于深度學習的方法可以很好地擬合大量非線性數據，在復雜的織物紋理背景下有著更好的檢測效果，但是其面臨數據集獲取困難、難以增量學習、不可解釋性等難題［3－4］。純色織物的紋理是具有周期性的，傳統的模板匹配的方式可以很好地增強瑕疵區域的顯著性［5］。但是模板匹配算法本身計算量龐大，當前的通用CPU 架構無法滿足實時計算需求。而FPGA 作為一種高性能、低功耗的可編程芯片，可以通過編程直接生成專用電路。與CPU 分時同步的并行方式不同，FPGA 利用電路的并行特性可實現真正的多核并行［6］。現有解決方案大多是將織物瑕疵檢測算法部署在高性能服務器上，這些服務器大多采用通用PC 外接圖像采集卡及圖形加速卡的結構，成本較高［7］。近年來，隨著SoC 技術不斷成熟，FPGA＋ARM 的異構平臺（Zynq－7000 系列）的推出，使得高性能且低成本的軟硬協同定制計算，逐漸成為織物瑕疵檢測系統的首選解決方案［8］。

本文首先分析了運用于瑕疵檢測領域的模板匹配算法，根據該算法的特點設計了相應的基于FPGA 的硬件加速器，并對加速器的訪存時延、傳輸時延、計算時延等環節進行了優化。本方案在Zynq－7020 平臺上實現，對該加速器進行了性能評估，并與通用CPU 的運行效果進行了對比。

1 瑕疵檢測中的模板匹配算法

目前基于計算機視覺的瑕疵檢測算法可大致分為4 類：基于結構的方法、基于統計的方法、基于頻譜的方法和基于機器學習的方法［9］。其中，基于結構的方法通常是將織物的紋理視為紋理基元的組合，織物圖案的紋理即為紋理基元的周期性排列。由于瑕疵會破壞織物紋理的周期性，可以使用無瑕疵的織物圖像作為模板，通過模板匹配算法將織物圖片與紋理模板相減，可以提取出擁有較好一致性與完整性的目標瑕疵，該方法可用于織物瑕疵圖像的顯著性檢測，織物瑕疵圖像的顯著性檢測就是將瑕疵區域定義為顯著區域，其余紋理圖案部分定義為低顯著性區域［10－11］。

比較常見的基于灰度的圖像匹配算法有平均絕對差算法（MAD）、絕對誤差和算法（SAD）、誤差平方和算法（SSD）、平均誤差平方和算法（MSD）、歸一化積相關算法（NCC）、序貫相似性檢測算法（SSDA）等［12］。由于SAD 方法計算較為簡單，適合FPGA 的實現，本文采用SAD 方法，基本原理如式（1）和（2）：

其中，s（x，y）為待檢測圖像，其分辨率為m ×n，t（x，y）為模板圖像，其分辨率為M × N，M ＞m，N ＞n。

將待檢測圖像在模板圖像上滑動，如圖1 所示。tij（x，y）為待檢測圖片覆蓋到的模板圖像區域，即子模板圖，i、j為待檢測圖左上角在模板圖像中的坐標位置，其中i、j的范圍為：0 ≤i ＜M－m，0 ≤j ＜N－ n。

圖1 模板匹配過程Fig.1 Template matching procedure

絕對誤差和算法（SAD）將子模板圖與待檢測圖像之間像素灰度的差的絕對值之和d（i，j）作為子模板圖與待檢測圖之間的相似度，絕對差之和越小，表示待檢測圖與該位置的子模板圖越相似，取使得d（i，j）最小的子模板圖tij（x，y）作為模板匹配的結果圖像I，計算公式如式（1）和（2）所示。然后將待檢測圖像與模板匹配的結果圖像相減，定義為該待檢測織物圖像的顯著性圖像。

值得注意的是M－m與N－n的取值，即待檢測圖像與模板圖像之間的大小關系。由于織物紋理存在周期性，將織物紋理抽象為一個正弦函數：

假設待檢測圖像所包含的紋理周期為：

模板圖像所包含的紋理周期為：

若φ0≠φ1，則待檢測圖與模板圖之間存在相位差，為了保證待檢測圖像是模板圖像的子圖，則須滿足θ0≥θ1＋2π，即模板圖像須在橫向及縱向上均比待檢測圖像大一個紋理周期。若織物紋理一個周期的像素大小為p ×q，則為一張分辨率為m ×n的待檢測圖像進行模板匹配運算，需進行m ×n ×p ×q次減法運算，該方法的計算量龐大，當前的通用CPU 無法滿足其在實時場景中的算力需求，需要設計加速器。

2 基于FPGA 的模板匹配加速器設計

2.1 從模板匹配算法到FPGA 加速器

模板匹配是提取顯著性圖像的重要步驟，其速度直接影響整個瑕疵檢測的實時性，為此設計了一個模板匹配加速器，作為一個外設掛載在操作系統之下，CPU 和加速器之間通過內部數據總線相連。此外加速器訪問內存需要消耗大量時鐘周期，因此被讀入片上緩存的數據要盡可能得到復用，但片上緩存的大小有限，一幀4k 的完整織物圖片無法直接存入片上緩存，因此每次將包含若干紋理周期的子圖存入片上緩存。本文的論述主要基于像素大小為16×16 的子圖，以及像素大小為24×24 的模板圖，該方案適用于紋理周期小于8×8 的純色織物圖片。針對紋理周期較大的情況，可以考慮增大模板圖，但這也意味著更大的計算量、更多的資源消耗。本文設計的加速器在每次啟動的時候先將模板圖像存入片上緩存，然后在完整的織物圖像中依次為每一個子圖執行模板匹配運算，并將結果不斷寫回內存，其工作流程如圖2 所示。

圖2 加速器工作流程Fig.2 Accelerator workflow

2.2 加速器結構

加速器采用了3 層存儲架構，分別為片外緩存（DDR），片上緩存（BRAM），以及運算單元內部的寄存器，如圖3 所示。加速器通過AXI4（Advanced eXtensible Interface 4）總線與PS（Processing System）的內存通信，兩個AXI4 接口均工作在master 模式下，可對內存進行隨機訪問，其中input 接口負責將內存中的數據寫入片上緩存，而output 接口負責將計算后的結果寫回內存。此外該加速器的多個控制寄存器通過AXI4－Lite 總線實現與內存統一編址，該接口工作在slave 模式下，PS 端可通過AXI4－Lite總線來獲取并控制PL（Programmable Logic）部分的加速器工作狀態。

圖3 模板匹配加速器結構Fig.3 The structure of template matching accelerator

該加速器的主要運行時延由3 部分組成，分別為訪存時延，即加速器通過AXI 總線在內存中隨機尋址所消耗的時間；傳輸時延，即數據在AXI4 總線上傳輸所消耗的時間；以及計算時延，即模板匹配運算本身所消耗的時間。因此，可以從這3 個方面對加速器進行優化設計，提高資源利用率，提升加速器的算力。

2.3 加速器時延優化策略

2.3.1 訪存時延的優化

訪存時延的優化主要通過AXI4 總線的突發傳輸機制來實現。AXI4 總線中的突發傳輸是指在地址總線上進行一次地址傳輸后，可連續進行多次數據傳輸，即第一次地址傳輸中的地址作為起始地址，后續數據的存儲地址在起始地址的基礎上遞增，AXI4 總線的最大突發傳輸長度為256［13］。得益于這一機制，在加速器順序訪問大量連續內存地址的過程中，其速率可近似為每個時鐘周期訪問一個內存數據。對于本文的模板匹配算法來說，每一次訪存即是從一張完整的圖片中選取一個16×16 的子圖，也意味著每次只有16 個數據在內存中是順序排列的，突發傳輸的長度被限制為16。實驗結果顯示，在突發傳輸長度為16，時鐘頻率為150 Mhz 的情況下，傳輸一張分辨率為1 024×1 024 的灰度圖耗時約31 ms，如果選取的子圖擴大為32×32，則突發傳輸的長度擴大為32，同樣傳輸一張1 024×1 024的灰度圖，則耗時約為19 ms。理論上子圖寬度越大，訪存時延越短，但是過大的子圖紋理難以與模板圖中的紋理對齊，獲得的檢測效果也越差；在不丟失圖片幾何特征的情況下，子圖越小，越容易與模板圖中的紋理對齊，獲得的檢測效果也越好。經實驗，在大多數應用場景中分辨率為16×16 的子圖在獲得相對較好的檢測效果的同時，也獲得了相對較低的傳輸時延。

2.3.2 傳輸時延的優化

傳輸時延的優化主要通過時延折疊的方式來實現。該加速器的執行過程可抽象為3 個步驟：數據輸入、數據計算、結果輸出。由于三者是對同一組片上緩存中的數據進行操作，因此在未經優化的情況下這3 個步驟是一個串行的過程。常見的乒乓操作是例化兩組片上緩存，在每組緩存上交替執行輸入與輸出的步驟，以實現輸入與輸出的時延折疊［14］。本文則進一步采用了三重緩沖的思想，例化了3 組片上緩存，將輸入、計算、輸出三者的時延折疊，在傳統乒乓操作的基礎上進一步優化傳輸時延，其時序圖如圖4 所示。

圖4 采用三重緩沖后的時序圖Fig.4 Time sequence with triple buffering

其中，同一種顏色代表同一組片上緩存，在某一時刻往第一組片上緩存中輸入數據時，計算單元開始處理第二組片上緩存，同時將第三組片上緩存中的結果輸出到內存中。3 組片上緩存交替執行各個步驟，構成一個三級流水線。

2.3.3 計算時延的優化

上文中提到完成一次模板匹配運算需進行m ×n × p × q次減法運算，因此對于16×16 的待檢測子圖及8×8 的紋理周期，完成一次模板匹配運算需進行16 384 次減法運算。如果加速器內只有一組運算單元，即使對整個運算過程進行了流水線優化，在運算單元的起始間隔為1 個時鐘周期的情況下，仍舊需要16 384 個時鐘周期才能完成一輪計算，完成一張1 024×1 024 圖片的模板匹配運算，則至少需要447 ms。以16 的突發傳輸長度實現分辨率為1 024×1 024 圖片的傳輸僅需31 ms，時延折疊方式，則會產生如圖5 所示的時序圖，此時的運算過程將成為性能瓶頸，因此需要對計算時延進行優化。

圖5 計算時延優化前的時序Fig.5 Time sequence before computation delay optimization

雖然可以通過例化多組計算單元并行計算來達到優化的目的，但是模板圖與待檢測圖存儲在片上緩存即BRAM 中，而BRAM 本身的讀寫端口數是有限的，一般為兩個，即一個時鐘周期內只能讀取兩個數據。可將BRAM 進行分塊，以此來增加接口數量，使得在一個周期內讀取更多的數據，再通過例化多個計算單元實現并行計算［15］。

如圖6 所示，將24×24 的模板圖沿著x 方向劃分成24 組數據，并存入24 塊BRAM 中，將16×16的待檢測圖同樣沿著x 方向劃分成16 組數據，并存入16 塊BRAM 中。每塊BRAM 擁有兩個端口，因此一個時鐘周期內可讀出32 組數據，同時再例化32 組計算單元實現并行計算，將原本16 384個時鐘周期的運算時延縮減為512 個時鐘周期。實測該方案為分辨率為1 024×1 024的圖片進行模板匹配運算耗時約24 ms，此時的數據傳輸與計算過程的時延相差不大，時延得到充分折疊，時序如圖7 所示，且消耗的資源也不多。

圖6 BRAM 分塊過程Fig.6 BRAM partition process

圖7 計算時延優化后的時序Fig.7 Time sequence after computation delay optimization

如果將所有BRAM 徹底分塊，即把模板圖與待檢測圖的每一個數據都存儲在一個單獨的寄存器中，例化256 組計算單元，以實現在64 個周期內完成一次模板匹配運算，該方案雖然可行但是訪存時延就會成為瓶頸，同時這種方案會消耗大量不必要的邏輯資源。

3 實驗評估

3.1 實驗環境

使用搭載Zynq－7020 芯片的Pynq－Z2 開發板，Zynq－7020 異構平臺由雙核ARM Cortex－A9 與Artix－7 FPGA 組成。其中FPGA 部分的資源包括可編程邏輯單元85 K、片上緩存BRAM 4.9 Mb、DSP切片220 個，雙核A9 的時鐘頻率為667 MHz，板載512 MB 內存。采用工廠中常見的的4 K 工業線掃相機作為數據輸入源，像素頻率為24 MHz，該類相機每分鐘可采集寬度約1 m、長度約85 m 的織物圖像。開發板通過轉接板擴展出Camera Link 接口與線掃相機連接。FPGA 部分除了包含模板匹配算法加速器，還集成了用于將Camera Link 差分信號解析為RGB 數據，并將RGB 數據轉為AXI4－Stream 總線數據傳入內存的一系列相關IP 核。其中模板匹配加速器的資源消耗見表1。

表1 模板匹配加速器資源耗費Tab.1 Template matching accelerator resource consumption

其中，LUT（Look－Up－Table）為查找表；FF（Flip Flop）為觸發器；BRAMs為大小為36 Kb 的片上緩存數量；DSP（Digital Signal Processing）為數字信號處理器，以上均為FPGA 內部資源；f代表該加速器的工作時鐘頻率。

與之對比的通用PC 機，采用CPU i7－8750H，6 核12 線程，默認主頻2.2 GHz，搭載16 Gb 內存，通過PCIE（peripheral component interconnect express）外接圖像采集卡的方式來連接線掃相機。

在成本的方面，傳統的PC 級板卡式結構中僅一張專業的Camera Link 圖像采集卡價格就千元以上，一臺高性能主機的價格也普遍在5 000 元以上。相比之下，一塊搭載Zynq－7020 的開發板價格僅為1 000 元左右，成本降低了6 倍以上。

3.2 性能對比

本文設計的模板匹配加速器的處理效果在觀感上與通用CPU 的處理效果一致，無論是通用CPU還是本文設計的加速器，都很好地消除了織物的紋理背景，凸顯了瑕疵區域。由于本文中的模板匹配算法是以子圖為單位進行處理的，因此處理結果存在輕微網格效應，通過OTSU 或TRIANGLE 自適應二值化及一些基本形態學操作后可以輕松消除這一現象，處理效果如圖8 所示。此外，對織物原圖進行諸如保邊濾波、紋理提取等預處理步驟之后，再對紋理特征進行模板匹配，可以更好地消除噪聲及光照不均所帶來的干擾，獲得更好的檢測效果。

圖8 加速器處理結果Fig.8 Accelerator processing result

在檢測速度上，通用PC 與本文設計的加速器對比見表2。處理一張分辨率為1 024×1 024 的圖片，使用同樣的算法，基礎頻率為2.2 GHz 的i7－8750H 耗時0.324 s，無法跟上線掃相機24 MHz 的像素頻率，時常出現漏幀現象。相比之下，本文設計的模板匹配加速器，在PL 部分時鐘頻率為150 MHz的Zynq－7020 平臺上耗時僅為0.031 s，速度是CPU的10.5 倍，相當于33 MHz 的像素處理頻率，該速率大于工業線掃相機24 MHz 的像素頻率。工廠中普遍采用4 個像素覆蓋1 mm 的織物長度，以此來估算，對于4k 分辨率的線掃相機，本系統每分鐘可處理的織物面積約為120 m2，大于每分鐘85 m2的速率要求，滿足了實時性需求。

表2 本文加速器與通用PC 對比Tab.2 The accelerator compared with general PC

4 結束語

為了將織物瑕疵檢測算法更有效地部署到實際生產環境中，本文對瑕疵檢測領域的模板匹配算法進行了改進，為該算法設計了一種基于FPGA 的算法加速器，并對該加速器的各項處理時延進行了優化。最終該加速器在Zynq－7000 系列異構平臺上獲得了33 MHz 的像素處理頻率，相當于每分鐘可處理面積約120 m2的織物圖片，滿足了工業領域的實時性需求。設計過程中采用SoC 技術取代了傳統的PC 級板卡式結構，使織物瑕疵檢測系統的成本降低了6 倍以上。