适用于资源三号立体影像的空间索引技术研究

颜 静，王卫京，范 磊，王文凯，肖丽娇

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

一、引 言

2012年1 月9 日，资源三号卫星发射升空，它集测绘和资源调查功能于一体，将为国土资源调查与监测、防灾减灾、农林水利、生态环境、城市规划与建设、交通和国防建设等领域提供有效的服务［1］。资源三号卫星影像的高效检索是其应用的关键基础。资源三号卫星拍摄的是立体测图［2］实际生产中使用的立体影像，影像之间的逻辑关系密切。而传统的影像数据管理服务主要实现对分景影像的存储管理服务，数据间不存在逻辑关系。采用传统的影像存储管理方式，不能高效地从海量的资源三号影像数据中检索到可用于立体观测的立体影像对。

因此，本文从空间索引入手，探讨立体影像高效检索的方案，同时对K均值聚类进行改进，并将改进后的聚类算法应用到Hilbert R树索引。通过试验分析，改进后的Hilbert R树索引更适合资源三号卫星影像的检索。

二、Hilbert R树索引

空间索引就是指在存储空间数据时，依据空间对象的位置、形状或空间对象之间的某种空间关系，按照一定的顺序排列数据的一种数据结构。空间索引包含空间对象的概要信息（如对象的标识、外接矩形）及指向空间对象的指针。它作为一种辅助性的空间数据结构，介于空间操作算法和空间对象之间。在进行空间操作时借助空间索引，大量与该操作无关的空间对象被排除，从而提高空间操作的效率［3］。目前，常用的空间索引有网格索引［4］、四叉树索引和 R 树索引［5］等。Hilbert R 树［6］索引是R树索引的一个优良变种，由于其具有良好的空间聚集特性，因此本文研究对Hilbert R树的优化。

1993 年Kamel和Faloutsos提出Hilbert R树的概念。Hilbert R树的建立思想是先将空间数据按照其最小外接矩形（MBR）的中心的Hilbert码值进行排序，然后按R树的叶子结点的容纳空间对象的数目数将排列好的数据依次放入各个叶子结点中。当所有空间对象都分到叶子结点中时，再按照各叶子结点产生的顺序组织中间结点，进而以自底向上的顺序生成R树。

由于Hilbert R树根据其Hilbert编码序列建立的叶子结点中所存空间对象在物理存储上也是相邻的，因此在映射过程中保存了大部分的空间位置关系信息，从而实现了对空间数据的有效组织。利用Hilbert R树进行相关的空间查询操作所消耗的计算机I/O读取次数和磁盘寻道时间都较少。Hilbert R树与R树的一点不同是它采用了批处理的方式构建索引树，使叶子结点的空间利用率几乎达到了100%，较大程度上降低了树的高度，从而大大提高了空间数据的检索效率。

但是Hilbert R树也具有一些缺点，由于它机械地按接近百分之百的空间利用率生成各结点，会造成结点面积过大，并产生大量的重叠和死空间，尤其在空间对象分布不均匀时，其结点间的重叠更为严重，从而极大地影响了其检索效率。本文探讨一种改进的Hilbert R树索引用于资源三号影像数据库的建设。

三、K均值聚类算法改进

1.K均值聚类算法

考虑到资源三号立体影像之间的逻辑关系密切，采用空间聚类算法对其空间索引进行改进。

空间聚类研究的对象是空间对象，它根据空间距离的大小或其他空间特征的差别，将空间对象聚集成若干个空间簇，并使得同种空间簇中的空间对象具有最大的相似性、不同空间簇中的空间对象差别较大［7］。目前最常用的空间聚类算法是K均值（K-means）聚类算法。K均值聚类算法是J.B.Mac Queen在1967年提出的，它具有算法简单且收敛速度快的特点［8］。

K均值聚类算法在对空间点聚类时，通常以空间点的欧氏距离为聚类依据。欧氏距离的定义如下

式中，D表示两点n维点对象p1（x1，x2，…，xn）、p2（y1，y2，…，yn）的欧氏距离；n指点对象的维数。

聚类结果的优劣，用均方差准则函数来度量

式中，k表示聚类的个数；Ci代表第i类；p为Ci数据集中的一个数据点；mi为Ci的平均值。E值越小，表示聚类效果越好。

K均值聚类算法的复杂度为O（nkt），其中，n代表目标点的个数，k代表聚类的个数，t为迭代运算的次数。通常情况下，k≪n且t≪n。因此，K均值聚类算法的主要优点是算法简单、高效，时间复杂性接近线性，特别适合用于处理大规模的数据。

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

1）聚类个数k需要事先给出。聚类个数k是作为K均值聚类算法的输入参数的，k的取值直接影响到聚类的结果。在实际应用中，k值往往是不确定的，这对K均值聚类的应用造成了很大的局限性。

2）聚类中心选取的随机性。由于K均值聚类算法的初始聚类中心是随机选取的，虽然经过多次迭代，但是，最初选取的中心点还是会显著地影响聚类结果。不合理的初始聚类中心的选取不仅造成聚类结果差，还会增加迭代次数。

3）K均值聚类对噪声和孤立点［10］敏感。K均值算法在迭代过程中，将每个聚类中的数据点的距离的平均值作为新的聚类中心，少量远离数据点密集区的孤立点和噪声点就会引起新聚类中心的较大偏离，从而降低聚类精度。

2.聚类算法改进

从上文可以得出，在K均值聚类算法中，初始的聚类中心对整个聚类过程影像较大，为了减少随机选取初始聚类中心而引起的误差，本文提出对聚类的个数确定及初始聚类中心选取的改进算法。

一个好的聚类中心应该能很好地代表它所在的类，并且在一定的范围内覆盖的空间数据对象应该是最多的，因此聚类中心应该是在空间对象分布密集的地方。根据这个思路，可以根据空间密度来确定聚类中心。文献［11］通过密度参数来衡量空间点所处空间的空间点的疏密程度，密度参数计算方法为

某点的密度参数越大，说明该点所处的区域的点越密集，则该点作为聚类中心的可能性越大，因此本文通过密度参数来寻找聚类的初始中心。改进的K均值聚类算法具体步骤如下:

1）设Center为聚类点集，利用欧氏距离公式计算各点之间的距离，形成距离矩阵MTX。

2）在MTX的基础上，利用式（4）计算所有聚类对象的平均距离MeanDist。

3）利用式（3）计算所有对象的密度参数，组成集合D。

4）找到D中的最大值作为聚类中心Ci，同时从D中剔除与聚类中心Ci距离小于MeanDist的值。

5）若D中还有非聚类中心的值，则返回步骤4）。

6）以D为初始聚类中心，调用传统的K均值聚类算法得出Center的聚类结果。

四、改进的Hilbert R树索引

资源三号影像是面对象，而K均值聚类算法是针对点对象的算法。因此，本文在利用K均值聚类算法时，需要将面对象转化成点对象，可以采用影像边框多边形的几何中心作为聚类对象。在R树的中间结点中，以其子结点的MBR中心为聚类对象。因此改进的Hilbert R树的结点的数据结构如下:

叶子结点:（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表示该结点包含的索引项个数；Level标志该结点在索引树所处的层级；MX为结点能容纳的数据项的个数；＜ObjIDi，Obj_Bouderi，Obj_Pathi，Obj_H1Ci＞代表影像的数据项；i取值从1到m（m为叶子结点的总数）；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）获取叶子结点的数据项。记录资源三号影像数据所有影像的四角坐标，并以四角坐标构成四边形，然后记录四边形的几何中心形成集合Center。

2）利用改进的K均值聚类算法对Center进行聚类。

3）对得到的各类分别计算其类内包含的空间点所对应的Hilbert码，并在每一类中将空间点所对应的影像按各空间点的Hilbert码值的大小升序排列。

4）计算各类聚类中心的Hilbert码，并将各类按照这些Hilbert码值进行排序。

5）按步骤4）得到的每类的处理顺序处理每类对象，对聚类内空间对象按其Hilbert码值从小到大的顺序分别构建叶子结点。若某聚类内的空间对象数小于或者等于结点的最大容量MX，则本聚类内的所有空间对象构成一个叶子结点。若聚类内的空间对象数大于MX，则对该聚类内所有空间对象按其Hilbert码值从小到大的顺序，分别生成多个含有MX个空间对象的分组。

6）对于所有叶子结点，按其生成的顺序自下而上构建各层中间结点和根结点，中间结点和根结点存放其子结点Hilbert码的最大值。如此即形成了一棵索引树。

五、试验分析

试验首先对改进的聚类算法的有效性进行验证。采用102个资源三号影像的边框模拟102张资源三号卫星影像，分别应用改进前后的聚类方式聚类，聚类结果如图1所示。

图1 K均值聚类算法改进前后试验结果对比图

该试验采用资源三号卫星影像的边框所形成的四边形代替影像进行处理，所选的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均值聚类能够很好地表现立体影像空间关系特征。图1（a）中第1类和第3类中有的多边形的重叠度较高，说明该方式没有很好地体现聚类让不同类之间的差别尽可能大的原则。虽然样本的分布大致均匀，但这种采用随机选初始点的分类方式，每类中的样本数量差别较大。相比之下，图1（b）中的类与类之间的重叠较少，每类中含有的样本数目均衡，很好地表现了空间对象之间的位置关系，说明了该算法改进的有效性。

下面仍然采用模拟的方式，以空间四边形代替影像进行试验，以500到3500个四边形为研究对象建立空间索引，对比改进前后的Hilbert R树索引的构建时间，分析结果如图2所示。

图2 改进前后的Hilbert R树索引的构建时间比较

从图2中可以看出，改进后的Hilbert R树构建时间大于传统的Hilbert R树构建的时间，原因在于改进的Hilbert R树的聚类过程增加了索引的构建时间。但是通过前文分析，若对分布不均匀的空间对象建立索引时，传统的Hilbert R树索引会因为空间的空白地区造成结点面积过大，并产生大量的重叠和死空间，这时索引的构建时间会增加。

在进行空间索引性能的分析时，查询操作时的磁盘I/O操作次数是重要的衡量指标。本文分析算法改进前后两种索引的查询操作的磁盘I/O操作次数，结果如图3所示。

图3 空间索引改进前后查询时磁盘I/O访问次数比较

从图3中可以看出，空间索引改进后，查询时的磁盘I/O访问次数较低，尤其是在查询较多的立体影像时，这种差别就更加明显。这是由于在查询立体影像，立体影像都在索引树的同一个结点，空间相邻的区域聚到了相同或邻近的结点上，就减少了访问树的结点的个数，从而降低了I/O操作次数，而改进前的索引不具有这种特性。

六、结束语

本文研究了适用于资源三号卫星立体测图影像检索的空间索引技术。为了体现立体影像之间的空间聚集性，首先分析了能较好体现影像空间聚集特性的Hilbert R树索引及其优缺点；然后引入了空间聚类算法，对常用的K均值聚类算法改进后，将其应用于Hilbert R树的构建。通过试验分析，改进后的空间索引算法更适合资源三号卫星立体测图影像的检索。

目前，资源三号卫星影像库尚在建设之中，本文所提出的空间索引算法有待利用大规模的影像数据进一步加以验证。

［1］ 国家测绘局卫星测绘应用中心.航天五院ZY-3卫星介绍［EB/OL］.［2009-12-17］.http:∥sasmac.sbsm.gov.cn/article∥wxzh/200912/20091200059259.shtml.

［2］ 张海涛，贾光军，虞欣.基于GeoEye_1卫星影像的立体测图技术研究［J］.测绘通报，2010（12）:43-46.

［3］ 黄飞鹏.海量遥感影像管理系统的设计与实现［D］.上海:华东师范大学，2011.

［4］ 周勇.改进的层次网格空间索引技术研究与实现［D］.福州:福州大学，2004.

［5］ 卢廷军，黄明.海量栅格数据空间索引与存储的研究［J］.测绘通报，2010（10）:24-26.

［6］ KAMEL I，FALOUTSOS 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.数据挖掘导论［M］.范明，范宏建，译.北京:人民邮电出版社，2006:308-322.

［11］ 黄敏，何中市，邢欣来，等.一种新的k-means聚类中心选取算法［J］.计算机工程与应用，2011，47（35）:132-134.