超圖約束和改進(jìn)歸一化互相關(guān)方法相結(jié)合的圖像配準(zhǔn)算法

朱 明，姚 強(qiáng)，唐 俊，張 艷

(1. 安徽大學(xué) 電子信息工程學(xué)院， 安徽 合肥 230601； 2. 偏振光成像探測技術(shù)安徽省重點(diǎn)實(shí)驗(yàn)室， 安徽 合肥 230031)

圖像配準(zhǔn)是對(duì)不同時(shí)間、不同視角、不同來源的兩幅或多幅圖像進(jìn)行空間幾何變換，使得各個(gè)圖像中相同場景在幾何上對(duì)準(zhǔn)的過程。圖像配準(zhǔn)是圖像處理一個(gè)重要的基礎(chǔ)問題，是諸多應(yīng)用，如目標(biāo)跟蹤檢測、目標(biāo)識(shí)別、對(duì)地觀測、安全監(jiān)控、智能交通、醫(yī)學(xué)成像等的先決條件[1]。

圖像配準(zhǔn)方法基本上可以分為基于區(qū)域和基于特征兩大類?；趨^(qū)域的配準(zhǔn)方法是直接利用像素點(diǎn)的灰度值來確定待配準(zhǔn)圖像之間的幾何變換關(guān)系，這類方法充分利用了圖像所包含的信息，不需要提取圖像的特征，而是直接利用其灰度信息，因此能提高估計(jì)的精度和魯棒性，但由于需要計(jì)算匹配點(diǎn)周圍區(qū)域點(diǎn)的灰度信息，因此存在計(jì)算量大、速度較慢等問題?；谔卣鞯呐錅?zhǔn)方法是目前應(yīng)用最為廣泛的方法，其優(yōu)點(diǎn)是能夠?qū)?duì)整個(gè)圖像的分析轉(zhuǎn)化為對(duì)特征的分析，極大地減小了運(yùn)算量，并且對(duì)灰度變化、圖像變形和遮擋等都有較好的適應(yīng)能力[2-6]。Pei等[7]將圖像進(jìn)行分割形成包含不同數(shù)量角點(diǎn)的局部區(qū)塊，對(duì)密集角點(diǎn)區(qū)域進(jìn)行篩選，提高了圖像配準(zhǔn)的效率和精度。Kang等[8]提出了結(jié)合互信息和角點(diǎn)檢測的圖像配準(zhǔn)算法，該方法利用互信息作為特征點(diǎn)粗匹配的相似準(zhǔn)則，然后采用隨機(jī)抽樣一致性(RANdom SAmple Consensus, RANSAC)算法消除誤匹配進(jìn)行配準(zhǔn)。文獻(xiàn)[9]提出了一種基于最近鄰圖結(jié)構(gòu)的圖形變換(Graph Transformation Matching, GTM)配準(zhǔn)算法，該算法使用最近鄰約束策略構(gòu)造待配準(zhǔn)特征的局部鄰近結(jié)構(gòu)作為特征描述方法來剔除錯(cuò)誤匹配對(duì)，但可能會(huì)因?yàn)橄嗤徲蚪Y(jié)構(gòu)的錯(cuò)誤匹配點(diǎn)的存在，而無法完全剔除錯(cuò)誤匹配點(diǎn)對(duì)。文獻(xiàn)[10]對(duì)RANSAC算法進(jìn)行了改進(jìn)，提出了一種改進(jìn)樣本一致性(Fast Sample Consensus, FSC)配準(zhǔn)算法，該算法利用不同均方根誤差獲得不同正確匹配率的樣本子集，從高正確率的樣本子集中得到全局變換模型剔除低正確率的樣本子集中的錯(cuò)誤匹配進(jìn)行配準(zhǔn)，它與RANSAC算法一樣都過于依賴隨機(jī)樣本的選擇。文獻(xiàn)[11]提出了一種特征點(diǎn)對(duì)齊度準(zhǔn)則，并基于該準(zhǔn)則進(jìn)行圖像配準(zhǔn)，該方法首先提取特征點(diǎn)的角度信息，然后計(jì)算特征點(diǎn)對(duì)之間的對(duì)齊度，從而得到最終的匹配對(duì)進(jìn)行配準(zhǔn)，這樣不僅計(jì)算量大，而且出格點(diǎn)的存在會(huì)影響該方法的配準(zhǔn)精度。

為提高圖像配準(zhǔn)的精度和配準(zhǔn)方法的適應(yīng)能力，本文提出了超圖約束和改進(jìn)歸一化互相關(guān)方法相結(jié)合的圖像配準(zhǔn)算法。

1 初始匹配

1.1 Hessian-Affine特征

Hessian-Affine特征檢測算子是Mikolajczyk等在文獻(xiàn)[12-13]中提出和完善的。Hessian-Affine特征檢測算子是基于圖像上某點(diǎn)的Hessian矩陣進(jìn)行興趣點(diǎn)計(jì)算，選擇在多尺度下Hessian矩陣行列式具有局部最大的興趣點(diǎn)。在每個(gè)獨(dú)立的尺度下，得到一系列對(duì)旋轉(zhuǎn)、尺度、平移、亮度改變穩(wěn)定的點(diǎn)，然后運(yùn)用多尺度迭代算法進(jìn)行空間定位和篩選尺度、仿射不變特征。該算子相對(duì)其他仿射不變算子而言，可以檢測出更多特征區(qū)域且具有較高的準(zhǔn)確性[14]，因此可以有效解決圖像配準(zhǔn)中局部畸變等難題。

1.2 改進(jìn)的NCC匹配算法

歸一化互相關(guān)(Normalized Cross Correlation NCC)匹配方法通過比較兩幅匹配圖像在特征點(diǎn)上的歸一化互相關(guān)系數(shù)來衡量匹配的程度，最大相關(guān)系數(shù)對(duì)應(yīng)最佳匹配。在得到的特征點(diǎn)集合中，以每個(gè)特征點(diǎn)為中心，取一個(gè)(2N+1)×(2N+1)大小的相關(guān)窗，設(shè)參考圖像I中第i個(gè)特征點(diǎn)和輸入圖像(待配準(zhǔn)圖像)J中第j個(gè)特征點(diǎn)對(duì)應(yīng)的窗口像素的灰度值分別是I(x,y)和J(x,y)，通過式(1)歸一化互相關(guān)函數(shù)計(jì)算兩個(gè)特征點(diǎn)之間的NCC值進(jìn)行特征點(diǎn)匹配。NCC的值域?yàn)閇-1，1]，NCC為-1時(shí)，表示兩個(gè)相關(guān)窗口不相似；NCC為1時(shí)，則表示兩個(gè)窗口完全相同。

(1)

設(shè)由HNCC算法得到的I和J的s個(gè)特征點(diǎn)分別為v1,v2,v3,…,vs和u1,u2,u3,…,us，通過雙向匹配策略可以較大程度地提高匹配正確率，但仍會(huì)存在一部分誤匹配點(diǎn)，接下來仍需要剔除剩余錯(cuò)誤匹配并在剩余的匹配點(diǎn)對(duì)中求解變換矩陣。

2 超圖匹配理論

若任意一條邊均連接兩個(gè)以上的點(diǎn)，則稱為超圖，如果每條邊均連接k(k≥3)個(gè)點(diǎn)，則稱該超圖為k一致超圖。相對(duì)于一般圖來說，超圖能很好地描述數(shù)據(jù)點(diǎn)間的多維關(guān)聯(lián)信息[15-16]。

圖1 相似度計(jì)算模型Fig.1 Similarity calculation model

Hi,j,k=

(2)

(3)

3 基于超圖約束的圖像配準(zhǔn)算法

Score(t)=Score(t)+Hi,j,k，t={(vi,ui),(vj,uj),(vk,uk)}

(4)

其中，σs∈(0,1)，t表示當(dāng)前三角結(jié)構(gòu)下的3個(gè)匹配對(duì)。

如果兩對(duì)三角結(jié)構(gòu)中的3個(gè)匹配對(duì)都正確，那么這兩對(duì)三角結(jié)構(gòu)的相似度較大，相應(yīng)的各個(gè)匹配對(duì)的分?jǐn)?shù)值就有較大的增幅；如果三角結(jié)構(gòu)中存在錯(cuò)誤匹配，那么得到的相似度值較小或者為0，匹配對(duì)的分?jǐn)?shù)值增加較小。在比較完所有的三角結(jié)構(gòu)之后，得到的正確匹配對(duì)的分?jǐn)?shù)值會(huì)高于錯(cuò)誤匹配對(duì)的分?jǐn)?shù)值。

所以，根據(jù)Score(x)的值按從大到小的順序?qū)對(duì)特征點(diǎn)對(duì)排序，得到s對(duì)匹配對(duì)集合：C={c1,c2,…,cs}，其中ci=(vi,ui)為第i個(gè)匹配對(duì)，且Score(ci)≥Score(ci+1)。選取集合C中前4個(gè)特征點(diǎn)對(duì)初始化正確匹配對(duì)集合C′={c1,c2,c3,c4}并求解圖像變換矩陣，然后逐步判斷集合C中剩余的匹配點(diǎn)對(duì)，并更新正確匹配對(duì)集合C′和變換矩陣T，具體步驟如下：

步驟1：對(duì)參考圖像I和待配準(zhǔn)圖像J中的s對(duì)特征點(diǎn)對(duì)，根據(jù)Score(x)值從大到小排序，得到s對(duì)匹配對(duì)集合：C={c1,c2,…，cs}。

步驟2：用集合C的前k個(gè)匹配對(duì)初始化正確匹配對(duì)集合C′，初始化k=4。

步驟3：檢驗(yàn)集合C中第k+1個(gè)匹配對(duì)，根據(jù)正確匹配對(duì)集合C′求變換矩陣T，對(duì)集合C中在待配準(zhǔn)圖像J的第k+1個(gè)特征點(diǎn)做變換，得到待檢驗(yàn)點(diǎn)在參考圖像I上的坐標(biāo)，利用均方根誤差選擇是否剔除此匹配點(diǎn)對(duì)，如果所得均方根誤差小于容錯(cuò)誤差，則加入集合C′，并更新k=k+1。

步驟4：判斷是否檢驗(yàn)完集合C中剩余的s-k個(gè)匹配對(duì)，若k

步驟5：通過雙線性插值對(duì)待配準(zhǔn)圖像進(jìn)行重采樣，最終實(shí)現(xiàn)配準(zhǔn)。

4 實(shí)驗(yàn)及結(jié)果分析

實(shí)驗(yàn)圖像共有4組，如圖2所示，左邊為參考圖像，右邊為待配準(zhǔn)圖像，第一組圖2(a)和第二組圖2(b)是來自Mikolajczyk測試數(shù)據(jù)集的“wall”和“graf”，兩組均為不同視角下的旋轉(zhuǎn)和尺度變換圖像，并且包含不同形式的重復(fù)紋理。第三組圖2(c)是不同視點(diǎn)拍攝的同一地點(diǎn)的遙感圖像，第四組圖2(d)是兩幅尺寸不同而且存在較大角度差異的遙感圖像。

(a) 第一組“wall”圖像(a) The first set of “wall” images

(b) 第二組“graf”圖像(b) The second set of “graf” images

(c) 第三組遙感圖像(c) The third set of remote sensing image

(d) 第四組遙感圖像(d) The fourth set of remote sensing image圖2 實(shí)驗(yàn)圖像Fig.2 Experimental images

在初始匹配中，NCC歸一化互相關(guān)匹配和改進(jìn)得到的HNCC匹配方法在四組實(shí)驗(yàn)圖像上的匹配效果用Precision作為評(píng)價(jià)指標(biāo)。該指標(biāo)直觀反映出匹配方法的有效性，Precision定義如下：

Precision=Nc/(Nc+Nf)

(5)

其中，Nc是指正確匹配對(duì)的數(shù)目，Nf是指錯(cuò)誤匹配對(duì)的數(shù)目。Precision值越大，則匹配效果越好。

在四組圖像提取的特征點(diǎn)中，隨機(jī)選擇部分特征點(diǎn)作為NCC與HNCC算法的匹配特征點(diǎn)，兩種方法關(guān)于Precision的實(shí)驗(yàn)對(duì)比結(jié)果如圖3所示。

圖3 NCC和HNCC算法關(guān)于Precision的性能對(duì)比Fig.3 Comparison of NCC and HNCC algorithms on precision performance

配準(zhǔn)算法的一個(gè)性能評(píng)價(jià)指標(biāo)采用均方根誤差(Root Mean Square Error, RMSE)，其值越小表明配準(zhǔn)效果越好。均方根誤差是各個(gè)誤差平方和的平均值的開方，計(jì)算公式為：

(6)

對(duì)圖像配準(zhǔn)精度的另一個(gè)指標(biāo)采用歸一化互信息(Normalized Messure of mutual Information, NMI)，它是一個(gè)重要的全局指標(biāo)，由Studholme等[17]提出，其值越大則表明圖像配準(zhǔn)的效果越好，其中NMI的最大值為2。

為了驗(yàn)證文中配準(zhǔn)算法的有效性，使用圖3中HNCC算法的匹配結(jié)果作為初始匹配的輸出，將本文配準(zhǔn)算法與RANSAC算法剔除誤匹配算法、GTM算法、FSC算法進(jìn)行比較，其中對(duì)于求解圖像變換矩陣的方法均采用最小二乘法，變換模型選擇射影變換(projection transform)模型。上述幾種算法重復(fù)100次在均方根誤差上的平均值取得的對(duì)比結(jié)果和在NMI上的平均值對(duì)比結(jié)果如表1所示。

由圖3知，改進(jìn)得到的HNCC算法在四組圖像中的匹配準(zhǔn)確率均高于NCC方法，因此HNCC算法匹配性能最好。由表1可知，在相同的初始匹配情況下，本文算法能夠在幾種算法的對(duì)比中取得最低的均方根誤差和最高的NMI值。在實(shí)驗(yàn)中，雖然HNCC算法極大地提高了初始匹配正確率，但由于在初始匹配中使用的特征點(diǎn)是從提取的特征點(diǎn)集合中隨機(jī)選取一部分得到的，所以在各組圖像上得到的初始匹配對(duì)中錯(cuò)誤匹配所占的比例會(huì)比較高，尤其是在第二組實(shí)驗(yàn)圖像中，圖像形變較大，正確匹配對(duì)所占的比例非常低，正確率僅為0.32。在這種情況下，RANSAC、GTM和FSC方法配準(zhǔn)失敗，而本文算法不僅能成功配準(zhǔn)，而且效果較好。實(shí)驗(yàn)中導(dǎo)致配準(zhǔn)失敗的原因是無法全部剔除錯(cuò)誤的匹配，而本文算法則可以完全剔除錯(cuò)誤的匹配。圖4為四組圖像在本文算法下的匹配和配準(zhǔn)結(jié)果。

表1 幾種算法配準(zhǔn)精度對(duì)比

注：“-”代表配準(zhǔn)失敗。

(a) 第一組圖像匹配及配準(zhǔn)結(jié)果(a) Results of matching and registration results of the first set of image

(b) 第二組圖像匹配及配準(zhǔn)結(jié)果(b) Results of matching and registration results of the second set of image

(c) 第三組圖像匹配及配準(zhǔn)結(jié)果(c) Results of matching and registration results of the third set of image

(d) 第四組圖像匹配及配準(zhǔn)結(jié)果(d) Results of matching and registration results of the fourth set of image圖4 本文算法在實(shí)驗(yàn)圖像上的匹配和配準(zhǔn)結(jié)果Fig.4 Results of matching and registration of the algorithm in the experimental image

5 結(jié)論

針對(duì)各場景中的圖像配準(zhǔn)問題，提出了超圖約束和改進(jìn)歸一化互相關(guān)方法相結(jié)合的HNCC算法。實(shí)驗(yàn)結(jié)果表明，HNCC算法有較好的匹配效果，配準(zhǔn)方法具有較高的配準(zhǔn)精度和適應(yīng)能力，且對(duì)于形變較大的圖像也有很好的配準(zhǔn)效果。