基于K―means的视频智能存储算法

开篇：润墨网以专业的文秘视角，为您筛选了一篇基于K―means的视频智能存储算法范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

智能存储是指将视频序列分割成几个完整的部分，方便客户回溯、查找可疑信息和视频后期处理，对于纯背景画面或者是那些长时间几乎没有变化的画面，选择放弃存储，在节约存储代价的同时也精简了视频序列。以摄像头异常检测为基础，在视频监控阶段提取视频图像的特征，利用K-means聚类算法将帧图像分门别类、然后将其存储到事先准备好的标签下，形成标准的视频文件。其过程包括动态特征提取、利用聚类算法进行聚类、将视频帧图像分类存储。

【关键词】动态特征提取 K-means聚类算法 信息增益比率 智能存储

1 引言

监控设备的普遍性带来了视频信息的爆发式增长，将这些海量信息分门别类、做上标记，然后将其选择性的储存，这一需求随之变得越来越迫切，因为这样不但能够帮助用户有效的检索相关信息和迅速的获取感兴趣的视频信息，而且能够节省大量的内存，但是这项工作需要一个能够对这些海量视频进行自动分析和处理的智能监控系统来完成。

通过智能监控系统可以将视频流分为三类选择性的存储：

（1）有运动目标的视频序列，可以用来实现人群密度估计、运动目标检测等。

（2）放弃纯背景的视频序列，节省内存。

（3）恶意遮挡摄像头、扭动摄像头的视频序列，方便对异常事件的定性并报警。

视频智能存储算法一般是在摄像头异常检测算法的基础上完成的，摄像头异常检测的基础主要是背景建模或特征提取。背景建模主要有单高斯模型、码本模型、混合高斯模型等，上述算法缺乏实时性，因此不适合应用到视频智能存储算法上去。文献[3]中首次将轮廓波应用到摄像头干扰异常检测中，通过比较背景图像与视频图像的特征函数做出判断，虽然该算法缺少自适应性，但可以借鉴特征提取的方法。

2 视频序列分割原理及特征提取

为提取视频流的特征，借鉴文献[4]中的方法，将摄像头拍摄到的视频流截成两段，分别存储到两个不同长度的缓存区中去，即长缓存区和短缓存区。帧图像顺序被存放在短缓存区中，若短缓存区中已满，则将短缓存区中最先进来的那一帧视频图像存放到长缓存区中去，若长缓存区中也已满，则将长缓存区中最先进来的那一帧视频图像丢弃。其存储流程如图1所示。

每一次抽样检测时，长短缓存区都会被比较然后判断异常是否发生。短缓存区中的每一帧都要和长缓存区中的每一帧进行比较，取其比较结果的中值，记为Dbetween。将长缓存区中的任意两帧视频图像进行比较，取其比较结果的中值，记为Dlong。

图2是在拍摄的几段视频中，随机抽取的一段视频，其中含有的事件个数为8个，分别是：有运动目标的3个（比较高的3个红线）、被扭动的2个（比较低的2个红线）、被遮挡的3个（蓝绿混合的3个突出的线）。数据没有做对数变换。

从图2可以看出直方图的绝对差能够准确的反映出来帧图像序列的变化，当视频画面出现明显的变化时，相应的数值分量会达到不同的峰值，然后可以借助于聚类技术将相同范围内的数据峰值聚类到一起（尤其是K-means聚类算法具有很好的实时性，其复杂度为O（n），n为对象个数）以这些峰值点为依据，将缓存区中前后连续的帧图像序列存储到事先准备好的标签下面，完成视频的智能存储。

3 以信息增益比率的加权距离计算方法为基础的K-means聚类算法

K-means聚类算法是把n个数据对象划分为k个类别，使每个类别中的数据点到该类的聚类中心的距离的平方和最小，算法具体流程如图3所示。

全部对象每被分配完一次就会被重新计算聚类中心，不断重复，直到标准测度函数收敛为止，一般采用均方差作为标准测度函数：

E为数据集合中所有对象的均方差之和，P为任一对象数据点，mi为类别Ci的均值。

在计算对象到各个聚类中心的距离计算中，欧氏距离是常用的计算方法，而权值信息能够完全的反映各个特征分量在聚类或者分类过程中对未知类别的倾向程度。所以准确的权值为提高聚类质量提供了一个可能，若每一变量均可被赋予一个权值，以表示其所代表属性的重要性。那么带权值的欧氏距离计算公式为：

在统计属性中，信息增益是衡量属性价值的一个好的定量标准。因此属性的信息增益值决定了属性在分类过程中的贡献大小，而在聚类算法中，相似度的度量使用的是距离的计算方法，特征属性作为距离计算中的一个子量，所以它的信息增益值可以作为权值表示该属性在距离计算过程中的贡献大小。

现假设样本数据集合为X={x1，x2，…，xN}，其属性集合为A={A1，A2，…，Aq}，设Ai（1≤i≤q）具有v个值，利用属性Ai将X划分为v个子集{X1，X2，…，Xv}，设分类属性具有m个值，根据分类属性将样本集合划分成m个子集{C1，C2，…，Cm}，设Xij为子集Xj中属于类Ci的样本数量。基于信息增益比率的属性加权计算步骤如下：

（1）若属性是连续的则将其进行离散化处理，否则省略此步骤；

（2）含有未知属性值的训练样本进行相应的处理；

步骤3 根据聚类结果，借助于长短缓存区将其补全以视频流的形式存储到相应的标签下面，完成对视频的动态智能存储。

4.2 仿真实验

测试视频采用分辨率为320*240的视频序列，选取了50个事件，依照采样规则，从中抽取出来1675个数据，然后将其分为两部分，其中训练样本数据集的个数为400个，包括纯背景事件中的96个数据对象、出现运动目标事件中的103个数据对象、摄像头被扭动事件中的103个数据对象以及摄像头被遮挡事件中的100个数据对象；剩下的1275个数据对象为测试数据集，其中包括在纯背景事件中的378个数据对象、出现运动目标事件中的294个数据对象、摄像头被扭动事件中的306个数据对象以及摄像头被遮挡事件中的297个数据对象。

（1）计算权值。将上述400个测试样本记为S，分布如表1所示。

然后将其归一化，则得到相应的权值。

（3）将上述权值带入距离的计算公式，实验结果如表3所示。

在展示实验结果之前先引入两个概念，即检测率ρr和误报率ρe，测试数据集T={T1，T2，T3，T4}，Ti为各个事件相对应的数据总数，i=1，2，3，4，经过聚类后所得到的数据集记为T_k={T_k1，T_k2，T_k3，T_k4}，其中T_ki为各个事件相对应的数据总数，且T_ki=ri+ei，i=1，2，3，4，ri表示被正确聚类的个数，ei表示被错误聚类的个数。

能够得出上述实验结果中较高的准确率，与视频序列的特征提取方法准确、及时分不开；而且在K-means聚类过程中，使用了信息增益比率的加权距离计算方法来度量样本数据点和当前聚类中心点的相似度，依靠权值各个特征分量能够在聚类算法中的优势发挥出来。

5 结论

基于K-means的视频智能存储算法取得了较好应用成果，在动态多特征组合的基础上利用聚类算法将视频序列分门别类，达到智能存储的目的。如何简单快捷选择聚类中心和减少对于运动目标的重复存储，是接下来研究的重点。

参考文献

[1]谭铁牛.智能视频监控技术概述[C].北京：第一届全国智能视觉监控学术会议，2002.

[2]C R Wren，A Azarhayejani.Pfinder： Real-Time Tracking of The Human[J].IEEE Transaction on Pattern Analysis and Machine Intelligence，vol.19，no.7， pp.781-785，1997.

[3]梁爽.基于轮廓波的摄像头干扰检测[D].河北师范大学，2012.

[4]徐红丽.智能视频监控中的摄像头异常检测[D].河北工业大学，2012.

[5]杨圣云，袁德辉，赖国明.一种新的聚类初始化方法[J].计算机应用与软件，2007，8（24）：51-52.

[6]Sergios Theodoridis.Pattern recognition[M].China：Publishing House of Electronics Industry，2010.

作者简介

郝伟杰（1985-），男，硕士研究生学历。现供职于阳煤集团深州化工有限公司。研究方向为图形图像处理。

作者单位

1.阳煤集团深州化工有限公司 河北省衡水市 053000

2.石家庄市环境监测中心 河北省石家庄市 050000