基于分块ROAM算法的大规模路面点云重建

吴启芳　唐好选　顾海燕

摘 要：本文主要工作是根据车载激光获取的路面点云数据，在尽量保留路面特征的基础上，建立路面细节层次模型。通过对比相关技术，研究了基于分块的ROAM算法，实现了实时调度大规模路面点云并建模的工作。首先将点云数据通过内存映射读入内存，选取进行建模的初始点云数据，对建模数据进行分块，根据与视点的距离建立两个不同评价准则，建立二元三角树，实现了三维路面可视化及漫游，并利用文件数据动态更新显示的数据。实验结果表明，文中算法能够很好的处理大规模点云数据，并且能保留路面特征。

关键词： 路面重建；点云；细节层次

中图法分类号： TP391 文献标识码： A

Large-scale Point Cloud of Pavement Reconstruction based on Blocked ROAM Algorithm

WU Qifang1，TANG Haoxuan1，GU Haiyan1

1（School of Computer Science and Technology， Harbin Institute of Technology， Harbin 150001， China）

Abstract：The main work of this paper is to establish pavement level of detail model according to pavement surface point cloud data obtained by the vehicle—borne laser， based on retain pavement features as much as possible. Through the comparison of related technology， the paper analyzes the ROAM algorithm based on block， realizes the real-time scheduling and modeling of large-scale pavement point cloud. First the paper reads point cloud data into memory through memory mapped， then select the initial point cloud data modeling.After that， the modeling data are divided into blocks， and according to the distance from viewpoint two different evaluation criteria are set up. At last， establishes Triangle Bintree， achieves The 3D road visualization and the roaming，therefore uses the data dynamic to update data.The experimental results show that this algorithm can deal with large-scale point cloud data， and can keep the pavement characteristics.

Key words：Pavement Reconstruction； Point Cloud； Level of Detail

0 引言

随着我国国民经济的快速发展，交通运输行业也进入高速增长期，公路总里程等多项参数业已升至世界首位。与此同时人们对于公路的要求也日趋高端，其中良好的路况即尤显重要，为此就对公路养护提出了更高要求，而路面检测则是路面养护的一项基础性的首要研究工作。传统的路面检测方法主要是依靠人力，我国现今也普遍采用此方法，这种方式存在着诸如耗时长，耗费人力大，效率低下等一众缺点；另外，对于工作人员也存在一定安全问题，有时甚至会影响交通正常运行。为了保证通车道路的舒适安全运营，传统路面检测方法中的路面养护已经难于适应时下的整体经济发展，因此一种实时自动的道路路面检测系统即已成为迫切期待解决的重点攻关技术课题。

激光测量技术由于其具备了精度高、速度快、操作简单等优点，而在近年来获得了迅速发展，并已广泛用于文物复原、汽车制造等领域。将其装载到车体上形成车载移动测量系统则可进行大范围的地表测量、建筑物信息获取等支持性技术工作。并且由于车载移动测量可以精确、快速获取高分辨率的三维数据，近年来即已发展成为热门研究领域。相比于传统的道路检测方法，车载移动测量不仅速度快，而且安全、可靠，同时还可进行路面二次可视化，因此将其应用于路面检测及道路三维可视化等方面必将具有广阔的应用前景。

本文给出的车载移动测量系统主要是将激光传感器、CCD相机及PC机装载到车体上，通过在道路上行驶扫描路面进行高程信息及黑白图像信息的实时获取。同时，系统还具备在线数据监控和数据同步存储功能。

本文主要研究基于车载移动测量系统中的激光传感器获取的路面海量点云的细节层次的三维建模工作。

1 相关工作

目前，对路面激光检测方面也已开展有一些研究。Si-Jie Yu和Sreenivas在2007年推出一个为路面表面映射和检测的集成多模态传感器移动成像系统[1]。提出一种分两级处理的思想，粗略模型由第一个内插值和网格化得到，而详细的模型是经过输出基于保留尖锐特征和几何细节的平滑去噪算法而最终得到，从而在建模速度上实现了优质协调。2011年Kelvin[2]设计的系统将三维激光技术应用到路面建模中。采用线性激光，沿着车移动的横向方向，并通过激光的照射，再利用高度集中的窄激光束扫描路面表面，由此形成线性三维信息并存储。系统具有对环境不敏感的特点，无论白天或是夜晚都可以获得高质量的二维和三维信息。

国内马荣贵[3]通过对横断面和纵断面的数据进行分析得出路面相关参数，同时建立了路面网格模型。但是其研究更多侧重于路面相关指数的测量，而不要求建立并真实得出完备、完善的可漫游路面模型。

本文的工作是对获取的点云数据在尽量保留路面特征的基础上，建立路面细节层次模型。针对大规模激光点云的建模可分为基于不规则网格（TIN）[4]的建模和基于规则网格的建模两种。其中，针对基于TIN的点云重建主要是进行Delaunay三角剖分[5]；由于TIN网格顶点之间距离允许不同，因此以相同精度近似一个表面将需要更少的多边形，并且能够更确切地表示特征部分。但其缺点则是构建TIN需要大量的计算，因此，时间开销很大致使无法在交互时间内实时动态生成大规模网格模型，而且也无法与动态细节层次技术实现良好结合。与基于TIN的方法相比，基于规则网格的方法主要是应用四叉树[6]或二叉树[7]结构。虽然规则网格相对TIN产生的多边形较多，但是规则网格很容易建立细节层次。相对地四叉树要求数据尺寸满足 ，另外裂缝等的处理也比较复杂。而ROAM（实时优化自适应网格）[7]则主要是使用二叉树结构，通过维护一个分裂队列和一个合并队列实现网格表示。基于分块的ROAM算法首先是将点云整个数据模型完成分块，然后对每一块单独进行网格化。基于分块的ROAM[8]算法能够很方便地进行数据交换，对建模尺寸要求也并不严格，适合于公路等狭长模型重构。下文即将重点介绍该算法的主要思想及其具体实现时算法的改进和优化。

2 算法

算法主要是依据分块的ROAM算法，同时为了更好地应用在路面点云数据上而相应增加了数据调度模块，在评价准则方面为了更精确地表达路面特征也进行了一定的修改。具体算法实现需要通过如下步骤：

（1）加载获取的路面点云文件；

（2）将一定量初始数据与整个场景类相关联，对整个场景数据进行分块，并对每一块进行初始化；

（3）递归计算整个场景模型的基于变差的粗糙度；

（4）对每一个块进行网格近似，即根据两种不同评价标准判断是否分裂三角形，建立二元三角树；

（5）遍历二元三角树结构并将树的叶子节点所表示的三角形送入图形管道进行渲染。

（6）更新对应块数据，同时更新节点变差。

（7）重复（4）、（5）、（6）直到所有数据绘制完成。

2.1 基于分块的海量数据调度策略

本文的车载系统所使用的激光传感器每秒钟采集的点云数据可以达到数百万个，针对路面检测系统持续工作一天，点云文件的数据量将累积至非常巨大。针对如此海量的路面三维数据进行漫游，根本无法一次应用全部数据进行建模。然而，根据视点动态更新数据，并且如果每次都进行读外存操作其时间效率不高。因此针对点云数据规模庞大与内存规格限制、计算能力有限的矛盾问题，研究提出一种可行的方法是分步调入海量的数据，内存映射文件就是基于这一思想的技术实现。

内存映射文件是将一个文件与一块内存建立映射关系，这也是windows的一个内存管理方法。内存映射文件对于管理大尺寸文件具有实效显著优势。

对于激光获取的数据是规则的扫描线点云，根据分块的思想将数据映射区中的前n条扫描线作为首次建模的数据，对其进行分块，研究选择每个子块大小为64*64个激光点，相邻的子块共享边界点。为了达到动态显示路面模型的目的，需要对数据进行不断更新，使得每一帧渲染的路面场景均呈动态变化，若干连续帧将整个路面全部渲染完成，因此，伴随视点的前移，要不断对场景模型数据块中数据进行动态更新。数据动态加载模型如图1所示。

针对路面扫描数据的宽度是固定不变的，在沿着公路延伸方向漫游过程中，视点随时间变化，数据的更替只发生在路面里程方向，而路面宽度方向上数据不会发生更新。因此要完成整个高程数据文件的漫游，只需要将基于路面横断面的数据动态调入和调出即可完成所有路面状况的浏览。另一方面本文的算法是分块的，这就为数据调度提供了另一便利条件。具体的实现方法则是根据视线方向移动块偏移量动态调度数据。漫游纵向移动块偏移量为：

（1）

其中， 为视点位置， 为路面场景大小， 为初始视点与场景间的纵轴距离， 为块边长，初始状态时：

（2）

场景实际更新纵向块的位置计算方法为： （3）

其中 为场景的纵向的标号， 为场景纵向的块数。随着视点移动过程中，块偏移量改变，同时就更新相应块数据， 所对应的横断面的所有块都要更新。

算法实际建模时，对应大小为8*16块的长方形，其中的8*15块用于处理显示模型的数据，另外的8*1块用于更新新数据，伴随视点移动循环。如图1中所示，显示了视线向前移动时数据的加载过程。填充方块为第一帧缓存区，浅灰色为屏幕绘制的块如图中虚线框所示，深灰色为数据更新块，下一帧更新块显示在空白块位置，依次循环，直到所有数据加载完成。当整个文件的数据加载完成时，数据将不会再进行更新，这时若沿着公路延伸方向的漫游只会变成最后一个场景的循环显示模型。

2.2 二元三角树

ROAM算法使用二元三角树结构记录三角形的x、y、z坐标，并由此来表示网格。这种结构相当于将整个场景切割为一块一块的小三角形，原始的正方形块所分成的两个三角形则作为二元三角树的根节点。利用这种逻辑方式存储顶点，ROAM针对每个三角形均能节省超过36字节的RAM，如此高效的坐标计算即可作为渲染步骤的一部分。

ROAM算法分为两个关键阶段，建立树阶段和遍历树阶段。建立树的过程与四叉树算法类似，也是自顶向下的。首先对每一个块分成两个最初的等腰直角三角形，作为两个二元三角树根节点，然后连接直角顶点和斜边的中点形成树的新节点，不断递归并为二元树添加孩子节点，直至达到研究需要的细节层次。树的子孙层次越多，整个场景就越庞大，就可以通过简单扩大树的规模来近似区域的细节。图2显示了二元三角树从0层到～3层的细分过程。

二元三角树中，每个三角形对其相邻三角形通过邻居关系逻辑上可见。也就是对于一个三角形节点，可以通过三角形节点的数据结构找到每条边的邻接三角形。二元三角树的每个节点上下层之间可见，也就是可以通过父三角形找到分裂得到的子三角形，反之亦然。因此考虑到分裂过程的传递性，二元三角树应能为ROAM算法维护节点所需的邻居关系和子孙关系，因此被剖分的三角形结构定义为：

struct BTriNode

{

BTriNode *left_child；

BTriNode *right_child；

BTriNode *base_neigh；

BTriNode *left_neigh；

BTriNode *right_neigh；

}；

数据结构中的指针left_child，right_child分别指向左、右孩子三角形，指针left_neigh，right_neigh，base_neigh分别指向左、右和底部邻接三角形。当进行节点分裂操作时首先需从已分配的二元三角树节点池中取出两个BTriNode，作为当前节点的孩子节点，调整各三角形节点指针，建立邻居及父子关系。

如图3所示灰色三角形节点的五个成员。其中，灰色三角形与base_neigh指针所指向的三角形成为一种diamond结构。对于一个三角形与邻居三角形只能有三种关系：同一级别，更精细级别和更粗糙级别。而ROAM充分利用邻接指针，防止了可能出现的裂缝问题。下面具体介绍算法如何在分裂三角形时防止裂缝的出现。

三角形分裂有一个原则：当前节点和斜边邻居节点base_neigh指针必须互相指向彼此。当分割遇到一个三角形的斜边邻接的三角形节点存在并且斜边邻接的三角形节点的base_neigh指针不指向自己时，就要强制分割底部邻接节点。具体来说，如图4灰色三角形需要分割，直角与斜边中心相连生成细分的孩子节点三角形，由于灰色三角形斜边中点位置的实际高程与斜边邻接的三角形的相应位置由插值得到的高程存在差异，造成渲染两个邻接的三角形产生缝隙，即T型裂缝。处理方法是对产生T型裂缝位置对应的节点强制要求分割，递归强制分割直到满足不产生T型裂缝的要求。强制分割三角形效果如图4所示。

在完成建立二元三角树后，第二阶段就是对二元三角树进行渲染，此阶段中遍历二元三角树的同时进行渲染树的叶子节点作为实际的三角形绘制到屏幕上。遍历二元树的步骤与建立二元树方法类似，只是建立二元树根据评价准则决定节点分裂与否而产生递归，渲染时则根据之前产生的子节点关系产生递归。整个二元三角树遍历完成，即可完成整个场景模型的网格化工作。下一节将介绍三角形分裂与否的双重评价标准。

2.3 评价标准

基于四叉树的算法[6]根据由细分新引入节点的高程变化来评价粗糙度，也就是近似网格时的可视化误差。节点变差是另一种描述网格模型的粗糙程度的方法，ROAM算法采用此方法。树中某个节点的局部变差就是由于分裂这个节点而改变的该三角形的斜边中点的高度值，简单说来就是当前二元三角形插值高程与实际高程的距离，大小为斜边中点的插值高度减去在高程数据位置的实际高度的值：

（3）

如果对每个节点只计算二元三角树的当前节点的变差，那么误差将会很大。为了精确地估计粗糙度，树中所有节点的实际变差即取为局部变差、左孩子节点变差及右孩子节点变差三者的最大值，也就是：

（4）

节点变差结构上也是一棵二叉树，但是存储在一个连续地址空间，如图5所示。每个块对应两个变差树，分别表示块的左右二元树。如果建模数据不发生变化，得到的变差不用重新计算。针对研究中的路面数据海量的特征，采取了动态更新数据块的机制，每次当建模数据发生变化时，就要对变化的建模数据重新计算变差，并更新变差数组。当数据完成更新后，则要将横向更新的8块数据块的变差进行重新计算，渲染新场景时即根据新计算的变差建立新的二元三角树。

为了更好地显示路面的裂缝、凹凸等特征，同时提高场景每秒渲染的帧数，本文舍弃分块ROAM算法的单一的评价标准，而是根据与视点距离远近使用了两种评价标准：对于距离视点小于一定距离的数据块，只根据路面的粗糙程度，即变差来评价是否细分；距离视点大于一定距离的块将综合考虑节点变差和视距两个因素，即第二个综合评价标准为：

（5）

其中， 为块到视点距离， 为粗糙度变差， 为调节常量，如果节点满足 ，则该二元三角树节点需要进行分裂，否则不分裂。视点距离的计算方法可表述为视点到块中心点的距离。具体地，图6则为使用原ROAM算法的单一评价标准的建模效果。图7即为综合考虑两种评价标准的ROAM算法建模效果。

根据实验效果图可以发现，利用综合评价标准使得离视点近的场景可以不考虑视点距离的影响，而只受路面本身的粗糙程度的影响，由此建立的路面漫游模型更能现实全面地表现路面特征。算法的这一特性也必将有助于系统使用者更能方便的观察路面的实际变况，如路面的裂缝、突起和凹陷等。

3 实验结果与结论分析

为了对算法进行验证，实验数据使用le 加拿大的三维传感器公司LMI的Gocator2380激光传感器获取的点云数据。实验环境为IBM system x3650 m4服务器，Intel Xeon处理器，96G内存。

实验数据建模时第一个评价标准变差设为2，即路面二元三角树节点粗糙度大于2的块需要进行细分。变差大小的设置可以控制系统漫游时肉眼能够看见的最小路面特征。对于离视点远的块需综合考虑视距和粗糙度，为此基于选择的实验数据进行实验，发现当第二个评价标准调节常量选择0.1，m选择800时，能够将粗糙度特别大的区域基本显示，而与此同时屏幕的突跳也并不明显。如果将变差设置较大，模型显示时就会丢失路面的特征，设置过小则会导致需要渲染的三角形过多，以致于画面不连续或者缓冲区溢出。综上所述，实际应用中变差大小的选择要根据路面粗糙程度动态变化。图8即为文中算法对512*1 536的数据进行动态建模的效果图。

图8 本算法对模拟特征路面的建模效果图

Fig.8 The simulation results of the road map

基于四叉树的算法对数据尺寸要求较为严格，如Stefan R?ttger的算法，而基于分块的算法对数据却没有必须是正方形区域的要求。这种特性使得基于分块的ROAM算法更加适合应用于呈狭长的带状物的建模。此外，基于分块的ROAM算法在数据更新上也更容易实现。基于四叉树的路面建模实验显示了对于路面特征尺寸小于当前四叉树分割节点的尺寸时，特征容易丢失，即便此特征非常重要也同样面临这一风险。如一个很短但是很深的裂缝就存在丢失的危险。但ROAM粗糙度评价标准是基于递归建立起来的，因此上就不存在丢失此类特征的可能。结合路面建模要求，基于分块ROAM算法实现路面三维建模即具有的现实应用更大优势。

本文的移动测量系统具有多个激光传感器和CCD相机，激光传感器工作频率为2KHZ，横向分辨率1.9毫米，每个激光传感器横向覆盖宽度为1米，四个传感器覆盖4米宽路面。CCD相机传感器运行频率为20KHZ，汽车的行驶速度为80KM/H。系统1秒钟产生的高程点云数据为8M，系统运行一天产生的数据量就会达到几千兆字节，加之更显可观的纹理影像数据，若针对如此规模数据实现可视化漫游，就要将细节层次技术和数据调度方法应用到建模过程中。

本文主要目的是对车载移动测量系统采集的激光数据进行三维重建，使用并改进了ROAM算法。实验表明，利用本算法重建的三维路面模型能够有效地保留路面特征，同时也可以实现对大规模点云数据的漫游操作。

4 结束语

我国路面总里程长，分布范围广，如果只是通过人工测量，其工作效率必然低下，也将难以满足社会的良性发展需求，因此，本文对路面检测及路面激光点云的三维重建进行了一些新尝试，为未来工作提供参考。

参考文献：

[1] YU S， SUKUMAR S R， KOSCHAN A F， et al. 3D reconstruction of road surfaces using an integrated multi-sensory approach[J]. Optics & Lasers in Engineering， 2007， 45：808–818.

[2] WANG K C P. Elements of automated survey of pavements and a 3D methodology [J]， Journal of Modern Transportation， 2011， 19（1）：51-57.

[3] 马荣贵.路面三维检测系统原理及方法研究[D].西安：长安大学，2008.

[4] 黄雄， 刘学军. 基于TIN的公路三维表面模型建立方法[J]. 现代测绘， 2006， 29（2）：6-8.

[5] 徐青，常歌，杨力.基于自适应分块的TIN三角网建立算法[J].中国图像图形学报，2000， 5（6）：461-465.

[6] R?TTGER S， HEIDRICH W， SEIDEL H， et al. Real-Time Generation of Continuous Levels of Detail for Height Fields[J]. Proc Wscg98， 2001，6：315-322.

[7] DUCHAINEAU M， WOLINSKY M， SIGETI D E， et al. ROAMing Terrain： Real-time Optimally Adapting Meshes[C]//Visualization97， Proceedings， Phoenix， AZ， USA：IEEE， 1997：81 - 88.

[8] Turner B. Real-Time Dynamic Level of Detail Terrain Rendering with ROAM. http：//www.gamasutra.com/view/feature/3188/realtime_dynamic_level_of_detail_.php