数图匹配方式
MeiDiFangLing-1_MA5616(config)#interface h248 0 MeiDiFangLing-1_MA5616(config-if-h248-0)#display digitmap-timer ?
---------------------------------------------
h248mgid-0 模式命令：
---------------------------------------------
<cr> 请输入回车以执行命令
MeiDiFangLing-1_MA5616(config-if-h248-0)#display digitmap-timer
-----------------------------------------------------
起始定时器时长(秒) ：20
短定时器时长(秒) ：4
长定时器时长(秒) ：10
持续定时器时长(毫秒) ：3000
-----------------------------------------------------
MeiDiFangLing-1_MA5616(config-if-h248-0)#quit
MeiDiFangLing-1_MA5616(config)#display se?
---------------------------------------------
privilege 模式命令：
---------------------------------------------
section-details Section细节
security <组>security命令组
service-num 查询业务号码
service-port 业务虚端口
---------------------------------------------
user 模式命令：
---------------------------------------------
serial-mode 显示串口的模式：命令行/CQT/112/SPL MeiDiFangLing-1_MA5616(config)#display mg?
---------------------------------------------
privilege 模式命令：
---------------------------------------------
mg-ringmode 振铃参数
mg-software MG接口软件参数
mgbrauser MG-BRA用户操作
mgpstnuser MG-PSTN用户操作
mguser MG用户操作
MeiDiFangLing-1_MA5616(config)#display mg-software ?
---------------------------------------------
privilege 模式命令：
---------------------------------------------
parameter 接口软件参数
MeiDiFangLing-1_MA5616(config)#display mg-software parameter ? ---------------------------------------------
privilege 模式命令：
---------------------------------------------
mgid<U><0,16777215> MG接口标识MeiDiFangLing-1_MA5616(config)#display mg-software parameter 0 ? ---------------------------------------------
privilege 模式命令：
---------------------------------------------
<cr> 请输入回车以执行命令
name<U><0,37> 接口软件参数名称：
2：MG接口是否支持双归属功能
4：注册时是否用通配符
6：是否支持鉴权
7：是否支持安全头
11：自交换允许标志
13：数图匹配方式
15：媒体流源端口过滤开关
16：媒体流源端口过滤定时器时长
22：配置MG与MGC中断后的提示音类型
23：端口状态同步定时器时长
24：RTP终端ID的最大值
25：H248接口防止雪崩机
制最大随机值(ms)
26：本地阻塞放音类型
27：远端阻塞放音类型
28：嚎鸣音时长
29：留言音提示时长
30：超长通话告警时限
31：是否启动超长通话告警
32：远端阻塞端口自动注册最小间隔时长
33：MG是否关闭心跳消息
34：软交换发起的进退服，网关是否要主动针对BRA用户进行拆建链
35：ISDN端口进退服方式
其他为系统预留
MeiDiFangLing-1_MA5616(config)#display mg-software parameter 0 13 ?
---------------------------------------------
privilege 模式命令：
---------------------------------------------
<cr> 请输入回车以执行命令
MeiDiFangLing-1_MA5616(config)#display mg-software parameter 0 13
-------------------------------------------------
接口标识：0 参数名索引：13 参数值：1
-------------------------------------------------
附录：
-------------------------------------------------
参数索引：参数名和含义：
13：数图匹配方式
0：按照协议要求
1：最长匹配
2：最短匹配
3：自适应匹配
Maigo的KM算法讲解(的确精彩) 顶点Ｙｉ的顶标为B［i]，顶点Xi与Yj之间的边权为w[ｉ,j]。在算法执行过程中的任一时刻，对于任一条边(ｉ,j),A［i]+B[j]>=w［i,ｊ]始终成立。KM 算法的正确性基于以下定理： * 若由二分图中所有满足A［i］+B[j]=ｗ[ｉ,ｊ］的边（i，ｊ)构成的子图（称做相等子图）有完备匹配,那么这个完备匹配就是二分图的最大权匹配。 这个定理是显然的。因为对于二分图的任意一个匹配，如果它包含于相等子图,那么它的边权和等于所有顶点的顶标和；如果它有的边不包含于相等子图,那么它的边权和小于所有顶点的顶标和。所以相等子图的完备匹配一定是二分图的最大权匹配。 初始时为了使A［ｉ]＋B[j]>=w[i,j]恒成立,令A[i]为所有与顶点Xi关联的边的最大权，Ｂ[ｊ］＝0。如果当前的相等子图没有完备匹配,就按下面的方法修改顶标以使扩大相等子图，直到相等子图具有完备匹配为止。 我们求当前相等子图的完备匹配失败了,是因为对于某个Ｘ顶点,我们找不到一条从它出发的交错路。这时我们获得了一棵交错树,它的叶子结点全部是X顶点。现在我们把交错树中X顶点的顶标全都减小某个值ｄ,Y顶点的顶标全都增加同一个值d，那么我们会发现：
两端都在交错树中的边(i，j）,A［i]+B[j]的值没有变化。也就是说,它原来属于相等子图，现在仍属于相等子图。 两端都不在交错树中的边(ｉ，ｊ)，A[i］和B[j]都没有变化。也就是说,它原来属于(或不属于)相等子图，现在仍属于(或不属于)相等子图。 X端不在交错树中，Y端在交错树中的边(i，ｊ)，它的Ａ［ｉ]+B[j]的值有所增大。它原来不属于相等子图,现在仍不属于相等子图。 X端在交错树中,Ｙ端不在交错树中的边（i,j),它的A［ｉ]+B[j]的值有所减小。也就说,它原来不属于相等子图，现在可能进入了相等子图,因而使相等子图得到了扩大。 现在的问题就是求d值了。为了使Ａ[i]+Ｂ[j］>=w［i,ｊ]始终成立,且至少有一条边进入相等子图,d应该等于mｉｎ{Ａ[i]+B[ｊ]-w[ｉ,j]｜Xｉ在交错树中,Ｙi不在交错树中｝。 以上就是KＭ算法的基本思路。但是朴素的实现方法，时间复杂度为 O(n4)——需要找O(n)次增广路,每次增广最多需要修改Ｏ(n)次顶标,每次修改顶标时由于要枚举边来求d值,复杂度为O(ｎ2)。实际上KＭ算法的复杂度是可以做到O(n3)的。我们给每个Ｙ顶点一个“松弛量”函数slaｃk，每次开始找增广路时初始化为无穷大。在寻找增广路的过程中,检查边(i,j)时，如果它不在相等子图中，则让ｓlaｃk[j]变成原值与A[i］+B[ｊ］-w[i,j]的较小值。这样,在修改顶标时，取所有不在交错树中的Y顶点的slacｋ值中的最小值作为ｄ值即可。但还要注意一点：修改顶标后，要把所有的ｓｌａｃk值都减去d。
前言： 高中时候老师讲这个就听得迷迷糊糊，有一晚花了通宵看KM的Pascal代码，大概知道过程了，后来老师说不是重点，所以忘的差不多了。都知道二分图匹配是个难点，我这周花了些时间研究了一下这两个算法，总结一下 1.基本概念 M代表匹配集合 未盖点：不与任何一条属于M的边相连的点 交错轨：属于M的边与不属于M的边交替出现的轨（链） 可增广轨：两端点是未盖点的交错轨 判断M是最大匹配的标准：M中不存在可增广轨 2.最大匹配，匈牙利算法 时间复杂度：O(|V||E|) 原理： 寻找M的可增广轨P，P包含2k+1条边，其中k条属于M，k+1条不属于M。修改M 为M&P。即这条轨进行与M进行对称差分运算。 所谓对称差分运算，就是比如X和Y都是集合，X&Y=(X并Y)-(x交Y) 有一个定理是：M&P的边数是|M|+1，因此对称差分运算扩大了M 实现： 关于这个实现，有DFS和BFS两种方法。先列出DFS的代码，带注释。这段代码来自中山大学的教材
核心部分在dfs(x)，来寻找可增广轨。如果找到的话，在Hungarian()中，最大匹配数加一。这是用了刚才提到的定理。大家可以想想初始状态是什么，又是如何变化的 view plaincopy to clipboardprint?
第二种方法BFS，来自我的学长cnhawk 核心步骤还是寻找可增广链，过程是： 1.从左的一个未匹配点开始，把所有她相连的点加入队列 2.如果在右边找到一个未匹配点，则找到可增广链 3.如果在右边找到的是一个匹配的点，则看它是从左边哪个点匹配而来的，将那个点出发的所有右边点加入队列 这么说还是不容易明白，看代码吧
诚信声明 本人声明： 我所呈交的本科毕业设计论文是本人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰写过的研究成果。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。本人完全意识到本声明的法律结果由本人承担。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：日期：2010 年05 月20日
毕业设计（论文）任务书 设计（论文）题目： 学院：专业：班级： 学生指导教师（含职称）：专业负责人： 1．设计（论文）的主要任务及目标 (1) 了解图象匹配技术的发展和应用情况，尤其是基于特征的图象匹配技术的发展和应用。 (2) 学习并掌握图像匹配方法，按要求完成算法 2．设计（论文）的基本要求和内容 （1）查阅相关中、英文文献，完成5000汉字的与设计内容有关的英文资料的翻译。（2）查阅15篇以上参考文献，其中至少5篇为外文文献，对目前国内外图象匹配技术的发展和应用进行全面综述。 （3）学习图象匹配算法，尤其是基于特征的图象匹配算法。 （4）实现并分析至少两种基于特征的图象匹配算法，并分析算法性能。 3．主要参考文献 [1]谭磊, 张桦, 薛彦斌．一种基于特征点的图像匹配算法[J]．天津理工大学报，2006， 22(6)，66-69． [2]甘进，王晓丹，权文．基于特征点的快速匹配算法[J]．电光与控制，2009，16(2)， 65-66． [3]王军，张明柱．图像匹配算法的研究进展[J]．大气与环境光学学报，2007，2(1)， 12-15．
二分图的最优匹配（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]的值没有变化。也就是说，它原来属于相等子图，现在仍属于相等子图。 2）两端都不在交错树中的边(i,j)，A[ i ]和B[j]都没有变化。也就是说，它原来属于（或不属于）相等子图，现在仍属于（或不属于）相等子图。 3）X端不在交错树中，Y端在交错树中的边(i,j)，它的A[ i ]+B[j]的值有所增大。它原来不属于相等子图，现在仍不属于相等子图。 4）X端在交错树中，Y端不在交错树中的边(i,j)，它的A[ i ]+B[j]的值有所减小。也就说，它原来不属于相等子图，现在可能进入了相等子图，因而使相等子图得到了扩大。（针对之后例子中x1->y4这条边） 现在的问题就是求d值了。为了使A[ i ]+B[j]>=w[i,j]始终成立，且至少有一条边进入相等子图，d应该等于： Min{A[i]+B[j]-w[i,j] | Xi在交错树中，Yi不在交错树中}。 改进 以上就是KM算法的基本思路。但是朴素的实现方法，时间复杂度为O(n4)——需要找O(n)次增广路，每次增广最多需要修改O(n)次顶标，每次修改顶标时由于要枚举边来求d值，复杂度为O(n2)。实际上KM算法的复杂度是可以做到O(n3)的。我们给每个Y顶点一个“松弛量”函数slack，每次开始找增广路时初始化为无穷大。在寻找增广路的过程中，检查边(i,j)时，如果它不在相等子图中，则让slack[j]变成原值与A[ i ]+B[j]-w[i,j]的较小值。这样，在修改顶标时，取所有不在交错树中的Y 顶点的slack值中的最小值作为d值即可。但还要注意一点：修改顶标后，要把所有的不在交错树中的Y顶点的slack值都减去d（因为：d的定义为 min{ (x,y)| Lx(x)+ Ly(y)- W(x,y), x∈ S, y? T }
本文基于相关性分析来实现图像匹配 第一步：读取图像。 分别读取以下两幅相似的图片，显示效果如下： 第二步：选择一副图像的子区域。用户可以通过鼠标选择需要截取的图像部分，用于匹配。随机选取图片的一块区域，如下图：
第三步：使用相关性分析两幅图像 采用协方差的方式计算相关系数，分析图片的相似性。 1．协方差与相关系数的概念 对于二维随机变量(,)X Y ，除了关心它的各个分量的数学期望和方差外，还需要知道这两个分量之间的相互关系，这种关系无法从各个分量的期望和方差来说明，这就需要引进描述这两个分量之间相互关系的数字特征——协方差及相关系数。 若X Y 与相互独立,则()( )0 Y E X EX Y EY σ--???? =≠;若()()0E X EX Y EY --≠????,则表 示X 与Y 不独立,X 与Y 之间存在着一定的关系 设 (,)X Y 是二维随机变量， 则称()()E X EX Y EY --????为X 与Y 的协方差（Covariance ），记为 ()cov ,X Y 或XY σ，即 ()()()cov ,XY X Y E X EX Y EY σ==--???? 若 0X σ≠ 且0Y σ=≠，则称 XY XY X Y σρσσ== 为X 与Y 的相关系数（Correlation Coefficient ）。()c o v ,X Y 是 有量纲的量，而XY ρ则是无量纲的量．协方差常用下列公式计算
()() =-? cov,X Y E XY EX EY 2．用全搜索和协方差计算截取图片与另外一幅图片的各点的相似度。c=normxcorr2(sub_I1(:,:,1),I2(:,:,1)); 第四步：找到整幅图像的偏移。 [max_c,imax]=max(abs(c(:))); [ypeak,xpeak]=ind2sub(size(c),imax(1)); [m,n]=size(sub_I1); xbegin=xpeak-n+1; ybegin=ypeak-m+1; xend=xpeak; yend=ypeak; 从原图像提取匹配到的图像 extracted_I1=I2(ybegin:yend,xbegin:xend,:); 第五步：显示匹配结果。 相关性匹配图： 找出峰值即最相似区域的中心
二分图匹配 1.最大匹配（hdu1068） Girls and Boys Time Limit: 20000/10000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 6410 Accepted Submission(s): 2888 Problem Description the second year of the university somebody started a study on the romantic relations between the students. The relation “romantically involved” is defined between one girl and one boy. For the study reasons it is necessary to find out the maximum set satisfying the condition: there are no two students in the set who have been “romantically involved”. The result of the program is the number of students in such a set. The input contains several data sets in text format. Each data set represents one set of subjects of the study, with the following description: the number of students the description of each student, in the following format student_identifier:(number_of_romantic_relations) student_identifier1 student_identifier2 student_identifier3 ... or student_identifier:(0) The student_identifier is an integer number between 0 and n-1, for n subjects. For each given data set, the program should write to standard output a line containing the result. Sample Input 7 0: (3) 4 5 6 1: (2) 4 6 2: (0) 3: (0) 4: (2) 0 1 5: (1) 0 6: (2) 0 1 3
形态学运算：基本思想是具用一定结构形状的结构元素去度量和提取图像中的对应形状以达到对图像分析和识别的目的。 腐蚀运算：将结构元素中心遍历整个图像，当图像完全包含结构元素时的中心点的轨迹即为腐蚀后的图像，图像变细。腐蚀运算可用于滤波，选择适当大小和形状的结构元素，可以滤除掉所有不能完全包含结构元素的噪声点。当然利用腐蚀滤除噪声有一个缺点，即在去除噪声的同时，对图像中前景物体形状也会有影响，但当我们只关心物体的位置或者个数时，则影响不大。 膨胀运算：将结构元素中心遍历整个图像边缘，中心点的轨迹即为腐蚀后的图像，图像整体变粗。通常用于将图像原本断裂开来的同一物体桥接起来，对图像进行二值化之后，很容易是一个连通的物体断裂为两个部分，而这会给后续的图像分析造成干扰,此时就可借助膨胀桥接断裂的缝隙。 开运算：先腐蚀后膨胀，可以使图像的轮廓变得光滑，还能使狭窄的连接断开和消除细毛刺；但与腐蚀运算不同的是，图像大的轮廓并没有发生整体的收缩，物体位置也没有发生任何变化。可以去除比结构元素更小的明亮细节，同时保持所有灰度级和较大亮区特性相对不变，可用于补偿不均匀的背景亮度。与腐蚀运算相比，开运算在过滤噪声的同时，并没有对物体的形状轮廓造成明显的影响，但是如果我们只关心物体的位置或者个数时，物体形状的改变不会给我们带来困扰，此时腐蚀滤波具有处理速度上的优势。 闭运算：先膨胀后腐蚀，可以去除比结构元素更小的暗色细节。开闭运算经常组合起来平滑图像并去除噪声。可使轮廓变的平滑，它通常能弥合狭窄的间断，填补小的孔洞。腐蚀运算刚好和开运算相反，膨胀运算刚好和闭运算相反，开闭运算也是对偶的，然而与腐蚀、膨胀不同的是，对于某图像多次应用开或闭运算的效果相同。 击中击不中运算：先由结构元素腐蚀原图像，再将结构元素取反去腐蚀原图像的取反图，最后将两幅处理后的图像取交。主要用于图像中某些特定形状的精确定位。 顶帽变换：原图像减去开运算以后的图像。当图像的背景颜色不均匀时，使用阈值二值化会造成目标轮廓的边缘缺失，此时可用开运算（结构元素小于目标轮廓）对整个图像背景进行合理估计，再用原图像减去开运算以后的图像就会是整个图像的灰度均匀，二值化后的图像不会有缺失。 Sobel算子： Prewitt算子： LOG算子： Canny算子：力图在抗噪声干扰和精确定位之间尊求折中方案，主要步骤如下所示： 1、用高斯滤波器平滑图像； 2、用一阶偏导的有限差分来计算梯度的幅值和方向； 3、对梯度幅值进行非极大值抑制； 4、用双阈值算法检测和连接边缘。 Hough变换： 边缘检测：
3. 要求对于邻接矩阵和邻接链表给出从G 到T G 的算法，并计算其复杂度。 对于邻接矩阵问题十分简单，直接求矩阵的转置即可，意味着把行换成列，把列换成行，对每行操作为O(|V|)，需要对|V|行操作，时间复杂度为O （|V|^2）。 对于邻接链表，很明显要遍历链表的所有结点来看：如果对于u 结点其指向的结点中有v,则在新的链表中，创建一条从v 的链表指向u 的路径，因此需要遍历所有的链表元素，因此时间复杂度为O （|V|+|E|）。 3. 给出一个多图（多图为包含重复边和自循环边的图）去除冗余边的复杂度为O(V+E)的算法。 遍历邻接链表的所有结点，对于结点u ，如果其链表中还有u ，则去除所有的u ；如果还有重复的v ，则去除除了第一个v 以外的v 结点（这里的标记方法有很多种，可以用个数组）。这样的复杂度应该在O(V+E)。 4. 求解平方图的问题 算法如下：遍历G 的邻接矩阵，对于结点u ，如果存在u 到v 的路径，则在G^2的邻接矩阵u 中加入v,然后再遍历v 结点的链表，如果存在v 到w ，则将w 也加入到G^2的邻接矩阵u 中。 时间复杂度：这样，再遍历u 的时候，如果遍历到了u →v 这条边，那就在看v 的链表，而v 的链表里最多有|V|个结点，因此总的复杂度为O （|V|+|V|·|E|）。 6. 邻接矩阵求通用汇点（入度为|V|-1但是出度为0）的算法 算法如下：从（1，1）开始扫描邻接矩阵，如果（i,j ）是0，则下一个扫描（i,j+1）;如果（i ，j ）是1，则下一个扫描（i+1，j ）,当i 或者j 任一方到达|V|时停止。 这样，在最坏的情况下，扫描一行加一列或者一列加一行的结点，一共有2*|V|-1时间复杂度，因此为O(V)。 7. 关联矩阵，说明BB^T 每个元素是什么意思。 其中bij = -1 （如果边j 从结点i 发出） 1（如果边j 进入i 结点） 0（其他） 此处需要分类讨论：要明白B^T 中i 行相当于B 中第i 列。 ①BB^T 对角线上的元素，T B B （i ，i ） = ∑=| E |1 j 2 bij ，这样如果存在一条由i 发出或者进 入i 的边，都会在T B B （i ，i ）中加一（因为就算是-1平方之后也是1），因此T B B （i ，i ）就是代表由多少条边从i 发出或者进入。 ②BB^T 非对角线元素，T B B （i ，j ） = ∑=| |1 k E jk ik b b ,由公式或者读者自己画矩阵图可以 得出，如果k 边从i 发出从j 进入，或者反过来，bik*bjk 就等于-1，否则就为0。原因是i,j
用匈牙利算法求二分图的最大匹配 什么是二分图，什么是二分图的最大匹配，这些定义我就不讲了，网上随便都找得到。二分图的最大匹配有两种求法，第一种是最大流（我在此假设读者已有网络流的知识）；第二种就是我现在要讲的匈牙利算法。这个算法说白了就是最大流的算法，但是它跟据二分图匹配这个问题的特点，把最大流算法做了简化，提高了效率。匈牙利算法其实很简单，但是网上搜不到什么说得清楚的文章。所以我决定要写一下。 最大流算法的核心问题就是找增广路径（augment path）。匈牙利算法也不例外，它的基本模式就是： 初始时最大匹配为空 while 找得到增广路径 do 把增广路径加入到最大匹配中去 可见和最大流算法是一样的。但是这里的增广路径就有它一定的特殊性，下面我来分析一下。 （注：匈牙利算法虽然根本上是最大流算法，但是它不需要建网络模型，所以图中不再需要源点和汇点，仅仅是一个二分图。每条边也不需要有方向。） 图1是我给出的二分图中的一个匹配：［1，5］和［2，6］。图2就是在这个匹配的基础上找到的一条增广路径：3->6->2->5->1->4。我们借由它来描述一下二分图中的增广路径的性质： (1)有奇数条边。 (2)起点在二分图的左半边，终点在右半边。 (3)路径上的点一定是一个在左半边，一个在右半边，交替出现。（其实二分图的性质就决定了这一点，因为二分图同一边的点之间没有边相连，不要忘记哦。） (4)整条路径上没有重复的点。 (5)起点和终点都是目前还没有配对的点，而其它所有点都是已经配好对的。（如图1、图2所示，［1，5］和［2，6］在图1中是两对已经配好对的点；而起点3和终点4目前还没有与其它点配对。） (6)路径上的所有第奇数条边都不在原匹配中，所有第偶数条边都出现在原匹配中。（如图1、图2所示，原有的匹配是［1，5］和［2，6］，这两条配匹的边在图2给出的增广路径中分边是第2和第4条边。而增广路径的第1、3、5条边都没有出现在图1给出的匹配中。） (7)最后，也是最重要的一条，把增广路径上的所有第奇数条边加入到原匹配中
图像匹配的主要方法分析 在我国的图像处理中，有很多的关键技术正在不断的发展和创新之中。这些相关技术的发展在很大程度上推动了我国图像处理事业的发展。作为图像处理过程中的关键技术，图像匹配技术正在受到越来越多的关注。文章针对图像匹配的主要方法进行详细的论述，希望通过文章的阐述和分析能够为我国的图像匹配技术的发展和创新贡献微薄力量，同时也为我国图像处理技术的发展贡献力量。 标签：图像处理；图像匹配；特征匹配；方法 在我国的图像处理技术中，图像的匹配技术不仅仅是其中的重要组成部分，同时还是很多图像技术的发展创新的技术基础。例如图像技术中的立体视觉技术；图像技术中的运动分析技术以及图像技术中的数据融合技术等。通过上述内容可以看出，在我国的图像技术中，图像匹配技术具有非常广泛的应用。随着我国的相关技术不断的创新和发展，对于图像匹配技术的要求也是越来越高。这样就要求我国的图像匹配技术有更深层次的研究和发展。我国现阶段的研究主要是针对图像匹配过程中的匹配算法进行研究，希望借助研究能够更加有效的提升在实际的工作应用中的图像质量，同时也能够在很大程度上提升图像处理的图像分别率。文章的主要陈述点是通过图像匹配技术的具体方法进行优点和缺点的分析，通过分析优点和缺点来论述我国图像处理技术中的图像匹配技术的发展方向以及改进措施。近些年出现了很多的图像匹配方法，针对现阶段的新方法以及新的研究思路我们在实际的应用过程中要有一个非常清醒的选择。文章针对这一问题主要有三个内容的阐述。第一个是图像匹配技术的算法融合；第二个是图像匹配技术中的局部特征算法；最后一个是图像匹配技术中的模型匹配具体算法。 1 现阶段在世界范围内较为经典的图像匹配技术的算法 关于现阶段在世界范围内的较为经典的图像匹配技术的算法的阐述，文章主要从两个方面进行分析。第一个方面是ABS图像匹配算法。第二个方面是归一化相互关图像匹配算法。下面进行详细的论述和分析。 （1）算法一：ABS图像匹配算法。ABS图像匹配算法最主要的原理就是要使用模板的图像以及相应的匹配图像的搜索用窗口之间的转换差别来显示两者之间的关联性。图像匹配的大小在数值上等同于模板图像的窗口滑动顺序。窗口的每一次滑动都会引起模板图像的匹配计算。现阶段ABS的算法主要有三个，如下： 在选择上述三种计算方法的过程中要根据实际情况社情相应的阀值，否则会出现很高的失误率。上述的三种算法使用范围较狭窄。只使用与等待匹配的图像在模板影像的计算。 （2）算法二：归一化相互关图像匹配算法。归一化相互关的图像匹配算法在现阶段是较为经典的算法。通常专业的称法为NC算法。此计算方法主要是采
二分图最大匹配算法 令G = （X,*,Y）是一个二分图，其中，X = {x1,x2,...xm}, Y = {y1,y2,...yn}。令M为G中的任一个匹配。 1）讲X的所有不与M的边关联的顶点标上（@），并称所有的顶点为未被扫描的。转到2）。2）如果在上一步没有新的标记加到X的顶点上，则停止。否则转到3）。 3）当存在X被标记但未被扫描的顶点时，选择一个被标记但未被扫描的X的顶点，比如，xi,用(xi)标记Y的所有顶点，这些顶点被不属于M且尚未标记的边连到xi .现在，顶点xi 是被扫描的。如果不存在被标记但未被扫描的顶点，则转到4）。 4）如果在步骤3）没有新的标记被标到Y的顶点上，则停止。否则，转到5）。 5）当存在Y被标记但未被扫描的顶点时，选择Y的一个被标记但未被扫描的顶点，比如yi，用(yi)标记X的顶点，这些顶点被属于M且尚未标记的边连到yi.现在，顶点yi是被扫描的。如果不存在被标记但未被扫描的顶点，则转到2）。 也可以叙述为： [ZZ]匈牙利算法 关键在于匈牙利算法的递归过程中有很多重复计算的节点，而且这种重复无法避免，他不能向动态规划一样找到一个“序”将递归改为递推。 算法中的几个术语说明： 1。二部图： 如果图G=(V,E)的顶点集何V可分为两个集合X,Y，且满足X∪Y = V, X∩Y=Φ，则G称为二 部图； 图G的边集用E(G)表示，点集用V(G)表示。 2。匹配： 设M是E(G)的一个子集，如果M中任意两条边在G中均不邻接，则称M是G的一个匹配。M中的 —条边的两个端点叫做在M是配对的。 3。饱和与非饱和： 若匹配M的某条边与顶点v关联，则称M饱和顶点v，并且称v是M-饱和的，否则称v 是M-不 饱和的。 4。交互道： 若M是二分图G＝(V,E)的一个匹配。设从图G中的一个顶点到另一个顶点存在一条道路，这条道路是由属于M的边和不属于M的边交替出现组成的，则称这条道路为交互道。 5。可增广道路： 若一交互道的两端点为关于M非饱和顶点时，则称这条交互道是可增广道路。显然，一条边的两端点非饱和，则这条边也是可增广道路。 6。最大匹配： 如果M是一匹配，而不存在其它匹配M'，使得|M'|>|M|，则称M是最大匹配。其中|M|表
图的匹配 一、什么是图的匹配 1.图的定义 无向图：无向图G 是指非空有限集合V G ，和V G 中某些元素的无序对的集合E G ，构成的二元组(V G ，E G )。V G 称为G 的顶点集，其中的元素称为G 的顶点。E G 称为G 的边集，其中的元素称为G 的边。在不混淆的情况下，有时记V ＝V G ，E ＝E G 。如果V ＝{v 1,…,v n }，那么E 中的元素e 与V 中某两个元素构成的无序对(v i ，v j )相对应，记e ＝v i v j ，或e ＝v j v i 。在分析问题时，我们通常可以用小圆圈表示顶点，用小圆圈之的连线表示边。 二分图：设G 是一个图。如果存在V G 的一个划分X ，Y ，使得G 的任何一条边的一个端点在X 中，另一个端点在Y 中，则称G 为二分图，记作G ＝(X ，Y ，E)。如果G 中X 的每个顶点都与Y 的每个顶点相邻，则称G 为完全二分图。 2.匹配的相关概念 设G ＝(V ，E)是一个图，E M ?，如果M 不含环且任意两边都不相邻，则称M 为G 的一个匹配。G 中边数最多的匹配称为G 的最大匹配。 对于图G ＝(V ，E)，在每条边e 上赋一个实数权w(e)。设M 是G 的一个匹配。定义∑∈=m e e w M w )()(，并称之为匹配M 的权。G 中权最大的匹配称为G 的最大权匹配。如果 对一切，e ∈E ，w(e)=1,则G 的最大权匹配就是G 的最大匹配。 设M 是图G=(V ,E)的一个匹配，v i ∈V 。若v i 与M 中的边相关联，则称v i 是M 饱和点，否则称v i 为M 非饱和点。 如果G 中每个顶点都是M 饱和点，则称M 为G 的完美匹配。 设M 是G 的一个匹配，P 是G 的一条链。如果P 的边交替地一条是M 中的边，一条不是M 中的边，则称P 为M 交错链。类似地，我们可以定义G 的交错圈。易知，G 的交错圈一定是偶圈。 一条连接两个不同的M 非饱和点的M 交错链称为M 增广链。 两个集合S 1与S 2的“异或”操作S 1⊕S 2是指集合S 1⊕S 2＝（S 1∩S 2）\（S 1∪S 2） 容易看出，设M 是G 的匹配，P 是G 中的M 增广链、则M ⊕P 也是G 的匹配，而且1+=⊕M P M 。 图表 1 “异或”操作 可以证明，G 中匹配M 是最大匹配当且仅当G 中没有M 增广链。
一共有RecuCal.m LockMap.m BuildMatrix.m Edmonds.m GUI1.m 这几个文件，我把它们合到一块粘上去了,你再把他们分开保存就可以了. 其中前三个文件都是为建立邻接矩阵服务的，Edmonds.m是匈牙利算法的主文件，GUI1.m只是调用Edmonds.m做个界面而已。 调用关系是GUI1.m调用Edmonds.m；Edmonds.m调用BuildMatrix.m和LockMap.m ；LockMap.m调用RecuCal.m 最后运行GUI1.m就ok了 #LockMap.m function [LMA, LMB] = LockMap(n, m) % LOCKMAP - 求解满足条件锁并设置相应的映射 % 输入参数:n 表槽数,m 表高度数。 % 输出参数:LMA,LMB 分别为二维矩阵表示自然数到满足条件锁之间的映射。 global jiA ouB ary A B mm N N = n; mm = m; jiA=0; ouB=0; A=[]; B=[]; ary = zeros(1, n); RecuCal(n); LMA=A; LMB=B; [lena, n] = size(LMA); [lenb, n] =size(LMB); if lena>lenb temp = LMA; LMA=LMB;LMB=temp; temp = lena;lena=lenb;lenb=temp; end #RecuCal.m function RecuCal(n) % RECUCAL - 递归函数 global jiA ouB ary A B mm N if n ==1 for k=1:mm % 调用递归函数时要用到的变量所以 % 设为全局 ary(1) = k; Max = max(ary); Min = min(ary); num = 0; neighbor = 0; for i=1:N num = num + (Max-ary(i))*(ary(i)-Min);
图像拼接算法及实现（一） 来源：中国论文下载中心 [ 09-06-03 16:36:00 ] 作者：陈挺编辑：studa090420 论文关键词：图像拼接图像配准图像融合全景图 论文摘要：图像拼接(image mosaic)技术是将一组相互间重叠部分的图像序列进行空间匹配对准,经重采样合成后形成一幅包含各图像序列信息的宽视角场景的、完整的、高清晰的新图像的技术。图像拼接在摄影测量学、计算机视觉、遥感图像处理、医学图像分析、计算机图形学等领域有着广泛的应用价值。一般来说,图像拼接的过程由图像获取,图像配准,图像合成三步骤组成,其中图像配准是整个图像拼接的基础。本文研究了两种图像配准算法:基于特征和基于变换域的图像配准算法。在基于特征的配准算法的基础上,提出一种稳健的基于特征点的配准算法。首先改进Harris角点检测算法,有效提高所提取特征点的速度和精度。然后利用相似测度NCC(normalized cross correlation——归一化互相关),通过用双向最大相关系数匹配的方法提取出初始特征点对,用随机采样法RANSAC(Random Sample Consensus)剔除伪特征点对,实现特征点对的精确匹配。最后用正确的特征点匹配对实现图像的配准。本文提出的算法适应性较强,在重复性纹理、旋转角度比较大等较难自动匹配场合下仍可以准确实现图像配准。 Abstract：Image mosaic is a technology that carries on the spatial matching to a series of image which are overlapped with each other, and finally builds a seamless and high quality image which has high resolution and big eyeshot. Image mosaic has widely applications in the fields of photogrammetry, computer vision, remote sensing image processing, medical image analysis, computer graphic and so on. 。In general, the process of image mosaic by the image acquisition, image registration, image synthesis of three steps, one of image registration are the basis of the entire image mosaic. In this paper, two image registration algorithm: Based on the characteristics and transform domain-based image registration algorithm. In feature-based registration algorithm based on a robust feature-based registration algorithm points. First of all, to improve the Harris corner detection algorithm, effectively improve the extraction of feature points of the speed and accuracy. And the use of a similar measure of NCC (normalized cross correlation - Normalized cross-correlation), through the largest correlation coefficient with two-way matching to extract the feature points out the initial right, using random sampling method RANSAC (Random Sample Consensus) excluding pseudo-feature points right, feature points on the implementation of the exact match. Finally with the correct feature point matching for image registration implementation. In this paper, the algorithm adapted, in the repetitive texture, such as relatively large rotation more difficult to automatically match occasions can still achieve an accurate image registration. Key words: image mosaic, image registration, image fusion, panorama 第一章绪论
电话拨号数图的匹配算法研究和高效实现 摘要：该文首先对拨号数图匹配的规则语法进行了分类讲解，通过对规则语法的分析，给出了数图匹配的算法分析，并以伪代码的形式进行了算法实现。整个算法过程包含规则预处理和拨号匹配两个过程，该文对算法实现的流程图进行了详细的描述。 关键词：voip；数图（digitmap）；超越匹配（over matched）中图分类号：tp312 文献标识码：a 文章编号：1009-3044（2013）04-0807-04 research & efficient implementation of digitmap matching algorithm wang xiao-lan （electromechanical department， suzhou institute of trade&commerce， suzhou 215009， china） abstract： the digitmap matching rules was classified and discussed in this paper. by analyzing the rules， the digitmap matching algorithm is illustrated and implemented in the form of pseudo-code. the whole process of algorithm holds two phases： rules preprocessing and digit matching. further more， this paper described in details the flow chart of implementation of the algorithm. key words： voip； digitmap； over matched 网络技术与多媒体技术的发展，促进了通信技术的综合化、数字
图论中的常用经典算法 第一节最小生成树算法 一、生成树的概念 若图是连通的无向图或强连通的有向图，则从其中任一个顶点出发调用一次bfs或dfs后便可以系统地访问图中所有顶点；若图是有根的有向图，则从根出发通过调用一次dfs或bfs亦可系统地访问所有顶点。在这种情况下，图中所有顶点加上遍历过程中经过的边所构成的子图称为原图的生成树。 对于不连通的无向图和不是强连通的有向图，若有根或者从根外的任意顶点出发，调用一次bfs或dfs后不能系统地访问所有顶点，而只能得到以出发点为根的连通分支（或强连通分支）的生成树。要访问其它顶点则还需要从没有访问过的顶点中找一个顶点作为起始点，再次调用bfs或dfs，这样得到的是生成森林。 由此可以看出，一个图的生成树是不唯一的，不同的搜索方法可以得到不同的生成树，即使是同一种搜索方法，出发点不同亦可导致不同的生成树。如下图： 但不管如何，我们都可以证明：具有n个顶点的带权连通图，其对应的生成树有n-1条边。 二、求图的最小生成树算法 严格来说，如果图G=（V，E）是一个连通的无向图，则把它的全部顶点V和一部分边E’构成一个子图G’，即G’=（V，E’），且边集E’能将图中所有顶点连通又不形成回路，则称子图G’是图G的一棵生成树。对于加权连通图，生成树的权即为生成树中所有边上的权值总和，权值最小的生成树称为图的最小生成树。求图的最小生成树具有很高的实际应用价值，比如下面的这个例题。 例1、城市公交网 [问题描述] 有一张城市地图，图中的顶点为城市，无向边代表两个城市间的连通关系，边上的权为在这两个城市之间修建高速公路的造价，研究后发现，这个地图有一个特点，即任一对城市都是连通的。现在的问题是，要修建若干高速公路把所有城市联系起来，问如何设计可使得工程的总造价最少。 [输入] n（城市数，1<=n<=100） e（边数） 以下e行，每行3个数i,j,wij，表示在城市i,j之间修建高速公路的造价。 [输出] n-1行，每行为两个城市的序号，表明这两个城市间建一条高速公路。 [举例] 下面的图（A）表示一个5个城市的地图，图（B）、（C）是对图（A）分别进行深度优先遍历和广度优先遍历得到的一棵生成树，其权和分别为20和33，前者比后者好一些，但并不是最小生成树，最小生成树的权和为19。 [问题分析] 出发点：具有n个顶点的带权连通图，其对应的生成树有n-1条边。 那么选哪n-1条边呢？设图G的度为n，G=（V，E），我们介绍两种基于贪心的算法，Prim算法和Kruska l算法。
Kuhn-Munkres 算法
Maigo 的 KM 算法讲解（的确精彩）
KM 算法是通过给每个顶点一个标号（叫做顶标）来把求最大权匹配的问题转 化为求完备匹配的问题的。设顶点 Xi 的顶标为 A[i]，
顶点 Yi 的顶标为 B[i]，顶点 Xi 与 Yj 之间的边权为 w[i,j]。在算法执行过程中 的任一时刻，对于任一条边(i,j)， A[i]+B[j]>=w[i,j]始终成立。KM 算法的正确 性基于以下定理： * 若由二分图中所有满足 A[i]+B[j]=w[i,j]的边(i,j)构成的子图 （称做相等子 图）有完备匹配，那么这个完备匹配就是二分图的最大权匹配。 这个定理是显然的。因为对于二分图的任意一个匹配，如果它包含于相 等子图，那么它的边权和等于所有顶点的顶标和；如果它有的边不包含于相 等子图，那么它的边权和小于所有顶点的顶标和。所以相等子图的完备匹配 一定是二分图的最大权匹配。 初始时为了使 A[i]+B[j]>=w[i,j]恒成立，令 A[i]为所有与顶点 Xi 关联的边 的最大权，B[j]=0。如果当前的相等子图没有完备匹配，就按下面的方法修改 顶标以使扩大相等子图，直到相等子图具有完备匹配为止。 我们求当前相等子图的完备匹配失败了，是因为对于某个 X 顶点，我们 找不到一条从它出发的交错路。这时我们获得了一棵交错树，它的叶子结点 全部是 X 顶点。现在我们把交错树中 X 顶点的顶标全都减小某个值 d，Y 顶 点的顶标全都增加同一个值 d，那么我们会发现：
两端都在交错树中的边(i,j)，A[i]+B[j]的值没有变化。也就是说，它原来属于 相等子图，现在仍属于相等子图。 两端都不在交错树中的边(i,j)，A[i]和 B[j]都没有变化。也就是说，它原来属于 （或不属于）相等子图，现在仍属于（或不属于）相等子图。 X 端不在交错树中，Y 端在交错树中的边(i,j)，它的 A[i]+B[j]的值有所增大。 它原来不属于相等子图，现在仍不属于相等子图。 X 端在交错树中，Y 端不在交错树中的边(i,j)，它的 A[i]+B[j]的值有所减小。 也就说，它原来不属于相等子图，现在可能进入了相等子图，因而使相等子 图得到了扩大。 现在的问题就是求 d 值了。为了使 A[i]+B[j]>=w[i,j]始终成立，且至少有 一条边进入相等子图，d 应该等于 min{A[i]+B[j]-w[i,j]|Xi 在交错树中，Yi 不在 交错树中}。 以上就是 KM 算法的基本思路。但是朴素的实现方法，时间复杂度为 O(n4)——需要找 O(n)次增广路，每次增广最多需要修改 O(n)次顶标，每次 修改顶标时由于要枚举边来求 d 值，复杂度为 O(n2)。实际上 KM 算法的复 杂度是可以做到 O(n3)的。我们给每个 Y 顶点一个“松弛量”函数 slack，每次 开始找增广路时初始化为无穷大。在寻找增广路的过程中，检查边(i,j)时，如 果它不在相等子图中， 则让 slack[j]变成原值与 A[i]+B[j]-w[i,j]的较小值。 这样， 在修改顶标时，取所有不在交错树中的 Y 顶点的 slack 值中的最小值作为 d 值即可。但还要注意一点：修改顶标后，要把所有的 slack 值都减去 d。