图的匹配算法

Ⅰ opencv关于像素点的图像匹配算法

首先，建议你将图像中感兴趣区域（比如上图中的字母）取出来进行归一化，然后在进行匹配率计算。这是因为周围环境会对匹配率产生影响。
其次，建议你将匹配率算法改成Hausdorff距离https://en.wikipedia.org/wiki/Hausdorff，这样对图像有些平移什么的都不怎么敏感了。

Ⅱ 图像匹配的算法

迄今为止，人们已经提出了各种各样的图像匹配算法，但从总体上讲，这些匹配算法可以分成关系结构匹配方法、结合特定理论工具的匹配方法、基于灰度信息的匹配方法、基于亚像元匹配方法、基于内容特征的匹配方法五大类型 基于内容特征的匹配首先提取反映图像重要信息的特征，而后以这些特征为模型进行匹配。局部特征有点、边缘、线条和小的区域，全局特征包括多边形和称为结构的复杂的图像内容描述。特征提取的结果是一个含有特征的表和对图像的描述，每一个特征由一组属性表示，对属性的进一步描述包括边缘的定向和弧度，边与线的长度和曲率，区域的大小等。除了局部特征的属性外，还用这些局部特征之间的关系描述全局特征，这些关系可以是几何关系，例如两个相邻的三角形之间的边，或两个边之间的距离可以是辐射度量关系，例如灰度值差别，或两个相邻区域之间的灰度值方差或拓扑关系，例如一个特征受限于另一个特征。人们一般提到的基于特征的匹配绝大多数都是指基于点、线和边缘的局部特征匹配，而具有全局特征的匹配实质上是我们上面提到的关系结构匹配方法。特征是图像内容最抽象的描述，与基于灰度的匹配方法比，特相对于几何图像和辐射影响来说更不易变化，但特征提取方法的计算代价通常较，并且需要一些自由参数和事先按照经验选取的闭值，因而不便于实时应用同时，在纹理较少的图像区域提取的特征的密度通常比较稀少，使局部特征的提 取比较困难。另外，基于特征的匹配方法的相似性度量也比较复杂，往往要以特征属性、启发式方法及闭方法的结合来确定度量方法。基于图像特征的匹配方法可以克服利用图像灰度信息进行匹配的缺点，由于图像的特征点比象素点要少很多，因而可以大大减少匹配过程的计算量同时，特征点的匹配度量值对位置的变化比较敏感，可以大大提高匹配的精确程度而且，特征点的提取过程可以减少噪声的影响，对灰度变化，图像形变以及遮挡等都有较好的适应能力。所以基于图像特征的匹配在实际中的应用越来越广-泛。所使用的特征基元有点特征明显点、角点、边缘点等、边缘线段等。

Ⅲ 图像匹配的匹配关键要素

同一场景在不同条件下投影所得到的二维图像会有很大的差异，这主要是由如下原因引起的：传感器噪声、成像过程中视角改变引起的图像变化、目标移动和变形、光照或者环境的改变带来的图像变化以及多种传感器的使用等。为解决上述图像畸变带来的匹配困难，人们提出了许多匹配算法，而它们都是由如下四个要素组合而成：
（1）特征空间
特征空间是由参与匹配的图像特征构成的，选择好的特征可以提高匹配性能、降低搜索空间、减小噪声等不确定性因素对匹配算法的影响。匹配过程可以使用全局特征或者局部特征以及两者的结合。
（2）相似性度量
相似性度量指用什么度量来确定待匹配特征之间的相似性，它通常定义为某种代价函数或者是距离函数的形式。经典的相似性度量包括相关函数和 Minkowski 距离，近年来人们提出了 Hausdorff 距离、互信息作为匹配度量。Hausdorff 距离对于噪声非常敏感，分数 Hausdorff 距离能处理当目标存在遮挡和出格点的情况，但计算费时；基于互信息的方法因其对于照明的改变不敏感已在医学等图像的匹配中得到了广泛应用，它也存在计算量大的问题，而且要求图像之间有较大的重叠区域。
（3）图像匹配变换类型
图像几何变换用来解决两幅图像之间的几何位置差别，它包括刚体变换、仿射变换、投影变换、多项式变换等。
（4）变换参数的搜索
搜索策略是用合适的搜索方法在搜索空间中找出平移、旋转等变换参数的最优估计，使得图像之间经过变换后的相似性最大。搜索策略有穷尽搜索、分层搜索、模拟退火算法、Powell方向加速法、动态规划法、遗传算法和神经网络等。遗传算法采用非遍历寻优搜索策略，可以保证寻优搜索的结果具有全局最优性，所需的计算量较之遍历式搜索小得很多；神经网络具有分布式存储和并行处理方式、自组织和自学习的功能以及很强的容错性和鲁棒性，因此这两种方法在图像匹配中得到了更为广泛的使用。
在成像过程中，由于噪声及遮挡等原因，导致一幅图像中的特征基元在另一幅图像中有几个候选特征基元或者无对应基元，这些都是初级视觉中的“不适定问题”，通常在正则化框架下用各种约束条件来解决。常用的约束有唯一性约束、连续性约束、相容性约束和顺序一致性约束。首先提取左右图像对中的线段，用对应线段满足的全局约束、相容性约束、邻域约束等表示 HopfieIk 神经网络的能量函数，通过最小化能量函数得到两幅图像中的对应线段，提高了匹配的可靠性。同时人们还采用最小平方中值法和投票算法等后处理来有效地消除假配点和误配点。

Ⅳ 双目视觉的匹配算法是不是有好几种具体是哪几种

与普通的图像模板匹配不同的是，立体匹配是通过在两幅或多幅存在视点差异、几何畸变、灰度畸变、噪声干扰的图像对之间进行的，不存在任何标准模板进行匹配。立体匹配方法一般包含以下三个问题:(1)基元的选择，即选择适当的图像特征如点、直线、相位等作为匹配基元;(2)匹配的准则，将关于物理世界的某些固有特征表示为匹配所必须遵循的若干规则，使匹配结果能真实反映景物的本来面目;(3)算法结构，通过利用适当的数学方法设计能正确匹配所选择基元的稳定算法。

根据匹配基元的不同，立体视觉匹配算法目前主要分为三大类,即区域匹配、相位匹配和特征匹配:

基于区域灰度的匹配算法是把一幅图像(基准图)中某一点的灰度邻域作为模板，在另一幅图像(待匹配图)中搜索具有相同(或相似)灰度值分布的对应点邻域，从而实现两幅图像的匹配。这类算法的性能取决于度量算法及搜索策略的选择。另外，也必须考虑匹配窗口大小、形式的选择，大窗口对于景物中存在的遮挡或图像不光滑的情况会更多的出现误匹配，小窗口则不具有足够的灰度变化信息，不同的窗口形式对匹配信息也会有不同的影响。因此应该合理选取匹配区域的大小和形式来达到较好的匹配结果。

相位匹配是近二十年发展起来的一种匹配算法，相位作为匹配基元，即认为图像对中的对应点局部相位是一致的。最常用的相位匹配算法有相位相关法和相位差——频率法，虽然该方法是一种性能稳定、具有较强的抗辐射抗透视畸变能力、简单高效、能得到稠密视差图的特征匹配方法。但是，当局部结构存在的假设不成立时，相位匹配算法因带通输出信号的幅度太低而失去有效性，也就是通常提到的相位奇点问题，在相位奇点附近，相位信息对位置和频率的变化极为敏感，因此用这些像素所确定的相位差异来衡量匹配误差将导致极不可靠的结果。此外，相位匹配算法的收敛范围与带通滤波器的波长有关，通常要考虑相位卷绕，在用相位差进行视差计算时，由于所采用的相位只是原信号某一带通条件下的相位，故视差估计只能限制在某一限定范围之内，随视差范围的增大，其精确性会有所下降。

基于特征的图像匹配方法是目前最常用的方法之一，由于它能够将对整个图像进行的各种分析转化为对图像特征(特征点、特征曲线等)的分析的优点，从而大大减小了图像处理过程的计算量，对灰度变化、图像变形、噪音污染以及景物遮挡等都有较好的适应能力。

基于特征的匹配方法是为使匹配过程满足一定的抗噪能力且减少歧义性问题而提出来的。与基于区域的匹配方法不同，基于特征的匹配方法是有选择地匹配能表示景物自身特性的特征，通过更多地强调空间景物的结构信息来解决匹配歧义性问题。这类方法将匹配的搜索范围限制在一系列稀疏的特征上。利用特征间的距离作为度量手段，具有最小距离的特征对就是最相近的特征对，也就是匹配对。特征间的距离度量有最大最小距离、欧氏距离等。

特征点匹配算法严格意义上可以分成特征提取、特征匹配和消除不良匹配点三步。特征匹配不直接依赖于灰度，具有较强的抗干扰性。该类方法首先从待匹配的图像中提取特征，用相似性度量和一些约束条件确定几何变换，最后将该变换作用于待匹配图像。匹配中常用的特征基元有角点、边缘、轮廓、直线、颜色、纹理等。同时，特征匹配算法也同样地存在着一些不足，主要表现为:

(l)特征在图像中的稀疏性决定了特征匹配只能得到稀疏的视差场，要获得密集的视差场必须通过使用插值的过程，插值过程通常较为复杂。

(2)特征的提取和定位的准确与否直接影响特征匹配结果的精确度。

(3)由于其应用场合的局限性，特征匹配往往适用于具有特征信息显着的环境中，在缺少显着主导特征环境中该方法有很大困难。

总之，特征匹配基元包含了算法编程上的灵活性以及令人满意的统计特性。算法的许多约束条件均能清楚地应用于数据结构，而数据结构的规则性使得特征匹配非常适用于硬件设计。例如，基于线段的特征匹配算法将场景模型描绘成相互联结的边缘线段，而不是区域匹配中的平面模型，因此能很好地处理一些几何畸变问题，对对比度和明显的光照变化等相对稳定。特征匹配由于不直接依赖于灰度，计算量小，比基于区域的匹配算法速度快的多。且由于边缘特征往往出现在视差不连续的区域，特征匹配较易处理立体视觉匹配中的视差不连续问题。

Ⅳ 匹配的图的定义

设有M个工人x1,x2，…，xm，和N项工作y1,y2，…，yn，规定每个工人至多做一项工作，而每项工作至多分配一名工人去做。由于种种原因，每个工人只能胜任其中的一项或几项工作。问应怎样分配才能使尽可能多的工人分配到他胜任的工作。这个问题称为人员分配问题。
人员分配问题可以用图的语言来表述。令X={x1,x2，…，xm}，Y={y1,y2，…，yn}，构造二分图G=(X,Y,E）如下：
对于1≤i≤m，1≤j≤n，当且仅当工人xi胜任工作yi时，G中有一条边xiyi，于是人员分配问题就成为在G中求一个最大匹配的问题。
求最大匹配常用匈牙利算法，它的基本思想是：对于已知的匹配M，从X中的任一选定的M非饱和点出发，用标号法寻找M增广链。如果找到M增广链，则M就可以得到增广；否则从X中另一个M非饱和点出发，继续寻找M增广链。重复这个过程直到G中不存在增广链结束，此时的匹配就是G的最大匹配。这个算法通常称为匈牙利算法，因为这里介绍的寻找增广链的标号方法是由匈牙科学者Egerváry最早提出来的。
理解了这个算法，就不难写出人员分配问题的解答了。在给出程序之前，先做一些假设：
为了简单起见，假设工人数等于工作数，即N=M，且N≤100，这里，N也可以看作是二分图的|X|和|Y|。
数据从文件input . txt中读入，首先是N和|E|，下面|E|行每行两个数（I,J），表示工人I可以胜任工作J，即二分图中的边xiyj。
结果输出到文件output . txt，第一行是最大匹配数s，下面s行每行两个数（I,J），表示分配工人I做工作J，即匹配边xiyj。 对于上面的人员分配问题，如果还考虑到工人做工的效率，就可以提出所谓的分派问题：应该怎样分配才能使总的效率最大？
同上一节，我们可以构造一个二分图G，如果把工人xi做工作yi的效率wij看作是G中边xiyi的权，则分派问题就相当于在赋权二分图G中求一个最大全匹配。
由线性规划的知识，求二分图G的最大权匹配，只需在匈牙利算法的基础上少许改进即可。它的基本思想是，对二分图的顶点编号，然后根据编号构造一个新的二分图G’，最后把求G的最大权匹配转换为求G’的完美匹配。
下面的这条定理是这个算法的理论基础。
定理：设M是赋权图（权非负）的完全二分图G=(V，E）的一个完美匹配，这里M是E的子集。如果M满足：对G的任意一个完美匹配M'，均有M的边权值之和大于M'边的权值之和，则M是G的最大权匹配。
下面，给出求最大权匹配的程序。输入文件中首先是N和|E|，下面|E|行每行三个数（I,J,W），表示工人I做工作J的效率是W。程序输出包括每个工人的选择和最后的总效益。其它假设参见上一节的算法假设。这个算 问题：FJOI-信封问题
John先生晚上写了n封信，并相应地写了n个信封将信装好，准备寄出。但是，第二天John的儿子Small John将这n封信都拿出了信封。不幸的是，Small John无法将拿出的信正确地装回信封中了。
将Small John所提供的n封信依次编号为1，2，…，n；且n个信封也依次编号为1，2，…，n。假定Small John能提供一组信息：第i封信肯定不是装在信封j中。请编程帮助Small John，尽可能多地将信正确地装回信封。其中n≤100。
例如，有4封信，而且第一封信不是装在信封1、2和3中，第2封信不是装在信封2和3中，则可以确定的第一封信装在信封4中，而且第二封信则装在信封1中。但这些条件还不足以确定第三封和第四封信的位置。
分析：
看了这道题目，感觉上和小学数学竞赛中的逻辑推理题如出一辙，而逻辑推理题的做法一般是表上作业法。
就以前面的例子为例，根据条件，可以得到如下信息：
1 2 3 4
1 × × ×
2 × ×
3
4
表格 1
由于每一行每一列都应该只有一个√，因此，可以确定第一封信装在信封4中，于是可以得到：
1 2 3 4
1 × × × √
2 × × ×
3 ×
4 ×
表格 2
然后，发现第二行有3个×，因此剩下一个肯定是√，于是就可以得出第二封信则装在信封1中：
1 2 3 4
1 × × × √
2 √ × × ×
3 × ×
4 × ×
表格 3
现在，第3行和第4行都只有两个×，因此无法确定它们放在那个信封里。
这样我们就得到了一个初步的算法：在程序中建立一个二维表格，首先，根据条件填入若干个×，然后，检查所有还未确定的行和列，看有没有一行（列）中有n – 1个×，如果没有，就结束；否则，把剩下的那一个空格填上√，并且填了√的那一行（列）的其它位置都填上×。
这种方法虽然很容易想到，但却有针对这个方法的反例，例如：
图表 3 一个反例
图中上半部分的顶点表示“信”，下半部分的顶点表示“信封”，如果信i可能放在信封j中，则在信i和信封j之间连一条边。由于每个顶点的度数都大于或等于2，即每行每列都至少有两个空位，故前面的算法无法进行任何推理，而事实却并非如此，比如说中间的那封信就只能放在中间的那个信封里。
正是这个反例，使我们需要另辟蹊径。进一步分析可以发现，信和信封之间的关系，是一种一一对应的关系，这是因为一封信只能放到一个信封里，而一个信封也只能装一封信。而从信息学的角度来看，这种一一对应的关系，也可以看作是二分图的匹配关系。
令X={x1,x2，…，xm}，Y={y1,y2，…，yn}，构造二分图G=(X,Y,E），当且仅当信i可以放到信封j中，G中存在边xiyj。这样，任何一种信的分配方案，都可以看作是图G的一个完美匹配。例如上图就有且仅有如下两种完美匹配：
图表 4 所有的完美匹配
由于中间的那条匹配边在两个完美匹配中都出现了，因此我们认为这条匹配边是“确定的”，换句话说，这条边所代表的关系也是确定的。容易看出，当且仅当对于G的所有完美匹配M，都存在一条匹配边xiyj，则可以确定信i可以放到信封j中。
这样，我们就从匹配的角度建立了一个新的模型。那么，这个模型要如何求解呢？
我们当然不能枚举出G所有的完美匹配，然后再去求它们边的交集——这和搜索就没什么分别。在这里，我们需要对这个模型再做一个小小的转换：我们发现，条件“对于G的所有完美匹配M，都存在一条匹配边xiyj”，等价于“如果图G存在完美匹配，而删除图G中的一条边xiyj得到的图G’中却不存在完美匹配”。例如，左下图删除了一条“关键边”，故不存在完美匹配，而右下图删除的是一条“非关键边”，故存在完美匹配。
图表 5 删边的例子
从表面上看，这个算法的时间复杂度似乎仍然很高。因为图G中最多有n2条边，每次试着删除一条边，又需要O(n3）的时间复杂度求一次完美匹配。总的复杂度高达O(n5）。
实际上，我们可以先找到图G的一个完美匹配M，这样，删边就只需考虑匹配边了（因为删除非匹配边得到G’，M仍然是G’的完美匹配）。这样，只需删除n条边，时间复杂度就降到了O(n4）。
再进一步分析，删除一条边以后，没有必要重新找完美匹配，只需检查可不可以找到新的增广链就可以了。这样，时间复杂度就进一步降到了O(n3）。 问题：CTSC-丘比特的烦恼
随着社会的不断发展，人与人之间的感情越来越功利化。最近，爱神丘比特发现，爱情也已不再是完全纯洁的了。这使得丘比特很是苦恼，他越来越难找到合适的男女，并向他们射去丘比特之箭。于是丘比特千里迢迢远赴中国，找到了掌管东方人爱情的神——月下老人，向他求教。
月下老人告诉丘比特，纯洁的爱情并不是不存在，而是他没有找到。在东方，人们讲究的是缘分。月下老人只要做一男一女两个泥人，在他们之间连上一条红线，那么它们所代表的人就会相爱——无论他们身处何地。而丘比特的爱情之箭只能射中两个距离相当近的人，选择的范围自然就小了很多，不能找到真正的有缘人。
丘比特听了月下老人的解释，茅塞顿开，回去之后用了人间的最新科技改造了自己的弓箭，使得丘比特之箭的射程大大增加。这样，射中有缘人的机会也增加了不少。
情人节（Valentine's day）的午夜零时，丘比特开始了自己的工作。他选择了一组数目相等的男女，感应到他们互相之间的缘分大小，并依次射出了神箭，使他们产生爱意。他希望能选择最好的方法，使被他选择的每一个人被射中一次，且每一对被射中的人之间的缘分的和最大。
当然，无论丘比特怎么改造自己的弓箭，总还是存在缺陷的。首先，弓箭的射程尽管增大了，但毕竟还是有限的，不能像月下老人那样，做到“千里姻缘一线牵”。其次，无论怎么改造，箭的轨迹终归只能是一条直线，也就是说，如果两个人之间的连线段上有别人，那么莫不可向他们射出丘比特之箭，否则，按月下老人的话，就是“乱点鸳鸯谱”了。
作为一个凡人，你的任务是运用先进的计算机为丘比特找到最佳的方案。
输入文件第一行为正整数k，表示丘比特之箭的射程，第二行为正整数n(n<30），随后有2n行，表示丘比特选中的人的信息，其中前n行为男子，后n行为女子。每个人的信息由两部分组成：他的姓名和他的位置。姓名是长度小于20且仅包含字母的字符串，忽略大小写的区别，位置是由一对整数表示的坐标，它们之间用空格分隔。格式为Name x y。输入文件剩下的部分描述了这些人的缘分。每一行的格式为Name1 Name2 p。Name1和Name2为有缘人的姓名，p是他们之间的缘分值（p为小于等于255的正整数）。以一个End作为文件结束标志。每两个人之间的缘分至多只被描述一次。如果没有被描述，则说明他们缘分值为1。
输出文件仅一个正整数，表示每一对被射中的人之间的缘分的总和。这个和应当是最大的。
分析：
题目中出现了三类物体和两种关系，我们一个个的来分析：
丘比特的箭，它有一个属性是射程，
男人和女人，他们的属性包括名字和位置，
男人和女人之间的关系，这个关系是他们俩的缘分值，
箭与男女的关系，如果两人的距离不超过箭的射程，并无他人阻挡，则可能被箭射中。题目就是要求一种射箭的方案，使得所有被射中的男女的缘分和最大。
这个问题很像是要求一个二分图的最大权匹配。因为男人和女人分属两个集合，而且同性之间没有任何关系，因此是一个二分图。而把缘分值记做边上的权，则缘分和最大，就对应了这个二分图中的一个最大权匹配。
要注意的是，题目中虽然说明没有被描述的男女之间缘分值为1，但这并不代表所得到的二分图是完全二分图。因为在构图的过程中，我们必须还考虑到箭的射程等因素——如果两人的距离超过了箭的射程，则他俩注定无缘了。
这时问题就来了，因为题目中除了要求缘分和最大之外，还要求“被丘比特选择的每一个人都要被射中一次”。
你可能会觉得，要缘分和越大，当然被射中的人越多越好，其实并不是这样。例如：
图表 6 一个反例
如果要求最大权匹配，则会选择匹配边AD，缘分和为10。但由于每个人都要被射中一次，因此我们只能选择AC和BD，缘分和为2。
换句话说，对于这个例子，正确答案应该是2，而最大权匹配的值却是10。这说明，这道题目和简单的最大权匹配还是有区别的，因为题目再要求权值最大的同时，还要求是一个完美匹配，我们称之为“完美”的最大权匹配。
那么，这道题是否就不能用最大权匹配来做了呢？先别急，我们再来回顾一下求最大权匹配的算法：我们通过对顶点编号，将图G转化为G’，然后在把求G的最大权匹配转换为求G’的完美匹配——这里好像就是求完美匹配，但对于上面的那个例子，又为什么不呢？
原来，对于上面的例子，在标号过后，新的图G’中加入了一条新的边BC，而这条边的权值是0，在图G’中的完美匹配，实际上是AD和BC，对应到图G中，就是边AD了。
因此，如果我们预先把BC的边的权值设为－∞，再求图中的最大权匹配，就不会再有问题了。
更一般的，如果要求二分图的“完美”的最大权匹配，只需将原图中没有的边的权值设为－∞，就可以了。 问题：IPSC-Magic
一个着名的魔术师上台表演，跟着他的是一位漂亮的女助手。魔术师先从他的魔术帽中拽出了几只兔子，接着他又从女助手的围巾中变出了一束鲜花，最后，他把女助手锁在一个看上去空着的箱子里。然后，魔术师选了一个观众来配合一个表演：他在一个桌子上摆出N张牌（所有N张牌两两不同，且N为奇数）。魔术师让这位自愿者走上讲台从中选出（N+1)/2张牌，其余的牌都在魔术师的帽子里永远的消失了。魔术师在选出的牌上方晃了晃手，接着他选出其中一张交给那一位自愿者，自愿者向观众展示了手中的这张牌，随后又将其藏在自己的衣袋里。那位女助手从箱子里放出来后，来到桌前也在剩下的（N+1)/2－1张牌上方晃了晃手，马上就说出了自愿者衣袋中的是什么牌。
这是为什么呢？我们先看一下下面这张表，这是N=5的情况：
自愿者选的牌 魔术师选的牌 助手所看到的牌
1，2，3 3 1，2
1，2，4 2 1，4
1，2，5 2 1，5
1，3，4 4 1，3
1，3，5 1 3，5
1，4，5 1 4，5
2，3，4 4 2，3
2，3，5 3 2，5
2，4，5 5 2，4
3，4，5 5 3，4
表格 4
其中，自愿者选的牌－魔术师选的牌=助手所看到的牌。表中包括了自愿者选牌的所有可能性，它们两两不同。而助手所看到的牌，也是两两不同的。
首先，魔术师和他的助手都要记住这张表。这样，当助手看到的牌是2，4时，她就可以肯定自愿者选的牌是2，4，5，且魔术师选的牌就是5。
现在，告诉你n的值，要你求出这张表。其中n≤15。
分析：
为了便于分析，我们令M表示从N张牌中选取（N+1)/2张牌的方案数，显然，从这N张牌中选出（N+1)/2－1张牌的方案数也是M。
我们先从枚举的角度入手，下面给出两种枚举的方法：
对于自愿者的每种选牌的方案，枚举魔术师所选的牌。
对于自愿者的每种选牌的方案，所对应的助手看到的牌。
方案一需要M次决策，每次决策中有N种选择；方案二同样需要M次决策，而每次决策的可以有M种选择。从这点上来看，方案一要好得多。、
可是方案一所表现出来的“自愿者的选牌的方案”和“魔术师所选的牌”之间的关系并不是一一对应的关系，对于自愿者不同的选牌的方案，魔术师可以选择相同的牌。
而方案二中所表现出的关系正是一一对应的关系，因为题目要求对于自愿者不同的选牌的方案，助手看到的牌必须不同。
前面已经提到过，从信息学的角度来看，一一对应，也可以看作是一种二分图的匹配的关系。因此，方案二更容易让人联系到匹配。
令X=自愿者的选牌的方案集，Y=助手看到的牌的集合，构造二分图G=(X,Y,E），当且仅当 时，G中存在边xiyj。这样，就把原问题转换成求图G的一个完美匹配。
下面问题又来了。首先，二分图的顶点高达2M个，当N=15时，M接近8000，而求匹配的复杂度为O(M3），这样高的复杂度，如何能够承受？
注意到这个图是一个稀疏图，一共只有MN条边。而稀疏二分图匹配的复杂度也可以表示成O(|V|×|E|）。因此，时间复杂度应该是O(M2N），基本上可以承受了。
另外，由于这是稀疏图，我们用邻接表来存储，则空间复杂度仅为O(NM），同样可以承受。
最后要说明的是，这道题目也可以用构造法以获得更好的效率，但不如匹配容易想到。具体的构造方法这里就不给出了，读者可以自己想一想。 问题：OOPC-神秘之山
M个人在追一只奇怪的小动物。眼看就要追到了，那小东西却一溜烟蹿上一座神秘的山。众人抬头望去那山看起来就是这个样子：
图表 7 样例示意图
那山由N+1条线段组成。各个端点从左到右编号为0…N+1，即x<x[i+1](0≤i≤n）。而且有y[0]=y[n+1]=0。
根据经验来说那小东西极有可能藏在1…N 中的某个端点。有趣的是大家很快发现了原来M恰好等于N，这样，他们决定每人选一个点，看看它是否在躲那里。
一开始，他们都在山脚下，第i 个人的位置是（s,0）。他们每人选择一个中间点（x,0），先以速度w水平走到那里，再一口气沿直线以速度c爬到他的目的地。由于他们的数学不好，他们只知道如何选择一个最好的整数来作为中间点的横坐标x。而且很明显，路线的任何一个部分都不能在山的上方（他们又不会飞）。
他们不希望这次再失败了，因此队长决定要寻找一个方案，使得最后一个到达目的地的人尽量早点到。他们该怎么做呢？
其中1≤N≤100，0≤x,y,s≤1000，1≤c<w≤100。
输入
第一行包含一个整数N。以下N+2行每行，包含两个整数xi和yi，代表相应端点的坐标。以下N行每行包含3个整数：ci,wi和si，代表第i个人的爬山速度，行走速度和初始位置
输出
输出最后一个人到达目的地的最早可能时间，四舍五入到小数点后两位。
样例输入
3
0 0
3 4
6 1
12 6
16 0
2 4 4
8 10 15
4 25 14
样例输出
1 . 43
样例说明
在这里例子中，第一个人先到（5 .0）再爬到端点2；第二个人直接爬到端点3；第三个人先到（4 .0）再爬到端点1。如下图：
图表 8 样例的解答
分析：
题目中的数据繁多复杂，我们先把他们提出来一个个分析：
人，共n个，与之有关的有初始横坐标s，速度w和c
山头，共n个，与之有关的有坐标x和y
根据这些信息，可以得到，人和山头的关系：t[I,J]，表示第i个人到达山头j所需的最短时间。
题目中已经指明是一个人负责一个山头，这显然是一个一一对应的关系，因此，我们可以从二分图的匹配的角度来考虑这个问题。
那么，这道题目属于哪一种匹配呢？是简单的最大匹配，还是最大权匹配，或者是前面所提到的“完美”最大权匹配呢？
其实都不是。因为一般的最大权匹配，一个匹配的权的定义是该匹配中所有边上权的和，而这道题目，一个匹配的权是指该匹配的边上权值的最大值。题目要求这个最大值最小，我们暂且称之为“最小最大匹配”。
直接求解似乎不太方便。换一个角度，如果我们给出一个时间，就可以用完美匹配的算法来判断能否在这个时间内完成所有的工作。
具体的来说，对于给定的二分图G和最大时间T，我们可以导出新的图G’，G’中所有边的权都不超过T。如果G’存在完美匹配，则所有工作可以在T时间内完成，否则则不能。
这样，一个简单的算法就诞生了：依次增加T，知道求出一个完美匹配为止。由于二分图中的边不会超过n2，因此T最多增加n2次，而每次增加T的值，需要O(n2）的时间来找增广链，这样总的时间复杂度就是O(n4）。
我们还可以采用二分查找的方法来寻找这个T，这样的算法时间复杂度就可以降到为O(n3logN）。

Ⅵ 图像匹配的概述

图像匹配是指通过一定的匹配算法在两幅或多幅图像之间识别同名点，如二维图像匹配中通过比较目标区和搜索区中相同大小的窗口的相关系数，取搜索区中相关系数最大所对应的窗口中心点作为同名点。其实质是在基元相似性的条件下，运用匹配准则的最佳搜索问题。