基于梯度向量角-模值二维直方图的镜头边界检测.doc

基于梯度向量角-模值二维直方图的镜头边界检测
葛 宝1，祝 轩1，谢明华1，彭进业1,2
(1. 西北大学 电子科学系，陕西 西安 710069；2. 西安电子科技大学 电子工程学院，陕西 西安 710071)
摘 要： 提出一种新的基于梯度向量角-模值二维直方图的镜头边界检测方法。该方法采用反对称双正交小波分解系数计算视频帧的方向梯度向量，再统计由梯度向量角和模值构成的联合空间二维直方图，然后计算连续帧直方图之间的距离，得到两帧之间的不连续值，最后采用自适应阈值分割，检测出镜头边界。初步实验结果表明，在保持检出率相同时，所提出方法的正确率比HSV空间颜色直方图方法高出8%左右
关 键 词：镜头边界检测；梯度向量角-模值二维直方图；HSV空间颜色直方图；基于内容的视频检索；反对称双正交小波
中图分类号：TP391 文献标识码：A 文章编号：1000-274X(2004)0069-06
镜头是一组连续的相互关联的帧，是相机的一次连续拍摄，代表时间或空间上连续的一组动作。镜头的切换形成镜头边界，镜头边界检测是进行视频内容分析的首要步骤，是基于内容的视频检索中更高一级的语义、内容分析的基础。镜头边界的类型一般可以分为突变型和渐变型两种。目前，针对这两种边界类型的检测方法主要有：像素亮度匹配、颜色直方图（RGB、YUV 或HSV空间）比较、边缘比较等方法。基于像素亮度匹配的方法由于它对运动、光照很敏感，所以它的检测效果不理想[1]。由于颜色直方图可以克服对物体运动的敏感性，而边缘对光照变化具有稳定性，因此基于颜色直方图和边缘的检测方法优于基于像素亮度匹配的方法。进一步，从文献[2]中给出的基于边缘变化率和基于颜色（YUV空间）直方图的镜头边界检测实验结果可以看出，基于颜色直方图的方法在某些方面比基于边缘变化率的方法更好一些。
颜色直方图可以在3种不同的颜色空间（即RGB、YUV和HSV空间）中统计。 HSV（Hue-　Saturation-Value）空间与RGB、YUV比较，具有两个重要特点：一是人眼可独立感知该空间各颜色分量的变化；二是在这种颜色空间上的颜色三元组之间的欧几里德距离与人眼感觉到的相应的颜色差具有线性关系，是一种符合人类视觉感知特性的颜色模型。因此，基于HSV颜色空间的测度能够更好地逼近人眼的感觉，其中H(Hue，色调)分量又较好地克服了一般光照变化对颜色直方图所带来的影响。这是因为H在光照发生变化时能保持相对稳定，这可以从下面H与R,G,B之间的变换关系表达式[3]中看出
(1)
其中
(2)
所以采用HSV空间颜色直方图进行镜头边界检测比RGB、YUV为优，并且常常加重H分量对颜色直方图的贡献。
本文提出基于梯度向量角与模值联合空间二维直方图（我们将其简称为AM直方图）的镜头边界检测方法，并与HSV空间的颜色直方图方法进行比较，初步实验结果表明本文方法的性能优于HSV空间的颜色直方图方法。
1 基于梯度向量角-模值二维直方图的镜头边界检测方法
1.1　视频帧梯度向量角和模值的计算
由于视频帧图像中不可避免地含有一定的噪声干扰，直接利用像素的差分来计算梯度向量是不可取的，因此在计算梯度向量之前对图像作某种平滑处理是必要的。Mallat等人提出了基于二进小波分解系数的多尺度边缘提取方法[4]，该方法计算工作量较大，且其变换系数不利于直接用于编码压缩。文献[5]中基于反对称双正交小波的多尺度边缘提取算法克服了这两方面的缺点，本文采用这一方法计算图像多尺度方向梯度，下面简述其算法。
将图像用反对称双正交小波作J级小波分解，设分解后的第j（j=1, …,J）级的近似系数为，水平方向、垂直方向及对角方向的细节系数分别为。模糊图像上的任意一点记为p(x, y)。则-j尺度下p位置处的梯度向量的模值为
(3)
而其对应的向量角为
(4)
其中: 是和按行先“半重构”再作下采样后在p(x, y)位置的值；是和按列先作“半重构”再作下采样后在p(x, y)位置的值。更详细的算法请参考文献[5]。
1.2　梯度向量角-模值二维直方图
设A为向量角空间，M为模值空间，现将向量角A的分布区间（0，2π]分成L等分，每等分宽度为，记为，。将M分成K等分，每等分宽度为，记为，。现在统计A处于，同时M处于内的像素点数，记为，然后对其进行归一化
(5)
即为梯度向量角-模值二维直方图。
为了增强直方图特征的有效性，模值太小的像素点不参与直方图统计，即只选取个M取最大值的像素点参与统计，这里
(6)
是全部像素点数。取值可在30%左右选取。
显然，如果K=1，则二维直方图退化为单纯的向量角直方图，向量角直方图可以应用于具有明显结构特征的图像相似性的检测，详细讨论可以参考文献[6]。反之，如果L=1，则退化为单纯的模值直方图。因此，选取L愈大，向量角分布的信息量愈大，而K愈大，模值分布的信息量愈大。因此，选取合适的K、L值也是值得考虑的因素，通过比较实验，本文中取L与K之比约为2:1。
1.3　帧间不连续值计算
以视频帧的梯度向量角-模值二维直方图作为特征矢量，计算第m帧和第n帧之间的不连续值
（7）
式中：、是按式(5)计算出的直方图向量；m和n 是帧的序号，且1，本文实验取1。
1.4　边界检测的自适应阈值
最简单的边界检测方法是选取一个固定的阈值，即全局阈值，将帧间不连续值大于阈值的位置判定为镜头边界。然而采用全局阈值，可能会使帧间不连续值的局部峰值出现漏检。因此，采用固定阈值是不恰当的，本文采用如下的自适应阈值[1]
(8)

式中：r 为预先设置的常数，r越大，错误检出的概率越小，r越小，错误检出的概率越大；和是当前镜头内Z值的均值和方差。其计算步骤如下：
1）初始化。在一个边界确定之后，令k=1，连续计算q个Z(k,k+1)值，得
(9)
(10)
并按式(8)得到T。
2）检测
(11)
如果成立，确定为边界，转第一步，否则
3）用求得的Z(k,k+1)更新、和T，然后转第二步。
2 实验结果
为了验证上节方法的有效性，我们随机选取了11 417帧（每帧大小352×288像素，25帧/s）连续故事片作实验素材。首先请专业人员通过对视频浏览，确定其共有镜头边界126个，其中包含有亮度变化显著的镜头，有剧烈动作的镜头，并且有几个镜头边界为渐变型边界。
用本文AM直方图方法和HSV颜色直方图法[7]分别对上述素材作镜头边界的检测。在AM方法中，为了加强体现视频内容的结构特性，所以对向量角的分布取12等分，即取L=12；而对模值空间只取5等分，即取K=5。在HSV方法中，按文献[7]将H取12等分，S和V分别取5等分。得到的不连续值分别如图1和图2所示。

图1　AM方法测得的不连续值 　　　　　图2　HSV方法测得的不连续值
Fig.1　Discontinuity values obtained by AM method 　 Fig.2　Discontinuity values obtained by HSV method
采用自适应阈值，取q=25。为了便于比较，通过调整r的取值（对于AM方法取r=5.5；对于HSV方法取r=5.0），使AM方法和HSV方法保持相同的检出率，检测结果如表1所示。
表1 本文方法(AM)与颜色直方图法(HSV)镜头边界检测结果比较
Tab.1　Comparing experimental results

镜头边界
检出数
正确检出
错误检出
漏　检
正确率%
检出率%
AM
126
113
112
1
14
99.12
88.89
HSV
126
122
112
10
14
91.80
88.89

其中检出率
(12)
正确率
(13)
式(12，13)中：为正确检出数目；为漏掉的数目；为错误检出的数目。
从表1所示的实验结果可以看出，本文所提出的AM方法与HSV颜色直方图法比较，在检出率保持一致的情况下，AM方法的正确率高出8%左右。由于AM方法同时考虑了视频帧的向量角和模值，因此对于视频图像结构的改变和颜色的改变都具有鉴别能力，而颜色直方图只对颜色的改变具有鉴别能力，因此AM方法的检测能力优于颜色直方图方法。但是，对于视频内容发生变化，而视频内容的结构无多大变化时，也可能导致AM方法的漏检。
下面简要分析这两种方法的算法复杂度。AM方法需要计算梯度向量的向量角和模值，HSV方法需要作RGB空间到HSV空间的转换，从这两种预处理过程来看，AM预处理的计算量稍大于HSV方法。但是，由于本实验中AM直方图维数（12×5维）远小于HSV直方图维数（12×5×5维），因此总的检测时间是AM方法远小于HSV方法。实验的实测结果也表明，本文AM方法比HSV方法快13倍。如果降低颜色直方图维数，例如只选取H-S二维颜色直方图[8]，并且使其维数与AM直方图相当，此时两种方法的时间复杂度相差不会很大，但H-S颜色直方图方法的准确率将比AM方法更低一些。
3 结　语
本文提出的镜头边界检测方法，是以向量角和模值作为视频帧特征，通过统计梯度向量角和模值联合空间二维直方图进行帧间不连续值的计算，并且采用自适应阈值进行检测，初步实验结果表明，其总体检测性能优于HSV颜色直方图方法。另外值得注意两点：一是从实验结果看，本文AM方法与HSV方法在“漏检”上可能具有一定的互补性，因此将这两种方法相结合，可望进一步提高检出率，这是我们下一步将要研究的课题；二是由于本文方法采用反对称双正交小波分解系数计算梯度向量，而小波系数又可以应用于图像和视频压缩。因此，本文方法可以推广应用于小波压缩域中的视频镜头检测，这也是我们感兴趣的研究方向之一。
参考文献：
[1] HANJALIC A. Shot-boundary detection: unraveled and resolved[J]. IEEE transactions on circuits and system for video technology, 2002, 12(2): 90-105.
[2] SMEATON A F, GILVARRY J, GORMLEY G, et al. An evaluation of alternative techniques for automatic detection of shot boundaries in digital video[OL]. http://citeseer.ist.psu.edu. 2003-06-23.
[3] CASTLEMAN K R. Digital image processing[M]. New Jersey: Prentice Hall, Inc., 1996.553.
[4] MALLAT S, ZHONG S. Characterization of signals from multi-scale edges[J]. IEEE Trans. PAMI, 1992,14(7): 710-732

[5] 彭进业, 俞卞章, 王大凯，等. 多尺度对称变换及其应用于定位人脸特征点[J]. 电子学报, 2002, 30(3)：363-367.
[6] PENG J Y, YU B Z. WANG D K, Image similarity detection based on directional gradient angular histogram[OL]. http://ieeexplore.ieee.org/search/basicsearch.jsp.2003-05-23.
[7] WAN X, KUO C C J. Color distribution analysis and quantization for image retrieval[OL] http://scitation.aip.org/vsearch/servlet/VerityServlet?key=all. 2003-04-23.
[8] ARMAN F, HSU A, CHIU M, Feature management for large video databases[OL] http://scitation.aip.org/vsearch/servlet/VerityServlet?key=all. 2003-04-13.
（编辑　曹大刚）

Shot-boundary detection based on the gradient angle-module 2D histogram
GE Bao1, ZHU Xuan 1, XIE Ming-hua1, PENG Jin-ye1,2
(1. Department of Electronics, Northwest University, Xi’an 710069, China；2. School of Electronic Engineering, Xidian University, Xi’an 710071, China)
Abstract: Dividing a video sequence into shots is the first step towards video-content analysis and content-based video browsing and retrieval. A novel method for shot boundary detection is presented based on gradient angle-module histogram. Firstly, each video frame’s gradient vector is obtained by using coefficients of anti-symmetrical bi-orthogonal wavelet decomposition. Secondly, the angle-module histogram is computed and normalized, followed by computing the distance between histograms of consecutive frames. Finally, an adaptive threshold is selected for detecting shot boundary. Experiments show that the precision of our method is 8% higher than that of the HSV-space histogram while preserving the same recall..
Keyword: shot boundary detection, gradient angle-module 2D histogram, HSV-space color histogram, content-based video retrieval, anti-symmetrical bi-orthogonal wavelet.
作 者 简 介
葛 宝，男，陕西西安人，生于1979年。2001年7月毕业于西北大学电子学与信息系统专业，获学士学位。2001年9月至今，在西北大学电子系攻读电路与系统硕士学位，主要研究方向为信号处理、模式识别、基于内容的视频检索等。

6