0 引言
点云配准[1-3]是指将模型不同视角的点云数据拼合起来,是三维重建、逆向工程中的第一步,配准的效率和精度对工程整体有十分重要的影响。
点云配准有多种解决方案,一类常用的方法就是迭代最近点(iterative closest point, ICP)算法[4-5],及其后来的一系列改进算法[6-10]。ICP算法虽然配准精度较高,然而这类方法通常要求两片点云在配准之前有较好的初值,否则容易产生局部最优解而使配准失败[11]。所以在通常情况下,需要对两片点云进行粗配准,然后运用ICP算法进行精确配准,粗配准方法有基于特征的方法、基于随机抽样一致算法(random sample consensus, RANSAC)框架的方法及全局配准的方法
基于特征的粗配准方法首先根据局部特征描述符[16]提出的点签名(point signature, PS)特征描述算子,通过对每个点建立一个签名,搜索两片点云中具有相同或相似签名的点作为对应点从而计算配准参数,该方法存在对噪声敏感、计算量大等缺点。Van等[17]使用特征描述的方法进行配准,但是由于噪声等的存在,容易造成错误匹配,难以获得理想的匹配效果。
基于RANSAC的粗配准方法利用点云数据间的重叠区域确定对应点,根据对应点求解待匹配点云间的刚体变换关系。刚体变换是一种低维的线性变换,仅包含6个自由度(3个绕坐标轴旋转的角度和3个沿坐标轴方向的偏移量),可以根据3对对应点进行变换参数的求解[18]。因此,点云配准可以看作是搜索问题。假设两个输入点云P和Q各自包含m和n个扫描点,最简单的穷尽搜索方法是每次从点云P和Q中各选择3个点,得到一个刚体变换并计算配准误差,穷举所有的组合,选择配准误差最小的刚体变换作为最优变换。显然,穷尽搜索的时间复杂度为O(m3n3)。Winkelbach等[20]提出RANSAC算法,在两片点云中各自随机采集两个点,使用点之间的欧式距离和法向量确定点的对应关系,其中两组带有法向量的点就可以确定一个刚体变换。但是该算法稳定性不佳,容易产生错误的对应。Irani等[19]提出了一种基于RANSAC的算法,将搜索复杂度降到O(mn3log n),但对于大规模点云仍然不适用。Zhou等[13]提出一种快速全局配准算法。该算法对点云表面的点进行匹配操作。为了使表面对准及去掉错误的匹配而优化单一目标,这种优化在没有初始化的条件下实现目标点云的紧密对齐。由于不需要初始化,该算法速度较快。Aiger等[21]提出了四点全等集合(4-points congruent sets, 4PCS)算法。该算法利用刚体变换的性质,在源点云上随机选取共面的四个点作为一组基,在目标点云上寻找所有与其近似全等的共面四点集合,然后选择集合中的每一个元素与基对应,进而求解变换参数,求取配准误差,选择配准误差最小的刚体变换作为最终的解。4PCS算法将搜索复杂度降低到O(n2),对噪声和离群点都有较好的鲁棒性。但该算法直接对整个点云进行配准,釆用全局的最大公共点集(largest common point set, LCP)来度量点云的配准效果,算法需要两个点云重叠的比例足够大。此外,当点云对称性较强,并且重叠区域的特征相对整个点云不明显时,算法容易陷入局部最优,从而得到错误的配准结果。
有一些研究者对4PCS方法提出了改进, Theiler等[24]提出了超级四点全等集(super 4-points congruent sets, Super4PCS)算法,通过对目标点云进行空间光栅化的网格划分,实现了点对的快速提取,避免了对点云数据的全局搜索。另一种有效的方法是对基的结构进行改进, Mohamad等[25]通过引入点对之间距离的概念,提出了一个更为通用的四点模型,减少了一致性基集合中元素的数量,提高了算法的效率。此外, Silva等[26]指出4PCS算法需要人工估计重叠比例,提出了动态四等全等集(dynamic 4-points congruent sets, D4PCS)算法,每次迭代时自动估计两个点云的重叠比例,通过对重叠比例的估计更新基的边长,在配准精度、计算速度和鲁棒性方面都有一定的改善,但该算法需要两个点云重叠的比例足够大。上述方法虽然在一定程度上提高了4PCS方法的效率,但是在点云规模较大或者重叠比例较低时,算法的效率仍然不够高。
本研究通过对源点云和目标点云进行边界提取,使用边界特征辅助基的选取,取代原算法中随机选取的方案,提高了选取的基在两片点云重叠区域的概率,提高了算法的效率;通过使用特征的一致性对从目标点云中获取的一致性四点基的集合进行特征限制,去除多余的四点基,减少算法的验证时间,进一步提高了算法的运行效率。在两片点云重叠率较低的情况下该算法效率不会有明显的下降,且对噪声等具有较强的鲁棒性。本研究提出了考虑边界的基选取的算法,即快速四点一致性(fast 4-points congruent sets, F-4PCS)算法,大大缩小了搜索空间,提高了搜索效率;提出了基于PFH特征的四点基简化算法,节约了算法的验证时间。
1 4PCS算法简介
给定源点云P和目标点云Q(P和Q在各自坐标系下,位置任意),点云配准的任务就是将两片点云变换到世界坐标系中, 4PCS算法将这个问题转化为求解两片点云最大公共点集,即求解使两片点云距离最小的刚性变换。假设T为任意一个刚性变换, P′为P的一个子集, ∀pi ∈ P′, qi ∈ Q,在满足║ T(pi)- qi║≤ δ的条件下,使P′最大化的刚性变换即为最优变换。
点云中的任意共面的4个点可以确定2个点对,四点集B={a, b, c, d}可以称为一组基。如图1所示,为每组基定义一组表示量: r1、r2、L1、L2,如果两组基的所有表示量都对应相等,则认为两组基具有一致性, r1、r2、L1、L2分别为:
$\begin{array}{*{20}{c}}{
{L_1} = \left\| {\mathit{\boldsymbol{a}} – \mathit{\boldsymbol{b}}} \right\|{\rm{, }}}\\{
{L_2} = \left\| {\mathit{\boldsymbol{c}} – \mathit{\boldsymbol{d}}} \right\|{\rm{, }}}\\{
{\mathit{\boldsymbol{r}}_1} = \left\| {\mathit{\boldsymbol{a}} – \mathit{\boldsymbol{e}}} \right\|/\left\| {\mathit{\boldsymbol{a}} – \mathit{\boldsymbol{b}}} \right\|{\rm{, }}}\\{
{\mathit{\boldsymbol{r}}_2} = \left\| {\mathit{\boldsymbol{c}} – \mathit{\boldsymbol{e}}} \right\|/\left\| {\mathit{\boldsymbol{c}} – \mathit{\boldsymbol{d}}} \right\|{\rm{。}}}\end{array}$
图1
图1
四点基及其表示
Fig.1
The 4-point basis and its representation
在源点云中随机选择一个共面的四点基B⊂P,然后在目标点云中找到所有与B具有一致性的基组成集合S,对于集合S中的每一个元素Si,利用其与B的对应关系求得刚性变换矩阵Ti,然后根据LCP方法求得所有Ti的最优值作为此轮迭代的最佳变换。进行L次迭代,选择所有迭代的最优结果作为最终的变换。
2 F-4PCS
对4PCS算法进行如下改进:利用边界特征对算法进行加速,从而在点云重叠率较低的情况下提高算法的运行效率;消除多余的四点基,加快算法的运行速度。
2.1 边界提取及四点基选择
Rusu等[27]实现了点云边界估计的相关算法。本研究使用该算法来进行点云边界提取,提取过程如图2所示。首先,求取目标点p的法向量和邻域内其他点的法向量的夹角α1, α2, …, αn,计算相邻夹角最大的角度差
$ \alpha = \max \left\{ {
{\alpha _1}, {\alpha _2}, \cdots , {\alpha _n}} \right\}。 $
图2
图2
边界提取过程示意图
Fig.2
Illustration of boundary extraction process
最后将α与阈值δ进行比较,如果α>δ,则p为边界点,否则p为非边界点。在进行法向量估计时,将其中的关键参数邻域搜索半径r设置为点云平均点间距的8~12倍,因为r太小,噪声会过大,造成时间开销增加;在进行边界点判断时, δ∈[0.5π, 1.5π]。
利用点云重叠区域靠近点云边界这一基本特征,对两片点云进行边界提取,边界提取过程如图2所示。在P中选取基的具体方案是:首先从边界点中随机选取一个点p1;然后根据点云边界包围盒对角线的长度L和大致重叠比例估计E,计算出b的变长最大值l,根据l在边界点集合中选取第二个点p1, p2满足:
$ \left\| {
{\mathit{\boldsymbol{p}}_1} – {\mathit{\boldsymbol{p}}_2}} \right\| = l, $
根据点到p1和p2连线的距离和l,在P中选取第三个点p3;然后根据共面的性质选取第四个点p4。
在源点云P中取得四点基b后,在边界提取的基础上,将目标点云Q的边界点扩展为边界特征带Q′(由边界扩展到边界特征带过程如图3所示),然后在Q′中抽取与b具有一致性的四点基集合B,取代原算法中对整片点云的操作,这在重叠率较低的情况下,有利于提高算法的运行效率。
图3
图3
边界扩展到边界特征带示意图
Fig.3
Illustration of boundary extension to boundary feature belt
为了提高在目标源点云中选取基的效率,需要找到边界点r邻域内的所有点,形成边界特征带,在特征带中进行基的搜索和匹配。一个直接的思路就是,对源点云建立KD树,对于边界的每一个点,在KD树中的r邻域内寻找临近点,然后将找到的点插入结果点云,边界点迭代结束,边界的r范围内的所有点将都存放到结果点云中。由于相邻的边界点会在r邻域内找到重复的点,结果中将存在大量重复的点。针对这个问题的解决方案为:对于边界的每一个点,在源点云中寻找范围内的临近点,将找到的点插入结果点云中,同时对源点云中对应的点进行标记。由于KD树已经建立完毕,改变点云中的点不会引发其对索引的重新建立,所以在边界点迭代完毕后,点云中的点分为r邻域内正确的点和重复搜索到的标记点,将标记点删除,即可得到正确的结果。
2.2 基于PFH特征的四点基简化
在源点云边界特征带中获取四点基后,找到所有具有一致性的四点基集,对于每个四点基集进行验证以确定最优变换。但是大部分四点基是无效的,对结果的求解没有帮助反而浪费了大量的验证时间。为了进一步提高计算效率,通过使用局部点特征直方图(point feature histograms, PFH)特征来消除冗余的四点基。
2.3.1 点特征直方图特征
PFH 通过使用多维直方图的值记录点周围的平均曲率,从而对点的几何特性进行编码[27]。这种高维度的特征具有刚体不变性,并且可以很好地处理噪声和密度不均等问题。
PFH 通过参数化查询点与邻域点之间的空间差异,形成多维直方图对点的k邻域几何属性进行描述。直方图所在的高维超空间为特征表示提供了一个可度量的信息空间,对点云对应曲面的6维姿态具有不变性,并且在不同的采样密度或邻域的噪音等级下具有鲁棒性。PFH表示法是基于点与其k邻域之间的关系以及它们的估计法线,或者说,其考虑估计法线方向之间所有的相互作用,试图捕获最好的样本表面变化情况,以描述样本的几何特征。因此,合成特征超空间