基于内容的视频检索

-1-基于内容的视频检索曹亚光(北京理工大学现代远程教育学院，北船院，计算机专升本2001级，2001023011076)摘要：视频检索有着广泛的应用和广阔的发展前景，是当前多媒体研究领域的热点。系统地介绍了基于内容的视频检索的一般实现步骤。从分析基于内容的视频检索的系统结构出发，全面地探讨了系统中所涉及的视频结构的构造、镜头切变检测技术、关键帧提取技术、从视频流中构造场景或组的技术、特征提取技术以及视频检索、浏览和检索反馈技术，重点分析了其中一些关键技术中各种实现方法的优缺点，并介绍了一些新的技术方法。最后提出了一些需要进一步研究的问题。关键词：视频数据库，基于内容，视频检索，镜头切变检测，关键帧提取，特征提取，检索反馈1前言随着多媒体技术和网络技术的飞速发展，视频在多个领域得到广泛地应用。对这些海量的而且包含大量非结构化信息的数据进行组织、表达、管理、查询和检索成为迫切的需求。因此基于内容的视频检索(Content-BasedVideoRetrieval，CBVR)成为近年来研究的热点。基于内容的视频检索系统如图1所示。图1基于内容的视频检索系统框图-2-首先要进行视频结构分析，将视频序列分割为镜头，并在镜头内选择关键帧，这是实现一个高效的CBVR系统的基础和关键。然后提取镜头的运动特征和关键帧中的视觉特征，作为一种检索机制存入视频数据库。最后根据用户提交的查询按照一定特征进行视频检索，将检索结果按相似性程度交给用户，当用户对查询结果不满意时可以优化查询结果，自动根据用户的意见灵活地优化检索结果。2视频结构的构造及有关的算法为了对视频数据库进行基于内容的查询，首要要构造便于检索的视频结构。视频数据可以按照由粗到细的顺序划分为四个层次结构：视频(Video)、场景(Scene)、镜头(Shot)和图像帧(Frame)。镜头是视频数据的基本单元，它代表一个场景中在时间上和空间上连续的动作，是摄像机的一次操作所摄制的视频图像，任何一段视频数据流都是由许多镜头组成的。镜头的切换有两种：突变和渐变。突变是指从一个镜头直接切变到另一个镜头；而渐变根据视频编辑手法的不同可以分为3种：淡化(Fade，又细分为Fadein和Fadeout)、融化(Dissolve)和滑变(Wipe)。渐变是切变检测中的难点。整个视频结构构造过程分以下三个步骤：从视频流中提取镜头、从镜头中选择关键帧和从视频流中构造场景或组。2.1从视频流中提取镜头（即对视频流的切变检测）镜头是视频数据的基本单元，视频处理首先就需要把视频自动地分割为镜头，以作为基本的索引单元，这一过程就称为镜头边界的检测。它是实现基于内容的视频检索的第一步，其核心处理是镜头切变检测。视频结构的构造中，镜头切变检测是重点，而且其算法和思想可用于其它步骤，故应重点研究。2.1.1基于颜色特征的方法(1)模板匹配法(对应像素法)模板匹配法是将两帧对应像素差的绝对值之和作为帧间差，当帧间差大于某个-3-阈值t时，则认为有镜头的切换。模板匹配法的缺点是，由于与像素的位置密切相关，因此对噪声和物体运动十分敏感，容易造成误识别。张宏江等人[3]提出将各帧划分为8×8像素的子块，并对每个块取平均，再用这个平均值对前后帧的对应子块进行比较，这种方法对小的噪声和运动不敏感。(2)直方图法直方图法是使用得最多的计算帧间差的方法，它丢失了颜色的位置信息，因而抗噪声能力要比模板匹配强。颜色直方图法的缺点是，两幅图像可能内容完全不同但直方图相似，也容易造成误识别。一种改进的方法是将图像划分成若干子块分别对各子块进行匹配。A.Nagasaka和Y.Tanaka[4]提出了一种将视频帧划分为4×4相同大小的子块并比较相应子块的方法。其它改进方法还有X2直方图匹配法[5]和Swanberg等人[6]采用的模板匹配法和直方图匹配法相结合的方法。2.1.2基于边缘的方法由于在镜头切变时新旧边缘应在不同的位置，所以可先提取两幅图像的边缘，计算新边缘在旧边缘的基础上增加和减少像素比例，当大于某一个阈值时便认为发生镜头切换。缺点是计算量大，当边缘不明显时效果差。2.1.3光流检测法张宏江等人[3]还提出了光流检测法，该方法的原理是镜头切换时无光流，而镜头运动应适合某种特定的光流类型。它能将渐变切换与镜头的运动区分开来，但计算复杂且在光照变化很大情况下检测失败。2.1.4基于模型的方法Hampapur等人[7，8]通过对视频制作过程的研究，提出了一种可用于镜头边界检测的视频编辑模型。它的缺点是，建模过程比较复杂，需要对每种切换类型建立模型。这种方法适用于专业领域。2.1.5压缩域的方法由于越来越多的视频数据是以压缩的形式保存，因此，最好能直接在压缩域中进行边界检测。(1)DC系数法DC图像是原图像8×8的平均，它包含了原图像的基本全局信息，且具有压缩性-4-处理过程更加快捷的特点。可以先从各帧中提取DC图像，再用帧间差的方法进行检测。(2)运动矢量法张宏江等人[3]根据统计发现镜头转换处的BP帧中有效运动向量个数较少，因此可以对这些帧进行解压，用非压缩视频的边界检测方法进行镜头边界检测。文献[9]中从视频流中提取宏块的运动矢量，宏块的相似度与它们的运动矢量成反比，帧的相似度由各宏块的相似度取平均求得。文献[10]中将各帧的类似度进行了归一化，（公式）结果是多帧类似度加权相加的结果，可以取比较简单的门限进行判断，减少了计算复杂度，多帧加权减小了误检，但对渐变检测效果不佳。这类方法的缺点是，目前的MPEG算法是面向数据压缩的，而不是面向视频内容表示的。随着基于内容的编码标准MPEG-4和多媒体数据内容表示MPEG-7成为国际标准后，上述问题将得到解决。(3)模糊查找法一种方法是只用视频流中的I帧进行检测，它适用于检测精度不是很高的需求；另一种方法是先找出差异大的相邻两个I帧作为可能存在镜头切换处，再用两帧间的B和P帧确定准确位置，这种方法精度较高。两种方法均受编码算法优劣的影响。2.1.6几种改进的算法张宏江等人[3]提出了双阈值比较法。当两帧间差在阈值d1和d2之间时，便认为潜在渐变开始，将差值开始累加，直到累加和大于d2时认为有渐变，当帧间差小于d1时认为渐变结束。这种方法对渐变检测有较好的效果，但对镜头的缓慢运动仍可能会造成误识别。YeoBL[11]提出了一种滑动窗口检测法。先以待检的帧作为中心开一个窗，计算各帧与邻帧的帧间差，若该帧的差值大于窗口内的其它所有帧的差值，且大于第二大差值的某倍数，则认为是发生切换。用双重窗口法[12]可进一步改进以减小搜索量，先选取一个大的窗口，取平均值，将大于均值一定倍数的差值作为候选切变帧，再以候选切变帧为中心取小窗口，检测具体位置。大窗口可避免误检并减小搜索量；小窗口可避免大运动造成的漏检。由于在很多情况下，人们仅对图像中的某一区域感兴趣。因此，先进行图像分-5-割，仅利用某一区域的信息进行检索。近几年来这一领域的研究逐渐引起了人们的兴趣。2.2从镜头中选择关键帧关键帧(也称代表帧)是用于描述一个镜头的关键图像帧，它通常会反映一个镜头的主要内容。关键帧的使用大大减少了视频索引的数据量，同时也为检索和浏览视频提供了一个组织框架。关键帧的提取原则是“宁滥勿缺”。关键帧选取的方法有以下几类：2.2.1基于镜头的方法一段视频分割成镜头后，将每个镜头的首帧(或首帧与末帧)作为镜头的关键帧。该方法实现起来比较简单，无论镜头的内容如何，关键帧的数量都是一定的(1帧或2帧)，但效果不是很稳定，因为每个镜头的首帧或末帧不一定总是能够反映镜头的主要内容。2.2.2基于内容分析的方法这种方法基于每一帧的颜色、纹理等视觉信息的改变来提取关键帧，当这些信息有显著变化时，当前的帧即可作为关键帧。张宏江等人[3]依据帧间的显著变化来选择多个关键帧，首先把镜头的第一帧作为关键帧，然后计算前一个关键帧与剩余帧之差，如果差值大于某一阈值，则再选取一个关键帧。这种方法可以根据镜头内容的变化程度选择相应数目的关键帧，但所选取的帧不一定具有代表意义，而且在有镜头运动时，容易选取过多的关键帧。帧平均法和直方图平均法[13]统计所有帧的像素值或直方图平均，取最接近平均值的帧作为代表帧。2.2.3基于运动分析的方法Wolf[14]通过光流分析来计算镜头中的运动量，在运动量取局部最小值处来选取关键帧，它反映了视频数据中的静止，视频中通过摄像机在一个新的位置上停留或通过人物的某一动作的短暂停留来强调其本身的重要性。Wolf的这种基于运动分析的方法可以根据镜头的结构选择相应数目的关键帧。如果先把图像中的运动对象从背景中取出，再计算对象所在位置的光流，可以取得更好的效果。-6-合成法将镜头中的所有运动转换拼接成一个合成帧作为关键帧。2.2.4基于聚类的方法聚类提取[15]的方法首先要确定一个初始类心，然后根据当前帧与类心的距离来判断是归为该类还是作为新的类心，再将镜头中帧分类后取各类中离类心最近的帧作为关键帧。另外，Zhao[16]提出了一种基于最近特征线(NearestFeatureLine，NFL)的端点检测算法用于选取关键帧。该方法的主要原理是用某些特征点的连线(特征线)近似并代表某个类的所有特征样本轨迹，而这些特征点就是关键帧。2.3从视频流中构造场景或组计算镜头间的相似性（实际是关键帧间的比较），选择合适的聚类算法进行分析。按时间顺序和关键帧的相似程度可分为场景[17]，也可以只按关键帧的相似程度进行分组。3特征提取视频分割成镜头后就要对各个镜头进行特征提取，得到一个尽可能充分反映镜头内容的特征空间，这个特征空间将作为视频聚类和检索的依据。特征提取包括关键帧中的视觉特征和镜头的运动特征的提取。3.1颜色特征颜色是图像最显著的特征，与其它特征相比，颜色特征计算简单、性质稳定，对于旋转、平移、尺度变化都不敏感，表现出很强的鲁棒性。颜色特征包括颜色直方图、主要颜色、平均亮度[3]等。其中利用主要颜色和平均亮度进行图像的相似匹配是很粗略的，但是它们可以作为层次检索方法的粗查，对粗查的结果再利用子块划分的颜色直方图匹配进行进一步的细查。为了能够在大规模图像数据集中进行快速的搜索，Smith和Change[18]等人提出了颜色集的概念：首先将RBG颜色空间转换为视觉上一致空间HSV，然后量化为m个颜色条，颜色集就定义为量化后的颜色空间中颜色的一种选择。由于颜色集特征向量是二叉的，因而可以通过构造二叉树来进行快速的搜索。-7-3.2纹理特征20世纪70年代初Haralick[19]等人提出了纹理特征的共生矩阵表示法，即利用纹理在灰度级的空间相关性，先根据图像像素间的方向和距离构造一个共生矩阵，再从中提出有意义的统计数据作为纹理的特征表示。该方法的缺点是这些统计特征没有和人在视觉上对纹理特征的感知之间建立对应。于是不少人提出了其它的纹理特征度量方法，其中Tamura提出的纹理特征集可以很好地与人类视觉感知相对应，这些特征包括：粗糙度、对比度、方向性、线像度、规则性、粗略度。其中最重要的特征是纹理粗糙度、对比度和方向性。另外，许多研究者开始将小波变换应用于纹理特征表示。Manjunath等人对三种小波变换方法(角、树结构、Galbo)做了比较之后，发现Galbo小波变换最符合人类视觉特征的表达。随着小波理论的建立，GrossMIT[20]等人提出了基于小波的纹理表达。参考文献[21]中有综合性的描述。3.3形状特征形状分析首先需要采用合适的图像分割算法把不同对象从图像中分割出来，再用各种方法进行匹配测量。形状特征表示的一个重要准则是要求对位移、旋转、缩放的不变性，通常形状的表示可以分为基于边界和基于区域两类。它们分别采用傅里叶[21]描述和矩不变量[22]表述特征，另外新的研究方向有弹性变形模板和边界方向直方图。最近的表达方法还有Chamfer匹配[23]，Borgerfos提出的层次Chamfer匹配算法，以及Wallace和Mitchell提出的局部形状分析算法的3D形状表达。3.4运动特征运动特征是视频镜头的重要特征，它反映了视频的时域