CN1938714A - 用于对视频序列的场景进行语义分段的方法和系统 - Google Patents

Abstract

本发明提供了用于对视频序列中的场景进行语义分段的方法和系统。描述了一种基于镜头的视频内容分析方法和系统，用于提供对逻辑故事单元(LSU)的自动识别。该方法采用矢量量化(VQ)来表示镜头的视觉内容，随后采用镜头聚类算法，以及自动确定合并和分割事件。该方法提供用于组织和索引日益增大的视频数据库的耗时费力处理的自动方式，从而可使用自然查询结构容易地对其进行浏览和搜索。

Description

用于对视频序列的场景进行语义分段的方法和系统

技术领域

本发明涉及一种允许在语义级别上对视频场景进行分段的视频内容分析和分段方法及系统。

背景技术

类似于文本文档，多媒体文档尤其是面向视听的视频内容既具有句法结构又具有语义结构。在后者中，语义内容(通常被称为场景、情景、情节，并且在更细级别上称为事件)的含义是由与镜头和帧(相当于文本文档中的句子、词和字母)的低级内容描述单位相对的视频节目所传递的高级知识(可比作文本文档中的章节和段落的含义)。随着数字时代的到来以及更快速因特网连接的普及，可以按日益增加的速度获得用于专业和家用消费环境的数字视频内容。但是，这些巨大的、通常为非结构化的数字档案使得即使可能访问和搜索到任何期望信息也难以在不耗时费力的情况下就访问和搜索到该信息。因此任何自动化的图像和多媒体处理工具对这些文档进行的分析、编制索引以及检索方面的辅助将是极受欢迎的。在工具除了能在句法级别上进行分析之外还能解释各文档的语义含义的情况下尤为如此。这样的工具将从内容制作及处理到资产重用、合成、以及个性化传输方面极大地帮助内容管理业界。

为了进一步了解背景，下面将描述关于视频结构的分级组织的各种概念，包括对于本文和本领域中使用的例如关于可计算的“逻辑故事单元”和视频编辑技术的定义的总结。

在说明书的最后列出了许多参考文献，在说明书中利用出现在方括号中的数字来对它们加以引用。

通常可基于三级来组织影片结构的分级模型，这三级包括(从低级至高级)镜头级、事件级、以及情景(场景)级。

镜头是单次摄像机操作中拍摄的一段视听数据。大多数多媒体内容分析任务以将整个视频分解为多个基本镜头为开始，这是提取视听内容描述符所必需的。

事件是影片中最小的语义单元。它可以是对话、一幕场景、或通常为一组共享地点和时间的连续镜头。也可能出现如下情况，即多个事件彼此交替以使多个事件并行发生。

情景(或场景)通常被定义为共享公共语义线索的镜头序列，并且可以包含一个或多个事件。

通常地，仅仅使用自动检测到的低级特征而没有任何在先知识地执行情景边界检测，。因此，通常的情况是，检测到的场景边界不能精确地与实际场景的边界相对应。为解决这个问题，研究人员提出了所谓的可计算场景[6]或逻辑故事单元(LSU)[1]，它们揭示了对真实影片情景的最佳逼近。与按其语义内容定义的实际场景相比，LSU是按照特定的时间空间特征(它们是所分析场景的特性)来定义的。

假设在特定影片角色出现于其中的限定时间间隔内发生的事件与特定的位置(称为“布景”)相关联，我们可以说通常场景的特征在于其视觉内容中的全局时间连贯性。于是，从[1]中摘选的对逻辑故事单元(LSU)的定义如下：

“以交叠利用类似视觉内容元素连接镜头的链接为特征的一系列时间连续镜头”。

现在转向影片编辑技术，我们下面说明的技术对说明本发明很有用。参考文献[13]提供了对在视听媒体创作中采用的某些通用惯例和技术的更为详尽的分析。在这篇参考文献中，关注点在于不同类型的镜头和场景，以及它们在影片的不同环境中的各种用途。

镜头可以是事件的一部分，或者可以用作其“描述”[1]。这意味着镜头可以显示正在发生的事件的特定方面(例如对话时的人脸)，或者可以显示随后事件发生的布景。下文中，分别将这两种镜头称作“事件”镜头和“描述”镜头。

通常，在情景开始时出现“描述”镜头，用来引入随后“事件”镜头的布景。例如，在广受欢迎的喜剧影片“诺丁山”中我们多次看到从外面展现书店的镜头，而随后的镜头就详细说明在书店内发生了什么。显然，该情景包括所有镜头(店外的镜头和店内的镜头)，但自动分析可能导致第一个镜头不被包括为书店LSU的一部分。在这种情况下，LSU边界没有准确地与实际场景的边界相对应，而是给出了最佳可能逼近。

就场景而言，通常被分类成两大类[6]，即：

N型：这种场景(标准场景)的特征在于色彩构成、照明状况、以及声音的长时间连贯性；以及

M型：这种场景(剪辑场景)的特征在于视觉内容差别极大(例如，不同地点、时间、照明状况、角色等)并常常具有音频内容的长时间连贯性。

许多后期制作视频节目类型(例如，影片、记录片、连续剧等等)除了它们的句法构成外还具有隐含的情节和语义结构。对这些逻辑视频段的自动检测可使得端用户在宽带连接或任何其他快速网络媒体访问的时代进行交互性和个性化的多媒体传送和消费。由于这些潜在的好处，已经对如下概述的这种自动检测技术进行了研究。

现有技术

近年来，为了搭接低级视听特征(例如，色彩、纹理、动作等)与高级语义含义之间的可感知“语义间隔”，在按语义级对视频数据库(各种类属的视频数据库)进行构建、索引以及检索的领域中已经进行了大量的研究和开发活动。例如在[2]中，提出了一种基于时间约束聚类的方法。通过利用关键帧之间的色彩和像素相关度来测量镜头之间的视觉相似度，然后运用预定的记忆模型来识别故事中的模式，得到了所关注的结果。但是，在这种情况下，对预定间隔(以帧为单位)的选择为情景的持续时间设置了人为限制。

在[3]中描述了另一所关注方法，其中利用链接镜头的概念来检测LSU，使用按照预置帧间隔的多个帧之间的块匹配来检查镜头间的不相似度。

另外，使用音频信息[5]和混合视听信息来检测场景边界[6，7，8]也引起了越来越多的研究兴趣。但是，如何有效地结合音频信息和视觉信息仍然是个难题，这是因为，由于视频类型的多样性和内容制作的风格，导致了在音频信息与视觉信息之间看似存在许多不同的关系。在[6]中，作者使用有限记忆模型来将音频和视频数据分段成各个场景，并且随后应用滑动窗来合并音频和视频场景的结果。在[7]中提出了一种使用音频信息来去除由视觉场景分段所产生的伪边界的音频辅助场景分割技术。其他作者[8]首先关注用于视觉分段的目标跟踪方法，然后基于检测到的视频镜头来分析音频特征，而不论音频数据内容实际如何。

本发明旨在提供除上述技术之外的又一种视频分段技术。

发明内容

根据本发明，提供了一种识别视频序列中的语义相似的镜头的方法，该方法包括以下步骤：a)识别所述视频序列内的镜头，各镜头是时间连续的视频帧序列；b)计算各镜头与每一个其他镜头间的距离值；以及c)依据相应计算出的其间距离值将镜头聚类成组；其中，在步骤c)中被聚类为一组的镜头具有语义相似的内容。

根据本发明的第二方面，提供了一种将视频序列中的视频镜头自动组织成具有相似语义内容的组的方法，该方法包括以下步骤：a)识别所述视频序列中的镜头，各镜头包括连续的视频帧序列；b)使用量化过程生成各镜头的码本表示；c)依据镜头的相应码本表示来计算各镜头与每一个其他镜头间的距离值；以及d)依据相应计算出的其间距离值将镜头聚类成组。

在优选实施例中，介绍了一种新的基于镜头的视频内容分析方法，其目标在于自动识别(LSU)，检测场景变化、相似(重复)场景以及/或者沿着视频序列的事件。该方法包括：镜头的基于矢量量化(VQ)的视觉内容表示、使用自动确定合并及分割的高效镜头聚类算法、镜头类中的时间约束分析、使用场景转换图进行场景检测、镜头的基于VQ的音频内容表示、音频特征变化检测、以及通过启发式规则对音频和视觉分析结果的融合。目标在于使得用于组织和索引日益增大的视频数据库的耗时费力处理自动化，从而可使用接近人类概念的自然查询结构容易地对其进行浏览和搜索。

附图说明

图1(a)是本发明实施例的系统架构的框图；

图1(b)是图1(a)中所示的系统架构的一部分的框图；

图2(a)至(c)是例示矢量量化(VQ)码本生成的图；

图3是例示如何在视频镜头之间生成VQ码本距离的图；

图4是例示作为一个原始镜头图(OSG)的镜头序列的图；

图5是例示镜头类之间的距离的图，称作VQ距离图；

图6是例示镜头类之间的距离的图；

图7是例示用于首次迭代的镜头聚类的示例的图；

图8是例示用新的类C₂′来替代两个类(C₂，C₄)的图；

图9是例示对群集操作进行校验的图；

图10是例示对镜头进行时间约束子聚类的图；

图11是使用场景转换图的示例；

图12是例示对音频数据进行的处理的流程图；

图13是例示使用堆土机距离(EMD)计算的图；

图14是例示检测音频场景变化的EMD的测绘曲线图；

图15是例示用于整合音频和视频场景边界的第一方案的图；

图16是例示用于整合音频和视频场景边界的第二方案的图；并且

图17是例示用于整合音频和视频场景边界的第三方案的图；

具体实施方式

现在将参照附图来描述本发明的实施例。更具体地，首先参照图1(a)和1(b)对本发明实施例所提供的语义视频分析系统的架构和操作处理进行综述。之后，将描述对各步骤的更为详细的考察。

操作综述

本发明实施例的方法和系统旨在对例如由MPEG视频流等提供的视频序列进行操作。但是，应该注意的是，不论编码是否为MPEG，本实施例不涉及对任何编码视频序列进行解码。假设本发明实施例的输入是已解码视频数据的形式。

本实施例中的方法和系统通过被设置为在处理器(例如，个人计算机)的控制下执行的计算机程序来实现。可使得该计算机程序可在便携式存储介质(例如，软盘或光盘)上获得，之后可在计算机上存储并且/或者执行该计算机程序。

在第一步骤1中，首先使用已知的自动方法将整个视频流分解为基本摄像镜头。将视频序列分解为单个镜头的技术是本领域中公知的，例如在L-Q.Xu，J.Zhu和F.W.M. Stentiford的“Video summarisation andsemantic editing tools”，Storage and Retrieval for Media Databases，Proc.ofSPIE，Vol.4315，San Jose，USA，21-26 Jan.2001中所描述的技术。通过引用将该文献中的内容并入于此。在后续的步骤3中，对于各基本镜头，利用某些特征性“标记”提取一个或更多个关键帧来代表该镜头的视觉内容。在这种情况下，由在后续的步骤7中生成的矢量量化(VQ)码本来提供所述标记。VQ码本是从低级视觉特征(例如色彩、纹理等)中导出的。

镜头关键帧的选择在本领域中是公知的，如在Y.Zhuang，Y.Rui，T.Huang，S.Mehrotra的“Adaptive key frame extraction using unsupervisedclustering”，Proc.of IEEE Int’l Conf.on Image Processing，pp.866-870，Chicago，October 1998中所描述的。矢量量化码本技术在本领域中也是公知的，正如R.M.Gray在“Vector quantization”，IEEE ASSP Magazine，Vol.1，pp.4-29，April 1984中所描述的。

在对视频序列进行上述分解的同时，还可以定义音频镜头。音频镜头的长度通常被选择为与视觉镜头的长度相对应，但是如果视觉镜头太短，则音频镜头的长度可以是几个相邻视觉镜头的串接。在初始阶段9，各音频镜头的特征在于短时间的频谱特性，例如Mel频率倒谱系数(MFCC)。然后，如稍后要描述的，在后续的阶段11基于在整个镜头中聚集的短时间音频特性计算可包括VQ码本的音频镜头的内容“标记”。

返回到视频分解处理，在步骤5中对关键帧进行表征之后，在后续的步骤7中基于VQ码本执行对镜头的视觉聚类。这里，目标是基于视频流的所有镜头的视觉内容标记(即，VQ码本)的相似度，将视频流的所有镜头全局性分组成为大量所谓的类。最初，各类包含单个镜头。使用采用完美定义的距离度量(well-defined distance metric)的聚类算法，该算法在两个类相似(根据它们之间的最小距离)到足以允许合并的情况下还具有纠错能力。这将得到共享相似视觉表观(根据它们的“外观和感觉”)且在无需在先知晓内容或人为设置的情况下自动确定的最终类集合。将视觉类输出到视听(A/V)框架(profile)分析阶段15。

在音频分解处理中，在阶段13使用与应用于视频流的矢量量化技术类似的矢量量化技术来执行对伴音频流的分段。如稍后将更详细概述的，使用公知的堆土机距离(EMD)度量来计算连续镜头的音频内容标记间的不相似度。EMD度量给出了音频内容变化在时域上的全局视图。然后应用基于对距离度量的统计分析的阈值操作来检测高于特定阈值的局部峰值。落在两个峰值内的镜头被识别为共享相似音频属性，并由此被安排为分段在一起。

现在参照图1(b)，图1(b)是A/V框架分析阶段15的详细框图，对接收到的视频类执行时间约束类分析17。在先前的阶段7中，类中的每个镜头都被标记有时间。为了区别在节目中不同时间/阶段发生的视觉上相似的场景(例如，在诸如特定酒吧、公寓等的相似物理环境中捕捉到的场景)，时间约束类分析阶段17被设置为使用滑动窗技术来执行检查场景的时域连贯性的任务。于是，生成了其中镜头不仅在表观上彼此相似而且在时间上也相邻的大量类。还生成了描述这些类之间的时间关系的图形表示。

在后续步骤17中，执行所谓的基于场景转换图(STG)的分析。在给出上述镜头类集合的条件下，使用场景转换图(STG)的概念，执行图形分析以通过将较弱的类A与具有相同的语义标记的第二类B关联起来而导出最终的语义场景。虽然类A在视觉上可能与类B不同，但它在时间上夹在属于B的镜头之间。然后基于STG的分析步骤19检测语义不同的视频段的转换图中的“切边”。

基于STG的分析步骤19的输出提供场景级而不仅仅是镜头级的关于视频序列的语义结构的有用信息，并可按照若干方式加以使用。具体地，后续的自动场景变化检测步骤21提供了朝向更好语义理解诸如影片的视频序列的第一步骤，这是因为将影片分解为多个场景有助于创建内容概要，这反过来也可被用来使得能够在影片内进行非线性导航。此外，确定各场景内的视觉结构有助于可视化影片概览中的各场景的处理。

即使没有后续的时间约束分析阶段17，视觉聚类阶段7本身也可提供有用的信息。这是因为视觉类阶段7将具有相似语义内容的所有镜头一并分组到同一类中。然后这可被用来方便地向用户展示与该语义内容相关的所有镜头。例如，用户可能会要求观看在特定场所拍摄的视频序列中的每个镜头。然后，为了识别及随后显示给用户，可以采用可视聚类来按照自动方式将在所述场所拍摄的所有镜头聚类在一起。

最后，在又一阶段23(其中，提供了视频和音频分段)，可执行对视频和音频结果的融合。这个阶段23以上述两个分组步骤的结果为输入，并基于一套启发式规则生成对视听场景变化的三种不同解释。

现在将更详细地描述在上述步骤中涉及的处理。

视觉信息处理

首先具体参照图2至11，将描述处理视频信息中涉及的步骤。虽然对于理解本发明并非必需，但仍假设熟知技术的读者了解用于执行摄像分解检测阶段1和关键帧检测阶段3的公知技术。不论何种情况，都在上面提及的参考文献中给出了详尽描述。

VQ码本和VQ间失真度量

在关键帧表征阶段5，接收与各镜头相对应的关键帧并对其进行分析。参照图2(a)，对于每个镜头，将所选关键帧解码为LUV格式的静态352×288图像。接下来，以2为因子对各关键帧进行子采样，并将图像细分为4×4像素的块。由于经子采样的图像具有176×144的显示格式，因此可以理解将会出现1584个4×4像素块。这些像素块用作对用于生成合适码本(其用于表征该特定关键帧)的矢量量化器的输入矢量(或“训练集”)。

矢量量化(下文中称为VQ)在视频处理领域是众所周知的。在上述R.M.Gray在IEEE ASSP期刊上的参考文献中对VQ的背景和使用提供了完整的介绍。简言之，VQ是一种基于块编码原理的有损数据压缩方法。它是一种用作逼近器的固定对固定长度算法。参照图2(b)，示出了一维矢量量化器的示例。这里，每个小于-2的数被近似为-3，介于-2与0之间的每个数被近似为-1，每个介于0与2之间的数被近似为+1，等等。近似值由两位唯一地表示。这类矢量量化器被称为比率为每维2位的1维2位矢量量化器。参照图2(c)，示出了两维矢量量化器的示例。可见每对落入特定区域中的数被近似为由圆25表示的单个值。在这种情况下，有16个区域和16个圆，其中每一个都可由4位唯一地表示。因此，图2(c)代表比率为每维2位的2维4位矢量量化器。在图2(b)和2(c)的示例中，圆被称为码字，区域被称为编码区域。所有码矢的集合被称为码本。

在当前的分析技术中，VQ处理包含用预定块(其是从码本矢量中选出的)替代各个输入图像块，使得失真测量结果最小化。通过这种方式，仅仅使用属于码本的块就可以重构整个图像。

通常来说，图像由一些不同大小的单色区域来表征，意味着隶属相同块的像素共享某些色彩属性，使得在一个块内的相关性可能非常高。然而，块尺寸越大，块内像素间可能存在的相关性就越小。此外，在各图像中，始终存在与颜色分量的特定组合相对应主导色。这意味着，如果我们在三维色彩空间中表示像素，则特定区域将更密集，这表示在颜色分量之间也存在很强的相关性。VQ自然地利用了关于要被量化的矢量的分量之间的相关性的信息——如果在标量模式下对单一分量进行量化，则将失去该信息。

对于属于特定4×4块的所有像素，各像素的三个LUV分量被从左上至右下串接起来，形成48维的矢量，如图2所示。各48维矢量构成对VQ码本生成处理的一个输入。

VQ码本生成

要针对各视觉镜头生成的码本包含C个码字，每个码字都是D维。下文中，我们称该VQ码本为与其相关的关键帧的标记(因此为视觉镜头的标记)。该码本包含以下元素：

i)C个码字，它们分别为最终码本中各类的质心值。如图2所示，各48维矢量被应用到矢量量化器中，并且根据该矢量所在的区域，随后将质心值分配给那个矢量。如下获得C个码字：

${\left({\mathrm{\μ}}_{1,...,}{\mathrm{\μ}}_D\right)}_c=\frac{{\mathrm{\Σ}}_{i=1}^{M_c}{\left(p_{1,...,}^i{p}_D^i\right)}_c}{M_c}$

其中C代表在码本中的码字(或类)数，例如C＝100，而c代表第c个码字。M_c是落入码字c的分区中的4×4的块的数量，pⁱ _k是第i个D维矢量的第k个分量，并且D＝48。第i个D维矢量被记为pⁱ ₁，...，pⁱ _D。

ii)按照下式获得码字的方差：

${\left({\mathrm{\σ}}_{1,...,}^2{\mathrm{\σ}}_D^2\right)}_c=\frac{{\mathrm{\Σ}}_{i=1}^{M_c}[{({\mathrm{\μ}}_1-p_1^i)}^2,...,{({\mathrm{\μ}}_D-p_D^i)}^2{]}_c}{M_c}.$

iii)码字的权重，其考虑与各码字c相关联的4×4的块的数量M_c。通常，使用介于0与1之间的归一化的权重，即

这里，分母是训练矢量的总数。如上所述，M_c是落入第c个类中的矢量数。

需要注意，丢掉没有或仅有一个相关联块的所有码字。

VQ码本距离度量(VQCDM)

如上所述，一旦获得各视频镜头的码本，将使用采用完美定义的距离度量的聚类算法。具体地，在本实施例中，使用VQ码本距离度量(VQCDM)。参照图3，可在两个步骤中计算任意两个镜头之间的VQCDM。

首先，将第一镜头中的各码本矢量y_i∈{y₁，...，y_N}与第二镜头中的各码本矢量z_j∈{z₁...，Z_N}相比较，以根据下式来计算距离矩阵d_i，j＝d(y_i，z_i)：对于i＝1，...，N，且j＝1，...，N，

$d_{i,j=\frac{1}{D}\underset{h=1}{\overset{D}{\mathrm{\Σ}}}[\mathrm{\α}{({\mathrm{\μ}}_{\mathrm{ih}}-{\mathrm{\μ}}_{\mathrm{jh}})}^2+(1-\α){({\mathrm{\σ}}_{\mathrm{ih}}-{\mathrm{\σ}}_{\mathrm{jh}})}^2]}$

其中D是码本矢量的维度，i表示在码本Y(关于镜头Y)中的第i个码字，j表示在码本Z(关于镜头Z)中的第j个码字。α是是权重因子，其中0＜α＜1.0。正如将要理解的，这生成了表示针对各可能组合的各个码本矢量之间的相对距离的矩阵集合。

第二，在给出上式结果的条件下，在两个给定镜头Y与Z之间的VQCDM被定义为：

由于i是固定的，所以对于所有的j值，我们寻找第一项的最大值和第二项的最小值。

注意，进行比较的两个码本可能具有不同的有效尺寸，也就是说，第一个镜头的码本的尺寸为N并且第二个镜头的码本的尺寸为M，其中M≠N。如前所述的，这并非不常见，因为当一些码本矢量不具有相关联块时简单地丢掉它们以减小码本的尺寸。

聚类过程

在初始分段为单个镜头之后，根据视觉相似性对视频镜头进行分组给出了对视频序列的下一分级描述。为实现这种分组，在接下来的步骤7中，我们在聚类算法中使用基于VQ的镜头级视觉内容描述以及上述的VQCDM。注意，这种方案既与视频的类型无关，也无需具体了解下层故事结构。

聚类处理假设沿着该序列出现重复(或者至少相似的)镜头结构。这对于包括题材影片的广类型范围内的高度结构化的节目(它们可以是喜剧和/或舞台剧、情景喜剧和卡通片)来说是合理的假设。然而例如当导演使用连续快速的镜头来突出悬疑时刻或仅仅使用一系列镜头来展开影片的情节时，故事结构也可能被部分丢失。在这种情况下，然而，由于属于相同场景的镜头通常至少共享该场景的相似的色彩构成或者环境照明状况，所以如果处理N个场景，则基于VQCDM的聚类算法能提供良好的性能。聚类过程被为两部分：无时间约束过程和时间约束过程。

无时间约束聚类过程

首先，我们假定有M个类C_i...C_M，每一个代表相应镜头S_i...S_M。参照图4，以简单的图来表示这种状况，该图被称为原始镜头图(OSG)，其中节点对应于类(或镜头)，边/箭头表示类间的转换。

如前所述，沿着时间轴对所有镜头组合计算VCDM，以便在整个视频序列中穷尽探察视觉相似性。在各步骤处，将类与代表所述类与所有其他类的距离的VQCDM一起在称作VQ距离图的更新图上表示为节点。图5中例示了示例VQ距离图。参照图5，VQ距离图包含4个类C_1...C₄，其中的一些包括一个以上的镜头。例如，类C1包括两个镜头。

由于一对类的VQCDM是对称的，所以为了便于说明，图6针对各对仅示出一个距离值。

在每次迭代中，上述的过程旨在将基准类R与其视觉上最相似的测试类T合并，其中在最小VQCDM的意义上R＜T，由此在时间线上形成新的单个类R’替代类R的位置。根据这种合并操作，属于基准类R和测试类T的所有镜头都成为属于新类R’的镜头。此外，更新向R和T/从R和T开始的所有转换，以便保持故事的正确时间流。图7示出了第一次合并操作的示例(其中各类只包括一个镜头)，合并发生在类C’₂(即，基准类R)与C₄(即，测试类T)之间。

对于所得组合的类R’，需要新的VQ码本来代表或表征其视觉内容。采用与前述相同的处理来生成码本，不过存在如下差别：属于R’的所有镜头的关键帧均将被用于生成码本。最后，计算类R’与所有其他类之间的VQCDM以用于下一步骤。

对类误差的在线统计分析

在开始下一聚类迭代之前，执行检查来确定上述聚类操作实际上是否应该已被执行。具体地，当形成新类R’时，相对于原始镜头图(OSG)，在镜头图中引入了VQ误差。应当注意的是，尽管针对特定镜头生成的VQ码本完全专用于该镜头，但是当类包含一个以上的镜头时，代表类中所有镜头的内容的经更新VQ码本通常要比针对任何特定镜头的VQ码本的专用性都要弱。这意味着，对于每个镜头，最佳VQ码本是在首次合并步骤之前给出的VQ码本。从那时起，在后续聚类迭代中，对于给定的类，VQ码本中的镜头表示误差可能会增多。在图8中，我们示出了在首次合并类C₂和C₄之后相对于OSG误差是如何产生的。

可容易地使用VQCDM来计算以新的类VQ码本来表示镜头所造成的误差。在每次迭代后，通过对类R’的VQ与属于R’的所有镜头的OSGVQ之间的距离进行求和来给出误差。在我们的示例中，在首次合并步骤之后，误差由下式给出：

VQ_err(first_step)＝VQ_Dist(C₂，C₂′)+VQ_Dist(C₄，C₂′)

＝VQ_Dist(S₂，C₂′)+VQ_Dist(S₄，C₂′)

在一般情况下，误差由下式给出，

$\mathrm{VQ}\_\mathrm{err}\left(\mathrm{step}\right)=\underset{S_i\∈R^{\′}}{\mathrm{\Σ}}\mathrm{VQ}\_\mathrm{Dist}\left(S_{i,}{R}^{\′}\right)$

其中R’是新形成的类，对所有相关联的镜头来说S_i∈R’。

由于我们在将相似的镜头分为类，所以随着类尺寸的增加，特定类的VQ码本有在代表其各个镜头的视觉内容方面丢失专用性和准确性的危险。为了防止这种退化过程，在每次迭代之后，对最新合并步骤中产生的误差进行统计分析，以评估新的VQ码本在代表类中的镜头方面如何普适，并且因此确定该合并步骤应予保留还是使其无效。

为此，在迭代步骤k中，我们计算了如下的所引入误差变化(Delta_VQ_err)：

Delta_VQ_err(k)＝[VQ_err(k)-VQ_err(k-1)]

另外，计算先前迭代中的平均值(Mean(Delta_VQ_err))以及标准偏差(Std(Delta_VQ_err))。此外，还如下计算相对于前一合并步骤的平均值和标准偏差的所有差异：

Mean(Delta_VQ_err(k))-Mean(Delta_VQ_err(k-1))，

Std(Delta_VQ_err(k))-Std(Delta_VQ_err(k-1))

然后，通过监视这些值，并对它们中的一个或更多个应用阈值，可以评估新形成的类相对于原始镜头图是否引入了太多的误差，并因此可使合并步骤无效。图9中表示了该处理。如果情况不是如此(即，不满足阈值)，则不采取任何行为，且执行下一聚类迭代。然而，如果情况如此，则进行前一聚类操作的逆操作(即，将合并后的类分为该聚类操作之前存在的镜头/类)。此外，基准类被锁定为不参与以后的聚类处理，并且利用最小的VQCDM选择针对下一类迭代的新的基准和测试类(它们当前被分类为非锁定)。重复该迭代过程，直到没有非锁定的类可用于合并。

再次注意，随着合并后类尺寸的增加，视觉上不相似的镜头可能进入类，更加恶化VQ码本的代表性。尽管上述的分析和后续的逆聚类操作可用于防止这种退化过程，但是当类的尺寸超过特定阈值(例如，12至15个镜头)时将其锁定也是有用的。也可使用另外的类锁定准则。

时间约束分析

因为上述的无时间约束分析方法仅仅基于镜头的视觉内容而不考虑环境的定时地将镜头分组到相同的类，所以该方法对于诸如影片的许多类型的视频节目都非常有用。这种方法没有为场景的持续时间设定在先时间限制(这是例如[2]中的一个问题)，此外该方法可被用于特定的检索目的，例如用户定义的查询，譬如搜索重播。例如，当观看影片“诺丁山”时，观看者可能希望按照出现的顺序来观看设定在“书店”周围的所有场景。如果将所有相似镜头都分组到同一类(利用无时间约束方法这是可能实现的)，这就很简单了。

然而，为了将一个逻辑故事单元与其他逻辑故事单元分开，需要进一步的分析来考虑分组到各类中的镜头的时间局部性。换言之，应该对每个类执行时间约束分析。时间约束分析的目的在于根据时间局部性准则将类分为一个或更多个时间连贯的子类(参见图10)。

时间约束分裂准则如下：

${\∀x}_h\∈C_{i,j},\∃x_k\∈C_{i,j}:|h-\mathrm{k|\≤TW}$

其中TW是表示用户所选时间窗的持续时间(按照镜头数)的时间窗，C_i是第i个类，C_i，j是C_i的一个时间局限的子类，x₁，x₂，...，x_n是属于C_i，j的镜头。简单来说，沿着时间线移动时落入时间窗TW内的每对镜头属于同一类。当仅有一个镜头落入TW内时，在TW的端部有一个裂口(split)。参照图10，可以看到，当TW自左向右移动移动时，建立了包括S1和S3(S5紧随其后)的类。正如所示，存在其中TW仅包括S5的点，因此在TW的端部进行一次分裂。第一子类被标记为C_i1，0。新的TW开始，并且按照同样的方式，镜头S9、S10(在时间线上未示出)以及S11被一起分组到新的类C_i，1。

显然，如果所有镜头都包含在同一个时间窗TW中，则类本身就成为时间局限的子类。这个条件可被应用于各类中的镜头，以根据类中所包含的镜头代表的场景将类分为一个或更多个时间局限的子类。在各子聚类操作中保留表示子类之间的时间流的转换信息，使得获得包括大量时间局限的子类以及子类之间的转换/边的有向图。各子类包含视觉上相似且时间上相邻的镜头，各转换代表情节的时间演变。如前所述，图10中示出了将类分为时间局限子类的示例，在图11中示出了如此获得的有向图的示例。在下一阶段19，对该有向图进行场景转换图(STG)分析，以自动地提取其结构，从而说明隐含视频节目的语义结构和时间流。

场景转换图(STG)

如前所述，逻辑故事单元(LSU)被看作是通过公共语义视觉内容来统一的相关镜头的有序集合。在给定先前视觉相似度和时间分析步骤的输出的条件下，我们在这一节展示最初在[16]中提出的STG概念如何被有效地用于寻找LSU的边，以提供对视频节目中的故事结构的紧凑表示。

正如已经提到的，来自前一处理步骤的输出是包括大量节点和节点之间的转换/边的所谓有向图。各节点可包含一些视觉上相似且时间上相邻的镜头，各转换代表情节的时间演变。在下面的描述中，我们首先概述STG的思想，然后讨论如何在没有在先了解视频节目的语义结构和时间流的情况下自动地提取STG的结构。

STG的定义如下——有向图G，这里G＝(V，E，F)，其中V＝{V_i}为节点集，E是边(或转换)集，F是将镜头集{S_i}划分为作为V的成员的节点V₁，V₂...等的映射。将各V_i中的镜头聚类为如在使用视觉VQCDM和时间约束分析之前一样。这意味着各V_i是时间局限的子类。

给定一对节点(U，W)∈V，如果在m＝l+1的情况下存在S₁∈U且S_m∈W，则边/转换(U→W)是E的成员。这意味着如果存在在由节点W代表的镜头紧前的由节点U代表的镜头，则(U→W)是E的成员。一个示例状况可能是两个角色之间的对话，摄像机镜头在他们之间交替。在这种情况下，图G由两个节点V₁和V₂组成，且有向边(V₁→V₂)和(V₂→V₁)是E的成员。这里，我们将各有向图G与无向图G’＝(V，E’)相关联。G和G’具有相同的节点集，并且对于各边e∈G，存在具有相同端的对应边e∈G’。如接下来要描述的，在给定了这些预备定义的条件下，然后可以使用STG来检测LSU。

用于LSU检测的STG切边

一种重要类型的两个节点间转换被称为“切边”。在无向图中，转换被看作是“切边”，如果当转换被去除时，该图得到两个不连通的图。G，中的切边集将G’分为n个不相交的子图G’₁，G’₂，...，G’_n，其中各G’_i＝(V_i，E’_i)。此外，切边对应地对G进行相同的划分，从而有n个不相交的STG，G₁，G₂，...，G_n，其中G_i＝(V_i，E_i，F)。从G的映射F在划分图G之后在各G_i中被保留。因此如果对应边e∈G’是G’的切边，则我们称有向边e为G中的切边，。

如图11所示，在去除切边后的各连通子图将代表LSU，而STG中所有切边的集合代表从一个LSU到下一个的所有转换，由此反映了视频流的自然演变，并允许对故事结构进行分级组织。通过使用从时间约束分析输出的有向图作为STG并且检测其中的切边，可在视频序列中检测LSU及其间的转换。正如前面所讨论的，这些LSU(或场景)在语义上比镜头更高级地代表视频序列，并且具有多种用途。

音频信号处理

现在将具体参照图12至17来描述处理音频信息中所涉及的步骤，这些步骤可与上述的视频处理步骤并行执行。

当前对于语义视频分析的方法相比相关联的音频暗示，对于视觉暗示给予了更多的关注。然而，音频数据中包含了大量信息，这些信息通常比视觉部分的信息更为重要或者作为其补充。在诸如题材影片的许多视频节目中，导演通常使用创造性的剪辑技术，其中短但视觉上不同的连续镜头共享相同的音频特性(通常是一段音乐旋律)。因此在这种意义下，这些镜头属于同一语义主题。在这种情况下，可以说音频暗示实际上在对视频数据进行解析和分段时起到主要的作用。

通常，结合音频和视觉数据会提供更可靠和准确的场景分析结果。

在这里描述的本发明实施例中，我们提供了两个单独的视觉和音频数据处理链/分支，并由此产生单独的视觉和音频分析结果，然后启发式地结合这些分析结果(如稍后描述)以提供对节目结构的更具逻辑和分级的描述。通常，音频数据被认为相对于视觉处理结果起到支持的作用，视觉部分仍然是检测实际场景变化的主要基准。然而，在一些情况中，音频分段可能更为重要。在这种情况下，视频分段支持音频分段。在下文中，我们描述了使用一组低级音频特征和时间分段方法来对音频数据的语义内容进行表征。

以经分段的音频镜头(它们可以被拍摄为具有在初始步骤1中生成的对应视觉镜头的长度)开始，可根据两个连续镜头之间的距离测量结果来识别音频场景变化。对于各音频镜头，我们基于频谱特征计算“标记”(其是以与先前对于视觉标记描述的方法类似的方式从VQ码本中导出的)。在这种情况下，频谱特征以Mel频率倒谱系数(MFCC)的形式给出。然后，采用被称为堆土机距离(EMD)的距离测量方法，来计算音频镜头之间的距离，或者计算它们的“标记”。最后，采用简单的阈值方法来检测音频场景变化并分离音频数据的连贯分段。

图12和13分别代表用于音频场景变化检测的音频镜头标记提取步骤和对连续音频镜头的距离计算步骤。下面给出了对各阶段的进一步解释。

音频镜头数据制备

如上所述，音频流首先被分为任意的段。在本实施例中，我们将音频流分为与已被分段的视频镜头相对应的段。由于在视频序列中可能出现的渐变效应(例如渐隐和溶解)，一些视频镜头在时间上可能非常短。为了避免与这种效应相关联的问题，如果镜头短于特定持续时间(例如，2秒)，则在处理该镜头前就将其与前一镜头合并。按照这种方式，我们试图避免分析较短的无声镜头，并且确保只对包括相对大量的音频信息的段执行分析。

根据对应的视频镜头段来处理音频数据的优点在于使得更加容易结合音频和视觉数据分析的结果。此外，在音频处理部分，无需关注音频数据内容，而是关注特征集值的变化。在此方面，处理的目标不是为了分类(即确定音频是否为音乐、语音、无声、噪声等等)，而是为了识别音频特性的变化(其可能与音频属性的重大变化隐含的场景变化或者故事演变中的重要事件相对应)。

短时频谱分析

在将音频流分为基于镜头的段之后，在下一步骤9中，对各音频镜头执行短时频谱分析以生成表征镜头的特征矢量。这是通过首先将音频镜头划分为多个音频帧来实现的，各音频帧是局部稳定的并且持续几十毫秒。然后，针对各音频帧，我们进行频谱分析，该频谱分析包括提取19 Mel频率倒谱系数(MFCC)加上一个声音能量分量。正如本领域技术人员所理解的，MFCC被广泛用于在语音识别应用中，另外还被用于对音乐的建模中[10]。

在我们的实施例中，优选地，以22.050KHz对音频数据进行采样，各采样由16比特来表示。然后将采样划分为20ms长并以Hamming窗加权的多个音频帧；滑动窗交叠10ms，从而每10ms获得输出特征矢量或19MFCC的集合。

对音频镜头的矢量量化

在后续的步骤11中，采用如此获得的MFCC来导出各音频镜头的标记。为了导出各音频镜头的标记，我们使用与先前关于视觉数据分析描述的矢量量化技术相同的矢量量化技术。

更具体地，在频谱分析之后，整个音频镜头由一序列19维实矢量(MFCC)(其代表镜头的10ms音频帧)来表示。因此，例如，如果音频镜头持续2.3秒，则将有230个矢量可用于码本生成处理。注意，由于高能量的音频帧对人耳具有更大的影响，所以当我们计算帧级别特征时，采用这些MFCC的加权形式。加权因子和帧的能量成正比。该处理在镜头中有许多无声帧的时候尤为有用，这是因为无声帧中的频率特征近似为随机。通过使用基于能量的加权，消除了有害效应。使用帧能量值和对音频文件(剪辑99％重合)计算出的最高能的一秒剪辑的值的比率，获得各音频帧的相对权重。

一旦选择了码本的维数K，就通过将K个种子(它们将形成类的中心)随机定位到包含所有频谱音频帧的19维超立方体中而开始用于VQ码本生成的算法。各帧根据其频谱坐标(即，其MFCC值)而定位在该超立方体中。VQ结构由其单元的重心(质心)的最终位置来定义，质心与描述音频镜头的内容的特征的统计密度直接相关。

测量音频镜头标记之间的距离

针对各音频镜头生成的码本由此包含C个码字，各码字具有D维。该VQ码本成为与其相关的音频镜头的“标记”，该码本包含以下信息。i)C个码字，它们分别为最终码本中各类的质心，利用以下公式获得这些码字：

${\left({\mathrm{\&mu;}}_{1,...,}{\mathrm{\&mu;}}_D\right)}_c=\frac{{\mathrm{\&Sigma;}}_{\text{i=1}}^{M_c}{\left(f_{1,...,}^i{f}_D^i\right)}_c<mrow>\; </mrow>}{M_c}$

其中M_c是与码字c相关联的镜头中的音频帧数，fⁱ _d是音频帧i的第d个MFCC；

ii)码字的方差，其由下式获得：

${\left({\mathrm{\&sigma;}}_{1,...,}{\mathrm{\&sigma;}}_D^2\right)}_c=\frac{{\mathrm{\&Sigma;}}_{\text{i=1}}^{M_c}[{({\mathrm{\&mu;}}_1-f_1^i)}^2,...,{({\mathrm{\&mu;}}_D-f_D^i)}^2{]}_c}{M_c}$

iii)码字的权重，其考虑了与各码字c相关联的音频帧数M_c。通常，使用介于0与1之间的归一化权重，即

注意，没有相关联的音频帧的任何码字都是可忽略的。另外，如果只有一帧与码字相关联，则其对应类将具有零方差，并根据下面讨论的距离度量而距每个其他码字具有无穷远距离。因此丢掉这些码字。

堆土机距离(EMD)

一旦得到各音频镜头的特征标记或VQ码本，我们使用公知的堆土机距离(EMD)来测量任意两个音频镜头之间的非相似度。这种距离度量由Rubner，Tomasi和Guibas在“The Earth Mover’s Distance as a Metricfor Image Retrival”，Technical Report STAN-CS-TN-98-86，CS Department，Stanford University，September 1998中描述为一种改进从大型图像数据库进行基于内容的图像检索的度量，并且在[10]中用于比较音频数据库中的歌曲来自动创建音频播放列表。在[18]和[19]中可找到基于计算机的实现细节。

简言之，EMD是一种评价两个标记之间的不相似度的方法。直观地说，给定两个标记，一个标记可被看作空间中适当散布的大量土，并且另一个标记是同一空间中的洞的集合。EMD提供一种将土填到洞中所需的最小工作量的测量。这里，单位工作对应于将单位土运送单位地面距离。

在各对连续音频镜头之间应用EMD来确定其间的距离，并且存储结果以用于下一阶段。图13中示出了音频镜头之间的EMD计算。可以看到，可关于时间轴来绘制EMD值的图形表示。这被称为音频镜头距离曲线。

用于音频场景检测的分段过程。

计算了连续音频镜头对之间的EMD值之后，采用所得的距离测量结果来将音频流分段为多个场景。此处的目标是检测空间相近(在频谱属性意义上的空间相近)且时间相邻的音频镜头的边界，以识别可能的音频场景变化。

通常，音频场景变化可能发生在声音中大多数主导音频特征改变的时候[9]。这可发生新的视觉场景正好开始之前(或正好开始之后)。然而，这也可表示故事中的重要事件，甚至在场景中间的重要事件。例如，声音中的主导音频特征可以改变以表示两个主角之间的接吻，或者用以在某种恐怖事情发生之前增加悬念。

由于EMD提供了一种两个相邻音频镜头之间的标记的距离度量，所以我们通常可以说，如果EMD较大，则这两个连续的音频镜头在它们与低级描述特征的定义集或标记相关的隐含属性方面有很大不同。相反，如果EMD值较小，音频在两个邻近镜头之间不会有可感知的变化。在步骤13中(参见图1(a))，执行一种统计分析来计算所有连续音频镜头对的距离的平均值μ和标准偏差σ。然后采用乘以了标准偏差σ的经验选取阈值来检测音频镜头距离曲线中的峰值并且来将音频镜头分为不同段，如图14所示。因此，通过分析EMD结果中的峰值，可检测到音频场景变化，并可实现音频场景分段。

音频辅助的视频场景分级分段

将本实施例中的最后阶段23设置用于整合经分段的音频场景信息与经分段的视频场景信息。

尽管结合使用视觉和音频分析结果仍然是一个具有挑战性的问题，但是音频在视频分段中的重要性已被许多研究人员所认识到，并近期出现在参考文献[20]中。这里，我们说明如何将根据先前的基于镜头的分析所分别导出的音频和视觉分析结果结合起来，以实现最终的对视频结构的高级描述。

与只使用音频暗示来删除视觉分析中错误检测到的场景边界的许多方法[7]不同，这里我们首先将视频流分段为视觉和音频镜头(在先前章节中进行了描述)，然后在单独的分支中执行各种处理和分析步骤之后，我们将两组结果结合起来以导出最终的场景边界。针对音频和视觉处理两者的基于镜头的分析方法避免了许多影响本领域的提出联合视听分析的一些解决方案的对准问题，并提供了一种使结果同步的简单方法。

下面，我们提出启发式规则以指导如何结合视听分析结果。基本上，对于检测到的各视觉场景变化，在与所述视觉变化相关联的镜头的相邻镜头中搜索最可能的音频场景变化。同样地，对于检测到的各音频场景变化，在与所述音频变化相关联的镜头的相邻镜头中搜索最可能的视频场景变化。当我们通常将视觉输出作为检测真实场景变化的主要基准时，采用音频输出来支持、或补充视觉处理结果。然后我们能够为不同类型的视听边界结合分配不同的分级含义。

视听结果结合规则

我们识别出如下所述的三种可能的场景分段边界情形。

i)检测到视频场景边界，但是不存在具有相同时间标记的音频场景边界。

这是一种其中故事改变地点和/或时间但是音频线实际上没有改变的常见情形。例如，这是在“说话”情形期间视觉场景改变了但是基础的音频场景仍然还是“说话”时的情况。有时这也可能发生在当一序列音频镜头具有相同隐含语义含义的时候。例如，可能提供伴有相同的歌曲或音轨的一系列不同视频镜头，例如在对长时期的事件(例如一次旅行)进行快速描述的情况下，或者在描述按顺序发生但共享一完美定义的语义含义的特定序列事件(例如季节的更替)的情况下。

ii)检测到音频场景边界，但是不存在具有相同时间标记的视频场景边界。

这通常发生在当作者希望强调序列中的一个重要时刻的时候，或者，更简单地，发生在当场景的情绪变为悲伤/喜悦/浪漫/恐怖/惊吓时刻的时候。例如，在“诺丁山”影片中，当在博物馆处向朱丽亚·罗伯茨扮演的角色求婚时的场景的中间有音频场景变化。

iii)检测到视频场景边界，并且在相同时间标记处存在音频场景边界：

在假定音频和视觉特征同时改变的条件下，这是检测的最简单的情况。这可能是音频变化正好在对应视觉场景变化之前(作为引子)或者正好在其之后。当定义要使用的规则时考虑这些情形。如前所述，检测到的场景边界并不总是与场景的实际开始和/或结束相对应，这是为什么LSU被认为是对真实电影情景的最佳逼近的原因之一。然而，在这种情况下，由于音频和视觉特征两者同时改变，所以我们可以较为肯定检测到的LSU边界也是真实场景转折(break)。

在给出不同场景边界情形之后，我们现在着眼于发现情节中的适当结构来定义多个规则。

在下面的描述中，我们使用VC(s_i)和AC(s_i)来分别表示在镜头i中发生的视觉变化和音频变化。

逻辑故事单元(LSU)边界

因为镜头序列共享镜头任一侧上的相似视觉内容，所以如果发生视觉变化但是没有检测到音频变化，则根据上述定义其可被看作为“LSU边界”。

规则i)

当且仅当如下条件下，在镜头i处检测到LSU边界：

VC(s_i)AND(NOT((AC(s_i-N))OR(AC(s_i-N+1))OR...OR(AC(s_i+N-1))OR(AC(s_i+N))))

其中N是在各VC周围的时间模糊窗。N是图15中示出的示例中的一个镜头。

LSU内的音频模式暗示

如果发生音频变化但是之后没有视觉变化，则根据LSU的定义，我们无法对最终场景转折作任何的断言。然而我们确实知道，出于某种原因，音频相对于前一镜头发生了变化——可能强调正在发生的重要事件、影片中情绪的变化、或者浪漫的时刻。出于这个原因，并且因为我们的技术主要依赖于检测场景变化的视觉分析，所以我们将这些音频变化称为“音频模式暗示”，视频节目创作者希望其对于情节的演变至关重要。

规则ii)

因此，当且仅当如下条件下，在镜头i处检测到音频模式暗示：

AC(s_i)AND(NOT((VC(s_i-N))OR(VC(s_i-N+1))OR...OR(VC(s_i+N-1))OR(VC(s_i+N))))

其中N是在各AC周围的时间模糊窗，并且在本示例中具有一个镜头的值。这种情形示于图16中。

视听场景变化

如果在镜头i处发生的音频变化与为该镜头中或周围的视频变化一致，则我们检测到“视听场景变化”。在这种情况下，检测到的LSU边界很可能是真实场景转折。长度为N的模糊窗考虑了音频变化预示(正好在之前发生)或跟随(正好在之后发生)视觉场景变化的情况。因此，第三个规则定义如下。

规则iii)

当且仅当如下条件，在镜头i处检测到视听场景变化：

VC(s_i)AND((VC(s_i-N))OR(VC(s_i-N+1))OR...OR(VC(s_i+N-1))OR(VC(s_i+N)))

其中N是各VC周围的时间模糊窗，且在本示例中，N具有一个镜头的值。这种情形示于图17中。

利用这些类型的语义内容信息(其包括视听场景变化、新的LSU、以及在LSU中的音频暗示)，就可能创建情节结构的更精确的分级组织，使得朝向对视频媒体的自动语义理解更进一步。

本发明可发现许多不同的工业应用。可以构想主要但非排他地利用处理器上运行的软件程序来实现本发明，尽管还可等同地构想专有硬件实现。作为一个应用示例，个人计算机、DVD记录器、或能够再现视听序列的其他视听设备可安装有被设置为在执行时实现本发明的软件。在用户的控制下，例如通过用户按压DVD等的遥控器上的“寻找类似物”控制按钮，来进行对该软件的执行。在视听序列回放过程中，用户在他希望DVD播放器搜索整个序列以寻找语义类似的场景的场景处按压“寻找类似物”按钮。然后DVD播放器执行实现本发明的软件直到执行无时间约束聚类的阶段，之后向用户显示在与他启动“寻找类似物”功能时所观看的场景相同的类中找到的所有场景。按照这种方式，用户通过触摸按钮就能够浏览视听序列中所有语义类似的场景。

在另一应用中，本发明可被用于自动生成关于音频场景变化、视频场景变化、以及逻辑故事单元边界的章节标记。再次地，诸如个人计算机、DVD记录器、或能够再现视听序列的其他视听设备可安装有被设置为在执行时实现本发明的软件。用户将视听序列(可存储在DVD盘上、从因特网下载、或以其他方式输入)加载到该设备中，然后命令该设备执行实现本发明的软件(例如通过按压适当的按钮或使用图形用户界面来控制该设备)。然后该软件运转以如所描述地确定视频和音频场景边界以及逻辑故事单元边界，并且与不同类型的边界相关的标记可被存储于内容中或对其的索引中。生成这种标记之后，用户可使用这些标记对视听内容进行导航。不同类型的标记提供了不同类型的导航，并且因此丰富了用户对于内容的体验。

本发明的其他应用对于有意的读者将是非常明显的。

除非上下文明确要求，否则在整个说明书和权利要求书中，按照与排他和穷尽相反的包含意义来解释术语“包括”、“包含”等；也就是说，是“包括，但不限于”的意义。

此外，为了避免起疑，给出了对于现有技术文档和公开物的引用，其内容(无论是全部还是部分)对于作为本领域技术人员的有意读者理解本发明任意实施例的操作或实现是必要的，则通过对其的所述引用将所述内容并入于此。

总结

总结上文，优选实施例提供了一种用于在语义级别上导出内容信息以便提供与视频序列(例如，电影或电视节目)的内容相关的有意义信息的技术。该技术最初将视频序列分为单独的镜头。还可根据基于镜头的视频划分将伴音序列分为多个音频镜头。这之后，采用了两个分支分析阶段来分别处理视频和音频镜头。在视频分析分支中，为各镜头提供了代表性的关键帧。将该关键帧分为构成VQ码本学习处理的训练矢量的像素块，码本之后表征该关键帧，由此表征镜头。采用了公知的距离度量来计算各码本(镜头)对之间的距离(表示视觉相似度)，这之后通过将镜头间距离落在预定范围内的镜头分组在一起来执行聚类。接下来，执行时间约束聚类，其中考虑分在同一类中的镜头的时间局部性。所得子类代表具有视觉上相似且时间上相邻的内容的视频镜头。然后采取多个步骤以从子群集中识别逻辑故事单元(LSU)。

在音频分支中，可对各音频镜头执行短时频谱分析以导出形成用于进一步VQ码本学习处理的训练矢量的一组Mel频率倒谱分量(MFCC)。可采用堆土机距离(EMD)测量方法来计算各音频码本对之间的距离(其表示音频相似度)，根据该距离，可以通过沿着序列时间线识别EMD测量结果中的峰值来定位音频镜头边界。

最后，可以将一组启发式规则应用于所得LSU和音频镜头场景，以在语义级别上识别关于视听序列的信息。这采用了LSU和音频镜头场景的各个边界之间的比较。

参考文献：

1、A.Hanjalic，“Visual-Content Analysis for Multimedia RetrievalSystems”，PhD Thesis，Delft University of Technology，The Netherlands，1999.

2、M.M.Yeung and B.L.Yeo，“Time-constrained clustering forsegmentation of video into story units，”Proceedings of ICPR’96.

3、A.Hanjalic，R.L Lagendijk，“Automated high-level moviesegmentation for advanced video retrieval systems，”IEEE Trans.OnCircuits and Systems for Video Technology，9(4)，June 1999.

4、B.Adams“Where does computational media aesthetics fit？”IEEEMultimedia，April-June 2003，pp.18-26.

5、Z.Liu，Y.Wang and T.Chen，“Audio feature extraction and analysisfor scene segmentation and classification”，Vol.20，No.1，Journal of VLSISignal Processing Systems for Signal，Image，and Video Technology.

6、H.Sundaram and S.F.Chang，“Determining computable scenes infilms and their structures using audio-visual memory models，”ACMMultimedia 2000，pp.95-104.

7、Y.Chao，W.Tavanapon，K.Kim and J.Oh，“Audio-assisted scenesegmentation for story browsing，”Proc.of Int’l conf.on Image and VideoRetrieval(CIVR’03)，pp.446-455，Urbana-Champaign，IL，USA，July2003.

8、S.-C.Chen，M.-L.Shyu，W.Liao，and C.Zhang，“Scene changedetection by audio and video clues，”Proc.of IEEE ICME’2002，pp.365-368，2002，Lausanne，Switzerland.

9、H.Sundaram and S.F.Chang，“Audio scene segmentation usingmultiple features，models and time scales，”Proc.of ICASSP’2000，Istanbul，Turkey，June 2000.

10、B.Logan，A.Salomon，“A content-based music similarity function，”Compaq Technical Report (CRL-2001-2)，June 2001.

11、Y.Rubner，C.Tomasi，and L.Guibas，“The Earth Mover’s Distance asa metric for image retrieval，”Technical Report STAN-CS-TN-98-86，CSDepartment，Stanford University，Sept 1998.

12、J.G.R.C.Gomes M.Carli，S.K.Mitra and A.Neri，“Vectorquantization-based automatic shot boundary detection，”Proc.of IEEEWorkshop on Multimedia Signal Processing (MMSP’02)，pp.216-219，2002.

13、http://www.aber.ac.uk/media/Documents/short/gramtv.html

14、http://www.alphaworks.ibm.com/tech/videoannex

15、B.L.Yeo and B.Liu，“Rapid scene analysis on compressed videos，”IEEE Trans.on C.S.V.T.，December 1995.

16、M.M.Yeung，B.Yeo，W.Wolf，B.Liu，“Video browsing usingclustering and scene transitions on compressed sequences，”in Proc.ofMultimedia Computing and Networking，Vol.SPIE 2417，pp.399-413，Feb 1995.

17、A.Gersho，R.M.Gray，“Vector Quantization and Signal Compression”，Kluwer Academic Publishers，January 1992.

18、F.Archetti，E.Fagioli e a.Scimachen，“Metodi della ricercaoperativa，”Giappichelli 1989.

19、W.H.Press，B.P.Flannery，S.A.Teukolsky，and W.T.Vetterling，“Numerical Recipes in C”，Cambridge Univ.Press，1988.

20、Y.Wang，Z.Liu，J.-C.Huang，“Multimedia content analysis usingboth audio and visual cues，”IEEE Signal Processing Magazine，2001.

Claims (26)

1、一种识别视频序列中的语义相似的镜头的方法，该方法包括以下步骤：

a)识别所述视频序列中的镜头，各镜头是时间连续的视频帧序列；

b)计算各镜头与每一个其他镜头间的距离值；以及

c)依据相应计算出的其间距离值将镜头聚类成组；

其中在步骤c)中被聚类为一组的镜头具有语义相似的内容。

2、根据权利要求1所述的方法，其中，所述计算步骤包括：

i)生成各识别出的镜头的码本表示，该码本表示至少将各镜头的关键帧表示为多个码；

ii)依据镜头的相应码本表示来计算各镜头与各个其他镜头之间的距离值。

3、根据权利要求2所述的方法，其中，所述生成步骤包括：

i)将所述帧分为x×y像素的块；

ii)在选定的颜色空间中，将各块的相应像素值(p₁，...，p_D)排列成一特征向量；以及

iii)识别能够根据其生成码本表示的特征向量的类。

4、根据权利要求3所述的方法，其中，所述生成的码本表示包括：

i)C个码字，其分别是各特征向量类的质心，按照下式而获得：

${({\mathrm{\&mu;}}_1,...,{\mathrm{\&mu;}}_D)}_c=\frac{{\mathrm{\&Sigma;}}_{i=1}^{M_c}{(p_1^i,...,p_D^i)}_c}{M_c}$

其中M_c是落入码字c的分区中的x×y的块的数量；

ii)码字的方差，按照下式而获得：

${({\mathrm{\&sigma;}}_1^2,...,{\mathrm{\&sigma;}}_D^2)}_c=\frac{{\mathrm{\&Sigma;}}_{i=1}^{M_c}{[{({\mathrm{\&mu;}}_1-p_1^i)}^2,...,{({\mathrm{\&mu;}}_D-p_D^i)}^2]}_c}{M_c};$ 以及

iii)码字的权重，其考虑与各码字c相关联的x×y的块的数量M_c。

5、根据权利要求4所述的方法，其中，采用介于0与1之间的归一化权重，并将其计算为

6、根据权利要求4或5中任一项所述的方法，其中，计算任意两个镜头之间的距离值包括以下步骤：

i)将第一镜头(A)的各码本矢量y_i∈{y₁，...，y_N}与第二镜头(B)的各码本矢量z_j∈{z₁，...，z_N}进行比较，以根据下式来计算距离矩阵d_i，j＝d(y_i，z_j)：对于i＝1，...，N，且j＝1，...，N，

$d_{i,j}=\frac{1}{D}\underset{h=0}{\overset{D}{\mathrm{\&Sigma;}}}[\mathrm{\&alpha;}{({\mathrm{\&mu;}}_{\mathrm{ih}}-{\mathrm{\&mu;}}_{\mathrm{jh}})}^2+(1-\mathrm{\&alpha;}){({\mathrm{\&sigma;}}_{\mathrm{ih}}-{\mathrm{\&sigma;}}_{\mathrm{jh}})}^2],$

其中D是码本矢量的维数，0＜α＜1.0是加权因子；

ii)根据下式确定所述两个镜头(A和B)之间的距离值(VQ_d(A，B))：

7、根据前述权利要求中的任一项所述的方法，其中，所述聚类步骤包括迭代地应用以下步骤：

i)选择相互间具有较短距离的第一镜头或镜头类以及第二镜头或镜头类；以及

ii)将所选镜头和/或镜头类聚类为新的类；

其中随后执行所述距离计算步骤b)以确定在其余的镜头和类与新的单个类之间的距离。

8、根据权利要求7所述的方法，该方法进一步包括以下步骤：

iii)计算所述新的单个类的至少一个误差值，所述至少一个误差值表示所述类的码表示表示该类中镜头的程度；

iv)依据所述至少一个误差值，使所述新类无效并保留所选镜头和/或镜头类。

9、根据权利要求8的方法，该方法进一步包括如下步骤：v)防止所选镜头和/或镜头类在后续迭代中被选择用于聚类。

10、根据权利要求7至9中任一项所述的方法，该方法进一步包括如下步骤：如果镜头类中的镜头数等于或大于阈值数，则防止所述类在后续的迭代中被选择用于聚类。

11、一种自动地将视频序列中的视频镜头组织成具有相似语义内容的组的方法，该方法包括以下步骤：

a)识别所述视频序列中的镜头，各镜头包括连续的视频帧序列；

b)使用量化过程生成各镜头的码本表示；

c)依据镜头的相应码本表示，计算各镜头与每一个其他镜头间的距离值；以及

d)依据相应计算出的其间距离值将镜头聚类成组。

12、一种识别视频序列中的语义相似的场景的方法，该方法包括：

根据前述权利要求中的任一项所述的识别语义相似的镜头的方法；并且进一步包括以下步骤：

对于各镜头类，识别包含在其中的时间连续的镜头；并将该类分成多个子类，每个子类都包含一组时间连续镜头；

其中特定子类中的各镜头与同一子类中的其他镜头在语义上相似并在时间上相邻。

13、一种识别视频序列中的逻辑故事单元的方法，该方法包括：

根据权利要求12所述的识别语义相似的场景的方法；并且进一步包括以下步骤：

对子类以及定义镜头子类间的视频序列的时间流的时间转换执行图形分析，以识别时间流在其中按顺序移动的子类组；

其中所述识别出的子类组对应于所述视频序列的逻辑故事单元。

14、根据前述权利要求中的任一项所述的方法，该方法还进一步包括以下步骤：

i)将所述视频序列的伴音音轨分段为与所述识别出的视频镜头相对应的段；

ii)计算连续音频段之间的距离值；以及

iii)依据计算出的距离值来检测音频场景边界。

15、根据权利要求14所述的方法，其中，所述计算步骤包括以下步骤：

i)生成各音频段的码本表示，该码本表示将各段表示为多个码；

ii)依据音频段的相应码本表示来计算连续段之间的距离值。

16、根据权利要求15所述的方法，其中，所述生成步骤包括以下步骤：

i)将各段分为多个帧；

ii)对各帧进行频谱分析以提取D频谱系数，并且确定帧能量；

iii)至少依据帧能量对D频谱系数进行归一化；

iv)将相应频谱系数(f₁，...，f_D)排列为一特征向量；以及

v)识别根据其可生成码本表示的特征向量类。

17、根据权利要求16所述的方法，其中所述生成的码本表示包括：

i)C个码字，其分别是各识别出的类的质心，按照下式而获得：

${({\mathrm{\&mu;}}_1,...,{\mathrm{\&mu;}}_D)}_c=\frac{{\mathrm{\&Sigma;}}_{i=1}^{M_c}{(f_1^i,...,f_D^i)}_c}{M_c}$

其中M_c是与码字c相关联的镜头中的音频帧数；

ii)码字的方差，按照下式而获得：

${({\mathrm{\&sigma;}}_1^2,...,{\mathrm{\&sigma;}}_D^2)}_c=\frac{{\mathrm{\&Sigma;}}_{i=1}^{M_c}{[{({\mathrm{\&mu;}}_1-f_1^i)}^2,...,{({\mathrm{\&mu;}}_D-f_D^i)}^2]}_c}{M_c}$

iii)码字的权重，其考虑与各码字c相关联的音频帧数M_c。

18、根据权利要求17所述的方法，其中使用介于0与1之间的归一化权重，其由下式给出：

${\mathrm{\&omega;}}_c=M_c/{\mathrm{\&Sigma;}}_{c=1}^C{M}_c.$

19、根据权利要求15至18中任一项所述的方法，其中，连续音频段之间计算出的距离值为堆土机距离值。

20、根据权利要求14至19中任一项所述的方法，该方法进一步包括如下步骤：使用预定义的启发式准则将所述音频场景边界与所述视频场景边界进行整合。

21、根据权利要求20所述的方法，其中，当与视频场景边界基本同时检测到音频场景边界时，确定检测到了视听边界。

22、根据权利要求20或21所述的方法，其中，当检测到视频场景边界，但没有与其基本同时地检测到音频场景边界时，确定检测到了逻辑故事单元边界。

23、根据权利要求20、21或22中任一项所述的方法，其中，当检测到音频场景边界，但没有与其基本同时地检测到视频场景边界时，确定在逻辑故事单元内已经发生了在语义上重要的事件。

24、一种计算机程序或一组计算机程序，该计算机程序或该计算机程序组被设置为使得当由计算机系统执行时其使得该计算机系统执行根据前述权利要求中的任一项所述的方法。

25、一种计算机可读存储介质，该计算机可读存储介质存储有根据权利要求24所述的计算机程序或计算机程序组中的至少一个计算机程序。

26、一种系统，该系统包括通用处理器，所述处理器被设置为用于执行根据权利要求1至23中的任一项所述的方法。

Images