匹配算法论文大全11篇

绪论：写作既是个人情感的抒发，也是对学术真理的探索，欢迎阅读由发表云整理的11篇匹配算法论文范文，希望它们能为您的写作提供参考和启发。

篇（1）

 

Rete算法是一个快速的模式匹配算法，它通过形成一个Rete网络进行模式匹配，利用基于规则的系统的两个特征，即时间冗余性（Temporalredundancy）和结构相似性（structural similarity），提高系统模式匹配效率。

一、模式匹配的基本概念

1、可满足规则：一个规则称为可满足的，若规则的每一模式均能在当前工作存储器中找到可匹配的事实，且模式之间的同一变量能取得统一的约束值。形式化地说，规则

if P1,P2,…Pmthen A1,A2,…An

称为可满足的，若存在一个通代σ，使得对每一个模式Pi，在工作存储器中有一个元素Wi满足

Piσ=Wii=1,2,3 …m

这里，σ作用在某个模式的结果称为模式实例，σ作用在整个规则的结果称为规则实例。在专家系统中，可满足的规则称为标志规则。

2、冲突集：由全体规则实例构成的集合称为冲突集，也称上程表。免费论文参考网。

3、模式匹配算法的任务是：给定规则库，根据工作存储器的当前状态，通过与规则模式的匹配，把可满足规则送入冲突集，把不可满足的规则从冲突集中删去。

二、Rete算法的依据和基本思想

Rete算法快速匹配的重要依据是：

1、时间冗余性。免费论文参考网。工作存储器中的内容在推理过程中的变化是缓慢的，即在每个执行周期中，增删的事实只占很小的比例，因此，受工作存储器变化而影响的规则也只占很小的比例。由产生式系统的折射性，只要在每个执行周期中记住哪些事实是已经匹配的，需要考虑的就仅仅是修改的事实对匹配过程的影响。

2、结构相似性。许多规则常常包含类似的模式和模式组。

Rete算法的基本思想是：保存过去匹配过程中留下的全部信息，以空间代价来换取产生式系统的执行效率。

三、Rete匹配网络结构与过程

Rete算法的核心是建立Rete匹配网络结构，其由模式网络和连接网络两部分构成。其中，模式网络记录每一模式各域的测试条件，每一测试条件对应于网络的一个域结点，每一模式的所有域结点依次连起来，构成模式网络的一条匹配链。

Rete网络匹配过程由模式网络上的模式匹配和连接网络上的部分匹配构成。在模式网络的机器内部表示中，我们把共享一个父结点的所有结点表示成一条共享链。同时，把每一模式匹配链中的结点表示成一条下拉链，于是，每一结点由共享链和下拉链指向其后继结点，模式网络就是一棵可以使用典型遍历算法进行测试的二叉树。

四、智能防火墙Rete算法设计

Rete快速匹配算法，函数Rete设计为:取IP地址、端口号各部分折叠、异或运算后，以Rete长度取模。免费论文参考网。算法如下(无关或部分无关称为集合A，相关、包含相等和相等的称为集合B):

1、Addr=sa+da sa:源地址 da:目的地址

2、Port=sp+dp sp:源端口号 dp:目的端口号

int Rete(long addr, int port)

{int addrxor,key；\地址折叠异或

addrxor=(addr&～(～0﹤﹤16))∧((addr﹥﹥16)&～(～0﹤﹤16))；

key=addrxor∧port； \与端口异或

return(key % max)； }\max为Rete表长度

防火墙初始化时，首先从规则集A用该散列函数构造Rete表R为

Void Initialization(RULE-SET A){

FOR(r∈A)DO{ \r为每条规则

idx=Rete(r.addr,r.port)；

R[idx]=&r； \R代表规则集合A

}}

因为Rete表的长度有限，但是如果设计太大会浪费存储空间，也降低了查找速度，所以免不了会出现冲突。解决冲突的方法是:如果两条规则经过散列后落到同一位置，则把这两条规则按照插入顺序组成一个链表结构。主要算法如下:

if(R[Rete(r.addr,r.port)]=NULL)\R为Rete表,r为规则

R[Rete(r.addr,r.port)]=&r；\没有冲突，则插入Rete表

Else{J=R[Rete(r.addr,r.port)]；\冲突解决方法

while (j->next!=NULL) {j=j->next；} \插入链表末尾

j->next=&r;}

数据包匹配流程：当防火墙收到一个数据包以后，用算法Match查找规则集(A和B)。

Match(IP-Packet p) { \p为数据包

Int idx=Rete(p.addr,p.port) ； \首先用Rete算法查找A类规则

IF (R[idx].addr≧p.addr&& R[idx].port=p.port) \找到匹配规则

return R[idx] ；

Else {int idex I =halfquery(p.addr) ； \利用折半查找索引表

J=L[indexl] ； \L代表规则集合B

While(j!=NULL){\顺序匹配找到的规则链

IF (Matchrule(p)) return j； \ Matchrule为规则匹配函数

Else j=j->next；

}}

Return(Norulematch)；

}

参考文献：

[1] 闫丽萍，潘正运. RETE算法的改进与实现.微计算机信息，2006 (36）

[2] 庞伟正，金瑞琪，王成武. 一种规则引擎的实现方法.哈尔滨工程大学学报，2005(03)

篇（2）

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

篇（3）

中图分类号：TP391.9 文献标识码：A 文章编号：1009-3044（2014）02-0305-03

伴随网络技术的发展，网络信息大量增加，涵盖期刊、会议纪要、论文、学术成果、学术会议论文的大型网络数据库应运而生，如万方数据库、百度文库、维普数据库等，文献存储容量近百万篇。如何有效搜集发现信息，并对信息提取、组织、处理，就需要寻找出高效算法，降低计算复杂度，提高运算效率，以适应文献资源的迅速扩充[[1]]。

1 文献资料搜索引擎技术特点

当用户以关键词查找信息时，搜索引擎会在数据库中进行搜寻，如果找到与用户要求内容相符的信息，便采用特殊的算法，根据文献中关键词的匹配程度，如出现的次数、频率等计算出各文献的排名等级，然后根据关联度高低，按顺序将这些资源接返回给用户。

与网络搜索引擎不同，因用户需求为数据资料而非网络资源，因此文献检索主要依据为相关关键词、内容的相关度等，对域名、外链等因素考虑较少。可利用关键词匹配算法，计算出各文献特征值，以特征值作为依据，对检索文献排序删选，满足用户需求。为便于理解，该文利用词频和位置加权算法计算特征值，采用快速排序算法进行整理输出，数据库可高效检索出与用户需求匹配程度较高的文献[[2]]。

2 快速排序算法规则及性能分析

快速排序是由托尼·霍尔于1962年（Tony Hoare）所发展的一种递归排序算法，采用分治的思想。在平均状况下，排序 n 个项目需要Ο（n log n）次比较。

其算法规则可表述为：

3 算法设计与仿真

首先建立包含十五篇文献的资料库，根据用户需求，随机输入关键词，在此可将关键词视为子串，对各文献进行字符串匹配操作。文献为A串，即目标串，关键词为B串，即模式串。若A串中存在和B相等的子串（ 若干连续的字符组成的子序列） ，则匹配成功，，否则，称匹配不成功[[3]]。

匹配过程如图2所示，将模式串设置为滑动窗口。在第一次匹配过程中，第三个字符出现不相同情况，此时根据KMP算法原则，利用已经得到的部分匹配的结果，将模式串窗口向后滑动一段距离后，继续进行比较[[4]]。

参考文献：

[1] 张兴华.搜索引擎技术及研究[J].现代情报，2002（2）：142.

[2] 黄知义，周宁.几类搜索引擎的原理剖析、比较研究及发展趋势探讨[J].图书馆学研究，2005（3）：61-62.

[3] 李静.字符串的模式匹配算法[J].青岛化工学院学报，2002（2）：80.

[4] 俞文洋，张连堂，段淑敏.KM P模式匹配算法的研究[J].郑州轻工业学院报，2007（5）：65.

[5] 黄德才，戚华春.PageRank算法研究[J].计算机工程，2006（2）：145-146.

篇（4）

中图分类号：TP309

随着计算机技术的不断发展，需要处理的数据内容不断呈现出大量化的特点。近年来，在计算机研究领域内模式匹配问题受到了极大的关注。在串处理系统中，子串在主串中的定位操作是一种重要的过程中，称之为串的模式匹配。随着计算机网络搜索引擎技术的发展、病毒技术的进步以及数据压缩方面的不断发展，模式匹配算法在计算机应用系统中得到了广泛的应用。目前主要的匹配算法有BF算法、KMP算法与一些改进的算法，从方式上，可以分为精确匹配、模糊匹配、并行匹配等。本文重点对KMP算法进行分析，另外对于改进的KMP算法进行研究与展望。

1 简单的模式匹配算法

现代计算机技术不断发展，人们的工作、生活与互联网有着密切的联系，同时网络内容也不断丰富，每一个终端几乎都有可能会上传与下载数据，造成网络上的类似相信也非常多，如何能够从大量的信息中进行查找同样的信息，则需要经过一定的算法。[1]这种典型的应用系统将会使用到匹配算法。简单的模式匹配算法主要是一种查找过程，给出一个特定的字符串P，在一大型的文本中进行查找，从而确定出P是否在大型文本中出现过，如果存在，同时给出相应的出现位置。在以上的算法定义中，为了对数学模式进行简单描述，进行以下符号定义。模式串为P，需要匹配的大型文本主串为T，模式串的长度为m，需要匹配的大型文本主串长度为n，在模式串中首字符与末字符分别为P1与Pm，而需要匹配的主串文本首字符与末字符分别为T1与Tn。文本字符串T与模式字符串P分别是由字符组成的一种集合，强行搜索模式实质上就是把模式P与文本T进行自左向右的挨个搜索，如果模式字符串P在某一点的匹配失败，则立即将T向右移动一个字符的位置，继续从模式字符串P的第一位向右来搜索。[2]这种算法基本上是最符合原理的，但同时它的工作量十分巨大，体现出的效率并不高，需要进行m（n-m+1）次的字母匹配运算，往往给过程浪费大量的时间。现代社会是高效社会，一旦在网络搜索中速度过慢，用户将会失去耐心。目前更多的手持设备在应用搜索时一般是即时搜索，对时间的要求较高，运算量太大的低效搜索模式已经不再满足现代需求。每个网站的用户数量都在不断增大，形成的用户名与密码都需要进行数据储存，利用模式匹配法可以对账户与密码进行匹配，从而判断是否可以登入，否则就进行拒绝，有效提高时间，保护网站利用与用户隐私。这是模式算法的典型应用，随着算法的不断进步，将会在多个网络领域内得以广泛应用。[3]

2 KMP算法

KMP算法目前已经经过了多年的发展，最早是由克努特、莫里斯与普照拉特同时发现，是一种改进的字符串匹配算法，在这种算法中，对主串指针回溯进行了消除，利用已经得到的部分匹配结果把模式串右行一段较远的距离，再次进行比较与匹配，从而使算法的效率得到大幅地提升。这主要是因为在前期的匹配过程经验总结中，一旦某字符不符合模式串的匹配要求，在附近的一段文本中也将不会出现匹配的对象。[4]

KMP的算法思想是当Ti与Pj匹配完成时，主串的指针i与模式的串指针j将会分别加1，不断向后面进行再次匹配，如果Ti与Pj匹配不成功时，主串的指针i保持不动，模式的串指针j将不会回到第一个位置，而是回到一个合适的位置，一旦j回到了第一个位置，将有可能会对需要匹配的文本字符进行错过。主串的指针i保持不动时，算法的关键就在于模式的串指针j指回到了哪一个位置。模式的串指针j不可右移太大的距离，避免错过有效匹配，同时也要右移尽可能地大，以提高匹配效率。在某次字符匹配时，一旦不匹配，模式的前j-1个字符能够匹配，则在下一次匹配时，可以把模式串向右移动j-s-1个字符位置，从而使P1与Tj-s对齐，需要从P3+1开始进行匹配情况检查。为了避免遗漏问题，在以上的首字串必须是最长的，自匹配的部分字串是唯一的，与模式自身结构有关。当模式的第j个字条与主串里的该字符进行比较位置时，它的值主要是取决于模式本身，与主串无关。这时关键是要选择模式的适当位置。

3 改进的KMP算法

模式匹配的KMP算法有效地避免了BM算法中频繁回溯的问题，极大地提高了模式匹配的效率，但这种算法并不是最优秀的。经过长时间的探索与分析，KMP算法中的扫描部分仍然可以进一步改进。[5]

在改进的KMP算法中，当某一次匹配失败时，i指针不需要进行回溯，而是使用已经匹配到的结果，查看是否对i的调整进行必要性评估，之后再决定与向右滑动的位置模式进行比较。主串指针i的有效变化可以有效提高匹配的效率。在进行第一次匹配结束时，j=6处，无法进行匹配时，i指针将会定为6，j指针为6，当模式串向右移动三个位置时，开始进行第二次的匹配，i的指针为9，而j的指针值为3，也就是说从主串的第九位开始进行比较，i值的不断增加也就加快了模式匹配的进度，提高了工作效率。

4 利用改进算法进行多次模式匹配

与单模式匹配算法相比，多模式匹配算法的优势在于一趟遍历可以对多个模式进行匹配，从而大大提高了匹配效率。对于单模式匹配算法，如果要匹配多个模式，那么有几个模式就需要几趟遍历。当然多模式匹配算法也适用于单模式的情况。在入侵检测系统中，一条入侵特征可能匹配或部分匹配很多条规则，如果采用单模式匹配，在匹配每条规则时都需要重新运行匹配算法，效率很低。然而，日益增多的网络攻击使得入侵检测的规则数目仍在不断增长。

在实际的应用中，模式串与主串一般需要多次的匹配，才能找到主串中是否有多次存在相同的子串，如在数据库中进行查找。[6]通过多次模式的匹配可以实现多个子串在文本中的位置，同时可以进行标记，有利于现代计算机庞大数据量的数理与分析。我国人口众多，网民数量庞大，姓名与用户名很可能会出现重复的情况，所以需要提前在数据库中进行查找，以确定是否可用，另外对匹配但其他特性不符的对象进行排除。

5 结束语

随着现代计算机技术的不断发展，越来越多的新技术得以应用与改进。网络安全发展形势也要求提高网络入侵检测系统的性能。模式匹配的效率问题引起了足够的重视。通过对传统的KMP模式匹配算法与其发展状况进行分析，明确未来发展思路，为其实践应用奠定理论基础。

参考文献：

[1]李桂玲.一种改进的KMP模式匹配算法[J].吉林工程技术师范学院学报，2009（10）：75-77.

[2]杨战海.KMP模式匹配算法的研究分析[J].计算机与数字工程，2010（05）：38-41.

[3]陈冬文，张帆，王斌，周启海.模式匹配算法――KMP算法的改进[A].2008中国信息技术与应用学术论坛论文集（一）[C].成都：西南财经大学信息技术应用研究所，2008.

[4]明廷堂.BF与KMP模式匹配算法的实现与应用[J].电脑编程技巧与维护，2013（23）：24-28+34.

[5]范洪博.快速精确字符串匹配算法研究[D].哈尔滨：哈尔滨工程大学，2011.

篇（5）

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

篇（6）

引言

建立城市交通综合信息平台，通过对庞大的城市交通网络中的实时交通信息进行深入分析，为改善城市交通信息服务水平，提高决策科学性，缓解城市交通拥堵提供了基础。交通综合信息平台的数据支撑来源于交通基础信息的实时采集，科学决策的依据在于数据分析的快速、准确。

GPS浮动车是获取道路实时车速便捷有效的方法，可以通过车载GPS定位信息获取道路实时车速及运行状态（拥堵、畅通、缓行），其作为一种便捷廉价、可操作性高的车速采集手段已经被各城市普遍采用，特别是公交车与出租车安装车载GPS设备最为常见。通过对公交车及出租车的GPS返回数据与城市道路网的匹配、分析来获取道路的实时车速，进而实现对道路状态的有效判断。因此确保GPS浮动车轨迹点数据与信息平台电子地图快速、准确匹配是管理决策的基础，研究准确适用的GPS浮动车轨迹点数据的地图匹配算法是非常重要的。

1 GPS数据的地图匹配原理

地图匹配（Map-Match）简称MM技术，就是利用电子地图的路网信息和GPS数据来实行对车辆行驶准确位置的确定，它是一种定位误差修正技术。

浮动车所上报的GPS数据中包含有经纬度等地理信息，但这些GPS坐标只能反映车辆位置情况，而不能与实际路网路段直接相关联。因此，车辆在路网中行驶的情况，必须要依赖于地图匹配算法来完成车辆位置信息与路网位置的关联。

地图匹配算法的直接目的是将GPS测得的车辆位置或行驶轨迹，与现有的电子地图道路路段数据进行比较，继而找到车辆所处的道路，计算出浮动车辆在道路上所处的位置。一般地图匹配过程有以下几个步骤：

（1）通过对获取的GPS数据的预处理及匹配模板的分析、描述，提取出点和道路的轨迹特征。

（2）根据对地图匹配规则的制定，计算出GPS样本和匹配模板两者的相似度、匹配度。

（3）选取待匹配点距离最近或者是轨迹相似度、匹配度最高的道路曲线模板，可更正匹配样本的位置或轨迹，作为匹配结果[1]。

图1 地图匹配原理图

地图匹配原理一般可分成两个过程来表达：即寻找GPS待匹配点最可能归属的道路，并将GPS浮动点投影到这条它所归属的道路上面。

以上两个过程的关键在于需找GPS待匹配点最可能归属的道路，基本的思想即是在GPS点四周一定范围内搜索所有的可匹配点，然后根据匹配度计算，淘汰匹配度较低的点，选出最优点。并将此最优点作为GPS浮动车车辆的当前行驶路线。这样，寻找最优点成为算法性能优劣的关键所在，如果搜索范围过大，需对周围各条道路一一筛选，增加了算法计算量，导致匹配速度缓慢。反之，如果搜索范围过小，则有可能未能准确寻找到最佳匹配点，出现匹配错误，降低匹配的准确率。

2 基于GPS轨迹点的浮动车地图匹配算法

可实现地图匹配的算法很多，在GPS数据量极大，且算法应用的场景为实时车速展示，需要选择一个合适的方法，保证匹配的准确性和匹配速度。因此文章提出的地图匹配算法是基于GPS点到校正点的匹配，并且利用连续几个GPS点的轨迹确定结果，最终获取较为正确的路网匹配结果。

2.1 网格匹配

Step1：计算GPS点所归属网格。

当在系统中导入GPS数据信息后，可从这些原始数据中提取出坐标信息。可设为（x，y）。然后对该GPS坐标信息进行可信度检测，首先取网格划分中最大和最小的两个坐标点，其中最大的坐标点位于地图的右上角，假设为（xm，ym），最小的坐标点则位于地图的左下角，假设为（xn，yn）。如果待匹配点坐标（x，y）满足以下条件：

则认为该GPS点在研究坐标范围之内，转到下一步计算。

Step2：搜寻所在网格匹配

根据该GPS点的坐标信息，在网格列表中搜寻其所属的网格。假设网格编号为G0，若

（x，y）∈{G0}

则判定该点位于G0网格内。

在搜寻到所在网格后，将所在网格G0中的所有校正点加入到待匹配集合。但在该匹配中需要注意的是当GPS点与网格边距离小于1/3时，则需要将其相邻网格（G1……G8）所包含的校正点一并加入待匹配集合，进行匹配度计算。（见图2）

2.2 节点匹配

Step1：计算GPS与路段的距离和方向差

在网格匹配中搜寻出的校正点集合被称为待匹配集合。需要将GPS点与带匹配集合中的各个校正点进行匹配，找寻出最佳匹配点。

计算GPS点与各待匹配校正点之间的距离。设GPS点坐标为（x，y），GIS校正点坐标为（xr，yr），由于两点距离较近，两点接近于平面，则可根据平面距离公式

得出GPS点与各校正点之间的距离d。

计算GPS点与路段各校正点之间的夹角。取GPS数据的角度为？渍0，再与网格内的GIS路段校正点的切线方向角度？渍r（取正北方向为0°）求差值。可得出GPS点与路段方向的夹角α。

Step2：匹配度计算

匹配度是判断校正点优劣的重要标准，是描述GPS点与一条道路的匹配程度，用实际算法所求得的数值进行量化，匹配度越大，就认为发出这个GPS数据的浮动车越有可能位于这条道路。对于匹配度的计算，主要考虑的是GPS与路段的距离及其与路段的夹角。

图3 GPS点匹配

Step3：Confidence Point（CP点）判断

针对GPS浮动车地图匹配的特殊性，本文提出了Confidence Point判断。所谓Confidence Point，就是可信点[8]。判断是否为CP点，主要判断其所有匹配点是否位于同一路段。

由于浮动车地图匹配的最终目的是为城市各条道路得到路段平均速度提供起点、终点以及时间信息，而当车辆距离路口（包括城市立交路口、普通平面交叉路口、主辅路的出入口等）比较近时，由于GPS浮动车减速、并线等驾驶行为导致GPS数据中的方向信息等变化较大、准确性降低，使得系统比较难以确定车辆的准确位置。 但是考虑到GPS浮动车地图匹配的一个最终目的是获取路况实时信息，因此，如果无论车辆当前在哪条道路上行驶，只要能确定车辆必定通过或者必定离开某个路口，就可以根据GPS浮动车辆的下一个GPS定位数据确定其这一段时间的行驶轨迹。

因此当GPS数据处于路口节点或分合流点附近时，它所对应的匹配点并不在同一路段上，系统将这样的数据判定为非CP点，作为延迟匹配点，利用行驶路径进行匹配。反之，若GPS数据所对应的匹配点位于同一路段，则系统将其判定为CP可信点，对其各匹配点进行匹配度计算。

其中对于CP可信点，系统按照step3中匹配度计算中所确定的方法进行匹配度计算。取匹配度最大的点为最佳匹配点。对于非CP点，则转入下一步。

Step4：延迟匹配

对于上一步所提到的非CP点，并无法通过单一的GPS数据匹配来确定浮动车的确切位置，这时就需要通过相同浮动车的多个GPS数据来联合判断车辆的行驶路线轨迹。

图5 非CP点延迟匹配示意图

假设某浮动车连续的n个GPS数据组成的序列Pn（n=1，2，3，……，k），满足以下条件：

（1）P1点为CP点，P2为非CP点，且k小于延迟匹配的允许最大值；（2）Pk为已经确定的CP点，并能按照地图匹配方法正确寻找到最佳匹配点。

则可利用前后两个CP点P1和Pk，寻找这相邻两个CP点的最短路径L。再利用最短路径L对P2，P3，Pn-1进行匹配，去掉不属于L的匹配点，再取最大匹配度点作为最佳匹配点。

3 结束语

文章所使用的地图匹配方法通过获取GPS浮动车数据，利用GPS坐标信息，通过比对电子地图各条路段的地理信息，将浮动车位置关联到路网上。

研究表明，该匹配算法具有以下优缺点：

（1）匹配速度快。由于将电子地图网格化，避免了将GPS数据坐标与地图中所有节点坐标的一一进行计算，而是仅选取了比较小范围的节点进行匹配。提高了运算、匹配的效率。

（2）匹配精度较高。由于在匹配方法上采取了多种方法进行联合使用，针对不同位置的GPS数据点运用不同的匹配方法，保证了每个GPS数据点匹配的准确性。特别是基于连续GPS点轨迹来判断位置，使得匹配的结果更为准确。

重庆市政府在2011年开展“重庆市交通综合信息平台”建设，信息平台对重庆城区的干路网交通信息进行采集与汇聚。文章的研究依托交通信息平台的基础数据，研究成果应用于重庆市主城区路网运行情况的评估与监控，经过实测对比，验证了该算法的良好精度和适用性。

参考文献

[1]张其善，吴金培，杨康凯.智能车辆定位导航系统及应用[M].北京：科学出版社，2002.

[2]肖锋.面向道路交通状态监测的GPS与GIS数据预处理关键技术研究[D].重庆大学硕士毕业论文，2008.

[3]重庆市交通综合信息平台试点工程技术报告[R].2012.

[4]孙棣华，等.基于预处理的城市路网拓扑结构构建算法[J].计算机工程与应用，2008（08）.

[5]车莉娜.车辆导航定位中的关键技术研究[D].辽宁工程技术大学硕士论文，2008.

[6]Weiliang ZENG， Zhaocheng HE and Xiwei SHE. Data Repair Method for Real Time Urban Link Speed Estimation，ASCE2011.

[7]王华.GIS城市道路最短路径算法研究[J].测绘科学，2010.

篇（7）

【关键词】 颈动脉;斑点跟踪;金字塔算法;运动分析;平均绝对差函数

Abstract：The motion information in the carotid ultrasound image can reflect the condition of carotid whether it has hardened， expanded and contracted in the right way. Then it can help doctor to diagnose cardio cerebral vascular diseases together with the carotid intima-medial thickness(CIMT).We used the modified block sum pyramid (MBSP) algorithm to analyze the motion of carotid ultrasound images. The result shows that the modified algorithm effectively reduced the computation while speckle tracking. Besides that， the MBSP algorithm has the same accuracy with the block sum pyramid. The tracking result can assist the doctor to evaluate the disk of cardio cerebral vascular diseases to a certain degree.

Key words：Carotid; Speckle tracking; Block sum pyramid; Motion analysis; Mean absolute difference

1 引 言

心脑血管疾病与颈动脉内中膜厚度及其运动特征等有着密切的相关性[1]。对于超声波图像而言，可以通过斑点跟踪的方法获得运动信息。斑点作为噪声不可避免地存在于超声波图像中。虽然斑点噪声影响超声波图像质量，但是根据斑点噪声的形成原理，可以通过跟踪斑点来获取图像中相关目标的运动信息。为研究组织的运动特征和弹性信息，进而辅助评估心脑血管疾病提供了一种可能。斑点跟踪算法一般包括两个方面：匹配和搜索。匹配的准则有许多种，常用的准则有归一化相关函数(NCCF)，平均均方误差函数(MSD)以及平均绝对差函数(MAD)等。因MAD不涉及乘法等复杂运算，所以较为常用，本研究也采用该匹配准则。搜索方法也有好多种，有全搜索法[2]，十字搜索法[3]，菱形搜索法[4]等。此外，在这些算法基础上发展出了许多快速算法，如金字塔算法[5]，连续淘汰法[6]，改进的自适应2BIT变换法[7]等。临床实践中医生除了用肉眼定性地去观察颈动脉的运动特征，有时需要定量测量出感兴趣的颈动脉某一目标的运动信息(如：短轴切面轮廓在一个心动周期内收缩和扩张的运动状况)。这样就能够更加可靠地评估心脑血管疾病和风险。由于辅助诊断对运动跟踪的实时性要求不是很高，而对运动跟踪的准确性要求较高。故我们选择能达到全局最优的全搜索法和金字塔快速匹配算法的组合进行斑点运动跟踪，并且对金字塔快速匹配算法进行了改进，将其应用于颈动脉运动分析，高效准确地跟踪出目标兴趣点运动的相关信息。

2 原理与方法

2.1 金字塔块匹配算法

设有块X和Y，块大小均为：2M×2M，对块X和Y均建立 M+1层的金字塔。从塔顶往下依次为第0，1，…，M层。X，Y的金字塔的第m 层分别记为Xm，Ym。第m-1层和第m层关系如方程(1)所示：

Xm-1(i，j)=Xm(2i-1，2j-1)+

Xm(2i-1，2j)+Xm(2i，2j-1)+Xm(2i，2j)(1)

令：MADm(X，Y)=∑2mi=1∑2mj=1|Xm(i，j)-Ym(i，j)|(2)

可以得出结论(3)：

MAD0(X，Y)≤MAD1(X，Y)≤MAD2(X，Y)…≤MADm(X，Y)…≤MADm(X，Y)(3)

两个块在生成了各自的金字塔之后，从顶层往下逐层计算MADm(X，Y)。如果发现其大于或者等于最新的MADmin时，说明本候选块一定不是最优块，舍弃该候选块继续搜索下一个候选块，如果比较到最底层，仍然比最新的MADmin还小时，将MADmin更新为当前候选块与参考块的MADm(X，Y)。直到所有的候选块均搜索完后，最小的MADmin的候选块相对于参考块的偏移量即为所要求解的运动向量。 金字塔匹配算法就是通过尽快地舍弃那些不是最优的候选块而减少运算量的。虽然建立金字塔会增加额外的计算量，但是由于大部分的块在比较时就被舍弃了，所以总的运算量还是大幅地减少。

2.2 改进的金字塔匹配算法

金字塔块匹配算法从顶层开始往下逐层比较时，层与层间的MAD值相差很大。当层数较大时，最后一层与倒数第二层的MAD值相差更大，因此，比较时仍有不少的计算冗余。为此，希望在现在的金字塔基础上不改变运算量，在层与层之间新增一些阈值，能够尽早地舍弃那些不是最优的块。为了叙述方便，以下讨论均以在最后一层(第M层)与倒数第二层(第M-1层)之间增加阈值为例。

两个要比较的块分别记为X，Y，块X和Y的金字塔的第M-1层分别记为：XM-1，YM-1。设SM-1为第M-1层塔的所有像素点空间。将XM-1，YM-1按照相同的方式均分割为N个区域：S1M-1，S2M-1，S3M-1，SkM-1，…，SNM-1，1≤k≤N，见图1。具体的分割方法还需要根据实际情况进行合理的选择。分割出的N个区域要满足以下两个约束关系：

∑Nk=1SM-1k=SM-1(4)

SM-1k∩SM-1l=，1≤k≠l≤N(5)

图1 像素空间分割方法

Fig 1 Pixels partition method

图2 实验所采取的分割方法

Fig 2 Experiment′s method

同时对块X，Y的金字塔的第M层也划分为N个区域SM1，SM2，SM3，SMk，…，SMN，1≤k≤N。也要满足约束关系：

∑Nk=1SMk=SM和SMk∩SMl=，1≤k≠l≤N。

SM-1k区域中的每一个点对应于SMk区域中的4个点，此对应关系和构建金字塔时从M层到M-1层的4个点累加成1个点的对应关系一致。

构造如下函数表达式：(0≤n≤N)

MADM-1n(X，Y)=MADM-1(X，Y)-∑nk=1∑(i，j)∈SM-1k

|XM-1(i，j)YM-1(i，j)|+∑nk=1∑(i，j)∈SMk |XM(i，j)YM(i，j)|(6)

根据层间区域关系式(1)，上式又可以写成(7)式：

MADM-1n(X，Y)=MADM-1(X，Y)-f(n)(7)

其中f(n)可写成(8)式:

f(n)=∑nk=1∑(i，j)∈SM-1k|XM-1(i，j)YM-1(i，j)|-

[|XM(2i-1，2j-1)YM(2i-1，2j-1)|+

|XM(2i-1，2j)YM(2i-1，2j)|+

|XM(2i，2j-1)YM(2i，2j-1)|+

|XM(2i，2j)YM(2i，2j)|](8)

又据三角不等式及上下层点的对应关系知：

f(n)≤0，且f(n)随着n的增大单调递减，据此得出(9)、(10)、(11)的3个结论：

MADM-1(X，Y)=MADM-10(X，Y)(9)

MADM-1N(X，Y)=MADM(X，Y)(10)

MADM-10(X，Y)≤MADM-11(X，Y)

≤…MADM-1n(X，Y)≤…MADM-1N(X，Y)(11)

如果将SM-1像素空间一列一列依次从左往右分割时，所得到的有关结论则和文献[8]是一致的。文献[8]中所提到的逐行更新算法可看作是本研究改进算法的特例。现将改进的金字塔匹配算法(以在两帧中跟踪一个兴趣点为例)归纳如下：

记前后两帧图像分别为fi(x，y)，fi+1(x，y)，被跟踪点坐标为(a，b)，前一帧图像点(a，b)所对应的块称为参考块，搜索范围为A。

(1)计算相对于参考块运动位移为(0，0)的候选块与参考块两者的MAD值作为MADmin，并且确定后一帧图像中的起始候选块。MAD计算公式如(12)式所示：

MADmin=∑2M-1-1x=-2M-1 ∑2M-1-1y=-2M-1|fi(a+x，b+y)

-fi+1(a+x，b+y)|(12)

(2)依据金字塔算法构建当前候选块和参考块各自的金字塔。金字塔总共假设有M+1层。沿金字塔至上而下逐层进行比较，因为这里只考虑在M-1层和M层间新增阈值，所以前M-1层的比较和原金字塔块匹配算法一样。当M-1层比较完后，发现MADM-1(X，Y)仍然小于最新的MADmin。此时则需要按照构造函数表达式生成一个新的中间阈值，再进行比较，其间发现新生成的阈值大于或者等于MADmin时，舍弃，直接进入步骤(3)进行下一个候选块的匹配。否则一直进行到最后一层为止。如果其结果仍然小于MADmin时，更新MADmin。

(3)按照选取的搜索算法(如全搜索法)，确认下一点被候选点及相应的候选块。重复步骤(2)，直到A所有需要搜索的点搜索完为止。

(4)最后，对应于MADmin值最小的候选块即为最优候选块，其相对于参考块的偏移量，即为所要跟踪的运动矢量。

2.3 利用MBSP算法分析颈动脉图像

(1)取颈动脉短轴切面一个心动周期的图像序列。在第一帧图像中，沿颈动脉短轴轮廓，手动大致均匀地选取出若干个兴趣点，兴趣点应尽量选取在整个运动序列图像中亮度较为平稳且肉眼观察较为明显的斑点噪声颗粒。

(2)利用改进的金字塔跟踪算法(MBSP)逐帧地跟踪所有兴趣点，得到各个兴趣点在各帧中的运动矢量，再将各帧上各点的运动矢量按照适合人眼观看的比例显示在各帧图像上。最后以动态的方式播放附有运动矢量的颈动脉图像序列，医生可以根据播放视频中的运动矢量定性地掌握兴趣点运动大小、方向、扭转、是否出现异常等情况，做出一些如是否可能出现斑块硬化等初步诊断。

(3)最后给出各个兴趣点的收缩扩张曲线，每条曲线给出每个点随时间的运动速度变化。设第j帧图像中跟踪到的N个点的分别为坐标(X1，Y1)，…，(Xi，Yi)，…，(XN，YN)。其均值为(X，Y)。记Vi=(Xi，Yi)-(X，Y)，1

3 实验与结果

3.1 实验结果

实验数据由合肥105医院超声科提供，为一个心动周期的颈动脉短轴切片序列图像，共25帧。第1、11、22帧图像分别见图3、4、5。图3中小白框即为我们要跟踪的6个兴趣点，左上角为1号点，按顺时针依次排列。为了表述方便，这里只选取了6个兴趣点为例。

分别用BSP和MBSP算法对该颈动脉序列图像进行斑点运动跟踪，其中MBSP算法在第3层和第4层增加了3个新的阈值。将第3层的像素空间从左到右依次分割成4个相同的区域，见图2。实验中块大小取为16×16，搜索范围为8×8。图4附上了第11帧图像上各兴趣点的运动矢量图，两个算法跟踪出来的结果一样。图6给出了各个兴趣点(从左往右，从上至下依次为1到6)随时间变化的扩张收缩运动速度图。从图中我们可以看出，兴趣点2、3、4的运动表现出较为一致的运动规律，在一个心动周期内经历一个明显的扩张和之后的收缩过程。但是观察兴趣点1、5、6的运动速度曲线，发现其运动起伏相对来说没有这些规律，从而可以认为1、5、6附近区域可能出现一些病变。这和医生的诊断结果：本试验者颈动脉左下部区域内膜形成了较为明显的斑块，而斑块区域收缩运动常出现紊乱是相互吻合的。

3.2 性能分析

(1)准确性。分析改进后的算法和改进前的金字塔匹配算法(BSP)，容易得出前后算法运动跟踪结果应该是一致的，差异只在于计算量上。实际跟踪的结果也证明了这一点。图7、8给出了前后两种算法的跟踪兴趣点1的运动轨迹图，图中横轴、纵轴分别对应于图像的X轴和Y轴坐标轴。

(2)效率。表1给出了改进前后算法在上述实验过程中需要计算的各MAD值统计次数。计算第m层的MADm值所需要运算量(含加减法及绝对值)可以公式化[9]为：3.22m-1，计算MADmn运算量约为：5n·(3·22m+2-1)/16。以第4层为例，如果直接采用表1 金字塔算法改进前后各MAD次数

原来的金字塔算法，需要计算总次数为821 457;但采用改进后的算法需要的计算量仅为721 747。可见因为第3层与第4层3个新增阈值的引入，第4层判决过程的总体运算就减少12.11%，可以考虑将区域进行更细划分，但是要权衡因为阈值增加而造成的比较运算量。如果在第3层等层也引入同样机制的话，运算量将进一步减少。

4 总结

本研究将改进后的金字塔匹配算法应用于斑点运动跟踪，实验结果表明该算法能准确而更加有效地跟踪出运动矢量。并且将该方法应用于颈动脉运动分析，结合颈动脉的自身特点，给出有利于辅助医生诊断的扩张与收缩曲线等依据，为颈动脉的进一步分析奠定了一定基础。

参考文献

[1]胡玮，张军，孔国喜，等. 超声检测颈内动脉内-中膜厚度及其形态结构与相关心脑血管疾病的关系[J]. 第四军医大学学报 ，2007，28(15):1431-1433.

[2]Brünig M， Niehsen W. Fast full-search block matching[J]. IEEE Trans Circuits Syst Video Technol，2001，11(2): 241-247.

[3]Ghanbari M. The cross-search algorithm for motion estimation[J]. IEEE Trans Commun，1990， 38(7): 950-953.

[4]Zhu S，Ma K-K.A new diamond search algorithm for fast block-matching motion estimation[J].IEEE Trans Image Processing，2000，9(2):287-290.

[5]Lee C H， Chen L H. A fast motion estimation algorithm based on the block sum pyramid [J]. IEEE Trans Image Processing， 1997，6(11):1587-1591.

[6]Li W， Salari E. Successive elimination algorithm for motion estimation [J]. IEEE Trans Image processing， 1995，4(1): 105-107.

篇（8）

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 最小二乘影像匹配的精度分析

篇（9）

一、引言

指纹自动识别技术是通过计算机实现的身份识别手段，也是当今应用最为广泛的生物特征识别技术之一。采用指纹识别技术进行身份验证是安全可靠的系统，它可以取代传统的基于密码、钥匙和证件的安全系统，而且不需记忆密码，无需携带证件，指纹就是身份证明。无数的研究单位和公司企业都积极从事自动指纹识别算法的研究和产品开发，现在国内外指纹识别大都采用基于细节特征点的指纹识别技术，即采用基于图像处理的指纹识别算法，但有些算法由于指纹图像的噪音、皮肤弹性引起的非线性形变等多方面因素，导致在识别过程中出现误差，影响识别率等。

二、研究现状

在国内，中国科学院自动化研究所人工智能实验室在指纹识别技术研究方面取得了大量成果，它们的产品“Finger pass嵌入式指纹识别系统”获国家信息产业部信息产业重人技术发明荣誉证书，“基于混合匹配的指纹识别系统与应用”曾获得国家科技进步二等奖，并在国内外重要学术刊物上发表多篇关于指纹的科研论文。

国外自动指纹识别技术的研究开发起步比国内早，到目前为止也已经取得了很多优秀成果，它们的技术和产品整体上都领先于国内。比较有代表性的“指纹研究组织”是南加利福利亚洲指纹联合会，它是一个非盈利组织，成立于1937年，目前拥有超过350个成员单位，该组织旨在推动指纹识别技术及其相应产品的研究、交流等。由国际模式识别协会组织的国际指纹识别算法竞赛“FVC2000”、“FVC2002”、“FVC2004”吸引了众多国际国内的高校、研究组织、企业等参加，这些竞赛都非常具有影响力，推动了指纹识别技术的研究和应用发展。

三、指纹预处理

在指纹识别过程中，输入的指纹图像由于各种原因的影响，是一幅含噪声较多的灰度图像，预处理的目的就是去除图像中的噪声，使图像画面清晰，边缘明显，把它变成一幅清晰的点线图，以便于提取正确的指纹特征。指纹图像预处理环节在整个指纹识别系统中具有重要的地位和作用，它的好坏直接影响着指纹识别的效果。预处理一般分为四步进行：指纹图像的规格化、指纹增强、二值化和细化。

四、指纹图像的特征

指纹图像的结构比较复杂，而且属于个人隐私，所以在一般情况下，指纹图像是用数字化的形式存储的，然而数字化存储信息量大，很难找到准确的指纹信息，因此指纹识别具有重大的意义。指纹识别算法是根据指纹图像中一些不同的特征来实现指纹的匹配，根据不同特征可以将指纹图像分为：总体特征和局部特征。

总体特征：指纹图像中存在一些清晰明了的特征，可以用肉眼直接观察到，将这一类特征称为总体特征，例如：纹型，模型区，核心点，三角点，纹数。

局部特征：指纹图像上节点的特征，而节点是指纹图像中具有某种特征的点，又称为特征点。一般来说，有些指纹会存在相同的总体特征，但绝对找不到相同的局部特征，即相同的特征点。所以在指纹识别过程中就是要寻找这些特征点，这些特征点往往出现在中断处、分叉处及转折处。

五、指纹特征匹配

人们对指纹匹配做了很多研究，提出了许多匹配算法，主要可分为两类：一类是基于图形的匹配方式，包括点模式匹配和基于图论的方法；另一类是采用人工神经网络的方法。图形匹配是针对纹线几何形状及其特征点拓扑结构的匹配方式，它的原理是基于相似变换的方法把两个特征点集中的相对应点匹配起来，这些相似变换可以是平移变换、旋转变换、伸缩变换等线性变换，可以在一定程度内允许少量伪特征点的存在、真正特征点的丢失以及轻微的特征点定位偏差，且对图像的平移和旋转也不敏感。但这种方法有两点不足：一是匹配速度比较慢；二是对指纹图像的质量要求比较高，低质量的图像匹配效果不佳。本文采用概率神经网络识别的模型进行网络拓扑。在情报不完全的情况下，对未知部分进行主观概率估计，然后用贝叶斯公式对其进行修正，最后结合期望值和修正概率做出最优决策。

六、小结

本文通过介绍混合神经网络相关知识，分析了自动指纹识别系统的研究现状和问题，按照指纹预处理、指纹特征提取和指纹特征匹配的研究过程，在现有的各种指纹处理算法的基础上，对它们进行了优化改进，研究了混合神经网络在自动指纹识别系统中的应用。

参考文献：

[1] 张莹，于宝。基于ARM9的指纹匹配算法[J]。计算机与数字工程，2013，5。

[2] 李娟。基于特征描述子的指纹算法研究[D]，西安电子科技大学，2012.

[3] 王启亮。指纹图像增强算法研究[D]， 太原科技大学，2013.

[4] 王行甫，覃启贤，程用远，侯成龙。一种改进的径向基神经网络预测算法[J]。计算机系统应用，2012，8。

[5]殷芳玺。嵌入式指纹识别应用系统与算法研究[D]， 华中科技大学，2012.

[6]车永刚，肖春雨，雷声，孙巍。基于环形BP神经网络的指纹匹配算法[J]。长江大学学报，2013，10（1）。

篇（10）

中图分类号：TP391.41文献标识码：A文章编号：1007-9599 (2011) 16-0000-01

Comparative Study of Ddigital Image Copy Paste Tamper Forensics Technology

Han Min,Sun Jinguo

(Chinese People's Public Security University,Beijing102623,China)

Abstract:This article describes several algorithms aiming at a common copy-paste forgery in the research field of digital image forensics,compared?the performance of?various methods.Different of kinds of tamper detection methods have been analyzed and discussed.It also prospects the future of copy-paste forgery in the research field of digital image forensics.

Keywords:Digital image forensics;Image area copy paste tamper

一、引言

近年来随着电子技术的发展传统的“胶卷相机”已经几乎被数码相机所代替，这为人们省去了很多传统相机使用上的不变，但伴随着数字图像处理软件的发展，数字图像的非法篡改给人们的生活以及社会带来很多负面的影响，数字媒体的信息安全无法得到保障。复制粘贴篡改是一种常见的篡改手法，它利用同幅图片内各种统计参数比较相近，从一个区域复制一个图块粘贴到另一区域上，以达到掩盖图像真实内容的目的。

二、数字图像被动取证技术

数字图像被动取证技术，要求只给出待检测图像就可以鉴别真伪，即在不依赖任何预签名提取或预嵌入信息的前提下，对图像内容的真伪和来源进行鉴别和取证的技术，因此这类取证技术也叫数字图像盲取证技术。

数字图像被动取证技术实现的可行性基于这样一个事实：任何来源的数字图像都有自身的统计特征，而任何对数字图像的篡改都会不可避免地引起图像统计特征上的变化。因此，可以通过检测图像统计特征的变化，来判断图像的原始性、真实性和完整性。

三、取证算法

目前的取证算法大体上可以分为两类，即基于单个像素的穷举搜索和基于图像块的检测方法。块匹配算法共同的特点就是对输入的图像数据进行分块处理。得到这些块之后，从这些块中提取相应的特征值构成特征向量，不同的基于块匹配的算法的实质区别就在于选取的特征值各不相同。下面就各种方法进行比较：

（一）穷举搜索。基于单个像素点的穷举法原理很简单，但计算复杂度很高，将之应用于大幅图像的篡改检测显然是不可行的，与此同时，此算法也不能够抵抗外来的一些干扰操作，如加噪、模糊等。算法本身受条件的约束性较强。一般我们只用于对较小尺寸的篡改图像的检测。

（二）简单块匹配。最基本的块匹配检测算法是将得到的b2大小的块展开，每个方形块按行优先顺序被展为一行，存入一个矩阵中，这样所有的行向量组成了一个二维矩阵X，其中列数为b2，行数为（Mb+1）（Nb+1）。为了减少算法的计算量，按照字典排序的方法对X阵中的行进行排列。最后根据判断是否存在等同的行向量来确定篡改结果。这种算法在图像遭到了复制粘贴篡改后没用进行其他篡改的情况下显示出了良好的性能，但是当篡改图像经过如压缩等后续操作时，检测的正确率明显降低，这是由于块与块之间不再是精确的相似，检测效果大打折扣。

Fridrich等人对此进行了改进，先对图像进行块离散余弦变换（BDCT）变换，采取经过量化后各块的BDCT系数进行对比分析。由于是在DCT域上做分析，算法具有一定的鲁棒性。但是当处理的图像比较大时，由于计算量太大，往往需要很长的时间来实现篡改定位，这个时间很可能无法令人接受。

骆伟祺等人提出了一种鲁棒的检测算法，这种算法也是基于图像块匹配的。假定问题图像为彩色图像（大小为MxN），首先对其进行分块处理，分块的方式同前面一样，在得到了（M-b+1）x（N-b+1）个图像块之后，对每个图像块提取可以代表其内容的七个特征值，并以向量的形式来表示，前三个分量a1、a2、a3分别是b2大小的彩色图像块RGB通道的均值。若为灰度图，只需记录像素点的灰度值即可，a4、a5、a6、a7则是由图像块内各像素点的亮度分量Y组成的阵列经过四种分解方式整合处理后得到的特征。此算法具有一定的鲁棒性能，能够抵抗一定程度的后处理操作，如模糊、压缩等。但如果被复制的区域发生了形变，则容易造成误判，甚至失效。

（三）基于不变矩的检测算法。不变矩方法是一种经典的特征提取方法，目前已经广泛应用于图像分析与模式识别领域中。Hu提出的7个矩不变量，不但具有平移不变性，而且还具有旋转不变性，适合用于表示图像的特征。但Hu矩的方法对模糊和加噪操作没有明显效果。

Zernike矩是一组正交矩，也具有旋转不变性，即旋转目标并不改变其模值。由于Zernike矩能构造出任意高阶矩，而高阶矩包含更多的图像信息，所以Zernike矩的识别效果优于其他方法。何坤等人提出了一种方法，将尺寸较大的篡改图像运用小波变换得到低频子图像，再把低频子图像分割为图像子块，对其子块序列图像分别进行Zernike矩分析判断是否存在复制篡改，该方法克服了噪声和几何变换对取证的影响。

（四）基于SVD的检测算法。奇异值分解（SVD），是一种图像特征分析方法。它的目的在于消除图像数据各分量间相关性，是基于信号二阶统计特性的一种方法。国防科技大学吴琼等人提出了一种基于SVD的图像复制区域检测算法。利用奇异值分解变换来处理图像块数据，并对图像块进行相似性匹配检验。这种方法对图像羽化或边缘模糊等处理具有鲁棒性。

四、结语

目前主流算法对于相对简单的复制粘贴篡改检测效果较好，但伪造者为了使篡改图像更加可信，除了采用简单的平移、旋转外，还可能会根据实际情况对篡改内容进行缩放、模糊等操作，这样传统的块匹配算法将会失效。因此，在保证算法健壮性与检测准确率的前提下，我们要设计出能够同时抵抗平移、旋转、缩放、模糊等各种操作的取证算法，这是我们今后努力的方向。

参考文献：

[1]周琳娜.王东明数字图像取证技术[M].北京:北京邮电大学出版社,2008:69-70

篇（11）

 

1 绪论

图像拼接技术有悠久的研究历史。早期用于航空遥感照片合成，在20世纪90年代Heung——Yeung Shum研究了同心圆拼图(柱面全景图)， 20世纪90年代中期，微软研究院的Szeliski教授提出基于运动的全景图像拼接模型，将8参数减低为4参数，2003年M.Brown发表了全自动的图像拼接算法的文章，使用捆绑调整技术，同时，鱼眼镜头拍摄图像生成球面全景图的绘制技术也得到广泛研究。

2 全景图像拼接技术的概述

2.1 全景图的模式分类

全景图根据图像投影方式的不同，存在几种全景图像：一种是球面全景图像，一种是多面体全景图像，还有一种是最常用的柱面全景图像。柱面全景处理起来比球面全景与多面体全景简单得多，因而应用面比较广。

2.2 全景图的生成流程

全景图的声称流程如下：图像的采集，图像的预处理，图像的变换，图像匹配，图像的平滑处理。

3 基于特征匹配的柱面全景图拼接技术的研究

3.1 原始图像的采集和几何校正

3.1.1 拍摄方法和原则

照相机拍摄时一般有三种情况：

1.旋转照相机拍摄

在这种情况下，放置照相机的三脚架在拍摄过程中一直在同一位置。照相机绕垂直轴旋转，每旋转一定的角度，拍摄一张照片。拍摄得到一系列照片中相邻两张必须有部分重叠。建议相邻图像之间重叠比例达到50%。重叠比例越大，拼接就越容易。

2.平移照相机拍摄

平移照相机指的是照相机在一个平行于成像平面的方向上平移。这种情况的缺点：拍摄的相片在一个平面上，拍摄的三维感觉不如旋转拍摄的。科技论文。

3.手持照相机拍摄

这种方法比较容易做到，手持照相机原地旋转拍摄。但是，拼接手持照相机拍摄的照片是很困难的，因为在拍摄过程中，照相机的运动非常复杂。可以增加重叠比例，使照相机旋转角度、平移减小，因而减小相邻图像之间的不连续程度。

用照相机拍摄全景图像，要取得较好的效果，必须注意以下几个方面的原则：

3.2 图像的变换

将一幅图像与另一幅图像匹配，常需要对一幅图像进行一系列的变换，这些变换可分为刚体变换、仿射变换、投影变换和非线性变换。

3.3 图像的匹配

3.3.1图像拼接算法的原理

一般情况下，经过柱面投影变换得到的具有重叠区域的柱面全景图中相邻的两幅待拼接图像间的重叠[2]范围大约在30%-50%之间。为了减少在特征区域提取时候的盲目性，我们可以先对灰度图像进行图像轮廓的提取，尽量的让选择的特征区域包含独特的信息，容易识别。

在图像匹配过程中，希望匹配点要准确，即关峰尖锐，定位精度高，因此在实验过程中用边缘检测的方法提取图像的边缘从而使图像的轮廓更为清晰，这样有利于提高匹配的精度和降低伪匹配的可能性。

3.3.2 基于特征区域的提取和匹配算法的实现

本文采用Moravec[3]算子进行特征区域的提取，窗口的大小可以采用55到2121。窗口越大，抗噪声能力越强，同时运算量也越大。

特征区域的匹配过程步骤如下：

1.将匹配图像重叠部分的像素灰度值和位置信息读入数据矩阵B，矩阵B读入的是匹配图像重叠部分的数据。

2.设置一个或者多个二维循环，通过对循环条件的设置或者分段设置循环，使搜索路径可以沿着预处理之后提取的轮廓边沿进行，将整个图像的重叠区域全部搜索一遍。科技论文。

3.沿着搜索的路径提取矩阵B的55，并且对矩阵内部的元素进行运算，分别计算该矩阵和单位矩阵的元素的均方差和灰度差的绝对值之和，分别把它们赋给两个变量。

4.将记录的当时搜索区域和单位矩阵的均方差和灰度差的绝对值之和跟之前的记录值作比较（记录值的初值的均方差为0，灰度值的绝对值之和为10），记录均方差的最大值和灰度值的绝对值之和的最小值，并且分别记录它们的坐标位置。科技论文。

5.搜索矩阵下移，再次重复步骤2和步骤3。

6.搜索结束，就得到了在矩阵B中令均方差最小且灰度值的绝对值之和最大的区域，记录该区域的位置和中心点的坐标位置。

在本课题的实现过程中，待拼接的图像已经经过了预处理和轮廓提取，所以在拼接的过程中，只需要将算子的中心沿着重叠部分图像的轮廓进行就可以了。

3.4图像的平滑处理

在拍摄柱面全景图时，周围环境和相机本身引起的最大问题就是相邻图像之间的光照变化较大，会出现带状痕，为了消除这种拼接区域带状痕影响，提出了一种直方图处理方法：

1.对于24位色图，首先将RGB图像转换成HIS类型图像，针对其I分量进行处理，等同于对灰度图像的灰度值进行处理。

2.将两幅图像的1/3公共部分作为重叠区域，注意要保证两个重叠区域像素数目一致。

3.分别计算左、右两边重叠区域的I分量或灰度图像灰度值的和sum1与sum2。

4.Differ=sum1/sum2，将图像2的每一个像素的I分量或者灰度图像2的每一个像素的值与参数Differ相乘加权。这样做的目的是将两幅图像的亮度均值统一，使得重叠区域在拼接时能够平滑过渡。

4 总结与展望

随着虚拟现实技术的不断发展，虚拟现实技术开始走向大众化，并应用于网上购物、网上旅游、网上教育和在线游戏等领域，虚拟现实系统将会成为未来世界一个不可缺少的重要组成部分。

【参考文献】

[1]王玉珍.基于特征区域的图像拼接技术.兰州大学硕士学位论文，2001：

3-10

[2]兰培真,马越,邱志雄,金一垂.不同视点重叠图像自动拼接算法.中国航海，2001，(2)：41-45