应用于增强现实变电运检三维场景重建的增量八叉树算法

焦进，迟小羽，赖秋，杨子力，储园，杨坤莲，杨锐

1. 云南电网有限责任公司曲靖供电局，云南 曲靖 655000 2. 北京航空航天大学青岛研究院，山东 青岛 266100 3. 昆明埃舍尔科技有限公司，云南 昆明 650000

数字孪生，即物理场景被复制为大小和内容都完全一致的数字场景并加以应用的数字化技术，在如今的各行各业中已经得到了越来越广泛地应用[1]。一个标准的数字孪生模型构建过程是通过传感器、激光雷达和视觉等多种数字化手段对场景进行扫描和记录，利用点云或三维实体方式对记录后的数字场景进行重建和拼接，进而渲染重建结果并交互式地漫游浏览三维场景。在对数字场景进行预构建的过程中，可利用专有设备采集数据并通过长时间的预先处理来完成；对于终端用户直接参与检查和验收的三维渲染成果，它需要适配不同的用户设备，并满足用户对实时性和结果真实性的要求。

对于一些特定的行业应用需求，例如变电站的运行检查辅助系统，终端用户对于数字孪生场景的使用要求将更为苛刻。用户常常会使用AR。增强现实头盔(例如微软公司的Hololens)作为承载平台，在巡检实际物理场景的同时，叠加显示数字场景的内容并基于实际位置来显示虚拟的分析结果[2]。因此，在变电站数字场景的建立过程中需构建一种预处理场景分割策略，并且在实时渲染过程利用该策略对场景数据进行动态调度，将海量数据构成的数字场景高效地叠加显示在性能较低的实时图形平台上(例如AR 头盔显示屏幕)具有重要意义。

传统的场景分割方法，例如二叉树(binary space partitioning，BSP)算法、四叉树(quadtree)算法和八叉树(octree)算法，可以将任意大小的原始数据划分成基于空间坐标的树状场景结构，并且根据实时渲染的要求动态地改变树中节点加载和卸载的状态，从而调度当前数字内容的显示区域和细节[3]。但是传统算法的构建时间长，最终的生成结果数据量大，因此调度过程中的性能损失也大。在带有独立显卡支持的桌面PC 上，该问题通常可以被忽略；但在低存储量和低运算能力的AR 眼镜这类硬件设备上，其问题就变得很突出。

本文在传统八叉树场景分割算法的基础上，提出了一种改进的增量八叉树(incremental octree)算法，其树状节点更少，遍历检索的速度更快，并且非常适用于数字孪生扫描生成点云场景的渲染。

1 三维场景点云的扫描重建与分割算法

1.1 扫描重建的硬件设备与重建流程

三维场景的扫描重建过程通常需要用到以下3 种类型的硬件设备。

1.1.1 激光雷达

通过电机带动激光线束快速旋转，接触到物体表面后产生反射，计算激光线束的发射时间和反射线束的接收时间的差值，即可计算出每条线束到达物体的途经距离，进而得到激光在场景中扫描的实时距离列表，其示意图如图1 所示。

图1 多线雷达VLP-16 扫描的单帧结果

将每帧的激光扫描数据拼接在一起，即可得到三维扫描数字化的点云结果数据。为了得到足够丰富的场景细节，一般选用多线雷达(例如Velodyne VLP-16)，或者多台单线雷达(例如HOKUYO UTM-30LX)来完成扫描[4-6]。

1.1.2 高精度惯导定位设备

由全球导航卫星系统定位技术(global navigation satellite system，GNSS)和惯性测量单元(inertial measurement unit，IMU)六轴传感器共同构成的惯性导航定位设备，可以实时输出设备位置和姿态数据。将惯导定位设备与激光雷达固定在一起，即可得到每一帧激光数据的实时位置和姿态信息。当已知每一条激光线束检测的物体距离为Di、自身的旋转角度为Ai、高度为Hi，以及通过惯导定位得到的激光器中心坐标位置矩阵P0和姿态矩阵O0，即可得到该激光线束的世界坐标矩阵Pi为

由此可以实现激光扫描数据的自动拼接，进而直接得到完整的场景点云数据。设备的对齐和拼接精度越高，得到的扫描重建结果也就越理想。因此，这一过程中也可以结合多线雷达采集的实时数据，通过并发建图与定位(simultaneous localization and mapping，SLAM)算法、IMU 和GNSS系统结合计算得到更为精确的定位结果[7-8]。

1.1.3 全景相机

可以用2 个鱼眼镜头构成全景画面，或者用多个普通摄像头同步拍摄和拼接得到全景画面。

将全景相机、激光雷达和惯导定位设备固定在一起，可通过标定得到全景图片在三维空间中的位置和姿态信息。在点云扫描重建过程结束之后，通过后处理的方式将每张全景图片重新置入到拼接完成的点云场景当中，并计算每个点投影到全景图上的颜色，即可完成点云数据的着色过程[9]。着色完成后的点云场景如图2 所示。

图2 典型变电站三维重建后的点云场景

1.2 基于增量八叉树算法的场景预分割

完成数字场景点云重建和着色过程之后，通常得到的结果数据十分巨大(数千万点，甚至数百亿点)，且因为点云本身并不具备几何拓扑信息，因此难以直接对原始数据进行简化，或者在简化过程中丢失大量有价值的信息。

为便于对数字化场景进行检查和浏览，并能在AR 眼镜设备中对完整场景进行叠加显示和数据分析，本文提出了一种高效的点云场景调度算法。该算法主要包括点云场景预分割算法和点云场景分割后动态调度显示算法，可以流式处理数百亿点的原始数据，将它转换为金字塔结构并实时渲染输出到屏幕上，整个过程几乎不会产生冗余的中间数据。这一方法是目前传统的分割方案所不具备的。

点云场景预分割是将三维扫描重建得到的原始数据经过空间索引(spatial indexing)和入库操作，无损地转换成一种可以流式读取和显示的数据管理格式。在格式转换过程中采用一种增量八叉树的算法，其具体实现过程如下。

1)计算整个场景的包围立方体B0，并作为系统的根节点，将场景点云数量抽稀(thinning)简化到低于某个阈值K，并保存到一个新的点云集合P′；原始点云P需减去P′后传入下一级分割过程；

2)将B0在空间中沿着X、Y和Z这3 个轴向各进行一次切分，将得到8 个新的子节点；每个子节点都可表示为B1-x-y-z的形式，其中x、y和z的取值范围均为0 或1，即根节点沿着某个方向一分为二后，其中一个子节点的索引；对于每个B1-x-y-z子节点，首先获取对应包围体范围内的原始点云P1-x-y-z，将它抽稀到低于阈值K并保存为传递给下一级使用；

3)以此类推，再次对每个B1-∗节点进行切分，可以得到第三级的B2-x′-y′-z′子节点以及对应的抽稀点集合其中x′、y′和z′的取值范围均为[0，3]区间内的整数，具体的分割过程和子节点间的结构关系图如图3 所示。

图3 增量八叉树的基本数据结构

4)对于第n级的某个子节点Bn-x-y-z， 可以得出x、y和z的取值范围以及包围立方体的实际值为

式中x,y,z的取值均为[2n, 2n+1]。

5)每一级子节点的分割过程，视该子节点中传入的原始点云Pn而定，如果剩余点少于阈值K，那么该子节点不再被分割，即=Pn；否则，抽稀原始点为新的集合 ρ′

n，并继续执行下一级分割，传入下一级的点云集合为Pn-；

6)在分割过程中，记录所有的Bn-的映射关系，其可以保存为零散文件的形式，以便于通过网络传输，也可以保存到NOSQL 数据库中，便于统一管理、修改和快速复制。

通过以上的场景分割和空间索引得到的树结构，与经典八叉树结构没有明显的差异，因此可以直接使用经典八叉树的插入、查询和删除等操作方法。但使用经典八叉树进行三维点云场景的管理时，所有的实际三维点数据均保存在最末端的子节点Bn中，从B0到Bn-1的所有中间节点中，或者不保存任何数据，或者保存自身子节点中所有点云数据的抽稀结果。前一种八叉树结构是不均衡的，有大量的空节点存在导致资源浪费；后一种八叉树会产生许多新的数据，比原始数据量增大了数倍，造成了存储空间浪费，增加了对后续点云数据的分析处理难度。

为解决这些问题，本文构建了一种增量八叉树算法数据结构，在实时运行和浏览时，设计了一种增量式的动态调度流程。

2 场景点云在AR 眼镜环境中调度显示

2.1 基于视场的场景动态调度算法实现

目前，常见的AR 眼镜(例如Hololens)采用了微型投影方式将虚拟场景画面投射到镜片上，与人实际视野叠加形成增强现实的显示效果。当人们戴上AR 眼镜观察一个已经数字化的场景(例如变电站)时，如果期望物理场景和数字场景能够完全贴合在一起，需要预先知道一些参数:人所在位置的姿态矩阵M0，可以通过惯导定位系统实时获取；微型投影机的内参矩阵Mi(记录镜头畸变参数)、透视投影矩阵Mp(通过投影机视场角设置)，可以通过AR 眼镜的标定流程获得；窗口变换矩阵Mw，根据当前显示分辨率计算得到。因此，将点云场景投影到镜片上并与真实物理世界叠加时，每个点P到屏幕坐标P′的变换公式为

对于增量八叉树的结构，首先判断某一级节点Bn投影到镜片之后的显示大小，该方法可获取Bn的中心点PBn以及一个边界点PEn并将它们转换到屏幕坐标。如果PBn和PEn均位于屏幕范围之外，或者两者的距离值小于某个指定的阈值L，则当前节点和所有子节点均被剔除出渲染队列；否则，显示当前节点的点云内容，并继续遍历下一级子节点，判断是否可以显示。

边界点PEn的计算方法可分为多种，一种较为简单的方法是:首先从M0计算得到佩戴AR 眼镜的人头顶方向V0，然后取Bn的外界包围球的半径Rn，于是有

上述计算显示大小和动态裁减八叉树算法的计算速度快，适合在AR 眼镜这种低算力的环境中使用。整个八叉树裁减过程几乎对实时渲染的效率没有影响，并且裁减结束后每帧剩余的可渲染数据量可控；点云场景的密度分布符合人眼观察的自然规律，可以直接用于海量数字化成果的展示应用。

2.2 基于AR 眼镜视场的动态加载与卸载流程

传统的场景调度方案往往是针对游戏场景设计的，多个不同分辨率的场景地块被线性地输入到队列中，依次完成加载和显示操作。而本文的调度算法是通过动态遍历八叉树的方式来快速完成场景的调度，并且自动优先选取更靠近用户视野中心的区块进行加载和显示，从而更贴近实际的使用体验。

将经过增量八叉树预处理的点云数据复制到AR 眼镜中(或者通过网络服务器进行流式调度)，并且可以通过惯导定位或其他定位方案来精确计算AR 眼镜在空间中的位置和姿态，即可精确地实现数字点云场景实时渲染，并且与眼睛中所见的物理场景实现准确地叠加显示，在此基础上实现虚实结合的场景导航或数据分析和计算工作。

因为AR 眼镜自身的CPU/GPU 算力和内存空间均非常有限，所以无法一次性将所有点云数据加载到内存中渲染。因此，采取动态调度的方法，即每帧计算和加载当前视野可见的子节点数据，并卸载已经不在当前视野内的子节点；同时，还需要设置一个总体加载阈值，例如1 000 万点。如果当前已经加载的点数据超过了该阈值，则自动屏蔽所有其他的子节点数据，不再载入新的数据。通过这些参数的设置，即可实现海量数字点云数据在AR 眼镜中的动态调度显示，其具体执行过程为:

1)开始当前帧的渲染；

2)根据当前视角，遍历增量八叉树数据，判断BPn和BEn的数值，得到加载列表An和卸载列表Rn；

3)如果BPn和BEn均在视野之外，将当前子节点Bn加入到Rn；

4)如果BPn和BEn的距离小于阈值L，将当前子节点Bn加入到Rn；

5)如果都不满足，则当前子节点Bn加入到An，继续遍历Bn的子节点；

6)对于An中的每一个元素Ai:如果Ai已经被加载，则略过当前元素，否则加载Ai中的数据请求，渲染对应点云数据；

7)对于Rn中的每一个元素Ri:如果Ri没有被加载，则略过当前元素，否则卸载Ri中的数据，不再渲染对应点云数据；

8)继续遍历下一级子节点，自动补充到Rn中；

9)返回步骤1)，继续执行下一帧的渲染。

3 实验测试与结果分析

本文使用了Unity 引擎作为主要的算法实现和测试平台，并使用C#语言编写了动态调度和实时渲染程序。场景扫描重建的硬件设备包括1 台VLP-16 多线雷达(负责实时位置和姿态计算)、2 台HOKUYO 单线雷达、IMU 惯性传感器、全景相机和运算用的PC 机，如图4 所示。

图4 扫描重建测试所用的硬件设备

本文通过C++和ROS 系统来完成场景扫描重建和增量八叉树预处理过程，测试场景1 是一个办公室的室内场景，其扫描得到的原始数据点约为8 000 万，如图5 所示。

图5 办公室室内环境三维重建后的点云场景

测试场景2 是运检系统功能验证所用的变电站场景，占地大约600 m2，其扫描得到的原始数据点约为15 亿，如图2 所示。2 个测试场景均采用Laz 压缩格式来保存数据。它们的原始数据量经过空间索引后的数据量和构建空间索引所用的时间如表1 所示。

表1 场景空间索引所需的时间对比

从表1 中可以看出，采用增量八叉树方法构建的场景空间索引结构，其在数据量上比原始场景的数据增加幅度不超过20%(增加的数据量主要来自大量散碎的子节点文件存储时产生的磁盘碎片)。构建过程中没有抛弃或者新增任何点，因此可以直接替代原始场景数据用于分析等用途，或者无损转换为原始数据的版本。而本算法的主要缺点在于数据预处理的时间较长，这主要是因为现有点云抽样稀疏化算法所限[10]。整个构建过程需要遍历所有的原始数据，因此消耗了较多的时间。

测试场景1 的原始数据和增量八叉树场景数据，分别使用带集成显卡(Intel HD)的PC 机、带独立显卡GTX1070 的PC 机和Hololens 眼镜，每隔1 min 测量一次当前运行的帧速率，对比结果如图6 所示。

图6 场景1 实时调度和渲染的效率对比

从图6 中可以看出，当不进行优化时，直接渲染原始点云，在普通集成显卡PC 或者Hololens 端的渲染速率均低于10 f/s，即低于人眼可以感受到动画效果的最低帧速率，此时已经严重影响了场景浏览的效果，操作员无法继续执行其他工作；使用独立显卡渲染场景时帧速率稳定在30 f/s 左右，可以满足使用要求，但是对系统渲染资源的消耗较为严重。使用本文所述的增量八叉树算法进行调度后，Hololens 平台的渲染速度已经可以达到32 f/s 左右的水准，满足使用需要；而采用台式PC 进行渲染时，渲染速度可以达到60 f/s 甚至更高，达到了独立显卡渲染未优化点云速度的2 倍，完全满足场景显示和浏览的要求，并且大幅度节省了系统的渲染资源。

测试场景2 在不经过优化以及经过了增量八叉树优化之后的渲染效果对比如图7 所示，每隔1 min 测量一次当前运行的帧速率。

图7 场景2 实时调度和渲染的效率对比

从图7 中可以看出，如果直接渲染未优化的原始数据，无论在PC 端还是在Hololens 眼镜中都无法正常浏览测试场景2(变电站)的数据，这是因为数据量巨大，使用集成显卡的PC 和Hololens AR 眼镜端已经无法承载实时显示的要求，导致测试程序长时间未响应就直接退出；独立显卡系统虽然可以显示场景，但是帧速率接近于0，无法进行任何进一步的操作。而经过本文所述方法进行动态调度之后，该测试场景在包括AR 眼镜的多种工作平台上均可以正常运行，其中基于独立显卡的PC 端的渲染效率已经完全满足人眼和VR/AR环境下观看的需求，达到了80 f/s；而集成显卡和Hololens 端的渲染效率虽然稍差，但是也超过了25 f/s，在操作者看来是流畅的，因此可以满足变电站运检系统的应用需求。

对比测试场景1 和测试场景2，采用增量八叉树算法进行调度的结果，在渲染效率上均可以满足要求；并且随着场景数据量的增加，渲染效率并没有明显的下降趋势，这也进一步验证了本算法的可靠性和应用价值。

4 结论

1)本文提出了一种改进的空间索引算法，即增量八叉树算法。它可用于三维场景扫描重建后得到的海量点云数据的存储和显示，构建结果的数据量几乎没有增加，并且可以与原始数据进行无损转换。

2)利用空间索引的结果数据，本文还给出了一种基于视场的场景动态调度和渲染虚拟场景的方法，可以将数字化的虚拟场景与实际物理场景无缝叠加，并在AR 眼镜中进行显示，满足了各种行业数据监测和数据分析的需求。

目前，本文所述的方法还存在一定的不足之处，如场景构建所需时间过长、数据更新效率较低，无法选择更新指定区域的数据等。这与本文目前所采取的点云数据采样稀疏化的方式直接相关，在后续研究工作中可以引入一些更加高效的手段和方法，并通过并行计算的方法来同时处理多组子节点的生成过程，进一步提升运算效率和显示效果。