基于結構信息的圖像拼接算法①

韓偉東,閔士桐

(東北大學 理學院,沈陽 110004)

圖像拼接研究已有數十年,拼接算法也較為成熟.近年來,關于灰度信息的方法研究也逐漸減少,現在提出關于彩色圖像的CSIFT[1](A SIFT Descriptor with Color Invariant Characteristics)算法,對于醫學圖像和遙感圖像拼接研究占了很大比例.利用Harris算子提取特征[2]時,由于無法去除誤配點對,Capel[3]在利用Harris算子提取特征點的同時,引入RANSAC (Random Sample Consensus)[4]算法,去除由Harris提取的誤配點對,進一步提高精度.而Harris算法不能處理尺度變換圖像.Lowe在文獻[5]中提出SIFT (Scale Invariant Feature Transform)算法及改進.提取特征的算法還有點特征提取算子 (如Harris算子和改進算子、Susan算子及其改進算子[6])、線特征提取算子 (如LOG算子[7]、Canny算子及其改進算子[8])和區域特征提取算子[9]等.2001年,EFROS提出了基于圖像渲染的紋理合成算法[10],進行了對紋理渲染以及合成.2012年,Xu基于相對總變差模型的圖像結構提取方法.本文將利用這種算法與圖像配準算法相結合,處理紋理多、背景復雜的圖像拼接問題.

1 圖像配準概念

相機將三維空間場景拍成二維是一種映射關系.拍攝時,世界坐標系 (Xw,Yw,Zw)、相機坐標系 (XC,YC,ZC)、圖像坐標系 (X,Y)三者關系[11]如圖1所示.

圖1 相機成像坐標系

點由世界坐標系到相機坐標系,最后在投影到圖像平面上.圖像配準就是對這種圖像變換的關系進行求解,使得兩幅圖像上對應像素點位置保持一致.對于參考圖像I1和帶配準圖像I2,在點 (x,y)處的灰度值可以分別表示為I1(x,y)和I2(x,y),則兩幅圖像可以表示為:

圖像配準目的是找到映射T,使得將兩幅圖變換為同一坐標系.

對圖像處理的配準方法有如下3類:

1)基于圖像灰度信息的配準方法

利用搜索算法找出時的相似度最有變換模型.基于圖像灰度信息的配準方法一般可以分為3類:基于互相關法[12]、基于序貫相似度檢測匹配法[13]、基于互信息法[14].

2)基于變換域內信息的配準方法

利用傅立葉變換為基礎進行頻域內的配準.算法具有一定抵抗噪聲的魯棒性.

3)基于圖像特征信息的配準方法

提取點、線、邊緣等特征信息,減少計算量、提高時間效率,對圖像的灰色變化有一定魯棒性.

2 圖像結構信息的拼接算法 (SKM)

對于兩幅或多幅圖像進行拼接時,提取出的圖像特征點的好壞對圖像拼接具有巨大影響.

SIFT (Scale-Invariant Feature Transform)[1]算法是一種較好的局部特征提取算法.但是在存在較多的紋理結構噪聲的圖像中,利用SIFT算法提取特征點,會提取數量較大的特征點,影響匹配的效率和準確性.如圖2流程圖所示,本文引用RTV (Relative Total Variation)算法[15]提取圖像結構信息,有效地去除圖像紋理噪聲.在此基礎上再對結構圖像進行SIFT特征的提取與匹配,然后利用RANSAC (RANdom SAmple Consensus)[4]算法對匹配進行篩選,并將左右兩側的圖像進行亮度調整.由SKM算法得到變換矩陣H,作用于兩幅原圖像,完成圖像的拼接.

圖2 SKM算法流程圖

2.1 基于總變差模型的圖像主結構提取算法

圖像紋理的去除選用既有的基于相對總變差模型的紋理結構提取方法 (RTV)[15],在圖像拼接之前對給定的兩幅照片進行主結構提取,然后進行拼接.該算法較其之前的雙邊過濾等算法處理圖像的程度更強,效果也更加明顯,可以充分保證對可能出現在紋理之上的特征點的過濾.

在此算法中,定義總變差量度:

其中,q屬于以像素p為中心的矩形區域R(P).Dx(p)和Dy(p)是x和y方向上對于像素p的圖像總變化,用來計算R(P)內部的絕對空間差異.gp,q是加權函數,表示為:

其中,σ控制窗口的空間尺度.在紋理突出的圖像中,表明圖像總變化的細節像素和的結構像素變差量度 D 都對視覺顯著性有作用.

為了幫助區分突出的結構和紋理元素,需要計算圖像固有的變化量,表示為:

L捕獲整體空間變化.因為就方向而言,一個像素的?S的符號可能是正的或負的,所以?S的符號取決于圖像中的顏色梯度是否一致.

由于一個局部圖像中的邊緣比復雜圖案的紋理能提供更多相近方向的漸變,算法假定在一個圖像中產生的L 包含的紋理通常小于圖像中包括結構邊緣的紋理,即噪聲的變差要比圖像的自然變化產生的基本變差大.為進一步增強紋理與結構之間的對比 (尤其對于視覺上顯著的區域),將D 與L 組合形成一個更有效的紋理分解正則化器.從圖像中去除紋理的效果由正則化器引導,該項稱為相對總變差 (RTV).目標函數最終表示為:

其中,(Sp-Ip)2可使輸入和結果不會產生較大偏差.從圖像中去除紋理的效果由正則化器引導,該項稱為相對總變差 (RTV).λ為權重.ε為一小量,從而使分母不為0.

通過求解該最小值來提取結構圖像.以x方向為例:

設

其中,Gσ為標準差為σ的Gaussian核函數,*表示卷積.y方向討論類似.原目標函數可以寫成矩陣形式:

其中,vS和vI分別代表S和I的兩個列向量,Cx和Cy是向前差分梯度算子的Toeplitz矩陣,Ux,Wx,Uy,Wy為對角矩陣,對角元素分別為Ux[i,i]=Uxi,Uy[i,i]=Uyi,Wx[i,i]=Wxi,Wy[i,i]=wyi.模型最終表示為:

在計算機程序中,RTV算法函數有兩個主要參數λ和ε.λ參數控制處理強度,取值范圍為 (0,0.05];ε參數控制最終結果的銳度,該值越小,結果圖像的銳度越高,取值范圍為 (0.001,0.03].

2.2 基于結構信息的配準算法

SIFT算法基于尺度空間理論[16],對于圖像的縮放、旋轉、仿射變換保持較好的穩定性.SIFT算子可以在紋理較少的圖像中提取更多特征,具有良好的性質.但在較多紋理的圖像中,該算子將提取較多的特征點.所以對于一般具有較多紋理噪聲的圖像,利用RTV算法對圖片紋理處理,再利用SIFT特征點的提取進行匹配.通過由SKM算法得到的變換矩陣H作用于原始圖像,從而完成對圖像進行拼接.

SIFT算法實現[17]如下:

1)構建圖像的尺度空間

文獻[18,19]中Lindeberg等人證明Gaussian核是實現尺度變換的唯一線性變換核.圖像的尺度空間L(x,y,σ)可以定義為圖像I(x,y)與高斯核函數G(x,y,σ)的卷積,

其中,σ是尺度因子,σ越小,在視覺上圖像就越清晰,σ越大,圖像越模糊,表示卷積,(x,y)代表像素的位置.

為了在尺度空間中檢測到穩定的特征值點,采用高斯差分尺度空間 (DoG空間,即Difference of Gaussian scale-space),DoG算子定義為兩個相鄰尺度的Gaussian核間的差分,公式表示為:

其中,k表示兩個相鄰尺度空間倍數的常數.

式(14)是由尺度歸一化的LoG (Laplace of Gaussian)函數 σ2?2G近似得到,LoG算子的極值能夠產生穩定的圖像特征.用DoG算子來代替尺度歸一化的LoG算子進行極值檢測,在實際計算過程中,將高斯金字塔 (如圖3)中每組圖像中的相鄰的上下兩幅圖像的像素值相減,得到高斯差分圖像.

圖3 高斯金字塔模型

如圖4,左邊的圖像是由初始圖像開始形成的高斯金字塔圖像,每一階的第一個圖像是由上一階的最后的高斯圖像進行降采樣得到的.

2)空間極值點的檢測

對尺度空間DoG函數進行曲線擬合 (子像素插值),利用DoG函數在尺度空間Taylor展開.

圖4 高斯差分圖像的形成

將修正因子代入,得到:

上式去除那些對比度較低的不穩定極值點.Lowe的試驗顯示,所有取值小于0.04的極致點均可舍去.

DoG算子具有較強的邊緣響應現象,一個較差的DoG算子的極值在橫跨邊緣的地方有較大的主曲率,而在垂直邊緣的方向有較小的主曲率.主曲率可由Hessian矩陣得到:

H的特征值α和β代表x和y方向的梯度:

D的主曲率和H的特征值成正比,其中α和β分別為矩陣H中的較大與小特征值.令α=γβ,則

當γ越大時,即在某一個方向的梯度值越大,而在另一個方向的梯度值越小,(γ+1)2/γ值越大,為了剔除這樣的邊緣響應點,需要設置一個閾值R(在Lowe的文章中,R取10),可通過如下公式來檢測判斷是否需要剔除極值點,

3)特征點方向分配與描述向量的生成

為使算子具有旋轉不變性,利用特征點的鄰域像素梯度給分配一個方向參數.對在DoG金字塔中求得的特征點,求其所在的金字塔圖像中3σ鄰域內像素點的梯度和方向分布,梯度的大小及方向為:

用一個梯度方向的直方圖進行統計,范圍0～360度,其中每10度一個柱.每個采樣點按照其梯度方向θ(x,y)加權統計到直方圖,權值為幅度m(x,y)和貢獻因子的乘積.貢獻因子是采樣點到關鍵點距離的量度,距離越大,貢獻因子越小.直方圖的峰值代表了該關鍵點處鄰域梯度的主方向.

接著將坐標軸的方向旋轉為特征點的主方向,并以特征點為中心選取16×16的鄰域窗口,將窗口平均地劃分為16個4×4的區域,在區域內求取8個分區的梯度直方圖,利用 Gaussian函數進行加權處理,如圖5所示,得到一個16×8維的向量,最后將向量進行歸一化處理,減少光照的影響,生成特征點的描述向量.

圖5 圖像描述算子的生成

圖5中左圖為特征描述子生成時其四分之一的像素的梯度方向,圓圈表示高斯加權的范圍,右圖為加權到8個方向后生成的描述子.

4)特征點匹配與篩選

以特征向量的歐氏距離作為特征點判定相似性的度量,取圖像中某個特征點,找出與另一圖像中距離最近的兩個特征點,如果最近距離與次近距離的比值小于某個閾時就接受這對匹配點,閾值一般取0.4～0.6之間.閾值越小,求出的匹配點對越少,匹配的穩定性越高.最后利RANSAC算法篩選匹配點[20-22],去掉匹配錯誤的點,提高匹配精度.利用這個模型測試所有數據,并計算滿足這個模型數據點的個數與投影誤差 (即代價函數),選出最優模型即代價函數最小.

具體步驟如下:

(1)從匹配點集中隨機選出4組匹配點對.

(2)計算變換矩陣H:

其中,s是尺度參數.

(3)通過變換矩陣H,對匹配點進行變換,并設置誤差度量函數,如果匹配點對變換后不超過誤差,則認為是一致集中的元素,遍歷完所有點對后,返回一致集中的元素個數.根據一致集中的元素個數判斷是否為最優,若是則更新最優一致集.

(4)更新當前的錯誤概率,若大于允許的最小概率則重復 (1)到 (3)迭代,知道小于最小概率時結束.

SIFT算法在特征匹配過程中,要對128維的特征描述向量進行計算,匹配時計算量較大.特別是在紋理較多的圖像中,提取的特征點個數較多,計算量就更大了.而生活中的場景一般有較多紋理結構,所以利用基于結構信息拼接算法(Structural Keypoint Matching,SKM),采用基于RTV的圖像主結構提取算法來像的結構,并在提取的結構圖像中進行SIFT特征點的提取與匹配特征點的提取與匹配,這樣可以避免圖像中細致紋理噪聲在圖像特征提取過程的影響.

SIFT算法在求特征點時,若提取了較多的特征點,就會占據較多內存空間來儲這些特征點描述向量,尤其是在高分辨率的圖像中,并且隨著提取特征點數量的增加會極大地增加特征點匹配時的計算量.而SKM算法提取圖像的主結構后,去掉了紋理噪聲,會使特征點數減少,從而減少計算量.下面以圖6、圖7兩幅紗窗示意圖為例,介紹基于信息結構的圖像拼接算法.

分別對圖6和圖7進行主結構提取,去除紋理.

如圖8所示,可以發現大部分細節紋理噪聲都被消去,并保留了圖像的主要結構特征,同時對其進行SIFT特征點的提取.

圖6 紗窗左側圖

圖7 紗窗右側圖

圖8 提取與匹配

最后根據特征點匹配的結果,求出圖像變換模型矩陣的參數.通過仿射變換,以及得出的模型參數對圖像進行變換和拼接,得到最終圖像,如圖9所示.

圖9 變換拼接圖

3 實驗分析與討論

3.1 圖像去紋理效果分析

對圖像去除紋理可以使圖像的顏色變化趨于連續,在物體和圖案的頂點處的特征點更容易識別,若進行直接拼接,有些情況下會造成平行的特征點匹配,或者在某一小范圍區域出現大量特征點對.這些特征點對后面的拼接過程起到的作用相當,因此即使去除一部分也不會對拼接造成困難.在進行紋理去除后,上述現象有了明顯的改善,特征點較原來可減少一半以上.

由2.1的理論分析知,λ為比較特征差異的程度,λ增大時,由該部分構成的方程 (7)在求解時將更偏重于此項,故λ可以簡化看作為去紋理強度.

在實際應用過程中,發現只需取較小的處理強度值λ即可將紗窗網格去除.另外,當采用不同的λ值時,該方法對圖像的特征點篩選作用也略有不同.

為了達到最好效果,即在保證圖像固有元素的完整性和可區分性的基礎之上,盡量少地保留特征點,分別對λ值進行了在0.1和0.01的數量級上的改動(這里進行的是逐步縮小區間的做法,需要大量試驗,只展示一組圖像,如圖10-圖12所示),最終發現只需λ值在(0,0.03]范圍時,能夠得到較好效果,當超過0.05時,效果便不再顯著,且圖像清晰度會大幅下降.

圖10 RTV 算法測試圖 (λ=0.005,σ=2)

圖11 RTV 算法測試圖 (λ=0.01,σ=2)

圖12 RTV 算法測試圖 (λ=0.05,σ=2)

對于另一個參數銳度,在允許范圍內更改其值,沒有發現拼接過程有很大變化.分析其原因,應為銳度值與圖像的細致程度為正相關,不能符合減少特征點的目標.

3.2 對虛影的處理結果分析

相對于RTV算法對紋理的去除及對后續拼接的影響,其對拼接產生的虛影的去除效果并不明顯.事實上,由于固有拼接方法在最后的拼接處理時,將兩幅圖像的對應像素做線性組合,這種連續變化的模糊像素與網格等有明顯特征的、與附近需保留的像素在RGB顏色數值上形成突躍的紋理有一定區別,不一定能被RTV算法的提取紋理結構的系統所識別,因此處理效果較不明顯,但實驗發現加強處理強度后同一色塊中的像素會相互影響進而融為一體,故僅僅在相近顏色的像素被RTV處理之后,虛影有一定減弱的程度.

3.3 匹配率對比和SKM的算法評價

實驗的結果中主要有下列參考值以評判幾種算法的性能:

(1)特征點數

特征點是拼接圖像的基礎.特征點的數量與計算量、準確度等后續要素都密切相關,保證特征點數在合理范圍內,是算法的首要目標.

(2)圖像匹配率

圖像配準后對配準的圖像進行圖像拼接,根據特征點的匹配率來評價拼接圖像的效果.匹配率越高,說明算法的對特征點的利用程度越強,算法的運行更加高效而浪費的數據資源越少.

下面由兩組實驗測試SKM算法與經典特征點算法的各個參數之間的對比和實驗效果.

第一組測試中,如圖13、圖14所示,以紋理較多的墻面和地磚為實驗,測試SKM算法和經典算法下特征點數及匹配率.如表1所示.

圖13 經典算法下的特征點匹配圖像

圖14 SKM算法下的特征點匹配圖像

表1 兩種算法對第一組測試圖像配準的性能比較

由表1可以看出,SKM算法所確定的特征點僅為經典算法的60%-70%,在運算次數與其平方成正比的匹配過程中,該特質有效減少了特征點匹配時的計算量,由于去噪作用,對拼接產生干擾的特征點被篩去,進而匹配率也有所提升.通過對比可知,SKM算法的特征點配對數要比經典算法少很多,而特征點的匹配效果還是很好的.

通過類似的一些圖像配準實驗,很容易發現,在紋理較多的圖像中,SKM算法的效率比經典算法的效率要高,且保證了配準的確性性.甚至在背景十分復雜的圖像中,SKM算法的優勢更加明顯.

4 實驗結果對比與分析

實驗采用了紗窗、涂鴉墻、籃球場網圖、馬路等背景復雜且噪聲較多的圖像作為研究對象.在導入圖像之后,立即對圖像做去紋理的處理.由于處理后的輸出為兩個圖像矩陣,需將其再轉化為圖像格式.經此步后轉而進行圖像拼接處理.

在圖像處理過后,利用SKM算法算出變換矩陣H,由此得到最終輸出結果,完成拼接并顯示圖片.

4.1 圖像數據來源

飾演的所有測試圖像均由由VivoX21A手機拍攝,由于當圖像的尺寸較大 (如1373×7373)時,程序處理時間過長,可能由于速度浮動和而無法比較且未知因素出現幾率增加,所以在進行實驗前在盡可能保證圖像質量的情況下對圖像進行了縮放處理,縮小后圖像大小為500×500.

4.2 實驗環境

硬件環境:運行實驗的計算機CPU型號為Intel (R)Core (TM)i5-6300HQ CPU @ 2.30 GHz,內存為8.00 GB(2133 MHz).

軟件環境:操作系統為 Microsoft Windows 10專業版 (64位),程序運行平臺為MatlabR2016a,部分代碼來源于Lowe的siftDemoV4[5].

4.3 實驗結果對比和分析

1)在第一組實驗中,我們采用了馬路街道圖 (如圖15,圖16所示),場景元素較多且分布復雜,還有些元素兩張圖僅出現一次,給拼接造成了難度.

圖15 左側街道圖

在表2中,反映了圖17中(上側圖是經典算法的特征點匹配圖,下側是SKM算法的特征點匹配圖)經典算法與SKM算法特征點數量以及匹配率.可以看出SKM算法的特征點配對數要比經典算法少很多,而且特征點的匹配率還高.

如圖18,圖19所示,經典算法拼接時,由于特征點匹配過多,拼接又不能顧及所有特征,故出現較大偏差,如圖中信號燈處和斑馬線處.去噪后,此兩處的拼接均大幅提高,斑馬線處基本無斷層.可見SKM拼接對圖像特征的取舍與對重點拼接位置的聚焦作用.

圖16 右側街道圖

表2 街道

圖17 經典算法和SKM算法特征點匹配圖

圖18 經典算法下測試結果圖1

2)在第二組測試中,測試了兩幅不同角度的涂鴉墻,如圖20所示.

圖19 SKM算法下測試結果圖1

圖20 不同角度的涂鴉圖

在涂鴉的圖片中存在大量的紋理,故作為典型案例測試.表3中將SKM算法與經典算法相比較,在這組實驗中,SKM算法減少大量特征點數.將兩幅圖像進行配準,提高了準確度.

表3 墻

結果表明,直接拼接中的效果圖能夠大致吻合,但在拼接處有極窄的縱向圖像帶并沒有顯示出來.而在去噪拼接中有效的避免了這一現象,并且右下方黑色形狀的邊界拼接的更加光滑,其上方的紋理也顯示的較為完整,如圖21,圖22所示.

圖21 經典算法下測試結果圖

3)第三組實驗,以籃球場為背景圖像進行拼接,如圖23所示.兩種算法實驗結果如圖24所示.

圖22 SKM算法下測試結果圖

圖23 籃球場圖

圖24 籃球場拼接結果圖

在最后一組實驗中,籃球場圍欄的紋理在整個圖像范圍內都很相似,對提取特征略有影響,從數據上看可以證實這一點.去噪后特征點數明顯降低,且拼接邊界也有可見的優化效果.如表4所示,雖然SKM從特征點匹配率上表現稍差,但減少對特征點的計算量的效果突出,算法仍具有一定的可取性.

表4 籃球場

5 總結

通過多次圖像配準實驗,可以發現,SKM算法的效率比經典算法效率要高,且保證了配準的準確性.SIFT特征點提取是一種較成熟的算法,但對于多紋理的圖像拼接時,耗時較長.本文提出的SKM算法將基于相關總變差模型的圖像主結構提取算法與基于SIFT特征點提取算法相融合.實驗表明,SKM算法在紋理較多的圖像中進行配準時,繼承了經典算法的穩定性,適用于紋理較多的圖像,并且在紋理較多的圖像配準過程中相比于經典算法而言有著更高效率.而日常拍攝的景物圖像中紋理結構不少,尤其是對于紋理結構特別多的圖像,SKM算法具有較好的性質.