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

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

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

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

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

1　引 言

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

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

2　SIFT影像匹配

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

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

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

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

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

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

2.3生成SIFT特征描述子

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

2.4特征點(diǎn)對(duì)預(yù)匹配

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

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

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

3.1RANSAC算法介紹

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

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

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

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

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

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

dv=d(A′i,HAi)2

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

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

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

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

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

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

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

圖1　匹配點(diǎn)獲取流程圖

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

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

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

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

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

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

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

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

(3)匹配精度分析

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

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

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

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

4.2像控點(diǎn)測(cè)量快速定位

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

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

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

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

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

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

圖6　像控點(diǎn)預(yù)選

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

5　結(jié) 語(yǔ)

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

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

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

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

文章編號(hào):1672-8262(2015)01-101-04中圖分類(lèi)號(hào):P231

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

收稿日期:?2014—08—28

作者簡(jiǎn)介:陳爾東昊(1988—),女,碩士,助理工程師,主要研究方向?yàn)榈乩硇畔⑾到y(tǒng)應(yīng)用、地理信息數(shù)據(jù)建庫(kù)等。