一種預判隨機抽樣算法在像控點測量中的應用

陳爾東昊,黃磊(1.重慶數字城市科技有限公司,重慶 400020; 2.重慶市地理信息云服務企業工程技術研究中心,重慶 400020; .重慶市勘測院,重慶 400020)

一種預判隨機抽樣算法在像控點測量中的應用

陳爾東昊1,2?,黃磊3
(1.重慶數字城市科技有限公司,重慶 400020; 2.重慶市地理信息云服務企業工程技術研究中心,重慶 400020; 3.重慶市勘測院,重慶 400020)

摘 要:像控點測量是航空攝影測量工作中必不可少的環節。為有效適應現代化航空攝影測量技術對像控點測量的要求,本文基于預判參數模型,利用RANSAC函數對SIFT匹配算法進行改進,并采用Visual Studio C++和OpenCV組件進行算法實現。實驗結果表明,將改進后的算法應用到實際的像控點測量工作當中,不但能為航空影像匹配、像控點快速定位提供有效支持,并且能提高像控點測量野外作業的生產效率。

關鍵詞:SIFT算法;RANSAC;像控點測量;圖像匹配

1　引 言

目前,為了適應現代化高效率的航空影像生產,各生產單位引進了一些集群式遙感影像處理系統。在航空攝影測量中,采用先進的IMU/ DGPS輔助航空攝影,可以在攝影的瞬間獲取影像的內外方位元素。并且,在數字攝影測量中采用了機載POS(Position and Orientation System)系統測定定位、定向參數,從而獲得帶有POS信息的航空數字影像。通過實際研究發現,帶有POS輔助的空中三角測量成果更容易滿足各項規范精度要求,而且較大地減少了野外像控點的布設密度以及節省了人力、物力,有力地推動項目的進展。然而,這一革新卻給現實作業中的野外像控點測量帶來了新問題,如像控點布點比傳統膠片航攝和不帶POS的數碼航攝稀疏了很多,像控點之間缺乏連續性和關聯性,相鄰像控點之間的距離又很遠。作業人員既要快速地確定像控點的實地位置,又要能以較快的速度確定像控點點與點之間最方便和快捷的交通路線,以提高野外作業的生產效率。如何解決以上問題,成為現階段像控點測量的瓶頸所在。

為此,本文選擇利用SIFT算法進行影像匹配以及像控區域快速定位。并且,針對SIFT的高誤匹配率,提出了一種基于預判參數模型的隨機抽樣一致算法對SIFT算子改進的航空影像匹配方式,并將其應用到野外像控實際測量工作當中。

2　SIFT影像匹配

SIFT為“尺度不變特征轉換(Scale-invariant feature transform,SIFT)”的簡稱,是一種對尺度、旋轉、仿射以及亮度變化都有很好的不變性的特征[1～3]。SIFT算法實現圖像之間的匹配主要包含了“尺度空間關鍵點定位”、“指定關鍵點方向參數”、“生成SIFT特征描述子”、“特征點對預匹配”4個步驟。

2.1尺度空間關鍵點定位

首先,在尺度空間中檢測極值點。尺度空間理論的目的是模擬圖像數據的多尺度特征,SIFT算法使用的是實現尺度變換的唯一線性核——高斯卷積核。將相鄰尺度的圖像進行差值運算從而得到一組高斯差分面DoG(Difference of Gaussian)圖像[4]。在計算出高斯差分平面之后,對于其中的某一點,將它與周圍的8個近鄰點以及上下相鄰尺度的對應位置的9×2個近鄰點(共26個點)進行比較,如果這一個點都大于或者小于這26個點,那么該點就被選取出來作為極值點。

對于確定的極值點,利用Taylor公式展開式和Hessian矩陣進行輔助,從而獲得關鍵點位置,并提高其在圖像中的位置級空間尺度上的精度。

2.2指定關鍵點方向參數

SIFT利用關鍵點鄰域像素的梯度方向分布特性為每一個關鍵點指定方向參數,使算子具備旋轉不變性。SIFT用以關鍵點作為圓心的高斯加權窗口來對梯度模值進行加權。通過對梯度方向的直方圖統計之后,將峰值處關鍵點的鄰域梯度方向作為主方向,并取最大值80%以內的方向作為輔助方向[5],從而得到該關鍵點的方向。

2.3生成SIFT特征描述子

通過以上步驟,確定了關鍵點的尺度、位置以及方向,確保了其尺度縮放不變性及旋轉不變性。Lowe[6]建議將每個關鍵點為中心的像素點劃成4個4×4的小區域,每個小區域由對應的8個方向的梯度模值表示。因此,最終特征向量為:4×4×8 =128維的,這就是所生成的特征描述子。

2.4特征點對預匹配

利用對K-D tree改進后的最優接點優先(BBF)搜索算法[7]增快特征點的搜索速度。根據特征點的最鄰近特征向量和次鄰近特征向量的歐式距離比來獲取預匹配點對。本文經過實驗發現,當距離小于0.4時,可認為該特征點匹配對為有效的,并且距離比閾值決定了匹配點對的數量和質量。

特征點對預匹配并不能標志著算法的結束,因為SIFT算法在匹配的過程中會產生大量的錯誤匹配點,為了更好地獲得匹配效果,往往會采用其他算法進行改進。本文采用帶預判參數的隨機抽樣一致算法進行錯誤匹配點剔除,以矯正匹配效果。

3　利用預判RANSAC改進SIFT算法

3.1RANSAC算法介紹

RANSAC(Random Sample Consensus)算法[8],又稱隨機抽樣一致算法,每次隨機抽取出多個數據來確定模型參數,再根據估計參數對所有數據進行分類。當數據在該參數模型允許的誤差范圍之內,稱之為內點,反之則為外點。該算法對錯誤率超過50%的數據仍能夠進行處理,是最有效的魯棒估計算法之一。但是RANSAC對于航飛影像這種大數據處理效率較低,且本文需要盡可能大數據量地過濾掉無效數據,因此在RANSAC的模型參數檢驗前,加入了預判參數的過程,提高RANSAC算法的整體效率。

3.2預判改進的RANSAC的算法

本文主要利用RANSAC方法來剔除誤匹配點對,從而減小SIFT特征提取算法所得到的誤匹配點對圖像模板匹配造成的干擾,從而提高匹配成功率。

首先設定初始的最佳內點數Ni為0,然后進行算法實現:

(1)從樣本集中隨機抽選一個RANSAC樣本,即4個匹配點對(每個平面中任意3個點不共面),兩平面間變換矩陣參數H可以根據4組點進行線性計算[9]。

(2)計算剩下(I-4)個特征點經過變化矩陣的坐標值與它預匹配點之間的距離,如下式:

dv=d(A′i,HAi)2

如果小于閾值,則認為該特征點匹配對為內點,否則就為外點。

(3)通過Ni與當前內點數的對比,如果當前點數＞Ni,那么就將H作為當前最佳矩陣估計,并更新Ni值。

(4)重復(1)～(3)繼續進行多次迭代的隨機抽樣計算,并在內點數基本穩定時,選擇內點最多、誤差函數最小的變換矩陣參數為圖像間的投影變換矩陣,這樣的變換矩陣已經相對比較精確。可是,其迭代次數與正確模型確定無法獲得,所以運行效率會不可控。

通過上述RANSAC算法實現在理論上可以得到理想效果的矩陣模型,但是由于RANSAC只有一定的概率得到可信的模型,并且其有著迭代次數沒有上線的確定,為提高匹配效果,以對航飛影像的大數據量特征點進行快速匹配,就需要對匹配正確模型進行預判斷。具體實現如下,將m表示為從匹配點中選取的一個內點的概率,如公式:m=內點數量/所有特征點

由于事先不知道m的值,因此假設選定n個點, 用w表示一些迭代過程中從數據集中機選取出的點均為內點的概率,k為迭代次數。mn是就是n個點都是內點的概率。1-mn表示估計出了一個模型不佳。(1 -mn)k表示永遠不會選擇到n個都是內點的概率,并與1-w相同,所以:1-w=(1-mn)k

由于結果的假設n都是獨立選擇的,所以被選出來的點還可能會被后面的迭代過程重新選到,所以此處的k值被認為是選取不重復點的上限。要想從數據中選擇合適的匹配直線,RANSAC算法通過每次迭代選擇2個點,并且這兩個點都是不重復的,將標準偏差或者它的乘積加到k上,得到k的標準偏差的定義:

對于RANSAC獲得可信模型的概率和標準偏差是成正比的,有了標準偏差k就可以獲得理論上推斷出來的迭代次數,從而可以預判斷出相對正確的可信模型。有了預判而得的正確模型,就可以對RANSAC的參數閾值和數據迭代進行改進,并對SIFT的特征點匹配進行改進,不僅可以有效地去除圖像間錯誤匹配點對,而且能估算出圖像之間的透視變化矩陣參數,從而進一步確定匹配位置,實現流程如圖1所示:

圖1　匹配點獲取流程圖

4　改進后SIFT對像控點測量工作的應用

改進后算法基于Visual studio C++語言,并結合跨平臺計算機視覺庫OpenCV進行實現。本文利用改進后的SIFT算法實驗了多張航片的像控點自動預選、像控點測量區域快速匹配等功能。

4.1改進后的SIFT算法匹配

本文采用重慶市某區域同一航帶上的相鄰兩張1∶5 000航飛影像作為實驗對象。此處通過對改進前后算法的匹配效果進行分析,并驗證RANSAC改進后SIFT算法對航飛影像的匹配效果。

(1)首先利用原始SIFT算子進行影像匹配,匹配效果如圖2所示:

圖2　原始SIFT算子影像匹配結果

(2)改進后的SIFT算子進行影像匹配,匹配效果如圖3所示:

圖3　改進后SIFT算子影像匹配結果

(3)匹配精度分析

實驗統計了兩種算法提取的特征點數級匹配點數,并采用分區域抽樣統計法對匹配正確率統計,抽取匹配區域占總匹配點數30%以上的樣本數據,且在抽取樣本時保證樣本數據在匹配區域分布較為均勻,得到的統計結果如表1所示:

由于像控點測量工作所需要獲得的是準確的定位位置,并利用更為準確的匹配點進行判定,因此本文方法在選擇迭代與預判的時候會進行更為嚴格的篩選。如表1所示,在城鎮地區與非城鎮地區,利用改進后的算法進行嚴格篩選,剔除大部分無效點,并減少了無效迭代所產生的重復與錯誤匹配點,所得到的有效匹配點數僅占原始的16.7%和18.6%,且匹配正確率大大提升。

原始與改進后SIFT算子影像匹配精度比較 表1

通過實驗對比分析,可以很容易地看出通過預判RANSAC對SIFT算法進行改進之后,匹配準確率得到了大幅提高。

4.2像控點測量快速定位

在影像匹配精度滿足生產需求之下,本文在快速匹配定位基礎上,進一步完善了像控點測量工作中的大數據量與多度重疊影像之間的快速定位。

首先,利用改進后SIFT算法進行相鄰航空影像重疊區域匹配,如圖4所示:

圖4　獲取重疊區域

其次,通過SIFT匹配獲取目標像控點和當前像控點影像在大幅影像中的大致位置。目標像控點將會在相鄰航空影像的重疊區域中選擇,因此將相鄰航片的重疊區域提取出來與工作區底圖進行匹配,如圖5所示:

圖5　目標區域定位

最后,通過重復一、二步驟,獲取當天預計目標像控點區域位置,并在匹配重疊區域中預選出像控點目標位置,如圖6所示:

圖6　像控點預選

在匹配獲得當前像控點和目標點位置之后,可以快速定位目標像控點位置,為接下來像控點測量的選點和路徑規劃提供支持,提高了像控點測量的工作效率。

5　結 語

利用預判模型改進后的SIFT算法對像控點測量工作進行輔助,不僅解決了由于航空攝影測量技術發展所帶來的像控點布點稀疏所造成的定位困難,而且能有效支持像控點選點與交通路徑規劃。該算法提高了野外像控點測點的生產效率,優化了工作模式。

本文的研究結果在一定程度上促進了像控點測量工作的進展。在接下來的研究中,將進一步加強利用異源影像輔助像控點測量的研究,并在路徑規劃基礎上研究實現工作路徑自動導航與人員實時定位功能等。

參考文獻

[1] MORTENSEN E N,Deng Hongli,SHAPIRO L.A SIFT Descriptor with Global Context[C].Computer Vision and Pattern Recognition,IEEE Computer Society Conference,2005: 184～190.

[2] EGENHOFER M.IEEE Symposium on Visual Languagers [C].IEEE Computer Society,1996:60～67.

[3] BRUNELLI R,MICH O.Image retrieval by examples[J].IEEE Trans.Multimedia,2000,2(3):164～171.

[4] 夏杰,李奇安,李悅等.基于改進SIFT算法的圖像匹配方法研究[J].電子設計工程,2012,20(14):157～159.

[5] 黃超,齊英劍.SIFT算法研究和應用[J].中國傳媒大學學報:自然科學版,2012,19(1):68～72.

[6] Lowe,DG.Object recognition from local scale-invariant features[C].Proceedings of Imternational Conference on Computer Vision.Corfu,Greece:IEEE,2009:1150～1157.

[7] Beis J S,Lowe D G.Shape imdexing using approximate nearest - neighbour search in high - dimensional spaces [ C].Conference on Computer Vision and Pattern Recognition.Washington D C,USA:IEEE Computer Society,1997:1000 ～1006.

[8] Wang Wei,HongJun,TangYiping.Image matching for geomorphic measurement based on sift and RANSAC methods [C].International Conference on Computer Science and Software Engineering.Wuhan, Huber: IEEE,2008:317～320.

[9] 黃有群,付裕,馬廣焜.基于RANSAC算法的柱面全景圖拼接方法[J].沈陽工業大學學報,2008,20(4):461～465.

Applications of Preview Random Sampling Algorithm at Photograph Control Point Survey

Chen Er-dong-hao1,2,Huang Lei3
(1.Chongqing Cybercity Sci-tech Co.,Ltd,Chongqing 400020,China; 2.Chongqing Enterprise Engineering Technology Research Center on Geographic Information Cloud Service,Chongqing 400020,China; 3.Chongqing Survey Institute,Chongqing 400020,China)

Abstract:Photograph control point survey is an essential part of aerophotogrammetry.In order to adapt to the requirement of modern technology of aerophotogrammetry,this paper used RANSAC function to improve SIFT algorithm on the basis of the anticipation parameter model,and used Visual Studio C++ and OpenCV components to implement the algorithm.the result shows that,applying the improved algorithm to the photograph control point survey can not only effectively support the aerial image matching and rapid positioning of photograph control point,but also improve the production efficiency of photograph control point survey in field operations.

Key words:SIFT;RANSAC;photograph control point survey;image matching

文章編號:1672-8262(2015)01-101-04中圖分類號:P231

文獻標識碼:A

收稿日期:?2014—08—28

作者簡介:陳爾東昊(1988—),女,碩士,助理工程師,主要研究方向為地理信息系統應用、地理信息數據建庫等。