软件学报
JOURNAL OF SOFTWARE
1999年　第10卷　第9期　Vol.10　No.9　1999



镜头频度用于视频检索的研究*
白雪生 徐光祐 史元春
摘要　在电影、电视等观赏类视频信号中,情节的紧张程度一般都在镜头的切换频率上得以体现,而在对此类视频信号的检索中，用户往往希望能够根据情节紧张程度来进行检索.文章提出了对此类视频信号的镜头切换频率进行度量,并根据得到的镜头频度进行视频检索的方法,给出了视频流的镜头分割算法,以及为减小漏分/错分影响所采用的镜头频度度量——镜头平均帧数的鲁棒计算方法.文章还阐述了利用镜头频度进行视频检索的基本思想及算法细节,并给出了对于实际影片视频信号检索的实验结果和分析.
关键词　视频检索,镜头频度,镜头切变,镜头渐变,镜头平均帧数.
中图法分类号　TP311
Using Shot Frequency in Video Retrieval
BAI Xue-sheng,XU Guang-you,SHI Yuan-chun
(National Key Laboratory of Intelligent Technology and Systems Tsinghua University Beijing 100084)
(Department of Computer Science and Technology Tsinghua University Beijing 100084)
Abstract　In the film, television and many other videos, exciting video sections are usually reflected by their frequent shot changes, and such sections are the most frequently objects in retrieval of this kind of video. In this paper, a method on retrieving videos according to their shot change frequencies is presented. Scene transition analysis has done on real videos, and video segmentation algorithm for both cut and dissolve are developed. To lessen the influence of error and missing shot segmentations, a robust calculation method of shot frequency on shot sequence acquired is proposed. Basic ideas and algorithm modules are given in detail, also with the experimental results on film video and analysis.
Key words　Video retrieval, shot frequency, shot cut, chromatic edit, average frame number.
　　在对视频信号的基于内容的检索中,大多数情况下，用户都希望能够根据语义信息来检索视频片段.然而,从当前媒体理解技术的水平出发,通用的、能够自动对视频信号进行分析并建立语义描述的系统在近期内还难以实现.但在一定的场合或应用中,某些特征往往具有特定的语义含义.利用这些特征,建立专用的视频检索系统也就成为目前视频信号基于内容检索研究中的一个热点.
　　对于视频检索,目前常用的处理方法往往包括如下步骤：(1) 将连续的视频流分割为具有独立语义信息的视频片段——镜头；（2） 对镜头建立内容描述,并根据不同镜头内容描述间的相似性和相关性对镜头进行组织,建立更高层的索引结构.利用得到的组织结果,用户可以通过浏览来选择感兴趣的视频片段进行检索［1～4］.
　　上述方法虽然提供了一种全面、有效的视频检索手段,但需要进行大量的建库工作,而在许多应用中,以用户的检索要求而言并不需要对视频信号建立如此细致的描述.例如,对于电影、电视等视频信号来说,用户一般希望能够根据情节(如打斗、追逐、对峙、交锋等)来检索,而情节往往通过镜头切换的频率得以体现.许多其他编辑处理过的观赏类视频信号也具有类似的特性.根据这个特点,对此类视频信号建立一个反映镜头切换频率的度量——镜头频度,从而为用户提供一个灵活的、对视频信号根据其紧张程度进行检索的方法,无疑具有相当重要的意义.
　　在实际应用中,需要直接对镜头进行频率计算，但因为用于统计镜头数目的单位时间不易确定而难以广泛应用,一种可替代的度量是镜头的平均持续时间.在实际应用中体现为镜头所含的平均帧数.由于目前的镜头分割方法不能确保得到正确的镜头分割结果,在得到的镜头中往往含有少量错分、漏分的镜头.在这种情况下,直接计算平均帧数会给出错误的结果.为了解决这个问题,我们在提高镜头分割算法性能的同时,提出了鲁棒的镜头平均帧数计算方法.采用这种方法,计算得到的平均帧数对于镜头分割中的错误具有较强的抗干扰能力,从而更能从本质上反映视频流中镜头切换的频率（即情节的紧张程度）,也就能更好地满足用户的检索要求.
　　本文第1节对视频流的组成和编辑特性作简要的介绍.第2节对采用的镜头分割技术以及提出的鲁棒镜头平均帧数估计方法进行介绍.第3节给出了对实际视频流利用镜头频度进行检索的实验结果.
1 视频流的组成及编辑特性
　　根据视频信号的产生原理可知,一般的视频信号本身是由多段镜头（摄像机上从ON到OFF期间所获得的一段连续视频信号）通过拼接编辑而成.在镜头内部,相邻和相近的视频帧特性相近,变化很小；但在镜头转换处,视频帧特性往往会发生明显的改变.根据转换处编辑特性的不同,镜头间的转换可分为切变（cut）和渐变（dissolve）两类.
1.1 镜头切变
　　镜头切变是最简单的视频编辑,通过将两个镜头直接拼接而形成,镜头转换间不作任何编辑.
如图1所示,两个长度分别为t1和t2的镜头A(t)和B(t)间进行镜头切变,形成一个长度为t1+t2的镜头C(t).C(t)的定义为
　　　　　　　　　　　（1）

图1　镜头切变
　　可见,在镜头切变t1处相邻帧特性发生突变,而其他地方相邻帧特性则变化很小.
1.2 镜头渐变
　　镜头渐变是一段视频镜头在镜头转换处在某段时间内渐渐转变为后续视频镜头的编辑方式.在实际视频信号编辑中,镜头渐变一般通过线性特性的光学组件或相应的视频编辑设备来完成.镜头渐变的信号构成方式如图2所示.

图2　镜头渐变
　　图2中,在长度为t1的镜头A(t)和长度为t2的镜头B(t)间存在着一个镜头渐变过程.镜头A(t)在t1处终止,经过长度为te1-t1的线性衰减后,在te1处完全消失.镜头B(t)信号在ts2处开始出现,经过长度为te2-ts2的线性增长后,在te2处达到100%.生成的新镜头C(t)长度为te2+t2,渐变过程中的视频信号是镜头A(t)的衰减信号和镜头B(t)的渐增信号之和.若分别定义镜头A(t)和镜头B(t)的长度为te2+t2的扩展镜头信号
　　　　　　　　（2）
和
　　　　　　　　　（3）
则产生的新镜头
c(t)=A*(t)+B*(t),　　　0≤t＜te2+t2.　　　　　　　　　（4）
　　当A(t)或B(t)分别为零信号时,镜头渐变就退化为淡入(fade-in)和淡出(fade-out)这两种常见的视频编辑方式.
2 视频镜头的分割
2.1 镜头切变的检测
　　针对镜头切变的编辑特性,显然，切变检测应针对帧特性的突变来进行.为了减少计算量,加快检测速度,我们采用了帧的直流分量DC图像来作为帧特性的描述.显然,在镜头内部，DC图像变化很小,但在镜头切变处，前后两幅DC图像分别对应于前一镜头的末帧和后一镜头的首帧,图像特性将会出现较大的变化.在DC图像的差序列中,则对应于一个单点峰值的出现.通过检测单点峰值,就可以确定切变的位置.
　　但当图像中景物出现较大或比较明显的运动时,DC图像的特性也会出现较大的变化,导致DC图像差序列中出现峰值.这样,直接对DC图像差设定阈值将导致大量的误检.但由于运动的连续性,其峰值的出现也是连续分布的,而非单点峰值.针对这个特点,我们采取了用DC图像差计算如下定义的最大/次大比值序列.
　　　　　　　　　　　　（5）
并对其进行阈值检测的方法.
　　在公式(5)中,d1(t)=‖IDC(t+1)-IDC(t)‖为相邻帧的DC图像差序列,w为窗口半径,和分别为以t为中心,以w为半径的窗口内此相邻帧DC图像差序列的最大值和次大值.
　　对实际视频信号的切变检测如图3所示,其中第1行(对应于Diff)为视频信号DC图像差序列.第3行(对应于Max)为经过计算而得到的如上定义的最大/次大比值序列.第2行(对应于Aver)为如下定义的最大值/均值序列

w即窗口半径设置为5.

图3 镜头切变检测结果
　　图3中,a,b,d处分别对应于3处镜头切变,而c处则对应于图像中出现的较大运动.从中可以看出,最大/次大比值序列可以给出很好的切变检测结果.
2.2 镜头渐变的检测
　　根据第1.2节中的模型,在镜头渐变过程中各像素以恒定的增量变化.针对此特点,Zhang Hong-jiang等人提出了计算恒定图像（constant image,简称CI)的渐变检测方法［1］.但由于实际渐变过程并不完全符合该模型（渐变过程中图像仍在变化）,我们在实际应用中发现该算法的性能难以令人满意.通过分析,我们提出了如下的渐变检测思想.
首先，我们定义间隔w帧的DC图像差序列：
dw(t)=‖IDC(t+w)-IDC(t)‖.　　　　　　　　　　　（6）
　　相对于渐变而言,在镜头内部,DC图像IDC(t)变化很小,可认为保持恒定,如图4(a)所示.这样,在序列dw(t)上镜头渐变过程就对应于一个梯形形状的峰,如图4(b)所示.其次,我们定义连续w帧的DC图像线性偏差序列
　　　（7）
　　在镜头内部,当景物非静止时,局部运动使Ew(t)保持一个相对较高的水平.但在镜头转换处,信号的变化以线性变化为主,将导致谷值的出现,如图4(c)所示.

图4　镜头渐变检测示意图
　　根据以上分析,我们采用了对dw(t)和Ew(t)分别检测宽度超过宽度阈值wthreshold的峰和谷的算法.在实现中,w设置为10,宽度阈值wthreshold也设为10.检测结果如图5所示.
　　图5(a)和(b)分别为对两段视频信号的检测结果,其中图5(a)中的a和b为两处渐变过程,而图5(b)中的c和d则为两处连续的渐变过程（实际上是前一字幕淡出接着后一字幕的淡入）.

图5 镜头渐变检测结果
2.3 镜头频度的鲁棒估计
　　通过对视频流采用上述镜头分割算法,可以得到一个镜头序列.下面我们将对镜头序列中镜头切换频率度量——镜头频度的估计进行讨论.
　　镜头频度的直接含义是在单位时间内出现的镜头数目.但由于不同镜头的持续时间相差很大,在实际应用中统计镜头数的单位时间就难以确定.一种与镜头频度相应的度量是镜头的平均持续时间,即计算以此镜头为中心的给定长度窗口内镜头持续时间的平均值.显然,镜头频度越高,镜头的平均持续时间越小.在实现中,镜头的持续时间往往用镜头中包含的帧数更方便地加以表示.
　　值得注意的是,镜头分割算法不能保证总能给出正确的分割结果,而是不可避免地存在着漏分和错分现象.若对镜头窗中所有镜头计算平均帧数,则得到的结果将直接受到漏分和错分的影响.此外,从人的感知角度而言,与情节紧张程度相关联的是镜头窗中大多数镜头帧数的平均统计,在计算中也应除去含有最多帧数和最少帧数的一些镜头.
　　基于上述分析,我们提出了如下的镜头平均帧数计算方法.
　　将镜头序列记为f(n),其值代表第n个镜头中所含的帧数.记窗口长度为L,SL(n)为以n为中心，长度为L的窗口中镜头帧数构成的集合.对SL(n)中的元素按从小到大的顺序排序,将除去其中最小a个和最大b个元素，得到的新集合记为Sa,bL(n),则镜头平均帧数可按如下公式计算.
　　　　　　　　　　　（8）
即镜头的平均帧数通过对长度为L窗口中去除最小a个和最大b个后的元素计算均值得到.显然,由于漏分造成的长镜头和错分造成的短镜头对此平均帧数的计算影响很小,算法具有较强的鲁棒性.
3 算法实现与分析
　　利用本文中提出的算法,我们设计并实现了一套镜头分割、计算镜头频度以及利用镜头频度对视频进行浏览的系统,并利用此系统对实际的影片视频流进行了基于镜头频度的检索.
　　系统提供了利用镜头帧数对视频进行浏览检索的功能,浏览界面如图6(a)所示.其中,上行为分割得到的镜头帧数序列,下行为采用文中算法得到的镜头平均帧数序列.在镜头平均帧数的计算中,我们将窗口长度L设定为8,滤去的最小元素个数a和最大元素个数b均设为2.为便于交互浏览,Naver(n)计算所用的窗口不是以n为中心,而是以n为起点的窗口.通过选择双击浏览界面中镜头对应的位置,系统就可从指定镜头开始视频播放.这样,用户可以通过选择镜头平均帧数序列中具有较小平均帧数的镜头来选择镜头切换频繁的视频片段（一般都对应于情节较为紧张的片段）来浏览检索.
　　
(a)　　　　　　　　　　　　　　　(b)
图6 利用镜头频度对视频信号进行检索
　　为了对镜头频度的作用进一步加以说明,我们在系统中提供了对镜头序列按平均帧数从小到大重新排列的功能,以便于用户的检索.重排后得到的代表帧序列如图6(b)所示.图中显示的是对美国影片“黑衣人”（Man In Black）(上)中的镜头代表帧重排得到的结果,经测试，序列中排在前面的代表帧对应的基本都是影片中情节紧张的部分.在图6(b)的重排序列中代表帧按顺序依次为：(1) 虫族在餐馆的谋杀；(2) 球型闪电在MIB中心造成的混乱；(3) 主人公J和K调查枪支来源与外星人在百货店的对峙；(4) 主人公J加入MIB的手续过程；(5) 主人公J对外星人的追逐等.其中除(4)外,都属于情节较为紧张的场面,而(4)是出于表现手法的需要而采用了一系列的短镜头.可见,镜头频度对于影片提供了一种相当好的根据情节进行检索的手段.
4 结 论
　　在本文中,根据影片等经过编辑处理过的观赏类视频信号中情节往往通过镜头频度——镜头切换的频率来体现这一特点,我们提出了对此类视频信号根据镜头频度进行检索的方法.针对实际视频信号中镜头切变和渐变的特点,我们分别设计并实现了相应的镜头分割算法，在此基础上提出了反映镜头频度的度量——镜头平均帧数的鲁棒计算方法.对实际影片进行的浏览和检索显示出,镜头频度可以很好地满足对影片根据情节进行检索的要求.
*　本文研究得到国家863高科技项目基金和国家“211”学科建设项目基金资助.
本文通讯联系人：白雪生，北京 100084,清华大学计算机科学与技术系信息教研组
作者简介：白雪生,1972年生,博士生,主要研究领域为基于内容检索,计算机视觉.
　　　　　徐光祐,1940年生,教授,博士生导师,主要研究领域为计算机视觉,多媒体技术，基于内容检索.
　　　　　史元春,女,1967年生,在职博士生,副教授，主要研究领域为计算机支持的协同工作,多媒体技术.
作者单位：白雪生，徐光祐，史元春（清华大学计算机科学与技术系　北京　100084）
　　　　　白雪生，徐光祐，史元春(清华大学智能技术与系统国家重点实验室　北京　100084)
参考文献：
［1］Zhang H J, Kankanhalli A, Smoliar S W. Automatic partitioning of animate video. Technical Report, Institute of Systems Science, National University of Singapore, 1992
［2］Yeung M M, Yeo B L, Liu B. Extracting story units from long programs for video browsing and navigation. In： IEEE Computer Society ed. Proceedings of the International Conference on Multimedia Computing and Systems. Los Alamitos： IEEE Computer Society Press, 1996. 291～305
［3］Irani M, Anandan P, Hsu S. Mosaic based representations of video sequences and their applications. In： IEEE Computer Society ed. Proceedings of the 5th International Conference on Computer Vision. Los Alamitos： IEEE Computer Society Press, 1995. 605～611
［4］Ardizzone E, Cascia M L. Automatic video database indexing and retrieval. Multimedia Tools and Applications, 1997,4(2)：29～56
收稿日期：1998-06-16，修改日期：1998-09-17
