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

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

責(zé)任編輯:時(shí) 雯

1 圖像匹配技術(shù)現(xiàn)狀分析

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

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

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

2 多級(jí)模板并行匹配原理

2.1 模板匹配原理

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

圖1 搜索圖和模板圖

SAD算法公式定義為

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

2.2 實(shí)現(xiàn)過程

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

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

3 多級(jí)模板并行匹配的FPGA上實(shí)現(xiàn)

3.1 基本思路

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

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

在模板一行數(shù)據(jù)和搜索窗一行數(shù)據(jù)都已經(jīng)保留的情況下，搜索窗進(jìn)行移位的同時(shí)計(jì)算行所有點(diǎn)的絕對(duì)差之和，并且能夠在規(guī)定時(shí)間內(nèi)計(jì)算出全部偏移量對(duì)應(yīng)的相關(guān)系數(shù) R(i0，j0) 。

3.2 設(shè)計(jì)方法

如圖2所示，整個(gè)系統(tǒng)分為4個(gè)模塊:存儲(chǔ)模塊、乒乓移位模塊、SAD計(jì)算模塊、SAD值存儲(chǔ)模塊。

圖2 系統(tǒng)框圖

1)存儲(chǔ)模塊

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

圖3 存儲(chǔ)模塊

2)乒乓移位模塊

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

圖4 乒乓鎖存和移位

該模塊優(yōu)點(diǎn)為:首先，在計(jì)算當(dāng)前行的SAD值時(shí)，就在存儲(chǔ)下一行的數(shù)據(jù)，形成了行流水方式，節(jié)約了讀取行消耗時(shí)間，減少匹配時(shí)間;其次，行與行相關(guān)系數(shù)計(jì)算占用邏輯單元少，有利于在有限的資源下計(jì)算多個(gè)模板。

3)SAD計(jì)算模塊和SAD存儲(chǔ)模塊

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

圖5 SAD模塊和行值累加

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

4 系統(tǒng)運(yùn)行結(jié)果性能分析

4.1 Modelsim仿真結(jié)果及分析

首先定義4個(gè)模板圖和搜索圖分別是:模板圖24×24對(duì)應(yīng)搜索圖40×40;模板圖32×32對(duì)應(yīng)搜索圖40×40;模板圖48×48對(duì)應(yīng)搜索圖為64×64;模板圖64×64對(duì)應(yīng)搜索圖72×72。以模板圖為24×24和搜索圖是40×40為例，對(duì)仿真結(jié)果進(jìn)行分析。如圖6所示，模板圖每行的數(shù)據(jù)0～23，搜索圖每行數(shù)據(jù)16～55。

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

如圖7和圖8所示，在開關(guān)信號(hào)為低電平時(shí)，一行數(shù)據(jù)從存儲(chǔ)器中讀出來并且存儲(chǔ)到移位寄存器當(dāng)中，該圖反應(yīng)了一個(gè)時(shí)鐘周期讀出8個(gè)像素點(diǎn)數(shù)據(jù)并且存入移位寄存器當(dāng)中。等待開關(guān)信號(hào)為高電平時(shí)移位寄存器進(jìn)行移位操作，這樣每移動(dòng)一位就相當(dāng)于模板圖在搜索圖中滑動(dòng)一位。模板行數(shù)據(jù)的保存類似搜索圖行數(shù)據(jù)的保存，只是在計(jì)算過程中模板行數(shù)據(jù)不進(jìn)行移位操作，只是維持值不改變，等待一行計(jì)算完畢，再進(jìn)行下一行存儲(chǔ)。

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

圖9 最終結(jié)果

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

圖10 4級(jí)模板并行匹配

4.2 匹配時(shí)間上的分析與DSP性能對(duì)比

整個(gè)系統(tǒng)采用50 MHz分頻之后13.5 MHz時(shí)鐘作為基本時(shí)鐘。在表1中Les為邏輯資源，MB為memory bit存儲(chǔ)資源，從表中的數(shù)據(jù)可以看出FPGA在并行處理多個(gè)模板匹配的優(yōu)勢(shì)是很明顯的，F(xiàn)PGA計(jì)算4個(gè)模板的匹配總的耗時(shí)等于單模板中最大耗時(shí)，模板32×32比模板24×24所用時(shí)間要小是由于其對(duì)應(yīng)搜索圖大小不同。但是DSP總的耗時(shí)便是4個(gè)模板匹配時(shí)間之和，超過場(chǎng)信號(hào)周期20 ms，沒有辦法用DSP來做4個(gè)模板相關(guān)系數(shù)計(jì)算?，F(xiàn)在FPGA系統(tǒng)時(shí)鐘采用13.5 MHz進(jìn)行計(jì)算，如果系統(tǒng)時(shí)間進(jìn)行倍頻，計(jì)算時(shí)間將會(huì)成倍減少。

4.3 FPGA+DSP與單獨(dú)DSP對(duì)比實(shí)際的效果跟蹤圖

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

表1 時(shí)間和資源統(tǒng)計(jì)

5 小結(jié)

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

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

［2］李國輝.基于多片DSP的相關(guān)匹配算法的研究與實(shí)現(xiàn)［D］.成都:電子科技大學(xué)，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］高陳強(qiáng)，余迪虎，李強(qiáng)，等.視頻圖像中基于特征匹配的人流量統(tǒng)計(jì)［J］. 電視技術(shù)，2011，35(15):20-23.

［6］陳辰，王沛，韋芳芳.圖像多通道邊緣信息輔助的快速立體匹配算法［J］. 電視技術(shù)，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.