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

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

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

　　設(shè)F（x，y）為一幅M×N的基準(zhǔn)圖像，B（x，y）是一幅m×n的實(shí)時(shí)圖像、Sx,y是一幅與實(shí)時(shí)圖像做互相關(guān)運(yùn)算的匹配子圖，且m<M，n<N。

　　標(biāo)準(zhǔn)歸一化互相關(guān)算法計(jì)算公式如下：

　　觀察上述公式可知，對(duì)應(yīng)數(shù)據(jù)的減法運(yùn)算、乘法運(yùn)算和累加運(yùn)算占據(jù)了絕大部分的計(jì)算量。針對(duì)TS20l處理器，可以借助其寬總線、大內(nèi)存及并行指令的特點(diǎn)實(shí)現(xiàn)圖像數(shù)據(jù)的高速存取和并發(fā)計(jì)算，提升標(biāo)準(zhǔn)算法的執(zhí)行效率，由于該處理器僅支持32位取值，計(jì)算單元不支持8位數(shù)據(jù)乘法的特性，也給提升標(biāo)準(zhǔn)算法的執(zhí)行效率造成阻礙。

    實(shí)驗(yàn)發(fā)現(xiàn)，導(dǎo)致算法效率下降的主要原因有兩個(gè)：一個(gè)是其本身龐大的計(jì)算量；另一個(gè)是處理器32位取值的特性難以獲取匹配子圖數(shù)據(jù)。

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

　　2.1 遞推方案

　　遞推多模板方案快速算法首先要解決算法本身計(jì)算量大的問(wèn)題。觀察式（1）可知，式（2）為匹配子圖與實(shí)時(shí)圖協(xié)方差計(jì)算過(guò)程，式（3）為匹配子圖方差的計(jì)算過(guò)程，式（4）為實(shí)時(shí)圖的方差計(jì)算過(guò)程。對(duì)于實(shí)時(shí)圖的方差計(jì)算部分，在整個(gè)匹配過(guò)程中只需要計(jì)算，而對(duì)于匹配子圖的方差計(jì)算和兩張圖像的協(xié)方差計(jì)算則需要多次重復(fù)執(zhí)行，共需要約（M-m）x（N-n）×3×m×n次加乘計(jì)算，計(jì)算量龐大。本文采用匹配子圖遞推方案來(lái)減少計(jì)算量。

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

　?。?）當(dāng)實(shí)時(shí)圖進(jìn)行水平平行移動(dòng)時(shí)，因Sx,y+1是Sx,y在基準(zhǔn)圖中右移1列的位置所對(duì)應(yīng)的新匹配子圖，即Sx,y+1的前n-1列是Sx,y的后n-1列，有：

　?。?）當(dāng)實(shí)時(shí)圖進(jìn)行垂直平行移動(dòng)時(shí)，因Sx+1,y是Sx,y在基準(zhǔn)圖中下移1行的位置所對(duì)應(yīng)的新匹配子圖，即Sx+1,y的前m-1行是Sx,y的后m-1行，有：

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

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

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

　　2.2 多模板方案

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

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

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

　　以圖2為例，上半部分圖像為構(gòu)建的大實(shí)時(shí)圖塊，大實(shí)時(shí)圖塊中連續(xù)像素“4”點(diǎn)集為起始像素不位于字位上的真實(shí)模板圖像；下半部分圖像為大實(shí)時(shí)圖塊對(duì)應(yīng)的大匹配子圖，大匹配子圖中連續(xù)像素“4”點(diǎn)集為真實(shí)實(shí)時(shí)圖對(duì)應(yīng)的起始像素不位于字位上的真實(shí)匹配子圖。將這兩個(gè)擴(kuò)大后的數(shù)據(jù)塊各個(gè)像素對(duì)應(yīng)相乘并累加，其結(jié)果即為真實(shí)實(shí)時(shí)圖與真實(shí)匹配子圖對(duì)應(yīng)像素的乘累加結(jié)果。這樣做不僅建立了兩個(gè)圖像數(shù)據(jù)塊各個(gè)像素間的對(duì)應(yīng)相乘關(guān)系，而且也解決了起始像素不位于字位數(shù)據(jù)塊的數(shù)據(jù)獲取問(wèn)題。

　　構(gòu)建的這些大實(shí)時(shí)圖塊可直接與基準(zhǔn)圖像上對(duì)應(yīng)的放大子圖進(jìn)行相關(guān)計(jì)算，省去匹配子圖數(shù)據(jù)的重復(fù)準(zhǔn)備過(guò)程，以適當(dāng)增加計(jì)算量的方式消去了多次重復(fù)數(shù)據(jù)準(zhǔn)備占用的處理周期。配合4字處理工作模式，只需在算法運(yùn)行的初期性地構(gòu)建16個(gè)（m+16）×n的大實(shí)時(shí)圖塊，即可與全部匹配子圖進(jìn)行相關(guān)運(yùn)算，而原有的匹配子圖數(shù)據(jù)準(zhǔn)備模式則需要構(gòu)建（M-m）×（N-n）個(gè)m×n像素的圖像塊。

　　3 實(shí)驗(yàn)結(jié)果

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

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

　　4 結(jié)語(yǔ)

　　歸一化互相關(guān)快速算法充分結(jié)合了ADSP-TS201處理器的特性，構(gòu)建了遞推多模板互相關(guān)快速算法。實(shí)驗(yàn)證明，該算法大大縮短了執(zhí)行時(shí)間，執(zhí)行效率也得到了提高。

　　關(guān)于ADSP-TS201

　　ADSP-TS201是美國(guó)模擬器件ADD公司繼TSl01之后推出的一款高性能處理器。其采用超級(jí)哈佛結(jié)構(gòu)，靜態(tài)超標(biāo)量操作適合多處理器模式運(yùn)算，可直接構(gòu)成分布式并行系統(tǒng)和共享存儲(chǔ)式系統(tǒng)。此系列DSP性價(jià)比很高，兼有FPGA和ASIC信號(hào)處理性能和指令集處理器的高度可編程性，適用于大存儲(chǔ)量、高性能、高速度的信號(hào)處理和圖像處理。如雷達(dá)信號(hào)處理、無(wú)線基站、圖像音頻處理等。

參考文獻(xiàn):

[1]. n-1 datasheet http://m.58mhw.cn/datasheet/n-1_1997158.html.