alpha shape算法原理和PCL实现

2022-07-31 14:56 作者:生医小王子 0人读过 | 我要投稿

一、alpha shape概述

PCL库在ConcaveHull类中实现了alpha-shape算法（凹包），以将点云重建为三角形网络。本文主要介绍2D和3D alpha-shape算法的原理以及PCL库算法实现流程。

凹包可以定义为点云所占距的区域，而alpha-shape算法通过创建一个多边形外壳（alpha shape）来近似估计这一区域。该多边形的顶点即为点云数据点，多边形的精细程度由一个常数α决定，α越大，多边形越接近凸包；α越小，多边形越接近于点云。

二、alpha shape算法常规流程

1. 2D alpha-shape算法

2D alpha-shape算法的基本思想是将一个半径为α的圆围绕给定的离散点集S滚动，如图3所示。当α取值适当，这个圆就不会滚到S的内部，与圆相交的点就是S的边缘轮廓点，其滚动的痕迹就是S的边界线。可以通过如下准则确定边界线：在点集S内任取两个点 $p_%7B1%7D%20$ 和 $p_%7B2%7D%20$ ，过这两点绘制半径为α的圆，若圆内没有其他点，则可以认为 $p_%7B1%7D%20$ $p_%7B2%7D%20$ 是边界线[3]。注意，当点 $p_%7B1%7D%20$ 和 $p_%7B2%7D%20$ 的距离小于2α时，会有2个圆通过这两个点，只要有一个圆中没有其他点， $p_%7B1%7D%20$ $p_%7B2%7D%20$ 就是边界线，因为边界线外面是空白的，在外面的圆中不会包含其他点。

1.1 暴力算法[5]

（1）遍历每条边 $p_%7B1%7D%20$ $p_%7B2%7D%20$

（2）如果边 $p_%7B1%7D%20$ $p_%7B2%7D%20$ 的长度大于直径2α，则跳过（无法找到这两个点的圆）

（3）求出两个圆的圆心 $C_%7B1%7D$ 和 $C_%7B2%7D$

（4）计算其他点到 $C_%7B1%7D$ 和 $C_%7B2%7D$ 的距离，若存在圆不包含点集S中的其他点，则边 $p_%7B1%7D%20$ $p_%7B2%7D%20$ 为边界

1.2 改进算法[5]

为减少计算量，先建立三角网，再从三角网的外边界开始判断

（1）根据点集S建立Delaunay三角网

（2）若三角形中某条边的长度大于2α，则删除该三角形

（3）对三角网每条边进行判断：若过某条边的两点且半径为α的圆包含其他点，则删除该三角形

（4）求出剩余三角网的边缘，该边缘即为点集S的边缘线

图4 不满足alpha-shape要求的三角形；要判断的三角形为△ABC，要判断的边为AB，因为半径为α且过AB两点的圆包含点C，从三角网中删除△ABC[5]

2. 3D alpha shape算法[6]

3D alpha-shape算法与2D算法相似，以一个半径为α的小球在点集上滚动，与小球相交的3个点所构成的三角形为点集边界面。3D alpha-shape算法的输入为n×3的三维空间点集S矩阵，每一行的三维向量代表空间中的一个点。输出为m×3的边界三角形序号集合矩阵M，其中m代表边界三角形数目，每一行的三维向量代表三角形的3个顶点序号。

（1）从点集S中任意选择一点 $p_%7B1%7D%20$ ，将与之距离小于等于2α的点组成新的点集 $S_%7B1%7D%0A$ ，从 $S_%7B1%7D%0A$ 中任意选取一组点 $p_%7B2%7Dp_%7B3%7D%0A%0A$ ，求出过点 $p_%7B1%7D%20$ $p_%7B2%7Dp_%7B3%7D%0A%0A$ 且半径为α的球的球心 $C_%7B1%7D$ 和 $C_%7B2%7D$

（2）遍历点集 $S_%7B1%7D%0A$ ，依次求出其他点到球心 $C_%7B1%7D$ 和 $C_%7B2%7D$ 的距离d和d'。如果d和d'中有1个集合的距离均大于等于半径α，则可以判断不是边缘轮廓点，停止遍历，转到第3步

（3）选择 $S_%7B1%7D%0A$ 中的下一组点按步骤1,2进行判断，直到 $S_%7B1%7D%0A$ 中的全部点判断结束

（4）选择S中下一个点按步骤1~3进行判断，直到S中的全部点判断结束，输出边界三角形矩阵M

三、PCL算法实现

1. 前提知识

（1）Lifting Map算法[2]

Lifting Map是一种计算点云Delaunay三角网的方法。该算法将3维点云映射至4维空间。计算4维空间点云的凸包，将该凸包下边界映射回3维空间即可得到点集的Delaunay三角网。

（2）Alpha Complexes[2]

Alpha Complexes是指alpha shape外壳内的单纯形复合体，且Alpha Complexes是点云Delaunay三角网的子集，Alpha Complexes可以简单理解为点云内数据点相连而形成的内部结构。单纯形是二维的三角形，三维的四面体，可在任意维度推广，n维单纯形是一个有n+1个顶点，n+1个面的多面体，即这些顶点的凸包。当 $%CE%B4_%7B%CF%84%7D%0A$ 为Delaunay三角网中的单纯形，且 $%CE%B4_%7B%CF%84%7D%0A$ 的外接球/圆的半径小于α，则 $%CE%B4_%7B%CF%84%7D%0A$ 属于Alpha Complexes，即 $%CE%B4_%7B%CF%84%7D%0A$ 在alpha shape的内部。

2. alpha-shape算法的PCL实现

PCL实现的大致流程为：使用Lifting Map算法计算点云的Delaunay三角网；确定Alpha Complexes，计算Delaunay三角网中的四面体/三角形的外接球/圆半径r，保留r<α的四面体/三角形；确定alpha shape，遍历Alpha Complexes中所有单纯形（四面体/三角形）的岭（三角形/边），若他们相邻的岭中有不属于Alpha Complexes的，则为边界单纯形。

算法流程如下：

（1）点云预处理。计算并减去点云质心坐标，将点云移动至坐标轴中心；计算点云特征值和特征向量，对点云做旋转变换（只有2D点云需要做旋转变换）

（2）计算Delaunay三角网。调用qhull库，通过qh_new_qhull函数计算点云在4D空间的凸包

（3）计算每个单纯形的中心。调用qhull库，通过qh_setvoronoi_all函数计算每个单纯形（四面体/三角形）的球心/圆心

（4）确定Alpha Complexes。3D时，遍历土堡中位于下边界（Delaunay三角网）的四面体，计算四面体外接球半径r，若r<α，则保存该四面体的4个三角形边界；若r>=α，则找出四面体中满足要求的三角形并保存。2D时，遍历Delaunay三角网中的三角形，计算三角形外接圆半径r，若r<α，则保存该三角形的3条边，否则跳过（可能单独留下一条边没有什么意义）

（5）确定alpha shape。3D时，遍历Alpha Complexes中所有三角形，若相邻的三角形中有不属于Alpha Complexes的，则为边界三角形，保存下来。2D时，遍历所有边，若相邻边有不属于Alpha Complexes的，则为边界边，保存下来

（6）将点云旋转回来，并加回质心坐标

PCL代码如下：

（1）点云预处理