相似性检测（共9篇）
相似性检测 篇1
1引言
空中弱小目标的检测是当前红外研究的热点和难点,当导弹﹑飞机与红外探测器的距离很远时,目标在红外图像中仅占一个或几个像素点,很难提取出目标的形状结构﹑纹理等特征,而且红外图像中绝大部分是起伏的云层和大气辐射背景,目标往往会淹没在背景当中,同时红外探测器和成像系统本身也会引入各种噪声,使得红外点目标的图像信噪比低,对比度低,更增加了弱小目标检测的难度。
鉴于点目标只有灰度信息,同时信噪比低,传统的基于目标的特征和强度信息的方法很难实现小目标的检测,因此,检测识别点目标的可用信息时除了目标本身的灰度信息外,还必须利用目标周围的灰度分布和图像中灰度起伏特征。本文利用背景像素点和目标像素点的灰度值在空间分布上与其邻域像素之间的差异,提出相似性滤波的方法来抑制背景杂波的干扰,提高图像的对比度和信噪比。同时为了降低噪声的影响,对红外图像中存在的高斯噪声和脉冲噪声分别进行处理,不但尽可能的消除了噪声的影响,还最大限度的保留了图像的边缘信息。结合Robinson Guard空域滤波方法,给出了红外点目标检测的具体实现。
2红外点目标﹑背景和噪声的特性分析
天空红外图像的背景绝大部分是云层和大气辐射,既有较亮的块状云团,面积较小的云朵,也有暗淡的大气背景。云层和大气辐射部分的像素值是平缓变化的,相邻像素点的灰度值之间具有很强的相似性。运动目标往往淹没在背景当中,仅占几个像素点,从灰度值上看,因为目标点的热辐射作用,点目标灰度值与背景灰度值之间存在很大差别,与周围邻域像素点之间的相似性很小。红外噪声主要包括热噪声﹑散粒噪声﹑1/f噪声和温度噪声等,红外噪声的分布与背景无关。
基于灰度信息的红外点目标图像模型可以描述为:
f(i,j)=fT(i,j)+fB(i,j)+fN(i,j) (1)
其中,fT(i,j)为红外图像的灰度值;fT(i,j)为点目标的灰度值;fB(i,j)为背景灰度值;fN(i,j)为噪声灰度值。点目标和噪声为图像中的灰度奇异点,属于图像的高频信息,大部分背景属于图像的低频信息。
3自适应噪声处理
天空点目标的红外图像是低信噪比的图像,为了有效的检测出点目标,必须去除图像中的噪声。传统的去除噪声方法主要有:中值滤波法﹑均值滤波法﹑形态学方法和小波方法。但这些方法往往只对某种噪声有效或严重依赖于给定的关键值。红外图像一般同时受到高斯噪声和脉冲噪声的污染,为了有效去除这两种噪声,很多自适应的方法被提出[2,3],但这些方法在去除图像噪声的同时使得图像变得模糊。图像的边缘包含很多有用的信息,在去噪的同时应尽可能的保留,因此,在上述方法的基础上进行改进:对图像中受噪声污染的像素和边缘像素进行识别,对被高斯噪声和脉冲噪声污染的像素点分别进行处理,保持边缘像素点,从而在尽可能消除噪声影响的同时保留图像的细节。
3.1像素点的区分
脉冲噪声(正脉冲噪声和负脉冲噪声)在数值上通常表现为局部极大值或极小值,但数值很大或很小的像素并不一定就是脉冲噪声点,还必须利用噪声的其他特性[4]。考虑噪声点往往是孤立点,即几个脉冲噪声点同时在一起的可能性很小,而边缘点虽然在局部也具有最大或最小特性,但边缘像素点是连续的,同时高斯噪声点集中分布在其均值左右的三倍方差范围内。利用这些特性来实现脉冲噪声﹑高斯噪声﹑边缘的分离。
设f(i,j)为图像中任意点,以像素f(i,j)为中心的邻域内全体像素点的均值为m﹑方差为σ,设max(i,j),min(i,j)分别表示邻域内像素的极大值和极小值,计算f(i,j)与均值m之间的偏差σy,表示y(i,j) 8邻域中的任意点,σy表示y(i,j)与均值m之间的偏差,则具体判别规则如下:
(1)若σf≥3σ,并且f(ij)=max(i,j)或f(ij)=min(i,j),且存在y(i,j)满足σy≤σf,则将f(i,j)判为边缘点,保留其灰度值,不对其进行去噪处理;
(2) 若σf≥3σ,且f(ij)=max(i,j)或f(ij)=min(i,j),但不存在y(i,j)满足σy≤σx,则将f(i,j)判为脉冲噪声点;
(3)将不满足(1)﹑(2)条件的点判为受高斯噪声污染的点;
对整幅图像的像素点分别进行计算,判别出图像中的像素点分别属于脉冲噪声﹑高斯噪声﹑边缘像素的类别,分别对它们进行不同的噪声处理。
3.2噪声处理
中值滤波利用当前滤波点的邻域平均值来代替当前点的灰度值,均值滤波利用邻域中值来代替当前点的灰度值,同时为减少滤波点周围噪声污染像素点对滤波效果的影响,对滤波窗口内像素点给出相对应的权值,权值随噪声类型和局部灰度变化而改变,通过改变权值控制滤波效果。如果当前像素点为高斯噪声或灰度值与局部的中值相差不大,最后的滤波器处理结果则趋近于均值滤波,如果当前像素点为脉冲噪声或灰度值和中值相差很大,最后的滤波器处理结果趋近中值滤波。通过噪声类型和局部灰度分布变化自适应得调节滤波器的参数,尽可能的利用中值和均值的滤波的良好特性。
改进的自适应滤波处理的表达式如下:
式中,med为滤波窗口内灰度中值;f(i,j)为点(i,j)灰度值;f(i+m,j+n)表示f(i,j)的滤波邻域;定义该点权值为wi,j(m,n),归一化权值为undefined;(-p,p)是滤波窗口的范围;g(i,j)为f(i,j)经过滤波后的灰度值。
4相似性滤波算法
在红外运动目标的检测中,为了消除背景的影响,提高图像的信噪比,一般采用预测背景的方法,将预测的背景fL(i,j)与原始图像作差分。自适应背景预测表达式如式(2)、(3)。wi,j(m,)为像素值的加权系数。权系数的取值由邻域像素值与窗口中心像素值绝对差的某个函数决定 即:
undefined (6)
若f(i,j)为物体内部或弱边缘,则与邻域点的灰度值相差不大,这时主要使用邻域点对其预测,需要选取较大的邻域权值wi,j(m,n)。若f(i,j)处于物体的强边缘,其邻域点灰度值与之差异显著,此时需要保留f(i,j),邻域权值wi,j(m,n)取值较小,为此ϕ可以选择单调递减函数。
将预测背景图像与原始的图像作差分,得到残差图像f'(i,j)如下式:
undefined (7)
利用邻域灰度值的加权对当前像素点进行预测不可能得到完全精确的值,预测值与原始灰度值之间存在着误差,对于整幅图像来说,各个背景像素值的误差其分布在实际处理中认为近似服从高斯分布,即后续的处理被看作是从高斯分布中寻找非高斯信号的过程。对高斯信号中非高斯信号的识别非常复杂,而且由于背景预测的影响使得点目标的非高斯特性不明显。同时采用预测背景的方法不但要计算各个邻域点的加权系数,还要将各个邻域点的灰度值与权系数相乘并计算累加和,计算非常耗时,不利于红外点目标在实际中的应用。为此,在背景预测基础上提出一种相似性滤波方法。
相似性滤波是基于红外天空图像的像素分布特点而提出的。若当前像素点属于背景像素时,因为背景平缓变化,相邻像素值之间具有很强的相似性,则当前像素与它的邻域像素点之间的平均相似性很大;若当前点为点目标像素,目标像素点因辐射作用,灰度值与周围像素点存在一定差异,与邻域像素点的平均相似性很小;若当前像素为背景的边缘,该点与邻域部分像素存在较大差别,则平均相似性介于点目标与背景之间。通过像素点之间平均相似性的评价,把图像中所有或明或暗的云层和暗淡的大气辐射背景都统一转化为平均相似性接近的区域,通过平均相似性取反值,背景区域的像素值趋近零,突出相似性小的点目标,而边缘部分的相似性介于两者之间,实现了背景﹑点目标﹑云层边缘的分离。相似性滤波的表达如下:
undefined (8)
undefined (9)
undefined (10)
其中,s(i,j)为当前滤波点s(i,j)的平均相似值;undefined为平均相似性的反值;k为邻域像素个数;(Δi,Δj)表示邻域大小,一般根据目标的大小选择合适的矩形区域;s(i+Δi,j+Δj)为邻域点f(i+Δi,j+Δj)与当前点f(i,j)的相似性;σ用于调节函数的衰减速度。
相似性滤波抑制了占图像中绝大部分的背景杂波,同时增强了待识别的点目标信息,保留了图像中的边缘细节,使得整幅图像的对比度和信噪比得到大大提高,即使点目标在原图像中的灰度值与部分背景灰度值差别不大也能够在图像中得到明显体现。相似性滤波后的背景部分不再是近似高斯分布的噪声,而是仍然满足平缓变化的区域,在减少大量计算量的同时,使得后续的点目标识别变得简单。
5点目标检测算法的实现
红外图像中噪声对点目标检测识别的影响很大,在进行相似性滤波之前,对原始图像进行去噪处理消除噪声尤其是高斯噪声的干扰,然后对图像进行相似性滤波,达到抑制背景的同时增强点目标,分离边缘云层,提高整幅图像的对比度和信噪比,为得到点目标,结合Robinson Guard 空间滤波算法进一步消除平缓变化的背景﹑背景边缘的影响。
6仿真试验与结果分析
6.1仿真试验
图1～图4为两组天空红外弱小点目标的仿真图像,其中图1为原始图像,对它分别进行处自适应去噪处理和相似性滤波操作,图2为相似性滤波后的图像,图2中云层和大气辐射背景被极大的抑制了,同时云层的边缘被很好的保留,不明显的点目标被极大增强了。利用Robinson Guard对图像进一步处理,如图4为最后检测的结果。
图1中,点目标并不明显,点目标的灰度值低于部分背景像素的灰度值,背景并不是均匀分布的,认为点目标与背景的灰度值具有极大差异,如基于局部能量比[5],图像熵[6],分形维数[7]和蚁群的Otsu[8]方法等都不能够很好的实现目标的检测。图3分别为原始图像与预测背景图像作差分后的残差图像(为便于直观显示,对整幅残差图像的灰度值进行了线性调整),图像中的背景部分经过抑制后仍然存在大量的杂波,这是由于预测的不准确造成的,部分杂波灰度值接近点目标灰度值,点目标难于利用简单有效的方法识别出来。图2采用相似性滤波的方法能够将明亮的云层和暗淡的大气辐射背景都转化为平缓分布的暗淡区域,其大部分像素趋近于零值,图像中点目标虽然与部分背景灰度值接近,但滤波后却被增强了,同时滤波后很好的保留了背景的边缘变化,图像的信噪比和对比度获得极大的提高。平缓背景的高信噪比和高对比度图像中目标的检测很容易实现。
6.2结果分析
采用自适应噪声处理和相似性滤波的方法能够有效地提高图像中信噪比和对比度,抑制图像中对点目标检测造成干扰的大量背景杂波信息,结合Robinson Guard滤波方法能够有效的实现点目标的检测。
算法的实现是建立在原始图像的背景分布比较平缓的条件下,若背景的变化特别剧烈,则相邻像素点之间的相似性很小,易于突出变化激烈的背景像素,造成点目标在相似滤波后仍然受到的背景杂波的干扰,相似性滤波对图像质量的提高能力有限;当点目标很小时,噪声斑块的大小和灰度值可能接近点目标,相似性滤波会引起部分噪声点的增强,因此必须对噪声进行有效地的预处理;相似性滤波窗口的大小要选择适当,过小时,使得当前像素点被误判为背景像素点,目标点有可能出现空洞甚至丢失现象,过大时,计算耗时。
摘要：针对天空红外图像的特点,利用背景像素点和目标像素点的灰度值在空间分布上与其邻域像素灰度值之间的差异,提出相似性滤波的方法,相似性滤波的方法,算法简单,图像中的背景干扰能够被极大抑制,图像中点目标的对比度和图像的信噪比被显著提高。为减小噪声影响,一种自适应的噪声处理方法被给出,它对图像中的高斯噪声和脉冲噪声分别处理,在提高去噪效果的同时保留了图像的边缘信息。仿真结果表明提出的算法对红外点目标的背景具有极好的抑制能力。
关键词：红外点目标,自适应噪声处理,相似性滤波
参考文献
[1]郭杰峰,陈桂林.云天背景下单帧红外图像的点目标检测.激光与红外,2007,37(9):898～891
[2]Tudan,Yanhong,Zhenkang Shen.A New Nonlinear Preprocessing Algorithm for Infrared Image.IEEE,1997.
[3]曹西征,郭立红.基于相似加权滤波的红外图像增强算法.计算机测量与控制,2007,15(4):534～537
[4]何洪英,姚建刚,罗真生.红外图像的自适应混合消噪方法.计算机工程与应用,2006,6:7～9
[5]林玉野,高晓颖,曹炬.基于局部能量比的空中红外弱小目标的检测方法.航天控制,2007,25(5):48～50
[6]赵钦佩,姚莉秀,刘瑞明等.一种新的基于背景的红外图像分割方法.计算机仿真,2007,24(5):202～205
[7]卢晓东,周军,周凤岐.自然背景下对人造红外目标的分形检测.航空兵器,2006(12):31～33
[8]王爽,黄友锐,李冬.基于蚁群算法的改进Otsu理论的图像多阈值分割.微计算机应用,2008,29(4):25～28
相似性检测 篇2
三才采编2011版于2011年4月隆重推出。新版本在原有系统的基础上，国内首家集成了论文相似度检测，支持优先出版、一键发布过刊等功能，同时使得系统的易用性，安全性以及运行效率得以大幅提升。同时，新的系统结构设计也为不同期刊之间的协同办公，构建行业期刊联盟成为可能。
新版本中添加的功能有：
1.首家集成 “论文相似度检测查询系统”
a)万方数据独家授权三才采编集成其“论文相似度检测系统”，可以自动在采编系统中形成PDF格式的检测报告。如图a所示
b)根据和万方数据所达成的协议，凡是使用三才期刊采编系统的编辑部用户都可以免费获得相似度检测查询系统的用户名和密码。
c)相似度报告形成及查看
i.作者上传稿件时会自动形成ii.编辑部可以查看相似度报告，并可设定是否开放给作者及专家查看报告内容
图ａ：论文相似度检测报告示例
2.首家支持“优先出版”，可自动抽取标题、作者、关键词等元数据
a)优先出版是以印刷版期刊录用稿件为出版内容，先于印刷版期刊出版日期出版的数字期刊方式。为了顺应这一趋势，三才采编2011版中添加了优先出版功能，b)系统可以从Word文档里自动提取如作者，标题，期刊名，论文摘要等元数据信息，不必再手动输入，大大提高工作效率。图b是预出版功能的一个界面截图。
图ｂ：预出版功能界面
3.中英文双语系统升级换代
a)中英文双语系统结合，系统维护更新便捷
b)中英文界面一键切换，使用方便
c)添加中英文系统模板，用户可以自行设置
d)用户字典可以自行设置
4.其他新增功能：
a)支持一键转发过刊
b)增加常用链接，便于编辑部团队培养和知识积累。
c)审稿系统提供万方、知网的相关论文查询快捷链接，方便专家审稿。
相似性检测 篇3
关键词：网络蠕虫,攻击检测,网络流量,自相似性
0 引言
随着网络蠕虫技术的发展与Internet应用的普及,网络蠕虫已成为当今网络面临的最大威胁。其多样化的传播途径和复杂的应用环境使其发生频率高、潜伏性强、覆盖面广、破坏巨大,预防并减小蠕虫传播所造成的破坏是当今网络安全迫切需要解决的难题。蠕虫的攻击分为扫描与目标选择、感染、传播3个阶段。如果在蠕虫感染传播前的第一阶段能对其检测到并发现其传播的特征信息,对防止中后期网络中由于蠕虫蔓延造成严重破坏尤为关键和重要。本文提出一种基于Hurst参数的蠕虫攻击检测方法,该方法采集网络数据包并提取相应的TCP、ICMP流量特征,检测被监控网络的网络流量自相似性。实验结果表明该检测方法对采用主动IP地址扫描方式传播的未知类型蠕虫攻击行为具有较好的检测效果。
1 网络流量自相似性与Hurst参数
1.1 网络流量的自相似性
自相似性是指一个随机过程在各个时间规模上具有相同的统计特性。Leland在1994年对局域网测试与分析的结果表明计算机网络通信中的网络流量具有统计自相似性[1]。其自相似性表现在较长一段时间内单位时间分组数的统计特性不随时间规模的变化而变化。Beran在1995年通过对大量的不同类别的可变比特率视频流数据的统计发现,网络流量同样表现出长相关特性[2]。
对于某时间序列X={Xi,i=1,2,…,N},如果其自相关函数可表示为:
则X称为严格自相似的序列,其中H是表征该序列自相似度的Hurst参数,0
自相似性最显著的特点是,它的m阶平滑过程X(m)在m→∞时相关函数结构上是非退化的,当m→∞且r(k)→0时,X(m)趋向于独立同分布随机变量序列。若r(k):k2H-2(k→∞),则称X是渐进自相似的序列。若∑r(k)=∞,则称X是长相关序列。序列X的自相似性程度使用Hurst参数H表示,H=1-β/2。对具有长相关特性的自相似性过程,0.5
1.2 Hurst参数的计算
计算Hurst参数有多种方法[3],主要有聚合方差法、绝对值法、R/S法、周期图法、小波系数方差法[4]。其中小波系数方差法具有算法简单、易于计算、计算结果准确的优点,本文选用小波系数方差法计算网络流量中的Hurst参数。
对于时间序X={Xi,i=1,2,…,N},Xi表示第i个单位时间内到达网络流量单元的数目。选取一个正整数N,并把这个序列化分成为N块,然后在每一块内部计算平均值,得到聚合以后的序列:
这样可得出与聚合序列XN(k)的方差相等价的式子:
两边取对数得:
由式(4)可构造线性相关函数:
对每个时间系列的X(N),都计算出其方差:
并将该计算方差过程记为PVar。
根据式(6)计算出的Var(X(N))值和N值,可以做出{log(N),log[Var(X(N))]}关系线性图。但是在实际分析过程中,不可能通过绘图进行测量。由于Var(X(N))和N的{log(N),log[Var(X(N))]}曲线呈线性关,因此可采用直线对所得曲线进行拟合。然后根据曲线的斜率t得出β值,β=-t,从而求出自相似系数H=1-β/2。
2 蠕虫攻击检测系统设计
2.1 蠕虫攻击检测方法
蠕虫利用系统漏洞进行传播之前要进行目标机扫描探测,ICMP Ping包和TCP SYN,FIN,RST及ACK包均可用于扫描探测[5]。在扫描探测时,若蠕虫攻击机需扫描的IP地址不存在或不可路由,则会返回给蠕虫攻击机一个ICMP不可达包;若目标机地址存在但没有可被感染的漏洞,蠕虫攻击机会产生一个RST重建连接的数据包。蠕虫进行扫描探测时,将产生了大量失败的TCP连接,收到的ICMP,RST数据包剧增,导致网络自相似性降低[6,7]。在蠕虫攻击导致网络中存在大量无效相似数据流时,网络流量将趋向于泊松分布,且Hurst参数值趋向于0.5。从Hurst参数值的变化可检测到当前网络中出现的蠕虫攻击。
在具体应用时,可先计算出正常网络流量的Hurst参数值。在发生网络蠕虫攻击时,计算出当前异常网络流量的Hurst参数值。最后分析前后计算的Hurst参数值变化情况。
令正常网络流量对应的Hurst参数值为Hnormal,有蠕虫扫描攻击的异常网络流量对应的Hurst参数值为Hworm,令Δh=Hnormal-Hworm。设定阀值θ,若Δh>θ,则认为蠕虫攻击发生了,否则可认为没有发生蠕虫攻击。典型的网络流量自相似参数Hurst参数值为0.75～0.85之间[8],当Hurst参数值小于0.5即可认为已不是自相似流量,阀值θ可设定为小于0.25。为能有效地检测到网络蠕虫攻击行为,本文设定的θ为0.2。当Hurst参数值变化值Δh超过0.2,就可认为在网络中检测到蠕虫攻击行为。
2.2 蠕虫攻击检测模型
当前多数攻击检测系统是基于Dorothy Denning的攻击检测模型,这种模型分为误用检测和异常检测[9]。与误用检测方法相比,异常检测的明显优点是能检测出未知类型的网络攻击。本文的网络蠕虫攻击检测系统采用的是异常检测模型。基于上述分析,设计实现的模型包括5个部分,分别是数据包捕获模块、数据包特征提取模块、Hurst参数计算模块、流量模型、蠕虫攻击检测模块,如图1所示。
在图1中,数据包捕获模块使用WinPcap对被监控网络进行数据包采集;数据包特征提取模块负责提取采集的网络数据包TCP,ICMP流量特征,并将其存储到特征库;Hurst参数计算模块将数据按照时间划分时间序列,计算求解出相应的Hurst参数值,这些数据为下一步建立正常/异常网络流量模型提供重要依据;蠕虫攻击检测模块根据前面的结果判断是否检测到蠕虫攻击。
3 实验结果
为验证该系统对蠕虫攻击检测的可行性、正确性,选取了一个典型的网络拓扑进行实验,其拓扑结构如图2所示。为了使测试更接近真实网络环境,检测机在不同时段、不同环境下从校园网路由器上捕获网络数据。
不同类型的网络蠕虫其扫描IP地址生成策略不同,实验中使用了Code Red,W32.Blaster,Flash,Warhol,Contagion产生5种不同扫描探测类型的蠕虫攻击数据包样本。实验中,为避免数据样本大小不对称造成的实验结果偏差,采用了12次交叉验证法,最后以12次实验结果的平均值作为最终的结果。在实验结果的评估指标方面,使用准确率、遗漏率、误报率3项指标作为验证实验有效性的依据。实验检测结果如表1所示。
表1中的前4种蠕虫按一定策略生成扫描探测目标IP地址并主动对目标机进行攻击,此类蠕虫在扫描探测时会导致网络流量异常。最后一种蠕虫Contagion采用被动式扫描方式,其在传播攻击时无需扫描,而是等待潜在的被攻击对象主动连接它[10],此类蠕虫的传播不会引起网络流量异常。该系统使用的是没有蠕虫类型特征库的异常检测方式。由实验结果可知,该系统根据网络流量的变化情况能及时准确地检测到采用主动扫描探测攻击的未知类型蠕虫攻击行为,但无法检测到不会引起网络流量异常的被动式扫描类型蠕虫攻击。
4 结语
网络蠕虫攻击是当前因特网的主要攻击方式。随着网络环境的日趋复杂,传统的检测方法已不能准确区别未知类型蠕虫攻击和正常网络流量拥挤之间的区别而造成误报漏报。基于网络流量自相似性的蠕虫攻击检测方法,无需获取蠕虫特征值信息就可检测到采用主动扫描探测的未知蠕虫攻击行为,实验表明该方法对蠕虫的检测防御具有一定的实用性和可用性。今后的工作重点是将误用检测和异常检测相结合进一步提高蠕虫检测成功率,并研究对采用被动式扫描的未知蠕虫攻击检测方法。
参考文献
[1]LELAND W E,TAQQU M S,WILLINGER W,et al.On theself-similar nature of Ethernet traffic(extended version)[J].IEEE/ACM Trans.on Networking,1994,2(1):1-15.
[2]BERAN J,SHERMAN R,TRAQQU M S,et al.Longrange dependence in variable bit rate video traffic[J].IEEETrans.on Communication,1995,43(2/3/4):1566-1579.
[3]第文军,薛丽军,蒋士奇.运用网络流量自相似分析的网络流量异常检测[J].兵工自动化,2003,22(6):28-31.
[4]李永利,刘贵忠,王海军.自相似数据流的Hurst参数小波求解法分析[J].电子与信息学报,2003,25(1):100-105.
[5]Fyodor.The art of port scanning[M].Phrack Magazine,1997,7(51):11-17.
[6]ELLIS Daniel R,AIKEN John G,ATTWOOD Kira S,et al.A behavioral approach to worm detection[C]//Proc.of ACM Workshop on Rapid Malcode.New York,USA:ACM,2004:43-53.
[7]WU J,VANGALA S,GAO L,et al.An efficient architec-ture and algorithm for detecting worms with various scantechniques[J].Proceedings of the Network and DistributedSystem Security Symposium.Washington:The Internet So-ciety,2004:143-156.
[8]LELAND W E,WILLINGER W,TAQQU Murad S,et al.On the self-similar nature of ethernet traffic[J].Computer Communication Review,1995,25(1):202-213.
[9]高能,冯登国.一种基于数据挖掘的拒绝服务攻击检测技术[J].计算机学报,2006,29(6):944-951.
相似性检测 篇4
针对目前空间数据相似性查询的广泛应用需求和实际应用情况,提出基于特征的.空间数据相似性查询(Feature Based Spatial Data Similarity Query,FBSDQ)的概念,并给出了形式化定义,分析指出了FBSDQ的特点.提出了统一的FBSDQ处理框架及其实现的关键技术,以典型的度量空间高维索引结构VP树为例,讨论了基于距离的度量空间高维索引技术,为空间数据相似性查询的研究提供了技术支持.
作 者：夏宇 朱欣焰 周春辉 XIA Yu ZHU Xin-yan ZHOU Chun-hui 作者单位：夏宇,XIA Yu(武汉大学,遥感信息工程学院,武汉,430079)
朱欣焰,周春辉,ZHU Xin-yan,ZHOU Chun-hui(武汉大学,测绘遥感信息工程国家重点实验室,武汉,430079)
相似性检测 篇5
微博客,又称微博,作为一种新的传播载体,包含了大量用户针对人物、事件等的评论信息,因此在网络舆情发起和传播中起着重要作用,并成为网络舆情浏览和分析的重要数据源之一。
但是,在微博空间,便捷的“转发”操作以及快速增长的“网络水军”,使得大量相同或相似的数据在微博空间内迅速传播。同时,噪音微博作为一种宣传手段也迅猛蔓延到微博空间的各个角落。对于网络舆情分析而言,噪音微博通常没有意义,相同或相似的微博也只具有一定的统计意义。对于微博用户的浏览而言,用户会发现自己看到的微博数据很多,但真正得到的有意义的信息量却很有限,浪费了时间和精力。同时,这类微博的存在也严重影响到了信息检索的准确性,大大降低了分析的可信性。因此,对微博客文本信息进行过滤提纯,对于减轻用户浏览理解和系统存储的负担,提高文本内容检索、网络舆情分析的效率等都具有十分重要的意义。
基于此,本文分析了微博客文本流中噪音微博和相似微博的特点,提出一种针对微博文本流的噪音判别和内容相似性双重检测的过滤方法。通过URL、字符率、高频词等特征判别,过滤噪音微博。通过分段过滤和索引过滤的双重内容过滤,检测和剔除相似微博。实验表明了这些方法能有效的对海量中文微博数据进行提纯,准确地过滤掉其中的噪音微博和相似微博。
1 相关工作
微博客近年来已经成为相关领域的研究热点。Sakaki等利用微博数据的实时性特征,将Twitter[1]中的用户看作“社会信息传感器”,并以此来对地震、台风等自然灾害信息进行跟踪与预警[2]。Weng等研究微博空间中关键用户发现问题,考虑用户间的话题相似性和链接结构,设计新的排序算法Twitter Rank来发现Twitter中有影响力的用户[3]。在文献[4]中,作者利用Twitter中蕴含的情感信息来对竞选结果进行预测。除此之外,在热点话题发现[5]、短文本分类[6]、虚拟社群挖掘[7]都是微博研究中的热点问题。
文本过滤是指依据一定的标准和运用一定的工具从大量的文本数据流中选取用户需要的信息或剔除用户不需要的信息的方法[8]。在微博文本过滤的研究方面,文献[9]对微博数据进行训练,利用半监督的机器学习支持向量机的方法发现微博上的噪音制造者。文献[10]提出了统计字符种类和最短编辑距离计算方法来判定Twitter中近似重复的消息。
虽然微博的研究目前已成为一个热点,但总体上,针对微博的文本过滤技术还处于起步阶段。中文微博考虑到“微博文本流”这一特点,以上过滤方法并不适用。因此,本文在分析了中文微博文本流中噪音微博和相似微博特点的基础上,提出了针对微博文本流的噪音判别和内容相似性双重检测的过滤方法,通过对微博数据实时抓取后再进行过滤,实现了保留高质量微博数据的目标。
2 中文微博客噪音文本、相似文本的特点
2.1 噪音微博文本的特点
目前针对微博的工作主要为舆情分析、观点挖掘等,因此我们将微博中对这类应用没有实际意义的微博数据定义为噪音微博,本文将其分为以下两类:广告型噪音微博和字符型噪音微博。
(1)广告型噪音微博
广告型噪音微博是指为达到宣传、增加点击率的目的而在微博客中有意加入的URL链接。为了分析该类噪音微博的特征,我们取不同时间段随机下载了1000条微博数据,并进行人工标注,统计发现其中噪音微博的覆盖率高达29.9%。进一步分析发现噪音微博中含有URL链接的信息约占85%,说明广告型噪音微博占有相当高的比例,同时说明了链接特征是广告型噪音微博最根本特点。噪音散布者通常利用链接的特性,人为地发表指向其他网站的链接,旨在宣传产品或者提升网站权威性。表1给出一些广告型噪音微博例子,其中都含有链接。
(2)字符型噪音微博
字符型噪音微博包括纯数字、纯英文等对中文微博分析和舆情分析无意义的字符型消息,以及用户分享视频、图片的文本保存形式,例如“分享图片”代表了用户在微博上分享的图片格式的文本保存信息。表2给出一些字符型噪音微博的例子。
我们分别统计了500条噪音微博和500条正常微博的文本字数,平均值为66和44,噪音文本的字数大于正常微博。图1显示了正常微博和噪音微博不同字数所占有的比率,噪音微博字数较为平均,长消息和短消息覆盖率相差不大,而普通用户发表的微博主要以少于40字的短消息为主,这是因为微博用户通常用简短的文字发表自己的观点和心情。图2显示了不同字数的正常微博和噪音微博消息中非汉字字符所占比率,发现噪音微博中所含有的无意义字符占有非常高的比率,例如在小于20字的噪音消息中,90%是非汉字字符,在这样的微博中通常只有URL链接的信息。同时我们统计了10万条微博信息的平均非汉字字符率,约为30%,而这500条噪音微博的平均字符率约为50%,因此本文将微博的字符率作为噪音微博判定的依据之一。
(3)噪音微博中的高频词
本文在人工标注的过程中发现噪音微博中大多含有URL,而在含有URL的噪音微博中用词相对集中,普通微博用词分散。这样,利用大量的含有URL的微博,可以找到噪音微博中的常用词。我们利用这一特点,从大量微博中提取出含有URL的微博消息作为训练集,对微博进行分词,去除停用词后作为噪音微博高频词的词库。统计发现词库中词的出现频率范围较大,本文保留了高于某一合适频率的词语作为高频词匹配词典。含有高频词的微博实例如表3所示。通过构建噪音微博高频词词典,累加高频词的频率计算权值,作为噪音微博判定的参考。同时,本文采用人工分析的方法修正了普通微博也会出现的高频词语,例如“微博”。
综上分析可见,噪音微博的3个主要特点是:(1)字符率较高;(2)URL较多;(3)噪音微博的高频词。其中(1)、(2)是显著特点,而(3)的检测则需要对内容进行分析,第3节将基于这3个特点检测噪音微博。
2.2 相似微博文本的特点
本文在对新浪微博平台的观察中发现,用户在发送消息时经常会复制别人的消息,或者直接转发好友的消息,或者经过少量的添加、删除、修改部分原始微博后作为新的消息再发送。同时,微博客空间内存在一定数量的“网络水军”,不断发布重复的微博数据。这些都是相似微博产生的原因,表4给出了一些例子。
可见,相同或相似微博本身并非噪音微博那样具有明显特点,只有通过内容相似性分析予以检测。
3 微博文本流中噪音微博和相似微博的过滤
我们利用API对微博进行实时抓取,首先基于噪音微博特征的判定方法,通过URL链接、字符率、高频词特征判别,过滤噪音微博。对文本进行预处理工作后,去掉微博本身特有的符号特征,然后基于VSM模型描述微博并采用向量夹角的余弦计算两微博间相似度,通过分段过滤和索引过滤的双重内容过滤,检测和剔除相似微博。第一重过滤基于时间分段,段内的微博之间进行相似度比较。第二重过滤时,考虑“微博文本流”的特点,将第一重过滤输出的微博集在缓冲池中构建索引,以提高搜索和比较的性能。微博文本流的过滤方法如图3所示。
3.1 基于特征判别的噪音微博检测与过滤
结合2.1节介绍的三个典型的噪音微博特征,即字符率较高、URL较多、以及噪音微博的高频词,首先以微博的字符率作为基础权值,对含有URL这种最为典型的噪音微博文本加上较高的权值,最后匹配高频词,本文对高频词的频率扩大了5倍。基于此,本文提出了算法1计算出微博的噪音权值,若大于所设定的阈值则过滤掉该条微博。
算法1 Spam microblog filter based on feature judgment
Input:microblogs mbs,spam weightβ,high frequency word lexicon HF,total thresholdθ;
Output:result without spam microblog result Set;
Method:
算法1中,第2)行是对字符率的处理,第3)行是对URL链接的处理,第6)~7)行是借助于2.1.3中所述的高频词典HF对高频词的处理。这三个特征的判别均以对β加权的形式统一到一个权重上,最后在第8)~9)行,判断该权重是否满足阈值θ,满足则视为噪音微博予以剔除。
3.2 特殊类型微博文本的预处理
微博中转发回复以及提到某一用户都有一定特征,系统会给消息加上一些固定模式的特殊字符(如//@),这类字符对转发回复消息的识别提供了可靠条件。微博中还包括“@”加上用户名,表示该微博是针对这一用户。由于本文仅考虑“原始消息”,在进行相似文本判断前对这类消息进行预处理,把特殊字符过滤掉。经过基于微博特殊规则的字符串匹配算法,使微博消息缩短,利于进一步的相似文本判断。预处理前后的微博文本对比如表5所示。
3.3 基于内容计算的相似微博双重检测与过滤
微博数据流属于海量数据,如果在整个数据集中去重,需要花费很多时间,也不能及时的得到处理结果,难以应用到实际中。而且,研究发现大量的转发微博更多地出现在相近时间里,重复率随着发表时间差距的增大而减小。为了证明这一规律,本文对各个时间段的总共800条话题微博计算重复率,利用VSM模型表达、向量夹角的余弦计算两条微博的相似值,该值高于所设阈值则定义为重复,重复率即为重复微博占段内总微博数的比例。如图4所示,在短时间内微博的重复率较高,随着相隔时间的加大,微博重复率迅速减少到很小值。
为了在尽量不降低召回率的前提下提高准确率,改善文本过滤性能,本文根据微博重复率随时间递减的特性,提出基于内容相似性计算的双重过滤法:首先对抓取的一个时间段内微博进行第一重过滤———分段过滤,再对相近时间发表的微博进行第二重过滤———索引过滤,达到微博文本流整体上的过滤,这样对发表时间相隔较短的微博去重,即能保证准确率,同时极大地减少处理时间,提高可用性。
(1)第一重内容过滤———分段过滤
首先,对噪音微博过滤以及文本预处理后的微博集分词,过滤停用词。然后构建向量空间模型,将每一条微博转换为一个文本向量,通过计算每两个文本向量的余弦值作为相似度,将相似度存在矩阵中,最后得到一个上三角相似度矩阵。遍历矩阵,查找相似的微博,如果相似值大于设定的阈值,则将其中一条过滤掉,如算法2所示。
算法2 Subsection-based similar microblogs filter
Input:microblogs subsection mbs,thresholdγ;
Output:result with less similar microblog in the subsection result Set;
Method:
(2)第二重内容过滤———索引过滤
经过算法2对微博进行一重过滤后,这里再对输出结果进行第二重过滤。本文使用索引查找相似微博的算法。首先构建一个微博缓冲池,存放最近发表的微博。由于微博的重复率随发表时间的递增而递减,因此本文只对最新一批微博构建索引。算法的基本原理如图5所示。图中的数据集经过了噪音微博过滤、微博预处理以及相似微博的一重过滤。图中(a)表示data5尚未加入缓冲池的状态,(b)表示data1数据集从缓冲池中移除后,data5加入缓冲池的状态。
算法3说明了将一重过滤后的微博集进行二重过滤的过程。首先对该微博集中的每一条进行分词处理,去除停用词。然后使用该条微博的分词结果集作为检索关键词,即可在构建的缓冲池索引中检索出最相关的一条微博。同样VSM模型表达、向量夹角的余弦计算两条微博的相似值。如果相似度值大于设定的阈值,则表示该微博与检索出的微博相似,过滤掉该微博。这样循环,对第一重过滤后的每一条微博再过滤后,将剩余微博集加入缓冲池进行更新,同时对缓冲池里的微博重新构建索引,该索引将作为下一批微博集进行二重过滤时所使用的新索引。
算法3 Index-based similar microblogs filter
Input:microblogs from first-level filter mbs,thresholdγ;
Output:result without similar microblog result Set;Method:
4 实验
4.1 实验数据与评价标准
目前在微博客过滤领域,尚无国际公认的标准测试语料库,本文从国内用户最多的新浪微博下载了公共大厅微博和话题微博作为实验数据源。本文的评价指标采用正确率(Precision)、召回率(Recall)及微F测度(F-score)来衡量算法性能的高低[11]。计算如式(1)、式(2)和式(3)所示。对于噪音微博分类,其中S为噪音微博分类算法检测为噪音微博结果中判断正确的数量,C是分类算法检测为噪音微博的数量,R是人工标注测试数据集中噪音微博的总数量。同样,对于相似微博过滤方法,其中S为相似微博检测算法检测为相似微博结果中判断正确的数量,C是算法检测为相似微博的数量,R是人工标注测试数据集中相似微博的总数量。实验中,程序找出的相似微博与人工标注的这组相似微博完全相同则为正确。
4.2 数据集大小对噪音微博过滤效果的影响
由于不同的数据集大小产生不同的噪音微博高频词,进而会影响到噪音微博过滤的效果,本文在阈值β为1的情况下,增加数据集的大小做了多组实验。首先从3000万微博中提取出含有URL的微博共700万作为总的噪音微博高频词训练集,然后取10万、50万、100万、200万、300万、400万、500万7组不同大小的数据集提取高频词,实验结果如图6所示,当数据量较小时,噪音高频词的覆盖面太窄,过滤效率不理想。随着数据量的增加,过滤的效率得到提升。但是当数据量足够大时,过滤的效率趋于平缓。当数据集选取100万时F值达到了峰值,本文选取这100万含有URL的数据集提取高频词,最终保留了含有5000词的噪音微博高频词词典。
4.3 噪音微博阈值β对判别性能的影响
在噪音微博判别算法中,判断是否为噪音微博的阈值β是一个很重要的参数,它会影响分类器的性能。本文标注了1000篇公共大厅微博作为检测噪音微博分类的数据集,利用上文确定的高频词词典,对该参数进行了多组实验。为了平衡准确率和召回率,以F值作为分类算法的评判标准,同时作为参数选取的标准。实验结果如图7所示,当β取值范围在0.8-1.0时,都取得了较好的分类效果;其中β在取值为0.9时,分类器具有最好的性能,此时F值达到峰值0.90,准确率P为0.84,召回率R为0.97。说明本文的判定方法能够较准确地过滤掉噪音微博,简单实用高效。由于阈值β的大小决定了分类效果,因此,若β取值过小,分类器则会过度拟合为噪音微博,从而导致分类准确率下降;若β取值过大,会导致分类的召回率下降。当β取0.9时,最好地平衡了准确率和召回率。
4.4 阈值γ和双重过滤对相似微博判断算法性能影响
在相似微博判断算法中,阈值γ也是一个很重要的参数,γ的取值将会影响过滤的性能。本文将经过了噪音微博过滤后人工发现的相似微博进行标注,其中含有大于或等于2个的多种相似微博,将标注的600多条相似微博加入不含相似微博的普通微博中,约2000条微博作为检测实验效果的数据集,针对不同参数进行了多组实验,同样以F值的大小作为算法的评判标准和参数选取标准。实验如图8所示,三条曲线分别表示进行双重过滤和仅第一重过滤、仅第二重过滤时F值的对比,其中双重过滤的算法性能明显较高,充分说明了本文提出的双重过滤法的必要性、准确性和实用性。双重过滤在γ等于0.5时F值取得最高值0.72,召回率为0.78,准确率为0.66,说明该算法判断较为准确、性能较高;当γ大于0.5的时候,F值开始出现下降现象。这是因为,随着γ的增加,被归类到相似微博的条件越高,被判为相似的文本越少,因此导致召回率大大下降。
4.5 相似微博双重过滤的时间性能
本文设计双重过滤法主要考虑到微博数据流属于海量数据,如果在整个数据集中进行去重,时间效率较低,难以达到实时应用的目的。因此本文首先对抓取的一个时间段内微博进行一重过滤,然后再对相近时间发表的微博进行二重过滤,达到微博文本流整体上的过滤目的。本文下载了2000条公共大厅微博,仅使用一重过滤处理的时间为90秒,使用二重过滤时处理时间仅为44秒,同时过滤掉了约20%的相似微博。实验说明本文提出的双重过滤法即能保证有效地过滤掉相似微博,同时极大地减少了处理时间,增加了处理效率。
5 结语
本文分析了中文微博数据的特点,针对其中的相似消息和噪音消息提出了一种面向微博客文本流的噪音判别与内容相似性双重检测的过滤方法。本方法实现效率较高,效果理想,实验证明了该方法能有效的对海量中文微博数据进行提纯,高效准确地过滤掉其中的噪音微博和相似微博,较好地保留下了高质量数据。同时该数据也可用于今后对微博数据的进一步分析,包括话题检测、情感倾向性分析等方面。
然而,这些工作尚需进一步深入和完善,主要包括以下几个方面:随着噪音微博的种类特征变化,还需根据新规则新特点进行过滤;在微博相似性计算方面可以选择其他更合理的方法进行比较。
参考文献
[1]Twitter[EB/OL].2011-3-16.http://twitter.com.
[2]Sakaki T,Okazaki M,Matsuo Y.Earthquake shakes Twitter users:real-time event detection by social sensors[C]//Proceedings of the 19th International Conference on World Wide Web,WWW2010,Ra-leigh,North Carolina,USA,April26-30,2010.ACM2010,2010:851-860.
[3]Weng J,Lim E,Jiang J,et al.TwitterRank:finding topic-sensitive influential twitterers[C]//Proceedings of the Third International Con-ference on Web Search and Web Data Mining,WSDM2010,New York,USA,February4-6,2010.ACM2010,2010:261-270.
[4]Tumasjan A,Sprenger T,Sandner P,et al.Predicting elections with Twitter:what140characters reveal about political sentiment[C]//Proceedings of the Fourth International Conference on Weblogs and So-cial Media,ICWSM2010,Washington,DC,USA,May23-26,2010.The AAAI Press2010,2010:178-185.
[5]Goorha S,Ungar L.Discovery of significant emerging trends[C]//Proceedings of the16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,Washington,DC,USA,July 25-28,2010.ACM2010,2010:57-64.
[6]Sriram B,Fuhry D,Demirbas M.Short text classification in Twitter to improve information filtering[C]//Proceeding of the33rd Interna-tional ACM SIGIR Conference on Research and Development in Infor-mation Retrieval,SIGIR2010,Geneva,Switzerland,July19-23,2010.ACM2010,2010:841-842.
[7]Kamath K,Caverlee J.Identifying hotspots on the real-time web[C]//Proceedings of the19th ACM Conference on Information and Knowl-edge Management,CIKM2010,Toronto,Ontario,Canada,October 26-30,2010.ACM2010,2010:1837-1840.
[8]黄晓斌.网络信息过滤原理与应用[M].北京:北京大学出版社,2005.
[9]Benevenuto F,Magno G.Detecting spammers on Twitter[EB/OL].http://ceas.cc/2010/papers/Paper%2021.pdf.
[10]曹鹏,李静远.Twitter中近似重复的消息的判定方法研究[J].中文信息学报,2011,25(1):20-27.
高程图数据相似检测及其并行算法 篇6
关键词：相似检测,曲面插值,并行算法,C语言,绘图
高程数据文件给定了横纵坐标x、y及相应点的高程z,设A、B是程序的两个输入文件,B为网格化的大图,A是B的局部,A通过实际测量得到,两组数据中x、y坐标是不一致的,需要通过比较二者对应的地形起伏,检测相似程度,求出两组数据图高程差最小即最吻合时的坐标差,从而校正A或B的坐标。程序首先读出数据,因数据量太大,用Matlab不便于处理,选用C语言用动态分配存储空间的方法,通过指针操作数据。程序中需画数据图,粗略选取比较区域,作者选用了简单的Windows绘图功能,未用复杂的MFC,以达到快捷简便,提高可移植性的目的。
检测方法为,以B的高程数据为插值节点,在B图上某区域选出一点为起始点,对应A的起始点,按A的所有数据的坐标间距,作为所求插值点,通过曲面插值算法,求出各插值点的高程,设为C。比较A与C的相似度,即通过A与C对应点高程差的绝对值和来量化相似程度。在选定区域搜索最佳起始点,并不断缩小搜索区域和步长,找到绝对值和最小的对应起始点,即可算出所求坐标差。
程序中编写了一些辅助函数来估算数据及运算量的大小,通过绘图等人工干预的方法修改一些参数来提高搜索效率。确定大致的搜索区域后,如果步长缩小,曲面插值及相似比较的运算量也是很大的,又给出基于MPI的并行算法,提高了运算速度。
1 数据结构的选定
数据文件中一般存放3列数据,x、y、z,对于等距网格高程数据,程序读取文件可转换为仅存x、y起始值及一对网格间距值,所有z值存放到动态分配的一维数组,这样可节约存储空间并提高运算效率。所以选用如下定义的结构类型存储A、B、C的数据,sx、sy为起始点即图的最左上一点的坐标,wx、wy为经纬向网格间距,M、N为网格数量,也相当于数据矩阵的行、列数,pd指向顺序存储的高程值z。
首先通过辅助程序分析数据,并进行必要的整理,确定A、B的sx、sy、wx、wy、M、N等值,C的大小等同A,定义全局变量A、B、C并分配好高程值z的存储空间,读取数据并转换,程序如下:
2 程序流程及数据绘图
程序采用最简单的Windows编程结构,主函数Win Main()中建立显示一个窗口,并开始消息循环。在消息处理函数Wnd Proc()中通过按下字符键的消息WM_CHAR,选择调用读数、计算等各函数模块,在WM_PAINT消息下绘出通用的高程色标及提示信息。
操作流程一般为:先如上所述整理和读取数据,确定所搜区域的起始点和步长,建立二维数组FMin[][];调用曲面插值函数,由数据B算出C,再对A和C高程差绝对值求和,存入FMin,同时找出最小值。主要程序如下:
在某区域计算出一组数据后,根据需要,可通过发送按键消息,调用绘图函数,再确定新的搜索起点和步长,直至找到最佳位置。
其中,绘图用画点函数Set Pixel(),如图1~图3所示,高程h和颜色的对应关系用如下函数:
3 曲面插值算法
算法采用矩形域上分片双一次插值,计算公式如下:
其中τ、h为网格宽度,pij(x,y)是1,x,y,xy 4个函数的线性组合。插值曲面p(x,y)在整个区域上连续。相应代码如下:
4 并行算法
为了提高运算速度,采用基于MPI的并行程序在Linux环境下来计算,本问题数据传输不频繁,而运算量大,很适合并行计算。先预设搜索起始点值,对搜索区域按从进程数划块,交给各个从进程计算,各从进程计算分配给自己的区域后返回最小值及坐标点位,主进程接收各个最小值后再进行比较得出结果。程序中主进程通过MPI_Send()函数发送各块起始点纵坐标,接收数据用MPI_Recv()函数。通过MPI_Reduce()函数并设置MPI_MIN参数可归约由从进程送来的值,得到最小值,主程序代码如下。
编译和运行命令如下:
mpicxx-o kj AD kj ADmpi.cpp
mpiexec-n 8./kj AD
5 结语
以上并行程序通过输出运行时间的代码进行了测试,证明在实践中是有效的,并行运算速度跟进程数及CPU内核数有关。另外,在实际应用中,如果测量所得数据不全,需要先通过插值网格化再进行相似检测计算。如果是稀疏的数据,也可改变数据结构,通过指针取测量点的坐标和高程,由网格化的大图做插值后求高程差的绝对值和来检测。
参考文献
[1]黄友谦,李岳生.数值逼近[M].北京:高等教育出版社,1987.
相似性检测 篇7
在这个海量信息充斥的时代,信息的重复也随之增多,而其中一些相似文本的出现不仅不能丰富信息的价值,反而造成资源的浪费。因此,如何在大规模数据中快速检测出这些相似的文档是一项十分重要的技术。目前,国内、外在该领域的检测手段普遍都采用将文本哈希成数字指纹的技术。特别是Simhash算法,由于其检测准确率高,“降维”的思想使得检测速度快,同时还可以根据指纹距离反映文本内容的差异程度,因此受到广泛的应用。但由于中文语义的复杂性,包括同义词,一词多义等问题,现有Simhash算法对于不同文档采用同义词作为关键字的相似检测性能并不是很理想。例如,两篇文档的关键词分别为:大规模、文档、去重、技术和海量、文本、查重、算法。
基于上述原因,本文在现有Simhash算法的基础上,通过对其进行改进,提出一种基于同义词扩展编码的语义指纹生成方法,实现海量文本的快速相似检测。该方法利用基于同义词词典的语义扩展编码,通过Simhash函数映射生成固定长度的语义指纹,解决了其中普通哈希函数无法进行语义表达的问题,扩展了指纹的表达能力,提升了检测准确率。再根据指纹信息进行分段索引建立,减少了比对过程中的冗余操作,提高整体检测效率。通过实验验证,该算法在海量文本相似检测过程中性能良好,其快速匹配机制也满足了大数据环境下的检测需求。
2 相关工作
2.1 Simhash算法
Simhash算法在2002年由Charikar[1]提出,后由Manku对其进行扩展研究,被认为是当前文本相似检测处理中最有效的算法之一[2]。Simhash算法实质上是一种具有局部敏感特征的哈希算法,它能够将文本内容特征向量映射到一个指定维度的二进制比特向量上,并由这个二进制哈希值来表示文本内容的数字指纹(Digital Fingerprint)。区别于其他哈希算法,Simhash不仅在保证低碰撞率的条件下通过哈希映射将原本不同的文本内容映射到不同的哈希空间中,同时还能通过比特位数的不同体现两个比较文本的相似性,这也正是其局部敏感特性的体现。根据局部敏感哈希算法(Local Sensitive Hashing,LSH)的基本思想[3],两篇文本p,q相似的可能性与其距离呈负相关关系,即它们之间的距离越小,相似的可能性就越高,反之,则相似的可能性就越低。这里我们定义Simhash函数h,则映射后h(p),h(q)与其距离的关系满足以下两个局部敏感性质(公式1):
这里参数c>1,概率P1>P2,p与q的距离也就是我们所需计算的文本相似度,h(p),h(q)的距离由二者的汉明距离来确定。两篇文档的相似性计算经过哈希映射后,转化为两篇文本的指纹值汉明距离计算。
基于Simhash的相似文本检测需要经过文本特征提取、指纹生成和指纹索引匹配三个数据处理过程。首先,算法以经过分词的文档词项作为文档的特征,其对应的频率作为每个特征的权值wi。通过普通的hash函数计算得到每个分词的一个f位的二进制哈希值,再将所有特征的哈希值加权累加,得到一个同样为f位的总向量V,根据V中各位的符号生成文档的数字指纹F。最后根据指纹的索引值指纹库中进行比对,找到满足一定条件的其他指纹作为相似比对结果。
2.2 同义词词林
在信息检索领域,将关键词进行同义词扩展实现模糊检索,这类方案目前已有一定研究[4,5,6]一般地,通过同义词挖掘算法事先建立同义词词库,再运用该词库对检索关键词进行语义扩展,生成一个扩展关键词集合。在检索时,根据集合内的关键词生成索引,依据索引进行查询比对。在本文中,需要对关键词的语义进行同义词概念的扩展,把从属于某一概念下的同义词和关联词均划归到该概念下的集合中,并以该集合的编码作为语义编码返回处理。
同义词的扩展是以同义词词典作为基础进行操作,而“同义词词林”作为其中一个具有代表性的中文词典,在中文自然语言处理领域受到广泛关注。在词林中,将所有词汇按照树状结构分层地组织到其中,树中的每个结点代表一个概念域。自顶向下整个词林树共有5层,依次对应1到2个编码进行标识,将各个标识排列后就形成词元的编码。词林的层次与其分类相对应,而分类的原则是依据汉语语言特点,以词义为主,兼顾词类,充分体现词义的聚集。
同义词词林依据“词义为主,兼顾词类”的原则,结合汉语语言本身的特点及其使用规则将收录的所有词语划分为三个等级:其中大类共12个,中类94个,小类多达1428个。再向下根据词义集中的原则划分成3925个词群并排列,每个词群对应一个标题词。最后按照以下三个原则划分成最小的子群:一、词义的细微差别;二、修辞色彩与使用范围的不同;三、词语结构的差异。其中第一个是主要的。
3 基于语义指纹的快速相似检测算法
本文提出的文本相似检测算法主要是基于经典的Simhash算法,而其主体思想是“降维”,通过将高维的文本特征向量映射成一个唯一的二进制指纹值,从而达到减少文本表示空间的作用。不同于其他指纹生成算法,Simhash算法可以将两篇相似的文本映射到一个距离相对较近的低维特征空间中,通过在该空间中距离的大小判别两个文本向量的相似程度。但由于中文语义的复杂性,包括同义词,一词多义等问题,现有Simhash算法对于不同文档采用同义词作为关键字的相似检测性能并不是很理想。例如,两篇文档的关键词分别为:大规模、文档、去重、技术和海量、文本、查重、算法。基于上述原因,本课题在现有Simhash指纹生成算法的基础上,通过对其进行改进,提出一种基于同义词扩展编码的语义指纹生成方法。语义指纹的生成流程如图1所示。
文本最终的语义指纹值是基于离散化的文本特征提取的结果,数据指纹间的汉明距离越接近,则代表文本的语义越相似。根据同义词词林在词语组织上的层次架构,对待文本中的关键词进行定位标识,在词林层级结构树中找到该关键词所有义项所属的层次,考虑到一词多义的情况,一个词的不同义项间可能差距较大,因此根据其上下文信息进行筛选,取最大概率的词项所属词群编码进行扩展。概率判定的指标主要基于该词与其上下文词汇的互信息。
一般地,在应用Simhash算法时,将划分出的词语作为文本的基本特征,再结合每一个词语的词频作为其权重。考虑到本课题算法中,文本块的划分以句子为单位,而各个单词在一句话中出现的频率区分度并不会很大,因此在本课题中特征的权值采用另一个指标——单词的词性。从词性角度来说,名词表征着文档更多的特征,因此其权重应该最高,动词次之,形容词再次之,其余词权重最低。
根据文本的特征向量信息生成文本语义指纹的算法如下:
输入:一个64维特征向量V={w1,w2…,wn},其中w1,w2,…,wn分别是文本关键词特征,其对应相对值分别为we1,we2,……wen;
输出:一个64位的二进制语义指纹F={f1,f2,…,fb};
1)初始化一组64位的二进制向量,其中一个向量F作为文本的语义指纹,其他向量用来存储关键词对应的同义词扩展词群编码;
2)将各个关键词在同义词词林中找到对应多个词项,并根据与前一个词以及后一个词互信息(公式2),计算该词汇对应的词群编码,并转换成64位二进制hash值;
3)根据关键词各位的hash值以及其标注词性的权重进行调整。如果第i位为1,则将该词hash值的第i位置为权值,如果为0,则将该位置为负权值;
4)将所有词向量的对应位进行求和运算,结果向量记为F’;
5)按照向量F’各个位的正负确定语义指纹F的数值:如果F’第i位为正,则指纹F的第i位置为1,反之,则置对应位为0。
这样,就得到了经过同义词扩展后的文本特征hash值的加权综合结果。
4 实验验证
4.1 实验数据及工具
由于汉语中没有句子相似度检索用的标准测试数据集,因此本实验的数据是通过从搜狗语料库网页数据中进行处理得到。实验所用语料为标准中文数据集SOGOU-T,从中选取800篇文档作为基础数据集,经过本课题语义指纹生成算法处理后形成指纹存入数据库中,作为相似检测依据。测试文档集中,其中一部分从基础数据集中选取200篇,并作不同种类的修改,构成论文相似目标数据集。通过将本文算法和其他算法,包括经典的词频统计算法,未改进的simhash算法进行比较。
文本处理过程中,采用ICTALAS中文分词系统实现,该系统采用层叠隐马模型,该工具具有160万字/秒的高速处理能力,同时支持外文字母以及数字等的分词处理和用户自定义词典的扩展,目前共收录有392755个词汇。
4.2 评价标准
本文采用传统的准确率、召回率两个关键指标来对本文提出的算法进行性能评价。假设在进行文本相似性检测的实验结果如表1所列,则其各参数的定义如下:
准确率:被检测相似句子中实际相似句子所占的比例,衡量的是查准率;
召回率:实际相似句子中被检测出的比例,衡量的是查全率;
4.3 实验结果分析
通过上述流程介绍,下面进行实验,对本文提出的相似度检测算法进行验证。实验运行环境是CPU为Intel(R)i53210.2.50GHz,内存4GB,操作系统为windows8.1 64bit,采用Java语言实现算法,并在My Eclipse上运行。
首先对算法运行情况进行分析。从整体流程上看,本文采用的相似检测方法可以分为个主要步骤:文本的语句划分及分词处理、构建特征向量、文本语义指纹生成、指纹对比计算四个过程。
如图2、图3所示,本文算法的经过加入同义词替换等处理的测试文本,文本的准确率和召回率都达到80%以上。而相比之下,传统simhash算法和词频统计算法的两项指标都只有70%左右,通过图2曲线的比较可以很直观地发现本文算法在语义识别上准确率有很大提升。同时,由于简化传统simhash算法根据Tfidf来计算关键词相对值的过程,本文算法在计算速度上也有一定提高,这与理论预期结果相一致。
5 结束语
针对传统的Simhash算法无法处理中文文本信息中一词多义、同义词等语义问题,本文提出一种基于同义词扩展词群编码的语义指纹改进算法,利用同义词词林中的语义项层次结构关系,对检测文本中关键词进行语义词群的扩展,利用词群中的关系信息来融合不同的同义词,再通过基于词性对关键词权值的确定,生成具有语义信息的语义指纹。经过与Simhash算法以及词频统计算法进行比对研究,实验表明,本文中的算法能对相似文本实现快速去重,而且能够保持较高的准确率、召回率以及F1值,弥补了其他算法在文本语义表达方面的不足,特别针对同义词替换的情况。同时,在时间效率上,本文提出的算法相比原始simhash算法,节省了大量无意义的比较计算处理,总体上提高了检测效率。
今后的研究目标是完善语料库,不断改进文本相似检测算法,不仅考虑到词汇对相似度计算的影响,同时挖掘更复杂情况如词汇组合、语句结构修改等方面的检测算法,力求在文本相似度计算中达到更高的准确度。
参考文献
[1]Moses S.Charikar.Similarity Estimation Techniques fromRoundings Algorithms[R].ACM STOC`02.May,2002:19-21.
[2]Sadowski C,Levin G.Simhash:Hash-based similarity detec-tion[R].Technical report,Google,2007.
[3]Datar M,Immorlica N,Indyk P,et al.Locality sensitive hash-ing scheme based on p-stable distributions[R].In Proceedingsof the ACM Symposium on Computational Geometry.2004.23-36.
[4]田久乐,赵蔚.基于同义词词林的词语相似度计算方法[J].吉林大学学报:信息科学版,2012,28(6):602-608.
[5]张继东,刘萍.基于语料库同义词辨析的一般方法[J].解放军外国语学院学报,2005,28(6):49-52.
相似性检测 篇8
引起HTTP-Get Flood攻击种类:
1) 页面刷新类攻击。频繁按F5键刷新网页会向服务器提交大量Get请求报文,导致HTTP服务器过载。这种攻击强度、攻击频率、持续时间长短因人而定。
2) 静态类型。这种攻击通过设定的程序自动执行,攻击参数可以设定。常有的攻击参数有目标IP地址、目标URL、攻击频率。
3) 动态类型。攻击者动态修改攻击参数,使攻击产生变化的效果。
1 相关研究
攻击者通过傀儡机或者多线程向目标Web发送大量的HTTP请求,这些请求可以随机生成,也可以通过拦截用户的正常请求序列后产生。从内容上看,攻击者对服务器的请求与合法用户的请求完全相同,基于数据包特征串检测很难发现到异常[1],而且特征串提取过程复杂,实时性不高。通过大量肉机向目标服务器发送海量分组的攻击并不是HTTP-Get Flood攻击的唯一手段,它可以通过低速的请求、动态变化的攻击参数隐藏自己,这样基于访问频率的检测[2]将无法可依。李敏提出用多分支的隐马尔科夫模型来分析Web页面访问行为[3],以区分正常数据和异常数据。这种检测方法对训练数据的纯洁度和数据量都要求很高,学习过程复杂,计算量十分庞大,况且数学估计本身就存在误差。通过分析Web服务器上的用户行为日志辨别异常[4]的方法缺乏主动性,不能从主干流量监控层面去实施。本文根据僵尸网络爆发的集中性,行为高度相似性等特点,提出了基于用户访问行为相似度鉴别异常的Web页面访问行为。
2 检测方法及其实现步骤
僵尸主机都是按照预定的程序运行,僵尸主机的行为在网络上的表现具有相似性,如果一组流量群体行为同步性以及聚类系数都在检测系统设定的阈值范围之内,且其目的服务器的可信度低,则认为此组流量是僵尸网络命令控制流量。无论是集中式还是分布式僵尸网络,同一僵尸网络中,僵尸主机之间具有相似的通信模式和行为特征,因此其网络流量具有较高的相似性,通过聚类技术搜索这种相似性,可以有效检测僵尸流量。僵尸网络控制发动的HTTP-Get Flood攻击时,攻击时间几乎吻合,访问Web页面的次序完全一致,持续的时间也高度相似。而用户对Web网页的访问行为在时空方面存在巨大差异,不同人访问Web页面的次序、点击Web网页的频率、在Web网页停留的时间都不相同。同一时间段内大量用户上述行为完全一致的情况很难发生,只能是僵尸主机操纵多台肉机进行群体攻击时肉机行为才能高度一致。正常人的反应时间一般都不超过0.1 s[5],当某个用户浏览行为切换得非常高时,也有可能是既定程序执行的操作。
2.1 HTTP-Get Flood攻击检测原理
Web网页的点击行为往往包含一个对主页的请求和若干个对网页内嵌对象的请求,用户点击产生的Get请求是对动态页面请求,动态的Web内容需要服务器执行脚本程序,也就是包含一次或多次的数据库查询,而内嵌的对象或静态页面是静态文件,由服务器直接响应的(动态页面的Get请求包的URL通常包含.asp,.jsp,.php,.asp,.net,.cgi等字符)。基于HTTP-Get Flood攻击就是对动态页面进行高频访问,让服务器应接不暇直至崩溃,而它对静态页面攻击几乎无效。动态页面Get请求包中的URL信息表示用户要浏览的资源地址,相邻两个动态Get请求间隔时间反应了用户在两个页面之间的切换时间。如图1所示,将动态页面Get请求包中的URL定义为不同的状态,以阿拉伯数字将每种状态进行编号,相同字符串的URL编号相同,相邻两个动态页面Get包的间隔时间T为跳转时间,公式P=(A-B)/T反应Web页面切换率(A与B为相邻状态)。
考虑到人的反应速度很少能达到0.1 s,T精确到小数点后一位。认为那些跳转时间小于0.1 s的切换是机器执行的动作,统一按0.1 s计算。不同用户流量页面的路径或许相同,但浏览停留时间却千差万别,即使一些人的浏览路径、转换时间高度相似,但同一时刻内多个用户浏览行为相似的概率是很小的,一定时间内P值相同的概率非常低。同一指令下被控肉机浏览页面的路径肯定是一样的,假设肉机同时收到攻击命令,排除线路拥塞等情况,攻击报文到达Web服务器的时间应该十分接近,时间偏差很少能超过0.1 s。这样受僵尸网络控制的肉机在同一时刻内的切换率P相等的概率非常之高。为了区别不同时刻的切换率,将P乘以第2个状态到来的时间S(精确到秒),这样公式Q=(A-B)×S/T就能唯一地表示S时刻内某个用户浏览行为,利用上述公式计算得到的Q值定义为行为活动值。即使多个用户同一时间段对Web服务器的访问路径相同,但浏览的时间不一定相同,而且切换时刻也不都相同,通过上述公式计算得到的行为活动值相等的概率非常低,而HTTP-Get Flood发送时浏览路径高度一致,切换时间几乎一样,发动攻击的时刻也会相同,通过上述公式计算的行为活动值相等的概率很高。某一时刻内多个行为活动值重复次数非常多,很可能Web服务器受到了HTTP-Get Flood 攻击。图2所示为某台受攻击Web服务器日志数据计算后时刻6内Q值分布情况,从图可知,时刻6内最黑点反应浏览行为高度重叠。
一段时间H内行为活动值Q的个数N反应这一时刻内切换行为总数。时间粒度H中去除重复Q值后剩下的个数记为M, K=N-M表示行为活动值相互重叠的个数。公式L=k/N反应时间粒度H内的重复率,这里将L定义为行为相似度,当行为相似度超过一定阈值时,认为此时刻内的浏览行为高度一致,疑似遭受到DDOS攻击。Web服务器的承受能力千差万别,很难有一个统一的标准。服务器在时间粒度内最多允许的访问量记为S,服务器最高允许同时访问的量为P,阈值一般要大于P/S,这样可以保证在某个时刻击瘫服务器。
2.2 HTTP-Get Flood行为相似度检测算法实现步骤
算法实现流程如图3所示。
1) 建立足够槽位的哈希表,每一个哈希节点表示一个Web服务器,以Web服务器的IP地址作为哈希节点键值。
2) 截获80,8080,43等HTTP业务数据的Get包,将动态页面Get数据包按目的IP地址映射到相应的哈希节点中,提取包中的URL信息、截获时间和源IP地址。利用基于状态机的变种AC算法[6]为URL编号,此编号即为状态号,按IP地址分类,将截获的信息存放到map结构体中。用公式Q=(A-B)×S/T计算源IP的行为活动值(如果IP中没有存放状态和时间信息,将新截获的信息存放其中),为Q值打上时刻标签。
3) 将同一个哈希节点中一定时间间隔内的N个Q值映射到hash_map计算频度。相同Q值被映射到同一个节点,这样hash_map的节点个数就是去掉重复后的Q值个数,记为M。用公式L=(N-M)/N计算行为相似度,超过阈值(V)判定这个时刻遭受攻击。
4) 将检测到的异常结果写入日志。
3 实验结果分析
3.1 实验数据选取
下载公开的Trace[7],该数据集包含了大约一个小时匿名的HTTP-Get Flood攻击数据。该攻击是控制多台肉机变换的请求Web服务器中的多个资源。以5 s为一个时间粒度检测行为相似度,根据经验阈值设定为40%。
3.2 实验结果
如图4所示为截取自Get Flood攻击频繁时期40 s内的行为相似度分布情况,从图中可知攻击不是持续不断的,而是一波波进行。图中横黑线为阈值线,黑点表示浏览行为相似度,超过阈值的点判断为疑似DDOS攻击。基于用户浏览行为相似性判断异常可以检测出那些攻击参数不断变化的HTTP-Get Flood。单位时间内某个IP多次访问同一个URL界定异常是不足的,因为僵尸主机可以通过控制多台主机同时对Web服务器发动短时攻击,而且控制指令指定的URL信息可以不断变化,统计得到某个IP访问同一个URL的次数或许达不到阈值。虽然单个IP浏览行为可以不断变化,但受同一指令控制的肉机在某个时刻内的浏览行为几乎是完全一致的,利用行为相似性分析HTTP-Get Flood 攻击更准确。图4高于阈值线的行为相似度点离散分布就是本算法对DDOS攻击的分布式特性免疫的伪证,表明本算法可以在分布式HTTP-Get Flood攻击中很好地揭示其发生的时间段。
4 总结
针对HTTP-Get Flood攻击检测,本文使用用户浏览行为相似度描述用户访问Web页面的特征。可以检测出改变参数的攻击,相比利用隐马尔科夫建模预测用户浏览行为,此方法更加简单,实时性更高。后期将重点研究如何追查攻击源和僵尸控制主机信息,从源头扼住异常行为。
参考文献
[1]WANG H N,ZHANG D L,SHIN K G.Detecting SYN flooding attacks[C]//Proc.the 21st Annual Joint Conf.IEEE Computer and Communi-cations Societies.[S.l.]:IEEE Press,2002:1530-1539.
[2]XIE Y,YU S Z.Anomaly detection based on Web users,browsing behav-iors[J].Journal of Software,2007,18(4):967-977.
[3] LI Ming.HTTP-Get flood attack detection method based on user access behavior[J].Journal of BeiHua University,2011,12(1):120-122.
[4]LI Ming.The Http-flood detection methods based on user browsing be-havior[J].Compter Safer,2010(2):61-63.
[5] YU Ge,YU Xiaocong,DONG Xiaomei,et al.Rapid detection technique for P2P-base botnets[J].Journal of Northeastern University,2010,31(12):1709-1712.
[6] CHENG Qilian,DOU Rongbin,LI Hongming,et al. On the speed barrier of human beings--firstly uncover the recipe of Jamaican athlete usain bolt,the creator of sprint world’s record[J].Journal of Jiangxi Normal University,2009,33(3):376-378.
相似性检测 篇9
虽然对目标检测的研究过程中有许多问题,但是目前较为流行和比较常用的方法主要有帧间差分法、光流法、背景差法。帧间差分法适用条件是存在很多运动目标和移动的监视器,并且是应用作差分运算对排列的视频图像分析最终得到运动目标轮廓的原理。基本思想是将相邻两帧图像做差分运算,将差值大于某一阈值的部分判为运动目标,其他部分判为背景。三帧差分法的优点是充分考虑了运动像素的时间相关性,融合了多帧图像的像素信息,可用于动态变化的场景,且该方法对运动检测比较灵敏,对随机噪声有很强的抑制作用,但也存在一定的缺陷,如检测到的运动目标会存在多检或者少检。 针对这个缺点,本文提出一种将三侦差分法和相似梯度相组合来进行检测,动态场景的运动目标检测算法的研究是当今图像处理与图像理解领域的一个热门方向, 也是未来视频处理的发展方向,受到当前图像界以及人工智能领域专家的极大重视。
1三帧差法的基本原理
三帧差法的公式的基本步骤是:第一,将相连的三张图片进行平滑去噪处理;第二,对三张图片分别进行帧差法处理,也就是用下一张图片减去上一张,分别用第k帧图片减去第k-1帧图片,再用第k=1帧图片减去第k帧图片,最终得到两个值,即D1(x,y)、D2(x,y) ;第三,将得到的这两个值进行或运算,就会顺其自然的得到我们想要的检测结果了。公式表示为:
2基于相似梯度的边缘连接算法
作为图像最基础的特征,图像边缘囊括了轮廓、位置、集合等相关信息,具体图像内容显现为屋顶变化或是阶跃变化的成像,提供是特征参数来解释图像和识别目标。
2.1边缘检测
边缘检测的基本思想旨在凸显图像的局部边缘,首先确定图像中的边缘强度,建立门限的方法来获取边缘点。本篇文章恰恰利用边缘检测来得到结果的,作为高斯函数的一阶导数,边缘检测器是将信噪比和定位做乘法运算逐渐取最接近算子,笔者认为正确的边缘检测有一下几方面的特征:(1)真实的边缘点上没有出现低概率的标记;(2)获得的边缘点无限接近真实的边缘中心;(3)单个数值很好地适应了边缘响应。
2.2边缘连接
在图像处理中,假如获得的图像优良,并且没有其它音质影响,边缘点最接近中心边缘的,边缘检测最大的优点就真正发挥出来了。可是现实情况也不完全一样,大部分的边缘检测结果不必要对图像进行再次处理。
2.3一种基于相似梯度的边缘连接算法
边缘检测的思想可以用于边缘算法的连接对于这种创新的思路我们可以解决很多问题,需要要用到图像像素的梯度值。
二维函数f(x，y)的一阶导数 ( 也就是梯度 ) 定义的向量形式为 :
该梯度向量的幅值为:
便于计算分析,对于公式(5)进行忽略平方根的方法:
或选择去近似绝对值的方法 :
梯度是在坐标位置的最明显变化方向,在最大变化方向出现的最大角度:
算法的假设思想是把边缘点看作是图像中的某些特殊重要点,在这些特殊的点区域内分析出梯度改变方向及图像像素相同的点,这样就是巧妙的运用上了边缘检测原理。
具体实验的操作过程为:
(1):对特殊点坐标进行变换边缘检测得到图像二值;
(2):赋予一个特殊的二值坐标图C(x,y),并且二值图像C(x,y) 的大小和B(x,y) 相同,并做C(x,y)=B(x,y) 操作;
(3):对二值图像B(x,y) 的的任意一点进行边缘查询,同时对其上下左右的点进行梯度定值分析;
(4):把结果(3)中的所有梯度点进行边缘连接得到最终的结果。
通过对阈值的分析判别进而得到梯度的相似性,首先对一个阈值T进行重新定义赋值重置,根据不同梯度下计算得出的阈值T的大小分析出图像的边缘特性, 梯度值是决定图像相似性的重要因素。
3实验仿真与分析
本文采用的实验平台为奔腾处理器, 1G内存,512M显存的计算机,用matlab R2009a编程实现。实验采用图像均为大小为256× 256的8bits灰度图像。实验分析可知图5是对图3的第13帧图像进行边缘扫描,结果如图5所示。再利用本文方法对边缘检测的结果进行边缘连接,最后边缘检测结果为图6。
对连续的第12、13、14帧图像做三帧差检测,并做过腐蚀和膨胀处理,然后从该结果中分析出边缘最大范围, 接着进行三帧差法连接设置增加边界条件息。
加入边缘分析处理后的检测结果与直接用三帧法的检测结果相比,可以看出目标显得更充实,目标区域的空洞明显减少了,目标显得相对完整,弥补了帧差法检测的区域漏检问题。
4结语
动态场景的视频图像序列的运动目标检测一直是计算机视觉、数字视频与图像处理和模式识别领域中一个重要的基础研究课题, 是目标跟踪识别与目标行为分析和理解的基础环节。随着成像设备的快速发展,计算机性能的迅速提高以及技术系统的无人化趋势发展,动态场景下的运动目标检测在将来的工业、智能交通、空间技术和国防军事等领域有着广阔的应用前景,然而至今仍然存在很多关键的问题尚未解决, 特别是当摄像机运动较复杂时, 如摄像机发生往返运动,摄像机的运动速度较大,或者摄像机运动方向复杂变化等,运动目标的检测将变得更加困难,本文通过角点检测及跟踪确定图像中的角点,再将检测出的角点进行分类以提取出属于目标的角点,最后利用等周分割方法进行初始分割,并结合目标点集的坐标信息在初始分割图像中提取出目标区域。目标角点检测的数量对目标提取的区域定位有重要的影响,属于目标身上的角点越多,定位越准确,提取出的目标越完整。
图2 第 12 帧图像
图3 第 13 帧图像
图4 第 14 帧图像
图5 第 13 帧图像边缘检测
图6 基于相似梯度的边缘连接结果
图7 三帧差法检测结果