一种基于内容视频检索中的镜头分割算法

O 引言
    随着多媒体技术和网络技术的迅速发展，现代计算机技术特别是海量数据存储与传输技术的成熟，视频作为一种主要的媒体类型在人们的生活、教育、娱乐等方面日益成为不可或缺的信息载体。但是由于视频非结构化的数据格式、巨大的数据量以及表现内容的不透明等缺点，使得对视频数据的管理和分析都相当困难。而从大量视频数据中找到自己感兴趣的相关视频片段己成为一种迫切的需求。这一技术就是目前人们普遍关注的基于内容的视频检索技术(CB-VR，Content-Based Video Retrieval)。
    我们知道视频的制作过程首先是进行单个镜头的拍摄，然后，对于内容相近的多个镜头通过各种镜头编辑方式(即镜头转换方式)衔接在一起，组成场景以及视频故事单元。可见镜头是组成视频的基本单元，也是对视频内容进行深入分析的基础。所以从基于内容的角度对视频进行分析时，首先检测镜头的转换边界，即各个不同镜头的连接处，这样就可以将视频分割为一个个的镜头；然后对每个镜头进行代表帧的提取并对内容相近的多个镜头进行聚类，组成更高层次的场景以及视频故事单元，便于对视频的检索。可见镜头边界检测是将视频自动地分割为镜头，以作为基本的索引单元，它是实现基于内容的视频检索的第一步。本文研究的主要工作就是镜头边界检测。
    按照镜头之间的转换也不同，主要分为突变(切变)和渐变，对于镜头边界检测，主要的工作就是找出视频中的突变和渐变变化。

1 相关工作
    镜头边界检测算法主要有直方图法、模板匹配法、基于边缘的方法和基于模型的方法等4种。直方图法使用像素亮度和色彩的统计值，不考虑像素的位置信息，抗噪声能力较强，但有时会漏掉场景切换。模板匹配法严格地区分像素的位置，对噪声、镜头和物体的运动非常敏感，容易导致错误的场景切换检测。基于边缘方法的基本思想是在镜头发生切换时新边缘应远离旧边缘的位置，旧边缘消失的位置也应远离新边缘的位置。上述3种方法都是通过计算帧间差进行镜头边界检测的，对于突变检测可取得较好的效果，但对渐变检测则存在一定的困难，这些方法在很大程度上忽略了渐变切换中帧间结构上的相关性。而基于模型的方法则是利用对镜头编辑的先验知识，对各种镜头切换建立一定的数据模型进行镜头切换的检测，因此对镜头渐变的检测能取得较好的效果。本文的算法就是一种基于模型的方法。

2 镜头分割算法
2．1 切变检测
    本算法根据相邻帧图像变化和不相似性确定切变，相邻帧的变化属于图像检索的范围，本算法中采用了颜色局部累积直方图与纹理相结合的方法。在一般情况下可通过将不相似值与一个阈值进行比较来做出判断，而基于“滑动窗口”的方法可以克服了不相似值不仅与帧间差有关，而且与成像亮度也有关的问题。
    首先定义一个时间长度为2R+l的窗口，使需检测的帧位于窗口正中。然后根据下式计算前后两帧间的差异：

   
    如果差异满足以下条件则认为待检测帧处为切变位置：
    1)窗口中D为最大值；
    2)设窗口中第二大的差异值为D2，有D<k×D2，k为正系数。
    一个图解例子见图1，其中横轴对应帧序列，竖轴对应帧差值，设这里k=3。图中从一R到R对应以帧间差为D的帧的检测窗口，由图可见上述第1个条件满足，第2个条件也满足(注意检测帧问差为D2的帧的检测窗口需向左移，但比较时仍用帧间差为D的检测窗口)，所以认为检测到一个切变。如果考虑窗口右侧外的那些峰，由于第2个条件得不到满足，所以不认为检测到切变。该方法由于利用了在切变位置附近的局部信息，检测效果比全局阈值法有相当大的提高。

    由于“滑动窗口”算法在实际中有可能遇到两个影响效果的问题，一个是漏检问题。例如在利用上面算法中对一些由于摄影机的晃动，造成前景中的物体相对于背景有较大的上下变动，造成了很多漏检。另一个时误检。使用上面的算法对一线电影画面几乎静止，但是由于加字幕、去字幕原因差生小的扰动，就会多检测出切变，出现误检。
    本文采用了基于双重窗口的检测算法。
    基于双重窗口算法进行切变检测的方法流程参见图2，这里对被检测视频流的要求比较简单，只需对原始视频流取平均或对压缩视频流取直流分量就可以得到。为了把闪光的影响除去，从检测视频流中先将闪光位置确定下来，其后在把这些位置从切变检测得到的可能切变位置中除去，就可得到真正的切变位置。

    基于双重窗口算法的主要特点是利用在大窗口中取全局阈值以提取候选切变位置，再利用以候选切变位置为中心的小窗口具体确定真正的切变位置。该算法在小窗口里的检测中结合了双侧和单侧比较检测方法以减少漏检提高查全率。而为了避免单侧检测可能造成的误检，这里采用了将图像分块并比较前后两帧对应块直方图的方法作进一步的确认。
2．2 渐变检测
    在切变检测时已经计算得到帧间差，同时采用了基于双重窗口的切变检测算法，计算了大窗口的帧间差均值用于解决误检问题。在整体实现算法时，采取仅可能统一且高效的方法，因此，在渐变检测中也借助于切变检测中已经计算得到的数据，改进了双重窗口算法，使它也适合于检测渐变。
    具体方法是：在帧间差检测切变的同时来检测渐变。先求得帧间差的大区间均值Ave1，然后根据每帧与此均值的比值决定是否存在一个潜在的渐变(在算法中我们发现取比值系数位0．9即可)，然后开始对于以后连续的大于比值的帧间差求累积和，直到存在两个小于此比值的帧间差出现。然后计算这些帧间差累积和的均值Ave2。在比较这两个均值的大小决定是否真的存在渐变，通过大量实验，发现当它们的比值大于2时一般存在渐变，小于2时一般是由其它原因造成的。
    在整个算法中，并未对渐变镜头进行分类，由于渐变过程中的帧间差总是大于区间内其它镜头内的帧间差。因此仅使用了两个均值用于判断渐变的发生，很好的完成渐变的检测。

3 试验
    视频镜头检测中，常会出现错误的检测或漏检，这些都是不允许的。常用查全率(也称复现率)和准确度以用来表示检索系统的性能。
    按本文的算法对4段视频进行了切变检测，对2段视频进行了渐变的检测，实验结果如下：

4 总结
    主要介绍了视频检索的核心技术——视频镜头的检测，重点提出了基于已经计算得到的帧间差为基础的双重窗口检测算法实现了切变的检测。对于渐变的检测，采取了统一的双阈值检测方法对所有渐变类型进行了检测。通过多次试验，证明了方法的可行性、有效性。