匹配算法论文汇总十篇

序论：好文章的创作是一个不断探索和完善的过程，我们为您推荐十篇匹配算法论文范例，希望它们能助您一臂之力，提升您的阅读品质，带来更深刻的阅读感受。

篇（1）

1 引言

藏文信息处理存在着分词的问题，而藏文分词是对藏文词性标注、藏语音合成、机器翻译、大型语料库建设和信息检索等藏文信息处理的基础。藏文分词的效果会对进一步研究的藏文词性标注、藏语音合成、机器翻译、大型语料库建设和信息检索等藏文信息处理软件的性能和效果产生影响。

为了提高分词的准确率，需要有一个足够大的词库，面对足够大的词库，对词库中的词语的搜索技术就显得十分重要，对词库中词语的搜索速度直接关系到分词系统的性能。词库目前主要是采用索引的机制来实现的，一般用到的索引结构的包括线性索引、倒排表、Trie树、二叉树等。线性索引、倒排表都是静态的索引结构，不利于插入、删除等操作。

2 分词

2.1 词典机制算法

本系统采用的是基于Hash索引的分词词典。分词词典机制可以看作包含三个部分：首字Hash表、词索引表、词典正文。词典正文是以词为单位txt文件，匹配过程是一个全词匹配的过程。首先，通过首字Hash表确定该词在词典中的大概位置，然后根据词索引表进行定位，进而找到在词典正文中的具置。该系统是采用Myeclipse10平台，使用Java语言进行实现的，直接调用Java里的hashmap创建函数，找到该词之后，然后进行字符串匹配。

2.2 基于匹配算法分词

主流的分词方法有三种：分别为基于语言学规则的方法、基于大规模语料库的机器学习方法、基于规则与统计相结合的方法，鉴于目前藏文方面还没有超大型的句子语料库。该系统便采用了基于语言学规则的根据词典进行匹配的方法对藏文进行分词。

根据匹配的方向不同，分为正向和逆向两种匹配算法。本系统采用的是正逆向匹配算法相结合的减字匹配法对藏文进行分词的，因为藏文在每个字的结束时，都会以“”作为分界；每个句子会以“”或者“” 作为分界。因此，对藏文进行分词的减字算法首先以藏文的字符“”或者“”切分出句子，如此一来，原文就被分为相应的若干个句子了。接下来，再对每一个句子进行词典的匹配，如果没有匹配成功就根据藏文字符中“”从句末尾减去一个字符，然后再次进行匹配，直到匹配成功为止。对每个句子重复这些流程，直到每个句子全部分解为词为止。逆向最大匹配是从句子的末尾选择计算最大词的长度，从后往前匹配、切分，其基本原理是和正向最大匹配的原理是相同的。

为了提高切分的精度，该系统使用的是正向最大匹配和逆向最大匹配相结合的方法进行分词，先分别采用两种方法分词，然后根据概率比较两种分词结果，选择概率较大的那种匹配算法作为分词结果。

本系统的逆向最大匹配和正向最大匹配均是采用减字匹配算法，减字算法实现简单，切分效果也比较理想，流程如图1所示。

正向最大匹配（MM） 对于文本中的字串 ABCD，ABCD？W，若ABC∈W，并且AB∈W，然后再判别CD是否属于W，若是，则就切分为AB/CD，如果不是，则切分为AB/C/D。其中W 为分词的词典。逆向最大匹配对于文本中的字串 ABCD，ABCD？W，BCD？W，CD∈W，并且AB∈W，其中W为分词的词典，那么就取切分 AB/CD，根据藏文词组最长的为6个字符组成的，所以进行匹配算法的时候，初始化藏文最大字符串长度为6，流程图如图2所示。而逆向最大匹配算法是从句子的末尾开始进行匹配，其核心算法与正向最大匹配算法相同，只不过开始匹配的方向不同而已。

无论是正向匹配（MM）算法还是逆向匹配（RMM）算法都会产生大量的歧义字段。我们很容易举出这样的例子，如：（五十六个民族心连心）这一句藏语，采用正向匹配算法分词的结果为：，采用逆向匹配算法的分词结果为：，在采用逆向匹配的时候，将会被划分为，而（五十六）实际是一个词，不该划分，诸如此类的藏文句子还有很多，例如 等，无论使用正向最大匹配算法或者使用逆向最大匹配算法都会产生歧义，这种歧义称为组合歧义。为了减少这种歧义的影响，本系统使用两种分词方法相结合的方式。首先分别使用两种算法进行分词，然后通过统计的方法消除部分歧义。具体实现为：设正向最大匹配算法所切分的n个词分别为，则这个句子切分的频率则为；设逆向最大匹配算法所切分的n个词分别为，则这个句子切分的频率则为。如果，则选择正向最大匹配算法所切分的结果，反之，则选择逆向最大匹配算法所切分的结果。

3 结果和分析

结合26个大小不同的实验文本，对基于哈希表索引和匹配算法的分词系统的准确率进行了分析，准确率如图3所示。结果显示，该分词系统的准确率在92%以上。由此可得基于哈希表索引和匹配算法的分词系统在准确率上有不错的效果。

参考文献

[1]华却才让.基于树到串藏语机器翻译若干关键技术研究[D].陕西师范大学，2014.

[2]石方夏，邱瑞，张|，任帅.藏文信息隐藏技术综述[J].物联网技术，2014，12：28-32.

[3]王思力，张华平，王斌.双数组Trie树算法优化及其应用研究[J].中文信息学报，2006，05：24-30.

[4]陈硕，桂腾叶，周张颖等.信息检索在论文写作和项目申报中的应用[J].科技展望，2015，13：274-275.

[5]黄昌宁，赵海.中文分词十年回顾[J]. 中文信息学报，2007，03：8-19.

[6]奉国和，郑伟.国内中文自动分词技术研究综述[J].图书情报工作，2011，02：41-45.

[7]贺艳艳.基于词表结构的中文分词算法研究[D].中国地质大学（北京），2007.

[8]戴上静，石春，吴刚.中文分词中的正向增字最大匹配算法研究[J].微型机与应用，2014，17：15-18.

[9]刘遥峰，王志良，王传经.中文分词和词性标注模型[J].计算机工程，2010，04：17-19.

作者简介

陈硕（1995-），男，自治区拉萨市人。本科在读，主研领域为自然语言处理，数学建模及其应用。

周欢欢（1994-），女，湖南省衡阳市人。本科在读，研究方向为数学建模及其应用、交通运输规划与管理。

通讯作者简介

赵栋材（1976-），男，现为大学藏文信息技术研究中心副教授。主要研究方向为藏文信息处理。

篇（2）

[4]

ZAKI T， ESSAADY Y， MAMMASS D， et al. A hybrid method ngramsTFIDF with radial basis for indexing and classification of Arabic document [J]. International Journal of Software Engineering and Its Applications， 2014， 8（2）： 127-144.

[5]

SIDOROV G， VELASQUEZ F， STAMATATOS E， et al. Syntactic dependencybased ngrams as classification features [C]// MICAI 2012： Proceedings of the 11th Mexican International Conference on Artificial Intelligence， LNCS 7630. Berlin： Springer， 2013： 1-11.

[6]

YI Y， GUAN J， ZHOU S. Effective clustering of microRNA sequences by ngrams and feature weighting [C] // Proceedings of the 2012 IEEE 6th International Conference on Systems Biology. Piscataway： IEEE， 2012： 203-210.

[7]

BOURAS C， TSOGKAS V. Enhancing news articles clustering using word ngrams [C] // DATA 2013： Proceedings of the 2nd International Conference on Data Technologies and Applications. London： dblp Computer Science Bibliography， 2013： 53-60.

[8]

GHANNAY S， BARRAULT L. Using hypothesis selection based features for confusion network MT system combination [C] // EACL 2014： Proceedings of the 3rd Workshop on Hybrid Approaches to Translation （HyTra）. Stroudsburg： Association for Computational Linguistics， 2014： 2-6.

[9]

SIDOROV G， VELASQUEZ F， STAMATAOS E， et al. Syntactic ngrams as machine learning features for natural language processing [J]. Expert Systems with Applications， 2014， 41（3）： 853-860.

[10]

HAN Q， GUO J， SCHTZE H. CodeX： combining an SVM classifier and character ngram language models for sentiment analysis on Twitter text [C]// SemEval 2013： Proceedings of the Second Joint Conference on Lexical and Computational Semantics （*SEM）， Volume 2： Proceedings of the Seventh International Workshop on Semantic Evaluation. Stroudsburg： Association for Computational Linguistics， 2013： 520-524.

http：//p.nus.edu.sg/～antho/S/S13/S13-2086.pdf

[11]

BESPALOY D， BAI B， QI Y， et al. Sentiment classification based on supervised latent ngram analysis [C] // CIKM 11： Proceedings of the 20th ACM International Conference on Information and Knowledge Management. New York： ACM， 2011： 375-382.

[12]

MILLER Z， DICKINSON B， HU W. Gender prediction on Twitter using stream algorithms with ngram character features [J]. International Journal of Intelligence Science， 2012， 2（4A）： 143-148.

[13]

WRIGHT J， LLOYDTHOMAS H. A robust language model incorporating a substring parser and extended ngrams [C] // ICASSP 1994： Proceedings of the 1994 IEEE International Conference on Acoustics， Speech， and Signal Processing. Washington， DC： IEEE Computer Society， 1994： 361-364.

[14]

HACIOGLU K， WARD W. Dialogcontext dependent language modeling combining ngrams and stochastic contextfree grammars [C] // ICASSP 2001： Proceedings of the 2001 IEEE International Conference on Acoustics， Speech， and Signal Processing. Washington， DC： IEEE Computer Society， 2001， 1： 537-540.

[15]

SIU M， OSTENDORF M. Variable ngrams and extensions for conversational speech language modeling [J]. Speech and Audio Processing， 2000， 1（8）： 63-75.

[16]

ZHOU S， GUAN J， HU Y， et al. A Chinese document categorization system without dictionary support and segmentation processing [J]. Journal of Computer Research and Development， 2001， 38（7）： 839-844. （周水庚，关佶红，胡运发，等.一个无需词典支持和切词处理的中文文档分类系统[J].计算机研究与发展，2001，38（7）：839-844）

[17]

GAO Z， LI X. Feature extraction method based on sliding window application in text classification[J]. Science & Technology Information， 2008（34）： 23-24. （高振峰，李锡祚.基于滑动窗口的特征提取方法在文本分类中的应用[J].科技信息：学术版，2008（34）：23-24.）

[18]

篇（3）

中图分类号：TP311.52

1 引言

在现有的毕业论文选题系统中，一个学生只能选择一个题目作为自己最终的题目，同样，一个题目只能分配给一个学生。如果最后题目由学生自己确定，那就会出现先选的学生具有更大的选择余地，后选的学生由于不能再选已经选定的题目，所以其可选择的题目会越来越少，这对很多学生来说很不公平。如果学生选择自己的志愿，最终题目由老师来定，这不但加大了老师的工作量，而且还是不能保证每位同学的公平性。如何采用计算机智能辅助选题，设计最优匹配算法实现学生与题目的整体最优匹配，会大大提高选题的效率。

汤颖曾在《毕业设计立项与选题管理及其支持系统》中提出，采用模糊匹配技术进行学生-题目的自动匹配；潘志方在《一种改进的Ford-Fulkenson算法在选题系统中的应用研究》中将题目与学生的匹配抽象为二分图的匹配，并采用改进的Ford-Fulkenson算法实现题目与学生的自动匹配。以上两种方法只考虑了学生与题目之间的最大匹配值，并没有考虑学生的整体满意度最优的情况。

本文将通过采用最优匹配算法（KM）确定一种匹配方案，使得学生的整体满意度最高。具体方法概括如下：学生预选多个题目，并根据自己对题目的满意度由高到底排序，这样，满意度成为二分图的一分值，如图1所示：

2 系统功能模块设计

根据前期的可行性分析，本系统主要进行以下模块的设计：系统管理员模块、专业负责人管理模块、指导教师管理模块和学生选题模块。

系统管理员模块主要负责对系统参数的设置及用户的管理。主要实现以下功能：

（1）系统设置：对系统标题、毕业生、选题参数设置；

（2）学院及专业设置：完成学院、专业的添加、删除、修改操作；

（3）数据字典的维护：教师信息、选题难度、选题方向灯信息的维护；

（4）教师和学生的管理：完成教师、学生信息的添加、删除和修改操作；

（5）文件文化建设管理：日志文件查看、上传文件的管理。

专业负责人管理模块与系统管理员权限相似，但操作的数据只能针对于指定专业，无法浏览及操作整个学院的课题及学生信息。最重要的功能是实现题目的审核。

导师管理模块主要用于选题以及选择自己选题学生的审核确认。

（1）个人中心管理：如信息修改及密码重置；

（2）选题管理：选题的增加、修改、删除以及选题类型的设置；

（3）学生选题查询及审核。

学生模块主要实现学生选题的选择及确认。

（1）学生个人信息的修改；

（2）学生选题及确认信息查询；

（3）学生留言及咨询。

3 KM算法在系统中的实现

KM算法由Kuhn和Munkras分别提出来，这是一种问题。经典的算法。该算法由通过每个顶点一个顶标（A[i][j]）来求最大权匹配的问题转化为不断寻找增广道路以使二分图的匹配数达到最大的完备匹配。KM算法的关键在于不断寻找二分图中的可增广道路。如果找到一条可增广道路，就可以额将属于和不属于相等子图的边取相反，从而相等子图里就是增加一条边，一直到所有的顶点都进入相等子图为止。

KM算法可以很好地解决选题系统中，题目与学生最优匹配的问题。下面以国际商学院09级本科学生选题为例。

在匹配过程中，设学生的集合为X={X1，X2，X3……Xn}，选题的集合设置为Y={Y1，Y2，Y3……Yn}，学生对自己选题的满意度为二维矩阵Z[m][n]，其他题目规定权值为0。系统规定学生最多可预选3个题目，并按照满意度分别设置0.9，0.7，0.5。以下表1是对国际经济与贸易专业使用不同算法得出的学生满意程度。

下面对以上数据进行说明。如采用手工分配的方式，使得681名学生中414名同学分的了题目，满意度为60.82%；如果采用最大匹配算法进行分配，可以使分配数达到最大，有517名学生分得题目，满意度上升为79.99%；最有用最有匹配算法进行分配，使总体满意度达到78.24%，533人。需要说明的一点是，KM算法只是找到了整体最优匹配而不是最大数匹配，如果整体最优情况下匹配数和最大匹配数相差得太大的话，那么整体最优方案显得不太可取。所以，最好的情况就是同时考虑最优匹配和最大匹配来同时控制两者的大小。

4 结语

本系统实现了毕业论文选系统工作的各个管理功能，通过实现教师与学生的双向选择，使用KM算法，提高选题的质量和效率，为学院充分利用网络完成毕业论文选题工作提供了便利的平台。

参考文献：

[1]汤颖.毕业设计立项与选题管理及支持系统[J].合肥工业大学学报，2006，29（5）.

篇（4）

中图分类号：TP301文献标识码：B

文章编号：1004 373X(2009)02 063 05

Application of Pattern Matching Algorithm in Intrusion Detection Technique

RAN Zhanjun1,YAO Quanzhu2,WANG Xiaofeng1,ZOU Youjiao1

(1.Xi′an University of Technology,Xi′an,710054,China;2.College of Computer Science and Engineering,Xi′an Unversity of Technology,Xi′an,710048,China)

Abstract：Relying solely on traditional passive defense technology has been unable to meet today′s network security needs,IDS based on pattern－matching is becoming a hotspot of research and application,the efficiency of pattern matching determines the performance of this kind of IDS.A survey of the intrusion detection system classic pattern matching algorithm is given in this paper,including single pattern matching algorithm:KMP algorithm,BM algorithm,RK algorithm and multi－pattern matching algorithm －AC algorithm,AC－BM algorithm.Meanwhile,the efficiency of various algorithms is summarized.Through analysis of algorithms,future research directions of this kind of algorithm are advanced.

Keywords：intrusion detection;KMP algorithm;BM algorithm;RK algorithm;AC algorithm;AC－BM algorithm

0 引 言

随着网络技术的发展，各种基于网络的应用层出不穷。面对日益突出的网络安全问题，仅靠传统的被动防御已经不能满足要求，能够主动检测并预防的入侵检测系统应运而生。

根据采用的分析方法，入侵检测分为误用检测和异常检测。误用检测是指：根据己知的攻击方法，预先定义入侵特征，通过判断这此特征是否出现来完成检测任务。异常检测是指：根据用户的行为或资源的使用状况的正常程度来判断是否属于入侵。由于异常检测的误检率和漏检率高，因此目前大多数入侵检测系统产品均主要采用误用检测的方法。误用检测中使用的检测技术主要有: 模式匹配、专家系统、状态转移等，其中模式匹配原理简单，可扩展性好，而且最为常用。据统计，现在大约95%的入侵检测都是特征匹配的入侵检测。

由此可见，模式匹配算法性能的好坏直接影响到入侵检测系统的效率。随着网络传输速度的大幅度提高，入侵检测系统需要处理的数据量越来越大，如果模式匹配算法来不及处理这些实时的大量的数据包，必然会丢弃部分数据包，而这些被丢弃的数据包中很可能就包含有入侵信息，从而造成漏报。在此介绍几种著名的用于入侵检测的模式匹配算法，包括单模式匹配算法和多模式匹配算法，通过对它们进行剖析和实际测试，提出入侵检测系统中模式匹配算法的选择策略和未来的研究方向。

1 单模式匹配算法

1.1 相关定义

模式匹配：是指在给定长度为n的目标串T=T1T2…Tn中查找长度为m的模式串P=P1P2…Pm的首次出现或多次出现的过程。这里Ti(1≤i≤n)，

Pj(1≤j≤m)∈∑(字符集)，若P在T中出现1次或多次，则称匹配成功，否则称匹配失败。

单模式匹配算法：在目标串中1次只能对1个模式串进行匹配的算法。

多模式匹配算法：在目标串中可同时对多个模式串进行匹配的算法。

最简单的模式匹配算法是Brute－Force算法(BF算法)。在BF算法的目标串和模式串的字符比较中，只要有1个字符不相等，而不管前面已有多少个字符相等，就需要把目标串T回退，下次比较时目标串T只后移1个字符。虽然算法简单，但效率低下，不适合用于入侵检测系统中，不做重点介绍。

高效的模式匹配算法都是设法增大不匹配时目标串T或模式串P之间的偏移量，以减少总的比较次数。下面介绍3种经典的快速单模式匹配算法。

1.2 KMP算法

1970年，S.A.Cook从理论上证明了一维模式匹配问题可以在O(m+n)时间内解决［1］。D.E.Knuth，V.R.Pratt和T.H.Morris 在BF算法的基础上提出了一种快速模式匹配算法，称为KMP算法［1］，该算法消除了BF算法的目标串指针在相当多个字符比较相等后，只要有1个字符比较不等便需要回溯的缺点，使算法的效率得到了大幅度提高，时间复杂度达到最理想的O(m+n)，空间复杂度是O(m)。

KMP算法的基本思想是：若某趟匹配过程中Ti和Pj不匹配，而前j-1个字符已经匹配。此时只需右移模式串P，目标串T不动，即指针i不回溯，让Pk与Ti继续比较。移动后重新开始比较的位置k仅与模式串P有关，而与目标串T无关，因此k可以通过下面的next函数事先确定。

定义next［j］函数为：

next［j］=max{k|1＜k＜j且 P1P2…Pk=

Pj-kPj-k+2…Pj-1} ，集合非空

0，其他情况

-1(标记)，j=0时

1.3 BM算法

相对于BF算法，KMP算法虽然消除了主串指针的回溯，在不匹配时能使模式串右滑若干位，但由上述next函数可知：右滑的最大距离不会超过1趟匹配操作所进了的比较次数j，原因在于KMP算法的匹配操作是从左到右进行的。受到KMP算法的启发，R.S.Boyer和J.S.Moore提出一种新的快速字符串匹配算法－BM算法［1－3］。

BM算法基本思想是：开始时将目标串T与模式串P左对齐，自右至左逐个字符进行比较(即首先比较Pm与Tm)；当某趟比较时Ti与模式串的对应字符不匹配，则把模式串右滑d(x)一段距离，执行由Pm与Ti+d(x)起始的自右至左的匹配检查。BM算法采用以下两条规则计算模式串右移的距离：

(3) g是转移函数，该函数定义如下：g(s,a)：从当前状态s开始，沿着边上标签为a的路径所到的状态。假如(u,v )边上的标签为a，那么g ( u,a ) =v；如果根节点上出来的边上的标签没有a，则g(0,a) =0，即如果没有匹配的字符出现，自动机停留在初态；

(4) f(不匹配时自动机的状态转移)也是转移函数，该函数定义如下：

f(s)：当w是L(s)最长真后缀并且w是某个模式的前缀，那么f(s)就是以w为标签的那个节点；

(5) q0∈Q是初态(根节点，标识符为0)；

(6) FQ，是终态集(以模式为标签的节点集)。

这样，在目标串中查找模式的过程转化成在模式树中的查找过程。查找一个串T时从模式树的根节点开始，沿着以T中字符为标签的路径往下走：若自动机能够抵达终态v，则说明T中存在模式L (v)；否则不存在模式。

AC算法模式匹配的时间复杂度是O(n)，并且与模式集中模式串的个数和每个模式串的长度无关。无论模式串P是否出现在目标串T中，T中的每个字符都必须输入状态机中，所以无论是最好情况还是最坏情况，AC算法模式匹配的时间复杂度都是O(n)，包括预处理时间在内，AC算法总时间复杂度是O(M+n)，其中M为所有模式串的长度总和。

2.3 AC－BM算法

对多模式串的匹配而言，虽然AC算法比BM算法高效得多，但AC算法必须逐一查看目标串的每个字符，即必须按顺序输入，不能实现跳跃，而BM算法则能够利用“右滑”跳过目标串中的大段字符，从而提高搜索速度。如果将BM算法的这种启发式搜索技术应用到AC算法中，则可大大提高多模式匹配算法的效率。许多人据此给出了各种改进的算法。Commentz－Walter最先将BM算法和AC算法结合在一起给出了Commentz－Walter算法；Baeza－Yates结合BMP算法和AC算法也给出了多模式匹配改进算法。

AC－BM算法［5］是Jang－Jong在1993年结合AC算法的有限自动机和BM算法的连续跳跃思想提出来的新算法，利用劣势移动表和优势跳转表来实现跳跃式地并行搜索，算法的时间复杂度为O(mn)。

该算法的思想是：首先把要查找的多个模式构成一个关键字树，把相同的前缀作为树的根节点。模式树从目标串的右端向左移动，一旦模式树确定在适当的位置，字符比较从左向右开始进行。模式树移动时同时使用坏字符移动和好前缀移动。坏字符移动的策略为:如果出现不匹配的情况，移动模式树，使得树中其他模式的能与当前目标串正在比较的字符相匹配的那个字符移动到与当前目标串正在比较的字符的相同位置上，如果在当前的深度上，目标字符没有出现在任何模式中，则模式树的偏移量为树中最短模式的长度。好前缀移动的移动策略为：将模式树移动到一个已被发现是另一个模式子串完全前缀的下一个位置，或者移动到作为树中另一个模式后缀能够正确匹配目标串的某个前缀的下一个位置。在模式树的移动过程中，必须确保模式树的偏移量不能大于树中最短的模式长度。

2.4 AC，AC－BM算法改进情况简介

文献［10］中卢汪节等人针对AC算法在构造状态机时空间冗余较大的情况，对状态机各结点进行压缩存储，使空间性能和时间性能都有提高；文献［11］中万国根等人对AC－BM算法的改进借鉴了BMH算法的思想，取消了原算法的好前缀跳转，优化了坏字符跳转，并修改了skip的计算方法，对大字符集的情况在平均情况下具有更优的性能；文献［12］对AC－BM的改进则是通过预处理思想实现的，在进行AC-BM匹配之前首先扫描首和(或)尾字符，确定其位置，再到相应位置进行匹配，相当于把目标串按模式串首、尾字符分成数段，每段进行比较，段间不含首字符的就直接跳过，不用比较，从而提高效率。

3 算法的实际执行效率

上述这些算法究竟哪种算法具有最好的执行效率呢?能不能仅通过时间复杂度来进行衡量呢？时间复杂度仅是一个度量的范围，表示受几个参数的影响，并不代表一个具体的值，还需要在具体的环境中进行测试。

文献［13］测试了包括上述算法在内的多种单模式和多模式匹配算法的性能。测试平台为：硬件：CPU Intel Xeon 3.46 GHz X 2，内存2 GB DDR，硬盘200 GB SCSI；软件：Windows 2003 Server,Intel IXA SDK4.1。单模式匹配测试的规则集，使用随机生成的8，16，32，48，128位具有代表意义的规则，可以对应端口、IP地址，MAC地址、IPv6地址等，对多模式匹配测试采用Snort系统2.4.3规则集。

单模式匹配算法主要测试模式长度与匹配时间、占用空间及预处理时间的变化关系。测试结果表明：各算法的测试指标在规则长度增长的情况下均呈递增趋势，但BM算法的增长速度最为缓慢，在不太在意存储空间的情况下，BM可以作为优先考虑的算法，同时对IPV6地址也更为合适。

多模式匹配算法的测试项目为规则数与单位匹配时间、占用储存单元、单位预处理时间的变化关系。测试结果表明AC－BM算法在上述3项测试中取得了很好的性能平衡。这也是新

版的Snort系统中选用AC－BM算法的重要原因。

4 入侵检测系统中模式匹配算法的研究方向

常用的模式匹配算法所采用的思想主要有基于字符比较、基于自动机、基于hash查找、基于位逻辑运算和基于Tries树型机构搜索。鉴于目前网络的实际状况，多模式匹配算法更加适合于基于模式匹配的入侵检测系统。这里认为应该从下面3个方面着手：一是继续研究和改进精确的模式匹配，将快速的单模式匹配算法和多模式匹配算法相结合，充分借鉴同类算法的先进思想，如：引入Hash函数、引入自动机、对字符串分块等来不断提高多模式匹配算法的性能；二是尝试采用模糊匹配的策略，国外对此已经开始进行相应的研究；三是对网络数据包和入侵特征进行研究，总结出这两类字符串特点，有针对性地对这两类字符串的匹配问题进行研究。

5 结 语

网络带宽的不断增加、日益严重的网络安全状况要求必须尽快提高网络入侵检测系统的性能。虽然入侵检测系统可以采用很多技术，并且这些技术也在不断的研究和发展中，但是目前主流的实用的入侵检测技术仍然是基于模式匹配的。因此如何提高模式匹配的效率成为研究入侵检测系统的一个关键所在。在此对已有的经典模式匹配算法进行了系统综述，并对入侵检测系统中模式匹配算法的未来研究方向给出了观点。

参考文献

［1］庞善臣,王淑栋,蒋昌俊.BM串匹配的一个改进算法［J］.计算机应用,2004,12(12):11－13.

［2］Boyer R S,Moore J S.A Fast String Searching Algorithm ［J］.Communications of ACM,1977,20(10):762－772.

［3］张立航,潘正运,刘海峰.基于改进的KR算法在网闸中的实现［J］.微计算机信息(管控一体化),2008(24):137－138.

［4］Johnson T,Newman－Wolfe R E.A Comparison of Fast and Low Overhead Distributed Priority Locks ［J］.Journal of Parallel and Distributed Computing,1996,32(1):74－89.

［5］Jason C C,Staniford S,McAlemey J.Towards Faster String for Intrusion Detection or Exceeding the Speed of Snort ［EB/OL］./sotfware/acbm/speed－of－snort－03－16－2001.padf,2003.

［6］黄占友,刘悦.对KMP串匹配算法的改进［A］.第四次全国便携计算机学术交流会论文集［C］.北京:科学出版社,1997.

［7］涛,方滨兴,胡铭曾.对BM串匹配算法的一个改进［J］.计算机应用,2003,23(3):6－8.

［8］张国平,徐汶东.字符串模式匹配算法的改进［J］.计算机工程与设计,2007,28(20):4 881－4 884.

［9］蔡晓妍,戴冠中,杨黎斌.一种快速的单模式匹配算法［J］.计算机应用研究,2008,25(1):45－46,81.

［10］卢汪节,鞠时光.入侵检测系统中一种改进的AC算法［J］.计算机工程与应用,2006(15):146－148.

［11］万国根,秦志光.改进的AC－BM字符串匹配算法［J］.电子科技大学学报,2006,35(4):531－533.

［12］周四伟,蔡勇.AC－BM算法的改进及其在入侵检测中的应用［J］.微计算机应用,2007,28(1):27－31.

［13］王琢,赵永哲,姜占华.网络处理模式匹配算法研究［J］.计算机应用研究,2007,24(12):310－312.

作者简介

冉占军 男，1977年出生，陕西西安人，讲师，硕士研究生。主要研究方向为算法、网络安全。

篇（5）

中图分类号：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.

篇（6）

中图分类号：TP301文献标识码：A文章编号：1009-3044(2011)25-6122-02

Research of the Text Subjective Question's Auto Remarking Algorithm Based on Word Segmentation Algorithm &VSM

LI Xue-jun

(Southwest University of Science and Technology, Mianyang 621010, China)

Abstract: The paper makes use of the studied results(such as Vector Space Model (VSM), Word Segmentation algorithm and so on) of the native language understanding, and applys them in processing the text subjective question's answer (including the standard answer and the student's answer), and then it used the text_charactered vector matching algorithm to auto remark those student's examining paper by the computer system. According to the experiment, the algorithm has accuracy of remarking and some valuable domains of application.

Key words: Auto-remarking; Word Segmentation algorithm; Vector Space Model (VSM); Text character matched

随着计算机技术和互联网技术迅猛发展，传统教育模式发生了变化，越来越多的课程提出了在线考试的需求。计算机可以很好地完成客观题（如选择题、判断题）的判分工作，其判分策略、关键技术及其应用实例详见文献[1]至文献[3]。亦即把考生作答的结果和题目标准答案进行精确匹配从而得到考生的得分。文献[4]提出了一种近似串匹配算法来对文本录入题的自动评分算法，其本质还是进行文本的比较，与客观题的判分原理基本是相同的。

计算机自动评分是指利用计算机程序来模拟人工评分的标准和内部过程。对客观题的评分是通过把试题的标准答案与考生的答案做一个精确比较，并据此作为是否给学生相应的题目分值；对于主观题，目前一般是让考生把其作答的结果形成一个文件（答案文件），再通过网络把考生的答案文件上传到考试服务器中的专用目录中，科任教师在考试结束后对考生的答案文件进行人工评判来进行给分；最后把考生客观题的计算机自动评分结果和主观题的人工评分结果累加起来作为考生的最终成绩。对于客观题可以完全不要人工干预，而主观题就必须在人工干预下才能完成。

因此本文就此提出将人工智能的自然语言理解技术（主要是分词算法）、文本的空间向量模型表示和知识的框架表示内容应用到网络考试系统中的主观题的自动评分过程中。

1 文本主观题自动评分原理

对于在线考试系统来说，其自动评分是在特定范围内的，不需要让其理解所有的自然语言，只需要理解标准答案即可。因此，应该使用某种算法使标准答案转化成机器能够理解的形式，将考生答案也按照一定的规则转化成计算机可以理解的形式，然后再将其和标准答案进行匹配并评分。其关键是如何将评分规则转化为可以被机器理解的知识库。主观题的自动评分原理如图1所示。

2 自动分词算法简介

2.1 最大匹配分词算法

匹配分词法是按照一定的策略将待切分的汉字串与一个“充分大的”机器词典（如金山词霸等）中的词条进行匹配，若在词典中找到某个字符串，则匹配成功（识别出一个词）。按照扫描方向的不同，串匹配分词方法可以分为正向匹配和逆向匹配。按照不同长度优先匹配的情况，可以分为最大（最长）匹配和最小（最短）匹配。最大匹配分词法即先确定一个最大的词的长度，然后从左（正向）或从右（逆向）取该长度的词串，将词串与词典中的词条匹配，如果没有该词则去掉一个字符继续匹配，以此类推，直到达到匹配或剩下一个单字为止。

2.2 最大概率分词算法

最大概率分词算法的基本思想是：假设一个待切分的汉字串可能包含多种分词结果，将其中概率最大的那个作为该字串的分词结果。例如，有一个句子S＝“有意见分歧”，第一种分词路径W1＝“有/意见/分歧/”，第二种分词路径W2＝“有意/见/分歧/”，如图2所示。到底应该选择哪一种为最后的分词结果呢？

根据概率分词算法的基本思想，需要计算每一种方法出现的选取概率的作为最后结果，即计算Max(P(W1|S), P(W2|S))。概率计算方法如图3所示。

每一个词汇出现的概率P(wi) 可以在带词频的词典中查出。通过查词典可以得到每个词的概率为：P(有)=0.0180，P(有意)=0.0005，P(意见)=,0.0010，P(见) =0.0002，P(分歧)=0.0001。

对于第一种分词方法：P(w1) = P(有) * P(意见) * P(分歧) = 1.8×10-9；

对于第二种分词方法：P(w2) = P(有意) * P(见) * P(分歧) = 1×10-11；

由上所示，P(w1) > P(w2)，所以取第一种方法作为分词结果。

3 文本矢量特征匹配算法

主观试题的答案以文本方式存储，经过分词后的文本如何表示才能更加容易地被计算机处理关系到文本处理的准确性，因此文本表示方法是自动评分算法的一个关键问题。近年来，在Web文本信息特征获取算法的研究中，矢量空间模型(Vector Space Model，VSM )[5-6]是应用较多且效果较好的方法之一，本算法借鉴了该模型的思想。在矢量空间模型中，文本被看作由一组正交词条所生成的矢量空间。根据这个思想，同时考虑到考试评分中经常将试题答案分为几个要点，因此提出主观题成绩评判模型为：

首先，答案文本是由一些要点组成，如果把答案文本（Answer text 用A来表示）看成一个由n个要点（Pi）组成的集合，则可以这样表示答案：A={P1,P2,…,Pi,…,Pn}；设每个要点Pi的分值为Mi，则该答案的总分M为：；按照VSM思想，将标准答案每一个要点Pi被看成是由Ki个特征词（wj）组成的向量P：；设每个特征词的权重是wj（由经验丰富的任课教师人工设置），则其归一化权重为：；设考生答案的每一个要点Pi'也被看成是由Ki'个特征词（wj'）组成的向量P'：；通过计算考生答案和标准答案的向量间的距离并据此计算考生可得到到该要点的分值，即：(如果向量间的距离为0，则说明考生答案和标准答案完全匹配，考生可以拿到该要点的所有分值)；考生所得总分M'为：。

4 算法测试及结论

本论文采用oracle作为后台数据库管理系统（因为系统所用的词典数据库都比较大），基于B/S模式设计了基于文本的主观题自动评分测试软件。通过对不同名词解释题目（答案长度及复杂度不同）的评测，再将本算法评得的分数与人工评分相比，分数的容差在（－0.5～＋0.5），可以测得其评分的准确度在86.93％。通过实际的数据测试可以看出，答案越复杂，要点越多，评分的准确性越差；相反，要点越少，答案越简单，评分的准确性越好。而且人工设置关键词和权重也有利有弊，人工设置固然增强了系统的准确程度，但是其前提是设置人必须是有经验的老师，如果是没有经验的老师设置，则给算法增加了人为的误差。该算法具有一定的实用性，但还有待进一步的完善。

参考文献：

[1] 华蕊. 自动组卷及评分系统的设计[J]. 中国电化教育.2002,(2):84-85.

[2] 朱映辉, 江玉珍.计算机自动评卷策略分析与研究[J]. 电脑知识与技术,2005,(35):30-32.

[3] 李丁. 计算机考试系统中自动评分策略的研究与实现[J]. 广东广播电视大学学报,2002,11(4):30-32.

篇（7）

中图分类号:TP391.7 文献标识码:A

The Research of Cloud Data Alignment

CHEN San-qing

(School of Computer, Panzhihua University, Sichuan Panzhihua 617000)

Key words: cloud data; alignment;ICP algorithm

为了得到物体真实的三维模型,人们需要获得三维物体表面的真实数据。但是,由于受到测量设备和环境的限制,物体表面完整测量数据的获得往往需要通过多次测量完成。点云(三维数据)就是使用各种三维数据采集仪采集得到的密集数据,它记录了有限体表面在离散点上的各种物理参量。三维曲面的重建就是依据这种密集的点云数据来恢复原始曲面,进而实现三维模型的真实重现的目的。

由于每次测量得到的点云数据往往只覆盖物体部分表面,并且可能出现平移错位和旋转错位,为了得到物体完整表面的点云数据,需要对这些局部点云数据进行整合和配准。因此,在得到点云数据之后,为了得到三维模型的原始曲面,必须要将不同角度,不同位置扫描得到的大容量三维空间数据点集转换到一个统一的坐标系中,该技术称之为数据缝合,即三维点云数据的配准。点云配准是点云数据获取后的第一步处理,也是所有后续处理的基础。因此,配准的精度将直接关系到建模精度。

1 点云数据配准算法的研究进展

一般情况下点云都是以高密度形态存在,为了有效处理各种形式的点云,根据点云的分布特征(如排列方式、密度等)可以把点云分为[1]:散乱点云,即测量点没有明显的几何分布特征,呈散乱无序状态;扫描线点云,即点云由一组扫描线组成,扫描线上的所有点位于扫描平面内;网格化点云,即点云中所有点都与参数域中一个均匀网格的顶点对应;多边形点云,即测量点分布在一系列平行平面内,用小线段将同一平面内距离最小的若干相邻点依次连接可形成一组有嵌套的平面多边形。

针对上述各种形式的点云数据,在20世纪80年代中期,很多学者对其配准进行了大量研究。1987年,Horn、Arun等人用四元数法提出点集对点集配准方法。这种点集与点集坐标系匹配算法通过实践证明是一个解决复杂配准问题的关键方法。1992年,计算计视觉研究者Besl和Mckay[2]介绍了一种高层次的基于自由形态曲面的配准方法,也称为迭代最近点法ICP(Iterative Closest Point),并在此基础上产生了许多的变种算法。ICP主要用于解决基于自由形态曲面的配准问题。但ICP算法对两个点云相对的初始位置要求比较高,点云之间初始位置不能相差太大,并且要求两个匹配点集中的一个点集是另外一个点集的子集。当条件不满足,或相差太大时,会影响ICP算法的收敛结果,使得配准变的不可靠。

Chen等运用两个曲面在法矢方向的距离来代替某一点到其最近点的距离,并将其作为匹配的目标评价函数。这一设想最初是由Potmesil于1983年提出的,它被推广为最优加权的最小二乘方法。Masuda等对点集进行随机采样,用最小中值平方误差作为度量准则,该方法在每次迭代后都需要进行重新采样。Johnson等使用特征提取策略去除没有启发信息的平面点来提高配准速度,在点云数据法矢连续、突变比较少的情况下,其速度没有明显的提高。也有一些学者通过引入参考点的方法来实现三维点云数据的配准,这些参考点实际也是一种标签,需要在测量前粘贴在被测物体上。此外,G.Barequet等人在几何哈希技术基础上采用投票机制实现了部分曲面匹配算法。还有使用卡尔曼估计子的三角片曲面匹配方法等。

2 ICP点云数据配准算法及其改进算法

ICP算法最初由Besl和McKay,提出来的时候,其原意是迭代最近点(IterativeClosestpoint)匹配算法,后来被广泛理解为迭代对应点(IterativeCorrespondingpoint)匹配算法。ICP法实质上是基于最小二乘法的最优匹配方法,它重复进行“确定对应关系点集并计算最优刚体变换”的过程,直到某个表示正确匹配的收敛准则得到了满足。目前,ICP算法在点云数据配准中应用相当广泛,并且得到了许多学者的进一步研究和扩充。基于ICP算法点云数据配准过程如图1所示:

2.1Beslhe和Mckay提出的原始ICP算法[2]

设扫描匹配过程中的参考扫描模型为Sr,待匹配的当前扫描模型为Sc,模型中的数据点个数为N。参考扫描模型和当前扫描模型间的变换矩阵为P=(p0,pl,p2,p3,p4,p5,p6)T 其中,PR=(p0,p1,p2,p3)T四元组表示旋转偏移量,可转化为3×3的旋转矩阵R(PR),PT =(p4,p5,p6)T表示平移偏移量。这样,模型间的变换矩阵可以表示为P=( PR | PT )T 。ICP算法在进行点对匹配时采用的是比较点间欧式距离的方法,而扫描模型间的变换矩阵是通过最小化欧式距离平方函数得到。

整个ICP算法描述如下:

第一步:初始化迭代,P0=( l,0,0,0,0,0,0 )T,迭代次数k,设置欧式距离均方差阀值r以及最大迭代次数Kmax 。

第二步:迭代步骤:

(1)对待匹配扫描模型中的每个点搜索其在参考扫描模型中欧式距离最近的点,生成整个扫描模型的邻近点对集合Yk。

(2)由参考模型中的扫描点和匹配点对集合计算扫描模型间的变换矩阵Pk=(PR k | PT k )T和匹配点对间的欧式距离误差dk。

(3)根据变换矩阵Pk=( PR k | PT k )T变换当前扫描模型Sr中的所有扫描点位置。

(4)计算变换后,参考扫描模型与当前扫描模型间的对应点对间的欧式距离误差dk+1,并计算第k和k+1次迭代中误差变化量。当该变化量小于欧式距离均方差阀值r或迭代次数k大于k max时,停止迭代。

ICP算法是一种迭代算法,具有很高的匹配精度。但由算法描述可知,它存在计算量较大且迭代过程可能无法收敛到全局最优解的缺陷。ICP算法最耗费时间的步骤是求解邻近点对的过程,因为它采用的是全局搜索。为适应不同的环境并克服ICP算法自身的部分缺陷,许多研究人员对其进行了改进。

2.2ICP的改进算法

为了提高基本ICP方法的可靠性和鲁棒性,从匹配点的选择到最小二乘度量目标函数的选取等ICP匹配算法中的各个阶段,许多研究者都提出了各种的优化方法,形成了相应的ICP变型算法。ICP算法的各个阶段划分如下[3]:

(1)匹配模型中进行匹配的数据点的选取采样;

(2)两模型中有对应关系的匹配点对的选择;

(3)匹配点对的适当权值赋予;

(4)过滤某些错误的匹配点对;

(5)度量准则的选取;

(6)最优化方法的确定。

对ICP算法的改进主要集中在如下四点[4]:

(1)点集的不同选取方法。一般情况下点集的选取方法包含如下五种情况,分别是选取所有可用点作为点集;随机选取抽样点作为点集;采用平均抽样方法进行点集选取;根据点的特征信息(如梯度信息等)进行点集选取;选取边缘点作为点集。

(2)点的对应方法。点的对应方法主要有二种,一种是搜索最近点作为对应点;另一种是采用投影求交的方法确定对应点。

(3)点对的拒绝。点对拒绝的实现主要有以下三种情况:对于边缘点的拒绝;对于对应点对中距离过大的点对的拒绝;考虑法向量的点对的拒绝。

(4)加速迭代。主要采用减少迭代次数或使用非迭代的方法来实现,作用是减少运算量,提高计算速度。

Chen和Medioni两位学者在Besl和Mckay的经典ICP算法的基础上进行了改进,该算法的不同之处在于改进后算法的目标函数中的距离是点到对应点出的切平面的距离。事实上,因为一开始的匹配点对通常都是不精确的,这种方法认为在这种不精确的意义下,严格地极小化匹配点对之间的距离平方和不能达到快速的收敛,因此它选取了到匹配点处的切平面的距离来代替点到点的距离。这种方法的好处是一开始就可以使迭代误差很快地减小,也就是快速的收敛,但是因为它用切平面来代替真正的曲面,也就是忽略了目标函数的Hessian中的二次项信息,所以这种方法有时候会不收敛,尤其当目标物体表面曲率变化明显时,这时,二次项信息在目标函数种占有更多的比重。事实上,这种方法是一种Gauss-Newton法,它不保证收敛,但是如果收敛,速度会比较快,是二次收敛。后来有研究者对这种方法提出了改进,加上了步长控制[5](Levenberg-Marquart方法),这样可以保证该方法收敛,而且如果步长选取地合适,并不影响收敛速度,仍然二次收敛。此外,Mitra等引入平方距离(Squared Distance)的概念。把Chen和Medioni的改进中所忽略的二阶信息做了一个理想的近似加入了迭代中,因此能保证更好的收敛性。这种方法在满足标准假设的情况下,是一种准牛顿方法。准牛顿方法是收敛的,而且是二次收敛的。

3 结束语

近年来随着三维扫描技术的发展,特别是三维激光扫描技术的出现,高效、快速、准确的获取真实场景的高精度三维点云数据变得较为容易。利用这些点云数据可以恢复重建具有准确几何信息和真实感的原始物体。本文对点云数据处理中的配准方法进行了论述。本文首先总结分析了点云数据配准算法的研究现状,然后对其中比较具有代表性的ICP算法及其改进算法进行了具体的探讨。目前,对ICP算法研究的主要集中在如何提高ICP算法的稳定性、收敛性和可靠性等方面上,通过改进搜索最近点以及计算的收敛性,来提高ICP算法的配准精度和配准速度。

参考文献:

[1]张舜德,朱东波,卢秉恒.反求工程中三维几何形状测量及数据预处理[J].机电工程技术,2001,30(l):7-10.

[2]Besl P J, MeKay N D. A method for registration of3-D shapes.IEEE Trans onPattern Analysis and Maehine Intelligenee ,1992 ,14(2): 239-256.

篇（8）

中图分类号：TP399 文献标识码：A文章编号：1009-3044(2011)23-5698-03

NCC Algorithm Optimization Based on the Wavelet Multi Scale

FU Yan-li

(Shandong SHENG DA Construction Group Limited Company, Jining 272000, China)

Abstract: Algorithms based on pixel gray value are already very common in mage template matching problem, which normalized cross correlation algorithm (Normalized CROSS Correlation. NCC) is one of the classic algorithm based on gray matching, and is widely applied, but the algorithm also has the disadvantages of high time complexity. Multi scale theory and the multiple resolution image are representation and analysis of relevant, i.e. a digital image can be expressed as a multiple resolution sub-images collection. Its characteristic cannot be found in a resolution while in the characteristics of another resolution is easy to find, the wavelet multi-scale analysis is an important tool, known as mathematical microscope, can be used to construct different adaptive filter with improved filter convergence, which is also one of the advantages of wavelet transform. Image after wavelet decomposition, in the lowest layer of the low frequency sub image resolution, retaining only the most information of image, that is after wavelet transform of image of a feature. Based on the wavelet multi scale NCC algorithm not only optimize the algorithm itself at the same time optimization based on gray matching search path, so that guarantee the NCC algorithm accuracy, and reduce the matching time, and also the simulation experiments show that this algorithm is effective.

Key words: image matching; normalized cross algorithm; wavelet transform; multi-scale; tower structure

图像匹配是对两幅图像找其对应的映射关系或根据已知模式到另一副图中寻找相应的模式。图像匹配是一种极其重要的图像处理和分析技术，无论在图像理解还是在视觉计算中都具有重要作用和地位，其成功应用到航空航天、地球物理信息、海洋船载导航和地理特征探测、工业生产、医疗卫生等，因此图像匹配技术越来越受到人们的重视和青睐。

图像匹配的实用的技术方法一般分为两大类，即基于灰度匹配和基于特征匹配。基于灰度匹配是把待匹配图像中的某一像素点的灰度邻域作为匹配模板或者称为子窗口，在参考图中搜索具有相同或者相似灰度值分布的对应的邻域，从而实现两副图的匹配。基于特征的图像匹配不是利用图像中的像素值进行匹配，而是通过灰度导出符号特征（如：拐点、角点、边缘线段、图像轮廓）实现图像的匹配。前者作为一种基本的匹配方法之一，在很多地方得到了充分的应用，可以充分利用图像的所有信息、尤其适合在图像仅有平移和模板图像中非零项比较少的情况下，便于匹配的实现。但是弱点也是很明显的，即对图像的几何变形、光照强度、对比度都很敏感，并且计算量大，不适合实时匹配。后者利用从图像得到的符合特征作为匹配的基元，有效的克服了前者的弱点，但是特征匹配过于依赖图像的特征点，并且特征点的提取涉及到几何和图形形态学的计算，没有统一的模型可以利用，需要对不同图像选择不同的自适应特征，需要额外的特征提取的计算，往往计算也比较复杂。

1 归一化交叉相关算法

归一化交叉相关算法[1] (Normalized Cross Correlation．简称NCC)定义如下：

假设模板图像w(s,t)的尺寸为m×n，其中m,n往往取奇数，参考图像f(x,y)是一个大小为M×N，（1≤m≤M, 1≤n≤N），则：

（1）

其中a=(m-1)/2,b=(n-1)/2

由于表示模板的能量所以是一个常量，，当模板移动距离比较小时，也近似一个常量，所以为使D(x,y)最小则需要达到最大值，由于对w(s,t)和f(x,y)的副值的变化比较敏感，所以定义归一化互相关函数为：

（2）

其中a=(m-1)/2,b=(n-1)/2

为了进一步克服噪声的影响和理想状态匹配时C(s,t)相同值太多，还进一步简化（2）式即：

（3）

其中a=(m-1)/2,b=(n-1)/2，Ef,Ew分别为f(x,y)和w(s,t)的期望。

当C(s,t)达到最大值时，两图匹配成功。

通过对NCC算法的理论分析，不难发现：为了让算法达到理想状态进行图像匹配，牺牲时间，换取了理想的匹配。通过对公式（1）（2）（3）分析，可以看出公式越来越复杂，计算量越来越大，匹配的时间越来越多，由于小波变换可以作为一个平滑过滤器来使用，所以小波变换可以消除图像的幅值和图像的噪音，因此选择了NCC算法的中的公式（1），这样就可以节省大量的计算时间，提高匹配的速度。

2 小波变换的多尺度分析

小波在1987年首次作为分析工具首次出现，小波是多尺度分析的重要工具，被誉为数学上的显微镜[3]，因为小波变换具有时间-频率局部化的特点，即在小波变换中，时间窗函数的宽度与频域函数窗口的函数的都是一个常数，根据测不准原理，他们的乘积也是一个常数。在对低频分析是可以加宽时间窗，减少频率窗；而对于高频分析是，可以增高频率窗，减少时间窗，这种特性被称为“自适应窗口特性”所以小波的这种特性是小波变换能提高为多尺度分析的基础，可以用来构建不同的自适应滤波器以改进滤波器的收敛性。

小波多尺度分析的表示：以多分辨率来解释图像的一种有效并且容易理解的结构就是图像金字塔如图1。一副图像金字塔是一系列以金字塔形式排列的分辨率逐层降低的图像集合。0层是N×N的图像，对0层的图像进行小波亚抽样，可以达到一个原图四分之一的较粗略的缩略图。这个过程是可以重复进行直到N层，这时图像是1×1的图像。这时图像的分辨率也从0层最高到N层逐次下降，是原来图像的四分之一。这样一个图像的金字塔结构共（logN 2+1）层，或者有这么多不同的图像组成，并且图像所用的容量只是原来的图像的4/3N2。

多尺度小波的特点[3]：1）多尺度小波具有窗口自适应的特性，即可以使图像的小波分析聚集到间断点、奇异点和边缘，体现了局部特点；同时也可以获得全局的视点。这个特性是小波变换独有的，对非稳定性和快速变换的信号的分析特别有用的。2）小波变换相当于一组多分辨率的带通滤波器。利用这个特性，可以将图像的信号分解为如图1所示的频率子带上，在每个子带可以用小波变换进行处理。3）多尺度小波分解图像的所有子图的和等于原图像的大小，即不增加存储空间。4）分解后的图像，没有信号损失，保证图像的完整性，便于对低频和高频的处理和上层对下层的实时重建。

3 基于小波多尺度的匹配算法

多尺度小波匹配主要利用了小波多尺度的特性对待配图和参考图进行金字塔式分解，结构如图1，匹配基本流程如图2所示，具体步骤如下：

1）首选判断待配图和参考图的大小，一般待配图比参考图像小多，这时就是在参考图中寻找待配图的位置；反之就是在待配图中搜索作为目标的参考图的过程。两者原理是一样的，所以匹配算法是基于前者论述和测试的。

2）判断待配图和参考图的灰度光照强度、对比度、物体在拍摄时的遮挡情况以及空间几何等，这些都会对基于灰度匹配造成错误的匹配，进行图像匹配前的预处理。

3）以上两步看作图像预处理的过程。接下来选择小波，这步非常重要，本课题选择了Daubechies（db4）小波，因为此小波在运动估计中应用非常广泛，可以很好的保留低频中图像的绝大部分信息，去掉高频信号中的噪声，是一个行之有效的小波。然后利用小波的多尺度特性将待配图和参考图像分解为N层，结构如图1，待配图和参考图未分解的图像为0层（有些文献是将原图定义1层），从低到上，分解的最大层为N层（或者分解的最大尺度为N层），在MATLAB中实现小波变换的最大层的函数是wmaxlev()。但是为了保证低频的中含有未解图的绝大部分信息，尤其是灰度变化比较剧烈的区域，一般分解的层次为：一维分解的分解尺度N不超过5；二维的分解尺度N不超过3。第N层图像的尺寸和大小都是原图来1/(N+1)2。

4）通过前三步，待配图和参考图的原图被分为N层不同频率子图的集合，现在可以在分辨率最低的N层进行待配图的子图与参考图的子图进行匹配。采用了经典灰度相似度量算法：归一化交叉相关算法NCC进行对待配图和参考图进行匹配。整个匹配过程就是将N层的待配图看作模板，匹配的实现基本过程：1）在第N层利用归一化交叉相关算法NCC进行匹配，即求出（1）式的最大值；找出对应匹配区域；2）在N-1层按照N层的算法，再在对应匹配区域进行NCC匹配；3）重复第5步直到0层；4）输出匹配结果。

4 仿真实验

本算法使用Matlab2007b进行了大量的仿真实验，图3是选择了最著名lena图进行算法的仿真说明。

结果分析：

1）为了与其他文献在匹配速度和精确度的可比性，选择了其中的一组著名图像：lena图，如图3和图4中的A图所示。进行尺度为2的小波分解，两幅图像中的尺度为2的低频子图，基本上无法辨认，即所需要的信息基本上都被过滤，所以在第2层匹配是无法匹配的，根据第4节的匹配步骤，只能在第1层子图匹配，匹配实验的结果证明是可行的。

2）将这幅lena的待配图和参考图如表1所示的各种算法进行匹配。通过表1可以看出，此算法是可行的。

5 结束语

论文的创新是首选剖析了NCC算法，选择了算法的中间过渡式作为本算法的一部分，好处是减少图像匹配的计算量，同时也保证了匹配的精确度；采用了小波变换的多尺度特性，优化了匹配的搜索策略，提高了匹配的精确度和匹配的时间，所以结合两者的特点可以很好的完成某些领域中图像的实时匹配。

参考文献：

[1] Gongzalez R C,Woods R E.Digital Image Processing[M].2nd Edition (DIP/2e).北京:电子工业出版社,2005.

[2] 李强,张钹.一种基于图像灰度的快速匹配算法[J].软件学报,2006,17(2):216-222.

[3] Luigi Di Stefan.Stefano Mattoccia Fast template matching using bounded panial correlation[J].Machine Vision and Applications,2003(13):213-221.

[4] Bamea D I,Silverman H F.A class of algorithms for fast digital image registration[J].IEEE Trans on Computers,1972,C-21:179-186.

[5] 郑运平,陈传波.一种新的灰度图像表示算法研究[J].计算机学报,2010,33(12):2398-2406.

[6] 李健,梁琨.基于小波多分辨率分析的快速图像匹配[J].陕西科技大学学报,2006,24(6):81-84.

[7] 刘莹.基于灰度相关的图像匹配算法的改进[J].应用光学,2007,28(5):537-540.

[8] 杜杰.两种基于灰度的快速图像匹配算法[D].大连:大连海事大学,2007.

[9] 范俐捷,王岩飞.一种新的基于灰度的图像匹配方法[J].微计算机信息,2007,23(30):296-297.

篇（9）

1 最小二乘法影像匹配的基础理论与算法

影像匹配实际上就是两幅（或者多幅）影像之间识别同名点，它是计算机视觉及数字摄影测量的核心问题。我们知道要匹配的点的同名像点肯定在其同名核线上。在进行最小二乘影像匹配之前，需要先进行粗匹配。然后在粗匹配的基础上用最小二乘法进行精匹配。我们这次讨论的是利用一维搜索的方法来进行粗匹配。这就是利用同名核线来进行同名像点的粗匹配。这相对于二维匹配来说速度更快。

1.1基于数字影像几何纠正法提取核线，利用共面条件来确定同名核线

我们知道，核线在航空摄影测量上是相互不平行的，它们相交于一点---核点。但是如果将影像上的核线投影（或者称为纠正）到一对“相对水平”-------平行于摄影基线的影像对上后，则核线相互平行。正是由于“水平”的像片具有这么一特性，我们就有可能在“水平”像片上建立规则的格网，它的行就是核线，核线上像元素（坐标为xt、yt）的灰度可由它对应的实际像片的像元素的坐标为x，y的灰度求的 ，即g（xt，yt）=g（x，y）。

根据前边的共线方程，同一摄站点摄取的水平像片与倾斜像片，其水平和倾斜像片的坐标之间的关系为：

(1-1-1)

(1-1-2)

上边的式子中a1,a2…,c3为左片的九个方向余弦，是该像片的外方位角素的函数，f为像片主距。显然在水平像片上，当yt为常数的时候，则为核线,将yt=c代入（1-1-1）和（1-1-2）式经整理，得：

（1-1-3）

其中：

e3=d3

若在“水平”像片上以等间隔获取一系列xt值 ，(k+1)*,(k+2)*…,可以得到一系列的像片坐标（x1，y1），（x2，y2），（x3，y3），…，这些点就位于倾斜像片p的核线上。

同样以yt=c 代入右边的共线方程：

(1-1-4)

(1-1-5)

其中， ， ，… 右方像片的对于单独像对像空间辅助坐标的角方位元素的函数，由此可得右片上的同名核线。

1.2核线的重排列（重新采样）

已知原始的影像的灰度序列，为求待定的平行于基线的“水平”影像。这就需要进行核线的灰度重采样。按照式（1-1-1）和（1-1-2）将“水平”像片上的坐标u，v反算到原始影像上的x，y。但是由于所求得的像点不一定恰好都落在原始影像采样的像元中心，这就必须进行灰度的内插-----重采样。通常所用到的是双线形插值法，取临近的四个像元点的灰度的数值进行待求点的灰度的计算。

图1-2-1双线形重采样

本公式中y1代P点到g1，g4连线的距离，x1代表P点到g3,g2连线的距离的大小

1.3数字影像匹配的基本算法

本论文讲述的相关系数法主要是对于一维影像相关的。

如图1-3-1所示是一维影像相关的目标区和搜索区（这里取m=n）。设g代表目标区内的点组的灰度值，g’代表搜索区内相应点组的灰度值，则每个点组共取得了n个点的灰度值的均值为

图1-3-1一维相关目标和搜索区域

，（i=0，1，2…n） （1-3-1）

两个点组的方差 ， 分别为：

， （1-3-2）

两个点组的协方差 为：

（1-3-3）

则两个点组的相关系数 为：

（0,1,… -n） （1-3-4）

在搜索区内沿核线寻找同名像点，每次移动一个像素，按照（1-3-4）来依次相关系数 ，取其中的最大的数值，其对应的相关窗口的中心像素就被认为是目标点的同名像点。

1.4用相关系数的抛物线拟合来提高相关精度

为了把同名点求的更为准确一些，可以把相关系数的最大点i点左右若干点（一般取左右个两个点）联系起来，从而将其函数的最大值k处的作为寻求的同名点的位置，结果会更好一些。

图1-4-1抛物线拟合

如图1-4-1所示设有相邻像元素系处的5个相关系数，用一个二次抛物线方程式来拟合，取用的抛物线方程，代表相应S位置处灰度的数值。

（1-4-1）

式中的参数A，B，C用间接平差方法求的。此时抛物线顶点k处的位置为：

（1-4-2）

由相关系数抛物线拟合可以使相关精度提高到0.15-0.2个子像素（当信噪比较高的时候），但是相关精度和信噪比近似成反比例关系。当信噪比比较小的时候，采用相关系数抛物线拟合也不能提高相关精度。

2仅考虑相对位移的一维最小二乘影像匹配

2.1一维最小二乘影像匹配原理

在本次仅仅考虑相对位移的一维最小二乘影像相关。在一维影像相关中是在倾斜影像相对应的水平影像坐标系中沿x轴方向寻求同名点，若在最小二乘算法中把搜索区像点移动的位移量作为一个几何参数引入，就可以直接解算像点的位移。

设有两个一维灰度函数 ， ，除了随机噪声 ， 外， 相对于 存在位移量 。如图4-3-1所示，则

（2-1-1）

则（2-1-2）

图 2-1-1 仅考虑相对位移的一维最小二乘影像相关

为了解求相对位移量，需要对（2-1-2）式子进行线性化：

（2-1-3）

对离散的数字影像，灰度函数的导数 可以由差分 代替，即

（2-1-4）

其中 采样间隔。令 ，则误差方程式可以写为；

（2-1-5）

为了解求 ，取一个窗口，对窗口内的每个像元素都可以列出一个误差方程式，按照的原则，则可以求得影像的相对位移的量 ：

（2-1-6）

因为解算都是线性化的结果得到的，因此，解算需要迭代进行。解得 后，对 进行重新采样，各迭代计算时，系数 以及常数项 均采用重新采样后的灰度值进行计算。

2.2计算最佳的匹配点位

我们知道，影像匹配的目的是为了寻求获得同名点。通常以待定的目标点建立一个目标窗口，窗口的中心点就是目标点。但是，在高精度影像相关中，必须考虑目标窗口的中心点是否是最佳的匹配点。根据最小二乘法影像匹配的精度理论可以知道：影像匹配中的精度取决于影像灰度的梯度 ， 。因此，可以用梯度的平方为权，在左方影像窗口中内对坐标做加权平均：

（2-2-1）

以它作为目标点坐标，它的同名点坐标可以由最小二乘法影像匹配所求得的几何变换参数求得；

（2-2-2）

随着以最小二乘法为基础的高精度数字影像匹配算法的发展，为了近一步提高起可靠性与精度，摄影测量工作者进而有提出了各种带有约束条件的最小二乘影像匹配的算法。例如，附带有共线条件的最小二乘相关以及与VLL法相结合的最小二乘影像匹配方法都得到了广泛的应用和研究。

3 最小二乘影像匹配的精度分析

篇（10）

引言

在计算机视觉领域，图像匹配仍然是当前研究的热点问题。基于特征的匹配方法[1]，因为根据图像中趋于稳定的少量特征进行匹配，使得运算速度快、匹配效果好，所以成为目前研究最多、应用最广泛的一种方法。但是，这种方法需要在图像间进行遍历性的匹配运算，存在计算量大，且精度不高的问题。

1999年，Lowe提出了SIFT（Scale Invariant Feature Transform）算法[2]，该算法利用高斯差分在图像的多尺度空间中快速求解高斯拉普拉斯空间中的极值点，加快了特征提取的速度，提取的SIFT特征对于图像平移、缩放、旋转具有不变性，并且对于仿射变换、视觉变化、光照变化有较强的稳定性和很好的匹配鲁棒性，所以被广泛应用于计算机视觉的图像匹配、图像检索和模式识别等方面[3，5]。虽然SIFT 算法具有上述的优点，但该算法首先要将彩色图像灰度化，仅利用图像的灰度信息和特征点的局部邻域信息，忽略了图像的颜色信息，导致不能识别图像内具有相似结构的特征点。

文章提出基于SIFT的多特征相似性度量算法，首先对彩色壁画图像提取SIFT特征点与特征向量，然后对每个特征点提取HSI彩色特征，最后按定义的相似性度量公式计算两个特征点之间的距离，确定二者是否匹配。

1 特征提取

1.1 SIFT特征提取

尺度空间极值点的检测采用DOG方法，将一个像素点与它相邻的26个点相比较，如果是最大值或最小值，就作为图像中的一个特征点。以特征点为中心，在16×16的邻域内，将采样点与特征点的相对方向通过高斯加权后，分别归入8个方向的梯度方向直方图，最后获得4×4×8的128维特征向量来描述一个SIFT特征点。

SIFT算法的两个关键步骤是关键点检测和关键点描述。在关键点检测阶段，大多是利用两种不同的方法，即尺度不变检测和致密采样。文章采用致密采样进行特征检测，理由如下。一方面，尺度不变检测器在描绘均匀信息时是低效的，而壁画图像中包含着这样的信息。另一方面，在特征匹配时，通过致密采样得到的关键点优于随机抽样和尺度不变的探测器[6]。

SIFT算法首先将彩色图像灰度化，提取的特征关注图像的梯度信息，忽视了图像的彩色信息。文章对彩色图像提取特征，实验发现图像的误匹配点中，存在着彩色信息不一致的问题。因此，文章对图像既提取SIFT特征，又提取颜色特征，对多特征融合设计相似性度量方案，可以减少误匹配率，提高匹配效果。

1.2 颜色特征提取

为了解决误匹配中存在的SIFT梯度信息一致，彩色信息不一致的问题，我们在对特征点提取SIFT特征后，再次提取其颜色特征。由于RGB颜色模型只考虑图像的亮度信息，而HSI颜色模型全面考虑图像的亮度和颜色信息，因而在开发基于彩色描述的图像处理算法中，HSI模型更为有用[7]，文章提取HSI彩色特征。

HSI颜色模型中，H表示色调，指的是人的感官对不同颜色的感受，描述纯色的属性；S表示饱和度，描述的是颜色的纯度；I表示强度，描述的是颜色的明亮程度。

常用的最近邻方法原理是，对于基准图像中的每个特征点，在待匹配图像中寻找距离最近的特征点，然后形成一组匹配对。因为最近邻获得的匹配对中存在大量的误匹配，所以Lowe在论文[8]中对于基准图像中的每个特征点，在待匹配图像中寻找距离最近和次近的两个特征点，当这两个距离的比值小于预设的阈值时，才认为找到了一组正确的匹配对，这样消除了大量的误匹配，取得了不错的匹配效果。文章设阈值为thr，且0

3 实验结果及分析

为了观察算法性能，我们从互联网上寻找了两张有重叠部分的壁画图片进行了实验。图像如图1所示。采用Matlab7.7.0编程，运行在AMD A6-3400M CPU 1.4GHZ和4G内存的PC机上，Windows 7.0操作系统。

实验首先寻找图像的SIFT特征点，然后提取特征点的SIFT特征和HSI特征，再对图1a和图1b按公式（9）进行相似性度量，再分别用欧式距离和卡方距离作为相似性度量，并且thr分别选用0.5，0.6，0.7，0.8进行特征对提纯。结果表明，匹配过程在使用同样的阈值时，三种相似性度量方法中，所得到的匹配正确率相同，而匹配时间不同，按公式（9）计算的距离稍快一些。随着thr值的增大，所得匹配对数减少，当thr取值为0.6时，具有较好的匹配结果。图2为thr取值为0.6时的匹配结果。

另外，实验同时表明，对于图像分别提取SIFT特征和HSI特征，如果仅按SIFT特征或HSI特征计算相似性，所得到的匹配正确率都低于两个特征按公式（9）计算相似性的情况。

因此，对图像提取SIFT特征和HSI特征，按我们定义的相似性度量计算方法，确实提高了图像匹配的效率。

4 结束语

文章采用的算法对彩色壁画图像同时提取SIFT特征和HIS彩色特征，有效地去除了梯度信息一致而彩色信息不一致产生的误匹配。通过定义的相似性度量公式，在计算两个特征点之间是否匹配时，速度更快一些。由于SIFT 算法计算量大，算法复杂，提高图像匹配的实时性，将是下一步的研究工作。

参考文献

[1]ZHU Q，WU B，XU Z.Seed point selection method for triangle constrained image matching propagation[J].IEEE Geoscience and Remote Sensing Letters，2006，3（2）：207-211.

[2]LOWE D G.Object recognition from local scale-invariant feature[C]// Proc.the Seventh IEEE International Conference on Computer Vision.Corfu，Greece： IEEE Press，1999：1150-1157.

[3]张书真，宋海龙，向晓燕，等.采用快速SIFT算法实现目标识别[J].计算机系统应用，2010，19（6）：82-85.

[4]王瑞瑞，马建文，陈雪.多传感器影像配准中基于虚拟匹配窗口的SIFT算法[J].武汉大学学报（信息科学版），2011，36（2）：163-166.

[5]钟金琴，檀结庆，李莹莹，等.基于二阶矩的SIFT特征匹配算法[J].计算机应用，2011，31（1）：29-32.

[6]K.Mikolajczyk，C.Schmid. A performance evaluation of local descriptors [J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2005，27（10）：1615-1630.