对电影类视频进行场景片段抽取方法及其建立索引的方法

1.一种对电影类视频进行场景片段抽取的方法，该方法包括如下步骤：
1)获取电影类视频的字幕信息，所述字幕信息包括字幕的文字内容以及该字幕的在视频中的出现和消失时间；
2)从所述电影类视频的剧本文本中抽取每个场景的结构化信息，所述结构化信息包括所述场景的发生地点、发生时间、场景类型、场景描述和场景对白信息；
3)对场景对白信息与字幕的文字内容进行匹配，将所匹配的字幕在视频中的出现和消失时间作为场景在视频中的开始和结束时间；根据得出的各场景在视频中的开始和结束时间，对于每两个相邻场景，抽取其中前一个场景的结束时间至后一个场景的开始时间之间的视频图像，根据每两个连续视频图像之间的颜色分布差异，进一步精确确定所述两个相邻场景的时间切分点，从而进一步精确确定各场景所对应视频片段的开始和结束时间；
4)根据步骤3)最后所得出的场景在视频中的开始和结束时间，对所述电影类视频进行分割，得到各场景的视频片断。
2.根据权利要求1所述的对电影类视频进行场景片段抽取的方法，其特征在于，所述场景对白信息包括一句或多句对白，每句对白包括以下信息：说话人、说话人说话时的动作注释、对白内容文本、对白之后的后继动作说明。
3.一种对电影类视频场景片段建立索引的方法，其特征在于，该方法包括：
1)获取电影类视频的字幕信息，所述字幕信息包括字幕的文字内容以及该字幕的在视频中的出现和消失时间；
2)从所述电影类视频的剧本文本中抽取每个场景的结构化信息，所述结构化信息包括所述场景的发生地点、发生时间、场景类型、场景描述和场景对白信息；
3)对场景对白信息与字幕的文字内容进行匹配，将所匹配的字幕在视频中的出现和消失时间作为场景在视频中的开始和结束时间；根据得出的各场景在视频中的开始和结束时间，对于每两个相邻场景，抽取其中前一个场景的结束时间至后一个场景的开始时间之间的视频图像，根据每两个连续视频图像之间的颜色分布差异，进一步精确确定所述两个相邻场景的时间切分点，从而进一步精确确定各场景所对应视频片段的开始和结束时间；
4)根据步骤3)最后所得出的场景在视频中的开始和结束时间，对所述电影类视频进行分割，得到各场景的视频片断；
5)根据步骤2)中得到的场景的发生地点、发生时间、场景类型、场景描述和场景对白信息，为各场景的视频片断建立索引。
4.根据权利要求3所述的对电影类视频场景片段建立索引的方法，其特征在于，所述场景对白信息包括一句或多句对白，每句对白包括以下信息：说话人、说话人说话时的动作注释、对白内容文本、对白之后的后继动作说明。

对电影类视频进行场景片段抽取方法及其建立索引的方法\n技术领域\n[0001] 本发明涉及视频索引与搜索技术领域，具体地说，本发明涉及一种对电影类视频进行场景片段抽取和建立索引的方法。\n背景技术\n[0002] 廉价的大容量存储设备制造技术的进步，更高的网络数据传输速率，以及持续改进的高效视频压缩技术使数字视频得以广泛传播和使用。视频为多媒体系统用户提供了大量的信息，同时它也是很多应用系统的数据源，这些系统如数字图书馆、数字出版、数字娱乐、数字广播和远程教育等。目前，基于视频信息的网络服务正处于高速发展期。但是，与成熟的文本信息搜索相比，目前高效地获取特定的视频片段仍然是一个非常具有挑战性的问题。文本与视频(运动图像)在检索时差异很大，文本内容中的某个词很容易被识别，并且该词包含人可理解的概念(含语义信息)，因此文本内容可进行全文检索(此时文本中的词汇是检索特征量)；但图像本身的特征很难用于直接搜索，例如颜色分布特征与用户的询问信息可能毫无关联，视频由一系列的图像构成，其语义更为复杂，机器将用户的查询信息转化为对一系列视频特征的查询存在很大困难，即存在所谓的“语义鸿沟”问题。所以，与文本信息不同，直接从视频数据中很难获得检索所需的特征量，要对视频进行有效的检索必须依赖于充分的视频元数据信息。当前大部分的商业视频搜索引擎一般也通过搜索视频的元数据信息如文件名、环绕文字或者语音脚本(使用语音识别技术从视频中获得)为用户返回所需的视频。这种方法对视频的搜索可以定义为一种浅层搜索，因为它无法进行基于视频内容的检索，而且只能检索到视频文件层次，而不是深入到每个视频片段。显然，这种搜索结果用户是不能满意的，例如用户可能只想看一部电影中的某个片段，这是当前搜索引擎所无法提供的。为了使原始视频数据可以被方便地浏览和检索，必须对视频数据进行分析、建立索引和重新组织，其目标是形成原始视频数据的结构化表示。\n[0003] 为了将视频进行结构化表示，一个连续的视频图像序列经常被分解成多个场景和镜头单元，这些场景和镜头单元根据其依赖关系形成了原始视频序列的层次化表示。一个镜头是由同一个摄像机连续捕获的一个帧序列，它实际上是视频图像序列之间的物理边界。场景由一个或多个连续镜头组成，这些镜头拥有共同拍摄背景/环境。例如，我们经常可以看到很多连续的镜头(由多个摄像机拍摄)共享类似的视觉内容，因为它们是在同样的环境中产生的如会议室或运动场等。一个视频场景片段一般是一个具有完整语义的故事单元，它实际上是视频图像序列的语义边界。由于用户检索一般是基于语义单元的检索，为此视频图像序列一般被以场景为单位进行组织。显然，比较准确的视频场景抽取是保证检索质量的关键。本发明主要讨论电影类视频进行场景抽取和索引的方法。该类视频进行场景抽取的过程一般可以分为两个步骤：首先是根据视频图像的颜色、纹理等特征进行镜头边缘检测；然后将视觉内容近似且连续的多个镜头划分为一个组并作为一个场景。这种方法的缺陷首先在于镜头检测容易受到干扰，例如对于渐变镜头有较高的误判率，其次镜头视觉内容的表示和镜头之间相似性的衡量方法目前也不够成熟。这些原因导致场景抽取的查全率和查准率都不是太理想，目前所报道的查全率和查准率的最好结果均在70％左右。\n另一方面，采用上述方法抽取场景后，为支持高效的检索，还必须为场景建立索引，例如说明场景发生的地点、主要人物和发生的事件等。这些工作耗时费力，而且由于个人主观性的影响，会导致标注结果的不客观。\n发明内容\n[0004] 本发明的一个目的是结合剧本和字幕信息对的电影场景进行分割(即场景片段抽取)，以达到较高精度的视频场景抽取效果。本发明的另一个目的是为所抽取的场景视频片段自动匹配其在剧本中的对应文字信息作为其索引，从而避免手工标注。\n[0005] 为实现上述第一个发明目的，本发明提供了一种对电影类视频进行场景片段抽取的方法，该方法包括如下步骤：\n[0006] 1)获取电影类视频的字幕信息，所述字幕信息包括字幕的文字内容以及该字幕的出现和消失时间；\n[0007] 2)从所述电影类视频的剧本文本中抽取每个场景的结构化信息，所述结构化信息包括所述场景的发生地点、发生时间、场景类型、场景描述和场景对白信息；\n[0008] 3)对场景对白信息与字幕的文字内容进行匹配，根据所匹配的字幕的出现和消失时间，得出场景在视频中的开始和结束时间；\n[0009] 4)根据步骤3)最后所得出的场景在视频中的开始和结束时间，对所述电影类视频进行分割，得到各场景的视频片断。\n[0010] 上述技术方案中，所述步骤3)包括如下子步骤：\n[0011] 31)对场景对白信息与字幕的文字内容进行匹配，将所匹配的字幕在视频中的出现和消失时间作为场景在视频中的开始和结束时间。\n[0012] 上述技术方案中，所述步骤3)还包括如下子步骤：\n[0013] 32)根据步骤31)得出的各场景在视频中的开始和结束时间，对于每两个相邻场景，抽取其中前一个场景的结束时间至后一个场景的开始时间之间的视频图像，根据每两个连续视频图像之间的颜色分布差异，进一步精确确定所述两个相邻场景的时间切分点，从而进一步精确确定各场景所对应视频片段的开始和结束时间。所述两个相邻场景的时间切分点就是精确确定的后一个场景的开始时间，也就是精确确定的前一个场景的结束时间。\n[0014] 上述技术方案中，所述场景对白信息包括一句或多句对白，每句对白包括以下信息：说话人、说话人说话时的动作注释、对白内容文本、对白之后的后继动作说明。\n[0015] 为实现上述第二个发明目的，本发明提供了一种对电影类视频场景片段建立索引的方法，该方法包括：\n[0016] 根据上述步骤1)至4)得到各场景的视频片断；\n[0017] 5)根据步骤2)中得到的场景的发生地点、发生时间、场景类型、场景描述和场景对白信息，为各场景的视频片断建立索引。\n[0018] 与完全基于视频内容分析的视频场景抽取方法相比，本发明的优势在于：第一、极大地降低了场景抽取的时间，这是因为本发明不需要对所有的视频帧都进行内容分析，而只需要分析两个相邻包含对白场景之间的那些视频帧。第二、提高了场景视频场景片段抽取的精确度，由于剧本实际上是电影视频的高层语义，剧本中的场景和视频中的场景是一一对应的，因此如果所有的场景都包含对白则理论上本发明给出的方法可达到100％的查准率和查全率；对于连续无对白场景不超过一个的情况，本发明基本也不会误判，由于连续出现多个无对白场景的情况非常少，因此可以认为本发明可以准确地抽取出视频中各个场景。第三、剧本中的场景描述文本可直接作为所对应抽取场景视频片段的索引信息，由于剧本中包含了场景所有的高层语义信息，因此可支持用户进行类似于文本检索的查询，而纯粹的基于视频内容分析方法在抽取视频场景片段后还要进行烦琐的标注。\n附图说明\n[0019] 图1本发明一个实施例中对电影类视频进行场景片段抽取和建立索引的总体流程框图；\n[0020] 图2本发明一个实施例中剧本信息的结构化表示示意图；\n[0021] 图3本发明一个实施例中基于剧本信息的视频场景分割方法示意图。\n具体实施方式\n[0022] 本发明在对电影类视频进行场景抽取和索引时，引入了视频所对应的剧本和字幕这两方面信息，达到较高精度的视频场景抽取效果，并且可以为所抽取的场景视频片段自动匹配其在剧本中的对应文字信息作为其索引，从而避免手工标注。剧本是影视作品拍摄制作的依据，实际上是视频(连续图像)的语义信息。一部电影作品的剧本一般由多个场景构成，剧本中的每个场景一般包含以下信息：地点、时间、内外景说明、场景描述、对白等内容。剧本中的对白实际上就是电影的字幕。目前对于高清DVD电影，其字幕一般以外挂文件的形式随视频文件一起发布，易于获得；对于内嵌型字幕则可通过视频OCR技术提取字幕。每条字幕均包含该字幕在视频中的出现和消失时间，本发明正是通过利用这些时间信息结合剧本场景对白对视频场景片段进行抽取。\n[0023] 下面，结合附图和具体实施例对本发明作进一步地描述。\n[0024] 1 总体流程\n[0025] 附图1是本专利提出的融合剧本与字幕信息的电影场景抽取与索引方法的总体流程框图。所包含的主要处理步骤如下：1)根据剧本的文本编辑特征(剧本一般采用文本格式来体现场景中不同信息域的内容)将剧本文本转换为一种由本专利定义的基于上下文无关语言的内部表示，该转换的目的是去除剧本的文本编辑特征并为其赋予语法格式特征，以便于后续处理；2)采用语法制导翻译的方法在上下文无关语言表示的剧本中抽取出每个场景的发生时间、发生地点、人物和对白等信息，并据此生成剧本的树形结构化表示；\n3)通过字幕与场景中对白文本的匹配，为场景中的每句对白生成其在视频中的出现和消失时刻信息，并把每个场景所包含的第一句对白的开始时刻和最后一句对白的消失时刻作为场景视频片段的初始分割边界；4)确定初始分割边界后，为达到视频的无缝分割采用基于视频内容分析的方法确定场景和场景之间的切换点，并据此确定场景视频片段的最终分割边界。下文对上述过程进行具体描述，其中前两个步骤合并在第2节中进行描述。\n[0026] 2 剧本信息的抽取与结构化表示\n[0027] 剧本是影视作品拍摄制作的依据，实际上是视频(连续图像)的语义信息。一部影视作品的剧本一般由多个场景构成，剧本中的每个场景一般包含以下信息：地点、时间、内外景说明、场景描述、对白等内容。根据一些正规出版的电影剧本如《中国电影剧本选集》和《谢晋电影选集》等，中文剧本中的场景一般具有以下格式(摘自《谢晋电影选集》)：\n[0028] 60.桥侧石柱 晨 外景\n[0029] 月红、小香给春花松开绑绳。\n[0030] 小香(不忍)\n[0031] 春花。\n[0032] 月红(哽咽)\n[0033] 春姐。\n[0034] 春花抱住月红放声痛哭。\n[0035] 场景虽然表示为一段文本，但它实际上蕴涵了丰富的结构化的信息，如在上面的示例场景中包含了以下不同角度的信息：\n[0036] 场景编号：60；\n[0037] 场景发生的地点：桥侧石柱；\n[0038] 场景发生的时间：晨；\n[0039] 场景类型：外景；\n[0040] 场景描述：月红、小香给春花松开绑绳；\n[0041] 在这些信息之后是场景中的对话信息，每个说话记录又可结构化表示为以下各个域的信息：\n[0042] 说话者：小香；月红；\n[0043] 说话时注释：不忍；哽咽；\n[0044] 内容：春花；春姐；\n[0045] 话后说明：(无)；春花抱住月红放声痛哭；\n[0046] 剧本通过一些显著的文本编辑特征来区分各个不同方面的信息，例如场景基本说明行(首行)一般顶格且为黑体，对白文本的缩进字数要远大于注释文本，对白中说话人用黑体显示等。这些格式信息是我们进行文本内部表示转换时的重要依据。一个剧本由多个场景构成，为让用户可以根据场景的不同方面内容进行视频的检索，本实施例把剧本(Script)所蕴涵的信息结构化表示为一棵树，如附图2所示。图中Script节点表示剧本，它包含多个场景(Scene节点)。每个场景又包含发生地点(Location节点)、发生时间(Time节点)、场景类型(Type节点)、场景描述(Description节点)、场景所对应的视频片段(URI节点)、和对白(Dialogues节点)这六个方面信息。每个对白节点可包含一或多句对白(Dialogue节点)。每句对白包含以下各个信息：说话角色(Role节点)、说话时注释(Annotation节点)、对白内容(Content节点)、话后说明(Show节点)、该句对白在视频中的出现时刻(Appear节点)和该句对白在视频中的消失时刻(Disappear节点)。域Appear和Disappear用于表示该条对白所对应字幕的出现和消失时刻，这两个域的内容仅从剧本文本是无法获得的，其值将通过剧本对白与视频字幕的匹配来获得，具体方法将在下文介绍。剧本作为视频的语义信息，其结构化表示即为视频的结构化表示。基于这种表示方法，剧本中的文本信息都可以作为视频的索引信息，由此可以很方便地搜索到发生在某个地点视频场景片段，甚至可以搜索到包含某个角色或某句对白的视频片段。采用XMLSchema对附图2所示的树结构进行描述，作为剧本信息的元数据模版。在此基础上，通过对剧本文本进行结构化信息抽取，可获得结构化的剧本信息XML文档，作为视频场景片段抽取的依据和视频的索引。\n[0047] 为便于剧本信息的抽取，本实施例首先根据剧本场景文本的编辑特征将原始场景文本转化为一种内部表示。对于上文的示例场景其转换后的内部表示如下：\n[0048] 60.桥侧石柱，晨，外景\n[0049] (月红、小香给春花松开绑绳。)\n[0050] 小香：(不忍)春花。\n[0051] 月红：(哽咽)春姐。(春花抱住月红放声痛哭。)\n[0052] 该内部表示实际上是本实施例定义的一种具有特定语法格式的剧本场景描述语言，采用CFG(上下文无关文法)进行定义，其基于BNF(巴斯科范式)的形式化描述如下所示：\n[0053] 一个场景描述文法是一个四元式(VT，VN，S，P)，其中VT是终结符的非空有限集合VT＝{comma，period，colon，character，(，)}，comma表示逗号，period表示句点，colon表示冒号，character表示字符(不包含‘#’和‘]’)；VN是一个非终结符的非空有限集VN＝{Scene，Head，Description，Dialogues，Number，Digital，Location，Characters，Time，Remark，Surroundings，Dialogue，Content，Role，Annotation，Show}；S是一个特殊的非终结符(S∈VN)称为开始符号；P是一个产生式(规则)的有限集合，P中的产生式如下：\n[0054] Scene→Head Description Dialogues|Head Dialogues\n[0055] Head→Identifier Location Time Surroundings|Identifier\n[0056] Identifier→Number period\n[0057] Number→Digital Number|Digital\n[0058] Digital→9|8|7|6|5|4|3|2|1|0|\n[0059] Location→Characters comma\n[0060] Characters→character|Characters character\n[0061] Time→Characters|Characters Remark comma\n[0062] Remark→(Characters)\n[0063] Surroundings→Characters\n[0064] Description→(Characters)\n[0065] Dialogues→Dialogue Dialogues|Dialogue\n[0066] Dialogue→Role colon Annotation Content Show|Role colon Content Show|[0067] Role colon Annotation Content|Role colon Content\n[0068] Role→Characters\n[0069] Annotation→(Characters)\n[0070] Content→Characters\n[0071] Show→(Characters)\n[0072] 从原始剧本转换为上述内部表示的方法如下：\n[0073] 步骤1：从原始剧本中读入一行，若已至文件尾的则转步骤4，如果是空行转步骤\n1，否则转步骤2；\n[0074] 步骤2：判断所读入行的类型：计算该行所包含的字符数量设为A，计算去掉该行左方空格后的字符数量设为B；设n＝A-B如果n＝0则该文本行为一个新场景的第一行(标记其类型为1)，转步骤3；否则如果n＜4则该文本行为场景中的说明/注释信息(标记其类型为2)，转步骤3；否则如果n＜20则该文本行为场景中的说话人(标记其类型为\n4)，转步骤3；否则该文本行为对白(标记其类型为3)，转步骤3；\n[0075] 步骤3：设当前文本行类型为T上一文本行类型为L(这两个量的初始值都为零)，剧本内部表示存于变量F。去掉文本前后空格后，依据下列规则处理文本：1)T＝1：此时若L＝2则首先在F之后追加右括号换行符，否则直接将场景发生地点和发生时间以及场景类型之间的空格替换为逗号，并将该行追加到F，设置L＝T转步骤1；2)T＝4：此时若L＝2则还是在F之后追加右括号，否则直接进行如下处理：如果在文本中检测到左括号，则在左括号之前插入冒号并将该行追加到F，否则直接将该行追加到F，最后设置L＝T转步骤1；\n3)T＝3：将该行追加到F，设置L＝T转步骤1；4)T＝2：此时若L＝1或者L＝3则首先\n在F之后追加左括号，并将该行文本追加到F，否则直接将该行文本追加到F，最后设置L＝T转步骤1；\n[0076] 步骤4：在F之后追加右括号，之后结束程序，转换完成；\n[0077] 对转换后的内部表示剧本，本实施例通过语法制导翻译的方法，抽取出场景描述文本中的结构化信息。语法制导翻译表如表1所示。文本分析过程中用到了两个栈：符号栈(Text Stack，TS)和控制栈(Control Stack，CS)，字符进入符号栈还是控制栈必须依据其上下文确定。文本分析过程：按照文本自然顺序从头依次读入字符，如果该字符是文字将其压入TS，否则该字符可能是标点符号或者括号等，此时要根据CS栈顶字符进行相应操作，操作依据表1进行(表中行表示当前读到的控制字符，列则是当前控制栈的栈顶符号，表中用EOF表示栈为空的情况)；上述过程持续进行直至读完所有字符，一般如无特别注明进行表1(该表为语法制导翻译表)中的操作后程序将读入下一字符。\n[0078] 表1\n[0079] \n . ， ( ) ：\n . Push(TS，c Loc＝Pop(T Push(CS，c) Des＝Pop(TS) Push(TS，c)\n ) S) CS.Pop()\n Push(CS，c)\n ， Push(TS，c Tim＝Pop(T Push(TS，c) Push(TS，c) Push(TS，c)\n ) S)\n Pop(CS)\n ( Push(TS，c Push(TS，c) Push(CS，’[’) CS.Pop() Push(TS，c)\n ) Push(TS，c) 不读新字符\n Push(TS，c Push(TS，c) if TS is null Sho＝Pop(Top， Pop(TS，Rol，Co\n ： ) Push(CS，’# TS) n)\n ’)\n else\n Push(CS，c)\n Top＝TS.Co\n unt\n # Push(TS，c Push(TS，c) Push(TS，c) Ann＝Pop(TS) Push(TS，c)\n ) CS.Pop()\n [ Push(TS，c Push(TS，c) Push(TS，c) Push(TS，c) Push(TS，c)\n ) CS.Pop()\n EO ID＝Pop(T Push(TS，c) Typ＝Pop(TS) Des＝Pop(TS) Rol＝Pop(TS)\n F S) Push(CS，c) Push(CS，c)\n Push(CS，c\n )\n[0080] 表中Push(CS/TS，c)表示将当前读到的字符压入栈CS/TS，CS.Pop()表示弹出CS的栈顶字符；Pop(CS/TS)表示弹出CS/TS栈的所有字符，对于TS栈其弹出内容一般为场景各个信息域的值，表中对于各个信息域我们用附图2中各个域名称的前三个字母表示；TS.Count表示当前TS栈的字符数量，sho＝Pop(Top，TS)表示弹出TS栈栈顶的(TS.Count-Top)个字符作为附图2中Show域的值；Pop(TS，Rol，Con)表示从TS栈中弹出所有字符，分割获得图2中Role和Content这两个域的值。\n[0081] 经过上述抽取过程之后，附图2中剧本场景结构化信息域的内容除URI、Appear和Disappear已全部生成，这几个信息域的内容的生成方法将在下文讨论。\n[0082] 3 剧本和字幕的匹配方法\n[0083] 本部分讨论利用电影字幕信息生成场景中每句对白的出现和消失时刻信息(即生成附图2中Appear和Disappear节点的值)的方法。高清DVD视频中字幕一般以外挂\n文件的形式存在，字幕外挂文件基本上可分为两大类，其一为文本文件，其二为图片文件加时间索引信息文件，对于这种格式可通过OCR技术转换成文本格式。文本形式外挂字幕中，每条字幕具有如下形式：\n[0084] 6\n[0085] 00:01:55，215--＞00:01:57，581\n[0086] 师父，赵公子是名门望族\n[0087] 其中第一行为字幕按照其在视频中出现顺序的编号，第二行为字幕的出现和消失时间，其后为字幕的文字内容。\n[0088] 为了便于算法的叙述，首先对剧本和字幕进行形式化描述。称一部电影视频文件为V，V所包含的所有字幕为集合T＝{D1，D2，...，Di，...，Dm}，集合中的元素Di为一个四元组：{DI，DB，DE，DC}，DI为字幕的编号，DB为字幕在视频中出现的时间，DE为字幕在视频中的结束时间，DC是字幕的文字。\n[0089] V所对应的剧本用集合P＝{S1，S2，...，Si，...，Sn}表示，集合中的元素Si表示剧本中的第i个场景，Si可表示为一个六元组{SI，SL，ST，SP，SS，SD}，SI表示场景的编号，SL表示场景发生的地点，ST表示场景发生的时段(晨，日或夜等)，SP为场景类型(内/外景)，SS为场景的描述文本，SD为场景中的对白；SD是一个集合{d1，d2，...，di，...，dp}，其中di为一个六元组{SDR，SDA，SDC，SDS，SDP，SDD}，SDR为该对白的说出者，SDA是说话者说出该对白时的一些注释信息，SDC是对白的文字内容，SDS是该对白结束之后场景中的后继动作说明，SDP为该条对白在字幕中的出现时刻，SDD为该条对白在字幕中的消失时刻。\n[0090] 设V中所有的字幕文字按其出现顺序构成集合：X＝{DC1，DC2，...，DCi，...，DCm}，为便于书写改写为X＝{x1，x2，...，xi，...，xm}，并以xi∪xi+1表示第i和i+1条字幕文字的连接(多条连续字幕可能对应场景中的一句对白)，只有连续字幕文字才能进行连接操作；剧本P中所有对白中的文字按照其出现顺序构成集合：Y＝{SDC1，1，SDC1，2，...，SDC2，1，SDC2，2，...，SDCi，j， ...，SDCn，p}，其中SDCij表示第i个场景中第j个对白的文字内容，为便于书写将集合改写为Y＝{y1，1，y1，2，...，y2，1，y2，2，...，yi，j，...，yn，p}；如果X和Y中的元素满足如下关系：\n[0091] \n[0092] 则称Y可配准到X用 来表示这种关系，此时yi，j所在对白的出现时刻SDPi，j＝DBk消失时刻为SDDi，j＝DBl。\n[0093] 如果剧本对白文字集合Y和字幕文字集合X，满足 则称Y对应的剧本P为I\n级剧本；否则如果剧本P中的场景Si满足以下条件：\n[0094] \n[0095] 则称剧本P为II级剧本；不满足上述两个条件的剧本称为III级剧本。从上述定义可以看出，I级剧本可以根据字幕中蕴涵的时间信息为其包含的每个对白生成Appear和Disappear域的值，II级和III级剧本则只能为部分对白生成这两个域的值，II级剧本与三级剧本的区别在于II级剧本中对于包含对白的场景存在第一句对白和最后一句对白。定义这三种类别剧本的原因是某些剧本并不列出影片中出现的所有对白。视频存在I级剧本时用户的查询粒度可以达到每句对白对应的视频片段。如果视频存在对应的I级或II级剧本，则该视频可以基于剧本场景信息进行基本与剧本吻合的视频场景片段抽取，对于III级剧本则更多的依赖基于视频内容分析的抽取。\n[0096] 下面给出字幕与剧本匹配的具体算法：\n[0097] /*本函数产生包含对白场景的初始分割边界，函数的输入是结构化表示的场景描\n[0098] 述和字幕*/\n[0099] Algorithm SceneDivide(SceneRecordArray:S，\n[0100] TitleReeordArray:T)\n[0101] begin\n[0102] bt＝0；et＝0./*一句对白可对应连续多条字幕，这两个变量用于记录第一条和\n[0103] 最后一条对应字幕*/\n[0104] for(i＝0；i＜S.length；i++)/*对剧本中的每个场景进行处理*/\n[0105] if(S[i]Contain Dialogue)/*如果场景包含对白*/\n[0106] for(j＝0；j＜S[i].D.length；j++)/*对场景中每一句对白根据字幕生成其开始\n[0107] 和消失时刻*/\n[0108] d＝GetPureText(S[i].D[j])./*去掉标点符号和感叹词*/[0109] if(MatchTitle(T，d，&bt，&et))/*在字幕中搜索本句对白对应的字幕\n[0110] */\n[0111] S[i].D[j].Appear＝T[bt].DB./*设置对白的开始时间为第一条字\n[0112] 幕的开始时间*/\n[0113] S[i].D[j].Disappear＝T[et].DE./*设置对白的结束时间为最后一条\n[0114] 字幕的结束时间*/\n[0115] bt＝bt+1. /*设置下一句对白的进行匹配的开始字幕*/[0116] /*设置场景所包含的第一句对白的开始时刻为场景的初始开始\n[0117] 边界*/\n[0118] if(j＝0)S[i].Begin＝S[i].D[j].Appear.\n[0119] /*设置场景所包含的最后一句对白的结束时刻为场景的初始结\n[0120] 束边界*/\n[0121] if(j＝S[i].D.length-1)\n[0122] S[i].End＝S[i].D[j].Disappear.\n[0123] end if\n[0124] end for\n[0125] end if\n[0126] end for\n[0127] end\n[0128] /*本函数为对白文本搜索其对应的开始和结束字幕，函数输入T为结构化表示[0129] 的字幕集合，d为\n[0130] 对白文本，bt为进行搜索的起始字幕编号，函数运行结束后bt和et存放开始[0131] 和结束字幕编号*/\n[0132] Algorithm MatchTitle(TitleRecordArray:T，Dialogue:d，\n[0133] BeginTitle &bt，EndTitle &et)\n[0134] begin\n[0135] flag＝false./*用于记录匹配状态，为假表示还没找到对白的第一个匹配字幕，\n[0136] 反之为真*/\n[0137] for(i＝bt；i＜T.length-1；i++)\n[0138] pat＝GetPureText(T[i].Text)./*去掉标点符号和感叹词*/\n[0139] m＝StringApproximatch(pat，d，2)./*字幕文本和对白文本的近似匹配*/\n[0140] if(m＝-1)/*字符串匹配失败*/\n[0141] if(flag＝false)continue.\n[0142] else\n[0143] et＝i-1；return true.\n[0144] end if\n[0145] else/*匹配成功*/\n[0146] if(flag＝false)\n[0147] bt＝i；flag＝true./*记录对白所匹配的第一个字幕编号*/[0148] end if\n[0149] d＝d.Substring(m+1，d.length-m-1)./*删除对白前端已经匹配字幕的字\n[0150] 符，其个数为m*/\n[0151] if(d.length＝0)/*表示本句对白已经没有文本，即所有的文本都已经\n[0152] 匹配到字幕*/\n[0153] et＝i；return true./*记录结束字幕编号，返回匹配成功信息*/\n[0154] end if\n[0155] end if\n[0156] end for\n[0157] return false./*至此表示无法为对白找到匹配字幕，返回匹配失败信息*/\n[0158] end\n[0159] 上述算法适用于三种不同级别的剧本，算法要求剧本中的对白必须在字幕中可以找到，即不能出现一句在字幕中根本没有的对白。伪代码中S是剧本场景信息记录集基本包含附图2所示的各个信息域，S[i]表示第i个场景对应的信息记录，S[i].D[j]表示第i个场景的第j条对白，T是字幕记录集。函数GetPureText()用于去除文本中的标点符号和感叹词，这样做的原因是剧本中对白文本的标点符号和一些感叹词与字幕会有一些细微差别。函数MatchTitle()用于为每条对白寻找其对应的开始和结束字幕，其中字符串匹配采用基于动态规划的近似字符串匹配算法，在编辑距离不超过2时认为两个串匹配。\n[0160] 4 视频场景片段抽取与索引\n[0161] 假设场景Si(1≤i≤n)中有对白，其中第一个对白的文字为yi，1且yi，1＝xk∪xk+1∪...∪xl，最后一个对白的文字为yi，p且yi，p＝xl+h∪xl+h+1∪...∪xu，则场景Si包含视频段[DBk，DEu](DBk为视频段的开始时刻，DEu为视频段的结束时刻)；另设场景Si之后第一个包含对白的场景为Si′包含视频段[DBk′，DEu′]，N＝|Si′-Si|表示Si到Si′之间无对白场景的个数，则视频段[DEu，DBk′]所要确定的切分点数量为N+1，设b1，b2，...，bN+1为这些切分点的切分时刻，则场景Si对应视频段的上界(不包含)为b1，场景Si′对应视频段的是下界为bN+1，中间每个无对白场景对应的视频段为[bi，bi+1](1≤i≤N)。获得每个场景对应视频段的时刻上下界后，根据该信息对视频进行分割即可获得每个场景对应的视频段。切分点采用基于视频内容分析的方法确定。算法要求剧本的第一个场景和最后一个场景必须有对白，显然I级或II级剧本符合这个要求，III级剧本则可能不满足这一条件，此时将第一个字幕和最后一个字幕部分文本作为剧本第一个场景和最后一个场景的对白。\n[0162] 下面结合附图3，对场景视频片段抽取的具体流程进行说明。经过上一节字幕和剧本的匹配处理之后，对于每一个包含字幕的场景S[i]已经初步确定了其在整个视频中的开始和结束边界，但这个边界是不够准确的，因为场景中的对白可能在场景出现一段时间之后才会出现，另外还可能有一些场景没有字幕此时它由上一节方法无法确定其边界，为此为了准确地分割出场景视频段，首先必须确定每个场景的精确边界。另一方面，本实施例假定电影视频的片头和片尾不作为场景的一部分，并将其单独从视频文件中分割出来。具体步骤如下：\n[0163] 步骤1：从视频片段中分割出片头：设置辅助变量Begin＝0，End＝S[0].\nbegin(即第一个场景在上一节中初步确定的边界)，从视频文件(设为V)中分割出起始时间为Begin结束时间为End的视频段(附图2中函数GetVideoSeg(V，Begin，End)表示这一分割过程)，设置i＝0，转步骤2。\n[0164] 步骤2：设S.Length表示剧本所包含的场景总数，判断i是否小于S.length-1，如果是转步骤3，否则转步骤8；\n[0165] 步骤3：判断第i个场景是否包含对白(S[i].F为真表示包含对白)，如果不包含转步骤4，否则转步骤5；\n[0166] 步骤4：设置i＝i+1，转步骤2；\n[0167] 步骤5：取场景i之后的第一个包含对白场景设为j(附图3中由j＝\nGetNextScene(S，i)表示)，设置Begin＝S[i].end，End＝S[j].begin，在视频文件中抽取出开始时刻为Begin结束时刻为End的视频段所对应的所有视频图像(即视频帧)，统计每幅图像中三个颜色分量RGB的颜色分布情况，之后使用下面的公式计算所抽取图像中两个连续图像n和n+1之间的颜色分布差异D(n，n+1)：\n[0168] (公式1)\nR\n[0169] 公式1假定对于每个颜色分量具有256个强度等级，Cn(p)表示第n个图象中颜R R\n色分量R强度等级为p的像素点个数，|Cn(p)-Cn+1(p)|表示连续图象n和n+1在颜色分量R的第p个量化等级上差异绝对值，其余各项含义可类推，假设所抽取的图像总数为N，则需要计算N-1个帧间差异，假设计算结果存于数组Diff中，计算完成之后转下一步骤；\n[0170] 步骤6：在数组Diff中找出最大的(j-i)个元素，并使用数组Pos记录这些元素在Diff中的下标，对Pos数组中的元素按从小到大顺序进行排序，之后设置变量k＝0，转下一步骤；\n[0171] 步骤7：如果k值等于Pos数组长度，转步骤4，否则进行如下处理：设置第(i+k)个场景的结束时刻为：S[i+k].end＝Begin+(Pos[k]+1)*T，第(i+k+1)个场景的开始时刻为：S[i+k+1].begin＝S[i+k].end，之后设置Begin＝S[i+k].begin，End＝S[i+k].end，从视频文件中分割出起始时间为Begin结束时间为End的视频片段作为第(i+k)个场景对应的视频片段，将视频片段的存取位置作为场景中URI域的值，设置k＝k+1，重复本步骤；\n[0172] 步骤8：分割出视频序列中最后一个包含对白的场景：设置Begin＝S[S.\nlength-1].begin，End＝S[S.length-1].end，从视频文件中分割出起始时间为Begin结束时间为End的视频片段作为第(S.length-1)个场景对应的视频片段，转下一步骤；\n[0173] 步骤9：分割出片尾：分割出时刻S[S.length-1].end开始直至结束的视频片段，结束程序；\n[0174] 通过上述方法分割出剧本中每个场景对应的视频片段后，剧本场景中所包含的文本直接成为相应视频片段的语义标注，通过搜索场景文本中的关键词即可找到对应视频，或者通过指定信息域进行检索，例如检索出现某个说话人的所有视频片段。具体而言，本实施例将附图2中的剧本结构化信息模板采用XML Schema进行描述，对于每部电影为其建立符合该描述的XML文件，并将该文件作为该部影片的索引。