本文探讨了多媒体和计算机视觉领域的一项关键技术—图匹配问题的形式化与算法设计。图匹配的目标是通过不同事物之间在结构上的相似性,自动地建立两个或者多个图结构之间的节点对应关系。该问题在图像处理、多媒体、计算机视觉、模式识别和图形学,乃至生物信息学等领域得到了广泛的研究和应用。本论文工作主要围绕图匹配问题的两个方面:二图匹配和多图匹配及配准展开,研究成果集中在如下几个方面:首先,作者提出并考察了一种基于线性迭代梯度指派的二图匹配基准算法,对其收敛性质从解空间可行域和相似度特征阶数两方面进行分析论证。对于任意给定的相似度矩阵,作者论证了离散域线性迭代梯度指派算法对于二阶问题将陷入二重循环解,这一结论被推广到解空间为连续域的对应算法。基于这一理论分析,本文提出了一个自适应的目标函数松弛机制,保证新算法收敛到稳态固定解。并进一步论证在问题阶数为N的一般情况下,高阶的线性迭代梯度指派算法具有N重循环解的性质,就此作者提出了新算法保证收敛到稳态解。理论和实验结果表明,离散域算法相对高效,而二阶连续域算法显示了更好的匹配精度。其次,作者提出了在匹配变量交替更新框架下的多图匹配形式化模型和迭代优化算法,将每步迭代中的子问题转化成一个数学上等价的二图匹配问题。同时,该模型可以包容相似度矩阵分解形式和非分解形式,进而可以重用现有的基于两种形式的任意二图匹配算法。更进一步的,论文提出了一个基于两两匹配相容性的评估函数,以此来设定用于推动交替更新的基准图与变量交替更新次序。实验证明,这一机制提升了初始解的质量,并往往能够加快算法迭代的收敛速度。另外,作者将该框架用于多个点集间参数化变换下的配准问题上,并提出了特定的迭代优化配准算法,兼顾配准精度和速度。再次,作者提出了另一个基于自举提升框架的迭代算法。交替更新多图匹配算法本质上是一种期望最大化迭代过程,无法完全避免初始解精度和迭代过程中误差累积对最终结果的负面影响。而自举模型基于两个重要的观察:第一,独立得到的两两匹配解可以通过传递点对应关系的方式得到相似度目标函数和精度的提升;第二,在大噪声的情况下,原有的目标函数无法与匹配精度完全一致,存在精度高的解反而对应的相似度目标函数得分更低的情况。这时,匹配相容性则与整体匹配精度的相关性更强。对于第一个观察,论文设计了基于一阶近似传导的相似度目标函数自举算法;对于第二个观察,论文定义了基于一阶传导的匹配相容性正则项,进一步设计了渐进性注入匹配相容性项的自举提升机制,并证明了部分算法的收敛性质。作者还针对存在大量外点的情况,设计了从多个图中进行公共内点抽取的机制。理论和实验结果表明,基于正则化的自举算法具有较强的鲁棒性,特别是在匹配图数目较多的情况下,显示了出众的匹配精度。最后,作者设计了一个在图属性信息显式表达下基于矩阵恢复凸优化技术的多图匹配算法。一方面,该方法挖掘了图匹配与矩阵恢复这两个问题直接的关联,将多图匹配问题转换成一个矩阵的低秩和稀疏分解问题。这一转化建立了近年来各种层出不穷的凸优化技术与本属于组合优化问题的图匹配之间的桥梁。另一方面,该方法假设属性图的点和边权值信息显式给出,而非像本文提出的其他多图匹配算法仅需给出两图间的相似度函数值。为了使得该方法具有更大的实际价值,作者对单个属性图信息的显式构建进行了初步研究,提出了一个基于行为主体属性个性化互激励点过程模型,从事件数据中挖掘事件各个维度之间的关联,定量描述潜在的属性图结构。理论和实验结果表明,基于矩阵恢复的多图匹配算法复杂度与待匹配的图数目呈线性关系,且具有较好的整体匹配精度。综上所述,本文对图匹配这一基本问题进行了广泛深入的研究。针对任意阶的二图匹配问题,提出了一种自适应松弛原问题的匹配模型和收敛算法;而针对多图匹配(和配准)问题,原创性地提出了三种不同算法,分别侧重于把握问题的不同层面。大量理论分析和实验结果表明,本文提出的一系列方法深入挖掘了图匹配问题的本质,显著提升了图匹配算法的性能。