基于斐波那契采样的三维线云模型平面提取算法

武 凯 周佳新 程章林

1(中国科学院深圳先进技术研究院 深圳 518055)

2(中国科学院大学计算机科学与技术学院 北京 100049)

1 引 言

近年来，随着虚拟现实和图形学的发展，三维场景模型在智慧城市、三维地图导航和文娱生活等场景中都具有广泛的应用，因而吸引了大量学者对其进行研究[1-4]。在城市场景三维重建中，由于平面是构成最终多面体几何模型中十分重要的元素，因此平面提取是解决城市场景三维重建的重要环节之一。

平面提取是从已采集的三维数据中提取可能存在的平面。其中，传统的方法(主要对点云模型进行处理)主要包括基于随机抽样一致(Random Sample Consensus，RANSAC)的平面拟合算法[5-6]、基于数据之间相似性的区域增长算法[7-8]以及基于霍夫变换[9-10]的平面拟合算法。由于点云具有数据量庞大、噪声繁杂等特性，基于点云的平面提取算法往往耗时较长，且精准性较差。目前，城市场景三维重建中的研究对象主要是一些规则的物体[11]，如城市中的建筑物通常是由规则的边线构成，通过观察分析这些边线就能推断整个建筑物的整体形状。线云的概念和点云类似，是由若干线段构成的集合。相较于使用点云数据，三维线段是比点更高一级的几何图元数据，不仅包含位置信息，还含有三维点所不能表示的方向信息。此外，同等场景下线云数据的量级比点云数据小。因此，合理地利用线段信息能够减少平面提取的难度，提高平面提取的效率和精度。

鉴于线云具有数据量小、蕴含信息量大等优势，近年来，研究人员逐渐将研究重点转向获取三维线云数据[12-15]，并开始研究基于线云数据的三维重建算法[16-17]。然而，目前基于三维线云进行平面提取的方法较少。虽然可以类比点云的平面提取算法进行实现，但是这些方法都具有一定的局限性。例如，与基于区域增长的算法依赖初始种子的选取以及需要相对稠密的数据相反，基于 RANSAC 的平面提取方法适合使用稀疏数据。但因该方法使用随机采样，较为依赖采样次数且随机性较大导致结果的精度不够。基于霍夫变换的方法先将原始数据投影到霍夫空间，使真实空间中的一个平面映射至霍夫空间中的一个点，然后利用投票机制确定平面的参数。由于每个平面的参数有较大差异，难以确定该方法的参数空间的范围且网格划分也比较困难。以极坐标表示的霍夫空间，虽然能有效缩减范围，但仍难以均匀划分空间。

针对以上基于三维线云的平面提取算法存在的问题，本文提出一种新的基于线云数据的平面提取算法。主要步骤包括：首先，将输入线云的每条线段映射成高斯球面上的一个点；其次，使用螺旋曲线斐波那契采样对高斯球表面空间做近似均匀采样，并对过球心的平面进行拟合；然后，根据平面方程的截距信息分离出平行的平面并使用奇异值分解修正采样造成的误差；最终，迭代拟合出所有可能存在的平面。该方法具有两个创新点：(1)将线云提取平面的问题转换为高斯球表面空间的采样问题，简化了问题的复杂性；(2)在高斯球表面使用螺旋曲线斐波那契采样，使采样空间分布更加均匀，提高了最终平面提取的质量。

2 相关工作

根据三维数据的输入源分类，平面拟合的算法可以分为基于点云模型的平面提取算法和基于线云模型的平面提取算法。

2.1 基于点云模型的平面提取算法

基于 RANSAC 的平面提取算法首先随机采样可以构成平面的点；然后计算其余点到该平面的距离，统计距离小于一定阈值的点并将这些点归类于该平面，随后计算最终平面上点的数量。经过多次迭代，选出具有点数最多的平面作为新拟合的平面。之后，继续在剩余的数据中迭代拟合其他平面，直至达到终止条件。该方法在选择合适的参数下能够得到较好的结果，但其因随机采样和依赖参数控制，得到的结果可能并非实际的最优解。Li 等[18]提出一种利用法线方向和邻近信息从点云中提取所有的子结构，进而在子结构上进行平面信息提取的方法。该方法作为基于 RANSAC 的方法的变种，在重建结果的精度上有很大的提升，但其缺点是难以确定子结构的大小。Yue 等[19]提出一种基于法线聚类和带约束初始点的 RANSAC 分割方法，该方法首先使用 Mean Shift 的方法求解点云法线，然后基于法线的初始约束执行 RANSAC 的方法完成平面分割。基于区域增长的方法首先选取种子点，然后设定增长条件和中止条件，算法将自动搜寻所有构成平面的点。然而，选取种子点缺乏统一的标准，这限制了区域增长算法的精确性和鲁棒性[20-21]。目前，许多高效的初始点选择方法已被提出，其中，最为经典的方法是将点云中具有最小曲率的点作为初始点进行区域增长[22-23]。区域增长算法实现简单，但是对噪声十分敏感，当不同区域之间过度平滑时，系统难以将平面结构区分开[24]。Li 等[25]采用分层聚类的方式解决初始点选择困难的问题，完成了对屋顶平面分割的任务。基于霍夫变换的方法——利用投票机制将原始数据投影到霍夫空间来确定具体的参数，常用于二维直线和圆的检测。对三维平面而言，霍夫空间中的每一个点都与真实空间中的一个平面对应，通过离散采样并统计霍夫空间中的峰值可以确定三维空间中平面的参数。此类方法虽然对噪声不敏感，但是存在参数空间分布不一致的现象。对此，也有学者提出解决方法，如章大勇等[10]采用一种基于对偶空间分割的三维霍夫变换方法将球面采样区域划分为多个对称的区域，然后在这些区域中借助不同的参数进行采样，一定程度上消除了变换带来的采样区域不一致。此外，Tian 等[26]使用 GPU 并行加速基于霍夫变换的平面提取算法，实现了对三维激光雷达点云的快速平面检测。

2.2 基于线云模型的平面提取算法

相较于从点云数据中提取平面，目前对利用线段等轮廓信息进行平面提取的方法研究较少。Wu 等[27]提出先从点云中获取交叉线段结构，再进一步提取平面信息的方法。Zhang 等[28]利用局部信息，通过计算线段之间的距离并进行谱聚类，以实现平面结构的提取。由于该方法需要计算局部信息，而现实中的建筑物在不同平面上线段的分布密度很可能不同，因而参数范围的设定存在较大困难。Cabo 等[29]使用激光扫描数据，并利用 3D 线段检测平面，但是它使用了激光雷达采集数据的强大特性，即采集的数据是相互平行而且密集的线云。

综上所述，大多数平面提取算法是基于点云模型或分析点云模型中的线段信息来进行平面拟合，系统仍然需要处理繁多的点云数据。直接以线云模型作为输入提取平面的相关研究较少，且现有的基于线云模型平面提取算法的普适性较差，通常对输入的线云有较高的要求，如需要密度分布均匀的线云信息[28]或是相互平行且密集的线云[29]。

3 基于斐波那契采样的三维线云模型平面提取算法

本文提出一种新的基于斐波那契采样的三维线云模型平面提取算法，算法流程主要包括数据获取和预处理、球面近似均匀采样、统计采样点以及平面拟合等 4 个步骤。其中，统计采样点和平面拟合步骤是迭代过程，流程如图 1 所示。

图1 方法流程图Fig.1 Method flow

3.1 数据获取和预处理

3.1.1 数据获取

图2 数据获取Fig.2 Data collection

3.1.2 数据预处理

图3 数据预处理Fig.3 Data preprocessing

理论上，空间中一组共面的线段对应于高斯球上一个过球心的平面。由此，基于三维线段的平面提取问题可转换为高斯球上过球心平面的检测问题。同时，对于每个经过高斯球球心的圆面，其用单位向量表示的法线也恰好对应高斯球面上的一个点。于是，过球心平面的确定也可以转化为高斯球面上点的确定。这样的处理不仅简化了三维线段的表达，降低了数据处理的难度，同时，也将复杂的平面拟合问题转换为高斯球面上点的采样问题。

值得注意的是，高斯球面上的点，仅表示三维线段的方向，而丢失了垂直于其方向的位置信息。因此，检测得到过高斯球球心的圆面之后，圆面上共面的点集对应原始三维线云模型中的线段集合并不一定全部共面，需要在后续过程中，结合原始的三维线段信息作进一步处理。但总体而言，将复杂的平面拟合问题转换为高斯球面上点的采样问题，极大地简化了问题。

3.2 球面近似均匀采样

尽管数据经过预处理后得到了简化，但基于点的平面检测由于噪声的存在，不宜直接通过 RANSAC 实现。而基于霍夫变换的方法，难以划分均匀的网格，仍然存在采样空间分布不均的现象。受霍夫变换投票机制的启发，本文使用螺旋曲线斐波那契采样方法对高斯球面上的点进行近似均匀采样，以得到可能存在的平面法线，从而确定过高斯球球心的平面。采用斐波那契螺旋曲线在球面上生成均匀分布的点有着出色的效果，有研究表明，与用经纬网格测量球面上不规则图形的面积相比，使用斐波那契网格测量球面上不规则图形的面积，加权误差可以减小40%[30]。

图4 采样点示意图Fig.4 Schematic diagram of sampling points

3.3 统计采样点

3.4 平面拟合

通过统计采样点过程能够获得待拟合平面的线段集合Lm。然而，由于将三维线段映射到高斯球面上时，损失了直线的截距信息，因此统计采样点过程获得的线段集合Lm可能表示一个平面或者多个平行的平面。即在高斯球上共面的线段集合对应的真实空间中三维线段集合有可能位于多个平行平面上。鉴于这些平面具有相同的法线且仅具有不同的截距，依据截距的差异便可分离出多个平行平面。

为了提取精确的单个平面，本文使用平面的截距信息对线段集合进行划分，并选择划分后具有最多数量的线段集合作为此次迭代提取的平面，一次平面拟合的过程如下：(1)给定统计采样点过程中得到的线段集合Lm以及采样点tm对应的单位方向向量u。

(4)当线段集合C中线段的数量小于指定阈值λ时，表示集合C中线段无法构成平面，平面提取算法结束。

每次平面拟合迭代过程结束之后，需要删除已经用于构建平面的线段集合C，以及集合C中线段对应在高斯球面上的点，更新原始线段集合L以及高斯球面上的点集S。随后进行下一轮的统计采样点和平面拟合过程，直至算法达到运行结束条件。

此外，在完成平面拟合迭代过程之后，由于离散采样法线存在一定误差，可能存在提取的两个或多个平面非常相近, 如图 5 所示，图 5(a)和图 5(b)两个平面对应原始模型中同一个平面。因此，在完成平面提取后需要进行一个后处理：将在角度误差阈值 之内相互平行且截距之差在距离误差阈值 之内的平面合并，并使用奇异值分解修正最终的平面参数。本文方法中 取2，后处理结果如图 5(c)所示。需要说明的是，得到多个相似平面是所有平面拟合算法都会存在的问题，因此在本文实验中，对所有平面拟合方法均进行相同的后处理操作。

图5 重复表达的两个平面Fig.5 Two planes of repeated expression

4 结果与讨论

与其他传统的方法相比，本文提出的平面提取算法的特点是：直接以线云作为算法输入，提取平面的完整性和质量都很高。其中，提取平面的完整性高说明算法提取平面的能力强。为了验证本文算法的有效性，从两个方面分析实验结果：(1)提取平面的完整性和效率；(2)提取平面的质量。同时，本文在多个数据样本下进行了实验，并与传统方法的实验结果进行对比。

4.1 实验设置

对于不同方法的实验参数尽可能选择保持一致，本实验中采用的参数如表 1 所示。

表1 不同算法的参数Table 1 Parameters of different algorithms

除了以上共同的参数之外，每种方法均需要设置额外的不同参数。在基于 RANSAC 的方法中，需要额外指定随机采样的次数，本文设置随机采样次数为 10 000。在霍夫变换方法中，需要指定采样步长为霍夫空间中采样点之间的角度差，实验中设置采样步长为 18 °。经试验，在步长为 18 ° 时，霍夫空间中需要采样 10 000 次。此外，本文方法需要额外指定近似均匀采样中需要的采样点个数，为保证与基于霍夫变换的方法和基于 RANSAC 的方法的采样次数一致，本文方法设置采样点个数为 10 000。

4.2 完整性

衡量平面提取算法的一个标准是提取平面的完整性，即能从线云中提取更多的符合原始线云模型的平面。本文在 4 个线云模型实例上进行实验，并与传统方法的实验结果进行对比。不同方法提取线段的结果如图 6 所示，图 6(a)为输入的4 个线云模型，图 6(b～d)分别为基于 RANSAC的方法、基于霍夫变换的方法和本文方法对线云模型提取平面的结果。其中，提取的不同平面分别以不同的颜色标注。结果表明，本文方法提取的平面更加完整，缺失的线段数量最少。

图6 平面提取结果对比Fig.6 Comparison of plane extraction results

平面提取算法的完整性越高，从线云中提取符合原始线云模型的平面越多。为了定量地评估算法提取平面的完整性，本文统计了平面拟合算法提取的平面个数以及有效平面占比。一般来说，提取平面的个数越多越能体现平面拟合算法对原始数据的表达能力。然而，并不是所有提取的平面都符合原始数据，即算法提取的平面与原始线云数据中对应的平面有较大差异，该平面无法对原始数据进行有效表达。因此，本文另外统计了平面拟合算法的有效平面占比，进一步衡量平面拟合算法对原始线云模型数据的表达能力。

本文使用不同平面提取方法对 4 个线云模型实例进行实验的数据统计结果如表 2 所示，表中数据均为算法运行 10 次的平均结果。其中，模型一和模型二是较为干净的线云数据，模型三和模型四是噪声较大的线云数据，且模型四的场景更加复杂。

从表 2 统计数据可以看出，在以上 4 个模型实例中，本文方法提取的有效平面个数最多且有效平面占比最高，说明本文方法提取的平面更完整。基于 RANSAC 的方法的提取结果同样十分优秀，但是因为随机采样可能产生非最优的结果，最终可能提取一些不合理的平面。图 7 展示了提取有效平面和无效平面的结果对比，图 7(a)呈现了预期提取的平面区域，图 7(b)是本文算法提取的平面，图 7(c)为基于 RANSAC 的方法提取的平面。结果表明，本文方法提取的平面能够较好地对应原始线云，记为一个有效平面。然而，基于 RANSAC 的方法因为离群噪声线段的影响，干扰了平面提取的过程，使得提取的平面相较于原始线云有较大偏差，这里记为无效的提取平面。基于霍夫变换的方法由于采样空间不均匀，提取较多不合理的平面，导致有效平面占比较低，平面提取的完整性较差。如表 2 中模型三和模型四的结果所示，当线云数据中含有较大噪声时，基于 RANSAC 的方法和基于霍夫变换的方法提取的有效平面占比显著下降，这是因为离群的噪声线段对 RANSAC 的随机采样过程造成了较大干扰，基于霍夫变化的方法对噪声比较敏感。相较于其他两种算法，本文方法对于具有较大噪声和较复杂场景的线云数据仍表现十分稳定。

图7 有效平面和无效平面的对比Fig.7 Comparison of effective plane and invalid plane

表2 不同平面提取方法的结果比较Table 2 Comparison of the results of plane extraction by different methods

在运行时间方面，基于霍夫变换的方法有最好的时间复杂度，这是因为霍夫变换利用对偶信息计算每条线段经过了哪些采样点，而不用遍历每个采样点。基于 RANSAC 的方法和本文方法略慢于基于霍夫变换的方法。当场景数据含有较大噪声且场景较复杂时，由于基于霍夫变换的方法提取了许多不合理的平面，导致该方法的效率有所下降。

4.3 提取平面的质量

衡量平面提取算法效果的另一个标准是提取平面的质量，由于难以对平面提取的质量进行定量评估，本文分别对比了使用不同方法提取相同平面的实验结果，并对这些结果进行定性分析。图 8 展示了不同方法提取相同平面的结果，自上而下共展示了 4 个平面拟合的结果，图 8(a)中红色方框的区域为提取的单个平面对应在原始图像和线云的区域，图 8(b～d)分别为基于 RANSAC的方法、基于霍夫变换的方法和本文方法提取的单个平面。由于缺失所提取平面的真实平面参数，难以量化提取平面是否准确。然而，通过观察所提取平面中线段集合的构成能直观感知所提取平面的质量。当平面上线段集合与原始线云和参考图像更契合时，可以认为对该平面的提取更准确。

图8 不同方法提取相同平面的结果对比Fig.8 Comparison of the results of different methods extracting the same plane

从图 8 可以看出，本文方法提取的平面中线段集合的构成能更准确地对应原始线云模型以及图像中的平面结构，且较少包含其他平面上的线段信息。这很大程度反映了本文算法所提取平面参数的准确性更高。这主要是因为本文采用螺旋曲线斐波那契的方法进行了近似均匀采样，使空间的划分更均匀，因而提取的拟合平面的线段集更精确，效果更好。相较于其他两种方法，基于 RANSAC 的方法提取平面的质量综合结果最差，这是因为该方法随机采样构造初始平面，导致提取平面参数的稳定性较差。

5 结 论

本文提出一种基于线云模型的平面提取方法，并采用螺旋曲线斐波那契的方法对采样空间进行近似均匀划分以提高平面拟合的结果。实验结果表明，与基于 RANSAC 的方法和基于霍夫变换的方法相比，本文方法在提取平面的完整性以及提取平面的质量方面具有更高的优越性。但是本文方法仍存在一定的局限性——运行效率较慢。在未来的工作中，将深入研究在保证现有的平面提取效果的同时，进一步提高算法的效率。