基于DPP改進RANSAC算法的圖像拼接①

汪 旌,張 赟,陳 爽

1(杭州電子科技大學 計算機學院 圖形圖像研究所,杭州 310018)

2(浙江傳媒學院 浙江廣播電視技術研究所,杭州 310018)

3(沈陽工業大學 信息科學與工程學院,沈陽 110023)

圖像拼接技術是現今熱門的圖像處理技術,圖像拼接是將取自同一場景,有相互重疊信息的一組圖像序列通過圖像配準和圖像融合的方法,拼接成為一幅無縫隙,寬視角,高清晰度圖像的處理技術[1].圖像拼接方法有以下 3 種: 1) 基于特征的圖像拼接; 2) 基于交換域的圖像拼接; 3) 基于灰度的圖像拼接.其中基于特征的圖像拼接是現今最常用的拼接方法.在基于特征的圖像拼接中,由于受特征點檢測方法精度,光照變化等因素影響,匹配特征存在錯誤信息,錯誤信息的存在會較大程度的影響模型參數估計的精度.針對模型參數估計的方法有: 線性法,迭代法和魯棒法.線性模型參數估計方法[2]速度快,但易受誤差匹配的影響.迭代模型參數估計方法精度高,但耗時久計算量大.而魯棒模型參數估計方法[3,4]是通過錯誤信息排除策略,利用正確信息進行模型參數估計的方法.魯棒參數估計算法中最廣泛應用的是隨機抽樣一致性(Random Sample Consensus,RANSAC)算法.該方法算法魯棒性強,結構簡單,較好實現,已成為眾多學者的研究對象.隨機抽樣一致性算法利用迭代方法從一組包含內點和外點的樣本集中估算出參數模型,從而得到優質的匹配點集,然而它是一種不確定的算法,精度不高,得到一個合理結果存在一定概率,因此相關改進的RANSAC算法應運而生.MSAC方法[5]引入邊界損失函數評估內外點的分布,獲取了具有最大可能的一致集.PSOSAC方法[6]利用測試樣本的匹配評價作為采樣依據.Optimal RANSAC 方法[7]通過增加局部采樣方式來提高模型估計精度與收斂速度.

本文提出一種基于行列式點過程的RANSAC算法,該算法利用行列式點過程(Determinantal Point Processes,DPP)采樣法從測試點集中選取一個子集進行參數估計,選取的子集具有全局性和分散性,利用抽取到的分散性好的特征點求取參數模型.接著,運用所有特征點集對該模型進行檢驗.根據特征點集中數據對模型的支持度,觀測內點數目來確定該模型估計的正確性.通過不斷建立假設與檢驗的迭代,以期獲取一個具有全局最優的模型.

1 圖像特征提取與匹配

本文對于特征點提取采用魯棒性較好的基于尺度空間理論的SIFT特征提取法[8].SIFT特征提取法首先建立圖像高斯差分多尺度空間(Difference-of-Gaussian,DoG); 在DoG尺度空間求取局部極值點,剔除低對比度點和邊緣響應點后對局部極值點進行精確定位,同時生成特征描述子,通過特征描述子建立兩幅圖像之間的關系.

目前,SIFT特征提取法已有相關改進,如文獻[9]提出高斯二階差分(D2oG)特征檢測算子的SIFT算法.本文基于實際應用中算法復雜度考慮,采用基于尺度空間理論的SIFT算法.

1.1 構建圖像的高斯尺度空間

一幅二維圖像的高斯尺度空間可以定義為:

其中,

是尺度可變高斯函數,(x,y)是各像素點坐標,σ是用于表示圖像平滑度的尺度空間參數,σ越大對應圖像的概貌特征越明顯,σ越小對應圖像的細節特征越清晰.

1.2 SIFT特征提取法

(1) 空間極值檢測

建立圖像DoG金字塔后,在DoG尺度空間中的26個領域中檢測極值點,如果一個點在DoG尺度空間本層以及上下兩層的26個領域中是極值點(最大值或最小值),即認為該點是圖像在該尺度下的一個特征點.如圖1所示.

圖1 Difference-of-Gaussian 金字塔示意圖

(2) 確定DoG算子的方向不變性

每個特征點的方向參數由特征點領域像素點的梯度方向分布特性決定.

像素點的梯度:

公式(3)、(4)分別給出了處像素點的梯度幅值和方向角.

實際計算中,在以特征點為中心的鄰域窗口內采樣,用直方圖統計鄰域像素的梯度方向.梯度直方圖的范圍是0～360度,每10度代表一個方向,總共36個方向,直方圖的峰值處即為特征點的主方向.

(3) 生成SIFT特征向量

將特征點描述為一組特征向量,特征向量是對特征點及其鄰域內的像素點特征的精確描述.一個特征點由4×4=16個種子點構成,特征點的特征向量由所有子塊梯度直方圖構成,圖2左圖的方型線框大小為16×16.每個小格代表一個像素點,像素點的梯度即小格內的帶箭頭直線表示,梯度的幅值大小即直線的長度,梯度方向即箭頭方向.16×16的方型線框共產生4個種子點.圖2給出特征向量生成的過程:

圖2 特征向量生成過程

(4) 特征點的匹配

獲取到特征點描述子后,進行特征點的匹配.特征點的匹配就是特征向量的匹配,本文采用的方法是比較特征向量的歐氏距離,當此距離小于某個閾值時則認為這兩個點已匹配上.文獻[10]證明: 當圖像的噪聲接近高斯噪聲時，L2歐式距離能夠更好的區分特征點對的真匹配與偽匹配。其次，L2歐式距離在特征點匹配的具體實現中具有極佳的便利性，在具體應用中利用一些數學工具箱則可非常快速的計算出特征向量間的L2歐式距離.

特征點匹配完成后,利用RANSAC算法篩選出匹配度低或誤匹配的點,最后選擇合適的特征點計算出最佳投影變換矩陣,實現圖像配準.但是當特征點對數量龐大、錯誤率高、估算模型復雜時,計算量會加大,傳統的RANSAC算法效率會大幅度下降.本文提出一種基于行列式點過程的改進RANSAC算法,能適應匹配點數目龐大,錯誤率高的情況.

2 RANSAC 算法

傳統的RANSAC算法的主要過程為: 首先在特征點集中隨機的選取幾個點作為基準點,利用基準點計算出一個模型,用點集中剩余點來估算此模型,同時記錄內外點.如果誤差距離在設定范圍內,那么此點即稱為該模型的內點; 否則為外點.當統計的內點數達到預設的閾值時,認為該模型合理,否則繼續隨機選擇特征點生成新的模型重復上述過程,最后將內點數量最多的模型作為最優模型[11]具體的算法流程如下:

(1) 首先在樣本點集S中隨機選取一定數量為N的點計算出數學模型A,用剩余的S–N個點測試模型A,將滿足模型A的點存入內點集M中.

(2) 判斷內點集M的數量,若大于或等于設定閾值C,則表述模型A合理,否則重新從(1)開始.

(3) 在設定的迭代次數D范圍內,不斷重復(1)(2).最終統計到內點數最多的點集M',獲取參數模型A',此模型即為最終的所選模型.

3 基于行列式點過程的改進RANSAC算法

傳統的隨機一致性RANSAC算法雖然可以很大程度上利用相對正確的配對點來生成變換矩陣,但是依然存在不足:

(1) 傳統的RANSAC算法采用隨機取點的方式進行初始模型計算,但是隨機取點會導致取樣點集中于某一區域,這個區域可能正確匹配率很低或存在過多誤匹配點,如此求取的投影變換矩陣精確性會有所下降,根據RANSAC算法的流程,在所有點都驗證結束后才可能區分出誤匹配點,這樣會大大降低算法的效率.

(2) 在隨機選擇特征點時,如果選取到的點位置很接近,則會被當成同一個點,這樣計算出來的投影變換矩陣精度也會降低.

基于以上傳統的RANSAC算法的缺陷與不足,本文提出了一種基于DPP的改進RANSAC算法.

3.1 基于DPP的改進RANSAC算法

在RANSAC算法執行過程中,對測試樣本的采樣是其算法框架下的重要環節之一,而DPP具有良好的全局性和負相關性,在抽樣過程中會呈現出覆蓋面廣且“分布均勻”的完美性質[12],這對于傳統的RANSAC隨機采樣過程中采樣不均的缺陷有非常正面的作用.

DPP最早在量子力學和隨機矩陣中提出,DPP是一種概率模型,它通過核矩陣的行列式來給出每一個子集的概率[13]基于它的特性,DPP為采樣,計算邊緣概率等其它推理任務提供了有效的解決辦法.在本文中主要利用其采樣特性對RANSAC算法進行改進.

一個離散集上的點過程P是在Y的所有子集上的概率分布,此過程的基礎上,當且僅當過程P由一個半正定矩陣K所確定,且矩陣k由Y中的元素索引時,將這個點過程稱為行列式點過程.即當Y為一個依據點過程P所獲得的子集時,對任意的有:

其中為保證公式的有效性,指定且當時,

從上式可以得到,矩陣K的對角元素表示單個元素被選擇到子集中的概率,非對角元素決定了元素對間共同出現的負相關性,矩陣K中包含了所有的元素間的信息.據此將K稱為核矩陣,并將這個全局負相關稱為多樣性.所以得到以下結論:Kij的值越大代表i和j同時發生的概率越小.標準DPP采樣法的算法描述如算法1.

End while

算法中,第j次抽取元素i的概率為:

由此,抽取序列的概率為:

由于所有的實對稱矩陣均可表示為葛朗姆矩陣,即實對稱矩陣K可寫成K=BTB.其中Bi表示集合Y中的元素.由算法1可見可以從K中得到一個子集Y作為標準DPP的抽樣結果.

由式(7)和(8)可知,標準的DPP采樣是完全根據概率進行操作,因此最終的取樣點不固定.如果采樣得到的點超過實際應用所需點數,那么會造成計算資源的浪費,因為采樣點已經足夠分散在采樣空間中,更多的采樣點對于提升計算精度的幫助微乎其微.若采樣得到的點數少于實際應用所需點數,則達不到計算仿射或者透視變換的參數個數.因此采用可控的采樣方法對于圖像拼接來說意義重大.對于RANSAC算法,希望可以人為的選擇每次采樣點的數目,保證計算精度的同時,不造成計算資源的浪費.所以本文采用k-DPP采樣[14].k-DPP是一種僅對基數k進行建模的條件DPP.在實際應用中基數k為采樣集合中采樣點的個數,k-DPP采樣法避免了標準DPP采樣法中采樣點不固定造成的計算精度不準確以及資源浪費的弊端,實現均勻分散采樣的前提下控制采樣點的個數.通過簡單調節標準DPP采樣方法即可實現k-DPP采樣.k-DPP采樣算法如算法2.

算法 2.k-DPP 采樣法[14]Input : 輸入K的特征值和特征向量對{()}Output: YFordo If thenif k=0 then break end if end if end for繼續算法1中采樣算法的第二個循環

算法2中e為關于特征向量的基本對稱多項式(elementary symmetric polynomials),e的計算公式如下:

相比較于標準DPP采樣法,顯然k-DPP采樣法有著更強的可控性,因此更加符合圖像應用上的要求.

3.2 基于DPP的改進RANSAC算法流程

(1) 利用SIFT特征提取算法分別提取有重合場景的兩幅圖像P1,P2的特征點集,記為

(2) 利用相似性度量函數構造DPP采樣所需核矩陣K.相似性度量函數計算公式如式(10),d是S(Am,An)的預設方差,本文設定d=5.

由S的定義可知,對任意的Am和An,必有 0 ≤S(Am,An)≤ 1,因此矩陣K滿足邊緣概率分布,K是核矩陣.

(3) 對模擬概率分布后的得到矩陣K進行特征分解,特征值和特征向量按照從大到小的索引順序排列按照算法2的描述循環判斷,更新集合J中的滿足條件的特征向量.本文的實現過程中k=8.

(4) 重復算法1中的while循環,按照概率中抽取8個特征點.

(5) 圖像P2重復上述操作,即可從匹配后的特征點對中選取8對分散性好的點對.

計算出臨時投影矩陣Hi,計算剩余樣本點通過Hi變換后的歐氏距離L2記為di,若di≤thresh0,則將此樣本點加入點集Si中,di加入Di中.在完成一定抽樣次數后,選擇點集Si中點數最多的點集為內點集Si,并記錄此時的投影矩陣對應的距離集合而此時獲取的投影矩陣即通過改進的RANSAC算法得到的最佳參數估計模型.值得注意的是,對于不同的問題可以選取不同數目的點對,在圖像拼接的算法中選取8對特征點對是對投影變換的最小自由度和計算魯棒性進行了折中.

4 實驗結果

4.1 圖像拼接

為了檢驗本文提出的基于DPP的RANSAC算法在剔除誤匹配點方面的有效性,本文進行了圖像拼接實驗.分別用傳統的RANSAC算法和改進后的RANSAC算法對兩組場景信息不同的圖像進行了處理.測試環境配置如下: Microsoft Windows 10,CPU 為 2.40 GHz,內存為 8 GB,硬盤為 500 GB SATA,編譯工具為matlab R2014a.

如圖3和圖4所示,本文選取了兩組測試圖像,均采用SIFT特征提取算法提取了特征點,通過計算圖像特征點之間的歐式距離L2距離進行初始匹配,然后分別利用傳統的RANSAC算法和改進后的RANSAC算法進行消除誤匹配點對的對比試驗.并分別統計兩種算法的正確匹配率,迭代次數以及完成拼接所用時間.

圖3 第一組實驗對比圖

第一組測試圖像大小同為788×788,對同一場景的拍攝角度不同.

第二組測試圖像大小為1278×852和736×852.兩幅圖像大小不同,清晰度也不同.

上述實驗對比可觀測出傳統的RANSAC算法雖然也能剔除掉一部分誤匹配點,但是依舊存在誤差匹配,而改進后的RANSAC算法基本無誤差匹配.表1給出迭代次數,正確匹配率,以及時間效果上的兩種RANSAC算法效率對比(實驗將原RANSAC算法的迭代次數控制在300次以內).

圖4 第二組實驗對比圖

由表1可知,雖然改進后的RANSAC最終得到的匹配點數目少于傳統的RANSAC算法,但是剔除了更多的誤匹配點,因此正確率明顯提高.同時改進后的算法迭代次數和拼接耗時大大減少.這是因為傳統的RANSAC算法在隨機取點的過程中不能保證取樣點的分散性,當隨機取樣點集中于正確匹配率低的區域時會大大增加了算法的迭代次數和拼接時間,而改進的RANSAC算法保持了取樣的分散特性,降低了迭代次數和拼接時間.

表1 實驗結果對照表

4.2 興趣區域圖像配準(ROI Image Registration)

ROI圖像配準在現代制造業中應用廣泛,如產品的局部近似立面檢測.如圖5(a)是拍攝到的一個計算機的前面板,圖5(b)是拍攝到的一部隨機擺放的計算機.實驗通過匹配興趣區域,將圖5(b)中的計算機前面板矯正到圖5(a)所示的正面角度,由于計算機的前面板不是完全的明面,而是有許多小凹凸,比如支架或者接口的凹凸,因此在拍攝視角改變后興趣區域的圖像配準不完全符合投影變換.在此情況下進行匹配點篩選,若采取到的匹配點位置集中,則進行透視模型估計時得到的模型參數估計精度不高,當采用分散性好的匹配點進行透視模型參數估計能得到更為魯棒的結果.

圖5 興趣區域圖像配準實例圖

實驗通過SIFT特征提取法提取圖5(a)和圖5(b)匹配特征點對,分別利用傳統的RANSAC算法和改進的RANSAC算法剔除誤差匹配點后求取最優變換矩陣.利用剔除誤差匹配點后計算得到的變換矩陣將圖5(b)中的計算機面板角度轉換成圖5(a)中ROI圖像所示的正面角度.圖5(c)是使用傳統RANSAC算法對圖5(b)進行興趣區域配準得到的結果,圖5(d)則是使用基于DPP的改進RANSAC算法對圖5(b)進行興趣區域變換的結果.可以觀察到的是,利用傳統RANSAC算法進行興趣區域配準得到的結果發生了畸變,而利用基于DPP改進的RANSAC算法則得到了非常魯棒的結果.

5 結束語

本文將DPP采樣法與RANSAC算法相結合,提出了一種更加高效,精確度更高的改進RANSAC算法.其特點如下:

k-DPP采樣法在傳統DPP采樣法加以改進,在均勻分散化采樣的前提下保證采樣點數目可控,這一特性對傳統RANSAC算法中隨機取點導致取點區域集中的問題有很好的正面作用[15].

改進的RANSAC算法在圖像拼接中也保持了極佳的效率.當原始點集數據很大,匹配錯誤率高的時,改進的RANSAC算法能快速精準的找到最佳變換矩陣,高效的完成圖像拼接.

RANSAC算法不僅可以應用于圖像拼接領域,同時也可應用到人臉識別[16]、圖匹配[17]、立體圖像配準[18]、醫學圖像拼接[19]等領域.今后作者考慮進一步將改進的RANSAC算法應用到更多領域,如虛擬現實,全景合成處理等.

參考文獻

1張亞娟.基于SURF特征的圖像與視頻拼接技術的研究[碩士學位論文].西安: 西安電子科技大學,2013.

2Armangué X,Salvi J.Overall view regarding fundamental matrix estimation.Image and Vision Computing,2003,21(2): 205–220.[doi: 10.1016/S0262-8856(02)00154-3]

3魏若巖,阮曉鋼.基于Skinner操作條件反射的抽樣一致性算法.控制與決策,2015,30(2): 235–240.

4唐永鶴,胡旭峰,盧煥章.應用序貫相似檢測的基本矩陣快速魯棒估計.光學 精密工程,2011,19(11): 2759–2766.

5Torr PHS,Zisserman A.MLESAC: A new robust estimator with application to estimating image geometry.Computer Vision and Image Understanding,2000,78(1): 138 –156.[doi: 10.1006/cviu.1999.0832]

6Chum O,Matas J.Matching with PROSAC-progressive sample consensus.Proceedings of 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition.San Diego,CA,USA.2005.220–226.

7Hast A,Nysj? J,Marchetti A.Optimal ransac —towards a repeatable algorithm for finding the optimal set.Journal of WSCG,2015,21(1): 21–30.

8Lowe DG.Distinctive image features from scale-invariant keypoints.International Journal of Computer Vision,2004,60(2): 91–110.[doi: 10.1023/B:VISI.0000029664.99615.94]

9徐敏,莫東鳴,張禎.高斯二階差分特征算子在圖像拼接中的應用.計算機系統應用,2016,25(4): 167–173.

10Brown M,Szeliski R,Winder S.Multi-image matching using multi-scale oriented patches.Proceedings of 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition.San Diego,CA,USA.2005.510–517.

11Fischler MA,Bolles RC.Random sample consensus: A paradigm for model fitting with applications to image analysis and automated cartography.Communications of the ACM,1981,24(6): 381–395.[doi: 10.1145/358669.358692]

12Kulesza A,Taskar B.Determinantal point processes for machine learning.Foundations and Trends in Machine Learning,2012,5(2-3): 123–286.[doi: 10.1561/2200000044]

13Johansson K.Determinantal processes with number variance saturation.Communications in Mathematical Physics,2004,252(1-3): 111–148.[doi: 10.1007/s00220-004-1186-4]

14Kulesza A,Taskar B.k-DPPs: Fixed-size determinantal point processes.Proceedings of the 28th International Conference on Machine Learning.Bellevue,WA,USA.2011.1193–1200.

15Decreusefond L,Flint I,Privault N,et al.Determinantal point processes.Peccati G,Reitzner M.Stochastic Analysis for Poisson Point Processes.Cham: Springer,2016.311–342.

16Shao H,Chen S,Zhao JY,et al.Face recognition based on subset selection via metric learning on manifold.Frontiers of Information Technology & Electronic Engineering,2015,16(12): 1046–1058.

17Yu TS,Wang RS.Graph matching with low-rank regularization.Proceedings of 2016 IEEE Winter Conference on Applications of Computer Vision (WACV).Lake Placid,NY,USA.2016.1–9.

18Tong RF,Zhang Y,Cheng KL.StereoPasting: Interactive composition in stereoscopic images.IEEE Transactions on Visualization and Computer Graphics,2013,19(8):1375–1385.[doi: 10.1109/TVCG.2012.319]

19Adwan S,Alsaleh I,Majed R.A new approach for image stitching technique using Dynamic Time Warping (DTW)algorithm towards scoliosis X-ray diagnosis.Measurement,2016,(84): 32–46.