一種基于TS201的歸一化互相關(guān)快速算法
加入技術(shù)交流群
圖像匹配指在已知目標基準圖的子圖集合中，尋找與實(shí)時(shí)圖像最相似的子圖，以達到目標識別與定位目的的圖像處理技術(shù)。由于歸一化互相關(guān)算法的實(shí)現方案簡(jiǎn)單，對灰度值的線(xiàn)性變化具有適應性、抗白噪聲能力強，以及匹配性能穩定的特點(diǎn)，已成為圖像匹配技術(shù)中應用最為廣泛的匹配算法。該算法不僅可以應用于民用圖像處理技術(shù)領(lǐng)域，也可以應用于SAR成像和紅外成像制導系統等軍事領(lǐng)域當中。雖然歸一化互相關(guān)算法的匹配能力強，性能穩定，但該算法的計算量較大，不易應用于實(shí)時(shí)系統當中。針對這一現象，討論了一種基于A(yíng)DSP-TS201處理器，在保證全圖遍歷條件下，使用遞推與多模板思想構建的歸一化互相關(guān)快速算法。實(shí)驗證實(shí)，該快速算法在保證算法性能的同時(shí)，有效地提高了算法的執行效率。
l 歸一化互相關(guān)算法實(shí)現過(guò)程分析
歸一化互相關(guān)算法是基于灰度圖像匹配技術(shù)中最為經(jīng)典的算法，具有抗白噪聲能力強，匹配準確性高的突出特點(diǎn)，但該算法的計算量較大，嚴重影響了算法應用的實(shí)時(shí)性。
設F(x，y)為一幅M×N的基準圖像，B(x，y)是一幅m×n的實(shí)時(shí)圖像、Sx,y是一幅與實(shí)時(shí)圖像做互相關(guān)運算的匹配子圖，且mM，nN。
標準歸一化互相關(guān)算法計算公式如下：
觀(guān)察上述公式可知，對應數據的減法運算、乘法運算和累加運算占據了標準算法中絕大部分的計算量。針對TS20l處理器，可以借助其寬總線(xiàn)、大內存及并行指令的特點(diǎn)實(shí)現圖像數據的高速存取和并發(fā)計算，提升標準算法的執行效率，但該處理器僅支持32位取值，計算單元不支持8位數據乘法的特性，也給提升標準算法的執行效率帶來(lái)了一定的限制。實(shí)驗發(fā)現，導致TS201執行歸一化互相關(guān)算法效率下降的主要原因有兩個(gè)：一個(gè)是標準算法本身計算量龐大；另一個(gè)是處理器32位取值的特性使匹配子圖數據的獲取困難。
2 遞推多模板方案快速算法
2．1 遞推方案
遞推多模板方案快速算法首先要解決的問(wèn)題就是歸一化互相關(guān)算法本身計算量龐大的問(wèn)題。觀(guān)察式(1)可知，式(2)為匹配子圖與實(shí)時(shí)圖協(xié)方差計算過(guò)程，式(3)為匹配子圖方差的計算過(guò)程，式(4)為實(shí)時(shí)圖的方差計算過(guò)程。對于實(shí)時(shí)圖的方差計算部分，在整個(gè)匹配過(guò)程中只需要計算一次，而對于匹配子圖的方差計算和兩張圖像的協(xié)方差計算則需要多次重復執行，共需要約(M-m)x(N-n)×3×m×n次加乘計算，計算量龐大。本文采用匹配子圖遞推方案來(lái)減少計算量。
結合實(shí)際圖像，最大互相關(guān)算法實(shí)際是將實(shí)時(shí)圖在匹配基準圖像上做逐點(diǎn)逐行平移，并與其覆蓋的匹配子圖做相關(guān)運算，求取相關(guān)系數并比對，以獲取最佳匹配位置。在實(shí)時(shí)圖平移的過(guò)程中，其覆蓋的新匹配子圖數據遵循如下遞推原則：
(1)當實(shí)時(shí)圖進(jìn)行水平平行移動(dòng)時(shí)，因Sx,y+1是Sx,y在基準圖中右移1列的位置所對應的新匹配子圖，即Sx,y+1的前n-1列是Sx,y的后n-1列，有：
(2)當實(shí)時(shí)圖進(jìn)行垂直平行移動(dòng)時(shí)，因Sx+1,y是Sx,y在基準圖中下移1行的位置所對應的新匹配子圖，即Sx+1,y的前m-1行是Sx,y的后m-1行，有：
利用此遞推原則，可以將歸一化互相關(guān)式中的式(3)進(jìn)行簡(jiǎn)化。觀(guān)察式(3)中數據計算結果是以各個(gè)數據平方和的累加形式出現的，所以先將式(5)和式(6)進(jìn)行平方運算，得到對應的式(7)和式(8)。
使用式(7)和式(8)對式(3)進(jìn)行變換，得到全圖遍歷過(guò)程中使用的匹配子圖遞推方差計算：
評論