双向匹配算法

双向匹配算法（精选八篇）

双向匹配算法 篇1

运动补偿帧率提升由运动估计( Motion Estimation,ME)和运动补偿内插( Motion Compensated Interpolation,MCI) 两部分组成。运动估计首先计算出帧间的运动矢量场,接着运动补偿内插根据运动矢量场利用前后参考帧估计出内插帧[2]。由于经常出现有多个或无运动轨迹通过内插帧中的某些块,因此导致空洞和重叠现象,使内插帧质量衰退。为了解决上述问题,双向运动估计( Bidirectional Motion Estimation,BME)被提出利用运动对称性假设为内插帧各块分配唯一运动矢量,而解决了空洞和重叠问题[3]。但是由于视频帧的纹理区域常含有大量的周期重复模式,而双向运动估计中内插帧的缺失会造成在该区域内块的错匹配,因此,文献[4]通过计算相邻块间的重叠块运动增加运动矢量场密度,尽最大可能逼近真实运动矢量,文献[5]则通过在块匹配准则中增加可反映当前运动单向可靠度的正则化项来提高运动估计精度,上述方法尽管均能够提升内插帧质量,但却引入了较高的计算复杂度。

为了能够以较低计算复杂度克服纹理区域的错匹配问题,本文提出提取视频帧多个特征进行块匹配以提高双向运动估计精度。视频帧具有亮度分量Y、色差分量U和V,利用这些分量进行块匹配,可更准确地追踪物体运动轨迹。又由于人眼对物体边缘特征较敏感,通过提取视频帧的边缘图,并将与边缘特征相关的正则化项融入块匹配准则,可进一步地提高运动估计精度。然而,多特征共同进行匹配,势必会成倍地增加运算成本,为了避免高计算复杂度,本文算法设计特殊模板将多个特征合并到单平面上,那么,只需进行一次块匹配便可完成多特征匹配,从而以较低计算复杂度实现了高质量视频帧内插。

1 本文算法

传统的双向运动估计算法使用绝对差和( Sum of Absolute Differences,SAD) 在既定的搜索范围内寻找最相似块。传统SAD仅使用了亮度分量,然而对于视频信号除了具有亮度分量外,仍包含色差分量,例如,4∶2∶0的YUV视频取样格式存在色差分量U和V,但它们的采样点个数在水平和垂直方向都是亮度Y的一半。由于相邻像素间的色差分量变化经常小于亮度分量,加之彩色亚采样导致彩色信息缺失,因此,在传统视频压缩领域中,基于SAD的运动估计被广泛使用。

对于帧率提升算法,高质量视频内插依赖于准确的运动矢量。忽略了彩色信息的SAD往往并不能有效地追踪物体运动,尤其是对于纹理细节丰富的视频序列。在视频的纹理区域,尽管存在大量的周期重复模式,但这些模式仅在亮度上具有较大相似性,而彩色特征往往具有很大差别。如图1所示( 原图为彩色) ,图1a中的方框为Flower视频序列第37帧的纹理区域,其内容是颜色各异的花朵与绿叶,由图1b可观察到通过颜色很容易区分纹理细节,而通过图1c显示的亮度图却不易区分纹理细节,尤其是观察不出黄花与绿叶的区别。

因此,在SAD中加入彩色特征的匹配,可有效地避免SAD在纹理区域的错匹配。那么,融入彩色特征的SAD可按式( 1) 计算

式中: v是当前块Bt的候选运动矢量; p为在Bt内的像素位置; Yt-1( ·) ,Ut-1( ·) 和Vt-1( ·) 是前参考帧ft-1的亮度和色差分量; Yt + 1( ·) ,Ut + 1( ·) 和Vt + 1( ·) 是后参考帧ft + 1的亮度和色差分量。考虑到相邻帧像素间色差分量的差值常小于亮度分量的差值,因此,U和V分量的SAD值被乘以平衡因子W以使Y,U和V三分量的差值对式( 1) 具有均等的贡献。对于4∶2∶0的YUV视频,色差分量U和V的取样个数仅是Y分量的1 /4,为了保证任一候选匹配块和当前块均有相同像素位置的色差分量,因此在计算式( 1) 之前首先使用双立方插值算法[6]放大U和V分量至Y分量的尺寸。

彩色特征虽然能够缓解纹理区域错匹配带来的不利影响,但其无法准确地描述物体的边缘特征。由于边缘包含了准确块匹配的显著信息,且在边缘区域的匹配误差与视觉理解是十分相似的,所以在SAD中加入与边缘特征相关的项也可有效地提升运动估计精度。梯度可反映图像边缘,且计算图像梯度的方法较多,但为了不引入过多的计算复杂度,简单的Sobel算子[7]被用来计算视频帧梯度,如图2所示,通过Sobel算子计算出的梯度图( 图2b所示) 可清晰地展现原始帧的边缘特征,因此其可被使用描述边缘特征,并按式( 2) 融入到基于SAD的块匹配准则

式中: ΔYt-1和ΔYt + 1为由Sobel算子计算的前后参考帧ft-1和ft + 1的梯度图。由于梯度匹配误差与亮度匹配误差具有一定差别,因此需要加入平衡因子α去权衡各项对式( 2) 的影响。

使用式( 2) 进行块匹配,虽然可综合不同特征的匹配误差,但也引入了较高的计算复杂度。为了以较低的计算复杂度完成多个特征的匹配,本文算法将亮度特征、彩色特征和边缘特征通过特殊模板融合至单平面上,该特殊模板如图3所示。

图3中Y代表亮度像素点,G代表梯度像素点,U和V代表色差像素点,由图3可看出,4种特征点均分了每个匹配块的所有像素,且均匀地分布在整个匹配块平面上,这相当于将当前块分成了同样尺寸的4层,每一层均是原始匹配块尺寸的1 /4。由于视频具有层间相似性( 图像金字塔) ,即下采样获得的图像仍会保持与原始特征相似的特征[8],所以通过该特殊模板融合而成的多特征块仍会近似保持原始匹配块的特征。那么,通过使用所提出的特殊模板,式( 2)可被改进为

式中: BtY,BtU,BtV和BtG分别是当前块Bt的Y,U,V和G的像素点集合。通过使用式( 3) 进行块匹配运算,其计算复杂度与传统SAD相同,但却兼顾了多个特征的匹配,因此可在较低的计算复杂度下提高运动估计的精度。对于平衡因子W和α的选取,若干真实视频序列在不同的W和α取值下被测试,图4显示了内插帧的平均峰值信噪比随W和α变化的曲线,可看出当α固定为0. 1时,最大的PSNR值出现在W = 8附近,当W固定为8时,最大的PSNR值出现在α = 0. 1附近,因此,在本文中W和α分别取8和0. 1。

上述改进的块匹配准则将被使用在双向运动估计中计算当前帧的运动矢量场,为了进一步的加快运动估计速度,三维递归搜索( 3-D Recursive Search,3DRS)[9]被使用在双向运动估计中。得到当前帧的运动矢量场后,再使用重叠块运动补偿( Overlapped Block Motion Compensated,OBMC)[10]计算出最后的内插帧。

2 实验结果

实验数据选取了4个4∶2∶0的YUV格式的CIF标准测试序列来验 证本文算 法的有效 性,它们包括: Foreman,Mobile,Flower和Football,其中Foreman前景背景分明且背景有轻微晃动,Mobile包含物体缩放和平移、旋转等复杂运动,Flower包含丰富的彩色纹理细节,Football含有大量快速运动。为了测试内插帧的主客观质量,每个测试序列的前50个偶帧被去除,并再次利用各种帧率提升算法从剩余51个奇帧中重建。插帧客观质量通过内插帧和原始帧的PSNR衡量。为了评比本文算法的性能,对比了其他3种算法: 文献[4]提出的EBME算法( 块大小为8×8,全搜索半径为4) ; 文献[5]提出的Dual ME算法( 块大小为8×8,全搜索半径为16) ; 文献[9]提出的双向3DRS运动估计法( 分块大小为8×8) 。本文算法的分块尺寸为8×8,且其与Dual ME算法和双向3DRS算法均使用重叠尺寸为4的OBMC算法计算出最后的内插帧,对于EBME算法则使用文献[4]提出的补偿方法。

由表1可见,本文算法除Foreman序列外均超过了对比算法的最优者,尤其是对于包含复杂和快速运动的序列。对于Foreman序列,本文算法比双向3DRS算法略低0. 08 d B,这是因为Foreman序列具有较清晰的边缘且纹理细节简单,这使得传统SAD就可保证高精度的运动估计。对于具有复杂和快速运动的Mobile和Football序列,本文算法分别超出对比算法中最优者2. 00 d B和0. 46 d B,这表明了本文算法可有效地追踪复杂快速运动。对于色彩丰富的Flower序列,本文算法也超出了双向3DRS算法0. 39 d B,这表明本文算法可较好地区分彩色纹理细节。对于计算复杂度,表1也显示了在Intel Core i5 3. 20 GHz,8 Gbyte内存PC平台上的平均内插时间,可看出本文算法内插出一帧平均需要0. 42 s,其远低于EBME算法。对于Dual ME算法,本文算法平均缩短了0. 27 s,且获得了4. 49 d B的PSNR增益。由于本文算法与双向3DRS算法的不同仅在于: 双向3DRS算法使用了传统SAD; 而本文算法使用了基于多特征的SAD,那么,本文算法尽管在块匹配上与双向3DRS算法有相同的计算复杂度,但由于需要一定的计算量提取边缘特征和内插U,V分量,这造成了其平均内插时间高于双向3DRS算法0. 14 s,但相比于双向3DRS算法,其可有效地改善内插帧质量,平均获得了0. 86 d B的PSNR增益。

图5显示了不同算法重建Flower序列第90帧的主观视觉质量对比。首先可看到在路灯附近( 左边方框圈定) ,Dual ME算法和双向3DRS算法均出现了不同程度的模糊与变形,而本文算法能够更好地保护路灯的边缘特征,而对于路旁鲜花区域( 右边方框圈定) ,对比算法均无法保证清晰的纹理细节,产生了一定程度的模糊,尤其是对于双向3DRS算法,但本文算法很好地复原了纹理细节,获得了更好的主观视觉质量。

图6显示了不同算法重建Foreman序列第72帧的主观视觉质量对比。对于双眼和鼻子区域( 方框圈定) ,EBME算法和Dual ME算法均出现了不同程度的块效应。对于双向3DRS算法,其内插帧的左眼角纹理细节丢失,造成了一定的视觉质量衰退。本文算法能够有效地抑制块效应且可保护纹理细节,获得了良好的主观视觉质量。

3 小结

快速景象匹配算法控制策略 篇2

快速景象匹配算法控制策略

为提高景象匹配算法的匹配性能,分析匹配算法设计的基本思路及常见两类匹配算法的优缺点,提出采用一定的控制策略以加快匹配速度,进而提高匹配效率的思想,给出几种匹配控制策略的设计思路.以归一化积相关景象匹配算法为例,采用先粗后精的.分层匹配策略,实现了算法的加速,通过大量的匹配仿真实验,验证了该匹配控制策略的可行性、有效性.

作 者：曹菲 杨小冈 缪栋 张云鹏 Cao Fei Yang Xiaogang Miao Dong Zhang Yunpeng 作者单位：第二炮兵工程学院,西安,710025刊 名：导弹与航天运载技术 ISTIC PKU英文刊名：MISSILES AND SPACE VEHICLES年，卷(期)：“”(3)分类号：V448.23关键词：精确制导 匹配算法 控制策略 归一化积相关

双向匹配算法 篇3

最新人口普查结果显示, 我国60岁以上老年人已达到了1.78亿, 老年群体的“未富先老”、“空巢老人”甚至“空心老人”的出现, 暴露了当下养老服务价高质低的现实问题。而现有的大学生志愿者进社区活动虽然一定程度上缓解了养老服务对多元化、花费低廉的需求。但事前需求信息不对称、事中反应时间过长、事后跟踪评价困难始终阻碍着活动的进一步发展。

关于养老信息化的研究, 已有许多学者提出了建设性的解决方案。如阎青春提出通过现代通信信息技术构建起社区信息服务网络和为老服务平台, “打造没有围墙的养老院”[1];吴诺分析了都市社区居家养老信息系统的构成和实施策略[2]。另一方面, 不少学者也对老年服务和大学生志愿活动的线下对接机制进行了有效探究。本文针对为老服务和大学生志愿活动的双向匹配进行了信息化尝试, 提出新的业务流程, 并阐述了两者对接的信息管理系统, 建立事前预约、事中监督、事后评价的服务信息档案, 旨在健全与为老服务接轨的大学生志愿者服务机制。

二、方案描述

2.1整体思路。

本文提出改善为老服务与大学生志愿活动对接模式的整体思路如下:在信息技术的支持下, 收集录入为老服务需求及各高校大学生志愿者现有活动信息后, 老年人或其代理人可通过互联网查询筛选所需服务的基本信息, 大学生志愿者可及时更新所愿提供的服务信息和其他要求, 在至少一方请求匹配且系统匹配成功和短信确认后, 双方进入下一环节即线下联络, 活动完成后, 进行双方互评。本系统的优势在于提供老年人和大学生志愿者更广泛的选择, 并对双方的每一次活动信息如服务时间、类型、地点等进行记录, 旨在进行跟踪评价, 促使形成持续的良性循环。

2.2人员组织框架。

由于大学生志愿者提供为老服务是一种公益性质的活动, 程序繁杂度较低, 故采取扁平化的组织结构。

组织分为三个层次, 第一层由本系统及其管理员组成, 负责信息的正常流动及有效对接;第二层的组成结构为老年人代理人如社区居委会、各高校的志愿者协会负责人, 主要起到桥梁作用, 根据第一层提供的服务匹配信息, 相互沟通协调, 确定服务的各方面内容与形式, 确保第三层能够服务顺利进行;第三层是整个系统的基石部分, 包含老年人与大学生, 主要内容为根据事前协商举办为老服务活动。

2.3线下活动流程。

为老志愿活动倾向于“多对一”模式, 内容主要包括初期的与区内组织合作, 以基础服务为主;中期拓展服务范围, 趋于专业, 以项目形式运行;后期鼓励大学生参与为老服务管理工作, 提供培训服务, 动员更多社会力量参与到为老服务中[3]。

老年人或其代理人通过线上联络大学生志愿者负责人后, 志愿者负责人将现有资源包括志愿者协会、大学生社团等进行整合, 组成社区志愿者团队, 安排条件合适的志愿者进行服务, 服务后回到线上进行双方互评。其流程如图1所示。

2.4线上业务流程。

本系统对于老年用户或其代理人线上流程分为如下步骤, 如图2所示。

1.针对老年人或其代理人采用有效证件一次注册、永久有效的服务模式;2.注册完成后, 可搜索、筛选需求服务或直接选中服务要求;3.提交服务申请后, 系统会对两者信息进行匹配, 因可能存在两者对服务要求如地点不同而不成功等原因导致匹配失败, 此举旨在节约时间, 提高匹配效率;4.匹配成功后, 双方进行协商, 协商成功在线确认后, 邮件通知双方服务的基本信息如时间、地点、禁忌事项、可能所需工具、友情提醒等, 并在系统中改变两者状态, 禁止其他人再对该志愿者 (或负责人) 提出申请, 但可进行预约;5.转入线下活动, 双方确认服务完成, 最后进行双方互评。

三、系统框架

整个系统框架, 由表入里分为外层的信息展现层, 中层的业务逻辑层, 基础的数据库层, 如图3所示。

3.1信息展现层。

网上服务平台:用户可在线浏览、搜索、筛选服务, 了解服务提供方的基本信息包括志愿者所属大学、地址、时间要求、特色服务类型、历史评价等。服务完成后, 进行评价, 针对服务内容、态度等给出个人评价, 并提出建议。

短信邮件平台:一旦系统匹配成功, 短信发送服务基本信息包括双方基本信息和系统确认的服务信息, 并提示用户进行协商, 双方初步确认同意后回复系统短信, 完成线上预约转入线下联络。

3.2业务逻辑层。

该层包括用户信息管理、服务信息查询管理、服务匹配、服务确认、评价管理五方面。 (1) 用户信息管理:录入、更新用户基础信息, 老年用户信息包括姓名、性别、地址、身体状况、子女基本信息、喜好、禁忌事项等, 大学生志愿者基本信息姓名、性别、所属学校学院、专业班级、特长、服务类型、合适时间等; (2) 服务信息查询管理:记录用户检索、查看、成功匹配的服务及其类型、特点, 在此基础上用户再次查询时会推荐符合过往需求的服务, 或提炼高频词放在查询栏下, 可直接点击进行查询; (3) 服务匹配:用户选择服务后, 系统进行信息匹配, 主要检查关键信息项如双方对时间、地点、服务类型等的硬性要求是否合适, 匹配成功, 即转入线下确认, 若不成功, 重新选择; (4) 服务确认:匹配成功后, 发送服务信息短信等待双方确认, 双方协商后回复系统短信即可完成确认流程; (5) 评价管理:服务结束后, 双方进行互评, 评价包括服务质量、积极 (或配合) 度, 互评结果作为双方公开信息供后来用户参考。

3.3数据库。

本系统包括三类数据库, 一是记录老年人信息的数据库, 二是记录大学生志愿者团体或组织信息的数据库, 三是记录服务信息的数据库, 前两个由用户注册时填写并时时更新, 第三个根据前两个提供的服务信息以及所实际查询的服务信息数据、线下成功举办的服务活动组成。

四、关键技术

本系统运行核心为信息匹配和邮件发送技术, 以此为基础来实现老年人需求信息与志愿者服务信息的有效对接。

信息匹配技术主要运用了机械切词的方法, 主要指将一个汉字序列切分成一个一个单独的词, 达到电脑自动识别语句含义的效果。在本技术中, 机械切词主要应用在老年人“输入关键字匹配”方面, 将老年人输入的关键字切成一个个的词汇, 然后将这些词汇逐个与服务信息数据库中记录的高频词表相互比较, 符合要求的词汇将建立索引, 最后利用索引结构进行搜索, 将搜索结果展示在系统页面, 以供用户选择。

邮件发送技术是为快速方便收集到同一服务区域老年人的集体需求信息, 并及时发送给社区服务团队提交系统, 旨在利用信息化的技术快速解决老年人的实际需求, 使养老服务节约社会资源和具有可管可控性。邮件发送主要通过Java Mail接口技术实现邮件发送与接收的功能, 遵循邮件接收的POP3协议, 邮件发送的SMTP协议。

五、结束语

本文在分析大学生志愿者参与社区居家养老服务和养老服务信息化的现存情况后, 提出信息化解决方案和建立“为老服务与大学生志愿活动双向匹配系统”完善志愿服务机制, 使为老服务内容和老年人实际需求接轨, 扩展选择范围, 缩短志愿组织反应时间等, 帮助老年人享受更优质服务。

参考文献

[1]阎青春.打造没有围墙的养老院[N].经济日报, 2011, 8, 25 (6) .

[2]吴诺.都市社区居家养老服务体系中的信息化系统构建[A].价值工程, 2012, (13) :179-180.

BM串匹配算法与改进算法的研究 篇4

关键词：BM算法,模式串,改进算法,模式匹配

0、引言

串匹配是字符串的一个基本运算，对于给出的长度为n的正文字符T=T1……Tn和长度为m的模式串P=P1……Pm (n>>m），要找出模式P在正文T中的首次出现，一旦模式P在正文中找到，则匹配成功，否则匹配失败。字符串匹配应用广泛，在数字通信、文本编辑、图像处理、数据压缩、模式识别等应用中，都需要进行串匹配。近年来对于一维字符串的匹配问题研究较多。1970年，S.A.Cook从理论上证明了一维模式匹配问题可以在O (m+n）时间内解决，为串匹配算法的进一步发展奠定了坚实的理论基础，其中n、m分别为正文和模式的长度；D.E.Knuth, V.R.Pratt和T.H.Morris仿照Cook的证明构造了KMP算法[1]；R.S.Boyer和J.S Moore设计了BM算法[2]；Karp和Rabin给出了RK算法和随机算法，这些算法都是精确的串匹配算法。本文主要介绍BM算法及其改进算法。

1、现有模式匹配算法的分析

目前关于模式匹配的算法很多，其中最著名的两个是KMP算法[1]和BM算法[2]。两个算法在最坏情况下均具有线性的搜索时间。

1.1 KMP算法

KMP算法的基本思想[3]是将正文T和模式P左端对齐进行比较，匹配Ti和Pj时，若Ti=Pj，则继续往前匹配比较；若Ti≠Pj，则正文中i不变，模式中j指向Next[j]所指示的位置。Next[j]表示当模式中第j个字符与正文中相应字符匹配失败时，在模式中需重新和正文中该字符进行比较的字符的位置，这一位置只与模式本身有关，而与正文无关。

KMP算法虽然能使样本右移若干位，但存在一个局限，即移动距离不可能大于一次匹配操作所进行的字符比较次数j，存在这一局限的根本原因是KMP算法的匹配操作必须从左向右进行。由Boyer R和Moore J共同设计的快速字符串匹配算法--BM算法打破了这种限制，实践证明BM算法往往比KMP算法快上3～5倍[4]。当然BM算法还不是最快的算法，还有很多改进的BM算法存在，如BMH算法[5]、BMHS算法[6]、BMG算法[7]等等。

1.2 BM算法

BM算法的基本思想是从右向左的将模式串同文本做比较。开始时仍是P的最左边与T的最左边对齐，当在某一趟比较中出现不匹配时，计算模式串右移的距离，将模式串向右移动该距离，再进行从右至左的匹配；当与最右的模式符号做比较的文本符号在模式中根本就没有出现，则模式可以在这个文本符号之后移位m个位置，这种情况在KMP算法中是不可能出现的。

表1是对文本串T="pghshehneshathdbpsapurchased"和模式串P="purchased"，用BM算法进行匹配的过程（加粗部分为匹配失败的字符）。

下面我们对表1中的BM模式匹配过程作一简单分析：

(1）第一次匹配是模式串的P与文本中的T首字符对齐，然后从模式串的最后一个字符开始从右向左比较，即先将P[9]与T[9]进行比较，匹配失败，因此模式串向右移动，同时T[9]位置的字符"e"在模式串P中仅出现1次，模式串移动1个字符，即P[8]与T[9]对齐，从而完成第二次匹配。

(2）第三次匹配是将P[9]与T[10]先作比较，发现匹配失败，且T[10]字符"s"仅在模式串P[7]位置出现一次，模式串向右移动2个字符，使P[7]与T[10]；同理，第四次匹配后模式串再向右移动3个字符，使P[9]与T[15]对齐，准备第五次匹配。

(3）在完成第四次匹配后，P[9]与T[15]进行比较，匹配成功，然后P[8]与T[14]进行比较，匹配失败，模式串向右移动。

(4）第六次匹配时，由于上一次匹配后P[9]与T[18]对齐，经比较发现不匹配，模式串再次向右移动2个字符。

(5）同理，第七次匹配时，模式串向右移动8个字符，使P[1与T[20]对齐，然后从右向左进行比较，发现每个字符都能够匹配，最终匹配成功。

2、现有的改进算法

2.1 BMH算法

一般情况下，在BM算法实际应用中每个字符匹配失败的应用次数要远远超过匹配成功的次数。因此应用失配字符的相关函数在匹配过程中起到的是主导作用，因此，1980年Horspoo提出了BM算法的改进算法，即BMH算法。算法将匹配失败与计算右移量独立计算，计算右移量时不关心文本中哪个字符匹配失败，而是使用与模式串最右端的字符对齐的那个文本字符来决定右移量。一般情况下BMH算法比BM算法有更好的性能。

2.2 BMHS算法

1990年，Sunday在BMH的基础上提出了BMHS算法，该算法的主要思想是在字符匹配失败时考虑下一个字符T[m+j]的情况，利用与模式串最后一个字符对齐的文本字符的下一个字符来决定右移量的多少。如果下一个字符不在模式串中出现时，则直接跳过该字符，即将模式串最后一个字符向右移动m+1个字符；如果下一个字符出现在模式串中，则将模式串中的出现该字符与文本中的T[m+j]字符对齐。

表2为利用BMHS算法实现的模式匹配过程，具体如下：

(1）首先将模式串的P与文本中的T首字符对齐。

(2）第二次匹配时，将前一次的P[9]与T[9]进行比较，匹配失败，且文本中的下一个字符T[10]出现在了模式串中，于是模式串右移，将P[7]与T[10]对齐。

(3）第三次匹配，将第二次比较结果中的P[9]与文本中的T[12]比较，匹配失败，且文本中的下一个字符T[13]没有出现在模式串中，因此模式串直接划过10个字符，使P[9]与T[22]对齐。

(4）同理，P[9]与T[22]比较，匹配失败，且T[23]字符出现在模式串中，右移模式串，将P[4]与T[23]对齐，同时从右向左对比每个字符，匹配成功。

2.3 BMG算法

文献[7]结合了BM算法和BMHS算法的优点，同时考虑字符串后一位字符的唯一性，提出了一种快速的模式匹配算法--BMG算法。该算法避免了死循环问题，同时大大提高了最大位移m+1的出现概率。BMG算法中产生m+1位移主要有两种情况，一是下一位字符T[m+j]不在模式串P中，这与BMHS算法相同；二是下一个字符T[m+j]在模式串中唯一，且与模式串末位P[m]对齐的那个文本串字符T[m+j-1]决定的移动量比下一个字符T[m+j]决定的移动量大。

BMG算法过程是：当比较进行到文本T的j处，首先计算出由模式串P末端对应文本串字符T[j+m-1]得到的右移位置k1和T[j+m-1]后一位置字符T[j+m]得到的右移位置k2，再判断k1和k2的大小。如果k1>k2，再判断T[j+m]在模式串出现频次，用函数Q (X) 判断T[j+m]在模式串出现的频次。若Q (T[j+m]) =1，即T[j+m]在模式串只出现一次，则将模式串移动m+1位进行新一轮匹配；若Q (T[j+m]) =0，即T[j+m]在模式串出现大于一次，则将模式串末端和T[k1]处对齐进行新一轮匹配；如果k2≥k1，则将模式串末端和T[k2]处对齐进行新一轮匹配。

其移动过程见表3所示。

2.4 PBM算法

文献[8]中提出PBM算法，其基本思想是：在长为m的模式串P中找出一个最长的前缀子串S, k是S长度，n是正文串的长度，令该子串的末字符Pk为模式串所有字符中最后一个首次出现的字符，根据S末字符Pk的惟一性，确定Pk在正文T中每次出现的位置，并对Pk的位置加以标注，在正T中仅就每两个被标注的相邻Pk之间长度不小于S的字段，对S进行模式匹配。若S匹配成功，则对模余下的部分E=P-S进行匹配；若匹配不成功，则在正T中寻找下两个相邻的被标注的Pk之间长度不小于S的长度的字段，这样模式P从正文中每次滑过的字段长度不小于S的长度。

3、BM算法与改进算法的比较

BM算法执行效率较高，但BM算法在匹配时的尝试中，采用从后向前比较的方式，对模式串的后缀进行匹配，在完成一次尝试 (包括匹配失败或者成功) 后，利用两个根据模式串预处理好的移动表坏字符移动与好后缀移动来尝试位置后移，但是由于它没有考虑已匹配的后缀与导致匹配失败的当前字符之间的相邻关系，使得算法的效率不够高。BM算法时间复杂度却为O (mn) ，大大高于KMP算法的时间复杂度O (m+n) 。

BMH算法在匹配过程中不管坏字符在哪个位置，只根据与模式串P末字符对应的字符在模式串中出现最大的位置来移动模式串，进行下一轮匹配，其在最好的情况下的时间复杂度为O (n/m) 。但该算法未考虑T[m+1]在模式串中是否存在，以及T[m+1]与T[m]在模式串P中的关系，同时也未考虑T[m+1]是否在模式串P的串首等特性。

BMHS算法的在最好的情况下的时间复杂度为O (n/m+1) ，其右移量比BMH算法的右移量大，BMHS算法最大移动距离为m+1位，BMH算法最大的移动量为m位。所以通常情况下，BMHS算法比BMH算法快，但当与模式串最后一个字符对齐的文本字符不出现在模式串中，而下一个字符出现在模式串中时，BMHS算法的效果就不如BMH算法了。

BMG算法的最大右移量为m+1位，时间复杂度为O (n/m+1) 。同时在综合最大移动量、产生最大位移的概率、模式串跳跃位置、时间复杂度等方面因素，BMG算法在提高匹配速度上要比BM、BMH和BMHS算法要高。但当下一个字符T[m+j]出现多次时，只是将模式串移动最小距离，而没有考虑到该字符在串中出现时，其前一个字符T[m+j-1]如果不在模式串中则可以直接跳过，减少匹配次数。

4、一种改进的BM算法

通过几种改进算法的比较，各种改进算法各有优缺点，但这几种改进算法都有一个共同的缺点，就是在模式串P和文本T对比时，如果对比字符在P中多次出现时，这几种算法的效率就没有大的差别。针对这一问题，说明BM的改进算法中还是有可以改进的地方。因为BMG算法在字符重复率不高的情况下的匹配速度相对较高，在此基础上提出了对BMG算法的一点改进。改进思路是将BMH算法与BMG算法结合起来，当下一个字符T[m+j]在模式串中多次出现时，则去判断前一个字符T[m+j-1在模式串中是否存在，若存在则与原有BMG算法相同，若不存在，则说明用BMG算法得到的下一次比较肯定是不成功的，同时判断T[m+j]是否是模式串的首字符，模式串可以最大划过m+1个字符。

算法思路过程如下（比较进行到文本T的j处）：

(1）首先计算出由模式串P末端对应文本串字符T[j+m-1得到的右移位置k1和T[j+m-1]后一位置字符T[j+m]得到的右移位置k2，其中k1=j+m-1+Miss[T[j+m-1]]；k2=j+m-1+Miss[T[j+m]]。

(2）若k1>k2，则判断T[j+m]在模式串出现频次，用函数G (X) 判断T[j+m]在模式串出现的频次。

若G (T[j+m]) =1，即T[j+m]在模式串中只出现一次，则将模式串移动m+1位进行新一轮匹配。

若G (T[j+m]) =0，即T[j+m]在模式串中出现大于一次，则判断T[j+m-1]是否存在于模式串P中。如果T[j+m-1]存在于模式串P中，则模式串末端移到和T[k1]处对齐进行新一轮匹配，如果T[j+m-1]不在模式串P中，则再判断T[j+m]是否是模式串的首字符，如果是首字符则模式串移动m位，若不是首字符，则模式串可移动m+1位。

(3）若k2≥k1，则将模式串末端和T[k2]处对齐进行新一轮匹配。

表4中，先将P[8]与T[8]对齐，对于BM算法P[8]与T[8]不匹配，且T[8]不在模式串中，向右移动8个字符。用BMG算法时，先比较P[8]与T[8]，发现不匹配，则计算k1和k2, k1=8+（8-0）=16, k2=8+（9-8）=9，结果为k1>k2，然后T[9]在模式串P中出现的次数大于一次，因此模式串末端向右移动到T[16]处。改进的BM算法中，当得到k1>k2，且T[9]在模式串P中出现的次数大于一次，则判断T[9]是否是模式串的首字符，发现不是首字符，则可以跳过T[9]，模式串末端移到T[17]位置。这种改进的算法相比BMG算法进一步提高了模式串移动m+1为的概率。

5、结论

通过对相同纯英文文本（文本长约1K，模式串长9）采用不同方的BM算法，改进的BMG算法相比BM算法比较次数减小约50%，比BMH算法的比较次数约减少35%，比BMHS算法的比较次数减少约22%，相比BMG算法的比较次数约减少1%。改进的BM算法相比BMG算法虽然没有大幅减少比较的次数，但也有所改善，主要是在普通文本中在模式串长度范围内字符出现重复概率相对比较小。如果文本中存在较多的重复字符时，改进的BM算法性能将有较为明显的改善。

6、结束语

目前对于BM算的改进算法有很多，各有特点，在对不同文本模式进行匹配时也有各自的优势。本文在BMG算法的基础上提出的改进算法，进一步提高了匹配过程中产生m+1位移动的概率。由于时间关系，并未对改进算法进行大量的匹配实验，该算法的实际效果还没有得到有效的验证，但通过简单文本的验证，改进的BM算法的性能已得到初步验证，具有一定的实用性。

参考文献

[1]KNUTH DE, MORRIS J H, PRATT VR Fast pattern matching instring[J].SIAMJournal on Computing, 1977, (6) :323-350.

[2]BOYER RS, MOORE J S.A fast string searching algorithm[J].Commu-nications of ACM, 1977, 20 (10) :762-772.

[3]闵联营, 赵婷婷.BM算法的研究与改进[J].武汉理工大学学报 (交通科学与工程版) , 2006, 30 (3) :528-530.

[4]王建国, 郑家恒.BM串匹配算法的一个改进算法[J].计算机工程与科学, 2007, 29 (5) :94-95.

[5]Nigel H R.Practical fast searching in st rings[J].Software2 Practice andExperience, 1980, 10:501-506.

[6]Daniel M S.A very fast subst ring search algorithm[J].Communications ofthe ACM, 1990, 33 (8) :132-142.

[7]张娜, 侯整风.一种快速的BM模式匹配改进算法[J].合肥工业大学学报 (自然科学版) , 2006, 29 (7) :834-838.

Chord双向查找算法研究 篇5

通过何种方式的查询来实现资源定位是结构化P2P网络的一个核心问题。Chord算法由MIT提出,其核心思想就是要解决在P2P应用中遇到的基本问题:如何在P2P网络中找到存有特定数据的节点。由于Chord搜索路由算法是以较长的时延为代价,增强用户查询的动态性,使网络的稳定性大大的增强,对突发状况的解决难度相对减小。因此很多文献对Chord做了进一步地研究。文献[6]提出的基于Chord的分层模型以大量增加路由表长度为代价,导致超级节点可能成为系统的通信瓶颈。文献[5]提出One-Hop的算法,如果每个节点维护全体节点的信息,那么所有的查找有可能只需一跳完成,但这会导致每个节点的维护开销过大。

本文先对经典Chord算法进行分析,通过扩展Chord路由表,提出一个新的算法,该算法删除路由表中的一些冗余信息,增加方向路由信息,变Chord的单向查找为双向查找。该算法能减少转发次数,缩短搜索路径的长度,提高搜索效率。

2 Chord算法分析

通过将关键字对2m取模后顺序排列,节点和对象关键字都被映射到了一个大小为2m的环上,即Chord环。对象关键字为K的数据对象被分配给Chord环上节点关键字为K的节点;如果K节点不存在,则将对象关键字K分配给Chord环上节点关键字按顺时针方向紧随其后的节点。存储关键字K的节点称为K的后继节点,表示为successor(k)。

节点查找算法:拓扑环中,每个节点只能与后继节点建立连接,只知道其后继节点的信息。进行查找时,节点依次查询其后继节点,直到节点N满足条件:N.Nid

算法伪代码说明如下:

每个Chord环中节点都需要维护一张路由表。节点n0的路由表中的第i(1≤i≤m)项是Chord环上标识符大于或等于(n0-2i-1)mod2m的第一个节点,即(n0-2i-1)mod2m的后继节点。如果关键字和节点用m位二进制位数表示,那么路由表中就有m个表项,但这样的路由表只能覆盖[n0,n0-2m-1]半个环的区域。

图1是Chord组织实例图,m=6的一个Chord环,节点8查找关键字52,遵循Chord查找算法,经过3次转发,最后找到52的后继节点56。由N8的路由表可知,节点8的第2条,第3条和第4条都是冗余信息,这样势必会对路由效率造成影响。造成冗余的原因是节点的数目分布稀少。如果假设节点平均分布,只要n

3 改进的Chord双向路由

对于一个有N=2m个节点的Chord网络,每个节点要维护一张有m个表项的路由表,平均查找跳数为(lb N)/2,但是该路由表中有1/3左右的重复表项,查找效率不高,可以把重复的路由信息删除,在路由表的多出的空间添加其他节点的信息,增加Chord原有路由表的指针密度,变Chord的单向查找为双向查找,则会提高查找效率。

一个大小为2m的Chord环,节点数为2n,假设所有节点平均分布,则每个节点路由表中的冗余信息数量为lb(2m/2n)=m-n条。那么可以补充m-n条路由信息。

3.1 双向路由表的构建

双方向路由表建立主要通过3步:

(1)建立一张有m个表项的方向路由表。节点n0方向路由的第i(1≤i≤m)项是Chord环上标识符等于或小于(n0-2i-1-2m)mod2m的前驱节点,即predecessor由对称性可知,临时建立的方向路由表也有m-n条冗余信息。当n≤m/2时,方向路由表中的有效条目数n等于或小于m-n条,而当n>m/2时,方向路由表有效表项n大于m-n条。

(2)当n≤m/2时,由上到下依次删除原表项重复的n个表项,当n>m/2时,将所有重复的m-n个表项删除。

(3)当n≤m/2时,从方向路由表中由上到下依次选取不重复的n个表项,将选取的表项依次添加到双向路由表的第m-n项开始到第m项;当n>m/2时,从方向路由表中由上到下依次选取不重复的m-n个表项,也将选取的表项依次添加到双向路由表的第n+1项开始到第m项。

图2是一个m=6,n=4的一个Chord环,且各节点平均分布,N8的双向路由表如图2所示。

3.2 双向路由表的查找

一个节点查找关键字K时,首先要选择顺时针还是逆时针查询。假设n0接到查找关键字为K的请求,它首先要查找关键字K的后继结点successor(K),则n0与K之间顺时针方向的环长为(2m-n0-K)mod 2m,n0与K之间逆时针环长为(2m-n0-K)mod2m。对两个长度进行比较,选择环长小的方向为路由方向。

当选择顺时针方向时,依然采用Chord协议的算法。当为逆时针方向时:n0查找自己的双向路由表中方向路由表条目,找到等于或大于K的第一个节点,并将这个查找请求转发给该节点,重复以上查找,直到找到K的后继节点。双向路由算法伪代码说明如下:

3.3 性能分析

现假设n0查找的目标节点位于[n0,n0-2m-1],由于Chord环的平均查找跳数为(lb N)/2,而改进算法在[n0,n0-2m-1]半环上的平均查找跳数为1/2l(N/2),根据对称性可知,目标节点位于剩下的半个环时,平均查找跳数也为1/2lb(N/2)。我们假设节点落入哪个区域为随机的,所以改进后的Chord的平均查找跳数为故比原来Chord的平均查找跳数要少。

4 结束语

本文在Chord的基础上提出路由优化算法,该算法增加路由表指针密度,通过增加一个逆向路由表,实现双向查找,减少了平均查找跳数,提高了查找效率。下一步的工作主要进一步研究该改进的算法和用仿真工具来验证算法的改进程度。

参考文献

[1]曹强.基于SIP协议的IP网络多媒体通信系统的研究与实现及其应用.山东师范大学,2009

[2]张文博.基于双向路由的Chord最佳路由计算.微机处理,2009,(6)

[3]卢卫青,张振宇,龚红翠.基于物理拓扑的双向搜索Chord路由.计算机工程,2009,(22)

[4]孔中明.Chord模型分析.应用技术研究.2009,(5)

[5]Li X,Zhuang Z Y,Liu Y H.Dynamic layer management in super-peer-architectures.IEEE Transactions on Parallel and Distributed Systems,2005,16(11):1078~1091

[6]Lin J W,Yang M F,Tsai J.Fault tolerance for super-peers of P2P systems Proc of the13th Rim Internatianl Symposium on Depend-able Computing.[S.1.].IEEE Press,2007

双向匹配算法 篇6

信息革命 对人类社 会产生了 巨大的影 响 , 尤其是今 天的大数据 时代。手 机上网变 得越来越 普遍 , 移动数据 的爆炸式增 长态势越 来越突出 , 大量新数 据无时无 刻在涌现 ,包括网络 日志、音 频、视频 、图片 , 地理位置 信息等非 结构化数据 。大数据 信息量庞 大且多为 非结构化 的数据 , 对搜索引擎 提出了更 高的要求 , 它不再是 帮助人们 从海量信息中查找更多的结果, 而是快速地查找精确的结果。大量的不相关信息导致价值密度的高低与数据总量的大 小成反比 。因此 , 如何通过 强大的机 器算法更 迅速地完 成数据的 价值“提纯 ” , 确保根据 用户需求 , 在大数据 库中查询 与用户阅读 资料相匹 配的数据 , 成为目前 大数据背 景下亟待 解决的难题。

目前人们通过对著名算法的研究改进了许多效率更高算法, 典型的是对BF[1]算法、KMP[2,7]算法和BM算法[8]及在这两种算法上改进的各种算法[3,4,5,9]的不断改进, 使得字符串的匹配效率取得明显的效果, 这些算法的共同出发点是解决如何使模式串向后移动最佳距离, 尽量跳过不必要比较的字符, 减少字符串的比较次数, 从而提高匹配效率。而思想是源于实际经验, 通过对BF算法的改进解决如何使模式串在一次匹配中比较最少的次数而加快匹配进度。

2 BF算法分析

BF (Brute-Force) 算法的基本思想是 : 从目标串的第一个字符与模式串的第一个字符比较。若比较相等, 则继续逐对字符进行后续的比较, 否则用目标串的第二个字符起与模式串的第一个字符重新比较, 直到模式串中每个字符和目标串中的一个连续字符系列都比较相等为止。若不能在目标串中找到与模式串相等的子串, 说明匹配失败。

假设目标串为target=aedaaebcdb, 模式串为pattern=aebc,长度分别为10、4, 其BF算法模式匹配过程如下所示。

(1) 第一次匹配 : 比较3次后p2不等于t2, 匹配失败。

(2) 第二次匹配 : 比较一次后p0不等于t1, 匹配失败。。

(3) 第k次匹配 : 比较两次后p1不等于tk+1, 匹配失败。

(4) 第k+1次匹配 : 比较4次都相等 , 匹配成功 , 匹配字串为tk+1tk+2tk+3tk+4。

BF算法实现简单 , 易于理解。BF模式每次匹配都是从模式串的第一个字符开始逐个字符往后匹配, 匹配完一 遍后 ,模式串往后移一个字符的距离, 匹配效率很低。

假设目标串长度为m, 模式串长度为n, 其中0

3 算法的改进

3.1 算法背景

对于任何已知的模式串不必用其字符从第一个字符一一与目标串中的相应字符比较, 这样效率很低。若是人工匹配,当一个人拿到一个模式串时, 并不会立即机械地按照字符从第一个字符开始一一与目标串比较, 通常会仔细观察模式串的结构特点和内容特点, 然后再在目标串中查找有没有符合这些结构特点和内容特点的子串。若有, 则确定子串在目标串中的位置, 然后再进一步比较模式串中其余字符, 当所有模式串中的字符都与目标串中的字符比较相等时才确定子串是所找的字符串, 否则匹配不成功。若没有, 则肯定子串不是要找的字符串。基于这种以人的常识设计算法, 使得机器能够像人的思维一样进行模式匹配, 大大提高模式匹配效率。

3.2 结构描述

该算法与其他的改进算法不一样, 主要是优化在一轮匹配中字符的比较顺序。算法的主要核心是如何表示模式串的结构和内容, 保证模式串的字符与目标串中对应位置的字符比较。为了表示所有模式串的结构和特点, 这里用一个二元组来表示不同模式串的结构和内容, 这里定义为抽象模式串。二元组的表示为:

A (m) =f (C,S)

其中m是原模式串; C是原模式串挑选出来的具有代表原来模式串的特殊字符的集合; S是支撑C中字符能够与目标串中相应位置的字符比较的结构的集合; A (m) 是原模式串的结构和字符串组成的新模式串, 即抽象模式串。

抽象模式串中的字符可以是模式串中异于其他字符的一个或一类特殊字符, 也可以是连续几个有规律的字符, 在目标串中有这样规律的连续字符或特殊字符很少, 这样规律的字符或特殊字符的组合更少。

不同的抽象模式串的结构不同是由于组成抽象模式串的连续字符数和它们之间的间隔字符数不同, 这里可用数组或链表来表示这种抽象模式串的结构, 把抽象模式串中连续的字符数和间隔的字符数作为数组元素或链表结点, 其顺序按连续字符数和间隔字符数在模式串中的位置顺序存放, 为了使抽象模式串的结构有统一的表示方法, 模式串的第一个字符和最后一个字符要包括在抽象模式串里面, 下面介绍用数组来表示结构的方法。

假设目标串为target=t0t1t2…ti-2ti-1ti, 模式串为pattern=p0p1…pj-1pj, i、j分别表示目标串和抽象模式串字符的下标 , 根据模式串的特点选出特殊字符组成抽象字符串, 设选出的字符为p0,p5,pj-5,pj-4,pj-3,pj, 则抽象字符串的结构表示为 :

AB [] = {1, 4, 1, j-11, 3, 2, 1}

算法执行时, 根据该数组控制先用抽象模式串中的字符与目标串中相应位置的的字符匹配, 开始时数组中第基数个元素控制比较个数, 第偶数个元素控制间隔字符数, 即p0→t0, p5→t5, pj5→tj-5, pj-4→tj-4, pj-3→tj-3, pj→tj, 若抽象模式串中从左到右顺序出现第一个字符不匹配则按相同方式进行下一轮匹配; 若抽象模式串中的字符都比较完成且都相等, 再通过该数组控制模式串中第一个没有比较的字符开始比较, 此时数组中第偶数个元素为比较个数, 第基数个元素为间隔字符数。这样先通过特殊字符与目标串中的字符比较减少比较次数, 从而达到高效匹配。

3.3 算法执行过程

假设目标串为target=abcdeabadca&cbbbabcd&abbb。通过观察模式串的字符把特殊字符 & 和连在一起的3个b以及首字符作为抽象字符串的字符, 3个子串的间隔字符数为3, 1,用AB表示抽象模 式串的数 组名 , 其结构可 记为 : AB [] ={1, 3, 1, 1, 3}, 算法具体执行过程如下所示。

(1) 第一次匹配 : 根据数组第一个元素比较第一个字符 ,此时相等, 再隔3个字符比较, p4不等于t4, 匹配失败。

(2) 第八次匹配 : 抽象模式串中的字符与目标串中对应位置的字符都相等, 则比较模式串中第一个没有比较的字符,p1不等于t8, 匹配失败。

(3) 第十七次匹配 : 此时抽象模式串中的字符与目标串中的字符相等, 模式串中其余字符也相等, 匹配成功, 返回t16。

该改进算法相对于BF算法的优越性: 抽象模式串中的字符是从整个模式串中选出来的特殊的字符, 它的内容体现了整个模式串的内容特征, 其字符的位置贯穿整个模式串, 相对于BF算法从头开始一一进行匹配 , 能加快字符匹配失败的速度 ;它的特殊结构保证模式串中特殊的字符能与对应位置上的模式串的字符比较, 连接整个模式串的特殊字符; 抽象模式串中的字符数少, 大多数情况下抽象模式串就能确定字符匹配失败。一般抽象模式串的字符数是模式串的几分之一甚至更少,则匹配效率可能就是BF算法一一匹配时的几倍或更高。

4 实验结果

根据文献[6]中提供的数据对改进算法与BF算法的效率进行了比较发现, 改进算法匹配成功后比较次数比BF算法要少, 则可说明改进的算法比BF算法更有优势。比较结果如表1所示。局限于模式串的长度 , 该算法的优势未能完全体现出来, 对于长度越长的模式串的优势越明显, 再就是从模式串中选择合适的字符组成抽象字符串也是提高匹配效率的关键,试验中由于目标串的极端性会出现个别反常情况。

5 结语

该算法适用于相似度匹配且要求模 式串有一 定的长度 ,主要是考虑到了人在模式匹配过程中一般会采取的思维方法,这种以理性人的思维设计算法是文中提出的算法提高模式匹配效率的重要思想支柱, 这也就说明了一个道理:“在生活中怎么想, 就这么编程”。这样设计能达到预想到的效果, 更好地为人类服务。

摘要：基于人在字符串匹配过程中常用的思维,提出一种从模式串中提取特殊字符和具有特殊结构的字符组成字符串,用数组或链表来表示这种字符串的结构,使得提取出来的字符能与目标串中相应位置的字符比较的算法。用以减少比较次数,提高匹配效率。

双向匹配算法 篇7

关键词：SIFT,图像匹配,特征点提取,图像处理

0 引言

图像匹配作为实现复杂的图像处理和视频处理的前提,是未来机器视觉处理技术发展的基础,在智能视频监控、机器人视觉、医疗手术、遥感测绘等领域有着非常广泛的应用,如何提高图像匹配速度和准确性将直接关系到整个机器视觉处理系统的效率和性能[1,2,3]。

目前,常用的图像匹配算法可以分为基于区域的图像匹配算法和基于特征点的图像匹配算法,其中基于区域的图像匹配算法由于计算复杂、效率低,往往不具备实用性[4]。而相对于区域匹配算法,基于特征点的图像匹配算法在处理过程中只需要对图像中的特征点进行处理和分析,因此极大地降低了图像匹配过程中的处理时间,计算时间复杂度极低,并且具有较高的匹配精度和可靠性,成为了目前应用最为广泛的图像匹配算法[5]。在基于特征点的图像匹配处理过程中,通常包括特征点检测、特征匹配、变换模型估计和图像重采样及变换等功能操作。具体地,特征点检测和匹配即是整个基于特征点的图像匹配的关键,而且又是图像匹配技术的应用前提,同时也已然成为当今图像处理技术领域的研究热点之一[6]。SIFT算法作为目前公认的最为理想的、普适性特征点提取算法,由其检测的特征点具有旋转、尺度、反射和光照等不变性,而且表现出极强的鲁棒性。但是该算法的时间复杂度却颇高,随着对智能视频处理速度的显著提升,使得强化完善SIFT算法的实时性和精准性,即已成为未来SIFT算法在复杂的图像处理系统中进一步拓展应用的研究攻关重点[7]。虽然目前国内外相关专家和机构都已根据自己的需求针对SIFT算法实施了一定的改进,如哈佛大学Ke等人提出的一种PCA-Sift算法通过降维技术有效地降低了SIFT算法的时间复杂度,但是同时也降低了角点检测精度,李晓明等人提出的改进的SIFT算法,主要根据遥感图像的处理特点进行提速,只是在遥感图像处理方面取得了较好的效果,但不适合其他图像处理,并且又降低了算法鲁棒性[8]。刘佳等人[3]用32维特征点描述向量,再运用欧式距离确定匹配点剔除误匹配点,提高了匹配正确率。刘辉等人[9]用Canny算子去除边缘点的影响,并配合以RANSAC方法消除误匹配,改进SIFT算法。冯政寿等人[10]用Harris算子结合张春美等人[11]的改进算法,以降低算法复杂度。综上可知,从目前图像处理技术相关应用领域对图像匹配处理的需求,以及已有的SIFT算法研究来看,在保证SIFT算法精度、鲁棒性的同时、优化提升基于SIFT算法的图像匹配速度则是今后图像匹配处理中亟需解决的核心焦点课题之一[12,13]。

结合这一背景需求,本文以SIFT特征点提取算法为基础,对其加入了合理改进,并基于Harris算法[14]提出了一种改进的SIFT算法以在确保sift算法鲁棒性和精度的同时提升其处理效率,对获得可观图像处理系统性能具有非常重要的现实意义。

1 相关理论基础

1.1 Harris算子

Harris算子是基于Morave算法的演化推理而来,其在图像匹配过程中的角点特征提取方面具有优秀强大的效率优势[15]。该算法中,角点检测的计算数学模型如式(1)所示:

式中,w(x,y)为高斯平滑因子,E表示在像素点(x,y)的地方移动一个(u,v)的窗口的亮度变化值,也就是与此像素点对应的一个梯度值,究其实质就是利用了图像二维信号的自相关的特点[16],并根据式(1)的原理,采用泰勒公式对其进行展开,同时忽略展开后的高阶项,就可以得到如下简化后的处理模型:

式中,Ix和Iy分别代表像素点(x,y)在水平方向和竖直方向的求导结果,根据泰勒公式展开后的简化模型可以看出,在该模型中每个像素点都有一个与之相对应的四元矩阵M,通过该矩阵就可以计算得到该像素点的相关的梯度信息。

基于上述简化后的数学模型,定义M的特征值为λ1和λ2,那么根据这2个特征值就可以得到相关的像素点的变化量,同时再通过定义相关的阈值,就可以根据特征值的大小对像素点进行分区,如果λ1和λ2都较小则判定其为平坦区域,一个较大、一个较小即确定其为边缘区域的像素点,否则可断定该点为角点,基于这一原理,就可以从图像中快速提取出相应的角点,具体计算模型如下:

式中,det表示矩阵M的行列式,trace为矩阵M的迹,k为系数,其取值通常设置在0.04~0.2之间,综上就是Harris算子提取角点特征的基本原理。相对于SIFT算子,Harris算子对角点的检测效率极高、检测的角点特征分布均匀,并且可以实现对角点特征的定量提取,但是抗噪能力却会略差,而且也容易受到干扰。

1.2 SIFT算子

SIFT算法作为目前图像处理领域公推的一种性能较好的算法,其检测精度和鲁棒性极强。基于SIFT算法的特征点检测是建立在多尺度分析理论基础之上,在应用SIFT进行特征点检测过程中,首先需要根据图像生成相应的参考图像和待匹配的图像的多尺度空间,在多尺度空间生成之后,再将不同尺度下的图像被检测出的局部极值点设置为后续进一步检测的候选特征点,同时通过提出低对比度和边缘相应点对该候选集合施行进一步的优化,其中在对特征点进行描述的过程中主要是计算出每个角点的主方向,而后就以角点为中心的圆形邻域为基础进行直方图统计,并根据直方图统计结果生成相应的特征描述因子,此后计算特征描述因子的距离,与预先设置的阈值进行比较,再次对候选集合加以进一步优化,最终确定候选匹配点,从而建立整合有匹配图像和参考图像的空间映射。

该过程中,多尺度空间的建立原理主要是构建一个高斯金字塔和高斯差分金字塔模型,具体如图1所示。

在尺度空间上进行局部极值点检测,将其加入到候选特征点点集合中,研究实现示意图如图2所示。

在SIFT算子中的特征描述重点是通过计算像素点(x,y)的梯度模值以及指示方向来提供定义的,其数学模型如下:

式中,L(x,y)为像素点(x,y)的尺度函数,m(x,y)为梯度模值,θ(x,y)为方向。

基于上述模型,在匹配的过程中就可以通过计算以特征点为中心的邻域的直方图,得到梯度方向的直方图,并且利用一个标准差σ为1.5L(x,y)的高斯噪声对梯度方向的直方图进行加权,如此处理后的像素点即已赋予了位置、尺度和方向3个信息;利用这些特征信息构建一个特征描述符,从而最大程度地保证其在光照变化、旋转幅度和比例缩放过程中能够保持不变性,最终实现具有极强鲁棒性的图像匹配。

论述至此,给出了就是基于SIFT算子进行图像精准匹配的完整过程,分析研究该过程发现,由于在SIFT算子中,设定特征是通过一个二维方向直方图来进行描述,获得了突出的刻画效果,但是处理过程也将趋于复杂,时间复杂度较高。

2 基于改进SIFT算法的图像匹配算法

2.1 图像匹配算法基本原理

综合上述对SIFT算法基本原理的展开分析,可以得到利用SIFT算法进行图像匹配的基本流程如图3所示。由图3可知,整个图像匹配包括特征点提取、特征点匹配、变换模型估计和图像重采样与变换4个过程。具体地,在特征点提取的过程中主要是建立多尺度空间(即高斯金字塔和高斯差分金字塔)和进行尺度空间的极值点检测;特征点匹配主要是利用BBF算法进行像素点搜索,同时构建出特征点之间的欧式距离关系模型,再通过设置阈值来判定参照比较而确定候选匹配特征点集合,并利用Opencv提供的RANSAC算法对特征点集合完成进一步优化,得到精确的特征点集合,实现精准匹配;变换模型的估计过程主要是利用变换模型来描述匹配图像和待匹配图像之间的变换关系,并且计算出相关的模型参数;图像重采样与变换主要是采用插值算法对变换后的图形进行插值,最终完成2个图像的精准匹配。

2.2 SIFT算法的改进

结合前文对Harris算法的原理分析,其在角点特征检测上相对于SIFT算法具有明显优势,在算法结果上表现出更好的实时性和更高的算法效率。因此在改进SIFT算法中,本文采用Harris算法进行角点提取,也就是将SIFT算法的角点提取使用Harris算法实现。同时,为了有效提升SIFT算法的效率,本文重点采用了主成分分析方法对其进行数学降维处理,就是在SIFT处理过程中找出一些综合变量来替代原来的复杂变量,限制前提是保持彼此之间的数学关系和变换关系恒定不变;处理过程中主要是利用仿射变换模型来近似地建立了SIFT匹配过程中的图像变换表示,同时利用RANSAC算法进行误匹配点检测和提取,深度提升其匹配精度,使得改进后的SIFT算法可以在获得较高匹配精度的同时,又极大地提高算法的效率。改进后的SIFT算法的实现流程如图4所示。

3 实验结果及分析

基于前文改进的SIFT算法和未改进的SIFT算法的原理,研究中采用opecv2.0开发库构建图像匹配系统,对本文设计提出的算法进行测试,测试结果如图5所示。通过图5可以看出,改进后的SIFT匹配算法得到的结果与原算法结果保持一致。同时仿真结果指出,改进后的算法得到的匹配特征点为218个,而原算法为421个,匹配的特征点虽然减少,但是匹配的特征点却更加均匀精确,如此即使得匹配时间大大降低:改进后的算法匹配时间提升了42 ms,只需要12 ms就能快速地实现匹配。

为了完善研究结论,文中继而设计给出了基于改进后算法而获得的图像拼接效果,如图6所示。可以看出,改进后的算法在提高效率的同时,也可以保持较高的匹配精度和准确性。

4 结束语

基于分段移位的虹膜匹配算法 篇8

虹膜识别已经成为近些年来生物特征识别领域的一个热点,相对于其他生物特征如:指纹,掌纹,静脉,人脸等,虹膜具有更高唯一性、稳定性、可采集性、防伪性和非侵犯性等优点[1]。虹膜识别也有广泛的商业前景,例如护照核对,银行自动付款机(ATM),财产或资产的警戒入口、法律实施、政府情报等,另外门禁保安,远程登录,津贴核实,出生证明,证书和现有的使用钥匙或各种卡等也都有很好的应用前景[2]。

现有的虹膜识别系统中,Boles提出的小波变换过零点虹膜识别算法[3]成为主流的虹膜识别算法之一,已经被广泛认可。近年来,在此基础上出现了一些改进的过零点方法如Sanchez-Avila等人[4],他们使用了不同的相似度匹配方式,如Euclidean距离和Hamming距离。田启川等人利用过零检测算子与信号局部的相关性提取虹膜纹理特征[5]。应忍冬等人[6]提出了有限变形相似度算法,克服了虹膜瞳孔缩放带来的影响。对于现有的虹膜图像采集装置的光源往往都存在侧光,这种光源使得虹膜纹理成像发生偏移,导致过零点的特征编码发生移位,从而影响特征匹配的相似度。现有方法并没有对同一个虹膜不同次成像的虹膜纹理会发生偏移,导致编码如何发生移位并没有具体研究。

本文分析了导致虹膜纹理偏移的因素和偏移规律,针对偏移规律提出了一种特征编码分段移位匹配的方法。该方法不但能够提高同一个虹膜不同次成像纹理偏移的特征匹配相似度,而且适应于实际情况的虹膜识别系统中。

1 过零点特征提取

1.1 二维Gabor滤波器

直角坐标系下的2D-Gabor变换函数[7,8,9,10,11]如式(1)所示:

其中:(x0,y0)表示滤波器中心的位置,(α,β)表示高斯窗函数的有效宽度和长度,(u0,v0)确定了滤波器的频率和方向。

图1(a)显示了二维Gabor变换实部滤波器形状,图1(b)显示了二维Gabor变换虚部滤波器形状。从滤波器的形状可以看到实部为一个二维的低通滤波器,虚部为二维高通滤波器。

1.2 二维Gabor变换及特征提取

实部变换:

虚部变换:

其中:“*”代表卷积,I(x,y)为原图像,I'(x,y)为滤波后的图像。由于滤波后的图像包括很多直流分量,为了使零点的位置更加具有代表性,需要按照式(4)去掉直流分量。

其中:K(x,y)为去掉直流分量的结果,I'(x,y)代表滤波后图像的均值。图2为图像中某一行部分数据经过虚部滤波后并去掉直流分量的结果。

由图3(a)所示对于2D Gabor实部而言,相当于一个二维的高斯平滑滤波器,对滤波后的图像计算过零点位置,相当于纹理中阶越部分。图3(a)描述了对采集后的虹膜图像增强后提取实部过零点位置图,从图中可以明显看到实部过零点位置对应于虹膜纹理边界处。图3(b)所示对于2D Gabor虚部而言,相当于一个计算梯度的滤波器,对滤波后的图像计算过零点位置,相当于纹理中极值部分。图3(b)描述了对采集后的虹膜图像增强后提取虚部过零点位置图,从图中可以明显看到虚部零点位置对应于虹膜纹理极值点处。其中对虹膜图像进行增强的主要目的是为了更清晰的观察零点所表示的特征信息,实际过程并不包括增强的过程。

2 成像规律与移位设计

2.1 成像规律

通常情况下,由于采集过程中头部的轻微旋转会导致归一化的虹膜纹理的位置发生移位,但是,针对具有不同光源的采集设备来说,头部旋转造成的虹膜纹理位置的偏移规律是相同的,均匀的。然而从图4和图5可以发现:不同采集设备零点位置移位规律不同,对于具有四个光源的采集设备零点的移位比较均匀。针对具有两个光源的采集设备,过零点位置(如图5所示)在区域A,C偏移比较大,而在区域B,D的偏移比较小,这是由于在采集虹膜的过程中当距摄像头距离发生改变时,区域A,B,C,D所接受的光照强度不是按照等比例的变化,其中区域A和区域C光照变化程度比区域B和区域D大,因此也不同程度的造成过零点信息的变化。因此采集设备的光源也是造成虹膜纹理的位置发生偏移的另一原因。

图4为在具有四个光源的采集设备上,同一个人采集的两个虹膜图像提取虚部过零点后图像的叠加,图5为在具有两个光源的采集设备上,同一个人采集的两个虹膜图像提取虚部过零点后图像的叠加。通过图中所叠加的过零点位置可以看到过零点位置发生一定程度的偏移。

当同一个人采集两次虹膜图像时,人眼和采集装置之间的距离必定会发生前后移位,使得虹膜采集装置的左右光源对虹膜的光照角度发生变化,导致虹膜成像发生偏移。在归一化的虹膜图像上,这种偏移的变化规律不同区域并不一致。

对于呈近似同心圆的虹膜区域,虹膜纹理的分布主要在径向方向上。在实际的识别系统中,前后两次采集的虹膜图像,人眼与采集设备的距离都会有所偏差。当光源的方向与虹膜纹理的方向相同时,两次采集的虹膜纹理的成像方向不会发生改变;当光源的方向与虹膜纹理的方向有夹角时,两次采集的虹膜纹理的成像方向也会随之变化。当所夹的锐角越小时,两次采集的虹膜纹理的成像方向的变化就越小,此时的矩形虹膜纹理的成像的偏移程度就越小;反之,当所夹角的锐角越大时,两次采集的虹膜纹理的成像方向的变化就越大,对应的矩形虹膜纹理的成像的偏移程度就越大。由此可知,当虹膜纹理与光源成90°时两次采集的虹膜纹理的成像方向变化最大,矩形虹膜纹理的成像的偏移程度最大。

2.2 分段移位匹配

由于实验室现有的采集设备不能定量的调节光源强度以及采集图像时的偏转程度,以及光照对纹理影响的复杂度比较大,因此不能定量的分析由于这些原因导致纹理变化的程度。为了有效的克服这种偏移,本文提出了一种分段移位匹配算法。假设待匹配的两幅图像为I1(x,y)与I2(x,y),其对应的零点特征矩阵为W1与W2,针对W1与W2以行为单位分别按照如图6所示的流程计算距离。

1)提取该行零点信息

本文采用论文第2部分所提到的二维Gabor变换提取零点位置信息,最终保存的结果为一个零点的特征矩阵,该矩阵有1和0组成,如果对应位置存在零点那么该位置的值为1,如果对应位置不存在零点那么该点的值为0。

2)分段保存零点索引值

针对本文采用的虹膜图像采集设备,将提取该行的零点位置信息分为四部分,并转换为索引值。过程如图7所示。图中零点位置信息中编码为1表示该位置存在零点,编码为0表示该位置不存在零点。位置索引值表中值表示零点所在的位置,例如6表示在第6个像素处存在零点。

3)计算每段的移位相异度

假设待匹配的两行A与B零点编码段位αi(i=1,2,…,m),βi(i=1,2,…,n),其中m,n表示零点的个数,该段的相异度计算过程如图7所示。通常情况下待匹配的两段零点个数不相同,不妨设m>n,对应图8中第一行零点的信息为αi(i=1,2,…,m)第二行零点的信息为βi(i=1,2,…,n),其中θ表示移位的边界阈值,该值的确定依赖于移位的最大限度(以像素为单位),一般该值小于移位的最大限度。本文实验选择该值为3。

相异度d的计算公式为

其中:abs为计算绝对值,ai(i=1,2,…,N)为编码αi与编码βi相重叠中A的部分,bi(i=1,2,…,N)为编码αi与编码βi相重叠中B的部分,N为重叠部分码的个数。

每段移位的相异度dj计算公式为

其中:di为每次移位后的相异度,k为移位的个数。

4)计算该行的距离

针对每行,每个部分得到一个相异度值,那么该行的匹配的最终距离dis为

其中dj(j=,1,2,34)为该行每段移位的相异度。针对待匹配的两幅图像的零点信息,对每行零点特征都采用以上方法计算该行的距离,最终将所有行的距离都相加即为这两幅图像的距离。在时间速度方面,由于分段移位匹配算法在程序实现过程十分简单,没有使用复杂的相异度函数,所以计算量减少,速度大大提高。

3 实验结果与分析

3.1 类内分段移位匹配算法有效性验证

本文选择方向为0°的二维Gabor虚部滤波器进行过零点特征的提取,其中滤波器频率等参数按照文献[12,13,14]所述方法选择。为了验证本文分段移位匹配的有效性,实验选择同一个人不同光照条件下的5幅图像作为实验样本,分别编号为A11～A15。针对选择的实验图库,分别采用分段移位匹配算法,不分段的移位匹配算法,不分段、不移位的欧式距离匹配算法,计算类内距离,验证本文匹配算法的有效性。

通过实验结果可以看出:移位匹配算法得到的距离小于欧式距离匹配算法得到的距离,其主要原因在于移位匹配算法相比较而言考虑了过零点特征整体发生移位的情况;分段移位匹配算法所得到的距离明显小于移位匹配算法,其主要原因在于,移位匹配算法虽然考虑了整体零点特征的移位情况但是忽略了由于采集设备的测光影响导致零点位置不同区域不同程度的移位,分段移位匹配则根据采集设备的光源情况将过零点的特征信息分为不同区间进行移位匹配因而达到最好的类内匹配结果。

3.2 类间分段移位匹配算法有效性验证

选择5个不同眼睛的虹膜图像,在每个眼睛的样本中任选一个,分别编号为A1～A5,通过本文的分段移位匹配算法计算类间距离,其结果如表4～表6所示。

通过类间距离的实验结果可以得到三种方法得到的数据差异性不大。通过分析其主要原因是:类间过零点的位置信息本身差异性很大。通过实验结果可以看出,分段移位匹配算法类内的距离主要分布在0.12至0.21的范围内,而类间的距离主要分布在0.43至0.47之间,类内类间被很好的区分开来;移位匹配算法类内的距离主要分布在0.39至0.46的范围内,而类间的距离主要分布在0.46至0.50之间,类内类间虽然能区分开来但是距离太相近区分度不大;欧式距离匹配算法类内的距离主要分布在0.42至0.48的范围内,而类间的距离分布在0.46至0.51之间,有部分数据互相重叠,类内类间不能完全区分开来。

3.3 不同匹配算法间比较

现有用于虹膜识别系统的匹配算法很多,为了验证本文匹配算法的性能,同样采用本文的特征提取算法选择了几种常用的用于虹膜识别的匹配算法针对同一个图库做了对比实验。图库来自实验室自采集,其采集设备是近距离采集仪:北京中科模识科技有限公司的天目便携式虹膜采集仪,图像分辨率:640×480,采集距离:4∼5 cm,定位归一化后的虹膜图像为512×64,取自采集图库中40只不同虹膜,每只虹膜20幅图像,共800幅虹膜图片作为实验样本。分别采用了四种常用的虹膜匹配算法进行了对比实验,结果如表7所示。

通过实验结果可以看出本文的方法在识别率上相比于其他几种方法都有所改进,但是所花费的时间则多于Hamming距离,余弦距离和加权Hamming距离,但是花费时间的数量级比较低对整个虹膜识别系统的影响不大。

3.4 实部与虚部识别效果比较

对于本文采用的特征提取算法,分别涉及到两个滤波器:2D Gabor实部滤波器与2D Gabor虚部滤波器。采用实部滤波器提取的零点特征表示纹理的阶越信息,采用虚部滤波器的零点特征表示纹理的极值点信息,为了选择识别效果比较好的滤波器,针对不同尺寸大小的实部滤波器与虚部滤波器针对3.3部分所采用的图库分别做了对比实验结果如表8所示。

通过实验表明,在相同情况下虚部滤波器提取的过零点信息其分类效果明显好于实部滤波器提取的过零点信息。当滤波器的大小选择为17时识别率达到最佳,这是因为相对于实部滤波器而言,其N值决定对原始图像的平滑程度。N的取值越大,其平滑程度越强,相对应的零点信息越少;N的取值越小,零点信息越丰富,但是图像的抗干扰能力越弱。

4 结论

通过分析实际采集虹膜图像受侧光影响而导致零点特征位置编码发生移位的规律,本文提出一种分段移位匹配算法,该算法针对特征码在不同区间移位程度的差异性,将零点特征分为划分一定数量的区间,采用移位的方法进行匹配。通过不同匹配算法间的比较验证该方法能够很好的克服这种移位,具有实用性强,稳定性高的特点。当虹膜识别系统的采集设备具有类似光源特点时,均可以采用本文的方法进行匹配,从而降低同一个虹膜不同次成像纹理偏移的特征匹配相异度。

摘要：对于某些虹膜成像装置,同一个虹膜不同次成像的虹膜纹理可能会发生偏移,这种偏移有可能导致虹膜特征编码的偏移,从而直接影响虹膜的特征匹配结果。本文通过对归一化虹膜图像中导致虹膜纹理偏移的影响因素进行了分析,发现这种偏移是有规律的,并针对这种变化规律,提出了一种特征编码分段移位匹配的方法。实验结果表明,本文所提出的方法能够显著降低同一个虹膜不同次成像纹理偏移的特征匹配相异度。