影像Internet服务中金字塔的高效组织

高永光，胡闻达，何鹏程

（61683部队，北京100094）

影像Internet服务中金字塔的高效组织

高永光，胡闻达，何鹏程

（61683部队，北京100094）

为了提高基于Internet的影像信息服务的速度，提出了相离式金字塔结构，用以组织和管理海量的影像数据；分别讨论了相离式金字塔结构数据和索引两部分的组织问题，并给出了适宜的组织方法。同传统的金字塔结构相比，相离式金字塔结构具有更高的查询响应性能和更好的可扩展性，适于作为影像Internet服务中服务器端的数据组织。

影像数据；瓦片；相离式金字塔；空间邻近性

影像数据作为一种的重要的基础空间数据，在“国家空间数据基础设施”建设中起着越来越重要的作用[1]。在 Internet飞速发展和普及的今天，如何通过 Internet提供影像信息服务，从而为数字摄影测量和遥感图像处理等应用领域提供影像数据，成为一个既有理论意义又有现实价值的问题[2]。自从谷歌推出GoogleEarth之后，只需一台能够连接Internet的PC机，普通用户即可近距离感知整个地球、居住城市乃至所在街区，他们同样需要影像信息服务，以方便自己的日常生活。为了同慢速且不稳定的Internet相适应，服务器端通常将海量影像数据组织成瓦片金字塔结构，仅仅发送用户请求的瓦片，以减少服务器处理量和网络传输量，从而达到快速分发影像数据的目的。显然，影像金字塔的组织在上述解决方案之中是一个基础和核心问题，其组织优劣将直接影响到该解决方案的效率高低。本文深入研究了影像金字塔的组织问题，提出了一种索引与数据相分离的金字塔结构，即相离式金字塔结构，并设计了组织瓦片索引和瓦片数据的有效方法。实验和分析表明，相离式金字塔结构具有较快的查询响应和较好的可扩展性，完全可以用作服务器端的数据组织。

1 影像金字塔

为了提供各种分辨率的影像数据，同时满足用户的无级缩放需求，原始影像数据一般需要经过拼接、抽样、分块和金字塔构建等环节[3]。拼接是指将一个区域内的多幅小的影像图片无缝地拼接成一幅大的影像图片；抽样是指按倍数关系（为了实现无级缩放，应当取2倍）逐级将高分辨率影像图片抽样成各种分辨率的影像图片；分块是指在每一个分辨率级别中，将影像图片均匀划分成多个瓦片；金字塔构建是指将所有瓦片构建成一个金字塔，相邻级别之间的瓦片通过父子指针关联。考虑一幅影像图片，它被划分成8× 8=64个瓦片（如图 1所示），其中，数字表示瓦片编号。按2倍关系对图1进行抽样，直到最低一级分辨率的影像图片仅仅包含一个瓦片，结果见图2。我们约定：第1级为最低分辨率的影像图片。据此，图1应该是第4级影像图片。图3指出了第2、3级影像图片中瓦片之间的对应关系，其他相邻级别中瓦片之间的对应关系可以依次类推。从图3中可以看出，第2级的瓦片1是从第3级的瓦片1、2、5和6抽样而成的。

图1 示例影像图片（第4级）

图2 1-3级影像图片

图3 2-3级中瓦片之间的对应关系

基于上述金字塔结构，我们不仅可以为用户提供各种分辨率的影像数据，而且直接支持无级缩放：首先显示大比例尺（低分辨率）影像，在用户选择感兴趣区域之后，依据父子指针调出小比例尺（高分辨率）影像。由于无需读出对于用户来说无用的瓦片，使得平滑的影像漫游和缩放成为可能。需要指出的是，为了降低存储开销和减少网络传输，瓦片通常以压缩形式存储，一般是 jpg格式。因此，由于细节程度的不同，任意 2个瓦片，即使是来自同一个级别，也不大可能有相同的尺寸。

如何在物理上实现一个金字塔呢？通常的做法是将其表示成一种类似于树的结构[4]：树中的一层表示影像一个分辨率级；自根节点而下，依次表示第1级影像、第 2级影像等；每一个节点项除了记录一个瓦片数据之外，同时维护4个指向下一层瓦片的指针。上述思想是将索引信息与数据信息整合在一个结构之内，检索总是从根节点开始，依据索引信息自上而下进行瓦片定位。如果待请求瓦片位于第N层（N是金字塔的级数），那么至少需要N次I/O操作才能读出该瓦片，I/O代价较高正是树结构金字塔实现的一个最大缺点。另外，结构的复杂性和饱和性使得树结构金字塔实现的可扩展性很差。

2 索引与数据相分离的金字塔结构

为了提高影像金字塔的I/O性能，并使之同时具有较高的可扩展性，我们提出了一种索引与数据相分离的金字塔结构（以下简称相离式金字塔），其核心思想是将索引信息剥离出来单独组织：一个金字塔结构包括索引与数据2个部分，两者通过指针关联。在相离式金字塔结构中，每一个瓦片的数据被存储在数据部分，它同时在索引部分有一条记录，指出这个瓦片的级别和编号，以及该瓦片的尺寸及其在数据部分中的位置。图4给出了相离式金字塔的一个例子，其中，箭头表示指向数据部分位置的指针。检索时，首先扫描索引部分（索引部分较小，通常可以常驻内存，同磁盘I/O代价比较起来，基于内存的扫描代价是较小的），在定位出待请求瓦片的位置之后，借助1次I/O操作即可读出该瓦片。

图4 相离式金字塔示例

较之传统的一体式金字塔结构实现，我们提出的相离式金字塔结构实现有3个主要特点：

1）索引部分和数据部分各自组织，互不干涉，在索引部分相邻的 2个瓦片不一定在数据部分相邻，反之亦然；

2）内外存结构一致，当系统配置足够内存时，无需任何转换即可将相离式金字塔结构从磁盘导入内存；

3）数据结构简单，易于实现、操作和扩展。

2.1 数据部分组织

数据部分通常很大，不大可能装入内存之中，其I/O性能是我们关注的主要问题。显然，读取单个瓦片没有任何优化技巧可言，但是，用户往往依次请求多个瓦片，并且这些瓦片是语义相关的，或者在水平方向上有兄弟关系，或者在垂直方向上有父子关系。如果相邻的2个被请求瓦片在物理存储上也是相邻的，那么在读取瓦片时，磁盘中机械磁头的移动距离将被尽可能地减少，因而能够降低I/O代价。基于上述考虑，我们可以对那些有兄弟或父子关系的瓦片进行聚簇存储，从而利用瓦片请求的局部性来提高数据部分整体的I/O性能。

对于数据部分来说，一种直观的组织方法是逐层、逐行和逐列组织各个瓦片，即首先存储第1层瓦片，接着存储第2层瓦片等，而在一层内，首先存储第1行瓦片，接着存储第 2行瓦片等。这种组织方法虽然简单，但是几乎没有考虑到访问的局部性，使得其空间邻近性（包括水平和垂直2个方向）很差。

考虑水平方向上的访问局部性，我们需要尽可能地提高一个层中瓦片的空间邻近性。在二维空间中，空间临近性指按某种编码方式将二维位置映射成一维码后，邻接的二维位置在一维码中的距离远近程度。在已出现的多种编码方式中，Morton码（也称Z-order码）是其中最为简单有效的一种[5]。Morton码是对行列号的二进制码进行位交叉之后的得到的一种编码，例如，(3，4)M=26，其编码过程如图 5所示。据此，我们可以得到一种数据部分的组织方式（以下称为逐层Morton码组织），即首先逐层组织，而在一层内，按Morton码大小依次存储各个瓦片。对于图 1、图 2所示的金字塔，数据部分的逐层Morton码组织如下：<1.1，2.1，2.2，2.3，3.1，3.2，3.5，3.6，3.3，3.4，3.7，3.8，…，4.55，4.56，4.63，4.64>，其中，每一项的前一部分是层号，后一部分是图1和图2中瓦片的编号。

考虑垂直方向上的访问局部性，我们应该首先存储父瓦片，接着存储子瓦片，依次类推下去，即按照深度优先顺序组织各个瓦片（以下称为深度优先组织）。对于图1和图2所示的金字塔，数据部分的深度优先组织如下：<1.1， 2.1，3.1，4.1，4.2，4.9，4.10，3.2，4.3，4.4，4.11，4.12，…，4.55，4.56，4.63，4.64>。

图5 (3，4)的Morton编码

显然，水平和垂直2个方向上的访问局部性是相互矛盾的，照顾水平方向上的访问局部性必然会损害到垂直方向上的访问局部性，反之亦然。在实际应用中，即使是以下钻操作为主，在下钻到一个层次之后也会请求该层中在视野范围之内的所有瓦片。因此，较之垂直方向上的访问局部性，水平方向上的访问局部性更为重要一些，因此，逐层Morton码组织比深度优先组织更适合用来组织数据部分。

2.2 索引部分组织

索引部分较小，一般可以装入内存之中。虽然同I/O操作相比，CPU操作快了很多，但是，通过扫描索引来定位瓦片也是不可取的。为此，我们提出了索引部分的逐层有序组织，即首先逐层组织，而在一层内，按编码大小依次存储各个瓦片对应的索引项。在逐层有序组织中，每一层索引项的起止点被预先记录在数据字典中。对于索引部分来说，逐层有序组织可以借助二分查找，从而将瓦片定位的时间复杂度从 O(N)降为O(log2N)。当新来一个瓦片请求之后，首先依据其行列号计算出层内编码，然后在所属层的索引项范围之内进行二分查找。前面已经说过，索引部分组织并不依赖于数据部分组织，因此，索引部分可以采用更为简单的编码方式，如行优先码（即逐行顺序编码），而不是Morton码。对于图1和图2所示的金字塔，索引部分的逐层有序组织如下：<1.1，2.1，2.2，2.3，2.4，3.1，3.2，…，4.64>。

3 实验与分析

本节将通过实验来验证相离式金字塔的有效性。实验采用南昌市DMC航拍数据，该数据集有7层，共开展了2组实验：第一组随机生成1000条瓦片查询，测试总响应时间；第二组采用World Wind客户端从第1层下钻到第 7层，测试平均响应时间。实验平台是一台配置了 PIV处理器、1 G内存和80 G硬盘的戴尔PowerEdge SC430小型服务器。实验结果如表1和表2所示，其中，数据部分的无序指瓦片的存储顺序无规律可循，而索引部分的无序指索引项的存储顺序无规律可循。

我们从表1和表2可以得出2点：①由于瓦片数据的聚簇性存储，数据部分的深度优先组织和逐层Morton码组织大大加快了瓦片查询的响应速度，而后者利用了水平方向上空间临近性，在响应速度方面更胜一筹；②由于避免了时间复杂度为 O(N)的扫描操作，索引部分的逐层有序组织明显地提高了查询响应性能。

表1 随机瓦片查询的总响应时间/s

表2 World W ind查询的平均响应时间/s

4 结语

本文研究了影像Internet服务中金字塔的组织问题，在传统的一体式金字塔结构的基础上，提出了相离式金字塔结构，其包括数据和索引 2个部分，两部分各自组织，互不影响，具有很好的可扩展性。以此为基础，研究了数据部分和索引部分的组织方法，得出了适合于数据部分的逐层Morton码组织和适合于索引部分的逐层有序组织。实验和分析表明，相离式金字塔结构具有很高的查询响应性能，能够胜任服务器端的数据组织。

[1] 王密.大型无缝影像数据库系统(Geo ImageDB)的研制与可量测虚拟现实(MVR)的可行性研究[D].武汉:武汉大学，2001

[2] 陈静，龚健雅，朱欣焰，等.海量影像数据的Web发布与实现[J].测绘通报，2004(1):22-25

[3] 李霖，吴凡.空间数据多尺度表达模型及其可视化[M].第一版.北京:科学出版社，2004

[4] 邓雪清.栅格型空间数据服务体系结构与算法研究[D].郑州:中国人民解放军信息工程大学，2003

[5] 龚健雅.地理信息系统基础[M].第一版.北京:科学出版社，2001

[6] Jensen J.R.Introductory Digital Image Processing.A Remote Sensing Perspective[M].Pearson Prentice Hall，Upper Saddle River，NJ，2005

[7] Powell M.W，Rossi R.A，Shams K.A Scalable Image Processing Framework forGigapixel Mars and OtherCelestial Body Images[C].Aerospace Conference，2010:1-11

Efficient Organization of Pyramid in Internet Image Service

by GAO Yongguang

In order to improve image service speed based on Internet, we proposed a new architecture for image pyramid,called Separated Pyramid,for organizing and managing huge image data.Separated Pyramid structure contains two parts:data and index,and so we discussed their organization problem,leading appropriate organization for data part and index part respectively.Compared with traditional pyramid structure,Separated Pyramid provides higher query answering and better scalability,and so it can be used as the data organization of the server side in the Internet image service.

image data，tile，Separated Pyramid，space locality

2011-11-27

P237

B

1672-4623(2012)02-0070-03

高永光，工程师，研究方向为3S集成与应用。