一種面向大建筑物的移動視覺定位算法

徐田帥　房勝　劉天池

摘 要：針對目前智能手機難以拍攝大建筑物全貌以及基于移動視覺檢索的戶外定位系統(tǒng)匹配大建筑物失準的問題，提出一種面向大建筑物的移動視覺定位算法。基于尺度不變特征變換理論，該算法通過提取建筑物不同角度的特征建立一種建筑物多視角特征模型，并基于該模型建立建筑物特征庫，同時通過在特征庫中匹配用戶提交的不同角度建筑物照片的特征點實現(xiàn)定位。實驗結(jié)果表明，與基于GPS定位的算法相比，該算法能夠通過建筑物圖像匹配精確的進行定位，解決了GPS在高樓林立的市區(qū)定位不準的問題；并且該算法通過保留建筑物特征的空間位置信息，能較好地過濾錯誤匹配，與基于BOF（bag of feature）算法的移動視覺定位算法相比，提高了匹配精確度，具有較強的實用價值。

關(guān)鍵詞：定位系統(tǒng)；大建筑物；多視角特征模型；移動視覺搜索；尺度不變特征變換

DOIDOI：10.11907/rjdk.151238

中圖分類號：TP312 文獻標識碼：A 文章編號：1672-7800（2015）007-0071-05

0 引言

隨著帶有GPS功能的智能手機的普及和互聯(lián)網(wǎng)技術(shù)的進步，基于位置的服務(wù)（location-based services， LBS）得到了較快發(fā)展。然而，作為LBS最重要的信息，位置信息主要通過衛(wèi)星導(dǎo)航的方式獲得，在市區(qū)由于高樓林立引起的多路徑效應(yīng)問題，衛(wèi)星導(dǎo)航獲取的位置信息通常偏差較大[1]。針對這一問題，G Schroth與R Huitl等[1-3]從視覺匹配的角度出發(fā)，研究了基于移動視覺檢索的定位方式。近年來，谷歌、亞馬遜等公司都開始在移動視覺搜索上進行探索，并取得了一些成果。谷歌在安卓平臺開發(fā)了Goggles[4]，用于查詢商標、圖書、藝術(shù)品等。亞馬遜在IOS平臺上開發(fā)了Snaptell[5]，用來識別圖書、DVD和游戲封面。oMoby在IOS平臺上開發(fā)了oMoby，用來識別普通物體。以上系統(tǒng)在商標、圖書等小圖案上檢索效果較好[6]，但是并不能很好地檢索跨越整幅圖片的戶外建筑物圖片。戶外建筑物的檢索面臨諸多挑戰(zhàn)：①建筑物的描述因為遮擋和覆蓋變得復(fù)雜；②查詢圖像與數(shù)據(jù)庫圖像的光照情況不同，產(chǎn)生的倒影與反射也不同；③查詢圖像與數(shù)據(jù)庫圖像中都存在汽車、行人等改變成像內(nèi)容的動態(tài)物體；④手機拍照造成的抖動模糊也會對匹配查詢造成影響[1]。

G Schroth基于移動視覺定位系統(tǒng)的研究使用谷歌球形全景圖作為數(shù)據(jù)庫圖像，同時為了實現(xiàn)普通照片與球形全景圖的匹配，采用了基于BOF（bag of feature）[7]算法的圖像檢索匹配方法。該算法通過K-means算法將高維特征描述子聚類量化為視覺詞匯，將圖片檢索再表示為文本檢索。但是由于BOF算法將原始特征量化為視覺詞匯，忽略了特征點的原始信息與空間聯(lián)系[1，7-8]，使得查準率不能保持在較高水平。而且球形全景圖存在寬基線效應(yīng)，改變了原圖像的三維視圖、尺度、灰度等信息。同時球形全景圖缺乏針對性，道路與樹木占據(jù)了圖片的大部分。

針對以上問題，本文在保證檢索效率的前提下，設(shè)計了一種面向大建筑物的移動視覺定位算法。該算法使用普通建筑物圖像作為數(shù)據(jù)庫圖像，避免了球形全景圖存在的寬基線效應(yīng)以及缺乏針對性的問題；并且通過提取建筑物不同角度特征建立建筑物多角度特征模型，并基于該模型建立建筑物特征庫。最后通過在特征庫中匹配用戶提交的不同角度的建筑物照片的特征點實現(xiàn)定位。在建筑物多角度特征模型中，該算法保留了建筑物的特征信息與位置信息，在特征匹配中通過RANSAC[9]算法進一步保證了準確度。

1 移動視覺定位相關(guān)技術(shù)

1.1 移動視覺定位基本架構(gòu)

移動視覺定位系統(tǒng)與移動視覺搜索系統(tǒng)的基本結(jié)構(gòu)大致相同，即用一幅或幾幅圖像查詢數(shù)據(jù)庫，然后得到匹配檢索結(jié)果[8]。目前，移動視覺檢索基本架構(gòu)主要有3種模式[10-11]。

模式1：用戶通過手機客戶端拍攝建筑物圖像，經(jīng)過部分預(yù)處理后將照片上傳到服務(wù)器，服務(wù)器進行特征提取、圖像匹配，將得到的檢索結(jié)果返回到手機客戶端。

模式2：用戶通過手機客戶端拍攝建筑物圖像，并在手機端進行特征提取，然后將提取的特征上傳至服務(wù)器進行特征匹配，最后服務(wù)器將匹配結(jié)果返回到手機客戶端，并顯示在手機屏幕上。

模式3：用戶通過客戶端拍攝建筑物圖像，并在手機端進行特征提取與特征匹配。

模式1主要針對運算能力較差，無法在手機端運行特征提取算法的手機。模式2主要針對運算能力較好的手機，可以在手機端提取特征，減小上傳的數(shù)據(jù)量，減輕服務(wù)器運算壓力。模式3減少了網(wǎng)絡(luò)傳輸環(huán)節(jié)，能較明顯地節(jié)省時間，但對運算性能要求最高[12]。

在手機端對圖像提取特征計算量很大，不僅考驗手機的運算能力，在電量方面也會增加消耗，而且運算時間如果過長也會影響用戶體驗。因此，該算法在結(jié)構(gòu)上選擇模式1，即從手機端上傳圖像到服務(wù)器并從服務(wù)器端進行特征提取和圖像匹配，再將匹配結(jié)果排序返回手機端。

圖1 移動視覺定位系統(tǒng)基本結(jié)構(gòu)

1.2 圖像特征提取與描述方法

本文采用SIFT（scale-invariant feature transform）[13]算法作為圖像的特征提取與描述算法。SIFT算法不僅對旋轉(zhuǎn)、尺度、亮度變化保持不變性，而且對視角變化、仿射變換、噪聲也保持一定的穩(wěn)定性。SIFT算法分為特征點檢測與描述兩個部分。（1）特征點檢測。首先構(gòu)建尺度空間，采用唯一線性的高斯卷積核與原圖像I（x，y）進行卷積。

L（x，y，σ）=G（x，y，σ）*I（x，y）（1）

將相鄰高斯尺度空間的圖像相減得到高斯差分圖像，并建立高斯差分金字塔。

D（x，y，σ）=（G（x，y，kσ）-G（x，y，σ））*I（x，y）=L（x，y，kσ）-L（x，y，σ）（2）

G（x，y，σ）=12πσ2e-（x2+y2）/2σ2（3）

其中，（x，y）為空間坐標，σ為尺度，k為乘積因子。通過對每個采樣點比較其圖像域和尺度域中的相鄰點來確定極值點的位置，并去除低對比度的極值點和不穩(wěn)定的邊緣響應(yīng)點得到最終特征點。（2）描述子生成。首先計算特征點領(lǐng)域像素的梯度方向得到該特征點的主方向。將坐標軸旋轉(zhuǎn)到特征點主方向，然后以特征點為中心取16×16的鄰域作為采樣窗口，將采樣點與特征點的相對方向通過高斯加權(quán)后歸入包含8個bin的方向直方圖，最后獲得4×4×8的128維特征描述子。在特征匹配時，SIFT算法選擇歐式距離作為128維SIFT算子的距離函數(shù)。設(shè)檢索圖像A的特征集合為Fa = ＼{ f（a）1 ，f（a）2 ，...f（a）Na ＼} ，特征數(shù)據(jù)庫中的一個特征集合為Fb = ＼{ f（b）1 ，f（b）2 ，...f（b）Nb ＼} ，其中Na、Nb為對應(yīng)的特征點個數(shù)。特征向量的歐氏距離可用式（4）表示：

d（fa，fb）=∑128i=1（fia-fib）2（4）

根據(jù)式（4）計算Fa中每個特征向量與Fb中每個特征向量的距離，得到Fb與Fa中每個向量最近的兩個距離d1、d2。將最近距離d1與次近距離d2的比值與閾值進行比較來確定是否為正確匹配的特征點對。

2 多角度特征模型與匹配算法

2.1 多角度特征模型

該定位算法的應(yīng)用場景是在道路上隨拍隨查，拍攝角度要求不高。手機鏡頭由于其自身局限性，并不能拍攝建筑物的全貌。并且，對于同一建筑物，拍攝地點不同，也會造成視角的改變，建筑物的成像內(nèi)容也會發(fā)生改變。這種視角的大范圍變換并不能通過SIFT算法解決。為了解決該問題，本文提出了一種多角度特征表示建筑物的方法，通過提取建筑物不同角度特征建立建筑物多角度特征模型，并基于該模型建立建筑物特征庫。其中，建筑物多角度特征模型是對建筑物的整體描述，定義如下：定義1：建筑物多角度特征模型由建筑物人文信息與建筑物特征點描述向量與空間坐標集合構(gòu)成，可以描述為：

MN=I∪UN（5）

其中，N表示圖像庫中該建筑物圖像的數(shù)量，I為建筑物位置、功能、歷史等人文信息的集合，UN為建筑物特征與空間坐標結(jié)合。

ui=Fi∪Ki（6）

UN={u1，u2，...，uN}（7）

Fi為建筑物第i幅圖像的特征向量集合，Ki為建筑物第i幅圖像特征向量對應(yīng)的空間坐標集合。ui為建筑物第i幅圖像特征向量與空間坐標的集合。如式（7）所示，UN是由以圖像為單位的ui組成的集合。該算法在特征匹配時采用如下匹配方式，即以最近距離與次近距離比作為特征點匹配的標準。若單獨將特征向量集合作為建筑物的描述信息，在特征匹配時由于特征點分布于多幅不同角度的圖像中，符合最近距離的特征點與次近距離的特征點常位于不同的圖像上，容易造成匹配失敗。因此在模型M中，特征的集合以圖像為單位進行存儲與匹配，之后再通過對應(yīng)的位置信息，使用RANSAC算法對錯誤匹配的特征點進行過濾。

2.2 多角度特征模型指紋庫

特征庫主要用來存儲建筑物特征。與G Schroth使用視覺詞匯作為移動視覺定位系統(tǒng)特征庫不同的是，本文使用更有針對性的建筑物多角度特征模型建立特征庫。具體流程如圖2所示。

圖2 多角度特征模型指紋庫流程

（1）環(huán)繞建筑物，每隔N米拍攝不同角度的建筑物原始圖像，建立原始圖像庫P（p1，p2，p3…，pn），本文N取15。對于較大較長的建筑物，可以將建筑物分塊處理，分別采集每塊建筑物不同位置不同視角的圖片。

（2）對P（p1，p2，p3…，pn）中的圖像進行預(yù)處理，得到新的圖像集P'（p'1，p'2，p'3…，p'n）。由于拍攝的圖片中存在樹木、草地、道路、汽車等噪聲，需要進行預(yù)處理去掉這些噪聲。校內(nèi)建筑物的主題顏色均為紅色與白色，可以通過顏色特征過濾掉草地與樹木枝葉。建筑物在空間分布上一般位于照片上半部分，道路與汽車位于照片下半部分，可以通過空間區(qū)域劃分去掉底部的無關(guān)內(nèi)容。

（3）對圖像集P'中的圖片進行相互匹配。

（4）以正確匹配特征點的數(shù)量評價匹配的優(yōu)劣，將正確匹配特征點數(shù)超過閾值T的圖片記錄為正確匹配的特征信息，構(gòu)建多角度特征模型MN。

（5）將建筑物多角度特征模型MN寫入指紋庫。

實驗發(fā)現(xiàn)，對于同一建筑物，由于拍攝方向、角度不同，圖像在內(nèi)容上差別較大。例如，一號教學(xué)樓東西長250m，整體具有一定弧度，具有中間凸兩邊凹的特點。如圖3所示。

圖3 一號樓不同角度照片

圖3為一號樓4幅不同角度的照片?？梢钥闯觯捎阽R頭的限制，一幅圖片很難涵蓋整座建筑物，而且由于拍攝地點、角度等不同，幾幅圖片差別較大。若只采用一幅特定角度的照片表示一號教學(xué)樓，則當(dāng)檢索圖像角度差別較大時，匹配就會失敗。例如，實驗中發(fā)現(xiàn)圖3 （a）和圖3（b）正確匹配的特征點為0。因此，為了獲得整棟建筑物各角度的特征同時考慮到特征數(shù)據(jù)庫的大小，本文采取每隔15m采集一次建筑物圖像的方法。如圖4所示。

圖4 建筑物連續(xù)角度照片

圖4（a）—（e）是在不同地點拍攝的連續(xù)6幅一號教學(xué)樓照片。其中，（a）（b）、 （a）（c）、（a）（d）、（a）（e）、（a）（f）之間的距離漸次增大。實驗發(fā)現(xiàn)，圖4 （a）與圖4（b）、圖4（c）匹配特征點數(shù)量均大于100，與（d）匹配數(shù)量低于100，與（e）、（f）匹配失敗?？梢钥闯觯?dāng)拍攝地點距離較遠，引起視角變化較大時匹配基本不成功，因此只需要相互匹配鄰近的四五個圖像采集點的不同視角的圖像即可。最后篩選匹配特征點數(shù)量較多的圖片對，得到穩(wěn)定的特征點。

2.3 在線特征匹配

由于照片拍攝環(huán)境復(fù)雜，為了得到準確的特征匹配，本文在匹配過程采用了RANSAC[9]算法過濾錯誤匹配。特征匹配具體步驟如下：

（1）獲取用戶上傳的圖像IQ并提取其特征FQ（f1，f2...fn）。

（2）依次讀取特征庫中的特征文件J（J=1，2，3…N）中的特征FD與FQ進行特征匹配，其中N為特征文件的個數(shù)。

（3）利用RANSAC算法過濾錯誤匹配。通過建筑物特征文件中保留的匹配特征點位置信息求得單應(yīng)性矩陣H。設(shè)PD（x1，y1），PQ（x2，y2）分別為數(shù)據(jù)庫與檢索圖片中一對匹配的特征點。PD（x1，y1）經(jīng)過矩陣H變換后得到PD′（x1 ′，y1′）。若PD′（x1 ′，y1′）與PQ（x2，y2）的歐式距離小于閾值，則認為PD（x1，y1），PQ（x2，y2）是一對正確匹配。

（4）累計每個特征文件J（J=1，2，3…N）中與IQ特征成功匹配的特征點的數(shù)量Num。

（5）將建筑物特征點匹配數(shù)量Num與閾值Tn進行比較，若大于閾值Tn，則該建筑物為候選匹配建筑物。

（6）返回匹配特征點數(shù)量最多的候選建筑物信息。

具體匹配流程如圖5所示。

本文以特征點匹配數(shù)量作為圖片匹配標準，其中閾值Tn的設(shè)定決定了算法的準確度。本文取不同建筑物不同角度照片與指紋庫中的特征文件進行特征匹配。表1和表2描述了指紋庫中部分建筑物與自身圖片及其它建筑物圖片匹配的結(jié)果。

可以看出，指紋庫中建筑物的測試照片與指紋庫進行匹配時，匹配特征點個數(shù)均大于20，而指紋庫以外建筑物的照片與指紋庫進行特征匹配時匹配數(shù)量普遍較少，且最高匹配數(shù)量均小于10，具有良好的區(qū)分性。因此本文將閾值Tn設(shè)為20，同時采用匹配特征點數(shù)量排序來保證匹配的準確性。

3 實驗結(jié)果與分析

本文實驗采用浪潮英信NF280D作為服務(wù)器，其配置為2.67GHz CPU，8GB內(nèi)存；手機端采用華為honor3C智能手機、三星SM-G3812、紅米手機等5部不同品牌型號的手機，其配置均為1GB內(nèi)存；無線網(wǎng)絡(luò)采用傳輸速度為54Mbps的WiFi。

算法采用第一種架構(gòu)模式，特征提取、匹配運算都集中在服務(wù)器端，性能評估也主要集中在服務(wù)器端，數(shù)據(jù)傳輸效率與匹配準確度是需要重點解決的問題。為了評估服務(wù)器端識別算法的性能，本文使用隨機拍攝的校內(nèi)建筑照片進行精確度測試。測試系統(tǒng)數(shù)據(jù)庫中存儲15座建筑物的特征信息。

圖6 測試數(shù)據(jù)集圖片

如圖6所示，校內(nèi)每座建筑選擇隨機拍攝的20幅不同角度、不同時間、不同天氣、不同光照情況下的照片共300幅，再選擇數(shù)據(jù)庫外建筑照片100幅對系統(tǒng)的精確度進行測試。

表3記錄了15座建筑物的匹配結(jié)果，分別用查全率與查準率對匹配結(jié)果進行評估。測試結(jié)果查全率在0.75～1之間，查準率在0.94～1之間，而G Schroth基于BOF算法的定位算法的查準率最大值為0.7[1]，可以看出本算法在查準率上有了較大提高，這主要是因為在每一次進行特征匹配后都會通過RANSAC算法進行一次幾何一致性校驗，來降低誤識別率。查詢圖像與建筑物數(shù)據(jù)庫中的所有圖像匹配完成后，算法將每座建筑所有匹配的特征點累加，再對特征點數(shù)量排序，選擇匹配特點數(shù)量最多的建筑作為最后結(jié)果，進一步保證了查準率。

圖7是一號教學(xué)樓兩幅不同角度的測試圖像，（a）為一號樓中部正面照片，（b）為一號樓西部正面照片。圖中黑色的點是圖像與特征庫實現(xiàn)匹配的特征點。若采用單一角度的特征作為建筑物的特征庫，特征匹配過程中只能匹配圖7（a）、圖7（b）中的一幅圖像。而采用多角度特征描述模型能夠保留建筑物不同角度的特征，在匹配過程中系統(tǒng)針對不同角度的上傳圖像匹配不同角度下的特征點（圖7（a）和圖7（b）中黑色的點），實現(xiàn)圖像匹配。

圖7 同一建筑不同角度照片匹配結(jié)果

圖8是一號樓匹配失敗圖像。可以看出，圖片中樹木遮擋嚴重，建筑物比例較低。匹配的特征點本身較少，經(jīng)過幾何一致性校驗后低于成功匹配的閾值。針對這種遮擋嚴重的情況，在后續(xù)工作中可以通過對圖像分塊的方式，獲取圖像中受遮擋干擾較小的部分實現(xiàn)匹配。

圖8 一號樓匹配失敗圖片

通過對實驗結(jié)果進行綜合分析可知，基于建筑物多角度特征模型的特征庫通過存儲建筑物不同角度的穩(wěn)定的特征信息，能較好解決視角變化造成的圖像不匹配問題。同時特征點的空間位置信息在過濾錯誤匹配和提高圖像搜索匹配查準率上具有重要作用。該算法查準率均大于90%，與基于BOF算法的移動視覺定位系統(tǒng)相比，精度有較大提高。實驗結(jié)果證明了該算法的可行性與優(yōu)越性。

4 結(jié)語

本文提出了一種面向大建筑物的移動視覺定位算法，通過提取建筑物不同角度的特征建立建筑物多角度特征模型描述建筑物，并基于該模型建立建筑物特征庫，最后通過在特征庫中匹配用戶提交的不同角度建筑物照片的特征點實現(xiàn)定位。該算法讓用戶可以通過拍攝周圍的建筑物即時定位，解決了GPS在高樓林立的市區(qū)定位不準，只能定位地圖中相應(yīng)坐標，不能獲取相應(yīng)位置的人文資訊的問題；同時，相比基于BOF算法的移動視覺定位系統(tǒng)，

提高了匹配的精度。

如何提高算法匹配效率，并研究能夠在手機端運行的特征提取算法，減輕服務(wù)器壓力，提高算法實時性，都有待進一步研究。

參考文獻：

[1] G SCHROTH，R HUITL，D CHEN.Mobile visual location recognition[J].IEEE Signal Processing Magazine， 2011， 28（4）： 77-91.

[2] G SCHROTH，A AL-NUAIMI，R HUITL.International rapid image retrieval for mobile location recognition[C].Acoustics， Speech and Signal Processing （ICASSP）， 2011： 2320–2323.

[3] R HUITL，G SCHROTH，S HILSENBECK.TUMindoor： an extensive image and point cloud dataset for visual indoor localization and mapping[C].IEEE International Conference on Image Processing （ICIP 2012）， 2012： 1773–1776.

[4] GOOGLE.Google goggles [EB/OL].http： // www. google.com/mobile/goggles/，2009.

[5] AMAZON.SnapTell[EB/OL].http：//www.snaptell.com，2007.

[6] XU LIU，JONATHAN HULL，JAMEY GRAHAM，et al. Mobile visual search， linking printed documents to digital media [C]. In CVPR 2010 Demonstrations，2010.

[7] J SIVIC，A ZISSERMAN.Video google： a text retrieval approach to object matching in videos[C]. IEEE Int. Conf. Computer Vision，2003： 1470-1477.

[8] B GIROD，V CHANDRASEKHAR，D CHEN，et al. Mobile visual search [J].IEEE Signal Processing Magazine， 2011， 28（4）： 61-76.

[9] FISCHLER M A，BOLLES R C.Random sample consensus： a paradigm for model fitting with applications to image analysis and automated cartography [J].Communications of the ACM，1981， 24（6）： 381-395.

[10] ZHUANG XINGWANG，HUANG XIAOBIN.An overview of mobile visual search abroad[J].Journal of Library Science in China，2014： 114-128.

[11] LING-YU DUAN，F(xiàn)ENG GAO，JIE CHEN，et al.Compact descriptors of mobile visual search and MPEG CDVS standardization[C].International Symposium on Circuits and Systems （ISCAS），2013：885-888.

[12] 段凌宇，黃鐵軍，高文.移動視覺搜索技術(shù)研究與標準化進展[J].信息通信技術(shù)，2012（6）：51-58.

[13] D LOW.Distinctive image features from scale-invariant keypoints[J].International Journal of Computer Vision， 2004， 59（1）： 91-110.

（責(zé)任編輯：孫 娟）