0 引言

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

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

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

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

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

　　觀察上述公式可知,，對(duì)應(yīng)數(shù)據(jù)的減法運(yùn)算,、乘法運(yùn)算和累加運(yùn)算占據(jù)了標(biāo)準(zhǔn)算法中絕大部分的計(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)致TS201執(zhí)行歸一化互相關(guān)算法效率下降的主要原因有兩個(gè)：一個(gè)是標(biāo)準(zhǔn)算法本身計(jì)算量龐大；另一個(gè)是處理器32位取值的特性使匹配子圖數(shù)據(jù)的獲取困難,。

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

　　2．1 遞推方案

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

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

　　(1)當(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列,，有：

　　(2)當(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)行變換,，得到全圖遍歷過程中使用的匹配子圖遞推方差計(jì)算：

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

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