二分图的最优匹配（KM算法）
KM算法用来解决最大权匹配问题： 在一个二分图内，左顶点为X，右顶点为Y，现对于每组左右连接XiYj有权wij，求一种匹配使得所有wij的和最大。
基本原理
该算法是通过给每个顶点一个标号（叫做顶标）来把求最大权匹配的问题转化为求完备匹配的问题的。设顶点Xi的顶标为A[ i ]，顶点Yj的顶标为B[ j ]，顶点Xi与Yj之间的边权为w[i,j]。在算法执行过程中的任一时刻，对于任一条边(i,j)，A[ i ]+B[j]>=w[i,j]始终成立。
KM算法的正确性基于以下定理：
若由二分图中所有满足A[ i ]+B[j]=w[i,j]的边(i,j)构成的子图（称做相等子图）有完备匹配，那么这个完备匹配就是二分图的最大权匹配。
首先解释下什么是完备匹配，所谓的完备匹配就是在二部图中，X点集中的所有点都有对应的匹配或者是
Y点集中所有的点都有对应的匹配，则称该匹配为完备匹配。
这个定理是显然的。因为对于二分图的任意一个匹配，如果它包含于相等子图，那么它的边权和等于所有顶点的顶标和；如果它有的边不包含于相等子图，那么它的边权和小于所有顶点的顶标和。所以相等子图的完备匹配一定是二分图的最大权匹配。
初始时为了使A[ i ]+B[j]>=w[i,j]恒成立，令A[ i ]为所有与顶点Xi关联的边的最大权，B[j]=0。如果当前的相等子图没有完备匹配，就按下面的方法修改顶标以使扩大相等子图，直到相等子图具有完备匹配为止。
我们求当前相等子图的完备匹配失败了，是因为对于某个X顶点，我们找不到一条从它出发的交错路。这时我们获得了一棵交错树，它的叶子结点全部是X顶点。现在我们把交错树中X顶点的顶标全都减小某个值d，Y顶点的顶标全都增加同一个值d，那么我们会发现：
1）两端都在交错树中的边(i,j)，A[ i ]+B[j]的值没有变化。也就是说，它原来属于相等子图，现在仍属于相等子图。
多模态图像匹配与配准技术研究
摘要：
多模态图像匹配与配准技术是计算机视觉领域中的一个重要研究方向。图像匹配与配准是指通过计算相似性或者一一对应关系，将不同传感器或者不同模态的图像进行一致性比较和对齐。本文将就多模态图像匹配和配准的定义、现有技术和未来发展进行详细阐述。
第一章 引言
1.1 研究背景
随着计算机视觉技术的不断发展和应用场景的扩大，多模态图像匹配与配准技术逐渐成为一个热门的研究方向。多模态图像匹配与配准技术能够帮助我们将不同模态或传感器获得的图像进行比较和对齐，从而实现更广泛的应用。例如，在医学影像领域，不同传感器获取的图像往往具有不同的特征和分辨率，通过多模态图像匹配与配准技术可以将它们对齐，便于医生进行更准确的诊断和分析。
1.2研究内容
本文旨在深入探讨多模态图像匹配与配准技术，全面梳理该领域的研究内容，主要包括以下四个方面：
（1）多模态图像匹配与配准的定义和原理：详细介绍多模态图像匹配与配准的概念、基本原理及其在医学、计算机视觉等领域的应用背景。
（2）多模态图像匹配与配准的应用领域：阐述多模态图像匹配与配准技术在生物医学、机器人视觉、遥感图像处理等领域的具体应用，展示其在实际问题中的重要价值。
（3）现有的多模态图像匹配与配准技术：对比分析当前主流的多模态图像匹配与配准方法，包括基于特征描述子的图像匹配方法、基于深度学习的图像匹配方法、特征点配准方法以及基于直接法的图像配准方法等。 （4）多模态图像匹配与配准的挑战和未来发展方向：分析当前多模态图像匹配与配准技术面临的挑战，如数据量大、计算复杂度高、鲁棒性不足等问题，并提出未来可能的研究方向，以期为该领域的发展提供有益的参考。
第二章 多模态图像匹配与配准的定义和原理
本章将首先介绍图像匹配和图像配准的概念及方法。
2.1图像匹配的概念和方法
2.1.1图像匹配的定义：图像匹配是指在两幅或多幅图像之间寻找一一对应的像素点，使得匹配后的图像能够在一定程度上满足某种相似性度量。
图论学习笔记
⽬录图的概念简史欧拉与⼽尼斯堡七桥问题
等价问题：“欧拉⼀笔画”\(\equiv\)与任⼀个顶点相关联的边必须是偶数条。图的基本概念图⽆向图邻接与关联
邻接与关联：
\((p,q)\)图
另⼀种表⽰⽅法：(p,q)图图相等与特殊的图
图相等、特殊的图（平凡图、零图）有向图
疑惑：⽆向图是集合反⾃反、对称的关系。有向图中为保证反⾃反性，去掉了⾃⾝到⾃⾝的有向线段\(\{(v,v)|v \in V\}\)。但是，图是不允许存在⾃⾝到⾃⾝的边吗？
答案：是的。图的表⽰图解法与邻接矩阵法
图解法与邻接矩阵法：
问题：关系的闭包在图中的意义是什么？图模型
利⽤图建模现实问题，并⽤图的理论加以解决的能⼒。
例⼦：结婚问题、地图与导航⼦图⼦图概念⽣成⼦图
特例：⽣成⼦图
记号：去除顶点u，去除边{u,v}
尤其地，注意去除边的记号不是去除u、v两个顶点。导出⼦图
（1）顶点导出⼦图：若V1⊆V(G)，则以V1为顶点集，以两个顶点均在V1中的边集组成的图，称为图G的顶点导出⼦图，记为G(V1)。
例如：求G(V1)，V1 ={1,3,5}
则G(V1)为
（2）边的导出⼦图：若E1⊆E(G),则以E1为边集，以E1中所有边的顶点为顶点集组成的图，称为图G的边的导出⼦图，记为G(E1)。
例如：求G(E1)，E1 = {13,24,35}则G(E1)为度度的概念
定理1——握⼿定理
【定理1】握⼿定理
证明：每⼀条边对度数总和的贡献为2（每⼀条边对应两个顶点），由于共有q个边，故度数总和为2q。
推论1：握过奇数次数⼿的⼈为偶数个。
证明：将⼈分为两类，握奇数次⼿\(V_1\)和握偶数次⼿\(V_2\)，
那么，\(V_1\)与\(V_2\)中顶点的度数总和为偶数（2q），
同时，\(V_2\)的度数之和必然为偶数，
那么，\(V_1\)的度数之和必然为偶数（偶数-偶数=偶数），
同时，由于\(V_1\)中均是握奇数次⼿（\(V_1\)中各顶点度均为奇数），
一种求解二部图最大匹配问题新算法及其应用
唐敏;关健;邓国强;王海刚
【摘 要】This paper proposed an algorithm for maximum matching of
Bipartite graph based on layered network model. Timetable Problems are
solved by the new algorithm. A matching rule for layered networks is
defined and proposed a concept of layered network first,and a layered
network system is generated with the breadth first search strategy.
Maximal matching is found according reversed network order. Experiments
show that this algorithm can get accurate results and has a good
performance with computational complexity in solving large-scale
theoretical and practical maximum matching problems of bipartite graph.%提出了解决二部图最大匹配问题的分层网络优化算法,并应用新算法对排课问题进行求解.定义了分层网络的概念及匹配的规则,结合广度优先搜索策略生成分层网络体系,然后按网络逆序找出最大匹配.实验表明,算法在解决大规模二部图最大匹配的理论问题和实际应用问题时均能获得准确的结果,具备良好的性能.
【期刊名称】《计算机系统应用》
【年(卷),期】2012(021)003
