（应用数学专业论文）rsglobe系统中空间数据调度和压缩算法研究.pdf

河南大学硕士研究生学位论文 第1 页 摘要 构建数字地球是一项跨越多学科的理论和系统性工程。随着空间技术迅速发 展，为数字地球带来强有力的数据支持，并对其功能扩展提出了新的要求，但同 时给系统构建带来了一系列问题，海量空间数据难以在有限系统资源条件下有效 处理以及数据加载过慢不能满足实时显示和交互的要求。这主要是在数据的组织 与调度，空间索引效率，数据压缩技术等方面存在着亟待改进的地方。 针对开发数字地球系统存在的问题，本文从数据处理的角度出发，讨论了海 量影像数据、矢量数据的结构、组织、索引以及在数字地球系统中场景简化的系 统模型；着重研究了数字地球的空间数据调度，矢量数据压缩技术等问题。作者 所在的课题组与中国科学院遥感应用研究所遥感论证中心合作研究并开发了一个 三维数字地球平台r s g l o b e ，目的是在i n t e r n e t 环境下实现我国资源卫星、m o d i s 以及其他卫星提供图像的实时可视化。本篇论文阐述的理论和算法大部分集成到 r s g l o b e 中并取得了良好的效果。 本文的主要工作如下： 1 、为了实现系统在显示多分辨率栅格影像数据时的大量数据载入，并且给系 统实时显示提供连续的数据支持，对栅格影像数据的分层分块技术进行分析，在 基于瓦片金字塔和线性四叉树的数据组织模式上设计了目标瓦片搜索与瓦片数据 请求预测相结合的调度策略，解决了系统的数据装入和支持的问题，最大程度满 足了多分辨率影像数据实时显示的需求。 2 、在r s g l o b e 系统中，由于原始矢量数据组织形式复杂，会造成数据加载 缓慢，为了实现矢量数据快速精确显示，在加载之前必须进行数据压缩。本文基 于对传统矢量数据压缩算法的对比研究，对传统d o u g l a s p e u c k e r 算法进行改进， 在拓扑关系保持上采用了建立等效元数据索引表分别对公共边和非公共边进行压 缩并按索引表还原曲线间拓扑结构，并在改进算法中引入了分割封闭曲线所用起 始点和终点的选择方案。实验结果表明，改进后的算法兼顾了压缩精度、存储容 量、系统加载时间等重要因素，有效的缓解了场景实时漫游需求与数据加载过慢 之间的矛盾。 3 、在r s g l o b e 系统中实现了所设计的目标瓦片搜索与瓦片数据请求预测相 结合的调度方法，并实现了提出的d p 改进算法，不仅满足了实时显示所需要的 连续数据支持，而且提高了矢量数据的加载和显示效率。 关键词：r s g l o b e ；数据调度；矢量数据；d o u g l a s p e u c k e r 第1 i 页河南大学硕士研究生学位论文 a b s t r a c t t h ec o n s t r u c t i o no fd i g i t a le a r t hi saa c r o s s i r 】l gm u l t i d i s c i p l i n a r yt h e o r e t i c a la n d s y s t e m a t i cp r o j e c t 。w i t ht h er a p i dd e v e l o p m e n to fs p a c et e c h n o l o g y , o n t h eo n e h a n d ，i t c a nb r i n g ss t r o n gd a t at os u p p o r tt h ed i g i t a le a r t ha n de x p a n dt h en e wd e m a n d st oi t s f u n c t i o n s ；b u t ，o nt h eo t h e rh a n d ，i ta l s oc a u s e sa s e r i e so fp r o b l e m st ot h es y s t e m ，f o r e x a m p l e m a s s i v es p a t i a ld a t aw o n ta c h i e v et h er e q u i r e m e n to f r e a l - t i m ed i s p l a ya n d i n t e r a c t i o nw i t hl i m i t e ds y s t e mr e s o u r c ea n ds l o wl o a d i n g t l l i sm a i n l yn e e d st o i m p r o v ea c p e c t s o fd a t ao r g a n i z a t i o na n ds c h e d u l i n g ，s p a c e e f f i c i e n ti n d e x i n g ，d a t a c o m p r e s s i o nt e c h n o l o g ya n ds oo n a st ot h ep r o b l e m sb a s e do nt h ed e v e l o p m e n to fd i g i t a le a r t hs y s t e m ，t h i sa r t i c l e i st od i s c u s st h em a s s i v ei m a g ed a t e 、v e c t o rd a t as t r u c t u r e 、o r g a n i z a t i o n 、i n d e x i n g 、 a sw e l la st h ed i g i t a ls c e n es i m p l i f i e ds y s t e mm o d e li nt h ee a r t hs y s t e mf o r mt h e p e r s p e c t i v eo fd e t ap r o c e s s i n g ；f o c u s i n go nt h ed i g i t a le a r t hs p a c es c h e d u l i n gd a t a , v e c t o rd a t ac o m p r e s s i o nt e c h n o l o g ya n ds oo n 1 1 1 ea u t h o r sg r o u pt o g e t h e rw i t ht h e c h i n e s ea c a d e m yo fs c i e n c e si n s t i t u t eo fr e m o t es e n s i n ga p p l i c a t i o nr e s e a r c hc e n t e r f o rr e m o t es e n s i n ga r g u m e n tt or e s e a r c ha n dd e v e l o pat h r e e d i m e n s i o n a ld i g i t a l t e r r e s t r i a lp l a t f o r m ，r s g l o b e ，t om a k es u r et h er e a l t i m ev i s u a l i z a t i o nf o ro u rr e s o u r c e s s a t e l l i t e s m o d i sa n do t h e rs a t e l l i t e si ni n t e r n e te n v i r o n m e n t t h et h e o r y a n d a l g o r i t h m sb a s e do nt h i sp a p e rd e s c r i b e da n di n t e g r a t e dt or s g l o b e a c h i e v eg o o d r e s u l t s 1 1 1 ep a p e rp r e s e n t st h em a i nw o r k sa sf o l l o w s ： 1 ) i no r d e rt or e a l i z et h el o a d i n gl a r g ea m o u n t so fd a t aw h e nt h es y s t e mi s d i s p l a y i n gm u l t i r e s o l u t i o n 鲥d ，a n dt op r o v i d ec o n t i n u o u sr e a l - t i m e d a t a i ta l s ot o a n a l y s i st h et e c h n o l o g yo fr a s t e ri m a g ed a t ao ft h eh i e r a r c h i c a ls u b - b l o c k ，b a s e do nt h e t i l e sp y r a m i da n dt h el i n e a rq u a d t r e ed a t am o d e lt od e s i g nt h et a r g e tt i l e sa n dt i l e s s e a r c hr e q u e s td a t af o r e c a s tac o m b i n a t i o no fs c h e d u l i n gs t r a t e g i e s ，a n ds ot os o l v et h e d a t ai n t oa n ds u p p o r tt h es y s t e m m a i l w h i l e m a x i m u me x t e n tt om e e tt h e m u l t i r e s o l u t i o ni m a g ea n dr e a l t i m ed i s p l a y 2 ) i nr s g l o b e ，b e c a u s eo ft h ef o r mo fv e c t o rd a t ao r g a n i z a t i o n sc o m p l e x ，t h i s w i l lr e s u l tt os l o wd a t al o a d i n g ，i no r d e rt oa c h i e v ef a s ta n da c c u r a t es h o w e dt h a tm u s t b ec a r r i e do u tp r i o rt od a t ac o m p r e s s i o n n l i sp a p e rw i l lc o m p a r ew i t ht h et r a d i t i o n a l 河南大学硕士研究生学位论文第1 i i 页 v e c t o r - b a s e dd a t ac o m p r e s s i o na n di m p r o v et h et r a d i t i o n a ld o u g l a s - p e u c k e ra l g o r i t h m ， t o p o l o g i c a lr e l a t i o n sh a v em a i n t a i n e di nt h ee s t a b l i s h m e n to fe f f e c t i v eu s eo fm e t a d a t a i n d e xt a b l e ，r e s p e c t i v e l y , w h i l et h ep u b l i ca n dn o n - p u b l i cs i d ea r ec o m p r e s s e da n dt h e i n d e xt a b l et or e s t o r et h ec u r v eb e t w e e nt h et o p o l o g i c a ls t r u c t u r e ，a n di n t r o d u c e dt o i m p r o v et h ea l g o r i t h mu s e dt op a r t i t i o nc l o s e dc u r v es t a r t i n gp o i n ta n dd e s t i n a t i o n o p t i o n s t h ee x p e r i m e n t a lr e s u l t ss h o wt h a tt h ea l g o r i t h mi m p r o v e dt h ea c c u r a c yo f c o m p r e s s i o n , s t o r a g ec a p a c i t y , s y s t e ml o a dt i m e sa n do t h e ri m p o r t a n tf a c t o r s ，t h e e f f e c t i v em i t i g a t i o no ft h es c e n e si nr e a l t i m er o a m i n gd a t a l o a dd e m a n da n dt h e c o n t r a d i c t i o nb e t w e e nt o os l o w 3 ) i ti st oa c h i e v et h eo b j e c t i v e so ft h es e a r c ha n df i l e st i l e sf o r e c a s td a t ar e q u e s t s c h e d u l i n gac o m b i n a t i o no fm e t h o d sr s - g l o b es y s t e m ，a n dt oa c h i e v ei m p r o v e m e n t s i nt h ep r o p o s e dd pa l g o r i t h m ，n o to n l yt om e e tt h er e a l - t i m ed i s p l a yo fd a t an e e d e df o r s u p p o r tv e c t o rd a t aa n dt h ei n c r e a s e dl o a da n dd i s p l a ye f f i c i e n c y k e yw o r d s ：r s - g l o b e ；d a t as c h e d u l i n g ；v e c t o rd a t a ；d o u g l a s - p e u c k e r 关于学位论文独立完成和内容创新的声明 本人向河南大学提出博士学位中请。本人郑重声明：所呈交的学位论文是 本人在导师的指导下独立完成的，对所研究的课题有创造性的见解。据我所知。 除文中特别加以说明、标注和致谢的地方外论文中不包括其他人已经发表或 撰写过的研究成果。也不包括其他人为获得任何教育、科研机构的学位或证书 而使用过的材料。与我一同工作的同事对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位中请人 ) e l s e r e t u r n ； ) ) v o i dc h e c k t i l e s ( l 1 ) i f ( 钡t j 试链表三不为空) f o r ( 钡u 试链表三j 中瓦片) i f ( t i c 片与可见区域交叠) ， o 瓦片插入到测试链表l 2 ； 第2 6 页河南大学硕士研究生学位论文 e l s e 舍弃瓦片； ) ) e l s e r e t u r n ； ) 清空测试链表l ，； f o r ( 测试链表上口中瓦片) i f ( e 片满足分辨率要求) e l s e 瓦片四个分支插入到测试链表三j ； ) 清空测试链表l 2 ； v o i dc h e c k t i l e s ( l 1 ) ； 算法具体流程如图3 1 0 所示。 河南大学硕士研究生学位论文第2 7 页 图3 1 0 目标瓦片快速搜索算法 在算法当中包含两种瓦片测试：交叠测试和分辨率测试。交叠测试时，如果 瓦片四个角点中的任何一点在可见区域内，即表示该瓦片与可见区域交叠；分辨 率测试时，首先要计算四个角点的目标分辨率，如果此目标分辨率大于或等于瓦 片所处金字塔层的分辨率，则表示该瓦片满足分辨率要求，否则需要对其四个分 支的分辨率进行测试。如图3 1 1 所示，假设被测试瓦片的分辨率为2 ，由于瓦片左 上角点目标分辨率数值小于2 ，则必须对瓦片进行细分，然后再进行交叠测试和分 辨率测试，图a 中因为左上角分辨率小于2 ，必须进行细分，然后再进行交叠检测 和分辨率检测，图b 中因为所有四个角点都大于2 ，因而不再进行细分。 第2 8 页河南大学硕士研究生学位论文 2 2 2 3 图3 1 1 瓦片分辨率测试图解 上述目标瓦片搜索算法是一个递归过程。在进行分辨率测试时只需对瓦片的 四个角点进行测试，因此提高了效率。另外，瓦片的分支是从瓦片索引数组中提 取的，无需进行空间位置判断，只需计算出瓦片偏移量即可，这同样能够显著地 提高算法的效率。 3 3 3 瓦片数据请求预测 合适的数据缓冲机制可以提高系统的性能，海量地形实时可视化也不例外。 在r s g l o b e 系统中，如果当场景连续运动时，应用程序能够提前预测系统即将需 要的影像数据，并能提前从磁盘把这些数据读取到缓冲区，那么当应用程序真正 需要这些数据的时候，便可以直接从缓冲区中读取，从而省去了从磁盘读取这些 数据的时间。由于在海量地形漫游时，数据预测调度和场景绘制需要同时进行， 因此，我们利用操作系统的多线程能力，将数据预测调度和场景绘制分别采用两 个独立的线程来完成。 数据缓冲通