一種預(yù)判隨機(jī)抽樣算法在像控點測量中的應(yīng)用

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

一種預(yù)判隨機(jī)抽樣算法在像控點測量中的應(yīng)用

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

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

關(guān)鍵詞:SIFT算法;RANSAC;像控點測量;圖像匹配

1　引 言

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

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

2　SIFT影像匹配

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

2.1尺度空間關(guān)鍵點定位

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

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

2.2指定關(guān)鍵點方向參數(shù)

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

2.3生成SIFT特征描述子

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

2.4特征點對預(yù)匹配

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

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

3　利用預(yù)判RANSAC改進(jìn)SIFT算法

3.1RANSAC算法介紹

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

3.2預(yù)判改進(jìn)的RANSAC的算法

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

首先設(shè)定初始的最佳內(nèi)點數(shù)Ni為0,然后進(jìn)行算法實現(xiàn):

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

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

dv=d(A′i,HAi)2

如果小于閾值,則認(rèn)為該特征點匹配對為內(nèi)點,否則就為外點。

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

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

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

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

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

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

圖1　匹配點獲取流程圖

4　改進(jìn)后SIFT對像控點測量工作的應(yīng)用

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

4.1改進(jìn)后的SIFT算法匹配

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

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

圖2　原始SIFT算子影像匹配結(jié)果

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

圖3　改進(jìn)后SIFT算子影像匹配結(jié)果

(3)匹配精度分析

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

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

原始與改進(jìn)后SIFT算子影像匹配精度比較 表1

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

4.2像控點測量快速定位

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

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

圖4　獲取重疊區(qū)域

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

圖5　目標(biāo)區(qū)域定位

最后,通過重復(fù)一、二步驟,獲取當(dāng)天預(yù)計目標(biāo)像控點區(qū)域位置,并在匹配重疊區(qū)域中預(yù)選出像控點目標(biāo)位置,如圖6所示:

圖6　像控點預(yù)選

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

5　結(jié) 語

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

本文的研究結(jié)果在一定程度上促進(jìn)了像控點測量工作的進(jìn)展。在接下來的研究中,將進(jìn)一步加強(qiáng)利用異源影像輔助像控點測量的研究,并在路徑規(guī)劃基礎(chǔ)上研究實現(xiàn)工作路徑自動導(dǎo)航與人員實時定位功能等。

參考文獻(xiàn)

[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] 夏杰,李奇安,李悅等.基于改進(jìn)SIFT算法的圖像匹配方法研究[J].電子設(shè)計工程,2012,20(14):157～159.

[5] 黃超,齊英劍.SIFT算法研究和應(yīng)用[J].中國傳媒大學(xué)學(xué)報:自然科學(xué)版,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].沈陽工業(yè)大學(xué)學(xué)報,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

文獻(xiàn)標(biāo)識碼:A

收稿日期:?2014—08—28

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