作者：小毛
Date：2020-05-07
泉源 ：点云局部特征形貌 综述
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算法只管 能找到配准全局最优解，可是 通常都极为耗时。
对于基于对点对应关系的配准要领，绝大部门是依赖基于点云局部特征形貌 与匹配建设的点对点匹配，也有一部门是基于二元或三元点对点对应关系。这类要领通常首先在两组点云之间检测一系列希罕 要害点，通过在要害点上提取局部点云特征并举行 特征匹配即可建设点对点的对应关系。由于待配准点云通常仅仅具有部门重叠区域，需要例如采样一致性（random sample consensus，RANSAC）等匹配筛选算法剔除误匹配并从准确 匹配子集中估算变换矩阵。该类配准算法和基于BnB的配准算法相比具有更高效、稳固 性更强等优点，是现在 点云配准的一个尺度方案。其中，点云局部特征形貌 和特征匹配是尤为要害的两步。
至此，这篇文章主要先容 了点云局部特征形貌 与特征匹配的研究意义与研究价值；然后叙述 了特征形貌 子、特征匹配与点云配准的海内外研究现状，后续将先容 一些较量 fancy的局部特征形貌 算法、特征匹配要领、点云配准算法以及基于深度学习的点云特征融合要领等。