一种基于空间层次分解的Hilbert码生成算法_陆锋

一种基于空间层次分解的Hilbert码生成算法_陆锋

第6卷(A版)　第5期2001年5月

中国图象图形学报

JournalofImageandGraphics

Vol.6(A),No.5

May2001

一种基于空间层次分解的Hilbert码生成算法

陆　锋

周成虎

(中国科学院资源与环境信息系统国家重点实验室,北京　100101)

摘　要　基于Hilbert空间填充曲线的Hilbert空间排列码是一种优秀的线性映射方法,故在空间查询与索引中得到广泛应用.传统的Hilbert排列码算法是基于Morton码上的二进制位操作,复杂度为O(n2),在Hilbert空间填充曲线的空间层次分解特征的基础上,提出了一种新的Hilbert排列码生成算法,即通过栅格空间层次分解与构造区域状态转移向量,以递归的方式来生成Hilbert码,其复杂度为O(n),较之传统算法显著地提高了效率.在此基础上,结合点特征空间区域查询方法,又进一步阐述了以Hilbert空间排列码作为地址码的二叉平衡排序树空间索引方法的应用特点,并结合实例进行了讨论.

关键词　线性映射　Hilbert排列　层次分解　算法

中图法分类号:TP301.6　　文献标识码:A　　文章编号:1006-8961(2001)05-0465-05

AnAlgorithmforHilbertOrderingCodeBased

onSpatialHierarchicalDecomposition

LUFeng,ZHOUCheng-hu

(StateKeyLaboratoryofResourcesandEnvironmentalInformationSystem,ChineseAcademyofSciences,Beijing100101)

Abstract　HilbertspatialorderingbasedonHilbert-Peanocurvesisanexcellentlinearmappingmethod,andgetswideapplicationsinspatialqueryingandspatialindexing.ThetraditionalalgorithmforHilbertorderingcodeisbasedonbinarybitmanipulationonMortoncode.IthasacomplexityofO(n2).Inthispaper,theauthorsetforwardanewgeneratingalgorithmforHilbertorderingcode,whichisimplementedbyrasterspacerecursivedecompositionandregionalphaseshiftingvector,andhasacomplexityasO(n).Experimentshavevalidetedtheefficiencyofthenewalgorithm.Thealgorithmhasbeenappliedinafeaturebasednon-planardatamodelforurban

trafficnetworkstogeneratetheaddresscodesoastofacilitatethepointfeaturedynamicindexingbasedonbalancedbinaryorderingtreeandthelinearfeatureindexingbasedonvertexretrospection.Theaddresscodesforqueryingareaboundarycellscanbeusedtoseparatetheareaintoseveralsub-areastodecreaseexcessivesearching.SpatialorderingbasedonHilbertcodefacilitatesspatialclusteringofthespatialobjectsandspeedsupdataextraction.SpatialindexingwithHilbertcodeismoreefficientthansequentialindexingwhenagreatnumberofspatialobjectsareprocesed.Itisdistinctforspatialextentandproximityquerying.Keywords　Linearmapping,Hilbertordering,Hierarchicaldecomposition,Algorithm

凑技术,即将数据库中的记录映射到磁盘上的桶内,

0　前　言

线性映射一直是空间数据操作的重要组成部分,其在影象压缩、行程编码形式的栅格数据表达、空间索引、计算几何中的启发式搜索等领域应用十分广泛.

最早的多维到一维线性映射主要采用多属性杂

基金项目:国家“九五”科技攻关项目(96-B02-03-05)::09-26

以加快一维遍历和指定范围查询[1],但这种方法需要设计良好的杂凑函数,并且还要处理重复码问题,

因此在应用中,已经逐渐被基于空间填充曲线的空间排列码方法所代替.

虽然任何一种空间排列方法都不能完全保证能对二维数据的空间关系进行维护,但不同的空间排

一种基于空间层次分解的Hilbert码生成算法_陆锋

解来递归构造;

(3)单调性　在栅格格网中对于一个固定的x(y)坐标,其空间排列码值将随着y(x)方向上特定移动方向的变化而呈现单增或单减.

引效率也不相同.专家学者们曾先后对应用最广泛的Morton码、Gray码、Sierpinsky及Hilbert码空间排列进行了比较,结果显示,Hilbert空间排列的聚集性能最好[3,5,6],因而Hilbert空间排列已被应

[7]

用于空间数据库的几何索引中.

传统的Hilbert空间排列码生成算法由

[2]

Faloutsos和Roseman(1989)提出,这种算法是基于空间目标栅格格网行列数的二进制操作,复杂度为O(n),本文则提出一种栅格空间层次分解与区域状态转移向量相结合的Hilbert码算法,其复杂度为O(max(ni)).其中,ni为与空间目标二维笛卡尔坐标xi、yi所对应的栅格行列数值的二进制位数中的较大者.

2i

2　Hilbert空间排列码

Hilbert空间排列码源于经典的Peano曲线族.该Peano曲线族是闭合间隔单元I=[0,1]到闭合矩形单元S=[0,1]2的连续映射,也是所有能够填满二维或更高维空间的连续分形曲线的总称,故又称为空间填充曲线,它由意大利数学家Peano于1890年首先提出,德国数学家Hilbert于1891年首先给出了构造这种空间填充曲线的几何过程,并提出了所构造的空间填充曲线“处处连续,但处处不可导”的著名假设,直到1994年,才由Sagan将之证明

[11]

1　空间排列基本特征

空间排列(Spatialordering),或称空间聚集(Spatialclustering),可以定义为连续整数或关键字值与空间实体集元素之间可逆的一一对应关系[3].由于这些关键字值可以决定目标的遍历次序或目标地址,故又可称为空间排列码.它们起初是作为栅格数据模型中的一种目标组织方式而提出的,但近年来,随着GIS技术的不断发展,空间排列码在目标空间索引中的应用研究也不断深入,如今空间索引的栅格化已经成为GIS数据结构重要的发展方向之一[10].

空间排列码可以通过将连续空间进行细致划分,并以栅格象元的联接进而构造规则曲线的方式来得到.空间目标的排列码即为空间目标所占据的象元在规则曲线中的排列次序,它与空间的细分程度密切相关.

基于空间排列的多维数据一维映射方法可分为如下两种基本类型[4]:

(1)非递归方法,如行(列)序排列、行(列)主序排列、螺旋排列等;

(2)递归方法,如Morton排列、Gray码排列、Hilbert排列、Sierpinsky排列等.

与空间数据处理相关的空间排列码可以用以下3种特征来描述[3]:

(1)连续性　指空间排列码相邻的目标在栅格格网中所占据的象元必须相邻;

[3,4,8,9]

.Lindenmayer于1980又年提出了一种空间填

充曲线的构造模式,即著名的LindenmayerSystem(L-system),或称ParallelString-RewriteSystems,它由一个原子与一个产生式规则集组成,而这种产生式规则则决定了原子的复写特征.

Peano曲线族保持了被扫描数据的空间联系,就是说,沿着由扫描形成的一维数据空间虽然有大的步移,但在空间联系上却只有少许移动.另外,Peano曲线族还具有以下特征:

(1)对于数据空间中的每一元素,曲线只通过一次;

(2)在曲线上靠近的点在空间上也是靠近的;(3)在空间上靠近的点在Peano曲线上也可能是靠近的;

(4)通过从一维空间到n维空间的变换,Peano曲线在一定程度上保持了空间数据之间的空间联系.

Hilbert空间填充曲线是peano曲线族的一员,其用二维Lindennmayer系统描述如下:若指定原子为F,其顺时针旋转一个角度单位为+,逆时针旋转一个角度单位为-,则Hilbert空间填充曲线的产生式规则为[12]

(L→+RF-LFL-FR+,R→-LF+RFR+FL-)

[13]

[12]

因而,Hilbert空间填充曲线的获得方法是,首先给定一个原子,然后递归地运用上述产生式规则,即可以得到逐渐细化的Hilbert空间填充曲线,它.

一种基于空间层次分解的Hilbert码生成算法_陆锋

第5期陆　锋等:一种基于空间层次分解的Hilbert码生成算法467

空间填充曲线的排列次序及逐步细化过程如图1所示,其曲线所经过的包含空间目标点的栅格格网的次序,即称为空间目标点的Hilbert排列码,由于Hilbert排列码是递归的、连续的、非单调的,且它与四叉树兼容,故在行程编码中具有较高的效率

.

有较大的影响.

3　基于空间层次分解的Hilbert空间排列码生成算法　　经过对

Hilbert空间填充曲线特征的分析,提

出通过栅格空间的层次分解来生成Hilbert排列码,以降低算法的复杂度.该空间层次分解即是通过可迭代的规则方法来对空间进行逐步细化,并用规则栅格格网来铺满整个空间的过程,因而这种方法实质上是一种在构造Hilbert空间填充曲线过程的同时来生成Hilbert空间排列码的方法.

由于在层次空间分解过程中,每个格网尺寸完全一致,不存在栅格图象的线性四叉树生成中的重复检测问题(判断块内格网元素是否相同,以决定是否继续划分),从而为算法效率的提高奠定了基础.

此算法采用栅格空间层次分解与区域状态转移

图1　Hilbert空间填充曲线的排列次序及细化过程

向量相结合的方法,其中状态转移向量表明了空间层次分解中子曲线的旋转与反射.算法描述如下:

(1)设定初始状态向量,并判断目标所在象限,根据初始状态向量得到初始空间排列码;

(2)将目标所在象限等分为4个子象限,若子象限对应区域范围小于限定值,则返回;

(3)判断目标所在子象限,根据父象限空间排列码及状态转移向量,来决定子象限空间排列码,并重新设定状态转移向量;

(4)返回(2),对子象限进行递归分解.通过Hilbert空间填充曲线特征的分析可以看出,曲线共有4种子象限形态,其决定了状态转移向量共有4种取值方式,即{1,2,3,4}、{1,4,3,2}、{3,2,1,4}和{3,4,1,2},如图2所示.

经典的Hilbert码生成算法由Faloutsos和Roseman(1989)提出,由于这种算法是基于空间目标点所在的栅格格网行列数的二进制位操作,故其复杂度为O(n),其中ni为与空间目标点i所在最终栅格格网行列数中较大者所对应的二进制位数.算法描述如下:

(1)将索引栅格格网行列数采用二进制位交叉方法转化为对应Morton码;

(2)以两位为一个单位,由高位开始,对生成的Morton码中的10和11互换;

(3)由高位开始,设为ti,对后续各位作如下处理:若ti为00,则将后续各位中的11和01进行互换;否则,若ti为11,则将后续各位中的10和00进行互换;

(4)将结果按顺序排列,即为Hilbert空间排列码.如图1所示,Hilbert空间填充曲线虽可通过栅格空间的层次分解方法来构造,但上述Hilbert空间排列码算法并没有考虑Hilbert空间填充曲线的层次分解过程,而且它与Hilbert空间填充曲线的构造无关,它是完全在最终栅格层次上进行处理,因而是完全针对最终栅格空间状态,对空间目标点行列数所对应的二进制代码进行的代数运算.其中(2)、(3)两步形成一个ni×ni的二重循环,使得算法的时间复杂度为O(ni2).这样,当空间目标点距离栅[2,14]2i

图2　Hilbert空间填充曲线状态转移

一种基于空间层次分解的Hilbert码生成算法_陆锋

468中国图象图形学报第6卷(A版)

由于状态转移向量的不同取值决定了后续子象限中子曲线的形态,也就决定了目标点所在子象限对应空间排列码,因此,算法的关键在于决定层次分解中状态转移向量的取值.

算法伪码如下:

f=0;scan-order=3;

//决定初始排列码和初始扫描序,扫描序决定状态向量inthilbert(a,b,p,scan-order)

//a,b为父象限角点,p为目标点{

if(b.x-a.x≤xtol||b.y-a.y≤ytol)return(f);

//子象限小于最终格网尺寸容限值则返回fc1=f 2;fc2=fc1+1;fc3=fc1+2;fc4=fc1+3;

//决定区域状态转移向量

t1=(a.x+b.x)/2;t2=(a.y+b.y)/2;

quadrant=locate-quadrant(a,b,p);//决定目标点象限switch(quadrant)

//根据所在子象限,决定扫描序和子象限排列码{

case1:

a.x=t1;a.y=t2;switch(scan-order){

//决定本层次目标点排列码及扫描序…}break;

…}

hilbert(a,b,p,scan-order);

}

排列码算法的时间复杂度为O(max(ni)).

对于任何一个空间目标点,基于栅格空间层次分解的Hilbert排列码算法均具有一致的时间耗费,而前面所述的Faloutsos和Roseman算法,其时间耗费则与空间目标点位置密切相关,即其时间耗费将随着与栅格格网坐标原点距离的增大而增大.表1是基于二进制位操作的Hilbert空间排列码算法与基于层次分解的Hilbert空间排列码算法在不同格网细化规模下的效率比较.由表1可以看出,基于层次分解的Hilbert空间排列码算法,较之基于二进制位操作的Hilbert码算法效率有了显著的提高.

表1　Hilbert空间排列码算法效率比较

格网数位操作层次分解

512×512

31

768×768

74

(单位:s)

1024×10242048×2048

127

5331

5　算法应用实例

本文提出的Hilbert码算法已用于基于特征的

交通网络非平面数据模型中,该模型是利用Hilbert空间排列码作为地址码来构造基于平衡二叉排序树的点特征动态索引及基于角点回溯的线特征索引,以完成几何查询工作.

将空间目标点按Hilbert空间排列码排序,即可将目标在一定程度上进行空间聚类,以加快数据提取过程.这种方法在处理大量空间目标时,比序贯索引更有效,且这一特征在空间范围查询与最邻近目标查询中表现十分突出.

图3为一个基于Hilbert空间排列码的空间范围查询实例.在该实例中,查询区域内栅格格网范围为(13,15)～(36,38),对应的Hilbert空间排列码为278～1107,以此作为地址码范围,从数据集中找出地址码落在此范围内的点目标,然后再对得到

由于空间层次分解的最终格网尺寸xtol与ytol是依赖于用户数据集的比例尺、数据密集程度及具体

应用特征,因此需要保持空间查询效率需求与空间目标区分之间的平衡.例如,在基于Hilbert空间排列码的GIS空间索引方法中,当应用于城市交通领域时,即采用50m×50m作为最小栅格格网尺寸.

4　算法效率分析

从上述伪码可以看出,算法的时间耗费取决于当达到最小栅格格网单元尺寸时的空间分解次数,而从分析空间层次分解的过程可知,由于每一次分解均使栅格格网行列数的二进制位数增大一位,也就是说,栅格空间层次分解次数,即为空间目标点可能具有的最大的栅格格网行列数的二进制位数mi图3　基于Hilbert排列码的区域查询搜索方法

一种基于空间层次分解的Hilbert码生成算法_陆锋

第5期陆　锋等:一种基于空间层次分解的Hilbert码生成算法469

的目标进行筛选.

由于Hilbert空间填充曲线是非单调连续分形曲线,因此指定区域内格网的最小最大地址码不一定对应区域的4个角点,但一定在指定区域的4条边上.图4表达了图3中的查询区域在数据集中的搜索过程.通过二叉排序树结构来组织数据,可找出Hilbert空间排列码为325、486和667的3个点目

标(见图3).

采用Hilbert空间排列码作为地址码,即可以以查询区边界地址码跳变为界来进行数据集搜索,

若跳变之间的点不在查询区域内,则以跳变为界划分区域,以减小过度的搜索规模.这里跳变为查询区边界上的相邻格网的地址码之差.跳变容限依赖于区域划分次数与过度搜索规模之间的平衡

.

图4　基于Hilbert排列码的数据集搜索过程

datasets.InternationalJournalofGeographicalInformation

参考文献

1　FaloutsosC.

Multiattributehashingusinggraycodes.

In:

ProceedingsofACM-SIGMOD,Washington,1986:227～238.2　FaloutsosC,RosemanS.Fractalsforsecondarykeyretrieval.

In:Proceedingsofthe8thACMSIGACT-SIGMOD-SIGARTSymposiumonPrinciplesofDatabaseSystems,Philadelphia,1989:247～252.

3　AbelDJ,MarkDM.Acomparativeanalysisofsometwo-dimonsionalorderings.InternationalJournalofGeographicalInformationSystems,1990,4(1):21～31.

4　KumarA,MuhannaWAetal.Analysisoftheperformanceof

spatialorderingmethods.InternationalJournalofGeographicalInformationScience,1998,12(3):269～289.5　MoonB,JagadishHV,FaloutsosCetal.

clusteringpropertiesof1996.

6　RongY,FaloutsosC.Analysisoftheclusteringpropertyof

Peanocurves.TechnicalReport,UniversityofMaryland,1991.7　KamelI,FaloutsosC.HilbertR-tree:AnimprovedR-treeusing

fractals.Proceedingsof20thInternationalConferenceonVeryLargeDataBases,LosAltos:MorganKaufmannPublishers,1995:500～509.

8　龚健雅.整体SIS的数据组织与处理方法.武汉:武汉测绘科技大学出版社,1993.

9　:http://www.cs.umd.edu/TR/UMCP-CSD

Analysisofthe

URL:

Hilbertspace-fillingcurve,

Science,1998,12(6):537～559.

10谈国新.一体化空间数据结构及其索引机制研究.测绘学报,

1998,27(4):293～299.

11MarianoA,MoscatoP,NormanMGetal.Arbitrarilylarge

planarETSPinstanceswithknownoptimaltours,TechnicalReport,CornellUniversity,USA,1995.

12DickauRM.Two-dimensionalL-systems,URL:http://forum.

swarthmore.edu/advanced/robertd/lsys2d.html,1996.

13顾其钧,杨海浪,赵锐等.皮亚诺扫描分形基图象编码与压缩.环境遥感,1993,8(4):300～305.14WeissteinEW.

1998.

Plane-fillingfunction,URL:

http://www.

astro.virginia.edu/～

eww6n/math/Plane-FillingCurve.html,

　陆　锋　1970年生,博士.主要从事地理信息系统中基于特征的地理网络数据模型、网络分析算法及空间索引方法的研究.

CS-TR-3611,

　周成虎　1964年生,研究员,博士生导师.研究兴趣包括地理信息分析与应用模型、遥感影象地学理解与分析、空间数据挖掘与知识发现等.

本文来源：https://www.bwwdw.com/article/nyz1.html