时间：2022-02-07 10:26:01
开篇：写作不仅是一种记录，更是一种创造，它让我们能够捕捉那些稍纵即逝的灵感，将它们永久地定格在纸上。下面是小编精心整理的12篇匹配算法论文，希望这些内容能成为您创作过程中的良师益友，陪伴您不断探索和进步。
关键词：Rete算法，智能防火墙，规则，快速，匹配
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)
[3] 江建国，张景中. 基于Rete算法的几何自动推理系统. 四川大学学报（工程科学版）， 2006(03)
关键词：KMP；改进；模式匹配算法；字符；分析；算法
中图分类号：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.
[6]赵森严，黄伟，李阳铭.一种改进的KMP入侵检测的模式匹配算法[J].井冈山大学学报（自然科学版），2013（01）：55-57.
【摘要】 颈动脉超声图像中的运动信息能够间接地反应颈动脉弹性等状况，结合颈动脉内中膜厚度(CIMT)能够为心脑血管疾病诊断提供定性与定量的依据。我们将改进后的金字塔快速匹配算法(modified block sum pyramid，MBSP)应用于颈动脉超声波图像斑点跟踪获得运动信息。理论和实验结果都表明，改进后的金字塔块匹配算法能有效地减少运动跟踪的运算量，并且有着和改进前的金字塔块匹配算法相同的准确度。运动跟踪结果能够为医生诊断心脑血管疾病起到一定的辅助作用。
【关键词】 颈动脉;斑点跟踪;金字塔算法;运动分析;平均绝对差函数
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.
[7]Demir B， Ertu¨rk S. Block motion estimation using adaptive modified two-bit transform[J]. IET Image Process， 2007，1(2):215-222.
关键词：数字图像取证；图像区域复制粘贴篡改
中图分类号：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
[2]骆伟祺,黄继武,丘国平.鲁棒的区域复制图像篡改检测技术[J].计算机学报,2007,11
关于树叶质量的建模与分析
封锁嫌疑犯的数学建模方法
正倒向随机微分方程理论及应用
数学建模与数学实验课程调查报告
基于肤色模型法的人脸定位技术研究
生猪养殖场的经营管理策略研究
从数学建模到问题驱动的应用数学
大学篮球教练能力评价的机理模型
基于WSD算法的水资源调度综合策略
关于地球健康的双层耦合网络模型
多属性决策中几种主要方法的比较
塑化剂迁移量测定和迁移模型研究进展
基于信息熵的n人合作博弈效益分配模型
混合动力公交车能量控制策略的优化模型
垃圾减量分类中社会及个体因素的量化分析
随机过程在农业自然灾害保险方案中的应用
“公共自行车服务系统”研究与大数据处理
天然气消费量的偏最小二乘支持向量机预测
微积分与概率统计——生命动力学的建模
美国大学生数学建模竞赛数据及评阅分析
微积分与概率统计——生命动力学的建模
在微积分教学中融入数学建模的思想和方法
2015“深圳杯”数学建模夏令营题目简述
字符串匹配算法在DNA序列比对中的应用
差分形式的Gompertz模型及相关问题研究
小样本球面地面条件下的三维无源定位算法
数学建模思想渗入代数课程教学的试验研究
基于贝叶斯信息更新的失事飞机发现概率模型
基于人体营养健康角度的中国果蔬发展建模
关于数学成为独立科学形式的历史与哲学成因探讨
深入开展数学建模活动,培养学生的综合应用素质
完善数学建模课程体系,提高学生自主创新能力
利用动态贝叶斯网构建基因调控网络的研究进展
地方本科院校扩大数学建模竞赛受益面的探索
城镇化进程中洛阳市人口发展的数学建模探讨
基于TSP规划模型的碎纸片拼接复原问题研究
卓越现场工程师综合素质的AHP评价体系研究
基于Logistic映射和超混沌系统的图像加密方案
嫦娥三号软着陆轨道设计与控制策略问题评析
嫦娥三号软着陆轨道设计与控制策略的优化模型
微生物发酵非线性系统辨识、控制及并行优化研究
含多抽水蓄能电站的电网多目标运行优化研究
连接我们的呼吸:全球环境模型的互联神经网络方法
垃圾焚烧厂周边污染物浓度的传播模型和监测方案
以数学建模竞赛为切入点,强化学生创新能力培养
一种新的基于PageRank算法的学术论文影响力评价方法
基于视频数据的道路实际通行能力和车辆排队过程分析
[关键词]通信技术；交通流，GPS定位
中图分类号：TN 文献标识码：A 文章编号：1009-914X（2014）23-0203-01
1.研究内容
手机定位技术是利用移动通信网络和移动通信设备进行手机定位的，只要能够实现双向通信的移动通信系统都可以作为这种定位系统的通信基础，如国内移动运营商较多采用的GSM系统、CDMA系统等。现阶段，国内两大主要移动运营商移动、联通均已推出了手机定位服务。
无线定位系统中将手机定位方式分为：基于网络方式及利用移动网络的基站获得手机位置信息，该方法不需要对现有的手机设备进行任何改进；基于手机终端的方式，该方法需要对现有手机设备进行一定的改进；以及两者的混合式定位方式。可见，将基于网络的手机定位数据作为交通检测信息不需要过多的基础设施投资，能够实现低成本、实时的交通流参数检测。
比较实用的GPS定位技术是网络辅助的GPS定位，即定位时，网络通过跟踪GPS卫星信号，解调出GPS导航信号，并将这些信息传送给移动台，移动台利用这些信息可以快速的搜索到有效的GPS卫星，接收到卫星信号后，计算移动台位置的工作可以由网络实体或移动成。基于GPS系统的定位技术，其优点是定位精度较高，定位半径可达到几米、十几米。因此利用该重定位技术，可提供对定位精度要求较高的业务，如电子地图显示用户位置等。其缺点是需要移动台内置GPS天线和GPS芯片等模块，并且需要支持IS-801协议，网络侧需要增加PDE和MPC；定位精度受终端所处环境的影响较大，如用户在室内或在高大建筑物之间时，由于可见的GPS卫星数量较少，定位精度将降低，甚至无法完成定位。
GPS（AssistedGPS）。A-GPS与GPS方案一样，也需要在手机内增加GPS接收机模块，并改造手机天线，但手机本身并不对位置信息进行计算，而是将GPS的位置信息数据传给移动通信网络，由网络的定位服务器进行位置计算，同时移动网络按照GPS的参考网络所产生的辅助数据，如差分校正数据、卫星运行状态等传递给手机，并从数据库中查出手机的近似位置和小区所在的位置信息传给手机，这时手机可以很快捕捉到GPS信号，这样的首次捕获时间将大大减小，一般仅需几秒的时间。不需像GPS的首次捕获时间可能要2―3分钟时间。而精度也仅为几米，高于GPS的精度。
在移动电话定位系统中，可以利用不同的信号特征参数，如信号强度（SS）、信号到达角度（AOA），时间测量值（包括信号到达时间TOA、信号到达时间差TDOA）等，以及他们的组合进行定位。各种定位方法采用的信号特征参数、信号检测设备、实现定位的难易程度、信号传播中的影响因素和定位的精度都不相同，但提供“微观”车辆运行状态的车载手机定位数据的确具有相同的数据特征，与传统检测器提供的车辆通过信息的数据特征完全不同。
从数据的检测对象上看，基于GPS定位的交通流参数估计，已采集道路车流中行驶的装配GPS定位装置的车辆自身的行驶数据――多点定位位置、瞬时速度数据及车辆的一些其他状态信息为基础，进而获得检测车辆所在道路的交通流参数。基于移动通信网络的手机定位信息包括公路沿线手机的ID号和经纬度，利用上述手机信息获得独立车辆运行状态，进而估计信息间的单元所在路段的交通流参数。
可见，基于传统检测器和GPS定位检测器的交通流参数估计均是以车辆为检测目标，检测车辆的通过或存在状况，获得道路上的独立车辆信息。而基于手机定位的交通流参数估计却以道路上行驶车辆的车载手机为检测目标，通过车载手机信息获得独立车辆状态。
标定切换网络
切换网络由切换点和切换路段构成，其中切换点指的是车载手机在道路上发生手机切换的位置；切换路段指的是连续发生两次手机切换的路段。在沿途道路上标定出基站切换或手机切换点的位置，利用预先准备的专业软件经实地测试获取切换点坐标，计算出切换网络中每条道路的路段长度，如图所示。其中（1，3）就是一个被标定的切换点，表示手机从基站1到基站3的切换点位置坐标；L1就是两个手机切换点A（1，3）和B（3，6）之间的路段长度。
2.路径匹配
与预先得到手机位置获取交通信息方式不同，基于手机位置切换技术的路径匹配是利用沿路行驶的车载手机切换序列来确定手机所处路段。在理想状态下，手机在两基站覆盖范围交界处发生切换，每条道路都有与之对应的一条稳定切换序列，按照上面原理示意图，根据已标定的切换网络，得到与实际道路对应的手机切换序列1-3-6-9-10-12-15-18-26，当通过七号信令解析出来的GSM网络中的小区部分或全部标识与这条道路的切换序列相一致，就能对该车载手机的行驶路径匹配到该路段中。例如，采集到手机的切换序列为1-3-6-9、9-10-12、12-15-18-26等，都可以确定车载手机在该条道路上行驶。
另一方面，由于手机信号受多方面因素影响，如城市内的高层建筑对信号的反射和折射、其他通信信号对手机信号传播的干扰等，都对手机切换造成不稳定影响，也降低了路径匹配概率，需要进一步研究这些现象，让两者关系趋于稳定。
计算路段行程车速
完成切换网络标定和路径匹配之后，就可以计算每条道路上的路段行程车速。手机至少连续发生两次位置切换才能得到手机行驶的路段长度Li， 这时根据Vi=Li/ti 即可计算出车载手机的行驶速度。以此类推，就可以获取切换序列中，手机对于所有相应路段的行驶速度。
3.地图匹配技术的算法
地图匹配算法的要求
地图匹配的结果需要尽可能的减小车载手机的轨迹坐标与行驶车辆的实际位置之间存在的影响误差，正确显示车辆在地图上的具置，提高系统信息采集的稳定性和可靠性。因此，地图匹配的算法就需要满足以下要求：
选用的算法具有实时性：算法简单，可以随时调整车辆行驶轨迹，减少时延估计；
选用的算法具有适应性：算法针对复杂交通路况都可以进行匹配，不受单一道路条件局限；
选用的算法具有可靠性：算法在复杂路网上，可以选择正确的候选道路；
算法要求距离因素：车辆实际位置与地图匹配道路之间的距离应最短；
算法要求方向因素：车辆行驶轨迹与地图匹配道路方向保持一致；
算法要求道路连通性因素：车辆行驶上一时刻的位置的匹配于一条道路上，则当前时刻的车辆位置也匹配于该道路上，或者匹配于与该道路连通的道路上；
算法要求路径长度因素：在某一时间间隔内，车辆行驶的实际距离与匹配到地图上的路径长度基本相同；
对于蜂窝无线定位，还需考虑两个因素：
【关键词】语音识别 语音辅助 办公系统 有限状态机
语音交互是人们最广泛使用和适应的一种日常交互方式，在电子信息领域，也是一种理想的人机交互方式，随着语音识别算法的发展和相关硬件技术进步，语音识别技术逐步走向成熟，目前在语音输入领域、语音大数据分析、语音生活辅助等领域已经有较多的应用场景。但是语音辅助技术目前仍存在一定难点，例如语音开集库识别、语音交互速度等方面。同时，语音识别技术在办公辅助系统上应用还较少，尤其是某些工作人员不方便进行手动指令输入操作的场景或手动指令输入效率较低场景，如果利用语音辅助技术，可以有效提高用户办公效率和系统适应性。
本文基于上述问题，针对性地提出了一种语音辅助系统模型，通过合理的模型设计和算法设计，有效改进了上述技术难点带来的语音识别效率和指令输入效率问题，提高用户使用语音辅助时的工作效率和用户体验。
1 系统概述
1.1 系统整体框架介绍
系统整体框架如图1所示，系统分为三层架构，分别为用户交互层、逻辑处理层和底层框架。用户交互层主要负责与用户进行指令交互工作和信息反馈工作，主要包含三个模块，为语音监听模块、用户输入模块和语音反馈模块，三个分别负责用户语音监听，用户手动指令输入和系统信息语音反馈。
逻辑层为系统核心部分，包含模式识别模块、指令执行模块和语音识别模块，其中，语音识别模块获取交互层提交的用户语音音频信息，将用户语音指令或语音输入转换为输入字符串，以便进一步处理。模式识别模块的主要作用是将用户输入语音转换获得的字符串进行模式匹配，将无结构的字符串转换为结构化的指令树，从中提取用户真正的指令信息。指令执行模块的主要功能是进行用户数据和系统操作的指令执行，其中为其他模块提供系统操作接口，供其他模块调用。
底层框架提供了系统基础运行平台，分别包含系统运行框架和数据库平台，底层框架根据不同的系统部署要求可以进行对应的调整。
2 系统关键部分
2.1 语音监听与识别模块
语音监听与识别属于用户交互端和逻辑预处理端，其核心部分为语音识别技术（Auto Speech Recognize，简称ASR），在本论文的实现过程中，采用科大讯飞的语音识别SDK，其语音识别算法采用深度神经网络（DNN）声学建模，同时采用多重降噪算法进行降噪处理，经测试，能够充分满足本系统针对的多样化使用场景需求。
系统在启动后，语音监听模块将进行常驻监听，保证用户指令随时处于输入状态，减少用户手动操作效率降低问题，获取语音信息经压缩后传递给语音识别模块，语音识别模块将音频信息识别后转换为字符串，此生成信息作为模式匹配样本交给逻辑层处理。
2.2 指令模式识别模块
指令识别模块的主要作用是获取经过对用户输入语音转换后的字符串，通过与系统预先设置的用户指令进行对比匹配，提取用户输入信息中的指令部分，再交由指令执行模块进行信息处理。
为提升用户指令匹配成功率，在指令模式识别过程中，采用有限状态机模型（Finite-state machine），采用有限状态机，可以建立指令样本，在对用户输入信息进行指令匹配时，采用顺序字符串匹配算法，这样可以高效过滤用户信息，快速提取用户指令。
3 系统关键技术
3.1 基于有限状态机的指令匹配模型
此部分主要包含两个方面，一是系统指令的预设定，如上文所述，在某信息系统嵌入该语音辅助系统时，首先要确定该系统所需要对用户提供的指令内容，将每个指令内容作为有限状态机中的单一状态，例如图2所示。
第二部分为用户输入信息指令提取，由于用户指令数有限，所以，在获取用户模式匹配样本之后，可以采用顺序字符串匹配计算，当匹配到预设指令时，便将该指令作为状态机状态转移标志，进而获取用户所需要进行的操作，达到指令匹配目的。在匹配过程中，采用KMP算法，有效提高用户指令输入效率。
3.2 指令快速匹配优化
在大多数信息系统中，除了用户操作有限之外，还具有上下层级关系，为提高用户输入效率，在系统初始化设定过程中，针对具有层级关系的指令，将其构筑为指令树结构，如图3中所示，如果用户输入指令为“AABB0246CC”，系统在匹配至“0”时，将不再向用户返回确认请求，将继续进行指令匹配，直至匹配至“C”，那么最终状态将跳转至状态7，向用户返回请求指令7执行，得到确认后，将执行指令。按照上述流程，在面对多层指令操作时，用户只需要语音输入连续状态指令，将直接跳转至目标状态，执行目标执行，达到指令快速匹配目的，这样极大提升了用户输入效率，省去大量重复语音指令输入步骤。
4 总结
目前语音识别正在进入越来越多的领域，利用本文设计的语音辅助系统，用户指令输入效率得到显著提升，同时给出整体模型，以便其他信息系统平台高效接入此语音辅助系统。
参考文献
[1]王炳锡.实用语音识别基础[M].北京：国防工业出版社，2005.
[2]童拉.办公自动化系统中语音功能的设计和实现[J].湖北工业大学学报，2005，20（02）：71-73.
[3]讯飞开放平台.科大讯飞股份有限公司.2017.http：///.
查看更多《信息技术》杂志社信息请点击： 《信息技术》编辑部
基金项目
(1)基于c＋＋ builder的共焦显微镜三维重建方法 杨召雷 张运波 董洪波
(4)m—link在通信系统仿真中的设计与实现 姚云龙 周俊 刘强
(8)基于嵌入式的无线煤炭自燃预警系统 刘德文 杜宇人
(11)tts语音单元的无损压缩与按需解压缩技术 卡斯木江·卡迪尔 古丽娜尔·艾力 艾斯卡尔·艾木都拉
无
(14)2012年中国国际信息通信展览会开幕 无
基金项目
(15)低载荷工业机器人运动学分析与仿真 陈蓓玉 胡凯 杨乐
(19)基于zigbee无线传感网络监测系统的实现 杨俊 阮超 陈睿瑶 付红桥
(23)endnote x5软件在论文撰写过程中的应用 程宏辉 程筱农 奚和平 黄新
(26)一种近距离无线传感器系统的设计 叶天凤 胡长晖 叶梦君 万里光
(29)sakai网络教学平台统一身份认证中心的实现 柯水洲 马雪梅 王新舸 邹刚
(33)增益连续可调宽带前置放大电路设计与实现 汪俊杰 盖建新 刘旭 程爽
(37)actionscript3.0垃圾回收机制及优化策略 李智勇
(40)基于彩信的远程控制宠物笼系统的研制 杨乐 高超
(42)spring mvc技术分析及在实践教学系统中的应用 符红霞
(47)支持向量机在广义预测控制中的应用 张伟 贾蓉
(50)测控信息技术领域提高学生实践创新能力的方法 王可宁 刘缠牢 王伟 张雄星
(53)一种复杂背景下车牌定位算法 赵大伟 陈刚
研究与探讨
(58)基于spce061a的语音手动双控制开关的设计 李建新 张肖飞 徐丽妍
(62)基于bp神经网络的钻井复杂情况和事故诊断 崔猛 汪海阁 李洪 纪国栋 于洋
无
(65)第九届通信企业管理现代化创新成果审定会开幕 无
研究与探讨
(66)一种基于单摄像头的虚拟键盘 杨骋
(68)基于椭圆曲线的充值卡加密 孙传亮 周海港
(72)基于ccd和光电编码器的差速整定方法研究 李增彦 张迪洲 张男
(77)嵌入式软件仿真测试平台开发 林丹丹
(80)基于anybus-s pn io模块的profinet远程i/o设计 杨明 王永刚 张陆毅
(85)采用mel倒谱参数的咳嗽声识别方法 尹永 莫鸿强
(92)模板匹配算法的两种实现方法比较 谢方方 杨文飞 陈静 李芳 于越
(96)基于msp430的低频信号分析仪设计 张君 李金龙 郭建强 杨林晓
(101)基于labview的双向智能钥匙充放电测试系统 尹武 张文娟 周继宇
br> (104)多用途市电负载功率调功电路的设计 姚正武 部绍海 林涛 李树伟
(107)gps周跳探测与修复方法的比较分析 徐欢 唐亮 都业涛
(112)并行计算技术综述 王磊
(116)卫星远程监视及实时故障诊断研究与应用 陈怀木 贾银山 穆友胜
(121)基于soa的一体化缴费接入管理平台设计 王树全 邹宁峰 金鑫
(125)基于增量式pid控制算法的智能车设计 肖文健 李永科
应用技术
(128)油层保护模糊专家系统的分析与设计 张丹 曹谢东 魏存挡 庞扬
(131)基于multisim10低频信号源的设计与仿真 兰羽 周茜
(134)光电池基本特性的测定 赵楠 孙雪萍 李平舟
(137)基于单片机的无视频报警监测仪设计 李钊
(140)基于hfss的有孔屏蔽体的屏蔽效能分析 陈新平 杨显清
(144)战术无线电台半实物仿真系统设计与实现 张爱民 辛广辉 郑振华
(147)基于混合高斯模型与核密度估计的目标检测 吕游 任政 李向阳 方向忠
(151)基于业务流程的信息化建设与应用 刘光伟
(153)基于国产cpu的嵌入式医疗电子无线网络设计 裴家俊 张辉 刘芸 戎蒙恬
(157)利用vba及office自动化技术辅助人事办公 王晶
(159)数字钟电路的设计 曹啸敏
(163)基于电磁传感器的智能车自主寻迹系统设计 师克 王洪军 李永科
无
(166)上海市中国软件名城创建暨软件产业工作会召开 无
应用技术
(167)异步时钟亚稳态仿真方法 高文辉 胥志毅 邬天恺 刘文江 仲景尼
(170)lwip的移植及其在并行系统中的应用 赵虎 黎英 游谦
(173)盲人行走辅助装置中道路检测算法的研究 徐姗姗 应捷 宋彦斌
无
(176)尚冰出席第八届中国信息无障碍论坛开幕式并致辞 无
应用技术
(177)多载波传输系统的频偏及采样钟联合补偿算法 李炎 周志平 李鑫
(181)智能小车模糊-pid控制调速系统设计 张家骅 徐连强 吴迎春
无
(183)第九届海峡两岸信息产业和技术标准论坛举行 无
综述与评论
(184)epc信息管理系统在装备器材保障中的研究 康帅 高庆 程远增
(187)基于供应链信息共享的备件资源整合研究 黄健 程中华 王亚彬
(190)航空航天侦察情报保障能力综合评价模型研究 童涛 杨桄 谭海峰 王寿彪 叶怡
(194)装备保障信息评价研究 赵国存 刘占岭
无
(f0003)
关键词：XML数据；节点加权；树编辑距离；相似性
中图分类号：TP391.1
随着网络快速发展，由于结构化的XML类型数据可扩展且跨平台而成为当前网络数据的主流形式。XML文档的迅速增多并集成统一平台后，会产生不被需要的“脏数据”，而对这些数据的清洗变的更加重要。这些“脏数据”使轻则会使获得的信息不准确，重则获得完全错误的信息。为了使XML数据源中的数据能发挥最正确的作用，清洗平台中的“脏数据”成为一个组要解决的问题。
非一致性转换、相似性判定、信息抽取等3方面是当前XML数据清理的主要关注点。如韩恺等人提出的在上下文语义影响下的XML文档的匹配方法[1]，Flesca等人将结构化的XML文档与时间序列、脉冲等内容联系起来进行相似性检测[2]。以上两篇文章关于XML数据清理方法考虑了不同DTD树间的匹配算法，其中文档内容提到较少，部分方法设计思想很好，但实践可行性有限。
首先，将一个XML文档转化为一棵树或一个图，然后通过度量这两棵树（图）间的距离来体现XML文档间的相似度。在众多树相似度匹配的研究工作中，普遍接收和采用的既是树编辑距离算法[3-6]。Tai[3]最早将编辑距离的方法应用到检测两颗树间的相似性。以他的理论为基础，提出的一系列树编辑距离算法及相关的改进算法等。
1 相似重复记录
信息集成中，数据清洗和提高数据质量是检测和消除集成数据中的相似重复记录中最需要解决的问题之一。相似重复记录的概念是指虽然在现实世界中表述的是同一个实体，但由于拼写错误或表达方式的不同，而导致数据库管理系统不能将其识别为重复的记录。这些重复记录的产生导致决策者在最终决策时由于依据的信息不正确而产生较大的影响。以此为基础，重复记录检测在信息的抽取、转换、加载的过程中显得更加重要。目前研究的主要方向体现在西文、中文字符集的相似重复记录的检测，已有了一定研究。但对于半结构化的XML数据的重复记录检测算法的研究还有待进一步提高。
XML数据在网络中使用的增多以及在数据库中的使用，使得这种数据类型在数据清理中越来越重要。实际多种XML数据被认为不一致，例如拼写错误等导致字符串属性不一致，从而使得此字符串类型数据不一致。另外，实际相同的XML数据由于结构上不同被认为是不同的数据。即使数据源具有相同的DTD结构，属性个数不同、属性值拼写不同均可导致XML数据不一致。
在XML数据的ETL中，主要摒弃其中的“脏数据”，也就是检测出相似记录合并，普遍采用的方式即将XML文档转换成树结构，转换的过程中要将树中的节点与数据元素相对应，即节点名为元素标签名。编辑距离方法分为两种，字符串编辑距离算法用判定两个字符串是否相似，而通过树编辑距离方法时大家更清晰的认识到带标号有序树间差异。以下给出与树编辑距离相关的概念定义。
2.1 基本概念
目前对于数据相似性的检测主要采用编辑距离的方式，而此方式又分为两种，字符串编辑距离主要用于字符串领域，树编辑距离主要应用于两棵树或图的差异检测，以下给出具体概念描述。
（1）字符串编辑距离：定义字符串S1、S2，当S1转换为S2时所需要的编辑操作的最小数目，此转换指单个字符上的转换，而操作主要指插入、修改、删除。此概念普遍应用于字符串的相似性检测。
（2）树编辑距离：定义两棵树T1、T2，当T1转换到T2时所需要的书编辑操作的最小代价，此转换指节点的转换。而节点的插入、删除、修改三种操作称为树编辑操作：
1）修改（替换）：节点改变；
2）删除：删除某一节点的同时，将该节点的儿子节点重新定义为兄弟节点并插入到其父节点的子树中；
3）插入：插入某一节点的子节点，而该节点的原部分子节点转换为新插入节点的子节点。
树编辑距离体现了在两个树转化的过程中树编辑操作的最小次数，而实际编辑操作次数计算方式可以通过映射这一概念来体现，将整个求解过程解释为树之间的映射过程，称为编辑映射。
（1）树编辑距离算法：定义两个树T1和T2，在两个树之间建立一映射，直接体现了树与树节点间的对应关系。在树与树之间建立映射需要满足一系列的条件，首先给出两组对应关系属于此映射，分别为（i1，j1），（i2，j2），其中1≤i、j的值≤树的节点数，则，当且仅当j1≤j2时，i1≤i2；另外当且仅当节点j1是节点j2的祖先是，节点i1是节点i2的祖先，从而将树编辑距离的计算转换为映射的计算，在计算过程中，最好的结果即是所付的代价最小。
（2）树编辑距离相似性检测：XML类型数据相似性的检测可以分两步走，首先计算文档转换为树结构时，数据所对应的节点元素字符串间的差异，然后把字符串差异的计算合并到树编辑距离的计算之中来。树编辑距离的值越小，则两颗XML树越相似，此过程中给出阈值的概念作为评判的标准，当值小于设定的阈值时，认为两个XML数据相同。
3 优化的XML相似重复数据检测算法
时间复杂度体现了完成操作所需要付出的代价，而针对上述的树编辑距离算法其时间复杂度跟树的节点数以及树的高度有直接的关系。因此，当XML文档的数据量足够大的时候，计算代价会成倍增长，这在实践过程中是无法忍受的，因此，必须采用优化措施来减少树编辑距离计算。本文优化树编辑距离算法，在整个过程中，首先通过树节点的权值进行第一次匹配，将相似性更大的数据聚集到一个集合中，在此集合中采用树编辑距离方法进一步匹配，从而减少时间复杂度。
3.1 带权树的生成
由于XML文档可以转化为多种树表示形式，针对XML文档通过SAX（Simple API for XML）解析器进行解析，将XML文档转化为XML树结构，并具有相应的可行匹配方法。根据解决问题的侧重点不同，XML带权树的属性在XML文档中具有不同的重要程度。通过XML带权树的权值的大小来表示属性的重要性。根据权值本身的设置特点，在带权树中，设置相同根节点的同一层次上的节点权值之和等于1。
3.2 相似性粗略匹配
针对完全展示XML文档的信息的带权树，通过权值的不同体现每个元素重要程度的不同。通过权值进行粗略匹配主要体现在XML树的属性相同时，权值是否相同，权值差异越小，则判断树的相似性越高。在整个判断的过程中，还需要考虑到属性的多少，即树分支数目。
通过实际情况分析推测出重复记录相似度的计算方法如下：带权树Ta和Tb，N代表两树所有节点的个数，a1 a2 … aN，b1 b2 …bN分别代表权值，其体现了属性的重要程度。另外，当某一属性仅存在于一棵树中时，则设定此属性的权值为0，相似度的计算公式见（1）[7]：
S（Ta，Tb）=（N-（a1-b1+a2-b2+ … +aN-bN））/N
=1-（ （ai-bi））/N （1）
上述公式作为相似度计算的工具，可以很好的计算出任意XML带权树之间的相似性，通过具体的数据来体现差异的大小，从而进行简单的匹配，节省时间。
根据以上描述给出XML类型数据相似性检测的伪代码算法描述如下：
（1）将输入的XML数据集转换为XML带权树；
（2）通过节点权值来计算两棵带权树间的相似度，从而粗略匹配数据；
根据上述思想给出粗略匹配的伪代码描述。
（a）从所有的XML树中任取其中一棵树；
（b）以所取树为基准，通过相似性度量公式计算基树与其它树之间的相似度，目的为了得到所有的相似度值；
（c）将上述相似度值与系统输入的相似度量λ进行比较，若大于等于λ；
（d）将相似度值大于等于λ的XML树聚合成新的集合C1；
（e）任取一不在集合C1中的带权树Tb；
（f）重复执行步骤（b）；
（g）直到所有的带权树均存在于一个集合中。
（3）在经过第（2）步聚集的所有新集合中使用树编辑距离算法，当计算后的距离值小于给定的阈值δ时，认为两个是相似的XML数据。
4 结束语
本文首先介绍了一系列概念定义，包括相似重复记录，两种编辑距离，并详细描述了树编辑距离相似性检测算法及相关问题。在此基础上，提出一种检测XML数据相似性的方法，即将XML文档转换成树结构的基础上，对树结构的节点加权，并结合树编辑距离算法。通过XML带权树各属性权值计算的相似度对数据进行粗略匹配与聚集，而在重新聚集的集合中使用树编辑距离算法更直接的进行相似性检测。该方法可以大大减少不必要的树编辑距离操作。
参考文献：
[1]韩恺，岳丽华等.基于上下文的异构文档类型定义匹配[J].小型微型计算机系统，2005，26（02）：256-260.
[2]Flesca S，Manco G，Masciari E et al. Detecting structural similarities between XML documents.In：Fernandez MF，Papakonstantinou Y，eds.Proc.of the Int’l Workshop on the Web and Databases（Web DB）.2002：55-60.
[3]Tai K C.The tree-to-tree correction problem. Journal of the ACM， 1979，26（03）：422-433.
[4]David T. Barnard，Gwen Clarke et al.Tree-to-tree Correction for Document Trees，1995.
[5]Zhang K，Shasha D.SIMPLE FAST ALGORITHMS FOR THE EDITING DISTANCE BETWEEN TREES AND RELATED PROBLEMS，1989，18（06）：1245-1262.
[6]Zhang K.Algorithms for the constrained editing distance between ordered labeled trees and related problems，1995，28（03）：463-474.
[7]江曼，陈继明，潘金贵.基于XML的层次式过滤研究[A].2006年全国体育仪器器材与体育系统仿真学术报告会论文集[C].2006.
关键词：伪二维隐马尔科夫模型；符号识别；图像匹配
中图分类号：TP312
目标的检测与识别主要应用于智能交通领域，如飞机、舰船、车辆等目标的检测与识别跟踪[1]。要实现图像目标的检测与识别，一方面可以通过一些图像处理的手段消除影响因素使其得到比较规范的数据；另一方面就可以寻找目标图像上能够保持恒定不变的某些特征参数来建立该类目标的表述模型。建立了这样的目标影像的表述模型后就能实现影像目标有效识别。第一种方法虽然是一个行之有效的方法，但是它需要一系列繁琐的预处理，效率很低；本研究主要是考虑提取标更一般化的不变量特征。
基于伪二维隐马尔科夫模型（Pseudo Two-Dimensional Hidden Markov Model-P2DHMM）的识别方法[2]，是基于P2DHMM模型的拓扑结构进行图像的匹配，计算得出P2DHMM距离，利用最近邻原则判别，没有固定的模板参量限制，因此P2DHMM在手迹识别、人脸识别和医学图像方面得到成功的应用[3-4]。本研究将P2DHMM引入到图像符号的识别中，工作重点放在三个方面：（1）研究图像中基于P2DHMM目标识别的二维非线性变形模型的适用性和潜在应用价值；（2）实验模型的拓扑结构、主要参数和算法选择；（3）建立典型参考图像符号库，进行了图像符号识别实验并分析结果，提出模型改进的建议。
1 伪二维隐马尔科夫结构与特征参量构建
1.1 隐马尔科夫模型与伪二维隐马尔科夫模型
隐马尔科夫模型（HMM）是在马尔科夫链的基础上发展起来的，由于实际问题比马尔科夫模型所描述的更为复杂，观察到的事件并不是与状态一一对应，而是通过一组概率分布相联系，这样的模型就称为HMM。它是一个双重随机过程，其中之一是马尔科夫链，这是基本随机过程，它描述状态的转移；另一个随机过程描述状态和观察值之间的统计对应关系[5]。
二维隐马尔科夫模型（2DHMM）是由HMM模型演变而来，它由水平方向HMM和垂直方向HMM构成，水平HMM中的某一状态不仅可以转移到水平方向的其它状态，同时还可以跃迁到垂直方向HMM中的某一状态，同样的垂直方向HMM中的状态也可转移到水平方向。由于二维HMM的结构的复杂性，算法复杂，限制了2DHMM的应用[6]。
伪二维隐马尔科夫模型（P2DHMM）利用了一维HMM的基本拓扑结构，将一个完整的一维HMM作为一个状态，形成P2DHMM的超状态，超状态里面的一维HMM的状态是子状态。子状态只能在相应的状态约束下进行跃迁，超状态与子状态之间也不允许跃迁，但是在超状态之间有状态转移。由于这一模型中不同超状态下的子状态之间不能够跃迁，因而不是真正意义的二维模型，故也被称为伪二维隐马尔科夫模型，见图1。每个超状态为一个隐Markov模型单向左右型的拓扑结构，超状态间转移的拓扑结构也为单向左右型。P2DHMM模型已被成功地应用于字符识别、人脸识别等领域。
图1 P2DHMM的拓扑结构图
1.2 基于P2DHMM拓扑结构的图像匹配
基于P2DHMM拓扑结构的图像匹配，没有进行目标的特征的提取直接用图像的灰度值进行匹配。
具体匹配算法如下所述：
假设，测试目标图像用A=（aij）表示，其中每个像素的位置为（i，j），i=1，……，I，j=1，……J。
参考目标图像用B=（bxy）表示，其中每个像素的位置为：
X=1，……，X，y=1，……，Y。
基于P2DHMM拓扑结构的测试图像和目标图像之间进行匹配满足的约束为：
x（1，j）=y（i，l）=1
x（N，j）=y（i，N）=N
0≤（xij-xi-1j）≤2
|xij-xij-1|=0
0≤（yij-yij-1）≤2 （1）
此约束忽略了相邻的列的像素之间的依赖关系，相邻列之间的垂直方向的相对置移被忽略，图像间的映射为列到列的映射，映射关系满足P2DHMM超状态的转移。每列内的像素之间的映射也是满足超状态内的子状态之间的转移。
超状态之间的转移是从左到右，子状态之间的转移是从下到上，跃迁都不超过2个像素宽。像素和其相邻的像素之间的关系保持下来，参考图像的二维变形图像保持了原始图像的结构特征。
通过基于P2DHMM的拓扑结构对两图像进行匹配，我们得到样本B的变形的图像B（xIJ11，yIJ11）。A，B图像之间的距离，就转化成A和B（xIJ11，yIJ11）之间的距离。
（2）
1.3 图像水平方向约束的补偿与构建特征参量
P2DHMM不是真正的二维，放松了水平方向的约束，目前通常采用两种方法对这种假设进行补偿[6-7]。第一种方法是对图像进行Sobel滤波（包括水平和垂直方向），得到图像的梯度图，在梯度图的基础上进行识别。第二种方法是加入像素的上下文信息，比如采用3×3的区域的上下文信息。
若用U表示3×3的区域，A和 之间的距离用欧几里的距离公式：
（3）
现在将这两种方法结合，对梯度图像进行上下文信息的提取和重构。
特征参量提取的步骤：
对图像分别进行垂直、水平方向的Sobel滤波，得到图像的两个梯度图。
将两个梯度图上同坐标的像素3×3的区域的9个像素的灰度值取出，得到每个像素的18维的矢量表示。
得到像素垂直方向提取结果3×3（V），水平方向提取结果3×3（H），将水平方向提取结果与垂直方向提取结果排列构成18维的矢量表示。
2 技术路线与典型实验
2.1 技术路线
从一系列图像中，选择200种典型的图像符号作为试验的参考样本。对样本进行缩放、旋形成测试样本。然后进行P2DHMM匹配处理，处理技术路线见图2：
图2 P2DHMM匹配处理的流程图
2.2 典型图像符号P2DHMM匹配实验
图3和图4是同种图像符号的识别效果图。从左到右分别是测试图像-1，变形图像-2，变形网格-3，参考图像-4。上层是垂直方向Sobel滤波的效果图，下层是水平方向Sobel滤波的效果图，每一次匹配结果可以得到一个P2DHMM距离值。其中，变形网格是参考图像二维变形过程中，像素的坐标位置的置移，变形图像-2是参考图像-4根据测试图像得到的二维变形图像。
如果背景相同、目标相同，测试图像-1和参考图像-4相同，变形图像-2就没有变化，变形网格-3是直角网格，P2DHMM距离值为零。见图5。
如果测试图像和参考图像是同种图像符号，发生了一定的缩放，计算得到两图像的P2DHMM距离值不为0，变形网格-3发生变化，P2DHMM距离值较小为6.79455。
如果测试图像和参考图像是不同种类型的图像符号，计算得到两图像的P2DHMM距离值不为0，变形网格-3发生变化，P2DHMM距离值较大为31.76735。
图3 同一图像符号的匹配效果图
图4 缩小图像符号的匹配效果图
图5 不同图像符号的匹配效果图
我们利用图2的技术路线开发了图像符号识别原型系统，取得了好的识别效果。为两种图像符号的识别效果图。
图像符号识别效果图中。左上角为待识别图像符号，识别结果中列出了识别出的图像符号。识别出的图像符号按照P2DHMM距离值的大小从左到右排序，越靠左P2DHMM距离值越小，表示与待识别图像符号越相似。
图6 图像符号识别效果图
3 结束语
论文介绍了将人工智能领域的P2DHMM模型介绍引入到图像目标识别的模型构建、算法选择和典型实验的技术过程。利用基于P2DHMM的拓扑结构的约束进行测试图像和参考图像的匹配，保持了参考图像的结构特征，得到更一般化的度量距离，采用了提取图像的水平和垂直两方向的两幅梯度图中像素周围3×3 区域的像素信息表示像素值，得到像素的18维矢量表示，提高了的符号的识别率。
实验结果展示了P2DHMM模型在图像符号识别方面的应用潜在价值。另外，当目标背景发生变化的情况下，可以先做中值滤波处理，可以提高P2DHMM处理效果。
参考文献：
[1]马建文，田国良，王长耀.遥感变化检测技术综述[J].地球科学进展，2004（19）：192-195.
[2]史忠植.高级人工智能[M].北京：科学出版社，1998.
[3]薛斌党，欧宗瑛.加权合成的嵌入式隐Markov模型人脸识别[J].大连理工大学学报，2002（05）：32-33.
[4]张引，潘云鹤.工程图纸自动输入字符识别的二维隐形马尔可夫模型方法[J].计算机辅助设计与图形学学报，1999（09）.
[5]D.Keysers，C.Gollan，and H.Ney.Local Context in Non-linear Deformation Models for Handwritten Character Recognition[J].In ICPR 2004.International Conference on Pattern Recognition，2004.
[6]D.Keysers，C.Gollan，and H.Ney.Classification of Medical Images using Non-linear Distortion Models[J].In BVM 2004.Bildverarbeitung für die Medizin 2004，2004（03）：366-370.
关键词：危险品；混沌理论；风险分析；路线选择
中图分类号：F253.9 文献标识码：A 文章编号：1008-4428（2016）10-23 -03
一、引言
随着社会经济的发展，危险品运输已经成为社会经济活动中的一个重要组成部分。危险品运输过程不仅是企业自身的生产运作问题，而且影响到环境、工程、经济、社会以及政治等诸多方面，因此危险品选线问题（即确定危险品的运输路线）通常是一个双目标决策问题：政府管理部门追求的是尽可能减少公共风险，而运输供应商则关心如何降低运输成本。因此，危险品运输选线问题成为企业、政府及国内外学者高度关注的问题之一。
国内已有关于危险品选线问题的研究，可分为定性研究和定量研究两类：定性研究多集中在建立优化指标体系并进行综合评价方面，而定量研究多集中于特定几条线路的风险评价。任常兴、吴宗之（2008）基于危险品道路运输风险分析辨识最优的运输路径，以道路运输事故率、影响人数、影响人员风险、环境风险、运输距离和运输时间6个指标，确定具体起点-终点之间危险品运输的有效路径，采用带目标权重系数的Pareto-最优路线算法寻找多个满足要求的有效解；马昌喜（2009）研究了不发达网络环境下危险品公路运输路径决策问题，在构建危险品公路运输路径决策指标系统的基础上，建立了危险品路径决策的BP神经网络模型；杨信丰，李引珍等（2012）为了增加城市危险品运输路径的实用性，对侧重于多属性时间依赖网络的城市危险品运输路径优化问题进行了研究。项曙光、焦巍（2013）等提出了基于模糊HSE评价的多目标反应路径综合方法，全面考虑HSE因素，形成了HSE指标结构，通过设定指标的隶属度函数，建立模糊推理系统，应用层次分析法确定指标的权重因子，形成模糊评价方法。冯艳红、刘建芹、贺毅朝（2013）针对萤火虫算法在全局寻优搜索中收敛速度慢、求解精度低、易陷入局部极值区域等缺陷，提出一种基于混沌理论的动态种群萤火虫算法。
国外相关研究多集中于危险品道路运输路径优化模型的建立及其算法研究。Erkut、Verter等（1998）从上世纪就开始从事危险品道路运输风险定量分析的研究，认为人口暴露聚集区是平面两维结构而不是平面中一点；Serafini（2006）建立了危险品路径选择问题的双目标模型，并扩展了适用于较大网络的动态规划模型。Martin（2009）认为危险品路径的选择很大程度上是根据各路段的风险来进行的，只根据路段上的事故发生率来评价路线风险过于片面，因此在研究中引入了危险品事故率、路段事故率和工作事故率三个指标来评价风险；Bhukya、Somayajulu（2011）将混沌理论运用于DNA搜索多模式匹配算法，在初始条件产生及其细微的变化后，随着时间的推移，最后的结果产生了巨大的差异，对多模式匹配算法的研究具有重要的借鉴意义。Abbas Mahmoudabadi等（2014）主要是运用模糊理论，基于不同风险属性的优先级确定目标函数，建立危险品路径选择模型。
综上所述，已有研究大多基于静态风险因素结合相关优化理论与算法进行研究，而对于动态条件下运输路径选择研究较少。本文针对危险品选线问题，将混沌理论运用到其中，主要阐述三个主要部分：第一部分是基于混沌理论的道路交通事故动态行为研究，时间限定在一个年度范围内，根据危险品在运输过程中的混沌特性，将危险品运输过程中存在的风险分为事故、人口、环境和应急设施四个因素。第二部分根据专家意见法（德尔菲法），收集行业内专家对上述的风险因素的意见，并运用三角模糊数法将它们转换为确切的数值。第三部分是建立基于混沌理论的危险品选线模型，并结合案例验证结果的正确性。本文创新之处是将混沌理论应用于危险品运输路径选择问题，同时结合了风险分析对各路段存在的风险因素进行研究，建立成本和风险的多目标模型，最后用一个算例验证结果的正确性。
二、混沌理论与交通流
美国气象学家Edvard Lorenz在1963年提出了混沌理论的概念，一些在非线性系统中突然、戏剧性的变化可能会引起复杂的后果叫做混沌理论。如果一个非线性系统对初始条件表现出敏感的依赖，那么它就被认为是混沌的，即初始条件出现很微小的差异，最终输出结果则可能产生非常巨大的变化。混沌理论通常适用于短期预测，已被广泛地应用于多个科学领域，特别是在交通流理论方面。混沌理论是一种兼具质性思考与量化分析的方法，用以探讨动态系统中无法用单一的数据关系，而必须用整体、连续的数据关系才能加以解释及预测的行为。
交通流中存在混沌现象这一事实已经被众多学者的研究从多角度所证实。李洪萍、裴玉龙（2006）通过分析现有交通流预测方法，在此基础上提出了一种基于混沌理论的交通流短时预测方法，利用基于小数据量的Wolf改进算法计算了流率序列的最大Lyapunov指数。将基于Lyapunov指数的一维预测模式具体化，建立了交通流短时预测模型，并对模型进行了改进，改进后的预测结果具有较高的精度。
Lyapunov指数是衡量系统动力学特性的一个重要定量指标，它表征了系统在向空间中相邻轨道间收敛或发散的平均指数率。指数为正意味着在系统相空间中，无论初始两条轨线的间距多么小，其差别都会随着时间的演化而成指数率的增加以致达到无法预测。指数越大，说明混沌特性越明显，混沌程度越高。公式（1）是用来确定Lyapunov指数的最大值λmax，
由于对交通行为的良好适应性，Logistic映射被广泛应用于设定选线问题的风险因素，公式（2）为一般的Logistic映射公式，
三、 基于混沌理论的多目标模型
根据已有的研究文献可知，道路交通事故中存在显著的混沌行为，将风险因素通过模糊语言变量转换成确切值，结合道路网各条边（分段路线）的事故率，把运输风险和运输时间的优先顺序组合作为目标函数的衡量标准，在迭代过程中更新风险因素，同时考虑不同风险和运输时间的优先级。迭代次数取决于该时间段内代表当地专家意见的问卷调查结果。如果模糊语言变量是基于一年的基础上，那么迭代次数应设置为365。如果是基于半年的基础上，迭代次数应设置为180，让所有的路径运行此过程并比较，列出出现最频繁的路径组合，即为在考虑风险和运输时间条件下危险品运输的最佳路径。
假设所研究的道路网为由节点i，j的各条连线（i，j）所组成的图形G，Ns为运输起点的集合，Nd为运输终点的集合，第一层次的目标函数风险最小化如公式（3）所示：
式中Rsd表示从出发地s到目的地d的危险品运输量，Wsd表示最频繁路径所有边的初始运输风险和运输时间优先级的总和，其中s、d分别属于集合Ns、Nd。
式中Qs表示出发地s所供应危险品运输量的最大值，Qd表示目的地d所需求危险品运输量的最小值。第二层次的目标函数如公式（6）所示：
式中Ksd（t）表示经过t次迭代后，所有边的运输风险和运输时间加权后的总和，Pij（t）表示边（i，j）的初始风险，Pr表示其优先级，同理TTij表示边（i，j）的初始运输时间，Pi表示其优先级，Pr+Pi=1意味着运输风险和运输时间的优先级呈负相关。
经过t次迭代后，若边（i，j）在目标函数被选中，则Xij（t）=1，否则为0。
式中SG（t）表示根据全道路网的事故得到的事故率，MQij（t）表示利用算法把模糊语言变量转换而得到边（i，j）的确切风险值。
公式（9）、（10）是一维Logistic映射公式，参数K1、K2根据均方误差最小化准则估算得到。
四、案例分析
以M省交通路网为例，每一个路段的风险因素评测主要从四个方面：事故、人口、环境和应急设施。事故因素由当地专家对该路段上碰撞事故率的意见得到，人口风险对应发生危险品运输事故可能影响范围的人口密度，环境风险是与影响周围环境有关的风险，比如危险品泄漏后附近的河流、空气等受污染程度，应急设施风险则是关于路线上应急设施的建设情况，如桥梁或隧道可能会对危险品事故发生后的救援产生影响。由当地专家给出包含上述成分的语言变量，分为五个不同程度的级别：安全、中等安全、一般、中等风险和高风险，并根据模糊层次分析法（FAHP）得出具体的风险值。
对于路网中的每一个边，都包括事故、人口、环境和应急设施四个风险因素，确定决策者将要使用的五个语言变量，根据三角模糊数（TFN）分配给每个变量的值如表1所示。
根据模糊层次分析法的理念，将风险因素作为运输过程中的决策指标，即事故（C1）、人口（C2）、环境（C3）、应急设施（C4），五位专家作为决策者（P1，P2， …，P5）填写调查问卷，每个语言变量的标准权重和由专家意见法得到每个标准的权重分别如表2、表3所示。
以M省道路网中一条边为例，五位专家根据风险的四种因素语言变量提出自己的意见并打分，利用程度分析方法将每个风险的组成部分的三角模糊数计算加总，显示在末行。利用重要标准的权重计算风险数值，得到最大和最小风险值分别为0.8376和0.3965，归化到此边的风险平均值为0.7680。
结果表明，在混沌模式风险条件下选择长路径和短路径而得到最终结果之间具有明显的差异。本文所提出的方法在较长路径中比较短路径中效果更加显著，主要原因是较长线路的可选路段相对多，运输过程中不确定性更大。
五、总结
在本文的研究工作中，同时考虑到了运输风险和运输时间因素，其中风险由事故、人口、环境和应急设施四部分组成。由于缺乏道路交通事故的数据，运用程度分析方法将语言变量转换成对应道路网的边的确切风险值。对一个包括50个节点及若干个边的省级道路网络进行分析研究，同时对实验数据中存在的混沌现象进行了检验，验证了交通事故的混沌特征。然后运用危险品动态变量和混沌理论的基本原理相结合，建立不同风险和时间优先级的数学模型。根据一维Logistic映射方程，每迭代一次就更新动态风险的优先级。
建议以后研究危险品选线及优化问题时，可以加上诸如天气条件和交通状况等更多因素进一步深入研究，为决策者提供更加完备、合理的决策建议。
参考文献：
[1]马昌喜.危险品公路运输路径决策方法研究[D].兰州交通大学， 2007.
[2]任常兴，吴宗之，李晋.基于风险分析的危险品道路运输多目标Pareto最优选线[J].中国安全生产科学技术， 2008， 4（6）： 9-13.
[3]马昌喜.不发达网络环境下基于神经网络的危险品公路运输路径决策[J].现代交通技术， 2009， 6（1）： 84-86.
[4]杨信丰，李引珍，何瑞春，马昌喜.多属性时间依赖网络的城市危险品运输路径优化[J].中国安全科学学报， 2012， 22（9）： 103-108.
[5]项曙光， 焦巍， 孙晓岩，等. 基于模糊HSE评价的多目标反应路径综合方法[J]. 化工学报， 2013， 64（12）：4330-4334.
[6]冯艳红， 刘建芹， 贺毅朝. 基于混沌理论的动态种群萤火虫算法[J]. 计算机应用， 2013， 33（3）：796-799.
[7]Erkut E， Verter V. Modeling of transport risk for hazardous materials[J]. Operations Research， 1998， 46（3）： 625-642.
[8]Bhukya R， Somayajulu D V L N. 2-Jump DNA Search Multiple Pattern Matching Algorithm[J]. International Journal of Computer Science Issues， 2011， 8（3）.
[9]P. Serafini， Dynamic programming and minimum risk paths[J]， European Journal of Operational Research， 2006， 175（8）：224-237.
[10]Martin Trépanier， Marie-Hélène Leroux. Cross analysis of hazmat road accidents using multiple databases [J]. Accident Analysis Prevention， 2009， 41（3）： 1192-1189.
[11]Abbas Mahmoudabadi， Seyed Mohammad Seyedhosseini. Developing a chaotic pattern of dynamic Hazmat routing problem [J]. IATSS Research， 2014， 37（7）：110-118.
[12]Abbas Mahmoudabadi， Seyed Mohammad Seyedhosseini. Solving Hazmat Routing Problem in chaotic damage severity network under emergency environment[J]. Transport Policy， 2014， 36（5）： 34-45.
[13]任常兴，吴宗之.危险品道路运输风险分级指数法研究[J].安全与环境学报， 2006， 6（4）： 126-129.
[14]G.L.L. Reniers， W. Dullaert. A method to assess multi-modal Hazmat transport security vulnerabilities：Hazmat transport SVA [J]. Transport Policy， 2013， 28（6）： 103-113.
[15]李洪萍，裴玉龙.基于混沌理论的交通流短时预测模型[J].昆明理工大学学报：理工版， 2006， 31（5）：95-99.
[16]冯艳红，刘建芹，贺毅朝.基于混沌理论的动态种群萤火虫算法[J].计算机应用， 2013， 33（3）： 796-799.
[17]吕品.基于改进VRP模型的危险品配送路径优化及其求解研究[J].中国安全生产科学技术， 2011， 7（11）： 87-91.
作者简介：
关键词：逆向工程；点云数据处理；CAD建模；汽车轮毂；实物模型数字化
中图分类号：TP391 文献标识码：A 文章编号：1009-2374（2011）36-0068-02
逆向工程是消化吸收并改进先进技术的一系列工作方法和技术的总和，它是以设计方法学为指导，以现代设计理论方法技术为基础，运用各种专业人员的工程设计经验，知识和创新思维，对已有新产品进行解剖、深化和再创造，是已有设计的设计。逆向工程设计技术的应用对提高我国工业产品设计水平，缩短设计周期，增强我国产品在国际市场上的竞争力有着重要的意义。
一、实物模型数字化
实物模型数字化是逆向工程中很关键的一步，数字化模型能否准确反映实物模型的结构特点，直接影响后续的建模质量。因此，本文引入了COMET测量系统，COMET测量扫描系统是利用光栅投影法，通过非接触方式获得物体表面数字化点云数据，是一个快速而高精度的测量和扫描设备，使用COMET测量系统测量零件表面，操作流程：表面着色处理D确定测量方法D启动软硬件D调整测量角度和距离，并设置参数D扫描零件，获取完整表面数据D数据输出。
二、点云数据预处理
数字化阶段获得的点云数据应当经过适当的处理后才能用于后续的曲面建模。由于测量设备或是测量对象的原因，往往不能一次完成整个测量过程，需要将多个测量结果进行拼接才可获得实物的整个数字化模型。
首先，在逆向扫描过程中，分块扫描得到的点云数据可看成一个具体本身固定坐标系的实体。所以，逆向工程的点云数据对齐问题可以看作是不同三维实体的坐标变换问题，即根据事先指定的最优匹配算法，通过坐标变换，将分块扫描得到的点云进行对齐。
其次，无论是使用接触式测量还是非接触式测量，在测量产品表面数据时，都会引入数据误差，尤其是有尖锐边的产品边界附近的测量数据。因此，在利用点云数据重构模型前必须对点云进行过滤。
数据精简也是逆向工程中的关键技术，伴随非接触式测量技术和测量设备的发展，我们可以很方便地获得复杂形状零件的表面数据。缺点是点云的数据量非常大，这就需要大量的存储空间，同时在数据处理过程中，运行速度很慢，降低工作效率。因此，有必要在保持一定精度的前提下对点云进行精简，去除大量多余的点，只保留能够反映曲面形状的点即可，这即是点云精简过程。
三、CAD模型
三维CAD模型的重构是逆向工程的另一个核心和主要目的，是后续产品加工制造、快速成形、工程分析和产品再设计的基础。三维CAD建模的理论，包括曲面建模方法、曲线和曲面的数学模型及拟合，应用CATIA软件是实现曲面重构一个重要手段。
四、工程实例
当前，我国汽车工业飞速发展，越来越多的新车型被引入国内。同时，国内的汽车公司也在国外车型的基础上大力自主研发设计新车型。因而，汽车的开发周期越来越短，汽车工业正逐渐由“大批量、单一车型”向“小批量，多种车型”制造模式转变，在这种情况下，发展先进的制造技术，获取或建立CAD模型具有重要的意义。
本文以研究汽车车轮毂盖为例，将对某汽车车轮毂盖进行数据扫描，并通过逆向工程手段实现的原有产品的逆向建模，以方便进一步的设计或模具制作，并可缩短其产品的开发周期。
（一）数据获取
测量之前，首先应检测轮毂盖表面是否光泽，由于我们所测量的轮毂盖表面的颜色是深灰色，表面颜色太深，反光能力差，应在其表面均匀地喷上白色反光喷剂，以便其有更好的反光效果。轮毂盖曲面类型多，需多次测量，所以我们还需在被测物体的表面贴上参考点，这样拼合点云的时候，多次测量得到的不同的点云就可以根据参考点实现自动拼合，将测量得到的数据以IGS格式输入到CATIA软件中。
（二）数据预处理
1．噪点删除。由于扫描仪的误差以及测量过程中人为误差的存在，使得扫描最终得到的点云包含了大量的噪点，其将会严重影响后续的反求建模，又因为系统无法精确识别误差的存在，所以需手动删除。在CATIA中，利用“remove”工具进行删除，如图1（a）所示。
2．点云精简。点云在消除了噪声点后，其中仍包含了大量的冗余点，这些冗余点的存在不但增加了计算机的负荷，还影响数据处理和模型重建的速度，需在精度允许的范围内采用一定的算法对其进行精简。所以为了计算机运算速度的提高，CATIA提供公差球和弦高差两种点云数据精简方式。在此因曲面曲率变化原因选用弦高差精简方式，其结果如图1（b）所示。精简后，点云的信息如下：
Number of Data Points： 59997
Units：mm
Min X=239.9893 Max X=505.7328
Min Y=-180.0058 Max Y=97.2953
Min Z=172.3559 Max Z=833.7889
3．网格化。在经过上述处理后便可以对其进行三角网格化，以便对其曲率进行分析，同时更好地观察各种曲面的特征。
4．网格面曲率分析。点云分割是构建曲线、曲面的基础，分块方式直接影响后续的曲面构造方式、曲面的拼接和缝合效果。数据分块分的好，将使曲面的重构变得简单，可以得到高质量的曲面。
（三）轮毂盖CAD模型重构
任何一个产品的模型建立之前，都必须有一定的基准，这样才能建立产品准确的拓扑关系，也才能准确地进行后续的加工。对于此轮毂盖同样为了反求建模的准确性以及方便性，必须先建立其基准，即建立坐标系，并使其一坐标轴通过轮毂盖的旋转中心。
特征线的构建是曲面重构的基础，也是最为关键的环节。由前面分析可知，此轮毂盖主要由两个旋转曲面以及若干相同的扫描曲面组成。对于旋转曲面，只要重构出它们的截面特征线即可。基本曲面重构完成之后，只需对其进行进一步的处理操作，如加厚、圆角等。最终进行表面质量的检查。最后完成整体模型，并对其进行斑马纹的检查，如图2所示，其质量足以满足操作者的要求。
五、结语
在产品开发的今天，建立产品的数字化模型是产品设计的中心内容。在产品数字模型建立中，作为实现创新的手段，逆向工程技术的应用越来越受到重视。本文的研究工作丰富了产品造型设计的理论和方法，将促进逆向工程在产品设计中的应用和推广。
参考文献
[1] 王霄．逆向工程技术及其应用[M]．北京：化学工业出版社，2004．
[2] 金涛，童水光．逆向工程技术[M]．北京：机械工业出版社，2003．
[3] 许志龙．逆向工程中多视觉点云数据拼合技术[J]．设计与研究，2006，（7）．
[4] K H Lee H Woo，T Suk. Point Data Reduction Using 3D Grids[J]．International Journal of Advanced Manufacturing Technology，2001，（18）．