空间数据匹配（精选八篇）
空间数据匹配 篇1
模式匹配[1,2](schema matching)是模式的基本操作之一,它的功能是轴入两个模式,找出它们的相关元素间的匹配关系,然后输出两个模式的元紊间的映射关系(mapping)。模式匹配广泛用于面向网络的数据集成、电子商务、数据仓库、数据库设计以及网站的建设和管理等方面,但其在基于网络的地理信息集成等领城的研究与应用还较少。
模式匹配主要是依靠各领域的专家进行人工操作,有时可能运用一些图形用户界面工具,但匹配仍然是一项费时费力的工作。在许多领域,如在空间信息集成中,仍然缺少能自动地将两个结构和语义上存在异构的GML应用棋式进行匹配的算法。
本文设计完成了一个GML模式匹配器的原型系统,满足了后续GML空间数据集成的需求。
本文以下部分安排如下:第二部分介绍模式匹配的相关技术;第三部分介绍GML匹配器原型系统框架;第四部分详细介绍GML模式匹配器的模块设计;第五部分给出实验和例子;第六部分为总结。
1 相关技术
模式匹配就是用匹配的算法生成相应的模式匹配器,得出相应的映射关系。
对于匹配的方式而言,一共有这么三种:单一的匹配方式,混合的匹配方式和复合的匹配方式。
单一的匹配方式仅仅只有一个标准,很难精确的得到匹配结果,混合的匹配方式由于标准选取的多样性,比采用多种单一的匹配方式更加精确和高效,这是因为各种标准综合加权考虑会减少在最初匹配过程中无谓的元素删除。
相对于混合的匹配方式,复合的匹配方式则更加灵活多变,因为复合匹配是根据实时的、当前要匹配的模式元素分标准进行匹配,更加具有针对性。
2 GML模式匹配器系统框架
GML模式匹配系统主要分为两个部分:GML模式生成树的建立模块和GML模式相似度计算的模块,如图1所示。
3 GML模式匹配器
3.1 建立GML模式生成树
“包含”和“被包含”是GML模式中常见的两种关系,但这会在计算结构相似度是出现问题,产生一些歧义。上下文间的关系在GML模式中显得尤为重要,尤其是在我们计算结构相似度时体现的更为明显。因此,在计算结构相似度的时候,上下文关系是必须要作为参考的,这时,仅仅对GML模式文件直接解析计算相似度就是行不通的事情了,这就需要我们将GML模式文件转换为一个不会产生歧义的结构或者文件,通常,树状结构是一种不会产生歧义的结构,这里采用GML模式树来表示GML模式,并且用它来计算结构相似度。算法如下[9]:
3.2 GML相似度计算(模式匹配)
GML相似度计算算法,其首要要考虑的是叶节点:对于两个节点中有任意一个是叶节点的匹配,其匹配关系我们就以前面所得的语义相似度为准。如果都非叶节点,通过比较两个节点的所有的子节点,得出所有子节点相似度,即所有的子节点的相似度加起来再和所有的子节点总数之比。此时,这两元素之间的相似度,就是它们的语义相似度以及所有叶节点相似度加权之后求和得出的最终相似度系数。而权值根据语义或者结构的偏重性来进行选取。算法如下[9]:
设置叶节点结构相似度
按公式加权计算出它们的相似度
相似度大于阈值就可进行匹配
生成匹配映射关系
返回mapping
算法结束
Output:匹配结果,即相似度
根据算法进行匹配后,我们得到的结果是两个元素间的映射关系。由于应用用户所定义的应用GML模式各不相同,对基于GML模式提取出来的本体实行匹配时产生一对多或多对一的匹配关系,这样就需要在匹配的后期处理工作中对产生的匹配映射进行校正和增删,并按照用户的要求和实际中的应用需要进行回馈和修改。
4 实验
本文使用2个GML模式文件来进行模式匹配实验:city1和city2,是两个相同地理实体所对应的各自的应用模式,区别只是在语义和结构上。首先,生成各自的GML模式树,转换后的模式树分别如图2和图3所示。
再通过相似度计算(模式匹配)得到的相似度结果显示给用户,如图4所示。
5 结论
本文设计和实现了支持空间数据集成的GML模式匹配器系统,并通过实验进行了验证。在匹配器设计过程中,我们首先建立GML的模式树,然后分别计算其语义和结构结构相似度,最后加权得出最终的相似度,完成匹配工作。
参考文献
[1]Geography Markup Language(GML)[EB/OL].http://opengis.net gml/01-029 GML2.html.
[2]Madhavan J,Bernstein P A,Rahm E.Generic Schema Matching with Cupid[C]//The27th VLDB Conference,Rome,2001.
[3]Rahm E,Bernstein P A.A Survey of Approaches to Automatic Schema Matching[J].The VLDB Journa1,2001(10):334-350.
[4]Doan A H,Domingos P,Levy A.Learning Source Descriptions for Data Integration[C]//Proc.WebDB Workshop,2000.
[5]Pottinger R A,Bernstein P A.Creating a Mediated Sct1ema Based on Initial Correspondences[C]//Bulletin of the IEEE Computer Society Technical Committee on Data Engineering,2002.
[6]Li W S,Clifton C.Semlnt:A Tool for Identifying Attribute Correspondences in Heterogeneous Databases Using Neural Network[J].Data and Knowledge Engineering,2000,33(1):49-84.
[7]Reynaud C,Sirot J P,Vodislav D.Semantic Integration of XML Heterogeneous Data Sources[C]//International Database Engineering&Ap plications Symposium(IDEAS'01),2001.
[8]Guan J H,Zhou S G,Chen J P,et a1.Ontology-based GML Schema Matching for Information Integration[C]//ICMLC’03,Xi’an,2003.
空间数据匹配 篇2
当契税申报表中房产性质选择的是“普通住房”和“非普通住房”时适用以下匹配规则（按顺序使用，当某条逻辑规则匹配到小区后，不再使用排在后面的规则，筛选结果排除只有商业、工业物业类型的小区，将最终结果作为候选列表显示）：
第1步：契税申报表上的“小区名称+幢号”依次和小区表的小区名、别名
1、别名
2、别名2 模糊匹配（前者名称词组包含在后者名称中），第2步：契税申报表上的“小区名称”依次和小区表的小区名、别名
1、别名
2、别名3完全匹配 第3步：契税申报表上的“所在道路+门牌号”和小区表的路名（坐落地址）完全匹配
第4步：契税申报表上的“小区名称”依次和小区表的小区名、别名
1、别名
2、别名3模糊匹配 第5步：契税申报表上的“所在道路”和小区表的小区名称、别名完全匹配
第6步：小区名前三个字与小区名、别名模糊匹配（小区名、别名都要匹配），第7步：契税申报表上的“所在道路”和片区表的“片区名称”、“区域内街巷名称1-20”完全匹配 注： “筛选结果排除只有商业、工业物业类型的小区，将最终结果作为候选列表显示”，即没有住宅物业类型的小区不予显示列表。
*非住宅匹配逻辑（2014.3.5修改）
当契税申报表房产性质选择“非住宅”时适用以下匹配规则（按顺序使用，当某条逻辑规则匹配到小区后，不再使用排在后面的规则，筛选结果排除只有住宅物业类型的小区，将最终结果作为候选列表显示）：
1.契税申报表“小区名称”+“栋号”依次和系统小区表（001、012、026表）的小区名称、别名
1、别名
2、别名3模糊匹配（前者名称词组包含在后者名称中）
2、契税申报表“小区名称”同系统小区表的“区段名称（小区名称）、别名
1、别名
2、别名3”进行模糊匹配（前者名称词组包含在后者名称中）。
3、契税申报表所在道路依次于小区表的路名、别名
一、别名
二、别名三完全匹配, 契税申报表如果填写了门牌号码则门牌号码必须在范围内。
4、契税申报表“所在道路”依次于小区表的路名、别名
一、别名
二、别名三模糊匹配,如果填写了门牌号码则门牌号码必须在范围内。
空间数据匹配 篇3
随着车辆的增多,道路交通安全问题日趋严峻,从而促进了智能交通系统(Intelligent Transportation System,简称ITS)的发展。ITS是指运用信息技术、数据通讯传输技术、电子传感技术、控制技术、计算机技术等对道路交通进行实时、准确、高效的监管和处理。交通标志是管理交通、指示行车方向、保证道路畅通与行车安全的必要设施,因此大力开发交通标志识别系统已然成为了一个重要的发展方向,其中交通标志的检测是交通标志识别系统的重要基础。
本文对交通标志检测现状进行了分析,并在颜色分割的基础上利用模板匹配的方法实现了交通标志的检测。
1 研究现状
自上世纪八十年代开始,国外就有科研工作者开展交通标志检测技术的研究。Akatsuka等人釆用在RGB颜色空间图像下对图像进行阈值分割的方式检测交通标志,并通过模板匹配的方法对限速标志设计分类[1]。Broggi等人提出了一种RGB模型改进法来保证分割效果,通过类似于线性gamma矫正的彩色均衡处理来保证RGB模型对光源的独立性[2]。大阪大学开发了利用摄像机拍摄远处的场景图像,经过颜色、强度和形状等信息处理和判断得到可能的交通标志区域,再采用模板匹配法识别此区域的系统。Green等人在归一化的RGB空间中选取R和B通道的最大值以及结合RGB图像提取MSER区域并利用SVM进行交通标志判断[3]。Miura等人通过一个内建函数来计算标准模板图像与候选交通标志图像之间的归一化相关性,相比直接使用归一化相关性的模板匹配算法,该算法具有较快的处理速度[4]。
我国在智能交通领域的研发进展比国外稍晚。2004年杭州大学蒋刚毅通过利用数学形态学方法提取交通标志的特征,再利用模板匹配算法来进行检测[5]。许少秋等人也釆用基于模板匹配的算法来对交通标志提供检测识别,再通过HSI颜色空间对图像进行分割。张静等人[6]将图像从RGB颜色空间转换到HSI颜色空间来优势提取颜色分割,同时进一步结合了对RGB颜色空间下的非彩色分割。沙莎等人[7]首先将图像转换到HSI颜色空间,对其饱和度定制实现阈值分割,再结合RGB通道的颜色特征进行颜色聚类,从而将交通标志从背景图像中分离出来。
2 交通标志检测算法
2.1 颜色空间处理
2.1.1 RGB颜色空间
RGB空间是目前具有最大可见广泛应用范围的功能系统。具体分为红(Red)、绿(Green)、蓝(Blue)3个颜色通道,通过3个通道值的变化及叠加,产生各种各样几乎可以囊括人类所能感知到的全部颜色。建立在笛卡尔坐标系统中的RGB颜色模型空间,是一个正方体,如图1所示。一般应用时,将其归一化为单位立方体,使得所有的R、G、B值均可定位在区间[0,l]之中,成为一个规格化的RGB彩色空间。
基于RGB颜色空间模型的标志图像检测算法主要原理为:首先按照交通标志的颜色特点,设定分割像素点的RGB阈值,然后对图像中的像素点选取逐行扫描模式,判断图像中的该像素点是否属于预先设定的RGB阈值范围内,如果属于,则将该像素点保留下来,反之则设为零,该像素点为背景。
若k1为图像中的交通标志,k2为图像的背景,fr、fg、fb分别为图像中各像素点的R、G、B通道值,运用(1)(2)两式对图像进行处理。具体如下:
对RGB空间的处理,首先获取图像的R、G、B的像素值,之后通过实验来确定交通标志图像中的红、黄、蓝三种颜色的R-B、B-R、R-G、G-R、B-G和G-B的分割阈值的范围,再将符合分割阈值范围的区域进行保留,不满足的区域则将其设为白色,最后合成RGB颜色像素,分割后的图像如图2所示。
2.1.2 HSV颜色空间
HSV(Hue,Saturation,Value)颜色空间模型中包含的3个独立属性是:亮度、色调和饱和度,其中,H是图像的色度也称色调,V是色彩的亮度,S是色彩的饱和度。HSV颜色空间的模型对应于圆柱坐标系中的一个圆锥形。如图3所示。圆锥的顶面对应V=l。色彩H由绕V轴的旋转角决定。每一种颜色和其补色之间相差180°。红色对应角度0°,绿色对应角度120°,蓝色对应角度240°。
HSV颜色模型是建立在柱坐标系中的。将RGB颜色空间转化为HSV颜色空间的算法为:利用方程式展开将RGB空间转换为HSV空间,即把笛卡尔坐标系中的RGB值映射至柱坐标系。转换后对图像中的像素点选取逐行扫描模式,判断图像中的该像素点是否属于预先设定的HSV阈值范围内,如果属于,则将该像素点保留下来。算法中涉及处理的公式如下:
H通道:
S通道:
V通道:
对于HSV空间的处理,首先获取图像的R、G、B的像素值,再将图像的RGB颜色转化为HSV的颜色值,之后通过实验来确定交通标志图像中的红、黄、蓝3种颜色H、S、V的分割阈值范围,对于符合分割阈值范围的区域进行保留,不满足的区域则将其设为白色,最后将HSV颜色转换成RGB颜色,合成像素后,显示分割后的图像,如图4所示。
2.2 模板匹配
模板匹配就是在一幅较大图像中搜索目标,已知图中含有要寻找的目标,而且该目标与模板有着相同的方向、尺寸。运行算法可以在图像中寻找到目标,确定目标的坐标位置。通过比较模板与子图的相似性,可以完成模板匹配的过程。
在此,给出模板匹配公式如下:
将模板T(m×n个像素)叠放在被搜索图S(W×H个像素)上下平移,模板覆盖搜索图的相应区域块称作子图Sij。i和j是子图Sij左上角在搜索图S上的坐标。如图5所示,通过比较T与Sij的相似性,可以完成模板匹配的过程。
当模板和子图完全一样时,相关系数R(i,j)=1。在被搜索图S中完成全部搜索后,找出R的最大值Rmax(im,jm),其对应的子图Simjm即为匹配目标。研究可得,误差公式如下:
E(i,j)为最小值处即为匹配目标。
为提高计算速度,取一个误差阈值E0,当E(i,j)>E0时就停止该点的计算,继续下一点计算,从而得到想要的结果。
3 实验结果
3.1 数据库
在我国迄今仍未推出公开的数据库用于提供给学者们展开相关的研究。本文通过车载相机拍摄的方式创建了一个含有交通标志图像的数据库。测试时,仅针对数据库中的150张禁止标志进行仿真实验。图6是数据库中含有禁止标志的一部分图像。
3.2 仿真实验
在RGB和HSV颜色空间的基础上,利用相似性公式对已经准备好的模板图像和分割后的图像进行匹配运算,计算出Rmax,从而找到最相似的ROI,完成交通标志的检测。对数据库中的150张禁止标志图像进行仿真实验,检测结果如图7所示。
实验结果表明,本系统能够取得较好的检测效果,检测准确率为96.67%。
4 结束语
本文对交通标志检测与识别系统中的交通标志颜色粗分割算法、候选交通标志图像块提取、交通标志模板匹配分类方法给出了相关研究,并展示了仿真实验过程及结果。本文的主要工作及结论如下:
1)本文介绍并分析了以RGB颜色模型及其确定阈值的粗分割算法和HSV颜色模型及其固定阈值的粗分割算法。
2)基于模板匹配方法的交通标志检测系统目前可以检测大量的禁止标志,对数据库中的150张禁止标志图像进行检测,检测成功率为96.67%。
本文只采用了固定大小的模板进行匹配,当交通标志出现较大变形及缩放等情况时,文中方法的检测效果较差,将在下一步工作中研究变形模板匹配。
参考文献
[1]余进程.车载辅助系统中禁令交通标志的识别研究[D].广州:广东工业大学,2014.
[2]匡麒旭.城市交通存在的问题及解决方法[D].武汉:武汉理工大学,2014.
[3]YE Yibin,SQUARTIN S,PIAZZA F.ELM based time variant neural networks with incremental number of output basis functions[J].Lecture Notes in Computer Science,2011,6675:403-410.
[4]NASCIMENTO J C,ABRANTES A J,MARQUES J S.Using middle level features for robust shape tracking[J].Pattern Recognition Letters,2003,24(1/3):295-307.
[5]陈荣波.智能交通系统理论的研究与实现[D].长春:吉林大学,2004.
[6]张静,何明一,戴玉超,等.多特征融合的圆形交通标志检测[J].模式识别与人工智能,2011,24(2):226-232.
空间数据匹配 篇4
在许多信号处理与电话语音传输系统中,信号发生部分丢失是不可避免的[1]。文献[1,2,3]等基于不同假设和应用场景提出了相应的数据恢复方法。在这些方法中,假定信号是一个冗余框架上的表示系数,通过利用框架的冗余性对发生擦除的信号进行恢复并取得了较好的实验结果。这些方法同样也可应用于信号降噪[4]。另一类方法通过实现擦除信号的稀疏表示来对原始信号进行恢复,如正交匹配追踪(Orthogonal Match Pursuit,OMP)[5]、基追踪(Basis Pursuit,BP)和l1最小范等[6]。且有实验表明当信号满足一定的稀疏条件时能够获得很好的恢复性能[6]。文献[7,8]提出一种基于自适应的稀疏恢复方法,此方法用于估计图像信号的丢失部分。总地来说,上述所有方法皆基于一个基础的假设,即信号是稀疏的。依据压缩感知的理论[9,10,11],信号的稀疏性在许多研究领域中起着基础作用,例如:音视频信号、图像信号、雷达信号等。
信号的稀疏性通常采用两种度量模式:信号表示基的正确度和恢复误差。在不同的度量模式下,不同的方法具有不同的性能表现。例如以信号表示基的正确度为度量时,OMP方法能够取得较好的效果;以信号恢复误差为度量时,BP方法会取得较好的效果。然而,就擦除部分恢复问题而言,只考虑单一度量标准的恢复性能显然是不全面的。为此,在同时兼顾两种稀疏约束条件下,提出了一种基于信号稀疏特征的重要子空间数据恢复方法。所提出的方法分为两个步骤:
(1)利用OMP算法和信号的剩余部分恢复出信号子空间中基;
(2)提出一个迭代方程,求出满足稀疏条件的近似信号。
相对于OMP和BP方法而言,所提出的方法既利用了OMP方法能够准确确定信号重要子空间的优点,又可在兼顾满足稀疏约束的条件下,寻求得到满足恢复残差最小的近似解,并将其作为近似信号。
1 信号稀疏恢复的基本框架
1.1 信号的稀疏表示
假定信号x是稀疏的,这意味着在不会导致较大感知损失的情况下,邀ci妖中较小的系数可以被舍弃,则信号x可近似表示为:
其中,PS和PI分别为子空间VS和VI的下次投影算子。信号的稀疏重构xS和相应的重构误差eS可表示为:
下面,分别采用信号表示基的正确度和恢复误差两种模式来度量信号的稀疏性:
1.2 擦除恢复
依据信号的擦除方式,信号x可以被表示为
由于xa是已知的,如果xS'被很好地近似,则也就相应地得到了xe的补偿。因此,解决擦除补偿问题依赖于对xS'的近似。依据式(9),信号x在非重要子空间中的表示满足:
在满足式(12)情况下,对信号x的近似可通过以下迭代方程得到:
其中,D=PePS,其初始值为x 0=xa。式(13)的证明如下:
(1)Pe和PS都是压缩算子,则迭代方程式(13)中的D也是一个压缩算子,因此迭代方程会收敛于唯一固定点,即迭代方程有唯一解。
(2)假定x觹是此迭代方程的解,即:
注意xa=Pax觹,Pa+Pe=I和PS+PI=I,于是可得到:
2 基于OMP的重要基向量的选择
在第1节中讨论了擦除补偿问题,通过对信号的重要子空间基向量的选择,此问题可以通过式(13)解决。而在本部分中,基于OMP算法,提出一种重要子空间基向量的选择方法。该方法的目标不是为了获得信号在基上的最稀疏表示,而是为了选择信号重要子空间的基向量。重要子空间基向量的选择方法如下:
算法1:基于OMP方法寻找重要子空间
输入:
稀疏度为λ-sparse的被擦除信号x
输出:
算法过程:
(3)将被选中的索引imax加入到集合∧中
(4)计算新的基向量uk
(5)计算残差rk+1
(6)重复过程(2)~(5),直到如下条件成立
(7)输出集合∧
依据算法1中得到的索引集∧,可获得一组基向量并以其构造信号重要子空间VS,同时满足。进一步地,可以构造此空间的正交投影算子PS,将其用于公式(13)中。尽管算法1经过有限次的迭代后最终会收敛,但算法的目标并不是寻找信号有效部分的近似,而是为选择其所在的重要子空间。当满足限定的误差条件时,算法将会结束,此时表示已经找到了信号的重要子空间向量。
3 实验结果与结论分析
下面通过实验来评估所提出方法的有效性。使用离散余弦变换(discrete cosine transformation,DCT)基向量来表示信号,并假设信号在此基上具有一个稀疏的表示。图1显示了运用所提出方法进行信号补偿的实验结果。一个长为120采样点、稀疏度为A(0.13,0.05)-sparse的输入信号以虚线绘制在图1中,并随机擦除其中的50个以方框标记的采样点。通过算法1从DCT基中选择重要子空间的基向量,并构造其正交投影算子。使用式(13)获得的信号擦除补偿结果以实线绘制在图1中。
此外,具有不同稀疏度的5个信号,每个信号的长度均包含120个采样点,图2显示了以信号擦除恢复的错误率作为信号擦除率的函数的实验结果。实验结果表明:随着擦除率的增加,信号恢复的错误率也随之增加;具有较好的稀疏性的信号(即α和β均具有较小的值),其恢复效果也较好。特别地,具有稀疏度为(0.13,0.07)和(0.13,0.05)的两个信号即使在擦除率达60%时,依然取得了较好的恢复效果。上述实验结果显示了所提出的方法能够较好地适用于信号擦除的补偿。
4 结束语
本文提出了一种基于信号稀疏性的擦除恢复方法。算法中,同时考虑到信号表示基的正确度和恢复误差作为信号稀疏性的度量。针对基于正交子空间的信号表示,完整地给出了信号的稀疏表示和擦除表示方法。对于信号擦除恢复问题,提出了基于重要子空间的信号恢复方法,该方法依赖于信号重要子空间的选择。因此,为根据擦除信号的可用部分来选择其重要的子空间,又提出一种基于OMP的重要子空间选择方法。最后,对所提出的方法进行了实验验证,实验结果表明发生擦除的信号可以通过文中所提出的方法进行恢复。
参考文献
[1]BOUFOUNOS P,OPPENHEIM A V,GOYAL V K.Causal co-mpensation for erasures in frame representations[J].IEEE Tra-nsactions on Signal Processing,2008,56(3):1071-1082.
[2]BERNARDINI R,RINALDO R.Efficient reconstruction fromframebased multiple descriptions[J].IEEE Transactions on Sig-nal Processing,2005,53(8):3282-3296.
[3]RATH G,GUILLEMOT C.Frame-theoretic analysis of DFT c-odes with erasures[J].IEEE Transactions on Signal Processing,2004,52(2):447-460.
[4]YU Guoshen,MALLAT S,BACRY E.Audio denoising by tim-e-frequency block thresholding[J].IEEE Transactions on Sig-nal Processing,2008,56(5):1830-1839.
[5]TROPP J,GILBERT A C.Signal recovery from random meas-urements via orthogonal matching pursuit[J].IEEE Transactionson Information Theory,2007,53(12):4655-4666.
[6]CANDS E J,ROMBERG J,TAO T.Robust uncertainty pri-nciples:exact signal reconstruction from highly incomplete fre-quency information[J].IEEE Transactions on Information Theo-ry,2006,52(2):489-509.
[7]GULERYUZ O G.Nonlinear approximation based image reco-very using adaptive sparse reconstructions and iterated denois-ing-part I:theory[J].IEEE Transactions on Image Processing,2006,15,(3):539-554.
[8]GULERYUZ O G.Nonlinear approximation based image recov-ery using adaptive sparse reconstructions and iterated denoisi-ng-part II:adaptive algorithms[J].IEEE Transactions on Imag-ge Processing,2006,15(3):555-571.
[9]CANDS E J,WAKIN M B.An introduction to compressivesampling[J].IEEE Signal Processing Magazine,2008,25(2):21-30.
[10]CANDS E J.Compressive sampling[J].International Congressof Mathematics,2006(3):1433-1452.
空间数据匹配 篇5
针对我国的计算机信息技术中,图像匹配算法存在图像特征过度分离的问题,研究优化当前的图像匹配算法,不仅有助于精确匹配图像中的特征点,也可提升图像检测率。本文将介绍基于曲率尺度空间的角点检测图像匹配算法,分析其原理及相关算法优化方法。该角点检测图像匹配算法已在实践中得到了应用验证。
1 角点检测与图像匹配概念
1.1 角点检测的概念
在图像匹配检测过程中,图像角点也被称作兴趣点,也就是在图像的像素点中,其相较于图像邻域各个方向中的灰度变化量大,或者是大于阈值的点[1]。掌握图像的轮廓特征很有必要,因为找到图像特征就可以掌握图像中物体的形状。角点不仅包含图像中的二维结构信息,同时,在处理图像匹配中,也可以应用角点检测技术,实现对图像匹配的处理[2,3]。角点所代表的局部结构关系信息,不会因为视角的不同而改变图像轮廓上曲率的局部极大点作为角点[4]。而对于角点检测的原理,则是在给定的模板以及图像中,找出图像所有区域中的相关性与相似性的点[5]。实现角点检测,最大的应用优点就是,具有图像旋转不变性,不会因为图像旋转形态而改变检测精度,也不易受到外界光照条件的影响,提升应用价值。
1.2 图像匹配
在计算机的图像匹配算法之中,在两幅图像匹配以及多幅图像匹配过程之中,通过图像匹配算法,就识别出在图像中存在的同名点,并进行图像匹配[6,7]。在图像匹配中,当实时图像大于基准图像时,图像的匹配过程则是基于实时图像寻找基准图像目标的过程。例如在地图系统的图像匹配中,基准图像比实时图像大,如图1所示。
图像匹配时,可以根据图像的颜色、纹理以及形状等[8]提取图像中的高层次特征,并建立不同匹配图像之间对应的匹配关系。基准图像与实时图像之间的关系中,应用高斯白噪声表示dx(x,y),dx(x,y)、dy(x,y)表示图像特征点在X和Y方向位置的偏差,其关系如下:
2 基于曲率尺度空间的角点检测算法
2.1 角点检测Harris算法
角点检测Harris算法改进了Moravec方法的自相关矩阵[9],可以在图像的检测匹配窗口中,通过高斯函数加权导数,有效避免图像中特征点离散与偏移情况的发生,取代对图像处理中的简单求和算法,优化算法精度。图2是Harris角点检测算法的示意图。
在该算法之中,可以根据角点检测图像窗口的平移,分析图像[u,v]位置的灰度变化:
展开图像的灰度函数Taylor:
之后去掉图像的高阶小量,得出:
基于该方法的角点检测图像匹配中,若是匹配图像的尺寸发生变化,则算法对此产生的变化比较敏感,如图3所示,左图中是图像匹配中的边缘信息,右图是在缩小图片后匹配得出的角点信息。
2.2 SIFT方法
基于不变量技术和尺度空间的图像局部特征描述算子,即尺度不变特征变换,可以建立高斯差分(DOG)尺度空间,得出高斯核函数为:
以(x,y)表示图像平面中的坐标,σ是尺度参数。令I(x,y)表示一张图像,则图像的尺度空间可以表示为:
由热传导方程,可得:
在图像匹配中,高斯差分函数会强烈响应,在计算极值点位置中,可以计算Hessian矩阵获得图片匹配精度。
2.3 CSS算法
定义CSS角点:边缘轮廓上的曲率极大值点。细节尺度上(Fine Scale),定位性好,噪声多;粗糙尺度上(Coarse Sclae),定位性差,噪声少。将曲线用弧长参数u表达为:
在最高的尺度上计算边缘轮廓的曲率绝对值,并选择局部极大值点作为角点候选点,满足:
(1)大于阈值t(去除圆形角和噪声);
(2)至少两倍于两侧相邻的某个曲率极小值点。
跟踪角点到最低(细)的尺度上以获得更好的位置精度,对于在高尺度上检测到的极大值点,在其低一级尺度的邻域搜索极大值点;如此,向更低的尺度进行跟踪,直到最低的尺度。
还可以将多个尺度下的特征融合在一起,随着尺度的增大,轮廓噪声被逐步减弱,从而曲率积逐步变小,曲率极大值对应的点可逐渐锐化,通过阈值化即可得到角点[10,11]。但是,在小尺度下的一些角点可能随着尺度的增大,曲率变得很小,从而曲率积也很小,这类角点就可能将被作为假角点滤除。
3 曲率尺度空间下优化设计角点检测图像匹配算法
3.1 特征点提取
在角点检测的图像匹配算法中,由于实际图像中的噪声高、对比度低,可以采用基于曲率尺度空间下的角点检测CSS算法,提取图像的边缘信息,以保留较多的图像特征信息;再对边缘长度进行判断,剔除长度较短的边缘[12]。可以利用CSS算法中的边缘检测方法,通过检测算子从原始需匹配图像之中提取出图像的边缘,然后从匹配边缘图像中填充图像边缘轮廓中的缺口,并寻找出在图像匹配交叉点中的角点信息。在最高尺度上计算曲率并确定角点的候选点(绝对曲率的极大值点);能够在图像匹配大尺度下来计算曲率,从而选择一个绝对曲率大的候选角点,并跟踪这个角点的小尺度信息,以提高角点检测图像匹配定位的精度。部分算法实现的代码如下所示:
3.2 生成特征向量
基于曲率尺度空间的角点检测图像匹配算法可以对互相连接的图像以及互相遮挡图像中的多候选特征区域,分离处理这些图像特征点信息,并且也可以有效避免应用分离算法加大对整幅图像匹配的计算开销,保证图像匹配时间符合实际需求,同时降低计算开销。提高图像匹配算法中角点检测构造中应用描述符的鲁棒性,确保图像的描述符保持旋转不变性,可以先确定该描述符的主方向,保证图像匹配中特征点向量可以保持旋转不变的特性,这样在图像旋转之后,可以依据图像的特征向量,而不会发生图像位置变化导致图像匹配精度降低的情况出现。如果图像匹配中,图像的特征描述符已经具有了很好的抗图像旋转匹配检测计算能力,则没有必要为图像的特征点分配一个主方向,也可以省去针对旋转图像匹配的转化,大大降低角点检测中图像匹配算法的计算复杂度,有效减少该算法的运行时间。主要是在圆到定点距离中,依据其定长点集合构造特征向量,依据圆的旋转不变性,改进图像匹配算法,用改进的特征向量描述符方法生成图像匹配算法的特征向量。
3.3 图像特征的匹配
在基于曲率尺度空间的角点检测图像匹配算法中,生产两幅待检测匹配图像的特征点以及特征向量之后,就可以将特征向量作为判定两幅图像特征点相似性的度量。同时,在曲率尺度空间的角点检测算法中,可基于匹配图像形状上下文特征点,确保特征点描述中包括有效的图像邻域边缘信息,有助于提升图像匹配精度。
4 算法的仿真应用
4.1 仿真基础
本文设计并优化基于曲率尺度空间的角点检测图像匹配算法,通过对提取的边缘长度进行判断,并通过仿真实验,分析检验该算法的应用有效性。采用PC作为算法仿真的硬件平台,CPU为2.8 GHz,内存为1.99 GB;同时,应用Windows XP操作系统作为仿真的软件平台,基于MATLAB2010b软件进行算法应用仿真。
4.2 仿真参数设置
仿真基于曲率尺度空间的角点检测图像匹配算法的过程中,主要对900幅路标图像进行检测匹配。设置图像匹配中特征点区域的特征矢量阈值为:
VSth={80[260,20 000][0.8,1.3]16}
而在角点检测图像匹配中,对于多个互连图像的特征点区域,其特征矢量阈值为:
VMth={80[512,25 000]{[1.4,2.3],[2.6,3.2]}16}
4.3 仿真结果
基于本算法的应用仿真中,采用TP表示图像真正数,也就是图像匹配检测结果中正确图像信息的数量;FN是图像的假负数,也就是没有被检测出的图像信息数;FP是图像的标志假正数,就是那些不需要被检测匹配的图像被匹配检测出的数量;R则是正确的检测率,也就是正确实现图像匹配数量占总数的百分率;FPPF是每幅匹配图像的平均假正率;TA是平均处理每幅图像的时间。其检测结果如表1所示。
从表1可以看出,基于曲率尺度空间的角点检测图像匹配算法的检测率相较于其他算法图像匹配精度均提高10.0%左右。并且,基于曲率尺度空间实现角点检测图像匹配算法,不仅可以精确图像匹配算法中的定位特征点,也可以有效节省提取特征点的时间。本算法优于现有的分水岭变换算法与自适应分离改进算法。
5 结论
综上所述,优化设计基于曲率尺度空间的角点检测图像匹配算法有助于实现对图像特征点的精确匹配,充分利用了特征点存在凹特性角点特性,克服了特征点过度分离的问题,整体图像匹配检测精度与现有图像匹配算法相比具有优势,适合广泛应用。
摘要：计算机技术的发展下,优化提升图像匹配算法,可以提升图像检测精度。基于曲率尺度空间的角点检测图技术,优化设计图像匹配算法,基于曲率尺度空间的角点检测算法进行图像特征点的提取,归一化处理特征点,有助于提高图像匹配精度。利用该算法最终实现图像匹配需求,验证了算法的有效性,改进了图像匹配中特征点过度分离的弊端,提高了图像匹配检测的整体精度约10.0%。该算法发挥了积极应用价值,值得在实践应用中推广。
关键词：角点检测,曲率尺度空间,图像匹配
参考文献
[1]高晶,吴育峰,吴昆,等.基于角点检测的图像匹配算法[J].仪器仪表学报,2013,34(8):1717-1725.
[2]郭鲁,魏颖.SUFT算法与改进的Harris算法相结合的图像匹配方法[J].黑龙江科技信息,2014(36):98.
[3]谢建春.基于改进Hausdorff距离的图像匹配快速算法[J].电光与控制,2012,19(8):34-37,49.
[4]王鑫,贾敏智.改进Harris-SIFT算法在水下图像匹配中的应用[J].电视技术,2014,38(13):50-53.
[5]于合龙,苏恒强,汪岩,等.SUSAN角点检测和匹配算法在高温变形测量中的应用[J].航空学报,2013,34(5):1064-1072.
[6]扈立超,史再峰,庞科,等.用于图像匹配的改进Harris特征点检测算法[J].计算机工程,2015,41(10):216-220.
[7]何艳,王沛,付杰,等.一种基于统计特性的Harris图像匹配[J].电视技术,2013,37(13):18-21.
[8]吕恒利,尚振宏,刘辉,等.基于Harris角点和SIFT算法的车辆图像匹配[J].昆明理工大学学报(自然科学版),2015(1):50-54.
[9]张官亮,邹焕新,秦先祥,等.基于改进SIFT特征和图转换匹配的图像匹配算法[J].计算机应用研究,2013,30(9):2861-2864.
[10]王鹏程,龙永新,文志强,等.一种基于边缘积分与邻域提纯的图像匹配方法[J].计算技术与自动化,2015(3):100-104.
[11]谢辉,刘浏,李建勋,等.基于局部结构特征的红外与可见光图像匹配[J].计算机工程,2012,38(15):230-233.
空间数据匹配 篇6
目前我们使用的彩色空间有R G B、Y U V、Y I Q、H I S、C I E X Y Z、C I E LAB、YCrCb等。YCrCb是由亮度Y与色差信号Cr、Cb构成,它可以通过RGB信号与一个常量矩阵相乘得到,在此我们选取YCrCb空间出于以下考虑:
1)大部分比赛,拍摄时的编码是采用的MPEG技术,由于经过MPEG1解码子系统的解码以后,首先得到的是Y’CrCb颜色空间的图像而不是RGB颜色空间的图像。如果再将Y C r C b颜色空间的图像转换到RGB颜色空间必将造成信息的损失。
2)减少计算量。用Y’C r C b颜色空间可以在两个方面减少计算量:
一方面不必进行颜色空间的转换;另一方面Cr矩阵和Cb矩阵只有Y矩阵的1/4大,相对于RGB与高质量的YUV来讲存在一定的优势。
由于在足球比赛中,成像距离远远大于被跟踪物体本身的尺度以及物体本身的尺度远远小于总的运动距离,所以我们用刚性模块(固定尺寸的象素块)为物体建模。用8*4的象素块来表示物体。物体模型如下图1.1所示:
二算法描述
2.1匹配准则的定义
首先我们给当前帧查找区域中的每一个象素位置定义一个能量函数,最佳位置就是对应能量函数最小的位置。最佳位置对应的运动向量就是物体的帧间运动向量。令Y(m,n)表示当前帧(Ft)Y分量矩阵中处于(m,n)位置的Y分量的值我们定义:Y(m,n)、Cr(m,n)t-1、Cr(m,n)t、Cb(m,n)t-1和Cb(m,n)t。位置(m,n)处的能量函数为E(m,n),其中α、β、γ分别表示为权重,M、N分别表示块的高度与宽度,方程定义为:
且的方程定义如下:
2.2运动矢量估计
运动估计的准确性依赖于在块匹配过程中所用的匹配准则。因为两个相匹配的象素块之间的失真度量(Block Distortion Measure,缩写为BDM)常常有几个谷底(最小值点),如果在前面的步骤里作出了不合适的选择就会把全局最优的运动向量排除在外。为了避免这种问题,我们通过比较最佳匹配位置的BDM跟当前阶段其它查找位置的B D M,为下一步保留多个候选。定义如下:
这里,BDMmin和BDMX分别是当前阶段最小的BDM值和第x个位置的BDM值。如果对于所有的x,Gx都接近于1,那么意味着朝当前位置寻找全局最优运动向量的方向很可能是正确的。那么下一步的查找区域应该只限于当前最小位置的邻域里。
如果一个或多个Gx接近于0,准确的查找方向就不确定,保留一个或多个候选用作下一步的查找中心。
在Gx接近于0时给定门限GT来确定是否选择某个候选。如果BDMmin大于预先设定的门限T,必须使用大的GT值(记为GT1)来不让它陷入局部最小值处;否则G T等于门限G T 0(G T 1>G T 0)。计算当前所有查找位置(即对所有的x)的Gx。如果Gx大于GT,那么选定该候选作为下一步的一个查找中心。
2.3基于预测修正的复合查找策略
根据过去运动估计的结果,在查找窗口中定义一个最可能出现的区域(子窗口),在子窗口中进行遍历查找(即测试子窗口中的每一个运动向量),得到一个最佳运动向量VE。
在整个查找窗口进行三步查找得到一个最佳运动向量VF,比较VE和VF对应的能量函数,然后确定最终的最佳运动。
2.4查找距离自适应
利用查找原点的B D M作为对块的运动进行分类的准则。按如下方式定义三种运动类型(低速运动、中速运动、以及高速运动):
1)如果BDM>T1,那么就是高速运动块;
2)如果T 2<B D M≤T 2,那么就是中速运动块;
3)如果B D M<T 2,那么就是低速运动块;
这里T1和T2是两个门限值。高速、中速和低速运动的最大位移分别设为。完成对块进行分类之后,根据相应的查找距离利用基于预测修正的复合查找策略找出物体在当前帧中的最佳位置从而给出物体的运动向量。每个图像序列的开始对T1和T2进行初始化。通过下面的四步操作完成门限T1和T2的初始设置:
1)用全搜索块匹配(FSBM)算法找出第一帧中每个块的运动向量。
2)计算每个块查找原点的BDM,并根据BDM值按降序进行排序。
3)找出位移大于w2的块数(N A)及位移大于w4的块数(N B)。
4)令T 1等于第N A个最大的B D M值,T 2等于第N B个最大的B D M值。
2.5跟踪速率自适应控制
物体的运动时慢时快,而原始数据的采样速率通常是恒定的(一般为3 0帧/秒)。在物体运动较慢的情况下,显然不必对每一帧都进行跟踪。我们提出跟踪速率的自适应控制策略来解决这一问题。利用运动估计得到的运动速率预测物体在未来帧的运动情况,从而确定是否对当前帧进行运动分析。我们定义式的函数如下:
式中Nt指当前帧(Ft)的编号(流水号),N t是最近一次被跟踪过的帧的编号,Vt是最近一次运动估计给出的物体运动速率,W是查找窗口的宽度。我们设置一个阈值,当Mt大于阈值时就对当前帧(Ft)进行运动分析,否则跳个过当前帧。
三实验结果
实验数据由一个图像序列组成,该序列是一段足球比赛实况,由130帧385×285的图像组成,图一到图四分别是其中某的一帧图像。
图一所示是跟踪足球运动员运动的实验结果,其中位于“□”内的运动员是被跟踪的对象。首先通过单击鼠标指定被跟踪的物体,从第28帧开始进行运动估计,从而跟踪运动的物体(运动员)。图3.1、图3.2、图3.3、图3.4分别对应于第28帧、38帧、58帧、78帧的运动跟踪结果。
从实验结果看,在复杂的环境下(背景比较复杂,灯光不强)动态跟踪的效果比较理想。
四讨论和总结
从整个实验的结果来看,该方法对背景、光照等环境条件的依赖不强,我们可以不作任何修改而直接把它用于其它领域。比如军事领域的多目标跟踪,以及球类比赛中对运动员或者球的实时跟踪等。
需要解决的问题包括摄像机的标定、遮挡处理以及运动解释(即根据运动估计得出的运动信息并结合实际应用的背景对物体的运动进行分析、总结)。
参考文献
[1].S.LakshmananandH.Grimmer“,Detecting straightedgesinradarimageusing deformabletemplates”,IEEETrans.PAMI,1996.
[2].A.L.Yuille,P.W.HallinanandD.S.Cohen“,Featureextractionfromfacesusing deformabletemplates”,IJCV,Vol.8,No.2,133-144.1992.
[3].L.H.Staib,andJ.S.Duncan“,Boundary findingwithparametricallydeformablemodels”,IEEETrans.PAMI,Vol.14,No.11,pp.1,061-1075,Nov.1994.
[4].唐建雄“,基于机器视觉的人运动检测HumanMotionDetectionBasedonMachineVision”,现代电子技术Modern Electronics Technique
[5].李远刚;蒋咏梅.“基于肤色特征的人脸检测算法”.中国临床康复.2007
[6].陈忠碧,张启衡“.基于块估计的运动目标检测方法”.光电工程.June,2006
海量数据过滤系统中匹配算法的研究 篇7
关键词：海量数据,过滤系统,AC-BM算法,AC多模式匹配
随着网络技术的迅猛发展,网络违法犯罪行为与日俱增。不法分子常常利用互联网进行一些违法犯罪活动,如传播色情信息、暴力信息和反动信息等,这些行为会严重扰乱社会次序,给人们的日常生活带来极大危害[1]。因此,如何有效剔除不相关信息和不良信息,已经成为新的研究热点。互联网中数据过滤系统的出现正是为了应对上述问题。过滤系统的性能低下会导致网络违法犯罪行为不能够被及时发现并制止,因此提升过滤系统的性能十分必要。
模式匹配算法是数据过滤系统的关键技术,因此其效率的高低间接地影响着互联网的安全。然而在实际应用的数据过滤系统中,所采用的模式匹配算法的效率不尽如人意,使得过滤过程耗费大量时间,互联网的安全因此无法得到保障。
本文提出了一种改进的AC-BM匹配算法,该算法能够充分利用匹配过程中匹配失败的信息,以达到每一次跳跃中跳跃尽量大的距离,从而使算法的执行更加快速。将此算法应用于数据过滤系统中,能够明显改善过滤系统的性能,使得过滤系统能够应对当前海量的数据环境,广大网民能够更加安全地享受互联网。
1 模式匹配算法简介
1.1 单模式匹配算法
经典的单模式匹配算法包括KMP算法[2]、BM算法等。下面主要简要分析这两种算法。
KMP算法由3个人共同提出,K,M,P分别是3人名字的首个字母。该算法是在BF算法的基础上改进而来。KMP算法创造性地消除了指针回溯,利用已经匹配的字符来确定下一次搜索的开始位置,进而将模式串移动后继续进行匹配。时间复杂度由BF算法中的O(mn)降低为O(m+n)。
BM算法因其由Boyer 和Moore提出而得名,该算法的基本思想是从待匹配文本的右边向左边依次进行比较。当某趟比较过程中失配情况发生时,该算法会利用坏字符和好后缀信息实现跳跃,这种方式能够很大程度上降低字符比较的次数,理想状态下,算法的时间复杂度可达O(n/m)。
总的来说,BM算法相比KMP算法简单,效率更高,实用性也更强,是目前单模式匹配算法中最优的算法。实践证明,BM算法执行速度比 KMP 算法速度快 3～5 倍,但在短模式串情况下,BM算法的优势就没那么明显了。同时,模式集规模较大时,BM 算法的效率难以满足实际要求。再者,它使用了两个数组,预处理开销大。
1.2 多模式匹配算法
1.2.1 AC算法
Aho—Corasick自动机算法[3](AC算法)是多字符串匹配中经典的算法,1975年产生于贝尔实验室,可被看作是KMP算法的改进,而它的创造性在于它在进行匹配之前对模式集进行处理,使得匹配效率不再受到模式集合规模的制约。对模式集进行处理的预先处理实质上就是创建3个表的过程,它们分别是goto表、fail表和output表。goto表可以理解为模式集的状态转换表,当goto表无法查询到时使用fail表,而output表则是用来记录当前位置是否成功匹配某种模式。此算法的时间复杂度可达O(n),并且时间复杂度与模式串的数目和长度无关。
AC多模匹配算法具有如下特点:
1) 算法相对简单、效率高(一次扫描可以完成所有模式的匹配)。
2) 与模式串长度和待匹配文本内容没有关联。
3) 适用范围广(算法适用任意字符)。
该算法的不足之处在于它对内存空间需求比较大。一旦匹配模式集合规模庞大,内存空间使用量会急剧增加,甚至可能导致系统崩溃。
1.2.2 AC-BM算法
AC算法的最突出的特点就是一次扫描可以匹配所有模式,BM算法最突出的特点在于它能够通过跳跃匹配降低比较次数。AC-BM算法的本质就是将这两个算法的优点结合产生的一种新的算法。
同AC算法一样,AC-BM算法会在匹配之前对模式集合进行预先处理,匹配时,采取自后向前的方法,一旦模式确定在适当的地方,从左到右判断是否匹配成功。
在此过程中,借用了BM算法的好前缀跳转(Good Prefix Shift)和坏字符跳转(Bad Character Shift)技术。
所谓好前缀跳转,就是当待匹配字符与模式树某个模式中的字符A不匹配时,利用字符A之前已匹配的字符串S查询模式树,计算距该模式树中下一个出现字符串S的距离L1, 将模式树向前移动L1后继续进行匹配。
坏字符跳转,就是当待匹配字符与模式树某个模式中的字符A不匹配时,计算该模式树中距离下一个A字符的距离L2,将模式树向前移动L2后继续进行匹配。如果字符A在模式树中不存在,那么移动距离可以达到最小字符串长度。
AC-BM算法结合多模式匹配AC和单模式匹配BM两者的优点,即一次扫描过程完成所有模式的匹配又可以在模式匹配的过程中跳过不必要的字符匹配过程,因此AC-BM算法具有更高的匹配效率。它的这些优点可以有效提高数据过滤系统的性能。但是,AC—BM算法的效率仍然无法使当前过滤系统的性能足以应对海量的数据环境,因此需要对AC—BM算法进行进一步改进和优化,使它能够给过滤系统的性能带来提升。
2 AC-BM算法的改进
进一步提高模式匹配算法效率的主要途径是利用模式串匹配失败时可以获取的信息以进一步增大跳跃距离。受BMH算法思想的启发,减少好后缀跳转的比较步骤后,算法的实际性能并不比BM算法差,相反,在某些情况下性能比BM算法优越[4]。因此,可以通过简化AC-BM算法的复杂性,同时对坏字符跳转进行改进,形成一种新的算法。
该算法的核心思想是:匹配的过程中模式串从左向右依次进行比较,当匹配过程中遇到失配字符时,继续判断文本后一字符是否存在于模式树中,如果当前字符和后一字符不存在于模式树当中,就可以直接跳过模式树最小字符串长度加1再进行比较。相比AC-BM算法,突破了无法跳跃大于最大字符串长度的限制,从而减少了比较的次数。如果在模式串中,则跳转到下一个同时出现当前字符和下一字符的位置。
与AC-BM的坏字节相比,在失配的情况下,采用两个字节来查找下一个匹配的位置,无疑加大了失配时的跳跃距离。此外,省去了好前缀跳转步骤,简化了算法,提升了效率。
算法的整个过程可以按时间先后分为模式集的预先处理阶段和字符的匹配阶段。下面将对这两个阶段的处理过程进行介绍。
2.1 预处理阶段
假设待匹配的文本字符串为Text,长度为N,模式字符串为P,模式个数为k,字符集合为Σ,模式集合中最短模式的长度为Lmin。模式集合的预处理阶段首先将模式集合P中所有模式按照AC算法的预处理方式构成模式树,之后再构造一个跳跃数组skip[x1][x2](x1和x2为字符集Σ上的字符)。
2.2 匹配阶段
从树的根字符开始逐个与文本字符串Text进行比较,如果出现了不匹配字符,读取文本字符串Text字符T(i)的下一字符T(i+1),在skip表中查找下一个出现T[i]T[i+1]的位置。若找不到,则移动模式树,将模式树向右移动Lmin+1,若找到,则移动模式树相应距离,与第一次出现T[i]T[i+1]字符的位置对齐。当整个文本字符搜索完成或者匹配成功时返回匹配结果。
改进的AC-BM算法对应的伪代码将展示该算法的具体实现过程,如下:
算法的改进主要体现在:
1) 利用两个元素来定位跳转位置,能够加大失配时的移动距离,从而减少比较次数。
2) 修改了坏字符跳转距离的计算方法,使其只与当前匹配字符有关,而与当前节点无关。
3) 取消了好前缀跳转的计算,计算得到了简化,效率相应得到提升。
3 算法性能测试
3.1 测试环境
测试中硬件环境是采用:CPU Intel Pentium 4,主频1.70 GHz,内存2 Gbyte, redhat 9.0 平台上进行测试。算法用C语言实现,编译器采用 gcc version 4.1.2,优化开关全部打开。
3.2 测试结果
3.2.1 时间测试
时间测试主要的目的是为了比较各个算法在外部环境相同的情况下处理不同模式集合所需的时间。
首先测试模式数量和匹配时间之间的关系。测试过程中选择的模式长度为20 byte,记录4种算法完成匹配过程所耗时间数据,根据测试数据绘制匹配时间-模式数量图。图1中显示,改进算法相比其他3种算法在模式数量较小和模式数量较大的情况下性能都得到了较大改善,与预期结果一致。
接着测试模式长度和匹配时间之间的关系。模式数量固定在1 000个的情况下,记录4种算法完成匹配过程所耗时间数据,根据测试数据绘制匹配时间-模式长度关系图。图2中显示,改进算法相比其他3种算法在长模式和短模式的情况下性能都得到了较大改善,与预期结果一致。
3.2.2 空间测试
空间测试的目的是为了比较各个算法在同等条件下内存空间的使用情况。测试过程中保持模式个数和模式长度相同,分别为1 000个、20 byte,记录各算法匹配过程中内存空间消耗数据,绘制内存消耗图。图3中显示,改进算法的内存消耗与AC算法和AC-BM算法相比并没有明显增大,与预期结果一致。
通过对各个算法进行时间和空间的测试可以得出如下结论:
1) 改进的匹配效率不受模式个数的限制。
2) 改进的匹配算法在模式长度较小和较大时匹配效率都较高,能够很好地抵抗短模式长度带来的性能低下。
3) 改进的算法对消耗内存资源的消耗并没有很大的增长。
4 改进算法在内容过滤系统中的应用
数据过滤系统是保护网络安全的一道重要防线,它通过对网络数据内容进行匹配,能够有效发现不良信息及违法信息,即时阻止其在网络中的传播和蔓延,从而保证网络的安全。内容过滤系统处理的对象主要是文本数据,在互联网中,需要处理的文本数据量非常的庞大,因此对内容过滤系统的性能要求很高。
内容过滤系统根据功能可以划分为3个模块(图4),分别为数据采集模块、数据还原模块和过滤模块。采集模块负责将网络中传输的MAC帧进行处理,还原出TCP和UDP流。TCP和UDP流经过还原模块后得到大量的文本数据,之后发送给过滤模块进行文本过滤。
过滤模块的工作过程分为两个阶段,首先匹配算法的预处理阶段,会将用户的需求以规则串的形式构建状态机和规则相应的失配跳跃表skip,在信息匹配阶段,系统会对待过滤的文本数据进行预先处理,之后对文本信息进行匹配,实时将匹配结果发送给用户。
5 小结
本文通过对各种匹配算法进行分析,进而提出了一种改进的算法。改进的算法在进行模式匹配时执行速度得到了明显提升。尽管空间上比AC-BM算法增加了一些额外开销,但它使得数据过滤系统的性能得到较大提升,综合考虑,这种空间换时间的方法是值得的。
参考文献
[1]耿金秀.浅谈计算机网络安全防范措施[J].中国科技信息,2011(8):110-111.
[2]朱娇娇,叶猛.多模式匹配及其改进算法在协议识别中的应用[J].电视技术,2012,36(7):60-63.
[3]KUNTH D E,MORRIS J H,PRATT V R.Fast pattern matching instrings[J].SIAM Journal on Computing,1977,6(2):323-350.
基于模糊匹配的多维数据查询算法 篇8
关键词：模糊匹配,基于案例推理,相关度
一、引言
随着信息技术的发展, 传统的燃气计费及用户管理方式需要消耗大量的人力物力, 已经无法满足现有状况的需求, 基于B/S分布式的燃气计费及用户管理系统已经成为当前燃气企业核心业务平台。用户培养、挖掘潜在用户、业务扩展已经被现代化企业视为提高核心竞争力的源泉。燃气计费及用户管理系统不仅为燃气计费及用户管理提供了有效的解决方案, 而且也能够通过建立企业与用户交互平台和业务信息决策平台来挖掘用户信息、扩展核心业务, 从而为企业发展提供决策支持。
用户及业务信息通常被存储到系统的数据库中, 随着用户数量以几何级数的方式增长, 注册到燃气企业的用户信息及业务数据信息离散的分布在系统数据库中。传统的数据查询方法仅利用用户的查询请求中所包含的特征项匹配数据库中数据, 这种基于布尔查询匹配方式无法满足用户对于多特征项数据的查询多样性需求。面对复杂的用户查询请求, 系统无法有效地分析用户请求信息, 以至于返回的低相关度结果不能满足用户需求。近年来, 基于案例推理 (简称CBR) 自20世纪80年代末、90年代初兴起之后, 该方法受到了国内外学者的广泛关注, 已经得到了大规模应用。CBR的推理过程是重用历史成功求解相似问题, 从中获得当前问题解的推理方法。利用基于案例推理的方法对数据库中的数据进行模糊匹配, 能够增大检索结果类比范围, 满足企业多维检索模式需求, 为企业决策提供支持。
本文设计了一个基于模糊匹配的多维数据检索模型, 将数据库中存储的数据视为多维特征项的案例, 为每个数据的特征项设置归一化算法, 对数据库中的数据进行检索训练, 动态生成检索结果相似度范围, 根据检索结果精度预设值范围, 动态返回检索结果。经过仿真实验, 该模型能够提高数据查询效率。
二、多维数据分类模型
在燃气用户管理系统的数据库中, 用户数据的存储结构通过多维特征项方式进行存储。设集合US= (u1, u2, …, un) 是一个非空有限集合, 它由n个元素组成, 每一个元素均为数据库中的一个数据项, 即U= (ID, name, addr, …, cost) , 其中ID为系统为该用户分配的ID号, ID作为主键通常用来唯一标识用户的信息;name作为结构化信息中的一个特征项被用来表示用户的名字;addr代表用户的居住地址;cost, 表示用户的消费情况。将U中的每一项视为一个特征, 以特征项对U进行整体描述, U在某方面拥有的属性用某一特征项表示, U的所有特征均能够被用来进行检索匹配。
设D= (t1, t2, …, tm) 为检索训练案例集合, 每一个训练案例ti= (f1, f2, …, fk) 均被用来执行多次检索训练, 其中f为训练案例的特征项且D中每个训练案例所包含的特征项均不同。利用D中每一个元素ti对集合US进行检索训练, 根据返回的结果集合R= (r1, r2, …, rx) , 抽取满足需求的结果TR= (ra, rb, …, rh) , 观察TR中元素相似度范围, 制定ti的检索精度范围CR= (DL, UL) , 其中DL和UL分别为精度上限值与下限值。在检索过程中, 首先为每个特征项的匹配方法制定归一化算法, 可根据特征项的数据类型进行个性化处理。例如, 对于整型类型, 可根据整型数据所属范围进行匹配, 如公式1所示。
其中, max和min分别表示整型数据范围, 而f则表示当前整型数值, 从而实现归一化处理, 进而在特征项匹配过程中将两个归一化值进行比较, 从而发现匹配结果相似性。对于布尔类型枚举类型等其他类型数据也可参与上述方法进行处理。案例推理过程如下:
(1) 特征提取。提取新生成的目标案例obj_c所含特征项, 。
(2) 计算距离。将该obj_c与US集合中所有元素进行匹配, 利用欧氏距离公式计算出距离disi, disj, …, disk。
(3) 更新dis。根据disi, disj, …, disk将检索集合进行排序。
(4) 返回结果并等待反馈。将排序后的案例检索结果集合返回给用户, 并等待用户筛选出满足其需求的结果或等待用户重新执行检索。
根据该推理过程, 能够获得案例训练检索过程, 如图1所示。
因此, 能够为D中所有元素制定检索精度范围。那么, D中的所有元素也可被视为用户查询条件先验案例。也就是说, 在用户选择一个或多个查询特征, 从而组成查询案例, 当系统接口获得该查询案例后, 将该案例与D中元素进行匹配, 从而获得D中元素对应的检索精度范围, 将该范围以及对应的检索结果快速返回给用户。用户根据返回的结果进行筛选, 若用户对当前检索结果无法满足检索结果需求, 则可由用户自行调节当前检索精度或系统自动扩大检索精度, 继续执行二次检索, 将检索结果返回给用户, 并继续等待用户反馈信息。利用先验知识即训练检索结果集合及检索精度范围, 能够快速响应用户, 从而减少了并发处理过程中用户等待时间, 提高用户体验效果。此外, D中元素均为不完全案例, 有利于对案例库中案例进行降维处理。降维能够降低案例相似度计算时的复杂度, 只需与具有相同案例结构类别的案例进行匹配, 从而缓解了案例检索效率降低的问题。D中元素均有一个或多个特征项组合而成, 用户输入一个或多个检索项时, 可根据特征项提取器提取的结果合并检索, 从而有效提高检索效率。
三、实验结果及分析
在仿真实验中, 数据库中存储的数据量为5000。训练检索案例集合中的元素设置为2000。本文与传统查询算法进行比较, 分别进行了1000次查询。图2表示查询时间对比结果, 图3表示查询相关度对比结果。
如图2所示, 随着请求数量的不断增加, 传统查询算法始终拥有较高的查询响应时间, 基于模糊匹配的查询算法则保持较低的查询时间。对于两种算法之间存在的性能差异而言, 当一个查询进入到系统中, 对于传统查询算法而言, 它需要从整个数据库中匹配所有数据, 根据匹配结果返回给用户, 较大的查询空间使得匹配时间过长, 响应速度低下。基于模糊匹配的查询算法能够根据预先设定的训练查询集合, 直接返回给用户查询结果, 查询时间仅仅在提取查询特征项匹配查询特征项这一过程中消耗, 降低了查询空间规模, 因此查询响应时间维持在较低的水平。快速响应用户能够确保用户高的体验效果。
如图4所示, 基于模糊匹配的查询算法利用先验知识, 即训练检索案例集合中的检索精度范围, 动态调节返回用户相关结果, 因此, 返回的结果能够大部分满足用户需求, 从而使得检索结果相关度较高, 即所检索的相似信息集合中的信息被采纳的程度较高。然而, 对于传统检索算法而言, 仅仅依赖于查询特征项的匹配结果, 返回结果相关度低, 无法满足用户需求。从而验证了本文提出模型的有效性。
四、结语
本文提出了一个基于模糊匹配的多维数据检索模型, 将数据库中存储的数据视为多维特征项的案例, 构建一个自学习自调节的数据检索训练算法, 动态生成检索结果相似度范围, 根据检索结果精度预设值范围, 动态返回检索结果, 降低了查询空间规模, 使得用户快速获得的相关查询结果。
参考文献
[1]李锴, IC卡燃气表预付费系统的研究[J].山西电子技术.2006, 3:86-88.
[2]隗晨雪, 朱建明, 基于隐私保护的朴素贝叶斯分类协议[J].计算机工程.2010, 36 (18) :26-28.
[3]王亚英, 邵惠鹤, 基于案例的不确定检索模型的研究[J].控制与决策, 2000, 15 (6) :750-752.