基于小波变换的视频流镜头切分及关键帧提取*

吴绍根

(广东轻工职业技术学院计算机工程系　广州　510300)



基于小波变换的视频流镜头切分及关键帧提取*

吴绍根

(广东轻工职业技术学院计算机工程系广州510300)

视频镜头切分及关键帧提取是基于内容的视频检索的基础。通过使用色彩直方图向量来表征视频帧特征,使用余弦夹角来度量视频帧的相似性并建立相邻视频帧的相似性数据序列,再通过小波变换寻找其中的突变数据点或数据点集来完成对视频镜头的切分,最后通过最小直方图特征标准差在每个镜头中提取关键帧。实验表明,该方法能有效地找到镜头的边界,所提取的关键帧可以表达镜头的主要内容。

小波变换; 视频; 镜头切分; 关键帧

Class NumberTP391

1　引言

基于内容的视频检索是当前视频检索领域的研究热点[1]。对视频的检索显然不能使用传统的基于文字的方式进行,而只能对视频进行特征抽取,建立视频的特征信息,并在此基础上进行基于视频特征的检索。为了建立视频特征信息,需要首先对视频进行结构进行分析。

视频的基础结构从语义角度由下至上划分为: 帧、镜头、场景、视频。在视频结构化研究中,其主要内容是以镜头为单位对视频内容进行划分,即镜头切割或切分[2],然后在分割的视频段内提取关键帧,在此基础上才能进行后续的工作,例如基于内容的视频检索等。

视频镜头的切换包括突变切换和渐变切换两种类型。突变切换是指将镜头直接从一个镜头切换到另一个镜头,中间没有过滤帧；而渐变切换则从一个镜头切换到另一个镜头时,中间包括一些过滤帧。所谓镜头切分,就是从视频流中找到这些镜头的切换点。而关键帧提取则是从已经切分的视频镜头中提取最能代表各个视频镜头的图像帧。

本文提出一种基于Daubechies小波变换的视频镜头切分方法和基于最小标准差的镜头关键帧提取方法。实验结果表明,本文所介绍的方法在镜头切分上优于线性切分算法,同时,从视觉判断上,本文方法所提取的镜头关键帧能较好地反映视频镜头的主要内容。本文后续内容将从算法的数学模型、算法描述、实验结果及其分析几个方面对算法进行介绍。

2　算法的数学模型

在进行算法设计之前,首先对算法中涉及到的数学模型进行介绍,包括：视频帧特征表示方式、视频帧相似性度量方法、使用小波变换检测视频帧突变及渐变的方法和镜头关键帧度量的方式。

2.1视频帧的特征表示

为了进行视频镜头切分,需要首先建立视频帧的特征表示并依据所建立的特征进行视频帧的相似性计算。由于色彩直方图能够从全局的层面表示视频帧的特征,因此,本文采用色彩直方图建立视频帧的特征。建立视频帧的特征过程包括两个步骤：第一步,对彩色视频帧进行灰度化处理；第二步,构建视频帧的灰度直方图向量。

2.1.1对视频帧进行灰度化处理

由于现有的大多数视频都是彩色视频,因此,在建立视频的特征信息之前,需要对视频帧进行灰度化处理。采用如下的计算方法进行RGB的彩色视频帧到灰度视频帧的转换：

GL=0.2989*R+0.5870*G+0.1140*B

(1)

其中,R、G、B分别表示原像素点的红、绿、蓝的值。

2.1.2构建视频帧的灰度直方图特征

对彩色视频帧进行灰度化处理后,视频帧的每个像素点的值都在0～255这个区间。对每一个视频帧,统计每一级灰度的像素个数,进而得到的一个256维的向量,这个向量称为灰度直方图向量,本文将这个向量作为视频帧的特征。视频帧的灰度直方图计算方法如下：

HG=〈v0,v1,v2,…,v255〉

(2)

其中,vb(0≤b≤255)表示灰度为b的像素点个数,vb的计算方法如下：

其中,M表示视频帧的高度,N表示视频帧的宽度,Pi,j表示在(i,j)空间位置上像素点的灰度值,b表示从0～255的一个灰度级。δ是符号函数,其定义如下：

2.2建立视频帧的相似性度量序列

通过为每一帧视频帧计算其灰度直方图,建立了每一视频帧的特征表示。然后,采用向量的余弦夹角来度量视频帧的相似度,计算方法如下：

(3)

其中,HGi、HGj分别表示第i个视频帧与第j个视频帧的灰度直方图向量,〈HGi,HGj〉表示向量HGi与向量HGj的内积,|HGi|、|HGj|分别表示向量HGi与向量HGj的模长。

对视频的所有相邻视频帧进行相似度计算,得到如下所示的相邻视频帧的相似性离散序列SM：

SM=(SM〈1,2〉,SM〈2,3〉, …,

SM〈i,i+1〉,…,SM〈n-1,n〉)

(4)

其中,n表示视频的总帧数,所建立的视频帧相似度序列是一个具有n-1个元素的序列。视频镜头分割的目标就是从该序列中找到发生突变或渐变的数据点或数据点集。本文采用消失矩为2的Daubechies小波db2来检测这些数据点或数据点集。

2.3利用db2小波变换检测突变或渐变数据点或数据点集

2.3.1小波变换

小波变换是继傅里叶变换之后的又一个有力的数学工具,它解决了傅里叶变换导致时域信息丢失的问题。小波变换能从时域及频域两个维度来观察一个函数或一个数据序列的变化性质。小波变换如下式所示[3]：

(5)

其中,f(t)是被变换的函数,ψ(t)为小波函数,*表示函数的复数共轭。从上式可以看出,小波变换将函数f(t)映射为一个二元函数C(a,b),其中,a表示尺度,b表示时移。小波变换的实质就是计算函数f(t)与特定的小波函数在尺度为a和时移为b时的相关度。如果将尺度参数a和移位参数b的选取以2的幂次方的方式离散取值,即可得到离散小波变换。离散小波变换可采用矩阵形式计算。本文采用消失矩为2的Daubechies小波db2来检测视频帧相似序列的突变点或渐变点集。

2.3.2构建db2小波变换矩阵

小波变换矩阵包括两个矩阵：分解矩阵和重组矩阵。

小波变换的分解矩阵由低通滤波矩阵和高通滤波矩阵两个子矩阵构成,其中低通滤波矩阵由低通滤波器参数通过逐行移位2列而构成,高通滤波矩阵则由高通滤波器通过逐行移位2列构成,在矩阵的最后一行需要进行回卷；由于所构建的小波分解矩阵是一个单位正交矩阵,因此,小波变换的重构矩阵就是小波分解矩阵的转置。

db2的低通滤波器参数[4]h=(-0.12940.22410.83650.4830),高通滤波器参数g=(-0.48300.8365-0.2241-0.1294)。基于这些参数,构建db2的分解矩阵WN如下：

(6)

WN是一个N×N的矩阵,其中N表示需要进行变换的数据的维度。由于WN是一个正交单位矩阵,因此,重构矩阵就是WN的转置,即：

利用这一性质可以方便的计算小波逆变换。

2.3.3对相邻视频帧的相似性序列SM的分解和对细节的重构

应用构建的db2小波分解矩阵WN对相邻视频帧相似序列SM进行分解,得到相似性近似序列系数A和细节序列系数D,如下所示：

(7)

其中的细节序列系数D的维度是SM维度的1/2,它表示数据序列SM中的突变成分。为了过滤掉D中的微小波动,采用累积能量法对细节序列系数D进行处理。数据序列累积能量的计算方式如下：

(8)

其中v是要进行累积能量计算的原数据序列或向量,y是对v的每个元素取绝对值后,从大到小排序而形成的数据序列。|y|是数据序列的y模长。本文选择保留原数据能量99.5%的元素值作为阈值对细节序列系数D进行过滤,得到经过过滤处理后的细节序列系数D′。

由于只需要从原数据序列找到突变点或突变点集,因此,可以将近似序列系数A全部设置为0,然后与细节序列系数D′构成向量来重构细节序列,细节重构的计算方式如下：

(9)

其中0表示元素全为0的向量。由上式(8)得到的数据序列D*就是相邻视频帧的相似性序列SM的变化点。下一步,需要对D*进行精化,从中找到视频帧的突变点和渐变点集。

2.4通过精化来确定视频帧的突变点和渐变点集

细节序列D*中的非0点就是发生变化的点。这些变化的点由两类点构成：镜头的突变点和由于镜头渐变而导致的一系列具有序列连续的变化点。考虑到渐变的过渡特性,设定当两个变化点的间隔小于视频帧速率的1/2时,则认为这两个相邻的变换点之间的视频帧为渐变过渡帧。在进行镜头切分时,舍弃这些过渡帧,取过渡帧的两边边界帧作为视频镜头的切分点,这将有利于更为有效地提取镜头关键帧。

2.5镜头关键帧的提取

有句俗语叫做“多姿多彩”,其含义是一幅多姿多彩的图像包含有更多的信息。一幅多姿多彩的图像在数学上的度量可以表达为图像的灰度直方图的标准差达到最小。为此,本文在为各个视频镜头中选取关键帧时,选取具有最小标准差的视频帧作为视频镜头的关键帧。视频帧灰度直方图标准差的计算方式如下：

(10)

xi(0≤i≤255)是视频帧直方图向量的元素。

3　算法设计

依据第2节的数学模型及其相关的计算方法,本文设计了对视频流进行镜头切分及关键帧提取算法。为了简化算法描述,算法中所提及的公式是指第2节中的相应编号的公式。

算法名称：视频流进行镜头切分及关键帧提取

输入：视频流

输出：镜头切分区间及各镜头区间的关键帧编号

算法描述：

①对视频流中的每一视频帧 do

利用式(1)对该视频帧进行灰度化处理；

利用式(2)计算该视频帧的灰度直方图特征；

if 不是第一帧视频帧

利用式(3)计算该视频帧的灰度直方图与前一视频帧的相似度；

end if

end do

②利用式(4)建立相邻视频帧的相似度序列SM；

③利用式(6)建立db2小波变换矩阵WN；

④利用式(7)对SM进行小波分解,得到细节系数D；

⑤利用式(8)对D进行累计能量计算,利用得到的阈值对D进行过滤,得到D‘；

⑥利用式(9)得到细节序列D*；

⑦对D*进行精化,丢弃渐变帧,确定镜头边界,并将结果存储为如下形式：

[(开始帧,结束帧),(开始帧,结束帧),……,(开始帧,结束帧)]

⑧利用式(10)在每个视频镜头中选取关键帧,并存储关键帧编号为如下形式：

[ 第一个镜头的关键帧编号,第二个镜头的关键帧编号,…… ]

⑨返回镜头切分的结果和关键帧提取的结果。

4　算法实验及结果分析

为了测试算法的有效性,本文使用Matlab实现了算法,并从三个方面做了实验：对视频突变和渐变的检测能力、视频镜头切分的有效性、视频镜头关键帧的提取有效性。

4.1对视频突变和渐变的检测能力分析

为了测试算法对视频突变和渐变的检测能力,本文对一段由7个镜头组成,时长为30s共901帧的测试视频采用本文的算法求出其细节序列D*。然后,对该视频进行人工编辑,在第1和第2个镜头中加入淡入/淡出(Fade In/Fade Out)渐变,在第6和第7个镜头之间加入了扫换(Wipe)渐变,再利用本文算法求出编辑后的视频的细节序列D*,结果如图1所示。

图1　算法对突变和渐变的检测有效性测试结果

从图1可以看出,本文算法能够检测出视频镜头的切变,同时,在加入了渐变的视频的细节序列中,可以清晰地观察到在视频的第1和第2个镜头间及第6和第7个镜头间的细节序列比原始视频具有更宽的变化序列,因此,本文算法也能检测到视频的渐变镜头。不仅如此,通过对这些连续变化序列的精化,可以在镜头切分时,丢弃这些渐变视频帧,使得镜头的切分和关键帧的提取更为合理。

4.2对视频镜头切分的有效性分析

为了验证算法对视频镜头切分的有效性,将本文算法与线性切分算法[5]进行比较,使用信息检索中最常用的度量指标“查全率”和”查准率”来衡量镜头切分的结果[6],计算公式如下：

并采用综合因子对算法的整体效果进行度量,综合因子的计算公式如下：

用于测试视频数据包括一段媒体演示视频、一段广告视频、一段新闻视频、一段电影片段和一段自行拍摄的视频,实验结果如表1和图2所示。

表1　查全率和查准率实验结果

图2　算法的切分有效性对比

图2中的视频类型1、2、3、4、5分别是媒体演示视频、新闻视频、广告视频、电影片段视频和自行拍摄的视频。在实验时,以第一段媒体演示视频为基础调试并设定相关阈值参数,该参数使得对第一段媒体演示视频的查全率和查准率均达到100%,然后,以得到的阈值为参数对其他的视频进行切分。从表1和图2可以看出,无论从查全率、查准率及从综合因子对整体效果进行度量,本文算法均优于线程切分算法。

4.3对视频镜头关键帧提取的有效性分析

目前没有一个通用的可以定量度量视频关键帧提取质量的计算标准,因此,对视频关键帧提取的有效性分析还仅限于直观观察。实验中,利用本文的算法对某媒体演示视频进行镜头分割并提取每个镜头的关键帧。该视频时长为30s,共有901帧,7个镜头转换,图3是镜头切分及关键帧的提取结果,从直觉观察判断,算法提取的视频关键帧能够反映每个镜头的主要内容。

图3　某媒体演示视频的关键帧提取结果

5　结语

对视频镜头的切分和对关键帧的提取是基于内容的视频检索的基础,自被提出以来[7],业界对这个问题进行了广泛的探讨和研究[8～10],并取得一定的成果,但是目前没有一个得到业界公认的算法。本文采用小波变换对视频镜头进行切分并进行关键帧提取,取得了较好的效果。如何动态确定能量阈值和渐变宽度阈值(目前分别设定为总能量的99.5%和帧速率的1/2)是后续的研究内容。

[1] 朱莉乐,朱习军,董国华.基于内容的视频检索中的镜头分割算法[J].计算机与数字工程,2015,313(11):2047-2051.

ZHU Lile,ZHU Xijun,DONG Guohua.Shot Segmentation Algorithms in Content-Based Video Retrieval[J].Computer & Digital Engineering,2015,313(11):2047-2051.

[2] 熊伟,吴春明,姜明.使用线性分割和序列合并的视频镜头分割方法[J].电子学报,2014,42(4):640-645.

XIONG Wei,WU Chun-ming,JIANG Ming.Video Shot Segmentation Method Using Linear Segmentation and Sequences Combination[J]. Electronica Sinica,2014,42(4):640-645.

[3] MathWorks Inc. Wavelet Toolbox Getting Started Guide[M]. Natick:MathWorks Inc,2015:25-30.

[4] David K. Ruch. Wavelet Theory：An Elementary Approach with Applications[M]. New Jersey: John Wiley&Sons,Inc,2009:234-246.

[5] 俞璐,乔瑞萍,胡宇平等.基于颜色直方图的快速镜头分割方法[J].微电子学与计算机,2014,31(2):72-76.

YU Lu, QIAO Ruiping, HU Yuping,et al. A Fast Shot Boundary Detection Method Based on Color Histogram[J]. Microelectronics & Computer,2014,31(2):72-76.

[6] 印勇,侯海珍.基于直方图帧差的自适应镜头分割算法[J].计算机工程与应用,2010,46(9):186-189.

YIN Yong,HOU Haizhen. Adaptive shot segmentation method based on histogram frame difference[J].Computer Engineering and Applications,2010,46(9):186-189.

[7] H. J. ZHANG, J. H. WU, D. ZHONG. An Integrated System for Content-Based Video Retrieval and Browsing[J]. Pattern Recognition,1997,30(4):643-658.

[8] 黄茜,张海泉,杨文亮.基于灰度和直方图的阈值自适应镜头边界检测[J].科学技术与工程,2008,8(14):3787-3792.

HUANG Qian, ZHANG Haiquan, YANG Wenliang,et al.Gray Value and Histogram Based Shot Boundary Detection with Adaptive Threshold[J]. Science Technology and Engineering,2008,8(14):3787-3792.

[9] 瞿中,高腾飞,张庆庆.一种改进的视频关键帧提取算法研究[J].计算机科学,2012,39(8):300-303.

QU Zhong,GAO Tengfei, ZHANG Qingqing.Study on an Improved Algorithm of Video Key Frame Extraction[J]. Computer Science,2012,39(8):300-303.

[10] 朱耀麟,李倩.视频检索常用的镜头分割方法的研究[J].电视技术,2014,38(3):178-181.

ZHU Yaolin, LI Qian. Survey of Used Methods for Partitioning Video into Shots in Video Indexing[J]. Video Engineering,2014,38(3):178-181.

Wavelet-Based Video Shot Segmentation and Key Frame Extraction

WU Shaogen

(School of Computer Engineering, Guangdong Industry Technical College, Guangzhou510300)

Video shot segmentation and key frame extraction are the basis of content-based video retrieval. By using histogram vector to represent the video frame characteristics, the cosine angle value is used to represent the similarity of neighbouring frames and establish the similarity series, using the wavelet transformation to find the abrupt data point or data point set, camera shots can be founded in video. At last, the minimum standard deviation is used to extract the key frames in each shot. Experiment indicates that this method is effective and can find the camera shots, also the extracted key frames are effective too.

wavelet transformation, video stream, shot segmentation, key frame

2016年3月4日,

2016年4月26日

吴绍根,男,硕士,副教授,研究方向：模式识别、图像处理和计算机视觉领域的研究与应用。

TP391DOI:10.3969/j.issn.1672-9722.2016.09.040