CN103118220A - 一种基于多维特征向量的关键帧提取算法 - Google Patents

Abstract

本发明提供了一种基于多维特征向量的关键帧提取算法及其在智能安防中的应用，该方法可以有效的解决球机等运动场景的基于内容的视频理解，并能够根据分析视频内容的结果构建出视频的概要关键帧序列，使监控人员可以快速的了解运动场景视频中的主要内容。

Description

一种基于多维特征向量的关键帧提取算法

技术领域

本发明属于计算机视觉领域，特别涉及一种基于多维特征向量的关键帧提取算法，及该方法在智能安防中的应用。

技术背景

随着计算机网络、数字化视频技术迅速发展，基于数字网络的视频监控得到广范的应用，但随之而来的是，随着监控部防的范围日益扩大，监控设备的数量也以惊人的数量增加，面对数以万计的监控设备，如何快速的了解海量监控点的视频主要内容成为平安城市等项目进一步发展的最大制约。

目前面对这一制约的一般解决方案为视频摘要系统、视频差异化快速播放系统等。但由于这些解决方案一般只能处理监控点固定不变的场景，对于广范部署球机的场景，这些解决方案也无能为力。因此业界亟待一种能够实现对变化场景的海量视频数据进行快速理解的算法工具，本发明提出了一种基于多维特征向量的关键帧提取算法，可以较好的针对运动球机的场景的摘要处理算法。

发明内容

本发明的目的是针对现有可变监控场景的视频监视系统，存在无法生成视频摘要，从而使监控人员无法快速了解海量视频数据基本内容的问题，提出一种基于多维特征向量的关键帧提取算法。

为了实现发明目的，采用的技术方案如下：

基于多维特征向量的关键帧提取算法的基本流程如图1所示。首先对输入的视频数据进行基于灰度直方图滑动窗口的关键帧初检并输出检测后的备选关键帧序列，然后对该序列进行基于高频信息检测的光照干扰检测，排除光照干扰帧，并输出过滤后的备选干扰帧，最后对备选干扰帧进行基于颜色特征的伪聚类关键帧提取并最终输出关键帧结果。以下分别具体说明。

1、基于灰度直方图滑动窗口的关键帧初检：首先，对本专利中用到的灰度图进行定，RGB彩色帧图像按如下方式转换成灰度图，令I_k为视频序列的第k帧图像，P_r(x，y)、P_g(x，y)、P_b(x，y)分别表示I_k在(x，y)像素点处的RGB像素值，P_gray(x，y)为I_k按下式转换后的灰度图。

P_gray＝(P_r×30+P_g×59+P_b×11+50)/100

将图像转换为灰度图后，再对本专利中用到的灰度统计直方图做如下定义：

若P_gray(x，y)表示灰度图像中的像素集，则灰度统计直方图H(b)表示为：

H(b)＝n_b  b＝0，1，…255

得到帧图像对应的灰度统计直方图后，在基于灰度直方图滑动窗口的关键帧初检算法中，按下式利用相关法对得到的帧间灰度直方图进行对比。

$d(H_k,H_{k+1})=\underset{i}{\mathrm{\Σ}}\min (H_k\left(i\right),H_{k+1}\left(i\right))i=\mathrm{0,1},...,\mathrm{bin}$

其中H_k(i)视频帧序列I_k中第k帧的灰度统计直方图，则第k帧和第k+1帧的相关差表示为：d(H_k，H_k+1)。

根据以上假设条件，本专利中所描述的滑动窗口算法可以描述如下：滑动窗口法是以一定的概率统计理论为基础，通过对历史信息的分布统计计算，从而对当前分布的未来发展进行预测的一种算法。现以关键帧初检测中的灰度直方图相关差的分布为例进行说明。本专利中认为灰度直方图的相关差在一定程度上反应了图像内容的变化趋势，图像内容的变化被分割为图像镜头内的变化和图像镜头外的变化，图像镜头通过语义的概念进行定义：令一个视频镜头所反应的图像内容为其视频内容不发生变化的图像帧序列；当图像所描述的状态内容发生了变化时，称之为镜头迁变。一般情况下可认为视频镜头内的图像帧内容变化服从高斯分布，即镜头内帧图像间的直方图相关差的变化服从高斯分布，而且镜头迁变时的灰度直方图相关差违背高斯分布。若假设滑动窗口在大小为L，向滑动窗口输入相关差，对于任意d(H_k，H_k+1)有：将此值输入滑动窗口，若此值依然服务滑动窗口中的高斯分布，则更新滑动窗口的高斯分布，并将此帧列为备选关键帧；若此值打破了滑动窗口的高斯分布，更新滑动窗口，直至内容稳定，则继续输出备选关键帧序列。

2、基于高频信息检测的光照干扰检测，通过关键帧初检，得到的备选关键帧中有很多球机运动时的过渡帧和光照干扰帧，这些帧的特征都是图像模糊不清，无法表达图像的基本信息，因此本单元利用光照使得图像中高频信息丢失的原则来实现对备选关键帧的过滤检测，为了降低算法的运算复杂度，专利中利用图像的一阶梯度图来间接的反应图像的高低频信息，具体描述如下：

算法中利用Sobel算子与图像做卷积的方法来求图像的一阶梯度图。由于Sobel算子结合了高斯平滑和微分，因此它对图像的噪声有一定的鲁棒性。Sobel算子有两种，分别利用水平方向的Sobel算子h₁和垂直方向的Sobel算子h₂所为卷积核对图像进行卷积运算，从而求得图像的梯度图。

$h_1=\left[\begin{array}{ccc}1& 2& 1\\ 0& 0& 0\\ -1& -2& -1\end{array}\right]$ $h_2=\left[\begin{array}{ccc}1& 0& -1\\ 2& 0& -2\\ 1& 0& -1\end{array}\right]$

在算法中首先对图像做水平方向的卷积运算，之后再做垂直方向的卷积运算，最后可以得到梯度图像。在求得图像的梯度图后，对梯度图进行直方图的统计，算法中对于梯度统计直方图的处理包括两个部分，去除低频分量；累计高频分量。设高低频分量间的区分线为T_frequency，P(i，j)代表着梯度图中(i，j)位置的像素值，则利用下式对梯度图进行二值化。

$P(i,j)=\left\{\begin{array}{cc}0,& P(i,j)=<T_{\mathrm{frequency}}\\ 255,& P(i,j)\&GreaterEqual;T_{\mathrm{frequuency}}\end{array}\right.$

之后统计二值图非零元的个数C即为图像的高频量。若对于阈值T满足C＜T，则认为当前图像为受干扰图，将它从备选帧序列中删除。

3、基于颜色特征的伪聚类关键帧提取，通过对备选关键帧的过滤，剩下的待选帧序列基本能够反应待处理视频的所有有意义内容，但在第一步中尽管通过灰度直方图的信息对视频内容进行了大致归类，尽管灰度直方图能够较好的将小运动图像归为一类，但由于灰度直方图对图像颜色信息变化较为迟钝，因此这些精分类极有可能把事实上的几类归为了一类。在本专利中，利用图像的颜色信息对备选关键帧序列进行最后的伪聚类划分，并提取伪聚类的聚类中心作为关键帧输出。

为了更好的反应出图像的颜色信息，本专利中将备选关键帧图像按下式规则从RGB颜色空间转换到HSV颜色空间。

V＝Max(R，G，B)

$S=\frac{\mathrm{Max}(R,G,B)-\mathrm{Min}(R,G,B)}{\mathrm{Max}(R,G,B)}$

$H=\left\{\begin{array}{cc}{H}^{\&prime;}\&times;60& H^{\&prime;}\&GreaterEqual;0\\ H^{\&prime;}\&times;60+360& H^{\&prime;}<0\end{array}\right.$

其中 $H^{\&prime;}=\left\{\begin{array}{cc}\frac{G-B}{\mathrm{Max}(R,G,B)-\mathrm{Min}(R,G,B)}& R=\mathrm{Max}(R,G,B)\\ 2+\frac{B-R}{\mathrm{Max}(R,G,B)-\mathrm{Min}(R,G,B)}& G=\mathrm{Max}(R,G,B)\\ 4+\frac{R-G}{\mathrm{Max}(R,G,B)-\mathrm{Min}(R,G,B)}& B=\mathrm{Max}(R,G,B)\end{array}\right.$

本专利中将色度H分量均分为16个区间，在每个区间下将饱和度S分量均分为8个区间，进行二维直方图的统计。设H_i(h，s)为第i帧图像的H分量S分量的颜色统计直方图，则有：

H_i(h，s)＝n_h，s  h∈[0，180]，s∈[0，255]

为了计算方便，将H分量标定在0到180之间，将S分量标定在0到255之间。

为了突出色彩间的差异，算法使用二维卡方的方法进行直方图间的匹配和对比[40]，则第k帧和第1帧间的卡方差值表示如下：

$d(H_k,H_l)=\frac{\underset{i}{\mathrm{\&Sigma;}}\underset{j}{\mathrm{\&Sigma;}}{H}_k^{\&prime;}(i,j)H_l^{\&prime;}(i,j)}{\underset{i}{\mathrm{\&Sigma;}}\underset{j}{\mathrm{\&Sigma;}}\left(H_k^{\&prime;}{(i,j)}^2\left(H_l^{\&prime;}{(i,j)}^2\right)\right)}---(3-6)$

其中

代表了直方图元素偏离直方图均值的程度。当相关度d越大，则表明直方图越匹配，否则表示不匹配。

利用颜色特征的伪聚类算法的具体流程如附图书4所示。图中k是备选帧序列的索引位置，聚类是以备选帧序列为基础，而不是帧图像在视频中的帧号，设startFrm为聚类起始帧，endFrm为聚类结束帧，keyFrm为关键帧，它同样是指在备选帧序列中的位置，最后关键帧在原视频中的帧号保存在备选帧序列结构体中。

附图说明

图1是本发明的算法流程图；

图2是本发明的滑动窗口算法流程图；

图3是本发明的关键帧初检流程图；

图4是本发明的关键帧复检流程图。

具体实施方式

1、基于灰度直方图滑动窗口的关键帧初检

滑动窗口自适应阈值计算流程见流程图2，结合附图，具体流程解释如下：

设滑动窗口的长度为1en，第k帧和第k+1间的灰度直方图差值为d(k，k+1)，则滑动窗口内差值的均值为：

${\mathrm{avg}}_{i,i+\mathrm{len}}=\frac{\underset{i=0}{\overset{\mathrm{len}}{\mathrm{\&Sigma;}}}d(i,i+1)}{\mathrm{len}}$

标准差为：

${\mathrm{dev}}_{i,i+\mathrm{len}}=\sqrt{\frac{\underset{i=0}{\overset{\mathrm{len}}{\mathrm{\&Sigma;}}}{(d(i,i+1)-\mathrm{avg})}^2}{\mathrm{len}}}$

所以特征差若要服从滑动窗口的向斯分布，则滑动窗口的下一帧差必须满足式下式，否则认为该帧所包含的内容已经与滑动窗口所描述的内容不相符。

d(k-1，k)＜avg_k-len，k+dev_k-len，k

以上分析均为理想状态的情况，对于普遍情况在基于滑动窗口的自适应阈值方法上加入了波动幅度的微调因子T，改动后的判别式如下。

d(k-1，k)＜avg_k-len，k+T×dev_k-len，k

关键帧初检的算法流程图如附图3，结合附图，具体流程说明如下：

获取第k帧图像，提取其灰度统计直方图；

若k帧为初始帧，则k++，返回第一步，否则继续；

计算k-1与k帧间的灰度直方图相关差d；

利用滑动窗口法获取自适应阈值Td，

若Td＞d，则将此帧归为当前视频镜头序列，以备选关键帧输出；

检查是否到达视频结尾，若是则结束算法；

更新滑动窗口，k++，跳入第一步。

2、基于高频信息检测的光照干扰检测。

算法基本流程为：

第一，求得图像的梯度图；

第二，利用梯度图求得图像的高频量C；

第三，若C大于阈值T则认为图像是受干扰图，否则结束。

3、基于颜色特征的伪聚类关键帧提取。

关键帧复检的流程图见附图4，结合附图具体流程解释如下：

第一，默认k＝1帧为startFrm。

第二，查找在颜色特征上与它相似的所有帧序列，直到发现第n帧与滑动窗口计算出的阈值不符，关于滑动窗口自适应阈值计算见上，令endFrm＝n。

第三，令起自startFrm，止于endFrm为一个聚类，并取聚类中心元素作为此聚类的关键帧。

第四，检查k是否指向备选帧序列的末尾，如果不是，则令startFrm＝endFrm，让k加1后转向第二步；否则结束算法输出关键帧的结果。

利用伪聚类的算法，可以有效的过滤备选帧序列中残余的运动干扰分量，镜头间的编辑帧。

Claims (6)

1.一种基于多维特征向量的关键帧提取算法，其特征在于首先利用基于图像灰度统计直方图特征的快速关键帧提取算法提取备选关键帧；其次，通过基于图像频域的方法对备选关键帧进行过滤处理；最后，通过基于伪聚类算法的关键帧复检，用以对运动场景或大运动画面的安防视频进行关键帧索引的建立。 

2.根据权利要求1所述的算法，其特征在于利用一种基于图像灰度统计直方图的关键帧初检算法进行视频的关键帧快速筛选，首先，将前后两帧图像转换成灰度图并提取其统计直方图；其次，利用卡方分布得出两个灰度统计的相似值，结合整个历史帧之间的相似值，以高斯分布为统计理论基础，建立基于滑动窗口的视频帧序列差异分布；最后利用基于滑动窗口的判定算法，得出视频序列的备选关键帧序列。 

3.根据权利要求1所述的算法，其特征在于利用一种基于图像频域信息的算法对备选关键帧进行光照和模糊化过滤，为了降低算法的运算复杂性，算法中通过图像的的梯度统计信息来反映图像的频域信息；首先，利用Sobel算子作为卷积核，先对图像的灰度图做水平方向的卷积，之后再对卷积结果做垂直方向的卷积，从而得到备选关键帧图像对应的梯度图；其次，对得到的梯度图像进行统计直方图统计；最后，能得到的一维统计直方图进行高低频分量的分析，若高频分量小于阈值T时，则认为该备选关键帧为受干扰图像，故而将该图像从备选关键帧图像中删除。 

4.根据权利要求1所述的算法，其特征在于利用一种基于HS彩色统计直方图的关键帧复检算法进行备选关键帧的复选检测，首先，将经过频域过滤的备 选关键帧转换到HSV色彩空间；第二，对HSV图像进行基于HS色彩分量的二维统计直方图统计；最后，利用基于伪聚类的方法抽取备选关键帧中的最终结果，输出关键帧序列。 

5.根据权利要求2所述的算法，其特征在于利用基于滑动窗口的算法进行帧间差异性预计和归类，其特点为，第一，待处理的数据集为一维数据集；第二，该方法基于一定的概率统计理论基础根据已经获取到的数据对数据的发展趋势进行预测；第三，根据已有数据的发展趋势来判定当前获取数据是否满足既定趋势。 

6.根据权利要求4所述的算法，其特征在于利用基于伪聚类的算法进行对备选关键帧的复检处理，其特点在于，首先，对备选关键帧序列进行伪聚类运算，最终选取每个聚类的聚类中心为最终关键帧；其次，伪聚类算法的特征选取对帧间图像HS颜色空间的统计直方图的卡方分布对比；最后，伪聚类算法的相似性测度选取基于滑动窗口的预测统计方法来规定聚类是否收敛，从而得到最终的一个聚类结果。 

Images