匹配算法论文十篇

匹配算法论文篇1

【关键词】深度挖掘匹配算法 毕业论文管理 应用

在毕业论文管理工作不断加强的情况下，注重管理模式的更新和合理选用，提高匹配算法的针对性，才能真正提高高校教务管理水平。因此，对深度挖掘匹配算法在毕业论文管理中的应用有比较全面的了解，才能为高校教务管理工作提供可靠参考依据。

1 深度挖掘匹配算法的相关分析

根据深度挖掘匹配算法在毕业论文管理中的应用情况进行全面分析来看，其主要包括如下两个方面：

1.1 志愿自动匹配算法的相关分析

对学生和课题的选择关系进行合理分析可知，两者的最优、最大匹配，最好是根据学生的实际情况量身定做，才能真正实现课题与学生的最完美匹配。因此，教师提出相关题目时，需要对学生的情况、特性和要求等进行全面分析，才能在学生对课题的特性、关联性等有一定了解的情况下，提高课题与学生的匹配概率，最终让学生选定最合适的课题。在实践过程中，志愿自动匹配算法的合理运用，需要根据毕业论文的管理流程，从教师出题开始。一般情况下，教师应该先提出大题让学生自由选择，在匹配学生确定好以后将大题分成几个小题，从而将每个小题分配给合适的学生。在这种情况下，教师设定的课题需要从修读课程达到的分数、难度、所属类别等多个方面确定，并从教务管理系统中获取学生的成绩和选题积分点等，才能根据分数线来判定学生是否符合相关选题。其中，选题的难度在简单、一般、难、很难和非常难几个等级，对应的成绩是及格、良好、优秀、极好。在实际进行选题时，学生可以根据自己的情况选择三个题目作为志愿，以在系统完成匹配后，自定将题目下发给学生。在实践过程中，初始化志愿显示的是学生的第一志愿，在经过while、if、else、break、continue等流程后，系统会将题目和学生进行适当分类，以确保题目与学生的匹配最合理、最科学。由此可见，志愿自动匹配算法是优先对具有课题相关能力的学生进行匹配的，在学生人数低于匹配数量的情况下，可继续为积分点高、能力稍差的学生进行匹配，对于确保课程成绩与积分点的完美结合有着极大影响。

1.2 调剂学生算法的相关分析

在经过上述算法进行匹配后，根据学生的实际情况进行深层挖掘，可以实现课题与剩余学生的完美调剂。因此，对上述阶段中匹配失败的学生志愿所选的教师、课题类别、难度等因素进行深度挖掘，并将搜索结果作为匹配课题的依据，才能在缩小搜索范围的情况下，找到与剩余学生最合适的课题。如果出现相近课题较多的情况，则需要有学生、工作人员共同协商，以确定最终和最适合学生的课堂。在实践应用中，调剂学生算法的运用需要对需要调剂的学生进行合理分析，并通过if、else、return、while、continue、else等多个流程，才能真正匹配出最适合学生的课题。

2 深度挖掘匹配算法在毕业论文管理中的实际应用

根据深度挖掘匹配算法的实际应用来看，在毕业论文管理中学生可以了解到最适合自己的课题信息，教师可以根据学生的积分点和成绩等确定课题，从而避免选择某一课题的学生过多或过少的情况出现，对于提高第一志愿自动匹配成功率有着极大作用。因此，在实际应用中，注重教师、课题类别、难度的合理设定，确保它们的排序科学，将课堂与学生的匹配关系看作是二分图，并且，每个学生可以选择的课题有三个，系统可以根据学生的实际情况进行自动匹配，最终深度挖掘与学生志愿匹配的课题。例如：志愿自动匹配和调剂学生的总数都为102人，通过深度挖掘匹配算法匹配成功的人数分别为72人和90人，成功率达到了70%、88%。在不使用任何算法进行匹配的情况下，两者的成功率是52%左右。由此可见，在毕业论文管理系统中，深度挖掘匹配算法在科学应用，可以为教务管理工作提供可靠参考依据，对于提高毕业论文管理工作人员的工作效率有着重要影响。

3 结语

综上所述，在深度挖掘匹配算法不断推广的情况下，其在毕业论文管理中的实际应用受到了很多教务管理工作人员的青睐。因此，充分发挥深度挖掘匹配算法的作用，提高深度挖掘匹配算法在毕业论文管理中的应用效果，才能更好的满足学生的选题需求。

参考文献

[1]冯丽慧，冯立智.数据挖掘在毕业论文成绩管理中的应用研究[J].电脑知识与技术，2012，30：7150-7153.

[2]徐章韬.用信息技术深度挖掘课程内容――以数学学科为例[J].教育发展研究，2015，12：29-33.

[3]连伊娜.深度挖掘高校档案文化内涵，更好为教育事业发展服务[J].黑龙江史志，2013，11：104-105.

作者简介

刘冰洁（1983-），女，江西省南昌市人。工程硕士学位。现为江西交通职业技术学院副教授。研究方向为大数据、系统集成、智能化技术。

匹配算法论文篇2

[关键词] 分层策略 图像匹配 序贯相似性检测算法 自适应遗传算法

一、引言

机器人的视觉导航控制是利用CCD摄像机采集路面上的图像信息，对当前图像与场景样本库中的图像进行匹配,以确定当前位置，由机器人的处理器识别出路径来控制机器人的运动方向。图像匹配算法在图像信息采集过程中起着至关重要的作用。影响图像匹配性能的主要因素不仅包括图像匹配测度，还与图像匹配快速方法相关。本文主要研究在保持较高匹配正确率的条件下，通过对算法的改进来提高图像匹配速度，从而缩短机器人反应时间。在图像匹配中，采用较多的是基于灰度的匹配算法，因为此算法匹配精度高、易于工程实现且算法已相当成熟，本文的快速算法是基于灰度匹配算法的。

二、图像的分层搜索

在保证图像匹配精度的基础上，减少数据处理的运算量，满足系统实时性要求，是图像匹配算法首先要解决的问题。分层搜索的过程是一个由粗到精的搜索过程，它的目的是减小搜索空间，进一步加快图像的匹配速度。分层的方法有很多种，本文设计了一种分层搜索算法。

把图像进行多分辨率分层处理，得到分辨率比较低和维数较小的图像。首先在分辨率较低、维数较小的图像上进行粗匹配，得到粗匹配点；然后返回到较高分辨率图像，在粗匹配点的邻域内进行进一步的精匹配，从而得到精匹配点。此过程可反复进行，直到满足系统设计精度为止。具体分层采用小波分解的方法得到一组不同分辨率的图像。本文先用小波多分辨率理论对图像进行分层预处理，然后在低分辨率图像上采用改进的序贯相似度检测算法（SSDA）进行粗匹配，得到粗匹配点后，在原始图像上对应粗匹配点的邻域内，采用平均绝对差算法(MAD)进行精匹配。

1.图像的小波分解

Mallat于1987年提出多分辨率理论，在泛函分析的框架下，统一了各种具体小波的构造方法，给出了构造正交小波基的一般方法和与FFT相对应的快速小波算法，并将它应用于图像分解和重建，成为小波理论与应用上的一个突破性进展。

小波的选择对图像分解来说是一个至关重要的问题。对于同一个问题，使用不同的小波会产生不同的结果，因此,必须结合不同的问题选择适当的小波变换。哈尔小波是正交小波变换中最简单的一个小波函数,它的优点在于算法简单、速度快,缺点是其分解的低频图像是对上一尺度低频图像平均得到的，所以图像的边缘信息损失较为严重,但由于本文采用的是灰度图像匹配，边缘信息的损失对其影响不大,而且为了加快图像分解速度,采用的小波变换必须尽量简单快速,因此选用的小波变换为哈尔小波。

2.改进的序贯相似度检测算法

序贯相似度检测算法可以用来有效地减少单次匹配中的计算量, 但算法本身没有抗干扰性能，在计算过程中没有利用图像自身的特点，采用穷举搜索，存在效率极低的问题。考虑到遗传算法在搜索问题上的优越性，本文将图像匹配问题转化为函数优化问题，采用非遍历寻优的遗传算法作为优化问题的搜索策略，把自适应遗传算法（AGA）和序贯相似度检测算法相结合，提出一种改进的快速图像匹配方法，以大幅减少计算量。

三、实验结果

将本文设计的算法应用于移动机器人视觉导航系统中，取得了满意的效果。基本的实验环境描述如下：实验场所为室内，背景不太复杂。目标物体为一个280mm×310mm×100mm的立方体纸箱，摄像机初始距离距目标物体为4.5m，图像采集分辨率设为160×128。移动机器人采用的是三星S3C44B0×32位微处理器，它使用ARM7TDMI核，最高工作在72MHz，芯片中集成了8KB Cache、配置了2MB的FLASH存储器，以及8MB的SDRAM存储器。

对序贯相似度检测算法与自适应――序贯相似度检测算法分别进行50次实验，其中自适应――序贯相似度检测算法的遗传算法群体规模为50，迭代次数为50次和150次；在此实验基础上，先用小波变换对图像进行两级分解，然后在1级图像上采用自适应――序贯相似度检测算法进行匹配，选取最后一代适应度值最高的5个位置，把它们映射到原始图像基准图上，在这5个位置的5×5领域内采用MAD 进行精匹配，最后获得真正的匹配位置。自适应――序贯相似度检测算法的迭代次数为150，实验结果的比较见下表。

从表中的结果可以看出，在遗传算法迭代次数较低时,寻优过程可能会陷入局部最优而不能跳出,增加到150次后可获得全局最优解，但匹配时间有所增加。采用150次迭代的自适应――序贯相似度检测算法进行匹配所需要的平均时间为单纯序贯相似度检测算法的平均匹配时间的18.5%。在小波分解的基础上进行的自适应――序贯相似度检测算法匹配，时间上比单纯的自适应――序贯相似度检测算法匹配又减少了将近50%。系统运行良好，跟踪目标没有出现大的偏差，基本上始终处于图像视野的中央位置，运动轨迹没有出现振荡，达到了机器人视觉导航的目的。可见基于分层的自适应――序贯相似度检测算法既具有很高的匹配速度，又保持了良好的匹配正确率。

四、结语

匹配算法论文篇3

关键词:规则匹配;并行树搜索算法;规则分解映射;平衡二叉决策树

中图分类号:TP309;TP393.08

文献标志码:A

0引言

近年来,随着Internet的不断发展,包括防火墙、路由器在内的许多网络设备都需要支持QoS,即为不同的流提供不同的服务质量保证。在这种情况下,规则匹配(即报文分类)已经成为了这些网络设备的基本功能之一。规则匹配的基本任务是:当接收到数据包时,搜索预先设置的规则集,找出数据包所能匹配的规则,并按规则定义的动作处理数据包。对于防火墙而言,规则定义的动作通常是放行或者丢弃。一个数据包有时能同时匹配两条或两条以上的规则,且规则间的动作互不一致,这种情况称为规则冲突。常见的解决方案是给不同的规则赋予不同的优先级。通常,规则在规则集中的位置代表了它的优先级。

随着链路速度的提高,特别是随着规则个数的增多,规则匹配已经成为许多网络设备的性能瓶颈,这引起了研究人员的广泛关注,并有不少规则匹配算法被提出[1]。

现有的众多规则匹配算法可以分为以下几类:基于TCAM(TernaryContentAddressableMemory)的匹配算法[2-3],基于哈希表的匹配算法[4-5],基于决策树的匹配算法[6-7],基于Trie的匹配算法[1,8-9],以及基于分治思想的匹配算法[10-11]。

常见的基于TCAM的匹配算法的优点是匹配速度快,时间复杂度通常为常数。但由于只支持以前缀形式表示的规则,能量消耗过大,价格高昂,TCAM的使用范围受到了很大的限制。

对于基于哈希表的匹配算法而言,这类算法通常能提供良好的最坏情况下的性能保证,但其平均性能往往较差。而基于决策树的匹配算法,正好相反。这类算法往往不能提供良好的最坏情况下的性能保证,但其平均性能通常较好。另外,基于决策树的匹配算法还有一个严重的缺点,即需要维护一棵庞大的决策树,空间开销过大。

基于Trie的匹配算法,通常只支持以前缀形式表示的规则集,且不能提供良好的最坏情况下的性能保证。而基于分治思想的匹配算法,要么时间复杂度较大,要么空间使用量较大。这类算法通常只适用于中小规模的规则集。

在众多的规则匹配算法中,文献[12]提出的并行树搜索(ParallelTreeSearch,PTS)算法是较为优秀的算法之一。PTS采用文献[9]提出的二阶段匹配机制:第一阶段对源IP地址前缀和目的IP地址前缀组合进行匹配;在第二阶段,根据第一阶段的匹配结果,顺序搜索数量有限的规则,以确定数据包能匹配的优先级最高的规则。PTS算法的主要工作在于对第一阶段进行改进,将源IP地址前缀和目的IP地址前缀组合组织成一棵平衡二叉树,以加快对数据包的处理。

虽然PTS算法在一定程度上对文献[9]算法进行了改进,但是PTS算法仍然存在以下两方面的问题:1)在构建平衡二叉树的过程中,PTS算法需要建立大量的externalnodes,这不仅影响规则匹配算法的预处理时间,增加了空间使用量,而且降低了数据包匹配效率;2)PTS算法只支持源IP地址分量和目的IP地址分量以前缀形式表示,而不支持它们以范围形式表示。由文献[1]可知,一个以范围形式表示的d维规则,最坏情况下,将转换成(2w-2)d条以前缀形式表示的规则。其中,w是规则分量的域长。例如,IPv4的IP地址分量,其w等于32。

匹配算法论文篇4

关键词:双目立体视觉;区域相关;立体匹配;标准测试图

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

文章编号:1004-373X(2009)12-068-03

Improvement of Regional Related Match Algorithm for

Binocular Stereo Vision and Its Implementation

HE Renjie

(Electronics and Information School,Northwestern Polytechnical University,Xi′an,710129,China)

Abstract:Match algorithm is one of key techniques in the binocular stereo vision system.The similarity functions,the regional related match algorithms for Binocular stereo vision are discussed and the algorithmic complexity is analyzed.Moreover,a new improved regional related match algorithm by sliding pattern plate is proposed to decrease the matching time and a test software is designed by using VC++ and OPEN-CV.A number of experiments are carried out through the two-camera system and the standard test images as well as practical sense images.The analytical and experimental results show that the improved method is effective and its matching time is decreased greatly.

Keywords:binocular stereo vision;regional related;stereo match;standard test image

0 引 言

立体视觉是计算机视觉的一个重要分支,主要研究如何借助成像技术从图像中获取场景中物体的三维信息[1-3] 。立体视觉的基本方法是从两个或者多个视点去观察同一场景,获得在不同视角下的一组图像;然后通过三角测量原理获得不同图像中对应像素间的视差,并从中获得深度信息,进而与平面信息整合形成立体图像。立体匹配是立体视觉算法中最重要也是最困难的部分。

根据匹配基元的不同,现有的立体匹配方法可大致分为三类:基于特征的匹配[4,5],基于区域的匹配[6]和基于相位的匹配[7]。

本文重点研究双目视觉立体匹配中基于区域的局部匹配算法,对基于SAD(Sum of Absolute Difference)的区域匹配算法通过模板滑动进行了改进。经分析和多次实验结果表明,该改进算法具有有效性和快速性。

1 双目立体视觉区域局部匹配的理论基础

1.1 相似性测度函数

匹配算法的实质就是估计待匹配点和候选匹配点之间的相似性程度,评价这种相似性程度度量方法有多种。由于单个像素点所包含的信息太少,因而只依据单个像素点是的信息建立度量方法可靠性较差。为了提高相似性度量方法的可靠性,一般需要在匹配点上的一个小邻域内的像素点集合中进行。

表1列出了目前几种主要的相似性测度函数[6]。其中,IL(x,y),IR(x,y)分别代表左右图像中像素坐标(x,y)处的灰度值;IL(x,y),IR(x,y)分别表示左右图中以坐标(x,y)为中心,在窗口范围U内像素灰度的平均值。由于SAD相似性测度函数在时间以及匹配质量方面较其他测度函数更具有优势,且实现较简单[8]。这里研究选择SAD作为局部相关匹配算法的相似性测度函数。

1.2 局部相关匹配算法原理

局部相关匹配算法是以基准图像中待匹配点为中心像素来创建一个大小为n×n的矩形窗,由该窗口内的像素灰度分布来表征该像素。在第二幅图像中,沿极线在视差范围内取出与基准点邻域同样大小为n×n的像素邻域,依次与匹配点的窗口进行比较,最大相似性对应的点就是最佳匹配。整个匹配过程如图1所示。

表1 几种相似性测度函数

名称公式

SAD∑(i,j)∈U|IL(x+i,y+j)-IR(x+dx+i,y+j)|

ZSAD∑(i,j)∈U|[IL(x+i,y+j)-IR(x,y)]-

[IR(x+dx+i,y+j)-IR(x+dx,y)]|

SSD∑(i,j)∈U[IL(x+i,y+j)-IR(x+dx+i,y+j)]2

ZSSD∑(i,j)∈U[IL(x+i,y+j)-IL(x,y)]-

[IR(x+dx+i,y+j)-IR(x+dx,y)]2

SSD-N∑(i,j)∈U[IL(x+i,y+j)-IR(x+dx+i,y+j)]2∑(i,j)∈UIL(x+i,y+j)2∑(i,j)∈UIR(x+dx+i,y+j)2

SCP∑(i,j)∈UIL(x+i,y+j)IR(x+dx+i,y+j)

图1 局部相关算法原理示意图

1.3 局部相关匹配算法的时间复杂度

在图1(a)中坐标为(x,y)的像素点,算法要计算图1(b)中所有相关像素的相似性。根据极线约束以及视差约束,在图1(b)中只需计算同一极线上,视差范围内的像素相似性即可,需要的计算量为:

T(x,y)=dmaxn2(1)

式中:n为正方形窗口边长;dmax为最大视差。设W为图像的宽度;H为图像的高度,对于整幅图片,全部相似性的计算量为:

T=∑0≤i

易知,局部相关匹配算法的时间复杂度为O(WHdmaxn2)。

1.4 局部相关匹配算法的改进

若假设匹配窗口的边长为2n+1,对于每行像素,其相似性测度函数为P(x,y,d)=∑ni=-n|IL(x+i,y)-IR(x+i+d,y)|;在模板向右滑动时,P(x+1,y,d)可由之前的计算结果得到,有迭代公式:

P(x+1,y,d)=P(x,y,d)+[|IL(x+n+1,y)-

IR(x+n+1+d,y)|-|IL(x-n,y)-

IR(x-n+d,y)|](3)

即在模板滑动时,不需要重新计算整个窗口的SAD,而只需计算新的一列SAD。分析可知,改进后算法的时间复杂度由O(WHdmaxn2)降为O(WHdmaxn),算法实时性有了较大提升。

2 双目立体视觉区域局部匹配算法的实现

2.1 实验环境

该研究的实验主要是通过计算机编程实现区域局部匹配算法,并在双相机系统上利用标准和实际场景图像进行验证性实验的。以VC++ 6.0及OPENCV为编程环境,完成验证软件设计。

该研究的验证实验使用了西安交通大学系统工程所的实验设备(如图2所示)。两只摄像机平行放置,其位置姿态参数已由标定结果给出,如表2所示。

图2 试验系统

表2 相机标定参数表(以像素为单位)

参数指标左相机右相机

焦距699.85696.15

相机中心[392.34 283.94][389.26 308.18]

畸变[-0.270 20 0.454 48][-0.239 75 0.256 22]

旋转角/radα=0.013 77,β=0.001 07,γ=0.000 38

相对位移/mmt1=87.921,t2=1.205,t3=4.980

摄像机与处理计算机之间通过双1394总线连接,计算机中配备2块64位PCI-1394卡,以适应摄像机高速图像流的要求。摄像机的主要参数如表3所示。

表3 摄像机参数

摄像机特性参数

CCD传感器Sony Progressive Scan CCDs

CCD最大像素1 624×1 224

像素大小4.4 μm×4.4 μm

支持图像大小320×240(30),640×480(30),800×600(30),1 600×1 200(15)

快门0.01~66.63 ms

图像输出方式双1394总线输出

2.2 软件设计流程图

系统算法流程图如图3所示。

图3 系统算法流程图

2.3 实验结果

部分实验结果如图4所示。

图4 实验结果

由图4可知[10],实验得到的图片较好地完成了对现实场景中的匹配,可以较直接地从所得视差图中获得物体的深度信息。

同时,图像边缘处的匹配精度受到图像边界的影响,误差较大,真实场景图片中噪声较大,导致误匹配较多。如何减少误差,提高精度是现在和今后重点考虑的问题之一。

3 结 语

这里对双目立体视觉中的区域局部匹配算法进行讨论,对现有SAD算法进行了改进,较显著地提高了匹配速度。在实验平台上较好地完成了对标准图像及现实场景图像的视差图获取,验证了算法的有效性和快速性。

参考文献

[1]章毓晋.图像工程(下册)图像理解[M].2版.北京:清华大学出版社,2007.

[2]何明一,卫保国.数字图像处理[M].北京:科学出版社,2008.

[3]游素亚.立体视觉研究的现状与进展[J].中国图像图形学报,1997,2(1):1-2.

[4]Hajar Sadeghi,Payman Moallem,Monadjemi S A.Feature Based Dense Stereo Matching using Dynamic Programming and Color[J].International Journal of Computational Intelligence,2004,4(3):179-186.

[5]高峰,文贡坚,吕金建.一种准自动高精度图像配准算法[J].现代电子技术,2007,30(6):56-59.

[6]Kuk Jin Yoon,In So Kweon.Adaptive Support-Weight Approach for Correspondence Search[A].APRIL[C].2006,28(4):650-655.

[7]徐奕,周军,周源华.立体视觉匹配技术[J].计算机工程与应用,2003,39(15):388-392.

[8]Cyganek B,Borgosz J.A Comparative Study of Performance and Implementation of Some Area-based Stereo Algorithms[A].CAIP[C].2001,21(24):709-716.

匹配算法论文篇5

关键词：动态规划；模板匹配；特征距离矩阵

DOIDOI：10.11907/rjdk.171142

中图分类号：TP312

文献标识码：A 文章编号：1672-7800（2017）06-0037-03

0 引言

在计算机领域，常需要将实验数据与预先设定好的模板进行匹配。图像处理领域中的图像检索、图像分割、图像拼接、图像检测、视频编码等，就需要运用到模板匹配技术。模板匹配技术在图像处理领域的具体应用可以简单分为两大类：基于特征点的匹配技术、基于像素灰度的匹配。基于特征点的匹配往往被更高级的机器视觉类任务采用，而在图像处理中，基于特征的匹配方法由于抽取的点、线、特征子等特征容易受到视角变换、遮挡等问题的干扰，会影响到最终匹配结果的质量，同时特征抽取方法的时间复杂度较高，对于实时性是一个挑战。基于像素灰度的模板匹配方法，只需要设定好匹配的模板尺寸与遍历方式，算法简洁、稳定性高，适合图像处理与计算机视觉问题中的底层预处理。但其也存在一些缺点，如噪声、光照引起的灰度变化，且运算数据量大，基于像素灰度的匹配算法也无法避免图像数据与模板匹配过程可能带来的高复杂度问题。

迄今为止，模板匹配技术已经被广泛应用到图像处理的实际问题中，并取得了一系列成果。例如，王倩倩[1]将模板匹配问题应用到藻类图像的识别问题中，李厚军[2]将模板匹配问题应用到眉毛的识别问题中，陈莹[3]将模板匹配方法用于增强微光图像，王正等[4]将模板匹配引入到图像编码中的调色板更正上，提高了图像编码效率，王志衡，郭超等[5]将模板匹配方法应用到了新闻图像字母行切分之中，张盼盼[6]等将模板匹配方法应用到了数字识别过程中，陈宁等[7]将该方法应用到集装箱识别与匹配的问题中。然而，采用上述方法在面临大数据量的数据时，也存在复杂度较高的问题。因此，如何进一步优化模板匹配问题有待进一步研究解决。

动态划方法（Dynamic Programming）早期诞生于运筹学，是一种迭代求解最优的方法。近年来，动态规划方法作为算法设计策略中求解最优子结构的一种重要思想，被广泛引入到计算机问题求解之中。动态规划求解计算机问题的基本思想是，将待求解问题分解成若干个结构相同的子问题，在求解过程中保存已求解子问题的答案并在后续求解过程中，有效利用之前求解的答案协助当前问题求解。由于后续问题在求解过程中已经遇到了需要之前已经求过的子问题，因此大大提高了求解效率[8-11]。可以简单地将动态规划算法分为基于线性的动态规划算法、基于树形的动态规划算法、基于区域的动态规划算法、基于背包的动态规划算法。具体采用何种动态规划方法应针对具体问题作具体分析，例如，有学者[12-13]在语音识别与动作识别等具体领域尝试采用动态规划算法尝试优化求解。但往往只是将动态规划算法应用到某一具体问题，尚未对图像处理中的模板匹配问题进行动态规划算法实现。

综上，鉴于动态规划方法的自身特性及当前图像处理在解决模板匹配问题上的不足，本文提出了一种采用动态规划解决模板匹配的方法，首先给出图像数据与模板的匹配问题，并对该问题进行符号化和相应的理论分析，此后采用动态规划的方法解决模板匹配问题，并对传统动态规划解决方法在时间复杂度上进行改进。相较于传统模板匹配方法，采用本文提出的方法可以将时间复杂度减少一个数量级。

1 问题分析与解决

图像模板匹配算法的过程可以简单归纳为：首先采用某一尺度的模板遍历所有数据（例如整幅图像），此后计算模板与模板在整个图像中所对应区域的匹配程度，最后在数据中找到与模板匹配程度最高的区域。对于一幅图像数据S而言，若图像的尺寸大小为H*W，模板T的尺寸为P*P，模板匹配算法需要在图像数据上进行遍历，并计算模板与模板覆盖区域的匹配程度，将模板覆盖到一个图像区域并计算匹配度的过程约定为一个动作。设有一组试验动作序列：V=（V0，V1，…，VM） 和一组模板动作序列T=（T0，T1，…，TN），（M>N），两组序列都满足动作的时间顺序，这里试验动作数据中的每个动作都必须出现在匹配路径中，而模板动作序列不做此要求。计算模板与图像对应位置的匹配程度，可以根据需求采取不同的度量方式，如欧式距离、光度距离与几何距离等。模板的移动可以采用Zigzag的方式实现。则上述模板匹配可以得到有效的距离矩阵，可以在该距离矩阵的基础上设计动态规划优化解决方案。这里，假设试验动作数为M=15，模板动作数为N=10。

1.1 问题符号化及分析

为了方便地表达该问题，采用3个矩阵进行存储和计算，如图1所示。一个是矩阵A，用来存放原始数据；一个是矩阵B，用来存放计算过程的局部最优值；一个是矩阵R，用来记录局部最优值所对应的路径。

1.2 问题解决

1.2.1 局部最优值计算

对于上述问题，采用动态规划思想进行解决，其基本思路如下：首先，试验动作从V0开始，由于它是第一个试验动作，前面没有其它动作，因而无论它选择哪一个模板，都可看成是当前的最优值；然后，考查第二个试验动作V1，如果V1选择的模板动作是T0，那么试验动作V0选择的模板只能是T0，这时它的最小值为a0，0+a1，0，同时在矩阵R中r0，0位置记录该局部最优值所对应的模板序号；如果V1选择的模板动作为T1，那么试验动作V0可以选择的模板是T0或T1，显然，只有取a0，0和a0，1中的最小值，与a1，1相加后可得V1在选择模板动作T1时的最优值，同时在矩阵R中r0，1位置记录该局部最优值所对应的模板序号；如果V1选择的模板动作为T2，那么试验动作V0可以选择的模板就可以是T0、T1或T2，这时，需要取a0，0、a0，1、a0，2中的最小值，与a1，2相加后可得V1在选择模板动作T2时的最优值，同时在矩阵R中r0，2位置记录该局部最优值所对应的模板序号；如果V1选择的模板动作为Tj，j=3，…9，则依次类推。

其中，k的最大值是第M层叶结点的个数。度为p的树中第i层至多有pi-1个节点（i>1），该问题求解的树的度p=3，则第M=15层至多有3M-1=315-1个结点，试验中k的最大值为16，通过分析可以得出该问题的时间复杂度为O（16*M）。

综上分析，文中给出的算法在求模板匹配的最优解时，其对应的时间复杂度为O（MN）+O（KM），即max（O（MN），O（KM））。若从p叉树的生成角度考虑，算法的时间复杂度为O（MN）+O（nodes），即max（O（MN），O（nodes））。

3 结语

针对传y模板匹配算法在应用图像处理问题时遇到的时间复杂度过高等问题，对数据与模板匹配的过程进行优化，提出了一种基于动态规划算法加以实现的方法，算法的时间复杂度为max（O（MN），O（KM））。利用本算法，可以将模板匹配过程的复杂度大大减小，也不需要对数据进行过多处理，而且程序编写简单，各方面比原算法和目前已有文献中提到的改进算法都有很大提高。

可以看出，未来无论是计算机处理领域的模板匹配问题，还是日常生活生产中经常遇到的“试验数据和事先存储好的模板动作进行匹配”及类似问题，本文所提出的算法都具有一定应用前景。

参考文献：

[1]王倩倩.基于聚类的模板匹配显微细胞图像分割算法的研究[D].重庆：重庆大学，2015.

[2]李厚军.快速模板匹配方法及其在眉毛识别中的应用[D].北京：北京工业大学，2015.

[3]陈莹.基于FPGA的微光图像增强和模板匹配研究[D].北京：中国科学院大学，2014.

[4]王正，陶品，冯立新，温江涛，杨士强.基于模板的调色板方法[J].计算机辅助设计与图形学学报，2016，28（7）：1146-1151.

[5]王志衡，郭超.基于模板匹配的新闻图像字幕行切分算法[J].北京邮电大学学报，2016，39（3）：49-53.

[6]张盼盼，张颖颖.模板匹配与八邻域分析法在数字细化预处理中的应用及比较[J].软件导刊，2016，15（5）：210-211.

[7]陈宁，王胜，黄正文.基于特征匹配的集装箱识别与定位技术研究[J].图学学报，2016，37（4）：530-536.

[8]THOMAS H CORMEN，CHARLES E LEISERSON.Introduction to algorithms[M].Second Edition.Massachusetts：The MIT Press，2001.

[9]王晓东.计算机算法设计与分析[M].第2版.北京：电子工业出版社，2005.

[10]徐孝凯，贺桂英.数据结构（C语言描述）[M].北京：清华大学出版社，2004.

[11]唐策善，李龙澍，黄刘生.数据结构――用C语言描述[M].北京：高等教育出版社，2003.

匹配算法论文篇6

关键词：双向立体匹配； 图像分割； 伪极线； 稠密匹配

中图分类号：TN919-34 文献标识码：A 文章编号：1004-373X(2011)24-0099-04

Realization of Two-way Stereo Matching Algorithm

XIA Gui-hua, LI Zhi-gang, CAI Cheng-tao

(Harbin Engineering University, Harbin 150001, China)

Abstract： In order to set up the corresponding relationship between pixels of two homologous images accurately and overcome the shortcomings of large amount computation in method, an improved stereo matching algorithm is proposed. The improved area-based stereo matching algorithm adoptes the two-way stereo matching strategy to improve the accuracy of matching between pixels of two homologous images. The dense parallax error of image is obtained in combination with the mean-shift image segmentation technology under the assumptions of the same area with the same parallax. Meanwhile, in order to conquer the disadvantage of large amount computation of the area-based stereo matching algorithm, the pseudo-epipolar constraint is introduced by this algorithm to limit the location of the true matching point in a very small area. Therefore, the search range of matching point is reduced significantly, and the computation amount of matching algorithm is decreased efficiently. The experiments results show that the improved algorithm can effectively reduce the matching range and achieve the exact dense matching between images.

Keywords： two-way stereo matching; image segmentation; pseudo-epipolar line; dense matching

收稿日期：2011-06-13

基金项目：黑龙江省教育厅科学技术研究项目（11553100）

计算机视觉技术被广泛应用于目标检测、目标测量、目标识别、视觉导航以及三维环境构建等场合。其中立体匹配是计算机视觉中最重要，同样也是最困难的一个环节。根据匹配基元不同立体匹配大体分为：基于特征的匹配［1］；基于区域的匹配［2］；基于相位的匹配［3］；其中基于区域的匹配算法又可分为以下两种：一种是局部窗口匹配算法；另一种是全局优化算法；前者原理简单、计算量相对较小，但存在许多局部最小值，例如爬山法［4］；后者虽然可以得到相对准确的匹配结果，然而计算量较大，不适合实时系统，例如图割法［5］；本文采用的就是局部窗口匹配算法。局部窗口匹配算法是通过比较窗口中像素的相似度，来实现两幅图像中对应点的匹配。

为了提高匹配质量本文采用双向匹配策略去除伪匹配，并引入伪极线约束缩小匹配搜索范围。为了实现图像的稠密匹配，本文算法将图像进行分割，并根据相同区域具有相同视差的假设重新分配视差。

1 BumblebeeR XB3三目摄像机

本文采用的是加拿大PointGrey公司生产的BumblebeeR XB3三目摄像机进行图像采集，如图1所示。

图1 BumblebeeR XB3三目摄像机BumblebeeR XB3三目摄像机是由3个光轴平行焦距为3.8 mm的摄像机组成，两两摄像机之间的最小基线距离为120 mm，最大基线距离为240 mm。PointGrey公司生产的BumblebeeR XB3三目摄像机对计算机的系统配置要求如表1所示。

2 图像分割

图像分割即根据图像的灰度信息将图像中每个像素归类到相应模式下。假设图像的相同灰度分割区域，具有相同的视差大小；视差变化不连续的情况一般出现在图像的边界处，这种假设满足大多数的真实场景。本文算法就是在这种假设的前提下，采用双向匹配策略以及伪极线约束来实现图像的稠密匹配。

进行图像分割的方法有很多，本文采用的mean-shift算法（均值漂移算法），是一种非参数概率密度估计鲁棒性高的图像分割方法。mean-shift算法放弃直接对概率密度函数的估计，转而对密度梯度进行估计；通过计算快速收敛的局部窗口均值偏移向量迭代寻找数据中心，成为计算局部最优解的一种非常实用的方法。

由于mean-shift图像分割算法具有原理简单、无需进行图像预处理以及参数少等优点，该算法在图像分割领域得到了广泛应用［6-7］。图2为采用mean-shift算法对摄像机采集到的左图像进行分割的结果。从图中可以看出该算法可以较准确的将图像中每一像素聚类到相应模式下。根据假设前提可知，分割算法对图像的分割越准确越有利于稠密视差的获取。因此，mean-shift算法可以为图像稠密视差的获取提供较好的图像分割信息。

3 伪极线的求取

在两幅图像的立体匹配过程中，存在着各种各样的约束准则，例如极线约束、惟一性约束、连续性约束、顺序一致性约束以及互对应约束等等。其中极线约束是较为常用的匹配约束准则之一。极线约束是指2幅图像中的对应匹配点必然位于各自对应的外极线上。如图3所示，外界任一点P映射在左右像平面上的像素点分别为PL，PR，根据极限约束准则PR必然在PL所对应的外极线L2上；同理，PL必然在PR所对应的外极线L1上。其中外极线L1,L2分别为左右摄像机中心点OL,OR以及外界物点P所构成的平面与左右摄像机成像平面的交界线。通过以上分析可知，极线约束只能确定某点对应的匹配点必然位于外极线上，而不能确定该匹配点的具置或者某一位置区域。

为了缩小对应匹配点的搜索区域，本文引入伪极线约束。所谓伪极线就是将两个光轴平行的摄像机进行横向和纵向的微小旋转后，图像中各点所对应的外极线。通过图3可知，当拍摄图像的两台摄像机光轴平行或者待匹配的两幅图像已经进行过极线校正时，左图像中的任一点所对应外极线是纵坐标与该点相同并平行于横轴的水平直线。所以，当摄像机位置发生微小旋转时，新产生的外极线（即伪极线）必然与原先的极线在真实匹配点附近存在交点［8］。在实际计算中，伪极线将通过伪基础矩阵进行求取。

3.1 基础矩阵的求取

立体匹配中极线约束准则可以通过式（1）进行描述：XTRFXL=0

（1）式中：XL=(xL,yL,1)T表示左图像中待匹配点的扩展坐标；XR=(xR,yR,1)T为右图像中与左图像待匹配点XL相匹配点的扩展坐标；F为基础矩阵。将式（1）展开可以得到式（2）：xRxLF11+xRyLF12+xRF13+yRxLF21+

yRyLF22+yRF23+xLF31+yLF32+F33=0

（2） 当已知2幅图像中的多个匹配点对时，式（2）可以简化为式（3）：AF1=0

（3）式中：A为系数矩阵；F1=(F11,F12,F13,F21,F22,F23,F31,F32,F33)T为由基础矩阵元素构成的9维向量。

常用的基础矩阵估计方法有7点法、8点法、RANSAC算法以及LMeds算法［9］。其中7点法和8点法对初始匹配采样点要求匹配精度较高，RANSAC算法估计前要设定正常点的尺度σ1，σ1假设的优劣直接影响估计精度，而LMeds算法即使存在对应点误匹配的情况也能得到较正确的估计基础矩阵，鲁棒性较强［10］。基于以上各种基础矩阵估计算法的特点，本文采用LMeds算法进行基础矩阵估计。

3.2 伪基础矩阵的求取

由于本文采用的BumblebeeR XB3三目摄像机各摄像机之间光轴是平行的，图像中各点所对应的外极线都是平行于横轴的直线。因此，在寻找待匹配点的匹配点时，只需在相应纵坐标位置的水平扫描线上寻找即可。为了进一步缩小搜索范围，本文引入伪极线约束。

在求取伪极线之前，首先要进行伪基础矩阵的估计。为了估计伪基础矩阵，本文算法将已知匹配点集进行如下变换:

XL=(xL,yL,1)T变为XLε=(xL+εL1,yL+εL2,1)T；XR=(xR,yR,1)T变为XRε=(xR+εR1,yR+εR2,1)T；其中εL1,εL2,εR1,εR2均为［－2,+2］区间内随机产生的整数序列。

将原始采样点分别增加一个微小偏移量，相当于原本光轴平行的两台摄像机发生了横向和纵向的反转。这样以来，原本平行于水平方向的各条极线都会发生偏移，变为与水平方向成一定夹角的直线，这条新产生的极线就是所谓的伪极线。将根据带有偏移量的匹配点集估计出来的基础矩阵称为伪基础矩阵。假设此时进行从左到右的顺序匹配，那么左图中某一点XL所对应伪极线将由式（4）求得。(FXL)TXR1=0

（4）式中：F为伪基础矩阵；XR1为右图像中在点XL对应伪极线上的点。

通过图4可知，每一个像素点所对应伪极线与极线的交点必将位于真正匹配点附近。因此，在寻找某一点的匹配点时，只需在该点伪极线与极线交点的附近寻找即可，从而节省了大量匹配时间。

4 双向立体匹配

实际的区域立体匹配过程中往往存在着大量的误匹配。为了提高图像的匹配精度，本文采用双向立体匹配策略。双向立体匹配策略的基本思想是：左图像中任一点在右图像的匹配点是惟一的，同样右图像中的匹配点在左图像中的匹配点也是惟一的，并且相互匹配的两点是一一对应的。假设左图像中任意一点Lpoint的右图像对应匹配点为Rpoint，那么从左图像到右图像匹配得到点Lpoint所对应的视差绝对值应该与从右图像到左图像匹配得到点Rpoint所对应的视差绝对值相等。为了更好地得到稠密视差图，本文将根据公式（5）重新分配双向匹配中各点的视差，假设点(xL,y)与点(xR,y)相互匹配：

|dLR(xL,y)|=

|dLR(xL,y)|+|dRL(xR,y)|2，

dLR(xL,y)|－|dRL(xR,y)

0, 其他

（5）

式中：dLR(xL,y)为从左到右顺序匹配左图像中任一点(xL,y)的视差；dRL(xR,y)为从右到左顺序匹配过程中右图像中对应点(xR,y)的视差；其中xL=xR+dRL(xR,y)；

由公式（5）可知，当左右匹配视差绝对值小于一定阀值σ时，将两视差绝对值均值作为该点视差；否则，认为左右匹配不一致即匹配错误。

常用的相似性测度有SSD，SAD，ZSSD，ZSAD，NCC，ZNCC，Rank以及Census。其中SSD和SAD计算简单，较为常用；ZSSD，ZSAD，NCC，ZNCC鲁棒性强，对图像对的轻微亮度差异不敏感，然而计算量相对较大；Rank和Census在物体边界处的匹配要胜过传统的相似测度［11］。

本文算法将ZNCC与像素点梯度幅值相似度相加来衡量两个像素点的相似性，如式（6）所示：SWEIGHT=ZNCC+SGRADS

（6）其中：

ZNCC=

∑(x,y)∈W(IL(x,y)－IL)×(IR(x+d,y)－IR)∑(x,y)∈W(IL(x,y)－IL)2∑(x,y)∈W(IR(x+d,y)－IR)2

（7）

式中：IL(x,y)为左图像对应点像素值；IR(x+d,y)为右图像对应点像素值；IL，IR为左右图像像素平均值；W为匹配窗口；d为两像素之间的视差；SGRAD=|GRADL(x,y)－GRADR(x+d,y)||GRADL(x,y)|×|GRADR(x+d,y)|

SGRADS=wg×exp(－SGRAD)

（8）式中：GRADL(x,y)为左图像像素点的梯度幅值；GRADR(x+d,y)为右图像候选匹配像素点的梯度幅值；SGRADS为像素点的梯度幅值相似度；wg为加权系数；

改进的双向立体匹配算法实现步骤：

（1） 采用mean-shift图像分割算法将图像的每一个像素归类到相应的模式下；并根据带有偏移量的采样点集估算出伪基础矩阵F；

（2） 采用双向匹配策略以及伪极线约束实现图像的快速初始匹配，并重新分配视差标记准确匹配点位置；

（3） 在假设图像的相同灰度分割区域，具有相同视差大小的前提下，将位于同一区域所有准确匹配点视差的中值dwi作为该区域的视差。dwi=medianx,y∈wi(d(x,y))

（9）式中：wi为被分割图像的第i区域；dwi为图像wi区域的视差中值；d(x,y)为准确匹配点(x,y)的视差；

（4） 采用均值滤波技术对得到的稠密视差图进行滤波，去除图像中部分细小区域产生的伪匹配点。

5 实验结果

为了检验伪极线约束的准确程度，从左图像中任取一点，计算其伪极线与极线交点并判断真正匹配点与该交点的相对位置。如图5所示，左图像任一点的匹配点与伪极线和极线交点的相对位置非常接近。大量实验表明两者的相对位置不会超过10个像素。因此，在寻找真正匹配点时只需在伪极线与极线交点的左右10像素范围内寻找即可，从而大大节省了匹配时间。

图5 伪极线约束为了检验本文算法的准确性，本文以Matlab为工具，对Tsukuba左右图像进行匹配，并将实验结果通过测试平台（vision.middlebury.edu/stereo）进行评价，各种算法结果如图6所示；各项评价指标见表2，其中Nonocc表示非遮挡区域的误匹配率；All表示总体误匹配率；Disc表示视差边界误匹配率。

根据图6可知，本文算法与双向立体匹配算法在物体边界处的立体匹配效果要好于文献［7］提出的匹配算法，因此可以提供更好的形状信息。

如表2所示，当最大允许误差为2个像素时，本文算法相对于文献［7］算法而言可以有效地降低边界处的误匹配率，并且在计算时间方面与文献［7］相当；与双向立体匹配相比，本文算法在保证匹配精度的前提下，有效地降低了匹配时间，并且可以克服双向立体匹配不能对视差值大于最大视差的点进行精确匹配的缺点。

通过以上实验结果可以看出，本文算法在保证立体匹配精度的同时，有效地降低了区域立体匹配的计算量，大大提高匹配速度；本实验是在最大允许误差为2个像素的前提下进行评估的，如果将最大允许误差减小，本文算法的误匹配率将会提高，这是因为该算法是在假设位于同一区域像素具有相同视差的前提下进行的，当复杂环境中出现大量表面存在弧度较大或斜平面的物体时，本文算法认为这些区域的各点属于同一区域，并为其赋予相同视差。然而，处于弧度区域的各点视差是互不相同的。因此，在这种情况下本文的匹配精度将会有所降低。

6 结 语

实验结果表明，采用改进的双向立体匹配算法可以有效地缩小匹配点搜索范围，提高匹配精度，克服视差图像边缘模糊现象；然而，当实际复杂场景中出现大量具有弧度较大或斜平面的物体时，本文算法在弧度表面和斜平面区域的匹配精度将有所下降，为了提高本文算法在弧度区域的匹配精度，后期准备对图像边界进行检测，并进行高精度匹配，根据具有高精度匹配的边界计算横向扫描线两相邻匹配边界视差的伸缩尺度，并根据伸缩尺度重新分配该区域的视差。这样一来，可以采用斜平面来近似描述弧度区域，从而达到提高弧度区域和斜平面区域匹配精度的目的。

参 考 文 献

［1］ RAYMOND V E, CLIFTON M S. Unconstrainted stereoscopic matching of lines［J］.Vision Research,2000:151-162.

［2］ KANADE T, OKUTOMI M.A stereo matching algorithm with an adaptive window［J］.Theory and Experiment,1994,16(9):920-931.

［3］ 李德广，李克杰，高丽丽.基于多尺度多方向相伴匹配的立体视觉方法［J］.仪器仪表学报,2004,25（4）：600-602.

［4］ MILLAN W, CLARK A, DAWSON E. Smart hill climbing finds better boolean functions［C］.//Proceedings of Workshop on Selected Areas in Cryptology. [S.l. ]:SAC, 1997:55-63.

［5］ BOYKOV Y, VEKSLER O, ZABIH R. Fast approximate energy minimization via graph cuts［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence ,2001,23(11):1222-1239.

［6］ 殷虎，王敬东，.一种基于彩色图像分割的立体匹配算法［J］.红外技术,2009,31(12):702-707.

［7］ 何西平.非参数mean-shift算法在计算机视觉中的应用［J］.重庆工商大学学报,2010,27(6):586-590.

［8］ 王昕，马岩，杨剑，等.区域立体匹配算法的实现及改进［J］.光学精密工程,2008,16(10)：2002-2008.

［9］ 向长波，刘太辉，宋建中.基本矩阵的鲁棒贪心估计算法［J］.计算机辅助设计与图形学学报,2007,19(5)：651-655.

［10］ 胡灵山，朱齐丹.计算机视觉中基础矩阵的估计方法［J］.应用科技,2005,32(10)：41-43.

［11］ 肖艳青，刘党辉，孙朋.图像立体匹配研究进展［J］.测控技术,2009,28(8):1-5.

匹配算法论文篇7

关键词：管理科学；双边匹配；不确定偏好序；心理行为；TODIM；感知价值；优化模型

中图分类号：C931

文章标识码：A

文章编号：1007-3221（2015）02-0113-08

引言

现实生活中存在着大量的双边匹配问题，如婚姻匹配问题、商品买卖问题、员工/求职者与岗位匹配问题、大学招生录取问题等。随着社会经济的发展，经济管理中的双边匹配问题引起了更为广泛关注，如二手房交易匹配问题、风险投资商与风险企业匹配问题。因此，双边匹配问题具有广泛的实际应用背景。

针对基于偏好序信息的双边匹配问题的研究，多年来一直受到了学者们的广泛关注。Roth针对美国医学院毕业生与实习医院的匹配问题，提出了Hospital-Resident算法。Irving等针对医学院毕业生与实习医院的匹配问题，着重分析了强稳定性的概念。Ehlers指出对于英国初级医药市场和部分美国公立学校录取的优先权机制与线性规划机制，在一个对称或不完全信息环境下，通过提交部分真实偏好才可能获益。Alkan研究了每个主体可能与多个合作者匹配情形下的双边市场中稳定匹配的结构，即稳定多合作者匹配的格结构，指出格具有两极性、分配性、互补性以及完全配额性。Sethuraman等聚焦于多对一稳定匹配问题的可行解的几何结构和公平性――非基解稳定匹配的研究。Knoblauch研究了具有随机分布偏好序偏好的Gale-Shapley算法的性质。

已有的研究为解决基于偏好序信息的双边匹配问题提供了理论与方法层面的借鉴指导，也扩大了实际应用背景。但需要指出的是，一方面在一些现实匹配问题中，双方主体给出的偏好信息可能是不确定偏好序，但关于不确定偏好序信息下的双边匹配决策问题的研究非常少见；另一方面已有研究大多从稳定性和满意性角度进行研究，在这些研究中主体往往被认为是完全理性的，没有考虑到主体的心理行为因素；而现实决策过程中，大多数主体是有限理性的。为此，本文针对不确定偏好序信息下的双边匹配问题，提出了一种考虑主体心理行为的双边匹配决策方法。

1 相关基础知识

1.1 双边匹配

双边匹配的相关概念及其符号描述可参照文献。进一步可知，双边匹配μ可表示为μ=μMUμs，其中μM为匹配主体对集合，μs为单身主体对集合。

1.2 不确定偏好序

不确定偏好序的相关概念及其符号描述可参照文献。进一步可知，对于某主体的不确定偏好序，若表示该主体的真实偏好序，则它包含在中，且中每个偏好序以等同概率覆盖r。因此，r可看作是上具有等概率信息的离散随机变量。

定义1 设为关于某主体的不确定偏好序，m为该方主体的数目，则；的概率向量为

2 问题描述

在考虑的不确定偏好序信息下的双边匹配问题中，设乙方主体集合B的不确定偏好序向量，其中表示甲方主体Ai把乙方主体Bj排在第至位，为乙方主体Bj给出的关于甲方主体集合A的不确定偏好序向量，其中表示乙方主体Bj，把甲方主体Ai排在第至位，设fi为甲方主体Ai根据已有信息和对未来预期等因素给出的临界值，fi∈N；设hi为乙方主体Bj根据已有信息和对未来预期等因素给出的临界值，hi∈M。

根据上述分析，不确定偏好序信息下考虑主体心理行为的双边匹配问题，可由图1表示。图1中，Ai与Bi之间的有向虚线的权值表示它们之间的偏好序大小，Ai与Bi之间的无向粗线表示Ai与Bj匹配；山m条无向粗线连接形成的匹配主体对集合表示μE，Bn-1在该匹配μ中为单身。

综上，本文要解决的问题是：依据甲方主体Ai给出的不确定偏好序向量Ri和临界值fi，乙方主体Bj给出的不确定偏好序向量Tj和临界值hj，如何通过一个有效的决策方法，对双方主体进行匹配。

3 双边匹配决策方法

为了解决上述问题，下面阐述本文提出的考虑主体心理行为的双边匹配决策方法。

3.1 感知价值矩阵的构建

首先，由于主体的临界值能很好地反映该主体的心理感受，即若Ai与排在其临界值fi之前的Bj匹配，即则Ai的心理感受为收益，且，越小，收益也越大；若Ak与排在其临界值fk之后的另一方某主体匹配，即则Ak的心理感受为损失，且越大，损失也越大；且临界值作为参照点能够很好地继承前景理论的各种性质，因此，本文以临界值作为参照点。

其次，为了计算主体给出的不确定偏好序相对于参照点的收益或损失，这里需要将不确定偏好序信息转化为期望信息。依据式（1），将不确定偏好序向量转化为期同时定义期望与其参照点fi之间的规范化距离，其计算公式为：在此基础上，叮建立甲方到乙方的相对于参照点的益损矩阵F=[F（rij）]m×n其中F（ij）表示不确定偏好序相对于其参照点fi的益损值，其计算公式为这里，当时，称为不确定偏好序相对于其参照点fi获得的收益；当时，称为不确定偏好序相对于其参照点fi产生的损失。

类似地，定义期望与其参照点hj之间的规范化距离，其计算公式为：在此基础上，可建立乙方到甲方的相对于参照点的益损矩阵序，相对于其参照点hi的益损值，其计算公式为这里，当E（tij）

根据前景理论可知，在双边匹配问题中，主体面对收益时是风险规避的，面对损失时是风险寻求的，且对损失比收益更敏感。考虑到主体对收益和损失的不同风险态度，下面依据TODIM思想，计算每个主体对另一方每个主体的益损值的感知价值。

考虑到主体损失规避的心理行为特征，即主体对待损失的感知比等量的收益更加敏感，依据TODIM思想，可将益损矩阵转化为甲方到乙方的感知价值矩阵，其中为主体Ai针对主体Bii的益损值的感知价值，其计算公式为

其中θi为衰减系数，0

类似地，依据TODIM思想，可将益损矩阵转化为乙方到甲方的感知价值矩阵VB=其中为主体Bj针对主体Ai的益损值的感知价值，其计算公式为

其中ω1，是衰减系数，0

3.2 决策模型的构建

设xij表示一个O一1变量，其中xij=0表示μ（Ai）≠Bj，即Ai与B，在μ中未匹配，xij=1表示μ（Ai）=Bj，则依据感知价值矩阵，可构建如下双目标优化模型（10）：模型（10）中，式（lOa）和（lOb）为目标函数；式（lOa）的含义是最大化所有甲方主体关于乙方主体的感知价值之和，式（lOb）的含义是最大化所有乙方主体关于甲方主体的感知价值之和；式（10 c-）的含义是每个甲方主体必须且只能与一个乙方主体匹配；式（lOd）的含义是每个乙方主体至多与一个甲方主体匹配，若

3.3 决策模型的求解

为了求解模型（10），考虑到，F（r，j）∈[0，1]，H（t，j）E[0，1]则采用线性加权法将式（lOa）和（10b）进行加权。设wA和wB分别表示目标ZA和ZB的权重，满足O

其中cij=wAvA（rij）+wBVB（tij），权重wD（D=A，B）反映了目标ZD在实际双边匹配问题中的重要程度，它由中介与甲乙双方主体磋商后给出，若考虑到甲乙双方主体的公平性，则有WA=WB。

显然，模型（Il）可转化为标准的指派问题模型，这样可使用匈牙利法进行求解。当模型（11）中的变量和约束条件个数较多时，可采用Ling0 11.0、Cplex9.0、WinQSB 2.0等软件，或采用启发式方法，如遗传算法、禁忌搜索算法等进行求解。根据模型求解结果，可获得双边匹配方案。

定理10 模型（11）存在最优解，且目标函数最优值F* >0。

证明 由于模型（11）是含有mn个变量的0-1整数规划，则它最多产生个可行解.显然，为模型（11）的可行解，则模型（11）的可行域非空。冈此，由式（lla）确定的目标函数在可行域某点/某个可行解上达到最大，即模型（11）存在最优解。

根据多目标规划理论可知，模型（11）的最优解是模型（10）的有效解。

综上，求解基于不确定偏好序信息的双边匹配问题的步骤如下：

步骤1 依据式（2）与（3），将不确定偏好序向量Ri与Ti分别转化为期望向量E（Ri）与E（Tj）；

步骤2 依据式（4）与（5），建立相对于参照点的益损矩阵，依据式（6）与（7），建立相对于参照点的益损矩阵；

步骤3 依据式（8）与（9），分别建立感知价值矩阵，与；

步骤4 依据感知价值矩阵，构建双目标优化模型（10）；

步骤5 运用线性加权法，将双目标优化模型（10）转化为单目标优化模型（11）；

步骤6求解优化模型（11），获得匹配结果μ。

4 实例分析

中国上海某IT服务外包中介网站，主要针对网站/软件开发、网络安全、安防监控、IT系统维护等项目提供中介服务。现有5个IT服务需求方（A1，A2，…，A5）欲将其公司的网站开发业务外包，通过在该TT服务外包巾介网站上信息，共收到6个IT服务供给方（B1，B2，…，B6）的承包意向和相关信息 IT服务需求方Ai，对IT服务供给方从技术能力、价格、信誉、交货期和售后服务等指标进行综合评价，给出关于IT服务供给方集合B的不确定偏好序向量，同时给出其临界值fi，i=1，2，…，5，见表1；IT服务供给方Bj对IT服务需求方从企业商誉、招标价格、付款速度和长期合作潜力等指标进行综合评价，给出关于IT服务需求方集合A的不确定偏好序向量同时给出其临界值hi，j=l，2，…，6，见表2；最后由该IT服务外包中介进行决策。

为了解决该双边匹配问题，下面简要说明使用上文给出方法的计算过程。

首先，依据式（2）与（3），分别将不确定偏好序向量Ri与Tj转化为期望向量E（Ri）与E（Ti）。其次，依据式（4）与（5），建立相对于参照点的益损矩阵，如表3所示；依据式（6）与（7），建立相对于参照点的益损矩阵如表4所示。接着，依据式（8）与（9），分别建立感知价值矩阵VA与，如表5和表6所示，其中θi=0.8，ωj=0.8。

进一步依据感知价值矩阵与，构建双目标优化模型（10）。不妨设wA=WB=0.5，则优化模型（10）转化为单目标优化模型（11），其中系数矩阵如表7所示，Cij=0.5VA

通过Ling0 11.0优化软件包编程求解模型（11），可得匹配结果为，其中B5），（A2，B6），（A3，B3），（A4，B2），（A5，B4）}，μo={（B2，B2，（B3，B3），（B4，B4）}；即A1与B5匹配，A2与B6匹配，A3与B3匹配，A4与B2匹配，A5与匹配B4，B1单身。

为进一步阐明本文提出方法的意义，给出如下分析。

在本例中，若不考虑主体心理行为，则依据期望向量E（Ri）（i=1，2，…，5）与E（Tj）（j=1，2，…，6），可建立双目标优化模型。设wA=WB=0.5，则该模型可转化为如下单目标优化模型（12），其中系数矩阵如表8所示，。进一步求解模型（12），可得匹配结果为，其中

表9所示了考虑主体心理行为与不考虑主体心理行为的双边匹配决策方法的匹配结果。从表9中叮知：运用这两种双边匹配决策方法获得的匹配结果完全不同。这就说明了主体心理行为对匹配结果有着重要的影响作用。

5 结语

本文从主体心理行为的角度出发，将临界值视为参照点，通过定义不确定偏好序的期望与其参照点之问的规范化距离，计算了相对于参照点的收益或损失，进而依据TODIM思想计算了每个主体针对另一方主体的益损值的感知价值，在此基础上，提出了不确定偏好序信息下考虑主体心理行为的双边匹配决策方法，主要结论如下。

（1）本文将主体心理行为因素引入到双边匹配问题的研究中，丰富并发展了双边匹配的相关理论，为后续开展双边匹配理论与方法的相关研究提供了新思路。

（2）本文提出的感知价值公式能够有效的测度双方主体的心理行为。

（3）主体心理行为对匹配结果有着重要的影响作用。

匹配算法论文篇8

关键词 地磁异常场；位置估计；室内定位；Hausdorff距离

中图分类号 TU19 文献标识码 A 文章编号 1674-6708（2016）160-0157-02

地磁场可以看作一个矢量场，在这个巨大的矢量场内，根据地磁学理论，靠近人类活动范围的每个位置上都具有唯一的磁场矢量值，如果可以测出该位置的多个地磁场的典型特征信息，即可实现全球任意地点定位。在生物界中，人类已经发现许多动物借助地磁场来实现方向定位和导航[1]。例如，大螯虾不仅可以判断出地磁场的方向，甚至能估计出自己相对于目的地的距离。目前在室外民用领域中，借助GPS可以实现精确定位和导航，然而GPS信号被建筑物遮挡，无法在室内进行定位。为了解决这个问题，提出了基于无线网络和蓝牙信标定位等方法。虽然提高定位精度，却要建立昂贵的基础设施，并容易受到移动物体、多路径效应的影响。实验证明[2]在钢筋混凝土结构的建筑物中，存在局部地磁异常场，这些异常场随着位置而有所不同，并且在时间上很稳定。本文选用这些地磁异常特征量绘制成基准图，通过载体上的地磁传感器测量地磁特征，根据Hausdorff距离地磁匹配算法与基准图进行相关匹配，实现对载置估计，并且通过仿真实验验证算法的可行性。

1 室内定位方法1.1 地磁匹配原理

在地磁扰动场中任何位置上地磁数据都具有典型特征，地磁匹配就是基于每个坐标位置上的地磁场强度值来实现定位的。室内地磁定位系统操作主要分为2部分，具体如图1所示。

1）预先建立地磁基准图，使匹配区域中的位置坐标与地磁场强度值相对应，这一步要求地磁基准图的精度适当，以便于下一步的定位。可以通过每隔0.5m采集一次地磁数据（连续采集10次数据求平均值，），通过插值构建地磁基准图。

2）估计载置，利用地磁传感器在载体运动过程中采集的地磁数据，通过合适的地磁匹配算法，将具有实时性的地磁特征量与基准图库中数据相比较，来估计当下载体在匹配区域中的位置。

1.2 地磁匹配算法

与地形匹配中点匹配算法类似，不过地磁匹配算法涉及的匹配特征量有多个。随着技术的进步，小型磁传感器不仅可以获得地磁场总强度，而且可以获得在正北、正东以及竖直方向的各个分矢量，甚至磁偏角和磁倾角等。由于本文所用地磁传感器不能精确测量地磁场三分量的方向角，加之载体在运动过程中的航向角经常变化。地磁基准图的构建采用地磁异常场总强度，在实验区域中分布特征明显，随时间变化非常稳定。

目前，地磁匹配算法的研究不是很成熟，多处于仿真研究阶段，主要有相关度度量算法和滤波算法[3]。由于地磁传感器在测量中存在噪声，载体的磁性物质干扰，计算过程复杂等其他误差和失真因素的影响，致使定位精度不高，匹配成功率下降。为了提高载体采集特征量序列与基准图采样点上特征量序列的相关性，本文采用Hausdorff距离地磁匹配算法，它会降低一组地磁序列中数据受到噪声等因素干扰引起的地磁数据不稳定的影响，在数据库中寻找出最合适的匹配序列。

1.3 Hausdorff距离算法

Hausdorff距离又被称作极大极小距离，它描述了两组点集之间的相似程度，已普遍应用到二值图形学中，地磁匹配借助此算法获得新测度方式[4]。

式中，H（A，B）表示两个方向上Hausdorff距离，h（A，B）表示A集合元素到B集合元素的单一方向上Hausdorff距离，令前者A与B互换可推出h（B，A）的定义。考虑仅比较磁场总强度，同时它也是一个标量，将|||| ||a ba b？=？看作是A，B间距离范数。从公式中，可以看出Hausdorff距离反映了两个点集的不匹配程度，它的距离越大，则两个集合相似性越低。

Hausdorff距离地磁匹配算法与传统算法有一定区别，它不强调点集中具体的匹配点对，使得点与点的关系变得模糊起来，因此在室内地磁定位中可以增强抗干扰性和容错性。

选用磁场总强度作为地磁特征量，建立地磁基准图，基于Hausdorff距离算法完成地磁匹配定位。实验过程中，由地磁传感器测量模块产生地磁特征量序列，遍历地磁基准图，将基准地磁数据序列当作（3）中集合A，将特征量序列当作集合B，运用Hausdorff距离算法，计算出H（A，B）中的最小值，它所对应的位置坐标即为匹配定位结果。

2 定位仿真环境

2.1 地磁基准图布置

为了实现前述定位过程，选择在本校科技研讨楼3层南北走廊进行实验，所取地磁区域长43.2m，宽1.8m，共有219（73×3）个采样点，采样点间隔为0.6m。将实测采样点上的地磁场强度作为Z值，走廊朝北方向作为X轴正方向，西方向作为Y轴方向，通过surfer软件建立地磁场总强度分布图。为了提高基准图分辨率，采用线性插值拟合出地磁场等值面图，将分辨率由0.6m提高到0.1m，如图2所示。

2.2 实验结果与分析

为了简化实验过程，选用一个智能小车作为载体，将地磁传感器（HMC5983）放置在小车竖直上方1.2m处（正常人手持手机高度），中间用木条连接，尽量降低磁性物质对测量精度的影响。设小车在地磁区域中作匀速运动，初始位置随机产生，采样周期0.2s，测量噪声为高斯白噪声，实验精度用定位坐标与实时坐标的点位误差来表示。

依据实验过程，分析比较量测噪声、小车行驶速度等因素对室内定位结果的影响。

1）设小车速度V=0.6m/s，量测噪声分别取50nT和100nT，在相同的匹配区域中随机放置小车。通过多次实验分析后，得出在其他影响因素不变的情况下，量测噪声越大，定位精度越低，甚至会增加错误匹配结果的次数，如表1所示。因此，地磁采集装置避免使用磁性物质制成，保持与磁传感器一定的距离，另外考虑精度更高、抗干扰能力更强的地磁测量模块。

2）设量测噪声为50nT，小车速度分别选取0.6m/s、1.2m/s、1.8m/s 3种情况下，与（1）种相同的匹配区域中随机放置小车。通过多次实验后，得出在其他影响因素不变的情况下，小车的速度快慢对于匹配结果的影响基本忽略不计，但是小车的速度过快，导致磁传感器采集的地磁数据量不够，会对匹配结果产生影响，如表2所示。

3 结论

本文提出基于Hausdorff距离地磁匹配算法的室内定位方法，并进行多次仿真实验，证明了该算法在室内定位中的可行性。由于本文选取的实验场所地磁匹配信息变化不明显，考虑下一步提高地磁基准图的精度。针对单一方式实现室内定位过程的匹配准确率不高的情况，探究利用当下无基础设施的WiFi环境来进一步提高室内定位的精度，使建立一种准确快速的室内定位方法成为可能。

参考文献

[1]Larry C.Boles and Kenneth J. Lohmann. True navigation and magnetic maps in spiny lobsters. Nature，421：60-63，2003

[2]G.Casinovi A.Geri， and G.M.Veca. Magnetic filed near a concrete wall during a lighning stroke. IEEE Transactions on Magnetic.vol.25 pp.4006-4008，1989

匹配算法论文篇9

关键词：自适应分数阶微分；图像增强；尺度不变特征变换；图像匹配

中图分类号：TP391.41

随着分数阶微积分的定义被大家熟知，其应用也越来越广泛，尤其是在信号分析与处理领域。分数阶微分在处理图像时，可以在加强图像高频信息的同理，也保留低频的轮廓部分。分数阶的这些显著特点在文献[1，2]中都得到了充分论证。

图像特征匹配也是当前计算机视觉领域的研究热点之一。目前图像匹配方法主要是基于灰度相关和特征的两大类方法，前者直接利用图像灰度进行计算，匹配的成功率高，但是需要的时间较长，不能适用于一些对实时性要求较高的项目；后者主要是先对图像进行提取，然后再进行匹配，此类方法运算量小，但相对匹配率不高。在实际应用中，物体变形、遮挡、噪声的影响也是不可避免的，为了能解决以上这些问题，2004年DAIDLOWE提出的尺度不变特征变换（Scale Invariant Feature Transform，SIFT），SFIT被广泛的应用于目标跟踪，图像检测、识别等诸多领域。文献[3]提出将分数阶与SIFT相结合，利用分数阶对图像的加强作用，提高了匹配率和关键点的个数。但是对于分数阶的选择，一方面浪费人力，另一方面要靠经验，如果输入阶数不合适，会达不到预期的目标，影响处理效果。文献[4，5]提出了不同的阶数的自适应方法，将梯度与阶数建立了一定的映射关系，或者利用分数维求得图像处理的阶数，都可以达到不错的效果。本文利用图像梯度信息和人眼视觉特性等理论的自动生成分数阶与SIFT相结合的方法，一方面可以节省大量的人工寻求分数阶的时间，另一方面也得到较理想的配准效果，使分数阶应用于实时性要求较高的动态目标跟踪成为可能。

1 自适应的分数阶微分在图像处理中的应用

目前自适应分数阶微分在图像中的应用还不太多，本文利用文献[4]中的方法，根据图像本身的梯度特性和人类视觉特性等理论自动寻找调整图像需要的合适阶数。自适应分数阶微分在图像处理过程中与普通的分数阶处理图像一样，均需要掩模设计。

1.1 自适应分数阶微分掩模及推导过程

目前流行的分数阶微积分的的计算的方法有Riemann-Liouville定义，Grunwald-Letnikov（G-L）定义和Caputo定义。本文采用对信号处理更精确的G-L定义对图像进行处理。分数阶微积分G-L差分定义如下：

（1）

其中：Gamma函数！，信号?（t）持续期为t∈[a，t]。对于图像信号持续区间按等分间隔h=1进行等分，可以得到n=[t-a]，对于一元信号分数阶微积分的差分表达式：

（2）

对于M×N的图像f（x，y）用大小为m×n的滤波器w（s，t）进行线性滤波，则输出图像g（x，y）可以用离散卷积表示：

（3）

其中a=（m-1）/2，b=（n-1）/2，w（s，t）在这里为掩模，为了得到完整的滤波图像，不响影响平均梯度等特性，我们对距掩模中心在和的像素进行逐个处理，对于大于此距离的像素点，则不处理，保留其灰度值。

在构造分数阶微分掩模时，我们采用x轴正负方向，y轴正负方向，左右对角线方向8个方向的具有各向同性的算子掩模，以便使其对于图像具有旋转不变性。为了降低时间复杂度，不影响处理后的图像纹理，在实验中我们采用3×3的掩模，对掩模内的各个系数进行归一化处理同除以（8-8v），所以构造近似分数阶微分算子掩模如图所示。

表1 3×3的掩模模板

1.2 自适应分数阶数的推导过程

图像梯度反映了图像灰度在空间上的变化率，表现在图像上梯度大地方像素变化明显；梯度变化小的地方，图像则变化平缓；灰度相同区域，则梯度为零。图像梯度实际是纹理的一个量化反映，据此我们来找出他们之间的函数映射关系。

图像f在某像素点（x，y）上的梯度是一个二维列向量，为了降低计算量，梯度模值采用近似公式可得：

（4）

将偏微分部分可近似用差分代替，则梯度的模值可以表示为：

（5）

根据人类的视觉特性，人眼会在图像灰度变化快的区域分辨力越强，这也是纹理细节丰富的区域，所以在这些区域应适当加强灰度间隔，对于边缘突变的地方，应当约束灰度间隔。而在图像灰度变化平缓的区域，保留其灰度不变。因此我们可以得到分数阶和梯度之间的一个关系，自适应分数阶用v表示。

（6）

其中，max’（G）是像素点最大梯度的模值，为了使所得分数阶的阶数在0到1之间，ε1为任意正数，为了突出掩模中心点对邻域各点的影响，可以增加一个可选的正数参数ε2，满足如下条件。

根据文献[4]中的限制，当mag（G）>90，ε1等于max’（G），并且ε2要小于0.5，为了达到较好的效果，我们选择ε2=0.499；当2

（7）

由式7可知，利用整数阶的梯度的概念推演得到了分数阶图像处理的自适应函数，从而实现根据图像本身灰度变化得到在此像素点时需要的阶数v（v∈（0，1]）。

2 自适应的分数阶SIFT算法

目前匹配算法较多，SIFT的匹配能力较强，不但能够提取稳定特征，在图像的旋转、变换、平移行也能得到稳定的匹配。然而在图像模糊的时候，特征点不明显的时候，匹配率可能就不太理想，这个时候我们利用分数阶可以实现图像的加强这一点，将自适应的分数阶用于图像处理匹配算法中，让图像根据自己梯度的变化来调整阶数，实现阶数自动化选取，也能得到较高的匹配率，具体设计如下：

2.1 尺度空间的极值点检测

本算法用的是分数阶微分运算结合高斯核总运算得到尺度空间的微分变换公式：

Lv（x，y，σ）=G（x，y，σ）・w（s，t）・I（x，y） （8）

其中：v是分数阶的阶数，是尺度空间变换高斯核，w（s，t）是分数阶掩模，I（x，y）是二维图像。为了得到相对稳定的关键点，Lowe采用不同尺度的高斯差分函数对图像进行卷积运算，得到高斯差分尺度空间函数：

（9）

k为常数，为了寻找极值点，对图像中的每个像素点和其相邻点进行比较，该点比其图像域和尺度域相邻点大或者小，则该点为特征点。

2.2 关键点的筛选和定位

把（11）式进行展开得到（12）式，然后进行拟合，除去边缘和对比度低的特征点，进而得到需要的关键点。

（10）

2.3 关键点的方向参数的确定

关键点方向应保持旋转不变性，其参数由其领域像素的梯度方面分布的特性决定。由式（11）（12）可得到像素（x，y）的梯度和大小。

m（x，y）=（（Lv（x+1，y）-Lv（x-1，y））2+（Lv（x，y+1）-Lv（x，y-1））2）1/2

（11）

θ（x，y）=tan-1（（Lv（x，y+1）-Lv（x，y-1））/（Lv（x+1，y）-Lv（x-1，y））））

（12）

2.4 关键点描述子的生成

文献[6]描述了其生成的具体算法。首先将平面坐标轴旋转到关键点的主方向，然后计算以关键点为中心的8×8窗口的每个特征点的梯度大小和方面，最后再把刚才窗口分为4个取以关键特征点为中心的窗口，计算每个特征点的梯度大小和方向，然后再把原窗口分为大小为4×4的4个这样的小窗口，同时计算每个4×4窗口8个方面梯度方向直方图，这样一共可以生成128个数据，我们这128个数据来描述做为SIFT的特征向量。两幅图像匹配就是通过计算各自特征点的欧氏距离来判断这两个关键点是否匹配的。

3 实验结果与分析

为了验证自适应分数阶匹配算法的可行性与效率，我们选取了不同的图片进行匹配实验，实验的匹配率比选择的固定的阶数方便易行，而且匹配率也较理想。我们选择了三对不同图像进行匹配实验，具体的实验如下：

图1 用0.5阶和自适应分数阶微分的SIFT算法的匹配效果（3×3算子）

表2 0.5阶和自适应分数阶算子匹配SIFT算法匹配效果分析

图2 用0.5阶和自适应分数阶微分的SIFT算法的匹配效果（3×3算子）

表3 0.5阶和自适应分数阶算子匹配SIFT算法匹配效果分析

图3 用0.5阶和自适应分数阶微分的SIFT算法的匹配效果（3×3算子）

表4 0.5阶和自适应分数阶算子匹配SIFT算法匹配效果分析

对比实验我们分别采用的是0.5阶的和自适应分数阶的阶数来进行SIFT匹配实验的，结果是自适应阶数得到正确匹配率要高于0.5阶的，关键点个数上略少于0.5阶，但是不影响我们进行图像进行匹配时需要的关键点，还避免了我们手动的寻找合适的阶数的麻烦，所以此方法是可行的。

4 结语

本文将自适应分数阶微分与SIFT匹配算法结合，代替原来手动输入分数阶阶数的匹配算法，从实验结果可以看到，自适应分数阶SIFT算法从一定程度上提高了匹配率，还减少了人工寻找合适阶数的麻烦，在图像匹配中还是比较有效的。

参考文献：

[1]杨柱中，周激流，晏祥玉，等.基于分数阶微分的图像增强[J].计算机辅助设计与图像学报，2008，20（3）：333-348.

[2]Pu Yi-fei， Zhou Ji-Liu， Yuan Xiao. Fractional differential mask： a fractional differential-based approach for multi-scale texture enhancement[J].IEEE Transactions on Image Processing，2010，19（2）：49-51.

[3]张丽敏，周尚波.基于分数阶微分的尺度不变特征变换图像匹配算法[J].计算机应用，2011，31（4）：1019-1023.

[4]汪成亮，兰利彬，周尚波.自适应分数阶微分在图像处理纹理增强中的应用[J].重庆大学学报，2011，34（2）：32-36.

[5]汪成亮，乔鹤松，陈娟娟.基于纹理复杂度的自适应分数阶微分算法[J].计算机工程，2012，38（7）：177-181.

匹配算法论文篇10

作者简介:齐军（1987-），男，河南息县人，硕士研究生，主要研究方向：软件工程、形式化方法； 张月菊（1980-），女，河北晋州人，硕士，主要研究方向：软件工程、工作流； 王涛（1975-），男，广西合浦人，副教授，博士，主要研究方向：软件工程、形式化方法、信息系统安全。

文章编号:1001-9081（2011）08-02253-05doi:10.3724/SP.J.1087.2011.02253

（华南师范大学 计算机学院，广州510631）

（）

摘 要:针对现阶段工作流集成研究中功能匹配查准率和查全率低的问题，给出了基于软件功能形式化语义的匹配机制的实现。在前、后条件pre/post的完全匹配模式下，以高级程序设计语言中的代数表达式为基础，提出了匹配原则，并给出了具体的算法，并且用实例进行分析说明。该算法适用于工作流集成中的功能匹配，同时基于严格的形式化方法，便于分析和验证。该算法局限于初等代数性的前提。

关键词:工作流集成；形式语义；语义匹配；代数表达式；功能匹配

中图分类号: TP311.521文献标志码:A

Semantic matching mechanism based on algebraic expression in workflow integration

QI Jun, ZHANG Yue-ju, WANG Tao

（School of Computer Science, South China Normal University, Guangzhou Guangdong 510631, China）

Abstract: Concerning the problems of low precision ratio and low recall ratio of function match in the research of workflow integration, the authors implemented the matching mechanism based on formal semantic of extract pre/post match pattern, and proposed matching principles on the basis of algebraic expressions in high level programming languages. The specific algorithm was raised up and also an example was given to analyze and illustrate the algorithm. The proposed algorithm is suitable for function matching in workflow integration and it is founded on strict formal method, so that it can be analyzed and verified conveniently with mathematical methods. The limitation is that it is based on elementary algebraic expression.

Key words: workflow integration; formal semantic; semantic match; algebraic expression; function match

0 引言

跨组织工作流之间的集成技术是工作流技术的一个重要研究领域，近十年来Web服务发现技术应用于工作流集成的研究，极大地促进了工作流集成技术的发展。但仍存在着以下问题。

1）功能查找不全、匹配率较低。对于工作流集成中的功能集成，计算机如何自动发现功能是否匹配，是实现功能自动集成的一个关键技术。目前，Web服务发现技术中的语法级服务发现技术的查准率和查全率不高。

2）可行性不高。服务发现技术中的语义级服务描述基于本体，使用逻辑演绎和推理进行匹配，虽然提高了查准率和查全率，但仍然存在一些不足［1］：缺乏灵活有效的服务匹配算法；服务发现效率低下等。

因此，本文将研究的重点放在功能匹配上，对以初等代数表达式为基础的功能以集合论和一阶谓词逻辑为基础进行形式化描述，关注其前条件和后条件，并对其进行数学推理，以判定功能是否匹配。

1 国内外研究现状

关于工作流集成，众多学者从5个方向分别进行了研究，分别是：工作流模型方向［2］、资源方向［3-4］、数据/信息方向［5］、任务/功能方向以及作业/应用方向［1］。本文研究重点在任务/功能方向，探讨工作流功能集成中的功能匹配机制。

关于语义匹配，学术界从Web服务发现领域［6］、信息检索和知识发现领域［7-8］、工作流模型互操作［9］等多个领域展开了研究。

目前，学术界已经存在基于各种技术的语义匹配研究，主要包括以下两种：基于本体的语义匹配和基于VDM、B、Z、Object-Z等形式化方法的语义匹配。其中基于本体的语义匹配方法又可分为以下四类：基于模式的匹配方法、基于实例的匹配方法、基于语言学的匹配方法和基于约束的匹配方法［10-11］。形式化方法能使软件开发人员创建比使用传统开发方法产生的需求规格说明更完整无二义性的规格说明，能帮助软件开发人员更快速准确地发现系统描述中存在的不一致性、不明确性或不完整性。在一些软构件匹配的研究中，给出了形式化语义匹配的雏形，基于形式化规格说明的前、后条件匹配，并给出了多种匹配概念：完全匹配（Extract Plug-In Match）、可替代匹配（Plug-In Match）、弱匹配（Weak Postmatch）等［11］，并未见具体实现。

2 语义匹配机制

研究基于软件功能的形式化语义，即形式化规格描述V，其前条件和后条件分别为Vpre和Vpost，操作为P。当操作P执行之前Vpre成立，执行之后Vpost成立。基于软件功能的形式化语义匹配，即形式化规格描述V和M之间的前、后条件满足一定匹配算法的匹配,V和M的匹配关系可以描述为如下形式（其中关系R1 、R2可以是等价关系（冢蛘咴毯关系（荩，R3是合取词（∧）或者蕴涵词（荩）［11-12］：

match（V,M）（VpreR1Mpre）R3（VpostR2Mpost）

上面的描述中，已经给出了形式化语义匹配的基本思路，由于R1和R2可以是等价关系也可以是蕴涵关系。由前、后条件组成的匹配便有多种匹配关系。下面给出几种匹配模式［12-13］：

1）前、后条件pre/post的完全匹配（Extract pre/post Match）。当R1和R2均为等价关系（冢┣R3为合取词（∧）时，即形式化规格说明V和M的前条件和后条件严格匹配，此时V和M完全一致。形如：

match（V,M）（VpreMpre）∧（VpostMpost）

2）前、后条件pre/post的可替代匹配（Plug-In Match）。形式化规格V同形式化规格M相比，其前条件较弱，后条件较强，即形式化规格M可替代V的功能要求，匹配公式如下：

match（V,M）（MpreVpre）∧（VpostMpost）

3）前、后条件pre/post的后条件可替代匹配（Plug-In Postmatch）。不考虑前条件Pre,只考虑M的后条件是否与V的后条件相符合。弱匹配公式如下：

match（V,M）（VpostMpost）

4）前、后条件pre/post的弱匹配（Guarded Post match/Weak Post Match）。形如match（V,M）Vpre （VpostMpost）或者match（V,M）（Vpre∧Vpost）Mpost。

3 基于代数表达式的功能匹配

前面讨论的4种匹配模式中，本文只讨论前、后条件pre/post的完全匹配。高级程序设计语言所描述的程序中，功能从狭义上讲就是函数，而一个实现了某个功能的函数往往包含了大量的代数表达式。对于此类功能，首先研究基于代数表达式的功能匹配，提出相应的匹配原则及其算法。

3.1 设计原则

图1展示了在前、后条件pre/post完全匹配模式下，验证功能间的前、后条件匹配的流程。

1）首先检查输入功能的参数类型及参数个数是否完全一致（即功能的类型检查，这样做的目的是为了提高匹配的效率）。

2）然后提取功能的后条件表达式。在一个功能中，会包含很多代码或者伪代码，其中，有中间变量，也有与后条件无关的表达式等，本文只提取与后条件相关的项并进行化简等规范化处理。

3）采用预先定义的规则集对表达式进行规范化处理（表达式的形式多种多样，计算机无法像人脑那样，对不同形式的表达式进行灵活处理），以降低后面的匹配过程中的复杂度。

4）将表达式转化为二叉树。因为转换为二叉树之后，可以采用自顶向下的匹配方法，也可以采用自底向上的匹配方式。

5）最后对处理过的后条件表达式进行匹配，以便得到最终的匹配结果。

3.2 匹配规则及表达式规范化

描述一个功能，重点关注的就是前、后条件的变化，与前、后条件无关的状态、变量可以忽略。

图2描述的是对一段C语言描述的功能（函数代码）进行后条件提取的简单例子。对于功能中的表达式，可能会存在不规范的描述，为了降低功能匹配的难度，在进行功能匹配前，首先对表达式按照如下规则进行规范化处理［14-16］。

1）表达式化简。在数学运算中，主要是针对可通过基本数学运算的化简。如：6－4×8－26； x+00+xx； x/x1； 2*xx+x； x2x*x。

2）表达式符号规范化。为了降低分析表达式结构时的难度，将复合赋值号转变为二元赋值号。

x+y xx+y

x－yxx－y

x*yxx*y

x/yxx/y

自增、自减也转变为相应的二元表达式。

yx++ yx;xx+1

y++xxx+1;yx

yx－－yx;xx－1

y－－xxx－1;yx

表达式中存在括号，会增加表达式比较的难度。因此，需要消除表达式中存在的括号，可以通过使用交换律、结合律、分配率来消除表达式中的括号。

图1 代数表达式匹配流程

图2 后条件的提取

3）消除中间变量。中间变量的用途有多种，可以用于值交换、值传递等。例如：ax+2*y+3; by/7－x; za2+b2。其中：变量a和b只是起到值传递的作用，可以将这两个变量消除，不会影响到z的取值，消除两个中间变量后z的赋值表达式如下：

z（x+2*y+3）2+[（y/7）－x]2

4）表达式元素排序。表达式由常量、变量、运算符、括号等组成。在同级运算符下，变量间的顺序是不固定的。为了降低表达式匹配的难度，本文规定了同级运算符下常量、变量出现的次序：先常量，后变量，常量按值大小顺序，变量按字母表顺序。如：x1y+z+3×c，经过排序后为x13×c +y+z。同级运算符在表达式出现的次序：先加后减、先乘后除。如：sa-c+d，经过排序后为sa+c-d。

5）表达式树形化。经过规范化处理之后的表达式是一个中缀表达式，虽然中缀表达式便于理解，但是对计算机而言中缀表达式是十分复杂的结构，而逆波兰式（后缀表达式）对计算机来说是比较简单易懂的结构［16］，因此采用算法，将中缀表达式转换为逆波兰表达式。

3.3 功能匹配算法的形式化描述

定义1 形如：F〈FN,PL,T〉称为功能，其中FN（Function Name）表示功能名（狭义上可指函数名）；PL（Parameter List）表示功能参数列表（狭义上可指代前条件），包含参数的类型和参数的个数；T是功能中有关后条件的表达式的集合。

定义2 一个功能的参数列表PL经过计算后，其计算结果包含了该参数列表类型及个数，称作参数列表计算集，表示为：PLC〈FN,PT,PTC〉，其中FN表示功能名；PT（Parameter Type）表示参数列表中的类型的集合，PTC（Parameter Type Count）表示某个参数类型的个数。

定义3 一个规则p具有如下形式：p〈pl,pr〉，其中pl是规则的左部，pr是规则的右部，若pl与表达式T或T的一部分的结构相匹配，那么就可以对表达式T应用规则p，将T变换为pr的结构形式，得到表达式T′。

定义4 若干规则p一起构成了规则集P（或称规则库），P中的规则须满足以下的两种性质。

1）不可逆性。若有规则R使得表达式由结构形式α变换到β，则不存在规则S使得该表达式由结构形式β到α。例如，若规则集中包含了a*（b+c）a*b+a*c，则不再包含规则a*b+a*ca*（b+c）。这样做可以保证在应用规则集处理之后同样功能的表达式的结构形式一致，便于功能比较，同时也可避免产生死循环。

2）非传递性。若规则集中有规则R使得表达式由结构形式α变换到β，并且有规则S使得该表达式由结构形式β到γ，那么规则集中不存在规则T，使得表达式由结构形式α到γ。这样可以减少规则匹配的次数。

定义5 一个功能的后条件表达式s具有形式：s〈C,E〉，其中E表示与后条件相关的表达式，C是执行该表达式需要满足的条件。s可以描述为s（C0∧E0） ∨…∨（Cm∧Em）,m∈N。

定义6 一个功能与后条件相关的表达式s往往不止一个，那么功能的所有后条件表达式s放在一起构成了该功能的后条件表达式集S，表示为：S（s1,s2,…,sn）。

算法1 功能的类型检查算法，如图3所示。

图3 功能类型检查流程

输入 要匹配的两个功能F1和F2，F1〈FN1,PL1,T1〉，F2〈FN2,PL2,T2〉。其中，表达式集T1和T2暂不输入。

输出 若类型检查匹配成功，返回真；否则，返回假。

1）初始如果输入的功能F1或F2为空，或者二者同时为空，类型检查匹配失败，算法结束，返回假。

2）接着如果功能的参数列表PL1、PL2都为空，则类型检查匹配成功，算法结束，返回真。

3）否则继续判断它们是否有且只有一个为空，是则类型检查匹配失败，算法结束，返回假。

4）否则计算它们的功能参数列表计算集：PLC1calcn（F1），计算后得到结果为PLC1〈FN1,（pt1,…,ptn）,（ptc1,…,ptcn）〉（n∈N,n≠0）；PLC2calcn（F2），计算后得到结果为PLC2〈FN2,（pt1,…,ptm）,（ptc1,…,ptcm）〉（m∈N,m≠0）。

5）最后match（PLC1,PLC2），匹配失败，返回假；匹配成功，返回真。

算法2 功能的后条件提取算法，如图4所示。

图4 提取后条件表达式流程

输入 经过类型检查匹配成功之后的功能F，包括功能名称FN、参数列表PL以及功能F的表达式集T（后条件表达式的介绍参见3.2节）。

输出 提取成功返回功能F的后条件表达式集S；提取失败，则返回空。

1）初始若TВ提取失败，算法结束，返回空。

2）s1search（p1）（C0∧E0）∨…∨（Cm∧Em），search（p1）查找出某个后条件的表达式，并且转换为符合上式右部的形式。对于后条件表达式中的逻辑表达式采取拆分的处理方式，比如（a>0）&&（b0和b

3）若T中存在下一个元素，取T的下一个元素pi，重复执行步骤2）。

4）否则，功能F的后条件表达式集S（s1,s2,…,si-1），提取成功，返回S。

算法3 表达式规范化处理算法，如图5所示。

输入 执行算法2之后得到的后条件表达式集S；规则集P。

输出 规范化处理之后的后条件表达式集S′。

1）初始S′В蝗SВ算法结束，返回S′。

2）对于S的第一项s1，处理得到s′1change（s1,P），即依据规则集P对s1进行规范化处理，将规范化后的表达式保存到s′1中。

3）sort（s′1），依据3.2节提到的表达式元素排序规则对s′1中的项排序。读取表达式集S中的下一项si，执行以上两个步骤。

4）规范化处理完S中的所有项后，返回新的后条件表达式集S′（s′1,s′2,…,s′i-1）。

图5 表达式集的规范化处理流程

算法4 两个功能的后条件匹配算法，如图6所示。

输入 经过类型检查和规范化处理之后的功能F1和F2，包括功能名FN1和FN2，参数列表PL1和PL2；规范化处理之后的后条件表达式集S1和S2。

输出 匹配成功返回真，否则返回假。

1）初始ismatchFalse。

2）replace（PL2,PL1）,s21replace（S2,PL1），将F2中的参数列表PL2的值和S2中每一项si的参数值用PL1替换得到s2i，对于S1来说，实际上s1isi。

3）对s11（C0∧E0）∨…∨（Cm∧Em）（这里s11表示S1中第一项s1的参数用PL1替换，实际上还是s1自身）和s21（C′0∧E′0）∨…∨（C′m∧E′m）中的各项，进行逆波兰式排序revesort（Ci）（i∈N,i≠0）和revesort（Ei）（i∈N,i≠0）。

4）对表达式集的各项做匹配［17］，match′（Ci,C′j）（i∈N,i≠0; j∈N, j≠0）和match′（Ei,E′j）（i∈N,i≠0; j∈N, j≠0）。

5）若此处匹配失败，则后条件匹配失败，ismatchFalse；否则，则取S1和S2的下一个元素，继续进行第2）、3）、4）步的变换与匹配。

6）若各项均匹配成功，ismatchTrue。

图6 后条件匹配流程

4 算法验证

本文将通过一个实例，验证以上算法的有效性,即验证该算法能够从数学体系上检验两个功能是否一致，并且也不存在词义理解偏差问题。下面有4个不同的功能，描述如下。

1）求自然数N的阶乘。

方法1 用递归方法求N的阶乘，代码如下：

int fact1（int n）

{

int sum0;

if（n0） {sum1;}

else{sumn*fact1（n-1）;}

return sum;

}

方法2 用while循环求N的阶乘，代码如下：

int fact2（int m）

{

int temp1;

while（m>0）

{temp*m;m－1;}

return temp;

}

方法3 用for循环求N的阶乘，代码如下：

int fact3（int k）

{

int r1;

for（int ik;i>0;i--）

{r*i;}

return r;

}

2）求自然数1,2,…,N的和。

int sum（int k）

{

int sum0;

for（int ik;i>0;i－－）

{sum+i;}

return sum;

}

匹配过程如下。

首先运用算法1，方法1中功能F1〈fact1,int n,T1〉，对其参数列表进行计算PLC1〈fact1,（int,1）〉；方法2中功能F2〈fact2,int m,T2〉，计算PLC2〈fact2,（int,1）〉；方法3中功能F3〈fact3,int k,T3〉，计算PLC3〈fact3,（int,1）〉；对自然数求和方法中功能F〈sum,int k,T〉，计算PLC〈sum,（int,1）〉。PLC1、PLC2、PLC3和PLC进行两两匹配，匹配成功，返回匹配结果：类型检查全部匹配。

类型检查匹配成功后，运用算法2，提取后条件表达式。上述前3个方法均是求阶乘的运算，第4个方法是求和运算。

在方法1中，后条件为自然数N的阶乘，只有一个值，其表示形式为S1（s11），s11（C0∧E0）∨（C1∧E1），其中s11中各项的值为：C0{n0}; E0{sum1}; C1{n>0}; E1{sumn*（n－1）*…*1}。

同样在方法2中，S2（s21），s21（C′0∧E′0）∨（C′1∧E′1），其中s21中各项值为：C′0{m0}; E′0{temp1}; C′1{m>0}; E′1{temp1;temp*m*（m－1）*…*1}。

在方法3中，S3（s31），s31（C″0∧E″0）∨（C″1∧E″1），s31中各项值为：C″0{k0}; E″0{r1}; C″1{k>0}; E″1{r1;r*k*（k－1）*…*1}。

在方法4中，S（s1），s1（C30∧E30）∨（C31∧E31），其中s1中各项值为：C30{k0}; E30{r1}; C31{k>0}; E31{r1;r+k+（k－1）+…+1}。

返回表达式集S1、S2、S3和S。

采用算法3对S1、S2、S3和S进行规范化处理，结果如下：

S1规范化处理之后的表达式为：C0{n0}; E0{1}; C1{n>0}; E1{n*（n－1）*…*1}。

S2规范化处理之后为：C′0{m0}; E′0{1}; C′1{m>0}; E′1{m*（m－1）*…*1}。

S3规范化处理之后为：C″0{k0}; E″0{1}; C″1{k>0}; E″1{k*（k－1）*…*1}。

S规范化处理之后为：C30{k0}; E30{1}; C31{k>0}; E31{k+（k－1）+…+1}。

S1、S2、S3和S采用算法4进行匹配，首先对S2、S3和S中参数列表及表达式中的参数值进行替换：

C′0{n0}; C″0{n0};

E′0{1};E″0{1};

C′1{n>0};C″1{n>0};

E′1{n*（n－1）*…*1}; E″1{n*（n－1）*…*1};

C30{n0};

E30{1};

C31{n>0};

E31{n+（n－1）+…+1}

接下来对四个表达式集的各项进行逆波兰式排序：

C0{n0}; C′0{n0};

E0{1};E′0{1};

C1{n0>};C′1{n0>};

E1{n（n－1）*…*1*};E′1{n（n－1）*…*1*};

C″0{n0};C30{n0};

E″0{1};E30{1};

C″1{n0>};C31{n0>};

E″1{n（n－1）*…*1*};E31{n（n－1）+…+1+}

之后两两进行匹配，S1、S2和S3匹配成功，说明fact1、 fact2和fact3这三个功能实现的功能是匹配的，S和S1、S2、S3三个中任一匹配都不成功，说明sum与fact1、 fact2、 fact3要实现的功能不同。

5 结语

本文以实现工作流系统自动集成为目标，对基于形式化语义的前、后条件pre/post完全匹配机制进行了实现，提出了以代数表达式为基础的前后条件pre/post的完全匹配的原则，并且给出了相应算法，最后用一个实例验证了该算法的有效性。该匹配机制源自于以集合论和一阶谓词逻辑为基础的形式化规格描述，避免了关键字理解意义上的偏差，一定程度上提高了功能查准率和查全率，适用于工作流集成中的功能匹配，为工作流功能的自动查找奠定了基础。该方法局限于初等代数性的前提，而实际情况中，抽象机作为一种伪程序设计语言，用它描述的程序不仅能够采用过程性程序设计语言书写，更关键的是它的每种结构都有精确的公理化定义，对于数学分析来说尤为重要。因此，基于抽象机的功能匹配是下一步的研究内容。

参考文献:

[1] PAPAZOGLOU M P, van den HEUVEL W J. Service oriented architectures: Approaches, technologies and research issues ［J］. The International Journal on Very Large Data Bases, 2007, 16（3）: 389-415.

［2］ 张静，王海洋，崔立真.基于Pi演算的跨组织工作流建模研究［J］.计算机研究与发展，2007，44（7）：1243-1251.

［3］ XU LIDA, LIU HUIMIN, WANG SONG, et al. Modelling and analysis techniques for cross-organizational workflow systems ［J］. Systems Research and Behavioral Science, 2009, 26（3）: 367-389.

［4］ LIN QIANG, GE JIDONG, HU HAO, et al. An approach to model cross-organizational processes using object Petri net ［C］// SCW 2007: 2007 IEEE International Conference on Services Computing-Workshops. Washington, DC: IEEE Computer Society, 2007: 146-152.

［5］ 吴长中.工作流中的数据集成技术研究［D］.长沙：国防科学技术大学，2002.

［6］ KOURTESIS D, PARASKAKIS I. Combining SAWSDL, OWL-DL and UDDI for semantically enhanced Web service discovery ［C］// ESWC' 08: Proceedings of the 5th European Semantic Web Conference on the Semantic Web: Research and Applications, LNCS 5021. Berlin: Springer-Verlag, 2008: 614-628.

［7］ 张小娟，李华.网格环境下基于语义关联的信息检索［J］.计算机应用，2009，29（6）：1517-1526.

［8］ 樊晓光，褚文奎，万明.基于领域本体的软构件检索［J］.计算机科学，2009,36（6）：156-158.

［9］ 袁世伦，李胜利，袁平鹏，等.一种基于规则的工作流模型互操作的实现方法［J］.计算机应用，2007，27（2）：400-402.

［10］ ZHANG JIDONG, HUO WEIPENG. Research on the composition mechanism of semantic Web services ［C］// ICCSIT 2010: Proceedings of the 3rd IEEE International Conference on Computer Science and Information Technology. Washington, DC: IEEE Computer Society, 2010: 100-103.

［11］ 王淑红，袁兆山.基于排序形式化规格说明的软构件匹配［J］.合肥工业大学学报，2000，23（4）：477-481.

［12］ HEMER D. Semi-automated component-based development of formally verified software ［C］// REFINE 2006: Proceedings of the 11th Refinement Workshop on Electronic Notes in Theoretical Computer Science. Amsterdam, Netherlands: Elsevier, 2007: 173-188.

［13］ 马亮，孙家.基于规约匹配的构件检索［J］.小型微型计算机系统，2002，23（10）:1153-1157.

［14］ 樊敏.程序作业自动测评的研究与实现［D］.广州：广东工业大学，2005.

［15］ 刘洋，欧阳春宜，施崇明.一类算术表达式的语法分析及规范化方法［J］.赣南师范学院学报，2003（3）:21-23.