计算机视觉三维测量与建模 课件 第7、8章 点云特征提取和三维配准、三维表面建模与网格模型滤波

第七章计算机视觉三维测量与建模点云特征提取和三维配准南京航空航天大学研究生教育教学改革专项（优质教学资源建设）项目资助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小结三维数据的配准融合是一个十分活跃的研究方向,仍有许多问题需要解决。普适性、稳定性、精准性和自动化程度是评价一种配准算法的性能优劣的主要指标项。为了避免穷举搜索，许多算法利用基于三维特征提取和特征匹配的技术实现更有效的配准策略。小结特别是特征点检测和描述可以大大减少分析点的数量。部分算法将三维数据与二维影像进行配准融合,为点云数据提供颜色、纹理信息，从而丰富了特征表达能力。这些努力都是为了提高特征的辨识度，但由于尺度和邻域定义存在差异，特征参数的选择仍有太多的不确定性。小结ICP算法和NDT算法是当前应用最为广泛的两类三维点云配准算法，其原理清晰、易于实现，经过不同的改进，得到了多样化的发展。两种算法都有非常多的拓展和变体，使其能够处理更广泛的场景。小结感谢观看第八章计算机视觉三维测量与建模三维表面建模与网格模型滤波南京航空航天大学研究生教育教学改革专项（优质教学资源建设）项目资助01三维表面网格模型】9在计算机上存储表面模型的网格（Mesh）的方法有很多种。不同的数据结构在编码、内存和访问性能方面具有非常不同的复杂性。这些结构的核心是存储定义网格的两类信息，即在创建的网格中会编码两种类型的信息：几何信息（即顶点在空间中的位置和表面法向量）和拓扑信息（即网格的连通性以及面之间的关系）。三维表面网格模型】9以三角形网格为例，网格中的每个三角形都和其他三角形共享边。这样的网格模型包含三类基本几何信息：每个三角形都有三个顶点，各顶点都有可能和其他三角形共享；边，一个三角形有三条边，每条边都连接了两个顶点：面，每个三角形都对应一个面，可以用顶点列表或边列表来表示面。010203三维表面网格模型在实际的数据存储中，一个网格模型通常会存储顶点列表和三角形列表（图8.2），存储多边形网格时，还需要定义一个多边形类，用来表达有任意多顶点的面。顶点列表中的每个顶点包含的最基本数据是一个三维坐标，也可能含有点的法向量和颜色亮度等附加数据。每个三角形由对应于顶点列表的三个索引组成，其中顶点索引的顺序是非常重要的，因为一个三角形的三个顶点顺序关系到该三角形面的“正面”和“反面”。一般会用逆时针方向列出顶点指示的面为正面，这样该面的法向量与三个点的列表顺序满足右手螺旋指向，另外预先计算的面的法向量和纹理坐标等也可以存储在面列表中。三维表面网格模型半边数据结构（FalfedgeDataStructure）是流形网格模型中的一种数据存储表达方式，其最大特点是定义了半边(Halfedge）的概念。如图8.4所示，网格的每条边都被分为两个半边，每条半边都是一个有向边，两条半边的方向相反。如果一条边被两个面元公用，则每个面元都能各自拥有一条半边。构造立体几何（ConstructiveSolidGeometry,CsG）是一种基于简单初级实体基元组成的对象模型表示法。CSG的模型通过初级实体集合的布尔型运算组合在一起。三维表面网格模型】9第一类算法是直接计算几何建模算法，也称为豆式建模算法，包括计算凸包（Convex

Fulls）、计算狱洛尼三角剖分（DelaunayTriangulation）和计算阿尔法形状（cshape）等代表性算法。显式建模算法主体上通过连接采样点构建三角形，是对采样点的精确插值。第二类是隐式建模算法，这类算法假设采样点云中隐含一种能够近似表达几何表面模型的隐函数。该类算法将空间区域假设为一个标量场，即由采样点云构造一个函数值分布空间。三维表面网格模型】9第三类算法是利用先导模式化结构对目标进行建模，是一种自上而下的建模算法。在第6章中介绍基于模型的场景结构分割的理论时，对模式化的结构有所定义，可以说这里的模式化建模就是在点云模型化分割的基础上形成网格的一种后处理。基于模板或者先验模式的重建方法可以细分出更多种类、更复杂的子类，随应用场景的不同而可以有多种多样的设计形式。三维表面网格模型纹理模式纹理模式是用于三维模型的真实可视化的直观表达方式，纹理是让三维模型看起来接近现实物体的一个最基本的要素。最简单形式的纹理贴图涉及将单个纹理（如照片或正射影像）映射到由一个或多个多边形组成的表面多边形上。当将影像映射到对象上时，每个对象的多边形颜色都将由从纹理派生的相应颜色进行修改。01三维表面网格模型阴影模式阴影模式（ShadingModel）是基于光学理论（兰伯特余弦定理）设计的，该理论指出，基于完美散射起伏表面的任何小区域（多边形）的亮度都会随着入射平行光角度的余弦而增大。该算法中，最广为人知的是平面阴影和平滑阴影。平面阴影和平滑阴影之间的主要区别在于使用法线的方式。02三维表面网格模型光照模式要为真实场景创建这样一个完整的模型，需要使用大量的视图。这些视图可以视为具有相应颜色值的光线集合，它们是一个完全连续函数的离散样本。考虑到物理限制的附加信息，必须从记录的光线中插入未表示的光线。03三维表面网格模型01压缩数据的几何形状：这类算法试图改善网格的数字信息（顶点的位置、法线、颜色等）的存储，或者寻求对网格拓扑进行有效编码的方法。02控制细节层次(LOD)：出于可视化目的，软件可以用LOD技术在整个场景中平滑变化，不同位置的渲染的细腻程度取决于观察者所在的当前位置。03网格滤波（Filtering）优化和简化(Decimation）：这些算法简化了网格，去掉了冗余的顶点、边和三角形基元，可以选代地移除不符合特定距离/角度标准的顶点，或将边折叠成唯一的项点。04点渲染：特别适用于点云可视化，并且通过是示较少数量的图元来工作。QSplat是一个基于点的渲染系统，能够使用不同复杂形状的溅斑（Splat）图元和不同的透明度米渲染相同的对象，以避免锯齿边缘，在实时性和渲染方面是示出良好的效果。基于网格模型的几何信息和拓扑结构这两个信息，学者们针对三角形网格模型提出了许多压缩算法。三维表面网格模型02显式建模方法凸集有两种定义方式。第一种：如果对任意两点2.9ES，线段P9CS，则集合S是凸的。第二种：如果集合5是(可能无限多个）半空间的交集，则S是凸的。图8.7给出了凸集和非凸集的二维示例。显式建模方法显式建模方法二维空间的Delaunay三角剖分Delaunay三角剖分是一种标准，己有许多计算Delaunay三角剖分的算法，它们主要依赖于检测点是否在三角形的外接圆内，需要设计快速存储三角形的有效数据结构。增量式的枸网算法是最直接有效地计算Delaunay三角剖分的算法。这类算法通过逐点添加的形式插入新顶点，确定图形受影响的部分，仅对一部分区域进行三角剖分约束判断和优化调整。显式建模方法二维空间的Delaunay三角剖分01显式建模方法三维点云数据的Delaunay三角剖分02把Delaunay三角剖分的屈性从二维扩展到更高的三维，其背后的原理是一致的。三维点云的Delaunay三角剖分的约束是四个点组成的四面体（4个三角形）的外接球不包含其他的点，即要生成符合空外接球规则的四面体组成。显式建模方法三维点云数据的Delaunay三角剖分对三维点云处理，依然适用增量式的Delaunay三角剂分算法。首先，初始化一个大的四面体，能够将场景中的所有三维点都包含在内，大四面体的顶点不一定是输入数据的点。然后，依次逐点向其中插入新的顶点，进行判断和构网。每次插入新顶点p时，需要判断点p是落在哪一个四面体的内部，这个四面体被视为一个父节点，新的顶点会将父节点四面体剖分重组，父节点四面体进而被标注为无效。新生成的四面体被视为子节点。寻找父节点的方法可以是遍历己经生成的列表中的所有四面体，也可以是通过设计数据结构加速检索。显式建模方法】9显式建模方法03隐式建模方法】9隐式建模方法】9隐函数表达式：隐式建模方法径向基函数（RadialBasisFunctions,RBF）是一种常用的对离散数据插值的函数方法。对于一组给定采样数据，RBF方法使用一组径向对称的基函数的线性组合生成高度平滑的拟合结果。隐式建模方法隐式建模方法移动最小二乘（MovingLeastSquares,MIS）算法将重建表面近似为一个空间变化的低阶多项式。如8.3.1节所达，隐式表面建模对应的是一个插值问题，MLS算法用局部多项式f(x)逼近表面F。用移动最小二乘算法将插值问题变为一个函数优化问题，f(x)被选为对数据点x的最佳名项式逼近。隐式建模方法隐式建模方法】9泊松表面重建方法（PoissonReconstruction）是KazhdanM等人在2006年提出的种隐函数建模方法143，并且提供了开源代码，是目前广为使用的一种表面建模方法。泊松表面重建方法利用Poisson两数来解决有向点云的表面拟合问题。它结合了全局拟合和局部拟合两类方法的特点，因此在速度和精度两个方面有较好的效果。由于全局优化的特性，在形成邻近区域、选择面片类型和调整权重时不涉及启发式的决策。另外，基函数是和周围空间相关的而不仅是和数据点相关的，有一个局部层次支持的结构，从而产生稀疏的优良表现。隐式建模方法】9隐式建模方法01下面介绍用MC算法构建网格模型的步骤：将三维空间规则地进行体素化，离散后的每个体素单元都包含8个顶点{v1,…,v8}，每个顶点都能够由隐函数计算出对应的函数值，即计算出f(vi）。02对体素的顶点进行标记。如果f(vi)的值大于或等于零等值面的值，则认为该顶点位于等值面之外，标记为“0”03根据8个顶点的二进制标记值计算体素的素31号index。隐式建模方法04根据体素的索引号index，在预先构建好的查找表中找到体素内的网格的连接方式。05尽管知道了等值面会穿过哪条边，如边（VaVb），但具体在边上会经过的点位置还没有确定。此时，需要通过插值计算找到，可以使用边的两个顶点位置由简单的线性插值计算。06消除歧义。在算法中设计了根据体素顶点的法向量消除这样的不连贯歧义。在整体的体素划分空间中，每个顶点有上、下、左、右、前、后6个相邻的顶点，采用中心差分方