基于内容的视频检索

1、基于内容的视频检索曹亚光(北京理工大学现代远程教育学院，北船院，计算机专升本2001级，2001023011076)摘要：视频检索有着广泛的应用和广阔的发展前景，是当前多媒体研究领域的热点。系统地介绍了基于内容的视频检索的一般实现步骤。从分析基于内容的视频检索的系统结构出发，全面地探讨了系统中所涉及的视频结构的构造、镜头切变检测技术、关键帧提取技术、从视频流中构造场景或组的技术、特征提取技术以及视频检索、浏览和检索反馈技术，重点分析了其中一些关键技术中各种实现方法的优缺点，并介绍了一些新的技术方法。最后提出了一些需要进一步研究的问题。关键词：视频数据库，基于内容，视频检索，镜头切变检测，关键帧

2、提取，特征提取，检索反馈1前言随着多媒体技术和网络技术的飞速发展，视频在多个领域得到广泛地应用。对这些海量的而且包含大量非结构化信息的数据进行组织、表达、管理、查询和检索成为迫切的需求。因此基于内容的视频检索(Content-Based Video Retrieval，CBVR)成为近年来研究的热点。基于内容的视频检索系统如图1所示。图1 基于内容的视频检索系统框图首先要进行视频结构分析，将视频序列分割为镜头，并在镜头内选择关键帧，这是实现一个高效的CBVR系统的基础和关键。然后提取镜头的运动特征和关键帧中的视觉特征，作为一种检索机制存入视频数据库。最后根据用户提交的查询按照一定特征进行视频检

3、索，将检索结果按相似性程度交给用户，当用户对查询结果不满意时可以优化查询结果，自动根据用户的意见灵活地优化检索结果。2视频结构的构造及有关的算法为了对视频数据库进行基于内容的查询，首要要构造便于检索的视频结构。视频数据可以按照由粗到细的顺序划分为四个层次结构：视频(Video)、场景( Scene)、镜头(Shot)和图像帧(Frame)。镜头是视频数据的基本单元，它代表一个场景中在时间上和空间上连续的动作，是摄像机的一次操作所摄制的视频图像，任何一段视频数据流都是由许多镜头组成的。镜头的切换有两种：突变和渐变。突变是指从一个镜头直接切变到另一个镜头；而渐变根据视频编辑手法的不同可以分为3种：

4、淡化(Fade，又细分为Fade in和Fade out)、融化(Dissolve)和滑变(Wipe)。渐变是切变检测中的难点。整个视频结构构造过程分以下三个步骤：从视频流中提取镜头、从镜头中选择关键帧和从视频流中构造场景或组。2.1 从视频流中提取镜头（即对视频流的切变检测）镜头是视频数据的基本单元，视频处理首先就需要把视频自动地分割为镜头，以作为基本的索引单元，这一过程就称为镜头边界的检测。它是实现基于内容的视频检索的第一步，其核心处理是镜头切变检测。视频结构的构造中，镜头切变检测是重点，而且其算法和思想可用于其它步骤，故应重点研究。2.1.1 基于颜色特征的方法(1) 模板匹配法(对应像

5、素法)模板匹配法是将两帧对应像素差的绝对值之和作为帧间差，当帧间差大于某个阈值t时，则认为有镜头的切换。模板匹配法的缺点是，由于与像素的位置密切相关，因此对噪声和物体运动十分敏感，容易造成误识别。张宏江等人3提出将各帧划分为8×8像素的子块，并对每个块取平均，再用这个平均值对前后帧的对应子块进行比较，这种方法对小的噪声和运动不敏感。(2) 直方图法直方图法是使用得最多的计算帧间差的方法，它丢失了颜色的位置信息，因而抗噪声能力要比模板匹配强。颜色直方图法的缺点是，两幅图像可能内容完全不同但直方图相似，也容易造成误识别。一种改进的方法是将图像划分成若干子块分别对各子块进行匹配。A. Na

6、gasaka和Y. Tanaka4提出了一种将视频帧划分为4×4相同大小的子块并比较相应子块的方法。其它改进方法还有X2直方图匹配法5和Swanberg等人6采用的模板匹配法和直方图匹配法相结合的方法。2.1.2 基于边缘的方法由于在镜头切变时新旧边缘应在不同的位置，所以可先提取两幅图像的边缘，计算新边缘在旧边缘的基础上增加和减少像素比例，当大于某一个阈值时便认为发生镜头切换。缺点是计算量大，当边缘不明显时效果差。2.1.3 光流检测法张宏江等人3还提出了光流检测法，该方法的原理是镜头切换时无光流，而镜头运动应适合某种特定的光流类型。它能将渐变切换与镜头的运动区分开来，但计算复杂且在

7、光照变化很大情况下检测失败。2.1.4 基于模型的方法Hampapur等人7，8通过对视频制作过程的研究，提出了一种可用于镜头边界检测的视频编辑模型。它的缺点是，建模过程比较复杂，需要对每种切换类型建立模型。这种方法适用于专业领域。2.1.5 压缩域的方法由于越来越多的视频数据是以压缩的形式保存，因此，最好能直接在压缩域中进行边界检测。(1) DC系数法DC 图像是原图像8×8的平均，它包含了原图像的基本全局信息，且具有压缩性处理过程更加快捷的特点。可以先从各帧中提取DC图像，再用帧间差的方法进行检测。(2) 运动矢量法张宏江等人3根据统计发现镜头转换处的BP帧中有效运动向量个数较少

8、，因此可以对这些帧进行解压，用非压缩视频的边界检测方法进行镜头边界检测。文献9中从视频流中提取宏块的运动矢量，宏块的相似度与它们的运动矢量成反比，帧的相似度由各宏块的相似度取平均求得。文献10中将各帧的类似度进行了归一化，（公式）结果是多帧类似度加权相加的结果，可以取比较简单的门限进行判断，减少了计算复杂度，多帧加权减小了误检，但对渐变检测效果不佳。这类方法的缺点是，目前的MPEG算法是面向数据压缩的，而不是面向视频内容表示的。随着基于内容的编码标准MPEG-4和多媒体数据内容表示MPEG-7成为国际标准后，上述问题将得到解决。(3) 模糊查找法一种方法是只用视频流中的I帧进行检测，它适用于检

9、测精度不是很高的需求；另一种方法是先找出差异大的相邻两个I帧作为可能存在镜头切换处，再用两帧间的B和P帧确定准确位置，这种方法精度较高。两种方法均受编码算法优劣的影响。2.1.6 几种改进的算法张宏江等人3提出了双阈值比较法。当两帧间差在阈值d1和d2之间时，便认为潜在渐变开始，将差值开始累加，直到累加和大于d2时认为有渐变，当帧间差小于d1时认为渐变结束。这种方法对渐变检测有较好的效果，但对镜头的缓慢运动仍可能会造成误识别。Yeo B L11提出了一种滑动窗口检测法。先以待检的帧作为中心开一个窗，计算各帧与邻帧的帧间差，若该帧的差值大于窗口内的其它所有帧的差值，且大于第二大差值的某倍数，则认

10、为是发生切换。用双重窗口法12可进一步改进以减小搜索量，先选取一个大的窗口，取平均值，将大于均值一定倍数的差值作为候选切变帧，再以候选切变帧为中心取小窗口，检测具体位置。大窗口可避免误检并减小搜索量；小窗口可避免大运动造成的漏检。由于在很多情况下，人们仅对图像中的某一区域感兴趣。因此，先进行图像分割，仅利用某一区域的信息进行检索。近几年来这一领域的研究逐渐引起了人们的兴趣。2.2 从镜头中选择关键帧关键帧(也称代表帧)是用于描述一个镜头的关键图像帧，它通常会反映一个镜头的主要内容。关键帧的使用大大减少了视频索引的数据量，同时也为检索和浏览视频提供了一个组织框架。关键帧的提取原则是“宁滥勿缺”。

11、关键帧选取的方法有以下几类：2.2.1 基于镜头的方法一段视频分割成镜头后，将每个镜头的首帧(或首帧与末帧)作为镜头的关键帧。该方法实现起来比较简单，无论镜头的内容如何，关键帧的数量都是一定的(1帧或2帧)，但效果不是很稳定，因为每个镜头的首帧或末帧不一定总是能够反映镜头的主要内容。2.2.2 基于内容分析的方法这种方法基于每一帧的颜色、纹理等视觉信息的改变来提取关键帧，当这些信息有显著变化时，当前的帧即可作为关键帧。张宏江等人3依据帧间的显著变化来选择多个关键帧，首先把镜头的第一帧作为关键帧，然后计算前一个关键帧与剩余帧之差，如果差值大于某一阈值，则再选取一个关键帧。这种方法可以根据镜头内容

12、的变化程度选择相应数目的关键帧，但所选取的帧不一定具有代表意义，而且在有镜头运动时，容易选取过多的关键帧。帧平均法和直方图平均法13统计所有帧的像素值或直方图平均，取最接近平均值的帧作为代表帧。2.2.3 基于运动分析的方法Wolf14通过光流分析来计算镜头中的运动量，在运动量取局部最小值处来选取关键帧，它反映了视频数据中的静止，视频中通过摄像机在一个新的位置上停留或通过人物的某一动作的短暂停留来强调其本身的重要性。Wolf的这种基于运动分析的方法可以根据镜头的结构选择相应数目的关键帧。如果先把图像中的运动对象从背景中取出，再计算对象所在位置的光流，可以取得更好的效果。合成法将镜头中的所有运动

13、转换拼接成一个合成帧作为关键帧。2.2.4 基于聚类的方法聚类提取15的方法首先要确定一个初始类心，然后根据当前帧与类心的距离来判断是归为该类还是作为新的类心，再将镜头中帧分类后取各类中离类心最近的帧作为关键帧。另外，Zhao16提出了一种基于最近特征线(Nearest Feature Line，NFL) 的端点检测算法用于选取关键帧。该方法的主要原理是用某些特征点的连线(特征线)近似并代表某个类的所有特征样本轨迹，而这些特征点就是关键帧。2.3 从视频流中构造场景或组计算镜头间的相似性（实际是关键帧间的比较），选择合适的聚类算法进行分析。按时间顺序和关键帧的相似程度可分为场景17，也可以只按

14、关键帧的相似程度进行分组。3 特征提取视频分割成镜头后就要对各个镜头进行特征提取，得到一个尽可能充分反映镜头内容的特征空间，这个特征空间将作为视频聚类和检索的依据。特征提取包括关键帧中的视觉特征和镜头的运动特征的提取。3.1 颜色特征颜色是图像最显著的特征，与其它特征相比，颜色特征计算简单、性质稳定，对于旋转、平移、尺度变化都不敏感，表现出很强的鲁棒性。颜色特征包括颜色直方图、主要颜色、平均亮度3等。其中利用主要颜色和平均亮度进行图像的相似匹配是很粗略的，但是它们可以作为层次检索方法的粗查，对粗查的结果再利用子块划分的颜色直方图匹配进行进一步的细查。为了能够在大规模图像数据集中进行快速的搜索，

15、Smith和Change18等人提出了颜色集的概念：首先将RBG颜色空间转换为视觉上一致空间HSV，然后量化为m个颜色条，颜色集就定义为量化后的颜色空间中颜色的一种选择。由于颜色集特征向量是二叉的，因而可以通过构造二叉树来进行快速的搜索。3.2 纹理特征20世纪70年代初Haralick19等人提出了纹理特征的共生矩阵表示法，即利用纹理在灰度级的空间相关性，先根据图像像素间的方向和距离构造一个共生矩阵，再从中提出有意义的统计数据作为纹理的特征表示。该方法的缺点是这些统计特征没有和人在视觉上对纹理特征的感知之间建立对应。于是不少人提出了其它的纹理特征度量方法，其中Tamura提出的纹理特征集可以

16、很好地与人类视觉感知相对应，这些特征包括：粗糙度、对比度、方向性、线像度、规则性、粗略度。其中最重要的特征是纹理粗糙度、对比度和方向性。另外，许多研究者开始将小波变换应用于纹理特征表示。Manjunath等人对三种小波变换方法(角、树结构、Galbo)做了比较之后，发现Galbo小波变换最符合人类视觉特征的表达。随着小波理论的建立，Gross M IT20等人提出了基于小波的纹理表达。参考文献21中有综合性的描述。3.3 形状特征形状分析首先需要采用合适的图像分割算法把不同对象从图像中分割出来，再用各种方法进行匹配测量。形状特征表示的一个重要准则是要求对位移、旋转、缩放的不变性，通常形状的表示

17、可以分为基于边界和基于区域两类。它们分别采用傅里叶21描述和矩不变量22表述特征，另外新的研究方向有弹性变形模板和边界方向直方图。最近的表达方法还有Chamfer匹配23，Borgerfos提出的层次Chamfer匹配算法，以及Wallace和Mitchell提出的局部形状分析算法的3D形状表达。3.4 运动特征运动特征是视频镜头的重要特征，它反映了视频的时域变化，也是用视频例子进行检索的重要内容。运动分析的方法有基于光流方程的方法、基于块的方法、像素递归方法和贝叶斯方法24等，但这些方法计算量大。于是，Tonomura等人25提出了X线断层分析的方法，将整个视频序列沿时间轴进行切片，从切片图

18、像中分析运动情况。Patel和Sethi26提出利用MPEG中的B和P帧的运动向量来避免光流计算和块匹配。该方法利用宏块的运动得到一个有九个分量的特征向量，再用这个特征向量判断镜头的运动。张宏江等人3用计算镜头内各帧平均亮度和主要颜色的均值和方差作为镜头运动量大小的度量，在新闻视频中取得了较好的效果。3.5 其它其它的特征主要有物体间的方位关系，特征点（即满足一定要求的像点，如曲线交点），基于目标的特征等，目前研究得较少。4 视频检索和浏览在对视频流中各镜头提取关键帧并进行特征提取后，还要建立基于视频特征的索引。通过索引，就可利用基于关键帧特征，或是基于镜头动态特征，或是将二者相结合进行对视频

19、进行检索和浏览了。于内容的检索是一个近似匹配，逐步求精的循环过程，主要包括初始查询说明、相似性匹配、返回结果、特征调整、人机交互，检索反馈等步骤，直至获得用户满意的查询结果。(1) 基于关键帧的检索视频被抽象为关键帧后，搜索就变成按照某种相似度来检索数据库中与查询描述相似的关键帧。通常使用的查询方法是通过目标特征说明(直接)的查询和通过可视实例(示例)的查询。检索时，用户也可以指定使用特定的特征集。如果检索到关键帧，用户就可以利用播放来观看它所代表的视频片断。浏览可以跟随检索，作为检验检索到的关键帧的上下文边界联系。浏览也可以初始化查询，即当浏览时，用户可以选择一个图像来查询所有与该图像相似的

20、关键帧。(2) 基于镜头动态的检索基于镜头和主体目标的运动特征来检索镜头是视频查询的进一步要求。可以利用摄像机操作的表示来查询镜头，可以利用运动方向和幅度特征来检索运动的主体目标。在查询中还可以将运动特征和关键帧特征结合起来，检索出具有相似的动态特征但静态特征不同的镜头。(3) 视频浏览对于视频来说，浏览与有明确目的的检索同样重要。浏览需要视频具有在语义层次上的表示，有学者提出了场景转换图(STG)的概念，以一个有向图的节点表示场景，边表示时间上的转换。通过对STG的化简，可以去掉不重要的镜头，得到视频的紧凑的表示。由于单纯从图像从获得语义信息非常困难，也有学者提出了综合采用视频中的图像、语音

21、以及文字信息的方法。(4) 视频的检索反馈在检索的实现中除利用图像的视觉特征进行检索外，还应根据用户的反馈信息不断学习改变阈值重新检索，实现人机交互，直到达到用户的检索要求。如何定义是否两个视频相似，仍然是尚未解决的问题，限制了检索系统的应用范围。而且由于视频内容的复杂性，不同用户在检索过程中，即使对同一部视频，其注重的角度也有可能不同，因此接受用户的反馈意见，当用户对查询结果不满意时可以优化查询结果，突出用户的需要。在综合了人类视觉心理特征的基础上，介绍了一种视频相似衡量的模型，从镜头、视频等多个层次，多种视觉判断角度，对视频间相似度进行衡量。并在此基础上提出了从多个粒度镜头层次和视频层次进

22、行检索反馈的方法。整个过程是自动进行的，根据用户的意见灵活地优化检索结果。5 总结与讨论基于内容的视频检索技术是一种综合集成技术，其一些关键技术如镜头边界检测、关键帧提取、特征提取等的研究虽然取得了一定的进展，但由于各种理论和相关技术都不尽完善，所以还有许多问题需要进一步深入研究。（1）提高识别率尽管目前已有多种算法，对突变切换和简单的渐变切换识别率可以达到80%以上，但由于视频内容的丰富性，尚存在许多问题，如大物体和镜头运动的区分、高速的物体或镜头运动、灯光背景的照射和闪烁、复杂的剪辑效果(如碎裂、波纹、变形等)等复杂情况下，误识别和漏识别率普遍较高。镜头的检测所用到的颜色、纹理、运动等特征

23、还用于最后的检索处理。因此，有必要对镜头切换识别进行重点研究。（2）合适阈值的选取阈值选取不当会造成误检和漏检。有的视频变化缓慢，应选取较小的阈值；反之则应选取较大的阈值。从而应不断地试验，尽量达到均衡，并综合利用人的知识进行人机交互式学习选取合适的阈值。以上所介绍的各种方法多受阈值选取优劣的限制，近年来趋向于更加鲁棒性的研究，如利用K均值法的检测28，可以减少阈值选取的限制。（3）提高速度由于视频的数据量大，处理时间长，算法处理的速度也很重要。由于大量的视频数据是以压缩形式存放的，直接对压缩数据进行处理可以节约时间。目前，很多算法的识别速度与实际应用相距还很远。（4）有效的特征提取特征提取是

24、基于内容的视频检索技术的关键。以往的研究主要集中在颜色、纹理、形状等低级特征上，但这些特征不能完全准确地描述出图像的含义，如何提取高级特征使检索更接近人类视觉生理、心理特点是一个研究课题。另外由于视频数据具有时空性，如何更好地提取物体和对象的运动特征也是一个研究课题。（5）高层语义检索目前在切变检测和检索算法中底层语义特征比较成熟，检测结果比较理想，故用得最多。但高层语义，如用户感兴趣的事件、运动、物体特征的变化等等，也是用户的检索需求。在实际的视频检索服务中，用户的最终要求是能够直接访问视频中的对象，如对某种动物行为现象的收集、某个球星历次参赛录像的查询等，这些要求更多的是从高层语义出发的检

25、索方式。基于对象的检索、高层语义和低层特征的关联、视频数据高级语义的提取都是视频检索算法方向。（6）综合的多特征检索技术声音和文字是伴随视频的高层次内容，包含着与其密切相关的许多信息，它们还间接地对视频分类、场景分割、对象识别等起很大作用。因此，在视频检索中加入声音和文字信息辅助检索能大大简化视频处理的复杂度，增加视频检索的效率，是完善基于内容的视频检索技术的可行方法。（7）检索效果的评价尚没有标准由于视频内容的丰富性和复杂性，以及人对视频内容评判的主观性，使得其检索性能的优劣很难有一个统一的标准。这也是CBVR技术研究的一个方向。目前主要使用多媒体信息检索中的两个指标：查全率（recall）

26、和准确率（precision），定义为recall = correct/(correct + missed)precision = correct/(correct + falsePosition)其中：correct为正确检测到的数目，missed为漏检的个数，falsePosition为误检的个数。参考文献：1 张洪德, 刘雨, 唐波. 基于内容的视频检索技术研究. 电视技术. 2001. 6: 30-39.2 陆燕, 陈福生. 基于内容的视频检索技术. 计算机应用研究. 2003. 11: 1-4.3 Zhang H J, Wu Jianhua, et al. An Integrated

27、 System for Content-Based Video Retrieval and BrowsingJ. Pattern Recognition. 1997. 30(4): 643-657.4 A Nagasaka, et al. Automatic Video Indexing and Full Video Search for Object AppearancesC. Second Working Conference on Visual Database Systems. IFIP WG2.6. 1991. 119-133.5 Haitao Jiang, Abdel Salam

28、Helal. Scene Change Detection Techniques for Video Databases System. Multimedia Systems. 1998. 6: 186-195.6 Deborah Swanberg, Chiao-Fe Shu, Ramesh Jain. Knowledge Guided Parsing in Video Database C. Storage and Retrieval for Image and Video Databases Proc. SPIE 1908. 1993. 13-24.7 Song S Moon-Ho, et

29、 al. On Detection of Gradual Scene Changes for Parsing of Video Data C. Storage and Retrieval for Image and Video Databases Proc. SPIE 3312. 1998. 404-413.8 Hampapur A , et al. Digital Video SegmentationC. Proc. Second Annual ACM. New York, NY, USA. 1994. 357-364.9 Zhang H J, Kankanhalli A, Smoilar

30、S W. Automatic Partitioning of Full-Motion Video. Multimedia System. 1993: 10-28.10 一种新的基于运动矢量的MPEG视频码流cut检出算法. Journal of Image of Graphics. 1999. 4: 323-326.11 Yeo B J, Liu B. Rapid Scene Analysis on Compressed Video. IEEE Trans Circuits and Systems for Video Technology. 1995. 5: 533-544.12 陆海斌等.

31、一种高效的视频切变检测算法. 图形图像学报. 1999. 4: 805-80913 Bilge Gunsel, Tekalp A Murat. Content-based Access to Video Objects: Temporal Segmentation, Visual Summarization and Feature Extraction. Singal Processing. 1998. 66: 261-280 14 Wolf Wayna. Key Frame Selection by Motion Analysis. On: Proc. of IEEE Int. Conf.

32、On Acoustics, Speech and Signal Processing. ICASSP. Atlanta. 1996. 7-10.15 Yueting Zhuang, Yong Rui, Huang T S. Adaptive Key Frame Extraction Using Unsupervised Clustering. In: Proc. IEEE Int. Conf. on Image Proc. Chicago, USA. 1998. 76-81.16 L Zhao, et al. Key-frame Extraction and Shot Retrieval us

33、ing Nearest Feature Line(NFL)C. Proc. of International Workshop on Multimedia Information Retrieval. in conjunction with ACM Multimedia Conference 2000. Los Angeles, USA. 2000. 217-220.17 Yong Rui, Huang T S, et al. Exploring Video Structure Beyond the Shots. In: Proc IEEE Conf on Multimedia Computi

34、ng and System. Austin, Texas, USA. 1998. 54-57.18 Smith J R, Chang S F. Single Color Extraction and Image Query. In: Proc. IEEE Int. Conf. on Image Proc. 1995. 80-88.19 Haralick R M, Shanmugam K, Dinstein I. Texture Features for Image Classification. IEEE Trans on Sys Man and Cyb. 1973. SMC-3(6): 768-780.20 Gross M IT, Koch R, Lippert L, Dreger A. Multiscale Image Texture Analysis in Wavelet Spaces. In: Proc. IEEE Int.