顏 靜，王衛(wèi)京，范 磊，王文凱，肖麗嬌

（北京吉威時代軟件股份有限公司，北京 100043）

一、引 言

2012年1 月9 日，資源三號衛(wèi)星發(fā)射升空，它集測繪和資源調查功能于一體，將為國土資源調查與監(jiān)測、防災減災、農林水利、生態(tài)環(huán)境、城市規(guī)劃與建設、交通和國防建設等領域提供有效的服務［1］。資源三號衛(wèi)星影像的高效檢索是其應用的關鍵基礎。資源三號衛(wèi)星拍攝的是立體測圖［2］實際生產中使用的立體影像，影像之間的邏輯關系密切。而傳統(tǒng)的影像數(shù)據(jù)管理服務主要實現(xiàn)對分景影像的存儲管理服務，數(shù)據(jù)間不存在邏輯關系。采用傳統(tǒng)的影像存儲管理方式，不能高效地從海量的資源三號影像數(shù)據(jù)中檢索到可用于立體觀測的立體影像對。

因此，本文從空間索引入手，探討立體影像高效檢索的方案，同時對K均值聚類進行改進，并將改進后的聚類算法應用到Hilbert R樹索引。通過試驗分析，改進后的Hilbert R樹索引更適合資源三號衛(wèi)星影像的檢索。

二、Hilbert R樹索引

空間索引就是指在存儲空間數(shù)據(jù)時，依據(jù)空間對象的位置、形狀或空間對象之間的某種空間關系，按照一定的順序排列數(shù)據(jù)的一種數(shù)據(jù)結構?？臻g索引包含空間對象的概要信息（如對象的標識、外接矩形）及指向空間對象的指針。它作為一種輔助性的空間數(shù)據(jù)結構，介于空間操作算法和空間對象之間。在進行空間操作時借助空間索引，大量與該操作無關的空間對象被排除，從而提高空間操作的效率［3］。目前，常用的空間索引有網格索引［4］、四叉樹索引和 R 樹索引［5］等。Hilbert R 樹［6］索引是R樹索引的一個優(yōu)良變種，由于其具有良好的空間聚集特性，因此本文研究對Hilbert R樹的優(yōu)化。

1993 年Kamel和Faloutsos提出Hilbert R樹的概念。Hilbert R樹的建立思想是先將空間數(shù)據(jù)按照其最小外接矩形（MBR）的中心的Hilbert碼值進行排序，然后按R樹的葉子結點的容納空間對象的數(shù)目數(shù)將排列好的數(shù)據(jù)依次放入各個葉子結點中。當所有空間對象都分到葉子結點中時，再按照各葉子結點產生的順序組織中間結點，進而以自底向上的順序生成R樹。

由于Hilbert R樹根據(jù)其Hilbert編碼序列建立的葉子結點中所存空間對象在物理存儲上也是相鄰的，因此在映射過程中保存了大部分的空間位置關系信息，從而實現(xiàn)了對空間數(shù)據(jù)的有效組織。利用Hilbert R樹進行相關的空間查詢操作所消耗的計算機I/O讀取次數(shù)和磁盤尋道時間都較少。Hilbert R樹與R樹的一點不同是它采用了批處理的方式構建索引樹，使葉子結點的空間利用率幾乎達到了100%，較大程度上降低了樹的高度，從而大大提高了空間數(shù)據(jù)的檢索效率。

但是Hilbert R樹也具有一些缺點，由于它機械地按接近百分之百的空間利用率生成各結點，會造成結點面積過大，并產生大量的重疊和死空間，尤其在空間對象分布不均勻時，其結點間的重疊更為嚴重，從而極大地影響了其檢索效率。本文探討一種改進的Hilbert R樹索引用于資源三號影像數(shù)據(jù)庫的建設。

三、K均值聚類算法改進

1.K均值聚類算法

考慮到資源三號立體影像之間的邏輯關系密切，采用空間聚類算法對其空間索引進行改進。

空間聚類研究的對象是空間對象，它根據(jù)空間距離的大小或其他空間特征的差別，將空間對象聚集成若干個空間簇，并使得同種空間簇中的空間對象具有最大的相似性、不同空間簇中的空間對象差別較大［7］。目前最常用的空間聚類算法是K均值（K-means）聚類算法。K均值聚類算法是J.B.Mac Queen在1967年提出的，它具有算法簡單且收斂速度快的特點［8］。

K均值聚類算法在對空間點聚類時，通常以空間點的歐氏距離為聚類依據(jù)。歐氏距離的定義如下

式中，D表示兩點n維點對象p1（x1，x2，…，xn）、p2（y1，y2，…，yn）的歐氏距離；n指點對象的維數(shù)。

聚類結果的優(yōu)劣，用均方差準則函數(shù)來度量

式中，k表示聚類的個數(shù)；Ci代表第i類；p為Ci數(shù)據(jù)集中的一個數(shù)據(jù)點；mi為Ci的平均值。E值越小，表示聚類效果越好。

K均值聚類算法的復雜度為O（nkt），其中，n代表目標點的個數(shù)，k代表聚類的個數(shù)，t為迭代運算的次數(shù)。通常情況下，k?n且t?n。因此，K均值聚類算法的主要優(yōu)點是算法簡單、高效，時間復雜性接近線性，特別適合用于處理大規(guī)模的數(shù)據(jù)。

K均值聚類算法在應用中也存在一些局限性［9］:

1）聚類個數(shù)k需要事先給出。聚類個數(shù)k是作為K均值聚類算法的輸入參數(shù)的，k的取值直接影響到聚類的結果。在實際應用中，k值往往是不確定的，這對K均值聚類的應用造成了很大的局限性。

2）聚類中心選取的隨機性。由于K均值聚類算法的初始聚類中心是隨機選取的，雖然經過多次迭代，但是，最初選取的中心點還是會顯著地影響聚類結果。不合理的初始聚類中心的選取不僅造成聚類結果差，還會增加迭代次數(shù)。

3）K均值聚類對噪聲和孤立點［10］敏感。K均值算法在迭代過程中，將每個聚類中的數(shù)據(jù)點的距離的平均值作為新的聚類中心，少量遠離數(shù)據(jù)點密集區(qū)的孤立點和噪聲點就會引起新聚類中心的較大偏離，從而降低聚類精度。

2.聚類算法改進

從上文可以得出，在K均值聚類算法中，初始的聚類中心對整個聚類過程影像較大，為了減少隨機選取初始聚類中心而引起的誤差，本文提出對聚類的個數(shù)確定及初始聚類中心選取的改進算法。

一個好的聚類中心應該能很好地代表它所在的類，并且在一定的范圍內覆蓋的空間數(shù)據(jù)對象應該是最多的，因此聚類中心應該是在空間對象分布密集的地方。根據(jù)這個思路，可以根據(jù)空間密度來確定聚類中心。文獻［11］通過密度參數(shù)來衡量空間點所處空間的空間點的疏密程度，密度參數(shù)計算方法為

某點的密度參數(shù)越大，說明該點所處的區(qū)域的點越密集，則該點作為聚類中心的可能性越大，因此本文通過密度參數(shù)來尋找聚類的初始中心。改進的K均值聚類算法具體步驟如下:

1）設Center為聚類點集，利用歐氏距離公式計算各點之間的距離，形成距離矩陣MTX。

2）在MTX的基礎上，利用式（4）計算所有聚類對象的平均距離MeanDist。

3）利用式（3）計算所有對象的密度參數(shù)，組成集合D。

4）找到D中的最大值作為聚類中心Ci，同時從D中剔除與聚類中心Ci距離小于MeanDist的值。

5）若D中還有非聚類中心的值，則返回步驟4）。

6）以D為初始聚類中心，調用傳統(tǒng)的K均值聚類算法得出Center的聚類結果。

四、改進的Hilbert R樹索引

資源三號影像是面對象，而K均值聚類算法是針對點對象的算法。因此，本文在利用K均值聚類算法時，需要將面對象轉化成點對象，可以采用影像邊框多邊形的幾何中心作為聚類對象。在R樹的中間結點中，以其子結點的MBR中心為聚類對象。因此改進的Hilbert R樹的結點的數(shù)據(jù)結構如下:

葉子結點:（Count，Level，MX，＜ObjIDi，Obj_Bouderi，Obj_Pathi， Obj_Hilberti＞，…）i=1，…，Count；

中間結點及根結點:（Count，Level，MX，＜CIDj，C_MBRj，C_Pathj，C_Hilbertj＞ ，… ）j=1，…，Count.

其中，Count表示該結點包含的索引項個數(shù)；Level標志該結點在索引樹所處的層級；MX為結點能容納的數(shù)據(jù)項的個數(shù)；＜ObjIDi，Obj_Bouderi，Obj_Pathi，Obj_H1Ci＞代表影像的數(shù)據(jù)項；i取值從1到m（m為葉子結點的總數(shù)）；ObjIDi表示第i張影像的編號；Obj_Bouderi表示第i張影像的邊界四邊形；Obj_Pathi為指向影像存儲的位置的指針；Obj_Hilberti表示第i張影像幾何中心的Hilbert編碼；＜CIDj，C_MBRj，C_Pathj，C_Hilbertj＞ 表示中間結點的索引項，CIDj是本層第j個索引對象的標志，C_MBRj是索引項的最小外接矩形，C_Pathj為指向其子結點的指針，C_Hilbertj是該結點的所有子結點中最大的Hilbert碼。

綜上，基于改進空間聚類算法的Hilbert R樹算法如下:

1）獲取葉子結點的數(shù)據(jù)項。記錄資源三號影像數(shù)據(jù)所有影像的四角坐標，并以四角坐標構成四邊形，然后記錄四邊形的幾何中心形成集合Center。

2）利用改進的K均值聚類算法對Center進行聚類。

3）對得到的各類分別計算其類內包含的空間點所對應的Hilbert碼，并在每一類中將空間點所對應的影像按各空間點的Hilbert碼值的大小升序排列。

4）計算各類聚類中心的Hilbert碼，并將各類按照這些Hilbert碼值進行排序。

5）按步驟4）得到的每類的處理順序處理每類對象，對聚類內空間對象按其Hilbert碼值從小到大的順序分別構建葉子結點。若某聚類內的空間對象數(shù)小于或者等于結點的最大容量MX，則本聚類內的所有空間對象構成一個葉子結點。若聚類內的空間對象數(shù)大于MX，則對該聚類內所有空間對象按其Hilbert碼值從小到大的順序，分別生成多個含有MX個空間對象的分組。

6）對于所有葉子結點，按其生成的順序自下而上構建各層中間結點和根結點，中間結點和根結點存放其子結點Hilbert碼的最大值。如此即形成了一棵索引樹。

五、試驗分析

試驗首先對改進的聚類算法的有效性進行驗證。采用102個資源三號影像的邊框模擬102張資源三號衛(wèi)星影像，分別應用改進前后的聚類方式聚類，聚類結果如圖1所示。

圖1 K均值聚類算法改進前后試驗結果對比圖

該試驗采用資源三號衛(wèi)星影像的邊框所形成的四邊形代替影像進行處理，所選的102個四邊形樣本空間分布大致均勻。圖1展示的均值聚類改進前后試驗結果對中，圖1（a）為K均值聚類算法改進前的聚類結果，圖1（b）為K均值聚類算法改進后的聚類結果。圖1（b）采用改進的聚類算法得到共有3個初始聚類中心。為了與之對比，在待聚類對象中隨機取3個初始聚類中心進行聚類，得到圖1（a）聚類結果。

圖1中，圖1（a）的聚類結果均方差Ea=0.180，圖1（b）的聚類結果均方差為Eb=0.153。說明圖1（b）的聚類結果相對較好。另外，從對比圖1（a）、圖1（b）可以看出，利用改進前和改進后的聚類算法，立體影像都被劃分到了同一類。這說明K均值聚類能夠很好地表現(xiàn)立體影像空間關系特征。圖1（a）中第1類和第3類中有的多邊形的重疊度較高，說明該方式沒有很好地體現(xiàn)聚類讓不同類之間的差別盡可能大的原則。雖然樣本的分布大致均勻，但這種采用隨機選初始點的分類方式，每類中的樣本數(shù)量差別較大。相比之下，圖1（b）中的類與類之間的重疊較少，每類中含有的樣本數(shù)目均衡，很好地表現(xiàn)了空間對象之間的位置關系，說明了該算法改進的有效性。

下面仍然采用模擬的方式，以空間四邊形代替影像進行試驗，以500到3500個四邊形為研究對象建立空間索引，對比改進前后的Hilbert R樹索引的構建時間，分析結果如圖2所示。

圖2 改進前后的Hilbert R樹索引的構建時間比較

從圖2中可以看出，改進后的Hilbert R樹構建時間大于傳統(tǒng)的Hilbert R樹構建的時間，原因在于改進的Hilbert R樹的聚類過程增加了索引的構建時間。但是通過前文分析，若對分布不均勻的空間對象建立索引時，傳統(tǒng)的Hilbert R樹索引會因為空間的空白地區(qū)造成結點面積過大，并產生大量的重疊和死空間，這時索引的構建時間會增加。

在進行空間索引性能的分析時，查詢操作時的磁盤I/O操作次數(shù)是重要的衡量指標。本文分析算法改進前后兩種索引的查詢操作的磁盤I/O操作次數(shù)，結果如圖3所示。

圖3 空間索引改進前后查詢時磁盤I/O訪問次數(shù)比較

從圖3中可以看出，空間索引改進后，查詢時的磁盤I/O訪問次數(shù)較低，尤其是在查詢較多的立體影像時，這種差別就更加明顯。這是由于在查詢立體影像，立體影像都在索引樹的同一個結點，空間相鄰的區(qū)域聚到了相同或鄰近的結點上，就減少了訪問樹的結點的個數(shù)，從而降低了I/O操作次數(shù)，而改進前的索引不具有這種特性。

六、結束語

本文研究了適用于資源三號衛(wèi)星立體測圖影像檢索的空間索引技術。為了體現(xiàn)立體影像之間的空間聚集性，首先分析了能較好體現(xiàn)影像空間聚集特性的Hilbert R樹索引及其優(yōu)缺點；然后引入了空間聚類算法，對常用的K均值聚類算法改進后，將其應用于Hilbert R樹的構建。通過試驗分析，改進后的空間索引算法更適合資源三號衛(wèi)星立體測圖影像的檢索。

目前，資源三號衛(wèi)星影像庫尚在建設之中，本文所提出的空間索引算法有待利用大規(guī)模的影像數(shù)據(jù)進一步加以驗證。

［1］ 國家測繪局衛(wèi)星測繪應用中心.航天五院ZY-3衛(wèi)星介紹［EB/OL］.［2009-12-17］.http:∥sasmac.sbsm.gov.cn/article∥wxzh/200912/20091200059259.shtml.

［2］ 張海濤，賈光軍，虞欣.基于GeoEye_1衛(wèi)星影像的立體測圖技術研究［J］.測繪通報，2010（12）:43-46.

［3］ 黃飛鵬.海量遙感影像管理系統(tǒng)的設計與實現(xiàn)［D］.上海:華東師范大學，2011.

［4］ 周勇.改進的層次網格空間索引技術研究與實現(xiàn)［D］.福州:福州大學，2004.

［5］ 盧廷軍，黃明.海量柵格數(shù)據(jù)空間索引與存儲的研究［J］.測繪通報，2010（10）:24-26.

［6］ KAMEL I，F(xiàn)ALOUTSOS C.Hilbert R-Tree an Improved R-Tree Using Fractals［R］.［S.l.］:National Science Foundation Engineering Research Center Program，1993.

［7］ 曾紹琴，李光強，廖志強.空間聚類方法的分類［J］.測繪科學，2012，37（5）:103-106.

［8］ HARTIGAN J A，WONG M A.Algorithm AS 136:A KMeans Clustering Algorithm［J］.Journal of the Royal Statistical Society:Series C（Applied Statistics），1979，28（1）:100-108.

［9］ 王寶祥.基于改進聚類的Hilbert R樹空間索引算法研究［D］.鄭州:河南大學，2011.

［10］ TAN P N，STEINBACH M，KUMAR V.數(shù)據(jù)挖掘導論［M］.范明，范宏建，譯.北京:人民郵電出版社，2006:308-322.

［11］ 黃敏，何中市，邢欣來，等.一種新的k-means聚類中心選取算法［J］.計算機工程與應用，2011，47（35）:132-134.