1 引言

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

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

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

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

　　采样问题，简化了问题的复杂性;(2) 在高斯球表面使用螺旋曲线斐波那契采样，使采样空间分布更加均匀，提高了最终平面提取的质量。

　　2 相关工作

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

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

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

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

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

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

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

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

　　3.1 数据获取和预处理

金沙彩票手机版app　　3.1.1 数据获取

　　本文算法的输入是三维线云。为了更方便地获取数据，本方法使用 Hofer 等提出的 Line3D 从多副图像中获得场景的三维线云。与三维点重建类似，利用图像中的直线结构重建三维线段。Hofer 等采用 Structure-from-Motion 提供的相机姿态解决不同图像之间线段匹配的问题，从而构建出三维线云。本文算法首先使用消费级相机采集若干场景图像，然后将图像序列输入 Line3D 中重构出原始线云作为本文算法的输入。获取的三维线云用集合 表示，其中，k 表示线云模型中线段的总数量;li 表示位于集合 L 中 第个线段。从图像序列中提取线云的一个实例如图 2 所示。

　　图 1 方法流程图

　　图 2 数据获取

金沙彩票手机版app　　3.1.2 数据预处理

　　原始输入的三维线云模型，线段之间非常杂乱。不同的线云模型也具有不同的空间范围，数据处理比较困难。由于判断一条线段是否位于特定平面，取决于该线段的方向，以及二者是否存在交点，而与线段的长度无关。据此，本文将线云模型中的每条线段映射到半径为 1 的高斯球面上，如图 3 所示。具体操作是：先将每条三维线段的长度单位化;然后平移每条线段，使得线段的一个端点位于坐标原点，则另一个端点位于半径为 1 的高斯球面上。将三维线云模型 L 映射到高斯球上得到一个新的点集，其中，k 表示集合中线段的总数量;si 表示位于集合 S 中第 个点。集合L 与集合 S 中的元素一一对应。

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

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

　　3.2 球面近似均匀采样

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

　　采样点构成的集合用 表示，其中，n 表示集合中采样点的总数量;ti 表示位于集合 T 中第 个采样点。图 4 展示了使用螺旋曲线斐波那契采样对高斯球面采样的示意图。　　

金沙彩票手机版app　　图 3 数据预处理

　　图 4 采样点示意图

　　3.3 统计采样点

　　区别于霍夫变换中的统计方式，在近似均匀采样过程中每个采样点代表对应平面的法向量。因此，近似均匀采样过程之后， 需要统计以该采样点作为法向量确定的过高斯球球心的圆面上所有点的数量。当点的数量大于指定阈值，说明圆面上的这些点可以拟合出该圆面，即对应原始三维线云中的线段集合可能存在待拟合的平面。统计采样点的具体过程包括：对于每个采样点，计算高斯球球心 o 和高斯球面上每个点构成的向量os_j与采样点t_i方向之间的夹角，当 处于 范围时，认为该高斯球面上的属于 t_i采样点。由于线云模型的获取过程存在误差，不能准确地获得每条直线在三维空间中的方向。因此， 本文设定一个角度误差阈值 ，若两个向量之间的夹角处于误差范围内，便认为两向量垂直。对每个采样点，统计过高斯球球心的圆面上所有点的数量，找出具有最多数量的点集 S_m  以及 S_m  对应的原始线段集合中的子集合 L_m ，同时记录对应的采样点t_m。线段集合  L_m  和采样点t_m将作为平面拟合的依据。

　　3.4 平面拟合

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

　　为了提取精确的单个平面，本文使用平面的截距信息对线段集合进行划分，并选择划分后具有最多数量的线段集合作为此次迭代提取的平面，一次平面拟合的过程如下：

　　(1) 给定统计采样点过程中得到的线段集合 L_m  以及采样点t_m金沙彩票手机版app 对应的单位方向向量 u。

　　(2) 对每条原始的线段以其中点作为代表，计算在向量 u 方向上的投影 d_i。

　　(3)计算以向量 u 作为法线的平面 P 的截距 d_p，使得截距在    范围的线段集合 C 中的数量最多，其中金沙彩票手机版app 为距离误差阈值。随后对该平面线段集采用奇异值分解修正由范围采样造成的误差，以确定最终的平面参数。

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

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

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

　　4 结果与讨论

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

　　4.1 实验设置

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

　　其中，距离误差阈值 表示当直线与平行平面之间的距离在  范围内时，认为直线位于平行平面上，本文实验中   取 0.1 m。角度误差阈值表示当两条直线之间的夹角在范围时，认为两条直线垂直，本文实验中 取1.5 ˚。由于在霍夫变换中，采样空间按经纬度进行划分， 所以霍夫变换中的角度阈值与实际采样的大小有关，在霍夫变换的方法中不设置角度误差阈值  。λ 表示可以构成平面的最少线段数目，在这 3 种方法中均设定为 15。

金沙彩票手机版app　　表 1 不同算法的参数

金沙彩票手机版app　　图 5 重复表达的两个平面

　　图 6 平面提取结果对比

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

　　4.2 完整性

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

　　图 7 有效平面和无效平面的对比

　　表 2 不同平面提取方法的结果比较

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

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

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

金沙彩票手机版app　　图 8 不同方法提取相同平面的结果对比

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

　　4.3 提取平面的质量

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

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

　　5 结论

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

   作者：武 凯 1,2 周佳新 1,2 程章林 1*

金沙彩票手机版app　      　1 中国科学院深圳先进技术研究院

金沙彩票手机版app　　      2 中国科学院大学计算机科学与技术学院

金沙彩票手机版app　      　转载自《集成技术》