基于FPGA實現多級模板并行匹配

薛順瑞，張 文，高 原，劉 怡，李 游

(1.電子科技大學，四川 成都 611731;2.內江師范學院，四川 內江 641112;3.西南技術物理研究所，四川 成都 610041;4.云南大學，云南 昆明 650091)

責任編輯:時 雯

1 圖像匹配技術現狀分析

在大規模戰爭中，具有高精確性的制導武器對戰爭的結局起關鍵性作用，圖像匹配技術作為精確制導圖像處理器的關鍵技術具有重要的理論意義和實用價值。對于精確制導武器，匹配性能決定著制導武器的精確度［1］。通常情況下，匹配性能是隨著模板面積的增加而提高，但是實際情況存在著幾何失真的干擾，幾何失真的強度會隨著模板面積的增加而增加，從而導致匹配性能下降，因而單純提高模板面積來提高匹配性能，在實際情況下是不可行的。由于單模板相關系數是包括模板圖和搜索圖每個像素點的函數，當搜索圖受到某種干擾導致搜索圖的某一部分發生變化，相關系數會有很大的影響。解決此問題，需要將模板圖進行劃分為多個模塊，采用多個模板最優相關系數子集方法［2］。

多個模板相關算法是為了解決幾何失真帶來的匹配精度下降的問題，將大模板劃分為多個子模板，然后分別將每個子模板與實時圖像進行相關匹配，由于子模板的像素點少，所以當部分像素發生變化時，主要影響的是相對的子模板，而對其他子模板影響較小，將每個子模板的相關系數矩陣進行綜合。這樣綜合之后匹配性能與大模板匹配性能相似，也減少了幾何失真所導致的匹配性能下降［3］。

在基于灰度圖像，本文采用的相關匹配算法是差的絕對值和相關法(Sum of Absolute Difference，SAD)［4］。由于SAD算法具有計算簡單、重復性大等特點，因而可以并行處理多個像素點，使得計算時間降低。如果采用DSP計算多個模板的SAD，由于DSP是逐點計算，所以實時性往往不能達到要求。但是FPGA具有并行處理多個進程的特點和SAD算法具有被并行處理特性，采用FPGA來實現多個模板的SAD算法，是在基于并行處理特性上和實時性要求很高的情況下完成對多個模板的SAD計算，在規定時間內得到相關系數，能夠提供足夠的時間讓DSP處理跟蹤算法，從而提高整體系統實時性和精確性［5］。

2 多級模板并行匹配原理

2.1 模板匹配原理

基于圖像灰度值模板匹配，本文采用的是SAD算法(差的絕對值和相關法)。如圖1所示，設搜索圖為(M+N)×(M+N)，模板圖為N×N。

圖1 搜索圖和模板圖

SAD算法公式定義為

式中:i∈(0，M+N)，j∈(0，N);R(i0，j0) 為相似性度量函數在偏移量是(i0，j0)時的匹配度量值也稱之為相關系數;S(i0+i，j0+j)為實時圖像中搜索區域中各像素點灰度值;T(i0+i，j0+j)為模板圖中各像素點灰度值;(i，j)為搜索圖與模板圖之間的偏移量，當R(i0，j0)取值最小時認為 (i0，j0) 為最佳匹配位置［2］。

2.2 實現過程

如圖1所示，最初模板T坐標(0，0)和搜索圖S坐標(0，0)對齊，計算完畢之后模板圖T在搜索窗上進行滑動一次，使得模板圖T坐標(0，0)與搜索窗坐標(0，1)對齊，同樣進行相同SAD計算，計算出相關系數R(i0，j0)。每滑動一次計算出偏移量為(i，j)的相關系數R(i0，j0)。當滑動M×M次之后，得到全部偏移量對應的相關系數R(i0，j0)［6］。

當模板級數達到多級時，如果采用DSP進行計算，則一級模板所有的匹配度量值計算完畢之后，才會進行下一級模板計算。用此方案時間會成倍增加，比如模板有N級，計算時間是單個模板時間的N倍，因此DSP在計算多個模板，實時性不能滿足要求。如果采用FPGA來實現多級模板的優勢是顯而易見的，FPGA并行處理特性可以并行處理多個模板，計算模板相關系數R(i0，j0)所用時間將會大大降低，多個模板所耗費時間等于單個模板耗費時間，比DSP計算時間減少N倍。采用FPGA實現多個模板SAD算法，能夠很大程度上降低匹配時間，滿足實時性要求。為DSP完成跟蹤算法提供了足夠時間，并且能夠提高整個目標跟蹤系統的可靠性和精確性［7］。

3 多級模板并行匹配的FPGA上實現

3.1 基本思路

本文采用的FPGA芯片是Altera公司CycloneIII系列EP3C40F484I7，總邏輯單元Total logic elements為39600，Total memory bit為 1161216 bit，M9K 為126 個［7］。

通過深入理解SAD算法原理之后，容易采用D觸發器陣列存儲模板圖和搜索窗每個點，為了便于實現SAD算法，經資源分析之后此方案是不可能實現的。為此設計一種方法優化該設計，能夠在滿足性能情況下實現資源優化。該芯片邏輯單元不多，應該減少邏輯單元使用，雖然不能得到所有點的D觸發器flip-flop陣列，但是能夠得到一行數據的D觸發器flip-flop，通過這樣的思路可以降低資源消耗。

在模板一行數據和搜索窗一行數據都已經保留的情況下，搜索窗進行移位的同時計算行所有點的絕對差之和，并且能夠在規定時間內計算出全部偏移量對應的相關系數 R(i0，j0) 。

3.2 設計方法

如圖2所示，整個系統分為4個模塊:存儲模塊、乒乓移位模塊、SAD計算模塊、SAD值存儲模塊。

圖2 系統框圖

1)存儲模塊

如圖3所示，模板圖數據和搜索窗數據各有一個存儲器，在寫使能有效時，將模板數據和搜索窗數據分別存入各自存儲器中，讀取模板數據和搜索窗數據以128 bit數據讀出，輸出位寬越大，讀數據所消耗的時間越少，該模塊的輸出作為兵乓移位模板的數據輸入。

圖3 存儲模塊

2)乒乓移位模塊

該模塊設計如圖4所示，基本思想是根據換行信號為高電平時，讀取搜索圖一行數據到移位寄存器A中，模板圖一行數據讀取到鎖存器A中。同時移位寄存器B進行移位操作，鎖存器B數據不變，鎖存器B和移位寄存器B并行輸出一行數據給SAD計算模塊進行行相關系數值的計算。換行信號為低電平時，讀取搜索圖一行數據到移位寄存器B中，模板一行數據讀取到鎖存器B中。同時移位寄存器A進行移位操作，鎖存器A數據不變，鎖存器A和移位寄存器A并行輸出一行數據給SAD計算模塊進行行相關系數值的計算。

圖4 乒乓鎖存和移位

該模塊優點為:首先，在計算當前行的SAD值時，就在存儲下一行的數據，形成了行流水方式，節約了讀取行消耗時間，減少匹配時間;其次，行與行相關系數計算占用邏輯單元少，有利于在有限的資源下計算多個模板。

3)SAD計算模塊和SAD存儲模塊

如圖5 所示，T_data［n:0］和 S_data［n:0］分別是模板圖行數據和搜索窗行數據，SUB為16 bit減法器，ABS為16 bit取絕對值模塊，多路ADD的作用是將行中所有點的絕對差值進行累加運算，SAD存儲器用于暫存行相關系數值以及存儲最終結果。

圖5 SAD模塊和行值累加

通過乒乓移位模塊輸出模板圖行和搜索窗行的數據到SAD計算模塊中，對它們進行減法，絕對值和求和運算。得到的一行相關系數將它送入2路ADD模塊中用于累加。用模板圖的滑動次數也就是偏移量作為SAD值存儲器的讀寫地址。計算SAD值時，一直讓SAD存儲器處于讀狀態，便于下一行的相關系數能夠與上一行的相關系數進行累加。最后滑動M×M次之后，完成了所有偏移量對應相關系數的計算，這樣SAD存儲器就存儲了所有的相關系數，其中存儲器地址于偏移量所對應，比如偏移量是(i0，j0)，那么在SAD存儲器地址為i0×16+j0的空間中就是偏移量(i0，j0)的相關系數。然后將所得到相關系數發送給DSP，DSP在相關系數基礎上進行后續算法運算。

4 系統運行結果性能分析

4.1 Modelsim仿真結果及分析

首先定義4個模板圖和搜索圖分別是:模板圖24×24對應搜索圖40×40;模板圖32×32對應搜索圖40×40;模板圖48×48對應搜索圖為64×64;模板圖64×64對應搜索圖72×72。以模板圖為24×24和搜索圖是40×40為例，對仿真結果進行分析。如圖6所示，模板圖每行的數據0～23，搜索圖每行數據16～55。

圖6 模板圖為24×24和搜索圖是40×40

如圖7和圖8所示，在開關信號為低電平時，一行數據從存儲器中讀出來并且存儲到移位寄存器當中，該圖反應了一個時鐘周期讀出8個像素點數據并且存入移位寄存器當中。等待開關信號為高電平時移位寄存器進行移位操作，這樣每移動一位就相當于模板圖在搜索圖中滑動一位。模板行數據的保存類似搜索圖行數據的保存，只是在計算過程中模板行數據不進行移位操作，只是維持值不改變，等待一行計算完畢，再進行下一行存儲。

如圖9所示，SAD存儲器發送地址(Mad_send_rdaddress)與模板圖滑動次數即偏移量是相對應的。發送地址為0的時候表示模塊處于初始位置，偏移量為(0，0)。圖中0地址對應的最終絕對差之和實際值Mad_Sum為9216(地址與數據有一個時鐘的延遲)。如圖6所示模板圖和搜索圖，容易得出模板圖和搜索圖偏移量為(0，0)時每個點對應的差值為16，總共有24×24個點，絕對差之和理論值為16×24×24=9216。由圖可以看出理論值和實際值相同，所以用FPGA實現的模板匹配具有匹配準確性。

圖9 最終結果

本 文 采 用 Altera公 司 的 CycloneIII系 列EP3C40F484I7設計4個模板并行匹配處理系統，如圖10所示，有4個SendMad_en讀信號為高電平時，表示對于該模板的MAD計算完畢。整個系統實現了4個模板的匹配算法并行處理，由圖分析可知，模板24×24首先計算完畢，64×64的最后計算完畢，由于模板越小計算量越小，所以匹配時間越小。

圖10 4級模板并行匹配

4.2 匹配時間上的分析與DSP性能對比

整個系統采用50 MHz分頻之后13.5 MHz時鐘作為基本時鐘。在表1中Les為邏輯資源，MB為memory bit存儲資源，從表中的數據可以看出FPGA在并行處理多個模板匹配的優勢是很明顯的，FPGA計算4個模板的匹配總的耗時等于單模板中最大耗時，模板32×32比模板24×24所用時間要小是由于其對應搜索圖大小不同。但是DSP總的耗時便是4個模板匹配時間之和，超過場信號周期20 ms，沒有辦法用DSP來做4個模板相關系數計算。現在FPGA系統時鐘采用13.5 MHz進行計算，如果系統時間進行倍頻，計算時間將會成倍減少。

4.3 FPGA+DSP與單獨DSP對比實際的效果跟蹤圖

驗證FPGA并行處理多模板實時性和可靠性，為此構造一個背景單一的實時場景，背景采用白色，運動物體是一把黑色的鑰匙，鑰匙通過一根固定在上方的線連接，使鑰匙做鐘擺運動。圖11的跟蹤圖是基于FPGA+DSP系統，由FPGA來完成4個模板的相關系數，通過圖11分析跟蹤框中心與運動物體中心始終對齊，匹配準確性高。圖12的跟蹤圖是基于單DSP系統，由DSP來做4個模板相關系數以及跟蹤算法，通過圖12分析圖像每隔一場，跟蹤框中心與運動物體的中心有很大的偏差，匹配性能差。通過圖11和圖12比較，能夠得出FPGA+DSP具有良好的實時性和精確性。

表1 時間和資源統計

5 小結

本文以低端FPGA為平臺，實現了實現多個模板圖與多個搜索圖之間像素值差的絕對值和相關法。本設計巧妙和靈活，將匹配技術中適合在并行處理的SAD算法在FPGA上移植，為DSP分擔了算法中大量的計算，并且利用有限的邏輯單元和RAM資源實現了4個模板同時進行相關系數的計算。特別是乒乓移位模塊，進行移位的同時也在進行讀取行的操作，很大程度上節約了匹配時間。匹配時間得到很大程度的降低，為DSP完成跟蹤算法提高了足夠的時間，從而提高了整體系統的實時性和精確性。

［1］馬莉，韓燮.主成分分析法(PCA)在SIFT匹配算法中的應用［J］.電視技術，2011，35(1):129-132.

［2］李國輝.基于多片DSP的相關匹配算法的研究與實現［D］.成都:電子科技大學，2004.

［3］TORU W，YUKIHIKO Y.Multi-template GAT/PAT correlation for character recognition with a limited quantity ofdata［J］.IEEE Computer Society，2010，10(704):2873-2876.

［4］MANZAR M A，CHEEMA T A，JALIL A，etal.New image matching technique based on hyper-vectorisation ofgrey levelsliced binary images［J］.IET Image Processing，2008，2(6):337-351.

［5］高陳強，余迪虎，李強，等.視頻圖像中基于特征匹配的人流量統計［J］. 電視技術，2011，35(15):20-23.

［6］陳辰，王沛，韋芳芳.圖像多通道邊緣信息輔助的快速立體匹配算法［J］. 電視技術，2011，35(23):17-21.

［7］MICHAEL D，CILETTI.Advanced digital design with the verilog HDL［M］.2nd ed.Beijing:Publishing House of electronics industry，2010:213-224.