面向影像金字塔的四叉树空间索引算法

2024年4月26日发(作者：)

计 算 机 工 程

第37卷 第10期

Computer Engineering

V

ol.37 No.10

文章编号：1000—3428(2011)10—0011—03

·博士论文·

2011年5月

May 2011

文献标识码：A

中图分类号：TP391

面向影像金字塔的四叉树空间索引算法

李建勋

a,b

，沈 冰

b

，姜仁贵

b

，陈田庆

b

(西安理工大学 a. 经济与管理学院；b. 水利水电学院，西安 710048)

摘 要：基于线性四叉树提出一种面向影像金字塔的空间索引算法。在分析线性四叉树拓扑关系的基础上，设计一个具有方向一致、层次

递进特性的编码方式，建立影像金字塔与线性四叉树的映射方案，给出一个按照经度纬度自然增长的邻域查找算法，并构建一个全球多分

辨率虚拟地形环境对编码和算法进行测试。实验结果表明，该算法能够明显地缩小空间影像的检索时间，具有较高的编码效率和查找效率。

关键词：影像金字塔；空间索引；线性四叉树；领域查找

Quadtree Spatial Index Algorithm Oriented to Image Pyramid

LI Jian-xun

a,b

, SHEN Bing

b

, JIANG Ren-gui

b

, CHEN Tian-qing

b

(a. Faculty of Economics and Management; b. Faculty of Water Resources and Hydraulic Power,

Xi’an University of Technology, Xi’an 710048, China)

【Abstract】Based on linear quadtree, a spatial image retrieval algorithm of image pyramid is proposed. According to the topological relations of

linear quadtree, this paper designs an encoding method with the characteristics of direction coherence, progressive hierarchy; establishes a mapping

between image pyramid and linear quadtree; gives a neighbors-searching algorithm in accordance with the natural growth of longitude-latitude; and

constructs a global multi-resolution virtual terrain environment to test the encoding method and algorithm. Experimental results show that the

algorithm can significantly reduce the time cost of spatial image retrieval, and has a high encoding efficiency and neighbors searching efficiency.

【Key words】image pyramid; spatial index; linear quadtree; neighbors-searching

DOI: 10.3969/.1000-3428.2011.10.003

1 概述

空间索引是指依据对象的位置、形状和空间关系，按一

定顺序排列的一种数据结构，其主要包含空间对象的标识、

外接矩形及指向其他空间对象实体的指针等信息。现有的空

间索引算法主要有

BSP树

[1]

、K–D–B树

[2]

、R树、R+树、

Hilbert–R

[3]

和CELL树等。长期的应用实践表明，此类算法

能够较好地满足空间索引的功能要求，但对海量的空间影像

而言则过于复杂，严重地影响了空间影像的进一步应用，特

别是随着影像金字塔

[4]

在空间信息重建、遥感影像数据访问

管理等方面的广泛应用，现有算法由于经纬度区域表示不明

确、方向性不强、检索效率低等问题，在一定程度上制约了

影像金字塔的发展。

为此，本文在分析线性四叉树

[5]

拓扑关系的基础上，在

影像金字塔和线性四叉树之间建立了空间映射，引入一个用

于描述经纬度区域的BBOX属性，并将位置信息与编码信息

予以结合，给出一个具有方向性、层次递进的快速邻域查找

算法。采用

BMNG影像数据及SRTM90数据构建了一个全球

多分辨率虚拟地形环境

[6]

，对编码和算法进行了评测。

2 面向影像金字塔的线性四叉树拓扑定义

定义1(结点) 在线性四叉树中，不能再分的结点称为叶

子结点，可再分的结点称为树杈结点。一个结点最多有

4个

子结点，每个子结点按照区域分解可命名为S

i

W

i

、S

i

E

i

、N

i

W

i

或N

i

E

i

，分别表示父结点所在区域的西南象限、西北象限、

东南象限或东北象限，其对应的遥感影像分别称为S

i

W

i

像元、

S

i

E

i

像元、N

i

W

i

像元和N

i

E

i

像元，其中，i∈{1,2,…,n}表示线

性四叉树的层高或深度。为了便于空间索引，将线性四叉树

的结点名称定义为：除根结点之外所有祖先结点的命名与本

结点命名的顺序字串和，表示为

H

1

H

2

…H

i–1

H

i

，其中，H

i

为

当前结点的命名；H

1

H

2

…H

i–1

均为其祖先结点命名；H

i

∈{S

i

W

i

,

S

i

E

i

, N

i

W

i

, N

i

E

i

}。显然，这种线性四叉树的结点名称也可看

作是除根结点之外父结点的名称与本结点命名的顺序字串

和。如：S

1

E

1

N

2

E

2

S

3

W

3

则表示原始影像东南象限的东北象限

的西南象限区域，也可看作父结点S

1

E

1

N

2

E

2

的西南象限区域。

由于结点和像元之间将构成一个双射，为简化描述，本文将

不对结点和像元2个概念进行区分，并统称为像元。

定义2(像元属性) 像元G被定义为由{IDX, D, R, W, H,

BBOX}所表示的一个六元组，如图1(c)所示，其中，IDX是

一个唯一的编码符号，用于描述该像元在线性四叉树中的索

引信息，IDX是像元的关键属性，合理地对IDX编码将能够

有效地简化本像元其他属性信息的描述；D为树的层高或深

度，其值由根向叶像元方向依次递增，且根像元的D值规定

为零；R为当前像元的分辨率，同一层的像元则具有相同的

R值；W和H分别表示像元影像的宽度和高度；BBOX

(Bounding Box)则是引入的一个用于描述地理空间的属性，以

提高编码与经纬度区域之间的转换效率。BBOX由{minLong,

基金项目：国家“863”计划基金资助项目(2006AA01A126)；国家

自然科学基金资助项目(50979088)；陕西省重点实验室基金资助项目

(05JS378)

作者简介：李建勋(1977－)，男，讲师、博士研究生；主研方向：

GIS，空间索引，水利信息化，中间件；沈 冰，教授、博士生导师；

姜仁贵，硕士研究生；陈田庆，博士研究生

收稿日期：2010-10-12 E-mail：jxli@

12 计 算 机 工 程 2011年5月20日

minLat, maxLong, maxLat}4个元素表示，分别对应于空间区

域的最小经度、最小纬度、最大经度和最大纬度，简记为{iLo,

iLa, xLo, xLa}。

分别称为西南角邻域、东南角邻域、西北角邻域、东北角邻

域，分别记为

Ne

SW

()、Ne

SE

()、Ne

NW

()、Ne

WE

()。

定义4(边界像元、非边界像元) 边界像元是指至少有一

个邻域不存在的像元，如图1(a)中标号为00、0101、0111、

1010、111010的像元，在研究其邻域搜索算法时应予以特殊

处理。非边界像元则是指

4个边邻域和4个角邻域均存在的

像元，如图1(a)中标号为1100、111000的像元。

3 影像金字塔到线性四叉树的映射及编码

3.1 影像金字塔到线性四叉树映射

建立影像金字塔到线性四叉树的映射主要是采用线性四

叉树的数据结构对多分辨遥感影像进行索引，从而将影像金

字塔中像元的空间索引任务变换到线性四叉树的像元查找

上。具体的映射步骤为：(1)对于一个n层影像金字塔，建立

一个D=n的线性四叉树，使得影像金字塔的第i层L

i

与线性

四叉树的第n–i层像元对应；(2)对顶层的影像金字塔不进行

切割，使其直接与线性四叉树的根像元对应；(3)对顶层之外

的各层影像金字塔进行切割，切割首先从第

n–1层影像金字

塔开始，将该层影像按照线性四叉树分解的方法分成SW、

SE、NW和NE 4个影像块，每个影像块对应于线性四叉树

深度为1的4个像元；(4)再对由n–2层影像金字塔进行切割，

将该层影像按照线性四叉树分解的方法分成SW、SE、NW

和NE 4个影像块，并对这4个影像块每个均按照线性四叉树

分解的方法切割一次，从而分解生成16个影像块，其对应于

线性四叉树深度为

2的16个像元；(5)按照上述方法完成其

他各层影像金字塔的切割，直到第0层影像金字塔。

3.2 面向影像金字塔的线性四叉树编码

规则1(空间编码) 像元属性IDX的编码简称空间编码，

如图1(a)和图1(b)所示：(1)线性四叉树中深度为零的像元，

即线性四叉树的根像元不编码；

(2)设线性四叉树中层为i的

某像元G的名称为H

1

H

2

…H

i–1

H

i

，其中，H

i

∈{S

i

W

i

,S

i

E

i

,N

i

W

i

,

N

i

E

i

},i∈{1,2,…,n}，提取该像元名称中的任意一部分命名

H

k

，对命名H

k

按照方向予以编码：S

i

和W

i

用0表示，E

i

和

N

i

用1表示，值S

i

W

i

、S

i

E

i

、N

i

W

i

和N

i

E

i

被分别表示为00、

10、01和11；(3)按i的自然顺序对H的名称H

1

H

2

…H

i–1

H

i

编码，编码结果记为m

1

m

2

…m

2i–1

m

2i

…m

2n–1

m

2n

, m

i

∈{0, 1}，

该值即为

IDX的编码值；如S

1

W

1

的子像元S

1

W

1

S

2

W

2

、S

1

W

1

N

2

W

2

、S

1

W

1

、S

2

E

2

和S

1

W

1

N

2

E

2

的编码分别为0000、0010、

0001、0011。空间编码是结点命名规则和方向编码的融合，

它不仅表示了结点的命名顺序和辈数，而且蕴涵了结点所在

区域的方位信息。当结点不断扩张时，空间编码的长度也随

之增大，遵循了划分越细致编码越精细的层次递进原则。

规则2(深度编码) 像元属性D的编码为由零开始递增的

自然数序列；根据

IDX的编码规则有D=Length(IDX)/2。

规则3(分辨率编码) 像元属性R的编码由R

i

=2×R

i–1

给

i为该像元的D值；显然R

i

=2

i

×R

0

=2

D

×R

0

=2

Length(IDX)/2

×R

0

。 出，

规则4(大小编码) 根据影像金字塔的性质，像元的高、

宽(W、H)为固定值，其大小为金字塔顶层影像的宽度和高度。

规则5(区域编码) 由于线性四叉树任意一个像元G

i

可由

4个子像元S

i–1

W

i–1

、S

i–1

E

i–1

、N

i–1

W

i–1

和N

i–1

E

i–1

构成，并

且4个子像元恰好分解了父像元所在的区域，因此4个子像

元的BBOX之和便是父像元的BBOX值，而子像元的BBOX

则可根据其所在父像元内的区域获得。

像元的BBOX属性值存在的递推公式为：S

i–1

W

i–1

子像

元: iLo

i–1

= iLo

i

；iLa

i–1

=iLa

i

；xLo

i–1

=(iLo

i

+xLo

i

)/2；xLa

i–1

=(iLa

i

+

(a)编码时的区域划分

(b)编码后的四叉树结构

(c)像元属性

图1 面向影像金子塔的线性四查树拓扑及编码

定义3(邻域) 邻域是指2个像元之间所存在的彼此连接

关系。若像元A为像元B的邻域，则记为：A=Ne(B)。根据

像元间连接关系的不同，邻域可分为边邻域和角邻域2种。

若像元A通过“边边相连”到像元B，则称A为B的边邻域，

记为A=Ne

S

(B)。边邻域按其所在方向分别称之为东边邻域、

南边邻域、西边邻域、北边邻域，分别记为Ne

E

()、Ne

S

()、

Ne

W

()、Ne

N

()。若像元A仅通过一个顶点与像元B相连，则

称A为B的角邻域，记为A=Ne

A

(B)。角邻域按其所在方向

第37卷 第10期

李建勋，沈

冰，姜仁贵，等：面向影像金字塔的四叉树空间索引算法

13

xLa

i

)/2；S

i–1

E

i–1

子像元：iLo

i–1

=(iLo

i

+xLo

i

)/2；iLa

i–1

=xLa

i

；

xLo

i–1

=xLo

i

；xLa

i–1

=(iLa

i

+xLa

i

)/2；N

i–1

W

i–1

子像元：iLo

i–1

=

iLo

i

；iLa

i–1

=(iLa

i

+xLa

i

)/2；xLo

i–1

=(iLo

i

+xLo

i

)/2；xLa

i–1

=xLa

i

；

N

i–1

E

i–1

子像元：iLo

i–1

= iLo

i

+xLo

i

)/2；iLa

i–1

= (iLa

i

+xLa

i

)/2；

xLo

i–1

=xLo

i

；xLa

i –1

=xLa

i

。

共计平移操作3 584次、在显示分辨率为1 024×768 像素时，

缩放操作200次、混合操作6 000次。表1是在IBM System

针对平移、放大、x3650服务器以及18层影像金字塔基础上，

缩小3种操作分别采用不同空间索引算法的代价对比表。由

表1可知：(1)采用本算法的平均操作代价均小于其他算法，

特别是在混合操作时，本算法响应速度能力相较于其他算法

明显提高；

(2)由于平移操作复杂度低，且涉及空间索引算法

较少，因此算法性能对其影响不大，因而本算法改善较小；

(3)缩放操作中蕴涵了众多与空间索引相关的算法操作，其代

价大小是衡量多分辨率虚拟环境以及其他空间影像服务系统

的重要指标，采用面向影像金字塔的线性四叉树算法后，系

统仅需要接近于其他算法一半的操作代价便完成了缩小或放

大操作，较好地提高了系统性能。

表1 不同空间搜索算法代价的对比 ms

算法

BSP tree

K-D-B tree

R tree

R+ tree

CELL tree

Linear quadtree based on

FD

Image pyramid oriented

linear quadtree

Cost of

pan

500

488

523

437

479

Cost of

zoom-in

1 200

1 309

1 444

1 105

1 094

Cost of

zoom-out

1 178

1 370

1 487

1 095

1 088

Cost of mix

operation

1 580

1 703

1 883

1 466

1 337

4 编码特性及邻域查找算法

邻域查找算法是对空间索引的一种扩展应用，其目的是

以当前像元空间编码为基础，并根据一个指定的搜索方向、

步伐和尺寸大小去探索另一个像元的空间编码，以实现对空

间影像的索引，从而建立一组或多组多分辨率影像的层次化

应用。

在上述编码方式下，邻域查找算法描述如下：

算法 面向影像金字塔的线性四叉树邻域查找算法(当前

像元为A，被搜索的邻域为B)。

输入 像元A的空间编码A

IDX

以及搜索方向Direction、

步长Step、尺寸大小Size。其中，Direction取值为编码值m

1

m

2

，

分别为M0、0M、M1、1M、00、01、10、11(M表示0或1)；

Step指定被查找邻域与当前像元之间的距离，其分为x和y

两部分，x表示A、B之间由南向北的顺序位置相差值，y表

示A、B之间由西向东的顺序位置相差值；Size指定被所查

找邻域尺寸大小，其值为B

W

×B

H

。

输出 像元B的空间编码B

IDX

。

(1)取A的空间编码A

IDX

，计算A

(Mo,Me)

，并将A

(Mo,Me)

转化为A

(i,j)

，其中Mo和Me为A的奇数位和偶数位的二进

制编码，

i和j则为Mo和Me所对应的十进制值。

(2)判断A是否为边界像元，即Ne

E

(A)、Ne

S

(A)、Ne

W

(A)、

Ne

N

(A)中至少一个不存在，如果是则转向步骤(3)，否则转向

步骤(4)。

(3)根据A的位置编码A

(Mo,Me)

，判断A的Direction方向

的邻域Ne

Direction

(A)是否存在，如果不存在则返回空，否则执

行步骤(4)。

(4)

对所得的(i,j)值按Direction方向做运算：B

(i,j)

=

A

(i+x,j+y)

。

(5)将所得B

(i,j)

转化为B

(Mo,Me)

；再将B

(Mo,Me)

转化为B

IDX

。

(6)计算A

W

×A

H

的值，并将其与Size=B

W

×B

H

比较，若

A

W

×A

H

=Size，则B

IDX

即为所求邻域的空间编码值；若

A

W

×A

H

≠Size，则执行步骤(7)。

(7)

令C=lb(B

W

/A

W

)，若C>0，则将B

IDX

末尾的2C位截

掉，且截掉后的B

IDX

为所求邻域的空间编码值；若C<0，则

取Direction方向的反方向的编码值在B

IDX

的末尾进行C次

拼补，则拼补后的B

IDX

为所求邻域的空间编码值。

(8)

每次拼补的方法为：首先提取Direction的方向编码

m

1

m

2

，然后计算m

1

m

2

的反码m

1

’m

2

’，最后将m

1

’m

2

’使用字

串的方式追加到B

IDX

的末尾即可。

378 900 891 1 201

316 547 529 612

6 结束语

本文采用线性四叉树建立了一个面向影像金字塔的空间

索引算法，该算法对于n层金字塔影像来说，仅需要2n位二

进制数即可建立据空间索引，具有方向性强、层次递进等特

性。采用该方法建立的全球多分辨率虚拟地形环境已经作为

一个空间应用基础服务平台在国家“

863”计划项目中进行了

示范应用，为空间影像存储访问以及数字地球的研究提供了

可借鉴经验。下一步的工作主要是与WebGIS互操作机制相

结合，改善GIS数据的访问效率。

参考文献

[1] Hamid R R, Kashyap R L, Radha H. Multiresolution Image

Compression with BSP Trees and Multilevel BTC[C]//Proc. of

IEEE International Conference on Image Processing. [S. 1.]: IEEE

Press, 1995.

[2] Santana O, Rodriguez G, Diaz M, et al. Infinite Distance in the

Determination of the Nearest Euclidean M-neighbours in the

K-D-B Tree[C]//Proc. of IEEE International Workshop on Tools

for Artificial Intelligence Architectures, Languages & Algorithms.

Fairfax, Virginia, USA: [s. n.], 1989.

[3] 何小苑, 闵华清. 基于聚类的Hilbert-R树空间索引算法[J].

计算机工程, 2009, 35(9): 40-42.

[4] Xia Song, Li Deren. Terrain Change Detection and Updating with

Image Pyramid[C]//Proc. of SPIE’07. Wuhan, China: [s. n.], 2007.

[5] Chan Yung-Kuan, Chang Chin-Chen. Block Image Retrieval Based

on a Compressed Linear Quadtree[J]. Image and Vision

Computing, 2004, 22(5): 391-397.

[6] 杜 莹, 武玉国, 王晓明, 等. 全球多分辨率虚拟地形环境的

金字塔模型研究[J]. 系统仿真学报, 2006, 18(4): 955-　958.

5 实验结果与讨论

为检验上述空间索引算法的性能和计算效率，本文采用

NASA的BMNG影像数据构建了一个全球多分辨率虚拟地形

环境，生成不同级别分辨率的金字塔影像320 000多幅，并

存储在以线性四叉树为编码方式的空间数据资源库中。在实

验中，基于

JUnit编写一个测试单元，自动地控制系统中的

平移、放大、缩小以及混合操作，使得每次操作等间距变化。

编辑 索书志