基于流形結(jié)構(gòu)的圖像地理信息標注方法

葉 巍，龔 建 華，郭 娜，路 梅，趙 向 軍

(1.江蘇師范大學(xué)計算機科學(xué)與技術(shù)學(xué)院，江蘇 徐州 221116；2.中國科學(xué)院遙感與數(shù)字地球研究所，北京 100101)

?

基于流形結(jié)構(gòu)的圖像地理信息標注方法

葉 巍1，龔 建 華2，郭 娜1，路 梅1，趙 向 軍1

(1.江蘇師范大學(xué)計算機科學(xué)與技術(shù)學(xué)院，江蘇 徐州 221116；2.中國科學(xué)院遙感與數(shù)字地球研究所，北京 100101)

借助攜帶地理信息的圖像數(shù)據(jù)，標注未知圖像的地理信息，是圖像視頻地理信息系統(tǒng)迫切需要的基于內(nèi)容的檢索工具。傳統(tǒng)基于文本的地理信息標注方法主要借助人工完成，效率低下且無法運用于視頻GIS檢索之中，針對該問題，提出了基于流形結(jié)構(gòu)的圖像地理信息標注方法。該方法提取圖像的視覺特征作為相似度度量，重構(gòu)地理圖像的流形結(jié)構(gòu)，用以刻畫不同視角視圖圖像的漸進變化規(guī)律，建立相同地理位置不同視角圖像之間的內(nèi)部關(guān)聯(lián)，以便攜帶地理信息的共享。構(gòu)建地理圖像的流形結(jié)構(gòu)需要連續(xù)視角變化的地理圖像，當已有地理圖像視角變化跳躍時，提出利用主動學(xué)習(xí)策略，通過交互完成視角變化跳躍位置的地理圖像補充，同時進行增量式訓(xùn)練，提升地理信息標注方法的泛化能力。實驗結(jié)果表明，給出攜帶地理信息的圖像，該文方法可以獲得相同地理位置處流形結(jié)構(gòu)內(nèi)的所有地理圖像，高效完成地理信息標注。此外，在應(yīng)對成像視角變化跳躍的情況時，具有較強的魯棒性。

圖像標注；地理信息系統(tǒng)；地理位置；流形學(xué)習(xí)；主動學(xué)習(xí)

0 引言

隨著移動互聯(lián)網(wǎng)絡(luò)的快速普及，攝錄和定位模塊在智能移動終端設(shè)備上的廣泛嵌入，巨量具有位置信息的圖像數(shù)據(jù)正以前所未有的速度急速聚集，特別是街景地圖的大量涌現(xiàn)，可供用戶多視角自由瀏覽，能夠方便地對特定目標位置的地形地貌、道路交通等進行直觀規(guī)劃與情景預(yù)演，給人們的生產(chǎn)生活帶來了極大的便利。上述問題的逆問題，就是根據(jù)圖像內(nèi)容獲得其地理信息特別是地理位置信息，進而可獲取對應(yīng)位置周邊的自然、社會信息。

傳統(tǒng)的地理信息系統(tǒng)(GIS)借助文本匹配獲得圖像的地理位置信息，需要大量人工標注，且標注結(jié)果易受主觀因素影響。國外一些學(xué)者直接利用圖像特征進行地理位置標注[1-4]，有效克服了上述不足，展現(xiàn)了較為理想的精度。然而這些地理位置標注方法直接采用圖像分類技術(shù)，當?shù)乩韴D像的成像視角發(fā)生變化時，將產(chǎn)生較大偏差。流形學(xué)習(xí)方法[5,6]可以有效發(fā)現(xiàn)數(shù)據(jù)集的內(nèi)在流形結(jié)構(gòu)，準確地表示地理圖像連續(xù)、漸進地變化，也可有效克服地理圖像特征的維度災(zāi)難(Curse of Dimensionality)[7]問題?；趫D的半監(jiān)督學(xué)習(xí)方法[8]借助圖學(xué)習(xí)模型重構(gòu)數(shù)據(jù)集的流形結(jié)構(gòu)，更直觀地呈現(xiàn)數(shù)據(jù)集的低維子流行，使得標注模型有較強的泛化能力。

流形重構(gòu)要求地理圖像變化連續(xù)，成像視角不連續(xù)直接影響重構(gòu)效果，進而降低標注精度。主動學(xué)習(xí)[9,10]主動選取訓(xùn)練集中高信息量的樣本，高效訓(xùn)練模型，可有效提升信息標注精度。為此，本文借助基于流形結(jié)構(gòu)的檢索方法進行圖像地理信息標注，消除成像視角變化對標注結(jié)果的影響。結(jié)合主動學(xué)習(xí)原理，有效克服在較大空間場景下采樣數(shù)據(jù)不足的問題，從而提高檢索準確率。

1 標注流程概述

本文提出了一種基于流形結(jié)構(gòu)的地理信息標注方法，該方法首先提取圖像庫中所有圖像的顏色特征和形狀特征，采用顏色直方圖和邊緣方向直方圖表示，以直方圖相交(Histogram Intersection) 作為相似性度量，在此基礎(chǔ)上，采用拉普拉斯特征映射(Laplacian Eigenmap,LE)[11]揭示地理圖像數(shù)據(jù)的流形結(jié)構(gòu)，在降維后的低維子流形進行檢索，并利用相關(guān)反饋技術(shù)(Relevance Feedback,RF)[12]獲得用戶語義信息，提高檢索精度。與此同時，借助BvSB (Best-versus-Second Best)[13]主動學(xué)習(xí)方法主動獲取欠采樣位置補充訓(xùn)練，高效調(diào)整流形結(jié)構(gòu)，增強模型的泛化能力。最后，統(tǒng)計檢索結(jié)果中位置信息，對輸入圖像進行標注。整個標注系統(tǒng)的檢索部分流程如圖1所示。

圖1 基于流形結(jié)構(gòu)的圖像地理信息標注方法檢索流程

Fig.1 The retrieval process of information annotation of geographic image based on manifold structure

2 基于流形結(jié)構(gòu)的標注方法

2.1 特征表示與度量

顏色對平移、旋轉(zhuǎn)變換具有不變性，表現(xiàn)出相當強的魯棒性，因此在圖像檢索中得到了廣泛的應(yīng)用。顏色直方圖是常用的顏色特征表達方法，能有效地反映地理圖像中的地貌特征，因此，本文采用顏色直方圖作為地理圖像的特征表示。

首先將地理圖像從RGB顏色空間轉(zhuǎn)換為HSV顏色空間。設(shè)RBG的顏色空間值為(R,G,B)，其中R,G,B∈[0,255]，令r=R/255，g=G/255，b=B/255，則可得HSV空間的值(H,S,V)：

(1)

(2)

(3)

由上式可知H∈[0,2π]，S∈[0,1],V∈[0,1]。在此基礎(chǔ)上，對圖像在HSV顏色空間中進行256級量化統(tǒng)計，即將H分成16等份，S和V分成4等份。令Hist=(h1,h2,…,hn)(n=256)表示地理圖像IM×N的顏色直方圖，則hc∈Hist可由下式求出：

(4)

(5)

形狀特征可以有效地表示地理圖像中的地形地物，也是圖像檢索中較為常用的視覺特征。本文借助Sobel算子[14]，采用邊緣方向直方圖表示地理圖像的形狀特征。水平方向和豎直方向上的Sobel模板如圖2所示。

首先用水平和豎直方向上的Sobel模板Sobelx和Sobely計算地理圖像I中點(i,j)處的梯度：

圖2 水平和豎直方向上的Sobel模板

Fig.2Sobelmasksinhorizontalandverticaldirection

Gx(i,j)=Sobelx*I(i,j)

(6)

Gy(i,j)=Sobely*I(i,j)

(7)

則點(i,j)處的邊緣強度為：

(8)

在此基礎(chǔ)上，對Gx(i,j)與Gy(i,j)進行閾值化處理，對于給定的閾值φ，當邊緣強度G(i,j)≥φ時，該像素點為地理圖像的邊緣像素點。而當邊緣強度G(i,j)≤φ時，令Gx(i,j)與Gy(i,j)為0。則點(i,j)處的邊緣方向為：

(9)

其中:θ∈[-π/2,π/2]。此時可將θ分成18等份，在此基礎(chǔ)上，利用求顏色直方圖的方法，求得地理圖像的邊緣方向直方圖。

兩個圖像的相似度可用直方圖相交來計算，設(shè)直方圖Ha和Hb有n個直方塊(Bin)，則兩個直方圖的相交可表示為：

(10)

本文采用地理圖像的顏色直方圖和邊緣方向直方圖加權(quán)值計算兩個地理圖像間的相似度，即：

L(I1,I2)=αLc(I1,I2)+(1-α)Le(I1,I2)

(11)

其中:Lc(I1,I2)表示兩個地理圖像的顏色直方圖相交，Le(I1,I2)表示兩個地理圖像的邊緣方向直方圖相交,α為人工給定系數(shù)。

2.2 流形重構(gòu)與檢索標注

地理圖像數(shù)據(jù)尤其是視頻圖像序列，成像視角通常漸進連續(xù)變化，因此，在每個微小的局部鄰域上，地理圖像的特征空間可被視作具有局部平滑性的線性結(jié)構(gòu)。在此基礎(chǔ)上，可以假設(shè)地理圖像的特征空間是嵌入在高維空間中的低維流形，采用基于譜圖的非線性降維方法對地理圖像特征進行降維。

步驟 1：構(gòu)造k近鄰圖G。

步驟 2：定義鄰接權(quán)值矩陣W。有兩種方法構(gòu)造權(quán)值矩陣：

(1)熱核法(HeatKernel)。如果i點和j點在近鄰圖G中有邊相連，則兩點間的權(quán)值設(shè)為：

Wij=exp(-t-1‖xi-xj‖2)

(12)

(2)簡單方法。如果點i和點j在近鄰圖G中有邊相連，則邊上的權(quán)值為1，否則為0。

步驟 3：特征映射。假設(shè)圖G為連通圖(否則對每一個連通部分分別計算)，構(gòu)造目標函數(shù)：

(13)

其中：Y=(y1,y2,…,yn)，Dij=∑i,jWij，L=D-W為拉普拉斯矩陣，為實對稱的半正定矩陣，采用拉格朗日乘數(shù)，計算矩陣L的d+1個最小特征值對應(yīng)的特征向量u1,u2,…,ud+1，則嵌入在低維空間上的坐標可表示為Y=[u1,u2,…,ud+1]T。

下午的議程將大會分為兩大主題分會場，分別圍繞著“轉(zhuǎn)型升級高峰論壇”和“新材料與綠色供應(yīng)鏈”進行主旨演講與高峰論壇環(huán)節(jié)，眾多國內(nèi)外專家學(xué)者、協(xié)會領(lǐng)導(dǎo)與品牌負責(zé)人進行對話，圍繞著專題內(nèi)容進行研究探討。

對于一張給定待標注地理圖片，標注步驟如下：

步驟 1：提取地理圖像數(shù)據(jù)的視覺特征，構(gòu)建特征向量，包括：1)構(gòu)建256類的顏色直方圖；2)在[-π/2,π/2]范圍內(nèi)，將不同走向的每10°劃分為一類，構(gòu)成18類的邊緣方向直方圖。

步驟 2：流形曲面的構(gòu)建。除了特征空間中特征向量較近的圖像建立鄰接外，充分考慮視頻流的恢復(fù)信息，對視點接近的各幀建立鄰接關(guān)系。

步驟 3：利用拉普拉斯特征映射對特征空間降維。

步驟 4：在樣本的低維特征空間下進行度量距離排序，以此為基礎(chǔ)，得到圖像檢索序列R={r1,r2,…,rn}。

步驟 5：相關(guān)反饋。返回檢索結(jié)果中前19張圖片。用戶對檢索結(jié)果標記負樣例，在線調(diào)整拉普拉斯特征映射。

步驟 6：用檢索結(jié)果中最先出現(xiàn)的有標簽樣本的位置信息標注輸入圖像，即：

其中：S為指示函數(shù)，即當yi=cj時S為i，否則為∞；k為標簽總數(shù)；n為圖像庫中圖像總數(shù)。

2.3 主動式增量訓(xùn)練

單張地理圖片包含的信息量較少，無法全面表達空間場景信息。而地理圖像庫中的圖片數(shù)據(jù)往往不能準確反映圖像成像視點的連續(xù)變化,從而使流形結(jié)構(gòu)上數(shù)據(jù)點的分布不均勻，檢索精度受到影響。此時可采用基于不確定性的主動學(xué)習(xí)方法[10]主動獲取欠采樣位置，高效提升標注模型的精度。

基于不確定性的主動學(xué)習(xí)方法每次選取具有最大熵的樣本：

(15)

信息檢索往往涉及多分類問題，然而在多分類問題中，有些具有較小熵的樣本的分類不確定性往往大于熵較大的樣本，使得基于最大熵的樣例選擇方法不能較為理想地選取高價值樣本[15]。因此，本文采用BvSB方法，它是基于不確定性主動學(xué)習(xí)方法的改進，只考慮在多分類問題中樣本分類可能性最大的兩類而忽略其他對分類結(jié)果影響較小的類別：

(16)

其中：P(yB|x)表示x屬于具有最大可能性類別yB的概率;P(yi|x)表示除yB之外，x屬于各個類別yi的概率。

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

3.1 實驗方案

標注原型系統(tǒng)采用Matlab編寫，運行于64位的window7操作系統(tǒng)，實驗設(shè)備采用IntelCorei7 3.4GHz處理器，4G內(nèi)存的PC機。

本文選取了60個不同的地理位置，每個位置拍攝視角各異的100張圖片，其中僅有一個圖像攜帶地理信息。事實上，這些地理圖片均采用具有定位功能的攝錄設(shè)備獲得，但每個位置中僅選取一張圖片進行地理位置標注。為保證流形結(jié)構(gòu)的重構(gòu)，攝錄視角間隔不能太大，以等間隔連續(xù)變化為宜。以上6 000張圖像作為標注系統(tǒng)的圖像庫，構(gòu)建地理圖像的流形網(wǎng)絡(luò)。此外，在上述拍攝位置，任意視角隨機拍攝若干圖片作為待標注測試集。用戶輸入待標注圖片，系統(tǒng)借助圖像的流形結(jié)構(gòu)從圖像庫中檢索出相同地理位置的地理圖像，并尋找到攜帶地理信息的樣本來標注輸入圖像。在相關(guān)反饋中，系統(tǒng)返回前19張檢索結(jié)果給用戶進行語義標記，重新檢索并標注圖片。如果因為流形不完整導(dǎo)致無法標注，算法會自動反饋最佳推薦位置，供用戶交互確認并補充數(shù)據(jù)，同時將補充數(shù)據(jù)加入訓(xùn)練集進行增量訓(xùn)練。

3.2 檢索性能評價

查全率(Recall)和查準率(Precision)是圖像檢索系統(tǒng)中普遍采用的評價標準，查全率是檢索系統(tǒng)返回的查詢結(jié)果中與被檢索數(shù)據(jù)語義相關(guān)的圖像數(shù)目占圖像數(shù)據(jù)庫中所有相關(guān)圖像數(shù)目的比例，查準率則指檢索系統(tǒng)中返回的語義相關(guān)圖像數(shù)目占所有返回的圖像數(shù)目的比例。令T為圖像數(shù)據(jù)庫中所有和被檢索圖像語義相關(guān)的圖像集合，S為所有返回的圖像集合，t為一次查詢中返回的所有語義相關(guān)的圖像數(shù)目，v為圖像數(shù)據(jù)庫中沒有被檢索到的相關(guān)圖像數(shù)目，u為返回的不相關(guān)圖像數(shù)目，則查全率表示為式(17)，查準率表示為式(18)。

(17)

(18)

查全率和查準率是一對負相關(guān)的評價指標。過高的查全率會導(dǎo)致低查準率，過高的查準率也會導(dǎo)致低查全率，因此大多檢索系統(tǒng)試圖尋找二者間的平衡。本文通過檢索的返回結(jié)果確定圖像的地理位置信息進行標注，所以僅需查準率來評價檢索精度。

3.3 結(jié)果分析

圖3為本文基于流形結(jié)構(gòu)的圖像地理信息標注方法的檢索結(jié)果，通過輸入的單張待標注地理圖片，可以在地理圖像庫中檢索出圖像內(nèi)容相近的圖片，系統(tǒng)自動根據(jù)檢索結(jié)果標注圖片的地理位置信息。

圖3 基于流形結(jié)構(gòu)的圖像地理信息標注系統(tǒng)檢索結(jié)果

Fig.3 The retrieval result of information annotation of geographic image based on manifold structure

圖4是從一座橋梁在不同視角下移動拍攝所得地理視頻數(shù)據(jù)中截取的3張圖片，可以看出，不同視角下得到的三張地理圖片差別較大。以歐氏距離為度量基礎(chǔ)的標注系統(tǒng)中，橋梁的一個側(cè)面視角圖像為待標注圖像，從該橋梁正面視角和另一側(cè)面視角得到的圖像與被標注圖像的度量距離分別為0.12537和0.08874。而基于本文算法設(shè)計的標注系統(tǒng)中，度量距離只有0.05553和0.03588。因此，本文提出的借助圖像流形結(jié)構(gòu)的地理信息標注方法能有效克服地理圖像成像視角變化對標注結(jié)果的影響。

圖5是采用拉普拉斯特征映射降維的圖像檢索方法和借助主動學(xué)習(xí)增量訓(xùn)練之后的圖像檢索方法的準確率比較。檢索系統(tǒng)利用前50個檢索結(jié)果計算查準率。在只有3 000張訓(xùn)練樣本(每個地理位置采樣50張)的情況下，以及每個地理位置采樣數(shù)據(jù)每次增加10張(總采樣數(shù)據(jù)每次增加600張)的情況下，可以看出借助BvSB進行主動式增量訓(xùn)練在檢索查準率上有一定提高。

4 結(jié)論

圖4 在歐氏距離下與流形結(jié)構(gòu)中同一地理位置的度量距離

Fig.4 The measure distances of image in Euclidean space and manifold structure at the same geographic position

圖5 主動式增量訓(xùn)練對基于流形結(jié)構(gòu)的圖像檢索查準率的影響

Fig.5 The effects of active incremental training on the precision of image retrieval based on manifold structure

本文提出了一種基于流形結(jié)構(gòu)的圖像地理信息標注方法，可以很好地解決圖像成像視角變化對標注精度的影響，采用流形學(xué)習(xí)方法對圖像特征進行降維，準確呈現(xiàn)地理圖像數(shù)據(jù)間的內(nèi)在聯(lián)系。根據(jù)圖像檢索結(jié)果標注圖像的地理信息，較之傳統(tǒng)基于分類的標注模型，泛化能力大大增強。除采用相關(guān)反饋方法增強模型的標注精度外，借助主動學(xué)習(xí)策略對采樣數(shù)據(jù)不足的地理位置進行補充采樣，在線調(diào)整地理圖像的流形結(jié)構(gòu)，使得本文提出的標注方法具有較強的魯棒性。地理圖像中的流形結(jié)構(gòu)是普遍存在的，本文僅僅就視角變化的流形結(jié)構(gòu)進行了探討，而對于季節(jié)變化、陰晴雨雪等天氣條件下的地理圖像之間的關(guān)聯(lián)結(jié)構(gòu)，仍需進一步深入研究。

[1] LUO J,JOSHI D,YU J,et al.Geotagging in multimedia and computer vision-a survey[J].Multimedia Tools and Applications,2011,51(1):187-211.

[2] GALLAGHER A,JOSHI D,YU J,et al.Geo-location inference from image content and user tags[A].Proceedings of the 2009 IEEE Conference on Computer Vision and Pattern Recognition[C].Miami,United states:IEEE Computer Society,2009.55-62.

[3] HAYS J,EFROS A A.IM2GPS:Estimating geographic information from a single image[A].Proceedings of the 26th IEEE Conference on Computer Vision and Pattern Recognition[C].Anchorage,United states:IEEE Computer Society,2008.1-8.

[4] LI Y,CRANDALL D J,HUTTENLOCHER D P.Landmark classification in large-scale image collections[A].IEEE 12th International Conference on Computer Vision[C].Kyoto,Japan:IEEE Computer Society,2009.1957-1964.

[5] ROWEIS S T,SAUL L K.Nonlinear dimensionality reduction by locally linear embedding[J].Science,2000,290(5500):2323-2326.

[6] TENENBAUM J B,DE SILVA V,LANGFORD J C.A global geometric framework for nonlinear dimensionality reduction[J].Science,2000,290(5500):2319-2323.

[7] DONOHO D L.High-dimensional data analysis:The curses and blessings of dimensionality[R].AMS Math Challenges Lecture,2000.1-32.

[8] ZHOU D,BOUSQUET O,LAL T N,et al.Learning with local and global consistency[J].Advances in Neural Information Processing Systems,2004,16(16):321-328.

[9] TONG S,CHANG E.Support vector machine active learning for image retrieval[A].Proceedings of the ACM Multimedia 2001 Workshops 2001 Multimedia Conference[C].Ottawa,Canada:Association for Computing Machinery,2001.107-118.

[10] LEWIS D,GALE W.A sequential algorithm for training text classifiers[A].Proceedings of the 17th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval[C].New York,United states:Springer-Verlag,1994.3-12.

[11] BELKIN M,NIYOGI P.Laplacian eigenmaps for dimensionality reduction and data representation[J].Neural Computation,2003,15(6):1373-1396.

[12] RUI Y,HUANG T S,ORTEGA M,et al.Relevance feedback:A power tool for interactive content-based image retrieval[J].IEEE Transactions on Circuits and Systems for Video Technology,1998,8(5):644-655.

[13] JOSHI A J,PORIKLI F,PAPANIKOLOPOULOS N.Multi-class active learning for image classification[A].Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition Workshops[C].Miami,United States:IEEE Computer Society,2009.2372-2379.

[14] PATEL J,PATWARDHAN J,SANKHE K,et al.Fuzzy inference based edge detection system using Sobel and Laplacian of Gaussian operators[A].Proceedings of the International Conference and Workshop on Emerging Trends in Technology[C].Mumbai,India:Association for Computing Machinery,2011.694-697.

[15] 陳榮,曹永鋒,孫洪.基于主動學(xué)習(xí)和半監(jiān)督學(xué)習(xí)的多類圖像分類[J].自動化學(xué)報,2011,37(8):954-962.

Information Annotation of Geographic Image Based on Manifold Structure

YE Wei1,GONG Jian-hua2,GUO Na1,LU Mei1,ZHAO Xiang-jun1

(1.SchoolofComputerScienceandTechnology,JiangsuNormalUniversity,Xuzhou221116; 2.InstituteofRemoteSensingandDigitalEarth,ChineseAcademyofSciences,Beijing100101,China)

Annotating the location for geographical image is an important tool in image and video geographic information system.Focused on the leakage of existing geographic information annotation methods,which take a great deal of manual annotation cost,this paper proposes a geographic information annotation method based on manifold structure.This method directly extracts visual features of images as similarity measure,meanwhile,makes use of manifold learning to accomplish the manifold reconstruction in order to describe the continuous change of viewing angle,and then annotates the image through the results of image retrieval.Active learning is used to actively get the insufficient sampling place and perform incremental training simultaneously so as to increase the accuracy of annotation.The experimental results show the method is reliable although the camera angle is dramatically changed.

image annotation;GIS;geographical location;manifold learning;active learning

2014-11-11；

2015-01-22

江蘇省普通高校研究生科研創(chuàng)新計劃項目(CXLX13_979)；國家自然科學(xué)基金項目(61272297、 61402207)

葉巍(1988-)，男，碩士研究生，主要研究方向為深度學(xué)習(xí)、圖像檢索與三維模型檢索。E-mail：396899547@qq.com

10.3969/j.issn.1672-0504.2015.03.002

TP391;P208

A

1672-0504(2015)03-0007-05