2. 陕西省人民警察培训学校, 陕西 西安 710054
视频关键帧主要用于构成视频索引，类似一本书的目录，可方便用户快速查询到感兴趣的视频片段[1]。近年来，随着公安监控系统的不断完善，视频信息已成为公安机关侦查破案的重要信息来源。然而面对海量的视频数据，如何快速查找到侦查所需的视频片段成为公安视频侦查的一大难题。本文从公安视频侦查中的兴趣点出发，提出一种快速的监控视频关键帧提取算法，该算法能有效提取监控视频中的所有包含运动目标的帧作为关键帧，既缩减了关键帧数目又不遗漏视频中的侦查信息。算法有望在海量公安视频检索中取得进一步的应用。
1 运动目标检测运动目标检测是视频分析和目标识别的第一步，快速正确检测运动目标可为后续的目标分类、跟踪和行为理解等提供良好基础[2]。目前主要的检测方法有帧间差法、均值背景法、高斯混合模型、特征背景模型以及核密度估计法等[3, 4, 5, 6]。
1.1 基于联合梯度的运动目标检测方法本文使用一种基于联合梯度的运动目标检测方法，该算法首先利用时间梯度确定候选像素点，然后求候选点在当前帧中的单帧图像梯度，从而确定运动目标。
将数字视频可以作为时间轴上的数字图像序列，图像上点(x,y)的灰度值f(x,y,t)随时间t变化，当坐标点恒定时该函数是关于时间t的一维函数[6]。
数字视频的时间梯度可定义为向量
该向量的幅值为 对离散时间序列，幅值可近似表示为 该向量的角度为
时间梯度反映了视频图像在每一点的变化情况，当视频中目标运动时，将引起从初始位置到目的位置之间整个轨迹的时间梯度变化。
数字视频的单帧梯度定义为向量
该向量的幅值为 通常，该向量用绝对值 来近似。该向量的角度为
单帧梯度描述了某时刻像素点灰度值相对其他像素点的变化情况。在适合阈值下可得到边缘图像，这些边缘包含了运动目标和非运动目标像素点。
在利用视频时间梯度得到运动目标候选点的基础上，求候选点的单帧梯度，可称为数字视频的联合梯度。联合梯度有效反映了视频图像中运动目标的边缘信息，并对视频中的运动噪声有一定抑制作用。
1.2 检测中一个负作用的利用在基于联合梯度运动目标检测的实现过程中，我们发现一个有趣的负作用。即当视频图像中出现运动目标时，该算法能准确地检测到运动目标的边缘图像；但当视频图像中不存在运动目标时，背景相对变化非常小时，算法检测的结果出现分散的噪音点。如图 1所示。
 |
| 图 1 KTH walking person01第123帧和第237帧的检测结果 |
这是由于在计算时间梯度的过程中是根据动态阈值提取运动目标的候选点，而非固定阈值。当不存在运动目标时，背景变化不大，时间梯度都很小，相对较大的点分散在整个画面中，因此提取结果为分散的噪音点。
这个现象虽然可以通过改用固定阈值消除，但固定阈值在运动目标出现时提取效果不佳，而且对不同的视频数据不具备鲁棒性。值得注意的是，采用动态阈值提取的结果在有无运动目标下有明显的区别，因此可利用这个负作用将视频划分为子镜头。在公安监控视频中这种无运动目标，背景相对不变的子镜头占整个视频数据相当大的比例。如果能快速去除这些子镜头，而只对有运动目标的子镜头提取关键帧，将大大减少视频数据的检索时间。
2 基于聚散熵的子镜头划分为了有效区分视频中有无运动目标的检测结果，将监控视频数据划分为小段的子镜头，定义了二值图像的聚散熵。下面介绍聚散熵的概念及基于聚散熵的视频子镜头划分。
2.1 聚散熵的定义信息熵是信息论中用于度量信息量的一个重要概念，代表了信源的平均自信息量。从信息传播的角度来看，信息熵可以表示信息的价值，用来衡量信息价值的高低。
信息熵的计算公式为
式中，P(ai)表示事件ai出现的概率[1]。
信息熵是信源的平均不确定性的描述，信息熵越大表示信源的平均不确定性越大。
根据信息熵的概念我们引入二值图像聚散熵的定义。
定义1 二值图像的聚散熵为二值图像包含信息的平均不确定性的描述，其计算公式为
式中，M，N为二值图像f的大小，p(xi,j)为某一像素点在某位置出现的概率。
分别为像素点行和列上的位置均方差，其中
通过定义可看出二值图像的聚散熵反映了二值图像的聚散程度。当像素点在画面中分散程度越大，则说明图像所携带信息的平均不确定性越大，信息量越少，因此熵值也就越大。反之当像素点较为集中，说明信息不确定性小，信息量大，熵值就小。图 2给出2幅二值图像及他们的聚散熵值。
 |
| 图 2 二值图像的聚散熵 |
通过上面定义的聚散熵可以很方便地区分联合梯度运动目标检测的结果。在没有运动目标的子镜头中聚散熵相对较大，当运动目标出现聚散熵急剧减小，并在有运动目标的子镜头中一直保持很低的熵值。当运动目标移出画面，聚散熵又急剧增大，回到高值。图 3是一实验视频在有无运动目标时聚散熵的变化情况。
 |
| 图 3 KTH walking person01的聚散熵 |
为了实时检测视频子镜头边界，并去除某些不确定性产生的干扰，使用一个移动的窗口对时间轴上的聚散熵进行均值滤波，然后进行二值化处理。如图 4所示。可明显看到，包含运动目标的子镜头以0→1上升沿开始，以1→0下降沿结束。而无运动目标的子镜头正好相反。从而标记了视频子镜头的边界。
 |
| 图 4 聚散熵均值滤波及二值化结果 |
目前视频关键帧的提取主要方法包括：镜头边界法、视频内容分析法、光流分析法及聚类法等[8]。虽然每种方法各有优点，但仍不能满足公安监控视频检索的需要。本文结合边界法与视频内容分析法，提出基子镜头运动目标检测的关键帧提取方法。
3.1 关键帧提取方法前面已经在划分子镜头前对整个视频进行了基于联合梯度的运动目标检测。对按照检测结果通过聚散熵对视频进行了子镜头划分，得到了有运动目标的“动子镜头”和无运动目标的“静子镜头”。
公安视频侦查关注的是运动目标的个数及其外貌特征。用于检索的关键帧需要能反映运动目标数目的变化情况，以支持后续的目标特征识别需要。对占整个数据很大比例的静子镜头只须提取其中间一帧作为关键帧，以反映背景情况。对于动子镜头需要进行进一步划分。由于运动目标具有边缘联通的特点，按照联通区域的变化情况将动子镜头划分为单独运动目标出现消失的小片段，再用小片段的中间帧作为关键帧，以反映每个独立运动目标的特征。
3.2 算法描述Ⅰ.设置初始帧值k:=1
Ⅱ. 输入视频数据第k帧、第k+1帧
Ⅲ. 检测运动目标
⑴ 计算时间梯度得到图像H
⑵ 计算H的单帧梯度
⑶ 动态阈值提取边缘图像I
⑷ 去噪处理
Ⅳ. 计算聚散熵
⑴ 边缘图像I的聚散熵E
⑵ 以w为窗口大小，计算E的均值Ew
⑶ 以l为阈值二值化Ew，得到Eb
Ⅴ. 根据Eb进行判断
⑴ 上升沿，则记录为静子镜头的起点，动子镜头的终点，执行Ⅶ
⑵ 高值，则执行Ⅶ
⑶ 下降沿，则记录为动子镜头的起点，静子镜头的终点，执行步骤Ⅵ
⑷ 低值，则执行Ⅵ
Ⅵ. 根据运动目标数目记录变化位置
⑴ 对边缘图像I的进行形态学处理，去除噪点，连接断点
⑵ 统计所有联通区域数目，以总像素的q%为阈值，提取运动目标数目。
⑶ 如果运动目标数目变化，则记录为动子镜头变化点。
Ⅶ. 令k:= k+1，转到步骤Ⅱ，直到视频结束
Ⅷ. 根据记录的子镜头起始位置，及动子镜头变化点，取中间帧为关键帧，输出
4 实验结果及分析为了更客观评价算法效果，我们选取KTH数据库、Weizmann数据库、CASIA数据库以及自建公安监控视频库作为实验数据，其中公安监控视频库(PSV)选取不同天气和时段中僻静家属区和繁华街面的实际监控视频段共20段。下面给出部分实验结果，及对实验结果的分析。
4.1 实验结果图 5为在行人较少的家属区中一段实际公安监控视频的关键帧提取结果。该视频时长1分钟共1 500帧，其全查率100%，查准率为87%，关键帧提取比为0.53%。
 |
| 图 5 公安监控视频中提取的关键帧 |
本文使用平均全查率(AFSR)、平均查准率(AP)，以及平均关键帧提取比(AKER)，即关键帧数目与视频帧数之比，作为结果评价依据。在4个不同视频库中的全部视频中进行实验。表 1为在不同视频库中关键帧提取的平均全查率和平均查准率及平均关键帧提取比。
| 视频库 | ASFR | AP | AKER |
| KTH | 100% | 99.6% | 1.167% |
| Weizmann | 100% | 100% | 0.121% |
| CASIA | 99.3% | 86.7% | 1.876% |
| PSV | 99.2% | 70.5% | 2.421% |
通过实验结果，可看到该算法在运动目标数目较少，出现频率较低的情况下达到最优的效果。尤其在单个运动目标不重叠出现的视频中可100%的全查率和查准率。 在自建公安监控视频库中查准率相对较低，主要是由于运动目标重叠交叉引起。但公安视频侦查中检索的目的是反映所有运动目标的外貌特征，以便在最短时间内确定侦查线索的位置。因此，有少许冗余误检帧是可以接受的。本算法在所有实验视频中都取得良好的全查率，不会遗漏移动目标，满足公安侦查的需要。本算法有很低的关键帧提取比，在海量监控视频检索中，可大幅缩减检索时间。
5 结论本文针对海量公安监控视频检索的需要，提出一种基于聚散熵及运动目标检测的视频关键帧提取算法。该算法利用聚散熵将视频分为有运动目标的动子镜头和无动目标的静子镜头，再通过对运动目标数目的统计对动子镜头进行进一步划分，从而提取视频关键帧。这种关键帧的提取方法能满足公安视频侦查的需要，在不遗漏运动目标的前提下，最大程度减少关键帧数目，并记录运动目标的外貌特征。对后续的人工或自动的目标识别和分析起到了很好的支撑作用。实验表明，该算法在不同拍摄场景、不同天气和光照条件下都具备很高的全查率和查准率。在公安视频侦查中有很强的实用价值。
| [1] | Wang Yao, Ostermann J, Zhang Yaqin. 视频处理与通信[M]. 侯正信, 译. 北京:电子工业出本社, 2003 Wang Yao, Ostermann J, Zhang Yaqin. Video Processing and Communication[M]. Hou Zhengxin, Translator. Beijing: Publishing House of Electronics Industry, 2003 (in Chinese) |
| [2] | 雷少帅. 基于内容的视频检索关键技术研究[D]. 太原:太原理工大学, 2012 Lei Shaoshuai. Besearch on Some Key Techniques of Video Retrieval Based on Content[D]. taiyuan: Taiyuan University of Technology (in Chinese) |
| Cited By in Cnki | |
| [3] | Zhan Chaohui, Duan Xiaohui, Xu Shuoyu. An Improved Moving Object Detection Algorithm Based on Frame Difference and Edge Detection[C]//International Conference on Image and Graphics (ICIG), 2007: 519-523 |
| Click to display the text | |
| [4] | Zhao Chunhui, Liu Wei, Wang Yi, Cheng Yongmei. A Fast Algorithm for Moving Objects Detection Based on Model Switching[C]//International Conference on Audio, Language and Image Processing (ICALIP), 2008: 143-146 |
| Click to display the text | |
| [5] | Mukherjee D, Wu Q M J, Nguyen T M. Multiresolution Based Gaussian Mixture Model for Background Suppression[J]. IEEE Trans on Image Processing, 2013, 22(12):5022-5035 |
| Click to display the text | |
| [6] | Yang Yun, Liu Yunyi. An Improved Background and Foreground Modeling Using Kernel Density Estimation in Moving Object Detection[C]//Computer Science and Network Technology (ICCSNT), 2011: 1050-1054 |
| Click to display the text | |
| [7] | Gonzalez R C, Woods R E. 数字图像处理[M]. 阮秋奇, 译.2版. 北京: 电子工业出版社, 2005 Gonzalez R C, Woods R E. Digital Image Processing[M]. Ruan Qiuqi, translator.2nd Edition. Beijing: Publishing House of Electronics Industry, 2005 (in Chinese) |
| [8] | Worf W. Key Frame Selection by Motion Analysis[C]//IEEE International Conference on Acoustics, Speech and Signal Processing. Atlanta, USA: IEEE Computer Society, 1996 |
| Click to display the text |
2. The People's Police Training School of Shaanxi Province, Xi'an 710054, China