使用多个标记按照帧精确地自动剪切媒体内容的制作方法

使用多个标记按照帧精确地自动剪切媒体内容


背景技术：

1.在诸如因特网的计算机联网环境中，第三方内容提供商提供第三方内容项以在最终用户计算设备上显示。这些第三方内容项(例如广告)可以显示在与相应发布者关联的网页上。这些第三方内容项可以包括标识提供该内容项的第三方内容提供商的内容。


技术实现要素：

2.本公开总体上针对使用一种方法来分析长度可变的媒体流以识别和提取感兴趣的片段。可以识别感兴趣的片段，因为它们在媒体流中重复不止一次，或者在其他媒体流中存在。与其他方法相比，本公开描述了一种以帧精确的方式识别和提取感兴趣片段的方法，同时降低了处理和存储要求。此外，本文描述的方法可以识别长媒体流甚至无限长的媒体流并从长媒体流甚至无限长的媒体流中提取片段。
3.本公开总体上针对用于使用散列指纹技术来识别媒体流中的重复片段的技术解决方案。该方法可以例如从广播或从计算机存储的类型接收媒体流。所接收的媒体流可以包括多个视频帧。与在其他解决方案中一样，代替单独地分析每个视频帧的原始媒体内容，本解决方案可以为每个帧生成指纹，该指纹既表示相应的帧又表示相应的帧之前或之后的一段时间内的帧。例如，对于媒体流的每个帧，该方法可以生成表示在相应帧之后的三秒钟的窗口内的所有帧的指纹。
4.为了生成帧的指纹，本解决方案可以在所讨论的帧之前或之后的时间窗口内选择多个帧。帧的数量可以预定或基于其他因素来确定。可以基于时间窗口内的预定或计算的间隔来选择帧。可以使用适合于媒体散列和比较的散列算法(例如，局部敏感散列算法)来对每个选定帧进行散列。生成后，每个散列可以被截断为某个位宽，以减少最终指纹的尺寸脚注(the size footprint of the final fingerprint)。可以通过将每个被截断的散列级联为单个值或数据结构来生成指纹。本解决方案中为每个帧产生的指纹在相对于媒体流的各个帧的时间窗口中的帧是唯一的。例如，如果窗口时间段被确定为在所选帧之后三秒，则该方法可以执行上面概述的步骤，以针对代表所讨论的帧和进行该帧的媒体的三秒钟的每个帧生成指纹。通过以这种方式生成媒体指纹，本解决方案为两个媒体流的比较提供了显著的计算改进，同时减少了媒体比较数据的所需存储。
5.本解决方案可以将帧聚合为代表整个媒体流的多个指纹。可以将多个指纹存储在数据库或其他计算机存储介质中以进行分析。本解决方案可以例如通过顺序或通过时间戳将多个指纹中的每一个与媒体流的相应帧相关联。该方法可以接收与媒体流中的帧相对应的目标时间戳，该目标时间戳可以与媒体流的感兴趣片段内的帧相对应。本解决方案可以在代表与目标时间戳相对应的媒体流的多个指纹中确定目标指纹。例如，本解决方案可以确定与包括目标时间戳的时间段相对应的指纹。本解决方案可以选择目标指纹，使得目标时间戳表示由所选目标指纹表示的时间段的确切中点。
6.为了确定感兴趣片段是否在其他媒体流中重复，本解决方案可以检索候选多个指纹，候选多个指纹中的每个指纹对应于候选媒体流中的帧。在一些实现方式中，候选媒体流
可以与第一媒体流相同。本解决方案可以将目标指纹与第二多个指纹中的每个指纹进行比较，以确定第二媒体流中的匹配位置。如果找到匹配的指纹，则该方法然后可以在目标指纹的匹配位置之前和之后找到其他匹配。例如，该方法可以继续匹配与小于目标指纹的匹配位置的时间戳相对应的两个媒体流的每个指纹。本解决方案可以继续匹配指纹，直到可以确定感兴趣片段的时间戳的下边界为止。同样，为了确定感兴趣片段的上边界，本解决方案可以继续匹配与大于目标脚注(footprint)的匹配位置的时间戳相对应的两个媒体流的每个指纹，直到出现非匹配。
7.本解决方案可以使用上边界和下边界来识别两个媒体流中的任何一个中的感兴趣片段。本解决方案可以从媒体流中提取感兴趣的片段。因为为两个媒体流中的每个帧都产生了指纹，所以提取的感兴趣片段在两个媒体流中都是帧准确的。然后可以将提取的感兴趣的片段存储在数据库中或提供给感兴趣的一方。
8.本公开的至少一个方面针对一种基于帧指纹提取匹配媒体片段的方法。该方法可以包括由具有一个或多个处理器的数据处理系统接收包括多个帧的媒体流。该方法可以包括：对于多个帧中的每个，由数据处理系统基于指纹窗口值从多个帧中选择第二多个帧。该方法可以包括，对于多个帧中的每个帧，由数据处理系统对第二多个帧中的每个帧进行散列以创建多个散列。该方法可以包括，对于多个帧中的每个帧，由数据处理系统截断多个散列中的每个散列，以生成多个截断的散列。该方法可以包括，对于多个帧中的每一个，由数据处理系统将多个截断的散列级联以计算帧指纹值。帧指纹值可以与多个帧中的各个帧以及与各个帧相对应的时间戳相关联。该方法可以包括由数据处理系统聚合每个计算出的帧指纹值以组装多个指纹。该方法可以包括由数据处理系统接收与多个帧中的目标帧相对应的目标时间戳。该方法可以包括由数据处理系统基于目标时间戳和指纹窗口值来确定多个指纹中的目标指纹。该方法可以包括由数据处理系统检索第二多个指纹，第二多个指纹中的每个与第二媒体流中的帧相关联。该方法可以包括通过数据处理系统将目标指纹与第二多个指纹中的每个指纹进行比较，以确定与第二媒体流中的位置相对应的匹配位置。该方法可以包括：由数据处理系统将与小于目标时间戳的时间戳相关联的多个指纹中的第一指纹与第二多个指纹中的第二指纹进行匹配，以确定下边界时间戳。该方法可以包括：由数据处理系统将与大于目标时间戳的时间戳相关联的多个指纹中的第二指纹与第二多个指纹中的第三指纹进行匹配，以确定上边界时间戳。该方法可以包括由数据处理系统基于下边界时间戳和上边界时间戳从第二媒体流中提取媒体片段。该方法可以包括由数据处理系统提供用于存储在数据库中的媒体片段。
9.在一些实现方式中，该方法可以包括由数据处理系统将多个指纹存储在数据库中。在一些实现方式中，该方法可以包括从数据库检索第二多个指纹。
10.在一些实现方式中，该方法可以包括由数据处理系统接收包括第三多个帧的第三媒体流。在一些实现方式中，该方法可以包括：对于第三多个帧中的每一个，由数据处理系统基于指纹窗口值从第三多个帧中选择第四多个帧。在一些实现方式中，该方法可以包括：对于第三多个帧中的每一个，由数据处理系统对第四多个帧中的每一个进行散列以创建第二多个散列。在一些实现方式中，该方法可以包括：对于第三多个帧中的每一个，由数据处理系统截断第二多个散列中的每一个，以生成第二多个被截断的散列。在一些实现方式中，该方法可以包括：对于第三多个帧中的每一个，由数据处理系统将第二多个截断的散列级
联以计算第二帧指纹值。在一些实现方式中，该方法可以包括：由数据处理系统聚合每个第二帧指纹值以组装第二组多个指纹，每个第二帧指纹值与与第三多个帧中的各个帧相对应的时间戳相关联。
11.在一些实施方案中，所述方法可包含使用局部敏感的散列算法来散列第二多个帧中的每一个。在一些实现方式中，第二媒体流与第一媒体流相同。在一些实现方式中，该方法可以包括由数据处理系统计算目标指纹与第二多个指纹中的每个指纹之间的相似度值。
12.在一些实现方式中，该方法可以包括由数据处理系统确定相似度值是否等于或大于相似度阈值。在一些实现方式中，该方法可以包括：响应于相似度值等于或大于相似度阈值，由数据处理系统确定与第二媒体流中的位置相对应的匹配位置。
13.在一些实现方式中，该方法可以包括由数据处理系统基于下边界时间戳和上边界时间戳从第二多个指纹中提取第五多个指纹。在一些实现方式中，该方法可以包括由数据处理系统将第五多个指纹存储在数据库中。在一些实现方式中，该方法可以包括由数据处理系统提供第五多个指纹。
14.本公开的至少另一个方面针对一种用于基于帧指纹提取匹配媒体片段的系统，该系统包括具有一个或多个处理器的数据处理系统。数据处理系统可以接收包括多个帧的媒体流。数据处理系统可以针对多个帧中的每个，基于指纹窗口值从多个帧中选择第二多个帧。对于多个帧中的每个帧，数据处理系统可以对第二多个帧中的每个帧进行散列以创建多个散列。对于多个帧中的每个帧，数据处理系统可以截断多个散列中的每个散列，以生成多个截断的散列。对于多个帧中的每个帧，数据处理系统可以将多个截断的散列级联起来以计算帧指纹值。数据处理系统可以聚合每个计算出的帧指纹值以组装多个指纹，每个计算出的帧指纹值与对应于多个帧中的各个帧的时间戳相关联。数据处理系统可以将每个计算出的帧指纹值与多个帧中的相应帧相关联。数据处理系统可以接收与多个帧中的目标帧相对应的目标时间戳。数据处理系统可以基于目标时间戳和指纹窗口值来确定多个指纹中的目标指纹。数据处理系统可以检索第二多个指纹，第二多个指纹中的每个与第二媒体流中的帧相关联。数据处理系统可以将目标指纹与第二多个指纹中的每个指纹进行比较，以确定与第二媒体流中的位置相对应的匹配位置。数据处理系统可以将与小于目标时间戳的时间戳相关联的多个指纹中的第一指纹与第二多个指纹中的第二指纹进行匹配，以确定下边界时间戳。数据处理系统可以将与大于目标时间戳的时间戳相关联的多个指纹中的第三指纹与第二多个指纹中的第四指纹进行匹配，以确定上边界时间戳。数据处理系统可以提供媒体片段以存储在数据库中。
15.在一些实现方式中，数据处理系统还被配置为将多个指纹存储在数据库中。在一些实现方式中，数据处理系统还被配置为从数据库检索第二多个指纹。
16.在一些实现方式中，数据处理系统还被配置为接收包括第三多个帧的第三媒体流。在一些实现方式中，数据处理系统还被配置为针对第三多个帧中的每一个，基于指纹窗口值从第三多个帧中选择第四多个帧。在一些实现方式中，数据处理系统还被配置为针对第三多个帧中的每一个，对第四多个帧中的每一个进行散列以创建第二多个散列。在一些实现方式中，数据处理系统还被配置为针对第三多个帧中的每一个，截断第二多个散列中的每个散列以生成第二多个截断的散列。在一些实现方式中，数据处理系统还被配置为针对第三组多个帧中的每个帧，将第二组多个截断的散列连接起来以计算第二帧指纹值。在
一些实现方式中，数据处理系统还被配置为聚合每个第二帧指纹值以组装第二组多个指纹，每个第二帧指纹值与对应于第三组多个帧中的各个帧的时间戳相关联。
17.在一些实现方式中，数据处理系统还被配置为使用局部敏感散列算法来散列第二多个帧中的每一个。在一些实现方式中，第一媒体流与第二媒体流相同。在一些实现方式中，数据处理系统还被配置为计算目标指纹与第二多个指纹中的每个指纹之间的相似度值。
18.在一些实现方式中，数据处理系统还被配置为确定相似度值是否等于或大于相似度阈值。在一些实现方式中，数据处理系统还被配置为响应于相似度值等于或大于相似度阈值来确定与第二媒体流中的位置相对应的匹配位置。
19.在一些实现方式中，所述数据处理系统还被配置为基于所述下边界时间戳和所述上边界时间戳从所述第二多个指纹中提取第五多个指纹。在一些实现方式中，数据处理系统还被配置为将第五多个指纹存储在数据库中。在一些实现方式中，数据处理系统还被配置为提供第五多个指纹。
20.这些和其他方面以及实现将在下面详细讨论。前述信息和以下详细描述包括各个方面和实现方式的说明性示例，并且提供用于理解所要求保护的方面和实现方式的性质和特征的概述或框架。附图提供了对各个方面和实现方式的说明和进一步的理解，并且被并入本说明书中并构成本说明书的一部分。可以组合各方面，并且将容易理解，在本发明的一方面的上下文中描述的特征可以与其他方面组合。各方面可以以任何方便的形式实现。例如，通过适当的计算机程序，其可以在适当的载体介质(计算机可读介质)上携带，该载体介质可以是有形的载体介质(例如，磁盘)或无形的载体介质(例如，通信信号)。各方面也可以使用合适的设备来实现，该设备可以采取运行被布置为实现该方面的计算机程序的可编程计算机的形式。
附图说明
21.附图无意按比例绘制。在各个附图中，相似的附图标号和标记指示相似的元件。为了清楚起见，并非在每个附图中都标记了每个组件。在附图中：
22.图1示出了描述用于基于指纹匹配来对媒体片段进行帧精确提取的示例环境的框图。
23.图2示出了基于指纹匹配的媒体片段的帧精确提取的示例方法的流程图。
24.图3示出了为媒体流中的帧生成指纹值的示例方法的流程图。
25.图4示出了使用两组媒体指纹来确定匹配媒体片段的下边界的示例方法的流程图。
26.图5示出了使用两组媒体指纹来确定匹配媒体片段的上边界的示例方法的流程图。
27.图6示出了图示基于媒体流中的帧的指纹值的示例生成的图。
28.图7示出了图示使用两组媒体指纹来确定匹配媒体片段的上边界和下边界的示例的图。
29.图8示出了可以用来实现本文讨论的任何计算机的说明性计算机系统的总体架构。
30.具体实现方式
31.以下是与用户标识符集合的交集的隐私保护确定的方法、装置和系统有关的各种概念以及其实现的各种详细描述。由于所描述的概念不限于任何特定的实现方式，因此可以以多种方式中的任何一种来实现上面介绍的以及下面将更详细讨论的各种概念。
32.图1描绘了基于帧准确的指纹比较来提取媒体片段的系统或环境100。环境100可以包括至少一个计算机网络110。网络110可以是计算机网络，其可以包括一个或多个局域网、广域网、专用网络、公共网络和因特网。环境100可以包括至少一个媒体源150。环境100可以包括至少一个数据处理系统105。环境100可以包括至少一个数据库115。数据处理系统105可以包括至少一个帧选择器120。数据处理系统105可以包括至少一个帧散列器125。数据处理系统105可以包括至少一个指纹计算器130。数据处理系统105可以包括至少一个目标帧匹配器135。数据处理系统105可以包括至少一个边界计算器140。数据处理系统105可以包括至少一个片段提取器145。在一些实现方式中，数据处理系统105可以包括媒体源150。在一些实现方式中，数据处理系统105可以包括数据库115。
33.系统100的每个组件(例如，数据处理系统105的网络110，数据库115，帧选择器120，帧散列器125，指纹计算器130，目标帧匹配器135，边界计算器140和片段提取器145和媒体源150)可以使用本文结合图8详细描述的计算系统800的组件来实现。例如，数据处理系统105可以包括服务器或其他计算设备。媒体源150还可以包括服务器或其他计算设备。数据处理系统105的每个组件可以执行本文详述的功能。
34.媒体源150可以获取、接收或识别媒体流(在本文中有时通常称为流)。每个媒体流可以包括至少一个媒体帧(在本文中有时通常称为帧)，其可以是视频流的帧，例如mpeg
‑
4h.264视频。该帧可以包括视频信息、音频信息和隐藏字幕信息。可以使用视频编解码器(例如，h.263，h.264，hevc，mpeg4，theora，3gp，windows media 8，quicktime，mpeg
‑
4，vp8，vp6，mpeg1，mpeg2或mpeg
‑
ts等)对视频信息进行编码。可以使用音频编解码器(例如，mp3，aac，he
‑
aac，ac3，eac3，vorbis，wma或pcm等)对音频信息进行编码。可以使用隐藏字幕格式(例如，webvtt，cea
‑
608，cea
‑
708，dfxp，sami，scc，srt，ttml或3gpp等)来对隐藏字幕信息进行编码。每个帧可以包括与其在媒体流中的位置相对应的时间戳。媒体流每单位时间可以具有固定数量的帧，例如每秒24帧。媒体流可以是自适应位率流。媒体流可以是实况视频流，例如因特网视频流，或者实况电视流。可以从由电缆提供商提供服务的电缆端点、由卫星服务提供商提供服务的卫星天线或电视天线接收实况电视流。在一些实现方式中，媒体源150可以从一个或多个媒体源(例如，因特网、电缆连接、卫星连接、无线电广播和/或电视广播等)接收媒体流。在一些实现方式中，媒体源160可以从数据库115检索一个或多个媒体流。
35.由媒体源150获取的媒体流的每个帧还可以包括索引值(例如，时间或序列号)。索引值可以对应于媒体流中包括的帧的顺序。在一些实现方式中，索引值可以对应于媒体源150接收帧的时间。媒体源150可以生成时间索引并将其与每个媒体流中的每个帧相关联。可以将帧存储在例如结构化模板中，计算机系统中由某些值填充的内存区域或通用数据结构(例如类或c类结构)中。在一些实现方式中，除了接收媒体流中的数据之外，媒体源150还可以解码媒体流中的信息。在一些实现方式中，媒体源150可以生成包括一个或多个帧的至少一个媒体流。例如，媒体源150可以是与配置为记录视频和音频的照相机传感器耦合的计
算系统。在该示例中，媒体源150可以生成媒体流，该媒体流包括具有视频和音频信息的帧，每个帧与时间戳相关联。
36.媒体源150可以经由网络110将媒体流的帧发送到数据处理系统105以进行处理。在一些实现方式中，媒体源150可以以连续流发送媒体流的帧。在一些实现方式中，媒体源150可以以规则的时间间隔(例如，每毫秒一帧)提供媒体流的帧。在一些实现方式中，媒体源150可以按照可变的时间间隔调度来发送帧。在一些实现方式中，媒体源150可以突发地将媒体流提供给数据处理系统。突发可以包括许多帧，每个帧对应于一个时间戳和/或索引值。在一些实现方式中，媒体源150可以经由通信接口将数据直接发送到数据处理系统105。在一些实现方式中，媒体源150可以基于与时间无关的调度来提供帧。
37.帧选择器120可以经由网络110从媒体源150接收帧。随着帧的接收，帧选择器可以将帧存储和维护在计算机可读存储装置(例如数据库115)上。帧选择器120可以将帧存储和维护在临时缓冲器中。临时缓冲器可以在计算机存储装置上创建，例如数据库115或结合图8的存储器825。帧选择器120还可以经由网络访问数据库115，以检索一个或多个帧以进行处理。帧选择器120可以基于指纹窗口值来存储和选择帧。在一些实现方式中，帧选择器120可以存储足够的帧以满足指纹窗口值的选择要求。指纹窗口值可以是预先确定的，可以通过网络110从另一个计算设备接收，或者可以从数据处理系统105的组件中接收。指纹窗口值可以用于确定媒体流中要选择哪些帧来生成指纹用于媒体流中的相应帧。例如，指纹窗口值可以是时间值，其指示应当在相对于各个帧的特定时间段内选择帧。指纹窗口值可以是计数器值，指示应该在相应帧之前或之后从媒体流中选择一定数量的帧。指纹窗口值可以是间隔值，指示如果帧对应于满足间隔条件的时间戳(例如，每25毫秒一次)，则应选择该帧。帧选择器120可以从经由网络110从媒体源150接收的媒体流中选择一个或多个帧。
38.对于媒体源150接收到的每个帧，帧选择器120可以从媒体流中选择代表由指纹窗口值指示的时间段的一组帧。例如，如果指纹窗口值为三秒，则帧选择器120可以针对从媒体源150接收的每个帧在三之内选择预定数量的帧。帧选择器150可以将所选择的帧以数据结构存储在易失性或非易失性计算机存储器中，例如数据库115或结合图8的存储器825。在一些实现方式中，帧选择器120可以从媒体源150选择帧。媒体流的每个帧的所选帧可以由帧选择器120以单独的数据结构存储在计算机存储器中。在一些实现方式中，可以通过帧选择器120将媒体流的每个帧的所选帧以单个的数据结构存储在计算机存储器中。存储的选择的帧与从媒体源150接收的媒体流的相应帧相关联，例如，使用时间戳、帧索引值、或者在数据结构或计算机存储器中的某个位置进行编码。
39.帧散列器125可以散列由媒体源150接收的一个或多个帧，或者从计算机存储器(例如数据库115)中检索到的一个或多个帧。散列帧125可以散列由帧选择器120选择的一个或多个帧。帧选择器120可以向帧散列器125提供一个或多个选择的帧。帧散列器125可以使用一个或多个散列算法来散列帧，例如局部敏感散列算法。帧散列器125可以选择局部敏感散列算法，以允许数据处理系统105比较两个散列的帧。例如，可以选择局部敏感散列算法以允许数据处理系统105计算两个帧之间的相似度值。帧散列器125可以使用位采样作为局部敏感散列算法。帧散列器125可以使用最小方向独立排列局部敏感散列算法。帧散列器125可以使用其他类型的局部敏感散列算法，例如随机投影方法。帧散列器125可以使用传统的散列算法来散列帧(例如，sha
‑
1，sha
‑
2，md5等)。
40.对于由帧选择器120选择的每个帧，帧散列器可以使用散列算法来创建散列帧。创建的散列帧可以具有固定的位宽度(例如8位、16位、32位、64位等)。在一些实现方式中，创建的散列帧可以具有可变的位宽。在一些实现方式中，帧散列器125可以在应用散列算法以创建对应的散列帧之前对帧进行解码或预处理。例如，在将散列算法应用于原始帧信息以创建散列帧之前，帧散列器125可以使用对应的编解码器对帧进行解码以访问原始帧信息。帧散列器125可以解码和散列包括在帧中的音频信息、视频信息和/或隐藏字幕信息，和/或散列包括在帧中的音频信息、视频信息和/或隐藏字幕信息作为不同的散列。帧散列器125可以创建散列并将其存储在计算机存储器中，例如在数据库115或结合图8的存储器825中。帧散列器125可以将散列的帧以存储在数据结构中，例如，类似c的数据结构或计算机存储器的区域中。帧散列器125可以将散列的帧存储在缓冲器中，该缓冲器可以是用于存储数据的计算机存储器的临时区域。帧散列器125可以将每个散列帧与相应的时间戳、索引值或定位数据相关联，以指示散列帧在相应的媒体流中的位置。帧散列器125可以将散列的帧提供给指纹计算器130。
41.指纹计算器130可以计算包括在媒体流中的一个或多个帧的指纹。例如，指纹计算器130可以处理从帧散列器125接收的一个或多个散列以计算与一个或多个帧所属的媒体流中的时间段相对应的指纹。指纹计算器130可以为从媒体源150接收的媒体流中的每个帧计算指纹。在一些实现方式中，指纹计算器130可以基于从例如结合图8中的数据库115或存储器825之类的计算机存储器中检索到的一个或多个成帧散列来计算指纹。指纹计算器130可以将每个计算出的指纹例如以数据结构存储在计算机存储器中。指纹计算器130可以将计算出的指纹或包括一个或多个计算出的指纹的数据结构存储在计算机存储器中，例如数据库115或结合图8的存储器825中。
42.指纹计算器130可以截断由与由帧选择器120选择的帧相对应的帧散列器125创建的每个散列帧，以生成截断的散列帧。截断散列帧可以包括在散列帧中选择固定范围的位，例如8个最低有效位。截断散列帧可以包括将截断的位以数据结构存储在计算机存储器中，例如数据库115或结合图8的存储器825。例如，如果一个散列帧具有二进制值01100100，则指纹计算器可以通过选择四个最高有效位(在本例中为0110)截断该散列帧。截断该散列帧可以减小该散列帧的整体尺寸，同时仍保留足够的信息以进行进一步处理，这是对其他实现的改进。在一些实现方式中，指纹计算器130可以跳过执行截断步骤，而是将整个散列帧用于进一步处理。在一些实现方式中，截断散列帧可以包括选择散列帧中的位的任何组合以生成截断的散列。例如，如果散列帧具有二进制值00110001，则指纹计算器130可以选择位置6、4、2和0中的每个位以生成具有值0101的截断的散列帧。指纹计算器130可以进一步处理截断的散列帧以计算帧指纹值。
43.指纹计算器130可以将与由帧选择器120选择的每个帧相对应的截断的散列帧进行级联，以计算与媒体流中的时间段相对应的帧指纹值。在一些实现方式中，指纹计算器130可以访问计算机存储器以检索一个或多个截断的散列帧以计算指纹值。帧选择器120选择的每个帧可以对应于媒体流中的时间段。散列、截断和级联每个选定的帧可以减少每个帧中数据的尺寸，而无需牺牲计算每个帧之间的相似度值所需的信息。这样，可以以比其他实现计算效率高得多的方式比较帧。此外，与发送整个媒体流以进行比较相比，传输级联、截断和散列的帧可能会使用明显更少的网络带宽，这是对其他实现的改进。指纹计算器130
可以为从媒体源150接收的媒体流中的每个帧计算指纹。指纹可以对应于时间窗，例如三秒。在该示例中，每个指纹可以对应于媒体流中的每个帧之后的时间窗口(例如，滑动窗口)，该时间窗口等于大约三秒。
44.尽管三秒钟的媒体信息会占用计算机内存的很大一部分，但从窗口中仅选择几个帧，对每个选定的帧应用散列算法，并截断与该窗口相对应的每个散列，可以大大减少媒体信息的存储要求。如果使用局部敏感散列算法，则可以将媒体信息与其他指纹进行比较以计算相似度值，该相似度值指示包括在两组帧中的媒体信息的相似度。指纹计算器130可以通过将每个被截断的散列帧级联在一起成为单个值来计算与媒体信息窗口相对应的最终指纹。例如，如果从媒体流中的时间窗口中选择了三个帧，并且它们的截断的散列值等于0110、0101和1000，则指纹计算器130可以将这些值中的每一个级联起来以生成指纹值011001011000。尽管在该示例中，帧被示出为以特定顺序被级联，但是应当理解的是，每个被截断的散列帧可以以任何组合或排列来级联。指纹计算器130可以将每个指纹值与时间戳或索引值相关联，以指示指纹所对应的媒体流中的位置。
45.指纹计算器130可以将计算出的每个指纹值存储在计算机存储器中，例如数据库115或结合图8的存储器825。指纹值可以存储在计算机内存中的数据结构中。数据结构可以包括与指纹中最早的帧相对应的时间戳，以及指定指纹所对应的时间窗口的值。数据结构还可以包括指示窗口在相应媒体流中的位置的时间信息。指纹计算器130可以在单个数据结构中将每个计算出的指纹值聚合在一起。例如，指纹计算器139可以根据从媒体源150接收的实况媒体流来连续计算指纹。在一些实现方式中，指纹计算器130可以随着每个指纹被计算而连续不断更新包括与媒体流相对应的指纹的数据结构。可以在计算机内存中连续地访问和更新数据结构，例如在数据库115中或结合图8的存储器825中。
46.目标帧匹配器135可以接收与媒体流(例如，由媒体源150接收的媒体流)中的目标帧相对应的目标时间戳。在一些实现方式中，目标时间戳可以包括时间戳对应的目标媒体流的指示。目标时间戳可以是与目标媒体流中的时刻相对应的相对时间值。目标时间戳可以是与目标媒体流中的目标帧相对应的索引值。目标帧匹配器135可以接收包括在与另一候选媒体流或另一操作进行比较的请求中的目标时间戳。目标帧匹配器135可以接收包括相应目标媒体流的指示符的目标时间戳。目标时间戳可以对应于已被指纹计算器130指纹识别的目标媒体流中的帧。目标帧匹配器135可以将目标时间戳以数据结构存储在计算机内存中，例如数据库115或结合图8的存储器825中。目标帧匹配器135可以经由网络110例如从外部计算设备接收目标时间戳。在一些实现方式中，目标帧匹配器135可以从媒体源150接收目标时间戳。
47.目标帧匹配器135可以确定与目标时间戳相对应的目标指纹和目标帧匹配器135接收的指示的目标媒体流。目标帧匹配器135可以访问计算机内存以检索对应于媒体流的一个或多个指纹以确定目标指纹。例如，目标帧匹配器135可以访问数据库115，该数据库115可以包含包括通过时间戳索引的指纹的数据结构。在该示例中，目标帧匹配器可以通过以等于由目标帧匹配器135接收到的目标时间戳的索引值访问数据库条目来确定目标指纹。在一些实现方式中，可以通过不同的值来对指纹进行索引。目标帧匹配器可以搜索包含与目标媒体流相对应的指纹的数据结构，以确定哪个指纹具有最接近目标时间戳或索引值的对应时间戳或索引值。在一些实现方式中，目标时间戳或索引值可以对应于覆盖包括目
标时间戳的时间段的指纹。在一些实现方式中，目标帧匹配器135可以将目标指纹确定为其代表时间段(例如，窗口)被目标时间戳最紧密地平分的指纹。例如，如果目标时间戳指示距媒体流的第一帧正好十秒的帧，则目标帧匹配器135可以将目标指纹确定为代表媒体流的8.5秒至11.5秒(例如，指纹的窗口值为3秒)的时间段的指纹。在该示例中，目标帧匹配器135将目标指纹确定为其窗口被与目标时间戳相对应的帧平分的指纹，因为10秒恰好介于8.5秒和11.5秒之间。
48.目标帧匹配器135可以访问计算机存储器以检索指纹的候选集合。在一些实现方式中，指纹的候选集合对应于候选媒体流。在一些其他实现中，指纹的候选集合可以对应于由目标时间戳指示的目标媒体流。以此方式，数据处理系统105可以从不同的媒体流和相同的媒体流计算匹配的指纹值，并且利用观察到的感兴趣片段可以在一个或多个媒体流上重复的观察的优势。在一些实现方式中，指纹候选集合可以由指纹计算器130基于媒体源150接收的候选媒体流来生成。目标帧匹配器135可以从数据库(例如数据库115)检索指纹候选集合。在一些实施方案中，目标帧匹配器135可从计算机内存(例如，结合图8的存储器825)检索指纹的候选集合。指纹候选集合中的每个指纹可以对应于媒体流(例如，由媒体源150接收的媒体流)中的帧和时间窗口。指纹候选集合合中的指纹可以由时间戳值、对应于相关帧在相应媒体流中位置的索引值或其他值来索引。目标帧匹配器135可以将检索到的指纹候选集合存储在计算机存储器中以进行进一步处理，例如在结合图8的存储器825或数据库115中。
49.目标帧匹配器135可以将基于目标时间戳确定的目标指纹与指纹候选集合的每个进行比较，以确定候选媒体流中的匹配位置。匹配位置可以指示目标指纹所指示的时间窗口中的帧已在候选媒体流中重复。在一些实现方式中，候选媒体流可以与目标指纹所指示的目标媒体流相同，但是处于不同的时间段。以此方式，数据处理系统105可以识别已经在相同媒体流或在一个或多个不同媒体流中重复的匹配指纹。当与目标指纹比较时，目标帧匹配器135可以通过为指纹候选集合的每个计算相似度值(例如，汉明距离，其他的基于局部的散列距离值等)来确定位置。如果目标帧匹配器135确定目标指纹与指纹候选集合中的帧之一之间的相似度值大于或等于预定相似度阈值，则目标帧匹配器135可以访问与指纹候选集合中的相应指纹对应的时间戳的值。如果目标帧匹配器135确定相似度值小于预定的相似度阈值，则目标帧匹配器135可以继续计算与候选媒体流相关联的其他指纹的相似度值。在一些实现方式中，如果目标帧匹配器135确定在指纹候选集合中没有匹配的指纹，则目标帧匹配器可以从数据库115或其他计算机存储器(例如结合图8的存储器825)一起检索另一指纹候选集合。
50.匹配时间戳的值可以是与对应于指纹候选集合的候选媒体流中的帧的索引相对应的索引值。索引值可以是指示指纹在候选媒体流中的位置的值。例如，索引值为零可以指示指纹与候选媒体流中的第一帧相对应，索引值为1可以指示指纹与媒体流中的第二帧相对应，依此类推。匹配时间戳的值还可以指示帧出现在候选媒体流中的确切时间。匹配时间戳的值可以是相对时间值(例如，第一帧的相对时间戳为零)，或者时间戳的值可以是绝对时间(例如，数据处理系统105上保持的一天中的时间，保持在媒体源150上的日期时间值，或对应的帧出现在广播中的一天中的绝对时间等)，匹配的指纹窗口出现在候选媒体流中。
51.边界计算器140可以枚举与候选时间戳之前和之后的候选媒体流中的帧相对应的
候选指纹，以进一步与目标媒体流进行比较。边界计算器140还可以枚举与目标媒体流中的目标时间戳之前和/或之后的帧相对应的指纹。目标帧匹配器135接收的目标时间戳可以对应于感兴趣片段中的帧。边界计算器140可以通过比较目标媒体流和候选媒体流中的指纹来计算感兴趣片段的上边界和下边界。
52.边界计算器140可以将目标媒体流的指纹中的至少一个与候选媒体流的指纹中的至少一个进行匹配，以确定感兴趣的片段的下边界时间戳。边界计算器140可以访问候选媒体流中紧接在由目标帧匹配器135确定的匹配帧之前的帧的候选指纹。边界计算器140可以从计算机存储器(例如数据库115或结合图8的存储器824)访问候选指纹。边界计算器140可以访问目标媒体流中紧接在由目标帧匹配器135确定的目标帧之前的帧中的指纹。边界计算器140可以通过访问计算机存储器(例如数据库115或结合图8的存储器825)来访问指纹。一旦访问候选指纹和目标媒体流的指纹，边界计算器140就可以比较两个指纹以确定下边界时间戳。在一些实现方式中，比较两个指纹包括计算指纹相似度值(例如，汉明距离，其他基于局部的散列距离值等)。如果指纹相似度值大于或等于预定阈值，则边界计算器140可以确定两个指纹足够相似。如果相似度值小于预定阈值，则边界计算器140可以确定两个指纹不是足够相似。在一些实现方式中，边界计算器140可以确定两个指纹如果不完全匹配则不足够相似。如果边界计算器140确定两个指纹足够相似，则边界计算器可以访问候选媒体流和目标媒体流中的每一个中紧接在所比较的指纹之前的指纹，并且执行比较，如本文所详述。以此方式，边界计算器140可以比较两个媒体流中从匹配位置开始并在流的开始处结束的每个帧，直到发生不匹配或已经达到至少一个流的开始为止。当两个媒体流的两个指纹不足够相似时，或者当到达候选媒体流或目标媒体流的开始时，就会发生不匹配。
53.如果边界计算器140确定发生了不匹配，则边界计算器140可以检索与先前匹配的比较中使用的候选指纹相对应的时间戳。边界计算器140可以从数据结构中检索时间戳，该数据结构包括候选指纹，该候选指纹被确定足够类似于来自计算机存储器(例如数据库115或结合图8的存储器825)的目标媒体流。因为边界计算器140已经确定两个流之间已经发生了不匹配，所以感兴趣的片段(例如，跨两个或多个媒体流重复的片段)可以在由包含在最后匹配的指纹中的时间戳指示的帧处开始。通过访问最后匹配指纹的时间戳，边界计算器可以确定候选媒体流中感兴趣片段的下边界。在一些实现方式中，边界计算器140可以通过访问与目标媒体流中的最后匹配指纹相关联的时间戳来计算下边界。
54.边界计算器140可以将目标媒体流的至少一个指纹与候选媒体流的至少一个指纹进行匹配，以确定至少一个媒体流中的感兴趣片段的上边界时间戳。边界计算器140可以访问紧跟在目标帧匹配器135确定的匹配帧之后的候选媒体流中的帧的候选指纹。边界计算器140可以从计算机存储器(例如数据库115或结合图8的存储器824)访问候选指纹。边界计算器140可以访问紧接在由目标帧匹配器135确定的目标帧之后的目标媒体流中的帧的指纹。边界计算器140可以通过访问计算机存储器(例如数据库115或结合图8的存储器825)来访问指纹。一旦访问候选指纹和目标媒体流的指纹，边界计算器140就可以比较两个指纹以确定上边界时间戳。在一些实现方式中，比较两个指纹包括计算指纹相似度值(例如，汉明距离，其他基于局部的散列距离值等)。如果指纹相似度值大于或等于预定阈值，则边界计算器140可以确定两个指纹足够相似。如果相似度值小于预定阈值，则边界计算器140可以确定两个指纹不是足够相似。在一些实现方式中，边界计算器140可以确定两个指纹如果不
完全匹配则不足够相似。如果边界计算器确定两个指纹足够相似，则边界计算器可以访问在候选媒体流和目标媒体流的每一个中紧随比较的指纹之后的指纹，并执行如本文中详述的比较。以这种方式，边界计算器140可以比较两个媒体流中从匹配位置开始并终止于流的最后一帧的每一帧，直到发生不匹配为止，或者已经到达至少一个流的最后一帧。当两个媒体流的两个指纹不足够相似时，或者当到达候选媒体流或目标媒体流的最后一个帧时，就会发生不匹配。
55.如果边界计算器140确定发生了不匹配，则边界计算器140可以检索与先前匹配的比较中使用的候选指纹相对应的时间戳。边界计算器140可以从数据结构中检索时间戳，该数据结构包括被确定为与来自计算机存储器(例如数据库115或结合图8的存储器825)的目标媒体流充分相似的候选指纹。因为边界计算器140已经确定两个流之间已经发生了不匹配，所以感兴趣的片段(例如，跨两个或更多个媒体流重复的片段)可以在由包括在最后匹配的指纹中的时间戳指示的帧处结束。通过访问最后匹配指纹的时间戳，边界计算器可以确定候选媒体流中感兴趣片段的上边界。在一些实现方式中，边界计算器140可以通过访问与目标媒体流中的最后匹配指纹相关联的时间戳来计算上边界。
56.片段提取器145可以基于下边界时间戳和上边界时间戳来提取感兴趣片段。上边界时间戳和下边界时间戳可以对应于候选媒体流或目标媒体流。在一些实现方式中，候选媒体流和/或目标媒体流的帧被存储在计算机存储器中，例如数据库115或结合图8的存储器825。在一些实现方式中，片段提取器145可以访问具有时间戳值的所有帧，该时间戳值包括由边界计算器140确定的下边界时间戳值和上边界时间戳值并处于由边界计算器140确定的下边界时间戳值和上边界时间戳值之间。片段提取器145可以检索所访问的帧，以组装已基于一个或多个媒体流中的重复帧提取的感兴趣的帧精确片段。在一些实现方式中，片段提取器145可以使用包括并处于在边界计算器140确定的下边界和上边界时间戳值之间的时间戳值来访问所有指纹值。片段提取器145可以检索所访问的指纹以便组装已基于一个或多个媒体流中的重复指纹来提取的帧准确的感兴趣片段。片段提取器145可以基于检索到的帧或检索到的指纹值来组装感兴趣片段。
57.片段提取器145可以提供所提取的媒体片段以存储在数据库中，例如数据库115中。所提取的媒体片段可以是一个或多个帧，或者是表示感兴趣片段中的帧的一个或多个指纹值。在一些实现方式中，片段提取器145可以经由网络110将感兴趣的片段发送到第三方，例如，发送到第三方计算设备。在一些实现方式中，片段提取器145可以经由网络110将提取的感兴趣片段提供给媒体源150。在一些实现方式中，提供感兴趣片段可以包括提供感兴趣片段的一个或多个媒体帧。在一些实现方式中，提供感兴趣的片段可以包括提供与感兴趣的片段的一个或多个帧相对应的一个或多个指纹。在一些实现方式中，提供感兴趣的片段可以包括为感兴趣的片段中包括的每个帧和/或指纹提供时间戳。在一些实现方式中，提供感兴趣片段可以包括关于感兴趣片段的元数据(例如，持续时间、内容、包含片段的媒体流、与该片段相对应的绝对时间戳、与时间戳相对应的相对时间戳等)。在一些实现方式中，提供感兴趣的片段可以包括以数据结构将与感兴趣的片段相关联的元数据，指纹和/或帧存储在计算机内存中，例如数据库115或结合图8的存储器825。
58.现在参考图2，描绘了用于基于指纹匹配的媒体片段的帧精确提取的方法的流程图。方法200可以使用上文结合图1中所述的数据处理系统105或下面结合图8所述的计算机
系统800来实现或执行。简要概述，数据处理系统可以从媒体流接收帧(202)。数据处理系统可以为每个帧生成指纹(204)。数据处理系统可以聚合指纹(206)。数据处理系统可以接收目标时间戳(208)。数据处理系统可以确定目标指纹(210)。数据处理系统可以检索候选多个指纹(212)。数据处理系统可以确定是否找到了匹配的指纹(214)。数据处理系统可以匹配指纹以确定上边界和下边界(216)。数据处理系统可以提取媒体片段(218)。数据处理系统可以提供媒体片段(220)。
59.数据处理系统(例如，数据处理系统105)可以从媒体流接收帧(202)。数据处理系统可以从至少一个媒体源(例如，媒体源150)接收一个或多个媒体流中包括的一个或多个媒体帧。每个媒体流可以包括至少一个媒体帧(有时在本文中通常称为帧)，它可以是例如mpeg
‑
4h.264视频的视频流的帧。该帧可以包括视频信息、音频信息和隐藏字幕信息。可以使用视频编解码器(例如，h.263，h.264，hevc，mpeg4，theora，3gp，windows media 8，quicktime，mpeg
‑
4，vp8，vp6，mpeg1，mpeg2，mpeg
‑
ts等)对视频信息进行编码。可以使用音频编解码器(例如，mp3，aac，he
‑
aac，ac3，eac3，vorbis，wma，pcm等)对音频信息进行编码。可以使用隐藏字幕格式(例如，webvtt，cea
‑
608，cea
‑
708，dfxp，sami，scc，srt，ttml，3gpp等)对隐藏字幕信息进行编码。每个帧可以包括与其在媒体流中的位置相对应的时间戳。媒体流每单位时间可以具有固定数量的帧，例如每秒24帧。媒体流可以是自适应位率流。媒体流可以是实况视频流，例如因特网视频流，或者实况电视流。可以从由电缆提供商提供服务的电缆端点、由卫星服务提供商提供服务的卫星天线或电视天线接收实况电视流。数据处理系统可以经由通信接口，例如网络或通信总线，接收一个或多个帧。
60.数据处理系统(例如，数据处理系统105)可以为每个帧生成指纹(204)。数据处理系统可以例如使用结合图3的方法204来执行基于窗口值为每个媒体帧生成指纹所必需的步骤。图6示出了该过程的示例图。在一些实现方式中，窗口值可以是与出现在相应的媒体流中的帧之前或之后的时间段相对应的值。例如，窗口值可以是一段时间(例如，所选帧之后的3秒)，帧的数量(例如，在所选帧之前的媒体流的300个帧)或包括选定的帧的媒体流的片段。媒体流的每个窗口可以对应于媒体流中的单个帧，并且媒体流中的每个帧可以与对应的帧窗口相关联。为每个帧生成的指纹可以基于与其关联的帧窗口。帧的窗口(例如，滑动窗口)可以基于预定值，或者通过媒体流被提供。
61.数据处理系统(例如，数据处理系统105)可以聚合指纹(206)。在一些实现方式中，可以在将指纹聚合为代表媒体流的最终数据结构之前，对其进行计算。在一些实现方式中，与媒体流相对应的指纹可以在由数据处理系统计算时被组装成计算机内存(例如，数据库115)中的数据结构。数据处理系统可以周期性地更新可以包括一个或多个指纹值的数据结构。在一些实现方式中，聚合一个或多个指纹值可以包括将每个指纹值与对应的时间戳相关联。时间戳可以对应于与指纹相关联的帧，例如帧时间戳或帧索引。帧时间戳可以是绝对时间戳(例如，帧出现在媒体流中的时间)、相对时间戳(例如，当帧出现时进入媒体流的时间量)或帧索引值(例如，按其出现顺序排列的帧列表中的帧编号)。数据结构还可以包括与每个指纹关联的时间戳值。
62.数据处理系统(例如，数据处理系统105)可以接收目标时间戳(208)。目标时间戳可以对应于目标媒体流中的特定时刻。目标媒体流可以包括一个或多个帧，并且每个帧可以包括对应的时间戳。目标时间戳可以是与目标媒体流中的由索引值索引的帧列表相对应
的索引值。目标时间戳可以是相对时间戳，其对应于媒体流中第一帧之后的时间段。例如，目标时间戳可以是5秒，这意味着与目标媒体流的第五秒相对应的帧。目标时间戳可以是绝对时间戳，其对应于正在播放目标媒体流(例如实况媒体流)时的绝对时刻。数据处理系统可以经由网络从外部计算设备接收目标时间戳。在一些实现方式中，数据处理系统可以从用户输入接收目标时间戳。
63.数据处理系统(例如，数据处理系统105)可以确定目标指纹(210)。数据处理系统可以搜索在步骤(204)中生成的一个或多个指纹，以确定哪个指纹与在步骤(208)中接收到的目标时间戳相对应。每个指纹可以对应于目标时间戳指示的目标媒体流中的帧。在一些实现方式中，每个指纹可以与对应于目标媒体流中的各个帧的时间戳相关联。在一些实现方式中，每个指纹可以与索引值相关联，该索引值对应于媒体流中的帧出现的顺序。数据处理系统可以搜索与目标媒体流相关联的指纹，并将各个相关联的时间戳与在步骤(208)中接收到的目标时间戳进行比较。在一些实现方式中，如果数据处理系统与最接近目标时间戳的时间戳相关联，则数据处理系统可以从指纹中选择目标指纹。在一些实现方式中，数据处理系统可以确定目标指纹的索引值。在一些实现方式中，指纹的时间戳必须与要选择作为目标指纹的目标时间戳完全匹配。
64.数据处理系统(例如，数据处理系统105)可以检索候选多个指纹(212)。在一些实现方式中，数据处理系统可以从数据库，例如数据库115，检索候选指纹。候选指纹可以与候选媒体流相关联。在一些实现方式中，候选媒体流可以与目标媒体流相同。在一些实现方式中，可以从媒体源(例如，媒体源150)接收候选媒体流，并且可以使用例如结合图3的方法204来生成候选指纹。候选多个指纹均可以分别与对应的候选时间戳相关联。候选时间戳可以与候选媒体流中的帧相对应。在一些实现方式中，候选媒体流可以包括可以构成感兴趣片段的一系列帧。感兴趣的片段也可以包括在目标媒体流中。
65.数据处理系统(例如，数据处理系统105)可以确定是否找到了匹配的指纹(214)。数据处理系统可以将在步骤(212)中检索到的每个候选指纹与在步骤(210)中确定的目标指纹进行比较。数据处理系统可以使用与用于计算目标指纹和每个候选指纹的散列算法相关联的距离方程来确定每个候选指纹的相似度值。可以通过将候选指纹与目标指纹进行比较来候选指纹的计算相似度值。如果任何候选指纹与目标指纹足够相似，则数据处理系统可以确定已找到匹配的指纹。例如，如果针对候选指纹计算的相似度值大于或等于预定的相似度阈值，则数据处理系统可以确定各个候选指纹与目标指纹足够相似，并且可以找到匹配。当找到匹配时，数据处理系统可以确定匹配的候选指纹的索引值，并且数据处理系统可以执行方法200的步骤(216)。如果没有候选指纹与目标指纹足够相似，数据处理系统可以确定在候选指纹中没有找到匹配项。如果在候选指纹中没有找到匹配，则数据处理系统可以返回到步骤(212)以检索与另一候选媒体流相关联的另一候选指纹集合。
66.数据处理系统(例如，数据处理系统105)可以确定上边界和下边界(216)。数据处理系统可以使用结合图4的方法216a来计算下边界。数据处理系统可以使用结合图5的方法216b来计算上边界。下边界可以对应于候选媒体流中的时间戳，该时间戳对应于候选媒体流中感兴趣的片段中的第一帧。上边界可以对应于候选媒体流中的时间戳，该时间戳对应于候选媒体流中感兴趣段中的最后一个帧。数据处理系统可以通过将目标媒体流中的指纹与候选媒体流中的指纹进行比较来计算上边界和下边界，从目标指纹开始，到感兴趣段的
第一个和最后一个指纹结束。数据处理系统可以通过比较候选媒体流和目标媒体流直到找到不匹配来确定上边界或下边界。两个流之间的不匹配(例如，指纹不足够相似)可以意味着该不匹配的指纹表示可能不是感兴趣片段的一部分的帧。
67.数据处理系统(例如，数据处理系统105)可以提取媒体片段(218)。媒体片段可以是感兴趣的片段，其可以由在步骤(216)中确定的上边界和下边界来定义。数据处理系统可以通过访问媒体片段的帧(例如候选媒体片段)来提取媒体片段，该帧包括小于上边界时间戳且小于下边界时间戳的时间戳。在一些实现方式中，数据处理系统可以访问与帧相对应的指纹，所述帧包括小于上边界时间戳且大于下边界时间戳的时间戳。在一些实现方式中，数据处理系统可以包括与所提取的感兴趣片段中的上边界和下边界时间戳相对应的帧和/或指纹。数据处理系统可以从计算机存储器，例如数据库(例如，数据库115)或计算机内存(例如，结合图8的存储器825)访问帧和/或指纹。
68.数据处理系统(例如，数据处理系统105)可以提供媒体片段(220)。数据处理系统可以提供在步骤(218)中提取的媒体片段。在一些实现方式中，数据处理系统可以经由计算机网络(例如，网络110)来提供媒体片段。在一些实现方式中，数据处理系统可以经由通信总线来提供媒体片段。当提供媒体片段时，数据处理系统可以提供包括媒体片段的帧和/或可以对应于包括媒体片段的帧的指纹。在一些实现方式中，构成媒体片段的帧可以包括相应的时间戳。在一些实现方式中，提供媒体片段可以包括关于媒体片段的元数据(例如，持续时间、内容、包含该片段的媒体流、与该片段相对应的绝对时间戳，与该时间戳相对应的相对时间戳等)。在一些实现方式中，提供媒体片段可以包括将与媒体片段相关联的元数据，指纹和/或帧以数据结构存储在计算机内存(例如，结合图8的内存825)或数据库(例如，数据库115)中。
69.现在参照图3，描绘了用于为媒体流中的帧生成指纹值的方法204的流程图。可以使用上文结合图1描述的数据处理系统105或下面结合图8描述的计算机系统800来实现或执行方法204。方法204可以被实现为上面结合图2描述的方法200的步骤204的一部分。简而言之，数据处理系统可以从多个帧中选择第i帧(302)。数据处理系统可以基于多个帧来选择m个帧(304)。数据处理系统可以从m个帧中选择第j帧(306)。数据处理系统可以散列第j帧(308)。数据处理系统可以截断第j帧(310)。数据处理系统可以确定是否已经处理了所有m个帧(312)。数据处理系统可以使计数器寄存器j递增(314)。数据处理系统可以级联截断的散列帧(316)。数据处理系统可以确定是否所有n帧都已经被处理(318)。数据处理系统可以使计数器寄存器i递增(320)。
70.数据处理系统可以从多个帧中选择第i帧(302)。在一些实现方式中，i可以指定计数器寄存器，该计数器寄存器在每次执行方法204时索引循环的迭代。在一些实现方式中，i的值用于索引多个帧以进行处理。在一些实现方式中，由i索引的循环的所有迭代可以并行执行。在一些实现方式中，在方法204中由i索引的循环的第一迭代中，数据处理系统可以从多个帧中选择第一帧(第i个，i＝1)。应当理解，可以以任何顺序选择帧。数据处理系统可以从多个帧中选择每个帧以生成与预定窗口值相对应的相应指纹值。
71.数据处理系统可以基于多个帧选择m个帧(304)。数据处理系统可以为媒体流中的每个帧生成指纹。媒体流可以包括一个或多个帧。数据处理系统可以基于在指定的窗口值(例如，媒体流中的时间段、帧数、滑动窗口等)内的各个帧和一个或多个其他帧来生成指
纹。数据处理系统可以从与要生成的指纹相关联的帧之前或之后的媒体流中的帧中选择m个帧。例如，数据处理系统可以在步骤(302)中选择的第i帧之后选择m个帧。可以基于时间间隔选择m帧，该时间间隔可以包括在窗口值中。例如，窗口值可以是三秒，指定可以在选择的第i帧之后选择m个帧。进一步扩展该示例，窗口值可以指定可以基于时间间隔(例如，每0.5秒一帧)来选择所选择的m个帧。在该示例中，m可以等于六个选择的帧，之所以可以选择六个选择的帧，是因为存在六个满足窗口条件和时间间隔条件的帧。在一些实施方案中，第i帧可包含在选定的m个帧中。在一些实现方式中，数据处理系统可以选择不在指定窗口值内的帧。
72.数据处理系统可以从m个帧中选择第j帧(306)。在一些实现方式中，j可以指定计数器寄存器，该计数器寄存器在每次执行方法204时索引循环的迭代。在一些实现方式中，j的值用于索引在步骤(304)中选择的m个帧以进行处理。在一些实现方式中，由j索引的循环的所有迭代可以并行执行。在一些实现方式中，在方法204中由j索引的循环的第一次迭代中，数据处理系统可以从m个选择的帧中选择第一帧(第j，j＝1)。应当理解，可以以任何顺序选择帧。数据处理系统可以从所选择的m个帧中选择每个帧，以生成与预定窗口值相对应的各个指纹值。
73.数据处理系统可以散列第j帧(308)。数据处理系统可以使用一种或多种散列算法或函数来散列在步骤(306)中选择的第j帧。在一些实现方式中，散列函数可以是局部敏感的散列函数。在一些实现方式中，散列函数是另一类型的散列函数(例如，sha
‑
1，sha
‑
2，md5等)。例如，可以选择局部敏感的散列算法以允许数据处理系统计算两个帧之间的相似度值。数据处理系统可以使用位采样作为局部敏感的散列算法。数据处理系统可以使用最小独立的排列局部敏感散列算法(min
‑
wise independent permutations locality sensitive hashing algorithm)。数据处理系统可以使用其他类型的局部敏感散列算法，例如随机投影方法。散列帧可以具有固定的位宽度(例如，8位、16位、32位、64位等)。在一些实现方式中，散列帧可以具有可变的位宽。在一些实现方式中，数据处理系统可以在应用散列算法以创建对应的散列帧之前对帧进行解码或预处理。例如，数据处理可以在将散列算法应用于原始帧信息以创建散列帧之前，使用对应的编解码器对帧进行解码以访问原始帧信息。数据处理系统可以解码和散列包括在帧中的音频信息、视频信息和/或隐藏字幕信息，和/或以作为不同散列来散列的帧中包括的音频信息、视频信息和/或隐藏字幕信息。数据处理系统可以在计算机内存，例如数据库(例如，数据库115)或计算机内存(例如，结合图8的存储器825)中创建并存储散列。数据处理系统可以将散列帧存储在数据结构中，例如，类似c的数据结构或计算机内存的区域中。数据处理系统可以将散列的帧存储在缓冲器中，该缓冲器可以是用于存储数据的计算机内存的临时区域。数据处理系统可以将每个散列帧与相应的时间戳、索引值或定位数据相关联，以指示散列帧在相应的媒体流中的位置。
74.数据处理系统可以截断第j帧(310)。数据处理系统可以截断在步骤(308)中创建的散列的第j帧以生成第j截断的散列的帧。截断第j散列帧可以包括选择第j散列帧中的固定范围的位，例如8个最低有效位。截断第j散列帧可以包括将截断的位以数据结构存储在计算机内存(例如，结合图8的存储器825)或数据库(例如，数据库115)中。例如，如果第j散列帧的二进制值为01100100，则数据处理系统可以通过选择四个最高有效位(在此示例中为0110)截断该散列帧。截断第j散列帧可以减小第j散列帧的总体尺寸，同时仍保留足够的
信息以进行进一步处理，这是对其他实现的改进。在一些实现方式中，数据处理系统可以跳过执行截断步骤，而是将整个散列帧用于进一步处理。在一些实现方式中，截断第j散列帧可以包括选择第j散列帧中的位的任何组合以生成第j截断的散列帧。例如，如果第j散列帧的二进制值为00110001，则数据处理系统可以选择位置6、4、2和0中的每个位，以生成值为0101的截断的散列帧。
75.数据处理系统可以确定是否已经处理了所有m个帧(312)。为在步骤(302)中选择的第i帧生成指纹可以包括为在步骤(304)中选择的m个帧中的每一个生成截断的散列帧。在一些实现方式中，数据处理系统可以将计数器寄存器j与数量m进行比较，以确定是否已经处理了m个帧中的每一个。在一些实现方式中，使用数据结构跟踪由j索引的循环的进度。在一些实现方式中，数据处理系统可以分别在数据结构中记录条目，该条目指示m个帧中的对应帧已经被如在步骤(308)和(310)中那样散列和截断。数据处理系统可以访问数据结构，以确定是否已对所有m帧进行了散列和截断。在一些实现方式中，数据处理系统可以通过将计数器寄存器j与数量m进行比较来确定已经对m个帧进行了散列和截断。如果j等于值m，则数据处理系统可以确定已经对所有m个帧进行了散列和截断，并且数据处理系统可以执行方法204的步骤(316)。在这种实现中，如果计数器寄存器j不等于数m，则数据处理系统可以转到步骤(314)。
76.数据处理系统可以使计数器寄存器j递增(314)。数据处理系统可以通过将值一加到寄存器来递增计数器寄存器j。在一些实现方式中，数据处理系统可以在数据结构中记录第j帧已经被分别如在步骤(308)和(310)那样散列和截断。在递增计数器寄存器j之后，数据处理系统可以执行方法204的步骤(306)。
77.数据处理系统可以级联被截断的散列帧(316)。数据处理系统可以基于媒体流中的每个帧来生成表示窗口值的指纹。所选择的第i帧可以与所生成的指纹相关联。数据处理系统可以通过将在步骤(306)
‑
(314)中生成的m个截断的散列帧中的每一个进行级联来生成与所选的第i帧相关联的指纹。数据处理系统可以通过将m个截断的散列帧中的每一个级联在一起成为单个值来计算第i指纹。例如，如果从媒体流的一个时间窗口中选择了三个帧(例如，m＝3)，并且它们的截断的散列值等于0110、0101和1000，则数据处理系统可以将这些值中的每个级联以生成指纹值011001011000。尽管在此示例中，m个截断的散列帧被显示为以特定顺序级联，但是应该理解，每个截断的散列帧都可以任何组合或排列的方式级联。数据处理系统可以将每个指纹值与时间戳或索引值相关联，以指示指纹所对应的媒体流中的位置。
78.数据处理系统可以确定是否所有n帧都已经被处理(318)。为媒体流中的每个帧生成指纹可以包括：从媒体流中选择m个帧；为m个帧中的每个帧生成一个截断的散列帧；以及针对媒体流中的n个帧中的每个帧级联该m个截断的散列帧。在一些实现方式中，数据处理系统可以将计数器寄存器i与媒体流n中的帧数进行比较，以确定是否已经为n个帧中的每一个生成了指纹。在一些实现方式中，使用数据结构跟踪由i索引的循环的进度。在一些实现方式中，数据处理系统可以在数据结构中记录条目，该条目指示通过方法204已经生成了m个帧中的相应帧的相应指纹。数据处理系统可以访问数据结构以确定是否已经为n个帧中的每个帧生成了指纹。在一些实现方式中，数据处理系统可以通过将计数器寄存器i与数字n进行比较来确定n个帧已经生成了对应的指纹。如果i等于值n，则数据处理系统可以确定
所有n个帧都已经生成了相应的指纹，并且数据处理系统可以完成执行方法204。在这样的实现中，如果计数器寄存器i不等于数n，则数据处理系统可以移至步骤(320)。
79.数据处理系统可以使计数器寄存器i递增(320)。数据处理系统可以通过将值一加到寄存器来递增计数器寄存器i。在一些实现方式中，数据处理系统可以在数据结构中记录已经为第i帧生成了对应的指纹。在递增计数器寄存器j之后，数据处理系统可以执行方法204的步骤(302)。
80.现在参考图4，描绘了用于确定匹配媒体片段的下边界的方法216a的流程图。可以使用上面结合图1描述的数据处理系统105或下面结合图8描述的计算机系统800来实现或执行方法216a。方法216a可以被实现为结合图2描述的方法200的步骤216的一部分。简而言之，数据处理系统可以从第一多个指纹中选择第i指纹(402)。数据处理系统可以从第二多个指纹中选择第j指纹(404)。数据处理系统可以比较第i指纹和第j指纹(406)。数据处理系统可以确定是否存在匹配(408)。数据处理系统可以递减计数器寄存器i和j(410)。数据处理系统可以计算下边界(412)。
81.数据处理系统可以从第一多个指纹中选择第i指纹(402)。在一些实现方式中，计数器值i可以是用于索引循环的计数器寄存器。所述第一多个指纹可以是在方法200的步骤(204)中生成的多个指纹(在本文中有时通常称为目标媒体流)。数据处理系统可以选择第i指纹，以与在步骤(212)中检索的候选多个指纹中的指纹进行比较，以确定感兴趣的匹配片段的下边界。在一些实现方式中，每个指纹可以对应于每个媒体流中的单个帧，这意味着如果在两个媒体流中找到匹配的指纹，则在两个媒体流的每个中可以存在匹配的帧。在一些实现方式中，在循环的第一次迭代中，i的值可以等于在方法200的步骤(210)中确定的目标指纹的索引值。
82.数据处理系统可以从第二多个指纹中选择第j指纹(404)。在一些实现方式中，计数器值j可以是用于索引循环的计数器寄存器。第二多个指纹可以是在方法200的步骤(212)中由数据处理系统检索的候选多个指纹(在本文中有时通常称为候选媒体流)。数据处理系统可以选择第j指纹以与方法200的步骤(204)中生成的多个指纹中的指纹进行比较，所述多个指纹可以对应于目标媒体流。数据处理系统可以在与目标媒体流关联的指纹和与候选媒体流关联的指纹之间执行迭代比较，以确定感兴趣片段的下边界。在一些实现方式中，每个指纹可以对应于相应媒体流中的单个帧，这意味着如果在两个媒体流中找到匹配的指纹，则在两个媒体流的每个中可以存在匹配的帧。在一些实现方式中，在循环的第一次迭代中，j的值可以等于在方法200的步骤(214)中确定的候选指纹的索引值。
83.数据处理系统可以比较第i和第j指纹(406)。数据处理系统可以确定是否存在匹配(408)。数据处理系统可以使用与散列算法(例如，用于生成每个指纹的散列算法)相关联的距离方程来确定每个候选指纹的相似度值。可以通过使用距离方程(例如汉明距离，其他基于局部的散列算法距离函数等)将候选指纹与目标指纹进行比较，来计算候选指纹的相似度值。如果第i目标指纹和第j候选指纹足够相似，则数据处理系统可以确定已经找到匹配项。例如，如果针对第i指纹和第j指纹计算的相似度值大于或等于预定的相似度阈值，则数据处理系统可以确定相应的第j指纹与第i指纹充分相似，并且可以找到匹配。当找到匹配时，数据处理系统可以执行方法216a的步骤(410)。如果没有找到匹配，则数据处理系统可以确定目标媒体流和候选媒体流中的匹配片段的边界，并执行方法216a的步骤(412)。
84.数据处理系统可以递减计数器寄存器i和j(410)。数据处理系统可以比较每一个候选指纹和目标指纹，以确定下边界时间戳。在一些实现方式中，数据处理系统可以从在步骤(210)中为目标媒体流确定的指纹索引值和在步骤(214)中为候选媒体流确定的指纹索引值开始，并且在不匹配时结束，或者到达一个流的开头时结束。为了确定下一个要比较的指纹，数据处理系统可以选择具有下一个最接近每个流的开头的索引值的指纹(例如，对于每个相应的媒体流，比i和j的当前索引小一的索引值)。在一些实现方式中，数据处理系统可以将计数器寄存器i和j中的每一个递减1以确定与每个媒体流的开头最近的下一个指纹。如果已经到达目标媒体流的开头或候选媒体流的开头(例如，没有更多的指纹可用于比较)，则数据处理系统可以确定下边界时间戳等于与候选媒体流中先前比较的指纹相关联的时间戳。在一些实现方式中，如果已经到达目标媒体流的开头或候选媒体流的开头，则数据处理系统可以确定下边界时间戳等于与目标媒体流中先前比较的指纹相关联的时间戳。
85.数据处理系统可以计算下边界(412)。如果第一多个指纹和第二多个指纹中的两个指纹(例如分别是目标媒体流和候选媒体流)之间发生不匹配，则数据处理系统可以确定感兴趣的片段的下边界。感兴趣的片段可以是目标媒体流中的媒体片段，其也存在于候选媒体流中。数据处理系统可以比较与目标和候选媒体流关联的指纹，以确定感兴趣的匹配片段的边界。在一些实现方式中，感兴趣片段的下边界可以是与感兴趣媒体片段的第一帧(例如，起始帧)相对应的时间戳。在一些实现方式中，下边界可以对应于感兴趣片段中的第一帧的帧索引。当在步骤(408)中确定了两个指纹之间的不匹配时，数据处理系统可以访问候选媒体流的最后匹配指纹(例如，对应于索引j 1)以确定与指纹对应的帧的时间戳。在一些实现方式中，数据处理系统可以访问目标媒体流的最后匹配指纹(例如，对应于索引i 1)以确定对应于该指纹的帧的时间戳。下边界可以等于与候选媒体流相关联的最后匹配指纹的时间戳。在一些实现方式中，下边界可以等于与目标媒体流相关联的最后匹配指纹的时间戳。在一些实现方式中，下边界可以等于候选媒体流的最后匹配索引(例如，j 1)。在一些实现方式中，下边界可以等于目标媒体流的最后匹配索引(例如，i 1)。数据处理系统可以例如通过执行方法200的步骤(218)，使用下边界来提取感兴趣的片段。
86.现在参考图5，描绘了用于确定匹配媒体片段的上边界的方法216b的流程图。可以使用上面结合图1描述的数据处理系统105或下面结合图8所述的计算机系统800来实现或执行方法216b。方法216b可以被实现为结合图2描述的方法200的步骤216的一部分。简而言之，数据处理系统可以从第一多个指纹中选择第i指纹(502)。数据处理系统可以从第二多个指纹中选择第j指纹(504)。数据处理系统可以比较第i和第j指纹(506)。数据处理系统可以确定是否存在匹配(508)。数据处理系统可以使计数器寄存器i和j递增(510)。数据处理系统可以计算上边界(512)。
87.数据处理系统可以从第一多个指纹中选择第i指纹(502)。在一些实现方式中，计数器值i可以是用于索引循环的计数器寄存器。所述第一多个指纹可以是在方法200的步骤(204)中生成的多个指纹(在本文中有时通常称为目标媒体流)。数据处理系统可以选择第i指纹，以与在步骤(212)中检索到的候选多个指纹中的一个指纹进行比较，以确定感兴趣的匹配片段的上边界。在一些实现方式中，每个指纹可以对应于每个媒体流中的单个帧，这意味着如果在两个媒体流中找到匹配的指纹，则在两个媒体流的每个中可以存在匹配的帧。在一些实现方式中，在循环的第一次迭代中，i的值可以等于在方法200的步骤(210)中确定
的目标指纹的索引值。
88.数据处理系统可以从第二多个指纹中选择第j指纹(504)。在一些实现方式中，计数器值j可以是用于索引循环的计数器寄存器。第二多个指纹可以是在方法200的步骤(212)中由数据处理系统检索的候选多个指纹(在本文中有时通常称为候选媒体流)。数据处理系统可以选择第j指纹以与方法200的步骤(204)中生成的多个指纹中的指纹进行比较，所述多个指纹可以对应于目标媒体流。数据处理系统可以在与目标媒体流关联的指纹和与候选媒体流关联的指纹之间执行迭代比较，以确定感兴趣片段的上边界。在一些实现方式中，每个指纹可以对应于相应媒体流中的单个帧，这意味着如果在两个媒体流中找到匹配的指纹，则在两个媒体流的每个中可以存在匹配的帧。在一些实现方式中，在循环的第一次迭代中，j的值可以等于在方法200的步骤(214)中确定的候选指纹的索引值。
89.数据处理系统可以比较第i和第j指纹(506)。数据处理系统可以确定是否存在匹配(508)。数据处理系统可以使用与散列算法(例如，用于生成每个指纹的散列算法)相关联的距离方程来确定每个候选指纹的相似度值。可以通过使用距离方程(例如汉明距离，其他基于局部的散列算法距离函数等)将候选指纹与目标指纹进行比较，来计算候选指纹的相似度值。如果第i目标指纹和第j候选指纹足够相似，则数据处理系统可以确定已经找到匹配。例如，如果针对第i指纹和第j指纹计算的相似度值大于或等于预定的相似度阈值，则数据处理系统可以确定相应的第j指纹与第i指纹充分相似，并且可以找到匹配。当找到匹配时，数据处理系统可以执行方法216b的步骤(510)。如果没有找到匹配，则数据处理系统可以确定目标媒体流和候选媒体流中的匹配片段的边界，并且执行方法216b的步骤(512)。
90.数据处理系统可以使计数器寄存器i和j递增(510)。数据处理系统可以比较候选指纹和目标指纹中的每一个，以确定上边界时间戳。在一些实现方式中，数据处理系统可以从在步骤(210)中为目标媒体流确定的指纹索引值以在步骤(214)中为候选媒体流确定的指纹索引值开始，并且在不匹配时结束，或者到达媒体流之一的结尾处时结束。为了确定下一个要比较的指纹，数据处理系统可以选择指纹，该指纹具有下一个最接近每个流的末尾的索引值(例如，对于每个相应的媒体流，比i和j的当前索引大一的索引值)。在一些实现方式中，数据处理系统可以将计数器寄存器i和j中的每一个递增一，以确定到每个媒体流的末尾的下一个最接近的指纹。如果已经到达目标媒体流的末尾或候选媒体流的末尾(例如，没有更多的指纹可用于比较)，则数据处理系统可以确定上边界时间戳等于与候选媒体流中先前比较的指纹相关联的时间戳。在一些实现方式中，如果已经到达目标媒体流的开头或候选媒体流的开头，则数据处理系统可以确定下边界时间戳等于与目标媒体流中先前比较的指纹相关联的时间戳。
91.数据处理系统可以计算上边界(512)。如果第一多个指纹和第二多个指纹中的两个指纹(例如分别是目标媒体流和候选媒体流)之间发生了不匹配，则数据处理系统可以确定感兴趣片段的上边界。在一些实现方式中，感兴趣片段可以是目标媒体流中的媒体片段，其也存在于候选媒体流中。数据处理系统可以比较与目标和候选媒体流关联的指纹，以确定感兴趣的匹配片段的边界。在一些实现方式中，感兴趣片段的上边界可以是与感兴趣媒体片段的最后帧(例如，最终帧)相对应的时间戳。在一些实现方式中，上边界可以对应于感兴趣的片段中的最终帧的帧索引。当在步骤(508)中确定了两个指纹之间的不匹配时，数据处理系统可以访问候选媒体流的最后匹配指纹(例如，对应于索引j
‑
1)以确定与指纹对应
的帧的时间戳。在一些实现方式中，数据处理系统可以访问目标媒体流的最后匹配指纹(例如，对应于索引i
‑
1)以确定对应于该指纹的帧的时间戳。上边界可以等于与候选媒体流相关联的最后匹配指纹的时间戳。在一些实现方式中，下边界可以等于与目标媒体流相关联的最后匹配指纹的时间戳。在一些实现方式中，上边界可以等于候选媒体流的最后匹配索引(例如，j
‑
1)。在一些实现方式中，上边界可以等于目标媒体流的最后匹配索引(例如，i
‑
1)。数据处理系统可以例如通过执行方法200的步骤(218)，使用上边界来提取感兴趣的片段。
92.现在参考图6，描绘了示出基于媒体流中的帧的指纹值的示例生成的图。在该图示中，帧605a
‑
d(在本文中有时通常被称为帧605)表示用于生成指纹615的所选帧。生成的指纹615可以与所选帧之一相关联，例如第一所选帧605a。帧605a
‑
d可以对应于由更多帧(未示出)组成的媒体流中的时间段。可以使用散列函数来散列每个帧605，以生成对应的散列帧610a
‑
d(在本文中有时通常称为散列帧610)。散列帧610可以是具有固定宽度的位流。某些位(例如，如图所示的最高有效位)可以由数据处理系统(例如，数据处理系统105)选择，并级联到相应的指纹615中。尽管该图示出了散列帧610的最高有效位为当被选择用于级联时，应当理解，可以为最终指纹615选择散列帧610中的任何位。同样，包括在指纹615中的每个散列帧610的顺序可以是任何布置、次序、组合或排列。在一些实现方式中，可以选择四个以上的帧605来创建指纹615。在一些实现方式中，可以在指纹中包括附加的元数据，例如，时间戳指的是指纹在相应的媒体流中表示的位置。
93.现在参考图7，描绘了图示使用两个媒体指纹集合来确定匹配媒体片段的上边界和下边界的示例的图。该图包括第一多个指纹710a
‑
i(在本文中有时通常被称为第一多个指纹710)。该图包括第二多个指纹725a
‑
i(在本文中有时通常被称为第二多个指纹725)。该图包括第一多个指纹710a
‑
i中的感兴趣目标片段715。该图包括第二多个帧725中的感兴趣的候选片段730。该图包括目标指纹索引735。该图包括匹配的候选指纹索引740。该图包括下边界索引745。该图包括上边界索引745。
94.数据处理系统可以接收目标指纹的索引，例如目标指纹索引735。数据处理系统可以将目标指纹710e与第二多个指纹725中的每一个进行比较，以确定对应于匹配指纹725f的候选指纹索引740。为了确定候选媒体流中的感兴趣片段730的边界，数据处理系统可以将第一多个指纹710与第二多个指纹进行比较。
95.为了确定下边界745，数据处理系统可以从目标指纹和匹配的候选指纹开始，并且比较下一个最接近每个多个指纹的开头的两个指纹以确定指纹是否匹配。例如，数据处理系统接下来可以比较第一多个指纹710d和第二多个指纹725e。因为这两个匹配，所以数据处理系统可以继续比较下一个最接近每个流的开头的两个指纹，在该示例中为指纹710c和725d。因为指纹710d和指纹725d匹配，所以数据处理系统可以继续比较下一个最接近每个流的开始的两个指纹，在该示例中为710b和725c。在此示例中，指纹不匹配。这样，数据处理系统可以确定感兴趣片段730的下边界745以对应于候选指纹725d，因为它是第二多个指纹中的最后匹配指纹。在一些实现方式中，数据处理系统可以确定感兴趣片段715的下边界745以对应于目标指纹710c。
96.为了确定下边界750，数据处理系统可以从目标指纹和匹配的候选指纹开始，并且比较下一个最接近每个多个指纹的末尾的两个指纹，以确定指纹是否匹配。例如，数据处理
系统接下来可以比较第一多个指纹中的指纹710f和第二多个指纹中的指纹725g。因为这两个匹配，所以数据处理系统可以继续比较下一个最接近每个流的开头的两个指纹，在该示例中是指纹710g和指纹725h。因为指纹710g和指纹725h匹配，所以数据处理系统可以继续比较下一个最接近每个流的开头的两个指纹，在该示例中为710h和725i。在此示例中，指纹不匹配。这样，数据处理系统可以确定感兴趣片段730的上边界750以对应于候选指纹725h，因为它是第二多个指纹中的最后匹配指纹。在一些实现方式中，数据处理系统可以确定感兴趣片段730的上边界750以对应于目标指纹710g。
97.图8示出了根据一些实现方式的示例性计算机系统1200的总体架构，该示例性计算机系统1200可以用于实施本文所讨论的任何计算机系统。计算机系统800可以用于经由网络810提供信息以供显示。图8的计算机系统800包括：通信地耦合到存储器825的一个或多个处理器820，一个或多个通信接口805，一个或多个输出设备810(例如，一个或多个显示单元)和一个或多个输入设备815。在数据处理系统105或系统800的其他组件(例如，数据处理系统805)中可以包括处理器820。
98.在图8的计算机系统800中，存储器825可以包括任何计算机可读存储介质，并且可以存储诸如用于为各个系统实现本文所述的各种功能的处理器可执行指令之类的计算机指令，以及由此生成或经由通信接口或输入设备(如果有)接收的与之相关的任何数据。再次参考图8的系统800，数据处理系统可以包括存储器825，以存储与用户标识符、生成的矢量等集合有关的信息。图8中所示的一个或多个处理器820可被用于执行存储在存储器825中的指令，并且这样做还可从存储器中读取或向存储器写入根据指令的执行而处理和/或生成的各种信息。
99.图8所示的计算机系统800的处理器820还可以通信地耦合到通信接口805或控制通信接口805以发送或接收根据指令的执行的各种信息。例如，一个或多个通信接口805可以耦合到有线或无线网络、总线或其他通信装置，并且因此可以允许计算机系统800向其他设备(例如，其他计算机系统)发送信息或从其他设备接收信息。虽然在图8的系统中未明确示出，一个或多个通信接口促进信息在系统800的组件之间流动。在一些实现方式中，(多个)通信接口可以被配置(例如，经由各种硬件组件或软件组件)以提供作为到通信接口805的至少一些方面的访问门户的网站。通信接口805的的示例包括用户界面(例如，网页)，用户可以通过该用户界面与数据处理系统800进行通信。
100.例如可以提供图8中所示的计算机系统800的输出设备810，以允许结合指令的执行来查看或以其他方式感知各种信息。可以提供输入设备815，例如以允许用户在指令执行期间进行手动调整，进行选择，输入数据或以各种方式与处理器交互。本文中进一步提供了与可以用于本文所讨论的各种系统的通用计算机系统架构有关的附加信息。
101.本说明书中描述的主题和操作的实现可以在数字电子电路中或在有形介质、固件或硬件上体现的计算机软件中实施，包括本说明书中公开的结构及其等同结构，或其中一种或多种的组合。本说明书中描述的主题的实现可以实现为一个或多个计算机程序，即计算机程序指令的一个或多个组件，其被编码在计算机存储介质上以由数据处理设备执行或控制数据处理设备的操作。可以在人工生成的传播信号(例如，机器生成的电，光或电磁信号，该信号被生成以对信息进行编码以发送到合适的接收器设备以由数据处理设备执行)上编码程序指令。计算机存储介质可以是计算机可读存储设备、计算机可读存储基板、随机
或串行访问存储器阵列或设备、或它们中的一个或多个的组合，或包括在上述其中。此外，尽管计算机存储介质不是传播信号，但是计算机存储介质可以包括以人工生成的传播信号编码的计算机程序指令的源或目的地。该计算机存储介质还可以是一个或多个单独的物理组件或介质(例如，多个cd，磁盘或其他存储设备)，或包含在其中。
102.本文公开的特征可以在智能电视模块(或连接的电视模块，混合电视模块等)上实现，该智能电视模块可以包括处理模块，该处理模块被配置为将因特网连接与更多传统电视节目源(例如，通过电缆，卫星，无线或其他信号接收到的电视节目源)集成在一起。智能电视模块可以物理地合并到电视机中，或者可以包括单独的设备，例如机顶盒、蓝光或其他数字媒体播放器，游戏机、酒店电视系统以及其他配套设备。智能电视模块可以被配置为允许观看者在网络上、本地有线电视频道上、卫星电视频道上或存储在本地硬盘上搜索和查找视频、电影、照片和其他内容。机顶盒(stb)或机顶单元(stu)可以包括一个信息设备，该设备可以包含调谐器并连接到电视机和外部信号源，将信号转换为内容，然后显示在电视屏幕或其他显示设备上。智能电视模块可以配置为提供主屏幕或顶级屏幕，其中包括用于多个不同应用程序(例如web浏览器和多个流媒体服务)的图标、连接的电缆或卫星媒体源、其他“web”频道等。智能电视模块可以进一步被配置为向用户提供电子节目指南。智能电视模块的配套应用程序可以在移动计算设备上操作，以向用户提供有关可用节目的附加信息，以允许用户控制智能电视模块等。在替代实现方式中，可以在膝上型计算机或其他个人计算机、智能手机、其他移动电话、掌上计算机、平板电脑或其他计算设备实现这些特征。
103.在本说明书中描述的操作可以被实现为由数据处理设备对存储在一个或多个计算机可读存储设备上或从其他源接收的数据执行的操作。
104.术语“数据处理设备”、“数据处理系统”、“用户设备”或“计算设备”涵盖用于处理数据的所有类型的装置、设备和机器，例如包括可编程处理器、计算机、芯片上的系统或前述的多个或组合。该装置可以包括专用逻辑电路，例如fpga(现场可编程门阵列)或asic(专用集成电路)。除了硬件之外，该装置还可以包括为所讨论的计算机程序创建执行环境的代码，例如，构成处理器固件、协议栈、数据库管理系统、操作系统、跨平台运行时环境、虚拟机或其中一个或多个的组合的代码。该装置和执行环境可以实现各种不同的计算模型基础结构，例如网络服务、分布式计算和网格计算基础结构。
105.计算机程序(也称为程序、软件、软件应用程序、脚本或代码)可以用任何形式的编程语言(包括编译或解释的语言、声明性或过程性语言)编写，并且可以部署为任何形式，包括作为独立程序或作为模块、组件、子例程、对象或适用于计算环境的其他单元。计算机程序可以但不必对应于文件系统中的文件。程序可以存储在保存其他程序或数据的文件的一部分中(例如，存储在标记语言文档中的一个或多个脚本)，存储在专用于所讨论程序的单个文件或多个协调文件(例如，存储一个或多个模块、子程序或部分代码的文件)中。可以将计算机程序部署为在位于一个站点或分布在多个站点并通过通信网络互连的一台计算机或多台计算机上执行。
106.可以通过一个或多个可编程处理器执行本说明书中描述的处理和逻辑流程，所述可编程处理器执行一个或多个计算机程序以通过对输入数据进行操作并生成输出来执行动作。处理和逻辑流程也可以由专用逻辑电路执行，并且装置也可以实现为专用逻辑电路，例如，fpga(现场可编程门阵列)或asic(专用集成电路)。
107.例如，适合于执行计算机程序的处理器包括通用和专用微处理器、以及任何种类的数字计算机的任何一个或多个处理器。通常，处理器将从只读存储器或随机存取存储器或两者接收指令和数据。计算机的组件包括用于根据指令执行动作的处理器以及用于存储指令和数据的一个或多个存储设备。通常，计算机还将包括或可操作地耦合以从一个或多个用于存储数据的大容量存储设备(例如，磁、磁光盘或光盘)接收数据或将数据传输到一个或多个大容量存储设备或向这两者传输数据。但是，计算机不必具有此类设备。此外，计算机可以被嵌入到另一个设备中，例如，移动电话、个人数字助理(pda)、移动音频或视频播放器、游戏机、全球定位系统(gps)接收器或便携式存储设备(例如，通用串行总线(usb)闪存驱动器)。适用于存储计算机程序指令和数据的设备包括所有形式的非易失性存储器、介质和存储设备，包括：例如半导体存储器件，例如eprom，eeprom和闪存器件；磁盘，例如内部硬盘或可移动磁盘；磁光盘；以及cd
‑
rom和dvd
‑
rom磁盘。处理器和存储器可以由专用逻辑电路补充或并入专用逻辑电路中。
108.为了提供与用户的交互，可以在具有显示设备(例如crt(阴极射线管)，等离子或lcd(液晶显示器)监视器)以及键盘和指示设备(例如鼠标或轨迹球)的计算机上实现本说明书中描述的主题的实现，其中显示设备用于向用户显示信息，用户可以通过键盘和指示设备向计算机提供输入。其他种类的设备也可以用于提供与用户的交互。例如，提供给用户的反馈可以包括任何形式的感觉反馈，例如视觉反馈、听觉反馈或触觉反馈；并且可以以任何形式接收来自用户的输入，包括声音、语音或触觉输入。另外，计算机可以通过向用户使用的设备发送文档以及从用户使用的设备接收文档来与用户进行交互。例如，通过响应网页浏览器收到的请求，将网页发送到用户客户端设备上的网页浏览器。
109.可以在包括后端组件(例如，作为数据服务器)，或者包括中间件组件(例如，应用服务器)，或者包括前端组件(例如，具有图形用户界面或web浏览器的客户端计算机，用户可以通过该web浏览器与本规范中描述的主题的实现进行交互)，或者包括一个或多个此类后端、中间件或前端组件的任意组合的计算系统中实现本说明书中描述的主题的实现方式。系统的组件可以通过数字数据通信的任何形式或介质(例如，通信网络)互连。通信网络的示例包括局域网(“lan”)和广域网(“wan”)、网际网络(例如因特网)和对等网络(例如ad hoc对等网络)。
110.诸如数据处理系统805的计算系统可以包括客户端和服务器。例如，数据处理系统805可包括一个或多个数据中心或服务器场中的一个或多个服务器。客户端和服务器通常彼此远离，并且通常通过通信网络进行交互。客户端和服务器之间的关系是通过在各自计算机上运行并彼此具有客户端
‑
服务器关系的计算机程序产生的。在一些实现方式中，服务器将数据(例如，html页面)发送到客户端设备(例如，出于向与客户端设备交互的用户显示数据并从中接收用户输入的目的)。可以从服务器处的客户端设备接收在客户端设备处生成的数据(例如，用户交互的结果)。
111.虽然本说明书包含许多特定的实施细节，但是这些不应被解释为对任何发明或可要求保护的范围的限制，而应理解为对本文所述系统和方法的特定实施特定的特征的描述。在本说明书中在单独的实现方式的上下文中描述的某些特征也可以在单个实现方式中组合实施。相反，在单个实现方式的上下文中描述的各种特征也可以分别在多个实现方式中或以任何合适的子组合来实施。而且，尽管以上可以将特征描述为以某些组合起作用并
且甚至最初如此宣称，但是在某些情况下，可以从组合中去除所要求保护的组合中的一个或多个特征，并且所要求保护的组合可以针对子组合或子组合的变型。
112.类似地，虽然在附图中以特定顺序描绘了操作，但是这不应被理解为要求以所示的特定顺序或顺序执行这样的操作，或者执行所有示出的操作以实现期望的结果。在某些情况下，可以以不同的顺序执行权利要求中记载的动作，并且仍然实现期望的结果。另外，附图中描绘的过程不一定需要所示的特定顺序或连续顺序来实现期望的结果。
113.在某些情况下，多任务和并行处理可能是有利的。此外，在上述实现中的各种系统组件的分离不应被理解为在所有实现中都需要这种分离，并且应当理解，所描述的程序组件和系统通常可以集成在单个软件产品中或打包成多种软件产品。例如，数据处理系统805可以是单个模块、具有一个或多个处理模块的逻辑设备、一个或多个服务器或搜索引擎的一部分。
114.现在已经描述了一些说明性的实现方式和实施方式，很明显，前述内容是说明性的而不是限制性的，已经以示例的方式给出了。特别地，尽管本文呈现的许多示例涉及方法动作或系统组件的特定组合，但是可以以其他方式组合那些动作和那些组件以实现相同的目标。仅结合一种实现方式讨论的动作、组件和特征不旨在被排除在其他实现方式或其他实现方式中的类似角色之外。
115.这里使用的措词和术语是出于描述的目的，而不应被认为是限制性的。本文中“包括”、“包含”、“具有”、“含有”、“涉及”、“以
……
表征”及其变化形式的使用意在涵盖其后列出的项目、其等同物以及其他项目，作为仅由其后列出的项目组成的替代实现。在一种实现方式中，本文描述的系统和方法由所描述的元件、动作或组件中的一个或多个的每种组合来组成。
116.对本文中以单数形式提及的系统和方法的实现或元件或动作的任何引用也可以包括包括多个这些元件的实现，并且在本文中对任何实现或元件或动作的复数形式的任何引用也可以囊括仅包含一个元素的实现。单数或复数形式的引用无意将当前公开的系统或方法、它们的组件、动作或元件限制为单个或多个配置。对基于任何信息、动作或元件的任何行为或元件的引用可以包括其中该动作或元件至少部分基于任何信息，动作或元件的实现。
117.这里公开的任何实现方式可以与任何其他实现方式组合，并且对“一种实现方式”、“一些实现方式”、“替代实现方式”、“各种实现方式”、“一个实现方式”等的引用不一定是相互的排他性的并且旨在指示结合该实现方式描述的特定特征、结构或特性可以包括在至少一个实现方式中。如本文所使用的这样的术语不一定全部指代相同的实现。任何实现方式可以以与本文公开的各方面和实现方式一致的任何方式与任何其他实现方式相结合，包括在内或排除在外。
118.对“或”的引用可以解释为包括性的，以使得使用“或”描述的任何术语可以指示单个、一个以上以及所有所描述术语中的任何一种。
119.在附图、说明书或任何权利要求中的技术特征之后是附图标记的情况下，仅出于增加附图、说明书和权利要求的可理解性的目的而包括了附图标记。因此，附图标记或其不存在对任何权利要求要素的范围没有任何限制作用。
120.在此描述的系统和方法可以以其他特定形式来体现而不背离其特征。尽管本文提
供的示例涉及控制信息资源内容的显示，但是本文描述的系统和方法可以包括应用于其他环境。前述实现方式是说明性的，而不是限制所描述的系统和方法。因此，在此描述的系统和方法的范围由所附权利要求而不是前述描述来指示，并且在权利要求的等同含义和范围内的改变被包含在其中。

技术特征：
1.一种基于指纹匹配的媒体片段提取方法，包括：由具有一个或多个处理器的数据处理系统接收包括多个帧的媒体流；对于多个帧中的每个帧：数据处理系统基于指纹窗口值从多个帧中选择第二多个帧；数据处理系统对第二多个帧中的每一个进行散列以创建多个散列；数据处理系统将多个散列中的每一个截断以生成多个被截断的散列；数据处理系统将多个截断的散列进行级联以计算帧指纹值、与多个帧中的各个帧相关联的帧指纹值以及与各个帧相对应的时间戳；数据处理系统对每个计算出的帧指纹值进行聚合，以组装多个指纹；数据处理系统接收所述多个帧中与目标帧对应的目标时间戳；数据处理系统根据目标时间戳和指纹窗口值确定多个指纹中的目标指纹；数据处理系统检索第二多个指纹，所述第二多个指纹中的每个与第二媒体流中的帧相关联；数据处理系统将目标指纹与第二多个指纹中的每个指纹进行比较，以确定与第二媒体流中的位置相对应的匹配位置；数据处理系统将与小于目标时间戳的时间戳相关联的多个指纹中的第一指纹与第二多个指纹中的第二指纹进行匹配，确定下边界时间戳；数据处理系统将与大于目标时间戳的时间戳相关联的多个指纹中的第三指纹与第二多个指纹中的第四指纹进行匹配，确定上边界时间戳；数据处理系统根据所述下边界时间戳和所述上边界时间戳从所述第二媒体流中提取媒体片段；和由数据处理系统提供媒体片段以存储在数据库中。2.根据权利要求1所述的方法，其中，对每个计算出的帧指纹值进行聚合还包括：数据处理系统将多个指纹存储在数据库中。3.根据权利要求1所述的方法，其中，检索所述第二多个指纹还包括从数据库检索所述第二多个指纹。4.根据权利要求1所述的方法，其中，检索所述第二多个指纹包括：数据处理系统接收包括第三多个帧的第三媒体流；对于第三多个帧中的每一个：数据处理系统基于指纹窗口值从第三多个帧中选择第四多个帧；数据处理系统对第四多个帧中的每一个进行散列以创建第二多个散列；数据处理系统将所述第二多个散列中的每个均截断以生成第二多个被截断的散列；数据处理系统将第二多个被截断的散列级联起来以计算第二帧指纹值；和由数据处理系统聚合每个第二帧指纹值以组装第二多个指纹，每个第二帧指纹值与对应于第三多个帧中的各个帧的时间戳相关联。5.根据权利要求1所述的方法，其中，对所述第二多个帧中的每一个进行散列包括：使用局部敏感的散列算法对所述第二多个帧中的每一个进行散列。6.根据权利要求1所述的方法，其中，所述第二媒体流与所述第一媒体流相同。7.根据权利要求1所述的方法，其中将所述目标指纹与所述第二多个指纹中的每个指
纹进行比较以确定匹配位置还包括：数据处理系统计算目标指纹与第二多个指纹中的每个指纹之间的相似度值。8.根据权利要求7所述的方法，还包括：数据处理系统确定相似度值是否等于或大于相似度阈值；和数据处理系统响应于所述相似度值等于或大于所述相似度阈值，确定与所述第二媒体流中的位置对应的匹配位置。9.根据权利要求1所述的方法，其中，基于所述下边界时间戳和所述上边界时间戳从所述第二媒体流中提取媒体片段包括：数据处理系统基于所述下边界时间戳和所述上边界时间戳从所述第二多个指纹中提取第三多个指纹；和数据处理系统将第三多个指纹存储在数据库中。10.根据权利要求9所述的方法，还包括：由数据处理系统提供第三多个指纹。11.一种包括一个或多个处理器的系统，所述处理器被配置为：接收包括多个帧的媒体流；对于多个帧中的每个帧：基于指纹窗口值从多个帧中选择第二多个帧；对第二多个帧中的每一个进行散列以创建多个散列；将多个散列中的每一个截断以生成多个被截断的散列；将多个截断的散列进行级联以计算帧指纹值；聚合每个计算出的帧指纹值以组装多个指纹，每个计算出的帧指纹值与对应于多个帧中的各个帧的时间戳相关联；将每个计算出的帧指纹值与多个帧中的相应帧相关联；接收所述多个帧中与目标帧相对应的目标时间戳；根据所述目标时间戳和所述指纹窗口值确定所述多个指纹中的目标指纹；检索第二多个指纹，第二多个指纹中的每个与第二媒体流中的帧相关联；将目标指纹与第二多个指纹中的每个指纹进行比较，以确定与第二媒体流中的位置相对应的匹配位置；将与小于目标时间戳的时间戳相关联的多个指纹中的第一指纹与第二多个指纹中的第二指纹进行匹配，以确定下边界时间戳；将与大于目标时间戳的时间戳相关联的多个指纹中的第二指纹与第二多个指纹中的第三指纹进行匹配，以确定上边界时间戳；和提供用于存储在数据库中的媒体片段。12.根据权利要求11所述的系统，进一步被配置为：将多个指纹存储在数据库中。13.根据权利要求11所述的系统，进一步被配置为：从数据库中检索第二多个指纹。14.根据权利要求11所述的系统，进一步被配置为：接收包括第三多个帧的第三媒体流；
对于第三多个帧中的每一个：基于指纹窗口值从第三多个帧中选择第四多个帧；对第四多个帧中的每一个进行散列以创建第二多个散列；截断第二多个散列中的每个散列，以生成第二多个截断的散列；级联第二多个截断的散列以计算第二帧指纹值；和聚合每个第二帧指纹值以组装第二多个指纹，每个第二帧指纹值与对应于第三多个帧中的各个帧的时间戳相关联。15.根据权利要求11所述的系统，还被配置为：使用局部敏感散列算法对第二多个帧中的每一个进行散列。16.根据权利要求11所述的系统，其中，所述第一媒体流与所述第二媒体流相同。17.根据权利要求11所述的系统，进一步被配置为：计算目标指纹与第二多个指纹中的每个指纹之间的相似度值。18.根据权利要求11所述的系统，进一步被配置为：确定相似度值是否等于或大于相似度阈值；和响应于所述相似度值等于或大于所述相似度阈值，确定与所述第二媒体流中的位置对应的匹配位置。19.根据权利要求11所述的系统，还被配置为：基于所述下边界时间戳和所述上边界时间戳从所述第二多个指纹中提取第三多个指纹；和将第三多个指纹存储在数据库中。20.根据权利要求19所述的系统，还被配置为：提供第三多个指纹。
技术总结
本公开的至少一个方面针对基于指纹匹配来提取媒体片段的系统和方法。该方法可以包括：接收包括多个帧的媒体流；以及生成与每个帧相对应的多个指纹。该方法可以接收目标时间戳，并从多个目标指纹中确定与目标时间戳相对应的目标指纹。该方法可以检索候选指纹，每个候选指纹对应于候选媒体流中的帧。该方法可以将目标指纹与候选指纹进行比较以确定匹配的候选指纹。该方法可以在目标指纹之前和之后匹配与媒体帧相对应的指纹以确定感兴趣片段的上下边界。该方法可以基于边界提取感兴趣的片段并将其提供给相应的一方。段并将其提供给相应的一方。段并将其提供给相应的一方。


技术研发人员：A.奥扎斯肯特 Y.沃洛维奇
受保护的技术使用者：谷歌有限责任公司
技术研发日：2019.10.25
技术公布日：2021/6/24