張軼飛，牛守瑞，馬 娜，張長(zhǎng)泉

?

一種新的基于多頻譜疊加的圖像配準(zhǔn)算法

張軼飛1，牛守瑞1，馬 娜2，張長(zhǎng)泉1

（1. 63963部隊(duì) 北京 100072；2. 中科院高能物理研究所 北京 100049）

針對(duì)現(xiàn)有頻域法FFT和PPFFT對(duì)于大倍率圖像配準(zhǔn)精度和計(jì)算效率難以同時(shí)保證的問(wèn)題，研究了一種基于多重頻譜疊加的頻域算法，為最大限度減小插值誤差噪聲，該算法采用多分辨率頻譜插值，構(gòu)造出更接近對(duì)數(shù)極坐標(biāo)網(wǎng)格。文中給出分辨率參數(shù)設(shè)置和算法流程。最后通過(guò)算例驗(yàn)證，結(jié)果表明：本算法對(duì)無(wú)裁減圖像最大配準(zhǔn)倍率可至10，對(duì)裁減圖像可至5，而FFT和PPFFT（無(wú)迭代）對(duì)于兩種類型圖像都約為2；相對(duì)于特征點(diǎn)匹配法，本算法也適用于更大倍率的圖像配準(zhǔn)，從而驗(yàn)證了該算法的準(zhǔn)確性和可行性。

多重頻譜；大倍率配準(zhǔn)；對(duì)數(shù)極坐標(biāo)；插值誤差

0 引言

圖像配準(zhǔn)是圖像運(yùn)動(dòng)估計(jì)的關(guān)鍵，廣泛應(yīng)用于圖像嵌入、視頻壓縮、電子穩(wěn)像及圖像增強(qiáng)等領(lǐng)域[1-5]。一般地，配準(zhǔn)方法主要分為空域法和頻域法兩種。頻域法主要有傅里葉變換法（FFT）[6-7]、偽極數(shù)傅里葉變換法（Pseudo Polar FFT，PPFFT）[8-10]等?？沼蚍ㄖ饕袎K匹配法[11]、灰度投影法[12]及特征匹配法等[13]。相較于空域法，頻域法抗噪性強(qiáng)、不受亮度變化影響，且計(jì)算簡(jiǎn)單，易于實(shí)現(xiàn)。在傳統(tǒng)的FFT法和PPFFT法實(shí)現(xiàn)過(guò)程中，坐標(biāo)變換易產(chǎn)生較大的插值誤差，使配準(zhǔn)精度降低。FFT法最高配準(zhǔn)倍率較低，最高為2[7]，而PPFTT法最高配準(zhǔn)倍率雖可達(dá)4[9]，但需經(jīng)過(guò)多次迭代，計(jì)算效率則較低。顯然傳統(tǒng)方法在配準(zhǔn)倍率和計(jì)算效率上難以兼?zhèn)洹?/p>

本文基于圖像的多分辨率頻譜疊加，提出一種改進(jìn)方法，該方法無(wú)需迭代，且能實(shí)現(xiàn)大倍率圖像的配準(zhǔn)。

1 圖像配準(zhǔn)信噪比及噪聲種類

1.1 配準(zhǔn)信噪比

一般地，圖像信噪比（Signal Noise Ratio, SNR）是針對(duì)單幅圖像質(zhì)量而言，表達(dá)為圖像信號(hào)與噪聲的功率譜之比，又可近似等于峰值信噪比10×lg(2552/MSE)。但在基于頻域法的圖像配準(zhǔn)中，兩種圖像能否準(zhǔn)確配準(zhǔn)，則取決于其互功率譜的傅里葉反變換圖像的最大值位置是否準(zhǔn)確。文獻(xiàn)[9]給出了配準(zhǔn)信噪比的定義：

并證明該式滿足：

顯然，正常情況下，配準(zhǔn)信噪比最大值處對(duì)應(yīng)正確的配準(zhǔn)參數(shù)。但當(dāng)噪聲強(qiáng)于信號(hào)時(shí)，則會(huì)產(chǎn)生誤匹配，因此區(qū)分噪聲種類，并予以去除或減弱，尤為重要。

1.2 噪聲種類

式(2)表明，SNR越大，配準(zhǔn)信噪比越高。而SNR又與噪聲功率成反比，因此，最大限度降低圖像經(jīng)縮放、旋轉(zhuǎn)及配準(zhǔn)過(guò)程中插值等產(chǎn)生的頻譜噪聲，能提高圖像配準(zhǔn)精度。

一般，圖像噪聲可分為以下3種。

1）旋轉(zhuǎn)混疊

圖像經(jīng)旋轉(zhuǎn)后，其離散傅里葉變換將產(chǎn)生多處疊加現(xiàn)象。這是因?yàn)閳D像不是無(wú)限周期延伸的，尤其當(dāng)圖像采樣頻率小于2倍頻譜截止頻率時(shí)。該噪聲主要表現(xiàn)為頻譜的高頻部分，文獻(xiàn)[14]提出采用窗口函數(shù)來(lái)消除該噪聲，但同時(shí)也會(huì)削弱真實(shí)信號(hào)能量。

2）倍率混疊

當(dāng)圖像被放大某一倍率時(shí)，其頻譜也被相應(yīng)放大，單周期內(nèi)的頻譜高頻部分與相鄰周期的頻譜可能產(chǎn)生重疊，從而產(chǎn)生倍率混疊噪聲。通常這種噪聲可通過(guò)低通濾波減弱，但對(duì)于大倍率圖像，因?yàn)V波帶寬難以估計(jì)，濾波函數(shù)往往會(huì)淹沒真正的圖像信息。

3）插值誤差

插值誤差是指圖像頻譜從笛卡爾坐標(biāo)或偽極坐標(biāo)變換至對(duì)數(shù)極坐標(biāo)時(shí)，因插值計(jì)算產(chǎn)生的誤差噪聲。

上述誤差中，旋轉(zhuǎn)和混疊噪聲，隨角度和縮放倍率變化，難以通過(guò)固定窗口的加窗函數(shù)和固定帶寬的濾波函數(shù)進(jìn)行消除，而插值誤差噪聲，則可通過(guò)改進(jìn)插值方法予以降低。

以下將重點(diǎn)圍繞如何降低插值噪聲，研究對(duì)數(shù)極坐標(biāo)下非均勻網(wǎng)格的特點(diǎn)，設(shè)計(jì)多分辨率傅里葉變換的分段插值，來(lái)提高配準(zhǔn)精度。

2 改進(jìn)方法

改進(jìn)方法按多頻譜網(wǎng)格的構(gòu)建、多重參數(shù)設(shè)置及改進(jìn)算法流程逐一介紹。

2.1 多分辨率頻譜構(gòu)建

1）對(duì)數(shù)極坐標(biāo)網(wǎng)格特點(diǎn)

頻域法進(jìn)行圖像配準(zhǔn)時(shí)，是對(duì)兩幅圖對(duì)數(shù)極坐標(biāo)下的幅度譜進(jìn)行比較。圖1示出極坐標(biāo)和對(duì)數(shù)極坐標(biāo)網(wǎng)格。顯然，極坐標(biāo)網(wǎng)格沿徑向均勻分布，而對(duì)數(shù)極坐標(biāo)網(wǎng)格則是沿徑向由密至疏非均勻分布。將圖1橫縱坐標(biāo)替換為徑長(zhǎng)和角度，則如圖2所示。圖2更直觀顯示出縱坐標(biāo)方向網(wǎng)格的非均勻分布情況。傳統(tǒng)的FFT和PPFFT法，都是基于均勻網(wǎng)格，而后插值出對(duì)數(shù)極坐標(biāo)網(wǎng)格。從圖2看出，在徑長(zhǎng)較大處時(shí)，由于均勻網(wǎng)格間隔與對(duì)數(shù)極坐標(biāo)網(wǎng)格相當(dāng)或更小，插值誤差將較小，而在徑長(zhǎng)較小處時(shí)，均勻網(wǎng)格則明顯大于對(duì)數(shù)極坐標(biāo)網(wǎng)格間隔，此時(shí)，插值結(jié)果將會(huì)產(chǎn)生較大誤差，影響匹配結(jié)果。

圖1 笛卡爾坐標(biāo)下均勻極坐標(biāo)網(wǎng)格和對(duì)數(shù)極坐標(biāo)網(wǎng)格比較

圖2 均勻極坐標(biāo)網(wǎng)格和對(duì)數(shù)極坐標(biāo)網(wǎng)格比較

2）構(gòu)建過(guò)程

根據(jù)以上分析，考慮構(gòu)造一種類似圖2(b)的網(wǎng)格，使其更接近對(duì)數(shù)極坐標(biāo)網(wǎng)格。

離散傅里葉變換（DFT）有如下表達(dá)形式：

圖3 多分辨率網(wǎng)格疊加示意圖

另外式(4)還可以通過(guò)分?jǐn)?shù)傅里葉變換得到：

0≤＜，＝1/

考慮到頻譜集需要疊加，為便于對(duì)中，將頻域變量范圍定義為關(guān)于原點(diǎn)對(duì)稱，則有－p≤≤p，于是式(4)變?yōu)椋?/p>

0≤＜，－(/2)≤￠＜/2

同樣，將式(5)對(duì)中，可變?yōu)椋?/p>

0≤＜，－(/2)≤￠＜/2，＝1/

比較式(6)和(7)可知，二者得到的頻譜范圍－p≤≤p和－p≤≤p，即前者得到的頻譜矩陣規(guī)模更大，而后者僅與原頻譜相當(dāng)。事實(shí)上，當(dāng)進(jìn)行多分辨率頻譜疊加時(shí)，若將由式(6)得到的各頻譜矩陣全部疊加，其本質(zhì)相當(dāng)于取最大分辨率值（即為最大）的頻譜，且計(jì)算量極大，失去了疊加的意義。因此應(yīng)對(duì)式(6)得到的全頻域頻譜進(jìn)行截取，得到與原圖像尺寸相當(dāng)規(guī)模的頻譜矩陣。而式(7)無(wú)需截取可即得到所需規(guī)模的矩陣。從計(jì)算量來(lái)看，式(6)的運(yùn)算量為10×()，而式(7)則只需30×()，因此，用分?jǐn)?shù)傅里葉變換更快捷。

2.2 多重頻譜參數(shù)設(shè)置

如上所述，通過(guò)設(shè)置多重頻譜并疊加，能使疊加后的頻譜更接近實(shí)際頻譜。其中，各頻譜的分辨率（即細(xì)化參數(shù)）的選取設(shè)置是關(guān)鍵。在確定參數(shù)設(shè)置之前，先分析一下頻譜插值誤差及網(wǎng)格插值誤差。

1）一階頻譜插值誤差函數(shù)

對(duì)于某頻譜為的圖像，定義一階插值誤差[9]為：

式中：grid(r,)為實(shí)際頻域點(diǎn)與網(wǎng)格中最近點(diǎn)距離，表示為：

2grid(r,)＝(closet－real)2＋(closet－real)2(9)

2）頻譜參數(shù)計(jì)算

建立200×200的二重均勻網(wǎng)格和對(duì)數(shù)極坐標(biāo)網(wǎng)格，并計(jì)算error。誤差曲線和誤差曲面如圖4、圖5所示。

表1反映出，傳統(tǒng)的笛卡爾及偽極坐標(biāo)網(wǎng)格都為均勻網(wǎng)格，與極坐標(biāo)網(wǎng)格插值比較看，偽極坐標(biāo)明顯優(yōu)于笛卡爾坐標(biāo)網(wǎng)，同時(shí)也優(yōu)于多重頻譜網(wǎng)，但與對(duì)極數(shù)坐標(biāo)網(wǎng)的插值誤差則明顯增大，而多重網(wǎng)格疊加的優(yōu)勢(shì)則比較明顯，隨著網(wǎng)格層數(shù)的增加，其插值誤差明顯減小，當(dāng)達(dá)到五重網(wǎng)格疊加時(shí)，插值誤差可達(dá)到傳統(tǒng)笛卡爾及偽極坐標(biāo)網(wǎng)的1/3和1/2左右。從多重網(wǎng)格參數(shù)比較看，優(yōu)化后的參數(shù)較隨機(jī)選取的參數(shù)能得到更小的插值誤差。同時(shí)，注意到多重網(wǎng)格同一參數(shù)下p較lp更大，這時(shí)因?yàn)閷?duì)數(shù)極坐標(biāo)網(wǎng)大部分點(diǎn)聚集在內(nèi)層高分辨網(wǎng)格，插值誤差更低，而極坐標(biāo)網(wǎng)格外層低分辨網(wǎng)格內(nèi)插值點(diǎn)較多，因此，各點(diǎn)插值誤差求和后，仍可能使二者相差相大。綜合來(lái)看，可以得到如下結(jié)論：多重網(wǎng)格疊加能明顯改善插值精度，當(dāng)網(wǎng)格層數(shù)超過(guò)2時(shí)，與對(duì)數(shù)極坐標(biāo)網(wǎng)格插值誤差大大低于偽極坐標(biāo)網(wǎng)格；多重網(wǎng)格插值精度隨網(wǎng)格層數(shù)增加而增高；多重網(wǎng)格采用優(yōu)化參數(shù)較非優(yōu)化參數(shù)具有更高的精度。

圖4 二重頻譜參數(shù)曲線

圖5 三重頻譜參數(shù)曲面

表1 各類網(wǎng)格插值誤差比較

2.3 改進(jìn)算法流程步驟

綜上所述，采用多重網(wǎng)格能明顯改善與對(duì)數(shù)極坐標(biāo)網(wǎng)格的插值精度，因此，基于傅里葉變換，采用多重頻譜疊加，可以得到改進(jìn)算法。具體實(shí)現(xiàn)步驟如圖6所示。

圖6 改進(jìn)算法流程圖

Fig 6. Improvedalgorithm flow chart

3 實(shí)驗(yàn)分析

3.1 單一圖像不同倍率下配準(zhǔn)比較

采用改進(jìn)方法與FFT、PPFFT法進(jìn)行圖像配準(zhǔn)，分別測(cè)試同一圖像不同放大倍率下的配準(zhǔn)情況，如圖7所示，所用圖像均未經(jīng)裁剪。實(shí)驗(yàn)平臺(tái)為CPU intelE31230雙核3.2G，內(nèi)存4G的PC機(jī)，編程軟件為Matlab，測(cè)試圖像分辨率均為256×256。

圖7 各倍率配準(zhǔn)圖

從表2結(jié)果看，前3組放大倍率在5以上的圖像樣本，F(xiàn)FT和PPFFT法均無(wú)法配準(zhǔn)，而改進(jìn)法則能準(zhǔn)確匹配。而放大倍率為2的圖像樣本，用3種方法均可正常匹配，這與文獻(xiàn)[7]、[9]闡述一致。由此可見，改進(jìn)法對(duì)于無(wú)裁剪圖像可配準(zhǔn)恢復(fù)的最大倍率約為10，且無(wú)需迭代，計(jì)算效率更高。同時(shí)改時(shí)法疊加層數(shù)在3～4層時(shí)，精度變化已經(jīng)很小。通常采用改進(jìn)法層數(shù)設(shè)置為3～4即可。

圖像經(jīng)放大后，在相同分辨率下，超出部分會(huì)被裁剪，這就造成圖片信息的丟失。換言之，同一幅圖片，在經(jīng)過(guò)放大剪切處理后，其有效頻域范圍變窄，干擾頻率增加，增大了配準(zhǔn)難度。

3.2 各類圖像配準(zhǔn)效果比較

分別選用不同類型圖片進(jìn)行配準(zhǔn)比較。實(shí)驗(yàn)選用圖片來(lái)自加州大學(xué)USC圖像庫(kù)，從中選出如圖8所示的具有代表性圖片，上述圖片中包含了頭像、建筑、風(fēng)景、重復(fù)紋理、航拍全景等風(fēng)格。配準(zhǔn)分裁剪和未裁剪兩種情形。裁剪情形，設(shè)定放大倍率為5，旋轉(zhuǎn)角為20°；未裁剪情形，設(shè)定放大倍率為10，旋轉(zhuǎn)角為20°。分別采用FFT、PPFFT、改進(jìn)法及特征點(diǎn)匹配法進(jìn)行比較。其中，為保證較高精度，改進(jìn)法設(shè)置為4層，特征點(diǎn)匹配法采用魯棒性和精度較好的SURF算法[13]。

表2 各圖配準(zhǔn)結(jié)果

表3顯示出，對(duì)于放大倍率為5，有裁剪圖像樣本，改進(jìn)法能準(zhǔn)確配準(zhǔn)；FFT和PPFFT均不能正確匹配；SURF法僅對(duì)4幅圖能準(zhǔn)確匹配，成功率較低。表4顯示出，對(duì)于倍率為0.1，無(wú)裁剪情形，改進(jìn)法能準(zhǔn)確匹配；其他方法均無(wú)法正確匹配。另外，通過(guò)對(duì)USC圖像庫(kù)中樣本大量計(jì)算表明，改進(jìn)法的圖像配準(zhǔn)倍率范圍約為0.1～5。

3.3 圖像拼接

通過(guò)配準(zhǔn)后，將圖像拼接，進(jìn)一步驗(yàn)證改進(jìn)算法的有效性。圖9(b)和圖9(c)分別為圖9(a)局部的不同倍率、角度、平移后的圖像。分別采用改進(jìn)法、PPFFT法和SURF法進(jìn)行配準(zhǔn)比較。

改進(jìn)法配準(zhǔn)后拼接效果如圖9(d)所示，各算法計(jì)算結(jié)果比較如表5所示。

圖8 圖像樣本集合

表3 裁剪后各圖不同方法下配準(zhǔn)結(jié)果比較

表4 未裁剪各圖不同方法下配準(zhǔn)結(jié)果比較

圖9 配準(zhǔn)拼接圖

表5 改進(jìn)法與PPFFT、USRF法配準(zhǔn)參數(shù)比較

圖9(d)顯示出改進(jìn)法對(duì)各圖配準(zhǔn)后，均能恢復(fù)到原圖中正確的位置，圖中在配準(zhǔn)位置存在部分細(xì)長(zhǎng)的白色邊緣線，說(shuō)明配準(zhǔn)后的(,)坐標(biāo)參數(shù)存在較小的誤差。表5反映出改進(jìn)法對(duì)圖9中兩個(gè)局部放大圖均能正確計(jì)算其參數(shù)，PPFFT法是均計(jì)算錯(cuò)誤，無(wú)法配準(zhǔn)。SURF法對(duì)于較小放大倍率局部圖9(b)可實(shí)現(xiàn)配準(zhǔn)，但對(duì)倍率5.2的圖9(c)無(wú)法實(shí)現(xiàn)配準(zhǔn)?？梢?，改進(jìn)法在大倍率圖像配準(zhǔn)中優(yōu)于PPFFT法和傳統(tǒng)的特征點(diǎn)匹配法。

4 結(jié)論

頻域法是圖像配準(zhǔn)的重要方法，因其抗噪性強(qiáng)、不受圖像亮度變化影響、計(jì)算簡(jiǎn)單而應(yīng)用廣泛。針對(duì)現(xiàn)有頻域法FFT和PPFFT對(duì)于大倍率圖像配準(zhǔn)精度和效率難以同時(shí)保證的問(wèn)題，本文研究了一種基于多重頻譜疊加的頻域算法，立足于最大限度減小插值誤差噪聲，該算法通過(guò)多分辨率頻譜插值構(gòu)造更接近對(duì)數(shù)極坐標(biāo)網(wǎng)格，并給出了分辨率參數(shù)設(shè)置和算法流程。最后通過(guò)實(shí)驗(yàn)進(jìn)行驗(yàn)證，結(jié)果表明：改進(jìn)法對(duì)無(wú)裁減圖像最大配準(zhǔn)倍率可至10，對(duì)裁減圖像可至5，而FFT和PPFFT（無(wú)迭代）對(duì)于兩種類型圖像都約為2；相對(duì)于特征點(diǎn)匹配法，改進(jìn)法也適用于更大倍率的圖像配準(zhǔn)。

[1] 王磊, 葛鏡, 熊曼子. 幀間預(yù)測(cè)編碼中的運(yùn)動(dòng)估計(jì)算法研究[J]. 計(jì)算機(jī)與數(shù)字工程, 2007, 35(12): 28-31.

[2] 鐘錦, 吳昊. 霧天視頻圖像增強(qiáng)與運(yùn)動(dòng)目標(biāo)跟蹤模型及方法[J]. 計(jì)算機(jī)仿真, 2013, 30(8): 402-407.

[3] 徐端全, 朱光喜. 基于幀間預(yù)測(cè)的視頻水印算法[J]. 計(jì)算機(jī)工程與應(yīng)用, 2008, 44(24): 22-24.

[4] 陳錢. 紅外圖像處理技術(shù)現(xiàn)狀及發(fā)展趨勢(shì)[J]. 紅外技術(shù), 2013, 35(6): 311-318.

[5] 杜小平, 劉明, 夏魯瑞, 等. 基于光譜角累加的高光譜圖像異常檢測(cè)算法[J]. 中國(guó)光學(xué), 2013, 6(3): 325-331.

[6] 周武, 胡躍明. 基于相位相關(guān)和重采樣的亞像素圖像配準(zhǔn)算法[J]. 華南理工大學(xué)學(xué)報(bào), 2010, 38(10): 68-73.

[7] Reddy B S, Chatterji B N. An FFT-based technique for translations, rotations and scale-invariant image registration[J].. 1996, 5(8): 1266-1271.

[8] 劉漢洲, 郭寶龍, 馮宗哲. 基于傅里葉變換的遙感圖像配準(zhǔn)[J]. 光電子×激光, 2006, 17(11): 1393-1397.

[9] Keller Y, Averbuch A, Israeli M. Pseudopolar-based estimation of large translations, rotations and scalings in images[J]., 2005, 14(1): 12-22.

[10] Liu H, Guo B, Feng Z. Pseudo-Log-Polar Fourier Transform for Image Registraion[J]., 2006, 13(1): 17-20.

[11] 趙振民, 彭國(guó)華, 符立梅. 基于形狀模板的快速高精度可靠圖像匹配[J]. 計(jì)算機(jī)應(yīng)用, 2010, 30(2): 441-444.

[12] 吳浩, 鄧宏彬, 何少陽(yáng). 基于分塊灰度投影的無(wú)人飛行器視頻穩(wěn)像方法[J]. 北京理工大學(xué)學(xué)報(bào), 2013, 33(4): 385-389.

[13] 劉少鵬, 郎躍東, 丁祝順. 改進(jìn)的SURF算法及其在目標(biāo)跟蹤中的應(yīng)用[J]. 傳感器與微系統(tǒng), 2012, 31(12):148-152.

[14] Harold S Stone, Bo Tao, Morgan. Analysis of image registration noise due to rotationally dependent alising. Commum[J].2003, 14(2):114-135.

A New Image Registration Method Based on Overlaying of Multiple Spectrums

ZHANG Yi-fei1，NIU Shou-Rui1，MA Na2，ZHANG Chang-quan1

(1. 63963,100072,; 2.,100049,)

Of frequency-domain method, registration accuracy and efficiency of FFT or PPFFT for large scale image is difficult to be obtained simultaneously. With this problem considered, a new registration method based on overlaying of multiple spectrums is proposed, which interpolates spectrums of multi resolution and generates the grid closest to log-polar, to minimize interpolation error noise. In addition, how to set resolution parameter and the algorithm flow is also explained. Finally, to validate the accuracy and feasibility of the algorithm, three examples were calculated through the new algorithm, and the result shows as followed: as for the image without cutting, the maximum registration scale of the improved method without iterations can reach 10, and as for the image with cutting, the same one can reach 5, while the FFT and PPFFT (non iterative) for the two kinds of image is about 2; compared with the feature point matching method, the improved method is also applied to image with larger scale.

multiple spectrum，large scale registration，log-polar ordinary，interpolation error

TP391.41

A

1001-8891(2015)05-0424-07

2014-11-02；

2015-01-18.

張軼飛（1980-），男，工程師，博士，主要研究圖像匹配、電子穩(wěn)像等。E-mail：flightzyf@126.com。

中國(guó)博士后科學(xué)基金，編號(hào)：2012T50870。