基于FSFDP-BoV模型的遙感影像檢索

沈 忱,祁 昆 侖,劉 文 軒,吳 華 意

(武漢大學測繪遙感信息工程國家重點實驗室,湖北 武漢 430079)

基于FSFDP-BoV模型的遙感影像檢索

沈 忱,祁 昆 侖,劉 文 軒,吳 華 意

(武漢大學測繪遙感信息工程國家重點實驗室,湖北 武漢 430079)

為提高遙感影像檢索的精度，提出一種基于快速查找密度峰值聚類(Fast Search and Find of Density Peaks,FSFDP)的改進視覺詞袋(Bag of Visual word,BoV)模型，該方法充分利用FSFDP聚類算法分類精度高和聚類參數易于選擇等優點，增強BoV模型特征量化的穩定性和可靠性。實驗表明，與經典BoV模型相比，FSFDP-BoV模型能夠得到更高的檢索精度。

遙感影像;檢索;BoV;密度峰值聚類

0 引言

隨著遙感影像的數據源和數據量的快速增長[2]，基于內容的圖像檢索[2]成為當前遙感影像檢索的一個研究熱點和難點[3,4]，提高遙感影像檢索精度已成為基于內容的影像檢索研究的必經之路。

視覺詞袋(Bag of Visual word,BoV)模型是基于內容的圖像檢索中最熱門的方法之一[5]。BoV模型源于信息領域的詞袋(Bag of Words,BoW)模型。對于一個文本，BoW模型忽略其詞序和語法句法，僅僅將其看作是一個詞集合，文本中每個詞的出現都是獨立的，不依賴于其他詞是否出現，即在任意位置選擇一個詞匯都不受前面句子的影響。由于BoW模型在特征描述方面有著獨特的優勢，因此將BoW模型的思想應用于圖像的特征描述中，即BoV模型，當前已經廣泛地應用于圖像和視頻的檢索方面[6,7]。

為提升BoV模型在遙感影像檢索中的精度和效率,研究者對BoV模型做出了改進[6-11]，改進后方法能夠有效地提高檢索的精度，但在特征量化時均沒有考慮密度信息，無法滿足地物繁多且目標復雜的高分辨率遙感影像檢索的需求。

2014年Rodriguez等提出了快速查找密度峰值聚類 (Clustering by Fast Search and Find of Density Peaks,FSFDP)[12]算法，該聚類方法具有靈活性高、穩定性強、效率高等特點。基于此算法，本文提出了BoV改進模型——FSFDP-BoV模型，并將其應用于遙感影像檢索中。

1 基于BoV模型的特征描述

BoV模型在遙感影像檢索中主要用于影像特征描述向量的生成[13]。假設有一組圖像，從中選出測試樣本和訓練樣本。首先，分別提取訓練樣本和測試樣本的底層特征，如SIFT(Scale-Invariant Feature Transform)特征[14]、將圖像剛性分割成多個塊提取的顏色特征、紋理特征等,則每個圖像就由很多個底層的局部特征表示，這些特征就是視覺詞匯向量。然后利用K-Means算法對訓練樣本的視覺詞匯向量進行聚類，選擇聚類中心作為視覺字典的基礎詞匯。再利用歐式距離計算測試樣本的視覺詞匯向量與基礎詞匯的相似度，并用基礎詞匯表中的單詞代替圖像中的視覺詞匯向量，統計出每一幅測試樣本中基礎詞匯出現的次數，即統計直方圖并作歸一化處理，得到每一幅影像的特征向量，最終應用于影像的分類、檢索等[15,16]。

BoV模型描述遙感影像的流程主要包含特征提取、字典訓練和特征量化3個階段。傳統BoV模型的字典訓練是采用K-Means聚類算法。為提高傳統基于K-Means的BoV模型描述影像特征的精度。Zhong等[17]提出球形K-Means聚類算法(Spherical K-Means)來減弱局部特征高緯度和稀疏性對K-Means聚類效果的影響。Bolovinou等[18]進一步驗證了該方法生成的聚類詞典在表達能力上得到增強。Philbin[19]提出了近似K-Means(Approximate K-Means，AKM)，并將其應用于目標區域檢索。Wang等[20]提出了快速近似K-Means聚類算法(Fast Approximate K-Means，F-AKM)用于有效識別類簇之間交界處的數據點，減少了每輪迭代的計算量，進一步加快了聚類收斂的塑封，提高了生成視覺詞典的效率。此外，為提高高維直方圖相似性度量的有效性，Wu等[21]提出了一種基于直方圖相交核(Histogram Intersection Kernel，HIK)[22]的K-Means聚類方法生成視覺詞典，并在目標識別實驗中驗證了該視覺詞典的良好性能。文獻[23]主要針對視覺詞匯表的改進進行了研究，并對近似K-Means和分層K-Means兩種方法進行了對比分析。

上述方法僅通過改進K-Means聚類來提升BoV模型在字典訓練的精度和效率，且沒有考慮到視覺詞匯空間下視覺單詞的分布和密度因素，得到的視覺字典無法很好地表達影像中的視覺單詞，造成較大的量化誤差。FSFDP聚類能夠通過查找密度峰值確定聚類中心，不僅有效地保證規則分布點簇的完整性，而且與K-Means聚類算法相比，FSFDP算法有聚類結果穩定、算法效率高等優點。本文將基于FSFDP聚類算法改進BoV模型，以期提高字典訓練的精度和改進BoV模型的影像特征量化方法。

2 基于FSFDP-BoV模型的遙感影像檢索

2.1 FSFDP聚類

FSFDP聚類方法是基于局部密度分布判別各個點類別的方法，該算法假設聚類中心由一些局部密度比較低的點圍繞，并且這些點距離其他高局部密度的點的距離都較遠，以保證聚類中心之間不屬于同一點集。找到聚類中心后，通過查找每個點臨近的高密度點來判斷該點的類別，以保證算法對呈規律分布的點群分類后的完整性。FSFDP算法的主要步驟如下：

(1)計算局部密度ρ。點i的局部密度為到點i的距離小于截斷距離dc的點的個數。

其中，若x<0，則χ(x)<0;若x>0，則χ(x)=1。

(2)計算δ。δ是指點i到比自身局部密度大的點的最小距離。如果點i已經是局部密度最大的，則δ賦值為點i到距自身最遠的點的距離。即:

(3)尋找聚類中心。由于成為聚類中心的點需要ρ和δ都優于其他點，也就是Density Peaks。本文用作為選取聚類中心的標準。對所有點按ρ*δ由大到小排序，前K個點作為聚類中心，其中K為聚類中心個數。

(4)確定各個點的類別。聚類中心選好后，每個點屬于距其最近的且比自身密度高的點所在的類別，直至所有點都能劃歸到某一個類別。

與K-Means相比，FSFDP算法有如下優點：1)靈活性:算法可根據ρ*δ的分布決定聚類中心個數K。2)穩定性:在相同數據源和參數的條件下，聚類結果完全一致，不會出現多次聚類得到不同的結果的情況。3)高效性：聚類流程只需一次即可完成，不需要重復迭代。4)完整性:結果中呈規則分布的點群能劃分到同一類別，保證分類精度。

2.2 FSFDP-BoV模型

基于FSFDP聚類算法提出FSFDP-BoV遙感影像檢索模型，利用FSFDP算法搜索密度峰值找到聚類中心并訓練字典，在BoV模型的特征量化上根據局部密度逐點歸類。該方法不僅在BoV模型生成字典的過程中充分考慮了點群密度分布情況，保證聚類中心是高密度的點，而且在BoV模型特征量化的過程中利用局部密度歸類量化生成直方圖。 FSFDP-BoV模型具體流程如圖1。

圖1 FSFDP-BoV模型

Fig.1 The FSFDP-BoV model

(1)局部特征提取。提取訓練樣本和候選樣本影像的SIFT特征作為BoV模型的局部特征。每張影像得到n個128維SIFT向量，其中n為SIFT點數目，向量組成n*128的矩陣稱為樣本的特征。

(2)基于FSFDP聚類算法構建BoV字典。分別計算每個特征點的ρ和δ，并對所有特征點按ρ*δ從大到小排序，取前K個特征點作為聚類中心(K為聚類個數)，即字典中的基礎詞匯。

(3)生成統計直方圖。生成待檢索影像和候選樣本庫中的每張影像的統計直方圖。經典的基于K-Means的BoV模型是利用歐氏距離度量測試樣本的特征向量和字典中基礎詞匯(聚類中心)之間相似度，而FSFDP-BoV模型是用特征向量的局部密度進行度量。首先將測試樣本的特征向量置于訓練樣本的向量集空間中，然后計算特征向量的局部密度，找最近并且比自身密度高的訓練樣本特征，若該訓練樣本不是聚類中心，則繼續找比該訓練樣本最近的且比自身密度高的特征，直到找到聚類中心。最后統計每個樣本基礎詞匯出現的次數，得到統計直方圖并進行歸一化，得到的向量即為每幅影像的FSFDP-BoV模型特征向量。

(4)相似度對比。計算待檢索影像特征向量與候選影像庫的特征向量的余弦相似度，通過測量兩個向量內積空間的夾角的余弦值來度量其間的相似性。0°角的余弦值是1，而其他任何角度的余弦值都不大于1，并且其最小值是-1，由于向量直方圖中數值都不小于0，故實際最小值為0。方法如下(其中H1、H2為兩個直方圖向量)：

最后據相似度大小對候選影像排序并輸出結果。

3 實驗與結果

3.1 實驗數據

本實驗的數據來源于USGS的UCMerced_LandUse數據中的10類典型地物樣本，每類各100張影像，影像大小為256*256，分辨率為0.3048 m。樣本示例如圖2所示。

圖2 樣本示例

Fig.2 Illustration of the samples

(1)所有10類樣本作為候選樣本庫A=(A1,A2,…,A10)，其中A1有100張影像。候選樣本庫共有1 000張影像。

(2)從中隨機抽取的10張影像的集合為Bi，10類Bi構成訓練樣本B=(B1,B2,…,B10)。訓練樣本B共有100張影像。

(3)待檢索影像集C=(C1,C2,…,C10)，其中C1是從候選樣本庫中隨機抽取的10張影像，待檢索影像C共有100張影像。

實驗首先用訓練樣本B訓練BoV模型的字典，通過字典量化待檢索影像C和候選樣本庫A的特征向量；然后計算待檢索影像C與候選樣本庫A的相似度并排序；最后統計檢索影像集C中所有影像檢索結果的準確率和召回率。

3.2 參數選擇

(1)截斷距離dc的選取。最佳dc應使得特征集合中平均每個點的鄰居數為所有點數目的1%～2%。首先取一個隨機值d，統計所有點的鄰居數之和，除以點的數目得到平均每個點的鄰居數，再除以所有點的數目。如果結果小于1%，則擴大d的值，如果結果大于2%，則減小d的值，當結果處于1%～2%的范圍內時，取d作為截斷距離。

(2)聚類個數K的選取。聚類中心應是ρ和δ都比較大的點。為確定聚類個數K，需通過分析經過排序的ρ*δ曲線，找出曲線的拐點作為K的值。步驟如下：1)統計每個點的ρ和δ并計算ρ*δ。2)對所有點按ρ*δ值從大到小的順序排序。3)根據ρ*δ值生成二維線性圖表(圖3)，其中縱坐標為ρ*δ，橫坐標為點的序號。4)根據特征點ρ*δ的分布，找出ρ*δ值與大部分點ρ*δ值相差較大的點集作為聚類中心。如圖3，第一個點和第二個點之間ρ*δ間隔最大(由于原始點數量過大，將原始ρ*δ線形圖按500間隔采樣，即每個點代表500個點)，即前500個點的ρ*δ值與后面的點差距較大，故聚類中心數目K應取500。

圖3 選取最佳K值

Fig.3 The best choice ofKvalue

3.3 實驗結果

用K-Means聚類的經典BoV模型作對比實驗。圖4為10類地物的待檢測樣本召回率的平均值,由此得到FSFDP-BoV模型和經典K-Means-BoV模型的準確率-召回率對比圖。在遙感影像檢索中FSFDP-BoV模型的準確率整體上要比經典BoV模型高，尤其是在召回率為10%的情況下更為明顯。

圖4 總體結果

Fig.4 The overall result

表1為10類地物在FSFDP-BoV模型和經典K-Means-BoV模型檢索結果的對比。可以看出，基于FSFDP-BoV模型在很多類別中檢索精度均強于經典BoV模型，尤其是高速公路、森林、中型住宅區、天橋，檢索結果優勢較為明顯。在高速公路類別，當召回率為10%時，FSFDP-BoV模型的準確率要相對經典BoV模型高。中型住宅區、森林、天橋類別中，相同召回率的條件下，FSFDP-BoV模型的檢索結果準確率優于經典BoV模型。

表1 各類別準確率-召回率

Table 1 Accuracy-recall of each category

召回率類別 10.0% 20.0% 30.0% 40.0% 50.0% 60.0%70.0%80.0%90.0% 農業用地建筑物灌木叢森林高速公路港口中型住宅區天橋停車場機場跑道FSFDPK-means100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0% 98.4%87.5%93.3%45.2%16.0%5.9%5.8%FSFDPK-means20.8%15.9%19.2%15.5%16.4%15.2%18.0%14.3%16.8%12.3%15.3%12.1%14.9%10.7%13.8%9.2%10.9% 8.0%FSFDPK-means100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%98.0%98.4%98.4%98.6%98.6%92.0%97.6%64.7%95.7%FSFDPK-means100.0% 52.6%100.0% 64.5%88.2%55.6%66.7%45.5%58.1%46.3%50.0%31.1%31.5%26.6%26.1%16.6%16.0%10.7%FSFDPK-means90.9%20.0%19.6%18.0%21.1%16.5%22.1%11.2%21.9%10.4%18.8% 8.9%17.5%8.4%16.0%7.9%11.3% 7.0%FSFDPK-means100.0%100.0%100.0% 54.1%71.4%47.6%28.4%36.4%14.7%25.6%12.8%14.7%10.9%11.8%10.8%8.9%9.6%6.5%FSFDPK-means76.9%45.5%52.6%29.4%38.5%25.2%26.7%27.2%24.5%24.2%21.9%23.3%18.6%21.4%16.5%21.4%12.7%17.2%FSFDPK-means45.5%13.7%43.5%14.6%46.2%13.7%41.7%12.6%37.9%11.7%32.6%11.3%29.5%11.3%20.3%8.9%18.5% 7.8%FSFDPK-means30.3%21.7%26.0%22.0%18.8%19.1%12.8%14.7%10.6%12.3%9.1%8.9%6.6%6.6%6.5%5.9%6.0%5.5%FSFDPK-means27.8%17.2%14.6%14.1%18.2%11.0%21.6%10.0%24.3%10.4%23.5% 9.0%23.0%8.4%15.9%7.4%9.4%6.1%

4 結語

本文基于FSFDP聚類算法對經典BoV模型進行了改進，提出FSFDP-BoV模型并應用于遙感影像檢索。實驗表明，該方法在遙感影像的分類檢索中能取得不錯的檢索精度，尤其在農業用地、灌木叢、港口類別中效果較好。FSFDP-BoV模型檢索精度普遍優于經典BoV模型，特別是在高速公路、森林、中型住宅區、天橋類別下，FSFDP-BoV模型的檢索精度具有明顯優勢。

[1] SMEULDERS A W M,WORRING M,SANTINI S,et al.Content-based image retrieval at the end of the early years[J].Pattern Analysis and Machine Intelligence,IEEE Transactions on,2000,22(12):1349-1380.

[2] HIRATA K,KATO T.Query by Visual Example,Content Based Image Retrieval[C].Advances in Database Technology,EDBT 92,Vienna,1992

[3] 程起敏.基于內容的遙感影像庫檢索關鍵技術研究[D].北京:中國科學院研究生院,2004

[4] 李德仁,寧曉剛.一種新的基于內容遙感影像檢索的圖像分塊策略[J].武漢大學學報(信息科學版),2006,31(8):659-663.

[5] SIVIC J,ZISSERMAN A.Video google:A text retrieval approach to object matching in videos[J].ICCV,2003(2):1470-1477.

[6] 周文罡.基于局部特征的視覺上下文分析及其應用[D].合肥：中國科學技術大學，2011.

[7] 李遠寧,劉汀,蔣樹強,等.基于“bag of words”的視頻匹配方法[J].通信學報,2007(12):147-151.

[8] ZHANG Y M,JIA Z Y,CHEN T.Image retrieval with geometry-preserving visual phrases[A].CVPR,2011.809-816.

[9] PHILBIN J,CHUM O,ISARD M,et al.Object retrieval with large vocabularies and fast spatial matching[A].CVPR,2007.

[10] 楊進,劉建波,戴芹.一種改進包模型的遙感影像檢索方法[J].武漢大學學報(信息科學版),2014(9):1109-1113.

[11] WU J,CUI Z,ZHAO P,et al.Visual vocabulary tree construction research using adaptive Fuzzy K-Means Clustering[J].Advanced Science Letters,2012,11(1):258-262.

[12] RODRIGUEZ A,LAIO A.Clustering by fast search and find of density peaks[J].Science, 2014,344(6191):1492-1496.

[13] 柴玉梅,王宇.基于TFIDF的文本特征選擇方法[J].微計算機信息,2006,24:24-26.

[14] LOWE D G.Distinctive image features from scale-invariant key points[J].International Journal of Computer Vision,2004,60(2):91-110.

[15] MOLINIER M,LAAKSONEN J,HAME T.Detecting man-made structures and changes in satellite imagery with a content-based information retrieval system built on self-organizing maps[J].Transaction on Geosciences and Remote Sensing,2007,45(4):861-874.

[16] 李士進,仇建斌,於慧.基于視覺單詞選擇的高分辨率遙感影像飛機目標檢測[J].數據采集與處理,2014,29(1):60-65.

[17] ZHONG S.Efficient online spherical K-means clustering[A].Proc.of the 2005 IEEE International Joint Conference on Neural Networks[C].Montreal,Canada,2005.3180-3185.

[18] BOLOVINOU A,PRATIKAKIS I, PERANTONIS S.Bag of spatio-visual words for context inference in scene classification[J]. Pattern Recognition,2013,46(3):1039-1053.

[19] PHILBIN J.Scalable Object Retrieval in Very Large Image Collections[D].University of Oxford,2010.

[20] WANG J,WANG J,KE Q,et al.Fast approximate K-means via cluster closures[A].Multimedia Data Mining and Analytics[M].Springer International Publishing,2015.373-395.

[21] WU J,REHG J M.Beyond the Euclidean distance:Creating effective visual codebooks using the histogram intersection kernel[J].Computer Vision IEEE International Conference on,2009,30(2):630-637.

[22] ODONE F,BARLA A,VERRI A.Building kernels from binary strings for image matching[J].Image Processing,IEEE Transactions on,2005,14(2):169-180.

[23] ZHENG Y T,ZHAO M,NEO S Y,et al.Visual synset:Towards a higher-level visual representation[A].Computer Vision and Pattern Recognition,2008[C].CVPR 2008,2008.1-8.

Remote Sensing Image Retrieval Research Based on FSFDP-BoV Model

SHEN Chen,QI Kun-lun,LIU Wen-xuan,WU Hua-yi

(State Key Laboratory of Information Engineering in Surveying,Mapping and Remote Sensing,Wuhan University,Wuhan 430079,China)

In order to improve the accuracy of retrieval of high-resolution remote sensing images,this paper proposes an improved Bag of Visual Word (BoV) model based on clustering by Fast Search and Find of Density Peaks (FSFDP).Taking the advantages that the result of clustering by FSFDP is highly accurate and that the clustering parameters are easy to choose,this model enhances the stability and reliability of feature quantification in BoV.

remote sensing images;retrieval;Bag of Visual words;density peaks clustering

2015-06-10；

2015-10-14

國家973計劃項目(2012CB719906)

沈忱(1991-)，男，碩士，主要從事高分辨率遙感影像檢索研究。E-mail：ShenChen0425@whu.edu.cn

10.3969/j.issn.1672-0504.2016.01.011

TP79

A

1672-0504(2016)01-0055-05