为什么用PCA做点云法线估计?

Posted by Ada on September 1, 2018

为什么用PCA做点云法线估计?

[TOC]

之前讲采用拟合法做泊松重建的时候,强调过该方法针对于oriented point,也就是有法线的点云。

但是我用到的很多数据都没有法线,在pcl中。对于法线的计算已经封装好,主要是积分图以及PCA法进行法线估算。后来想自己手动写一写,就去研究了一下原理。网上有很多关于PCA分析的文章博客,侧重点不尽相同,主要是从数学、统计角度。

我不相应的展开。推荐一些我觉得还不错的博文:

彻底理解PCA(Principal Component Analysis)主成分分析

彻底学会PCA1-理解PCA原理

由于我属于数学公式一多就本能抗拒那种,所以我倾向于看国外的资料。

许多外文资料更倾向于循序善诱告诉你为什么要这么做。而不是一上来就抛理论。

希望你在阅读的时候,循着这样的思路来思考这个问题。

1、问题情境的理解:

假设初始点云是没有法矢的,我们的目的是为了求取法矢。

1533521209769

法矢的特性是垂直于其点所在的平面。所谓三点(不共线)确定一个平面,所以我我们可以猜想:采用当前点的邻近点,拟合出一个局部平面,那么法矢就好求了。

1533521614790

其它出的点也一样:

1533521640102

但是会出现二异性问题,毕竟经过一点且垂直一个面的法矢是有两条的:

1533521707649

所以后续还需要用特定的方法进行法矢定向,这里先不用展开

还记得现在的问题思路么?

求取某点法矢–》先求该点所在的拟合平面–》求拟合平面?

好了,理解了问题的出发点,下一步就是寻找解决方案了。

2、用什么方法拟合平面好呢?

拟合出的平面应当具有一个性质:候选点到这个平面的距离最小

翻译一下,局部平面拟合的方式:

  • 选取当前点的 k 个临近点(上述图都 k=2)。或者划定一个半径为 r 的球,选取球内部所在的点
  • 找到一个平面,使得以上选出得到点到这个平面的距离最小

1533521990089

(所以你明白为什么pcl做这些的时候为什么要建立 kd-tree/octree, 还限定search radius了吧)

说到平面拟合,我们最常见的当然是最小二乘法了:

下图首先给出的二维情况下,回顾一下点集拟合直线的情况。

1533522265666

但是我们是要拟合平面,所以这里的距离,而是考虑垂直距离:

1533522448354

3、PCA怎么做?

好了,PCA终于上场了。忘记大家通常说的PCA的先验知识吧,比如用来降维什么的。就把场景限定在这里:

  • PCA是为了找到一组新的变换后的正交基(下图绿色部分),这组正交基是给定点集的最佳表达

    可以理解为PCA的问题其实是一个正交基的变换,使得变换后的数据有着最大的方差

1533522651692

到这里,你可能尚且不明白它的目的,但是看起来,我们似乎要建立一个新的正交坐标系统


好了,还记得之前的问题场景么?我们是要寻找一个平面,使得点到这个平面的距离最小。

假设这个平面的中心点为 c , 穿过中心点的法矢为 n, 那么点 xi 到平面的距离 d ,可以看作是向量 xi-c 在法线方向上投影向量的长度,所以这个问题就化解为下图框起来的部分。 1533605892772


接下来是很多数学的部分!可能你看不懂,但是请记住涉及到的关键点:协方差矩阵和奇异值分解。

这是我看PCA的很大一个障碍,我一度不知道为什么要这么做。我会在下一节里去阐述。

1、定义中心原点。

1533539481962

这个m为什么可以是原点,因为原点的特性就是其他点到它的距离的平方和最小。

接下来,问题转化为:

1533606520341

解释一下这个式子:1533525788795

备注:数学公式里argmin 就是使后面这个式子达到最小值时的变量的取值。也就是,当所有候选点到目标点c距离的平方和最小时,m就是这个c点

到这里问题一路化简为,(不要忘记 yi 的含义),下面的式子看着脑壳疼,但是无非就是把积分号移动了,注意 n 是未知待求解的。

1533606688835

2、构建协方差矩阵S1533527529459

​ 其中:1533527515994也就是 前文上图中的 yi

3、奇异值分解

1535940728586

4、取U中的最后一列作为法矢

总结一下:

1535941053654

你可能对步骤1和步骤2还能跟上。到了奇异值分解就开始疑问了。不要着急,下面来说为什么要做这样的操作。

4、协方差矩阵、奇异值分解、特征向量、特征值是为了干嘛?

奇异值分解:

这里比较推荐这篇文章,图文并茂。关键是从几何角度阐释了奇异值分解的意义。

奇异值分解(SVD) — 几何意义

如果你看这篇文章还是觉得数学很多,那么我定性的给你解释:

1535941280180

在此处,可以把矩阵 Y 看作三个其它的矩阵相乘

  • U 表示经过变换之后新的坐标系下的正交基
  • 1533605209324代表V中的向量与U对应的向量的变换关系
  • V 代表变换前原坐标系下的正交基坐标系,T代表转置(有些地方写的是*)

1535943877369

至于怎么求解,可以看一下这片文章:奇异值分解(SVD)原理与在降维中的应用

我们看到最后取的法向量就是U中的最后一列,也就是特征值最小的那些特征向量。为什么呢,这就要说到协方差矩阵的意义了。

协方差矩阵的意义:

协方差矩阵衡量了沿着特定方向v的点的相关性

举例:如果找一条穿过原点 m 的直线 l , 直线 l 沿着方向 v , 把点xi 投影在直线上,

得到点 xi’ 。 然后下面这一串数学公式,表达的就是点 xi’ 的相关性

1533541679702

可以看到相关性越大(对应的特征值也就越大)的点,几乎就快落在(甚至重合)直线l上。

1535943071575

当然PCA的应用还有很多,比如在数据分析中常常被用来降维。而这里就不展开了。仅仅从三维点云的角度聊一下为什么用PCA的方法求取法矢。

而在PCL中。还有一种针对有序点云的积分图求解法矢的做法。会在之后的博文里展开。

希望自己能以讲人话的方式,写好每一篇技术博文。


本站总访问量: