匹配算法论文篇（1）

中图分类号： TN711?34； TP393 文献标识码： A 文章编号： 1004?373X（2016）15?0008?06

Abstract： The various applications of wireless sensor networks （WSNs） are restrained by the sensor′ battery in severe environment， and the WSNs face various difficulties in data collection， so the wireless energy transfer technology used to replenish the energy of sensor cluster is proposed. Aiming at the wireless rechargeable senor cluster deployed in severe environment， an efficient data collection scheme is proposed. In the scheme， the unmanned aerial vehicle （UAV） is used to arrive at the site of the sensor cluster in severe environment， after that the data is collected， and the sensors corresponding to the cluster are charged. In this paper， the utility function of data collection is defined to describe the data collection problem as an optimal problem taking utility maximization of data collection as the target， and the greedy algorithm based on bilateral preference matching and unilateral preference matching algorithm are proposed to solve the above problems. The theoretical analysis and simulation experiment results show that the matching relation of UAV and sensor cluster determined with the proposed greedy algorithm can generate the optimal solution of making data collection utility maximum， and can realize the efficient collection of sensor data.

Keywords： wireless sensor network； data collection； unilateral matching； greedy algorithm； optimal solution

0 引 言

在过去10年间，无线传感器网络（Wireless Sensor Network，WSN）获得了人们的广泛关注[1?2]。究其原因，一方面是因为WSN部署简单，另一方面是因为在战场侦察、环境监测、生物观察等领域具有巨大的应用潜力[3?4]。数据处理和计算技术的进步，使传感器可以测量多种领域中的数据（比如温度、压力、光照、湿度及红外线等）。但是电池技术进展缓慢，使电量有限的传感器受到严重的能量约束。此外，人们还希望利用WSN对广大区域实现无人值守式观察。虽然传感器部署简单（比如通过飞机散播在广大区域上），但是使WSN保持长时间运行，在大面积部署区域尤其是恶劣环境条件下实现传感数据的高效收集（比如高温沙漠、密林、雪山），难度很大[5]。

为了避免传感器的能量消耗完，学者们已经提出了多种能量节约[6]、环境能量利用[7?8]和增量部署算法[9]。然而，能量节约算法只能延缓能量被消耗的步伐，无法补充能量。对太阳能、风能和振动能等环境能量进行利用时，会受到这些能量可用性的约束，且这些能量的可用性往往不受人力控制。此外，部署的传感器节点可能会污染环境，因此增量部署算法对环境不够友好。

无线能量传输技术在近期取得突破[10]，为WSN的传感器能量补充提供了一种有力途径。具体来说，文献[11]中提出了3种无线能量传输技术，即：感应耦合技术、电磁辐射技术及磁共振耦合技术，同时介绍了这些技术在WSN中的应用。美国国家航空航天局（NASA）的电磁辐射实验[12]证明了能量远距离高效传输的可行性：在Goldstone网络实验中，NASA在1.5 km的距离上传输了34 000 W的能量，效率达到82%。另外，无人机（Unmanned Aerial Vehicle，UAV）技术越来越成熟，成本也不断下降。在此背景下，文献[13]利用一个无人机携带充电设备，周期性地访问传感器集群，对传感器实施无线充电，进而使WSN永久工作。文献[14]设计了一种移动式无线充电车，并通过实验验证了无线充电车在为WSN补充能量方面的性能。虽然在这些创新性研究中传感器能量得以补充，但WSN将数据以多跳方式从数据源向Sink节点传输时仍然浪费了大量能量。此外，对于部署在恶劣环境中的传感器集群，无线充电设备到达这些区域并收集这些感应数据将会消耗大量时间和成本。针对以上不足，本文并不是使用无线充电车，而是提出使用无人机携带无线充电器（如图1所示），同时利用UAV选择传感器集群，飞往被选择的传感器集群，并对集群中的传感器进行充电，同时将这些集群中的感应数据传输给Sink节点。本文的主要工作如下：

（1） 提出利用携带无线充电传输设备的UAV收集部署于恶劣环境下的传感器集群的感应数据，同时对相应集群中的传感器补充能量。具体而言，本文根据UAV到传感器集群间的距离、从传感器集群收集到的数据以及集群内传感器的剩余能量，定义了数据收集效用函数，并将数据收集问题描述为以数据收集效用函数最大化为目标的优化问题。

（2） 提出单边匹配算法和基于双边偏好匹配的贪婪算法解决上述问题，并通过理论分析和仿真实验验证了利用本文贪婪算法确定UAV和传感器集群间的匹配关系可生成使数据收集效用最大化的最优解，且可实现传感器数据的高效收集。

1 网络模型

假设在感应/监测应用中，多个传感器集群部署于恶劣环境中。每个集群包括一个中央Sink节点和一组传感器，其中传感器将其感应到的数据周期性地发往Sink节点。为了补充传感器的能量损耗、收集传感器的感应数据，利用一个或多个UAV飞往传感器集群，对集群中的传感器进行充电，通过相应集群中的Sink节点收集传感器感应数据。网络模型如图2所示。

2 本文算法

下面以匹配理论为基础，提出两种分布式算法来获得上述问题的最优解。首先给出单边偏好匹配算法，然后根据文献[15]中的Gale?Shapley算法将单边偏好匹配算法扩展为基于双边偏好匹配的贪婪算法。最后通过理论分析证明了算法的正确性。

2.1 匹配定义

匹配理论主要是解决如何将一组不可分的物品分配给一组申请人。每个申请人可能有多种偏好。以上述匹配概念为基础，可将本文研究的数据收集问题阐述如下：

设有一个实例[I]表示一组UAV[N=UA1，UA2，…，UAn]及一组传感器集群[?=SC1，SC2，…，SCm]。实例[I]中的主体是[??N]中的UAV和传感器集群。可接受的UAV?SC匹配对为集合[ε?N×?]。每个UAV[UAi∈N]有一组可接受的传感器集群[AUAi，]其中[AUAi=][SCj∈?：UAi，SCj∈ε]。类似地，每个集群[SCj∈?]有一个可接受的申请人[ASCj，]其中[ASCj=][UAi∈N ：UAi，SCj∈ε]。本文将[UAi]和[SCj]的匹配关系定义如下：

定义1 匹配关系[Φ]为如下函数：

[ΦUAi∈???，]且[ΦUAi∈0，1，…；ΦSCj∈][N ??，][ΦSCj∈0，1，]其中[ΦUAi=SCj]且[ΦSCj=][UAii∈N， j∈?]。

该定义表明，如果函数的输入是[SCj，]则[Φ]是一个单对单匹配。另一方面，如果函数的输入是[UAi，]则[Φ]是一个多对单匹配。在匹配理论中，本文中的主体（即UAV和SC）需要一个偏好列表才能开始匹配过程。因此，本文在选择传感器集群进行能量补充和数据收集前，要求每个[UAi]根据自己相对所有集群的效用形成一个降序排列的偏好列表。

2.2 单边偏好匹配算法

单边偏好匹配算法如下，分为两步：第一步，计算UAV的效用函数，然后，构建降序排列的偏好列表[UALISTi，]同时构建一组未匹配的传感器集群[UNMATCH；]第二步，根据偏好列表[UALISTi]构建匹配关系。[UAi]向[UALIST]中层次最高的未匹配集群[SCj]做出申请，并将[SCj]从[UNMATCH]中移除。如果[UNMATCH≠?]，则算法回到第2步开始。算法不断进行匹配过程的迭代，直到[UNMATCH=?]。

3. 算法结束

2.3 贪婪算法：双边偏好匹配

第2.2节从UAV角度给出了单边偏好匹配算法。为了进一步提升系统效用，本文进行双边偏好匹配，即从UAV和传感器集群两个角度进行匹配。

传感器集群也可以构建它们自己的偏好列表。然后，每个[UAi∈N]或每个[SCj∈?]均有一个按严格次序排列且互不相同的偏好列表。

文献[15]提出一种可以始终找到稳定性匹配关系的Gale?Shapley算法。本文以该算法为基础提出一种贪婪算法。在第一阶段，它计算UAV和传感器集群的效用函数。然后，构建按降序排列的偏好列表[UALISTi]和[SCLISTj]。它还构建未匹配传感器集群组成的集合UNMATCH。根据偏好列表[UALISTi，][UAi]向[UALISTi]列表中之前从未拒绝过自己且层次最高的集群[SCj]做出申请。如果[SCj]还未被匹配，则保留配对[UAi，SCj]。如果[SCj]已经被匹配，则[SCj]检察新采用的[UAi]和上一次迭代时的[UAi]的等级。[SCj]与其[SCLISTi]列表中等级较高者匹配，排除另外一个。被拒绝的[SCj]添加到UNMATCH中，等待下一轮匹配过程。如果[UNMATCH≠?，]则算法回到第2步。即使[UNMATCH=?，]但[UAi]还没有结束对所有[SCj（j∈?）]的申请，则算法仍然回到步骤2。只有[UNMATCH=?]且每个UAV均申请过所有[SCj（j∈?）]时，算法才终止。

3.算法结束

2.4 理论分析

为了便于分析，下面首先给出了“最优匹配”的定义。

定义2 最优匹配：如果在约束条件[j∈?xij≤1]下，对匹配关系[Φ，]式[i∈Nj∈?UUAji]被最大化，则认为[Φ]为最优匹配。

以该最优匹配定义为基础，有如下理论：

定理1 贪婪算法获得的匹配关系[Φg]为最优匹配。

证明：如果对匹配关系[Φ，]在约束[j∈?xij≤1]下，式[i∈Nj∈?UUAji]最大化，则每个[SCj]必与其偏好列表中层次最高的[UAi]相匹配，现将其表示为[UAjf]。

假设[Φ]最优，但是至少有一个[SCj]不与其[UAjf]匹配。根据贪婪算法，在第一轮中，[SCj]与向其申请且等级最高的[UAi]匹配，现将其表示为[UAjrh]。在下一轮中，如果新申请的[UAjrh]级别高于[UAjrh，]则[SCj]将会与[UAjrh]匹配且[UAjrh]被拒绝。因此，发现[SCj]总是与UAV中级别最高且向[SCj]做出申请的UAV相匹配。每个[UAi]有一个偏好列表包括所有的[SCjj∈?]，这说明所有的UAV将会向各个[SCj]做出申请。于是，每个[SCj]均与其[UAjf]匹配，与至少有一个[SCj]不与其[UAjf]相匹配的结论相矛盾。所以，贪婪算法获得的匹配关系[Φg]是最优匹配。证毕。

3 性能评估

3.1 仿真配置

本文利用部署在10 km[×]10 km区域上的UAV和传感器集群进行仿真实验。电池容量为[emax=70 J，][SCj]中传感器节点的剩余能量为[ejk∈60，65 J]。每个集群中的传感器数量为[SCj∈50，100]。发射功率为[Si=1.2 W，]UAV的速度为120 km/h。对于其他参数，传感器的数据率从[1，10] Kb/s中随机生成。在网格拓扑和随机拓扑结构上分别进行了仿真实验，取20次仿真结果的平均值作为最终的实验结果。

3.2 结果和分析

为了评估本文算法的性能，对最优匹配、贪婪算法、单边匹配算法以及随机匹配算法进行了比较。图3给出了UAV数量固定时的仿真结果，此时传感器集群数量为25～40个，传感器集群分别部署于网格拓扑和随机拓扑结构上。从图3中可以发现，本文提出的贪婪算法的性能和最优匹配的性能一样，而单边匹配算法的性能远优于[UAii∈N]和[SCjj∈?]的随机匹配算法。因为单边匹配算法考虑了UAV的偏好列表，每个[UAii∈N]有机会向其[UALISTi]偏好列表中的最高级别[SCj]做出申请，所以单边匹配算法的性能优于随机匹配算法。此外，贪婪算法的性能优于单边算法。在贪婪算法中，集群在构建偏好列表时的效用函数与UAV进行决策时的效用函数相同。[SCj]可拒绝向其做出申请的[UAi，]选择可显著提升系统效用的更为合适的UAV。

图4给出了系统效用随网络规模的变化关系。当网络规模增加时，系统效用增加。此外，当网络规模增加时，贪婪算法与单边算法及随机匹配算法间的性能差异增加。这表明，当UAV的数量和位置固定时，相比于单边匹配算法和随机算法，本文贪婪算法更适用于大规模WSN。当网络规模增加时，受欢迎传感器集群的数量也在增加（在所有UAV偏好列表中均有较高等级的集群定义为受欢迎集群）。无论在单边匹配算法还是随机匹配算法，受欢迎集群均无法拥有其偏好列表。因此，传感器集群很可能做出非最优决策，降低系统效用。

图5给出了匹配决策和航行时间之间的关系。为便于讨论，这里只给出包含两架UAV的情况。采用贪婪算法确定UAV和集群间的匹配。星星表示UAV飞到每个集群处的时间，方形表示飞到与[UAi]相匹配的[SCj]处的航行时间，圆圈表示飞到未被匹配[SCj]处的航行时间，该时间至少比一个被匹配的[SCj]短。在图5中发现虽然部分集群与UAV较近，但它们未与任何UAV相匹配，这是因为匹配决策不仅与航行时间有关，还与充电时间和传感器集群的数据量有关。匹配关系并不只存在于相距最近的UAV和传感器集群间。此外，在图3中还发现最优算法的曲线与贪婪算法的曲线相吻合。仿真实验证明了贪婪算法确定的匹配关系是最优匹配这一结论。

4 结 语

本文研究了如何使用UAV高效收集部署于恶劣环境中的无线可充电传感器集群的感应数据。通过考虑无线能量传输的特点，将高效数据收集问题描述为多种约束条件（即UAV和集群间的距离，集群中Sink节点处汇集的数据量以及集群中传感器的剩余能量）下的优化问题。为了使上述问题中的系统效用最大，提出两种基于匹配理论的分布式算法，单边匹配算法和贪婪算法，同时证明贪婪算法最优。仿真实验验证了本文的理论分析结果，证明本文算法可实现感应数据的高效收集，同时可对恶劣环境中的传感器集群充电。在下一步工作中，将分析移动Sink条件下传感器节点无线充电与数据收集质量的关系，研究面向高效数据收集的移动Sink路径规划算法。

参考文献

[1] 李建中，高宏.无线传感器网络的研究进展[J].计算机研究与发展，2008，45（1）：1?15.

[2] 郭忠文，罗汉江，洪锋，等.水下无线传感器网络的研究进展[J].计算机研究与发展，2010，47（3）：377?389.

[3] 张豫鹤，黄希，崔莉.面向交通信息收集的无线传感器网络节点[J].计算机研究与发展，2008，45（1）：110?118.

[4] GUO S， HE L， GU Y， et al. Opportunistic flooding in low?duty?cycle wireless sensor networks with unreliable links [J]. IEEE transactions on computers， 2014， 63（11）： 2787?2802.

[5] ZHAO M， LI J， YANG Y Y. A framework of joint mobile energy replenishment and data gathering in wireless rechargeable sensor networks [J]. IEEE transactions on mobile computing， 2014， 13（12）： 2689?2705.

[6] BOUABDALLAH F， BOUABDALLAH N， BOUTABA R. Cross?layer design for energy conservation in wireless sensor networks [C]// Proceedings of 2009 IEEE International Conference on Communications. Dresden： IEEE， 2009： 1?6.

[7] PARK C， CHOU P H. AmbiMax： autonomous energy harves?ting platform for multi?supply wireless sensor nodes [C]// Proceedings of 2006 3rd Annual IEEE Communications Society on Sensor and Ad Hoc Communications and Networks. Reston： IEEE， 2006： 168?177.

[8] FAN K W， ZHENG Z， SINHA P. Steady and fair rate allocation for rechargeable sensors in perpetual sensor networks [C]// Proceedings of the 6th ACM Conference on Embedded Network Sensor Systems. Raleigh： ACM， 2008： 239?252.

[9] PENG Y， LI Z， ZHANG W， et al. Prolonging sensor network lifetime through wireless charging [C]// Proceedings of 2010 31st IEEE Real?Time Systems Symposium. San Diego： IEEE， 2010： 129?139.

[10] BEH T C， KATO M， IMURA T， et al. Automated impedance matching system for robust wireless power transfer via magnetic resonance coupling [J]. IEEE transactions on industrial electronics， 2013， 60（9）： 3689?3698.

[11] XIE L， SHI Y， HOU Y T， et al. Wireless power transfer and applications to sensor networks [J]. IEEE wireless communications， 2013， 20（4）： 140?145.

[12] WANG R， YE D， DONG S， et al. Optimal matched rectifying surface for space solar power satellite applications [J]. IEEE transactions on microwave theory and techniques， 2014， 62（4）： 1080?1089.

匹配算法论文篇（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）

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

参考文献

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

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

匹配算法论文篇（4）

 

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)

匹配算法论文篇（5）

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2013）01-0088-04

1 概述

信息技术地不断发展出现了越来越多的以图作为逻辑表达的数据，例如城市规划中的建筑模型、化学分子结构式，生物网络，社会网络图中的实体关系和图像检索等等。从图数据中发现有用的知识已成为图数据查询领域一项重要的研究课题。图查询是其中最重要的一个研究分支，因为与图有关的绝大部分应用（例如：图查询、图分类、图聚类等）都需要利用图来管理、查询和分析图数据。

对于在大量累积的图数据（即图数据库）上进行查询处理的问题，已有的对图数据库查询处理的研究工作主要包括两大类：一类是在小尺寸图的大规模集合（简称为集合类图数据库）上处理查询，其中包括子图查询处理、超图查询处理和相关子图查询处理等；一类是在一个或为数不多的大尺寸图（简称为大图类图数据库）上处理查询，如子图匹配查询处理、可达查询和最短路径/距离查询等。然而，这些方法全部针对确定图数据，无法应用到不确定图数据的查询处理中。对不确定图数据库中多种查询类型（如子图匹配查询）的高效处理是一项具有挑战性的工作.因此对图数据的查询处理方法的研究具有现实意义和理论价值，有待探索.

虽然遗传算法是非常优秀的智能优化算法，但是目前大多数应用都可以归纳为解决路径问题，比如TSP问题，而将其与计算机数据的图数据匹配的研究还很少[6]。

本文针对不同的拓扑结构图，对两个图是否相似的过程采用遗传算法进行讨论，对于种群进化的过程思路进行拓展研究，在算法复杂度上对比现有的深度优先搜索、宽度优先搜索等算法得出遗传算法应用于图匹配问题的新解。

匹配算法论文篇（6）

 

1.引言

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

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

2.1 传统的被动定位技术

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

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

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

2.2.1 远程定位精度不高

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

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

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

3. 匹配场被动定位技术

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

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

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

图1 匹配场定位原理图。

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

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

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

4.水下GPS定位

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

5.结束语

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

参考文献：

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

匹配算法论文篇（7）

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2013）33-7571-04

随着互联网的不断普及和数字化技术的快速发展，数字图像日益丰富，为了能够从大量得图像库中快捷、确地找到用户所需要的图像，必须借助于计算机技术进行机器识别。识别过程首先需要将已知图像和陌生图像的全部或部分在二维空间上对齐，然后选取合适的图像特征，并根据相似度模型，在陌生图像中寻找与已知图像近似的子图，这一比较过程就是图像匹配。基于内容的图像检索[1]（CBIR，Content-based image retrieval），是计算机视觉领域中关注大规模数字图像内容检索的研究分支，众多的图像匹配算法为其提供理论支撑。该文将全面剖析当今各种图像匹配技术，重点分析其中的SSDA[2]图像匹配算法，并最终将粒度计算[3]引入其中，提出基于粒度计算的自适应阀值SSDA匹配算法。

1 图像特征

图像匹配的关键因素在于选取用于描述陌生图像中潜在匹配子图和已知图像的特征。理想状态的图像特征能够有效表示图像本质，并且不受图像中物移、旋转和变形影响。但是现实情况是：成像环境的影响、采样条件的差异、预处理计算的误差等都会造成陌生图和已知图像的不一致，从而干扰图像特征的选取，最终影响图像匹配的精确度。

1.1 基本特征

研究中应用最广泛的图像特征有：形状、纹理、颜色、空间关系等特征。

形状特征：是一种局部特征，通常包括区域和轮廓特征两部分。区域特征描述的是图像中对象的整个形状区域，而轮廓特征则主要针对图像中对象的外边界。从图像中分割出对象之后，形状因子与尺寸因子结合起来可以用于区分不同物体，机器视觉系统常常使用各种基于形状特征的检索方法来检索图像中感兴趣的目标。

纹理特征：是一种全局特征，表现为图像区域中对象的表面特质。由于纹理仅仅是物体表面特性的一个方面，所以不能完全体现物体的本质属性，仅仅利用纹理特征已无法获得抽象的图像内容的。纹理特征往往需要对图像区域中多个像素点进行统计才能得出。图像匹配中纹理特征的区域性具有较大的优越性，不会由于局部偏差导致匹配失败。同时图像特征是一种统计特征，具有旋转不变性，有较强的噪声抵抗能力。纹理特征得缺点是：随着图像的分辨率发生变化，统计出来的纹理特征值有较大偏差，另外光照、反射等因素也会干扰纹理特征的准确度

颜色特征：与纹理特征一样表现为图像区域中对象的表面特质，也是一种最常用的全局特征。与纹理特征不同，颜色特征一般体现在像素点的颜色特征上，所有图像区域的像素点都为该图像的颜色特征作出贡献。但是颜色特征对图像的方向、尺寸等性质不敏感，因此颜色特征不能有效的体现图像中对象的局部特征。

1.2 特征提取

提取颜色特征可以采用颜色直方图，其优点在于：它能简单描述一幅图像中颜色的全局分布，即不同色彩在整幅图像中所占的比例，特别适用于描述那些难以自动分割的图像和不需要考虑物体空间位置的图像。其缺点在于：它无法描述图像中颜色的局部分布及每种色彩所处的空间位置，即无法描述图像中的某一具体的对象或物体。改进的颜色直方图包括：直方图相交法、参考颜色表法、累加颜色直方图法等。

提取纹理特征可以采用Gotlieb和Kreyszig等人提出的灰度共生矩阵的纹理特征分析法，通过对图像的能量谱（灰度共生矩阵的四个关键特征：能量、惯量、熵和相关性）函数的计算，提取纹理的粗细度及方向性等特征参数；也可以采用以Voronio棋盘格特征法为代表的几何法——建立在纹理基元（基本的纹理元素）理论基础上的一种纹理特征分析方法。纹理基元理论认为，复杂的纹理可以由若干简单的纹理基元以一定的有规律的形式重复排列构成；也可以采用以马尔可夫（Markov）随机场（MRF）模型法和 Gibbs 随机场模型法为代表的模型法——以图像的构造模型为基础，采用模型的参数作为纹理特征；其他方法包括：Tamura 纹理特征法（基于人类对纹理的视觉感知心理学研究，提出6种属性，即：粗糙度、对比度、方向度、线像度、规整度和粗略度）、自回归纹理模型法（simultaneous auto-regressive， SAR）、小波变换等。

2 相似度计算

为了量化陌生图像中潜在的匹配子图和已知图像间的相似程度，通常需要使用距离测度来完成。

2.1 理想距离测度

理想距离测度指的是陌生图像的特征元素与已知图像的特征元素是一致的，即有一一对应的关系。

假设在复合特征空间中，陌生图像的特征序列为：矢量[X=x1，…，xi，…，xnT]，已知图像的特征序列为：矢量[Y=y1，…，yi，…，ynT]，[xi]和[yi]为对应的特征元素的量化值（也可为矢量）。

复合特征空间的匹配程度刻画为矢量[X]和矢量[Y]之间的距离测度，用[dX，Y]表示。

1）马氏距离（Mahalanobis distance）[4]

[dMX，Y=X-YTS-1X-Y]

马氏距离要求已知图像的复合特征矢量[Y]符合协方差矩阵[S-1]的正态分布。由于该算子考虑了已知图像复合特征的离散程度，其分类能力优于下述两种距离。

2）城市块距离（City block distance）

[dX，Y=X-Y1=i=1nxi-yi]

3）欧氏距离（Euclidean distance）

[dX，Y=i=1nxi-yi2]

2.2 通用距离测度

其实匹配时，要保证每一幅陌生图像的特征元素都和已知图像的特征元素一致是几乎不可能的。在实际应用中，甚至连已知图像库中的每一副样本图像的特征元素是的一致性也不能百分之百的保证。通常，解决这个问题的方法是采用豪斯多夫距离（Hausdorff distance）[5]，即利用计算集合的相似程度来刻画图像间的相似度。

假设在复合特征空间中，陌生图像的特征集合为[X=x1，…，xi，…，xnn>0]，已知图像的特征集合为[Y=y1，…，yi，…，ymm>0]。则这两个特征集合之间的豪斯多夫距离定义为：

[dHX，Y=maxsup infxi∈X yi∈Ydxi，yi，sup infyi∈Y xi∈Xdxi，yi]

其中，[xi]、[yi]分别是集合[X]与集合[Y]中的点，[sup]、[inf]分别表示集合的上确界和下确界，[dxi，yi]表示[xi]与[yi]之间的欧式距离。

由上式可知，豪斯多夫距离[dHX，Y]度量了两个特征集合间的最大不匹配程度，结果距离越小，则表示匹配程度越高。

3 匹配算法

3.1 传统匹配算法

图像分割：把图像分成若干个特定的、具有独特性质的区域，它是由图像处理到图像分析的关键步骤。现有的图像分割方法主要分以下几类：基于阈值的分割方法、基于区域的分割方法、基于边缘的分割方法以及基于特定理论的分割方法等。灰度阈值分割法[6]作为一种最常用的并行区域技术在实际应用中使用的最频繁。其分割算法如下：

[gi，j=1 f（i，j）≥T0 f（i，j）

其中，[f]为输入图像，[g]为输出图像，[T]为阈值。阈值分割的优点是计算简单、运算效率较高、速度快。

图像对齐：根据一幅陌生图像在众多的已知图像中检测出匹配的子图，即得到已知图像在陌生图像中到位置是一件复杂的工作。因为已知图像与陌生图像中潜在的匹配子图间可能存在旋转、位移、缩放、倾斜等非线性变换，所以在传统匹配算法中，陌生图像中潜在的匹配子图K和已知图像S存在下述对齐关系：

[xy≈α11α12α21α22x，y'+φ1φ2]

其中图像点[x，y∈K]，图像点[x，，y'∈S]，[αij]和[φi]是常量。考虑到成像噪音的影响，用“[≈]”符号表明陌生图像中潜在的匹配子图可以由已知图像的高阶多项式近似表示。

图像匹配：经过了图像分割和图像对齐就可以在已知图像中搜索与陌生图像潜在子图匹配的图像了。假设陌生图像的尺寸为[M×N]，已知图像尺寸为[m×n]，其中[M≥m]，[N≥n]。采用逐点比较的算法进行比较，等概率的情况下，需要的平均比较的次数为：[M-m+1×N-n+1×m×n/2]。一对一图像的比较尚且如此，一对多的匹配运算的数量级，是单台计算机绝对无法承受的。

3.2 改进的匹配算法

传统的匹配算法效率低下的关键点在于：每一次匹配结论都必须等到陌生图像和已知图像中某一潜在子图的完全匹配结束才能得出。如果能在比较的过程中发现两者差异较大而立刻放弃当前匹配，并提前进入下一轮匹配，那么匹配效率将大大提高。目前由Barnea提出的序贯相似性检测算法（SSDA）能够比较方便地做到这一点，但是起效率仍然有待提高。该文采用的匹配策略基于SSDA算法的思想，并融入了粒度计算的理念。

传统SSDA算法

1）定义绝对误差值

[εi，j，mk，nk=Si，jmk，nk-1M2m=1Mn=1MSi，jm，n-Tm，n+1M2m=1Mn=1MTm，n]

2）取一个不变的阀值[Tk]

3）在子图[Si，jmk，nk]中随机选择像素点，计算它同T中相应点的误差值[ε]，并进行累加，当经过[r]次累加，误差和超过[Tk]，则马上停止累加，并记下当前[r]值。定义该算法的检测曲面为：

[Ii，j=r|min1≤r≤m2k=1rεi，j，mk，nk≥Tk]

4）重复第3）步，计算所有点的[r]值，选取[Ii，j]值最大的点[i，j]作为匹配点。

粒度计算

粒度计算是一种全新的信息处理模式，它的对处理对象是信息粒（Information Granule）——一种复杂的信息实体。从理论上来说，对待同一事物，粒度计算主张通过设置不同的分辨率或尺寸，对计算中出现的知识进行辨识、认知以及阐述。

针对传统的SSDA算法，匹配的过程等效于遍历，除同位点外，其它点的搜索显得非常无用，浪费了大量的时间，最终影响匹配效率。该文借助于粒度计算的思想，采取金字塔式的搜索策略[7]，通过控制粒度由粗到细的变化过程逐步找到原始陌生图像中潜在匹配子图的的精确匹配点，减少SSDA算法匹配搜索时间。若选取图像分辨率（即子带尺寸）作为粒度的标准，选取灰度作为图像的匹配特征，则粒度分层算法如下：

1）分别求取待匹配的两副原始图像中所有像素点灰度平均值记为[G0]，该层定义为[L0]层。

2）将待匹配的两副原始图像分别分割成为粒度更小的[2×2]的4个子带，再求取每个子带域中像素点灰度平均值，分别记为[Gi，j0≤i≤1，0≤j≤1]，该层定义为[L1]层。

3）以此类推，通过对[Lm-1]层的子带进行再划分，可以定义粒度更小的[Lm]层，其每个子带域中像素点灰度平均值，分别记为[Gi，j0≤i≤2m，0≤j≤2m]。

4）定义[Ln]层为原始图像层。

按照粒度由大到小的顺序，通过划分可以得到一个图像分层序列：[L0，…，Li，…Ln]，他们的分辨率也是由大变小。改进的匹配过程如下：

首先从两副图的低分辨率[L1]层开始匹配，确定匹配的大致位置，由于[L1]层粒度大、维数小，匹配过程会非常高效，但是由于分辨率太低，可能会出现多个匹配位置[P1，i1≤i≤2]。然后在[L2]层上进行匹配搜索，与传统的SSDA算法不同的是，此时只在上一次得到的匹配点[P1，i]附近进行搜索，所以计算量不会大，得到的新的匹配点记为[P2，i1≤i≤4]。以此类推，基于第[Lm-1]层的匹配点[Pm-1，i1≤i≤2m-1]，可以更加精确的获取第[Lm]层的匹配点[Pm，i1≤i≤2m]。最终达到原始图像[Ln]层，匹配过程结束。

3 实验及结果分析

为了验证将粒度计算法引入图像匹配技术的有效性，特地在.NET环境下开发一套测试软件，在已知图像T中对陌生图像S进行匹配，寻求人物潜在的“眼睛”，实验得出各种匹配算法的耗时数据表：

从表1中数据可以看出：NCC（归一化相关匹配算法）效率最低；传统SSDA由于没有进行算法优化，承担了巨大的计算量，比起NCC算法效率提升不够明显；而本文提出的综合改进算法在进行特征匹配时优势明显，具有很高的实时性和技术可行性。

4 结论

本文将全面剖析当今各种图像匹配技术，研讨了将粒度计算引入到图像匹配技术中的具体实现细节，提出基于粒度计算的自适应阀值SSDA匹配算法，并且通过试验证明该算法的实用性和高效性，取得了令人满意的结果。

参考文献：

[1] 钱晶，高月松.图像检索系统中的CBIR技术研究[J].电脑知识与技术，2011（2）.

[2] 刘晓光，陈曦，陈政伟，等. 基于图像灰度的SSDA匹配算法[J].航空计算技术，2010（1）.

[3] 张铃，张钹. 模糊商空间理论（模糊粒度计算方法）[J].软件学报，2003（4）.

[4] Gnanadesikan， Ramanathan，Kettenring， John R.Robust estimates， residuals， and outlier detection with multiresponse data， Biometrics，1972（28）：81-124.

匹配算法论文篇（8）

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

一、解决问题的思路

在高效字典中，在同样首字下的词条，在内存中是按照汉字内码大小排列的。在词典中匹配成功某个字串后，会在其后面增加一个字即得一个新的字串，如果新字串在词典中出现了，那么新字串一定在原字串后面，且相隔的位置不会太远。近邻匹配算法基于这一特点设计的，使用这种算法避免了每增加一个字就要重新在字典中从头开始匹配的冗余操作，是一种高效的分词算法。该算法的分词过程如下：

1、将词库读入内存。这是读入词库切词的第一步，为了提高整个切词的速度，可将整个词库一次性读入内存，并常驻内存。

2、读入要切分的中文文本数据。对于待切分的文本数据按行进行处理，每处理一行，就要先将字符数据读入缓冲区，并进行相应的字符集转换。

3、从缓冲区中读取搜索字串P=C0C1C2……CL-1。（L为字串长度），根据待搜索字符串P的首字C0，可以根据计算出的C0相应的索引项Ii的地址，并得到以C0为词首字的词数n及指向所有词条：W0W1……Wn-1的指针Pi。如果说，这个字不能成词，那么就退出。

4、在词表中查询中，前两个字形成的子串CoCl，得到索引index，然后在index之后寻找最长且完全匹配的词条。

5、如果当前匹配长度小于最大匹配长度或词表中的词条比字串大，结束寻找过程，然后用同样方法切分下一词条。

算法实现如下：

Neighborhood Matching

{

int totalOffset=0；

int strLen=strlen（P）；

while（totalOffset

int

result=-O；

//计算索引项的地址

Unsigned char q=*P；

unsigned char w=*（P+1）：

q-=0xB0；

W-=0x A1：

Char**Pi=ptrArray[q][w]；

int n；//词条数；

int index=FindWord（4，（char*）C0C1，&result）；

if（index==-1）{

/*没找到）C0C1，还不能确定它是某个词条的前缀还是应分开*/

start=result+l；

}else{

start=index+l：

matchMax=l；

}

int offset=2；∥跳过首字

int bContinued=l；∥是否继续查找标志

while（start0）{

bContinued=l；

Char *wordPtr=Pi[start]；

int wordLen=strlen（wordPtr）-2；

if（*（P+offset）！=*wordPtr ||*（P+offset+1）！=*（wordPtr+1））

break；

i=2；

while（i

if（*（P+offset+i）==*（wordPtr+i））

i++；

else{//如果字串比词条小，退出当前循环

bContinued=*（textPtr+offset+i）-*（wordPtr+i）；

break；

}

}

//完全匹配

if（i==wordLen）{

i>>=l；

if（i

break；

else matchMax=i；

start++；//准备匹配下一词条

//处理下一个词

offset+=matchMax

P+=offset；

TotalOffset+=offset）

}

}

}在上述算法实现的切分情况，在切分“中国人民成功守住了大堤”时，词表中以“中一开头的词有100多个，以“中国"开头的词有“中国人民”、“中国青年”、“中国银行"、“中国政府”，找到“中国”后，在其后找“中国人民”一词，只需两次词条匹配操作即可。

由于本文采用的是词表结构支持首字Hash和标准的二分查找方法，避开了词表访问过程中的I/O操作，并且在分词过程中采用近邻匹配算法，大大降低了时间复杂度，根据表3-1的统计数据，单字词的出现频率约为56.75%，二字词的出现频率约为39.65%，二字词以上的词的出现频率为3.6%，每个首字下的平均词数为12.35，该算法时间复杂度计算如下：

查找单字词无需匹配。

查找一个两字词的平均匹配次数为：

0.3965 ？log2n = 0.3965 ？log212.35 ≈ 1.44

查找一个三字词或高于三字的词平均匹配次数：

（1-0.5675-0.3965） ？n / 2 = 0.036 ？13.35 / 2 ≈ 0.22

利用这种算法，假设有12万条词库的基础上，在P42.0GHz的电脑，lG内存的平台下，1.2MB的文本在最大匹配算法的状态下，所需时间约为1.0 ～1.1s，在同类算法中是比较优秀的。

二、分词算法准确性测试

为了检验本论文采用的分词算法的准确性，本论文采用了两段文字进行测试：

源文件：中文信息和英文信息相比，有一个明显的差别，英文单词之间用空格分隔；而在中文文本中，单词之间没有天然的分隔符，中文单词大多是两个或两个以上的汉字组成的，并且，语句是连续的，这就要求在对中文文本进行自动分析前，先将整句切割成单词单元，即中文分词。

分词结果：中文/信息/和/英文/信息/相比/有/一个/明显/的/差别/英语/单词/之间/用/空格/分隔/而/在/中文/文本/中/单词/之间/没有/天然/的/分隔符/中文/单词/大多/是/由/两/个/或/两/个/以上/的/汉字/组成/的/并且/语句/是/连续/的/这就/要求/在/对/中文/文本/进行/自动/分析/前/先将/整/句/切割/成/单词/单元/即/中文/分词

三、结论

通过试验得知，本论文采用的分词算法分词精确率达到95%，分词速率快，基本满足了一个中大型搜索引擎的需要。

（作者：桂林电子科技大学工程硕士在读，本科学士学位，研究方向：垂直搜索引擎，中文分词）

参考文献：

匹配算法论文篇（9）

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

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

1 入侵检测系统Snort

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

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

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

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

2.1 单模式匹配算法（BM）

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

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

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

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

2.2 BM算法改进

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

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

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

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

2.3 算法性能比较

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

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

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

3 结论

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

参考文献：

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

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

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

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

匹配算法论文篇（10）

电视跟踪系统对目标的跟踪是通过跟踪指定目标的图像实现的。目前在该系统中应用比较广泛的是形心跟踪和积相关跟踪算法。形心跟踪算法简单,在一般条件下可以达到较高的跟踪精度,但是这种算法的跟踪精度受周围条件的影响较大。积相关跟踪的优点是受环境的影响很小,并且通过快速简化积相关算法的实现,能够提高系统的实时性,因此能够得到广泛的应用。

1、积相关算法概述

以图像匹配为基础的电视跟踪方法,习惯上称为电视图像相关跟踪,简称为相关跟踪。积相关算法是常见的相关算法中的一种,也叫归一化相关算法:

相似性度量(x0,y0)的表达式为:

n~(x0,y0)=m-1X=0m-1y=0f(x,y)t(x+x0,y+y0)m-1X=0m-1y=0f2(x,y)m-1X=0m-1y=0t2(x+x0,y+y0)

其中,0≤x0≤n-m, 0≤y0≤n-m。如果把f(x,y)和t(x,y)分别看作两个欧式空间里的矢量,那么积相关算法的度量值表达式正是这两个矢量在欧式空间里夹角的余弦。这是一个非常有用的性质,它的实际意义是,当环境光强发生变换时。应用积相关算法可以不受干扰。

2、跟踪稳定性的研究

所谓跟踪的稳定性是指匹配点的位置是否能够唯一确定或者在一个极小的范围内滑动。研究系统跟踪的稳定性具有十分重要的意义。

2.1图像预处理对跟踪稳定性的影响

在智能电视跟踪系统中实现积相关算法时,采取必要的图像预处理是非常必要和有益的。对模板和实时图像进行灰度均衡,使相关峰变得尖锐,从而提高跟踪性能;增大图像的对比度,也可以使相关峰变得尖锐,从而提高跟踪性能;对图像进行灰度最小化处理,使相关峰变得尖锐,提高跟踪性能。

2.2模板选取对跟踪稳定性的影响

积相关跟踪算法的模板需要人工在视场范围内进行锁定,这个初始的第一个模板对跟踪效果也是有影响的。为了得到良好的跟踪效果,相关峰应当尽量选择在图像比较复杂并且没有规律的区域内。

2.3奇偶场对跟踪稳定性的影响

系统采用的摄像头是按照PAL-D制式进行隔行扫描按照奇偶场产生图像的。对一幅静止的图像如果采用隔场匹配,那么一个模板始终与奇数场或者偶数场的实时图像进行匹配,此时跟踪点就始终是稳定的。对于动态的、连续的图像,应该在算法中加入一些处理措施,比如对模板进行刷新,否则可能造成跟踪不稳定。

3、简化的快速积相关图像匹配算法

基于前面给出的简化归一化积相关度量方法,为了进一步减少匹配算法匹配时间,提高匹配效率,且同时保证一定的匹配精度与匹配概率,设计了先粗后精的分层匹配控制策略。

3.1先粗后精的分层匹配控制策略

下图中给出了匹配控制策略的设计框图。

这种匹配控制策略首先是进行粗匹配,确定匹配点的大概位置或候选位置,接着进行精匹配,确定匹配点的精确位置或最佳位置。精匹配是在粗匹配的结果---候选匹配子图中完成的,因而搜索范围大大减少,提高了匹配速度。

对于本文算法,使用该方案需要注意以下三点。

(1) 粗匹配阶段,为了保证精匹配阶段的有效性,必须确保粗筛选后所保留的预选点包含有匹配点。

(2) 门限法实现起来难度较大,多数是靠大量实验及经验获取,且仅在特定的情况下可以采用。实际中,可以考虑采用3~5点筛选法,即直接取粗匹配阶段度量值最优的3~5个匹配点作为精匹配基准点。

(3) 图像的预处理是指对匹配图像的灰度数据进行一定的压缩或特征提取。在粗匹配阶段,可以考虑隔像素取值且隔像素搜索。而在精匹配阶段,像素值及搜索范围均要适当扩展。

3.2算法设计

结合简化的度量方法及前面给出的先粗后精的分层匹配控制方案,设计了简化的快速归一化积相关图像匹配算法。

(1) 粗匹配阶段

计算总的匹配搜索次数(如对于大小分别为m×m和n×n的基准图与实时图,则总的搜索次数为(m-n+1)×(m-n+1),进行循环递推匹配。匹配准则如下。

①每隔n1像素从基准图左上角开始扫描获取各个基准子图,并在实时图及所选的基准子图中隔n2个像素取其灭度值,组成用于相关匹配的维数较小的灰度矢量。

②利用简化的归一化积相关度量方法比较基准子图与实时图灰度矢量的相似性。

③采用递归比较的方法得到3~5个最优的匹配点,对应的基准子图作为候选配子图。

(2) 精匹配阶段

在粗匹配阶段得到的各个匹配点周围适当展开进行搜索匹配(若粗匹配阶段是隔n1像素进行搜索的,则在各匹配点周围展开的幅值为应在n1/2到n1的范围内)。

①利用简化的积相关度量方法逐一取候选子图,并在其扩展的范围内进行灰度匹配。

②所有度量值中,Rs(u,v)值最大的匹配位置便是最终的匹配结果。

4、提高跟踪实时性

经过大量的实验,采用快速的简化积相关算法进行匹配仿真实验可得出如下结论:

第一是积相关及本文简化快速积相关算法在智能电视跟踪系统中出项的稳定性干扰以及较小的几何畸变具有良好的抑制作用,且实时图像越大,其抑制能力越好。

第二是对未经选定的图像,可以考虑对匹配数据及搜索方案进行适当调整以获得满意的匹配效率。对于经过选定的图像,采用本文提出简化的积相关度量方法及先粗后精的分层匹配控制策略,有效地提高了匹配效率。

第三是减少匹配次数。在匹配时,进行一次粗匹配和二次精匹配。一次粗匹配时将步长设为2个像素,这样可以使计算量减少为原来的1/4。需要指出的是,采取上述的参数进行积相关处理时,一次粗匹配的过程中,可能会遗漏实际的最佳匹配点,但是最佳匹配区域不会被遗漏,也就是说,最佳匹配点可以在二次精匹配中找回。

总之,通过上述方法可以在有限的硬件条件下,有效地提高了系统跟踪的稳定和实时性。

参考文献:

[1] Franz Matthias O, Bernhard. Scene-based homing by image matching[J].Biol. Cybern,1998:191-202.

[2]刘扬,赵峰伟,等.景像匹配区选择方法研究[J].红外与激光工程, 2001, 30(3): 168-170.

[3]任仙怡,廖云涛,张桂林等.一种新的相关跟踪方法研究[J].中国图象图形学报(A版),2002,7(6):553~557.

[4]刘嘉.应用随机过程[M].北京:科学出版社,2002:12~13.

[5]彭架雄,雷达图像匹配制导技术,华中理工大学.

[6]孔丹,李介谷.亚像元精度的图像匹配技术[J].红外与激光工程,1999,27(1): 29-32.

[7]李尊民.电视图像自动跟踪的基本原理.国防工业出版社.1998.

[8]齐文宁.导弹上图象处理机的研制及边缘提取算法的研究.东南大学硕士学位论文.1997.