一种顾及属性的游程编码_交_运算方法与实验.pdf

第 25 卷?第 3 期2009年 5月地 理 与 地 理 信 息 科 学Geography and Geo-Information ScienceVol.25?No.3May 2009?收稿日期:2008-12-09;?修订日期:2009-01-05?基金项目:国家基础科学人才培养基金(J0630535)?作者简介:沈定涛(1983-),男,硕士研究生,主要研究方向为地理信息系统。E-mail:sdt2003 一种顾及属性的游程编码?交 运算方法与实验沈 定 涛,王 结 臣,陈 焱 明,于?庆(南京大学地理信息科学系,江苏 南京 210093)摘要:考虑到基于直接编码的栅格数据在计算效率和存储能力上的不足,提出一种便于代数操作的游程编码数据结构,以优化基于直接编码栅格数据的代数运算。介绍了基于该数据结构的游程?交 运算的实现方法,并在算法实现过程中完成游程属性的各种代数运算。算法实现思路为:将栅格场中任一行游程集合以链表的形式存储,将欲执行代数运算的新游程单元与对应栅格行游程集合执行游程?交 运算,并在插入删除游程结点的过程中完成属性值的代数运算。该算法通用性较强,在数据精度及计算效率方面比直接栅格编码方法具有优势。关键词:游程编码;栅格数据;?交 运算中图分类号:P208?文献标识码:A?文章编号:1672-0504(2009)03-0008-04?游程编码是一种重要的栅格数据压缩方法,广泛应用于 GIS 空间数据的压缩存储。现有的游程编码方法研究一般侧重于栅格数据的压缩、编码及解码等策略的实现与优化 1-3,基于游程编码数据结构的栅格运算则研究较少。基于栅格数据的运算主要是针对栅格单元的属性进行各种代数运算和逻辑运算,其运算过程简便,而游程编码既能高效的压缩栅格数据,又能保持栅格数据比较直观的优点。因此,若将二者有效地结合,在 GIS 空间分析中采用基于游程的运算,将兼具内存占用低、运算效率高的优点。基于游程的?交 运算是栅格代数运算中重要的运算方法之一,本文着重研究便于代数操作的游程编码数据结构以及?交 运算的实现方法。最后,以?交 运算在多边形叠置分析中的应用为例,表明游程的?交 运算应用于相关空间分析算法设计中,能有效地简化算法复杂性、提高算法效率。1?游程编码数据结构栅格数据结构是指将空间分割成规则的网格,在各个网格上给出相应的属性值来表示地理实体的一种数据组织形式 4。栅格数据显式地表达了各栅格单元的属性值信息,任一栅格单元的行列号则隐式地表达了该栅格单元的坐标信息。游程编码方法是逐行将相邻同值的网格合并,并记录合并后网格的值以及合并网格的长度,以此压缩栅格数据,消除数据间的冗余。常规的游程编码方法以一个二维数组表示游程,每个游程单元以一对数值表达,第一个值表示游程的属性,第二个值表示游程的长度 5,一行上每个游程的长度相加就等于该栅格场的列数。这种数据结构比较直观,能够有效的压缩栅格,解码也很容易,但在进行其他操作时相当不便。对于某游程单元,为了确定它的左右端点(该游程单元的起始列和终止列)在该行栅格中的位置,必须遍历该游程前所有游程,统计各游程的长度。王结臣等 6提出通过链表的方式存储游程单元,该游程单元不直接存储游程的长度,而是存储游程左右端点所在的列号以及指向下一游程的指针。通过一个行游程结构体将每行的游程串联起来,这样由每行的起点游程即可访问此行任一游程单元。在某栅格行上,只有地理实体跨过的栅格单元才会用游程表示,因此游程单元之间允许有?空隙 存在。但在该研究中,游程不带属性值,仅适于执行游程的合并运算,无法应用于更广泛的游程代数运算。考虑到很多 GIS 数据都带有属性信息,在很多空间分析算法中属性值也是一个重要的参照要素,因此,本文为每个游程单元加上属性信息。在算法实现过程中,并不是为每个游程单元显式地记录该属性值,而是为整个待处理数据建立一个属性值列表,并为各游程单元建立属性值索引,将游程单元与属性表对应的属性值联系起来,通过游程单元所在的属性表索引即可找到该游程对应的属性值。因此,本文设计了一种新的游程编码数据结构,用 C 语言描述如下:struct Run?Length_Node/游程结点?int Start,End;/游程起始列号、终止列号?Run?Length_Node*next;/下一游程地址指针?int AttributeIndex;/属性表索引;struct Run?Length _LINE/行游程链表?int Node_Num;/该行游程数量?Run?Length_Node*Begin,*End;/该行游程链表的起始和终止结点指针;2?游程?交 运算及其实现2.1?主要思路栅格代数运算有很多种,根据栅格属性数据的类型将采取不同的运算方式。该属性数据主要分为数字型和字符型两种,数字型数据一般采用?加、?减、?乘、?除 等运算,而字符型数据一般采用?AND、?OR、?NOT 等运算 4。直接栅格编码中这种代数运算易于实现,在统一的空间参照坐标系及栅格场下,只需将各栅格图层中位于同一网格位置的各层属性值执行代数运算即可。在游程编码下,这种代数运算则表现为图层之间游程单元的?交、?并、?差 运算。对于?交、?并、?差 的实现,一种简单的方式是将游程数据恢复为按照直接栅格编码序列进行运算,但是这样则失去意义,没有对栅格运算效率起到优化作用。因此,有必要建立一种基于直接游程编码的代数运算方法,该方法需要考虑各游程单元在栅格场中所代表的范围以及游程之间的位置关系,比直接栅格编码方法复杂得多。文献 6 中实现了游程的?并 运算,但是该研究中的游程没有考虑属性值,对于栅格数据的代数运算失去一般性。同时,考虑到游程的?交 运算具有更广泛的应用意义,本文着重研究?交 运算的实现。在算法应用中,栅格图层间这种游程?交 运算通常包含如下步骤:1)将各栅格图层数据转换为游程编码表示,若图层数据为矢量数据,则可通过矢栅转换直接转成游程编码形式;2)新建一个数组,该数组大小为栅格场的行数,每一元素为对应行的游程链表,初始状态下每个链表都为空;3)将上述每个图层中游程单元逐个插入该链表,执行?交 运算。基于游程的?交 运算思路描述如下:如图 1 所示,设栅格场上某行的游程集合为 A(以链表表示),A 中有两个游程单元(用深色表示),待插入游程链表 A 的游程单元为 a,则通过游程的?交 运算,游程链表 A 的游程单元将变为 5 个。可以看出,游程的?交 运算发生在单个游程插入到总栅格场上对应行游程链表的过程中,随着新游程单元的插入,不断执行游程?交 运算。游程?交 运算后行游程链表中出现的新游程主要分为两种,一种是待插入游程与原链表上游程部分重叠产生,另一种则是因待插入游程覆盖了原链表上的空隙,这些空隙也成为游程。行游程链表中任一游程的尾位于栅格场中的列号总是大于等于下一游程的头所在的列号,各游程的头尾所在的列号是以一种有序的形式存在。对于待插入的游程单元,已知其头尾位于栅格场中的列号,即可通过折半查找方法 7快速找到该列位于链表中的区间位置。因此,通过此方法可以快速找到游程集合中哪些游程单元与该游程单元有关系,并进行相应的处理。图 1?游程?交 运算示意Fig.1?The schematic diagram of intersectionoperation for run?length unit上述游程单元在执行?交 运算时即可进行属性值的各种运算,包括游程单元多重属性值相加,以及常规代数运算中属性值的?加、?减、?乘、?除 和?AND、?OR 运算等。通过在游程的插入过程中完成属性值的运算,因而游程的?交 运算通用性很强。为探讨一般性,本文在算法原理分析中以属性值相加为例,允许游程单元带多重属性,表示在执行?交 运算时该游程所占网格被多段游程所覆盖。2.2?实现方法在搜索待插入游程单元两端点位于游程链表中的区间位置时,本文作出如下规定:该端点的列号小于某游程起始列号,则端点位于该游程左边;若与起始列号相等,则端点位于游程左端点上;若该列号大于游程起始列号小于终止列号,则端点位于游程中间。其他类推,并将端点位于游程左端点上、中间和右端点上统称为位于游程上边。在不同的情形下,执行游程的?交 运算将产生完全不同的结果。鉴于这种空间位置组合的复杂性,为了详细分析游程的?交 运算,本文按待插入游程在游程链表中的位置总结出 8大类情形共 39 种?插入 方式(图 2)。表 1给出这 8 类情形的详细说明,情形 1 6 较简单,此时待插入游程所处的位置只与链表的头结点或尾结点有关。情形 7 中待插入游程只与行游程链表中处于中间位置的某一游程有覆盖关系,或者位于其左边。而情形 8中待插入游程则覆盖了游程链表中的多个游程单元,此时该游程的两端点位于链表中不同的游程单元区间。页9第第 3 期?沈定涛等:一种顾及属性的游程编码?交 运算方法与实验图 2?游程单元?交 运算的各种情形Fig.2?Types of run?length unit intersection operation表 1?游程单元?交 运算的 8 类情形Table 1?The eight types of run?length unit intersection operation序号行游程中游程个数图 2 对应方式类型描述10(1)当前行游程链表尚无游程结点2!1(2)待?插入 游程位于游程链表最左边3!1(3)待?插入 游程位于游程链表最右边41(4)游程链表只有一个结点,且待?插入 游程将该结点完全覆盖5!1(5)(10)待?插入 游程与游程链表第一个结点左部分重叠或落入该结点中6!1(11)(16)待?插入 游程与游程链表最后一个结点右部分重叠或落入该结点中7 1(17)(24)待?插入 游程单元的起始列和终止列都位于某一游程的左边或位于该游程上8 1(25)(39)待?插入 游程单元的起始列和终止列位于不同游程的左边或位于该游程上?假设当前栅格场中第 L 行的行游程链表为 A,有 N 个游程结点 Node1 NodeN,每个游程单元的起始列号和终止列号分别为 Starti和 Endi。现有一个新的游程单元 a 欲与 A 做?交 运算,设该结点的起始列号为 Start,终止列号为 End,通过折半查找Start 和 End 值可知该游程单元在行游程链表中的区间位置。针对 8 类不同的游程?插入 情况,判断游程单元 a 与游程集合 A 的?交 运算方式属于这39 种方式中的哪一种,作出相应处理。本文详细讨论情形 4 和情形 8,其他处理方式基本类似。在情形 4下行游程链表 A 中只有一个游程,且游程单元 a 将此游程单元完全覆盖,即 Start End1。通过游程的?交 运算,行游程链表 A 将有 3 个游程单元,除了已有的一个游程单元,还需在头和尾增加两个游程单元。这 3 个游程单元的起始列和终止列值分别为(Start,Start1)、(Start1,End1)、(End1,End),其中第 1 和第 3 个游程单元将具有游程单元 a 的属性值,而中间游程单元将带有多重属性值,即在原属性值下再加上游程单元 a 的属性值。算法设计时优先判断待插入游程是否满足 1 6的简单情形,当都不满足时,则需通过折半查找确定a 的两端点位于游程链表 A 中的位置,进而判断该插入方式是情形 7 还是情形 8。折半查找时在行游程链表中定位两个游程,待插入游程两端点分别位于这两个游程左边或上边,比较两游程单元所在的位置,如是同一游程单元则为情形 7,否则为情形 8。情形 7 中游程单元 a 只与链表中单个游程单元作?交 运算,与上述方法类似。在情形 8 中,假定游程单元 a 两端点分别定位到链表中的游程单元 i、j。如图 3 所示,结点 i 和 j 之间有 j-i-1 个结点,其中任一结点和前一结点之间的游程空隙必定都被待插入结点完全覆盖。算法设计中优先处理这种游程单元,这 j-i-1 个游程单元处理过程较简单,其只用增加待插入游程的属性;另外当游程单元与前一游程单元有空隙时,插入一个新的游程单元?填补 空隙,没有空隙的则忽略此操作。优先处理完这些结点后,再处理 i 和 j 两个游程单元,处理方式与上述方式类似。图 3?情形 8 示例Fig.3?An example of case eight3?实验测试根据数据类型的不同,往往将叠置分析分为基于矢量数据和基于栅格数据的叠置分析,前人对这两类算法进行了一定的研究。在矢量算法方面,薛胜等 8讨论了简单多边形数据结构和带拓扑关系多边形数据结构,并叙述了这两种类型多边形数据的并、交、差等叠置运算。谢忠等 9探讨了基于简单多边形结构下叠置分析中交运算的实现,并给出了线段求交、追踪以及多边形构建策略。耿协鹏等 10则提出了一种基于栅格数据的多重多边形数据叠置分析方法,并借助数据库技术实现各图层间属性数据的叠加。这两种数据类型下的叠置分析各有优缺点,矢量数据需执行弧段求交、拓扑重建等比较复杂的处理过程,而基于一般栅格数据的叠置分析则因计算过程中数据量大,受内存限制较明显。本文采用游程编码?交 运算实现图层间的多边形叠置分析,规避了矢量算法中复杂的计算过程;同时由于采用了游程数据结构,相对于直接栅格编码算法占用内存少且算法执行效率高。页10第?地 理 与 地 理 信 息 科 学?第 25 卷在叠置分析过程中,首先将两图层中多边形数据分别生成独立的游程集合,不同图层上的游程其属性类型不同,图层间多边形的叠置运算则表现为对应栅格行之间游程的?交 运算,在运算过程中执行属性类型的相加。该算法运算过程为:1)在统一的空间参照坐标系及格网系统中,将两个图层中的多边形数据栅格游程化,分别获得两个图层的游程集合。2)两个游程集合在对应的栅格行上进行游程的叠加,即执行上述游程?交 运算。3)将结果游程集合矢量化为多边形数据,并建立面与弧段之间的关系。对于游程编码数据的矢量化方法,目前有很多成熟的算法,如基于游程编码数据的边界追踪方法 11,12,本文不再赘述。为验证游程?交 运算的算法执行效率,本文采用多边形数据进行叠置分析测试,并从栅格行列数目与多边形数据量大小两方面进行比较,图 4 为两个多边形图层经叠置分析后的局部放大图。本测试环境中计算机配置为:奔腾 IV 1?86G CPU,1?0 GB内存,操作系统为 Windows XP Professional,程序设计采用 VC?6?0 实现。多边形数据的相关测试结果如表 2 和表 3 所示,表 2 中栅格行列数设定为 2万,表 3 中实验多边形大小分别为图层 1 上多边形 1万个,数据量大小 33?9 M,图层 2 上多边形 400 个,数据量大小 2?61 M。测试数据表明,通过游程编码下?交 运算实现多边形叠置算法,可以进一步提高直接栅格编码下算法的执行效率。当栅格行列数达到 10 万时,测试时间依然比较理想,相同数据量使用直接栅格编码算法很难达到理想结果。测试实验表明,算法执行效率不仅与多边形数据量大小有关,图 4?多边形叠置结果局部放大Fig.4?Local amplification of the polygon overlay result表 2?多边形数据量大小与测试时间关系Table 2?The relation between polygon quantity and test time图层1多边形数量/数据量图层2多边形数量/数据量叠置分析耗时(s)20/350 KB20/350 KB1.36178/695 KB10/315 KB4.39?10 000/33.9 MB400/2.61 MB18.540 000/135.04 MB10 000/33.9 MB71.25还受制于多边形的复杂程度。在数据量相当的情况下,多边形越复杂,算法耗时越长,这是因为复杂的多边形在栅格行上将产生更多?细碎 的游程单元。表 3?栅格行列数与测试时间关系Table 3?The relation between row and column number and test time网格行数网格列数叠置分析耗时(s)5 0005 0004.4510 00010 0008.9120 00020 00018.550 00050 00065.13100 000100 000111.254?结语与直接栅格编码相比,采用游程编码方法将降低算法设计中内存耗用,可以设定更高的网格密度,进一步提高数据精度。由于栅格行之间游程结构的独立性,可通过链表的方式存储每行的游程单元,任一行上游程的插入删除将变得较为容易。本文提出将这种链表结构用于实现游程的?交 运算,在该过程中完成游程单元之间的属性代数运算,实验表明该方法在耗用内存、执行效率方面优于直接栅格编码数据的运算。参考文献:1?LIN C F,CHUNG Y C,YANG D L.T RLE an efficient data com?pression scheme for image composition of volume rendering on dis?tributed memorymulti?computers J.Supercomputing,2007,3(29):321-345.2?HUR Y M.Test data compression using a hybrid run?length codemethod J.IEICE T ransactions on Information and Sy stems,2005,E88-D(7):1607-1609.3?RAVINDRA BABU T,NARASIMHA MURT Y M,AGRAW?AL V K.Classification of run?length encoded binary data J.T he Pattern Recognition Society,2007,40:321-323.4?黄杏元,马劲松,汤勤.地理信息系统概论(修订版)M.北京:高等教育出版社,2007.188-191.5?刘冰.游程长度编码算法的研究 J.天津理工学院学报,2001,17(4):77-81.6?王结臣,芮一康,刘杰.GIS 中面的游程编码表达、实现与应用 J.测绘科学,2007,23(6):778-784.7?徐士良.C 常用算法程序集 M.北京:清华大学出版社,1994.8?薛胜,潘懋,王勇.多边形叠置分析算法研究 J.计算机工程与应用,2003(2):57-60.9?谢忠,叶梓,吴亮.简单要素模型下多边形叠置分析算法 J.地理与地理信息科学,2007,23(3):19-23.10?耿协鹏,胡鹏,杨传勇.多重多边形叠置栅格算法 J.测绘工程,2006,15(1):34-37.11?谢顺平,都金康,王腊春,等.基于游程编码的 GIS 栅格数据矢量化方法 J.测绘学报,2004,33(4):323-327.12?QUEK F K H.An algorithm for the rapid computation ofboundaries of run?length encoded regions J.The Pattern Rec?ognition Society,2000,33:1637-1649.(下转第 15 页)页11第第 3 期?沈定涛等:一种顾及属性的游程编码?交 运算方法与实验查询效率。同时,该算法采用泛型编程实现,能自动适应 N 维空间索引,是一种具有通用性的空间索引算法。参考文献:1?GUTT MAN A.R?T rees:A dynamic index structure for spatialsearching A.Proc.ACM SIGM OD,Massachusetts,1984.47-57.2?SELL IS T,ROUSSOPOULOS N,FALOUT SOS C.The R+?T ree:A dynamic index for multi?dimensional objects A .VLDB,1987.507-518.3?BECKMANN N,KRIEGEL H P,SCHNEIDER R,et al.T heR*?Tree:An efficient and robust access method for points andrectangles A .Proceedings of ACM SIGMOD InternationalConference on M anagement of Data,1990.322-331.4?KAMEL I,FALOU TSOS C.On packing R?Trees A.Proc.2ndInternational Conference on Information and Knowledge Man?agement(CKIM-93),Arlington,VA,1993,12:490-499.5?LEUTEEGGER S T,LOPEZ M A,EDGINGT ON J M.ST R:Asimple and efficient algorithm for R?T ree packing A.Proceed?ings of the International Conference on Data Engineering,1997.603-611.6?TAEWON L,BONGKI M,SUKHO L.Bulk insertion for R?Treesby seeded clustering J.Data&Knowledge Engineering,2006,59(1):86-106.7?KAMEL I,FALOU TSOS C.Hilbert R?T ree:Improved R?T reeusing fractals A.BOCCA J B.Proceedings of the 20th Interna?tional Conference on Very Larg e Databases C.San Francisco:M organ Kaufmann Publishers Inc,1995.500-509.8?何珍文.地质空间三维动态建模关键技术研究 D.华中科技大学,2008.139-153.9?ZHU Q,GONG J,ZHANG Y T.An efficient 3D R?T ree spatialindex method for virtual geographic environments J.ISPRSJournal of Photogrammetry&Remote Sensing,2007,62(6):217-224.Bulk Construction Algorithm of Clustered Sorting Generics 3DR?TreeHE Zhen-wen(School of Earth Resources,China University of Geosciences,Wuhan430074,China)Abstract:A new 3DR?Tree construction techniques for 3D spatial index is proposed.T he main ideal of this algorithm is to makethe spatial objects that near to each other in spatial space in nearest leaf nodes,and to reduce the overlap among the spatial ob?jects#rectangles.Given a collection of multi?dimensional spatial objects with rectangles,all the spatial objects will be clusteredthem to K groups by distance relativity,and be sorted in the i?th(i 1,k)group,and then all the groups will be sorted by thegroup center points,and the R?T ree is built bottom?up at last.The experimental results show that the 3DR?T ree constructed bythis method outperforms the previously R?Tree methods in query efficiency and space utilization.Key words:spatial clustering;spatial sorting;3DR?Tree;spatial index(上接第 11 页)Implementation and Application of Intersection Operation Based on Run?Length Encoding DataSHEN Ding-tao,WANG Jie-chen,CHEN Yan-ming,YU Qing(Department of Geograp hic Inf ormation Science,N anj ing University,N anj ing 210093,China)Abstract:Considering that the direct encoding raster data has a deficiency on the computational efficiency and storage capacity,a new run?length encoding data structure which is suitable to the algebraic operations and can optimize the algebraic operationsbased on direct encoding raster data is proposed in this paper.The implementation of intersection operation based on this datastructure is discussed and the algebraic operations of the attributes are described.The idea of the algorithm is to store the run?length data set by the Linked?List in every raster line,the run?length unit which will execute the intersect operation is taken toexecute the intersect operation with the corresponding run?length data set in raster line,and the algebraic operations of the at?tributes is implemented when inserting and deleting the run?length unit.This algorithm is suitable to most raster operation,andhas an advantage in data precision and computational efficiency compared with direct encoding raster data algorithms.Key words:run?length encoding;raster data;intersection operation页15第第 3 期?何珍文:泛型聚类排序 3DR 树批量构建算法