赋权图匹配问题的一种新的松弛模型

图匹配是一个NP难(NP-hard)问题. 基于置换矩阵是非负正交矩阵这一经典结论, 提出赋权图匹配(Weighted graph matching, WGM)的双向松弛障碍规划, 理论上证明新模型的解与原模型的解是一致的. 该规划是一个二元连续规划, 它是正交矩阵上的线性优化问题, 同时也是非负矩阵上的凸二次优化问题. 故设计求解新模型的交替迭代算法, 并证明算法的局部收敛性. 数值实验表明, 在匹配精度方面, 新方法强于线性规划方法和特征值分解方法.     

含各向异性尺度形变数据集匹配问题的Lie群方法

通过分析含各向异性尺度形变的数据集匹配问题, 将尺度约束引入模型, 再结合迭代最近点(Iterative closest point, ICP)方法的一般过程, 将含各向异性尺度形变的数据集匹配问题描述为Lie群约束优化问题. 通过Lie群的局部参数化和局部线性化方法, 将带尺度上下界约束的Lie群约束优化问题转化为一系列的二次规划问题, 最终形成了一个完整的匹配迭代算. 该方法不仅具有传统ICP方法的快速准确的特点, 而且还能够处理存在大尺度形变的数据集匹配问题. 由于对尺度参数进行约束, 因此比传统方法有更好的鲁棒性. 最后, 为确保匹配的全局性, 给出了一套初始变换的选择方案.