1.引言
在计算机视觉发展初期，机器对客观世界的视觉感知主要依赖相机捕获的二维图像或图像序列。然而世界在欧氏空间内是三维的，图像因为仅仅捕捉了世界在某个视角下投影的信息将在对物体的尺度和几何属性表征上产生不确定性。相比之下，点云（Point cloud）作为一种最原始的三维数据表征能够精准地反映物体的真实尺寸和形状结构，逐渐成为了机器视觉感知所依赖的另一种数据形式。
图1 典型的主动式和被动式点云传感器。（a）Velodyne 激光雷达及其扫描的点云数据，（b）ZED 立体视觉相机及其捕获的点云数据。
点云是一种由若干离散、无序、无拓扑结构的三维点组成的集合，通常是三维传感系统所获取数据的初始形式，具有抗光照和尺度变化等优点。当前主流的点云数据传感器分为两类：主动式和被动式。主动式传感器又可分为基于 TOF（Time of Flight）系统和三角测量系统两种，其中 TOF 系统通过测量所发射信号到达物体表面和返回接收器之间的时间间隔来确定传感器到物体表面的真实距离，而三角测量系统则通过两个传感器在不同地点对物体同一点之间的测量关系计算点的空间位置。被动式传感器依赖图像对或图像序列并根据相机参数来从二维图像数据中复原出三维数据。典型的主动式传感器包括 LiDAR（Light Detection And Ranging）、TOF 相机、结构光传感器等；典型的被动式传感器包括立体相机、SFM（structure from motion）系统、SFS（shape from shading）系统等。图1展示了 Velodyne 激光雷达和 ZED 双目相机以及它们捕获的点云数据。近年来，诸如微软 Kinect、谷歌 Tango 平板、英特尔 Real Sense 等廉价传感器的涌现使得点云数据的获取和图像一样便捷，进一步推动了三维计算机视觉技术的发展。
图2 三维点云局部特征描述与匹配示意图
和图像感知类似，对于点云数据的感知任务包括检测、识别、分类、分割、匹配等，本专栏致力于研究点云视觉任务中一个基础而关键的问题，即点云之间点对点对应关系的建立。该问题也被称作三维点匹配问题，在计算机视觉、计算机图形学、遥感、机器人等领域均有着广泛的应用。以源点云和目标点云来命名两组待匹配的点云序列，当两组点云之间发生了旋转、平移等刚性变换时，称之为刚性点云匹配数据；当两组点云之间发生了伸缩、仿射、变形等非刚性变换时，则称之为非刚性点云匹配数据。本文研究的数据对象为刚性点云匹配数据，通常为传感器在不同视角或不同场景下捕获的刚体目标点云数据序列。对于刚性点云匹配数据之间的点对应关系建立通常包含两步：局部几何特征描述和特征匹配。如图2所示，局部几何特征描述的目的是用一个特征向量来表征隐含在局部曲面内的空间信息和几何信息；特征匹配的目的是通过度量两组点云特征集中任意两个特征的相似性确定初始匹配并筛选出正确的匹配子集。当点云数据体量较大时，在初始点云中检测若干稀疏且具有区分能力的关键点是一种常用的预处理方案。在二十一世纪初期，曾有一系列点云关键点检测子被陆续提出，例如三维 Harris 检测子（Harris 3D，H3D）和本征形状签名（intrinsic shape signature，ISS）。但最近关于点云关键点检测子评估研究指出现有的检测子在现实应用场景数据中可重复性低且较为耗时。另外，取代传统关键点检测子的均匀采样和随机采样方法在目标识别以及点云配准应用中均被证明为一种快速有效的关键点选取方式。因此，当前的研究热点主要集中在点云局部特征描述和特征匹配两方面。
对于点云局部特征描述子的质量评估主要体现在以下五个方面：
• 刚体变换不变性—当目标或者传感器进行了旋转和平移等刚体运动时，在对应点提取的局部特征应当具有不变性；
• 描述性—因为点和点之间是一一对应的，局部特征需要具有一定的鉴别能力来区分相同目标之内或不同目标之间的局部几何模式；
• 鲁棒性—局部特征需要对由于自遮挡、遮挡、嘈杂、测量距离变化等引起的孔洞、噪声、数据分辨率变化等干扰具有鲁棒性；
• 时效性—机器人等实时性高的应用平台对于局部特征计算的速度有着严格的要求；
• 紧凑性—局部特征的紧凑性取决于其占用的内存资源，主要受特征维度和特征数据类型影响，紧凑性高的局部特征有着维度低、二值化等特点。
然而，现有的点云局部特征仍难以充分满足上述需求，而且对于数据模态和应用场景的变化较为敏感。对于特征匹配的质量评估一方面体现在抗离群点（错误匹配）的干扰能力，另一方面体现在匹配的效率。评估研究表明大部分现有特征匹配算法存在耗时长、对高离群点率敏感的缺陷。
2.研究意义
首先从工程应用的角度来例证本研究所能带来的社会价值，然后分析当前点云局部特征描述与匹配领域存在的难点与挑战来表明理论研究意义。点云局部特征描述与匹配在计算机视觉、计算机图形学、机器人学、遥感等领域具有重要的实际应用价值，对应的应用场景通常取决于两组点云序列的分别表征的物理含义，可分为“不同视角”、“不同时刻”、“模型-模型”以及“模型-场景”四类。照此分类，我们分别例举点云局部特征描述与匹配在如下实际场景中的应用：
•不同视角：此类数据利用点云之间的点匹配关系旨在估算不同视角点云序列之间的空间变换关系，从而完成姿态归一化来得到更大视场范围内的点云或进行三维重建。在计算机视觉领域的应用包括三维目标重建、三维场景重建以及三维数据融合。在遥感领域的应用包括大场景遥感点云拼接以及地形场景重建。在文化遗产保护领域的应用包括基于多目点云拼接重建的古文物数字模型库构建，在我国该技术已被应用于故宫数字博物馆的建立。
•不同时刻：对于该类数据，点云特征匹配可以解算物体在给定时间内所产生的三维旋转和空间位移变化，从而得到物体在三维空间中的运动信息包括速度、角速度、动量等并能跟踪运动物体。在计算机视觉领域的典型应用为三维运动物体的姿态跟踪。在航空航天领域的应用包括太空非合作目标的运动位姿解算等。
•模型-模型：此类数据主要通过建立两个属于同一类别模型之间的特征对应关系来衡量模型之间的相似性。在计算机视觉中的应用包括三维人脸识别和三维物体分类。
•模型-场景：该类数据中模型是指感兴趣目标的三维模型，场景数据则为传感器在特定视角捕获的、包含感兴趣目标的场景数据（通常称为 2.5D 数据），这类数据广泛应用于嘈杂和遮挡环境中的三维目标识别。在计算机视觉中的主要应用为三维目标检测与识别。在机器人领域的主要应用包括物体的抓取及摆放姿态的估计。在国防领域的应用包括空对地的精准目标打击等。
图3 点云局部特征描述与匹配面临的四类主要挑战
点云局部特征描述与匹配的研究已历经三十余年，尽管取得了一定的进展，例如刚体变换不变性问题的解决，但是仍然面临着如下挑战（图 3）：
•噪声：由于环境的干扰和设备的缺陷等因素，初始捕获的点云数据通常含有大量不同尺度的噪声，这种干扰在廉价传感器例如微软Kinect 获取的数据中尤为明显。噪声的存在将扰乱点云的局部几何结构，干扰特征的精准表达。
•数据分辨率变化：尽管点云数据具有尺度不变性，但是相同物体在不同距离被捕获的点云将呈现出不同的分辨率。这里点云的分辨率为一组点云中任意两个相邻点之间的平均距离。不同分辨率的点云对于物体局部形状信息的表达将产生差异，例如低分辨率的点云难以表征物体微小的局部结构，从而进一步增加了特征描述的困难。
•孔洞：物体丰富的形状结构也会造成某个视角下捕获的点云存在自遮挡现象，进一步形成了孔洞；另外某些物体的材质（例如玻璃）也会导致点云数据出现数据缺失。分布在孔洞边缘的局部区域因为数据不完整的问题，将难以对局部曲面原本具有的几何结构进行正确表征。即使在理想情况下，该曲面与对应的匹配曲面之间的相似度也将大大降低，使得问题更具挑战性。
•重复模式：现实世界中有许多物体具有轴对称性，这种对称性将造成重复模式的存在。由于目标的局部模式是一一对应的，这些重复模式将导致特征匹配的二义性。
上述干扰的存在一方面影响着点云局部特征的描述性和鲁棒性，另一方面将造成初始匹配集中掺杂大量误匹配而进一步给正确匹配的识别带来严重干扰。最近关于点云局部特征描述子和特征匹配方法的实验评估表明现存方法难以充分克服以上干扰。
3.点云局部特征描述研究现状
点云局部特征可按照是否基于局部坐标系来分类。我们首先回顾现有的局部坐标系方法，然后简要介绍当前点云局部特征描述子的研究进展。
局部坐标系
局部坐标系（local reference frame，LRF）可以分为基于协方差分析和基于点空间分布两类。对于第一类，Novatnack等人将关键点的法向量定义为局部坐标系的z轴，然后为局部邻域点计算一个协方差矩阵；最大特征值对应的特征向量在z轴的切平面上的投影向量经过归一化后即为x轴；最后，y轴为x轴和z轴的交叉乘积。Mian等人将协方差矩阵对应的三个特征向量定义为局部坐标系的三个轴。这些基于协方差分析的局部坐标系计算方法并没有解决参考轴符号二义性的问题。后来Tombari等人首次利用局部几何特性解决了参考轴符号二义性的问题并提出了一种加权协方差分析方法；该方法被证明具有对噪声鲁棒的特性，然而其主要缺陷为对数据分辨率变化敏感。Guo等人提出首先对局部曲面进行三角化然后为每一个三角面片计算协方差矩阵，其中每个三角面片对应的协方差矩阵具有两个权重；与其它基于协方差分析的方法不同，该方法首次提出对三角面片进行协方差分析并大大地提升了局部坐标系的鲁棒性。
对于第二类方法，Chua和Javis以关键点为球心放置一个球体，得到球体与曲面的交叉轮廓，轮廓所有点中到关键点法向量切平面投影距离最大的点被用来计算x轴；z轴为关键点的法向量，y轴由其余两轴叉乘所得。Petrelli等人为了达到抗遮挡的目的，提出采用邻域点集内一小部分点来计算法向量并作为z轴；邻域边缘区域所有点中对应的法向量与关键点法向量偏移角最大的点被用来计算x轴，他们后续提出利用局部深度来代替法向量偏移角作为选择依据来提升局部坐标系的可重复性。然而，大尺度的噪声对于x轴的计算仍将产生明显的干扰。
局部特征
在现有的众多点云局部特征描述子中，部分是针对非刚性物体的，被称为本征局部描述子，具有抗非刚性变化的能力。在该类描述子中，Sun等人利用在曲面进行拉普拉斯-贝尔特拉米运算和其衍生的空间嵌入计算来获得热核签名描述子（heat kernel signature，HKS）；HKS对等容等距变化具有鲁棒性而且有一定的抗非等容等距变换能力。随后，Aubry等人凭借一种量子力学的方式来描述曲面的多尺度细节并提出波核签名描述子（wave kernel signature，WKS），展现出比HKS更强的区分性。除了手工特征，Litman和Bronstein提出一种基于学习的最优谱变换特征（optimal spectral descriptor,OSD），主要通过学习来获得多种滤波器并在曲面上计算不同频率的谱特征。Boscaini等人提出各向异性传播特征（anisotropic diffusion descriptor，ADD），通过任务驱动的学习方式计算了一系列方向性滤波器，解决了诸多应用中存在的各向同性问题。
和主流的局部特征更为接近的是另外一类针对刚性物体的描述子，可以按是否基于局部坐标系LRF划分为两类。对于非基于LRF的描述子，Johnson和Hebert提出了自旋图特征（spin image，SI），他们首先将关键点的法向量作为参考轴然后将局部邻域点投影到以水平和垂直投影距离为坐标的二维平面，最后通过二维累加运算的方式得到一张二维灰度图；SI是被引用次数最多的描述子之一，但是描述能力有限、对数据分辨率变化敏感。Rusu等人提出利用点特征直方图（point feature histograms，PFH）的方式来编码局部曲面的形状信息；PFH鉴别能力很强但是极为耗时。为了解决该问题，Rusu等人后来利用简化版点特征直方图（simplified point feature histogram，SPFH）来构造快速点特征直方图（fast point feature histogram，FPFH），具有快速、鉴别能力强的特点。Albarelli等人提出一种低维曲面哈希的描述子并将其应用于博弈论框架下的曲面匹配问题中；曲面哈希特征主要基于多尺度的局部属性统计直方图计算，包括法向量夹角、积分体积以及它们的结合。
对于基于LRF的特征，Stein和Medioni基于关键点与测地邻域点之间的偏移角、扭转角和曲率关系来设计点云的局部特征。Frome等人将二维中的形状上下文特征（shape context，SC）扩展到三维领域并提出三维形状上下文特征（3D shape context，3DSC）；3DSC首先将局部球域划分为多个子空间并计算每个子空间内的点占比来计算特征描述子。Malassiotis凭借在点云局部曲面上方的虚拟相机对点云进行“快照”的方式进行特征表达，这种特征表达首次表明了局部深度这种属性的强区分性，然而因为其仅获取了局部曲面单个视角信息的缘故，具有的描述能力仍然有限。Zaharescu等人为每个邻域点计算了梯度向量并将它们投影在LRF的三个正交平面上；每个平面被划分为四个象限，每个象限对应一个八维特征，最后所有象限内特征的串接形成了名为MeshHOG的描述子。Tombari等人提出了方向直方图特征（signature of histograms of orientations，SHOT）；SHOT首先对局部球域进行空间划分，然后为每个子空间计算一个反映子空间内点的法向量和关键点法向偏移角统计量的特征，最后计算每个子空间对应特征的串接向量；尽管SHOT描述性很强，但是对点密度分辨率的变化敏感。最近，Guo等人首先将局部曲面在LRF中不断旋转，并对每一次旋转后的曲面进行投影来计算一些投影后点密度的统计量，最后将这些统计量串接得到旋转投影统计量特征（rotational projection statistics，RoPS）；RoPS在多个数据集中取得了当前领先的匹配性能，其不足主要为在对点分布不均的数据描述性差、计算较为耗时。和RoPS的旋转投影机制类似，Guo等人利用LRF的三个正交轴来计算三个自旋图特征，得到的三元自旋图（triple spin images，TriSI）和RoPS相比抗遮挡能力更强，但仍较为耗时。
4.特征匹配研究现状
特征匹配在二维和三维领域内均得到了广泛的关注。
二维特征匹配
Leordeanu和Hebert基于高置信度的匹配通常以聚类方式呈现的假设，提出了一种谱分析的方法；其首先为匹配集构建一个图，每个节点代表一个对点对的匹配，每条边代表匹配之间的兼容性，从而构建出一个邻接矩阵并从基于该矩阵对应的特征值发现具有一致性的匹配聚类。Torresani等人通过最小化一个关于匹配相似度和空间兼容性的能量函数来对初始匹配进行排序打分。这两种方法要求初始匹配集具有较高的内点率。为了解决该问题，Cho和Lee将图的概率级数与图匹配相结合，提出了一种渐进匹配的框架。然而，大部分图匹配的方法可扩展性不强。Lowe设计了一种高效的方式来为匹配的可区分性进行打分，主要基于计算最小与次小特征距离之间的比率；这种方法能有效解决可重复模式造成的匹配二义性问题，但是缺乏对匹配空间一致性信息的利用，得到的匹配正确率较低。
三维特征匹配
三维特征匹配方法中有一部分是直接根据特征相似度或特征比率分数来进行正确匹配筛选。几何刚性约束被用来检验两匹配之间的空间一致性。对于基于投票机制的方法，Tombari和Stefano提出了三维霍夫变换方法（3D Hough voting，3DHV）；借助于LRF之间的变换，该方法将匹配投影到一个三维空间并通过找到三维空间核密度最大的点来确定一致性匹配集群。Johnson和Hebert设计了结合距离和方向信息的匹配约束项并基于此来寻找满足该约束项的最大特征匹配聚类，该聚类则被认为是筛选出的正确匹配子集；后来Chen和Bhanu采用了仅包含距离的约束项并表明该改进对于噪声干扰具有更强的鲁棒性。Buch等人将局部约束和全局约束集成到了一个投票的框架下来判定匹配的正确性。
5.点云配准研究现状
刚体数据之间的点对应关系最直接的应用为点云配准，即求解源点云和目标点云之间的旋转和平移信息。Besk和Mckay提出的迭代最近点法（iterativeclosest point，ICP）为点云配准领域最为经典的算法之一，ICP算法迭代式地寻找两组点云之间的对应点集并更新变换矩阵来完成配准；ICP算法是一种局部的算法，在没有初始化的情况下容易陷入局部最优。现有的全局配准方法主要分为两类：基于分支定界（branch and bound，BnB）或点对点对应关系。
对于基于BnB的配准方法，Yang等人提出的Go-ICP算法首次完成了ICP框架下的全局最优配准；Go-ICP算法用一个不确定性球来表达几何边界，在配准过程中优化和传统ICP算法一致的距离目标函数并根据几何边界推导出最小值的下界；Go-ICP设计了一种由一个外部BnB和一个内部BnB组成的嵌套BnB模式；其中外部BnB在旋转空间SO(3)中进行搜寻，内部BnB在R3空间内搜寻其对应的最佳平移变换。Campbell和Petersson通过对齐两组点云对应的混合高斯模型（Gaussian mixture models，GMM）来达到配准点云的目的，他们采用了一个和Go-ICP相比更为严格的几何界限，即不确定性球的顶部区域；因为该方法在刚体变换的六维空间进行搜寻，其需要借助于GPU进行加速。Bustos等人采用了类似的几何边界但是建立了一种基于一致性集的目标函数；该方法对于最大一致性集上界的评估依赖将不确定球顶部区域从三维到二维平面上的投影。Lian和Zhang等人提出了APM（asymmetric point matching）算法来解决点集配准问题；APM将点集配准问题建模成一个凹二次分配问题并在BnB框架下进行求解。Straub等人提出了一种基于点云法向量的二阶段BnB算法，其将六维刚体变换空间分解成三维旋转空间和三维平移空间然后分别在分解后的空间内进行寻优。BnB算法尽管能找到配准全局最优解，但是通常都极为耗时。