10.3. 点云的模型拟合#
模型拟合是点云的另一个重要课题。具体来说，这指的是从给定的点云中提取出平面或球体、圆柱体等几何基元的过程。它在低层次的三维数据（无序的点集）和高层次的三维形状的结构信息之间，架起了一座桥梁，为许多下游的应用提供基础。 例如，如何从 图 10.10 所示的点云中提取出墙面或地面的位置，就是几何拟合所需要解决的问题。
图 10.10 北京大学治贝子园处重建得到的三维点云。#
几乎所有的几何形状都可以用一个确定的方程来描述它。
对于实体：\(F(x,y,z)\ge0\,.\)
对于表面：\(F(x,y,z)=0\,.\)
因此，我们可以形式化地定义几何拟合问题（以表面为例）： 对于给定的点云 \(P=\{(x_i,y_i,z_i)|i=1,2,\dots,N\}\) 和给定的形状 \(F\)，找到一组 \(P\) 的子集 \(P'\subset P\)，使得 \(\forall(x,y,z)\in P',F(x,y,z)=0\)。
由于实际上不可能做到完美的拟合，因此我们往往定义一个误差函数，然后求解一组点云的子集，使得误差最小化。
10.3.1. 平面的拟合#
首先我们考虑一个最简单的例子，以平面的拟合为例，输入的点云也基本在同一个平面上，即不存在任何噪点、错误点和无关点。给出三维空间中平面的方程：
我们需要求解 \(A,B,C,D\)。
对于点云中的某个点 \((x_i,y_i,z_i)\)，我们定义误差：
则总误差：
写成矩阵的形式：
使用奇异值分解（SVD）解最小二乘拟合问题：
分解得到的矩阵 \(V\) 最后一列即为所求的 \(M\)，它将使误差 \(L\) 最小化。
实际中遇到的问题远比我们刚才遇到的更加复杂。就像治贝子园的例子那样，给定的点集中可能不全是待求平面上的点，而有很大一部分其他点集（例如建筑的房檐、墙檐，门前的孔子像等等）。 这就使得刚才使用的最小二乘拟合失效了，因为最小二乘拟合对于误差越大的数据越敏感；当完全不在墙面上的点参与到平面参数的估计中时，最小二乘得到的结果也会被极大地影响。
那么，是否有方法能够减少房檐、墙檐等无关点的干扰，从而较为准确地进行拟合呢？事实上，的确有一类方法能够很好地利用采样一致性（sample consensus）来完成对无关数据的过滤。下面我们将介绍其中最为经典的一种算法：随机抽样一致性算法。
10.3.2. 随机抽样一致性算法#
随机抽样一致性算法（RANSAC）基于这样的一个思想：
对于 图 10.10 所示的点云，显然有相当一部分点都落在墙面上。如果这个比例至少为 \(p\)，那么在点云中随机挑选三个点所确定的平面，其正好是墙面所在平面的概率为 \(p^3\)；并且，如果这三个点恰好都落在墙面上，那么点云中剩下的点至少有 \(1-p\) 的比例也同样落在这三个点所确定的平面上。
利用这种一致性，我们便可以实现对干扰点的排除。具体来说，我们每次随机地挑选点云中的三个点，然后按照 §10.3.1 所介绍的方法估算平面的位置，并且评估点云中其他的点有多少比例同样落在该平面上，记这个比例为 \(q\) 。随后，重复这一步骤若干次，取其中 \(q\) 最大的尝试所对应的平面，即为算法的结果。不难证明，如果点云中至少有 \(p\) 比例的点落在目标平面上，那么经过 \(N\) 次随机采样后，最终确定的平面就是目标平面的概率为
例如，当 \(p=30\%,N=200\) 时，算法得到准确估计的概率为 \(99.6\%\)，由此可以看出，即使存在大量（\(70\%\)）的无关点，也仍然能够利用随机抽样的方式来对点云进行几何拟合。
下面我们系统地描述随机抽样一致性算法的流程：
随机选择一个用于估算的最小子集（对于估计平面来说，该子集包含 3 个点）；
用这个子集估算待求的参数；
用估算的参数测试整个数据集，将误差在一定范围内的数据点作为“内点”（inliers）；
如果内点的数量超过一定比例，就以全部内点为输入，使用最小二乘法重新估计一组更精确的待求参数；
重复 1-4 步若干次，最后将“用最多内点估计出的参数”作为最终结果。
随机抽样一致性算法具有鲁棒性好、效率高的特点（不难看出它可以并行化执行），因此长久以来是可视计算领域广泛应用的拟合手段。