海量3D点云数据压缩与空间索引技术

赵尔平，刘 炜，党红恩

(西藏民族大学 信息工程学院，陕西 咸阳 712082)(*通信作者电子邮箱xdzep@163.com)

0 引言

真实旅游总会涉及体力运动、昂贵花费、烦心事情及危险[1]，虚拟旅游可以避免这些情况发生，人们足不出户就能漫游、沉浸和体验世界各地风景名胜，近年在国内外逐渐兴起。三维激光扫描技术作为一项成熟技术在很多领域被广泛应用，能够快速采集复杂、大型物体外表面数据，这些数据是由离散矢量距离点构成，俗称点云数据。点云数据实现物体重建是当前应用研究热点，并被广泛应用于建筑设计、虚拟旅游、城市规划、事故监测等领域[2]。虚拟旅游建模大都采用三维激光扫描仪采集不同场景表面大量密集点的三维坐标、激光反射强度、法线和颜色等信息，然后利用软件把它们重建为3D点云模型。旅游景点空间都比较大，而且一次大范围扫描运动产生出数十亿点样[3]，一个景点3D点云模型顶点数目一般可达百亿到万亿数量级，海量点云数据空间索引与压缩已成为大数据时代一个研究热点。

随着三维激光扫描技术在虚拟旅游、数字城市、地理信息系统领域广泛应用，海量点云大数据日益成倍增长，对其压缩变得越来越重要，压缩可以从源头减少数据总量，缓解系统资源瓶颈。虽然网格模型三维数据压缩技术已经比较成熟，但是3D点云模型数据压缩却是一个新研究领域，多数网格模型压缩算法不能直接用于点云数据压缩，然而一些压缩思想已被点云模型借鉴，例如平面抽取方法是从3D点云模型中检测并抽取若干平面，将属于某个平面的所有点按颜色相近划分若干群，然后提取每个群边界点构成凸壳，对凸壳进行德洛涅三角剖分，这些三角形中的点及颜色信息被最终保留[4]。Smith等[5]用移动立方体算法重构八叉树节点曲面，通过把低曲率面或扁平面冗余点进行修剪来压缩八叉树，其余重构面利用三角形三个点到子节点曲面的距离进行编码来进一步压缩八叉树节点重构面数据，文献[4-5]都借鉴了网格模型压缩思想，把点云数据形成的曲面进行剖分、重构后删除冗余点，压缩剩余点信息，它们都是有损压缩方法，它们在构建点云模型拓扑结构时增加额外开销。文献[6]利用八叉树迭代划分物体点云空间，每一层节点位置信息用所有子节点位置几何中心近似表示，节点的属性(法线和颜色)信息用子节点属性的平均值近似表示，该方法是一个无损渐进压缩方法。文献[7]根据特征分布把八叉树分成三个部分，每个部分按初始预给的概率模型进行独立压缩。Cohen等[8]利用八叉树按预设最小分辨率来划分点云模型，利用图像和视频编码技术的3D块预测和变换编码压缩点云属性方法。把点云数据三维坐标转化成莫顿码表示，计算相邻点莫顿码差值，对差值取以8为底对数来近似表示点坐标，直接减少莫顿码长度实现压缩[9]。Song等[10]采用最小二乘法的曲率估计算法计算八叉树模型中所有点曲率，如果某个点曲率变化小于阈值则删除相邻某点,达到数据压缩目的，但是八叉树迭代造成其中间层数据冗余，压缩率有限，不适合大规模虚拟旅游点云数据压缩。R树索引的3D点云数据压缩中间层不存在数据冗余，已有研究成果较少。Chovanec等[11]提出R树索引的可变长编码(Variable-Length Codes， VLC)无损压缩方法，对点的坐标和属性数据采用可变长编码压缩，但是VLC不适合大规模数据压缩。数据规模变大查询性能会大幅度降低，空间索引是解决它的有效途径。

R树是支持范围查询的多维空间索引结构，它的每个节点独占一个磁盘页面[12]，其中非叶节点索引记录为：(MBR, Child-Pointer)，叶节点索引记录为：(MBR, tuple-identifier)，MBR是节点拥有点数据的最小外接矩形(可扩展到高维空间)，Child-Pointer为指向孩子指针，tuple-identifier是空间对象标识。除根节点外每个节点最大索引记录个数称扇出(fan)。R树在对数级时间复杂度内支持窗域、邻域和最近邻域等的范围查询[13]，但是不能支持按点查询，因为R树仅维护多维数据边界框和指向实际数据的指针[14]。它是B树在多维空间扩展的高度平衡树，是基于空间区域匹配原理向下逐层搜索，最终获取叶节点外接立方体包围的空间对象，且被广泛应用于空间索引。

聚类排序R树(Clustered Sorting R-Tree， CSR-Tree)[15]和R树森林(R-Tree Forests， R-Forests)[16]都是基于不同方法在R树上改进的索引结构，目的是解决R树兄弟节点空间区域重叠造成多路查询问题，但是这两种索引结构更新、删除操作空间代价太高。基于维诺图R树(Voronoi diagrams R-Tree， VoR-Tree)[17]索引结构首先预构空间数据维诺图，R树每个叶节点存储这些维诺图，并存储该维诺图最近邻居指针，缩短最近邻域搜索时间，基于哈希索引R树(Perfect Hash base R-tree， PHR-Tree)[18]把两级哈希表集成到R树每个节点上，并为节点内部的点建立哈希索引，PHR-Tree既能按范围索引又能按点查询。不管是通过维诺图实现最近邻域搜索还是两级哈希表实现点云查询，由于辅助索引结构空间复杂度太高不适合海量点云数据。三维R树(3 Dimensional R-Tree， 3DRTree)[19]和空间数据多尺度R-Tree(Spatial Data Multi-scale R-Tree, SDMR)[20]利用R树不同层实现空间对象细节层次(Level Of Detail， LOD)索引，它们都缺乏数据冗余控制。

综上所述，八叉树管理的3D点云数据压缩虽然都是渐进压缩算法，但是在树的中间层形成不同分辨率的大量数据冗余，给本来海量的点云数据雪上加霜；大部分基于八叉树压缩方法都是有损压缩，对压缩率方面考虑较多，对数据精度与查询效率方面考虑较少；以上各种在R树基础上改进的索引结构由于自身或辅助索引结构复杂，数据精度损失过大，缺乏有效控制数据冗余，都不适合在无拓结构、离散、高精度、海量虚拟旅游3D数据中应用。本文针对虚拟旅游3D点云数据庞大特征和虚拟漫游特点提出R树管理的3D点云数据压缩与索引技术，即邻点数据差值渐进压缩方法和基于裁剪重叠区域进行冗余处理的R树空间索引技术。块内保存相邻点差值，以块为单位渐进压缩，从而实现流式传输，本次查询借助上次查询位置及区域直接从该区域边界开始在R树叶节点搜索，这样处理减少了数据源端输出数据总量和查询时间，再加之流式传输方式能够缓解虚拟漫游网络带宽压力。

1 点云数据压缩

1.1 3D模型空间剖分及点云数据除噪

3D模型中的点云噪声点是由于激光扫描仪在扫描过程中由于外界因素或在三维重建过程中造成少量稀疏离散点。噪声点之间距离或与非噪声点之间距离比较大，造成数据空间范围虚大，容易造成压缩结果失真和R树兄弟节点重叠，所以点云数据压缩前要清洗噪声点，使得R树叶节点包围盒边界较规整，点数据分布较均匀、密集，压缩率与精度较高，降低空间区域重叠概率。欧氏距离是欧氏空间中两点之间距离[21]，在八叉树叶节点局部空间利用点与其相邻各点欧氏距离期望值大于阈值δ的方法除噪,阈值δ是指立方体内所有点之间距离的均值，用八叉树叶节点立方体边长除以它所包含的点云总数计算，由于外包立方体可以用左上角(Xmin，Ymin，Zmin)和右下角(Xmax，Ymax，Zmax)坐标表示，δ值计算公式为：

δ=(Xmax-Xmin+Ymax-Ymin+Zmax-Zmin)/(3w)

(1)

其中：w表示外包立方体管理点云个数。点与其相邻点欧氏距离及期望值计算公式为：

(2)

(3)

为了避免R树兄弟节点空间区域重叠，引入八叉树对虚拟旅游模型进行空间剖分，八叉树剖分优势在于其快速收敛性，剖分结束条件为八叉树叶节点点云个数不大于R树叶节点管理的点云个数。3D点云模型被八叉树剖分后，点云数据按空间区域分布在不同叶节点立方体中，逐个读取八叉树叶节点数据，用式(1)计算该节点阈值δ，用式(2)、式(3)计算某点与邻域各点欧氏距离期望值，若E(D)远大于δ作为噪声点去除，以叶节点为单位的局部空间除噪能保证除去噪声点的准确性。

1.2 Morton码排序

一个3D点云由X、Y、Z浮点类型坐标和反射强度(Intensity)数据及整型颜色数据等组成，没有描述层次的语义信息，而且点云数据具有杂乱、无序特征，给数据压缩和空间索引带来极大挑战。文中压缩算法思想是借助相邻点云位置及特征具有相似性，对其数据差值进行压缩能够提高压缩率。压缩前需要对点数据进行排序，排序结果既要保证相邻点云数据线性有序而且空间位置相邻关系不能被破坏。由于位置坐标是三维数据，所以不能直接把它们作为关键词排序，但可以使用它们的莫尔顿编码(Morton)排序。莫尔顿码排序能将多维数据唯一映射到一维空间，不但把三维数据按线性关系排序而且能保留点云原始空间相邻关系[22]。莫尔顿编码通过把X、Y、Z坐标二进制数据每个bit位交叉组合实现编码。由于3D点云数据坐标是浮点类型，所以先要把浮点型转化为二进制表示，然后再进行编码排序，文中用Morton对每个八叉树叶节点内数据进行单独排序，使得虚拟旅游模型点云数据在局部空间内唯一有序。利用莫尔顿码对八叉树叶子节点管理的点云数据排序结果如图1所示，很显然莫尔顿码能使3D点数据按线性关系有序且保留了数据空间位置相邻关系。本文压缩算法是借助数据相邻关系对点云原始数据差值进行无损压缩，所以排序后的点坐标依然采用浮点数据类型表示。

图1 八叉树叶节点数据莫尔顿码排序示意图

1.3 有序数据分块

虚拟旅游3D点云数据海量，如果采用单分辨率压缩算法进行整体压缩，客户端就必须接收完整体数据后才能解压、渲染，这样压缩率不管有多高，网络资源也无法满足漫游时客户忍耐极限。若采用渐进压缩方法势必额外增加大量冗余数据，这种空间换时间的做法也不适合体积本来庞大3D数据，采用折中办法对海量点云数据按空间区域分成小块，按块进行压缩，以块数据流传输和解压。另一方面，点云数据分布在R树每个叶节点的若干个外接立方体中管理，叶节点通过索引记录管理外接立方体，间接管理点云数据，所以分块也便于为3D模型构建R树索引结构，但是分块后有可能重新造成某些块间空间区域重叠，影响R树查询性能，所以分块后必须进行去除块间区域重叠，运用定理1和推论1进行去重。

定理1 空间去重。V1，V2，…，Vi为立方体，任意二个Vi，Vj若存在Vi∩Vj≠∅，则必须合并操作，即Vi∪Vj=V′(其中1

推论1 空间去重。假设任意多个立方体存在Vi∩Vi+1≠∅，Vi+1∩Vi+2≠∅，…，则进行合并操作，即Vi∪Vi+1∪Vi+2=Vi′(其中1≤i≤fan)。

将1.2节已排序的每个八叉树叶节点均匀分块，分块结束条件为块数不大于R树扇出fan，由于R树每个节点独占一个磁盘页面，扇出fan计算公式为：

fan=Vdisk/Vrecord

(4)

其中：Vdisk为磁盘页面容量；Vrecord为叶节点一条索引记录所占字节数。计算每块数据覆盖区域最小立方体范围MBR1，MBR2，…，MBRi，MBR立方体范围用其左上角(Xmin，Ymin，Zmin)和右下角(Xmax，Ymax，Zmax)坐标表示，它们将作为R树叶节点外接立方体。这些分块可能存在空间区域重叠，需要利用定理1消除重叠，显而易见，由推论1可知，最坏情况下这些分块空间区域全部重叠，重新合并为一块，但是这种情况十分罕见。

1.4 计算邻点差值

文中采用算术编码方法压缩，算术编码是无损的熵编码方法。它把整个输入信息编码为一个小数n，n满足(0≤n<1.0)，适合于由相同的重复序列组成的数据，即被压缩符号中相同符号概率越高编码越短，压缩率越高，可以达到理论熵值[23]。物体局部特征相似性原理可知3D点云模型某个局部区域点的三维坐标、反射强度和颜色信息高度近似。由1.2节可知点云数据Morton码排序后没有破坏它们局部相邻关系，即局部特征相似性，表示它们空间位置的三维坐标、反射强度和颜色等数据都非常接近，差值数据中“0”出现频率较高。差值数据指Morton序列中相邻两个点的坐标、反射强度和颜色数据作差运算，即每个立方体除第一个点外其余点分别存储它们与前面点的坐标、反射轻度、颜色数据差值。由局部相似性原理可知差值数据中“0”出现频率较高，非常符合算术编码特点。由于Morton排序仅能保证局部点严格相邻，个别点存在跨空间区域现象，个别前、后相邻两个点在实际3D模型中空间位置并不相邻，如图1中的A点和B点在Morton排序中是前、后相邻关系，实际却处在3D模型中不同区域，那么B点和A点数据差值有可能比原数据大，包含“0”字符可能不会增加，但是下一个点与B点在Morton排序中相邻，也在模型空间相邻，而且从图1看到跨区域点仅占少数，不会影响整体压缩性能，利用算术编码对位置相邻两点数据差值压缩能使点云模型整体压缩率有较大提高。基于以上原因本文提出邻点差值渐进压缩(Adjacent Point Difference Progressive Compression, APDPC)方法。

1.5 邻点差值渐进压缩

虚拟旅游3D模型不仅数据量庞大而且空间区域跨度也特别大，网络带宽和系统资源的限制不允许一次性加载完数据再进行渲染、漫游。显然基于顺序流式传输方式是最佳选择，只需等待几秒钟加载数据就能解压、漫游，但是流式传输方式要求数据采用渐进压缩方式进行。3D模型所有渐进压缩算法都是典型的以数据冗余换取网络响应时间，先传输的粗糙模型都是冗余数据，对于海量3D点云数据不是长久之计，但是算术编码又是单分辨率压缩方式，要用单分辨率编码算法实现渐进压缩就必须把巨大3D模型拆分为许多较小独立块压缩，以1.3节中每个立方体块为单位编码压缩，这样只要一个立方体块数据传输结束就可以解压、渲染，同时传输下一块数据，周而复始实现渐进压缩算法的流式传输效果，并且无需增加额外冗余数据。逐个取每个立方体内点差值数据作为输入信源符号序列，设算术编码初始区间[LH)=[0 1)，当前区间为[lihi)，当前区间长度为rangei=hi-li，则符号编码公式为：

li+1=li+rangei×li+1

(5)

hi+1=li+rangei×hi+1

(6)

如果序列中某个符号出现频率越高，那么算术编码就越短，压缩效果就越好，由于差值数据中“0”符号出现概率非常大，邻点差值渐进压缩方法大幅度提高3D点云数据压缩率，而且能实现以块为单位流式传输，从数据源头解决海量虚拟旅游3D点云数据网络瓶颈问题。

2 点云数据空间索引

3D点云模型数据量特别庞大而查询数据集又相对特别小，查询效率不高一直困扰3D点云数据广泛应用，建立空间索引是提高查询效率关键，空间索引是按照对象位置、形状和空间关系的某种排列管理数据。有了索引查询就能依据查询条件(如立方体)快速搜索与查询区域相交的空间对象。众所周知R树是工业界常用的多维空间索引结构，例如Oracle数据库的企业版2007年实现基于R树的空间索引[24]，所以本文给虚拟旅游模型选择R树作为空间索引结构有理论和实践依据。

2.1 创建索引结构

虚拟旅游3D点云数量海量，为了减少时间开销采用静态批量加载方法构建R树索引结构。以八叉树叶节点数据作为批量加载单元，即批量有序读取1.5节数据块，计算它们对应空间最小立方体范围MBR1，MBR2，…，MBRi，利用它们构造R树叶节点每个外接立方体索引记录(MBR, tuple-identifier)。创建R树叶节点t，将所有索引记录批量有序插入叶节点t，若t中索引记录个数不大于fan/2，则这些数据块与八叉树下一个叶节点数据合并处理，数据批量插入前还要检查t的索引记录上线数是否大于扇出fan，若大于fan则先分裂叶节点t，然后在批量插入到新分裂的叶节点中。若t中索引记录个数大于fan/2，则将读取的所有数据批量插入磁盘数据区，为它们建立引用标识tuple-identifier，计算叶节点t的立方体范围MBRt，构造叶节点t的索引记录并插入其父节点。同样方法创建父节点、祖父节点……，同理也要进行索引记录数上、下限检查，这样既可保证R树兄弟节点空间不重叠又能保证磁盘页面使用率在1/2以上，如此重复，直到整棵R树创建完。利用八叉树对点云数据进行空间剖分、分块等预处理后再创建索引，既保证了R树兄弟节点空间区域不重叠，提高了查询性能，又保证点云数据能实现渐压缩，使其能按流式传输。

2.2 裁剪重叠区域的冗余处理技术

定理2 查询重叠区域裁剪。假设W1、W2为任意相邻两次查询请求窗口，且W1优于W2执行，其中W1∩W2=W，W2-W1∩W2=W′，若W≠∅则按W′在R树搜索空间区域交叉的子节点；否则按W2范围搜索R树子节点。

R树索引的查询是从根节点开始自上而下递归搜索与查询窗口交叉的子树节点，在叶节点上获取所有重叠外接立方体包围的空间对象[25]，下一次查询同理。由于在实际虚拟旅游或数字城市漫游过程中相邻两次漫游请求的查询窗口存在重叠是大概率事件，如果两次查询都按原窗口范围搜索空间对象必定会产生大量冗余数据，再次将这些冗余数据传输到客户端必将增加网络和客户端硬件资源开销，对网络带宽本来就紧缺的虚拟漫游系统无益有害。由于查询算法开销主要取决于访问I/O代价[26]，所以重叠区域查询会额外增加磁盘I/O开销，重叠区域必将造成查询效率低、冗余数据造成网络带宽开销等弊端。本文提出裁剪重叠区域的冗余处理技术，即利用上次查询范围，本次查询时首先根据定理2判断本次查询与上次查询是否存在重叠区域，若存在重叠区域，则通过空间运算进行裁剪，计算本次查询有效范围，去除重叠区域，然后按本次有效查询范围在R树搜索空间区域交叉的子节点，利用这些索引子节点定位到对应磁盘文件，获取本次查询的数据；若相邻两次查询窗口不存在重叠区域，则直接利用R树查询。查询结束时利用本次查询请求窗口值作更新上次范围，作为后续查询时窗口重叠判断依据。如图2所示相邻两次查询窗口A和窗口B，其中窗口A优先于窗口B执行，由定理2可知两次查询存在重叠区域为R23和R24，它们所包围的对象为冗余数据，查询时需要去除。裁剪重叠区域的冗余处理技术能够在索引树上获取有效索引，从而减少了查询时的I/O访问次数，如图2所示，相邻两次查询情况利用文中的冗余处理技术可以减少2次I/O访问，不但提高查询效率而且减轻了网络传输压力。

图2 R树与窗口查询交叉

2.3 基于R树点云查询

由1.2节3D点云排序、1.3节分块和去重叠处理、2.1节构建索引结构可知，R树叶节点每个立方体包围数据是有序的、空间区域相邻，并且漫游过程中相邻两次漫游窗口存在区域重叠是大概率事件，所以查询时要进行冗余查询处理，查询实现过程算法描述如下。

算法1 基于R树点云查询算法。

输入：查询窗口Wi点云模型D。

输出：满足条件点云数据Di。

W←Wi-1

while (Wi≠∅) do

{W′ ←W∩Wi

if(W′≠∅)

{W′ ←Wi-W∩Wi

Di← Query(W′RD)}

else

Di← Query(WiRD)

endif

W←Wi}

endwhile

outputDi

算法中的Query(WiRD)为基于R树3D点云数据查询函数。

3 实验结果与分析

利用TrimbleVX激光扫描仪采集不同场景3D点云数据，通过三维重建软件构建3D模型。实验环境是机器内存为8 GB，CPU 1.7 GHz，存盘页面为8 KB。主要测试压缩率、创建索引代价、查询性能、数据冗余率。实验效果与文献[11]基于R树的可变长编码(VLC)无损压缩方法和索引方法进行比较，因为VLC方法与本文提出邻点差值渐进压缩APDPC方法都是基于R树管理的点云数据压缩，且索引机制都是基于R树实现，具有可比性。

3.1 压缩性能比较

压缩率可以相对减少数据传输总量，因而可以缓解虚拟漫游网络传输瓶颈。随着近几年硬盘容量成倍增加，压缩目的主要是相对减少网络传输数据量，很少考虑硬盘空间利用率，所以把服务器端输出有效数据量作为数据压缩评价指标。压缩性能通过与文献[11]可变长编码VLC无损压缩方法比较，压缩性能测试结果如表1所示。本文的APDPC方法压缩率明显高于VLC方法，压缩率平均提高了26.61个百分点。由于本文APDPC方法是对立方体内相邻点云数据差值进行算术编码压缩，根据物体局部相似性原理和Morton码排序结果可知相邻点的三维坐标、属性数据值非常接近，所以它们差值中“0”字符出现概率相当大，此特性正是算术编码算法优势所在，VLC方法压缩前没有对3D点云数据进行分块、排序、计算差值等处理，直接压缩原始3D数据，所以APDPC方法比VLC方法有较高压缩率。由于不规则物体相邻两点数据逆值情况较多，如图1中A、B两点情况，所以压缩率低于规则物体。APDPC方法几乎不受数据量大小影响，VLC方法对数据规模较敏感，也正暴露可变长编码不适合大规模点云数据压缩弱点。

表1 APDPC方法压缩性能

3.2 创建索引开销

对于海量点云数据而言创建索引时间是一项重要性能指标，如果创建索引时间太长超出人们承受范围，再好的索引结构也无济于事，创建时间如图3所示。本文方法创建索引时间花费高于VLC方法，原因是为了防止R树兄弟节点空间重叠，创建索引前用八叉树对3D模型进行了空间剖分、Morton码排序、分块、计算邻点差值，压缩差值并构建R树，VLC方法直接压缩点云数据后就创建R树，所以本文创建索引结构时间开销大。图3显示创建索引时间会随数据量增大而增加，但是增加幅度不是跳跃式剧增而是在可承受范围内。创建这两种索引实质都是创建R树，只是创建过程中数据前期处理和组织方式不同而已，最终导致时间开销不同。

3.3 平均查询性能

平均查询性能是衡量一个索引结构最重要、最直观的指标，本文提出的裁剪重叠区域冗余处理技术目的在于减少查询时访问I/O次数，是对特定应用领域查询方式改进和优化，而文献[11]的方法完全是传统R树查询方式。实验设计Q1、Q2、Q3、Q4三类查询，测试平均查询性能，每次实验的三类查询选择相同区域，即MBR(Q1)=MBR(Q2)=MBR(Q3)=MBR(Q4)，但它们查询方式不同：Q1为一次窗口查询请求完成，Q2、Q3、Q4设计两次窗口查询请求完成，并且Q2、Q3两次查询窗口有重叠区域，Q3窗口重叠区域大于Q2，Q4两次查询窗口不相交，查询平均性能如图4所示，本文索引结构使平均查询性能提高了35.44%。图4显示在Q1查询中本文方法略优于文献[11]方法，原因是Q1查询是单窗口查询，本文方法与文献[11]方法都使用R树索引，但是本文构建索引前对数据进行空间划分、去除兄弟节点重叠、排序、分块等处理，3D模型在R树中分布均匀且数据压缩率高，所以查询开销小于文献[11]方法。Q2、Q3属于相邻二次窗口查询情况，由本文裁剪重叠区域的冗余处理技术可知Q2、Q3查询时先要进行冗余处理，使得Q3的查询代价大幅度减少，在文献[11]中Q2、Q3相邻查询开销和Q2、Q3分别独立查询开销几乎等价，所以文献[11]中Q2、Q3查询开销远大于本文方法。裁剪重叠区域冗余处理技术目的是剔除二次查询的重叠区域，最终减少访问磁盘I/O开销，即使Q3比Q2重叠区域大，重叠区域一样被裁剪，它们实际访问磁盘块数几乎是一样的，所以实验结果显示Q3与Q2查询时间几乎相等，实验证明相邻两次查询窗口不管重叠多少都能有效裁剪冗余查询，但是在实际漫游中重叠区域越大两次查询获得有效数据就越少，漫游越慢。Q4为无重叠窗口相邻两次查询，等价于Q1查询，但两次查询比一次查询开销要高，文献[11]方法也同理。在实际漫游中，请求窗口是否重叠，重叠区域大小因人而异。

图3 两种方法创建索引时间对比

图4 不同方法查询性能对比

3.4 冗余分析

对于庞大3D模型，查询方法的数据冗余也是重要性能指标。本文裁剪重叠区域冗余处理技术目的不仅是减少查询的I/O次数而且还控制查询时的数据冗余，创建R树前的空间剖分、局部Morton码排序、分块等处理都起到控制数据冗余作用，从数据源端缓解网络传输压力。按查询窗口重叠和不重叠两种情况测试，查询方法的数据冗余率为多次实验结果平均值，数据冗余率=I/O数据量-原数据量/原始数据量，测试结果如图5所示，本文方法查询时数据冗余平均减少了16.49%。两种情况下本文方法数据冗余率都非常低，进一步说明本文索引方法性能较高。漫游窗口不重叠时文献[11]方法数据冗余率也相对较低，但远高于本文方法，这是因为文献[11]方法构建R索引树前没有对3D模型空间剖分、分块和去除兄弟节点重叠预处理，重叠节点产生数据冗余较多。相邻两次窗口重叠情况下本文用了裁剪重叠区域冗余处理技术查询，而该方法裁剪了重叠窗口区域数据，几乎杜绝冗余数据产生，而文献[11]方法把重叠窗口区域查询了2次，所以数据冗余率明显大；而且数据冗余率总体趋势随重叠窗口增加而变大，但是非线性增大，这也说明虚拟旅游3D模型非均匀分布在R树空间，兄弟节点重叠情况也不均匀。

图5 不同查询方法数据冗余率对比

4 结语

网络带宽有限和3D点云数据海量制约着虚拟旅游畅通漫游和广泛发展，解决办法除了改进网络技术增加网络带宽外还可以利用本文提出的邻点差值渐进压缩方法和冗余处理技术从数据源头减少数据传输总量，并能支持按流式传输，可以从数据源端缓解带宽压力；利用本文提出的索引方法在查询时能有效减少非叶节点I/O访问次数，有效控制数据冗余，从而提高查询速度，缩短数据传输时间，但是系统运行中要不断维护上次查询信息，占用少量系统开销。实验证明本文提出压缩方法和索引结构非常高效，非常适合于虚拟旅游、数字城市等3D模型中的海量点云数据。

由于3D模型点云数据非常庞大，如果集中部署在一台机器上，即使对其采取优化措施，系统性能还是相对较低，如果将数据分块部署在多台机器上并行处理性能会更优。下一步研究工作将R树索引结构与分布式系统结合，例如与Hadoop或Spark平台结合把点云模型合理分块后分别部署在不同工作节点上，实现并行处理和多细节层次索引,提高点云数据查询与加载速度将是今后研究重点。

References)

[1] MIRK D, HLAVACS H. Virtual tourism with drones: experiments and lag compensation [C]// Proceedings of the First Workshop on Micro Aerial Vehicle Networks, Systems, and Applications for Civilian Use. New York: ACM, 2015: 40-45.

[2] NING X J, ZHANG X P, WANG Y H, et al. Segmentation of architecture shape information from 3D point cloud [C]// VRCAI09: Proceedings of the 8th International Conference on Virtual Reality Continuum and Its Applications in Industry. New York: ACM, 2009: 127-132.

[3] MERRY B, GAIN J, MARAIS P. Fast in-place binning of laser range-scanned point sets [J]. ACM Journal on Computing and Cultural Heritage, 2013, 6(3): 1-19.

[4] MORELL V, ORTS S, CAZORLA M, et al. Geometric 3D point cloud compression [J]. Pattern Recognition Letters, 2014, 50(2014):55-62.

[5] SMITH J, PETROVA G, SCHAEFER S. Full progressive encoding and compression of surfaces generated from point cloud data [J]. Computers & Graphics, 2012, 36(5):341-348.

[6] HUANG Y, PENG J L, KUO J, et al. A generic scheme for progressive point cloud coding [J]. IEEE Transactions on Visualization & Computer Graphics, 2008, 14(2): 440-453.

[7] CAI K Y, JIANG W F, MA T, et al. Probability model-adaptive coding of point clouds with octree decomposition [C]// Proceedings of SIGGRAPH Asia 2011 Posters. New York: ACM, 2011: Article No. 33.

[8] COHEN R A, TIAN D, VETRO A. Point cloud attribute compression using 3-D intra prediction and shape-adaptive transforms [C]// DCC’16: Proceedings of 2016 Data Compression Conference. Piscataway, NJ: IEEE, 2016: 141-150.

[9] DAI C Q, CHEN M, FANG X Y. Compression algorithm of 3D point cloud data based on octree [J]. The Open Automation and Control Systems Journal, 2015, 7(8): 879-883.

[10] SONG W W, CAI S L, YANG B, et al. A reduction method of three-dimensional point cloud [C]// BMEI2009: Proceedings of the 2009 2nd International Conference on Biomedical Engineering and Informatics. Piscataway, NJ: IEEE, 2009: 1-4.

[11] CHOVANEC P, KRATKY M, WALDER J. Lossless R-tree compression using variable-length codes[C]// Proceedings of the 5th International Conference for Internet Technology and Secured Transactions. Piscataway, NJ: IEEE, 2010: 1-8.

[12] GUTTMAN A. R-trees: a dynamic index structure for spatial searching [C]// SIGMOD’84: Proceedings of the 1984 ACM SIGMOD International Conference on Management of Data. New York: ACM, 1984: 47-57.

[13] CHALLA J S, GOYAL P, NIKHIL S. A concurrentk-NN search algorithm for R-tree [C]// Proceedings of the 8th Annual ACM India Conference. New York: ACM, 2015: 123-128.

[14] PATEL P, GARG D. Perfect hashing base R-tree for multiple queries [C]// Proceedings of 2014 IEEE International Advance Computing Conference. Piscataway, NJ: IEEE, 2014: 636-640.

[15] HE Z W, WU C L, WANG C. Clustered sorting R-tree: an index for multi-dimensional spatial objects [C]//ICNC2008: Proceedings of 2008 Fourth International Conference on Natural Computation. Piscataway, NJ: IEEE, 2008: 348-351.

[16] NOLEN M, LIN K I. Approximate high-dimensional nearest neighbor queries using R-forests [C]// Proceedings of the 17th International Database Engineering & Applications Symposium. New York: ACM, 2013: 48-57.

[17] SHARIFZADEH M, SHAHABI C. VoR-tree: R-trees with Voronoi diagrams for efficient processing of spatial nearest neighbor queries [C]// Proceedings of the 36th International Conference on Very Large Data Bases. Singapore: VLDB Endowment, 2010: 1231-1242.

[18] PATEL P, GARG D D. Perfect hashing base R-tree for multiple queries [C]// IACC2014: Proceedings of the 2014 IEEE International Advance Computing Conference. Piscataway, NJ: IEEE, 2014: 636-640.

[19] GONG J, ZHANG H W. A method for LOD generation of 3D city model based on extended 3D Rtree index [C]// FSKD2011: Proceedings of the 2011 Eighth International Conference on Fuzzy Systems and Knowledge Discovery. Piscataway, NJ: IEEE, 2011: 2004-2008.

[20] 邓红艳，武芳，翟仁健,等.一种用于空间数据多尺度表达的R树索引结构[J].计算机学报，2009,32(1):177-184.(DENG H Y, WU F, ZHAI R J, et al. R-tree index structure for multi-scale representation of spatial data [J]. Chinese Journal of Computers, 2009,32(1): 177-184.)

[21] DRAISMA J, HOROBE E, OTTAVIANI G. The Euclidean distance degree [C]// Proceedings of the 2014 Symposium on Symbolic-Numeric Computation. New York: ACM, 2014: 9-16.

[22] LEE K C, LE W C, ZHENG B H, et al. Z-SKY: an efficient skyline query processing framework based on Z-order [J]. The VLDB Journal, 2010, 19(3): 333-362.

[23] WITTEN I H, NEAL R M, CLEARY J G. Arithmetic coding for data compression [J]. Communications of the ACM, 1987, 30(6): 520-540.

[24] ZHANG R, QI J Z, STRADLING M, et al. Towards a painless index for spatial objects [J]. ACM Transactions on Database Systems, 2014, 39(3): 19-41.

[25] YI K. The priority R-tree [J]. SIGSPATIAL Special, 2012, 4(2): 8-12.

[26] 宋杰，李甜甜，朱志良，等.MapReduce连接查询的I/O代价研究[J].软件学报，2015,26(6):1438-1456.(SONG J, LI T T, ZHU Z L, et al. Research on I/O cost of MapReduce join [J]. Journal of Software, 2015, 26(6): 1438-1456.)

This work is partially supported by the National Natural Science Foundation of China (61762082), the Natural Science Foundation of Tibet (12KJZRYMY07).

ZHAOErping, born in 1976, M. S., associate professor. His research interests include database, data fusion.

LIUWei, born in 1978, Ph. D., associate professor. His research interests include database, geographic information system.

DANGHong’en, born in 1978, M. S., lecturer. His research interests include database.