匹配算法论文范文
匹配算法论文范文第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篇
关键词： 无线传感器网络； 数据收集； 单边匹配； 贪婪算法； 最优解
中图分类号： 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.
[13] XIE L， SHI Y， HOU Y T， et al. Making sensor networks immortal： an energy?renewal approach with wireless power transfer [J]. IEEE/ACM transactions on networking （TON）， 2012， 20（6）： 1748?1761.
匹配算法论文范文第3篇
Key words： highway freight;vehicle cargo match;information platform
0 引言
公路货物运输业一直是国民经济发展中的一个基础性和先导性产业。统计公报显示，2017全年货物运输总量479亿吨。公路货物运输总量368亿吨，同比增长10.1%;可见公路运输的占比在所有交通运输方式中是最高的。随着我国货运总量连年提升，公路货运的占比也在不断提高。但目前我国货车实载率不及60%，远低于发达国家 80%～95%的水平。传统线下物流大多数存在着多、小、散、弱等问题，人找车难、车找货难的问题也屡见不鲜。随着中国互联网飞速发展，“互联网+”、大数据、云计算等早已深入货运行业。车货匹配信息平台有效的缓解了信息不对称，减少了车辆空载和社会成本，同时为车货双方提供了货物配载信息服务，但目前还不具备按双方需求实现快速智能匹配的功能。为了解决当前物流需求多样性，服务对象不确定性，车货匹配信息不对称及车货匹配效率低等问题，减少较大的经济损失和社会资源浪费。本文从车货匹配的决策建模，理论方法及信息平台等三个方面，汇总了针对车货匹配的国内外学者观点，并且囊括近些年来相关领域的优化问题，回顾了相关成果的研究热点、模型特征，并提出了未来公路车货匹配研究中应该关注的主要问题。
1 车货匹配决策建模理论研究
车货的有效匹配可以提高物流资源的利用率，降低运输车辆的空驶率。本文主要从车货匹配决策建模方面对前人的研究文献做简要综述。
陈进博等人[1]基于信息、功能及效益三大模块并应用MA-OWA算子进行权重赋值，结合车货匹配网站的业务流程构建了评价指标体系。姚国龙[2]提出结合精益物流思想特征和专家调查法对车货匹配中的具体要素进行评价，采用定性与定量的AHP模糊综合评价法分析过程中的问题。张庆英等人[3]，采用权重分析法对物流企业和个体用户交易指标进行打分，以承运商和托运方估值之和作为车货信息匹配交易的撮合机制。孙彬[4]通过构建智能匹配模型及指标体系实现了基于地域因素的第四方物流平台的供需智能匹配。李慧[5]运用理论分析法，模糊综合评价法和多目标匹配排序法为供需匹配模块建立以货源方、车源方为主的车货两层筛选匹配指标体系。胡觉等人[6]提出了利用信息评价体系，大小数量规模下的TS算法和PSO算法，PSO-TS混合算法等证明了TS算法在车货匹配问题上的有效可行性。郭静妮[7]，利用三角模糊数及清晰化的效用函数构建了车货双方多指标语言评价体系。黄美华[8]等人根据车货信息平台的特点用最小二乘支持向量机来匹配需求信息，并建立了车货信息匹配模型。吴广盛[9]以货源方和车源方为主导偏好因素提出车货供需匹配排序模型，并提出匹配指标和信誉评价体系。牟向伟等[10]提出了利用量子进化算法对车货匹配模型进行设计与改进，并采用约束惩罚的适应度衰减方法解决了量子群初期无强可行解时最优量子个体的选择问题。陈火根[11]等人讨论了在电子交易市场上利用网络服务信息建立了子目标任务，人工干预交易协商，并实现车货匹配资源自动配对。陆慧娟等人[12]利用软件及服务（SaaS）与计算机支持的协同工作（CsCw）相结合，采用车辆混合禁忌搜索算法，构建“货找车”的高智能车货匹配系统。王训斌等人[13]构建了多目标多层级公路车货匹配系统，并采用车辆混合禁忌搜索算法对其进行优化。陆江[14]研究了基于虚拟物流平台的公路零担运输车货匹配模型，选定遗传算法作为模型的求解算法，并使用Java语言实现了算法。张涛和赵冰洁[15]运用遗传算法对车辆调度实际问题进行研究。李建民[16]等人针对车货配载过程中的货选车和混载的问题构建了多目标规划模型，并提出运送价格和车主可靠程度是其重要的影响因素。顾佳倩[17]利用Java程序，以语义网本体和自定义推理规则为知识导向搭建了车货基于语义的相互匹配。张璐[18]通过了解交易双方策略，研究并分析了基于公路货运信息平台的组合拍卖机制对运力资源的订单分配等领域问题。蒋忠中等人[19]分析了多属性商品交易中存在的模糊信息，并建立了的新的交易匹配模式。常连玉，陈海燕[20]基于主体诉求和运价机制，利用神经网络和微粒子群智能算法对运力组织优化模型进行了求解。Karen Renee Smilowitz[21]通過分析研究实例UPS路网对多式联运运输系统网络发表了最新的见解。Lao和Goh[22]用JAZZ技术实现了一个基于智能匹配的网上支持4PL业务的系统。研究成果提出了很多建模决策方法例如 “语义网技术”，禁忌算法，模糊综合评价法，层次分析法，神经网络，微粒子群等。对车货智能匹配功能和车货双方的多指标评价体系也进行了较丰富的研究。
2 车货匹配相关理论方法研究
在合理的市场机制下双方能够基于各自的偏好进行稳定的市场匹配称之为双边匹配理论，以其为基础导向从车货匹配平台与车、货双方关系出发，运用分析方法和建模，能够有效的解决实际问题。所以本文重点探讨双边匹配理论在车货匹配问题上的研究。
国内相关研究成果：贾兴洪等人[23]基于双边市场和演化博弈理论，构建了车货匹配平台双边用户交易博弈模型，提出平台用户单归属比率提升的最优控制。宋娟娟等人[24]提出物流信息平台具有双边服务、交叉网络外部性等特性，并建立配套信用机制对平台用户资质进行认证。赵保燕[25]以双边市场理论为基础构建了车货物流平台并用平衡计分卡模型对模式的各个维度进行评价。李铭洋等人[26]基于车货双方的序值偏好，构建了主体序值和最小的目标函数模型。樊治平等人[27]基于双边匹配稳定满意的出发点，建立了以满意度最大化为目标的双边匹配模型。张振华和汪定伟[28]从权匹配的角度阐述了稳定性匹配问题，提出按重要性从大到小排序，使每一个结点上的匹配主体都尽量得到最优匹配。
国外相关研究成果：Roth[29]最早明确公开提出双边匹配的概念，在1985年发表的文章“Conflict and conflicting interests in two sided matching markets”中界定了“双边匹配”和“双边”的概念，并分析了双边匹配的现实例子。Gale和Shapley[30]于1962年在“American Mathematical Monthly”上“大学录取和稳定婚姻匹配问题”。Rochet等人[31]在其working paper中首先从价格结构的不对称性角度给出了双边市场的定义。Armstrong [32]进一步强调了双边市场中一边用户对另一边用户数量的依赖性。 Gardenfors [33]以指派理论为依据研究了双边匹配问题。Vate[34]在研究中指出最大化线性目标函数的稳定匹配能够通过线性规划计算出来，认为稳定匹配是一个线性规划问题。Fleinr[35]提出可以用不动点理论来解释双边匹配问题并分析了Gale-Shapley的稳定婚姻理论与Tarsk不动点理论的联系。Roth[36]在双边匹配市场的理论基础上创新性的提出了如何识别非空内部点的方法，同时在Shapley和Shubik[37]研究的转让市场的理论核心基础上得出一套固定点。Korkmaz等人[38]提出双边匹配模型是将雇员和雇主进行有效匹配并使每一边都接受匹配结果，还指出双边匹配理论可以用在指派问题中。
双边匹配理论为匹配的稳定性，线性规划都做了开拓性的研究。车货匹配依据双边匹配理论可以分为一对一匹配，一对多匹配，多对多匹配模型。但双边匹配理论针对车货匹配问题的研究尚处于探索阶段，已有的成果还存在不足之处。
3 车货匹配信息平台研究
当下我国公路货运成本居高不下，存在大量物流资源的浪费，而其中很重要的原因就是物流信息不对称。车货匹配信息平台的设计就是为了减少或消除信息不对称，实现车货在最优条件下的匹配。本文主要是从车货匹配信息平台方面进行阐述。
刑鹏[39]针对车货匹配信息平台问题提出加强云计算与配送之间的联系，从而产出云配送模式。熊然[40]分析了部分地区公路货运行业的主要问题，不仅指出了车货匹配信息平台给车货双方和社会带来的正面意义还提出交易安全性和信息真实性的重要性。王博，朱杰[41]分析了代表性行业的物流现状，对物流信息平台与车货匹配信息平台进行对比，强调了资源整合的重要性 。张松[42]针对货运配载行业的发展现状提出了影响公路货运返程配载效率的因素，并比较分析了南京主流的配载模式。汪逸敏[43]从公路货运平台经济的角度出发，指出配货需求不能局限于落地配等单一模式应当趋于随机与碎片化模式。熊宜强[44]提出利用“反馈式竞争法”进行权重改进，研究了车货匹配排序诚信激励机制和信号博弈模型等级划分机制。
在车货匹配信息平台中物联网、云计算、大数据及移动互联网技术扮演着重要的角色，不仅能够为系统结构提供科学依据，还可以为未来智能发展方向，及运作机理提供建设性思路。
匹配算法论文范文第4篇
[关键词] 分层策略 图像匹配 序贯相似性检测算法 自适应遗传算法
一、引言
机器人的视觉导航控制是利用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%。系统运行良好，跟踪目标没有出现大的偏差，基本上始终处于图像视野的中央位置，运动轨迹没有出现振荡，达到了机器人视觉导航的目的。可见基于分层的自适应――序贯相似度检测算法既具有很高的匹配速度，又保持了良好的匹配正确率。
四、结语
匹配算法论文范文第5篇
关键词：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)
匹配算法论文范文第6篇
关键词：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)
匹配算法论文范文第7篇
关键词:规则匹配;并行树搜索算法;规则分解映射;平衡二叉决策树
中图分类号: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。
匹配算法论文范文第8篇
关键词：粒度计算；图像匹配；SSDA
中图分类号：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.
[5] R. Tyrrell Rockafellar， Roger J-B Wets， Variational Analysis， Springer-Verlag， 2005：117.
匹配算法论文范文第9篇
关键词：图像匹配；归一化交叉算法；小波变换；多尺度；塔式结构
中图分类号：TP399 文献标识码：A文章编号：1009-3044(2011)23-5698-03
NCC Algorithm Optimization Based on the Wavelet Multi Scale
FU Yan-li
(Shandong SHENG DA Construction Group Limited Company, Jining 272000, China)
Abstract: Algorithms based on pixel gray value are already very common in mage template matching problem, which normalized cross correlation algorithm (Normalized CROSS Correlation. NCC) is one of the classic algorithm based on gray matching, and is widely applied, but the algorithm also has the disadvantages of high time complexity. Multi scale theory and the multiple resolution image are representation and analysis of relevant, i.e. a digital image can be expressed as a multiple resolution sub-images collection. Its characteristic cannot be found in a resolution while in the characteristics of another resolution is easy to find, the wavelet multi-scale analysis is an important tool, known as mathematical microscope, can be used to construct different adaptive filter with improved filter convergence, which is also one of the advantages of wavelet transform. Image after wavelet decomposition, in the lowest layer of the low frequency sub image resolution, retaining only the most information of image, that is after wavelet transform of image of a feature. Based on the wavelet multi scale NCC algorithm not only optimize the algorithm itself at the same time optimization based on gray matching search path, so that guarantee the NCC algorithm accuracy, and reduce the matching time, and also the simulation experiments show that this algorithm is effective.
Key words: image matching; normalized cross algorithm; wavelet transform; multi-scale; tower structure
图像匹配是对两幅图像找其对应的映射关系或根据已知模式到另一副图中寻找相应的模式。图像匹配是一种极其重要的图像处理和分析技术，无论在图像理解还是在视觉计算中都具有重要作用和地位，其成功应用到航空航天、地球物理信息、海洋船载导航和地理特征探测、工业生产、医疗卫生等，因此图像匹配技术越来越受到人们的重视和青睐。
图像匹配的实用的技术方法一般分为两大类，即基于灰度匹配和基于特征匹配。基于灰度匹配是把待匹配图像中的某一像素点的灰度邻域作为匹配模板或者称为子窗口，在参考图中搜索具有相同或者相似灰度值分布的对应的邻域，从而实现两副图的匹配。基于特征的图像匹配不是利用图像中的像素值进行匹配，而是通过灰度导出符号特征（如：拐点、角点、边缘线段、图像轮廓）实现图像的匹配。前者作为一种基本的匹配方法之一，在很多地方得到了充分的应用，可以充分利用图像的所有信息、尤其适合在图像仅有平移和模板图像中非零项比较少的情况下，便于匹配的实现。但是弱点也是很明显的，即对图像的几何变形、光照强度、对比度都很敏感，并且计算量大，不适合实时匹配。后者利用从图像得到的符合特征作为匹配的基元，有效的克服了前者的弱点，但是特征匹配过于依赖图像的特征点，并且特征点的提取涉及到几何和图形形态学的计算，没有统一的模型可以利用，需要对不同图像选择不同的自适应特征，需要额外的特征提取的计算，往往计算也比较复杂。
1 归一化交叉相关算法
归一化交叉相关算法[1] (Normalized Cross Correlation．简称NCC)定义如下：
假设模板图像w(s,t)的尺寸为m×n，其中m,n往往取奇数，参考图像f(x,y)是一个大小为M×N，（1≤m≤M, 1≤n≤N），则：
（1）
其中a=(m-1)/2,b=(n-1)/2
由于表示模板的能量所以是一个常量，，当模板移动距离比较小时，也近似一个常量，所以为使D(x,y)最小则需要达到最大值，由于对w(s,t)和f(x,y)的副值的变化比较敏感，所以定义归一化互相关函数为：
（2）
其中a=(m-1)/2,b=(n-1)/2
为了进一步克服噪声的影响和理想状态匹配时C(s,t)相同值太多，还进一步简化（2）式即：
（3）
其中a=(m-1)/2,b=(n-1)/2，Ef,Ew分别为f(x,y)和w(s,t)的期望。
当C(s,t)达到最大值时，两图匹配成功。
通过对NCC算法的理论分析，不难发现：为了让算法达到理想状态进行图像匹配，牺牲时间，换取了理想的匹配。通过对公式（1）（2）（3）分析，可以看出公式越来越复杂，计算量越来越大，匹配的时间越来越多，由于小波变换可以作为一个平滑过滤器来使用，所以小波变换可以消除图像的幅值和图像的噪音，因此选择了NCC算法的中的公式（1），这样就可以节省大量的计算时间，提高匹配的速度。
2 小波变换的多尺度分析
小波在1987年首次作为分析工具首次出现，小波是多尺度分析的重要工具，被誉为数学上的显微镜[3]，因为小波变换具有时间-频率局部化的特点，即在小波变换中，时间窗函数的宽度与频域函数窗口的函数的都是一个常数，根据测不准原理，他们的乘积也是一个常数。在对低频分析是可以加宽时间窗，减少频率窗；而对于高频分析是，可以增高频率窗，减少时间窗，这种特性被称为“自适应窗口特性”所以小波的这种特性是小波变换能提高为多尺度分析的基础，可以用来构建不同的自适应滤波器以改进滤波器的收敛性。
小波多尺度分析的表示：以多分辨率来解释图像的一种有效并且容易理解的结构就是图像金字塔如图1。一副图像金字塔是一系列以金字塔形式排列的分辨率逐层降低的图像集合。0层是N×N的图像，对0层的图像进行小波亚抽样，可以达到一个原图四分之一的较粗略的缩略图。这个过程是可以重复进行直到N层，这时图像是1×1的图像。这时图像的分辨率也从0层最高到N层逐次下降，是原来图像的四分之一。这样一个图像的金字塔结构共（logN 2+1）层，或者有这么多不同的图像组成，并且图像所用的容量只是原来的图像的4/3N2。
多尺度小波的特点[3]：1）多尺度小波具有窗口自适应的特性，即可以使图像的小波分析聚集到间断点、奇异点和边缘，体现了局部特点；同时也可以获得全局的视点。这个特性是小波变换独有的，对非稳定性和快速变换的信号的分析特别有用的。2）小波变换相当于一组多分辨率的带通滤波器。利用这个特性，可以将图像的信号分解为如图1所示的频率子带上，在每个子带可以用小波变换进行处理。3）多尺度小波分解图像的所有子图的和等于原图像的大小，即不增加存储空间。4）分解后的图像，没有信号损失，保证图像的完整性，便于对低频和高频的处理和上层对下层的实时重建。
3 基于小波多尺度的匹配算法
多尺度小波匹配主要利用了小波多尺度的特性对待配图和参考图进行金字塔式分解，结构如图1，匹配基本流程如图2所示，具体步骤如下：
1）首选判断待配图和参考图的大小，一般待配图比参考图像小多，这时就是在参考图中寻找待配图的位置；反之就是在待配图中搜索作为目标的参考图的过程。两者原理是一样的，所以匹配算法是基于前者论述和测试的。
2）判断待配图和参考图的灰度光照强度、对比度、物体在拍摄时的遮挡情况以及空间几何等，这些都会对基于灰度匹配造成错误的匹配，进行图像匹配前的预处理。
3）以上两步看作图像预处理的过程。接下来选择小波，这步非常重要，本课题选择了Daubechies（db4）小波，因为此小波在运动估计中应用非常广泛，可以很好的保留低频中图像的绝大部分信息，去掉高频信号中的噪声，是一个行之有效的小波。然后利用小波的多尺度特性将待配图和参考图像分解为N层，结构如图1，待配图和参考图未分解的图像为0层（有些文献是将原图定义1层），从低到上，分解的最大层为N层（或者分解的最大尺度为N层），在MATLAB中实现小波变换的最大层的函数是wmaxlev()。但是为了保证低频的中含有未解图的绝大部分信息，尤其是灰度变化比较剧烈的区域，一般分解的层次为：一维分解的分解尺度N不超过5；二维的分解尺度N不超过3。第N层图像的尺寸和大小都是原图来1/(N+1)2。
4）通过前三步，待配图和参考图的原图被分为N层不同频率子图的集合，现在可以在分辨率最低的N层进行待配图的子图与参考图的子图进行匹配。采用了经典灰度相似度量算法：归一化交叉相关算法NCC进行对待配图和参考图进行匹配。整个匹配过程就是将N层的待配图看作模板，匹配的实现基本过程：1）在第N层利用归一化交叉相关算法NCC进行匹配，即求出（1）式的最大值；找出对应匹配区域；2）在N-1层按照N层的算法，再在对应匹配区域进行NCC匹配；3）重复第5步直到0层；4）输出匹配结果。
4 仿真实验
本算法使用Matlab2007b进行了大量的仿真实验，图3是选择了最著名lena图进行算法的仿真说明。
结果分析：
1）为了与其他文献在匹配速度和精确度的可比性，选择了其中的一组著名图像：lena图，如图3和图4中的A图所示。进行尺度为2的小波分解，两幅图像中的尺度为2的低频子图，基本上无法辨认，即所需要的信息基本上都被过滤，所以在第2层匹配是无法匹配的，根据第4节的匹配步骤，只能在第1层子图匹配，匹配实验的结果证明是可行的。
2）将这幅lena的待配图和参考图如表1所示的各种算法进行匹配。通过表1可以看出，此算法是可行的。
5 结束语
论文的创新是首选剖析了NCC算法，选择了算法的中间过渡式作为本算法的一部分，好处是减少图像匹配的计算量，同时也保证了匹配的精确度；采用了小波变换的多尺度特性，优化了匹配的搜索策略，提高了匹配的精确度和匹配的时间，所以结合两者的特点可以很好的完成某些领域中图像的实时匹配。
参考文献：
[1] Gongzalez R C,Woods R E.Digital Image Processing[M].2nd Edition (DIP/2e).北京:电子工业出版社,2005.
[2] 李强,张钹.一种基于图像灰度的快速匹配算法[J].软件学报,2006,17(2):216-222.
[3] Luigi Di Stefan.Stefano Mattoccia Fast template matching using bounded panial correlation[J].Machine Vision and Applications,2003(13):213-221.
[4] Bamea D I,Silverman H F.A class of algorithms for fast digital image registration[J].IEEE Trans on Computers,1972,C-21:179-186.
[5] 郑运平,陈传波.一种新的灰度图像表示算法研究[J].计算机学报,2010,33(12):2398-2406.
[6] 李健,梁琨.基于小波多分辨率分析的快速图像匹配[J].陕西科技大学学报,2006,24(6):81-84.
[7] 刘莹.基于灰度相关的图像匹配算法的改进[J].应用光学,2007,28(5):537-540.
[8] 杜杰.两种基于灰度的快速图像匹配算法[D].大连:大连海事大学,2007.
[9] 范俐捷,王岩飞.一种新的基于灰度的图像匹配方法[J].微计算机信息,2007,23(30):296-297.
[10] 范新南,朱佳媛.基于小波变换的快速图像匹配算法与实现[J].计算机工程与设计,2009,30(20):4674-4676.
匹配算法论文范文第10篇
关键词:双目立体视觉;区域相关;立体匹配;标准测试图
中图分类号: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.
匹配算法论文范文第11篇
【关键词】图像匹配 积相关跟踪 算法
电视跟踪系统对目标的跟踪是通过跟踪指定目标的图像实现的。目前在该系统中应用比较广泛的是形心跟踪和积相关跟踪算法。形心跟踪算法简单,在一般条件下可以达到较高的跟踪精度,但是这种算法的跟踪精度受周围条件的影响较大。积相关跟踪的优点是受环境的影响很小,并且通过快速简化积相关算法的实现,能够提高系统的实时性,因此能够得到广泛的应用。
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.
作者简介:
匹配算法论文范文第12篇
【关键词】 正交匹配 追踪研究 压缩感知信号 检测算法
压缩感知是一种新型的采样方法，通过信号记录每个观测过程中投影的数据，如果感知信号资源小，则可以将这些信号资源进行压缩处理，以保证在观测值数量少的情况下信号结构的准确性和完整性。相对于重构结构复杂的感知信号，信号和图像的重构步骤复杂，且重构效果很差，面对这些不能被正确重构的感知信号，应采用采样的方法将特征量从样本数据中采集出来，通过检测目标信号，完成检测流程。综上所述，通过正交匹配追踪研究压缩感知信号的检测算法，其综合应用性能很好，检测范围和效果很好。
一、感知信号检测
1. 感知信号理论概述
信息获取是压缩感知信号理论的核心内容，其理论基础建立在信号系数、样本数据处于非相关性的状态下的数据测算，通过数据重构和特征量数据采集，以局部分析整体的方式，完成检测流程。压缩感知理论的内容主要包括：①将感知信号的投影在观测向量上，利用重构思想对样本数据进行重构测算，并建立检测集合，如果信号程度为M，则其重构集合稀疏度为K（K
2. 感知信号检测原理
二、基于正交匹配追踪的压缩感知信号检测算法
1.检测算法。正交匹配追踪是一种新型改进算法，其检测方法的理论依据是正交匹配理论，和其他感知信号检测算法相比，正交匹配追踪算法的检测流程更为简单，检测结果的准确度很高。其检测特点是在每次迭代中将选出的列用Gram-Schmidt正交化方法进行正交化处理，将采集到的样本数据选列在空间投影中，通过直观的数据变化曲线，选择精确的检测算法，这种检测方式不仅可以简化检测过程，还能提高样本数据各特征量的收敛速度。在数据迭代次数相同的情况下，空间投影出的采样信息的更新速度很快，检测人员可以通过采样值选出最优投影，并随时更新系数，以确保空间投影的真实性，检测结果的准确度。
2. 实验结果分析。实验结束后，通过检测结果进行分析可知，在每次迭代中，OPM检测算法的感知信号的波形都相对平稳，在一段时间内，其特征量不会随着加性高斯白噪声的变化而变化。当采集样本数据在规定资源数量时，OPM的检测结果和MP的检测结果大体相同，当检测阈值超过3时，OPM的检测结果的准确率明显由于MP检测算法。实验结果表明，与MP检测算法相比，本文提出的OMP检测算法其检测成功率很高，可以在提高检测成功率，所需采样点数、抑制噪声等方面有更好的性能，所以正交匹配追踪压缩感知信号检测算法是一种综合应用性能很好的信号检测方法。
结论：通过上文对正交匹配追踪压缩感知信号检测算法进行系统分析可知，通过匹配追踪定位感知信号，采集特征量，不仅可以方便于检测人员搜集信号样本，还能大大提高检测结果的准确性。通过对每次迭代的特征量进行及时、系统修正，可以延长采集样品的有效时间，以获得更科学、更真实的检测结果。
参 考 文 献
[1] 刘冰，付平，孟升卫. 基于正交匹配追踪的压缩感知信号检测算法[J]. 仪器仪表学报，2010，13（07）：109-113
匹配算法论文范文第13篇
关键词：动态规划；模板匹配；特征距离矩阵
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.
匹配算法论文范文第14篇
关键词：双目视觉；匹配算法；计算机视觉；立体匹配；相位一致性
1.计算机视觉系统分析研究
1.1计算机视觉技术及双目立体视觉
计算机视觉是通过计算机技术实现对视觉信息处理的整个过程，是一门新的学科。视觉是人们认知事物的重要途径，视觉是人们对视觉信息获取、处理和存储的过程。随着计算机技术的发展，信号处理技术的应用，人们通过照相机来把实际的事物拍摄下来转变为数字信息，并通过计算机信号处理技术队获取的视觉信号进行处理。计算机视觉技术对图像的处理分为获取图像、特征抽象选取、事物识别及分类和对三维信息的理解。获取图像主要是通过摄像机和红外线等技术对周围视觉事物进行获取，并通过计算得到和真实事物相应的二维图像，二维图像主要是数字图像。计算机视觉系统的最基本的功能是数字图像的获取。可以看出计算机视觉研究最基本内容是三维场景距离信息的获取。在计算机被动测量距离方法中，有一种重要的距离感知技术叫作双目立体视觉。双目立体视觉技术是其他计算机视觉技术无法取代的一种技术，对双目立体视觉技术的研究在计算机视觉技术和工程应用方面都是非常重要的。
1.2计算机视觉理论框架
第一个视觉系统理论框架的提出是以信息处理为基础，综合了图像处理和神经生理学等研究内容而建立的。这个视觉系统理论框架是计算机视觉系统的基本框架，与计算机视觉技术有着密切的关系。视觉系统的研究是以信息处理为基础的，从理论层次、算法层次和硬件层次3个层次进行研究。计算机理论层次主要是表达系统各个部分计算的目的和方法，对视觉系统的输入和输出进行规定，输入作为二维图像，输出是以二维图像为基础建立起来的三维物体，视觉系统的目的就是对三维物体进行分析和识别，通过计算对二维物置和形状进行重新建立。算法层次对计算机规定的目标进行计算，算法和计算机表达有关，不同的表达可以通过不同的算法进行实现，在计算机理论的层次上，算法和表达比计算机理论的层次要低。硬件层次是通过硬件来实现算法的一种表达方法。计算机理论层次在计算机信息处理中时最高的层次，取决于计算机的本质是解决计算机的自身问题，不是取决于计算问题的计算机硬件。要更好地对计算机系统和框架进行理解最好的方法就是要区分3个不同的层次，计算机理论的含义和主要解决的问题是计算机的目的，表达算法含义和主要解决的问题是实现计算理论的方法和输入输出的表达，硬件的实现的含义和主要解决的问题是如何在物理上对表达和算法进行实现。计算机视觉处理的可以分为3个阶段，对视觉信息的处理过程从最初的二维图像的原始数据，到三维环境的表达。第一阶段基元图的构成，基元图是用来表示二维图像中的重要信息，主要是图像中亮度变化位置及其几何分布和组织结构，图像中每点的亮度值包括零交叉、斑点、端点和不连续点、边缘等。第二阶段2.5维图描述，在以观测者为中心的坐标中，表示可见表面的方向、深度值和不连续的轮廓，基元是局部表面朝向离观测者的距离深度上的不连续点表面朝向的不连续点。第三阶段三维模型表示，在以物体为中心的坐标系中，有由体积单元和面积单元构成的模块化多层次表示，描述形状及其空间组织形式，分层次组成若干三维模型，每个三维模型都是在几个轴线空间的基础上构成的，所有体积单元或面积形状基元都附着在轴线上。视觉理论框架图如图1所示。
2.基于计算机的视觉立体匹配算法研究
视觉立体匹配算法是基于人类视觉系统的一种计算机算法。立体匹配算法作为计算机立体视觉问题研究的重点，快速地实现图像对应点的匹配来获得视差图是当今研究的热点问题。立体视觉匹配算法根据基元匹配的不同可以分为相位匹配、区域匹配和特征匹配3种，其中区域匹配算法可以减少计算负担，区域匹配算法实时性高，应用前景广阔。计算机立体视觉通过对人的双眼进行模仿，在双眼的立体感知中获得信息，从摄像机拍摄的图像中获取物体的三维深度信息，这就是深度图的获取，把深度图经过处理得到三维空间信息数据，二维图像到三维空间实现转换。深度的获取在双目立体成像视觉系统中分为两步，首先在双目立体图像与图像之间建立点对点的对象关系，双目立体视觉算法研究的重点问题是解决对应点之间的匹配问题。其次以对应点之间的视差为依据对深度值进行计算。双目成像是获取同一场景中两幅不同的图像，两个单目成像模型构成一个双目成像模型。双目成像示意图如图2所示。系统的基线B是两个镜头中心的连接线，空间点w（z，y，z）作为世界坐标的值由（x1，y1）与（x2，y2）进行确定，如果摄像机的坐标位置和空间点w世界坐标的位置重合，图像平面和世界坐标轴xY的平面就是平行的。如果两个摄像机在坐标系统中的原点不同但是它们的光轴平行，那么双目成像计算人们可以看图3所示，图3表示的是两个摄像头连线在平台xY的示意。
立体视觉的成像过程是成像的逆过程，具有一定的不确定性。大量的数据信息在从三维影像向二维图像进行投影的过程会出现丢失的现象，所以视觉系统要通过自然的约束条件才能保证获取正确的解。这些约束条件在减少匹配的计算量方面可以提供有利的帮助。针对基于区域匹配快速算法，还可以应用基于视差梯度的匹配算法，这种匹配算法应用较大的搜索范围在边缘的特征点上进行搜索，采用视差梯度在非边缘区减少搜索范围。应用计算机视觉立体匹配算法可以减少成像匹配时间，大大提高了工作效率。计算机立体匹配算法征点的提取是算法的关键问题，今后的研究方向重点是对有效特征点提取方法的研究。
匹配算法论文范文第15篇
关键词：后缀数组分布式存储串匹配
1引言
键，在分布式环境下加速后缀数组的构造需要充分考虑到通信对算法性能的影响。串匹配问题是计算机科学中研究得最广泛的问题之一，在文字编辑与处理、图像处理、信息检索、分子生物学等领域都有很广泛的应用。本文解决的是分布式存储环境下的精确串匹配问题。在串匹配的许多实际应用中一个确定的文本常常被查询很多次(比如对非常长的基因序列的查询)。针对这种情况，Manber.U和E.W.Myers提出建立后缀数组(suffixarrays)〔1〕来提高查询的性能论文，而后缀数组最大的不足是它的构造时间过长。因此一直以来，如何快速有效地构造后缀数组成了提高基于后缀数组的串匹配算法性能的关
2USAA算法
假设N，M为文本串和模式串的长度，P为处理器数，算法设计思路如下:
(1)将长为N的文本串A均匀划分成互不重盛的P段，分布于处理器。~(P一l)中，且使相邻的文本段分布在相邻的处理器中，显然每个处理器中局部文本段的长度为〔N/P〕。
(2)除了处理器O外，其它每个处理器利用KMP算法计算分配到自己的文本串的头个字符与模式串，基金项目:国家自然科学基金重点项目(60533020)的匹配信息。如果存在匹配情况，就向相邻的前一个处理器发送最大匹配后缀长度Maxsuffixlen，否则就发送一个负数。每个处理器可独立地计算和发送该值，所以这一步的计算复杂度为O(M)，通信复杂度为O(1)。
(3)处理器1~(P-l)接收前一个处理器的信息。
(4)利用Manber.U和E.W.Myers在文献〔〔1〕中的算法各处理器并行地构造局部文本段的后缀数组。
(5)利用Manber.U和E.W.Myers在文献〔1〕中的算法各处理器并行地进行模式申的匹配。算法的计算复杂度为O((N/P(109109(N/P)))，通信复杂度为0(1)，大大降低了通信复杂度。
3实验结果及分析
我们在基于分布存储的32节点HPRX2600高性能机群系统上测试了上述算法，比较了USAA和目前理论值最好的MMsortlz〕算法之间的性能，其计算复杂度为，通信复杂度为。
图1给出了当M一16、P~2时，N的取值对算法执行时间的影响。从图中看出当时，由于N、P的取值成了影响算法复杂度的主项，因此在实际应用中USAA算法比MMsort算法表现要好。
图2给出了当N变大时，USAA算法和MMsort算法的通信时间比较。可以看出，随着文本串的规模变大，由于处理器间需要进行的通信量增加，MMsort算法的通信时间有明显的上升，而USAA算法的上升幅度要显著小于MMsort。
4结论
本文提出的USAA算法通过采取均匀的后缀分配方式来降低处理段间匹配时的通信消耗，在(N/P)M的情况下使算法在保持计算复杂度的同时大大降低了通信复杂度。通过实验结果可以看到，USAA算法很好地解决了在分布式存储环境下降低后级数组构造中的通信复杂度的问题。
参考文献
[1]U.Manber，G.Myers.Suffixarrays:Anewmethodforon-linestringsearehes[C〕.InProeeedingsofthe