摘 要:歸一化互相關(guān)算法因其圖像匹配穩(wěn)定性高的特點被廣泛應(yīng)用于SAR成像和紅外成像的制導(dǎo)系統(tǒng)中。為增強其應(yīng)用的實時性，討論一種基于TS201處理器，在保證全圖遍歷條件下，結(jié)合處理器的自身特性，采用遞推與多模板思想構(gòu)建的歸一化互相關(guān)快速算法。實驗證明，該執(zhí)行效率常規(guī)算法的實現(xiàn)方案有了很大提高，可以實現(xiàn)低對比度條件下的目標(biāo)精確匹配。

關(guān)鍵詞:ADSP-TS201;歸一化互相關(guān);遞推與多模板方法; 目標(biāo)精確匹配

中圖分類號:TP391 文獻(xiàn)標(biāo)識碼:A

文章編號:1004-373X(2010)10-0125-03

TS201 Based Fast Algorithm of Normalized Cross-correlation

SUN Zu-xin， WU Qiang

(College of Electronic and Control Engineering，Beijing University of Technology，Beijing 100124，China)

Abstract:The normalized cross-correlating algorithm with high stability for image matching has been widely used in SAR imaging and infrared imaging-guided systems. To enhance the characteristic of real-time application， a fast algorithm based on TS201 processor is proposed， which ensures the entire graphergodicy conditions， combines the processor's own characteristics， and usesthe recursive plan and the multi-template method. The experiments show that the program makes the algorithm more efficient than the other conventional algorithms and can accurately match the targets under the condition of low-contrast.

Keywords:ADSP-TS201; normalized cross-correlation; recursive plan and multi-template method; accurate matching of target

0 引 言

圖像匹配指在已知目標(biāo)基準(zhǔn)圖的子圖集合中，尋找與實時圖像最相似的子圖，以達(dá)到目標(biāo)識別與定位目的的圖像處理技術(shù)[1]。由于歸一化互相關(guān)算法的實現(xiàn)方案簡單[2]，對灰度值的線性變化具有適應(yīng)性、抗白噪聲能力強，以及匹配性能穩(wěn)定的特點，已成為圖像匹配技術(shù)中應(yīng)用最為廣泛的匹配算法[3-4]。該算法不僅可以應(yīng)用于民用圖像處理技術(shù)領(lǐng)域，也可以應(yīng)用于SAR成像和紅外成像制導(dǎo)系統(tǒng)等軍事領(lǐng)域當(dāng)中。雖然歸一化互相關(guān)算法的匹配能力強，性能穩(wěn)定，但該算法的計算量較大，不易應(yīng)用于實時系統(tǒng)當(dāng)中[5-6]。針對這一現(xiàn)象，討論了一種基于ADSP-TS201處理器，在保證全圖遍歷條件下，使用遞推與多模板思想構(gòu)建的歸一化互相關(guān)快速算法。實驗證實，該快速算法在保證算法性能的同時，有效地提高了算法的執(zhí)行效率。

1 歸一化互相關(guān)算法實現(xiàn)過程分析

歸一化互相關(guān)算法是基于灰度圖像匹配技術(shù)中最為經(jīng)典的算法，具有抗白噪聲能力強，匹配準(zhǔn)確性高的突出特點，但該算法的計算量較大，嚴(yán)重影響了算法應(yīng)用的實時性。

設(shè)F(x，y)為一幅M×N的基準(zhǔn)圖像，B(x，y)是一幅m×n的實時圖像，Sx，y是一幅與實時圖像做互相關(guān)運算的匹配子圖，且m

標(biāo)準(zhǔn)歸一化互相關(guān)算法計算公式[7]如下:

NCC(x，y)=cov(Sx，y，B)/Dx，yDB(1)

式中:

cov(Sx，y，B)=1mn∑mi=1∑nj=1[Sx，y(i，j)-Sx，y]#8226;

[B(i，j)-B](2)

Dx，y=1mn∑mi=1∑nj=1[Sx，y(i，j)-Sx，y]2(3)

DB=1mn∑mi=1∑nj=1[B(i，j)-B]2(4)

觀察上述公式可知，對應(yīng)數(shù)據(jù)的減法運算、乘法運算和累加運算占據(jù)了標(biāo)準(zhǔn)算法中絕大部分的計算量。針對TS201處理器，可以借助其寬總線、大內(nèi)存及并行指令的特點實現(xiàn)圖像數(shù)據(jù)的高速存取和并發(fā)計算，提升標(biāo)準(zhǔn)算法的執(zhí)行效率，但該處理器僅支持32位取值，計算單元不支持8位數(shù)據(jù)乘法[8]的特性，也給提升標(biāo)準(zhǔn)算法的執(zhí)行效率帶來了一定的限制。實驗發(fā)現(xiàn)，導(dǎo)致TS201執(zhí)行歸一化互相關(guān)算法效率下降的主要原因有兩個:一個是標(biāo)準(zhǔn)算法本身計算量龐大;另一個是處理器32位取值的特性使匹配子圖數(shù)據(jù)的獲取困難。

2 遞推多模板方案快速算法

2.1 遞推方案

遞推多模板方案快速算法首先要解決的問題就是歸一化互相關(guān)算法本身計算量龐大的問題。觀察式(1)可知，式(2)為匹配子圖與實時圖協(xié)方差計算過程，式(3)為匹配子圖方差的計算過程，式(4)為實時圖的方差計算過程。對于實時圖的方差計算部分，在整個匹配過程中只需要計算一次，而對于匹配子圖的方差計算和兩張圖像的協(xié)方差計算則需要多次重復(fù)執(zhí)行[9]，共需要約(M-m)×(N-n)×3×m×n次加乘計算，計算量龐大。本文采用匹配子圖遞推方案來減少計算量。

結(jié)合實際圖像，最大互相關(guān)算法實際是將實時圖在匹配基準(zhǔn)圖像上做逐點逐行平移，并與其覆蓋的匹配子圖做相關(guān)運算，求取相關(guān)系數(shù)并比對，以獲取最佳匹配位置。在實時圖平移的過程中，其覆蓋的新匹配子圖數(shù)據(jù)遵循如下遞推原則:

(1) 當(dāng)實時圖進(jìn)行水平平行移動時，因Sx，y+1是Sx，y在基準(zhǔn)圖中右移1列的位置所對應(yīng)的新匹配子圖，即Sx，y+1的前n-1列是Sx，y的后n-1列，有:

∑mi=1∑nj=1Sx，y+1(i，j)=∑mi=1∑nj=1Sx，y(i，j)+

∑x+m=1i=x[S(i，y+n)-S(i，y)](5)

(2) 當(dāng)實時圖進(jìn)行垂直平行移動時，因Sx+1，y是Sx，y在基準(zhǔn)圖中下移1行的位置所對應(yīng)的新匹配子圖，即Sx+1，y的前m-1行是Sx，y的后m-1行，有:

∑mi=1∑nj=1Sx+1，y(i，j)=∑mi=1∑nj=1Sx，y(i，j)+

∑y+n=1i=y[S(x+m，i)-S(x，i)](6)

利用此遞推原則，可以將歸一化互相關(guān)式中的式(3)進(jìn)行簡化。觀察式(3)中數(shù)據(jù)計算結(jié)果是以各個數(shù)據(jù)平方和的累加形式出現(xiàn)的，所以先將式(5)和式(6)進(jìn)行平方運算，得到對應(yīng)的式(7)和式(8)。

∑mi=1∑nj=1S2x，y+1(i，j)=∑mi=1∑nj=1S2x，y(i，j)+

∑x+m=1i=x[S2(i，y+n)-S2(i，y)](7)

∑mi=1∑nj=1S2x+1，y(i，j)=∑mi=1∑nj=1S2x，y(i，j)+

∑y+n=1i=y[S2(x+m，i)-S2(x，i)](8)

使用式(7)和式(8)對式(3)進(jìn)行變換，得到全圖遍歷過程中使用的匹配子圖遞推方差計算:

Dx，y=1mn∑mi=1∑nj=1(S1，1(i，j)-S1，1)2，x=1，y=1

∑mi=1∑nj=1S2x，y(i，j)+∑x+m=1i=x[S2(i，y+n)-S2(i，y)]

∑mi=1∑nj=1S2x，y(i，j)+∑y+n=1i=y[S2(x+m，i)-S2(x，i)]，y=1(9)

在全圖遍歷的過程中，式(9)每次需要得到的計算結(jié)果只是在上次累加結(jié)果的基礎(chǔ)上，減去移出數(shù)據(jù)的累加值和增加移入數(shù)據(jù)的累加值，中間重復(fù)數(shù)據(jù)的累加結(jié)果不再重復(fù)計算，從而減少了計算量。匹配子圖遞推方案將會使單次子圖方差計算的計算量由2×m×n次加乘減少至2×m或者2×n次加乘。

2.2 多模板方案

遞推多模板方案的快速算法需要解決的另一個重要問題是匹配子圖的數(shù)據(jù)準(zhǔn)備問題。有兩個不利因素導(dǎo)致產(chǎn)生此問題，一個是匹配子圖數(shù)據(jù)準(zhǔn)備過程重復(fù)進(jìn)行(M-m)×(N-n)次[10]，占據(jù)了大量處理時鐘;另一個由式(2)的分析可知，算法運行過程中，每次相關(guān)匹配運算需要將實時圖數(shù)據(jù)塊與匹配子圖數(shù)據(jù)塊中的像素一一對應(yīng)進(jìn)行乘法運算。由于TS201自身只支持32位取值(字取值)，所以無法將直接獲取數(shù)據(jù)的方法獲得的起始像素不位于字首的匹配子圖數(shù)據(jù)塊用于計算，也即不能利用DMA使用雙緩沖的常規(guī)方式準(zhǔn)備數(shù)據(jù)。

本文采用多模板計算方案來解決匹配子圖數(shù)據(jù)的準(zhǔn)備問題。

多模板計算方案首先將處理器定位于4字取值工作模式，加載并行指令，使處理器的計算能力最大化;其次將實時圖予以適當(dāng)?shù)臋M向放大，構(gòu)建多個與匹配子圖等高的大實時圖塊，并分別在大實時圖塊范圍內(nèi)將真實實時圖像數(shù)據(jù)進(jìn)行逐點平移，與預(yù)匹配子圖像素相對應(yīng)，非真實實時圖像素位置零，如圖1、圖2所示。

圖1 一號大實時圖塊與大匹配子圖示意圖

圖2 四號大實時圖塊與大匹配子圖示意圖

以圖2為例，上半部分圖像為構(gòu)建的大實時圖塊，大實時圖塊中連續(xù)像素“4”點集為起始像素不位于字位上的真實模板圖像;下半部分圖像為大實時圖塊對應(yīng)的大匹配子圖，大匹配子圖中連續(xù)像素“4”點集為真實實時圖對應(yīng)的起始像素不位于字位上的真實匹配子圖。將這兩個擴大后的數(shù)據(jù)塊各個像素對應(yīng)相乘并累加，其結(jié)果即為真實實時圖與真實匹配子圖對應(yīng)像素的乘累加結(jié)果。

這樣做不僅建立了兩個圖像數(shù)據(jù)塊各個像素間的對應(yīng)相乘關(guān)系，而且也解決了起始像素不位于字位數(shù)據(jù)塊的數(shù)據(jù)獲取問題。

構(gòu)建的這些大實時圖塊可直接與基準(zhǔn)圖像上對應(yīng)的放大子圖進(jìn)行相關(guān)計算，省去匹配子圖數(shù)據(jù)的重復(fù)準(zhǔn)備過程，以適當(dāng)增加計算量的方式消去了多次重復(fù)數(shù)據(jù)準(zhǔn)備占用的處理周期。

配合4字處理工作模式，只需在算法運行的初期一次性地構(gòu)建16個(m+16)×n的大實時圖塊，即可與全部匹配子圖進(jìn)行相關(guān)運算，而原有的匹配子圖數(shù)據(jù)準(zhǔn)備模式則需要構(gòu)建(M-m)×(N-n)個m×n像素的圖像塊。

3 實驗結(jié)果

對使用匯編語言和遞推多模板方案構(gòu)建的歸一化互相關(guān)快速算法進(jìn)行測試。輸入由紅外圖像拉伸而來的128×128像素的8位基準(zhǔn)圖像和64×64像素的實時圖像，如圖3所示。

圖3 模板圖像與基準(zhǔn)圖像

使用TS201處理器的運行快速算法，可以精確獲得實時圖像匹配坐標(biāo)，運算時間統(tǒng)計結(jié)果見表1。

表1 算法處理時間對比

方案名稱計算量 /MIPS處理時間 /s

標(biāo)準(zhǔn)算法方案3 674.9577.349 91

TS201匯編優(yōu)化方案10.4840.020 96

遞推多模板方案6.1260.012 25

4 結(jié) 語

結(jié)合ADSP-TS201處理器特性，構(gòu)建了遞推多模板最大互相關(guān)快速算法。實驗證明，該快速算法較常規(guī)算法的執(zhí)行時間明顯縮短，執(zhí)行效率提升較高。

參考文獻(xiàn)

[1]劉瑩，曹劍中.基于灰度相關(guān)的圖像匹配算法的改進(jìn)[J].應(yīng)用光學(xué)，2007，28(5):536-540.

[2]李卓，丘淑娟.基于相關(guān)系數(shù)的快速圖像匹配研究[J].北京理工大學(xué)學(xué)報，2007，27(11):998-1000.

[3]劉紅俠，楊靚，黃巾，等.快速圖像匹配相關(guān)系數(shù)算法及實現(xiàn)[J].微電子學(xué)與計算機，2007，24(2):32-35.

[4]曹炬，馬杰，譚毅華，等.基于像素抽樣的快速互相關(guān)圖像匹配算法[J].宇航學(xué)報，2004，25(3):173-178.

[5]杜杰.兩種基于灰度的快速圖像匹配算法[D].大連:大連海事大學(xué)，2007.

[6]張紅源，陳自立.圖像匹配經(jīng)典算法及其改進(jìn)方法研究[J].軟件開發(fā)與應(yīng)用，2008，27(9):91-94.

[7]董安國.圖像匹配最大互相關(guān)快速算法[J].浙江萬里學(xué)院學(xué)報，2005，18(4):13-15.

[8]劉書明，羅勇江.ADSP TS20XS系列DSP原理與應(yīng)用設(shè)計[M].北京:電子工業(yè)出版社，2004.

[9]韓先鋒，李俊山，孫滿囤，等.巡航導(dǎo)彈景象匹配算法適應(yīng)性研究[J].微電子學(xué)與計算機，2005，22(7):53-57.

[10]薛利軍，李自田，李英才，等.一種基于圖像分層的快速相關(guān)匹配算法[J].計算機工程與科學(xué)，2006，28(7):65-66.