匹配算法论文范文

匹配算法论文篇1

关键词：图像处理；图像匹配；特征匹配；方法

在我国的图像处理技术中，图像的匹配技术不仅仅是其中的重要组成部分，同时还是很多图像技术的发展创新的技术基础。例如图像技术中的立体视觉技术；图像技术中的运动分析技术以及图像技术中的数据融合技术等。通过上述内容可以看出，在我国的图像技术中，图像匹配技术具有非常广泛的应用。随着我国的相关技术不断的创新和发展，对于图像匹配技术的要求也是越来越高。这样就要求我国的图像匹配技术有更深层次的研究和发展。我国现阶段的研究主要是针对图像匹配过程中的匹配算法进行研究，希望借助研究能够更加有效的提升在实际的工作应用中的图像质量，同时也能够在很大程度上提升图像处理的图像分别率。文章的主要陈述点是通过图像匹配技术的具体方法进行优点和缺点的分析，通过分析优点和缺点来论述我国图像处理技术中的图像匹配技术的发展方向以及改进措施。近些年出现了很多的图像匹配方法，针对现阶段的新方法以及新的研究思路我们在实际的应用过程中要有一个非常清醒的选择。文章针对这一问题主要有三个内容的阐述。第一个是图像匹配技术的算法融合；第二个是图像匹配技术中的局部特征算法；最后一个是图像匹配技术中的模型匹配具体算法。

1 现阶段在世界范围内较为经典的图像匹配技术的算法

关于现阶段在世界范围内的较为经典的图像匹配技术的算法的阐述，文章主要从两个方面进行分析。第一个方面是ABS图像匹配算法。第二个方面是归一化相互关图像匹配算法。下面进行详细的论述和分析。

（1）算法一：ABS图像匹配算法。ABS图像匹配算法最主要的原理就是要使用模板的图像以及相应的匹配图像的搜索用窗口之间的转换差别来显示两者之间的关联性。图像匹配的大小在数值上等同于模板图像的窗口滑动顺序。窗口的每一次滑动都会引起模板图像的匹配计算。现阶段ABS的算法主要有三个，如下：

在选择上述三种计算方法的过程中要根据实际情况社情相应的阀值，否则会出现很高的失误率。上述的三种算法使用范围较狭窄。只使用与等待匹配的图像在模板影像的计算。

（2）算法二：归一化相互关图像匹配算法。归一化相互关的图像匹配算法在现阶段是较为经典的算法。通常专业的称法为NC算法。此计算方法主要是采用计算模板以及待匹配模板相互之间的关值来进行匹配程度的计算和认定。具体的定义公式如下：

2 图像技术中的图像匹配的三个主要因素

关于图像技术中的图像匹配的三个主要因素，文章主要从三个方面进行阐述。第一个方面是图像匹配的特征空间。第二个方面是图像匹配的相似性度量。第三个方面是图像匹配的搜索策略。下面进行详细的分析和论述。

（1）因素一：图像匹配的特征空间。图像的特征空间的组成有很多种，主要石油参与匹配的图像的基本要素构成。包括了很多的方面。例如图像的灰度值；图像的轮廓和图像的统计特征等。在图像匹配的过程中，选择合适并且恰当的图像特征非常重要，这样能够有效的提升图像匹配的性能。

（2）因素二：图像匹配的相似性度量。相似性的度量主要指的是匹配图像图形的的确定方式。通常的方式是函数的形式或者是函数的表达方式。较为主要的函数形式是Minkowski函数距离。伴随着科学技术的发展，会有越来越多的函数表达形式被应用和创新。

（3）因素三：图像匹配的搜索策略。搜索策略主要是一种图像匹配的搜索空间的选择方法。通过有效的搜索策略能够将图像匹配的相似性有效的提升。搜索策略主要的方法有分层搜索以及动态规划等。

3 图像技术中图像匹配相关算法的主要分类

图像匹配的算法很多，但基本原则是不变的：有效性，稳定性以及实时性。文章将匹配算法分为基于区域的匹配方法、基于特征的匹配方法、基于模型的匹配和基于变换域的匹配。基于区域的匹配方法又称为基于图像灰度的配准方法，通常直接利用整幅图像的灰度信息，建立两幅图像之间的相似性度量，然后采用某种搜索方法，寻找使相似性度量值最大或最小的变换模型的参数值。基于图像特征的配准方法需要对图像进行预处理，然后提取图像中保持不变的特征，如边缘点、闭区域的中心、线特征、面特征、矩特征等，作为两幅图像配准的参考信息。基于模型的匹配方法在计算机视觉领域中的应用非常广泛，它可以分为刚体形状匹配和变形模板匹配两大类。Kass提出的Snake主动轮廓模型是比较典型的自由式变形模板模型。

4 未来我国图像技术中图像匹配的发展方向

关于未来我国图像技术中图像匹配的发展方向的阐述和分析，文章主要从四个方面进行分析和论述。第一个方面是图像匹配算法融合的内容。第二个方面是图像匹配算法的局部特征主要内容。第三个方面是图像匹配算法关于模型的深入研究。第四个方面是图像匹配技术研究中的色彩图像研究。下面进行详细的分析和论述。

（1）图像匹配算法融合的内容。在图像匹配的众多算法中，每一种算法都有相应的特点和主要的应用范围，这样就需要我们在使用匹配算法过程中能够有效的将算法进行融合以及相互渗透，这样能够有效的克服单一匹配算法的应用局限性，能够在很大的程度上提升图像匹配的适应性。

（2）图像匹配算法的局部特征主要内容。现阶段我国的很多图像匹配算法采用的都是全局的图像特征进行计算，这种算法对于图像质量要求非常高。同时进行图像匹配的图像有时候很难得到完整的图像，这样就会降低图像匹配的准确性。我国在图像匹配的方法上的研究方向还是要在局面的图像特征发展，这样能够更好的提升我国图像特征匹配的准确性。

（3）图像匹配算法关于模型的深入研究。在图像匹配的模型算法创新过程中，能够为我国的边缘图像监测以及图像的切割研究提供另外一种可能性。这种创新方法在现实的使用过程中也展现出了非常好的技术特性。现阶段我国对于这种方法的研究还是处在一种初级阶段，我们应该更加深入的进行研究，最大程度上提升我国图像匹配结算量较大的问题。

（4）图像匹配技术研究中的色彩图像研究

我国现阶段对于色彩图像的匹配的技术基础是图像颜色的特征。通过颜色特征来进行图像特征的匹配，但是对于图像的其他特征还没有很好的匹配计算。这一方面的图像匹配方法还不是很多，这一研究方向也是我国的一种研究重点。

参考文献

[1]章毓晋.图像工程[M].北京：清华大学出版社，2000.

[2]沈振康，孙仲康.数字图像处理及应用[M].北京：国防工业出版社，1983.

[3]郑南宁.计算机视觉与模式识别[M].北京：国防工业出版社，1998.

[4]施鹏飞.图像匹配算法及其应用[D].上海交通大学，2000.

匹配算法论文篇2

关键词：被动定位，匹配场，水下GPS，动目标分析

 

1.引言

声纳按照工作方式一般分为主动声纳和被动声纳。对于被动声纳，由于它不发射声波，它具有很好的隐蔽性，且具有作用距离远、不容易被发现等优点，在军事领域中有着很好的应用前景。近年来，世界各国都加紧了对被动定位技术的研究和开发，被动定位技术受到广泛的重视。随着水中兵器作用距离和打击精度的提高，对被动声纳的定位性能提出了更高的要求，远程定位问题引起人们的广泛关注，出现了多种新型的定位方法。

2.传统被动声纳定位技术及面临的问题

2.1 传统的被动定位技术

传统的水声被动定位技术是六十年代研究开发出来的,这类定位技术利用沿不同距离路径传播的水下声脉冲间的时间差或相位差对水面、水中目标进行定位，其典型代表就是三子阵法和球面内插法。三子阵被动测距方法是己经实用化了的被动定位技术，它是六十年代后期出现的噪声测距方法。它利用时延估计技术求出到达三个基阵的相对时延，然后得到目标的方位和距离。但是，三子阵定位方法对水声信道进行了简化，三子阵系统是在同一平面内进行定位的，它不考虑信道声速的垂直分布，也不考虑信道的多途效应。，动目标分析。，动目标分析。不过这种定位方法算法简单，而且对近距离声源定位能达到较高的精度，目前在工程上已经得到广泛应用。

2.2 传统被动声纳定位技术面临的问题

传统被动定位方法在理论和实际应用中都存在很大的缺陷，主要表现在以下两个方面。

2.2.1 远程定位精度不高

传统的被动定位方法，利用球面波或柱面波波前曲率的变化，通过测量各基元的相对时延，估计目标的距离和方位。测距精度与时延估计精度、目标距离、方位、基阵孔径、基阵安装精度等因素有关，其中时延测量精度是关键，然而对于有限的基阵孔径，随着声纳探测距离的增加，波前曲率的变化越来越小，加上信道传播起伏的影响，时延的精确测量以及距离信息的提取变得越来越困难，因此传统的定位方法难以实现远程定位。此外，由于海洋中的声速分布是不均匀的，特别在远距离定位时，声速的不均匀分布使传统的定位算法存在较大的误差。为此，研究人员必须寻求新的被动定位方法。

2.2.2 定位效果受声场环境影响大

由于海水介质的不均匀性，在海水信道中由于温度、盐度、压力的不同，导致了海水介质中各点的声学特性差异很大，特别是不同深度层的声学特性差异很大，导致了声波在海洋中的传播非常复杂，声传播受海洋信道的影响比人们想象的要大得多。要提高声纳的探测效果，必须要充分研究海洋信道特点。

3. 匹配场被动定位技术

匹配场声源定位是国际上新兴的水声定位方法，它根据海洋声信道性，在声场建模的基础上，运用一定的匹配场处理算法反演声源位置。匹配场定位技术充分利用了海洋信道特点来反演声源位置，因此它可以有效消除信道对定位的影响，它的定位精度比传统的被动定位精度高。

3.1 匹配场被动定位原理[1]

匹配场定位的被动原理图如图1所示。匹配场定位首先将水听器阵列接收到的数据经过傅立叶变换后计算频域协防方差矩阵。假设声场中某一位置有目标，已知海洋声场环境参数时，利用现有的声场模型可以计算出该目标声源产生声信号在接收水听器阵列处的声场值，通常称之为拷贝场向量。最后将拷贝场向量和测量信号的协方差矩阵进行匹配运算从而输出定位模糊表面，如果实际目标位置与假设声源位置一致，则匹配处理器有最大值输出，这样从定位模糊表面上可以读出目标的位置。

图1 匹配场定位原理图。

3.2 匹配场被动定位关键技术及发展趋势

匹配场定位有两个重要环节，一是拷贝声场的计算，二是匹配处理器的设计。拷贝声场可利用现有的声场模型计算得到。，动目标分析。现有的声场模型主要有简正波模型、声线模型、抛物方程模型等。其中，最常用的2种传播模型是射线模型和简正波模型。射线模型具有简捷、直观的特点，适用于描述深海声场。在浅海存在严重的多途和较强的海底散射，射线模型不再适用。简正波模型考虑了各种海底边界的影响，适用于研究浅海、低频的声传播问题。目前声传播模型的研究主要集中在快速、高精度的声场模型的研究上。

匹配处理器就是将拷贝场与实测声场进行匹配运算的算法，从理论上来说，匹配场处理器是传统的阵列信号处理的波束形成概念的推广，因此，很多传统的阵列处理方法都可以用于匹配场处理，而且人们已经证明其中的很多方法是很有效的。按照匹配场处理器的权向量是否与测量数据有关，将其分为线性匹配处理器（CMFP）和自适应匹配处理器(AMFP)。常用的MFP处理器有线性处理器(Bartlett)、最小方差估计器(MV)和匹配模处理器(MMP)。随着人们对传播理论研究的深入以及阵处理技术的飞速发展，匹配场处理技术的研究取得了一些突破性的进展。近年来，匹配场处理技术逐渐走向实用阶段，宽带、稳健自适应[1]、高分辨率[2]的匹配场处理技术成为研究热点，以试验研究带动理论研究成为主要的研究方法。，动目标分析。

4.水下GPS定位

水下GPS技术的设计灵感来自于GPS,该技术可以用于潜艇定位，进行爆炸军火处理，还能用于水雷对抗许多领域。水下GPS利用空间GPS系统在海洋中布放一系列声纳浮标，形成网格，在水面用空间GPS，在水下用水声通信。法国的ASCA公司已经开发了用水下全球定位系统进行搜索与救援的系统，它可以利用水下的GPS信号确目标的三维坐标。，动目标分析。该系统可以用于跟踪水下的飞机或潜艇中黑匣子的声波发器，从而找到目标。系统包括GPS浮标，控制站及声波发送器。浮标下有水听器，浮标通过水面上的三个天线与指挥、控制、通信等系统联系。利用目标发射的信号与浮标接收信号的时间延迟得到浮标和目标的相对位置，同时，利用分GPS接收机能精确测量出浮标的精确位置。空间GPS技术已相当成熟。，动目标分析。

5.结束语

由于传统的被动定位方法在理论和实际应用中都存在一些问题，研究人员致力于研究新的被动定位方法，其中匹配场被动定位技术充分利用了海洋信道，在远距离复杂水文条件下，其定位精度较高，有着诱人的应用前景，随着研究的不断深入，这项技术正逐步走向实用阶段，但匹配场的模型精确性，匹配算法的计算速度以及匹配场的定位的稳健性问题还急需解决。水下GPS技术系统使用条件相对苛刻，不适用于非合作被动目标的探测，工程应用受到了一定的限制。

参考文献：

[1]杨坤德,等.水声信号的匹配场处理技术研究[D].西北工业大学,2003,06.

[2]周俊山，陶进绪等.一种基于MUSIC算法的匹配场定位方法[J].电子技术，2010，01：21～23.

 

匹配算法论文篇3

关键词：入侵检测；模式匹配；算法

中图分类号：TP393 文献标识码：A 文章编号：1009-3044（2014）34-8117-02

入侵检测系统（Intrusion detection system，简称“IDS”）[1]是一种对网络传输进行即时监控，在发现可以传输数据时发出警报或者采取主动反应措施的网络安全设备。

1 入侵检测系统Snort

Snort[2]入侵检测是一个基于Libpcap的轻量级入侵检测系统软件，是从著名的tcpdump软件发展而来的。它是个基于Libpcap包的网络监视软件，是一个十分有效的网络入侵监测系统。Snort入侵检测系统基本由四部分组成：嗅探器，预处理器，检测引擎，日志报警[3]。如图1所示。

其中检测引擎， 是 Snort 的核心部件， 主要功能是规则分析和特征检测。当数据包从预处理器送过来后， 检测引擎依据预先设置的规则检查数据包，使用某种模式匹配算法 一旦发现数据包中的内容和某条规则相匹配， 就通知报警模块。

2 单模式匹配算法研究与改进

为了提高入侵检测系统的准确率，减少误报率，在实际的入侵检测系统中一般大都采用精确的模式串匹配算法。模式匹配问题分为单模式匹配算法和多模式匹配算法[4]。该文主要对单模式匹配算法（BM）进行研究和改进。

2.1 单模式匹配算法（BM）

仅一次在文本串中查找一个模式串出现的过程，称为单模式匹配，相应的算法称为单模式匹配算法。目前比较常见的单模式匹配算法有KMP（Knuth-Morris-Pratt）算法，BM 算法，BMH 算法等。其中， BM 算法由于使用了启发式搜索，采用从右向左的比较方式， 使用好后缀和坏字符来决定模式串移动的距离，通常同时使用两个来加快查找速度。能够在搜索过程中跳过大部分文本，从而使执行效率得到很大的提高，因而在 IDS 中运用最为广泛。

Boyer-Moore算法（简称为BM算法）[5]是一个著名的字符串匹配算法，它把被匹配的字符串模板与匹配字符串自左向右对齐，并从字符串的最后一个字符开始自右向左进行比较。BM算法并不是对每个字符依次进行比较，当出现不匹配的字符时，它使用两步启发式搜索过程来决定字符串向右移动多少个字符继续与文本串进行比较，从而减少比较次数。

其中：n>m，需要从T中查找出与P完全匹配的子串，并返回该子串在正文串的首字母的位置。

BM算法采用从右向左比较 的方法，同时应用到了两种启发式规则，即坏字符规则 和好后缀规则 ，来决定向右跳跃的距离。 BM算法的基本流程： 设文本串T，模式串为P。首先将T与P进行左对齐，然后进行从右向左比较 。若是某趟比较不匹配时，BM算法就采用两条启发式规则，即坏字符规则 和好后缀规则 ，来计算模式串向右移动的距离，直到整个匹配过程的结束。

2.2 BM算法改进

尽管BM算法是拥有高效，考虑全面，简便易懂等优点，但是由于其使用了两个数组，预处理时间较大，匹配次数较多，造成许多重复、不必要的比较，还是存在很多需要改进的地方。

通过对BM算法的分析，我们可以发现，原算法虽然是用到了两种启发式规则，即坏字符规则和好后缀规则。但是，在算法的分析中我们看到，当进行字符或者字符串匹配时，大多数匹配都用到的规则是坏字符规则。因此我们可以只用坏字符规则，通过移动量和规定字符这两个方面对BM算法进行一些改进。

根据改进算法的思想，可以对BM算法进行如下改进。由文本串和模式串最后一个位置对应的字符的下一个字符做启发向右滑动。其作用在于在每次匹配失败后，把模式向右滑动的距离变大，减少了模式匹配中一些不必要的和重复的比较，缩短了模式匹配的时间。

首先，对模式串和文本串进行分析，将文本串中文本串与模式串最后一个位置对应的字符的下一个字符（假设为x）与模式串进行匹配。当字符x在模式串中不存在时，那么显然从x开始的m个文本不可能与模式串 匹配成功，所以直接跳过，移动距离为模式串长度+1。当x在模式串中出现，并且x的前一位字符也存在于模式串中。移动模式串使字符对齐，计算偏移量。利用原BM算法进行匹配。当x在模式串中出现，但是x的前一位字符不存在于模式串中，计算移动模式串使字符x对齐时的偏移量和原BM算法中字符不存在模式串中时的偏移量，进行比较，取两者中的偏移量大的进行匹配。

2.3 算法性能比较

分别对BM算法和改进后的BM算法进行性能测试，用同一主程序分别调用BM算法和改进后的BM算法进行匹配测试，匹配算法实验中均插入CPU内部时间戳进行高精度计时，同时统计两种算法在匹配时模式串向右移动的次数。

初始条件：文本串：whiccmnxmxammm 模式串： emam

下图是分别用BM算法和改进后的BM算法对文本串和模式串进行匹配后所得到的数据。

3 结论

本文以目前最著名、最活跃的、基于误用检测的Snort为基础，针对目前应用最广泛的模式匹配算法BM算法的缺陷进行改进。但由于各个方面的局限性，该文研究还有不足和待改进的地方。总之，网络安全是技术问题，也是管理的问题。只有提高使用者的安全意识，合理使用网络及安全工具，才能达到网络的真正安全。

参考文献：

[1] 蒋建春，冯登国.网络入侵检测原理与技术[M].北京：国防工业出版社，2001.

[2] Brian Caswell，Jay Beale C Foster，Jeffrey Posluns.snort2.0入侵检测[M].宋劲松，译.北京：国防出版社，2004.

[3] Jack Koziol.Snort入侵检测实用解决方案[M].吴薄峰，许诚，译.北京：机械工业出版社，2005.

[4] 李晓芳，姚远.入侵检测工具Snort的研究与使用[J].计算机应用与软件，2006，23（3）：123-124.

[5] 胡大辉，刘乃齐.高效的snort规则匹配机制[J].微计算机信息，2006（2）.

[6] 2009年中国互联网网络安全报告[R].北京：电子工业出版社，2010.

匹配算法论文篇4

关键词：模式匹配；藏文音节；BM算法

中图分类号：TP393.08

藏文网络舆情是当前必须关注的舆论涌现与信息传播现象。近几年藏文网络舆情的数量呈现递增的增长趋势，网络信息的传播途径也呈现出多样化和复杂化。由于藏文网络的这些显著的特点，藏文信息处理相对滞后于英文和中文等，短时间内迅速的获取大量信息则不容易。另，目前藏文网站大量的涌现，网页数量巨大，处理起来速度相对慢，以往藏文网络舆情页面的统计都是基于手工统计实现的，效率低，很难对网络舆情的变化做出快速响应。模式匹配技术是内容过滤的核心技术，是计算机信息技术领域研究的基础问题之一，研究敏感词作为模式串的藏文模式匹配算法具有重要的研究意义。

BM算法是Boyer和Moore提出的一种字符串快速匹配算法。其基本思想是从右向左的把模式字符串同文本做比较。开始时仍是P的最左边与T的最左边对齐，当在某一趟比较中出现不匹配时，计算模式串右移的距离，把模式串向右移动该距离，再进行从右至左的匹配，同时应用到了两种启发式规则，即坏字符规则和好后缀规则，来决定向右跳跃的距离。

1 BM算法在藏文中的改进

藏文字符匹配中应用BM算法时，必须结合藏文文字特征，对BM算法进行改进以符合藏文的特点，提高匹配效率。

1.1 藏文文字结构及编码特点

藏文是由多个基本字符通过纵向叠加组成的字符串，构成一个完整藏文词素的基本单位是由藏文中的“音节分割符tsheg bar”来确定。一个或多个音节构成一个藏文词。音节，则是由音节分割符（音节点）或者其他藏文标点符号来划分的。一个音节中基字符是不能被省略的，其余相关构件都可以减少掉一个或几个这样仍然可以成一个音节（藏字）。七个构件中辅音字母在各部位依据藏文语法要求都有一定限制并不是所有的辅音字母都能够做前加字或者后加字等。

藏文在计算机中进行编码时一个音节需要用多个编码来表示，长度是不定的，这使得藏文在信息系统中的实现非常的麻烦。

（1）国内的几种藏文处理系统将藏文作为整字给予编码。将藏文垂直组合的部分作为一个处理单元编码（预先进行垂直组合，称为垂直预组合，垂直预组合后的字符称为藏文字丁），比如北大方正的报刊排版系统、华光藏文排版和同元藏文处理系统、激光照排系统等，这几个系统都有各自的编码方案这类编码采用双字节进行编码。这样，具有完整构件组合的藏字（即一个音节最多由4个字丁组成）。因此，国内的这几种编码方式一个音节就最多有4个编码。国家标准的扩A和扩B编码方案采用的是也是整字编码方案。

（2）国外的几种藏文编码方式也是采用整字编码方案，但是将带元音的字丁与元音分离后分别进行了编码。一个藏文音节最多就由5个字丁组成，即一个藏文音节由5个编码组成。

（3）ISO/IEC 10646藏文基本集是国际标准的编码方案，它完全将藏文视做拼音文字，字丁则是通过字母的动态组合实现的。即将一个藏文音节拆分成不同构件的独立的部分，对每一个构件都单独进行编码。采用国际标准后一个藏文音节最多由7个编码组成。基于不同编码的方式使得一个音节的编码个数不同，即使具有相同编码个数的同一种编码方案，由于编码范围不同编码值也将不一致。1997年，我国的藏文基本字符集被收入了国际标准ISO/IEC 10646《信息技术通用多八位编码字符集》。藏文编码标准得到了统一。故本匹配算法以小字符集国际编码标准（ISO/IEC 10646）编码进行讨论。

依据藏文采用小字符集编码中音节字的特点：

（1）具有完整构件的音节具有7个编码且每个编码都是两个字节，则对一个藏文音节字的表示则最多需要14个字节，最少也需要两个字节。匹配过程中只有在一个音节的所有字节都相等的情况下，一个藏文音节才匹配成功。

（2）藏文音节与音节之间由音节点分割，在小字符集中该音节点为0X0F0B。

1.2 基于藏字特征改进的BM算法

改进后的BM模式匹配算法的具体思路：

（1）用模式串P的尾字符与文本串T进行比较，结果失配，且文本串字符不为音节点，则模式串P右移到下一个出现的音节点处在新的位置继续比较。

（2）用模式串P的尾字符与文本串T进行比较，结果匹配，再把模式串第一个字符与文本串T比较，结果匹配。则将模式串与文本串T由右向左依次比较。当所有字符都能匹配上时，则找到字符串返回查找结果并结束；如果模式串第一个字符与文本串T比较，结果不匹配，则：

求move（o）=First（OT）-First（OP），将模式串移动move（o）个字符。

其中First（OT）：表示文本串T出现的第一个音节点；First（OP）：表示模式串P出现的第一个音节点。move（o）：距离差值；

（3）用模式串P的尾字符与文本串T进行比较，结果匹配，再把模式串第一个字符与文本串T比较，结果匹配。则将模式串与文本串T由右向左依次比较。如果在模式串P的某一字符x失配，则转4；

（4）如果失配的字符x在模式P中没有出现，则：

求：First（x）：从x起始的字符到第一个出现的音节点的距离。那么从字符x开始的m（模式串的长度）+First（x）个文本显然不可能与P匹配成功，直接全部跳过该区域即可，则模式串移位m+First（x）个位置；

（5）如果失配的字符x在模式P中出现，则：以该字符进行对齐。设move（x）为P右移的距离，m为模式串P的长度，max（x）为字符x在P中最右位置。作模式串移位：[m-max（x）]+First（x）。

通过上对面算法的分析，我们可以看出，改进后的BM算法可以减少比较的次数，提高匹配的速度。

2 结束语

越来越多的藏文出版作品在以数字化方式存储，网络上的藏文资料也日益增多，改进针对西文以及中文的搜索算法，寻找适合藏文文字特点的字符查找算法是值得研究的。改进的BM模式匹配算法就是利用藏文字符构字特征以及编码特点，改变了BM算法的比对方式，从而提高匹配的效率。

参考文献：

[1]江涛，于洪志.基于藏文文本的网络舆情监控系统研究[A].全国计算机安全学术交流会论文集[C]，2006.

[2]闵联营，赵婷婷.BM算法的研究与改进[J].武汉理工大学学报，2006（03）：528-530.

[3]殷丽华，张冬艳，方滨兴.面向入侵检测的单模式匹配算法性能分析[J].计算机工程与应用，2004（24）：46-47.

[4]扎西加，珠杰.面向信息处理的藏文分词规范研究[J].中文信息学报，2009（04）：113-117.

[5]严蔚敏，吴伟民.数据结构[M].北京：清华大学出版社，1999.

作者简介：春燕（1977-），女，藏族，讲师，硕士研究生，主要研究方向：藏文信息处理、数据挖掘。

作者单位：大学藏文信息技术研究中心，拉萨 850012

匹配算法论文篇5

关键词:教学分析;阻抗匹配;分贝

中图分类号:O441 文献标识码:A 文章编号:1672-3198(2010)02-0190-01

1 影响阻抗匹配的因素

(1)反射系数。

(2)反射衰减 Return loss。

(3)回波损耗γ=(ZL-ZC)/(ZL+ZC) RL=20γ。

(4)驻波系数(电压驻波比、驻波比)。

VSWR=1+|γ|1-|γ|

2 匹配参数的计算

阻抗匹配计算有三个要素:中心频率、Q值、电抗元件,这部分最典型的问题是:已知负载阻抗ZL=R+jX(或者负载导纳YL=G+jB),设计匹配网络,将其匹配到50欧姆。

需要运用繁琐的复数运算

jXL=jωL jXC=1jωC ω=2πf

最基本的匹配电路

3 匹配电路的类型

所谓阻抗变换,一定是在谐振状态下的变换,因此一定是跟谐振频率相关的。常见的匹配电路类型有Pi型和T型匹配。可看作两级L型匹配,可同时满足对阻抗变换和Q值的要求。4 匹配电路的仿真

阻抗匹配电路有相关的辅助计算工具,Smith圆图工具就是其一。smith圆图是将反射系数绘制成极坐标形式的图形,因为反射系数是一个模不超过1的复数,因此其取值落在一个半径为1的圆内,故名“圆图”。在软件工具的辅助之下,利用圆图计算匹配是非常直观的事情。该辅助工具也适用其他的阻抗变换方式。

(1)变压器实现高低阻抗的变换。

早期音频功放上驱动低阻喇叭采用的方法以及振铃电路上使用的变压器耦合,以驱动低阻喇叭。

(2)传输线变压器的阻抗变换。

实现1∶4、1∶9的阻抗变换,或者实现平衡-非平衡转换。

(3)微带线、传输线、波导阻抗匹配。

RF、微波场合,利用特定的传输线、波导,作为电感、电容、互耦元件,从而实现阻抗变换。

5 结论

对于阻抗匹配仿真结果,应该使学生明白,仿真是设计阶段的依据,方案验证的手段;是调试的助手;是辅助的可靠性分析手段。阻抗匹配的教学过程和实践过程有着本质的区别,教学过程趋于理论较多,学生不易理解,实践过程易懂清晰,易于理解,并且是电路理论教学中最重要的环节和步骤。

参考文献

[1]高文焕,汪蕙.模拟电路的计算机分析与设计――PSPICE程序应用[M].北京:清华大学出版社,2002.

匹配算法论文篇6

关键词：多属性匹配决策；多阶段；orness测度；累积权重；感知效用；极大极小法

中图分类号： TP311.5；C934

文献标志码：A

英文摘要

Abstract： The current research of bilateral matching problem is limited to singleperiod scenario. Aiming at the issue， an approach was proposed to study matching decision problem under multiperiod and multiattribute. First， through the orness， a measurement of Agents preference， an optimal program was constructed to determine the cumulative weight of an Agent within each attribute. More specifically， the criteria of this program consisted of two parts： one part was to minimize the sum of deviation between an orness and corresponding cumulative weight of an Agent in different period； another part was to minimize the maximum disparity among cumulative weights of an Agent. Then， based on obtained cumulative weight， matching degree which represented by Agents positive and negative ideal between the cumulative evaluation value and perceived expectation can be determined via the Technique for Order Preference by Similarity to Ideal Solution （TOPSIS）. Furthermore， a doubleobjective optimization model based on perceived expectation was constructed and the minimax method was used to solve this model for obtaining matching results. Finally， a numerical example was given to compare the minimax method with the linear weighting method. The results show that difference of profit and loss of utility obtained by the former method was 0.33， less than 0.36 that obtained by the latter method. Moreover， it also demonstrates the proposed method can maximize the profit and loss of utility of inferior side.

英文关键词

Key words：

multiattribute matching decision； multiperiod； orness measurement； cumulative weight； perceived expectation； minimax method

0 引言

匹配决策是指参与匹配的双方主体在既定框架下进行双向（效用）评价与选择的过程。鉴于匹配在理论实践中的重要性与复杂性，自文献[1]针对男女婚配和北美大学录取问题提出“延迟接受机制”以来， 学术界对匹配决策问题从不同视角运用不同方法进行了广泛研究，如双边拍卖问题[2]、风投与创业企业匹配问题[3]、电子中介的交易匹配问题[4-5]、职工与职位匹配问题等[6]。

匹配决策的开展有赖于双方对匹配方的准确评价，并根据评价结果测算匹配度再确定匹配对象[7-8]。评价过程中双方一般考虑对方多个属性或指标，多属性匹配决策近年来得到许多学者的关注：文献[4，9]等针对电子中介多数量多属性商品交易问题，从基于改进模糊信息公理的角度计算匹配度，设计了基于Prüfer编码的多目标离散差分进化算法求解该问题；文献[10]考虑无差异区间型的多指标双边匹配问题， 通过求解各指标值相对于主体期望值得到匹配度， 得到双方的综合匹配度矩阵并将其作为匹配依据；文献[11]等研究了权重不确定的多属性匹配问题，采用非线性优化方法求主体的属性权重，再确定匹配结果。

然而，上述研究均是建立在期望效用理论的基础上，假设决策者是完全理性的。为克服该不足，文献[3]考虑多种类型信息的多指标匹配问题，结合前景理论及交互式多准则决策方法计算双方的总体感知价值，在此基础上建立优化模型进行匹配；文献[12]通过建立双方主体的损益矩阵和前景决策矩阵，进一步通过使双方收益最大化得到匹配结果；此外，也有一些学者尝试对多属性评价信息为语言变量[13]或为关联变量[14]进行了分析研究。

已有研究丰富了多属性匹配决策的模型和方法，扩大了匹配决策的实际应用背景；然而，需要指出的是，已有的研究大都只考虑静态单阶段情形下的匹配过程，但现实中由于主体偏好的易变性、信息的时效性和决策环境不确定性等因素，匹配过程往往呈现出动态多阶段的特点[15-16]。 因此，要提高匹配决策的可靠度和准确度，最大限度真实反映主体的匹配偏好，有必要对多阶段情形下的匹配决策开展研究。本文提出一种考虑双方主体感知效用的多阶段多属性匹配决策途径。先建立计算得到属性累积权重的确定模型， 该权重反映了权衡各阶段后主体对匹配方各属性偏好；再与给定的属性值加权得到累积评价值，该值是匹配对象的实际的评价值，借鉴逼近理想解法[17]（Technique for Order Preference by Similarity to Ideal Solution， TOPSIS）的思想计算它与主体期望的理想值之间的距离，得到主体的感知效用；最后构建基于双方主体感知效用的优化模型并求解得到最终匹配结果。

1 问题描述及思路分析

本文要解决的问题是：根据已知信息，如何确定最优匹配方案。限于篇幅，文中所指的匹配、匹配方案的定义详见文献[8]。下文以Ai和Bj为例进行阐述。

1.3 研究思路

多阶段多属性匹配决策因积累了多个阶段信息，需要考虑所有阶段属性信息才能全面掌握匹配方的综合表现[23]。 由于主体对不同阶段属性信息的偏好存在差异，通过融合主体偏好，对各个阶段以及各个属性分别赋权再加权集结，是解决该问题的一般思路。但这会产生两个问题：1）如何确定阶段权重；2）如何确定阶段内的属性权重。

根据定义1，orness测度不仅可表示主体对属性权重的偏好，也可以表示对阶段权重的偏好。单阶段多属性情形下， 由给定的orness测度可获得相应的属性权重；多阶段多属性情形下，由各阶段orness测度构成的一组测度数据，包含着主体对于各个阶段、各个属性两方面的偏好信息。因此，对该组orness测度数据进行“挖掘”，就能直接求得主体对各属性的累积权重。该权重综合反映了集结阶段权重后主体对各属性的偏好。这样避开了求解两个问题的复杂过程。

根据orness测度确定累积权重，实际上也是主体对各阶段偏好的协调与博弈，一种常见的方法是通过最小化累积权重之间的最大离差[20]。此外需注意的是，由多个orness测度集结生成的权重可能不唯一[19]。而所求的属性累积权重应最大限度反映主体偏好，换句话说，累积权重对应的orness测度应与主体给出的该测度尽量接近。根据以上分析， 以各阶段orness测度与累积权重对应的该测度之间的偏差和，以及累积权重间的最大离差，两者之和最小为优化准则， 建立模型直接求得属性的累积权重。累积权重再与专家给出的属性评价值加权集结，进而测算双方匹配度。最后，采用极大极小法（Minimax）最大化匹配双方的匹配度，即得到匹配方案。

3 算例分析

3.1 计算步骤

十月福州市海西设某市高新技术产业园有6家应用软件公司 （记A1， A2，…，A6）和5家网游服务公司（B1， B2，…，B5）参加由市政府和管委会联合主办的软件外包合作会。因存在限额，主办方规定每家公司至多选择一家合作方。各公司对合作方资质水平有着不同的正负期望值，分别记为c+i、c-i（见表1）。由于缺乏合作基础，主办方聘请专家、企业顾问等专业人士对每家公司在2011―2013三个年度的相关指标进行综合评估以增进了解。根据历史经验和市场调查，专家对网络游戏公司从企业规模（d1）、管理能力（d2）、前期项目回报率（d3）和历史信誉（d4）四个方面进行评价；对应用软件开发公司从技术水平（o1）、研发能力（o2）、财务运营能力（o3）和售后服务（o4）进行评价（详细评价信息如表2）。另外，由于各公司对不同阶段信息的偏好存在差异，约定以orness测度（表3）。根据收到的双方反馈信息，主办方以合作双方吻合度最大为准则，决定匹配方案。

3.2 方法对比

文献[8，10，12，14]在建立求解双边匹配问题的多目标优化模型时，均使用线性加权法将多目标优化模型转化为单目标优化模型，然后最大化双方主体的损益效用（满意度）之和求解模型获得结果。以文献10、12、14为何列出说明不比较二修稿已答复，文献8、10、12、14使用的方法相同，均为线性加权法.为避免累赘，以文献8为例。

文献[8]的方法为例，与本文采用的极大极小法进行对比。将表 6、表7中双方的感知效用作为文献[8]定义的主体损益值，不妨令双方在匹配中的权重相等，均等于0.5，则两种方法得到的匹配结果见表8。

不难看出，使用文献[8]的方法，A2与B1匹配，A5与B4匹配，这两组与本文的匹配结果不同。本文方法得到的双方主体满意度和略小。这是因为极大极小法保证最劣目标函数达到最优从而确定最优解。因此在匹配过程中，它使损益效用（满意度）之和较小的一方达到最大，在某种程度上本文方法有利于均衡双方的损益效用。另外需指出的是，文献[8]的方法先要人为设定各目标函数的权重值，权重不同时得到的损益值也不同；而本文方法无需确定目标权重，得到的结果具有唯一性。

4 结语

针对多阶段多属性双边匹配决策问题，提出一种考虑主体感知效用的决策方法。具体地，先求得多阶段情形下主体偏好的属性累积权重，以各阶段的orness测度与累积权重对应的orness测度之间的偏差和，以及累积权重间的最大离差，两者之和最小为准则计算得到。进而与专家给出的属性值加权得到累积评价值，然后采用TOPSIS法计算匹配对象的实际评价值与主体期望的理想值之间的差距，从而获得主体的感知效用。感知效用反映了主体权衡匹配方后所感知到的损益效用，是双方匹配的依据。最后，构建一种双目标优化模型，并使用极大极小法求解得到匹配方案，该匹配方案使双方中目标函数较劣一方达到最优，缩小了与另一方损益值的差距。但本文未考虑阶段之间的关联情况，今后将进一步考虑多阶段间存在关联信息下的匹配决策方法。

调整结语内容，与前面重复，而且也不要自我评价性语句。根据文献检索结果，目前对于匹配决策的研究仅限于静态单阶段的情形。为了使匹配决策过程更加贴近实际，并真实反映主体的匹配偏好，提出一种多阶段多属性考虑主体感知效用的匹配决策方法。具体过程为先求得多阶段情形下主体偏好的属性累积权重，它是以各阶段的orness测度与累积权重对应的orness测度间的偏差和，以及累积权重间的最大离差，两者之和最小为准则计算得到。进而与专家给出的属性值加权得到累积评价值，然后借鉴TOPSIS法的思想，计算匹配对象的实际评价值与主体期望的理想值之间的距离， 得到主体的感知效用。感知效用是主体权衡匹配方后所感知到的损益效用，是匹配的重要依据。最后，建立一种双目标优化模型并使用极大极小法求解得到匹配方案，该匹配方案使双方中目标函数较劣的一方达到最优，缩小了与另一方损益值的差距。

本文提出的方法不仅丰富了匹配决策方法，也为实际中多阶段匹配问题提供理论参考。但本文未考虑阶段之间的关联情况。今后将进一步考虑多阶段间存在关联信息下的匹配方法。

参考文献：

[1]GALE D， SHAPLEY L S. College admissions and the stability of marriage [J]. American Mathematical Monthly， 1962， 69（1）： 9-15.

[2]NICOLAISEN J， PETROV V， TESFATSION L. Market power and efficiency in a computational electricity market with discriminatory doubleauction pricing [J]. IEEE Transactions on Evolutionary Computation， 2001， 5（5）： 504-523.

[3]WAN S， LI D. Decision making method for multiattribute twosided matching problem between venture capitalists and investment enterprises with different kinds of information [J]. Chinese Journal of Management Science， 2014， 22（2）： 40-47. （万树平，李登峰.具有不同类型信息的风险投资商与投资企业多指标双边匹配决策方法[J].中国管理科学， 2014， 22（2）：40-47.）

[4]JIANG ZZ， IP W H， LAU H C W， et al. Multiobjective optimization matching for oneshot multiattribute exchanges with quantity discounts in Ebrokerage [J]. Expert Systems with Applications， 2011， 38（4）： 4169-4180.

[5]RAGONE A， STRACCIA U， NOIA T D， et al. Fuzzy matchmaking in emarketplaces of peer entities using Datalog [J]. Fuzzy Sets and Systems， 2009， 160（2）： 251-268.

[6]LIN HT. A job placement intervention using fuzzy approach for twoway choice [J]. Expert Systems with Applications， 2009， 36（2）： 2543-2553.

[7]ECHENIQUE F. What matchings can be stable？ The testable implications of matching theory [J]. Mathematics of Operations Research， 2008， 33（3）： 757-768.

[8]YUE Q， FAN Z. Decision method for twosided matching based on cumulative prospect theory [J]. Journal of Systems Engineering， 2013， 28（1）： 38-46. （乐琦，樊治平.基于累积前景理论的双边匹配决策方法[J].系统工程学报，2013，28（1）：38-46.）

[9]JIANG Z， FAN Z， WANG D， et al. Matching model and algorithm for multiunit muftiattribute exchanges with fuzzy information in Ebrokerage [J]. Journal of Management Science in China， 2014， 17（5）： 52-65.（蒋忠中，樊治平，汪定伟，等.具模糊信息的多数量多属性电子交易匹配问题[J].管理科学学报，2014，17（5）：52-65.）

[10]YUE Q. Indifference interval multiple criteria matching decision method [J]. Journal of Systems Engineering， 2014， 29（1）： 41-47.（乐琦.无差异区间型多指标匹配决策方法[J].系统工程学报，2014，29（1）：41-47.）

[11]ZHANG Z， GUO CH. A hybrid multiple attributes twosided matching decision making method with incomplete weight information [C]// BI11： Proceedings of the 2011 International Conference on Brain informatics， LNCS 6889. Berlin： Springer， 2011： 272-283.

[12]CHEN X， HAN J， ZHANG X. Method for multiple attribute matching decision making considering matching bodys psychological aspiration and perception [J]. Control and Decision， 2014， 29（11）： 2027-2033. （陈希，韩菁，张晓.考虑心理期望与感知的多属性匹配决策方法[J].控制与决策，2014，29（11）：2027-2033.）

[13]HUYNH VN， NAKAMORI Y. A satisfactoryoriented approach to multiexpert decisionmaking with linguistic assessments [J]. IEEE Transactions on Systems， Man， and Cybernetics， Part B： Cybernetics， 2005， 35（2）： 184-196.

[14]CHEN X， FAN Z， HAN J. Method for twosided matching decision making considering correlated index [J]. Operations Research and Management Science， 2012， 21（6）： 94-99.（陈希，樊治平，韩菁.考虑关联性指标的双边匹配决策方法[J]. 运筹与管理，2012，21（6）：94-99.）

[15]ZHU J， LIU S， LI H， et al. Aggregation approach of multiple stages multiple judgment preferences styles in group decision making [J]. Control and Decision， 2008， 23（7）： 730-734.（朱建军，刘思峰，李洪伟，等. 群决策中多阶段多元判断偏好的集结方法研究[J]. 控制与决策， 2008， 23（7）： 730-734.）

[16]ZHANG F， GUO Y， YI P. Multiphase interactive group evaluation method based on rank correlation analysis [J]. Journal of Systems Engineering， 2011， 26（5）： 702-709.（张发明，郭亚军，易平涛. 序关系分析下的多阶段交互式群体评价方法[J]. 系统工程学报， 2011， 26（5）：702-709.）

[17]

LAI Y J， LIU T Y， HWANG C L. TOPSIS for MODM [J]. European Journal of Operational Research， 1994， 76（3）： 486-500.查不到

[18]YAGER R R. On ordered weighted averaging aggregation operators in multicriteria decision making [J]. IEEE Transactions on Systems， Man and Cybernetics，1988，18（1）： 183-190.

[19]WANG YM， LUO Y， HUA Z. Aggregating preference rankings using OWA operator weights [J]. Information Sciences， 2007， 177（16）： 3356-3363.

[20]WANG YM， PARKAN C. A minimax disparity approach for obtaining OWA operator weights [J]. Information Sciences， 2005， 175（1/2）： 20-29.

[21]

HAO J， ZHU J， LIU S. Aggregation of multistage uncertain linguistic evaluation information based on orness [J]. System Engineering-Theory and Practice， 2013， 33（11）： 2866-2873. （郝晶晶，朱建军，刘思峰. 基于Orness测度的多阶段不确定语言信息优化集结[J]. 系统工程理论与实践， 2013， 33（11）： 2866-2873.）

[22]LI D. Fuzzy multiobjective manyperson decision making and game [M]. Beijing： National Defense Industry Press， 2003： 75-77.（李登峰. 模糊多目标多人决策与对策[M]. 北京：国防工业出版社，2003：75-77）

匹配算法论文篇7

 关键词：后缀数组分布式存储串匹配

 1引言

键，在分布式环境下加速后缀数组的构造需要充分考虑到通信对算法性能的影响。串匹配问题是计算机科学中研究得最广泛的问题之一，在文字编辑与处理、图像处理、信息检索、分子生物学等领域都有很广泛的应用。本文解决的是分布式存储环境下的精确串匹配问题。在串匹配的许多实际应用中一个确定的文本常常被查询很多次(比如对非常长的基因序列的查询)。针对这种情况，manber.u和e.w.myers提出建立后缀数组(suffixarrays)〔1〕来提高查询的性能，而后缀数组最大的不足是它的构造时间过长。因此一直以来，如何快速有效地构造后缀数组成了提高基于后缀数组的串匹配算法性能的关

2usaa算法

假设n，m为文本串和模式串的长度，p为处理器数，算法设计思路如下:

(1)将长为n的文本串a均匀划分成互不重盛的p段，分布于处理器。~(p一l)中，且使相邻的文本段分布在相邻的处理器中，显然每个处理器中局部文本段的长度为〔n/p〕。

(2)除了处理器o外，其它每个处理器利用kmp算法计算分配到自己的文本串的头个字符与模式串，基金项目:国家自然科学基金重点项目(60533020) 的匹配信息。如果存在匹配情况，就向相邻的前一个处理器发送最大匹配后缀长度maxsuffixlen，否则就发送一个负数。每个处理器可独立地计算和发送该值，所以这一步的计算复杂度为o(m)，通信复杂度为o(1)。

(3)处理器1~(p-l)接收前一个处理器的信息。

(4)利用manber.u和e.w.myers在文献〔〔1〕中的算法各处理器并行地构造局部文本段的后缀数组。

(5)利用manber.u和e.w.myers在文献〔1〕中的算法各处理器并行地进行模式申的匹配。算法的计算复杂度为o((n/p(109109(n/p)))，通信复杂度为0(1)，大大降低了通信复杂度。

3实验结果及分析

我们在基于分布存储的32节点hprx2600高性能机群系统上测试了上述算法，比较了usaa和目前理论值最好的mmsortlz〕算法之间的性能，其计算复杂度为，通信复杂度为。

图1给出了当m一16、p~2时，n的取值对算法执行时间的影响。从图中看出当时，由于n、p的取值成了影响算法复杂度的主项，因此在实际应用中usaa算法比mmsort算法表现要好。

图2给出了当n变大时，usaa算法和mmsort算法的通信时间比较。可以看出，随着文本串的规模变大，由于处理器间需要进行的通信量增加，mmsort算法的通信时间有明显的上升，而usaa算法的上升幅度要显著小于mmsort。

4结论

本文提出的usaa算法通过采取均匀的后缀分配方式来降低处理段间匹配时的通信消耗，在(n/p)m的情况下使算法在保持计算复杂度的同时大大降低了通信复杂度。通过实验结果可以看到，usaa算法很好地解决了在分布式存储环境下降低后级数组构造中的通信复杂度的问题。

参考文献

[1]u.manber，g.myers.suffixarrays:anewmethodforon-linestringsearehes[c〕.inproeeedingsofthe

lstannualacm一siamsymposiumon压seretealgorithms.1990:319一327.

匹配算法论文篇8

关键词：匹配 目标识别 角点检测 现状

中图分类号：V243.1 文献标识码：A 文章编号：1674-098X（2017）01（c）-0110-02

1 目标识别算法的研究现状

现代智能监控系统主要分为目标识别和跟踪两部分，而最重要的是目标识别部分。其算法主要分为：（1）基于统计模式识别的算法；（2）基于匹配的识别算法。

1.1 基于统计的识别算法

该算法原理是将目标识别当作从样本中区分出目标所属种类，识别前需用大量样本对分类器进行训练。支持向量机（SVM）是Corinna Cortes和Vapnik等于1995年首先提出的，在小样本分类学习中有性能和速度上的明显优势。

1.2 基于匹配的识别算法

模板匹配是在图像域直接利用像素灰度匹配，简单、实时性好，但抗干扰能力、适应性和鲁棒性均不高。

因此，学者们提出了基于特征匹配的目标识别算法。2004年，Hahnel和Klunder等提出利用颜色、纹理特征对人进行识别。同年，Csurka等提出利用一组特征点分类识别物体。2005年，Berg等提出通过物体的形状特征进行识别。2007年，Ullman提出基于图像块机制的目标识别方法。2009年，Cao等人提出基于角点特征匹配的目标识别方法。基于特征匹配的方法最大的优点是对于几何变形和亮度变化不敏感，且算法的鲁棒性较好。

2 基于模板匹配的目标识别

2.1 概述

基于模板匹配的目标识别因计算量小、识别率高等优点已被应用于汽车、指纹、人脸等多领域，其对视频或连续图像中跟踪特定目标也有很好的准确性。

2.2 常用的模板匹配算法

FS算法是实现模板匹配最简单有效的算法，但易受像素值影响，不一定能正确匹配。文献[2]使用NCC作为度量方法，兼顾了稳定性和匹配速度。文献[3]使用汉明距离定义模板与识别窗间的匹配相似性，减少了计算量。文献[3]基于图像描述子方法进行目标识别，减少了计算量。

快速模板匹配算法大致可分为以下几种。

（1）快速傅里叶变换算法（FFT算法）。匹配结果与FS算法一致，但无需搜索候选窗口，而是计算模板在图像各个位置上的相似度值。

（2）全搜索等价算法。一般采用逐层筛选策略，匹配结果同FS算法，但速度更快。

（3）非全搜索等价算法。采用搜索查找空间，或在特征空间中近似匹配的策略加快匹配速度，但其结果不一定与FS算法一致。

3 基于特征匹配的目标识别

3.1 目标特征概述

图像的特征一般可以分为以下几种。

（1）直观性特征：①基于边缘的方法：常用拉氏算子、Mary算子等进行边缘检测。Nevada在1980年提出一个较成功的直线特征提取案例。Alireza等在2002年引入模糊理论选择边缘点。②基于区域的方法：通常用于建筑等区域信息较强的目标。孙琪等人在2001年介绍了一种在红外图像中提取出桥梁的方法。③基于纹理的方法：以灰度共生矩阵为基础的纹理特征提取是一种常见的有效方法。

（2）灰度的统计特征。主要是指直方图特征等，目前常引入统计上的各阶矩作为特征。

（3）代数特征。将图像作为矩阵看待，对其进行各种代数变换，或矩阵分解以得到目标特征。

（4）变换系数特征。对图像进行Fourier变换、小波变换等，能从时域、频域等多方面分析，能更本质地反映目标。

3.2 基于角点特征的目标识别

角点就是极值点，目前仍无明确的数学定义。通过检测角点进行目标识别加快了计算速度，使实时处理成为可能。

目前，角点检测算法主要分为：（1）基于图像边缘信息的角点检测算法；（2）基于图像灰度信息的角点检测算法；（3）基于小波变化的角点检测算法。

3.2.1 基于图像边缘信息的角点检测算法

此类算法将角点视作由2条或多条边界线相交而成的点。

20世纪70年代，A.Rosenfeld等和H.Freeman等提出用角点强度k来计算角点。1983年，J.Ponce和M.Brady提出将图像对x，y求偏导数来求角点。同年，A.P.Witkin提出采用自适应弯曲度求取角点的方法。1986年，Asada等改进A.Rosenfeld的算法，提出先进行边缘平滑以去除干扰。1993年，Cooper利用链码处像素坐标估计最大曲率值来求角点。1996年，Hsin-Teng和Wu-Chin Hu利用多边形近似边界链，将交点作为角点。2004年，钟宝江和廖文和提出了隐式精化数字化曲线策略，推出一种新的角点强度公式。

此类算法对边缘提取算法依赖性较强，边缘线中断将严重影响检测结果。

3.2.2 基于图像灰度信息的角点检测算法

此类算法主要通过计算梯度及曲率来检测角点，大致分为：（1）基于方向导数；（2）直接基于图像的亮度对比关系。

此类算法最早由Kitchen-Rosenfeld提出。Moravec提出利用灰度方差提取“兴趣算子”来提取角点。1988年，Harris等人改进了Moravec算子，提出了著名的Harris角点检测算子。1997年，Smith和Brady提出了具有很强抗噪声性能的SUSAN提取算子。1998年，Trajkovic和Hedley就是基于同值分割吸收核（USAN）算法提出了一N快速角点检测方法――MIC算法。

此类算法缺点是定位精度较低。

3.2.3 基于小波变化的角点检测算法

小波变换对分析图像局部特征十分有效。根据尺度空间的图像分析理论，1992年，Rattarangsi提出基于尺度空间的角点检测思想。1998年，Mokhtarian和Suomela基于尺度空间提出一种高尺度检测角点，降低尺度改善角点定位的新的角点检测算法。

王展等人采用二阶导数零交叉边缘检测算子以及围线跟踪算法提取边缘曲线，用一组自相似二进Gabor小波变换滤波器将频域分为多个子带，对两不同尺度滤波器输出求差并取模，根据结果判定该点是否是角点。

4 结语

基于匹配的目标识别是图像识别、目标跟踪等研究领域非常重要的研究方向，其征匹配、焦点检测、小波变换等都具有广泛的应用范围。该文介绍了多种基于匹配的目标识别方式，分析其发展和优缺点，对进一步的算法选择和研究提供了参考。

参考文献

[1] Lewis JP.Fast Template Matching[J].Vision Interface ，1995，32（4）：351-361.

[2] Kim Jeesun，Cvejic Erin，Davis Chris.Tracking eyebrows and head gestures associated with spoken prosody[J].Speech Communication， 2014（57）：317-330.