计算机视觉三维测量与建模 课件 【ch07】点云特征提取和三维配准

第七章计算机视觉三维测量与建模点云特征提取和三维配准南京航空航天大学研究生教育教学改革专项（优质教学资源建设）项目资助01点云特征提取将不同时刻或不同视角由影像重建或激光雷达扫描的点云数据,根据数据重叠区域的关联，找到一组转换参数，使不同组数据能够统一到相同的坐标系统下，这个过程叫作点云配准。配准算法的本质是在全局坐标系中找到不同视图之间的相对位置姿态，使对应点云的相交区域完全重合(如图7.1所示)。将点云配准融合成一个点云结构，可以便于进行后续的内容分割和对象表面建模。点云特征提取点云特征提取三维数据的特征表达能力是目标特性分析的主要依据。当前的研究趋势正在从以点为单元向着以体素和对象等为单元的处理方式发展,它们是点的再组织形式。这类单元的上下文信息更丰富，能够适应不同的数据质量；而且降低了数据量，可以明显提高特征表达的效率。点云特征提取点云配准算法的总体流程包含两个阶段：全局粗配准和局部精配准，也可叫作粗配准和精配准。粗配准是在两组点云没有相对位置的先验信息的情况下，找到两组点云的初始配准参数；精配准是在有先验初始配准参数的条件下,进一步优化调整参数，提高匹配精度。点云特征提取】9特征描述子的数学形式是一类特征向量，用量化的方式记录了空间结构的某些特性，反映指定点、局部邻域集合或全局结构的形状特征。通过在特征空间中度量向量的相似性，建立不同曲面点的对应关系。点云特征提取】9点特征直方图（PointFeatureFtistogram，PFH）是对邻域范團内空间差异的一种量化，通过数理统计的方法获得一个用于描达中心点邻域点集合几何信息的直方图。PFH是将一个点的邻域均值、曲率、几何特性编码到多维的直方图中，这样的高维数据提供了大信,息量的特征表达。PFH特征不仅在旋转和平移六自由度变换下具有不变性，还能很好地适应不同程度的采样密度和噪声影响，属于一个整体尺度和姿态不变的多值特征。点云特征提取快速点特征直方图(FastPointFeatureFistogram,FPFH)）是PFH的快速版本，与PFH特征的大部分特性和原理相同。区别在于，FPFH简化了PFH计算特征元素的过程，降低了算法的复杂度，同时保留了PFH的大部分判别能力。快速版本采取一些简化和优化措施来提升计算速度。需要再次强调，点云的法向量质量对于FPFH特征的质量有很大影响。点云特征提取首先，FPFH将原有的4个特征简化为3个特征，只保留了3个角度特征。其次，在PFH中，求查询点p的特征直方图需要计算P和飞邻域内所有点{Pk}组成的集合poUip.了中的所有两两点之间的特征，这无形中添加了很多冗余的计算。在FPFH中，只计算中心点和邻域点的点对（P0，Pk）之问的特征，与中心点p0。无关的点对就不再计算，这样就构成了一个新的简化点特征直方图(SimplePointFeatureFtistogram,SPFE)。然后，使用中心点p0和{pk}中每个点的SPFH加权求和构成了所谓的FPFH。点云特征提取Harris角点最早被应用手二维影像特征提取，3.3.1节内容已经对其做了介绍。后来，Harris角点提取算法被拓展到三维数据处理中。三维Harris特征方法基于三维点云的局部邻域形状的可求导性研究，用一个函数对邻域点进行拟合，并将该函数的导数较大的点提取并作为特征点。与影像不同，三维数据可能具有任意的拓扑结构和采样密度，这使得导数的计算复杂化。点云特征提取基于投影的方法0102基于体素的方法03基于点的方法基于深度学习的分割而设计的点特征提取技术，通常需要依靠计算昂贵的内核化或图形构造，概括起来的技术分类有：点云特征提取02点云精配准就解决具体问题的过程而言，粗配准操作要在精配准操作之前完成。然而从理论知识的介绍而言，首先介绍精配准更具有意义。如果提供了良好的粗配准结果作为精配准的初始值，那么通常算法可以保证配准结果的收敛。但是,在一个完全陌生的观测场景，粗配准是一项更具有挑战性的工作，这项工作目前仍是一个研究热点。遵循由简入难的原则，本节先对精配准算法进行介绍。点云精配准】9迭代最邻近点（IterativeClosestPoint,ICP）算法被认为是当今应用最广泛的一种精配准参数优化算法，该算法由BeslPJ和MckayHD在1992年提出1，是一种高层次的基于自由形态曲面的配准方法。ICP算法不仅能够处理点云与点云之间的配准问题，而且对点云到模型、模型到模型的配准问题同样具有一定的效果。点云精配准01基于统计学的方法参与配准的两组观测数据必须彼此接近。否则，ICP算法可能会陷入局部极小值。这个问题通常通过两组点云的预对齐来解决，也称为粗配准。02基于表面重采样的方法两组观测数据的视场范團必须基本一致，或者待配准视图数据卫必须是参考视图数据的子集。算法中，ICP为每个待配准的数据点都分配一个最近的参考数据点。虽然ICP算法己经可以成功地解决许多配准问题，但仍有几个关键问题需要注意，特别是以下情况需要考感。点云精配准提高配准速度(1)降采样方法。降采样可以仅作用于待配准的目标点云数据，也可以同时应用于参考点云数据和待配准点云数据。随机和均匀的采样策略都是常见的方法。(2)最近点计算。早期的最近点计算策略是用KD树对参考点云进行组织，可以将最近点搜索的复杂度降低到O(glogn)。最近点缓存也加快了ICP的速度，缓存方法是指在点对应搜索时仅在上一次选代中最近点的周围点子集中进行搜索。(3)距离定义。点到面的距离是根据点投影计算的，点云表面模型的知识将在第8章中介绍。尽管距离公式的复杂度增大，但收敛所需的ICP迭代次数减少了。点云精配准提高配准精度(1)可以使用最简单的策略剔除异常值。(2)可以借助其他辅助信息（如颜色和纹理或局部几何特性等）来提高精度。(3)基于概率的方法是提高精度的一类有效方法。点云精配准将观测场景的二维空间规则地细分为大小不变的矩阵单元格，使用单元格内的所有点计算一个概率密度函数（ProbabilityDensityFunction,PDF），执行以下操作。下面具体介绍二维扫描数据的NDT配准算法的步聚。点云精配准点云精配准配准目标是找到一组转换参数，最大化所有的待配准的扫描点位于参考点云中的位置的概率值，即最大似然函数。最大概率值是通过评估每个映射点的分布并对结果求积来确定的。最大化的目标函数为：点云精配准01固定尺寸划分。固定尺寸是最常见的划分方式之，初始化操作简单，而且能容易找到每个点对应的网格。02八叉树划分。如何快速找到每个点对应的网格是搜索速度的关键，八叉树结构是常见的三维搜索树。三维NDT算法最重要的参数是单元格的尺寸。尺寸太大，容易导致损失一些局部特征；尺寸太小则会增加很多计算量。点个数很少的单元格会失去统计的意义，少数数据对结果影响过大。对空间进行单元格划分的方法有以下几种。点云精配准03尺寸细化选代划分。好的初始位置可以加快收敛过程，一种常见的方法就是迭代起始位置，将上一次的终点位姿作为本次的起点位姿。04自适应聚类划分。对点云数据采用聚类算法（如区均值聚类）划分为多个聚类，每个聚类都作为一个NDT单元。05连接单元格。之前提到少于5个点的单元格会被舍弃，导致出现一些空的单元格，因而损失了数据的完整性。06三线性插值。由于固定尺寸划分的单元格计算的PDF在单元格边界出现不连续的情况，插值的方法相当于做了平滑。点云精配准03点云粗配准点云数据的自动化粗配准目前来说还是一个难点。针对不同的数据，有许多不同的方法被提出。粗配准算法求出的位置姿态参数结果可以用作精配准的初始值，从而在局部进行优化配准。在实践中，粗配准预对齐技术不是搜索密集的点对点对应，而是从视图中提取出稀疏的特征点之间的最佳关联对应。点云粗配准简单来说，特征可以是全局的，也可以是局部的。前者是一种紧凑的表示,有效而简洁地描述了整个观测视图；后者基于观测视图的一部分子集计算出局部的和具有区分能力的描述符集合。全局特征描述难以捕捉细节的细微变化，对物体遮挡敏感。如7.1节所介绍的特征提取的内容，局部几何特征一般是点云局部结构上的关键点，提取这些三维关键点的方式与从影像中提取二维特征的方式类似。点云粗配准】9点云粗配准】9四点一致集（4-PointCongruentSet,4PCS）配准算法是由AigerD等人在2008年提出来的适用于各种点云的一种快速搜索关联点对的算法，4PCS不需要先验信息的搜索策路。点云粗配准超级四点(Super4-PointCongruentSet,Super4PCS)算法。Super4PCS算法是对4PCS配淮算法拓展的加速方案。这种算法在4PCS配准算法的基础上额外记录两条直线相交的角度，判断角度是否在一定范围内。0102普适四点一致集(Generalized4-PointCongruentSet,G-4PCS)算法。G-4PCS算法是对Super4PCS算法的进一步扩展132，此时提取的4个点不再要求共面。点云粗配准超点SP实质上就是由部分点组成的一个点集合，并将这个集合当作整体处理流程的基本单元。下面介绍LORAX粗配准算法的基本流程。（1）随机选择球包络内点集合(RandomSphereCoverSet,RSCS)。为了能够覆盖点云的绝大部分，采用以下的迭代步骤来定义这些超点。（2）为每个SP建立一个归一化的局部坐标系。（3）投影获得深度图。（4）显著性检测和SP筛选。（5）深度自动编码器(DeepAuto-Encoder,DAE)降维。（6）选择候选匹配。（7）迭代寻优配准。点云粗配准04异源三维数据的配准融合异源配准算法是将点云的其他属性信息(比如颜色、强度和几何信息)相结合进行配准的方法，或者将影像重建的点云与LiDAR扫描的点云进行跨模态方式的配准。例如，将RGBD深度图基于颜色的配准方案和基于几何位置的配准方案相结合，并推广到无序点云中用于点云配准。异源三维数据的配准融合】9异源三维数据的配准融合】9异源三维数据的配准融合05应用举例】9应用举例】9本章所列的配准算法都是针对两组观测数据设计的配准算法。观测数据是序列化的多组，可以在连续的观测数据之间成对地执行配准。一般来说，即使所有的成对数据都能明显地被很好地配准，由于存在配准误差的累积和传播，在所有数据整合后，重构完整模型时依然会出现一些失准。应用举例为了解决全局配准问题，多视点配准技术利用多视点之间的相互依赖性，引入额外的约束，以减少全局错误。PulliK提出了一种全局方法，首先将扫描数据两两对齐，然后在多视图匹配步骤中使用两两对齐作为约束。其目的是均匀地分配两两配准的误差，但该方法本身仍然是基于两两对齐的。通常减小累计误差的方法都是在所有视图中均匀地分配误差。另外，有研究基于著名的广义普罗科斯特斯分析（GeneralizedProcrustesAnalysis）方法来设计新算法，将数学理论无缝嵌入ICP框架。该方法的一种变体是使用基于曲率的相似性度量对配准的对应关系进行非均匀加权，实现误差的分配。应用举例01基于优化技术的配准算法02基于概率统计的配准算法利用概率方法，可通过采用最大似然估计来解决场景目标柔性变换的不确定性。概率方法的基础是通过核密度函数对每个点集进行建模。通过引入适当的距离函数来计算这些密度函数之间的差异。配准是在没有明确建立匹配点对应的情况下进行的。实际上，该类算法通过优化一个联合概率模型来配准两组数据，该数据模型覆盖了它们之间的所有点到点对应关系。应用举例06小结三维数据的配准融合是一个十分活跃的研究方向,仍有许多问题需要解决。普适性、稳定性、精准性和自动化程度是评价一种配准算法的性能优劣的主要指标项。为了避免穷举搜索，许多算法利用