基于相关系数的道路监控视频关键帧提取算法

蓝章礼，帅 丹，李益才

( 重庆交通大学 信息科学与工程学院，重庆 400047)

基于相关系数的道路监控视频关键帧提取算法

蓝章礼，帅 丹，李益才

( 重庆交通大学 信息科学与工程学院，重庆 400047)

为从固定摄像头的道路监控视频中有效地提取出关键帧，提出了基于相关系数的关键帧提取算法。算法将监控视频中图像帧的RGB值处理为灰度值，结合滑动窗口机制，通过当前帧和当前关键帧之间相关系数的绝对值与阈值比较判断当前帧是否为关键帧。实验结果表明：算法在有效提取关键帧的同时还具有流程清晰、避免了冗余关键帧的特性。最后利用基于欧式距离的帧间差异性对提取的关键帧进行评价，验证了算法的有效性和合理性。

交通运输工程；关键帧；相关系数；滑动窗口；道路监控

随着网络和多媒体技术的飞速发展，涌现出了大量多媒体信息。为方便管理和索引海量的视频数据，视频数据库管理系统得到了广泛应用。视频数据库管理系统中需要有效地视频摘要、视频检索技术，而这些技术的基础和关键是如何有效地提取关键帧[1-5]。尤其在道路监控中，存在大量的视频数据需要存储和分析、处理。

关键帧是镜头中最具有代表性、最重要的一帧或者多帧图像。提取的关键帧一般满足两个基本原则：尽可能完整、准确地反映镜头的主要内容；数据量小，计算简洁。关键帧提取技术的使用，大大减少了视频数据的处理量，为视频摘要和检索提供了组织框架。

1 典型的关键帧提取算法

关键帧提取技术因其在视频摘要和视频检索中的重要地位，近几年得到了广大研究者的广泛关注，同时也有一些重要的研究成果。关键帧的提取主要有以下几种方法。

1.1 基于镜头边界提取关键帧

当一段视频分割为镜头之后，将每个镜头的第一帧或者最后一帧作为该镜头的关键帧，如视频镜头边界检测及关键帧提取算法[6]，及基于多种视频特征的镜头边界检测算法[7]。此类方法实现简单，运算量小，关键帧数目一般固定，但选取的关键帧多数情况下不能完整的反映一个镜头的信息，不具有代表性。

1.2 基于聚类提取关键帧

镜头聚类主要研究镜头之间的关系，即如何将内容相近的镜头组合起来，先初始类中心，再将当前帧的特征值与某个类的距离进行比较，判断当前帧是归于某个类还是作为一个新类，最后对镜头中的帧进行聚类分析，关键帧为与类中心距离最小的帧，如改进的蚁群算法与凝聚相结合的关键帧提取[2]，基于聚类的关键帧提取算法[8]。此类方法综合考虑了镜头内和镜头间的相关性，但不能有效地保存原镜头中图像帧的动态信息和时间顺序，同时计算量很大。

1.3 基于运动分析提取关键帧

通过光流分析来计算镜头中的运动量，包括基于局部运动和基于全局运动的方法，如W0LF光流法，利用光流与熵统计法对花卉生长视频进行关键帧提取[9]。此类方法能很好地表达视频内的全局性运动，但在分析运动时，所需要的计算量较大，且局部最小值也不一定准确。

1.4 基于视觉内容提取关键帧

通过每一帧图像视觉内容的变化程度提取关键帧，如图像的纹理、颜色等视觉信息，当图像的这些信息有显著变化时，当前帧即为关键帧，如利用改进的互信息量对关键帧提取的研究[10]，对基于镜头内容的视频检索系统研究[11]。此类方法选取的关键帧数目由镜头变化程度决定，选取的关键帧能够反映镜头内图像的变化，但选取的帧不一定具有代表意义，同时物体快速运动时，容易选取出过多连续的关键帧。笔者针对现有基于图像信息提取关键帧存在的问题，结合滑动窗口机制，提出了基于相关系数的道路监控视频关键帧提取算法。

2 基于相关系数的关键帧提取算法

2.1 算法提出

道路监控中，主要关注车辆信息和异常信息，因此道路监控视频关键帧可以定义为有车辆运行和出现异常信息的帧，即图像帧间变化较大的图像帧。在道路监控中，摄像头位置固定，监控视频镜头单一，不需要镜头分割，不能直接使用上述4种典型的关键帧提取算法，笔者结合滑动窗口提出了基于相关系数的道路监控视频关键帧提取算法。

道路监控视频中，两个图像帧之间的相关系数绝对值越小，其图像的变化越大；反之，图像变化越小。基于相关系数的道路监控视频关键帧提取算法是通过比较当前帧与关键帧的相关系数绝对值与自定义阈值θ的大小判别当前帧是否为关键帧。笔者将图像帧的RGB值转化为灰度值Y进行处理和分析，降低了算法复杂度，减小了计算量；使用滑动窗口，有效地防止提取过多连续重复关键帧，得到与前一关键帧相比差别更大、更具有代表性的关键帧。

2.2 算法流程

算法的基本过程描述为：

输入：视频文件自定义阈值θ，滑动窗口宽度w。

输出：视频关键帧序列。

1)从视频文件中分离视频流，读取图像帧数目N；

2)初始化，定义关键帧Fk=F0，从第1帧开始遍历视频帧序列，index=1；

3)判断视频中的所有图像帧是否遍历完成，即index

4)N帧内，滑动窗口(Findex,Findex+1,Findex+2,…,Findex+w-1)内的帧与关键帧Fk的相关系数绝对值最小值的第l帧Fl，相关系数绝对值最小值记为|r(Fk，Fl)|；

5)判别第l帧Fl是否为关键帧，若g(Fk，Fl)=|r(Fk，Fl)|-θ>0，则Fl不是关键帧，转至步骤7)；若g(Fk，Fl)=|r(Fk，Fl)|-θ<0，则Fl是关键帧，输出关键帧信息，并转向下一步；

6)重新定义当前关键帧Fk=Fl，更改遍历序列下标index=l+1，转至步骤3)；

7)改变遍历序列下标index=index+w，转至步骤3)。

2.3 图像帧预处理

从道路监控视频流中获取的图像帧中，包含了图像中像素点的RGB信息，笔者用相关系数分析图像帧的差别，注重的是图像的轮廓信息，灰度图像是像素点之间只有亮度差别而没有颜色差别的图像，因此可以利用图像的灰度值进行分析[12]。彩色图像灰度化公式为：

Y=0.299R+0.578G+0.114B

(1)

式中：Y是图像的灰度值集合；R，G，B分别代表彩色图像的红、绿、蓝三个颜色通道的数值集合，将第l帧图像的灰度信息集合记为Fl，其表达式为：

Fl={Y(1,1),Y(1,2),…,Y(1,n),Y(2,1),Y(2,2),…,Y(m,n)}

(2)

式中：Y(i,j)为图像第i行第j列像素点的灰度值；Y(1,1)为第l帧图像第1行第1列像素点的灰度值；m为图像的宽度；n为图像的高度。

将原来图像帧的RGB值转化为图像帧的灰度信息Fl进行分析，可以有效降低算法复杂度，减小计算量。

2.4 关键帧判别

通过与当前关键帧Fk比较，判别第l帧Fl是否为关键帧。关键帧判别函数g(Fk,Fl)的表达式为：

g(Fk，Fl)=|r(Fk，Fl)|-θ

(3)

式中：θ为自定义阈值；r(Fk，Fl)为关键帧Fk与第l帧Fl的相关系数，其表达式为：

(4)

(5)

cov(Fk,Fl)=E[(Fk-E[Fk])(Fl-E[Fl])]=

(6)

(7)

关键帧Fk与第l帧Fl的相关系数r(Fk,Fl)为：

(8)

式中：m为图像像素列数；n为图像像素行数。

相关系数绝对值|r(Fk,Fl)|越大，表示关键帧Fk与第l帧Fl的相关性越小，变化越大；反之，变化越小。判别函数g(Fk，Fl)<0时，判别第l帧Fl相对于当前关键帧Fk为关键帧；反之，第l帧Fl不是关键帧。

2.5 滑动窗口

在关键帧的提取过程中，为了避免提取出连续重复的关键帧，采用滑动窗口机制。滑动窗口是将连续的w个图像帧组成一个集合，用关键帧判别函数g(Fk，Fl)判断滑动窗口中相关性绝对值最小的帧Fl相对于当前关键帧Fk是否为关键帧，不存在关键帧，滑动窗口移动到窗口中最后一帧的下一帧；存在关键帧，滑动窗口移动到关键帧的后一帧。

关键帧的提取过程中，滑动窗口机制描述为：

1) 依次计算当前关键帧Fk与滑动窗口内的图像帧(Fi,Fi+1,Fi+2,…,Fi+w-1)相关系数的绝对值|r(Fk，Fi)|，|r(Fk，Fi+1)|，|r(Fk，Fi+2)|,…,|r(Fk，Fi+w-1)|；

2) 找出相关系数绝对值最小的第l帧Fl，其最小的相关系数绝对值表示为|r(Fk，Fl)|；

3) 利用关键帧判别函数g(Fk,Fl)判别第l帧Fl是否为关键帧，是则转至步骤5)，否则转向下一步；

4) 将滑动窗口移动至第(i+w)帧，继续查找下一个滑动窗口(Fi+w,Fi+w+1,Fi+w+2,…,Fi+2w-1)中的关键帧；

5) 将滑动窗口移动至第(l+1)帧，继续查找下一个滑动窗口(Fl+1,Fl+2,Fl+3,…,Fl+w)中的关键帧。

其中，滑动窗口大小的选取主要考虑2方面的因素：① 滑动窗口不宜选取过大，防止漏选取关键帧；② 滑动窗口不宜选取过小，防止提取过多的冗余关键帧。因此需要结合监控区域大小、车速及车辆通过监控区域的时间选取合适大小的滑动窗口。

实验中，在车速正常的情况下，一般车辆通过监控区域的时长为1～2 s且分析的视频为PAL制式、AVI格式，帧速率为25帧/s，因此滑动窗口选取25～50帧之间均可，若滑动窗口大小比25小很多，可能出现冗余帧；若滑动窗口比50大，可能漏提取关键帧。文中滑动窗口的大小w取25，以图1说明滑动窗口工作原理。

图1 滑动窗口(w=25)工作原理Fig.1 Working principle of sliding window

(w=25)

图1(a)中，滑动窗口含有图像帧(F1,F2,F3,…,F25)，若滑动窗口中无关键帧，滑动窗口移动至第26帧，包含图像帧(F26,F27,F28,…,F50)；若滑动窗口中有关键帧，如第2帧为关键帧，滑动窗口移动至第3帧，包含图像帧(F3,F4,F5,…,F27)。

3 实验与分析

3.1 实验结果

提出的基于相关系数的道路监控视频关键帧提取算法在VC++平台实现。对学校车行道上一段60 s、1 500帧的监控视频进行分析，视频中有2辆车分别通过监控区域，在阈值θ不同的情况下，使用滑动窗口和不使用滑动窗口提取的关键帧结果如表1。其中提取出的关键帧分为含有车辆和不含车辆，若关键帧中含有车辆，则提取的关键帧为符合需求的关键帧；若不含车辆的关键帧，则为误检关键帧；若提取的关键帧没有包含2辆车，则存在漏检关键帧。

从表1分析得出以下结论：

1)未使用滑动窗口的情况下，当阈值θ≤0.905，不能提取出关键帧；当阈值θ为0.970，0.930时，误提取出关键帧；在阈值θ≥0.910时，有效地提取出关键帧。

2)随阈值θ的增加，关键帧冗余度明显增加，当阈值θ的增加到一定值时，存在误检验帧。

3)使用滑动窗口的，提取有效关键帧的同时，冗余度明显降低，冗余关键帧的数目明显减少。

4)滑动窗口拓宽了阈值θ的取值范围，降低了阈值θ的选取难度。未使用滑动窗口，阈值θ在0.910附近，提取关键帧效果最佳；使用滑动窗口，在0.910≤θ≤0.925时，能提取出有效地关键帧。

表1 有无滑动窗口实验结果对比

在使用滑动窗口机制，阈值θ=0.910时，提取的关键帧序列如图2。

图2 阈值θ=0.910提取的帧序列(滑动窗口)

由图2可知，提取的关键帧分别为2辆车通过监控区域，并可以清晰的看见车辆信息的图像帧。实验结果表明：结合滑动窗口，基于相关系数的道路监控视频关键帧提取算法可以提取包含清晰的车辆信息的关键帧，能够将车辆进入和离开监控区域的信息很清晰的体现。

3.2 关键帧评价

利用本文算法提取的关键帧，符合道路监控特点，包含了清晰的车辆信息，同时通过基于欧式距离的帧间差异性进行评价。

为判断提取出的关键帧是否为有效关键帧和最佳关键帧，笔者提出利用基于欧式距离的帧间差异性进行评价。如果2个相连关键帧Fk1，Fk2之间的差异Dis(Fk1,Fk2)是关键帧Fk1与帧Fl之间的差异的最大值，其中k1≤l≤k2，那么选取的关键就是正确、有效地。实现的过程中，允许存在σ=0.001的误差，即提取出的关键帧满足式(9)，提取的关键帧为有效关键帧和最佳关键帧：

(9)

式中：Max[Dis(Fk1,Fl)]为关键帧Fk1与帧Fl之间的差异的最大值；Dis(Fk1,Fk2)为关键帧Fk1,Fk2之间欧式距离；Dis(Fk1,Fl)为关键帧Fk1与帧Fl之间欧式距离。

两帧之间的欧式距离越大，差异性越大，第k帧和l帧的欧式距离公式如式(10)：

(10)

式中：m为图像像素点列数；n为图像像素点行数。分析实验过程中的当前帧和当前关键帧之间的欧式距离，得关键帧之间的欧式距离是所在区间中最大的，证明了提取的关键帧的有效性和合理性。

在利用滑动窗口机制，阈值取0.970和0.910时的帧序列和相关系数(图中虚线)，欧式距离(图中实现)的曲线图如图3、图4。为了图像更加清晰，在图3(a)、图4(a)显示1 500帧图像序列的曲线图的同时，还增加了图3(b)、4(b)显示前200帧图像序列的曲线图；将欧式距离线性的转化到相关系数的区间，转化后的距离d的公式如式(11)：

Min(R)

(11)

式中：d为显示距离；Max，Min分别为求最大值、最小值函数；Dis为所有图像帧的欧式距离的集合；R为所有图像帧的相关系数的集合；dis为当前需要转化的原始欧式距离。

图3 阈值θ=0.970的帧序列——欧式距离、相关系数Fig.3 Euclidean distance and correlation coefficient of frame sequence when threshold θ is 0.970

图4 阈值θ=0.910的帧序列——欧式距离、相关系数Fig.4 Euclidean distance and correlation coefficient of frame sequence when threshold θ is 0.910

4分析图3、图得出以下结论：

1)随着帧间相关系数的增大，欧式距离减小；反之，欧式距离变大。

2)相关系数相应区间极小值对应欧式距离极大值。

3)相关系数减小速度加剧时，欧式距离增大速度也加剧，此时存在关键帧。

4)两个关键帧的区间内，关键帧之间的相关系数是第一个关键帧和任意帧相关系数的最小值；关键帧之间的欧式距离是第一个关键帧和任意帧欧式距离的最大值。

4 结 语

结合滑动窗口机制，提出基于相关系数的道路监控视频关键帧提取算法，实验表明，在固定摄像头的道路监控中可以有效地提取出具有代表性的关键帧，同时通过基于欧式距离的帧间差异性验证得出提取的关键帧之间差异性是最大的。算法流程清晰，结合的滑动窗口机制有效降低了关键帧的冗余度，使得关键帧更具有代表性，拓宽了阈值的取值范围，降低了阈值选取难度。但是算法中阈值还是需要根据不同的应用场景，凭经验选取，有待进一步研究、完善算法，使得阈值可以自动选取。

[1] JADON R J,CHAUDHURY S,BISWAS K K.A fuzzy theoretic approach for video segmentation using syntactic features [J].PatternRecognitionletters,2001,22:1359-1369.

[2] 张建明,刘海燕,孙淑敏.改进的蚁群算法与凝聚相结合的关键帧提取[J].计算机工程与应用,2013,49(3):222-225. ZHANG Jianming,LIU Haiyan,SUN Shumin.Key frame extraction based on improved ant algorithm and agglomerative [J].ComputerEngineeringandApplications,2013,49(3):222-225.

[3] 程照辉,毋立芳,刘健.基于运动特征的视频检索[J].信号处理,2011,27(5):765-770. CHENG Zhaohui,WU Lifang,LIU Jian.Motion feature based video retrieval [J].SignalProcessing,2011,27(5):765-770.

[4] 刘帷,贾克斌,王卓峥,等.融合视频指纹和时空信息的视频检索算法[J].北京工业大学学报,2014,40(2):200-205. LIU Wei,JIA Kebin,WANG Zhuozheng,et al.Video retrieval method based on video fingerprints and spatial-temporal information [J].JournalofBeijingUniversityofTechnology,2014,40(2):200-205.

[5] 陆燕,陈福生.基于内容的视频检索技术[J].计算机应用研究,2003,20(11):1-4. LU Yan,CHEN Fusheng.Content-based video retrieval techniques [J].ApplicationResearchofComputers,2003,20(11):1-4.

[6] 方勇,戚飞虎.一种新的视频镜头边界检测及关键帧提取方法[J].华南理工大学学报(自然科学版),2004.32(增刊1):18-23. FANG Yong,QI Feihu.A new method of video shot boundary detection and key frame extraction [J].JournalofSouthChinaUniversityofTechnology(NaturalScience),2004.32(Sup1):18-23.

[7] 杜奎然,肖国强,江健民.基于多种视频特征的镜头边界检测算法[J].计算机工程,2009,35(11):243-245. DU Kuiran,XIAO Guoqiang,JIANG Jianmin.Shot boundary detection algorithm based on multiple video features [J].ComputerEngineering,2009,35(11):243-245.

[8] MOIR G L,GRAHAM B W,DAVIS S E,et al.An efficient method of key-frame extraction based on a cluster algorithm [J].JournalofHumanKinetics,2013,39(1):15-23.

[9] 王璐,高林,闫磊,等.基于光流与熵统计法的花卉生长视频关键帧提取算法[J].农业工程学报,2012,17(28):125-130. WANG Lu,GAO Lin,YAN Lei,et al.Key-frame retrieval method based on optical flow and entropy statistic for blooming video [J].TransactionsoftheChineseSocietyofAgriculturalEngineering,2012,17(28):125-130.

[10] 刘高军,杨丽.改进的互信息量相似度曲线关键帧提取研究[J].计算机应用与软件,2014,31(2):153-156. LIU Gaojun,YANG Li.On key frame extraction based on improved mutual information similarity survey [J].ComputerApplicationsandSoftware,2014,31(2):153-156.

[11] 姜静,张栋梁.基于镜头内容的视频检索系统[J].山东理工大学学报(自然科学版),2013,27(3):21-24. JIANG Jing,ZHANG Dongliang.Video retrieval system based on shot contents [J].JournalofShandongUniversityofTechnology(NaturalScience),2013,27(3):21-24.

[12] 曹建秋,王华清,蓝章礼.基于改进YCrCb颜色空间的肤色分割[J].重庆交通大学学报(自然科学版),2010,29(3):488-492. CAO Jianqiu,WANG Huaqing,LAN Zhangli.Skin color division base on modified YCrCb color space [J].JournalofChongqingJiaotongUniversity(NaturalScience),2010,29(3):488-492.

An Algorithm of Key Frame Extraction in Road Monitoring VideoBased on Correlation Coefficient

LAN Zhangli, SHUAI Dan, LI Yicai

(School of Information Science & Engineering, Chongqing Jiaotong University, Chongqing 400074, P.R.China)

In order to effectively extract the key frame from the road monitoring video photographed by fixed cameras, the algorithm of extracting key frame based on correlation coefficient was proposed. Firstly, theRGBvalues of the video monitoring video were translated into gray values by the proposed algorithm. Secondly, combining with the sliding window, whether the current frame was the key frame was determined by comparing the threshold and absolute value between the correlation coefficient of the current frame and the current key frame. Experimental results show that the algorithm can not only extract the key frame effectively, but also has the clear process and can avoid redundant key frame. Finally, the extracted key frame was evaluated by the frame difference based on Euclidean distance, which verified the validity of the algorithm and the correctness of the key frame.

traffic and transportation engineering; key frame; correlation coefficient; sliding window; road monitoring

2014-08-06；

2014-10-27

重庆市教委科学技术研究项目(KJ130421); 重庆市自然科学基金项目(CSTC2011jjA10054); 重庆市科技攻关项目(CSTC2011AC6102)

蓝章礼(1973—)，男，重庆人，教授，主要从事数字图像处理与模式识别、交通信息化、太阳能光伏发电方面的研究。E-mail: 674437004@qq.com。

10.3969/j.issn.1674-0696.2016.01.25

U.491.1+16

A

1674-0696(2016)01-129-05