LiSA图匹配算法

平方级复杂度

将图匹配转化为一维线性分配，用排序替代经典谱方法的四阶张量计算，大规模图匹配首次实现实用化。

Shen, Binrui · 牛强 · 朱圣鑫

Journal of Computational and Applied Mathematics 2025

技术优势

复杂度降两个量级

算法将谱匹配中的四阶张量计算替换为排序操作，时间与空间复杂度均由 O(n⁴) 降至 O(n²)。

可直接处理大规模图

原算法因 O(n⁴) 的空间开销无法处理大规模图匹配，新算法因复杂度降低，使大规模任务变得可行。

实现只需排序

将匹配问题转化为一维线性分配后，核心计算就是对两个 n×1 向量排序，比原方法更易实现。

应用场景

• 图像匹配：大规模图像匹配中可用低复杂度算法替代谱匹配，减少计算资源消耗。
• 点云配准：点云配准常需处理海量关键点，新算法使快速匹配成为可能。
• 网络对齐：网络对齐可将节点对应问题转化为线分配，用排序高效求解。
• 机器人视觉：机器人视觉中的实时匹配需求可从降低复杂度中直接受益。