|
圖像匹配指在已知目標基準圖的子圖集合中，尋找與實時圖像最相似的子圖，以達到目標識別與定位目的的圖像處理技術。由于歸一化互相關算法的實現方案簡單，對灰度值的線性變化具有適應性、抗白噪聲能力強，以及匹配性能穩定的特點，已成為圖像匹配技術中應用最為廣泛的匹配算法。該算法不僅可以應用于民用圖像處理技術領域，也可以應用于SAR成像和紅外成像制導系統等軍事領域當中。雖然歸一化互相關算法的匹配能力強，性能穩定，但該算法的計算量較大，不易應用于實時系統當中。針對這一現象，討論了一種基于ADSP-TS201處理器，在保證全圖遍歷條件下，使用遞推與多模板思想構建的歸一化互相關快速算法。實驗證實，該快速算法在保證算法性能的同時，有效地提高了算法的執行效率。 1 歸一化互相關算法實現過程分析 歸一化互相關算法是基于灰度圖像匹配技術中最為經典的算法，具有抗白噪聲能力強，匹配準確性高的突出特點，但該算法的計算量較大，嚴重影響了算法應用的實時性。 設F(x，y)為一幅M×N的基準圖像，B(x，y)是一幅m×n的實時圖像、Sx,y是一幅與實時圖像做互相關運算的匹配子圖，且m＜M，n＜N。 標準歸一化互相關算法計算公式如下： 觀察上述公式可知，對應數據的減法運算、乘法運算和累加運算占據了標準算法中絕大部分的計算量。針對TS20l處理器，可以借助其寬總線、大內存及并行指令的特點實現圖像數據的高速存取和并發計算，提升標準算法的執行效率，但該處理器僅支持32位取值，計算單元不支持8位數據乘法的特性，也給提升標準算法的執行效率帶來了一定的限制。實驗發現，導致TS201執行歸一化互相關算法效率下降的主要原因有兩個：一個是標準算法本身計算量龐大；另一個是處理器32位取值的特性使匹配子圖數據的獲取困難。 2 遞推多模板方案快速算法 2．1 遞推方案 遞推多模板方案快速算法首先要解決的問題就是歸一化互相關算法本身計算量龐大的問題。觀察式(1)可知，式(2)為匹配子圖與實時圖協方差計算過程，式(3)為匹配子圖方差的計算過程，式(4)為實時圖的方差計算過程。對于實時圖的方差計算部分，在整個匹配過程中只需要計算一次，而對于匹配子圖的方差計算和兩張圖像的協方差計算則需要多次重復執行，共需要約(M-m)x(N-n)×3×m×n次加乘計算，計算量龐大。本文采用匹配子圖遞推方案來減少計算量。 結合實際圖像，最大互相關算法實際是將實時圖在匹配基準圖像上做逐點逐行平移，并與其覆蓋的匹配子圖做相關運算，求取相關系數并比對，以獲取最佳匹配位置。在實時圖平移的過程中，其覆蓋的新匹配子圖數據遵循如下遞推原則： (1)當實時圖進行水平平行移動時，因Sx,y+1是Sx,y在基準圖中右移1列的位置所對應的新匹配子圖，即Sx,y+1的前n-1列是Sx,y的后n-1列，有： (2)當實時圖進行垂直平行移動時，因Sx+1,y是Sx,y在基準圖中下移1行的位置所對應的新匹配子圖，即Sx+1,y的前m-1行是Sx,y的后m-1行，有： 利用此遞推原則，可以將歸一化互相關式中的式(3)進行簡化。觀察式(3)中數據計算結果是以各個數據平方和的累加形式出現的，所以先將式(5)和式(6)進行平方運算，得到對應的式(7)和式(8)。 使用式(7)和式(8)對式(3)進行變換，得到全圖遍歷過程中使用的匹配子圖遞推方差計算： 在全圖遍歷的過程中，式(9)每次需要得到的計算結果只是在上次累加結果的基礎上，減去移出數據的累加值和增加移人數據的累加值，中間重復數據的累加結果不再重復計算，從而減少了計算量。匹配子圖遞推方案將會使單次子圖方差計算的計算量由2×m×n次加乘減少至2×m或者2×n次加乘。 2．2 多模板方案 遞推多模板方案的快速算法需要解決的另一個重要問題是匹配子圖的數據準備問題。有兩個不利因素導致產生此問題，一個是匹配子圖數據準備過程重復進行(M-m)×(N-n)次，占據了大量處理時鐘；另一個由式(2)的分析可知，算法運行過程中，每次相關匹配運算需要將實時圖數據塊與匹配子圖數據塊中的像素一一對應進行乘法運算。由于TS201自身只支持32位取值(字取值)，所以無法將直接獲取數據的方法獲得的起始像素不位于字首的匹配子圖數據塊用于計算，也即不能利用DMA使用雙緩沖的常規方式準備數據。 本文采用多模板計算方案來解決匹配子圖數據的準備問題。 多模板計算方案首先將處理器定位于4字取值工作模式，加載并行指令，使處理器的計算能力最大化；其次將實時圖予以適當的橫向放大，構建多個與匹配子圖等高的大實時圖塊，并分別在大實時圖塊范圍內將真實實時圖像數據進行逐點平移，與預匹配子圖像素相對應，非真實實時圖像素位置零，如圖1、圖2所示。 以圖2為例，上半部分圖像為構建的大實時圖塊，大實時圖塊中連續像素“4”點集為起始像素不位于字位上的真實模板圖像；下半部分圖像為大實時圖塊對應的大匹配子圖，大匹配子圖中連續像素“4”點集為真實實時圖對應的起始像素不位于字位上的真實匹配子圖。將這兩個擴大后的數據塊各個像素對應相乘并累加，其結果即為真實實時圖與真實匹配子圖對應像素的乘累加結果。這樣做不僅建立了兩個圖像數據塊各個像素間的對應相乘關系，而且也解決了起始像素不位于字位數據塊的數據獲取問題。 構建的這些大實時圖塊可直接與基準圖像上對應的放大子圖進行相關計算，省去匹配子圖數據的重復準備過程，以適當增加計算量的方式消去了多次重復數據準備占用的處理周期。配合4字處理工作模式，只需在算法運行的初期一次性地構建16個(m+16)×n的大實時圖塊，即可與全部匹配子圖進行相關運算，而原有的匹配子圖數據準備模式則需要構建(M-m)×(N-n)個m×n像素的圖像塊。 3 實驗結果 對使用匯編語言和遞推多模板方案構建的歸一化互相關快速算法進行測試。輸入由紅外圖像拉伸而來的128×128像素的8位基準圖像和64x 64像素的實時圖像，如圖3所示。 使用TS201處理器的運行快速算法。可以精確獲得實時圖像匹配坐標，運算時間統計結果見表l。 4 結語 結合ADSP-TS201處理器特性，構建了遞推多模板最大互相關快速算法。實驗證明，該快速算法較常規算法的執行時間明顯縮短，執行效率提升較高。 |
