基于顶点的法向量估计

简单介绍通过某点附近的点估计该点法向量的方法，并介绍通过RANSAC进行优化的方法。

Estimating Normals

估计的基本假设是：认为目标点附近的点和目标点近似在同一平面中，从而求一个近似的法向量。设目标点邻域中的点为$x_1,...,x_n$（包含目标点自身），单位法向量为$w$，该法向量对应的切平面经过一点$c$（注意：$c$的最优值并非为目标点（见下）），则可以考虑解如下优化问题得到法向量的估计：

$minimize_{w,c} \space J(w,c)=\sum_i (w^T(x_i-c))^2$

$s.t.||w||^2_2=1$

则$L(w,c,\lambda)=\sum_i (w^T(x_i-c))^2-\lambda (<w,w>-1)$

KKT条件为：

$\frac{\partial L}{\partial w}=2\sum_i w^T(x_i-c)(x_i-c)^T-2\lambda w^T=0$

$\frac{\partial L}{\partial c}=-2\sum_i(x_i-c)^Tww^T=0$

$\frac{\partial L}{\partial \lambda}=1-<w,w>=0$

由此得到$w$必然是协方差矩阵$\sum_i(x_i-c)(x_i-c)^T$的某个特征向量。

而$J=\sum_iw^T(x_i-c)(x_i-c)^Tw=\lambda w^Tw=\lambda$，因此**$w$是协方差矩阵最小特征值所对应的特征向量（当然还要单位化）。**

可以验证：协方差矩阵的另外两条特征向量是最优切平面的一组正交基。这一点从PCA的角度来看是显然的（方差较大的方向当然就是切平面内的某两个方向）。

同时$c$的最优值也容易由KKT条件得到，为$\frac{1}{n}\sum_ix_i$。因此最优法向量对应的切平面经过邻近点的重心。

这种方法的问题在于：究竟取多少附近的点较难确定。且假设“附近的点都在一个平面内”在物体边缘等位置并不成立。

RANSAC

Random Sample Consensus（RANSAC）其实是数据拟合、参数估计等过程中的一种通用方法，其作用为通过迭代自动判别并抛弃离群点（Outliers）。

每一次的迭代过程大体如下（摘自Wiki）：

1. 在数据集中随机选取一个子集（称为假想正常点集（hypothetical inliers））
2. 在假想正常点集上拟合出一个模型
3. 计算剩余数据点在拟合出的模型上各自的损失。
4. 损失较小的数据点组成一致点集（Consensus set）
5. 如果一致点集足够大（大过预先设定的阈值*），则认为找到了一个较好的模型，迭代结束；否则从1继续迭代。

*当然，也可以对总的迭代次数设定阈值，最后的结果选用一致点集最大的模型。

最后还可以用最好的模型对应的一致点集再拟合一次模型进行调优等。事实上，RANSAC还有很多实现细节，这里暂且略过。

使用RANSAC估计法向量，就可以部分地解决“附近的点未必都在一个平面内”的问题。