1.1 研究目的及意义

伴随着第三次人工智能浪潮的到来，研究如何赋予机器自然视觉，实现对客观世界的三维场景的感知、识别和理解成为近几年学术研究的热点问题。研究表明，人类大脑皮层的70%活动都在处理视觉信息。而人工智能旨在让机器可以像人那样思考、处理事情，因此计算机视觉被视为人工智能的重要分支。

计算机视觉是指用摄像机和电脑模拟人类视觉对目标进行识别、跟踪、测量等的机器视觉，并通过识别和分析做进一步的图形处理，使电脑处理成为更适合人眼观察或传送给仪器检测的图像。这门技术对于建立能够从图像或多维数据中获取“信息”的人工智能系统起着很大的作用。机器之所以能够完成需要用上人类智能的任务和特定功能，很大部分是依靠计算机系统中的计算机视觉，比如视觉感知、图像识别、人脸识别、目标定位等等。

而图像匹配是计算机视觉领域一个基础而关键的问题，其目标在于寻找多幅图像之间的特征点对应关系，可以实现不同视角下的立体空间感知、物体之间的相似特征感知，图像匹配技术在立体视觉匹配、目标识别与跟踪、医学图像分析、遥感图像处理等方面都有广泛应用。当我们需要整合从不同角度或不同传感器获取的图像所包含的信息，或者需要找出在不同时间或不同拍摄条件下获取的图像之间的异同，又或为了分割或目标检测而进行基于模型的匹配时，建立一个好的图像匹配往往是必不可少的。

在所有特征中，点特征是最为简单的，其本质上由空间中点的坐标来表示。而相对于其它类型的特征，点特征又具有很大优势，且为其他一些更加复杂特征的基础。例如，曲线和曲面特征的提取通常是为了融入除点集坐标信息以外的额外信息。由于点特征为所有特征的基础，点集匹配是从图像匹配各种具体应用中抽象出来最基本的一个问题，其中“点”通常为角点或由特征提取算法获取的其它一些点特征，例如图像的兴趣点和形状轮廓的采样点。本文将致力于研究基于点特征的方法并对点集匹配技术进行深入的探讨。同时，对点集匹配技术的深入研究不仅可以对点集匹配技术进行改善，还可以为研究基于其它特征的方法带来启发。

1.2 国内外研究现状

目前，各领域学者从不同角度对点集匹配问题进行了研究，本文的研究背景是计算机视觉与模式识别领域。从已发表文献来看，点集匹配技术主要可分为以下三类：

（1）基于特征描述子与几何约束的算法 此类方法的基本思路是首先依据特征点局部描述子之间的相似性建立粗略的点集匹配关系，然后在此基础上采用鲁棒算法拟合点集间的几何变换模型，同时估计点集间的精确对应关系。这里可以采用的描述子类型包括二维情况下的 SIFT 和 形状上下文（shape context，SC）以及三维情况下的自旋图（spin image）和MeshDOG/MeshHOG等。 此类算法最具代表性的是由 Fischler 和 Bolles 于 1981 年提出的 RANSAC 算法，该算法能够应付大比例的离群点。其首先计算一个初始点匹配集，然后采用鲁棒方法施加参数模型的几何约束。RANSAC 使用一个假设-验证的框架，其通过重复随机采样数据中一个可以估计模型参数的最小子集来估计模型参数，然后测试每次估计的模型参数在原始数据上的支持度以确定最优解。RANSAC 有多个变种， 诸如 MLESAC、LO-RANSAC、PROSAC等，它们改进 RANSAC 算法的采样策略或定义支集的方法。RANSAC 系列算法依赖于具体的几何参数模型，而当场景中包含非刚性运动时则难以适用。为了解决这个问题，近期一些新的基于非参数模型点集匹配算法也被提出，例如采用对应函数识别点对应（ICF）。

（2）基于估计对应矩阵的算法 求解点集匹配问题的另一种策略是结合参数或非参数的几何约束估计两个点集的对应矩阵（correspondence matrix）。所谓对应矩阵，即描述两个点 集（假设分别有 #119872; 和 #119873; 个点）对应关系的 #119872; × #119873; 的矩阵 #119875;，其中矩阵每个元素 #119875;#119898;#119899; ∈ [0, 1] 指示第一个点集中第 #119898; 个点与第二个点集中第 #119899; 个点的匹配度。 与前一类独立估计点集对应关系与变换函数的方法不同，基于估计对应矩阵的方法联合估计点集间的对应关系与变换函数。这类方法通常用于求解点集配 准问题。为了优化目标函数，常用的手段是迭代估计两个未知变量。ICP 算法（iteratedclosest point）是此类方法中应用最为广泛的方法之一，其通过挖掘点集邻域结构信息为对应矩阵进行二元赋值，然后使用估计出的对应关系来计算变换函数。Rangarajan 等人基于 Yuille 和 Grzywacz 早期的工作在点集匹配问题中建立了估计对应关系与变换函数的一个基本框架。特别地，对于非刚性情况，其采用薄板样条（thin-platespline，TPS）对变换函数进行建模，并基于确定性退火（deterministic annealing）与软指派（soft-assignment）策略提出了一个鲁棒点匹配算 法（TPS-RPM）。另外，一致性点漂移（coherencepoint drift，CPD）算法采用高斯径向基函数代替薄板样条，其对应了另一种不同的正则化方式。在这些数学模型中，刚性和非刚性的情况均可以处理，但它们通常不能容忍过多离群点，而且在所有可能的匹配中进行搜索本身属于NPC 问题。此外，为了达到鲁棒性的目的，此类算法通常对未匹配上的点施加惩罚。