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

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

一、引 言

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

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

二、Hilbert R樹索引

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

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

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

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

三、K均值聚類算法改進(jìn)

1.K均值聚類算法

考慮到資源三號(hào)立體影像之間的邏輯關(guān)系密切，采用空間聚類算法對(duì)其空間索引進(jìn)行改進(jìn)。

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

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

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

聚類結(jié)果的優(yōu)劣，用均方差準(zhǔn)則函數(shù)來(lái)度量

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

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

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

1）聚類個(gè)數(shù)k需要事先給出。聚類個(gè)數(shù)k是作為K均值聚類算法的輸入?yún)?shù)的，k的取值直接影響到聚類的結(jié)果。在實(shí)際應(yīng)用中，k值往往是不確定的，這對(duì)K均值聚類的應(yīng)用造成了很大的局限性。

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

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

2.聚類算法改進(jìn)

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

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

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

1）設(shè)Center為聚類點(diǎn)集，利用歐氏距離公式計(jì)算各點(diǎn)之間的距離，形成距離矩陣MTX。

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

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

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

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

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

四、改進(jìn)的Hilbert R樹索引

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

葉子結(jié)點(diǎn):（Count，Level，MX，＜ObjIDi，Obj_Bouderi，Obj_Pathi， Obj_Hilberti＞，…）i=1，…，Count；

中間結(jié)點(diǎn)及根結(jié)點(diǎn):（Count，Level，MX，＜CIDj，C_MBRj，C_Pathj，C_Hilbertj＞ ，… ）j=1，…，Count.

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

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

1）獲取葉子結(jié)點(diǎn)的數(shù)據(jù)項(xiàng)。記錄資源三號(hào)影像數(shù)據(jù)所有影像的四角坐標(biāo)，并以四角坐標(biāo)構(gòu)成四邊形，然后記錄四邊形的幾何中心形成集合Center。

2）利用改進(jìn)的K均值聚類算法對(duì)Center進(jìn)行聚類。

3）對(duì)得到的各類分別計(jì)算其類內(nèi)包含的空間點(diǎn)所對(duì)應(yīng)的Hilbert碼，并在每一類中將空間點(diǎn)所對(duì)應(yīng)的影像按各空間點(diǎn)的Hilbert碼值的大小升序排列。

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

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

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

五、試驗(yàn)分析

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

圖1 K均值聚類算法改進(jìn)前后試驗(yàn)結(jié)果對(duì)比圖

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

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

下面仍然采用模擬的方式，以空間四邊形代替影像進(jìn)行試驗(yàn)，以500到3500個(gè)四邊形為研究對(duì)象建立空間索引，對(duì)比改進(jìn)前后的Hilbert R樹索引的構(gòu)建時(shí)間，分析結(jié)果如圖2所示。

圖2 改進(jìn)前后的Hilbert R樹索引的構(gòu)建時(shí)間比較

從圖2中可以看出，改進(jìn)后的Hilbert R樹構(gòu)建時(shí)間大于傳統(tǒng)的Hilbert R樹構(gòu)建的時(shí)間，原因在于改進(jìn)的Hilbert R樹的聚類過程增加了索引的構(gòu)建時(shí)間。但是通過前文分析，若對(duì)分布不均勻的空間對(duì)象建立索引時(shí)，傳統(tǒng)的Hilbert R樹索引會(huì)因?yàn)榭臻g的空白地區(qū)造成結(jié)點(diǎn)面積過大，并產(chǎn)生大量的重疊和死空間，這時(shí)索引的構(gòu)建時(shí)間會(huì)增加。

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

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

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

六、結(jié)束語(yǔ)

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

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

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

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

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

［4］ 周勇.改進(jìn)的層次網(wǎng)格空間索引技術(shù)研究與實(shí)現(xiàn)［D］.福州:福州大學(xué)，2004.

［5］ 盧廷軍，黃明.海量柵格數(shù)據(jù)空間索引與存儲(chǔ)的研究［J］.測(cè)繪通報(bào)，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］ 曾紹琴，李光強(qiáng)，廖志強(qiáng).空間聚類方法的分類［J］.測(cè)繪科學(xué)，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］ 王寶祥.基于改進(jìn)聚類的Hilbert R樹空間索引算法研究［D］.鄭州:河南大學(xué)，2011.

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

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