改进的RANSAC算法用于结构面提取

在通过以上组织和索引方法对岩体点云数据进行法向量聚类和分组后，得到整个样本数据的多个法向量相同且相互平行的子集。在此基础上，本节用改进的RANSAC算法对每个点云子集进行平面拟合，消除噪点和无效数据的影响，提取出比较可靠的平面特征。

前文已经论述RANSAC算法是处理散乱岩体点云数据的有效算法，其主要通过3个步骤和3个阈值参数来完成。本节针对岩体结构面的特点，对RANSAC算法进行优化改进。

RANSAC算法中包括以下几个主要参数：

t——用于决定数据是否适应于模型的阀值；

d——判定模型是否适用于数据集的最小数据数目；

n——适用于模型的最少数据个数；

k——算法的迭代次数。

一般情况下，参数n可以根据特定的问题来确定。针对岩体结构面的特点，其平面特征最少只需3个点即可，因此n=3。

Nurunnabi等（2012）在其分割实验中已经证明，在含有噪点的点云数据中，如果仅用一个角度参数来设定模型的阈值t，往往得不到正确的分割结果，因为这些平面含有相同的法向量。其实验结果证明，在添加了距离阈值后，分割出的平面结果既正确又平滑。所以参数t在改进的RANSAC算法中将被细化为两个准则阈值：可接受点与平面模型间的距离阈值Tol以及每个点与初始拟合平面之间的法向量角度阈值Rθth；

参数d定义为点云聚类分组后平面内的最少点数MinPointNo。

参数k定义为迭代次数的阈值MaxIterNo。

本书提出的改进策略是将一种顺序法向量检测机制引入到RANSAC算法，以检测点云数据和计算拟合出的RANSAC平面之间的法线向量（NV）是否符合一定的约束条件。顺序法向量检测的RANSAC方法（以下简称SEQ-NV-RANSAC）可以自动地决定一个点是否可以被加到这个平面模型的迭代中去。通过这一项检查，可以保证不会从错误的平面中得到符合平面特征的点的最大数目。在得到第一个结构面之后，迭代此过程直到在该约束条件下准确提取所有的结构面。

具体思路为：

设定一个角度阈值Rθth，比较迭代中每一个点的法向量NV=（nx，ny，nz）与RANSAC算法初始拟合平面时随机选取的3个点的法向量NV3pl=（）之间的夹角θth与Rθth之间的关系，进而自动地决定这个点是否可以被加入到平面模型的迭代中去，同时避免得到符合错误平面模型的最大点数出现，消除RANSAC算法在迭代的过程中接受错误结构面模型的可能性。

必须要注意的是RANSAC算法中顺序选取3个随机点法向量NV3pl的方向可能存在相反的问题，如图4-13所示。所以，必须要保证所有法向量NV顺序的一致性，并在改进的算法中对法向量相反的情况进行检查。

此外，某个平面和它所包含的局内有效点（平面内点）之间的最小距离之和决定了迭代过程中哪个平面被确定为代表性的平面模型，如式（4-6）所示：

图4-13　法向量相反示意图

（a）顺序选取3个点；（b）两个含有相反NV的平面(https://www.xing528.com)

每个分组后的子集内包含多个平面，通常情况下是相互平行的，如图4-12所示。采用本节提出的SEQ-NV-RANSAC算法进行平面拟合，可以成功提取每个子集内的所有平面。在现有的角度和距离阈值条件下，当循环迭代被拒绝的平面外的点中再没有平面能够被拟合和提取出来时，整个迭代过程将会终止。

SEQ-NV-RANSAC算法的流程如图4-14所示，描述如下：

（1）根据法向量及其之间的夹角θth对每个点进行聚类分组（PS）。

（2）读取分组后的子集（PSj）；

（3）在子集内任意选取3个点拟合成一个平面3PL。计算每个点与平面3PL之间的距离PD3pl。

（4）根据设定的距离阈值Tol和角度阈值Rθth对每个点Pi进行检查，如果满足阈值要求，则在本次迭代m中接受Pi点为平面内的点；如果不满足阈值要求，则对Pi+1点进行检查。

（5）当没有点满足阈值要求时，则得到本次迭代m中可接受为平面模型的所有点和点的数量（PointNo）m。

（6）比较本次迭代m的点数是否大于适合平面模型的最小点数阈值（Min-PointNo）th：如小于，则忽略此次迭代；如大于，则继续比较m次迭代和m+1次迭代的点数是否相等：如相等，则对两次迭代m和m+1中接受的平面内点计Nv3pl：初始平面拟合时随机选取的3个点的法向量；PS：聚类分组后的子集；（MaxIterNo）th：阈值（最多迭代次数）；Tol：可接受点与其平面模型间的距离阈值；PD：点与平面模型间的距离；（Min-PointNo）th：阈值（判断模型是否适用于数据集的最小数据的数目）；Rqth：角度阈值；PL：拟合的平面模型；（PointNo）m：第m次迭代中点的数量

图4-14　SEQ-NV-RANSAC算法流程图

算平均距离和，并保存最小平均距离和的迭代次数。如迭代次数小于最多迭代次数阈值（MaxIterNo）th，则进行m+1次迭代；如大于阈值（MaxIterNo）th，则输出结果。此结果作为中间结果，包括：平面内点、结构面平面、平面外点。

（7）输出中间结果后，检查下一个分组子集（PSj+1）是否存在，如存在，则转至步骤（2）进行下一步计算；如不存在，则保存中间结果中的结构面平面的数量；并与上一次迭代循环计算的结构面数量进行比较；如大于，则转至步骤（2）重新计算，如小于，则输出最终结果。最终结果包括：平面内点、结构面平面、平面外点。

此外，图4-15详细描述了每一步检测的过程，其中用SEQ-NVRANSAC算法检测每个点的法向量与两个阈值之间是否满足条件，同时要注意检查法向量相反的情况。具体描述如下：

（1）输入每个点和初始平面拟合时随机选取的3个点的法向量：

Pi=（x，y，z，nx，ny，nz，PD3pl）和NV3pl=（）。

（2）比较每个点与平面之间的距离PD与设定的距离阈值Tol之间的大小：如小于，则根据式（4-5）计算每个点Pi的法向量与平面法向量之间的夹角θ；如大于，则对Pi+1点进行判断和计算。如果cosθ＜0，则说明Pi点的法向量存在相反的问题，需要重新定义NVPi=（-nx，-ny，-nz），重新进行夹角θ的比较。

（3）如果cosθ＞0，则继续比较θ与角度阈值Rθth的关系，即当cosθ＞cosRθth时，则θ＜Rθth，可以接受Pi点，并加入整体已接受的模型；当cosθ＜cosRθth时，则θ＞Rθth，则不可接受Pi点。

（4）判断Pi+1点是否存在，如存在则转至步骤（1）读取Pi+1点，进行判断；如不存在，则得到整体可接受的平面模型。