检测序列（精选7篇）
检测序列 篇1
直接序列扩频是在第三代移动通信系统中被广泛应用的一种多址技术, 其最早是在军事通信领域为了抗干扰而诞生并且得到广泛研究的, 它的主要原理是利用信号的正交性原理, 通过相互正交或准正交的扩频码 (Spreading Code) , 以及不同形状的码片 (CHIPS) 构建相互正交或准正交的特征信号 (Signature Waveform) , 用来作为各个用户数字信息的载体。CDMA信号中不同用户的信息相互叠加, 占据相同的信号带宽。如果用户扩频码之间不能严格正交, 则会引起用户间相互干扰, 即“多址干扰MAI”, 这也是CDMA系统的自干扰特性。随着用户数增多, MAI将增大, 接收机的误码率性能也会随之变差。多用户检测是一种从接收端设计入手的干扰抑制方法, 主要作用是从各个用户信息相互叠加的信号中可靠地解调出部分或全部用户的信息。多用户检测技术是消除多址干扰, 提高系统性能的有效方法。
1 最优多用户检测算法 (ML)
不确定性最优多用户检测算法是1986年Verdu提出的最大似然 (ML) 多用户检测算法。对于同步CDMA系统, 接收信号的最佳解调向量如下表示:
对于CDMA系统中同时传送信息的K个用户来说, 每个用户传送信息bk的取值有+1和-1两种可能, 向量B=[b 1, b 2, , ......b K]T的组合有2K种, 这种算法的目的就是要从种组合的用户信息向量中找出一种使似然函数最大的输出信息向量。使用该算法时, 用户每发送一个比特信息, 该算法的复杂度为O (2K) 。实际的CDMA系统具有相当庞大的活动用户数量, 该算法的复杂度随用户数量的增加呈指数上涨, 实际的系统中该算法运算的复杂度会使得系统难以忍受。
2 解相关多用户检测算法 (DEC)
多址干扰是由于不同用户的扩频码不能完全正交引起的。抑制多址干扰的影响, 去除所有用户扩频码之间的相关性, 是解相关检测的基本思想。
考虑离散CDMA信号模型。
第一步, 用转置后的扩频码集矩阵S左乘信号Y得到匹配信号Z。
其中R=SST, 叫做相关矩阵, 第一步的处理实质上就是对每个用户进行匹配的单用户检测。
第二步, 对相关矩阵R求逆, 得到R-1。
第三步, 用R-1左乘第一步中得到的匹配信号z, 并对结果进行判决。
由于需要计算相关矩阵的逆矩阵, 使得解相关多用户检测算法的计算复杂度达到了O (k3) 。
3 最小均方多用户检测算法 (MMSE)
最小均方 (MMSE) 多用户检测算法同时考虑了背景噪声和多址干扰, 该多用户检测算法的实质是使发送的信息与检测输出数据的均方误差最小, 即代价函数E[B-TY2]最小, 其检测过程如下。
其中R=SST为相关矩阵, A为振幅矩阵, ∂2为高斯白噪声的方差。将线性变换矩阵与匹配滤波器组输出向量相乘得到最小均方误差检测器输出, 再对此输出进行判决。
和解相关多用户检测一样最小均方多用户检测算法也需要计算相关矩阵的逆, 在运算复杂度上相对解相关多用户检测算法没有改变。
参考文献
[1]Verdu S.Multiuser detection[M].Cambridge University Press, 1 99 8.
[2]R.Kohno, M.Hatori, H.Imai.Cancellation technique of co-channel interference in asynchronous spread spectrum mul-tiple access systems[J].Elect.And Comma.In Japan, 1983, 66:20～29.
[3]Z.Xie, R.T.Short, C.K.Rushforth.A family of suboptimumdetectors for coherent multi-user communications[J].IEEEJSAC, 1990, 8:683～690.
视频序列中目标的检测与跟踪 篇2
目标的检测与跟踪涉及到人工智能、机器视觉、生物医学、自动控制等多个学科,近年来,随着计算机技术的发展,得到了广泛的研究与应用[1]。目前比较流行的目标检测算法包括帧间运动估计和背景差分的方法,帧间运动估的方法是利用图像序列中相邻帧图像之间的差来提取图像的运动区域的。该方法实现简单,但只能检测相对运动的目标,并且检测出目标的位置不够精确。背景差分法首先定义视频图像的特定帧为背景,然后将当前帧和背景进行差分比较,如果同位置的像素特征、像素区域特征或其他特征的差别大于选定的阈值,则当前帧中该位置的像素区域就判定为前景目标区域,反之则为背景。该方法容易受到光线亮度变化的影响[2]。基于上述原因,本文提出了一种基于时间序列的编码建模算法,该算法能够解决像素剧烈变化的问题,可以提高复杂背景下目标检测的稳健性。目标的跟踪是通过算法获得目标在特定时间段上的运动轨迹,包括目标的产生、运动和销毁三个过程。由于算法中涉及到帧间目标空间位置的测量,在传统的跟踪算法中,当目标数目增加的时候,算法的时间复杂度呈指数形式增加。本文在分析上述问题基础上,将KD-Tree方法[3]引入目标跟踪算法之中,降低了算法的时间复杂度,同时降低了算法对目标数目的敏感程度,实现了高精度、高效率的目标检测与跟踪。
1 目标检测
很多场景都包含复杂的运动目标,诸如摇曳在风中的树、转动的风扇、摆动的窗帘等。通常这种场景中还有光线的变化。解决这个问题最好的方法是采用基于时间序列的编码建模算法,对每个像素或者一组像素建立时间序列模型,在每个像素点进行抽样,根据颜色扭曲尺度和亮度边界聚类获得编码本的集合,并不是所有像素点拥有相同数量的编码本数量。通过编码本表示的聚类子不需要对应单个高斯分布或者其他参数的分布,因此该编码方式是以像素为基础的。
归一化颜色算子是用来处理全局和局部亮度变化的方法,该技术在图像的暗色区域效果不理想,因为颜色比率的不确定性与亮度相关,所以灰度级低的像素点相对与灰度级高的像素点不确定性更高。这些不确定性使灰度级低的区域变得不稳定,在可能聚集在低灰度级的区域造成无检测[4]。本文通过建立颜色模型来估计颜色的亮度和扭曲,该模型依赖于编码元素主轴界定在亮度值高低边界的背景像素值。对于输入像素点pixi=(B,G,R)和编码本ci,定义Vi=(Bi,Gi,Ri),可得
由式(1)和式(2)可得
(pixi,Vi)2=(BiB+GiG+RiR)2 (3)
颜色扭曲度为
u2可以由式(5)求解
此外,统计地分配亮度变化的最大和最小值,将其赋给一个编码本,在特定的范围内限制阴影水平和焦点水平,能够有效地适应亮度的变化。为了去除图像中引入的噪声,首先对目标检测完成的图像进行3×3的中值滤波,然后进行形态学处理,使待检测的目标形成一个完整的连通域,并在一定程度上消除中值滤波无法消除的噪声,最终得到比较理想的目标图像。
不同处理阶段目标检测的结果如图1所示。可以看到,在经过上述处理,得到了完整的目标。
2 目标跟踪
目标跟踪是建立在目标检测的基础上的,即确定实时视频帧中检测到的目标的运动轨迹,这种轨迹的建立可以通过目标特征的匹配来实现,通常采用的特征信息有目标的位置、尺度、形状以及颜色等。本文采用目标的位置(即每个目标的质心坐标)建立运动模型,实现目标轨迹的精确匹配。
将每帧图像检测出的多个目标同上一帧图像检测出的目标进行比较并分类,主要有3种情况:1)当前目标是由上一帧中某个目标运动得到的(运动速度大于或等于0);2)当前目标在上一帧中没有出现,是新增加的目标;3)某些目标在上一帧中出现过,但在当前帧消失了。
在跟踪用摄像机完整标定的情况下,视场中的目标的运动速度会保持在某个区间之内,即可以通过实验的方法确定某一类别目标的最大运动速度,因为摄像系统的帧率是一定的,所以可以确定目标在两帧之间的时间间隔内的最大位移,定义为D_max,以此作为阈值条件。然后把上一帧的所有目标的质心坐标放在一个数组中,作为一个待遍历的集合Vec。将当前帧的每一个目标的质心坐标在集合Vec中寻找出与之几何距离最近的对应目标A,然后计算该距离d与D_max的关系:1)如果d≤D_max,当前帧的目标是从上一帧的目标A运动得到的;2)如果d>D_max,当前帧的目标是新增加的目标;3)如果在上一帧的目标中存在没有和当前帧目标相对应的,则说明没有对应的这些目标在当前帧中消失了。
针对上述3种情况,本文采用KD-Tree算法[5]实现目标跟踪。KD-Tree算法是一种由二叉搜索树推广而来的用于多维检索的树的结构形式(K即为空间的维数,此处定义K=2)。与二叉搜索树不同的是,它的每个结点表示k维空间的一个点,并且每一层都根据该层的分辨器对相应对象做出分枝决策。顶层结点按由分辨器决定的一个维度进行划分,第二层则按照该层的分辨器决定的另一个维度进行划分,以此类推在余下各维之间不断地划分。直至一个结点中的点数少于给定的最大点数时,结束划分。
如图2所示,在二维空间内存在点A,B,C,D,E,首先以A点的y维度为起始点,将点集分为2个部分,然后在左右2个子树中以B点和C点的x维度将左右2个子树分为2个部分,以此类推,在B点、C点各自的子树当中,以D点、E点的y维度对其子树划分,遍历集合当中的每一个点,就可以得到1个完整的KD-Tree。目标轨迹建立的过程就是在KD-Tree中搜索最近点的过程,采用KD-Tree进行最近点搜索可以提高系统的工作效率。
算法流程如下:
1)定义目标质心点坐标存储结构体,即
typedef struct Blob2D32f
{
int ID;
float x;
float y;
} kidBlob2D32f;
其中ID为每个目标对应的序号,x和y分别为每个目标质心坐标的横、纵坐标值。
2) 将第i帧的每个目标(定义为Blobi,其中i=1,2,3,…,N)的横纵坐标按照Blob2D32f结构体形式进行存储,ID号从0开始顺次排列,然后存放在起始帧数组ArrayL中。
3) 将第i+1帧的每个目标的横纵坐标按照Blob2D32f结构体形式进行存储,ID号不填充,然后存放在当前帧数组ArrayN中。
4) 对起始帧数组ArrayL建立KD-Tree。
5) 定义D_max。
6) 遍历当前帧数组ArrayN中的每个Blobi,搜索其在KD-Tree中最短距离元素,定义最短距离为d。
7) 如果d>D_max,则该Blobi为新当前帧新增加的目标,将其赋予一个新的ID;如果d≤D_max,则该Blobi为由上一帧的目标运动得到的,将其ID更新为ArrayL数组中与其距离最短的目标的ID,并将其对应元素在ArrayL数组中删除。
8) 遍历结束后,ArrayL数组中余下的Blobi即为上一帧存在但当前帧消失的目标,将其删除。
9) 将当前帧数组ArrayN中的元素更新到ArrayN数组中。
10) 循环执行步骤3)～9)过程,直到程序结束。
随着视频帧数据的不断采集,循环进行上述过程,即实现了目标的检测与跟踪。流程图如图3所示。
3 目标跟踪实验
采用三轴云台固定摄像机进行实验,视频图像分辨力为640×480,背景模型建立过程累积了35帧图像,在普通PC上目标检测与跟踪的速度可以达到25 f/s(帧/秒)。
图4分别为第4,6,26,150帧时目标跟踪的情况,可以看到,目标被完整地检测出来,在目标物像素尺寸相对整个视频帧图像的比例较大的时候,没有出现单一目标被误检测成多个目标的现象,且目标的运动能够被较好地跟踪。
4 结论
本文讨论了几种目标检测中背景建模的方法,并重点说明了背景差分的建模方法,对差分后的图像进行滤波和形态学处理之后,可以得到较完整的目标轮廓,并且通过KD-Tree算法对目标进行跟踪,大幅度提高了跟踪效率。
参考文献
[1]蔡荣太,吴元昊,王明佳,等.视频目标跟踪算法综述[J].电视技术,2010,34(12):125-127.
[2]潘翔鹤,赵曙光,柳宗浦,等.一种基于梯度图像帧间差分和背景差分的运动目标检测新方法[J].光电子技术,2009,29(1):34-36.
[3]SPROULL R F.Refinements to nearest-neighbor searching in K-dimen-sional trees[J].Algorithmica,1991,6(4):579-589.
[4]KIM K,CHALIDABHONGSE T H,HARWOOD D,et al.Real-time fore-ground-background segmentation using codebook model[J].Real-TimeImage,2005,11(3):172-185.
视频序列中的运动目标检测与跟踪 篇3
近年来,随着计算机速度的不断提高以及数字图像处理技术研究的不断深入,智能视频监控技术得到了很好的发展,并被广泛应用于军事及民用监控系统,它能够大大减少人力物力,保障监控场所安全[1]。
视屏监控技术主要包括运动目标检测、目标提取、目标识别与跟踪几个模块。其中以目标检测部分为关键。目前,常用的运动目标检测方法有:光流法、帧差法和背景减法。光流法对光线和噪声的变化特别敏感且计算复杂耗时,没有特别硬件支持很难在实时系统中应用[2]。帧差法是基于运动图像序列中,相邻两帧图像间具有强相关性而提出的检测方法,具有很强的自适应性,但分离出来的运动目标容易出现空洞和沿着运动方向拉伸,不利于进一步分析与识别[3]。背景减法是目前最简单而又常用的方法之一。背景减法适用于摄像机静止的情况,能够完整分割出运动对象,却容易受光线、天气等光照条件、前景目标短暂或长久性的闯入和移出、背景自身的运动(如:树叶摇动等)等因素的影响。尽管如此,在实时监控系统中背景减法仍是运动目标检测的最常用方法[4]。常用的背景建模方法为混合高斯模型[5],但是模型复杂,计算量大。本文的目标检测部分采用了基于直方图统计的多帧平均混合法做背景提取,然后使用背景减法提取运动目标[6]。
1 背景模型
由于交通场景中视频序列特定像素位置出现频率最高的像素值是背景像素值。实际上交通场景中的视频序列还有一个特点:某点背景的像素值总是在某个区间内波动。因此将某点的灰度范围[0,255]等分为若干区间[0,256/N],[256/N,2×256/N],…,[(256-256/N),255],N为等分区间数,对应于某个像素的每个区间,考虑其落在区间内像素点的灰度值的均值μ及区间的计数统计S。在读取视频序列的同时,更新背景。具体方法如下:
(1) 均值更新。如果:
则更新第n个区间的像素均值:
否则:
(2) 区间计数统计更新。如果:
则更新第n个区间计数统计:
否则:
式中:ci(x,y)表示在第i帧图像中的坐标为(x,y)处的像素点的灰度值;α与β为权系数。这样将直方图灰度划分成区间段,对帧中的每个像素点计算ui,n和si,n后,比较不同区间段的si,n后,将具有最大si,n的区间的ui,n作为背景。
2 目标提取
2.1 噪音消除
在背景差分的基础上,可以得到一幅粗略的二值图像,然后对其采用3×3的方形窗口进行中值滤波,以消弱图像中噪声的影响。
2.2 形态学滤波[7]
噪声的影响可能会使目标边界呈现不同程度碎片,对此本文使用形态学滤波中的膨胀、开运算对二值图像做处理,使目标区域轮廓变得平滑,同时抑制峰值噪声。
2.3 阴影消除
阴影的存在不利于准确判断目标的位置,像素点(x,y)在未被阴影覆盖和被阴影覆盖时的亮度值近似成线性关系,由概率论中相关系数的性质可知,若随机变量X和Y成线性关系时,则X和Y的关系系数为1,因此本文利用了万相关系数的性质进行阴影检测与滤除[8]。
2.4 区域标记提取
经过以上方法处理后的前景背景二值图像中,目标为若干个黑色联通区域,首先通过八连通域区域标记法[9],给每个目标一个标记。
然后从左到右,从上到下扫描已经标记的图像,遇到相同标记的点时,就更新对应标记区域的中心上下左右四个坐标值,结束扫描后,再根据每个区域的上下左右四个座标值获取其中心坐标。如此,就得到了每个区域的标记以及具体位置。
最后,对于这些区域的异常情况例如对于携物者、牵手并行者、迎面相交者等做处理。处理方式主要根据目标区域的长、宽、中心坐标距离,面积等特征来做判断。例如一个区域的面积很小(小于某个阈值),并且距它最近的区域的距离大于某个值,那么把它当噪声处理,更改它的标记为255。
3 目标识别与跟踪
在连续的视屏序列中,采用背景差法得到的目标,需要识别当前图上的某个目标是与上一副图中的哪一个目标相对应。对于人流量大,行走速度快的情况,目标识别是一个比较繁琐的过程。本文采用最小距离匹配法做目标识别,构建以下结构体描述目标信息。定义两个该结构体类型指针。
struct TargetArea
{
int flag; //区域有效标号
int CorrespondingFlag; //匹配标号
int number; //区域中包含的像素数
int centerX; //区域中心X坐标
int centerY; // 区域中心Y坐标
int direction; //区域移动方向
}*mpPersonInAreaBefore,*mpPersonInAreaNow;
目标跟踪程序步骤如下:
(1) 统计监测区中的目标个数,使用一个循环语句来将当前目标与上次目标(上幅图中处于检测区的目标)之间的中心距离逐一比较,如果距离小于某个阈值,则认为匹配,那么将当前目标与上次目标变量中的CorrespondingFlag 置1,表示找到了匹配点。
(2) 对于已经找到匹配目标的当前目标,比较它与匹配目标的中心坐标(centerX,centerY)来得到他的行走方向。在本文实验中,因为行人在监控区的主要行走方向是上行和下行,因此只对centerY做了比较。然后根据结果给direction赋值(1表示上行,0表示静止,-1表示下行)。
(3) 对于当前目标中匹配标志为0的点,表示是新点,那么它可能是一个新进入监控区域的人,或者是一个噪声。如果距离监控区的边界线小于某个阈值,认为是新进入区域的人,否则认为是噪声,置区域有效标记flag为0。
(4) 对于上次目标中匹配标志为0的点,表示目标已经离开了监控区域。那么根据它的行走方向以及距离上下检测线的位置判断是上行穿过区域还是下行穿过区域。如果距离下检测线近而且行走标志为-1,则判为下行通过区域,下行人数计数器加1,如果距离上检测线近且方向标志为1,则认为上行通过检测区,上行人数计数器加1,否则认为是噪声。
(5) 判断结束,释放上次目标的数据空间,重新申请当前目标个数的目标结构体数据空间,将当前目标数据放入其中,更改匹配标志为0,以便与下一副图中的目标做对比。
4 实验数据与分析
实验中以每100 ms每张的频率针对四川大学室外场景拍摄了1 506张照片。通过对这些照片做图像处理分析,统计在这段时间内通过该区域的人数。视频图像帧的大小为320×240像素,在普通PC机(AMD Sempron Processor 3000+,1.60 GHz,1.00 GB的内存,天敏SDK2500视频采集卡)上,用VC++ 2005编写了一个基于对话框的程序做实验。图1为程序界面。打开视屏序列中的某幅图片后即可点击“视屏监控”按钮开始监控,程序界面可以显示实时刷新背景、背景差后经过处理的二值图像、经过区域标记和目标识别跟踪后的监测画面。设置了纵坐标从60～130的范围为监控区,在监控时间内通过监控区的行人人数显示在右下角。针对这次实验的1 506张照片,实验结果准确地统计出了通过区域的行人人数。
图2为使用直方图统计与多帧平均混合法得到的背景图像。
图3为背景差后的二值图像,目标用黑色表示,背景用白色表示,可以看出,目标被明显地提取出来了,并且经过消除噪声、形态学滤波、阴影消除后的前景二值图像,比较干净,具有较好的对比分析使用价值。
图4为行人特殊情况的目标提取结果,可以看出,对于相遇造成的目标重叠、两人紧靠并行、携物者,都能得到较好的目标提取结果。
图5为行人监测,行人进入监控区域后能对其进行跟踪,穿过区域时,能较准确地判断出其行走方向,并且统计人数。
5 结 语
本文针对固定场景提出一种基于背景模型的运动目标检测和跟踪算法。该方法使用直方图统计与多帧平均混合方法背景建模。使用八连通域区域标记法和最小距离匹配方法对目标进行识别跟踪,根据目标特征参数进行逻辑判断监控行人人数,都取得了良好的效果,并且能对多种特殊情况兼容处理,具有实用价值。
摘要：提出一种视频序列中的运动目标检测跟踪算法。该方法采用直方图统计与多帧平均混合作为动态背景更新法,经过噪音消除、形态学处理、阴影处理后,用区域标记法提取目标。利用目标特征参数建立目标数组,通过当前帧目标数组和前一帧目标数组距离匹配实现运动目标的快速跟踪。该方法与传统方法相比具有更好的学习能力,从而有效地提高了运动目标检测的正确率和快速性。实验结果表明该方法具有良好的鲁棒性和自适应性。
关键词：背景模型,背景提取,运动目标检测与跟踪,视频序列
参考文献
[1]施华,李翠华.视频图像中的运动目标跟踪[J].计算机工程与应用,2005(10):56-58.
[2]Kinoshita K,Enokidani M,Izumida M,et al.Tracking of aMoving Object Using One-Dimensional Optical Flow with aRotating Observer[A].9th International Conference on Con-trol,Automation,Robotics and Vision[C].2006:1-6.
[3]Gao Hongzhi,Green R.A Robust Moving Object Segmenta-tion Algorithm[A].Proceedings of the 2007 InternationalConference on Wavelet Analysis and Pattern Recognition[C].2007,1:214-217.
[4]Piccardi M.Background Subtraction Techniques:A Review[A].IEEE International Conference on Systems,Man andCybernetics[C].2004,4:3 099-3 104.
[5]Chris Stauffer,Grimson W E L.Adaptive Background Mix-ture Models for Real-time Tracking[A].IEEE Computer So-ciety Conference on Computer Vision and Pattern Recogni-tion[C].Fort Collins:IEEE Press,1999.246-252.
[6]李晓飞,梅中辉.一种基于直方图统计的多帧平均混合的背景提取算法[J].南京邮电大学学报:自然科学版,2008,28(6):74-77.
[7]冈萨雷斯,阮秋琦.数字图像处理[M].2版.北京:电子工业出版社,2003.
[8]蔡友杰,陈秀宏.基于视频图像的运动目标检测与识别[J].微计算机信息,2009,25(3):280-281.
地震监测时间序列异常值检测策略 篇4
关键词：地震前兆,时间序列,异常检测,相似性度量
地震前兆监测数据往往都包含着许多重要的信息, 从这些海量的数据中挖掘出有用的信息真实可靠地应用在地震预测中一直是地震工作者和学者研究的热点, 然而受局部环境、人为因素以及仪器内部故障等等诸多主客观因素的影响, 使得这些前兆时间序列中难免存在着一些异常点, 这些异常值对上述研究结果的准确性有着直接的影响, 因此前兆数据预处理中的异常值的检测是从前兆监测数据中准确的挖掘出前兆信息的前提和保障。
由于监测时间序列数据反映的是监测对象实时信息这一特征, 因此其异常定义不能简单的等同于传统的异常定义, 在前兆监测数据中, 一类是由地质结构的发生变化而引起的监测对象的实际结构发生变化的数据异常。一类则是有由仪器自身故障、噪声, 以及外部干扰, 其他局部干扰等因素引起的监测数据异常。前者异常能够反映地质结构变化, 称之为前兆信息。而后则与地质结构变化没有直接关系, 称之为干扰因素。因此前兆数据预处理中的尽可能的保护前兆信息的原始特征, 而剔除出干扰因素造成的异常值。而实际情况中, 由于监测对象涉及几大学科, 每个学科有涉及多个测项, 其数据的特点通常也存在较大的差异, 另外干扰因素繁多, 呈现形式多种多样, 这些不规则的, 交错的干扰因素, 让数据预处理时区分辨认这些干扰和处理时显得愈发困难。另一方面, 对于很多干扰因素, 如果不能做到实时监测, 事后则再去分析落实干扰因素则存在很大困难。而由于监测数据时间性较强, 数据量庞大, 采用在线动态监测则使检测算法面临很高的挑战。
时间序列的异常值监测方法很多, 大体可以分为阈值检测和聚类两大类。本文根据地震监测时间序列的数据量大、动态性、时效性等特征, 考虑阈值监测计算量小、速度快、可信度低, 适合用于动态检测, 然后将阈值检测的结果生成一个新的简化序列, 再用计算复杂, 高时间复杂度、高可信度的聚类分析的检测办法来对新的简化序列进行聚类分析, 从而达到异常值检测的目的。
1 相关定义与技术
定义1 (地震前兆时间序列) 设地震前兆时间序列{xi (t) } (i=1, 2, …, n, t=1, 2, .., m) , 其中i表示观测分量的变量, 当n=1时, 表示单分量地震前兆时间序列, 当n 2时表示多分量地震前兆时间序列。m是观察值的个数。
若对前兆观测时间序列进行在线动态检测, 则必须考虑其子序列随着随时间推进而变化, 所以这里给出滑动窗口的概念。
定义2对当前时间序列x (n) 进行异常检测, 当接收到指定长度的一段新数据x (n+1) 时, 将当前最新数据x (n+1) 添加进去从而形成一个新的时间序列{x (n’) } (n’=1, 3, …, n+1, ) , 进而再次触调用检测算法对其进行异常监测。
定义3 (欧式距离度量公式) {x1 (t) }和{x2 (t) }是给定的两个时间序列, 其中, t=1, 2, .., n, n为序列的长度, 将每个序列看成是n维空间中的一个点, 则{x1 (t) }和{x2 (t) }之间的距离定义为:
2 统计量阈值型异常值检测
统计量阈值检测是比较简易的一种检测方法。V.Barnett和T.Lewis[1]很早就提出用统计学思想进行异常值检测的方法, 即对观测数据时间序列的某个特征值的大小进行限定, 观测数据出现异常时, 可以体现在许多特征值的大小变化上, 文章这里将领域平均差分做为特征值为例进行说明[2], 因为通常观测数据出现异常表现在其数据平稳情况发生较大变化, 因此考虑从数据平稳性的角度对观测数据进行监控, 这里采取求领域时间段内观测值的二阶差分平均值的办法来衡量数据的稳定程度。假定观测值二阶差分在某个范围之内, 则定义这个范围为平均差分阈值。
设一段时间T[1, N]内某系统在时间点T1, T2, …, TN上的N个有序观测值X1, X2, …, XN.
若设定其平均差分阈值为Z, 则该时间段观测数据为正常数据必须满足条件:
这种方法算法复杂度低, 可以满足对前兆数据进行实时检测的要求, 从较粗的粒度上发现异常值。显然, 它缺乏一定的可信度, 不能真正达到异常值检测的目的。下面给出自定义阈值型数据异常判定算法。
算法2.1自定义统计量阈值检测算法 (C#语言)
3 相似性度量检测法
时间序列的相似性度量的方法有很多种, 包括欧式距离法 (ED) , 动态时间弯曲 (DTW) 距离法[3]和形态特征距离法[4]。这些时间序列相似性度量方法各有优缺点, 观测员在系统中可以根据自己实际情况进行选择相似性度量方法, 并设置其相似度的阈值。而基于相似性度量的孤立点检测早在2002年香港大学的E.Hung和D.Cheung就提出了并行化基于距离的孤立点的挖掘算法[5], 本文这里提出的检测算法, 是在阈值检测法的基础上进行的, 实际上是对阈值检测法检测出的异常点进行二次筛选的过程。为了检测样本时间序列相对于临近观测点的时间序列是否离群, 首先给出样本时间序列的平均临近距离和样本时间序列临近测点间的平均离散距离的概念。
定义4.1设x1 (tn) 为观测样本点G的时间序列, p={x2 (tn) , x3 (tn) , …xk (tn) }代表与G临近的k-1个测点的同一观测分量的时间序列集合, 则样本G的平均临近距离表示为:
P内平均离散距离表示为:
定义4.2设x1 (tn) 为观测样本点G的时间序列, p={x2 (tn) , x3 (tn) , …xk (tn) }代表与G临近的k-1个测点的同一观测分量的时间序列集合, 当Avd (G) -Aud (G) >L时, 则样本点G为干扰异常。当Avd (G) -Aud (G)
相似性度量规不过多的考虑对异常形态本身的规律上的认识, 而是按照某种度量方法, 从直观上去度量观测数据与周围测点之间的相似程度, 从而判定其是否离群。
然而实际应用中, 根据用户对异常信息的兴趣点的不同, 异常判定的方法有很多, 这里的自定义阈值规则和相似性度量规则只是其中的较为常见的设计方法。采用阈值规则是为了简化相似性度量的计算量, 而是用相似性度量规则则是为了提高判定结果的可信度。文中利用地震观测数据邻近测点时间序列特性相似的特点, 将两者结合起来。
4 应用实例与分析
文章以信阳形变观测台降水干扰图, 交汇记录鲁甸地震震例的情况为例进行分析, 首先用平均二阶差分阈值对整个长度为8640的原始数据 (见图a) 进行实施检测, 设时间序列长度为10, 设阈值取附近10个数值平均值的2倍, 共检测出异常点如125个, 将的这125个点进行插值形成新的时间序列与郑州荥阳测点和焦作测点相对应数据进行相似性度量, 根据定义4.2分别设定K值为0.1, L值为4, 计算得出地球物理变化点一个, 正好对应图c中的震例。而计算出干扰异常32个点, 但是尽管降水干扰在这32个点的范围内, 但是很难直观的看出来, 显然, 降水干扰的一个下降的过程是一个缓慢的趋势变化, 因此仅用二阶差分阈值难以将其清除的提取出来, 因此对其傅里叶变化后, 用幅频特征与邻近测点再次进行相似性度量, 清楚的显现出三个大的趋势, 其中日潮, 半日潮三个测点具有很好的同步性, 而降水干扰异常仅仅在信阳台观测数据的幅频特征中清晰的提取出来, 见图b。
从该实例分析情况来看。阈值异常值检测能够大范围的提取出各种可能为异常的点, 但它却难以清楚的将干扰异常和地球物理变化区分开来, 但是特征阈值的选取又至关重要, 因为它的结果将直接影响相似性度量检测的效果。
5 结语
前兆观测数据真实可靠地应用在地震预测中前提是由台站观测人员能够准确去除和标记干扰异常数据。本文根据地震监测时间序列的数据量大、动态性、时效性等特征, 考虑阈值监测计算量小、速度快、可信度低, 适合用于动态检测, 然后将阈值检测的结果生成一个新的简化序列, 再用计算复杂, 高时间复杂度、高可信度的聚类分析的检测办法来对新的简化序列进行聚类分析, 从而达到异常值检测的目的。文中分别给出了阈值型异常检测策略与算法, 以及相似性度量型异常值检测策略, 最后用实例分析表明, 文中提出的前兆数据异常值检测的方法是有效可行的。
参考文献
[1]V.Barnett, T.Lewis.Outliers in statistical data.John Wiley and sons, 1994.
[2]成万里, 熊豪, 曲翠兰.前兆仪器数据异常实时监控系统研究[J].数字技术与应用, 2012 (10) :12-14.
[3]翁颖钧, 朱仲英.基于动态时间弯曲的时序数据聚类算法的研究[J].计算机仿真, 2004, 21 (3) :37-40.
[4]董晓莉, 顾成奎, 王正欧.基于形态的时间序列相似性度量研究[J].电子与信息学报, 2007, 29 (5) :1228-1231.
[5]Edward Hung, David W.Cheung.”Parallel Mining of Outliers in Large Database”, in Distributed and Parallel Database (DAPD) , Kluwer Academic Publishers, Volume 12, Issue 1, pages 5-26, July2002.
[6]郑健, 皮德常.基于共享最邻近的聚类和孤立点检测算法.第一届中国高校通信类院系学术研讨会, 2007.
检测序列 篇5
事实上,目标具有多样化的特征(包括物理特征和数学特征),而强度特征仅仅是其诸多特征中的一部分,充分利用信号的多方面特征信息可有效提高系统对目标和杂波的分辨能力[2]。本文主要创新点在于:利用弱小运动目标在时频多维联合域中分析目标和杂波的特征差异,系统分析运动目标和杂波的时频特征,指出弱小目标经过处是长时非平稳而短时平稳的随机信号,而杂波所在处通常为长时平稳信号。利用运动目标经过处时频发生的微小变化来检测目标,而杂波处的时频基本保持平稳的差异,有效去除背景杂波的干扰,于此检测出弱小运动目标。最后通过DSP实现弱小运动目标检测算法。
1 检测算法分析
弱小运动目标的序列图像f(x,y,k)可表述为:
其中,s(x,y,k)、b(x,y,k)和n(x,y,k)分别为第k帧经过像素(x,y)的目标、杂波和噪声的幅度值,k为图像序列的帧数。在图像大小、帧数等参数已经确定的条件下,首先调用目标检测模板对序列图像进行处理,根据目标经过处的像素点会引起灰度值的瞬时起伏,而噪声点是服从时间独立的高斯分布这一特点,设置相应判决门限并根据判决准则得到一系列疑似目标点,然后根据目标与杂波在时频上存在的明显差异识别运动目标。
1.1 设置门限过滤噪声
假设目标检测模板大小为n=m×m,Fm为滤除噪声设置的门限,H1判定为疑似目标点,H2判定为噪声,则检验统计量为:
其中,f(xi,yi)为模板上像素点的灰度值。检验统计量T大于设置门限Fm时,则认为此点为疑似目标点,反之则为噪声。
一般情况下,采用的检测模板大小为9个像素,如图1所示。考虑到目标点及其他干扰所占像素值有可能大于实际所选用模板,所以做了适当的改进,将疑似目标点属于同一疑似目标斑块的像素点进行合并,如图2所示。
假设Fi为3×3模板上任意一点,Fim为3×3模板中心点,将满足以下条件的疑似像素点进行合并:
式(3)表明两个3×3模板上任意两点八邻域距离小于L1的情况(L1取n1个像素),式(4)表明两个3×3摸板上两中心点八邻域距离小于L2的情况(L2取n2个像素)。其中n1、n2根据实际目标点、杂波大小确定。式(5)表明将满足式(3)、式(4)的两个疑似目标点合并为一个新的疑似目标点,重复进行上述合并操作,直至将所有疑似目标点合并完为止。
1.2 时频分析及其实现
时频检测方法体现了信号在时域和频域的联合分布信息,可为分析及分辨目标和杂波提供细微的空间、时间、频率及其联合多维度的特征。
假设序列图像(x,y)按采样时间先后顺序形成三维图像(x,y,k),将所有待处理原始序列图像中同一位置空间坐标为(x,y)的灰度值读取出来并按照时间的先后顺序存储为f(m),即形成f(x,y,k)→f(m)的映射。然后对f(m)信号进行如下短时加窗处理:
其中,t为时频变换后的时间,如果假设图像序列中相邻帧之间的时间间隔为△t,则时间t即为△t×k;m为序列图像的第k帧,w为短时傅里叶变换之后的频率,与采样点数有关;W(N1)为短时窗函数,一般为能量聚集性强的汉明窗或汉宁窗,N1为短时窗函数的窗长。
假设目标经过处像素点幅度为目标幅度和噪声幅度累加,即f(x,y,k)=s(x,y,k)+n(x,y,k),且s(x,y,k)、n(x,y k)相互独立。则目标经过像素点的短时傅里叶变换为:
可见,目标经过像素点的时频值是噪声时频值与目标时频值的和。
夜晚深空的杂波主要是恒星,幅度变化缓慢。杂波经过处像素点幅度为杂波幅度和噪声幅度累加,即为f(x,y,k)=b(x,y,k)+n(x,y,k),且b(x,y,k)、n(x,y,k)相互独立。则杂波经过像素点的短时傅里叶变换为:
可见,杂波经过处像素点的幅频值是噪声幅频值与杂波幅频值的和,与目标点的短时傅立叶变换的波形存在明显的差异。
根据目标经过的时间窗口内,其短时傅里叶变换波形的低频段幅度存在短时波包,形成了明显的“主瓣”和“旁瓣”效应,而杂波低频段幅度比较平稳,则提出假设统计检验量T为:
其中,H4表示接受疑似目标点为真实目标点;H3表示接受疑似目标点为杂波点;F(ti,0)为短时傅里叶变换ti为0、1...51时,频率w=0处的数据矩阵;max F(ti,0)为max F(t,w)中峰值;为F(t,w)均值;为F(t,w)标准差;T0为区分目标和杂波的判决门限。将检验统计量T与判决门限T0进行比较判断出真实目标。
2 系统结构
系统结构如图3所示。首先将序列图像进行预处理(可以采用FPGA等逻辑器件处理),使得图像序列每帧大小一致、时间间隔恒定,然后通过系统核心芯片DSP进行算法实现(即滤除噪声干扰、识别出疑似目标点),最后根据运动目标的空时频特性的差异识别出运动目标,输出检测结果[3]。
系统设计软件流程框图如图4所示。系统初始化开始后,首先从待处理原始图像中读取任意一张图像,然后初始化一系列参数,根据目标与噪声的像素特性的差异设置门限滤除噪声的干扰,再根据短时傅里叶变换波形差异区分目标和杂波,最后根据目标短时波包的“主瓣”和“旁瓣”比值,动态改变窗函数的宽度和序列图像的帧数,以达到最优的检测性能[4,5]。
3 实验与分析
试验数据为外场采集的真实红外图像序列,该图像序列有51帧,每帧图像为160×160像素。图5为本系统所采用序列图像中具有代表性的一帧图像。对序列图像进行设置门限滤除噪声的处理并对属于同一斑块的像素点进行合并,得到如表1所示的疑似目标点。通过以上方法可以有效地识别出疑似目标点。
系统取序列图像中疑似目标点的空间坐标(x,y)分别为(108,88)、(32,43),窗函数W(N1)为hanning(N1)(其中N1=8),FFT的采样点数为1 024,△t=1进行处理。疑似目标点(108,88)短时傅里叶变换之后取t=1时刻的幅频特性曲线如图6所示,t=20时如图7所示。疑似目标点(32,43)短时傅里叶变换之后取t=1时刻的幅频特性曲线如图8所示,t=20时如图9所示。
根据短时傅里叶变换的数据得到在某一时刻的幅度-频率二维图像。图6~图9所示4张图的包络大致相同,其中疑似目标点(32,43)在t=1、t=20时刻的幅频曲线的峰值分别为600、614,其峰值差异并不明显。其余4个疑似目标点峰值差异也很小,与疑似目标点(32,43)类似,这里就不再赘述[6]。而疑似目标点(108,88)的峰值差异明显,分别为624、391。因此利用此特征可以有效地识别目标。
将每个疑似目标点的短时傅里叶变换后零频的数据矩阵F(t,0)的峰值(如图6~图9处的峰值)按照时间t组合在一起,形成每个疑似目标点的时间-幅度峰值二维图像。图10为疑似目标点(32,43)的时间-幅度峰值图,图11为疑似目标点(108,88)的时间-幅度峰值图。其余疑似目标点的时间-幅度峰值与疑似目标点(32,43)类似,这里就不再重复。
由图10、图11可见,疑似目标点(32,43)和(108,88)的时间-幅度峰值图特性存在明显的差异。即运动目标点存在明显包络,而杂波比较平稳,因而根据这一差异可以区分目标与杂波。
本系统针对现有弱小目标检测技术在挖掘目标细微特征方面存在的缺陷和严重不足,利用时频信号处理理论感知弱目标时、频特征,探索能切实提高弱目标检测性能的有效方法,为提升空间暗弱目标的探测能力提供了切实有效、先进的技术手段。一般情况下,序列图像弱小运动目标的检测算法运算量大,实时性要求高,应用一般传统器件无法满足其要求,而高速DSP芯片则可以很好地实现。本系统即利用DSP实现了序列图像弱小运动目标在软件上的检测算法。通过分析最后的检测结果,调节初始化参数,可以方便地达到所需要的性能,对于算法的验证与调试具有广泛的适用性。
摘要：针对强杂波背景中的弱小运动目标检测问题,在分析弱小目标的运动特性在时频变换中表现出显著差异的基础上,采用两级滤波方法检测运动目标,提出了一种基于DSP的序列图像弱小运动目标检测方法。该方法首先对序列图像进行预处理、设置门限过滤噪声,然后根据目标和杂波的时频特征差异识别出弱小运动目标。实验结果表明,该方法可以很好地抑制噪声的干扰,并能检测出复杂背景下的弱小运动目标。
关键词：时频分析,DSP,弱小目标检测,序列图像
参考文献
[1]GHAMASAEE R,AMOOZEGAR F,HOYUEN P.Surveyof neural networks as applied to target tracking[J].SPIE,1997,3069:412-423.
[2]LEONOV S.Nonparametric methods for clutter removal[J].IEEE transaction on aerospace and Electronic Systems,2001,37(3):832-847.
[3]李桂菊,赵建,王金库.目标检测算法在DSP系统中软硬件优化方法的实现[J].红外与激光工程,2006,10(35):377-381.
[4]李飞飞,刘伟宁,孙海江.基于FPGA+DSP的红外弱小目标检测与跟踪系统设计[J].激光与红外,2009,39(4):450-453.
[5]李宏,李伟,李蒙,等.基于多DSP的红外目标跟踪系统设计与实现[J].电子技术应用,2006,32(8).
检测序列 篇6
入侵检测, 就是对入侵行为的发觉和识别, 是一种试图通过观察行为、安全日志或审计数据来检测入侵的技术[1]。为此目的所研制的系统就称为入侵检测系统 (Intrusion Detection System, IDS) 。随着人类社会生活对计算机和互联网依赖程度的日益增强, 计算机系统安全也越来越成为领域内研究的热点;而入侵检测技术的研究则是这个领域中的重要分支。
现有的入侵检测技术都或多或少地存在一些不足。异常检测类技术只能发现异常系统或网络数据的出现, 却不能及时给出这些异常数据到底代表了什么样的入侵或攻击行为, 误报率高;滥用类检测技术一般只能检测到已知的入侵及其简单变种, 不能识别新出现的入侵, 特别是在用模式匹配技术[2]或状态转移分析技术[4]的滥用检测系统中, 由于实际存在的入侵种类繁多, 对应的入侵模式或入侵状态转移表数量也很多, 使得匹配分析成为盲目的试探过程, 检测效率低。
如果能将多个入侵用一个统一的模式描述, 这样就可以有效减小匹配分析过程的盲目试探性, 从而提高检测分析的效率。为此, 该文提出了基于特征信息序列语法分析的入侵检测方法。
1 特征信息序列语法分析
特征信息序列由一定的特征信息组成, 基于特征信息序列语法分析的检测分析方法的基本思想是:将同一类入侵 (比如所有的针对或利用IP数据包进行的入侵可视为一类) 用一个形式文法[8]模式描述, 所有入侵类型的文法 (即模式) 组成入侵文法库。在此基础上, 当检测分析程序面对由特定系统日志数据或网络数据包抽象而得的特征信息序列后, 对其按照模式库中相应入侵模式作自下而上的语法分析, 如果分析过程能够将这个特征信息序列最终归约为该文法模式的开始符号, 则说明这个特征信息序列确实代表了该入侵模式的一个具体入侵实例 (待分析的特征信息序列可以是由专门的数据解析程序输出, 可参阅作者的另一篇论文《基于数据解析的入侵检测技术研究》。具体用哪个入侵模式进行语法分析匹配, 要根据这个特征信息序列是由什么样的数据解析自动机识别而定, 例如, 若一个特征信息序列是由IP协议数据包解析自动机识别的, 就用IP协议对应的入侵模式) 。这样, 检测分析程序实质上就是一个语法分析器。语法分析的过程也是创建语法分析树的过程, 可以把这种针对特征信息序列的分析树称为检测分析树, 故也把这种检测分析技术称为基于检测分析树的入侵检测技术。
任何入侵模式都可用一个文法I (S, C, I, P) 描述, 其中S是入侵发生过程中关键状态的集合;C是特征信息的集合, 这里的特征信息是对单位源数据的抽象表示;I是文法的开始符号, 也是入侵模式名;P是派生式集合, 其中的每个派生式都形如Si→α, Si∈S, α∈ (S∪C) *。
在实现基于特征信息序列语法分析的入侵检测系统时, 要为每一个网络协议族建立相应的攻击模式库, 比如有TCP/IP攻击库, 库里的模式都是针对或利用TCP/IP数据包进行的攻击。其中, 每个协议对应一个入侵或攻击模式, 如TCP SYN FLOODING攻击、TCP三次握手攻击等都用TCP类攻击模式描述等;IP类攻击模式描述了所有针对或利用IP数据包进行的攻击, 如IP欺骗、IP分片攻击等;还有HTTP类攻击模式、SNMP类攻击模式等。这样检测分析程序可与数据解析程序配合, 当特征信息序列是由一系列IP协议数据包抽象而得时, 只须用IP类攻击模式对其进行匹配检测——语法分析;同样, 如果待分析的特征信息序列是HTTP协议数据包的抽象表示时, 则只须用HTTP攻击模式对该特征信息序列进行检测分析。这样可大大减少匹配分析中的盲目试探次数, 提高检测分析效率。
2 几个常见攻击的文法描述模式的构造及检测分析过程
上述思想和方法的基础是为每个入侵类型都构造一个用文法描述的模式。构造方法如下:首先, 确定将构造的模式要描述的各种入侵对应的特征信息序列, 所有的这些特征信息序列构成的集合即是文法模式描述的语言;然后, 依次构造四元组文法中的每个成员, 组成完整的文法模式。下面通过实际例子介绍文法描述的入侵模式的建立方法。
2.1 IP分片攻击和IP欺骗攻击
首先为IP分片攻击和IP欺骗攻击各自单独创建文法模式。
IP分片攻击的特征信息序列为a…a, b, c, 所有符合这个特点的特征信息序列集合即为IP分片攻击的模式要描述的语言。据此, 可以将其描述为如下以语法规则表示的攻击模式:
根据该IP分片攻击的模式, 对IP分片攻击的检测过程如下:
(1) 检测程序处于初始状态, 当IP数据包协议解析程序输出一个解析结果——特征信息序列后, 检测分析程序按照IP分片攻击模式对这个信息序列进行匹配分析。若特征信息序列的第一个特征信息是a (IP包分片标记为1) 时, 根据产生式S1→a, 检测程序归约到状态S1。
(2) 在状态S1, 特征信息序列的下一个特征信息仍然为a时, 根据产生式S1→S1a, 检测程序归约到状态S1;以此类推, 只要特征信息序列的下一个特征信息仍然为A, 则根据产生式S1→S1a, 检测程序归约到状态S1。
(3) 在若干次由S1归约到新的S1状态后, 直到特征信息序列下一个特征信息为b (接收到了所有的分片数据包, 并且没有超时) 时, 根据产生式S2→S1b, 检测程序归约到状态S2。
(4) 紧接着, 若下一个特征信息标记为c (各分片数据包的总长度小于该包数据的设定总长度, 说明有分片重叠发生) , 根据产生式S3→S2c, 检测程序归约到状态S3, 并报告发现了IP分片攻击。该检测分析过程对应的检测分析树参照图1 (a) 。
同理, 根据IP欺骗攻击的特征信息序列是f, 可以构造描述它的模式的文法:
这样, 对IP地址欺骗攻击的探测过程如下, 参照图1 (c) 的检测分析树。
在IP数据包协议解析程序输出一个特征信息序列后, 检测分析程序依据IP欺骗攻击模式进行匹配分析。若特征信息序列是f, 则根据规则展开式S4→f归约到S4状态。此时, 可向响应程序输出检测结果:发现了假冒IP地址的IP数据包。
图1 (b) 是对代表一系列正常的IP分片数据包的特征信息序列的检测分析过程对应的分析树, 即在将分片重组后得到一个与分片前完全一样的正常的IP数据包的情况。
然后, 用一个统一的文法模式描述包括IP分片攻击和IP欺骗攻击在内的所有针对IP包的攻击, 方法是:将所有针对IP数据包攻击对应的文法模式特征信息集合并为一个总的特征信息集合;将所有攻击模式的攻击状态集合并为一个总的攻击状态集合, 并引入一个新的文法开始符号IIP, 作为总的入侵类名;将所有攻击模式的派生式集合并为一个总的派生式集合, 并引入一组由新的开始符号IIP到各入侵名对应的入侵状态的派生式。这样就形成了IP类攻击的总的文法模式:
IIP (S, C, IIPFRAG, P) , 其中:
该文法是IP欺骗、IP分片攻击和正常IP分片数据的共同模式。实际上, 其他针对或利用IP数据包进行的攻击也可以包括在这个模式中, 当然, 不同类的入侵体现在模式中的不同派生式子集上。需注意的是, 按这种方法处理, 需要给每个产生式加上必要的语义规则集, 而使得描述模式的文法成为属性文法[8], 因为对不同的IP攻击的特征信息序列的分析都将归约到IIP。如果分析过程的最后是用IP→IIPFRAG, 由IIPFRAG归约到IP时, 根据语义规则中的属性计算, 就可以知道发生的是IP分片攻击而不是其他类型的IP攻击。如果能够将所有这样的利用相同的协议数据包进行的入侵用一个统一的模式描述, 那么, 只要知道待分析的特征信息序列是由什么协议数据包抽象而得的, 并用该协议对应的入侵模式进行检测分析即可。这样就避免了用多个模式依次试探匹配的盲目性及由此引起的低效率问题。
2.2 利用TCP数据包进行的攻击
用同样的方法, 可以将用TCP数据包进行的攻击抽象为如下攻击模式:
ITCP (S, C, ITCP, P)
其中:C={j, k, l, m}是以下攻击特征信息的集合:
根据这个描述模式, 对TCP SYN FLOODING攻击的探测过程, 参照图2的检测分析树。这时, 数据解析程序输出的特征信息序列可能是j…jk, 这是经过滤预处理的特征信息序列, 其中j的重复次数超过了设定的阈值:
(1) 系统开始处于正常状态, 由于协议数据包解析程序输出的特征信息序列中第一个信息标记为j, 检测分析程序根据产生式S1→j归约到S1。由此可确定出现地址假冒攻击, 并报警发现了地址假冒的IP数据包。
(2) 在归约到S1后, 分析器读到特征信息序列中下一个信息标记仍然为j, 用S1→S1j再次归约为S1;依此类推, 分析器连着若干次用S1→S1j归约为S1。
(3) 经若干次用S1→S1j归约到S1后, 若协议解析程序输出的特征信息序列中下一个信息为k, 检测分析程序根据当前状态, 用ITCPSYNFLOODING→S1k归约到状态ITCPSYNFLOODING。接着, 用ITCP→ITCPSYNFLOODING归约到ITCP, 并根据分析过程中的属性值的传递, 确定发生了TCPSYNFLOODING攻击。
(4) 在第二步后, 即经若干次用S1→S1j归约到S1后, 若协议解析程序输出的特征信息序列中下一个信息为m, 而不是k, 检测分析程序根据当前状态, 用ITCPFAKE→S1m归约到状态ITCPFAKE。接着, 用ITCP→ITCPFAKE归约到ITCP, 并根据分析过程中的属性值的传递, 确定发生了ITCPFAKE攻击。
用同样的方法, 可以为其他类型的攻击建立模式, 如针对其他网络协议数据包的攻击或针对主机系统的攻击类等。
3 入侵模式的可扩展性
黑客攻击的方式是日新月异的, 新入侵不断涌现。初始建立的模式库中没有后来才出现的入侵模式。而一个好的滥用入侵检测系统需要经常更新和丰富模式库。在新的攻击方式出现的时候, 解析程序可能发现其对应的特征信息序列, 而用相应的模式对这个新的特征信息序列进行语法分析时, 检测分析程序必然会报告异常的发生, 此时可以根据这个新的特征信息序列对相应的模式进行扩展改造——加入能够派生出该特征信息序列的派生式。比如, 如果这个新的特征信息序列是由TCP协议数据包解析程序识别的, 则检测分析程序用TCP类攻击模式对这个特征信息序列进行语法分析时应该报错, 这是因为根据已经构造TCP类攻击模式, 这个新的特征信息序列不属于对应文法模式的句子, 所以必然在分析的某一步报错——发现异常的特征信息序列。这样, 可以根据这些新出现的特征信息序列对相应的入侵模式进行修改或增加新的入侵模式。用这种方法, 入侵模式库可得到不断的更新和丰富。从这个角度说, 由于文法描述模式的可扩展性, 基于特征信息序列语法分析的入侵检测技术是一个滥用检测和异常检测的综合技术, 不仅可以确定已知类型的入侵是否发生, 还可以发现异常系统或网络行为的出现。
4 结 语
本文针对滥用入侵检测常用技术存在的不足, 提出了基于特征信息序列语法分析的入侵检测技术。通过该技术, 可以有效避免匹配分析过程的盲目性和试探性, 提高检测分析的效率。另外, 由于文法描述模式的可扩展性, 使得基于特征信息序列语法分析的入侵检测技术成为具备一定异常检测能力的滥用检测技术, 即能确定已知类型入侵是否发生, 也能及时发现新出现的异常系统或网络活动的发生。
参考文献
[1]唐正军.入侵检测技术导论[M].北京:机械工业出版社, 2004.
[2]Kumar S, Spafford E.An Application of Pattern Matching inIntrusion Detection[Z].Department of Computer Science, Purdue University, CSD-TR-94-013, Coast TR 94-07, 1994.
[3]张燕, 刘方爱.IDS中一种新的模式匹配算法及其并行化[J].山东科学, 2005, 18 (11) :134-138.
[4]胡睿, 张冬茉, 杜蓬.用有限状态转换图来识别系统入侵[J].计算机工程与应用, 2001, 37 (20) :81-84.
[5]Hochberg J, Jackson K, Stallings C, et al.NADIR:An Auto-mated System for Detecting Network Intrusion and Misuse[J].Computers and Security, 1993, 12 (3) :235-248.
[6]周子庭, 李建华.系统日志分析及在主机入侵检测中的应用[J].信息安全与通信保密, 2004 (9) :31-33.
[7]刘美兰, 南相浩, 姚京松.基于审计的入侵检测系统[J].计算机工程, 2000, 26 (Z1) :127-132.
检测序列 篇7
关键词：入侵检测,序列比较算法,相似性
1 引言
入侵检测的研究是当前的研究热点[1,2,3,4],最早可追溯到James Anderson在1980年的工作,他首先提出了入侵检测的概念,将入侵尝试(Intrusion attempt)或威胁(Threat)定义为:潜在的有预谋未经授权访问信息、操作信息、致使系统不可靠或无法使用的企图。入侵检测是识别网络攻击的主要手段。
序列比较分析与入侵检测具有着很大的相似性:从目的上看,序列分析其目的即寻找一个最大可能长度的序列,而且此序列同时被二个序列所拥有。即寻找序列直接的相似性。入侵检测分析即分析监测行为与用户过去行为,找出这两种行为之间的差别和相同点。从实现手段上看,序列分析其无非是寻找到序列之间最大可能的匹配段,很可能就是一条最佳匹配序列。入侵检测分析则是寻找监测行为与用户过去行为的异同,通过偏差度来做为手段分析异同。从结果显示上看,序列分析会由得分函数得到相似度数值,由数值的大小表征序列之间的相似情况。入侵检测分析则是通过判断监测行为与用户过去行为相似与否,作出正常或者异常的判断。本文将试图把这种技术应用于专用网的拒绝服务攻击的入侵检测中去。
由于大多数的入侵检测都会以用户命令序列的分析作为开始。这种分析与序列比对分析有着很大的相似性。对于全局联配和局部联配技术,事实上单独地将任意的一种用于入侵检测都是不合适的。在全局联配中,两条序列要么匹配,要么需要加入空格,在入侵检测中有可能只有一小部分是不匹配的,而序列的大多数部分是匹配的,从而掩盖住了相似性部分大于不匹配部分这一事实。而局部联配会忽略掉大多数的数据,尽管匹配部分匹配值很高,但是实际上这没有任何的意义。本文采用了一种Smith Waterman序列比较算法[2],有效地提高检测效率。
2 相关设置
2.1 得分函数的特殊设置
得分函数是用来评定序列相似性的方法,主要包括对匹配以及不匹配的得分。匹配记为正分,不匹配或者加入了编辑操作的情况记为负分。这种记分函数的选取方法对于入侵检测是不合适的。由于入侵检测一部分高度相似,其余部分相似。对应的在测试序列中出现空位,在正常序列中有空位的影响小的多。而当出现完全不匹配的情况,此时两条序列相似度是及其低的。因此对得分函数进行特殊设置:+1,两个序列是匹配的;-1,正常序列中有空位;-2,测试序列中有空位;0,完全不匹配的情况。这种设置有利用入侵检测行为的比对,使匹配得分值能更好的反映监测行为与用户行为的差异。
2.2 比对数据的选取设置
序列的比对对所有的数据如果采用所有数据都进行比较的方法,对应的整体数值就会偏低,从而不能反映某一个区域相似性非常的高这一特性。所以选取设置可以将数据中的一部分给予剔除,由于这一部分的不匹配将会带来过多的负分,从而影响总体的得分。选取设置只截取头部或者尾部的数据进行去除处理。选取美国兰德公司提供的入侵检测数据SEA Data,对采集的数据进行测试并分析。
3 算法测试分析
算法衡量的主要标准有:False Postive Rate(错报率),即将非入侵数据检测为入侵数据的百分率;False Negative Rate(漏报率),即将入侵的数据检测成为非入侵数据的百分率;Hite Rate(命中率),即将入侵的数据检测为入侵数据的百分率。首先将要从数据的角度阐述测试的步骤,然后从阈值选取、记分函数选取和实验结果参数分析三个方面对测试结果进行分析。
本文使用的测试数据包含着50个文件。每一个文件包含有着15,000个命令,最开始的5000个数据是不包含任何入侵数据的,在实际测试中将会把这5000个数据作为正常数据看待。接下来10000个数据将其分为100个块,每一个块中包含有100个命令,在这些块中散布着入侵者的数据。在测试数据的入侵数据是人为制造的。50个文件的数据,来源于两个组用户(50和20个)。人为地将前50个用户的命令序列认为是正常用户的命令。若出现后20个用户的命令序列,视为入侵者的序列数据。在这些数据中,如果当前的块不包含入侵,接下来的块中包含入侵数据的可能性为1%;如果当前块包含入侵,接下来的块中包含入侵的可能性为80%。
SEA数据中入侵的位置分布包含有100行与50纵对,每一个纵对对应于50个SEA数据文件中的一个,每一行对应于一个数据块。开始于数据的第5001个位置截止到15000个位置(由于前5000个作为正常数据)。分布图中包含着0或者1,0意味着对应的这个数据块是不包含入侵的,1则代表着这个数据块中包含着入侵。
3.1 检测步骤介绍
SEA标准数据测试实验用到的数据是比较庞大的,将所有的750,0000个数据进行测试总共要进行50×100×4901=24,505,000次。通过编程和检测步骤的优化,可以将检测次数下降到5000次左右,总共使用二个月左右的时间完成数据的测试。并将所有数据结果取平均得到测试实验结果。
为了方便步骤的解释,这里只拿50个数据文件中的第一个数据文件,而且选取这一数据文件中第一块数据作为例子。实际上每个数据文件的每块数据都是使用相同的方法(以下简称Data1,Block1)。SEA标准数据测试实验步骤主要包括以下几个步骤:
1)将Data1加载于程序,将Data1的前5000个数据提取作为正常测试数据,将其他的10000个看作是100个块,每个块包含100个数据,测试中块是最为基本的单元。
2)Data1阈值的选取,将Data1数据做20次随机实验,每次实验抽取100个数据与随机抽取的1000个数据进行匹配,将20次随机实验的平均值看出为Data1的阈值。
3)记分函数的选取,在实验中一律选取匹配计为+1分;若在正常数据中出现空位,计为-1分;若在测试数据中出现空位,计为-2分;完全不匹配计为0分。
4)将Block1分别与Data1的正常数据做4901次匹配,匹配中用的是序列比较算法。匹配后得到的最佳匹配序列按记分函数打分,记录4901次的最高得分。
5)将Data1的100个数据块按步骤4)处理,记录测试结果。按照2)的阈值判断入侵与否。
6)将Data1到Data50重复以上实验步骤,得到测试算法判断入侵分布图,将该图与标准入侵分布图相比较,由参数定义求得本次实验最终测试结果。
另外可以改变步骤3)的记分函数选取测试记分函数不同对实验最终结果的影响。
3.2 数据测试实现分析
实验选取VC作为编程语言和平台,以下将首先就测试的流程加以说明,然后为几个主要测试块运行步骤和结果进行了截图。
执行步骤如下:首先通过算法的初始化定义和矩阵推导可以得到一个得分矩阵,然后由得分矩阵得到最佳匹配序列,最后根据设计的得分情况给出序列匹配得分,根据这个匹配得分的高低,与阈值大小判断入侵与否。整个流程包括:1)对用户的操作提取特征行为数据;2)对提取的数据进行预处理;3)利用了序列比较算法,对用户数据序列与正常的数据进行算法匹配,通过得分函数得到匹配得分;4)与阈值比较,若判断为入侵,则进入系统报警处理环节。若正常,则返回开始界面,重新开始新一轮检测。
4 系统性能分析
4.1 攻击路径长短对错误判断率的比较
下面通过模拟实验分析和评估的性能。以某个ISP服务商的实际运行的网络拓扑结构为基础,取其中的50个主要路由器。在该网络中随机的选择一个攻击源和被攻击主机,从攻击源以自适应的概率发出1000个攻击数据包。每个数据包在攻击被攻击主机的路径中,通过路由器(已经安装了SHTE引擎的路由器)时都以自适应概率的方式进行标记。追踪过程从模拟的被攻击路由器开始,直到攻击源为止。均匀的通信量以最大错误概率P来模拟每个路由器之间的通信。虽然真实的情况并不是相同的通信量,由于错误判断对通信量是否相同起的作用很少,因此认为这种表示攻击的起点是正确的。为了精确模拟网络中的真实通信负荷,有效的错误判断率要根据不同路由器进行调节的。
明显地,没有被标记的数据包只包含一个源地址和目的地址。有多个攻击源的初步实验显示了错误判断率随着攻击路径的增长而成直线上升。图1显示了以标记概率0.125的情况下,攻击路径长短对错误判断率的影响的比较图。直线代表分析的错误判断率,曲线代表实际错误判断率。图中曲线表示的非线性表明网络拓扑结构对错误率的影响。很明显,如果一个路由器周围有很多路由器相连,那么它就是处于中心地带,相反,如果周围相邻的路由器比较少,就处于网络拓扑的边缘。由于处于边缘的路由器相比中心路由器通过的数据包少,那么错误判断率也将有所增加。
系统追踪关键是SHTE引擎查询是否成功。SHTE引擎资源的请求由数据包摘要通过光晕滤波的数量和存储摘要表的存储量决定。利用SHTE引擎追踪的特性也有2方面:第一,数据包摘要保存的时间。只有查询中心在数据还没有为存储更新数据包摘要信息前查询该摘要信息,才能查到正确的数据;第二,保证在错误判断的情况下SHTE引擎的正确性。
4.2 阈值对实验结果影响及分析
在提供检测数据的网站中,提供了研究成熟的6种算法的阈值,而对于本文研究的算法,图2是阈值的选取对实验结果的影响图。(深色线为漏报率,浅色线为错报率)从图上可以清晰的看到阈值选取对错报率和漏报率的影响情况。(下转第879页)(上接第872页)
通过对图2的分析,可以看到阈值选取对实验参数有着很重要的影响。阈值取的过于低,则几乎所有的数据块都会被测试为不包含入侵,这样会带来很高的漏报率,同时错报率是低的。当阈值的选取比例为0%时,所以的数据都被认为是正常的数据,此时错报率为0%,漏报率也达到最高值。而阈值选取过于高,则很多数据块都会被认为含有入侵,此时错报率较高,同样对实验结果不利。
4.3 记分函数对实验结果影响及分析
在入侵检测序列匹配记分过程中,记分函数也会对实验结果有着影响,下表描述了记分函数对实验影响。下表的数据来自于对一个数据块变换得分函数值后测试结果。可以看到记分函数值对实验结果有着影响,但是不是非常的大。增加序列匹配得分值,一方面会提高实验的命中率,但是实验的错报率也相应的增加;增加置空位的负分值,则命中率和错报率均会有一定的提高。
4.4 实验结果参数分析
数据提供的网站介绍了六种算法的实验结果(如表2)。
采用的算法,经过多次的重复性实验取得平均值,通过实验其命中率可以达到接近70.1%,错报率为2.1%。
5 结论
该文从阐述序列比较入手,分析了序列比较算法。通过对序列比较与入侵检测行为比较的相似性研究,采用了一种序列比较算法应用于专用网的拒绝服务攻击的入侵检测中。使用标准数据和收集数据对其进行测试,从阈值选取、记分函数选取和实验结果参数分析三个方面对算法进行了分析,取得了较好的实验结果。
参考文献
[1]Elliott J..Distributed Denial of Service Attack and the Zombie Ant Ef-fect[J].IP Professional,March/April 2000,55-57
[2]蒋建春,冯登国.网络入侵检测原理与技术[M].北京:国防工业出版社,2001.
[3]Chang H Y,Narayan R,Sargor C,et al.Decentralized Source Idetification for Network-Based Intrusions[C].Proceeding of 6th IFIP/IEEE International